Prefix Sharing Is a Sorting Problem 证明 LLM 服务中前缀共享等同于排序问题

该研究证明 LLM 服务中的前缀共享优化在数学上等同于在请求上构建二进制层次结构，打破了传统固定顺序的假设。 作者提出 O(3^m) 精确算法，指出聚类算法可实现 1/2-近似最优节省，并识别出两部件情况对应最小点覆盖。 在 BM25 检索迹线上，新布局使 prefill 减少 17-36%，且层级 DFS 排序可精确达到无限缓存最优性能。