acceptodds
Withdrawn from ICLR 2027

Is Exact Constrained Sampling Right for You?

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Constrained sampling lets a language model (LM) produce outputs that satisfy a grammar or another hard constraint, and how it is done matters: masking invalid tokens one step at a time distorts the LM's distribution over valid outputs, which harms applications that need that distribution, such as program fuzzing and molecule generation. Recent work samples from the correct constrained distribution either approximately or exactly, and the exact methods—adaptive rejection sampling (ARS) and the recent Constrained Adaptive Rejection Sampling (CARS)—are preferable when their cost is affordable. But nothing tells a practitioner in advance whether it is, or which exact method to use. We analyze the cost of these methods exactly. Over a run, ARS pays one rejected LM call for every possible first mistake of the LM, while CARS pays at most one per prefix, and CARS is optimal among all strategies that learn only from their own draws. The speedup of CARS over ARS is bounded below by two masses read off the trie CARS builds: the light invalid mass, too unlikely for ARS to have drawn, and the unreachable mass, at prefixes too rare for CARS to have reached. Our analysis is practical: the measured costs fall inside the predicted range on every task, tight when the run has seen most of the ways the LM violates the constraint.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
constrained decoding, adaptive rejection sampling, convergence rates

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_KtCZOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper analyzes the cost of exact constrained sampling with ARS and CARS. An atom-based decomposition and shared-stream coupling yield exact formulas for expected rejection counts and the corresponding LM-call costs. The analysis explains when CARS offers substantial speedups through bounds involving reachable prefixes and low-probability invalid atoms, and establishes its optimality within a restricted class of prefix-based methods that learn only from their own draws. The paper also investigates whether partial sampling runs provide useful predictions of subsequent costs. The results are evaluated on a synthetic example and nine grammar-constrained benchmarks, with additional comparisons across multiple language models and partial Lean formalization of the theoretical analysis.

Critical strengths
  1. The atom-based decomposition and shared-stream coupling yield interpretable closed-form expressions for expected rejection counts. This goes beyond empirical comparisons and explains why CARS can be substantially more efficient than ARS.
  2. The reachable-prefix and light-atom bounds connect speedup to the structure of the constraint and the LM’s error distribution. This provides practical guidance for deciding whether exact constrained sampling is worthwhile, supported by experiments across multiple grammars and model checkpoints.
Critical weaknesses
  1. The empirical evidence does not fully support the paper’s practical prediction claims. The evaluation uses a limited set of grammar-based benchmarks and measures primarily LM-call counts. More importantly, the early cost predictions rely on finite-sample estimates, but the statistical reliability of the reported ranges has not been established. Some ranges are very wide, so simply containing the observed cost does not demonstrate accurate advance prediction.
  2. The practical affordability claims need stronger support beyond LM-call counts. This metric does not capture differences in sequence length, oracle/trie overhead, or memory use. Appendix G reports no wall-clock measurements and notes that the JSON CARS trie requires approximately 50 GB of host memory. While these limitations do not undermine the theoretical rejection-count results, they leave unclear when fewer LM calls translate into an affordable sampling procedure.
Questions for authors
  1. How do the reported early cost-prediction ranges perform across independent pilot seeds when uncertainty in P(L) and P(v|L) is included? In particular, what are their empirical coverage rates and relative widths, and does the claim that a small fraction of a run is sufficient remain valid under this evaluation?
  2. Could the authors provide representative wall-clock and peak-memory measurements, with a breakdown of LM inference and oracle/trie overhead? In particular, how does the approximately 50 GB trie requirement on JSON affect practical feasibility, and under what conditions are LM-call counts a reliable basis for deciding whether exact sampling is affordable?
2 comments

Prediction accuracy. The reviewer is right that falling inside a wide range does not establish accurate prediction. The ranges use estimated probabilities without accounting for their uncertainty and are not calibrated confidence intervals.

Pilot evaluation. We ran a new evaluation using 20 independent pilots per condition at fixed budgets of 10, 25, 50 and 100 calls, against nine separate evaluation seeds.

Coverage and width. At 100 calls, the ranges contain the held-out mean in 9/20 SLIA pilots and 8/20 XML pilots, with average widths of 5% and 73% of the respective evaluation means. Other ranges can be much wider. These results do not establish that a specific small fraction of a run always suffices across tasks, but show strong signal.

Wall time and memory. The corrected L40S cohort reports sampling time and memory from a fresh process per run. For 100 valid outputs, CARS/ARS average 115/999 calls but 11.5/11.1 seconds on SLIA, and 442/2,859 calls but 19.5/15.6 minutes on XML (ten CARS seeds, five ARS seeds).

These timing comparisons concern tasks where both methods reach 100 valid outputs. On JSON and SQL, CARS reaches that target while ARS exhausts even our larger 8,000-call budget.

Both methods heavily cache model outputs at visited prefixes. This makes many additional ARS calls cheap: 88% of its XML rejections require no new model forward pass. CARS and ARS perform almost the same number of forward passes (34,080 versus 33,995 on average), despite the large difference in sampling-call counts. Cache reuse therefore explains why the call-count savings do not translate into proportional wall-time savings.

JSON averages 23.6 minutes, including 18.4 minutes (78%) in model-forward work. The remaining 5.1 minutes combine grammar, trie, sampling and instrumentation work. Model loading is excluded. Across ten JSON seeds, peak observed process RAM during sampling is 13.05 GiB and peak GPU allocation is 15.12 GiB. This measures the process footprint; it does not isolate trie memory.

Thank you for the additional experiments and clarifications. The independent pilots and runtime measurements are helpful, and I continue to appreciate the theoretical analysis. However, my main concerns remain. The pilot results do not yet establish reliable advance cost prediction: the ranges contain the held-out mean in only 9/20 SLIA pilots and 8/20 XML pilots at 100 calls. The timing results also show that substantially fewer sampling calls do not necessarily translate into lower runtime, as CARS is slightly slower on average on both tasks. This limits the practical affordability conclusions that can be drawn from call-count optimality. Overall, the response improves the empirical characterization, but the practical forecasting claims remain insufficiently supported. I therefore maintain my rating of 2 (weak rejection).

Reviewer_71nZOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper is a theoretical analysis of two exact constrained sampling methods for language models. Adaptive rejection sampling (ARS) and Constrained Adaptive Rejection Sampling (CARS, Parys et al. 2026). The authors split invalid outputs into "atoms," one for each possible first mistake the model can make. That gives closed-form expressions for how many rejected LM calls each method needs. ARS pays one rejection for every possible first mistake, while CARS pays at most one per prefix. They also show CARS is optimal among strategies that learn only from their own draws, and bound the speedup of CARS over ARS using quantities read off the trie CARS builds. Experiments on nine tasks from the CARS paper check whether one CARS run can predict the cost of other runs.

Critical strengths
  • The paper attemtps to answer a question the CARS authors left open. How much faster CARS is than ARS, and when is an important questions. The atom view is clean and makes the difference between the two methods easy to understand.

  • The theory is careful and the math looks correct. The running example is worked through in detail, and the paper is clear about which proofs are machine-checked in Lean (I haven't validated the artifacts myself) and which are on paper only

  • Sorting constraints into four kinds, format, tight grammar, loose grammar, global, gives useful intuition for when exact sampling is cheap and when it is not.

Critical weaknesses
  • I'm not convinced of the practical value of the paper. The paper says it helps practitioners decide (a) which exact method to use and (b) whether exact sampling is affordable at all. On (a), the paper itself proves CARS is never worse than ARS, so there is not a real choice to make (you would just always use CARS?). On (b), the main prediction needs a partial CARS run. It does settle early, which is nice but CARS already tracks how much probability is still in play, so a simple estimate based on the current acceptance rate is also available. The paper never compares its prediction with that simpler estimate, so I cannot tell how much the theory adds in practice. The "predicting without a run" mode in the appendix still needs a short run to estimate the valid probability, costs one forward pass per prefix it lists, and is only evaluated in one appendix table. Also the main practical advice, that approximate methods like SMC or MCMC are the better choice for global constraints is not evaluated.

  • To me the contributions of the paper feels incremental. The paper reads as a follow-up to the CARS paper rather than a standalone one. There is no new algorithm, and it uses the same benchmarks, prompts and code. Some of the theory is also fairly direct. For example, CARS being optimal is close to true by construction, since it already records everything the grammar checker can say about each draw.

  • The experiments are small and the predictions are often loose. There is one task per benchmark family, 10 CARS runs and 5 ARS runs per task, and one main model (Llama-3.1-8B). The predictions are tight on SyGuS, but on JSON, SQL and the grammar-in-prompt tasks the ranges span one to several orders of magnitude, so "falls inside the range" doesn't say much there. A few predictions also miss like the BV4 ARS cost falls outside its range and the speedup bound gives 1 on SMILES where the measured speedup is 1.8

Questions for authors
  • Does the cost prediction do better than a simple baseline that extrapolates the acceptance rate from the first few percent of the run?

  • In practice many users sample with top-k or top-p, which removes the long tail of unlikely tokens that seems to drive most of CARS's advantage over ARS. How do the predicted and measured speedups change under truncated sampling? how do the results change with more instances per benchmark family and with larger models?

  • Beyond choosing between ARS and CARS, what decision would a practitioner make differently because of this analysis?

1 comment

Contribution. Our main contribution is that we characterize the fundamental call-count limit for exact samplers that learn by excluding invalid continuations at prefixes of their own draws. CARS attains this limit. Theorem 3.1 gives the exact expected rejection count for any requested number of valid samples. This is the central result; the constraint classification provides supporting intuition.

Practical value. What we have is useful for estimating the expected number of calls needed to obtain a given number of valid samples and whether that request fits a budget. Extrapolating the acceptance rate from a short preliminary run assumes it stays fixed; our formulas account for how CARS improves as it learns.

Prediction accuracy. The reviewer is right that falling inside a wide range does not establish accurate prediction. The ranges use estimated probabilities without accounting for their uncertainty and are not calibrated confidence intervals.

Pilot evaluation. We ran a new evaluation using 20 independent pilots per condition at fixed budgets of 10, 25, 50 and 100 calls, against nine separate evaluation seeds.

Acceptance-rate baseline. Compared with acceptance-rate extrapolation, at 100 calls the range midpoint reduces mean relative error from 99% to 22% on SMILES and from 20% to 6% on BV4, gives similar error on SLIA, and higher error on the remaining six conditions.

Diagnostic cost. The reviewer is right that the appendix diagnostic has a computational cost: it evaluates prefixes and estimates the valid-output probability. Whether this diagnostic saves computation remains untested.

Specific bounds and breadth. ARS on BV4 falls outside its estimated range. The original SMILES mass-ratio bound is uninformative. This ratio is distinct from adaptive speedup, which compares expected total calls from Theorem 3.1 at the same valid-sample target.

Top-k/top-p. The formulas apply when truncation defines the base distribution before grammar constraints are applied. All methods must target that same distribution. We have not measured the resulting change in speedup.

SMC/MCMC. The original CARS paper already reports MCMC producing the requested samples where CARS exhausts its budget (Parys et al., Table 8). This is why we recommend considering approximation when exact sampling is too costly and distributional bias is acceptable.

Reviewer_5dSFOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This submission revisits CARS, an existing method for sampling outputs that satisfy a grammar while preserving a language model's relative probabilities over valid outputs. CARS uses grammar checks at sampled prefixes to rule out invalid continuations and reduce wasted draws.

The submitted paper adds exact formulas for expected rejections and related bounds, and evaluates cost predictions on the earlier work's benchmarks. This work mainly quantifies behavior already explained in the earlier paper, without demonstrating better sampling decisions.

Critical strengths
  • Theorem 3.1 provides an exact cost analysis beyond Parys et al.'s qualitative comparison.
Critical weaknesses
  1. The cost formulas are new, but their significance is unclear. The main explanation of when CARS helps already appears in Parys et al. (Sec.4.4). The submission does not demonstrate better sampling decisions or substantial additional insight.

  2. I see little new research contribution in most of this formalization. Sec.H mostly lists elementary counting, survival bounds and algebraic consequences (easy to formalize); the main cost theorem and the connection to CARS remain unformalized.

  3. The practical claims are overstated. SQL's forecast spans 236–450,000 calls against 2,901 observed (Table 2). Being within 5% of a range does not establish 5% prediction accuracy. Also, the ranges are too narrow because they do not consider the sampling uncertainty in P(L)P(L) and P(v∣L)P(v\mid L). There is no simple pilot baseline.

  4. Appendix C equates pε(W)/P(L)p_\varepsilon(W)/P(L) with expected next-sample cost, but that assumes a frozen proposal. With equiprobable 0$ (valid) and 1$ (invalid), Speedup(1)=3/2\mathrm{Speedup}(1)=3/2, but the expected next-sample cost ratio is 5/45/4. The mass bounds are unaffected, but the cost interpretation needs correcting.

Questions for authors
  1. What substantive insight or sampling decision does the analysis enable beyond the earlier paper's guidance or a short pilot?

  2. You disclose substantial AI use. To be sure, automatic research might sometimes yield valuable results that should be published (like the recent refutation of ETH). But I'm curious: what were the specific human contributions to this paper? (That is, what would the Human Use Statement say?) You say that you "directed" or "reviewed" the AI work, but not that you changed any of it. Stylistically much of the writing still sounds like AI (including the AI Use Statement itself), suggesting that the final form of the arguments didn't emerge through careful human discussion and revision of the prose.

  3. Why does JSON take 700 calls here versus about 130 in Parys et al., Table 8?

1 comment

Contribution. Our main contribution is that we characterize the fundamental call-count limit for exact samplers that learn by excluding invalid continuations at prefixes of their own draws. CARS attains this limit. Theorem 3.1 gives the exact expected rejection count for any requested number of valid samples. This is the central result; the constraint classification provides supporting intuition. What we have is useful for estimating the expected number of calls needed to obtain a given number of valid samples and whether that request fits a budget. Extrapolating the acceptance rate from a short preliminary run assumes it stays fixed; our formulas account for how CARS improves as it learns.

Prediction accuracy. The reviewer is right that falling inside a wide range does not establish accurate prediction. The ranges use estimated probabilities without accounting for their uncertainty and are not calibrated confidence intervals.

Pilot evaluation. We ran a new evaluation using 20 independent pilots per condition at fixed budgets of 10, 25, 50 and 100 calls, against nine separate evaluation seeds.

Acceptance-rate baseline. Compared with acceptance-rate extrapolation, at 100 calls the range midpoint reduces mean relative error from 99% to 22% on SMILES and from 20% to 6% on BV4, gives similar error on SLIA, and higher error on the remaining six conditions.

Appendix C and Lean. The reviewer is right: the mass ratio is 3/2, while the adaptive next-sample cost ratio is 5/4. The correct interpretation is that these bounds describe proposal mass and costs with learning frozen. Actual adaptive speedup follows from comparing Theorem 3.1's expected total calls for the same number of valid outputs. The exact cost and optimality results are unchanged.

Human contribution. The authors defined the problem: We wanted to understand when CARS helps and by how much. The initial AI argument was weak and incomprehensible. We reworked it until the analysis was tight, made intuitive sense, and could be stated cleanly: the process took tens of iterations (many more days) between getting proposals of analysis from AI and us reworking it. We also revised the formalization with the goal of obtaining quantities that can be estimated from a few runs. The original disclosure undersold what we did.

JSON. We confirmed with the CARS authors that the discrepancy comes from a reporting error in the original paper and that our JSON call counts are correct. The released Llama JSON runs take 600, 625, and 681 calls for 100 valid outputs, with the same prompt and grammar as ours.

We also fixed a cache-handling bug in our implementation and corrected the recorded statistics. A matched JSON check took 792 calls before the changes, 742 with the cache fix alone, and 685 with all changes. Across ten corrected seeds, the mean is 712 calls for 100 valid outputs (standard deviation 48), with no truncations.

Comments on the paper

1 comment
AuthorsOpenReview ↗

# Shared reviewer questions

1. What does the analysis add, and what practical decision does it support?

Shared by R1 and R2.

Our main contribution is that we characterize the fundamental call-count limit for exact samplers that learn by excluding invalid continuations at prefixes of their own draws. CARS attains this limit. Theorem 3.1 gives the exact expected rejection count for any requested number of valid samples. This is the central result; the constraint classification provides supporting intuition.

What we have is useful for estimating the expected number of calls needed to obtain a given number of valid samples and whether that request fits a budget. Extrapolating the acceptance rate from a short preliminary run assumes it stays fixed; our formulas account for how CARS improves as it learns.

2. Do the reported ranges establish accurate prediction?

Shared by R1, R2 and R3.

The reviewers are right that falling inside a wide range does not establish accurate prediction. The ranges use estimated probabilities without accounting for their uncertainty and are not calibrated confidence intervals. We ran a new evaluation using 20 independent pilots per condition at fixed budgets of 10, 25, 50 and 100 calls, against nine separate evaluation seeds.

R1 and R2 also ask for a comparison with acceptance-rate extrapolation:

Compared with acceptance-rate extrapolation, at 100 calls the range midpoint reduces mean relative error from 99% to 22% on SMILES and from 20% to 6% on BV4, gives similar error on SLIA, and higher error on the remaining six conditions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.