acceptodds
Under review as a conference paper at ICLR 2027

CTRL-CFG: Tractable Constrained Decoding with LL(1) Grammars

Abstract

Language models often need to generate structured outputs that satisfy a context-free grammar such as JSON or Python. Steering a language model towards satisfying such a grammar requires marginalizing the probability that a future continuation will be grammatical. Hidden Markov models have proven effective as tractable surrogates for this marginalization, but existing methods focused on regular languages. We extend this line of work to LL(1) grammars, a widely used subset of context-free grammars. Unfortunately, even with a tractable surrogate, constrained generation with unambiguous grammars is still cubic time in the sequence length. We hence develop **CTRL-CFG**, a linear-time approximation that marginalizes only over a fixed look-ahead window. Experiments on program synthesis and molecule generation illustrate the potential of this approach as a step towards more broadly usable tractable constrained decoding.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
constrained generation, hidden markov models, tractable circuits, context-free grammars

Reviews

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

This paper tries to calculate the intractable membership probability in constrained decoding.

It extends the idea of using hidden Markov models (HMM) as a tractable surrogate to use context-free grammars (CFG) as constraints. It approximates CFG constraints for linear-time inference by only looking ahead a fixed number of tokens past the current prefix, requiring the 'prefix-unambiguity' only available in LL(1) grammars.

It calculates the probability conditioned on the prefix by using the remaining stack as the start symbol. It precomputes relevant probabilities for each non-terminal and every length, so at runtime it can be calculated efficiently.

Critical strengths
  • Novel and realistic idea of only considering a fixed number of look-ahead tokens for linear-time inference.
  • Clear writing, thorough theorital analysis, and full respect for existing work.
Critical weaknesses
  • The alignment between the terminals and tokenizers is not considered.
  • The effectiveness of this work (and similar work) depends on how well the HMMs can approximate the base LMs.
Questions for authors
  1. How well do the HMMs approximate the base LM?
  2. Can we get some experimental comparison with the concurrent work of Scribner et al. (2026), both in performance and speed?
  3. The GPU memory consumption of this work is nearly double the memory of LCD. Why?
  4. How much empirical performance gain can we get if we can use the full constraint instead of limited look-aheads? Or asked in another way, how well do limited look-heads empirically approximate the full constraint?
Reviewer_X7teOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

CTRL-CFG uses an HMM surrogate and bounded look-ahead to approximate grammar-conditioned LLM decoding beyond local token masking. It establishes the hardness of prefix marginalization for unambiguous CFGs and shows that LL(1) grammars permit an unambiguous prefix construction. Cached parser-stack probabilities and shared next-token marginal computation yield constraint-inference time linear in output length for fixed window, surrogate, and grammar sizes. Experiments cover molecule generation, regex synthesis, and text-to-SQL. The method improves the molecule validity-diversity trade-off; on Spider, execution accuracy increases from 62.18% to 63.52% over same-grammar LCD, and reaches 66.27% with SMC.

Critical strengths
  1. The paper provides a substantive theoretical and algorithmic contribution: it distinguishes full-string from prefix marginalization, identifies an LL(1) tractability condition, and develops a cached decoding algorithm with an explicit complexity bound. The presentation clearly connects these results to the practical decoding problem.

  2. Evaluation spans three structured-generation tasks and measures semantic quality as well as computational cost. The molecule results and integration with SMC provide useful evidence that bounded probabilistic look-ahead can improve the quality-cost trade-off beyond local masking.

Critical weaknesses

W1. Applicability depends on token-level LL(1) grammars and manual grammar-tokenizer alignment. The effort required to adapt new grammars or tokenizers, and the resulting coverage of the target languages, remain insufficiently characterized.

W2. Gains over same-grammar LCD are modest on regex synthesis and Spider relative to the added cost. On Spider, a 1.34-point accuracy gain increases latency from 26.11 to 40.59 ms/token and memory from 16.38 to 33.75 GB. Surrogate data generation and initialization further complicate the benefit for small workloads.

Questions for authors

Q1. What manual transformations are required to align each grammar with the tokenizer while preserving LL(1)? Do they restrict the supported language, and how much effort would a new tokenizer or grammar require?

Q2. What are the grammar-precomputation time and total surrogate preparation costs? Including these costs, for which workloads does CTRL-CFG offer a favorable quality-cost trade-off relative to LCD and rejection sampling?

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

The paper proposes CTRL CFG a constrained decoding method for LL(1) grammars. It uses an HMM as a tractable surrogate for the language model and approximates future grammatical validity by looking ahead at a fixed number of tokens. They evaluate the method on molecule generation, regex synthesis and text to SQL tasks.

Critical strengths

The paper addresses a relevant limitation of locally constrained decoding.

The motivation behind the look-ahead approximation is clearly presented.

Critical weaknesses

Some relevant references are missing, including SynCode [1], Guidance [2], Outlines [3], Pre3 [4], and SWYB [5]. These approaches also provide practical solutions for grammar constrained generation and are relevant baselines.

LL(1) grammars are strictly less expressive than deterministic context-free languages, which are a subset of context free languages. This restriction may limit the applicability of the proposed approach compared to methods that support more expressive grammars like DCFGs and CFGs.

The experiments do not report the percentage of generated samples that satisfy the target grammars. This is an important metric for evaluating the effectiveness of a grammar constrained decoding method.

[1] Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. 2025. Syncode: LLM generation with grammar augmentation. Transactions on Machine Learning Research.

[2] https://github.com/guidance-ai/guidance

[3] https://github.com/dottxt-ai/outlines

[4] Junyi Chen, Shihao Bai, Zaijun Wang, Siyu Wu, Chuheng Du, Hailong Yang, Ruihao Gong, Shengzhong Liu, Fan Wu, and Guihai Chen. 2025. Pre3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 11253–11267, Vienna, Austria. Association for Computational Linguistics.

[5] Vincenzo Collura, Karim Tit, Eleonora Giunchiglia, Mike Papadakis, and Maxime Cordy. 2026. Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance. In Findings of the Association for Computational Linguistics: EMNLP 2026, pages 37479–37492, Budapest, Hungary. Association for Computational Linguistics.

Questions for authors

Could the authors clarify the differences between their approach and the mentioned methods? If feasible, could they also include an empirical comparison to assess potential gains in terms of generation quality and/or efficiency?

Could the authors report the percentage of generated samples that satisfy the corresponding grammars for each task?

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

This paper extends the HMM surrogate of constrained decoding to LL(1) grammars which is a subclass of unambiguous grammars. They provide a tractable approximation of the probability that a given string ends up in the language of the grammar by using a k lookahead window together with an HMM based surrogate. Their decoding approach is shown to be linear in the length of the generated sequence. This methodology is tested in real-world settings such as molecule or text-to-SQL generation.

Critical strengths
  • The theory fits nicely and outlines the story well. They first show that given an unambiguous grammar, computing the probability that the next k tokens lie in the prefix of the language of the grammar is #P-hard outlining the need for a restriction to a more narrow class of grammars which is a relevant contribution in itself. A method is then provided for LL(1) grammars by observing that their prefix grammar is unambiguous. This makes the problem well motivated and shows that the authors appear to understand the limitations of their work.
  • Good optimisation technique for the decoding algorithm involving computing of all marginals using DP, caching probability matrices which brings the problem closer to practice.
Critical weaknesses
  • There does not appear to be a study of where the approximation error comes from. They vary k only on molecules (Fig. 2) and vary the HMM hidden state size only on regex (Table 1). The two parameters are never varied together in a single experiment.
  • The gains appear to be quite modest relative to the time and space costs. For text-to-SQL generation CTRL-CFG (63.52%) lies within one standard deviation of the Unconstrained method (62.99%) while time and memory requirements are respectively 1.6 and 2 times higher. It is true that with SMC added the gain is slightly higher though. Gains are modest as well for regex generation where unfortunately token efficiency is not reported which makes it also harder to compare the different methods on time costs. Also, a comparison with rejection sampling is missing for that experiment. However, it is true that the results on molecules are stronger.
Questions for authors
  • Table 2. In the text-to-SQL experiment unconstrained and rejection sampling have nearly the same accuracy (resp. 63% and 66%). Meanwhile rejection sampling is 5 times less time efficient. Is it because most samples are rejected on first try or because rejected samples are very long ? If it is because most samples fail the grammar on first try, then most unconstrained outputs aren’t valid SQL, so how can 63% unconstrained be correct?
  • Do the prompts provided to the LLMs ever include the grammar ? This could ensure a more fair comparison for the Unconstrained setting. Maybe it is not feasible in practice, but are format instructions and examples in the prompt ? For regex it appears to be the case but what about molecules and SQL ?
  • How does the gain provided by the method change when tested on a slightly better model ? Do Unconstrained or rejection sampling get more efficient / accurate ?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.