Pith. sign in

REVIEW 1 major objections 4 minor 6 cited by

Flexible and Efficient Grammar-Constrained Decoding

T0 review · 1 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read GREATGRAMMA cuts grammar-constrained decoding preprocessing by 17.71x on average while keeping per-token mask computation at 5-32 ms.

desk verdict Genuinely new algorithmic design with a real engineering speedup, but the soundness proof rests on an unproven assumption that the paper's own limitations section admits is false in general. read the letter →

arxiv 2502.05111 v2 pith:2DPUOPBU submitted 2025-02-07 cs.CL cs.AI

Kanghee Park , Timothy Zhou , Loris D'Antoni This is my paper · ORCID
classification cs.CLcs.AI
keywords grammar-constraineddecodingcontext-freegrammartokenspannertablelexingtransducerpushdownautomatonmaximalmunchstructuredgenerationLLM
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Grammar-constrained decoding (GCD) lets an LLM only emit tokens that can still lead to a sentence of a given context-free grammar, but existing methods pay either seconds per token online or tens of minutes of offline preprocessing. This paper introduces GREATGRAMMA, a GCD algorithm that tries to get both: offline preprocessing that is on average 17.71x faster than one leading approach (SYNCODE) while keeping online mask computation at 5-32 ms per token. The key move is to precompute only the terminal sequences that are actually realizable by the LLM's subword vocabulary from each lexer state, rather than unrolling all possible terminal sequences. If right, GCD becomes practical for grammars that change frequently, such as per-example grammars in program synthesis or grammar prompting.

What carries the argument

The load-bearing object is the inverse token spanner table $T_{inv}(q,\alpha)$, which maps a lexer state $q$ and a realizable terminal sequence $\alpha$ to the set of LLM tokens that produce $\alpha$ from $q$. It is built from the composed transducer $T_{A\circ V}$, the sequential composition of the lexing transducer $T_A$ (characters to terminals under 1-lookahead maximal munch) with the detokenizing transducer $T_V$ (LLM tokens to characters). Together these let the decoder relate subword-vocabulary tokens to grammar terminals once, offline, and then answer mask queries online with table lookups plus a limited PDA analysis.

What would settle it

Enumerate all small lexer automata, terminal sets, and LLM vocabularies to find a state $q$ and terminal $T \in \mathrm{Prod}(q)$ for which some grammar-valid continuation $T\alpha$ cannot be produced by any character string from $q$; then simulate Algorithm 6 on a prefix that reaches $q$ and check whether it admits a token whose full character-level continuation has no valid lex-and-parse completion. A single such token would refute Theorem C.8 and the Lemma C.7 assumption.

Watch

Extended reading notes

Core claim

The paper's central claim is that grammar-constrained decoding can be made flexible and efficient by composing the grammar lexer with the LLM detokenizer into a single token-level lexing transducer $T_{A\circ V}$, extracting from it the set $Re_{A\circ V}$ of realizable terminal sequences, and storing the token-to-sequence relation in an inverse token spanner table. A stack-free FSA obtained by deleting stack operations from the parser PDA overapproximates accepted sequences, splitting terminal sequences into always-accepted and context-dependent. At each decoding step, Algorithm 6 starts from the always-accepted tokens and tests only context-dependent sequences against the current PDA stack, then unions the corresponding tokens from the inverse token spanner table. The paper proves completeness and soundness for this masking procedure, with the stated goal that the allowed tokens are exactly those whose concatenation can still lex and parse into a sentence of the grammar.

Load-bearing premise

Once a terminal can be produced from a given lexer state, any terminal continuation allowed by the grammar must also be producible, even though the greedy longest-match lexer decides character consumption one step at a time.

Editorial extensions

If this is right

  • Preprocessing a new grammar drops from thousands of seconds to tens or low hundreds of seconds on the tested tokenizers and grammars.
  • Per-token mask computation stays in the 5-32 ms range, comparable to the best existing online GCD tooling rather than the seconds-per-token cost of runtime-validating tools.
  • Only realizable terminal sequences are stored, so the inverse table is smaller than the full set of vocabulary-by-terminal-sequence combinations and can be built by straightforward transducer composition.
  • Because masks are computed by a checker inside the generic constrained-decoding loop, GREATGRAMMA can be dropped into existing GCD pipelines that target CFG constraints.
  • For program synthesis and grammar prompting, where the grammar changes with each request, the lower offline cost makes GCD a practical option.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • I infer that the inverse token spanner table could be reused across grammars that share a terminal set and lexer, since it depends only on the vocabulary and terminal regexes, not on the CFG.
  • I infer that the soundness claim should be read as conditional on the 1-lookahead maximal-munch assumption; for lexers needing parser context, such as Java generics with `>>`, the paper only sketches a nondeterministic extension, so the measured guarantees do not automatically transfer.
  • I infer that a brute-force fuzz test over small grammars and tokenizers, comparing Algorithm 6 masks against full lex-and-parse enumeration, would give a cheap empirical check of the unproved Lemma C.7 assumption.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper presents GREATGRAMMA, a grammar-constrained decoding algorithm that precomputes, offline, a token spanner table relating LLM subword tokens to sequences of lexer terminals, and then uses this table at decoding time to mask LLM tokens that cannot lead to a string in the target context-free grammar. The authors report a 17.71x average speedup in offline preprocessing over SYNCODE while maintaining state-of-the-art online per-token masking overhead, and they provide correctness theorems (completeness and soundness) for the masking algorithm in Appendix C. The implementation is concise (~900 lines of Python) and is evaluated against Outlines, SYNCODE, and XGrammar on Go, Java, and Python grammars with three tokenizers.

Significance. If the soundness guarantee is established, this is a practically valuable contribution: grammar-constrained decoding with low offline preprocessing cost enables frequent grammar changes, and the evaluation against third-party baselines is credible. The paper also has notable strengths: no free parameters are fitted, the comparison is against external tools, and the authors identify soundness bugs in a baseline implementation. However, the central advertised property--that the algorithm masks exactly the tokens with no valid completion--rests on an unproven and questionable lemma, so the current manuscript does not fully support its main claim.

major comments (1)
  1. [Appendix C, Lemma C.4 proof] The proof of Lemma C.4 contains a typo that obscures the argument: the sentence "this means Tk+1 must exist and be producible from the state q′, i.e., q′ ∈ Prod(q′)" should read "... i.e., Tk+1 ∈ Prod(q′)". As written, the proof claims a state is an element of a set of terminals, which is not meaningful. This should be corrected in revision.
minor comments (4)
  1. [Section 5 and Table 1] The paper states that GREATGRAMMA is implemented in 900 lines of Python in Section 5 but says 800 lines in the Conclusion; the discrepancy should be reconciled.
  2. [Appendix A, Algorithm 5] The identifier "spannar" in the algorithm signature and pseudocode is a typo for "spanner"; it appears in the input description and output table name.
  3. [Table 1] The caption should explain the meaning of the 'X' entries in the SYNCODE online-overhead columns; the main text mentions incorrect masking only in a sentence, and a reader scanning the table cannot infer what the symbol denotes.
  4. [Section 3.2, Definition 3.4] Definition 3.4 and Algorithm 4 use slightly different formulations: the definition refers to T ∈ Prod(q′), while Algorithm 4 computes T recognized at a state q′′ reachable from q′. The relationship between these two formulations should be stated explicitly to avoid ambiguity about whether the definition and the construction coincide.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: GREATGRAMMA's preprocessing and masking claims are benchmarked against external baselines and its correctness proofs target an external grammar-lexer definition.

full rationale

The paper's central claims are (1) 17.71x faster offline preprocessing than SYNCODE, (2) state-of-the-art online masking efficiency, and (3) sound masking with respect to a CFG and a maximal-munch 1-lookahead lexer. None of these claims is obtained by fitting parameters to data or by adopting as input the conclusion it later derives. The offline and online times are measured against third-party tools (Outlines, SynCode, XGrammar, with discussion of LLGuidance), and the tables (token spanner, inverse token spanner, always-accepted and context-dependent sequences) are constructed from the grammar, regex terminal definitions, and vocabulary by explicit automata and transducer constructions. The soundness theorem (Theorem C.8) and completeness theorem (Theorem C.5) are proven against the external definition LLex(G) = {w | Lex(w) = T1...Tk$ and T1...Tk$ in L(G)}; the proofs do not assume the theorems they prove. The self-citation to Park et al. (2024) appears only to justify not re-evaluating downstream task effectiveness and to mention possible integration, so it is not load-bearing for the algorithmic claims. The paper does contain an explicitly stated assumption in Lemma C.7: from a lexer state, if a terminal T is producible, then for any terminal continuation alpha there exists a vocabulary string producing T alpha. This is an unproven premise that the soundness guarantee depends on, and the Limitations section concedes maximal-munch cases such as Java generics where the assumption fails. That is a correctness risk concerning the validity of the guarantee, not a circular derivation: the paper does not derive Lemma C.7 from Theorem C.8 or from the evaluation results. The experimental setup is self-contained against external baselines, so no fitted input is later relabeled as a prediction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central algorithm depends on the greedy 1-lookahead lexer model, a vocabulary covering the character alphabet, and standard automata results. The most fragile item is Lemma C.7's unproved producibility extension assumption, which is ad hoc to the paper and load-bearing for soundness. The token spanner table is a data structure and is not counted as an invented physical entity.

assumptions (5)
  • domain assumption 1-lookahead lexing with maximal munch (Sec. 3.1, Definition 3.1)
    The soundness proofs and implementation require the greedy 1-lookahead lexer; grammars needing context-sensitive lexing, such as Java generics, are explicitly unsupported and named in the limitations.
  • ad hoc to paper Lemma C.7 extension assumption
    Assumes that from any lexer state, if a terminal T is producible then for every terminal continuation alpha a character string exists producing T followed by alpha. Stated without proof in Appendix C and used as a load-bearing step in the soundness theorem.
  • domain assumption Vocabulary contains all characters of the alphabet (Sigma subset of V)
    Sec. 3.2 relies on Sigma subset of V to claim Sigma* equals V*, ensuring that any lexer behavior can be simulated at the token level. This holds for byte-level subword tokenizers but is an assumption about the vocabulary.
  • standard math Standard PDA and FSA equivalence and stack invariance (Prop. 3.5)
    Background automata results that justify the over-approximation of PDA acceptance by stack-free FSA and the always-accepted token table.
  • domain assumption LARK LALR parser supports the target grammars
    The implementation uses LARK's LALR parser to build a deterministic PDA for parsing terminal sequences. This restricts the approach to grammars accepted by that parser generator, not all context-free grammars.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Flexible and Efficient Grammar-Constrained Decoding." pith.science (2026). https://pith.science/paper/2DPUOPBU

@misc{pith2026250205111,
  author       = {Pith},
  title        = {Pith review of: Flexible and Efficient Grammar-Constrained Decoding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2DPUOPBU}},
  note         = {Machine review of arXiv:2502.05111}
}
read the original abstract

Large Language Models (LLMs) are often asked to generate structured outputs that obey precise syntactic rules, such as code snippets or formatted data. Grammar-constrained decoding (GCD) can guarantee that LLM outputs matches such rules by masking out tokens that will provably lead to outputs that do not belong to a specified context-free grammar (CFG). To guarantee soundness, GCD algorithms have to compute how a given LLM subword tokenizer can align with the tokens used by a given context-free grammar and compute token masks based on this information. Doing so efficiently is challenging and existing GCD algorithms require tens of minutes to preprocess common grammars. We present a new GCD algorithm together with an implementation that offers 17.71x faster offline preprocessing than existing approaches while preserving state-of-the-art efficiency in online mask computation.

Figures

Figures reproduced from arXiv: 2502.05111 by the authors.

Figure 1
Figure 1. Illustrative example of the approach implemented in G [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 3
Figure 3. Detokenizing transducer for vocabulary V = {a, b, c, ab, ac, aba}. q0 q1 q B 2 q C 3 a:ϵ, aba:B ab:ϵ ac:ϵ EOS:$ b:ϵ c:ϵ b:ϵ, ab:B a:B, aba:BB ac:B EOS:B$ c:ϵ, ac:C ab:C a:C, aba:CB EOS:C$ [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. A determinized token-level lexing transducer [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Continuous Diffusion Models Can Obey Formal Syntax

    cs.LG 2026-02 conditional novelty 7.0 of 10

    Training-free gradient guidance, based on the exact regex-acceptance probability under the decoder's unigram distribution, lets continuous diffusion language models satisfy regular-expression constraints.

  2. Specification-Guided Synthesis of Deadlock-Free Communication Protocol Refinements with Large Language Models

    cs.SE 2026-07 conditional novelty 6.5 of 10

    Syntropy synthesises asynchronous multiparty session-type subtypes with 95.6–99.5% checker-accepted validity via LoRA fine-tuning and two-level constrained decoding.

  3. The Format Tax

    cs.CL 2026-04 conditional novelty 6.0 of 10

    Structured-output instructions alone impose a large accuracy tax on open-weight LLMs; decoupling freeform reasoning from formatting recovers most of it, while recent closed models largely avoid the tax.

  4. Constrained Adaptive Rejection Sampling

    cs.AI 2025-10 conditional novelty 6.0 of 10

    CARS is an exact constrained-sampling algorithm that prunes all constraint-violating token continuations encountered along sampled paths, monotonically raising acceptance rate while preserving the target conditional d...

  5. The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding

    cs.CL 2026-02 conditional novelty 5.0 of 10

    Draft-then-constrain decoding—first generate a free-form draft, then run format-constrained decoding conditioned on that draft—consistently improves structured-output accuracy across 1B–14B models.

  6. Precise Robot Command Understanding Using Grammar-Constrained Large Language Models

    cs.RO 2026-04 conditional novelty 4.0 of 10

    A fine-tuned LLM plus grammar canonicalizer and feedback loop yields higher valid robot-command rates on HuRIC than a fine-tuned LLM or grammar NLU alone.

Reference graph

Works this paper leans on

24 extracted references · 16 canonical work pages · cited by 6 Pith papers

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    and Riley, M

    Allauzen, C. and Riley, M. A pushdown transducer extension for the openfst library. In Implementation and Application of Automata: 17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012. Proceedings 17, pp.\ 66--77. Springer, 2012

    work page 2012

  3. [3]

    Sygus-comp 2018: Results and analysis, 2019

    Alur, R., Fisman, D., Padhi, S., Singh, R., and Udupa, A. Sygus-comp 2018: Results and analysis, 2019

    work page 2018

  4. [4]

    Crane: Reasoning with constrained llm generation, 2025

    Banerjee, D., Suresh, T., Ugare, S., Misailovic, S., and Singh, G. Crane: Reasoning with constrained llm generation, 2025. URL https://arxiv.org/abs/2502.09061

    arXiv 2025

  5. [5]

    Guiding llms the right way: fast, non-invasive constrained generation

    Beurer-Kellner, L., Fischer, M., and Vechev, M. Guiding llms the right way: fast, non-invasive constrained generation. 2024

    work page 2024

  6. [6]

    A general-purpose algorithm for constrained sequential inference

    Deutsch, D., Upadhyay, S., and Roth, D. A general-purpose algorithm for constrained sequential inference. In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), pp.\ 482--492, 2019

    2019

  7. [7]

    F., Cai, Y., Lai, R., Xu, Z., Zhao, Y., and Chen, T

    Dong, Y., Ruan, C. F., Cai, Y., Lai, R., Xu, Z., Zhao, Y., and Chen, T. Xgrammar: Flexible and efficient structured generation engine for large language models. arXiv preprint arXiv:2411.15100, 2024

    arXiv 2024

  8. [8]

    Floyd, R. W. Algorithm 97: Shortest path. Commun. ACM, 5 0 (6): 0 345, June 1962. ISSN 0001-0782. doi:10.1145/367766.368168. URL https://doi.org/10.1145/367766.368168

    arXiv 1962

Show all 24 references
  1. [9]

    Grammar-constrained decoding for structured NLP tasks without finetuning

    Geng, S., Josifoski, M., Peyrard, M., and West, R. Grammar-constrained decoding for structured NLP tasks without finetuning. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, Singapore, Decemb...

    2023

  2. [10]

    Jsonschemabench: A rigorous benchmark of structured outputs for language models, 2025

    Geng, S., Cooper, H., Moskal, M., Jenkins, S., Berman, J., Ranchin, N., West, R., Horvitz, E., and Nori, H. Jsonschemabench: A rigorous benchmark of structured outputs for language models, 2025. URL https://arxiv.org/abs/2501.10868

    2025 arXiv

  3. [11]

    llama.cpp, 2024

    Gerganov, G. llama.cpp, 2024. URL https://github.com/ggerganov/llama.cpp

    2024

  4. [12]

    Knuth, D. E. On the translation of languages from left to right. Information and control, 8 0 (6): 0 607--639, 1965

    1965

  5. [13]

    Automata-based constraints for language model decoding

    Koo, T., Liu, F., and He, L. Automata-based constraints for language model decoding. 2024. URL https://openreview.net/forum?id=BDBdblmyzY

    2024

  6. [14]

    Lundberg, S., Ribeiro, M. T. C., Edgar, R., Harsha-Nori, Cooper, H., Koch, P., King, N., Markus, Marawan, Moskal, M., Jenkins, S., cpcdoy, h-k nyosu, Chirculescu, M., Viggiano, D., X, H., Rafael, J., Bell, A. G., Zivontsis, S., sam rodriguez, Amemiya, R., SimFG, Peach, R., Hei...

  7. [15]

    and Yamada, H

    McNaughton, R. and Yamada, H. Regular expressions and state graphs for automata. IRE transactions on Electronic Computers, 0 (1): 0 39--47, 1960

    1960

  8. [16]

    guidance-ai/llguidance

    Moskal, M., Cooper, H., Pham, A., Lucato, D., Wolski, S., and Xiong, Y. guidance-ai/llguidance. 5 2025. URL https://github.com/guidance-ai/llguidance

    2025

  9. [17]

    Grammar-aligned decoding

    Park, K., Wang, J., Berg-Kirkpatrick, T., Polikarpova, N., and D'Antoni, L. Grammar-aligned decoding. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=5G7ve8E1Lu

    2024

  10. [18]

    Synchromesh: Reliable code generation from pre-trained language models

    Poesia, G., Polozov, A., Le, V., Tiwari, A., Soares, G., Meek, C., and Gulwani, S. Synchromesh: Reliable code generation from pre-trained language models. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=KmtVD97J43e

    2022

  11. [19]

    Sch \"u tzenberger, M. P. On context-free languages and push-down automata. Information and control, 6 0 (3): 0 246--264, 1963

    1963

  12. [20]

    lark-parser/lark

    Shinan, E., MegaIng, chanicpanic, Malard-Adam, J., Chilamkurthy, S., Lannigan, P., Emanuel, K., konstantin, evandrocoan, Chang, Y., Schreiner, H., ThatXliner, Chammas, N., ornariece, Rogdham, Makukha, M., Lauer, K., K., M., Rose, R., decorator factory, orcharddweller, Gritsenk...

  13. [21]

    R., Wu, C.-K., Tsai, Y.-L., Lin, C.-Y., Lee, H.-y., and Chen, Y.-N

    Tam, Z. R., Wu, C.-K., Tsai, Y.-L., Lin, C.-Y., Lee, H.-y., and Chen, Y.-N. Let me speak freely? a study on the impact of format restrictions on large language model performance. In Dernoncourt, F., Preo t iuc-Pietro, D., and Shimorina, A. (eds.), Proceedings of the 2024 Confe...

    2024 doi

  14. [22]

    Syncode: Llm generation with grammar augmentation, 2024

    Ugare, S., Suresh, T., Kang, H., Misailovic, S., and Singh, G. Syncode: Llm generation with grammar augmentation, 2024. URL https://arxiv.org/abs/2403.01632

    2024 arXiv

  15. [23]

    Grammar prompting for domain-specific language generation with large language models

    Wang, B., Wang, Z., Wang, X., Cao, Y., A Saurous, R., and Kim, Y. Grammar prompting for domain-specific language generation with large language models. Advances in Neural Information Processing Systems, 36, 2024

    2024

  16. [24]

    Willard, B. T. and Louf, R. Efficient guided generation for large language models. arXiv e-prints, pp.\ arXiv--2307, 2023

    2023

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.