A new decoding method for language models produced syntactically valid output in every setting tested across JSON, SQL and linear temporal logic, according to an arXiv preprint. The finding is a guarantee about form, not a guarantee of task success: the same evaluation reported lower task-accuracy scores for SQL and LTL.
The method, called SWYB, is built for structured generation, in which an output must follow a context-free grammar, or a set of rules for how its pieces may be arranged. The paper's formal result is narrow but clear: Theorem 4.1 states that every output returned by SWYB is accepted by the target PDA, the formal machine used to check those grammar rules.
How SWYB looks ahead
SWYB combines bounded pushdown summaries with reachability labels and upper-bound token-distance estimates. Those summaries guide candidate validation, pruning, reranking and beam search, allowing the decoder to keep several possible continuations in play while favoring choices that remain reachable within the grammar. The design is tokenizer-aware, meaning it accounts for the model's way of breaking text into tokens.
The benchmarks contained 100 JSON examples, 1,034 examples from the SQL validation split and 6,185 examples in a drone-planning golden dataset built around linear temporal logic, or LTL. The evaluation used Llama-3.1-8B-Instruct, Llama-3.2-3B-Instruct and Qwen2.5-7B-Instruct. A uniform maximum token budget of 120 was used across the three tasks.
Perfect syntax did not mean perfect task results
In JSON, SWYB reported 100.0 syntactic validity and 100.0 schema validity for each model. Decoding took 3.96 seconds per output with Llama-3.1-8B-Instruct, 3.46 seconds with Llama-3.2-3B-Instruct and 4.05 seconds with Qwen2.5-7B-Instruct. Perplexity, a measure of how expected the output was to the model, was 1.13, 1.14 and 1.11 in that order.
SQL showed the difference between grammatical form and the task metric. SWYB's reported execution-accuracy scores were 61.1 for Llama-3.1-8B-Instruct, 51.5 for Llama-3.2-3B-Instruct and 62.8 for Qwen2.5-7B-Instruct, while syntactic correctness was 100.0 for each. The syntax score therefore should not be read as a matching task-accuracy score.
The same contrast appeared in the drone-planning LTL results. Task-accuracy values were 29.6, 22.1 and 31.6 for the three models in that order, while syntactic correctness remained 100.0 for each. In this evaluation, following the grammar and completing the task were measured separately.
The trade-offs behind the guarantee
An ablation of the Llama-3.2-3B SQL setup recorded 26.0 execution accuracy without distance-guided scoring or beam search. The four-beam version without distance-guided scoring recorded 50.9, distance-guided scoring without beams recorded 26.3, and the combination recorded 51.2. Syntax was 100 in all four configurations. The distance-guided scoring setting in the latter configurations used a weighting parameter of 0.5.
Simply increasing the maximum output allowance from 512 to 4,096 tokens did not materially improve schema satisfaction. The paper reports the upper setting as up to 40 times the default budget.
The formal guarantee has boundaries. SWYB is not search-complete because it uses bounded successor exploration and a finite beam width, although it preserves at least one certified completion under its stated condition. That means the method does not claim to examine every possible continuation.
Two tuning limits sit behind that trade-off. If the stack-height bound is too low, the precomputed summary can omit reachable configurations. A larger exploration budget increases runtime while enabling more detailed lookahead.
The evaluation protocol also affects how the comparisons should be read. Stochastic baselines were summarized with means and standard deviations over multiple seeds, while deterministic methods were reported with a single run. The figures therefore describe the configurations tested in this study.
This is an arXiv preprint, version 1, dated 28 Aug 2026. The work was supported by the AI for Math Fund and by the Luxembourg National Research Fund through grant C23/IS/18177547/VARIANCE.
Paper data and sources
Original title: Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance
Authors: Vincenzo Collura, Karim Tit, Eleonora Giunchiglia et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text