Leyline: KV Cache Directives for Agentic Inference
Leyline: KV Cache Directives for Agentic Inference — L2 #
1. TL;DR #
用“KV 缓存编辑指令”把 agent 的消息改写变成服务端可执行的 span splice；在 MLA 下用闭式 RoPE $\delta$-rotation 让编辑后缓存仍位置正确，从而提升 replay cache hit（+11.2pp）并在部分并发下显著降延迟（峰值 -241ms）。
2. Q1 / Q2 / Q3（痛点 / 方法 / 结果） #
Q1 痛点：agentic 会“改历史”，而 KV 假设是“只追加” #
- 工作负载变化：agent 在多轮循环里会执行 message edit（删/替换/截断工具输出、压缩历史、插入 stub），导致同一条轨迹的后缀 token “重新定位”，而不是简单的前缀增长。
- 现有缓存缺口：prefix caching / radix trie 适合“前缀不变、后缀重放”，但遇到 in-place edit 时要么 整段 re-prefill（昂贵），要么 天真复用旧 KV（RoPE 位置不对，语义漂移/错误）。
Q2 方法：把“改什么”与“怎么改 KV”拆开（指令接口 + $\delta$-rotation 内核） #
- 指令抽象（serving-side）：把一次编辑表述为 4-tuple 指令
- $D=(s_{\mathrm{start}}, s_{\mathrm{end}}, R, m)$
- 语义：把缓存中 span $[s_{\mathrm{start}}, s_{\mathrm{end}})$ 替换成 replacement $R$，模式 $m \in \{\texttt{amortize},\texttt{forget}\}$。
- 两种模式：
amortize：目标是“像 full-context 一样继续生成”，但不做全量 re-prefill；服务端 splice KV 并对下游位置做修正。forget：目标是真正语义删除；通过裁剪前缀 + re-prefill 达成（牺牲复用换语义擦除）。- MLA $\delta$-rotation 关键机制：对下游缓存 slot 的 RoPE positional component $K_{\mathrm{pe}}$ 做一次闭式旋转修正；$K_{\mathrm{nope}}$ 与 $V$ 复用不动，从而把“替换引起的位置偏移”用代数补回。
- 核心技术壁垒：在“语义层 span edit”与“张量层 KV splice”之间建立 可审计的指令契约，并在 MLA 的 $K_{\mathrm{pe}}/K_{\mathrm{nope}}$ 分解下给出可实现、可组合的闭式位置修正，使 radix 前缀在编辑后仍可复用而无需全量重算。
Q3 结果：正确性可证伪 + 机制收益 + 策略收益（分两条腿验证） #
- 正确性（机制层）：构造 full-context 与 re-prefill 的下一 token 故意分歧，用“第一 token”做可证伪判据；Leyline 在
amortize下与 full-context 对齐。 - 机制收益（服务层）：在真实 serving 设置下提高 replay cache hit（+11.2pp），并在某些并发点显著降低端到端 p50（峰值 -241ms）。
- 策略收益（应用层）：把一个简单 truncation policy 接到接口上，在 debug-gym 上总体 solve rate 从 31.2% 提升到 45.5%（+14.3pp）。
3. 架构 / 方法图（含 agent loop） #
Paper's Figure 2, verbatim (caption: "Leyline serving-stack pipeline. A policy emits directives; the kernel matches the unchanged prefix, prefills the replacement tokens, and rotates cached $K_{\mathrm{pe}}$ for downstream slots via the $\delta$ -rotation (Section˜3.2). The radix prefix’s unchanged subtree is preserved across the edit.").
这张图把系统分成三层：policy 发指令、serving 执行 splice、内核做位置修正。关键观察点是：replacement 只需要局部 prefill，而下游缓存通过 $\delta$-rotation 继续可用，从而保留 radix 的“未变子树”。
Paper's Figure 1, verbatim (caption: "Teaser. A coding agent emits an explicit directive over its KV cache, expressed as a $(\mathrm{span},\,\mathrm{replacement})$ pair. The serving stack splices the cache in place: the old chunk is replaced by a short stub, downstream cached slots are re-anchored via a closed-form $\delta$ -rotation, and the radix prefix is preserved across the edit. The agent supplies what to evict; Leyline supplies how to splice it without re-prefill.").
Figure 1 强调“接口边界”的新意：agent 只声明 编辑意图（span+replacement），而服务端负责 正确地动 KV。读者应注意：stub/截断这类常见 agent 操作，在这里被显式提升为可组合的 cache-edit primitive。
3.1 指令接口（可被 agent 当作一种“工具调用”） #
最小信息量可以表述为（概念 schema）：
{
"span": {"start": 123, "end": 456},
"replacement": "token sequence (may be a short stub)",
"mode": "amortize | forget"
}
- Side effects：
amortize会修改缓存并保留 radix 结构；forget会触发裁剪 + re-prefill（可视为“明确放弃复用以换语义擦除”）。 - Error surface：当多指令组合、RoPE pairing 或数值精度导致验证失败时，系统的安全回退路径是
forget/re-prefill（重新计算而非继续复用错误缓存）。
3.2 Agent loop（单轮状态机，含失败回退） #
这里的“行动”不是外部 API，而是对 内部 memory（KV cache） 的一次可审计编辑。Leyline 把 agent 常见的“改历史”从隐式 prompt hack 变成显式状态迁移，因此能把错误恢复（fallback）纳入 serving 合约，而非留给上层策略盲猜。
4. 作者证明（无形式化作者证明 — 仅实证） #
4.1 记号表与方程物理意义 #
| 记号 | 含义 | 备注 | ||
|---|---|---|---|---|
| $D$ | cache edit directive | $D=(s_{\mathrm{start}}, s_{\mathrm{end}}, R, m)$ | ||
| $s_{\mathrm{start}}, s_{\mathrm{end}}$ | 被替换的 span 边界 | token/slot index | ||
| $R$ | replacement token 序列 | 可为短 stub | ||
| $m$ | 模式 | amortize / forget | ||
| $\Delta$ | 长度差导致的位置偏移 | $\Delta= | R | -(s_{\mathrm{end}}-s_{\mathrm{start}})$ |
| $K_{\mathrm{pe}}$ | key 的 positional 部分 | MLA 分解下可单独旋转 | ||
| $K_{\mathrm{nope}}$ | key 的 non-positional 部分 | 复用不动 | ||
| $V$ | value | 复用不动 | ||
| $R(\cdot)$ | RoPE 旋转算子 | 依赖实现的 pairing 约定 |
$$K_{\mathrm{pe}}^{\mathrm{new}}[i]=R(\Delta)\cdot K_{\mathrm{pe}}[i],$$
该式的“物理意义”是：span splice 改变了下游 slot 的绝对位置，服务端用一次 $\Delta$ 对应的旋转把缓存 key 的位置分量重新锚定到新位置，从而让注意力的几何关系与“正确的 full-context”一致。
$$R(\Delta)\,R(p)\,k\;=\;R(p+\Delta)\,k$$
这条闭包性质解释了为什么“只补一次 $\Delta$”就足以把旧位置 $p$ 的 RoPE 映射到新位置 $p+\Delta$，从而支持对缓存中下游 token 的批量修正。
4.2 经验性检查（≥6 项） #
| 检查项 | 结论 | 证据位置（纸内） |
|---|---|---|
| 1) 可证伪正确性判据：full-context 与 re-prefill 诱导分歧，Leyline 应跟 full-context | 通过（在 amortize 目标下） | §4.1 构造例子与 ablation 描述 |
| 2) 多模型覆盖：不同 MLA 模型是否同样满足一阶正确性 | 部分通过（模型间差异显著） | Table 4/5/7/10 |
| 3) 随机/语义 edit-suite 压测：编辑位置与 replacement 多样性 | 部分通过（存在失败与偏向） | Table 5/7 与附录压力测试概述 |
| 4) 多次编辑组合：多 directive 串联是否仍稳定 | 部分通过（成功率随模型变化） | Table 7 |
| 5) 数值稳定性：bf16 下旋转误差是否积累 | 给出误差随编辑次数上升的曲线 | Table 6 + fp32 旋转缓解开关说明 |
| 6) 机制层收益：cache hit / latency 是否改善且与并发相关 | 通过（命中率提升稳定；延迟在某些点显著） | Table 3 |
| 7) 策略层收益：把 policy 接到接口后是否改善任务成功率 | 通过（该 leg 明确不做机制归因） | Table 2 + §5 讨论 |
| 8) 失败模式分类：主导失败是否被方法直接针对 | 针对“RoPE stale after edit”；对“架构差异/精度漂移”只能缓解 | §4 + Limitations |
| 9) 交互延迟预算：是否达到“交互式”并量化 | 只覆盖 serving 端 p50；端到端 agent turn 预算未完整拆分 | Table 3 + Limitations |
在“agent 成功率模型”的意义上，本文只给出了一个具体策略（truncation）的 before/after（Table 2），并未系统 sweep $(\text{difficulty},\text{planning depth},\text{toolset},\text{backbone})$；因此更准确的定位是：提供可组合的 cache-edit primitive，让上层策略有机会把“历史改写”变成可测量、可审计的系统操作。
5. 实验与数据（机制 + 策略） #
Paper's Table 2, verbatim (caption: "debug-gym task solve rate: Baseline vs Treatment; Overall 31.2% → 45.5%.").
该结果证明“有了指令接口后，策略可以更激进地做 history truncation/编辑而不必总是全量重放”。同时它也刻意回避机制归因：收益可能来自策略本身，也可能来自更便宜的重放路径（论文将两者拆开验证）。
Paper's Table 3, verbatim (caption: "replay p50 e2e (ms) and replay cache hit (%), cache-off vs radix vs splice (Δ), with concurrency C.").
读这张表要抓两点：其一，splice 方案在所有并发点把 replay cache hit 从 49.6% 提升到 60.8%（稳定 +11.2pp）；其二，延迟收益是 并发相关 的（例如 $C=8$ 峰值 -241ms），说明瓶颈可能在 prefix match / prefill / KV 读写的组合上而非单一内核。
Paper's Table 7, verbatim (caption: "Valid edit steps and first-token correctness under single-edit vs multi-edit, across models.").
这张表揭示了方法的“骨感现实”：即便在同一 splice/rotation 框架下，不同模型的多编辑正确率差距巨大（从接近 100% 到个位数）。因此“适用前提”不仅是是否支持 RoPE，而更细到注意力结构与数值实现细节。
Paper's Table 6, verbatim (caption: "relative L2 and max-abs distance vs fresh as number of edits N grows.").
这组数字提供了一个直观的工程结论：即使代数上闭式成立，bf16 存储与旋转会引入累积误差；当编辑次数上升时偏差单调变大，意味着生产系统需要“验证 + 回退”或更高精度的旋转路径来兜底。
6. 论证链（paper 内部，≥3 步） #
| Step | 论点（要成立什么） | 关键假设 / 机制 | 证据（纸内） |
|---|---|---|---|
| 1 | agentic 推理引入“可变历史”，现有 KV 复用假设不再成立 | message edit 破坏 append-only；天真复用会 RoPE stale | §1 + Table 1 |
| 2 | 需要一个“cache-edit 通道”把策略意图显式化 | 把 edit 抽象为 span+replacement+mode 的指令合约 | §3 + Figure 1/2 |
| 3 | 在 MLA 下可以只修正 $K_{\mathrm{pe}}$ 来恢复位置正确性 | $K_{\mathrm{pe}}/K_{\mathrm{nope}}$ 分解 + RoPE 旋转闭包 | §3.2 + Eq(1)(2) |
| 4 | amortize splice 在语义上应等价于 full-context（而非 re-prefill） | 构造让 full 与 rp 分歧的可证伪 test；Leyline 需跟 full | §4.1 + Table 4/5 |
| 5 | 该 primitive 在 serving 上带来可观收益，并可被上层策略利用 | radix 保留提升 replay hit；延迟收益随并发变化；策略截断 solve rate 提升 | Table 3 + Table 2 |
7. 实现 cross-reference（核心壁垒 + 关键细节 + 适用前提） #
[实现未公开]
7.1 核心技术壁垒（最难复现的一点） #
难点不在“做缓存”本身，而在把 语义级编辑（span splice） 变成 张量级可组合变换：在 MLA 的结构约束下只旋转 $K_{\mathrm{pe}}$ 并保持 $K_{\mathrm{nope}},V$ 不动，从而在不破坏 radix 前缀的前提下恢复“等价于 full-context”的位置几何。这个边界一旦设计错（例如 pairing、索引重映射、组合顺序），就会出现“看似能跑但语义漂移”的隐蔽故障。
7.2 关键实现细节（容易踩坑的 1–2 个点） #
- RoPE pairing 约定必须匹配实现：interleaved vs half-split 的旋转实现不同，若按错约定旋转 $K_{\mathrm{pe}}$ 会产生系统性偏差（论文把它标成实现关键点）。
- 多指令组合的顺序与索引更新：多次 splice 需要左到右组合并维护 span 边界与 $\Delta$ 的累计，否则后续 rotation 会对错 slot。
7.3 Tool / environment contract（面向 agent 的接口视角） #
- 工具目录：本质是一个
edit_kv_cache(D)原语（指令为输入、KV splice 为副作用），而不是外部世界的读写 API。 - 可逆性：
amortize修改缓存但语义上可通过 re-prefill 回滚；forget直接放弃复用以保证擦除语义。 - 错误呈现：理想实现应把验证失败（logit 偏差、数值漂移、越界 span）变成显式错误，让 agent/serving 进入 fallback，而不是静默继续生成。
- 环境假设：依赖缓存可复现重放与确定性设置（如 greedy / 固定随机性）来做可证伪验证；真实部署下需额外的观测与 guardrail。
7.4 LLM backbone 要求与敏感性 #
- 结构前提：本文的闭式旋转修正依赖 MLA 的分解；对 GQA/MHA 虽可讨论代数迁移，但实证上敏感性更高且需要额外 recompute/边界策略（论文在泛化段落中明确点出）。
- 模型敏感性：即便在 MLA 家族内，多编辑正确率也强烈依赖具体模型与数值路径（Table 7/6）；因此生产落地必须把“验证 + 回退”视为设计的一部分。
- 成本形态：节省来自“避免全量 re-prefill”，其收益大小随任务轨迹长度、编辑频度、缓存命中率与并发瓶颈而变；可用粗略式子估算：$\text{cost/task} \approx \text{prefill tokens saved} \times \text{price/token} - \text{splice+rotate overhead}$。