Search papers, labs, and topics across Lattice.
This paper introduces CFGzip, an offline token space compression technique, to accelerate context-free grammar (CFG) constrained decoding for large language models. By reducing the per-step search space, CFGzip significantly lowers the overhead associated with CFG engines, especially for complex grammars. Experiments demonstrate up to two orders of magnitude latency reduction and a 7.5x speedup in total constrained generation time when combined with a state-of-the-art grammar engine.
Constrained decoding, previously impractical for complex grammars, is now feasible at scale thanks to a novel token space compression technique that slashes latency by up to 100x.
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.
