Accelerating Constrained Decoding with Token Space Compression
Michael Sullivan, Alexander Koller · 2026
Read Accelerating Constrained Decoding with Token Space Compression by Michael Sullivan, Alexander Koller (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29986.txt.
Introduction
Michael Sullivan and Alexander Koller speed grammar-constrained language model decoding by shrinking the token search space. Grammar engines force each next token to fit a context-free grammar, but scanning the whole vocabulary each step costs dearly, worst for complex grammars where engines help most. Their CFGzip method compresses the token space offline, slashing engine overhead. Batched tests cut latency up to seventy-five times, leaving overhead near one to two times on the hardest grammars. Constrained decoding for complex grammars thus turns practical at scale.
Catalog record
| CREATOR | Michael Sullivan, Alexander Koller |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44052 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29986
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Accelerating Constrained Decoding with Token Space Compression Michael Sullivan, Alexander Koller 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. 1 Introduction Many modern LLM applications such as coding 10 ; 11 , tool calling 19 ; 20 ; 18 , etc. necessitate structured generation: the generation of text that conforms to a specific format. Although LLMs excel at generating syntactically-correct text in formats frequently found in their training data 4 ; 15 , they struggle to conform to the specifications of novel formats such as domain-specific languages and unique programming languages (see Section 4 ). In such situations, it is desirable to constrain the model’s outputs to guarantee syntactic correctness. 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. Structural constraints for LLM decoding are often defined by context-free grammars (CFGs; 5 ; 2 ; 6 , etc.) , which are strictly more expressive than regular expressions, and encompass use cases such as the JSON file format, XML, many programming languages, chemical structure notation ( 22 , e.g.) , etc. To guarantee that LLM outputs conform to a given CFG, constrained decoding engines are employed to modify the LLM’s next-token distribution, masking the probability of all tokens which would lead to a generated sequence that violates the format specified by the CFG. Figure 2: C++ code generated by Llama-3.2-3B-Instruct using CFGzip . The LLM operates over the actual tokens (left), while the grammar engine operates over the smaller vocabulary of equivalence class representatives (right): in this figure, each unique equivalence class is highlighted with a unique color for reference. Given the large overhead already associated with parsing a CFG— \mathcal{O}(n^{3}) in the worst case 7 —the runtime cost associated with naively checking the validity of each token at each step can be prohibitively high. For this reason, SoTA grammar engines incorporate substantial online and offline optimization techniques. Despite these improvements, even the fastest grammar engines still introduce massive latency—a 2-10x slowdown—when used with more complex CFGs (e.g. programming languages; see Section 4 ). To ameliorate this online overhead, we introduce CFGzip (Section 3 ), a compression technique that vastly reduces the per-step runtime of the grammar engine. The key idea behind our approach is that many tokens are interchangeable with respect to the grammar, in that we need only check the validity of one to determine the validity of all tokens within a given equivalence class. CFGzip works by first pre-computing these equivalence classes, then wrapping the grammar engine at inference time, so that the engine operates over representatives of the equivalence classes, rather than the token vocabulary itself (see Figures 1 and 2 ). In this way, CFGzip synergizes with the engine’s built-in optimizations, resulting in a more than 20x reduction in overhead over the current SoTA grammar engine. This corresponds to an up to 7.5x reduction in total constrained generation time —i.e. the combined runtime of the LLM and grammar engine—for more complex CFGs (see Section 4 ), making CFG-constrained generation feasible at scale for complex CFGs. CFGzip is: 1. Offline: compression is performed once per tokenizer/CFG pair, and the compressed vocabulary is cached to disk. At inference time, CFGzip incurs virtually no overhead. 2. Lossless: CFGzip compression is provably lossless, meaning that the outputs of a grammar engine equipped with CFGzip are guaranteed to be byte-identical to those of the original engine. We make available on GitHub all code used in the experiments in this paper 1 1 1 https://github.com/coli-saar/cfgzip-experiments — CFGzip itself is available as a pip-installable Python package 2 2 2 https://pypi.org/project/cfgzip . 2 Background and Preliminaries In the following, we adopt the Kleene star 12 notation: given a set X , we define X^{*} as the set of all sequences of elements of X (i.e. strings over X ), including the empty sequence/string \epsilon . Given strings w,z , we denote their concatenation through juxtaposition: wz . 2.1 Context-Free Grammars (CFGs) A CFG G=(V,\Sigma,R,S) is defined by a set V of non-terminal symbols , an alphabet (set of characters) \Sigma , a start symbol S\in V , and a set R of productions (rewrite rules) of the form A\rightarrow\alpha , where A\in V is a non-terminal and \alpha\in(V\cup\Sigma)^{*} is a sequence of terminals and non-terminals. Each CFG G defines a language (set of strings) L(G)\subseteq\Sigma^{*} , where w\in L(G) if and only if S\Rightarrow^{*}w : i.e. there is a finite sequence of rules S\rightarrow\alpha_{0},A_{1}\rightarrow\alpha_{1},\dots,A_{n}\rightarrow\alpha_{n}\in R that derives w from S (a parse of w ). We additionally define the set \textit{Pr}(L(G)) of prefixes of L(G) : strings w\in\Sigma^{*} such that there is some (possibly empty) string z\in\Sigma^{*} such that the concatenation wz is in L(G) . Greibach Normal Form ( 9 , GNF;) . A CFG G is in GNF if all productions in G are of the form S\to\epsilon (where S is the start symbol) or A\to a\hskip 2.84526pt\beta , where a\in\Sigma is a (non- \epsilon ) terminal symbol and \beta\in(V-\{S\})^{*} is a (possibly empty) sequence of non-terminal, non-start symbols. It is a well-known result that for every CFG G , there is an equivalent CFG G^{\prime} in GNF—i.e. such that L(G)=L(G^{\prime}) . Each GNF CFG G defines a simple pushdown automaton (PDA 3 3 3 Every CFG defines a PDA: we defer an in-depth discussion of PDAs to prior work, and provide an semi-formal description here that is sufficient for the discussion at hand. ) that recognizes (parses) L(G) : this PDA consists of a stack \sigma of non-terminal symbols of G , and a transition function 4 4 4 We ignore states in the definition of the transition function, as PDAs derived from GNF CFGs have only one state. \delta_{G} mapping pairs of terminals and non-terminals to sequences of non-terminals. For each terminal a\in\Sigma , non-terminal A\in V , and sequence of non-terminals \beta\in V^{*} , \beta\in\delta_{G}(a,A) if and only if A\to a\hskip 2.84526pt\beta is a production in G . Given a string w in \Sigma^{*} , the PDA parses w non-deterministically, with its stack initialized to \sigma=(S) , where S is the start symbol of G . The PDA scans w character-by-character: at the i^{th}