🤖 AI

Accelerating Constrained Decoding with Token Space Compression

This paper introduces CFGzip, an offline token space compression technique that significantly reduces the computational overhead of constrained decoding, achieving up to a 7.5x speedup in total generation time for complex context-free grammars.

Original authors: Michael Sullivan, Alexander Koller

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Sullivan, Alexander Koller

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very talented but slightly chaotic chef (the LLM) who can cook almost anything. However, you need them to prepare a dish that follows a very strict, complex recipe (a Context-Free Grammar or CFG), like a specific programming language or a precise data format.

If the chef guesses the wrong ingredient, the whole dish is ruined. To prevent this, you hire a strict Grammar Engine (like a head chef or a food safety inspector) who stands next to the chef. Before the chef adds any ingredient, the inspector checks the entire pantry to see if that specific ingredient is allowed at this exact step in the recipe.

The Problem: The "Pantry" is Too Big

The problem is that the chef's pantry (the token vocabulary) is massive, containing hundreds of thousands of different ingredients (words, symbols, code snippets).

Every time the chef wants to add one ingredient, the inspector has to run through the entire pantry to check if that specific item is valid. For simple recipes (like JSON data), this is fast. But for complex recipes (like C++ code or a made-up language called "Bython"), the inspector gets overwhelmed. They have to check so many possibilities that the cooking process slows down drastically—sometimes taking 2 to 10 times longer than normal. The paper calls this "intractably high overhead."

The Solution: CFGZIP (The "Grouping" Trick)

The authors introduce a new tool called CFGZIP. Instead of making the inspector check every single ingredient in the pantry, CFGZIP reorganizes the pantry before cooking even starts.

Here is the analogy:

Grouping Ingredients: CFGZIP looks at the pantry and realizes that many ingredients are interchangeable for the purpose of the recipe. For example, in a specific part of a code recipe, the words if, else, and while might all act the same way grammatically. Or, in a different context, the numbers 1, 2, and 3 might all be valid placeholders.
Creating "Representative" Buckets: CFGZIP groups these interchangeable ingredients into buckets. It picks one "representative" ingredient from each bucket (usually the shortest one) to stand in for the whole group.
The New Workflow:
- Before Cooking (Offline): The system does the hard work of sorting the pantry into these buckets. This is done once and saved.
- During Cooking (Inference): When the chef picks an ingredient, the system quickly swaps it for its "representative" from the bucket. The inspector only has to check the representative against the recipe, not the whole pantry.
- The Result: Because the inspector is now checking a tiny list of representatives instead of the massive original pantry, the process becomes incredibly fast.

Why This is a Big Deal

The paper claims that using CFGZIP with a top-tier grammar engine (XGrammar2) creates a massive speedup:

Latency Reduction: The time it takes to check the rules drops by 10 to 100 times (two orders of magnitude).
Total Speedup: The entire process of generating the text becomes 7.5 times faster for complex tasks.
No Quality Loss: This is a "lossless" compression. The final output is byte-for-byte identical to what you would get without the speedup. The chef still produces the exact same perfect dish; they just got there much faster.

Real-World Results from the Paper

The researchers tested this on three different AI models (Llama, Qwen, and GPT) and four different tasks:

JSON & XML: Standard data formats.
C++: A complex programming language.
Bython: A fictional, made-up programming language (similar to Python but with braces and semicolons instead of spaces).

The Findings:

For standard formats (JSON), the speedup was good but not revolutionary because those rules are already simple.
For complex and unfamiliar languages (like C++ and Bython), the difference was huge. Without CFGZIP, the grammar engine was so slow it made the AI practically unusable for these tasks. With CFGZIP, the AI could generate complex code quickly and correctly.
Interestingly, for the "Bython" task (which the AI had never seen before), using this constrained method improved the AI's ability to write working code from 2.3% to 46.9% (for one model), proving that strict rules help AI when the task is hard.

The Catch (Limitations)

The paper notes one main limitation: Preparation Time.
Sorting the pantry into buckets (the "offline pre-computation") takes time.

If you need to generate a JSON file for a one-off, quick task, the time it takes to sort the pantry might be longer than just doing the task normally.
However, if you are doing large-scale code generation or using the same complex rules over and over again, the initial setup time is worth it because the cooking (generation) becomes so much faster.

Summary

CFGZIP is like a smart librarian who reorganizes a massive library into "topic buckets" before you arrive. Instead of you searching every single book to find the right one, the librarian just points you to the "topic bucket" representative. This makes finding the right information (or in this case, generating the right code) dramatically faster without ever losing a single book or changing the story.

Technical Summary: Accelerating Constrained Decoding with Token Space Compression (CFGZIP)

Problem Statement

Large Language Models (LLMs) are frequently required to generate text conforming to specific structures, such as JSON, XML, or domain-specific programming languages. While LLMs perform well on common formats found in their training data, they struggle with novel or complex formats. To guarantee syntactic correctness, Constrained Decoding engines are employed. These engines use Context-Free Grammars (CFGs) to mask invalid tokens at each generation step.

However, current state-of-the-art (SoTA) grammar engines (e.g., XGrammar2) face a significant performance bottleneck. Although optimized, they must validate tokens against the entire token vocabulary at every decoding step. For complex CFGs (e.g., C++ or custom languages), this results in prohibitive overhead, causing inference latency to increase by 2x to 10x compared to unconstrained generation. This latency renders constrained decoding infeasible for large-scale applications involving complex grammars.

Methodology: CFGZIP

The authors introduce CFGZIP, an offline technique designed to compress the token search space, thereby reducing the per-step runtime of the grammar engine without sacrificing correctness.

Core Concept: Equivalence Classes

The fundamental insight of CFGZIP is that many tokens in a vocabulary are interchangeable with respect to a specific CFG. If two tokens $t$ and $u$ are "syntactically congruent," they can be swapped in any valid string of the language $L(G)$ without affecting validity. Consequently, the grammar engine only needs to verify the validity of one representative token per equivalence class rather than every individual token.

The Pipeline

Offline Pre-computation:
- Approximation: Since exact syntactic congruence is undecidable for arbitrary CFGs, CFGZIP computes a tractable approximation called Displacement Equivalence ( $\sim_{L(G)}$ ).
- Mechanism: The CFG is converted to Greibach Normal Form (GNF) to utilize a Pushdown Automaton (PDA). For each token, the system computes its "displacement" $\Delta_G(t)$ , defined as the set of input/output stack transitions the token induces on the PDA. Tokens with identical displacement sets are grouped into the same equivalence class.
- Optimization: To make this computationally feasible, the authors restrict the stack backtrack operation using a pre-computed stack-adjacency relation, preventing memory blowup in large grammars.
- Caching: The system maps token IDs to class IDs and selects a byte-wise shortest token as the "representative" for each class. These mappings are cached to disk.
Inference-Time Operation:
- Vocabulary Reduction: The grammar engine is initialized with the vocabulary of equivalence class representatives rather than the full token vocabulary.
- Token Mapping: When the LLM samples a token, CFGZIP maps it to its class representative and passes this representative to the grammar engine to update the parser state.
- Masking: The grammar engine produces a validity mask over the smaller set of representatives. This mask is then "gathered" and applied to the original LLM logits. This operation is parallelizable on GPUs and incurs minimal overhead.

Key Properties

Lossless: The compression is provably lossless; the outputs of a CFGZIP-equipped engine are byte-identical to those of the original engine.
Engine-Agnostic: Theoretically compatible with any grammar engine, though the paper focuses on XGrammar2.
Offline: The heavy computation occurs once per tokenizer/CFG pair, incurring virtually no overhead during inference.

Experimental Results

The authors evaluated CFGZIP coupled with XGrammar2 on Llama-3.2-3B, Qwen3-4B, and gpt-oss-20B across four tasks: JSON Schema, XML, C++, and Bython (a custom, brace-based Python variant).

Latency Reduction: CFGZIP reduced the overhead of the grammar engine by one to two orders of magnitude.
- For C++, total inference time was nearly halved.
- For Bython (a complex, low-resource language), total constrained generation time was reduced by a factor of ~7.5x.
Correctness: CFGZIP maintained 100% syntactic correctness (byte-identical to the baseline engine).
- Functional Correctness: Constrained decoding significantly improved functional correctness, particularly for the Bython task, where unconstrained models struggled (e.g., GPT-20B improved from 10.8% to 46.9% functional correctness).
Compression Ratios: The technique achieved compression ratios ranging from 40:1 (Llama-3B/C++) to 800:1 (GPT-20B/JSON), drastically reducing the vocabulary size the engine must process.

Significance and Claims

The paper claims that CFGZIP makes constrained decoding feasible at scale for complex CFGs.

Bridging the Gap: While SoTA engines are efficient for simple grammars (like JSON), they introduce intractable latency for complex ones (like C++). CFGZIP shrinks this overhead to near-negligible levels, unlocking the performance benefits of constrained decoding for these difficult cases.
Cost-Effectiveness: The results suggest that for smaller, cheaper models, constrained decoding can be a viable alternative to using larger models to achieve high functional correctness.
Practicality: By decoupling the heavy lifting to an offline pre-computation phase, CFGZIP enables real-time applications requiring strict adherence to complex domain-specific languages without sacrificing speed.

Limitations

The authors note that CFGZIP is not a universal solution for all scenarios:

Dynamic Contexts: The offline pre-computation time (ranging from seconds to minutes) makes it less suitable for dynamic, single-use CFGs (e.g., ad-hoc JSON schemas or function calls) where engines like llguidance are already highly optimized.
Engine Compatibility: While theoretically engine-agnostic, the current implementation is Python-based and integrated with XGrammar2. It is not compatible with C++-only engines like llama.cpp (due to lack of Python bindings) or engines that do not support the specific CFGs used (e.g., left-recursive grammars in transformers-cfg).
Scope: The method is best suited for static, large, and complex CFGs, such as those used in code generation.