随机化提升KV缓存，学习平衡查询负载：联合视角

KV缓存是一种通过重用先前查询的键值对来加速大语言模型（LLM）推理的基本技术，但其在有限内存下的有效性高度依赖于驱逐策略。默认的最近最少使用（LRU）驱逐算法难以应对动态在线查询到达的问题，尤其在多LLM服务场景中，平衡工作节点上的查询负载与最大化每个节点的缓存命中率是固有的冲突目标。本文首次提出一个统一的数学模型，捕捉KV缓存驱逐与查询路由之间的核心权衡关系。分析揭示了现有方法的理论局限性，并提出了结合可证明竞争性随机化KV缓存驱逐与基于学习的方法的算法，以自适应地处理具有演变模式的查询，从而实现查询负载与缓存命中率的平衡。理论结果通过4个基准和3种前缀共享设置的大量实验验证，展示了在缓存命中率、延迟、首词生成时间（TTFT）和吞吐量方面的显著提升。