A closer look at “The Parser Already Knows”

This is a companion post for “The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding” (arXiv:2608.10137), which I wrote with Yaoxuan Wu, Guy Van den Broeck, and Miryung Kim. Instead of re-summarizing the abstract, I want to walk through the toy example by hand, dwell on a connection to classic parsing theory that we didn’t really have room for in eight pages, and leave this post open as a place to drop in extra diagrams and earlier framings of the idea as I get around to writing them up.

The one-sentence problem

Grammar Constrained Decoding (GCD) keeps a language model syntactically honest by masking out any token that would immediately break the grammar. The question we kept running into while working on this: what if a token is valid right now, but picking it corners the model into a bad continuation later? Masking has no way to see that coming, and it’s exactly what quietly distorts the model’s output distribution.

A toy grammar you can actually compute by hand

We used a small counterexample grammar to make this concrete, small enough that you can check it with fractions instead of just trusting us. It accepts binary strings of length five, with one twist: a string can only continue with more 0s if it started with 0.

\[ G_{sk}: \quad 00000 \mid 1(0 \mid 1)^4 \]

That’s 1 valid string starting with 0 (namely 00000) and 16 valid strings starting with 1, so 17 grammar-satisfying strings total. If the underlying LLM assigns uniform probability over all 5-bit strings, every valid string should end up with equal probability once we condition on grammar-validity and renormalize.

So here’s the question we asked next: what does greedy masking actually do at the very first step? Before masking, the model splits evenly between the first token being 0 or 1. Say it samples 0. From here, masking has no choice left: the only grammar-valid completion after a leading 0 is 0000, so every remaining step is forced. Under token-masked decoding, the string 00000 ends up with the same probability as that very first coin flip, way more than its fair share of 1 in 17.

That’s the whole paper in miniature, really. Local validity checks are blind to how much future freedom a choice destroys, and by the time you notice, the damage is already baked into the distribution.

So where does the correction actually come from?

Our fix, which we call SHIM, multiplies the masked distribution by a correction factor at each step instead of touching the model’s weights at all. A quick Bayes’ rule expansion shows the ideal correction is proportional to the probability that committing to a given token still leaves a grammar-valid continuation reachable. That’s intractable to compute exactly (it’s asking the model to see its own future), which is why we train a small offline model to approximate it, using features that are already just lying around: the parser state, the lexer state, and the candidate token itself.

Why we needed both parser state and lexer state

The part of this paper I find most quietly satisfying is the parser and lexer split, because it resolves something that’s easy to hand wave past: LLM tokens and grammar lexemes don’t line up one to one.

Take the BV4 bit-vector grammar and the string (bvand s t). The opening ( completes a lexeme by itself, so the parser jumps straight from \(S_0\) to \(S_1\). Now suppose the LLM’s tokenizer emits b and v as two separate tokens. Does the parser move? No, it doesn’t, it only advances once a full operator token is consumed, so as far as the parser can tell, nothing has happened yet. But the lexer has quietly been narrowing things down: its buffer now reads "bv", which already rules out every BV4 operator except bvand, bvlshr, and bvor (see Figures 2 and 3 in the paper for the parser state machine and lexer trie).

So which one do you trust, the parser or the lexer? Turns out you need both, and they’re not redundant with each other. Parser state gives you structure across completed lexemes, but it stalls out mid-lexeme. Lexer state gives you progress within a lexeme, but it’s blind to anything beyond it. SHIM reads both because each one is filling in exactly what the other one misses.

Figure 4 in the paper stitches the whole pipeline together, worked through step by step on the toy grammar from earlier: raw LLM probabilities, which tokens survive masking, the structured features extracted, and the final corrected probabilities.

A detour into LR(1) parsing, because I think it’s worth it

We mention in passing that using the next token as a feature mirrors how LR(1) parsers use a single token of lookahead to resolve ambiguity (this goes all the way back to Knuth in 1965), but I don’t think we ever really sat with why that analogy holds, so let me do that here. An LR(1) parser sits on a stack of partially reduced grammar symbols, and at some point in parsing it genuinely can’t tell whether it should shift the next input symbol onto the stack or reduce using a rule it’s already completed. One token of lookahead, for a well-behaved grammar, is exactly enough to break that tie.

Our cheapest variant, which only looks at the candidate next token and ignores parser and lexer state entirely, is doing the same job but on the probability axis instead of the decision axis. Instead of resolving “shift or reduce,” it’s resolving “does this token still leave the grammar reachable.” And here’s the fun part: this variant’s performance is exactly as conditional as the LR(1) analogy would predict. It wins on grammars where tokens and lexemes line up tightly, like BV4’s short operator names. It loses precisely where the disambiguating signal lives further back than one token, like a SQL query where knowing which table a column belongs to is a structural fact no single next token can carry on its own. That’s a genuinely LR(1)-shaped failure mode, not just “the small model underperforms.”

More diagrams and earlier drafts

Before it was SHIM, this project was drafted under a different name, Grammar-Tailored Decoding (GTD), on the same \(G_{sk}\) toy grammar and the same core idea. That draft never got submitted anywhere and eventually got scrapped for the tighter SHIM framing, but a few of its diagrams are worth keeping around.

This is the cleanest version of the “masking traps mass, GTD reallocates it” argument from that draft, labeled explicitly enough to stand on its own:

And a version of the lexer-state mechanism itself, worked through on bvudiv this time instead of bvand, showing exactly which features get read off at the moment the model is about to generate u:

Here’s the original end-to-end workflow, offline training phase and all:

The diagram I genuinely miss from the final paper is the lexer-branching example beyond BV4: a restricted hex-value terminal, where the lexer state narrows a wide-open LLM prior down to exactly three legal digits.