Grammar-constrained decoding forces a language model's output to follow a formal grammar. At every step it deletes any next token that would break the grammar, which guarantees output that a program can parse. The price is well documented: when a model must reason inside a rigid schema, its accuracy falls sharply. The field has studied only two settings, fully free text and a fully constrained document. We propose treating the granularity of the grammar as the variable to study, meaning how much of the output it pins down and at what structural level. The hypothesis is that there is a middle setting that does something neither end can. A grammar that constrains only the interfaces between reasoning steps, and in particular which quantities a step is allowed to use, could block a specific class of careless errors while leaving the model's reasoning prose free.
The analogy comes from topic modeling, where choosing the number of topics trades resolution against statistical support. Too few topics merge distinct concepts. Too many fragment the evidence until each topic is noise (PUTOP sees disambiguation accuracy peak at 5 topics and fall by 200; Mimno et al. and Otmakhova et al. document incoherent fragments at high resolution). We expect a parallel for constraints. A grammar that is too coarse cannot catch errors. A grammar that is too fine removes so much of the model's probability at each step that the model is pushed into unlikely states and its reasoning degrades. We also expect the best granularity to depend on model size.
Core Claim
The claim has two parts. First, a grammar that constrains the provenance of quantities, requiring every number or variable a step uses to be either a literal from the problem statement or a name declared in an earlier step, reduces the "data mismatch" and "misinterpretation" failures that Yang et al. identify as the causes of hard-to-easy inconsistency. It should do so while paying much less of a reasoning penalty than full schema enforcement. Second, the size of that penalty at any granularity is predicted by the feasible mass, the probability the unconstrained model assigns to the tokens the grammar allows. Reddy et al. use this quantity to select drafts. We use it instead as a measurable cost for comparing grammars. If both parts hold, practitioners get a principled way to decide how much structure to impose. They also get a remedy for inconsistency that works at decoding time rather than through fine-tuning.
Relation to Prior Work
Two papers establish the problem and supply our strongest competitor. Let Me Speak Freely? shows that JSON-mode and format instructions hurt reasoning. The damage is worst when the answer field comes before the reasoning field: GPT-3.5 on Last Letter Concatenation falls from roughly 56% to 25%. The same paper finds that constraints help classification. DCCD frames constrained decoding as a projection away from the model's natural distribution. Its fix is a two-pass method in which the model first reasons freely and a second pass projects that draft into the required format. On MATH500 with Qwen-2.5-14B, it recovers accuracy from 47% (standard constrained decoding) to 58.6%, against 76% unconstrained. Both papers compare endpoints. Neither varies how much of the reasoning the grammar touches. DCCD's draft is left entirely unconstrained, so its authors note it cannot recover when the draft itself uses the wrong quantity. Our proposal targets exactly that failure. It constrains the draft lightly rather than leaving it free.
Grammar-Aligned Decoding shows that token masking distorts the model's sampling distribution. It corrects this by resampling with estimates of which prefixes can still lead to a grammatical output, reaching +38% geomean correct solutions on INV-BV loop-invariant synthesis. The cost is up to 2,000 samples per prompt. It shapes our design as a negative constraint: fine-tuning does not remove the distortion, so the variable we can control is the grammar itself. GREATGRAMMA supplies the engine, with 5–32 ms per-token masking. We note its lexer limitations, which our step grammars are designed to avoid.
On the reasoning side, two lines of work motivate what the intermediate steps should look like. Divide-and-Conquer prompting argues that clean interfaces between sub-tasks stop errors from spreading, but it enforces those interfaces only by prompting. Adaption-of-Thought shows that step granularity should match problem difficulty, and it adjusts granularity only through the choice of demonstrations. We carry both intuitions into the decoding mask. The cognitive-scaffold claims of ASPIRO and GAMMA appear to contradict the reasoning-tax literature. Our granularity sweep is meant to settle this directly, by locating where structure changes from helping to hurting.
Research Program
For grade-school and competition math, we build a ladder of four grammars over the same output. Level 0 constrains only a final answer field that comes after free text. Level 1 adds numbered step headers with free prose inside each step. Level 2, the proposed level, adds a provenance line to each step that names its inputs and its declared result. The inputs are restricted to literals found in the problem statement or names declared in earlier steps. Level 3 requires every step to be a typed arithmetic expression, which approaches program-of-thought.
The provenance restriction depends on the problem, so recompiling a grammar for each problem is impractical. We therefore compile a single fixed grammar in which the literal and identifier slots are open. At run time we intersect the grammar's mask with a second mask over those slots, updated after each problem and each step. Each masking pass stays within GREATGRAMMA's latency envelope. All four levels are run with and without token masking. The unmasked version gives the same format as an instruction only, which separates the effect of enforcement from the effect of the format.
We sweep open models at roughly 1B, 8B, 14B and 70B parameters. The models come from the Llama-3 and Qwen-2.5 families used by Reddy et al. and Tam et al. At every token we log feasible mass, which lets us test whether the mean log feasible mass of a grammar–model pair predicts its accuracy penalty relative to free generation. A secondary component is a mass-triggered relaxation rule. When feasible mass inside a step falls below a threshold, that step drops to Level 1 before the grammar is restored. We treat this rule as optional and keep it only if it beats the best fixed level.
Baselines
The naive reference point is unconstrained chain-of-thought with a simple answer extractor, run with the same prompts, the same few-shot exemplars and the same sampling temperature. Its answers are scored with the tolerant parser that Tam et al. use, so that formatting failures do not count against it. This gives the ceiling for final-answer accuracy that any constrained method must approach.
Standard grammar-constrained decoding with a monolithic answer-and-reasoning JSON schema reproduces the reasoning-tax condition. We run it through the same engine. Reported anchors from Reddy et al. are 47% on MATH500 for Qwen-2.5-14B and 15.2% strict structured accuracy on GSM8K for Llama-3.2-1B.
The strongest competitor is DCCD. We run it with the same drafting model as our method, a projector of equal size, and a matched Best-of-K budget, so that total generated tokens are equal. We count our method's single pass against DCCD's two passes. The reported numbers we must meet or beat are 58.6% on MATH500 at 14B and 39.0% strict GSM8K accuracy at 1B, both from DCCD. We found no reported result on Lacuna for DCCD on ConsisEval. On that benchmark, beating DCCD means a higher Consistency Score and a lower data-mismatch error rate at equal or better final accuracy. A win on consistency that costs more than two points of accuracy would count only as a trade-off, not a win.
Grammar-Aligned Decoding is run only on a 200-problem subset because of its sample budget. It serves as a reference for whether the correction to the sampling distribution, rather than the choice of granularity, explains any gains.
The key ablation compares Level 2 with masking against Level 2 as an instruction only. If the two match, the enforcement contributes nothing and the proposal reduces to prompt design.
Why not just…?
Why not just reason freely and format afterward, as DCCD does? This is the real threat. On final-answer accuracy DCCD may simply win, because its draft pays no penalty at all. Our bet is narrower. We expect DCCD to inherit every data-mismatch error its unconstrained draft makes, since its authors state the projector cannot repair a wrong draft, and we expect provenance constraints to remove some of those errors. The hybrid in which a Level 2 draft is then projected by DCCD is also in the experiment matrix. If that hybrid dominates, we will report it as the result, rather than framing single-pass decoding as the contribution.
Why not just use self-consistency voting or a trained verifier? Cobbe et al. show that a 6B verifier over 100 samples matches a 175B fine-tuned model on GSM8K, at roughly 35% versus 33%. However, verifiers are fooled by correct answers reached through unsound steps. Al-Khalili et al. find exactly this pattern in code-assisted math. Voting also does not address ConsisEval's measure, which is whether a model that solves the hard problem also solves the easy one. We therefore include self-consistency with 16 samples as a compute-matched arm. We also report whether provenance decoding combined with voting is additive.
Why not just scale the model? ConsisEval already shows Llama3-70B-Instruct at 91.9% consistency, against 50–70% for 7B models. Scale may therefore close most of the gap by itself. Our model sweep tests this directly. If the benefit of Level 2 over Level 0 shrinks to zero at 70B, the contribution is limited to small and medium models, which is still where cheap structured pipelines run. That would be a scoped but honest result.
Why not just execute code, as in program-of-thought? Level 3 is essentially this approach, placed on the same ladder. Tam et al. and Reddy et al. predict that it pays the largest penalty in feasible mass on word problems. If it does not, the interior-optimum hypothesis fails.
Proposed Experiments
We evaluate on GSM8K, MATH500, and the 298 math pairs of ConsisEval, with Last Letter Concatenation as a symbolic control where the provenance of quantities should matter little. The metrics are final-answer accuracy, strict structured accuracy, ConsisEval Consistency Score, feasible mass per token, and wall-clock time per problem. We also measure a per-trap error rate. Two annotators label 300 sampled failures per condition using Yang et al.'s five traps (redundant information, data mismatch, misinterpretation, off-by-one, computation).
Three checks decide the outcome. The first is whether masked Level 2 lowers the data-mismatch rate relative to both instruction-only Level 2 and DCCD, while staying within two points of unconstrained accuracy. The second is whether accuracy against granularity has an interior maximum, rather than falling steadily from Level 0 to Level 3. The third is whether mean log feasible mass predicts the accuracy penalty across all grammar–model pairs with a rank correlation above 0.7.
Failure on the first check ends the main claim. Failure on the second would mean the topic-granularity analogy does not transfer, which is itself a clean negative result about structured reasoning. Success on the third alone would still give practitioners a way to price a schema before deploying it.
References
- PUTOP: Turning Predominant Senses into a Topic Model for Word Sense Disambiguation
- Optimizing Semantic Coherence in Topic Models
- Improved Topic Representations of Medical Documents to Assist COVID-19 Literature Exploration
- Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones?
- The Hidden Cost of Structured Generation in LLMs: Draft-Conditioned Constrained Decoding
- Let Me Speak Freely? A Study On The Impact Of Format Restrictions On Large Language Model Performance
- Grammar-Aligned Decoding
- Flexible and Efficient Grammar-Constrained Decoding
- When Splitting Makes Stronger: A Theoretical and Empirical Analysis of Divide-and-Conquer Prompting in LLMs
- Adaption-of-Thought: Learning Question Difficulty Improves Large Language Models for Reasoning
- ASPIRO: Any-shot Structured Parsing-error-Induced ReprOmpting for Consistent Data-to-Text Generation
- Gamma: Revisiting Template-Based Automated Program Repair Via Mask Prediction
- Training Verifiers to Solve Math Word Problems
- Evaluating Intermediate Reasoning of Code-Assisted Large Language Models for Mathematics