The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding

# The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding
Source: [https://arxiv.org/html/2608.10137](https://arxiv.org/html/2608.10137)
###### Abstract

Grammar Constrained Decoding \(GCD\) forces Language Models \(LMs\) to produce syntactically valid outputs by masking out non\-conforming tokens at each step\. However, rigid masking distorts the model’s underlying probability distribution, often biasing generation toward valid but suboptimal outputs\. While online sampling restores this distribution, it requires computationally expensive iterative resampling\. As a result, existing methods force a compromise between output quality and inference latency\. Our key insight is that the internal parser and lexer states inherently maintained during incremental parsing already encode future grammatical validity—exactly the information required to restore the LM’s true distribution\. We propose a lightweight, offline\-trained logit correction conditioned on this syntactic and lexical state together with candidate next tokens\. Because these states are already computed as a necessary part of incremental parsing for masking, extracting them adds negligible overhead while leaving the base LM’s weights completely untouched\.

Across several grammars, this correction substantially closes the gap between the masked distribution and the LM’s true distribution, consistently outperforming both masking and online sampling\. Even its lightest variant, which relies on the candidate next token alone, still matches or exceeds both baselines: the next token itself carries an implicit lookahead, much like how parsers commonly use a lookahead token to resolve ambiguous decisions\. By restoring the probability mass that masking removes, it reconciles the LM’s probabilistic integrity with grammar conformance\.

## 1Introduction

### Problem statement\.

While Language Models \(LMs\) generate remarkably human\-like text and code\(Chowdheryet al\.[2023](https://arxiv.org/html/2608.10137#bib.bib26); Liet al\.[2022](https://arxiv.org/html/2608.10137#bib.bib27); Chenet al\.[2021](https://arxiv.org/html/2608.10137#bib.bib28); Austinet al\.[2021](https://arxiv.org/html/2608.10137#bib.bib29)\), they consistently struggle to satisfy rigid syntactic and semantic constraints\(Luet al\.[2023](https://arxiv.org/html/2608.10137#bib.bib30); Liet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib31)\)\. In practice, prompt engineering and fine\-tuning fall short of guaranteeing strict conformance to context\-free grammars \(CFGs\)\(Luet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib33); Tenckhoffet al\.[2026](https://arxiv.org/html/2608.10137#bib.bib34)\)\. This unreliability creates a bottleneck when integrating LMs into real\-world software pipelines: even minor syntax violations yield malformed outputs that cause immediate downstream failures in parsers, input validators, structured data processing engines, and auto\-formalization frameworks \(e\.g\., SMT solvers or SQL engines\)\.

### Existing approaches\.

Prior work on constrained generation fundamentally trades generation quality for computational cost\. The simplest approach, rejection sampling, repeatedly draws completions until a valid candidate emerges within a fixed budget\(Chowdheryet al\.[2023](https://arxiv.org/html/2608.10137#bib.bib26); Chenet al\.[2023](https://arxiv.org/html/2608.10137#bib.bib32); Paryset al\.[2026](https://arxiv.org/html/2608.10137#bib.bib19)\); however, this is computationally prohibitive and provides no formal compliance guarantee\. Grammar Constrained Decoding \(GCD\) methods\(Ugareet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib13); Donget al\.[2025](https://arxiv.org/html/2608.10137#bib.bib14); Parket al\.[2025](https://arxiv.org/html/2608.10137#bib.bib15); Willard and Louf[2023](https://arxiv.org/html/2608.10137#bib.bib17); Beurer\-Kellneret al\.[2024](https://arxiv.org/html/2608.10137#bib.bib16)\)111Some prior work \(e\.g\. SMC Steering\(Lewet al\.[2023](https://arxiv.org/html/2608.10137#bib.bib25)\), AWRS\(Lipkinet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib21)\), and P\-GCD\(Danget al\.[2026](https://arxiv.org/html/2608.10137#bib.bib22)\)\) instead calls this masking\-based family*Locally Constrained Decoding \(LCD\)*and reserves*GCD*for*Globally Constrained Decoding*; we keep GCD as*Grammar*Constrained Decoding throughout, using*local*/*global*only as plain descriptors\.address this by masking non\-conforming logits at each decoding step\. While masking guarantees structural compliance with minimal overhead, it only evaluates whether a token is valid*locally*, ignoring whether it forecloses high\-probability completions down the line\. Consequently, masking distorts the model’s output distribution, often steering generation toward unnatural or degraded outputs\(Lewet al\.[2023](https://arxiv.org/html/2608.10137#bib.bib25); Parket al\.[2024](https://arxiv.org/html/2608.10137#bib.bib18)\)\.

Online sampling techniques\(Parket al\.[2024](https://arxiv.org/html/2608.10137#bib.bib18); Paryset al\.[2026](https://arxiv.org/html/2608.10137#bib.bib19); Gonzalezet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib20); Lipkinet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib21)\)restore this lost probability mass by dynamically reweighting candidates, but doing so requires expensive online resampling at every step, severely inflating inference latency\. Alternatively, tractable probabilistic model augmentation\(Zhanget al\.[2023](https://arxiv.org/html/2608.10137#bib.bib23),[2024](https://arxiv.org/html/2608.10137#bib.bib24); Danget al\.[2026](https://arxiv.org/html/2608.10137#bib.bib22)\)avoids runtime sampling by pairing the LM with an offline surrogate model that is exactly computable\. However, learning a tractable approximation of the full LM distribution is notoriously difficult and introduces significant modeling errors\. Because each paradigm compromises on either latency, fidelity, or scalability, none of these options is ideal for practical deployment\.

### Our solution\.

To resolve this trilemma, we propose an offline, decoupled framework that achieves strict grammatical correctness without sacrificing inference speed\. Rather than altering base model weights or performing expensive online resampling, we introduce SHIM: a lightweight, offline\-trained probability controller\. Like a physical shim aligning two mismatched surfaces, it aligns the masked distribution back to the LM’s true one\. Our key insight is that the masking tool’s own parser and lexer state\(Ahoet al\.[2006](https://arxiv.org/html/2608.10137#bib.bib38)\)already encode the grammatical structure this correction needs\. Instead of training a separate model to learn that structure from scratch, our controller reads it out directly, together with the candidate next token, at essentially no added cost\. This keeps the controller lightweight while still capturing which continuations remain grammatically valid, so generation stays natural and diverse rather than collapsing onto degenerate, low\-probability sequences\.

Root::=::="\(define\-fun inv \(\(s \(BitVec 4\)\) \(t \(BitVec 4\)\)\)\(BitVec 4\) " Start "\)"Start::=::="s"∣\\mid"t"∣\\mid"\#x0"∣\\mid"\#x8"∣\\mid"\#x7"∣\\mid"\(" "bvneg" " " Start "\)"∣\\mid"\(" "bvnot" " " Start "\)"∣\\mid"\(" "bvand" " " Start " " Start "\)"∣\\mid"\(" "bvlshr" " " Start " " Start "\)"∣\\mid"\(" "bvor" " " Start " " Start "\)"∣…\\mid\\dotsCFG:𝒢BV4\\mathcal\{G\}\_\{\\text\{BV4\}\}Snapshot

Figure 1:Subset of the BV4 bit\-vector grammar\.Startrecurses over unary \(bvneg,bvnot\) and binary \(bvand,bvlshr,bvor\) operators over input variablessandt\. Recursive structure like this induces high lookahead ambiguity during constrained decoding\.S0S\_\{0\}S1S\_\{1\}S2S\_\{2\}S3S\_\{3\}S4S\_\{4\}S5S\_\{5\}\(bvandbvlshrbvorstst\)StartOp consumedAccept

Figure 2:Incremental parser state transitions during decoding for the string\(bvand s t\)under the BV4 grammar \(Figure[1](https://arxiv.org/html/2608.10137#S1.F1)\)\. Because binary operators require two arguments, the parser advances through intermediate statesS3S\_\{3\}andS4S\_\{4\}before expecting the closing parenthesis\.Structured generation tools like Syncode maintain exactly this kind of incremental parser and lexer state\(Wagner and Graham[1998](https://arxiv.org/html/2608.10137#bib.bib39)\)as they decode; we illustrate how these states work, and how our controller uses them, with a concrete example\. Consider parsing the expression\(bvand s t\)under the BV4 grammar excerpt in Figure[1](https://arxiv.org/html/2608.10137#S1.F1)\. The opening\(is consumed as its own token, advancing the parser toS1S\_\{1\}in Figure[2](https://arxiv.org/html/2608.10137#S1.F2); suppose the LLM’s tokenizer then producesbandvas its next two tokens\. The LLM itself generates at the token level, but the lexer state tracks progress at the character level: its*buffer*accumulates the characters of the current, in\-progress lexeme only, emptying each time a lexeme completes – unlike the prefixx<ix\_\{<i\}, which accumulates every token the LLM has generated\. Since\(already completed as its own lexeme, the buffer excludes it and accumulates onlybandv, regardless of how these characters were chunked into tokens\. Right after these two tokens, the buffer is"bv", landing the lexer state on nodevvin Figure[3](https://arxiv.org/html/2608.10137#S1.F3)\. Formally, the lexer state is the set of lexemes that remain consistent with this buffer, together with how far it has advanced into each candidate lexeme’s pattern\. Here,bvand,bvlshr, andbvorare all still possible\. The next token then narrows this set to the intended lexeme\.

ϵ\\epsilonbvaloxnd\(BVAND\)shr\(BVLSHR\)r\(BVOR\)Masked / RejectedLexer State at Steptt\(Buffer:"bv"\)

Figure 3:Probability control conditioned on lexical state and candidate tokens\. The lexer state is a node in this terminal trie; buffer"bv"alone cannot distinguishbvand,bvlshr, andbvor\. Combining it with the candidate next token \(e\.g\.,"a","l","o"\) resolves this, boosting valid continuations and masking invalid ones \(e\.g\.,"x"\)\.At this point in decoding, the parser itself is still at stateS1S\_\{1\}in Figure[2](https://arxiv.org/html/2608.10137#S1.F2): it only advances once a complete operator token is consumed, so it gives no indication that the possibilities have already narrowed tobvand,bvlshr, andbvor\. Only the lexer state captures this within\-lexeme progress; the parser catches up once the operator token completes and it advances toS2S\_\{2\}\.

Together with the candidate next token, these two states map directly to a probabilistic adjustment factor at the logit level that approximates the future validity of the tokens; this factor, in turn, increases the chance of generating a sample that is true to the LLM’s valid sequence distribution\. By training this controller on transitions between parser states and valid token sequences, we enable it to predict a candidate token’s likelihood of leading to a grammatically valid continuation before the model samples a single token\. During inference, we apply this correction by adding its logarithm to the masked logits of the streaming LLM output, effectivelyrestoringthe LLM’s natural distribution over valid sequences without the need for iterative sampling\. Our method functions as a refinement layer on top of existing masking tools, including Syncode, XGrammar, and Outlines – together, over 17,000 GitHub stars\. It guarantees grammatical compliance regardless of the underlying tool, requiring only access to that tool’s internal parser, which already maintains the state our controller reads\. This positions SHIM against masking, online sampling, and tractable augmentation at once: unlike GCD, it accounts for a token’s effect on future grammar conformance, not just conformance so far; unlike online sampling, it evaluates a fixed, pre\-trained correction rather than updating its estimate during generation; and unlike HMM\-based augmentation, it only needs to learn the narrow correction induced by masking rather than distill the LLM’s entire output distribution\.

Step 0: Initial State \(Prefix =""\)’0’’1’’2’’A’0\.4950\.4950\.0070\.003pLLMp\_\{\\text\{LLM\}\}ValidValidMaskedMaskedGrammar Mask0\.0590\.9410\.0000000\.000000pH,adjp\_\{\\text\{H,adj\}\}Structured Features Parser State:S0S\_\{0\} Lexer State:L0L\_\{0\} Next Valid Tokens:\{’0’, ’1’\} SHIM Logit Processor γ​\(0\)=2/17\\gamma\(0\)=2/17 γ​\(1\)=32/17\\gamma\(1\)=32/17ExtractApplyγ\\gammaCorrectionStep 1 \- Scenario A: Path00000\(Prefix ="0"\)’0’’1’’2’’A’0\.0610\.8500\.0500\.039pLLMp\_\{\\text\{LLM\}\}ValidMaskedMaskedMaskedGrammar Mask1\.0000\.0000000\.0000000\.000000pH,adjp\_\{\\text\{H,adj\}\}Structured Features Parser State:S1S\_\{1\} Lexer State:L1L\_\{1\} Next Valid Tokens:\{’0’\} SHIM Logit Processor Absolute Constraint γ​\(0\)=1\.0\\gamma\(0\)=1\.0ExtractApplyγ\\gammaCorrectionStep 1 \- Scenario B: Path10101\(Prefix ="1"\)’0’’1’’2’’A’0\.6150\.2500\.1000\.035pLLMp\_\{\\text\{LLM\}\}ValidValidMaskedMaskedGrammar Mask0\.7110\.2890\.0000000\.000000pH,adjp\_\{\\text\{H,adj\}\}Structured Features Parser State:A2A\_\{2\} Lexer State:L2L\_\{2\} Next Valid Tokens:\{’0’, ’1’\} SHIM Logit Processor No Further Constraint γ​\(0\)=γ​\(1\)=1\\gamma\(0\)=\\gamma\(1\)=1ExtractApplyγ\\gammaCorrection

Figure 4:Overview of the probability adjustment pipeline during constrained decoding\. The pipeline masks invalid tokens and applies a trained correction factorγ\\gammato the survivors, restoring the LM’s true grammatical distribution\.γ\\gammais learned offline, conditioned on the parser state, lexer state, and candidate next tokens\.
### Evaluation\.

We implement our correction approach at three levels of feature availability and model capacity, all integrated on top of Syncode’s\(Ugareet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib13)\)masking infrastructure, built on the Lark parsing toolkit\(Shinan[2018](https://arxiv.org/html/2608.10137#bib.bib40)\)\. We choose Syncode as a state\-of\-the\-art masker, but our approach extends to any GCD tool that exposes parser and lexer state\. We generate training samples offline via the vanilla LLM and process them with Syncode to capture the parser state, lexer state, and candidate next token features\. On these available features, we train \(1\) a Multi\-Layer Perceptron \(MLP\) and \(2\) a lightweight Logistic Regressor, each estimating the probability that its input will yield a valid, high\-probability generation in the future\. We also train \(3\) a Logistic Regressor restricted to the candidate next token alone\. LR\(1\) parsers combine a lookahead token with their current parse state to resolve ambiguous decisions; we test whether the candidate next token alone already carries enough signal to predict future grammatical validity\.

We measure performance via KL divergence against the target LLM distribution and average inference latency, benchmarking SHIM against standard token masking via Syncode\(Ugareet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib13)\)and the state\-of\-the\-art online sampling framework ASAp\(Parket al\.[2024](https://arxiv.org/html/2608.10137#bib.bib18)\)\. Our strongest variant achieves up to 113×\\timeslower KL divergence than masking and up to 235×\\timeslower divergence than online sampling, while all variants add negligible additional inference cost over standard masking\.

## 2Characterizing the Probability Drift

Given an LLMpp, a promptx≤sx\_\{\\leq s\}of lengthssand a grammar constraintα\\alpha, we want to sample from the conditional distribution

p​\(x\>s\|x≤s,α\)=∏i\>sp​\(xi\|x<i,α\)\.p\(x\_\{\>s\}\|x\_\{\\leq s\},\\alpha\)=\\prod\_\{i\>s\}p\(x\_\{i\}\|x\_\{<i\},\\alpha\)\.However, we do not have access to the conditional next\-token distributionp​\(xi\|x<i,α\)p\(x\_\{i\}\|x\_\{<i\},\\alpha\)and therefore this approach is not practical\. Instead, Grammar Constrained Decoding \(GCD\) tools give us access to a different, unconditional distributionqαq\_\{\\alpha\}, which we can sample from directly\. At the token level,qαq\_\{\\alpha\}is defined as

qα​\(xi\|x<i\)=p​\(xi\|x<i\)​𝕀​\(x<i​xi∈Pref⁡\(L​\(α\)\)\)∑t∈Vp​\(t\|x<i\)q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)=\\frac\{p\(x\_\{i\}\|x\_\{<i\}\)\\mathbb\{I\}\(x\_\{<i\}x\_\{i\}\\in\\operatorname\{Pref\}\(L\(\\alpha\)\)\)\}\{\\sum\_\{t\\in V\}p\(t\|x\_\{<i\}\)\}whereVVstands for the grammatically valid next tokens for the prefixx<ix\_\{<i\}\.qαq\_\{\\alpha\}masks out any token that would make the prefix invalid and renormalizes the LLM’s probability over the tokens that remain valid, where a prefixx<ix\_\{<i\}is valid if it can still be extended into a complete string inL​\(α\)L\(\\alpha\)\. Over a full sequence,qαq\_\{\\alpha\}factorizes the same way as the target:

qα​\(x\>s\|x≤s\)=∏i\>sqα​\(xi\|x<i\)\.q\_\{\\alpha\}\(x\_\{\>s\}\|x\_\{\\leq s\}\)=\\prod\_\{i\>s\}q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\.Unfortunately, this approximation is not exact:qαq\_\{\\alpha\}only masks based on whether the prefix conforms to the grammarso far, i\.e\.,past grammaticality, so it does not incorporate the future grammaticality of the tokens it selects:

qα​\(x\>s\|x≤s\)≠p​\(x\>s\|x≤s,α\)\.q\_\{\\alpha\}\(x\_\{\>s\}\|x\_\{\\leq s\}\)\\neq p\(x\_\{\>s\}\|x\_\{\\leq s\},\\alpha\)\.
We demonstrate this with an example grammar𝒢s​k\\mathcal\{G\}\_\{sk\}, adapted from ASAp\(Parket al\.[2024](https://arxiv.org/html/2608.10137#bib.bib18)\), in Equation[1](https://arxiv.org/html/2608.10137#S2.E1), illustrated step by step in Figure[4](https://arxiv.org/html/2608.10137#S1.F4), given as a regular expression over tokensΣ=\{0,1\}\\Sigma=\\\{0,1\\\}\. Suppose the grammar accepts binary strings of length five, where a string can only continue with 0 if it started with 0\.

𝒢s​k:00000∣1\(0∣1\)4\\mathcal\{G\}\_\{sk\}:\\quad\\texttt\{00000\}\\mid\\texttt\{1\}\(\\texttt\{0\}\\mid\\texttt\{1\}\)^\{4\}\(1\)
Supposep​\(xi\|x<i\)p\(x\_\{i\}\|x\_\{<i\}\)is uniform\. Simplifying the notation ofp​\(xi\|x<i\)p\(x\_\{i\}\|x\_\{<i\}\)top​\(x\)p\(x\)for sequencexx, we have

p​\(00000\)=p​\(10000\)=…=1/32p\(00000\)=p\(10000\)=\.\.\.=1/32
Then the target probability distributionp​\(x∣α\)p\(x\\mid\\alpha\)for sequencexxshould preserve the LLM’s distribution over the grammar\-valid sequences, renormalized to sum to one, i\.e\., every grammar\-satisfying string should have a probability of1/171/17:

p​\(00000\|α\)=p​\(00000\)∑x∈L​\(α\)p​\(x\)=1/3217/32=1/17\.p\(00000\|\\alpha\)=\\frac\{p\(00000\)\}\{\\sum\\limits\_\{x\\in L\(\\alpha\)\}p\(x\)\}=\\frac\{1/32\}\{17/32\}=1/17\.
At each generation stepii, GCD algorithms that use token\-level masking would only sample the next tokenxix\_\{i\}ifx≤ix\_\{\\leq i\}is a valid prefix of the grammarα\\alpha\. However, this masked decoding algorithm would distort the final distribution\. For example, assume that the LLM would producex1=0x\_\{1\}=0andx1=1x\_\{1\}=1with an even probability1/21/2\. Suppose the masked LLM choosesx1=0x\_\{1\}=0\. Then, because the only grammar\-satisfying string that starts with 0 is 00000, the decoding algorithm would always append a 0 to the existing generated string, so the probability of generating0000000000in the token\-masked setting is 1/2\. However, the actual probability should have been 1/17 to preserve the uniform distribution the LLM initially had, because the LLM models an even distribution over all 17 grammar\-satisfying strings\. Figure[4](https://arxiv.org/html/2608.10137#S1.F4)traces this same grammar step by step: Step 0 shows SHIM’s correction factorγ\\gammapulling the masked, even1/21/2–1/21/2split overx1x\_\{1\}down to the target1/171/17–16/1716/17split; Scenario A then shows why masking alone still forcesx1=0x\_\{1\}\{=\}0into the degenerate continuation00000described above; and Scenario B shows the complementary case, where the idealγ\\gammais a no\-op because every continuation afterx1=1x\_\{1\}\{=\}1is already grammar\-valid\.

The root cause of the problem is that, in each decoding step, the algorithm should take into account thefuture, or theprobability of the next token yielding a valid sequence in the future\. Concretely, it should take into account the probability mass of valid future continuations, i\.e\., producexi\+1x\_\{i\+1\}according to the probability∑x\>ip​\(x≥i∣x<i\)​\[x∈α\]\\sum\\limits\_\{x\_\{\>i\}\}p\(x\_\{\\geq i\}\\mid x\_\{<i\}\)\[x\\in\\alpha\], which is intractable\.

## 3SHIM Methodology

At a high level, SHIM predicts a correction factorγ\\gammafor each candidate next token and applies it to the masked distributionqαq\_\{\\alpha\}at every decoding step \(Equation[2](https://arxiv.org/html/2608.10137#S3.E2)\)\. We predictγ\\gammafrom three features already exposed by the masking tool: the parser state, the lexer state, and the candidate next token\. Below, we first derive what an idealγ\\gammawould look like, simplify it into a tractable form, and then describe how we approximate it in practice with a lightweight model\.

### Improving the alignment

We aim to takeqαq\_\{\\alpha\}, the distribution produced by an existing GCD tool, and improve it to become a better approximationqα⋆q^\{\\star\}\_\{\\alpha\}:

qα⋆​\(x\>s\|x≤s\)=∏i\>sqα⋆​\(xi\|x<i\)≈p​\(x\>s\|x≤s,α\)\.q^\{\\star\}\_\{\\alpha\}\(x\_\{\>s\}\|x\_\{\\leq s\}\)=\\prod\_\{i\>s\}q^\{\\star\}\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\\approx p\(x\_\{\>s\}\|x\_\{\\leq s\},\\alpha\)\.Starting from an existingqαq\_\{\\alpha\}, we achieve this by applying a correction factorγ\\gammato the choice of next token:

qα⋆​\(xi\|x<i\)∝qα​\(xi\|x<i\)⋅γ​\(xi,x<i\),\\displaystyle q^\{\\star\}\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\\propto q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\\cdot\\gamma\(x\_\{i\},x\_\{<i\}\),\(2\)

### An impractical solution

Ifγ​\(xi,x<i\)≈p​\(xi\|x<i,α\)qα​\(xi\|x<i\)\\gamma\(x\_\{i\},x\_\{<i\}\)\\approx\\frac\{p\(x\_\{i\}\|x\_\{<i\},\\alpha\)\}\{q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\}, then the following solution is correct but impractical\.

qα⋆​\(x\>s\|x≤s\)≈p​\(x\>s\|x≤s,α\)q^\{\\star\}\_\{\\alpha\}\(x\_\{\>s\}\|x\_\{\\leq s\}\)\\approx p\(x\_\{\>s\}\|x\_\{\\leq s\},\\alpha\)
We can writeγ\\gammaby using Bayes’ rules and then simplifying the constant factors with respect toxix\_\{i\},

γ​\(xi,x<i\)≈p​\(α\|xi,x<i\)​p​\(xi\|x<i\)qα​\(xi\|x<i\)​p​\(α\|x<i\)∝p​\(xi\|x<i\)​p​\(α\|xi,x<i\)qα​\(xi\|x<i\)\.\\gamma\(x\_\{i\},x\_\{<i\}\)\\approx\\frac\{p\(\\alpha\|x\_\{i\},x\_\{<i\}\)\\,p\(x\_\{i\}\|x\_\{<i\}\)\}\{q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\\,p\(\\alpha\|x\_\{<i\}\)\}\\propto\\frac\{p\(x\_\{i\}\|x\_\{<i\}\)\\,p\(\\alpha\|x\_\{i\},x\_\{<i\}\)\}\{q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\}\.

### Simplifyingγ\\gamma

LetV=\{xi∣p​\(xi\|x<i,α\)\>0\}V=\\left\\\{x\_\{i\}\\mid p\(x\_\{i\}\|x\_\{<i\},\\alpha\)\>0\\right\\\}be the set of tokens that can lead to a solution forα\\alpha\. Then,

qα​\(xi\|x<i\)=\{0if​xi∉Vp​\(xi\|x<i\)∑t∈Vp​\(y\|x<i\)otherwise\.\\displaystyle q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)=\\begin\{cases\}0\\qquad\\text\{if~\}x\_\{i\}\\not\\in V\\\\ \\frac\{p\(x\_\{i\}\|x\_\{<i\}\)\}\{\\sum\_\{t\\in V\}p\(y\|x\_\{<i\}\)\}\\qquad\\text\{otherwise\.\}\\end\{cases\}This means that the value ofγ\\gammais irrelevant for the first case, since the definition ofqα⋆q^\{\\star\}\_\{\\alpha\}multiplies it by zero\. It also allows us to simplifyγ\\gammafor the second case\. In that case,qα​\(xi\|x<i\)∝p​\(xi\|x<i\)q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\\propto p\(x\_\{i\}\|x\_\{<i\}\)because∑t∈Vp​\(y\|x<i\)\\sum\_\{t\\in V\}p\(y\|x\_\{<i\}\)is a constant that does not depend onxix\_\{i\}and the factorp​\(xi\|x<i\)qα​\(xi\|x<i\)\\frac\{p\(x\_\{i\}\|x\_\{<i\}\)\}\{q\_\{\\alpha\}\(x\_\{i\}\|x\_\{<i\}\)\}inγ\\gammabecomes a constant we can ignore\. Thus, ifγ​\(xi,x<i\)≈p​\(α\|xi,x<i\)\\gamma\(x\_\{i\},x\_\{<i\}\)\\approx p\(\\alpha\|x\_\{i\},x\_\{<i\}\)we have that

qα⋆​\(x\>s\|x≤s\)≈p​\(x\>s\|x≤s,α\)\.q^\{\\star\}\_\{\\alpha\}\(x\_\{\>s\}\|x\_\{\\leq s\}\)\\approx p\(x\_\{\>s\}\|x\_\{\\leq s\},\\alpha\)\.In other words, the correction factor is the probability that the LLM generates something that satisfies the constraint\.

### Proposed Solution: Lightweight Grammar Alignment

Still, computing the quantityp​\(α\|xi,x<i\)p\(\\alpha\|x\_\{i\},x\_\{<i\}\)is intractable\. A practical workaround is to train from data a regression model forγ\\gammathat looks at features of\(xi,x<i\)\(x\_\{i\},x\_\{<i\}\)and predicts an estimate ofp​\(α\|xi,x<i\)p\(\\alpha\|x\_\{i\},x\_\{<i\}\)\. Ifα\\alphais a context\-free grammar \(CFG\), we can use an interactive parser to expose its internal stateS​\(xi,x<i\)S\(x\_\{i\},x\_\{<i\}\)as a feature: this exposed state summarizes the prefix’s grammaticality so far and correlates with which future tokens keep the sequence valid, making it a natural signal for the same future validity thatp​\(α\|xi,x<i\)p\(\\alpha\|x\_\{i\},x\_\{<i\}\)measures\. Moreover, since we applyp​\(α\|xi,x<i\)p\(\\alpha\|x\_\{i\},x\_\{<i\}\)as a probability correction to valid tokens, the next token itself is another intuitive feature: much like an LR\(1\) parser uses a single look\-ahead token to resolve shift/reduce ambiguity about what to do next\(Knuth[1965](https://arxiv.org/html/2608.10137#bib.bib35)\), the candidate next token can itself trigger a parser state transition, making it an early signal of what comes next and whether the sequence stays grammatically valid\. However, LLM tokens and grammar lexemes rarely align one\-to\-one: a single LLM token can complete only part of a lexeme, in which case the parser makes no progress and the parser stateS​\(xi,x<i\)S\(x\_\{i\},x\_\{<i\}\)stays unchanged, leaving it uninformative about what comes next\. We therefore also expose the lexer state as a feature, since it tracks this finer\-grained, within\-lexeme progress and gives a signal about what the parser is likely to do once the lexeme completes, even when the parser state alone would not have moved\. Parser state and lexer state are thus complementary: parser state captures structure across completed lexemes but stalls mid\-lexeme, while lexer state captures within\-lexeme progress but is blind to structure beyond it\. Together with the next token, these three features giveγ\\gammaa compact but sufficient signal of the sequence’s grammatical trajectory\.

We build this model’s training data from LLM samples: for each of 1000 generated sequences per grammar, we run the masking tool’s incremental parser over the sequence and, at every decoding step, record the parser state, lexer state, and candidate next token as a feature row, labeling it according to whether the resulting sequence is grammatically valid, i\.e\., parsable in full\. We instantiate this correction model at two levels of capacity\. The simplest is a lightweight logistic regression model, which is cheap to train and to evaluate at each decoding step\. To capture non\-linear interactions between the parser state, lexer state, and next token that a linear model cannot, we also train a small Multi\-Layer Perceptron \(MLP\) over the same features: a compact feed\-forward network with two hidden layers \(64 and 32 units, ReLU activations\)\. We deliberately restrict the search to small architectures, selecting this configuration by cross\-validating on 5000 collected examples and picking the one with the lowest log\-loss\.

![Refer to caption](https://arxiv.org/html/2608.10137v1/reverse_kl_grid_big.png)Figure 5:Our variants remain close to the target distribution as sample estimates grow\. KL divergence is evaluated across four representative grammars and plotted as a function ofkk, the number of unique valid vanilla\-LLM samples used to estimate the target\. Our probability controller consistently maintains lower divergence askkscales\.

## 4Experiments

### Baselines\.

We compare SHIM against Syncode\(Ugareet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib13)\), a state\-of\-the\-art masking\-based GCD tool, and ASAp\(Parket al\.[2024](https://arxiv.org/html/2608.10137#bib.bib18)\), an online sampling method that iteratively reweights its distribution toward the target\. Because ASAp’s resampling cost grows with each sample, running it to convergence was computationally infeasible at our evaluation scale, so we cap it at 100 samples per grammar\.

### Metrics\.

We measure probabilistic integrity via KL divergence to the target distribution, and computational efficiency via average inference time per sample\. We estimateDK​L\(p\(⋅∣α\)∥q\)D\_\{KL\}\(p\(\\cdot\\mid\\alpha\)\\parallel q\), whereppis the LM’s distribution andqqis a method’s distribution\. We calculate this metric by drawing 1000 samples from the LM and keeping the grammar\-valid ones, then renormalizing bothppandqqover this finite set\.

### Experimental setup\.

We evaluate on the Syntax Guided Synthesis \(SyGuS\) invariant\-generation problems\(Aluret al\.[2019](https://arxiv.org/html/2608.10137#bib.bib37)\), following prior work\(Parket al\.[2024](https://arxiv.org/html/2608.10137#bib.bib18)\), usingMistral\-7B\-Instruct\-v0\.2as the base LLM\. We focus on INV\-BV, SyGuS’s bit\-vector invertibility\-condition split and the same benchmark ASAp was evaluated on; its grammar variants span a range of difficulty over a small, closed vocabulary, enabling an exact oracle distribution\. We additionally evaluate on text\-to\-SQL using Spider\(Yuet al\.[2019](https://arxiv.org/html/2608.10137#bib.bib36)\), whose schema\-dependent identifiers form a much larger, open vocabulary than INV\-BV’s, testing generalization across vocabulary structure\. Table[1](https://arxiv.org/html/2608.10137#S4.T1)gives the complete picture across all methods and BV4 grammars; the remainder of this section breaks this down into three parts, mirroring the feature levels introduced previously: \(1\) a full\-feature MLP correction using parser state, lexer state, and the candidate next token, \(2\) a lightweight logistic regression on the same features, compared against Syncode and our online sampling baseline ASAp, and \(3\) a next\-token\-only correction\. We will release our code and generated training data publicly upon publication under an open\-source license\.

### \(1\) Full\-feature correction with an MLP\.

We first ask whether a corrector with access to the full feature set \(next token, parser state, and lexer state\) can recover more of the LM’s original distribution than masking alone\. Table[1](https://arxiv.org/html/2608.10137#S4.T1)reports the results for Syncode, our MLP variant, and ASAp across all 14 grammars: our MLP variant reduces KL divergence over Syncode on 11 of 14 grammars and over ASAp on all 14, running roughly4\.6×4\.6\\timesfaster than ASAp on average \(3\.64s vs\. 16\.62s\)\. It remains slower than Syncode, though \(3\.64s vs\. 2\.97s\) – the overhead we address next with a lighter\-weight model\.

### \(2\) A lightweight logistic regression matches the MLP at a fraction of the cost\.

We next replace the MLP with a lightweight logistic regression \(LR\_FULL\) trained on the same full feature set, and compare both against Syncode and ASAp\. Table[1](https://arxiv.org/html/2608.10137#S4.T1)shows thatLR\_FULLmatches or beats Syncode on 12 of 14 grammars, which is almost the same coverage as the MLP variant\. While ASAp, despite reweighting its sampling distribution online, never achieves the lowest KL divergence in this comparison\. We also evaluate whether this gap holds as more of the target distribution is revealed\. Figure[5](https://arxiv.org/html/2608.10137#S3.F5)shows KL as a function ofkkacross four representative grammars\. Because an empirical KL estimate is optimistically biased when computed from few target samples, a curve that keeps rising askkgrows is not a method getting worse with more sampling, but a more complete picture of the target exposing a gap the low\-kkestimate had missed\. Under this test,MLPandLR\_FULLstay low and largely flat, so their small KL in Table[1](https://arxiv.org/html/2608.10137#S4.T1)was already close to the true value;LR\_NTstabilizes rather than climbs but is not always low\. ASAp instead climbs steadily and ends the worst of all methods on three of the four grammars shown, indicating its early competitiveness reflected an under\-sampled evaluation rather than genuine closeness to the target distribution\.

This gap widens once we account for inference cost\. Table[1](https://arxiv.org/html/2608.10137#S4.T1)’s bottom row showsLR\_FULLrunning in 2\.52s on average – faster than Syncode’s own 2\.97s – and roughly7×7\\timesfaster than ASAp’s 16\.62s\. Because we trainLR\_FULLonly once, offline, it requires no per\-sample online training, unlike ASAp, which must update its internal representation after every generated sequence\.LR\_FULLeven runs faster than Syncode overall\. Computingγ\\gammaadds a small per\-step cost, but by correcting for future grammaticality,LR\_FULLavoids the forced, longer completions that plain masking’s short\-sighted choices can produce; the resulting savings from needing fewer steps outweigh that added cost\.

Table 1:Our probability controller lowers KL divergence across grammars and methods while keeping inference fast\. KL divergence \(↓\\downarrow\) measures distortion relative to unconstrained generation across grammars and baselines\. Average latency per sequence \(seconds\) shows our lightweight controller adds negligible overhead over standard masked decoding, avoiding online sampling’s severe inference bottlenecks\.
### \(3\) The next token alone is enough to help, even with no parser or lexer access\.

Finally, we ask how much of this improvement survives whenLR\_NTrestricts the corrector to*only*the candidate next token, with no parser or lexer state at all\. This efficiency stems from the structure of BV4 grammars: because their terminals are notably short, individual LLM tokens frequently encapsulate the signal needed to trigger a parser state transition, so the next token alone provides an early, informative cue for whether a generation trajectory is losing its future grammatical correctness\. The next token’s disambiguating role here mirrors the one a lookahead token plays in LR\(1\) parsing, though without the parse state LR\(1\) normally pairs it with: for grammars with high overlap between LLM tokens and grammar lexemes, the next token alone still carries enough signal to guide the LLM toward accepting continuations, without the corrector ever seeing the parser or lexer state directly\. Table[1](https://arxiv.org/html/2608.10137#S4.T1)reports KL divergence for Syncode,LR\_NT, and ASAp across all 14 grammars\. As the table shows,LR\_NTis a genuinely weaker corrector than the full\-feature variants \(MLP,LR\_FULL\): it beats Syncode on exactly half the grammars rather than the vast majority, but it is never far behind Syncode even when it loses, and its correction model needs no parser or lexer state at all\. This trade\-off shows up in the bottom row too:LR\_NTruns in 2\.45s on average, marginally faster than Syncode’s 2\.97s and roughly7×7\\timesfaster than ASAp’s 16\.62s, while still costing less time than the heavierMLPvariant \(3\.64s\), echoing the trade\-off from Part \(1\)\.

### \(4\) A second domain: text\-to\-SQL\.

We use a sample of four pairs from Spider as our benchmark\. Table[2](https://arxiv.org/html/2608.10137#S4.T2)reports KL divergence for each row\. As on BV4, our lightweight correctors match or improve on Syncode’s masked distribution on most rows \(store\_product, entertainment\_awards, cre\_theme\_park\), though Syncode remains best on election\.

TheLR\_NTcolumn in Table[2](https://arxiv.org/html/2608.10137#S4.T2)shows that the next\-token\-only benefit from BV4 \(Part \(3\) above\) is conditional rather than universal: on store\_product,LR\_NTimproves on the full\-feature variants, consistent with the LR\(1\) lookahead intuition; but on entertainment\_awards, it is substantially worse than every full\-feature variant\. This is not a contradiction of the lookahead story so much as a boundary on it, and the four rows’ queries make the boundary concrete: all four share the same grammar structure, differing only in their closed vocabulary\.LR\_NTwins on store\_product, whose query matches a substring viaLIKE "%Scanner%"– once the LLM starts spelling out the pattern, the next token is nearly the whole signal, mirroring BV4’s short\-terminal case\. Its worst row is entertainment\_awards, a flat numeric disjunction with the smallest vocabulary of the four and no strings at all; the difficulty there is not vocabulary size but that its schema has several near\-duplicate column names \(e\.g\.Num\_of\_Audience,NumOfAudience,Total\_Audience\), which only diverge many tokens in – the bookkeeping the parser and lexer state provide andLR\_NTdiscards\. cre\_theme\_park has the largest vocabulary of the four but only a middling penalty, confirming vocabulary size alone is not the driver\. Election, the onlyJOINrow, isLR\_NT’s second\-worst: which table a column belongs to is a structural decision the next token alone cannot track\.

Sample generation time also diverges sharply across methods\. On store\_product, Syncode and our correctors generate a valid sample in 1\.7–4\.0s on average, while ASAp takes18\.8718\.87s, roughly an order of magnitude slower\. This gap narrows on the other three rows, where every method falls in the22–88s range, but ASAp’s cost grows more steeply, reaching9393–108108s on election and cre\_theme\_park\. On cre\_theme\_park, that requires simplifying ASAp’s vocabulary to obtain a timing result; since this changes the target distribution, we omit its KL for that row\. ASAp’s recognizer tracks every live parse alternative as a separate state rather than sharing prefixes across near\-duplicates, so its per\-step cost can grow combinatorially as the vocabulary grows more repetitive\. SHIM’s inference cost, by contrast, is fixed regardless of grammar ambiguity\.

Table 2:Generalization to complex SQL queries\. Rows report KL divergence per query; the bottom row shows mean inference time \(seconds\)\.§Grammar simplified so ASAp’s sampling terminates in finite time\.

## 5Related Work

### Grammar Constrained Decoding:

These methods enforce grammar conformance through token\-level masking, differing mainly in how they make that masking efficient\. Syncode\(Ugareet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib13)\), Xgrammar\(Donget al\.[2025](https://arxiv.org/html/2608.10137#bib.bib14)\), and GREATGRAMMA\(Parket al\.[2025](https://arxiv.org/html/2608.10137#bib.bib15)\)each precompute an offline artifact – a token mask store or token\-lexeme dependency map – and consult it via lookup during decoding\. Outlines\(Willard and Louf[2023](https://arxiv.org/html/2608.10137#bib.bib17)\)instead reformulates decoding as transitions over an automaton whose states map directly to allowed\-token masks\. DOMINO\(Beurer\-Kellneret al\.[2024](https://arxiv.org/html/2608.10137#bib.bib16)\)targets the LLM\-token/grammar\-lexeme mismatch directly, classifying tokens as a start, end, or continuation subterminal and deriving the mask from a subterminal tree\. Existing GCD methods guarantee grammar conformance only with respect to tokens generated*so far*, ignoring each token’s effect on*future*grammar conformance and distorting the LM’s probability distribution by forcing it into a token domain its training never covered\. We show this distortion can be learned from data, using features available at decoding time – the candidate next token together with the masking mechanism’s parser and lexer state – to correct masked probabilities and restore GCD’s probabilistic integrity\.

### Online Sampling Methods:

Rather than masking greedily, these methods restore the LM’s true conditional distribution by tracking which prefixes are grammatical dead ends and repeatedly resampling around them\. ASAp\(Parket al\.[2024](https://arxiv.org/html/2608.10137#bib.bib18)\)and CARS\(Paryset al\.[2026](https://arxiv.org/html/2608.10137#bib.bib19)\)both maintain such dead\-end information and reweight future sampling to avoid it\. MCMC\(Gonzalezet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib20)\)and AWRS\(Lipkinet al\.[2025](https://arxiv.org/html/2608.10137#bib.bib21)\)adopt a propose\-and\-correct strategy, iteratively refining or adaptively rejecting candidates to prune invalid paths early\. SMC Steering\(Lewet al\.[2023](https://arxiv.org/html/2608.10137#bib.bib25)\)instead formalizes constrained generation as Sequential Monte Carlo posterior inference, using a learned proposal and potential to steer particles toward valid completions\. All five methods share the same downside: they must update their internal representation and recompute probabilities after every sampled sequence, bloating inference time\. SHIM instead uses a lightweight probability controller trained offline and adds no inference\-time overhead, even speeding up inference by aligning masked probabilities with the underlying model\.

### Tractable Probabilistic Model Augmentation:

GeLaTo\(Zhanget al\.[2023](https://arxiv.org/html/2608.10137#bib.bib23)\), Ctrl\-G\(Zhanget al\.[2024](https://arxiv.org/html/2608.10137#bib.bib24)\), and P\-GCD\(Danget al\.[2026](https://arxiv.org/html/2608.10137#bib.bib22)\)all pair the LLM with a second, tractable model, typically an HMM distilled offline via maximum likelihood from LLM samples\. At each step, this model’s exact constraint\-satisfaction likelihood is multiplied into the LLM’s next\-token distribution\. They differ mainly in how they reason about constraints\. GeLaTo uses a hand\-crafted dynamic program over CNF keyword clauses\. Ctrl\-G generalizes this to arbitrary DFAs via a GPU\-parallelized backward recurrence\. P\-GCD instead fuses a tensorized constraint automaton with the distilled HMM via circuit multiplication, using the result as an SMC proposal and potential\. SHIM follows this same augmentation philosophy, pairing the LLM with a small auxiliary model rather than modifying its weights or hard\-masking its outputs\. However, SHIM avoids distilling a full HMM approximation of the LLM’s output distribution\. It instead learns only the narrow correction induced by grammar masking, from a few decoding\-time features\. This makes SHIM’s controller orders of magnitude smaller, cheap to retarget to new grammars, and interpretable, while still matching or exceeding prior methods’ distributional fidelity\.

## 6Conclusion

Language models are increasingly deployed in real\-world applications where strict adherence to formal constraints is necessary, ranging from code parsing and auto\-formalization to structured data processing engines\. While Grammar\-Constrained Decoding \(GCD\) guarantees structural compliance in these settings, maintaining the LLM’s true probability distribution remains challenging\. Traditional token masking is fast but distorts the distribution, while alternatives such as online sampling or HMM\-based augmentation improve fidelity at the cost of significant computational overhead or complex output distribution modeling\. We introduce SHIM, which avoids these pitfalls by learning only the probability adjustment based on the internal parser state instead of masking\. SHIM learns this correction offline from lightweight decoding\-time features already computed during constrained decoding – the internal parser and lexer states, together with the candidate next token – which inherently encode future grammaticality yet have remained completely unexploited for logit adjustment\. SHIM applies the learned correction during inference with negligible runtime overhead\.

On the BV4 SyGuS benchmark, our full\-feature MLP – robust across varying feature availabilities, model capacities, and grammar families – achieves up to113×113\\timeslower KL divergence than Syncode \(mean23×23\\times, median7×7\\times\) and up to235×235\\timeslower divergence than online sampling \(mean56×56\\times, median21×21\\times\)\. A lightweight logistic regression trained on the same state features matches or exceeds the MLP’s performance on several grammars while executing as fast as, or faster than, standard token masking\. When grammatical validity depends primarily on immediate local context, even a next\-token\-only controller—requiring zero parser or lexer state access—substantially improves upon both standard GCD and online sampling\. On Spider, a real\-world text\-to\-SQL benchmark with larger and more ambiguous grammars, SHIM matches or surpasses baseline distributions while maintaining fast inference speeds\. In contrast, online sampling scales poorly on complex SQL rows, failing to complete within practical time budgets\. Overall, these results demonstrate that lightweight, offline\-trained probability control effectively closes the gap between speed and distributional fidelity in grammar\-constrained decoding\.

## References

- A\. V\. Aho, M\. S\. Lam, R\. Sethi, and J\. D\. Ullman \(2006\)Compilers: principles, techniques, and tools\.2nd edition,Pearson Education,Boston, MA, USA\.External Links:ISBN 0321486811Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px3.p1.1)\.
- R\. Alur, D\. Fisman, S\. Padhi, R\. Singh, and A\. Udupa \(2019\)SyGuS\-comp 2018: results and analysis\.External Links:1904\.07146,[Link](https://arxiv.org/abs/1904.07146)Cited by:[§4](https://arxiv.org/html/2608.10137#S4.SS0.SSS0.Px3.p1.1)\.
- J\. Austin, A\. Odena, M\. Nye, M\. Bosma, H\. Michalewski, D\. Dohan, E\. Jiang, C\. Cai, M\. Terry, Q\. Le, and C\. Sutton \(2021\)Program synthesis with large language models\.External Links:2108\.07732,[Link](https://arxiv.org/abs/2108.07732)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px1.p1.1)\.
- L\. Beurer\-Kellner, M\. Fischer, and M\. Vechev \(2024\)Guiding llms the right way: fast, non\-invasive constrained generation\.External Links:2403\.06988,[Link](https://arxiv.org/abs/2403.06988)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px1.p1.1)\.
- M\. Chen, J\. Tworek, H\. Jun, Q\. Yuan, H\. P\. de Oliveira Pinto, J\. Kaplan, H\. Edwards, Y\. Burda, N\. Joseph, G\. Brockman, A\. Ray, R\. Puri, G\. Krueger, M\. Petrov, H\. Khlaaf, G\. Sastry, P\. Mishkin, B\. Chan, S\. Gray, N\. Ryder, M\. Pavlov, A\. Power, L\. Kaiser, M\. Bavarian, C\. Winter, P\. Tillet, F\. P\. Such, D\. Cummings, M\. Plappert, F\. Chantzis, E\. Barnes, A\. Herbert\-Voss, W\. H\. Guss, A\. Nichol, A\. Paino, N\. Tezak, J\. Tang, I\. Babuschkin, S\. Balaji, S\. Jain, W\. Saunders, C\. Hesse, A\. N\. Carr, J\. Leike, J\. Achiam, V\. Misra, E\. Morikawa, A\. Radford, M\. Knight, M\. Brundage, M\. Murati, K\. Mayer, P\. Welinder, B\. McGrew, D\. Amodei, S\. McCandlish, I\. Sutskever, and W\. Zaremba \(2021\)Evaluating large language models trained on code\.External Links:2107\.03374,[Link](https://arxiv.org/abs/2107.03374)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px1.p1.1)\.
- X\. Chen, M\. Lin, N\. Schärli, and D\. Zhou \(2023\)Teaching large language models to self\-debug\.External Links:2304\.05128,[Link](https://arxiv.org/abs/2304.05128)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1)\.
- A\. Chowdhery, S\. Narang, J\. Devlin, M\. Bosma, G\. Mishra, A\. Roberts, P\. Barham, H\. W\. Chung, C\. Sutton, S\. Gehrmann, P\. Schuh, K\. Shi, S\. Tsvyashchenko, J\. Maynez, A\. Rao, P\. Barnes, Y\. Tay, N\. Shazeer, V\. Prabhakaran, E\. Reif, N\. Du, B\. Hutchinson, R\. Pope, J\. Bradbury, J\. Austin, M\. Isard, G\. Gur\-Ari, P\. Yin, T\. Duke, A\. Levskaya, S\. Ghemawat, S\. Dev, H\. Michalewski, X\. Garcia, V\. Misra, K\. Robinson, L\. Fedus, D\. Zhou, D\. Ippolito, D\. Luan, H\. Lim, B\. Zoph, A\. Spiridonov, R\. Sepassi, D\. Dohan, S\. Agrawal, M\. Omernick, A\. M\. Dai, T\. S\. Pillai, M\. Pellat, A\. Lewkowycz, E\. Moreira, R\. Child, O\. Polozov, K\. Lee, Z\. Zhou, X\. Wang, B\. Saeta, M\. Diaz, O\. Firat, M\. Catasta, J\. Wei, K\. Meier\-Hellstern, D\. Eck, J\. Dean, S\. Petrov, and N\. Fiedel \(2023\)PaLM: scaling language modeling with pathways\.Journal of Machine Learning Research24\(240\),pp\. 1–113\.External Links:[Link](http://jmlr.org/papers/v24/22-1144.html)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1)\.
- M\. Dang, L\. Song, H\. Zhang, J\. Zhao, G\. V\. den Broeck, and S\. Ermon \(2026\)Mitigating bias in locally constrained decoding via tractable proposals\.External Links:2606\.01926,[Link](https://arxiv.org/abs/2606.01926)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px3.p1.1),[footnote 1](https://arxiv.org/html/2608.10137#footnote1)\.
- Y\. Dong, C\. F\. Ruan, Y\. Cai, Z\. Xu, Y\. Zhao, R\. Lai, and T\. Chen \(2025\)XGrammar: flexible and efficient structured generation engine for large language models\.InProceedings of Machine Learning and Systems,M\. Zaharia, G\. Joshi, and Y\. Lin \(Eds\.\),Vol\.7,pp\.\.External Links:[Link](https://proceedings.mlsys.org/paper_files/paper/2025/file/5c20ca4b0b20b0bd2f1d839dc605e70f-Paper-Conference.pdf)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px1.p1.1)\.
- E\. A\. Gonzalez, S\. Vaidya, K\. Park, R\. Ji, T\. Berg\-Kirkpatrick, and L\. D’Antoni \(2025\)Constrained sampling for language models should be easy: an mcmc perspective\.External Links:2506\.05754,[Link](https://arxiv.org/abs/2506.05754)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px2.p1.1)\.
- D\. E\. Knuth \(1965\)On the translation of languages from left to right\.Information and Control8\(6\),pp\. 607–639\.External Links:ISSN 0019\-9958,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/S0019-9958%2865%2990426-2),[Link](https://www.sciencedirect.com/science/article/pii/S0019995865904262)Cited by:[§3](https://arxiv.org/html/2608.10137#S3.SS0.SSS0.Px4.p1.10)\.
- A\. K\. Lew, T\. Zhi\-Xuan, G\. Grand, and V\. K\. Mansinghka \(2023\)Sequential monte carlo steering of large language models using probabilistic programs\.External Links:2306\.03081,[Link](https://arxiv.org/abs/2306.03081)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px2.p1.1),[footnote 1](https://arxiv.org/html/2608.10137#footnote1)\.
- L\. Li, S\. Rahili, and Y\. Zhao \(2025\)Correctness\-guaranteed code generation via constrained decoding\.External Links:2508\.15866,[Link](https://arxiv.org/abs/2508.15866)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px1.p1.1)\.
- Y\. Li, D\. Choi, J\. Chung, N\. Kushman, J\. Schrittwieser, R\. Leblond, T\. Eccles, J\. Keeling, F\. Gimeno, A\. Dal Lago, T\. Hubert, P\. Choy, C\. de Masson d’Autume, I\. Babuschkin, X\. Chen, P\. Huang, J\. Welbl, S\. Gowal, A\. Cherepanov, J\. Molloy, D\. J\. Mankowitz, E\. Sutherland Robson, P\. Kohli, N\. de Freitas, K\. Kavukcuoglu, and O\. Vinyals \(2022\)Competition\-level code generation with alphacode\.Science378\(6624\),pp\. 1092–1097\.External Links:ISSN 1095\-9203,[Link](http://dx.doi.org/10.1126/science.abq1158),[Document](https://dx.doi.org/10.1126/science.abq1158)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px1.p1.1)\.
- B\. Lipkin, B\. LeBrun, J\. H\. Vigly, J\. Loula, D\. R\. MacIver, L\. Du, J\. Eisner, R\. Cotterell, V\. Mansinghka, T\. J\. O’Donnell, A\. K\. Lew, and T\. Vieira \(2025\)Fast controlled generation from language models with adaptive weighted rejection sampling\.External Links:2504\.05410,[Link](https://arxiv.org/abs/2504.05410)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px2.p1.1),[footnote 1](https://arxiv.org/html/2608.10137#footnote1)\.
- A\. Lu, H\. Zhang, Y\. Zhang, X\. Wang, and D\. Yang \(2023\)Bounding the capabilities of large language models in open text generation with prompt constraints\.External Links:2302\.09185,[Link](https://arxiv.org/abs/2302.09185)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px1.p1.1)\.
- Y\. Lu, H\. Li, X\. Cong, Z\. Zhang, Y\. Wu, Y\. Lin, Z\. Liu, F\. Liu, and M\. Sun \(2025\)Learning to generate structured output with schema reinforcement learning\.External Links:2502\.18878,[Link](https://arxiv.org/abs/2502.18878)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px1.p1.1)\.
- K\. Park, J\. Wang, T\. Berg\-Kirkpatrick, N\. Polikarpova, and L\. D'Antoni \(2024\)Grammar\-aligned decoding\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37,pp\. 24547–24568\.External Links:[Document](https://dx.doi.org/10.52202/079017-0774),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/file/2bdc2267c3d7d01523e2e17ac0a754f3-Paper-Conference.pdf)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p2.1),[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px4.p2.2),[§2](https://arxiv.org/html/2608.10137#S2.p2.2),[§4](https://arxiv.org/html/2608.10137#S4.SS0.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2608.10137#S4.SS0.SSS0.Px3.p1.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px2.p1.1)\.
- K\. Park, T\. Zhou, and L\. D’Antoni \(2025\)Flexible and efficient grammar\-constrained decoding\.External Links:2502\.05111,[Link](https://arxiv.org/abs/2502.05111)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px1.p1.1)\.
- P\. Parys, S\. Vaidya, T\. Berg\-Kirkpatrick, and L\. D’Antoni \(2026\)Constrained adaptive rejection sampling\.External Links:2510\.01902,[Link](https://arxiv.org/abs/2510.01902)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px2.p1.1)\.
- E\. Shinan \(2018\)Lark: a parsing toolkit for python\.External Links:[Link](https://github.com/lark-parser/lark)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px4.p1.1)\.
- S\. Tenckhoff, M\. Koddenbrock, and E\. Rodner \(2026\)LLMStructBench: benchmarking large language model structured data extraction\.External Links:2602\.14743,[Link](https://arxiv.org/abs/2602.14743)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px1.p1.1)\.
- S\. Ugare, T\. Suresh, H\. Kang, S\. Misailovic, and G\. Singh \(2025\)SynCode: LLM generation with grammar augmentation\.Transactions on Machine Learning Research\.Note:External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=HiUZtgAPoH)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px4.p2.2),[§4](https://arxiv.org/html/2608.10137#S4.SS0.SSS0.Px1.p1.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px1.p1.1)\.
- T\. A\. Wagner and S\. L\. Graham \(1998\)Efficient and flexible incremental parsing\.ACM Trans\. Program\. Lang\. Syst\.20\(5\),pp\. 980–1013\.External Links:ISSN 0164\-0925,[Link](https://doi.org/10.1145/293677.293678),[Document](https://dx.doi.org/10.1145/293677.293678)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px3.p2.3)\.
- B\. T\. Willard and R\. Louf \(2023\)Efficient guided generation for large language models\.External Links:2307\.09702,[Link](https://arxiv.org/abs/2307.09702)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p1.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px1.p1.1)\.
- T\. Yu, R\. Zhang, K\. Yang, M\. Yasunaga, D\. Wang, Z\. Li, J\. Ma, I\. Li, Q\. Yao, S\. Roman, Z\. Zhang, and D\. Radev \(2019\)Spider: a large\-scale human\-labeled dataset for complex and cross\-domain semantic parsing and text\-to\-sql task\.External Links:1809\.08887,[Link](https://arxiv.org/abs/1809.08887)Cited by:[§4](https://arxiv.org/html/2608.10137#S4.SS0.SSS0.Px3.p1.1)\.
- H\. Zhang, M\. Dang, N\. Peng, and G\. Van Den Broeck \(2023\)Tractable control for autoregressive language generation\.InProceedings of the 40th International Conference on Machine Learning,A\. Krause, E\. Brunskill, K\. Cho, B\. Engelhardt, S\. Sabato, and J\. Scarlett \(Eds\.\),Proceedings of Machine Learning Research, Vol\.202,pp\. 40932–40945\.External Links:[Link](https://proceedings.mlr.press/v202/zhang23g.html)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px3.p1.1)\.
- H\. Zhang, P\. Kung, M\. Yoshida, G\. Van den Broeck, and N\. Peng \(2024\)Adaptable logical control for large language models\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37,pp\. 115563–115587\.External Links:[Document](https://dx.doi.org/10.52202/079017-3670),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/file/d15c16cf5619a2b1606da5fc88e3f1a9-Paper-Conference.pdf)Cited by:[§1](https://arxiv.org/html/2608.10137#S1.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2608.10137#S5.SS0.SSS0.Px3.p1.1)\.