通过压缩搜索空间，让语法约束解码快100倍
Accelerating Constrained Decoding with Token Space Compression
- 离线压缩词表搜索空间，减少每步计算量
- 实测延迟降低两个数量级，生成速度提升7.5倍
- 适合需要复杂结构输出的大模型应用
为确保大模型输出符合指定结构，上下文无关文法（CFG）解码引擎需在每一步筛选符合文法的下一个词元。尽管现有引擎已高度优化，但因每步需遍历整个词表带来的固有开销，在处理复杂文法时仍导致难以接受的延迟——而这正是CFG引擎最需发挥作用的场景。本文提出CFGzip，一种离线压缩词元搜索空间的技术，显著降低引擎开销。实验表明，结合当前最优文法引擎，使用CFGzip可实现高达两个数量级的延迟下降，总约束生成时间提速7.5倍，使复杂文法下的约束解码在大规模应用中成为可能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。