用于大有限集约束解码的Trie自动机

大语言模型日益需要生成符合预定义模式的结构化输出，其中一种常见约束是从有效字符串的有限集合中选择。当前约束解码系统通过通用文法编译处理这一问题，但当有效值的数量增长到数千时会变得极其缓慢，即基数墙。我们提出Trie自动机，一种专门化机制，通过Aho-Corasick多模式匹配利用有限集合结构（共享前缀、有界深度、已知基数）来预计算每个节点的token掩码。相比vLLM与SGLang的主要后端之一XGrammar，Trie将每步有效token计算提速7倍（0.65微秒对5.8微秒），并在K≥300时将编译提速2–6.5倍。由于预计算掩码支持绕过引导解码管线的无状态服务路径，该优势在批量服务中叠加：批大小256时，端到端vLLM吞吐达到219 req/s，而XGrammar为7.5 req/s（29倍）。这29倍是算法加速与只有预计算掩码才能释放的集成路径节省的结合。跨七个分词器家族（32K–262K词表），Trie在K=10,000以内保持百毫秒以内的编译，且每步成本不随集合大小变化，同时保证100%输出有效性。