- 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
- 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.
- 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
- 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.
- 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
- 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?
- 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
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).
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.