Professor @ucsd & Scholar @CodeMetal. Helps people write code they can trust
Loris D'Antoni
Loading...
Constrained Adaptive Rejection Sampling (CARS) exploits this information to incrementally build a representation of the constrained distribution. As more samples are processed, CARS learns to avoid large classes of failures, while still producing samples from the exact target distribution. 4/
Every interaction with the checker, whether a sample is accepted or rejected, provides information about the structure of the constrained space and where future failures are likely to occur. 3/
This work shows that the structure of constraint checkers can be exploited to dramatically accelerate sampling without sacrificing correctness; reminiscent of how conflict-driven clause learning transformed SAT solving by extracting and reusing information from failed search attempts. 6/
Paper: Constrained Adaptive Rejection Sampling
arxiv.org/abs/2510.01902
Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, and Loris D'Antoni
Why is it called a Large Language Model and not a Word Wide Web?
On some of our benchmarks, acceptance rates improve from roughly 1 valid sample out of every 100 attempts to nearly 1 out of every 3, while preserving exact sampling guarantees. 5/
In our ICML26 paper, we show that autoregressive constraint checkers reveal rich information that can be used to drastically reduce the rejection rate any autoregressive sampling algorithm. 2/
Getting LLMs to generate samples that satisfy constraints is a fundamental problem in machine learning. The standard approach is rejection sampling: generate a sample, check whether it satisfies the constraint, and if not, try again. 1/
