Accelerating Constrained Decoding with Token Space Compression
For LLM practitioners needing structured outputs, CFGzip dramatically reduces the overhead of CFG-constrained decoding, enabling practical use of complex grammars.
CFGzip compresses the token search space for CFG-constrained LLM decoding, reducing latency by up to two orders of magnitude and achieving up to 7.5x speedup in total generation time, making constrained decoding feasible at scale for complex grammars.
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.