Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance

Vincenzo Collura; Karim Tit; Eleonora Giunchiglia; Mike Papadakis; Maxime Cordy

cs.AIAug 28, 2026

Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance

Authors: Vincenzo Collura, Karim Tit, Eleonora Giunchiglia, Mike Papadakis, Maxime Cordy

Organizations: University of Luxembourg, Luxembourg · Imperial College London, United Kingdom

Abstract

Grammar-constrained decoding helps large language models produce syntactically valid structured outputs, such as code, JSON, and SQL. For context-free grammars, many practical decoders enforce local prefix feasibility: each token must keep the current prefix extendable to some valid completion. Yet, under tokenizer-grammar mismatch and finite token budgets, feasible prefixes may still fail to reach acceptance. We propose a lookahead-guided decoding framework for context-free grammars based on pushdown automata. Offline, we compute bounded pushdown summaries with reachability labels and upper-bound distances to acceptance. Online, these estimates guide horizon-aware pruning and beam search. The resulting decoder is syntactically sound: every output is accepted by the target grammar. Experiments on JSON, SQL, and Linear Temporal Logic (LTL) show both consistent syntactic validity and improved completion quality over existing baselines.

Figures & tables

Panel of Figure 1 — Figure 1: Overview of SWYB : Model top- $K$ tokens are validated by tokenizer-aware PDA execution, filtered using reachability and distance-to-acceptance estimates, and combined with PDA-proposed candidates. Surviving tokens are reranked and used to update the beam state.

Method	Constraint	Prefix	Budget
Guidance ( Lundberg and et. al., 2024 )	CFG	partial	no
Outlines ( Willard and Louf, 2023 )	CFG	yes	no
DOMINO ( Beurer-Kellner et al., 2024 )	CFG	yes	no
SynCode ( Ugare et al., 2025 )	CFG	yes	no
XGrammar ( Dong et al., 2025 )	CFG	yes	no
GreatGramma ( Park et al., 2025 )	CFG	yes	no

Table 1: Positioning of SWYB relative to constrained and controlled decoding methods. "Prefix" indicates whether generation is kept within the prefix closure of the constraint language. "Budget" indicates whether decoding uses a remaining-horizon, distance-to-acceptance, or related lookahead signal.

	Llama-3.1-8B-Instruct				Llama-3.2-3B-Instruct				Qwen2.5-7B-Instruct
Method	Syn.	Schema	Time	Perp.	Syn.	Schema	Time	Perp.	Syn.	Schema	Time	Perp.
Base LM	63.7 $\pm$ 15.9	57.1 $\pm$ 14.4	1.74 $\pm$ 0.0	1.05	56.4 $\pm$ 9.8	49.4 $\pm$ 8.7	0.96 $\pm$ 0.1	1.06	93.6 $\pm$ 0.8	87.4 $\pm$ 0.8	1.47 $\pm$ 0.0	1.01
Sample-Verify	92.0 $\pm$ 0.0	80.9 $\pm$ 0.9	17.38 $\pm$ 0.0	1.08	80.0 $\pm$ 0.0	67.1 $\pm$ 1.9	9.65 $\pm$ 0.0	1.22	96.0 $\pm$ 0.0	88.3 $\pm$ 0.5	14.71 $\pm$ 0.0	1.04
Guidance	96.0	89.0	2.88	1.08	93.0	84.0	2.76	1.12	92.0	87.0	2.85	1.02
Outlines	94.0	90.0	3.49	1.07	93.0	90.0	2.04	1.12	95.0	89.0	3.62	1.02
XGrammar	93.0	85.0	1.57	1.45	95.0	88.0	0.96	1.38	93.0	85.0	1.60	1.80

Table 2: JSON generation results across base models. Syn. denotes syntactic validity and Schema denotes schema validity. Best results within each model are shown in bold and second-best results are underlined. SWYB is ran with

\alpha=0.25

and

2

beams, and GenLM is ran with default configuration using

2

and

5

number of particles (NP). Syncode has two modes: Strict and Mask, here we only report Strict as it outperforms its counterpart all metrics.

	Llama-3.1-8B-Instruct				Llama-3.2-3B-Instruct				Qwen2.5-7B-Instruct
Method	Ex.	Syn.	Time	Perp.	Ex.	Syn.	Time	Perp.	Ex.	Syn.	Time	Perp.
Base LM	53.8 $\pm$ 4.7	92.9 $\pm$ 7.9	0.87 $\pm$ 0.0	1.61	46.3 $\pm$ 4.0	96.2 $\pm$ 6.7	0.53 $\pm$ 0.0	2.16	61.4 $\pm$ 0.6	99.2 $\pm$ 0.2	0.88 $\pm$ 0.0	3.48
Sample-Verify	57.5 $\pm$ 1.1	100.0 $\pm$ 0.0	8.90 $\pm$ 0.0	1.56	47.8 $\pm$ 0.7	99.1 $\pm$ 0.3	5.29 $\pm$ 0.0	3.50	61.5 $\pm$ 0.4	99.7 $\pm$ 0.1	8.83 $\pm$ 0.0	10.38
SynCode	43.2	90.7	3.31	3.70	39.6	98.1	2.01	2.47	43.2	90.7	3.31	3.70
GenLM (NP=5,5,4)	59.2 $\pm$ 0.9	99.9 $\pm$ 0.1	10.74 $\pm$ 8.4	1.67	49.4 $\pm$ 0.7	99.9 $\pm$ 0.1	4.17 $\pm$ 0.3	1.38	51.9 $\pm$ 0.4	86.1 $\pm$ 0.6	6.77 $\pm$ 0.1	3.78
$\triangleright$ SWYB	61.1	100.0	9.92	1.22	51.5	100.0	6.25	1.43	62.8	100.0	13.03	2.10

Table 3: SQL generation results across base models. Ex. denotes execution accuracy and Syn. denotes syntactic correctness. Best results within each model are shown in bold and second-best results are underlined. GenLM uses NP=5 for Llama models and NP=4 for Qwen. SWYB uses beam width

4

;

\alpha

is set to

0.25

0.75

, and

0.50

for Llama-3.1-8B, Llama-3.2-3B, and Qwen2.5-7B, respectively.

	Llama-3.1-8B-Instruct				Llama-3.2-3B-Instruct				Qwen2.5-7B-Instruct
Method	Acc.	Syn.	Time	Perp.	Acc.	Syn.	Time	Perp.	Acc.	Syn.	Time	Perp.
Base LM	22.1 $\pm$ 3.3	98.8 $\pm$ 0.4	0.29 $\pm$ 0.0	1.31	9.6 $\pm$ 3.3	94.6 $\pm$ 3.1	0.17 $\pm$ 0.0	1.57	30.9 $\pm$ 0.5	98.4 $\pm$ 0.4	0.29 $\pm$ 0.0	1.61
Sample-Verify	22.2 $\pm$ 0.3	100.0 $\pm$ 0.0	2.86 $\pm$ 0.0	1.31	9.3 $\pm$ 0.2	99.9 $\pm$ 0.0	1.64 $\pm$ 0.0	1.56	30.6 $\pm$ 0.2	99.7 $\pm$ 0.0	2.89 $\pm$ 0.0	1.07
SynCode	24.4	99.9	0.30	1.21	15.2	99.9	0.19	1.36	31.0	100.0	0.31	1.09
$\triangleright$ SWYB	29.6	100.0	1.69	1.23	22.1	100.0	0.78	1.27	31.6	100.0	1.53	1.09

Table 4: LTL generation results across base models. Acc. denotes task accuracy and Syn. denotes syntactic correctness. Best results within each model are shown in bold. SWYB uses beam width

4

;

\alpha

is set to

0.75

0.50

, and

0.50

for Llama-3.1-8B, Llama-3.2-3B, and Qwen2.5-7B, respectively.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Table 6

	Llama-3.1-8B-Instruct				Llama-3.2-3B-Instruct				Qwen2.5-7B-Instruct
Method	Syn.	Schema	Time	Perp.	Syn.	Schema	Time	Perp.	Syn.	Schema	Time	Perp.
Guidance	98.0	90.0	3.63	1.07	98.0	85.0	3.16	1.10	98.0	91.0	3.56	1.01
Outlines	99.0	91.0	3.74	1.07	95.0	92.0	1.95	1.09	100.0	93.0	3.62	1.02
SynCode	100.0	83.0	13.27	1.02	99.0	79.0	7.52	1.11	100.0	92.0	1.61	1.01
GenLM (NP=2)	98.0 $\pm$ 0.0	92.6 $\pm$ 0.7	2.50 $\pm$ 1.4	1.04	95.7 $\pm$ 0.8	89.3 $\pm$ 1.3	4.00 $\pm$ 1.1	1.08	98.0 $\pm$ 0.0	92.6 $\pm$ 0.7	2.50 $\pm$ 1.4	1.01
GenLM (NP=5)	98.0 $\pm$ 0.0	92.9 $\pm$ 0.3	4.20 $\pm$ 0.1	1.04	97.2 $\pm$ 0.6	90.8 $\pm$ 0.9	6.10 $\pm$ 0.7	1.08	98.0 $\pm$ 0.0	92.9 $\pm$ 0.3	4.20 $\pm$ 0.1	1.01

Appendix

Table 7: Max New Tokens = 512.

Current State	Input	Stack Top	Next State	Stack Operation
$q_{0}$	(	$Z_{0}$	$q_{0}$	push (
$q_{0}$	(	(	$q_{0}$	push (
$q_{0}$	)	(	$q_{0}$	pop (
$q_{0}$	x	$Z_{0}$	$q_{f}$	–

Appendix

Table 11: PDA transitions for the running example.

Explore similar work

Grammar-Aligned Decoding
May 31, 2024Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick +2Constrained Generative Modeling Constrained Decoding
University of Wisconsin-Madison · University of California San Diego
Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees
Aug 6, 2026Kevin Cheang, Geoff Hulette, Rahul Kumar +5LLM-Based Program Synthesis Linear Temporal Logic
Amazon Web Services · Purdue University
GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning
Sep 30, 2026Gabriele Tuccio, Antonino Furnari, Aldo Gangemi +1RL for Language Models Constrained Decoding
University of Catania · ISTC - National Research Council, Italy · University of Bologna

May 31, 2024, cs.AIJ/K move · Enter open · S save

Grammar-Aligned Decoding

Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova+1

University of Wisconsin-Madison · University of California San Diego

Constrained Generative Modeling Constrained Decoding Adaptive Sampling LLM Code Generation Grammar-Constrained Decoding

Open paper AskPDF arXiv

Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code, mathematical formulas, or well-formed markup. Constrained decoding approaches mitigate this problem by greedily restricting what tokens an LLM can output at each step to guarantee that the output matches a given constraint. Specifically, in grammar-constrained decoding (GCD), the LLM's output must follow a given grammar. In this paper, we demonstrate that GCD techniques (and in general constrained decoding techniques) can distort the LLM's distribution, leading to outputs that are grammatical but appear with likelihoods that are not proportional to the ones given by the LLM, and so ultimately are low-quality. We call the problem of aligning sampling with a grammar constraint, grammar-aligned decoding (GAD), and propose adaptive sampling with approximate expected futures (ASAp), a decoding algorithm that guarantees the output to be grammatical while provably producing outputs that match the conditional probability of the LLM's distribution conditioned on the given grammar constraint. Our algorithm uses prior sample outputs to soundly overapproximate the future grammaticality of different output prefixes. Our evaluation on code generation and structured NLP tasks shows how ASAp often produces outputs with higher likelihood (according to the LLM's distribution) than existing GCD techniques, while still enforcing the desired grammatical constraints.

Abstract

Explore similar work

Grammar-Aligned Decoding

Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees

GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning