[EMNLP 2025] Suffix-Constrained Greedy Search: Solving the "Formatting Tax" in LLM Reasoning

TL;DR

Current LLMs face a paradox: if you let them speak freely, their answers are hard to parse; if you force them into a format (like JSON), their reasoning performance drops. This paper introduces a Suffix-Constrained Greedy Search that allows the model to think "out loud" in an unconstrained way, only enforcing a strict template (e.g., "The answer is: [X]") at the very end. The result? 100% extractable answers and often better accuracy than standard greedy search.

Academic Positioning: This work bridges the gap between Grammar-Constrained Decoding (reliable but restrictive) and Chain-of-Thought Reasoning (powerful but messy).

The Motivation: Why Constraints Kill Reasoning

Researchers have long observed a "formatting tax." When a model is forced to adhere to a strict grammar from the first token, it consumes its "computational budget" (attention heads/KV cache) on syntax rather than logic.

Prior work typically tried to solve this via:

1. LLM-as-a-judge: Expensive, biased, and non-reproducible.
2. Global Constraints: Using a CFG/FSA to mask every token. This often prevents the model from generating the necessary "Thinking" steps that lead to the correct answer.

The authors' insight is simple: The reasoning should be free, but the conclusion must be formal.

Methodology: The Bifurcation Penalty

The core challenge is: When should the model stop reasoning and start answering?

If we use a standard suffix grammar ($V^{\ast }imeslang(G)$), the transition is ambiguous because any token is technically a valid prefix of $V^{\ast }$. To solve this, the authors propose a Beam-of-2 approach:

1. Greedy Hypothesis ($y$): Follows standard unconstrained decoding.
2. Constrained Hypothesis ($r\odot a$): A version that "branched off" from $y$ at some point $t$ to start the formal answer template.

The Decision Logic

Instead of standard beam search (which favors the most probable string and would likely kill the constrained path), they use a Bifurcation Penalty. At each step, they calculate the "cost" of forcing the model to start the template right now:

$\Delta ={\max }_{v\in V}p(v|x\odot y)-{\max }_{v\in ext{next}_G(ϵ)}p(v|x\odot y)$

If the model naturally starts to output something that fits the template (like "The"), the penalty is 0. If it wants to keep reasoning, the penalty is high. The algorithm keeps the hypothesis with the lowest penalty or the most recent valid branch.

Figure 1: Comparison between standard Greedy Search and the Suffix-Constrained approach. Note how the "Bifurcation" allows the model to switch to a structured suffix once the reasoning is complete.

Experimental Results: Reliability Without Sacrifice

The authors tested their method on OLMo 2 models across Mathematics (GSM8K, SVAMP) and Multiple Choice (ARC, CSQA).

Key Findings:

• 100% Parseability: Unlike unconstrained greedy search, which often fails to terminate or ignores formatting, the proposed method always finishes with a parseable string.
• Accuracy Boost: On GSM8K with the OLMo 2 13B Pre-trained model, the Last Hypothesis selection improved accuracy from 60.8% to 69.9%.
• The Failure of "Constrained Only": Forcing the model to skip reasoning and go straight to the answer (Constrained Baseline) crashed math scores (e.g., 63.9% $\to$ 1.5% on GSM8K), proving that "free reasoning" is non-negotiable.

Table 2: Performance across tasks. Suffix-constrained methods (especially "Last Hypothesis") consistently outperform both unconstrained and purely constrained baselines.

Critical Analysis & Insights

Why does it work?

The "Bifurcation Penalty" acts as a bridge. For Instruction-Tuned (IT) models, they have already learned to follow "The answer is:". The penalty is low when the model is naturally finished. For Pre-trained (PT) models that tend to ramble/repeat, the algorithm effectively "clips" the rambling and forces a conclusion once the reasoning has likely peaked.

Limitations

• Beam Overhead: While $k=2$ is efficient, it still requires more KV cache management than simple greedy search.
• Template Sensitivity: The quality depends on the chosen template (e.g., "The answer is:") being naturally accessible in the model's latent space.

Conclusion

This paper provides a robust algorithmic answer to the "LLM formatting" problem. By treating the final answer as a formal suffix constraint rather than a global structural constraint, we can preserve the model's "right to reason" while ensuring the output is ready for downstream production pipelines.

Future Outlook: This approach could be integrated into LLM inference engines (like vLLM or TGI) as a standard decoding parameter, potentially replacing the unreliable "regex" constraints used today for JSON extraction.