小红书精读：Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators

Trie拍平成稀疏矩阵，解码快948倍

各位算法同学们，约束解码的瓶颈往往不在算法对不对，而在内存访问规不规整——把前缀树拍平成一个静态CSR稀疏矩阵，TPU上每步只多0.033ms、占推理时间0.25%，比CPU trie快948倍。做生成式推荐时被“只能推有货的、只能推新鲜的”这类业务规则卡过的人，这篇是正面解法。

📄 Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators

🔧 把前缀树压成静态CSR稀疏矩阵，树遍历变成向量化的稀疏矩阵操作，读取是coalesced的，对约束集大小的I/O复杂度是O(1)，而二分查找baseline是对数级。

🧩 无分支解码：动态切片加掩码算术，约束逻辑全程留在加速器上跑，Host和Device之间不用来回通信，也让依赖静态图的XLA能编译。

⚙️ 面向SID生成检索的真实规模：2000万量级的物品约束集也扛得住；FST在这种百万级以上高基数词表上会状态爆炸，而且没有TPU原生支持。

📊 线上每步解码只增加0.033ms，约占推理时间的0.25%。

📈 相比CPU trie实现948倍加速，相比硬件加速的二分查找baseline快47到1033倍。

✅ 已部署在服务数十亿用户的视频推荐平台上，2000万新鲜视频约束集下核心业务指标有正向变化；论文称这是首个生产规模的严格约束生成式检索。

📉 Amazon Reviews评测里，把冷启动物品集作为约束，冷启动推荐效果有明显提升。

要我判断的话：如果你在做生成式推荐、又被业务过滤规则和延迟两头夹着，这套方案可以直接抄，代码已开源。真正要盯的指标是per-step延迟和约束集规模放大后的曲线，而不是只看向上的加速倍数。落地坑在于CSR索引本身的内存占用和构建成本，约束集高频变化（比如库存实时变动）时怎么增量维护，论文没展开；另外加速来自稀疏算子，约束集特别小的时候未必划算。

原文：AlphaXiv