💬 NLP

Constrained Adaptive Rejection Sampling

The paper introduces Constrained Adaptive Rejection Sampling (CARS), a method that enhances the sample efficiency of language model generation under strict constraints by adaptively pruning invalid continuations via a trie, thereby preserving the original distribution while improving acceptance rates and diversity compared to existing greedy or standard rejection sampling approaches.

Original authors: Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

Published 2026-06-04

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to create a new recipe, but you have a very strict rule: the dish must contain exactly three ingredients, and they must be in a specific order. You have a brilliant sous-chef (the Language Model) who is great at suggesting ingredients, but they don’t always follow your strict rules. They might suggest "salt, pepper, and... a whole watermelon?" which breaks your rule.

This paper introduces a new technique called CARS (Constrained Adaptive Rejection Sampling) to help you get perfect recipes from your sous-chef without wasting time or ruining the flavor.

The Problem: Two Bad Options

Before CARS, chefs had two main ways to deal with this problem, and both were annoying:

The "Trash Can" Method (Rejection Sampling): You ask the sous-chef for a recipe. If it’s wrong (e.g., has a watermelon), you throw it in the trash and ask for another. You keep doing this until you get a valid recipe.
- The downside: You waste a lot of time and ingredients. If the sous-chef is bad at following rules, you might throw away 99 out of 100 recipes.
The "Forced Hand" Method (Greedy Constrained Decoding): You grab the sous-chef’s hand and physically force them to pick only valid ingredients. If they try to pick a watermelon, you stop them and force them to pick salt instead.
- The downside: The recipes become boring and unnatural. By forcing the sous-chef, you change their creative style. The final dish might be "valid," but it doesn’t taste like the sous-chef’s true style anymore. It’s like forcing a jazz musician to play only classical music—they’ll play correctly, but it won’t sound like jazz.

The Solution: CARS (The Smart Notebook)

CARS is like giving the sous-chef a smart notebook that learns from mistakes.

Here is how it works:

Start Fresh: You ask the sous-chef for a recipe.
Learn from Mistakes: If the sous-chef suggests "salt, pepper, watermelon," you reject it. But instead of just throwing it away, you write in the notebook: "Hey, if we start with 'salt, pepper,' we should never pick 'watermelon' next."
Adapt: Next time, if the sous-chef starts with "salt, pepper," the notebook automatically blocks "watermelon" from even being considered. The sous-chef is forced to pick something else, but only because we know that path leads to a dead end.
Keep the Style: Crucially, CARS doesn’t force the sous-chef to change their personality. It just removes the invalid options. The remaining options are still chosen based on the sous-chef’s original preferences. So, the final recipe is valid (follows the rules) AND authentic (sounds like the sous-chef).

Why CARS is Better

It Gets Smarter Fast: In the beginning, you might still get some bad recipes. But with every mistake, the notebook gets smarter. The paper shows that CARS learns very quickly. After just a few tries, it stops suggesting the same types of errors.
It Saves Time: Because it learns from past mistakes, it wastes far less time than the "Trash Can" method.
It Keeps the Flavor: Unlike the "Forced Hand" method, CARS doesn’t distort the sous-chef’s style. The recipes are statistically identical to what the sous-chef would have made if they had perfectly followed the rules from the start.

Real-World Examples from the Paper

The authors tested CARS on three tricky tasks where rules are strict:

Program Fuzzing (Testing Software): Imagine trying to break a computer program by feeding it weird code. The code must be syntactically correct (like proper grammar) to be useful. CARS generated valid, diverse code much faster than other methods, helping testers find bugs more efficiently.
Molecule Generation (Chemistry): Chemists want to create new molecules that are stable and have specific properties. The "grammar" here is the rules of chemistry (atoms must bond correctly). CARS created valid, diverse molecules with less wasted computation than other methods.
Text-to-SQL (Database Queries): Asking an AI to write database queries. The query must be perfect SQL code. CARS produced correct queries more efficiently than other exact methods, and more accurately than approximate methods that sometimes "faked" the rules.

The Bottom Line

CARS is a way to get the best of both worlds: strict rule-following without losing creativity. It’s like having a sous-chef who learns from their mistakes in real-time, ensuring every dish is both delicious and perfectly compliant with your dietary restrictions.

Technical Summary: Constrained Adaptive Rejection Sampling (CARS)

Problem Statement
The paper addresses the challenge of constrained generation in Language Models (LMs), where outputs must satisfy strict semantic or syntactic constraints (e.g., valid programming syntax, chemical structures). Existing methods face a fundamental trade-off between fidelity (sampling from the exact conditional distribution $P_L$ ) and efficiency (computational cost per valid sample):

Exact Methods: Rejection Sampling (RS) preserves fidelity but is inefficient, discarding the vast majority of invalid candidates. Adaptive Rejection Sampling (ARS) improves RS by avoiding previously seen invalid samples but still struggles with high rejection rates in structured domains.
Approximate Methods: Greedy Constrained Decoding (GCD) is efficient but distorts the LM’s distribution, potentially degrading downstream performance. Asymptotic methods (e.g., MCMC, SMC) converge to the correct distribution only in the limit, offering no principled stopping rule and suffering from biased early samples.

The authors argue that domains requiring diverse, constraint-satisfying samples (e.g., program fuzzing, molecular discovery) need an algorithm that is both exact and amortized-efficient.

Methodology
The authors propose Constrained Adaptive Rejection Sampling (CARS), an exact sampling algorithm that improves upon ARS by adaptively pruning entire families of invalid continuations.

Core Mechanism: CARS maintains a set $W$ of invalid prefixes, stored in a trie structure. Unlike ARS, which only records specific rejected sequences, CARS identifies all continuations of partial prefixes that inevitably violate the constraint.
Adaptive Reweighting: The algorithm defines a reweighted distribution $R_W$ that subtracts the probability mass of sequences extending any prefix in $W$ . This ensures that once a prefix is proven invalid, it is never revisited. The acceptance rate improves monotonically as $W$ grows.
Update Strategy: Upon generating a sample $w$ $w$ , CARS updates $W$ $W$ by adding:
- The shortest prefix of $w$ that violates the constraint.
- All invalid continuations of every proper prefix of $w$ (i.e., for any prefix $u$ of $w$ and token $a$ such that $ua \notin \text{prefix}(L)$ , $ua$ is added to $W$ ).
Exactness: The paper proves (Theorem 3.2) that CARS samples unbiasedly from the true constrained distribution $P_L$ . It also establishes (Theorem 3.3) that the expected probability mass removed per sample is non-increasing, suggesting diminishing returns that allow for practical heuristics (e.g., freezing the trie).

Key Contributions

Algorithm: Introduction of CARS, which combines the distributional fidelity of RS with the efficiency of constraint-aware decoding by leveraging the structure of constraints (specifically prefix-checkable constraints like CFGs).
Theoretical Guarantees: Proof of soundness (exact sampling) and monotonic improvement in acceptance rates.
Empirical Validation: Demonstration that CARS achieves higher efficiency and sample diversity than both exact baselines (RS, ARS) and approximate baselines (GCD, MCMC, AWRS) across multiple domains.

Results
The authors evaluate CARS on three primary benchmarks:

Grammar-based Fuzzing (JSON, SQL, XML):
- CARS significantly outperforms RS and ARS in sample efficiency. For example, in XML fuzzing without grammar prompts, CARS required ~440 generations to produce 100 valid samples, whereas RS and ARS failed within the 2,000-sample budget.
- CARS achieved higher line coverage (~~7,985 lines) compared to GCD (~~7,115) and MCMC (~7,965), demonstrating that distributional fidelity translates to better downstream exploration.
- CARS exhibited lower KL divergence (better fidelity) than approximate methods like MCMC and GCD.
Molecular Synthesis (SMILES generation):
- CARS required 4.3× fewer samples than RS and 1.3× fewer than ARS to generate 100 valid molecules.
- It maintained high validity and diversity, matching or exceeding exact methods while being far more efficient.
- KL divergence was 1.5× lower than MCMC and 1.8× lower than AWRS.
Text-to-SQL Generation (Spider dataset):
- CARS achieved the highest execution accuracy (0.578) among exact methods, outperforming GCD (0.525) by 5.3%.
- It required 1.85× fewer samples than RS and 1.28× fewer than ARS.
- Compared to approximate methods (MCMC, AWRS), CARS achieved similar accuracy with 9× fewer samples.

Significance and Claims
The paper claims CARS sets a new state-of-the-art for sampling from the exact LM constrained distribution by resolving the fidelity-efficiency trade-off. It is particularly effective when constraints are prefix-checkable and restrictive (e.g., allowing only 1–20 tokens out of 128K+ at certain positions), where CARS yields 3.3–7× improvements over ARS. The authors note that CARS struggles when invalid inputs do not share prunable prefixes (e.g., constraints dependent on late-position tokens), in which case approximate methods may remain more practical. The work positions CARS as a principled extension of ARS, utilizing auxiliary signals (the trie) to accelerate exact statistical procedures without sacrificing formal guarantees.

The Problem: Two Bad Options

The Solution: CARS (The Smart Notebook)

Why CARS is Better

Real-World Examples from the Paper

The Bottom Line

More like this