Grammar-Constrained Decoding Can Produce Feasible Prefixes That Never Reach Acceptance; Lookahead Distances Fix It

arXiv 2608.28229·medium signalXBlueskyLinkedInCopy link

arXiv 2608.28229 (2026-08-28, cs.AI/cs.CL/cs.FL/cs.LG) identifies a real failure in the grammar-constrained decoders used for JSON, SQL and code: most enforce only local prefix feasibility, so under tokenizer-grammar mismatch and a finite token budget a feasible prefix can still fail to reach acceptance. The fix computes bounded pushdown-automaton summaries offline with reachability labels and upper-bound distances to acceptance, then uses those estimates online for horizon-aware pruning and beam search. The resulting decoder is syntactically sound by construction, and experiments on JSON, SQL and Linear Temporal Logic show both consistent syntactic validity and improved completion quality over existing baselines.