$$x_{i,t+1} \leq \sum_{j=1}^{t}(q_{i,j} + a_{i,j}), \quad \forall i \in [N], t \in \mathcal{T}_i, t < T$$

$$x_{i, t+1} \leq x_{i, t}, \quad \forall i \in[N], t \notin \mathcal{T}_{i}, t<T \quad \text { (cache increases only on arrival) }$$</div> 我们假设采用可选缓存（optional caching），即服务完一个请求后不强制要求将其添加到缓存中。

延迟目标：TEL。我们旨在通过缓存策略优化尾部延迟。由于基于百分位的尾部延迟难以直接优化，我们引入尾部超额延迟（Tail Excess Latency, TEL） 作为一种易于处理的替代指标：

$$ \mathrm{TEL} := \sum_{i \in[N], t \in \mathcal{T}_{i}} \max \left\{\operatorname{TTFT}(i, t)-\xi_{s}, 0\right\}, $$

其中 TTFT(i, t) 是对话 i 在时间 t 请求的TTFT，ξs 是预定义阈值。TEL类似于风险价值条件（CVaR），但具有明确的用户指定阈值。我们将 ξs = 0 的情况视为恢复了平均延迟目标。

TTFT的线性近似。我们假设TTFT与未缓存块的数量成线性增长，这一假设得到了经验验证（如图3所示）。因此，TEL可以表示为：

$$ \text{TEL} = \alpha \sum_{i \in [N], t \in \mathcal{T}_i} \max \left\{ \sum_{j=1}^t q_{i,j} + \sum_{j=1}^{t-1} a_{i,j} - x_{i,t} - \xi, 0 \right\} $$

其中 ξ = ξs/α，而需要计算的块数为对话 i 在时间 t 的总历史长度减去已缓存的块数 xi,t。

TEL的后见最优策略。如果系统预知整个未来的到达轨迹，那么最小化TEL的最优缓存策略是什么？这个后见最优基准揭示了改善尾部延迟的关键因素，从而指导我们的策略设计。后见最优策略选择缓存变量 {xi,t} 来最小化TEL，可以形式化为一个优化问题：

$$\begin{aligned} \begin{aligned} \min_{x_{i,t}, u_{i,t} \in \mathbb{N}} & \sum_{i \in [N]} \sum_{t \in \mathcal{T}_i} u_{i,t} \\ \text{s.t. } & (4), (5), (6) \\ & u_{i,t} \geq \sum_{j=1}^{t} q_{i,j} + \sum_{j=1}^{t-1} a_{i,j} - x_{i,t} - \xi, \quad \forall i \in [N], t \in \mathcal{T}_i \quad \text{(slack variable)} \end{aligned} \end{aligned}$$

其中 ui,t 是松弛变量，在最优解中等于超出阈值 ξ 的未缓存块数。

定理1 (后见最优策略结构)。最小化TEL的后见最优策略将分配给每个对话的KV缓存块数量限制在TEL安全预算内，即 (Σ(qi,j + ai,j) - ξ)+。如果总分配超过缓存容量，该策略会从下一个请求预计最晚到达的对话中驱逐缓存块。
该定理的证明见附录A。当 ξ = 0 时，该策略恢复为经典的Belady最优策略【Belady, 1966, A study of replacement algorithms for a virtual-storage computer】。因此，最小化TEL的后见最优策略可以被描述为Belady策略的一个阈值上限版本，我们称之为尾部优化Belady (Tail-Optimized Belady)。

尾部优化LRU

算法设计。受尾部优化Belady策略（定理1）的启发，我们提出了尾部优化LRU（Tail-Optimized LRU, T-LRU），这是一种在线策略，它同样着眼于未来，并仅缓存足以防止对话的下一轮影响TEL的量。为了将后见最优策略应用于在线设置，我们做了两个修改：1) 用一个估计值 Qˆ 替代实际的下一轮提示长度 Q；2) 使用最近最少使用（LRU）的驱逐策略替代最远未来（furthest-in-future）策略。算法1给出了伪代码。

算法1: 尾部优化LRU策略
输入: 对话数量N, 上一轮时间戳{τi}, 缓存块数{Xi}, 对话历史长度{Li}, 到达的对话θ, 到达的对话长度L'θ
参数: 策略参数：阈值ξ, 下一轮长度估计{Qˆi}
输出: 更新后的缓存大小{Xi}

Lθ ← L'θ, Xθ ← Lθ, τθ ← 当前时间戳 // 更新到达对话的系统状态
if Σi∈[N] Xi > C then
  foreach i ∈ [N] do
    if Xi ≥ Li + Qˆi − ξ then
      Xi ← Xi − 1 // 在TEL目标下的“免费驱逐”
  if Σi∈[N] Xi ≤ C then
    return X
while Σi∈[N] Xi > C do
  找到 j = arg mini∈[N]:Xi≥1 τi // 使用LRU驱逐
  Xj ← Xj − 1
return X

与现有缓存系统的轻量级集成。在基于LRU的缓存系统中实现T-LRU仅需一个额外的记录：将可以“免费”驱逐的块（即在主动修剪阶段识别出的块）标记为无限老。然后，任何现有的LRU引擎都可以通过常规方式无缝驱逐这些块。此设计也与将键和值存储在非连续内存空间的分页KV缓存技术兼容。

尾部优化LRU在随机对话模型中的最优性

随机对话模型。经典的缓存模型无法捕捉LLM工作负载的特性。为了解决这个问题，我们构建了一个新的随机模型，该模型通过一个连续时间的生灭过程来建模活跃对话的数量，从而捕捉LLM工作负载的独特特征，如多轮对话的动态开始、演变和终止，以及强大的时间局部性（即一个用户越久没有发送下一个提示，他们返回的可能性就越小）。具体来说：
* 新对话以速率 λconv > 0 “诞生”，每个活跃对话以速率 μ > 0 “死亡”。
* 活跃期间，对话 i 根据速率为 λ¯i > 0 的独立泊松过程生成请求。
* 每轮对话中，从已知分布中抽取一个随机的提示长度 Q。

信念马尔可夫决策过程 (Belief Markov Decision Process)。由于决策者只观察到轮次的到达而无法观察到对话的终止，该问题被建模为一个部分可观察马尔可夫决策过程（POMDP）。系统的信念状态可以分解为每个对话的个体期望轮次到达率。决策者在时间 t 对话 i 仍然活跃的信念 πi(t)，其期望轮次到达率为 πi(t) · λ¯i。该信念根据以下公式更新，因为每个对话的持续时间服从均值为 μ 的指数分布：

$$\pi_{i}(t)=\exp (-\mu(t-\text { last turn time })),$$

期望尾部优化LRU (ET-LRU)。我们定义了ET-LRU策略，该策略选择在服务完每个请求后缓存哪些块，以最小化下一轮的期望TEL。
定义1 (期望尾部优化LRU)。ET-LRU选择使下一轮期望TEL最小化的到达后缓存分配。形式上，它解决以下优化问题：

$$ \boldsymbol{X}^{ETLRU} \in \arg \min \sum_{i} \lambda_{i}(t^{+}) \cdot \mathbb{E}[(L_{i}(t^{+}) + Q_{i} - Y_{i} - \xi)^{+}] $$

服从以下约束：

其中，期望是针对下一轮随机用户提示长度 Qi 计算的。

定理2 (期望尾部优化LRU的最优性)。在上述随机对话模型下，期望尾部优化LRU（定义1）是最小化尾部超额延迟的最优在线缓存策略。
该定理的证明通过对轮次数进行归纳，并比较我们策略与其他驱逐策略的未来价值函数。该定理有三个重要推论：
* LRU对于平均延迟是最优的。当设置 ξ = 0 且各对话轮次到达率相同时，ET-LRU退化为LRU。因此，定理2在我们的随机到达模型下确立了LRU在最小化平均延迟方面的最优性。
* T-LRU的最优性。如果用户提示长度是确定性的，ET-LRU就简化为策略1中描述的确定性版本（T-LRU）。因此，定理2确立了T-LRU在该模型中的最优性。
* 对经典缓存的推广。当 Q = 0 且响应长度为零时，我们的模型简化为经典的单位页面大小缓存问题。在这种情况下，最优策略是“驱逐其对话最不可能返回的块”，这是对LRU的推广。

实验

实验环境

• 数据集: 我们在两个对话数据集上评估我们的缓存策略：WildChat【Zhao et al., 2024, Wildchat: 1m chatgpt interaction logs in the wild】和ShareGPT【Contributors, 2025, Sharegpt: A dataset of multi-turn chat interactions with large language models】。我们从每个数据集中选取按到达时间戳排序的对话，并提取前1000-2000轮进行模拟。WildChat的数据分布如下图所示。

• 模型与硬件: 默认实验配置使用在单张A100 GPU上通过vLLM服务的Vicuna-7B模型，张量并行度为1（TP=1），且未启用混合批处理。
• 评估指标: 我们测量延迟指标（中位数、P90、P95、P99）和服务水平目标（SLO）达成率。

尾部延迟降低

与基线的比较。我们比较了T-LRU与LRU和Threshold-LRU（仅当对话长度超过固定阈值时才缓存）的性能。T-LRU的下一轮提示长度估计 Qˆ 设为平均提示长度（WildChat为200），Threshold-LRU的阈值设为1024。

结果分析。如表1和表2所示，T-LRU显著降低了尾部延迟。与LRU相比，T-LRU将P90尾部TTFT降低了高达27.5%，将P95尾部TTFT降低了高达23.9%。

对延迟阈值 ξs 的敏感性。T-LRU的效益在延迟阈值 ξs 与目标尾部百分位数相匹配时达到峰值。例如，当LRU下的P90延迟约为240ms时，将 ξs 设为200ms可以获得最大的P90延迟改进。操作上，ξs 可以根据固定的SLO（例如目标TTFT）进行调整，或者根据观察到的服务轮次的尾部延迟自适应调整。

Threshold-LRU与T-LRU的比较。Threshold-LRU对每个对话做出二元的“全有或全无”缓存决策。相比之下，T-LRU做出自适应、细粒度的缓存决策，仅缓存足以确保下一轮请求不会超过延迟阈值的令牌量。这种根本性差异使得T-LRU更为高效。

表1：T-LRU相对于LRU在不同ξs下的相对延迟改善

表2：T-LRU相对于Threshold-LRU在不同ξs下的相对延迟改善

SLO违规减少

结果分析。我们测量了延迟超过200ms的请求数量。如表3所示，当延迟阈值 ξs 设置为200ms时，与LRU相比，T-LRU减少了8.8%至40.7%的违规请求。这表明TEL最小化的设计目标不仅惩罚了请求超出 ξs 的程度，而且当 ξs 与目标延迟预算对齐时，也能有效减少SLO违规的数量。

对延迟阈值 ξs 的敏感性。当 ξs 远低于SLO时，改进不大；当 ξs 远高于SLO时，T-LRU专注于更大的尾部延迟，可能会允许一些200ms的违规。

表3：T-LRU的相对改进：延迟 > 200ms的请求减少百分比

离线基线和具有未来知识的T-LRU变体

实验设置。为了探究何种类型的未来预测对缓存最有价值，我们设计了具有不同未来知识水平的T-LRU变体：
* T-LRU (基线): 使用经验平均提示长度进行预测。
* End-Aware T-LRU: 知道每个对话是否将继续或终止。
* Length-Aware T-LRU: 既知道对话是否继续，也知道下一轮用户提示的确切长度。
* Tail-Optimized Belady: 后见最优策略，知道整个未来到达序列。

结果分析。图5展示了不同缓存策略在WildChat数据集上的延迟分布。
* 中位数与尾部延迟的权衡。T-LRU（蓝色方块）在尾部延迟方面始终优于LRU和Threshold-LRU，但其中位数延迟略高（从10ms增加到40ms）。这种权衡是设计使然，T-LRU特意牺牲了用户几乎无法察觉的几毫秒中位数延迟，以换取数十到数百毫秒的尾部延迟降低，这对用户体验更有利。
* 预测的价值。一个简单的“该对话是否会继续？”的预测信号非常强大。End-Aware T-LRU的性能远优于T-LRU，而知道确切提示长度的Length-Aware T-LRU仅获得了微小的额外优势。这表明，预测对话是否继续是提高缓存性能的一个极具潜力的方向，且比预测确切的提示大小更容易实现。

结论与未来方向

我们提出了尾部优化LRU（T-LRU），这是对最近最少使用（LRU）缓存策略的一个简单而有效的修改，显著改善了多轮对话式LLM服务中的尾部延迟。通过自适应地缓存刚好足够的令牌以使每个对话的下一轮请求低于延迟阈值，T-LRU在对中位数性能影响不大的情况下，实现了显著的尾部延迟降低（例如，P95 TTFT改善20-30%）。

T-LRU的设计选择是以牺牲中位数的几十毫秒为代价，来消除尾部的数百毫秒延迟，这与生产系统中的严格SLO要求非常吻合。

未来工作包括：
* 探索平衡尾部和中位数延迟的多目标策略。
* 将T-LRU扩展到多层级KV缓存系统，其中被驱逐的块迁移到较慢的存储（如CPU内存、SSD）而不是被丢弃。
* 对缓存和负载均衡进行联合优化，系统地分析缓存局部性和负载分布之间的基本权衡，以指导实际的系统设计。

附录

A 定理1（TEL的后见最优策略）的证明

证明概述。证明分两步：1) 证明优化原始TEL问题(7)等价于一个新的问题(11)，即在附加的“TEL安全”上限约束下最大化重用缓存块的总数；2) 证明这个新问题是一个经典的离线缓存问题，其最优解是对KV缓存大小使用TEL安全预算进行限制，然后使用最远未来（furthest-in-future）策略进行驱逐。

第一步：优化问题的等价性。对于一个给定的可行缓存决策 x，最优的松弛变量 u 由下式给出：

$$u_{i, t}=\left(\sum_{j=1}^{t} q_{i, j}+\sum_{j=1}^{t-1} a_{i, j}-x_{i, t}-\xi\right)^{+},$$

可以证明，优化问题(7)的最优解必须满足TEL安全预算，即对于每个 i ∈ [N], t ∈ Ti，xi,t ≤ (Σqi,j + Σai,j - ξ)+。否则，如果 x'i,t > (Σqi,j + Σai,j - ξ)，那么多出的缓存不会改善目标函数值，但占用了可以分配给其他对话的缓存容量，这与最优性矛盾。
因此，最小化总的 ui,t 等价于最大化总的 xi,t。我们可以将问题(7)重写为：

服从约束 (4), (5), (6) 和

第二步：与经典分页问题的联系。我们可以将每个块解释为一个单位大小的项。在时间 t ∈ Ti，对话 i 请求的缓存命中数恰好等于 xi,t。因此，(11)的目标是最大化整个时间范围内的总缓存命中数。由于缓存内容仅在请求时改变，且所有项大小为单位1，问题(11)是一个具有单位页面和预知知识的分页实例，只是每个请求对允许的命中数有一个上限。在单位页面的分页问题中，最大化总命中数的离线最优策略是Bélády的最远未来规则：当需要驱逐时，驱逐下一个请求最远的项。在这里，对话 i 的所有块共享相同的下一个请求时间，因此规则简化为：从下一个到达最远的对话中驱逐。

B 定理2的证明

证明概述。证明使用了对轮次数的归纳法，并论证了如果选择不同于ET-LRU的缓存状态，成本将会更高。有限范围内的未来价值函数（value-to-go function）可以表示为：

$$V_{k}(\boldsymbol{\lambda}, \boldsymbol{L}, \boldsymbol{X}, \theta, Q, A) = \underbrace{(L_{\theta} + Q - X_{\theta} - \xi)^{+}}$$

其中 VM+1(·) = 0，X 是可行的缓存决策空间。证明的核心在于表明，无论两次到达之间的时间间隔 τ 为何，对话的返回率保持相同的相对顺序。然后通过对每次驱逐一个令牌进行分析，证明ET-LRU策略（即驱逐具有最低排名准则分数的令牌）比任何其他驱逐策略都能获得更低的未来期望成本。排名准则分数由下式给出：

贪心实现。优化问题(8)无需显式求解，一个逐令牌的贪心程序即可。该策略通过计算每个令牌的边际成本增加（即驱逐该令牌导致的期望成本增加）来对其进行排名。实现时，可以使用最小堆来处理要驱逐的令牌。

引理1。策略2返回了优化问题(8)的一个最优解。
证明通过反证法进行。假设存在一个最优解 X*，其中存在两个对话 i, j，使得从 j 驱逐一个令牌并将其分配给 i 会违反策略2的排名顺序。然后可以构造一个新的解 X'，并证明 X' 的目标值优于 X*，从而与 X* 的最优性相矛盾。

C 关于强制缓存的讨论

强制缓存下的T-LRU实现。在强制缓存（forced caching）模式下，服务器在服务完一轮后必须缓存其完整的对话历史，包括新生成的响应。由于模型响应长度的不确定性，服务器可能不知道总共需要驱逐多少缓存块。然而，服务器可以重复调用我们的策略，在需要时驱逐更多的令牌。

后见最优策略。在强制缓存下，定理1仍然成立。

期望尾部优化LRU。在强制缓存下，定理2（ET-LRU的最优性）在以下条件下仍然成立：
* 未来的每个提示（如果到达）都有一个已知的、固定的长度 Q ≥ 0。
* 对话具有同质的轮次到达率 λturn。

D 附加图表

E KV缓存大小计算

我们计算了Vicuna-7B模型的KV缓存内存需求。对于以Float16精度存储的10,000个令牌，总KV缓存大小约为4.88 GB。

模型配置:
* 隐藏层大小: 4096
* 注意力头数: 32
* 隐藏层数: 32
* 键值头数: 32
* 头大小: 128
* 数据类型: Float16 (每值2字节)

计算:
每个令牌的KV缓存大小 = 2 × 层数 × KV头数 × 头大小 × 数据类型大小 = 2 × 32 × 32 × 128 × 2 = 524,288字节。
对于10,000个令牌，总内存需求为：

$$\begin{aligned} \begin{aligned} \text{Total KV cache (bytes)} &= 10,000 \times 524,288 \\ &= 5,242,880,000 \text{ bytes} \end{aligned} \end{aligned}$$

转换为千兆字节：

F 在带有合成时间戳的ShareGPT上的结果

实验设置。ShareGPT数据集不包含请求的时间戳，因此我们使用第5节中描述的随机模型生成它们。

结果分析。如表4和表5所示，T-LRU仍然优于LRU和Threshold-LRU，将P90延迟削减了高达10%，P95延迟削减了高达7%。与WildChat相比，改进幅度较小，这是因为LRU下的基础延迟已经很高。

表4：T-LRU相对于LRU在不同ξs下的相对延迟改善（ShareGPT）

表5：T-LRU相对于Threshold-LRU在不同ξs下的相对延迟改善（ShareGPT）

SLO违规。使用200ms的SLO，T-LRU将超出预算的请求比例降低了2-8%（表6）。

表6：T-LRU的相对改进：延迟 > 200ms的请求减少百分比（ShareGPT）

预测的价值。如图7所示，在ShareGPT数据集上，End-Aware T-LRU和Length-Aware T-LRU相对于T-LRU的收益很小，并且所有三种策略的性能都非常接近后见最优的Tail-Optimized Belady策略。这与我们的随机模型预测相符：在泊松到达下，LRU的近时性顺序已经很好地代理了“最远未来”，因此额外的预知信息带来的回报递减。