Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective¶

会议: ICLR 2026
arXiv: 2601.18999
代码: GitHub
领域: LLM Serving / KV Cache / Load Balancing
关键词: KV缓存淘汰策略, 随机化算法, 负载均衡路由, 多LLM服务, 竞争比分析

一句话总结¶

提出首个KV缓存感知负载均衡统一数学模型，设计随机化叶节点淘汰算法RLT(O(log n)竞争比)和基于学习的贪心路由LBGR，在多LLM服务场景下将延迟降低最高11.96×、TTFT降低14.06×。

研究背景与动机¶

KV缓存是LLM推理加速的核心技术：通过复用先前查询的key-value对避免重复计算，但在内存受限时其效果高度依赖淘汰策略

LRU淘汰策略存在根本缺陷：传统最近最少使用(LRU)策略在动态查询到达模式下表现脆弱，最坏情况下恰好淘汰下一个查询需要的token，导致缓存命中率骤降

多LLM服务场景的固有矛盾：最大化单个LLM的缓存命中率（将相似查询发往同一LLM）与全局负载均衡（避免队列延迟）是相互冲突的目标

现有方法依赖启发式：SGLang用固定阈值切换路由策略，NVIDIA/llm-d用静态线性评分，缺乏形式化建模，无法适应动态查询模式

缺乏理论分析：实际系统设计和理论理解之间存在显著差距，没有统一模型捕捉缓存淘汰与负载均衡之间的耦合关系

队列负载建模过于粗糙：现有方法仅用待处理查询数量衡量拥塞，未考虑各查询实际服务时间的差异

方法详解¶

统一形式化模型¶

M个worker(LLM)各配备大小为B_i的KV缓存，在线处理N个查询序列Q={q_j}
服务时间Cost_{ij} = α_CACHED·h_{ij} + α_MISS·(|q_j| - h_{ij}) + O_{ij}，其中h_{ij}为缓存命中token数
路由决策x_{ij}∈{0,1}决定查询分配，目标：最小化所有worker的makespan（最大累计负载）
缓存状态通过UpdateCache函数更新，队列负载P_i按服务时间累加
形式化揭示了LRU的理论局限：L-LRU(SGLang的叶节点LRU)竞争比为O(n)，当查询长度高度不平衡时退化严重

RLT：随机化叶节点淘汰¶

维护标记集合T，记录已访问token；当标记数达B_i+1时清除（仅保留最新token）
当缓存满且需要加载新token时，从未标记的叶节点中均匀随机选择一个淘汰
理论保证：竞争比Θ(log(B_i - L))，比L-LRU的O(n)指数级改进
证明了这是所有随机化淘汰算法的最优下界（信息论最优）

LBGR：基于学习的贪心路由¶

服务时间估计：利用全局Radix Tree追踪各worker缓存状态，估计缓存命中token数h̃_{ij}
队列负载估计：维护P̃_i追踪每个worker负载，使用指数衰减(ρ)模拟负载随时间自然减少；查询完成后释放残余负载
残差修正：在线线性回归模型θ_i捕获环境波动带来的延迟偏差，特征向量φ包含命中数、未命中数和当前负载
贪心决策：Ê_{ij} = Cost_{ij} + P̃i + θ_i^T·φ，将查询路由到预测延迟最低的worker
在线更新：观测实际延迟后最小化(E_{ij} - Ê_{ij})²持续更新回归模型
后台衰减线程：每Δt时间单位对所有worker执行P̃_i ← ρ·P̃_i，避免负载估计累积失真

实验¶

主实验结果¶

对比方法	中位延迟降低	中位TTFT降低	缓存命中率提升	吞吐提升
vs Random+LRU	30.9×	44.49×	-	-
vs Cache-Aware+LRU (SOTA)	11.96×	14.06×	36.45%	36.51%
vs Cache-Aware+LRU (P95)	2.03×	2.62×	-	-

消融实验¶

方法	P50延迟(ms)	P50 TTFT(ms)	命中率	额外开销
Cache-Aware+LRU	26680	25022	23.89%	baseline
Cache-Aware+RLT	19191	14332	26.36%	+0.58ms淘汰
LBGR+LRU	6025	2958	33.33%	+0.56ms路由
LBGR+RLT	2263	1088	37.31%	+2ms总开销

模型规模与架构泛化¶

模型	硬件	vs Cache-Aware+LRU 延迟降低	vs Cache-Aware+LRU TTFT降低
Llama-3.1-8B	10×L40	11.96×	14.06×
Llama-3.1-70B	4×H200	5.46×	7.19×
Mixtral-8×7B (MoE)	4×H200	显著优于所有baseline	显著优于所有baseline

关键发现¶

在Llama-3.1-8B(L40 GPU)和70B(H200 GPU)、Mixtral-8×7B上均有效，跨稠密/稀疏架构泛化
最坏情况轮询到达顺序下，LBGR+RLT依然大幅领先(22.8×延迟降低、15.5× TTFT降低)
缓存大小从50%到90%、worker数从2到10、请求率4-20 req/s均鲁棒
单worker实验也验证RLT优于L-LRU：缓存命中率最高提升6.92×，吞吐提升77.4%
随着缓存容量增大，LBGR+RLT与baseline的性能差距进一步拉大
worker数≥6时各方法吞吐趋于饱和（请求率固定12 req/s时系统容量充足）

亮点¶

首次为KV缓存感知负载均衡建立统一数学模型，填补了理论与实践的空白
RLT的O(log n)竞争比证明是信息论最优（不可再改进），这是经典在线算法理论在LLM系统中的优雅应用
两个算法的额外运行时开销极低（每查询仅~2ms），高度实用，可即插即用到现有系统
LBGR的指数衰减+在线回归设计简洁有效，避免了复杂RL或预测模型的训练开销
实验覆盖4种基准(GSP/ShareGPT/UltraChat/Loogle)、3种前缀共享场景、多种模型规模/架构，非常全面

局限性¶

仅评估文本推理，未涉及多模态KV缓存（图像token的缓存特性可能不同）
受限于10个worker的单域部署，未验证大规模或异地分布式场景下的网络延迟影响
理论分析假设在线对抗到达，实际workload的分布特性（如Zipf分布）可进一步利用以获得更紧的界
LBGR的线性回归残差模型可能在高度非线性的延迟场景中不够表达力
输出token长度实验仅测试到128，更长生成（如4K+）场景未探索

评分 ⭐⭐⭐⭐⭐¶

新颖性: 5/5 — 首个统一形式化+最优竞争比证明，理论贡献扎实
实验充分度: 5/5 — 4基准×3设置×多模型×多参数扫描，消融彻底
写作质量: 5/5 — 理论与实验衔接清晰，问题动机阐述充分
实用性: 5/5 — 额外开销仅2ms，可直接集成到SGLang等系统