Pith. sign in

REVIEW 3 major objections 6 minor 45 references

Efficient Grammar-Constrained Decoding via Parser Stack Classification

T0 review · 3 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read By merging the acceptance conditions of every vocabulary token into a single automaton over parser stacks, PSC computes the full legal-token mask in one stack pass per decoding step, with cost independent of vocabulary size.

desk verdict PSC has a genuinely fast practical idea and credible experiments, but its headline theorem about finite-state epsilon-closure is unproven and likely false for general DCFGs. read the letter →

arxiv 2608.03065 v1 pith:5LMMHDGY submitted 2026-08-04 cs.SE

Yongmin Li , Yihong Dong , Jia Li , Ge Li This is my paper · ORCID
classification cs.SE
keywords grammar-constraineddecodingparserstackclassificationfinite-stateautomatadeterministicpushdownstructuredoutputgenerationvocabularymaskingLLMcode
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 makes an LLM's output respect a context-free grammar by masking illegal tokens at every generation step, but the usual way to build that mask is to ask the parser, for every one of the model's 100,000-plus tokens, whether that token is legal — work that grows linearly with the vocabulary. This paper proposes Parser Stack Classification (PSC), which inverts the question: during preprocessing it computes, for each token, the exact condition on the parser stack under which the token is legal, and merges all these conditions into a single automaton that classifies stacks. At generation time the automaton is run once over the current stack and the full mask comes out, so the per-step cost is independent of vocabulary size. On programming-language grammars the paper reports mask computation up to 700 times faster than the fastest comparison baseline, and end-to-end constrained throughput close to unconstrained decoding.

What carries the argument

The load-bearing object is the combined classifier automaton $\mathcal{A} = \bigcup_{v,q} \bigcup_{w \in R_q(v)} I_q A_w I_v$ (Equation 9): a minimized deterministic finite-state automaton over the alphabet of lexer states, stack symbols, and vocabulary tokens, with every state pre-mapped to the vocabulary mask it implies. Each per-token automaton $A_w$ derives from the transducer $P_w = P_\varepsilon \circ \tilde{P}_{w_1} \circ P_\varepsilon \circ \dots \circ P_\varepsilon \circ \tilde{P}_{w_n} \circ P_\varepsilon$, which simulates the parser consuming the terminal sequence $w$ from an arbitrary stack and returning the stabilized stack. The critical component is $P_\varepsilon$, the epsilon-closure transducer that fires all needed epsilon transitions to stabilize a stack; finiteness of its state set is what keeps the whole construction finite, and is the property the paper justifies by the parser's termination. Theorems 1 through 3 chain together to show the transducer simulation is exact and the resulting acceptance language is regular, so the online step reduces to a single traversal of the stack plus a table lookup.

What would settle it

Run the offline construction (Algorithm 1) on a deliberately engineered terminating grammar whose epsilon-transitions push symbols that enable further epsilon-transitions, and observe whether the $P_\varepsilon$ construction terminates; if the number of closure states grows without bound, Theorem 1's finiteness claim fails. A complementary check: measure PSC's per-step mask time with two very different vocabulary sizes — the central claim predicts flat time, whereas linear growth would contradict the vocabulary-independence result.

Watch

Extended reading notes

Core claim

The paper's central claim is that validity checking in grammar-constrained decoding does not need to be done online, token by token. For a grammar parsed by a terminating deterministic pushdown automaton with a lexer modeled as a deterministic finite-state transducer, the set of (lexer state, parser stack) configurations from which a given vocabulary token can be legally appended is a regular language (Theorem 3), and PSC constructs that language explicitly. The construction builds a transducer $P_w$ that simulates the parser reading any terminal sequence $w$ starting from an arbitrary stack — epsilon transitions are handled by a stabilizer transducer $P_\varepsilon$, and each terminal by a single-step transducer — then strips outputs to get an automaton $A_w$ for each realizable terminal sequence. All these automata are unioned, marked with lexer-state and token markers, and determinized and minimized into one automaton $\mathcal{A}$ whose states each correspond to a precomputed vocabulary mask. Running $\mathcal{A}$ once over the current stack ($O(|\alpha|)$ time) and looking up the mask ($O(1)$) therefore reproduces exactly the mask that repeated per-token parsing would produce; the paper reports this mask is correct on essentially all tested samples, and that preprocessing, done once per grammar-and-vocabulary pair, has a quantified break-even point for prospective users.

Load-bearing premise

The entire preprocessing pipeline rests on the assumption that the epsilon-closure of any parser stack is captured by a finite-state transducer with only finitely many states; the proof cites the parser's termination, but no bound is given on how long an epsilon-chain can grow, so a deterministic grammar that drove epsilon-closure through unbounded stack prefixes would make preprocessing fail to terminate or produce an infinite automaton.

Editorial extensions

If this is right

  • Per-step mask computation drops from $O(|V|)$ to $O(|\alpha|)$ plus a constant-time lookup, so vocabulary sizes in the hundreds of thousands no longer set the cost of constrained decoding.
  • End-to-end throughput with grammar constraints approaches unconstrained decoding, with the remaining gap smallest on small models and large batch sizes, where inference time per token is not the dominant cost.
  • Preprocessing is done once per (grammar, vocabulary) pair and its results can be shared, so model providers can amortize minutes-to-an-hour preprocessing of programming-language grammars across all users, while JSON-schema preprocessing takes about half a minute per schema.
  • The break-even analysis gives users a decision rule: self-preprocessing pays off after roughly half a minute of decoding for JSON schemas, and after noticeably longer for the more complex programming-language grammars.

Reading between the lines

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

  • The structural claim implies a directly measurable scaling law: doubling or tripling a model's vocabulary should leave PSC's per-step mask time essentially flat while baseline costs grow roughly linearly, a test that can be run on tokenizers and grammars alone, without model inference.
  • Because the finiteness of $P_\varepsilon$ is inferred from termination rather than bounded, a natural stress test is a family of deterministic grammars with cascading nullable productions; if any terminating deterministic grammar defeats preprocessing, the practical scope of PSC would be narrower than the theorem suggests.
  • The same offline/online split — classify the configuration once, reuse the decision for every token — is not inherently tied to context-free grammars; any constraint device whose acceptance sets over configurations are regular could be accelerated the same way, including indentation-sensitive or typed output specifications.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper proposes PSC (Parser Stack Classification), a grammar-constrained decoding method that precomputes a deterministic finite automaton over (lexer state, parser stack) pairs, so that the per-step vocabulary mask is obtained by a single traversal of the parser stack rather than by invoking the parser once per vocabulary token. The authors formulate the acceptance condition of each token as a finite-state transducer on the parser stack, compose these to build a single DFA, and report up to 700x faster mask computation on programming-language grammars and up to 30x on JSON schemas, with end-to-end throughput close to unconstrained decoding. The paper also provides an analysis of preprocessing cost and a break-even point for when users should preprocess themselves.

Significance. If the theoretical foundation is made sound, PSC is a significant contribution: it changes the per-step cost of grammar-constrained decoding from O(|V|) to O(|stack|) and removes all runtime parser calls, which is especially valuable for the 128k-262k token vocabularies of modern LLMs. The empirical study is extensive and carefully controlled (teacher-forcing for fair comparison, three model families, batch-size sweeps, and multiple baselines), and the reported speedups are large and internally consistent. The paper ships open-source code, datasets, and preprocessing results, which strengthens reproducibility. The principal risk is the proof of finiteness of the epsilon-closure transducer in Theorem 1; this must be repaired before the general DCFG claim is credible, although the experimental results for LALR grammars may remain valid regardless.

major comments (3)
  1. [§3.3, Theorem 1 (Eqs. 5a-5c)] The proof that P_epsilon is a finite-state transducer is invalid. Termination of P bounds each individual epsilon-run, but P_epsilon must be a single finite FST for all possible input stacks. Equation 5c can produce states whose length is |β|+|α|-2, and if β has length greater than 2, state length can grow without bound across different stacks (e.g., a terminating epsilon-transition that temporarily pushes two symbols before popping them yields intermediate stack prefixes of length proportional to the number of input symbols read). Consequently, the closure defined by Eqs. 5 may not terminate, and P_w, A_w, and the DFA A in Eq. 9 are not guaranteed to exist for general terminating DCFGs. This is load-bearing for the paper's general correctness claims (Theorems 2 and 3), though not directly for the LALR-based experiments, where reductions are length-decreasing. Please either prove finiteness under an appropriate bounded-stack condition, or restrict the theoretical claims to a class of grammars for which the construction is finite.
  2. [§3.4 and Algorithm 1, line 6 (vs. Eq. 8)] The composition order in Algorithm 1, line 6, contradicts Equation 8. Equation 8 defines P_w = P_epsilon ◦ \tilde{P}_{w_1} ◦ P_epsilon ◦ ... ◦ \tilde{P}_{w_n} ◦ P_epsilon, which processes the terminals in the order w_1, ..., w_n. Algorithm 1 line 6 lists the composition as P_epsilon ◦ \tilde{P}_{w_n} ◦ ... ◦ \tilde{P}_{w_1} ◦ P_epsilon, which would process the terminal sequence in reverse. Since FST composition is order-sensitive, one of the two must be corrected; please also confirm that the implementation matches the corrected version.
  3. [§3.2, Equation 3] The equivalence in Eq. 3 relies on the assumption that reaching a stable stack after reading a realizable terminal sequence w implies the existence of some continuation y with T(xvy) ∈ P. The paper calls this a 'common assumption' but provides no proof or formal condition on the grammar, and it is load-bearing: if some stable stack cannot be extended to a complete accepted string, the computed mask would admit invalid tokens. Please state this as an explicit assumption on the grammars (or prove it for DCFGs), and confirm experimentally or by construction that the grammars used in the evaluation satisfy it.
minor comments (6)
  1. [§4.1 and Contributions list] The contributions bullet in Section 1 says experiments were conducted on 'Java, Go, Python, and schema-conformant JSON', but Section 4.1 lists only Java, Go, SQL, and JSON schemas; Python never appears in the evaluation. Please align the two descriptions.
  2. [§5.1.2] Typos: 'programmaing' should be 'programming' and 'perprocessing' should be 'preprocessing'.
  3. [Figure 3] The legend label 'Upper bound (uncostrained)' should read 'Upper bound (unconstrained)'.
  4. [Algorithm 1 heading] The heading 'Offline constructon in PSC' should be 'Offline construction in PSC'.
  5. [References] Several references have garbled author lists, notably the McEval reference (with malformed author tokens) and the Llama 3 reference (with duplicated names). These should be cleaned up.
  6. [§4.2] The near-100% sample pass rate of PSC is inherited from the adopted GreatGramma lexer; RQ1 does not independently validate PSC's mask correctness against a gold standard for the cases where the lexer succeeds, because all methods are designed to compute the same masks. The text should state this more explicitly to avoid overstating the correctness evidence for PSC itself.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: PSC's derivation is self-contained, with a separate proof gap in Theorem 1 that is not a circularity.

full rationale

I found no circular step in the paper's claimed derivation chain. The core construction is self-contained: P_epsilon (Equations 5), P_w (Equation 8), A_w, and the combined automaton A (Equation 9) are all defined as explicit simulations of the terminating deterministic PDA, with no fitted parameters and no reliance on the paper's own experimental outputs. Theorems 1-3 are argued directly from the automaton definitions, and the speedup claims in Section 4 are controlled empirical comparisons against external baselines such as LLGuidance, XGrammar, GreatGramma, and Formatron, rather than predictions derived from fitted constants. The only load-bearing citation is to GreatGramma [33] for the lexer construction and for the stable-stack simplification in Equation 3; that citation is external to the present authors, and the assumption is stated explicitly rather than smuggled in. The proof of Theorem 1 does contain a finiteness gap: termination of P bounds each individual epsilon-run but does not by itself bound the union of states over all stacks, so the claim that only finitely many new states arise is not established by the argument given. That is a correctness and robustness concern, not a circularity, because it does not reduce the theorem to its own inputs or to a self-citation chain.

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

No fitted parameters appear in the method; the only inputs are the grammar, vocabulary, and lexer. No new physical or external entities are postulated; the FSA A is a mathematical construction. The load-bearing assumptions are DCFG determinism, the stable-stack completion property, finiteness of the epsilon-closure transducer, and lexer tokenizability.

assumptions (5)
  • domain assumption The target grammar is deterministic context-free (or LALR), so the parser is a terminating deterministic PDA.
    Stated in Section 2.4 and Threats to Validity 5.3; the PSC construction relies on deterministic, terminating PDA transitions.
  • domain assumption Reaching a stable stack after reading a realizable terminal sequence implies existence of a completion to a valid string.
    Section 3.2 calls this a common assumption from GreatGramma; it is load-bearing for mask correctness.
  • ad hoc to paper The epsilon-closure FST P_epsilon has finitely many states because the PDA is terminating.
    Theorem 1, Equations 5a-5d. The proof asserts termination bounds the state count, but does not show a uniform bound; this is the paper's own claim, not a standard theorem.
  • domain assumption The lexer can be modeled as a deterministic FST and each token maps to a finite set of realizable terminal sequences.
    Section 3.1. RQ1 errors from Unicode split tokens and one-character lookahead show this assumption is not always satisfied in practice.
  • standard math Regular languages are closed under reversal, Brzozowski derivative, union, concatenation, determinization, and minimization.
    Used in Theorem 3 and Section 2.3; standard automata theory from Hopcroft and Ullman and Brzozowski.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Grammar-Constrained Decoding via Parser Stack Classification." pith.science (2026). https://pith.science/paper/5LMMHDGY

@misc{pith2026260803065,
  author       = {Pith},
  title        = {Pith review of: Efficient Grammar-Constrained Decoding via Parser Stack Classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5LMMHDGY}},
  note         = {Machine review of arXiv:2608.03065}
}
abstract

LLMs are widely used to generate structured output like source code or JSON. Grammar-constrained decoding (GCD) can guarantee the syntactic validity of the generated output, by masking out tokens that violate rules specified by a context-free grammar. However, the online computational overhead of existing GCD methods, with latency typically scaling linearly with vocabulary size, limits the throughput of LLMs, especially for models with large vocabularies. To address this issue, we propose PSC, a novel grammar-constrained decoding method. By combining acceptance conditions of all vocabulary tokens into a single classifier of the parser stack during preprocessing, PSC can compute the complete vocabulary mask by checking the parser stack exactly once per decoding step, with time complexity independent of the vocabulary size. Experiments show that PSC computes masks up to 700$\times$ faster than baselines on complex programming language grammars, and up to 30$\times$ faster for schema-conformant JSON; end-to-end LLM throughput with PSC approaches that of unconstrained decoding. We analyze the preprocessing overhead for preprocessing providers and decoding users, and provide a break-even point analysis to help users decide whether to do preprocessing by themselves.

Figures

Figures reproduced from arXiv: 2608.03065 by the authors.

Figure 1
Figure 1. An illustration of grammar-constrained decoding, showing (a) the overall working process, (b) the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. An example of how PSC works during runtime decoding, compared with a naive GCD implementation. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. End-to-end throughput (tokens per second) on the different dataset using different methods on [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The break-even point of PSC versus LLGuidance, [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 26 canonical work pages

  1. [1]

    Lark - Parsing Library & Toolkit

    Lark - Parsing Library & Toolkit 2025.Lark - a Parsing Toolkit for Python. Lark - Parsing Library & Toolkit. https: //github.com/lark-parser/lark

    work page 2025

  2. [2]

    d.].Llama.Cpp: LLM Inference in C/C++

    ggml.ai [n. d.].Llama.Cpp: LLM Inference in C/C++. ggml.ai. https://github.com/ggml-org/llama.cpp

    work page

  3. [3]

    d.].MaskBench

    [n. d.].MaskBench. https://github.com/guidance-ai/jsonschemabench/tree/main/maskbench

    work page

  4. [4]

    Aho and Jeffrey D

    Alfred V. Aho and Jeffrey D. Ullman. 1972.The Theory of Parsing, Translation, and Compiling. Prentice-Hall, Inc

    work page 1972

  5. [5]

    Anysphere Inc. [n. d.].Cursor - The AI Code Editor. https://cursor.com/en

    work page

  6. [6]

    2023.Multi-Lingual Evaluation of Code Generation Models

    Ben Athiwaratkun, Sanjay Krishna Gouda, Zijian Wang, Xiaopeng Li, Yuchen Tian, Ming Tan, Wasi Uddin Ahmad, Shiqi Wang, Qing Sun, Mingyue Shang, Sujan Kumar Gonugondla, Hantian Ding, Varun Kumar, Nathan Fulton, Arash Farahani, Siddhartha Jain, Robert Giaquinto, Haifeng Qian, Murali Krishna Ramanathan, Ramesh Nallapati, Baishakhi Ray, Parminder Bhatia, Sudi...

    arXiv doi:10.48550/arxiv.2210.14868 2023

  7. [7]

    2021.Program Synthesis with Large Language Models

    Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. 2021.Program Synthesis with Large Language Models. arXiv:2108.07732 [cs.PL] doi:10.48550/arXiv.2108.07732

    arXiv doi:10.48550/arxiv.2108.07732 2021

  8. [8]

    2023.Qwen Technical Report

    Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang, Shijie Wang, Wei Wang, Shengguang Wu, Benfeng X...

    arXiv doi:10.48550/arxiv.2309.16609 2023

Show all 45 references
  1. [9]

    Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. 2024. Guiding LLMs the Right Way: Fast, Non-Invasive Constrained Generation. InProceedings of the 41st International Conference on Machine Learning(Vienna, Austria, 2024) (ICML’24). JMLR.org, Article 146

    2024

  2. [10]

    Brzozowski

    Janusz A. Brzozowski. 1964. Derivatives of Regular Expressions.J. ACM11, 4 (Oct. 1964), 481–494. doi:10.1145/321239. 321249

    1964 doi

  3. [11]

    Didier Caucal and Roland Monfort. 1991. On the Transition Graphs of Automata and Grammars. InGraph-Theoretic Concepts in Computer Science(Berlin, Heidelberg, 1991), Rolf H. Möhring (Ed.). Springer, 311–337. doi:10.1007/3-540- 53832-1_51

    1991 doi

  4. [12]

    Linzheng Chai, Shukai Liu, Jian Yang, Yuwei Yin, JinKe, given-i=JIAHENG family=LIU, given=JIAHENG, Tao Sun, Ge Zhang, Changyu Ren, Hongcheng Guo, Zekun Wang, Boyang Wang, Xianjie Wu, Bing Wang, Tongliang Li, Liqun Yang, Sufeng Duan, Zhaoxiang Zhang, and Zhoujun Li. 2025. McEva...

    2025

  5. [13]

    Junyi Chen, Shihao Bai, Zaijun Wang, Siyu Wu, Chuheng Du, Hailong Yang, Ruihao Gong, Shengzhong Liu, Fan Wu, and Guihai Chen. 2025. Pre^3: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation. InProceedings of the 63rd Annual Meeting of the Association...

    2025

  6. [14]

    Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott G...

    2021 doi arXiv

  7. [15]

    Yann Collet and Murray Kucherawy. 2021. Zstandard Compression and the ’application/zstd’ Media Type. RFC 8878. doi:10.17487/RFC8878

    2021 doi

  8. [16]

    Ruan, Yaxing Cai, Ziyi Xu, Yilong Zhao, Ruihang Lai, and Tianqi Chen

    Yixin Dong, Charlie F. Ruan, Yaxing Cai, Ziyi Xu, Yilong Zhao, Ruihang Lai, and Tianqi Chen. 2025. XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models. InEighth Conference on Machine Learning and Systems(2025). https://openreview.net/forum?i...

    2025

  9. [17]

    Jay Earley. 1970. An Efficient Context-Free Parsing Algorithm. (1970). doi:10.1145/362007.362035

    1970

  10. [18]

    Philip Gage. 1994. A New Algorithm for Data Compression. 12, 2 (1994), 23–38

    1994

  11. [19]

    Choquette-Choo, C

    Gemma Team, Aishwarya Kamath, Johan Ferret, Shreya Pathak, Nino Vieillard, Ramona Merhej, Sarah Perrin, Tatiana Matejovicova, Alexandre Ramé, Morgane Rivière, Louis Rouillard, Thomas Mesnard, Geoffrey Cideron, Jean-bastien Grill, Sabela Ramos, Edouard Yvinec, Michelle Casbon, ...

    2025 doi arXiv

  12. [20]

    2025.JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models

    Saibo Geng, Hudson Cooper, Michał Moskal, Samuel Jenkins, Julian Berman, Nathan Ranchin, Robert West, Eric Horvitz, and Harsha Nori. 2025.JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models. arXiv:2501.10868 [cs] doi:10.48550/arXiv.2501.10868

    2025 doi arXiv

  13. [21]

    Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2023. Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning. InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing(Singapore, 2023-12), Houda Bouamor, Juan Pino...

    2023 doi

  14. [22]

    2021.GitHub Copilot·Your AI Pair Programmer

    GitHub. 2021.GitHub Copilot·Your AI Pair Programmer. https://github.com/features/copilot

    2021

  15. [23]

    Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Art...

    2026 doi arXiv

  16. [24]

    Hopcroft and Jeffrey D

    John E. Hopcroft and Jeffrey D. Ullman. 1979.Introduction to Automata Theory, Languages, and Computation. Addison- Wesley

    1979

  17. [25]

    Donald E. Knuth. 1965. On the Translation of Languages from Left to Right. 8, 6 (1965), 607–639. doi:10.1016/S0019- 9958(65)90426-2

    1965 doi

  18. [26]

    Denis Kocetkov, Raymond Li, Loubna Ben Allal, Jia Li, Chenghao Mou, Yacine Jernite, Margaret Mitchell, Car- los Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Dzmitry Bahdanau, Leandro Von Werra, and prefix=de usepre- fix=false family=Vries, given=Harm. 2022. The Stack: 3 TB of Pe...

    2022

  19. [27]

    Terry Koo, Frederick Liu, and Luheng He. 2024. Automata-Based Constraints for Language Model Decoding. InFirst Conference on Language Modeling(2024). https://openreview.net/forum?id=BDBdblmyzY

    2024

  20. [28]

    Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient Memory Management for Large Language Model Serving with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Princip...

    2023

  21. [29]

    Fiannaca, Terry Koo, Lucas Dixon, Michael Terry, and Carrie J

    Michael Xieyang Liu, Frederick Liu, Alexander J. Fiannaca, Terry Koo, Lucas Dixon, Michael Terry, and Carrie J. Cai

  22. [30]

    2025.LLGuidance: Making Structured Outputs Go Brrr

    Michał Moskal, Harsha Nori, Hudson Cooper, and Loc Huynh. 2025.LLGuidance: Making Structured Outputs Go Brrr. https://guidance-ai.github.io/llguidance/llg-go-brrr

    2025

  23. [31]

    2025.Json-Mode-Eval

    NousResearch. 2025.Json-Mode-Eval. https://huggingface.co/datasets/NousResearch/json-mode-eval

    2025

  24. [32]

    OpenAI. [n. d.].Structured model outputs - OpenAI API. https://platform.openai.com

  25. [33]

    Kanghee Park, Timothy Zhou, and Loris D’Antoni. 2025. Flexible and Efficient Grammar-Constrained Decoding. In Forty-Second International Conference on Machine Learning(2025). https://openreview.net/forum?id=L6CYAzpO1k

    2025

  26. [34]

    Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2021. Synchromesh: Reliable Code Generation from Pre-trained Language Models. https://openreview.net/forum?id= KmtVD97J43e

    2021

  27. [35]

    2025.Qwen2.5 Technical Report

    Qwen, An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le ...

    2025 doi arXiv

  28. [36]

    Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021. PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models. InProceedings of the 2021 Conference on Empirical Methods in Natural Language Processing(Online and Punta Cana, Dominican ...

    2021

  29. [37]

    Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural Machine Translation of Rare Words with Subword Units. InProceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (Berlin, Germany, 2016-08), Katrin Erk and Noa...

    2016 doi

  30. [38]

    2013.Introduction to the Theory of Computation(third edition, international edition ed.)

    Michael Sipser. 2013.Introduction to the Theory of Computation(third edition, international edition ed.). Cengage Learning

    2013

  31. [39]

    Xintong Sun, Chi Wei, Minghao Tian, and Shiwen Ni. 2025. Earley-Driven Dynamic Pruning for Efficient Structured Decoding. InForty-Second International Conference on Machine Learning(2025). https://openreview.net/forum?id= 6hDNXCdTsE

    2025

  32. [40]

    Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. 2025. SynCode: LLM Generation with Grammar Augmentation. (2025). https://openreview.net/forum?id=HiUZtgAPoH

    2025

  33. [41]

    vLLM Team. [n. d.].Structured Outputs - vLLM. https://docs.vllm.ai/en/stable/features/structured_outputs.html , Vol. 1, No. 1, Article . Publication date: August 2026. Efficient Grammar-Constrained Decoding via Parser Stack Classification 25

    2026

  34. [42]

    Willard and Rémi Louf

    Brandon T. Willard and Rémi Louf. 2023.Efficient Guided Generation for Large Language Models. arXiv:2307.09702 [cs] doi:10.48550/arXiv.2307.09702

    2023 doi arXiv

  35. [43]

    Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018. Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task. InPr...

    2018

  36. [44]

    Ruiqi Zhong, Tao Yu, and Dan Klein. 2020. Semantic Evaluation for Text-to-SQL with Distilled Test Suites. InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (Eds.). Association fo...

    2020 doi

  37. [2024]

    We Need Structured Output

    "We Need Structured Output": Towards User-centered Constraints on Large Language Model Output. InExtended Abstracts of the CHI Conference on Human Factors in Computing Systems(Honolulu, HI, USA)(CHI EA ’24). Association for Computing Machinery, New York, NY, USA, Article 10, 9...

Pith tools

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