Accelerating Constrained Decoding with Token Space Compression

Alexander Koller; Michael Sullivan

arxiv: 2605.29986 · v1 · pith:VKNUU26Q · submitted 2026-05-28 · cs.AI

Accelerating Constrained Decoding with Token Space Compression

Michael Sullivan , Alexander Koller This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-29 07:24 UTCgrok-4.3pith:VKNUU26Q record.json open to challenge →

classification cs.AI

keywords constrained decodingcontext-free grammarstoken space compressionCFGziplarge language modelsgrammar enginesdecoding latency

0 comments

The pith

An offline compression technique called CFGzip reduces the latency of CFG-constrained LLM decoding by up to two orders of magnitude.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that compressing the token search space offline allows CFG decoding engines to avoid searching the full vocabulary at each step. This overhead has previously made complex grammars impractical despite being the cases where constraints are most valuable. CFGzip performs this compression once per grammar and reuses it, delivering up to 100-fold latency cuts and 7.5 times faster total generation. A sympathetic reader would care because it turns structural guarantees from a theoretical tool into a scalable one for real LLM applications like code or data generation. The central mechanism preserves all valid strings under the grammar while shrinking the effective choices.

Core claim

CFGzip is introduced as an offline technique for compressing the token search space used by CFG decoding engines. By reducing the massive per-step search space from the entire token vocabulary, it cuts engine overhead dramatically. Experiments show latency reductions of up to two orders of magnitude and up to 7.5x speedup in total constrained generation time when paired with a state-of-the-art grammar engine. This makes constrained decoding feasible at scale for complex CFGs.

What carries the argument

CFGzip, an offline token search space compression method that shrinks the vocabulary considered by the CFG engine while maintaining coverage of all valid strings.

If this is right

Constrained decoding engines can handle more complex grammars without runtime becoming intractable.
Total time for generating structured outputs from LLMs decreases substantially.
Pre-computed compressions can be reused across many generations for the same grammar.
State-of-the-art grammar engines see immediate performance gains from the added compression step.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This could open the door to enforcing CFGs in real-time interactive applications where latency matters.
The compression idea might apply to other search-heavy decoding methods beyond strict CFGs.
Future work could explore dynamic or online versions of the compression for changing grammars.

Load-bearing premise

That the compression of the token space can be computed offline once per grammar and then reused indefinitely without excluding valid strings or requiring repeated expensive pre-processing.

What would settle it

Running the method on a complex CFG and finding either that some valid strings are no longer generable or that the pre-processing time is larger than the total savings across a realistic number of generations.

Figures

Figures reproduced from arXiv: 2605.29986 by Alexander Koller, Michael Sullivan.

**Figure 1.** Figure 1: CFGZIP first pre-computes equivalence classes over the token vocabulary. At inference time, the grammar engine operates over the smaller vocabulary of equivalence class representatives: (a) a sampled token is mapped to the representative of its equivalence class; and (b) the grammar engine produces a mask over the equivalence class vocabulary, which is then mapped to a mask over the token vocabulary. as th… view at source ↗

**Figure 2.** Figure 2: C++ code generated by Llama-3.2-3B-Instruct using [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗

**Figure 3.** Figure 3: Illustration of Algorithm 1 applied to the token t = abcxyz. Each sub-figure (3i-3vi) illustrates the corresponding parse tree at that step: the caption indicates the current position/character t0 (underlined/bolded), the rule A → t0 β in G that is applied (i.e. transition β ∈ δG(t0, A)), and the resulting input/output stacks σ (i) /σ (o) after applying the transition. stack-adjacency computation algorith… view at source ↗

**Figure 4.** Figure 4: Comparison of the mean per-example (top; milliseconds) and per-token (bottom; microseconds) overhead [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗

**Figure 5.** Figure 5: Illustration of the stack adjacency sub-relation [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗

read the original abstract

To guarantee that an LLM's outputs conform to a specified structure, context-free grammar (CFG) decoding engines force the selection of next tokens that produce strings that conform to a given CFG. While current CFG-constrained decoding engines are highly optimized, the inherent costs arising from the massive per-step search space -- i.e. the entire token vocabulary -- result in intractably high overhead for more complex CFGs: precisely the situation where CFG engines are most useful. In this paper, we introduce CFGzip, an offline technique for compressing the token search space, which massively reduces CFG engine overhead. In experiments, we report latency reduction of up to two orders of magnitude when CFGzip is used with a SoTA grammar engine, yielding an up to 7.5x speedup in total constrained generation time: with CFGzip, constrained decoding is now feasible at scale for complex CFGs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

CFGzip's offline token-space compression delivers reported speedups that could make complex CFG decoding practical, but the evaluation details are too thin to judge how general or robust the gains are.

read the letter

CFGzip's main contribution is an offline compression of the token vocabulary for CFG-constrained decoding that shrinks the per-step search space while aiming to keep every valid derivation reachable. The authors report this yields up to two orders of magnitude lower latency and a 7.5x improvement in end-to-end generation time when added to an existing engine.

The technique is new in its framing as a reusable, precomputed reduction rather than an online optimization. It directly targets the scaling problem the field already knows: simple grammars are cheap to enforce, but the ones that actually constrain output structure make the full-vocabulary search prohibitive. If the compression step is both exact and cheap to amortize, the practical payoff is clear for anyone shipping structured LLM outputs.

The paper states the motivation cleanly and shows the speedups on top of a strong baseline engine. That is useful engineering evidence.

The soft spot is the evaluation. The abstract gives headline numbers but supplies little on the grammars tested, how the compression was constructed, the pre-processing cost, variance across runs, or whether the gains hold when the grammar complexity increases further. Without those controls it is hard to know whether the reported factors are typical or best-case. The assumption that one offline pass stays lossless and reusable across workloads also needs explicit verification in the results.

This is work for people building or deploying constrained generation systems. A reader who needs faster structured output will want to test the method. It deserves peer review because the idea is concrete enough to check and the claimed improvement addresses a known bottleneck, even if the current experiments need tightening.

Referee Report

1 major / 0 minor

Summary. The paper introduces CFGzip, an offline technique for compressing the token search space to accelerate context-free grammar (CFG) constrained decoding in large language models. It claims that this method reduces the per-step search overhead, achieving latency reductions of up to two orders of magnitude and up to 7.5x speedup in total constrained generation time when integrated with a state-of-the-art grammar engine, thereby making constrained decoding feasible at scale for complex CFGs.

Significance. If the results hold and the compression is lossless with amortized pre-processing cost, this would be a significant practical contribution to constrained generation with LLMs by addressing a key scalability bottleneck for complex CFGs.

major comments (1)

[Abstract] The abstract reports quantitative speedups (latency reduction of up to two orders of magnitude and 7.5x speedup in total constrained generation time) but supplies no experimental details, baselines, variance, or methodology. This prevents evaluation of the central empirical claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and constructive comment. We address the major comment below.

read point-by-point responses

Referee: [Abstract] The abstract reports quantitative speedups (latency reduction of up to two orders of magnitude and 7.5x speedup in total constrained generation time) but supplies no experimental details, baselines, variance, or methodology. This prevents evaluation of the central empirical claim.

Authors: We agree that the abstract, constrained by length, omits the specific experimental details. The full methodology (including the SoTA grammar engine baseline, multiple random seeds for variance reporting, and evaluation protocol) is described in Section 4 of the manuscript. To address the concern, we will revise the abstract to include a concise reference to the experimental setup and baselines while preserving its brevity. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces CFGzip as an algorithmic offline compression technique for the token search space in CFG-constrained decoding. No equations, fitted parameters, predictions, or self-citations appear as load-bearing elements in the derivation chain. The central claims rest on the description of a lossless, reusable compression method whose correctness and performance are presented as externally verifiable through implementation and benchmarks rather than reducing to self-definition, fitted inputs renamed as predictions, or self-citation chains. The work is therefore self-contained with no circular reduction of results to inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no technical details on free parameters, axioms, or invented entities are provided.

pith-pipeline@v0.9.1-grok · 5669 in / 983 out tokens · 29065 ms · 2026-06-29T07:24:50.091687+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages · 2 internal anchors

[1]

The Llama 3 Herd of Models

On formal properties of simple phrase struc- ture grammars.Sprachtypologie und Universalien- forschung, 14:143–172. Ben Bogin, Shivanshu Gupta, Peter Clark, and Ashish Sabharwal. 2024. Leveraging code to improve in- context learning for semantic parsing. InProceed- ings of the 2024 Conference of the North American Chapter of the Association for Computatio...

work page internal anchor Pith review Pith/arXiv arXiv 2024
[2]

Efficient Guided Generation for Large Language Models

Flexible and efficient grammar-constrained decoding. InForty-second International Conference on Machine Learning. Shishir G Patil, Huanzhi Mao, Fanjia Yan, Charlie Cheng-Jie Ji, Vishnu Suresh, Ion Stoica, and Joseph E Gonzalez. 2025. The berkeley function calling leader- board (bfcl): From tool use to agentic evaluation of large language models. InForty-s...

work page internal anchor Pith review Pith/arXiv arXiv 2025

[1] [1]

The Llama 3 Herd of Models

On formal properties of simple phrase struc- ture grammars.Sprachtypologie und Universalien- forschung, 14:143–172. Ben Bogin, Shivanshu Gupta, Peter Clark, and Ashish Sabharwal. 2024. Leveraging code to improve in- context learning for semantic parsing. InProceed- ings of the 2024 Conference of the North American Chapter of the Association for Computatio...

work page internal anchor Pith review Pith/arXiv arXiv 2024

[2] [2]

Efficient Guided Generation for Large Language Models

Flexible and efficient grammar-constrained decoding. InForty-second International Conference on Machine Learning. Shishir G Patil, Huanzhi Mao, Fanjia Yan, Charlie Cheng-Jie Ji, Vishnu Suresh, Ion Stoica, and Joseph E Gonzalez. 2025. The berkeley function calling leader- board (bfcl): From tool use to agentic evaluation of large language models. InForty-s...

work page internal anchor Pith review Pith/arXiv arXiv 2025