Many applications need language models to emit text that obeys a formal grammar, such as valid JSON, executable SQL, or well-typed code. The standard way to enforce this is grammar-constrained decoding. An incremental parser reads the output token by token and, at each step, forbids every next token that could not lead to a valid string. A second standard technique, speculative decoding, makes generation faster: a cheap "drafter" guesses several tokens ahead, and the large model checks all of the guesses in one forward pass, keeping the longest prefix it agrees with. The two techniques fit together poorly. Speculative decoding verifies a whole tree of guessed continuations at once. The parser, as built today, computes one exact mask of legal tokens per position, at a cost of several to tens of milliseconds each. That is comparable to a forward pass. Run a mask at every node of a 50-node draft tree and the parser can absorb the entire speedup.
This note proposes a different division of labor. The drafter works under cheap, deliberately loose grammar masks, and parser states are shared across tree branches that begin with the same tokens. Exact masks are computed lazily, only along the single path the verifier actually walks. The parser's own state also decides how the draft tree is shaped. Where the grammar forces the next tokens, such as a closing bracket or a schema key, they are inserted for free. Where the parser sees a real structural choice, the tree branches. Inside an identifier or string literal, it drafts a single chain. The resulting sampler is provably identical in output distribution to ordinary token-by-token grammar-constrained sampling, and the parser's cost scales with tokens accepted rather than tokens drafted.
Core Claim
Mask both models with the grammar and run standard speculative sampling: this simple combination is exact with respect to the masked target distribution. Its practical speed is limited by two things that an incremental parser is well placed to fix. The first is the cost of computing exact masks at every draft-tree node. The second is draft trees shaped by drafter confidence alone, which ignore the fact that legal choices in structured output are concentrated at a few parser decision points.
Exactness survives a looser drafter mask for a simple reason. Speculative sampling accepts a drafted token $x$ with probability $\min(1, \tilde p(x)/q(x))$, where $\tilde p$ is the large model's distribution after exact grammar masking and $q$ is whatever distribution the drafter actually sampled from. If $q$ is masked only by a superset of the legal tokens, an illegal draft has $\tilde p(x)=0$ and is always rejected. The residual resampling step, drawing from the normalized $\max(0,\tilde p - q)$, then only ever produces legal tokens. The output is therefore distributed exactly as token-by-token constrained sampling from $\tilde p$.
Exact masks are applied to output logits after the forward pass, not inside it. They are only ever needed at nodes the left-to-right acceptance walk visits: the accepted path plus one rejection point. The same argument covers any deterministic prefix-dependent filter applied to the verifier. One example is the budget filter of Stay Within Your Bounds, which discards prefixes whose minimum distance to a complete parse exceeds the remaining token budget.
Relation to Prior Work
The closest bridges between the two areas each leave out the piece this proposal supplies.
Several papers supply the parsing machinery we reuse but do not speculate. Flexible and Efficient Grammar-Constrained Decoding (GREATGRAMMA) composes the tokenizer with the grammar's lexer into a single transducer, which handles subword tokens that split or span grammar terminals. It also uses a cheap finite-automaton over-approximation for tokens whose validity does not depend on the parser's stack. It reports 5–32 ms of masking per token, but it is strictly a next-token mask provider. We reuse its transducer and its over-approximation as the drafter's loose mask, and we unroll both over a tree with prefix-shared states. Stay Within Your Bounds adds precomputed distance-to-acceptance so that outputs close before the budget runs out. It runs sequential beam search. We use its distances both as an exact verifier-side filter and as a signal for where to stop drafting. ChopChop extends incremental checking to types and program equivalence. Its 50–200 ms per-token overhead is exactly the regime where lazy exact checking along one path, rather than across a whole tree, would matter most.
Other papers speculate but ignore grammar. Graph-Structured Speculative Decoding observes that over 70% of draft-tree tokens are redundant across branches and merges them into a graph. Its argument that tree shape matters is the methodological precedent for parser-shaped trees, but its pruning uses only drafter probabilities. SAM Decoding drafts from suffix-automaton retrieval over generated and static text. It is relevant here because structured outputs repeat schema keys heavily.
Constrained Decoding with Speculative Lookaheads is the nearest attempt to combine the two. It handles lexical and reward-model constraints with heuristic acceptance thresholds, and it is explicitly not distribution-preserving and tracks no grammar state.
One paper constrains what our claim can be. Grammar-Aligned Decoding shows that masked sampling distorts the model's distribution relative to true conditioning on grammaticality. Our method is exact with respect to the masked distribution, not the grammar-conditioned one, and we state this as a scope limit rather than claim to fix it.
Is Incremental Structure Prediction Process Universal across Languages? motivates the tree-shaping policy. It shows that how far ahead a parser commits to structure trades easier learning against wider search, and that the best trade-off depends on where branching occurs. We carry this over as a tunable "structural speculation depth" for the draft tree.
Research Program
The system has three parts.
The first is a tree-unrolled lexing transducer. Each draft-tree node stores a pointer to its parser configuration, and children share the parent's configuration until their tokens diverge. During drafting, each node gets GREATGRAMMA's stack-invariant over-approximate mask. The full pushdown check is never run at drafting time.
The second is a lazy exact verifier. After the large model scores the tree in one pass, the acceptance walk computes exact masks only for the nodes it visits. It optionally applies the budget-distance filter, then performs the min-ratio test and residual resampling described above.
The third is a parser-shaped tree builder. At each frontier node it reads two signals: the number of legal grammar terminals under the current configuration, and the drafter's entropy. It uses them in three ways. Spans with exactly one legal continuation are appended without any drafter call or tree budget. Tree width is spent at nodes where the parser has several legal terminals and the drafter is uncertain. Inside a single terminal, such as an identifier or literal, the builder drafts a linear chain.
On the analysis side, we will prove the exactness statement formally and measure where the time goes: drafter, verifier, eager masking, and lazy masking. This tests the premise that mask cost, not acceptance rate, is the binding constraint for structured speculative decoding. We will also study when parser-shaped trees help. Our hypothesis is that gains concentrate in schema-heavy outputs like JSON and SQL, and are smaller in free-form code where most uncertainty sits inside identifiers.
Baselines
The do-nothing reference is ordinary autoregressive grammar-constrained decoding with GREATGRAMMA masks, run on the same model, grammar, GPU, and sampling temperature. All speedups are reported relative to it. Its validity numbers anchor quality. On json-mode-eval, Stay Within Your Bounds reports 100% syntactic validity for its method, against 77–92% for SynCode and XGrammar. On Spider it reports 51.5% execution accuracy for Llama-3.2-3B, against 46.3% unconstrained.
The strongest competitor is "shared-mask tree speculative decoding." This is a standard draft tree, built as in Graph-Structured Speculative Decoding from drafter probabilities, with exact GREATGRAMMA masks computed eagerly at every node for both drafter and verifier. It is the strongest because it is already exact, it is easy to build, and it captures every gain from simply refusing to draft illegal tokens. It gets the same drafter, the same tree-node budget swept over the same grid, and the same tuning time as our method.
There is no reported result on Lacuna for grammar-constrained speculative decoding speedups on json-mode-eval, Spider, or code grammars. The nearest reported speedups are for unconstrained text. Graph-Structured Speculative Decoding reports 1.96× wall-clock on GSM8K with LLaMA-2-70B. SPEED-Bench reports a 1.90× mean speedup for EAGLE3 on Llama 3.3 70B with draft length 3. These calibrate what a good speculative system achieves. They are not directly comparable targets.
Beating the strongest competitor means two things. Our method must deliver at least 15% higher wall-clock speedup at equal tree budget on JSON and SQL. Its output distribution must be statistically indistinguishable from the do-nothing reference.
Three ablations isolate the ingredients:
- Lazy exact masking alone. Keep the competitor's confidence-shaped tree but replace eager exact masks with loose draft masks and lazy exact verification. This isolates the cost argument.
- Forced-span insertion alone. Add free grammar-forced spans to the competitor's tree. This isolates the cheapest parser contribution.
- Parser-shaped allocation alone. Use parser-shaped allocation with eager exact masks. This isolates tree shape.
A linear-chain masked speculative decoder, with no tree, is included to show how much of the gain needs a tree at all.
Why not just…?
Why not just mask both drafter and verifier with the grammar and run standard speculative decoding? This is the real threat, which is why it is our strongest baseline rather than a straw man. It is exact and simple. The open question is whether it is fast. GREATGRAMMA's measured 5–32 ms per masked token is comparable to a 7–8B forward pass, so eager masking over dozens of tree nodes could cancel the speedup. That reasoning is still an inference, not a measurement. The time breakdown and the lazy-masking ablation settle it directly. If eager masking takes under about 10% of wall-clock time and the competitor matches our speedup within 5%, the cost argument is wrong. We would then report that negative result and reduce the contribution to tree shaping.
Why not just let the parser draft forced tokens and use a normal drafter otherwise? Forced-span insertion is one of our own ablations, because it may well capture most of the benefit on rigid schemas. It does nothing at nodes with several legal choices, which is where rejections happen. Comparing it against full parser-shaped allocation shows whether branching at structural decision points adds anything beyond free forced spans.
Why not just retrieve repeated structure with a suffix automaton? SAM Decoding drafts by exact matching against prior text. It is 18% faster than other retrieval drafters and adds 3–11% on top of EAGLE-2. JSON keys and SQL keywords repeat, so retrieval could be strong. It cannot generalize to new nesting patterns, though, and it falls back to a model drafter on short matches. We will run SAM-style drafting under the same shared masks, and also as a draft source inside our tree. Retrieval and parser shaping then compete and combine on equal terms.
Why not just relax acceptance, as Cactus does? Cactus bounds the divergence from the target in exchange for higher acceptance and reaches nearly 1.9×. It deliberately changes the output distribution, and in formal syntax a single substituted delimiter breaks validity. Our method gives up no exactness, so the methods answer different questions. We will report Cactus with masks as a reference point on the speed–fidelity curve, not as a like-for-like competitor.
Proposed Experiments
We will use the target and drafter pairings from Stay Within Your Bounds: Llama-3.1-8B verified with Llama-3.2-3B drafting, and Qwen2.5-7B with a same-tokenizer small drafter. Structured tasks are json-mode-eval, Spider, and code generation under GREATGRAMMA's Python, Java, and Go grammars. The code tasks use HumanEval prompts and TypeScript MBPP with type-safe checking where feasible. Spec-Bench serves as a check that general text is not slowed down.
For speed and quality we measure four things: wall-clock speedup over the do-nothing reference, accepted tokens per verifier pass, parser milliseconds per accepted token, and validity plus execution or pass rates. We test batch sizes 1, 8, and 32, because SPEED-Bench shows speculative gains shrink as batches become compute-bound.
Fidelity is tested on small synthetic grammars where the masked distribution can be enumerated exactly. A chi-square test compares output frequencies from our sampler with those from token-by-token constrained sampling. For real tasks, we compare token-level statistics between the two samplers across many seeds.
The decisive check is the comparison against eager shared-mask tree speculation, together with the time breakdown. Parser-shaped lazy speculation should win at equal tree budget on JSON and SQL, with the measured share of time spent masking explaining the margin. If either fails to hold, the central claim fails.
A secondary check sweeps the structural speculation depth. In the spirit of the cross-lingual parsing result, it tests whether the best depth differs systematically between grammars that resolve structure early (JSON objects) and grammars that resolve it late (SQL clause ordering).
References
- Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
- Flexible and Efficient Grammar-Constrained Decoding
- ChopChop: A Programmable Framework for Semantically Constraining the Output of Language Models
- Graph-Structured Speculative Decoding
- SAM Decoding: Speculative Decoding via Suffix Automaton
- Constrained Decoding with Speculative Lookaheads
- Grammar-Aligned Decoding
- Is Incremental Structure Prediction Process Universal across Languages?: Revisiting Parsing Strategy through Speculation
- SPEED-Bench: A Unified and Diverse Benchmark for Speculative Decoding
- Cactus: Accelerating Auto-Regressive Decoding with Constrained Acceptance Speculative Sampling