Technical Summary: Leyline: KV Cache Directives for Agentic Inference

1. Problem Statement

Modern Large Language Model (LLM) serving systems have evolved around a specific workload assumption: prompts arrive once, and the KV cache grows monotonically (append-only). This assumption underpins optimizations like prefix caching and forward-only eviction. However, Agentic LLMs (Yao et al., 2023; Yang et al., 2024) break this monotonicity through policy-driven editing. Agents frequently modify conversation history by retrying failed tool calls, dropping stale outputs, or pivoting trajectories.

This behavior creates two distinct cache management problems:

1. Position-Invariant Reuse: Identical content shifts to new absolute positions between turns (e.g., due to inserted tool outputs). Exact-prefix caching fails to reuse these chunks because their positions have changed, even though the underlying Key-Value (KV) data remains valid. Recent work (Ma et al., 2026) addresses this via content-addressed matching.
2. Policy-Driven Mutation (The Focus of this Paper): An agent or policy may need to actively remove or replace a span of cached content (e.g., truncating old tool outputs to free memory) and continue generation without re-prefilling the entire subsequent context.
   • Current State: Production systems (e.g., Anthropic, 2025) handle this by editing the message list and triggering a full re-prefill, incurring the full cost of recomputing the prefix that the edit intended to save.
   • Kernel Limitations: Existing kernel-level eviction methods (Zhang et al., 2023; Li et al., 2024; Xiao et al., 2024) make autonomous decisions and cannot accept explicit directives from an external policy to perform specific in-place edits.

There is no existing primitive that allows a policy to direct the serving system to actively splice the KV cache while preserving the correctness of downstream attention math without re-prefilling.

2. Methodology: The Leyline Primitive

The authors introduce Leyline, a serving-side primitive designed to close the gap between policy intent and kernel execution.

2.1 The Directive Abstraction

Leyline decouples what to edit from how to edit it via a declarative 4-tuple directive:
$$D = (s_{start}, s_{end}, R, m)$$

• $(s_{start}, s_{end})$: The token-index range of the span to be replaced.
• $R$: The replacement token sequence (often a short stub, e.g., [evicted: 3 older tool turns]).
• $m$: The semantic mode, chosen from:
  • AMORTIZE: The default mode. The system performs an in-place splice. The replacement is inserted, and downstream positions are re-indexed. Crucially, the underlying KV values ($K_{nope}$ and $V$) for downstream tokens are preserved, maintaining the model's attention to the original content that was evicted, rather than the new stub.
  • FORGET: The system routes the edit to a standard prefix-trimmed re-prefill. This is used when true content forgetting is required (e.g., redaction), ensuring the model does not retain influence from the evicted content.

2.2 The Mechanism: $\delta$-Rotation

The core technical innovation enabling the AMORTIZE mode is a closed-form correction for position encoding shifts, specifically for Multi-Head Latent Attention (MLA) architectures (e.g., DeepSeek-V2).

• Structural Insight: In MLA, the Key tensor is split into $K_{nope}$ (position-independent) and $K_{pe}$ (position-dependent, rotated by RoPE).
• The Operation: When a span of length $|S|$ is replaced by a span of length $|R|$, all downstream tokens shift by $\Delta = |R| - |S|$.
• The Correction: Instead of re-computing the attention for downstream tokens, Leyline applies a $\delta$-rotation to the cached $K_{pe}$ values of all downstream slots:
  $$K_{pe}^{new}[i] = R(\Delta) \cdot K_{pe}[i]$$
  Due to the unitary rotation closure of RoPE ($R(a)R(b) = R(a+b)$), applying $R(\Delta)$ to the existing $R(i)$ is algebraically equivalent to having computed $R(i+\Delta)$ from scratch.
• Result: The system updates the position encoding in a single matrix multiplication per slot, preserving the $K_{nope}$ and $V$ tensors. This allows the model to continue generation with the attention math of the original full context, despite the physical cache having been spliced.

2.3 Serving Stack Integration

Leyline integrates into the serving stack (specifically demonstrated with SGLang) via three steps:

1. Radix Match: The unchanged prefix ($[0, s_{start})$) is matched against the radix cache as usual.
2. Prefill: The replacement tokens $R$ are prefilled into new slots.
3. Rotation: The kernel applies the $\delta$-rotation to the $K_{pe}$ band of all downstream slots and re-indexes them.

The interface is signal-agnostic: any policy that can emit a span-replacement tuple (e.g., a truncation rule, a detector for stale tool calls) can drive the cache without the kernel inspecting the rationale.

3. Key Contributions

1. Problem Distinction: The paper formally distinguishes between reuse (position shifts of identical content) and mutation (policy-driven active editing), identifying mutation as the open sub-problem in agentic cache management.
2. Directive Abstraction: A 4-tuple interface that decouples policy (what to edit) from mechanism (how to splice), enabling explicit, in-place cache editing without re-prefill.
3. Semantic-Edit Channel: A new interface boundary for post-agentic serving stacks, sitting above block-level storage to decompose agent edits into block-level operations while preserving position-encoding correctness.
4. Two-Leg Validation:
   • Mechanism Leg: Demonstrates that the splice kernel preserves replay cache-hit rates and reduces latency by avoiding re-prefill.
   • Policy Leg: Demonstrates that a simple truncation policy routed through this interface improves agent solve rates by reducing context noise.

4. Results

4.1 Mechanism Performance (SGLang Microbenchmark)

• Cache Hit Rate: The splice arm lifted the replay cache-hit rate by +11.2 percentage points (pp) over a standard radix baseline across concurrencies $C \in \{1, 4, 8, 16\}$.
• Latency: End-to-end latency was reduced by up to 241 ms (at $C=8$) by saving the re-prefill cost on the critical path.
• Correctness: The splice path maintained 100% first-token argmax agreement with the warm-prefix (full-context) path, confirming that the $\delta$-rotation preserves the attention math of the original context.

4.2 Policy Performance (Debug-Gym)

• Task: 8 debug-gym mini_nightmare tasks using the JoyAI-LLM Flash model.
• Policy: A 10-line truncation rule that drops tool outputs older than $n=2$ turns.
• Outcome: The truncation policy routed through Leyline improved the agentic solve rate from 31.2% (baseline, no truncation) to 45.5% (+14.3 pp).
• Analysis: The gain was driven by tasks with long trajectories (e.g., shopping_cart, sum_tree). By dropping stale tool turns, the model could attend more effectively to the few turns that actually mattered. Without Leyline, exercising this policy would have forced a full re-prefill on every truncation, negating the efficiency gains.

4.3 Correctness Verification

• Single-Prompt Microbenchmark: Constructed scenarios where full-context and re-prefill paths must disagree. Leyline consistently matched the full-context prediction (tracking the original chunk's influence) rather than the re-prefill prediction (which lost the chunk's influence).
• Cross-Architecture: Validated on four MLA models (DeepSeek-V2-Lite, JoyAI-LLM Flash, GLM-4.7-Flash, Moonlight-16B-A3B).
• Numerical Stability: The $\delta$-rotation introduces a small drift (bounded by $\sim 4.7 \times 10^{-3}$ rel-L2 in bf16), which accumulates sub-linearly. The authors note that running the rotation in fp32 (while storing KV in bf16) mitigates this drift effectively.

5. Significance and Claims

The paper claims that Leyline provides the missing interface for policy-driven cache editing in agentic systems.

• Shift in Interface: It moves the serving stack interface boundary. Pre-agentic systems only exposed the prompt; post-agentic systems require a cache-edit channel. Leyline defines this channel concretely.
• Decoupling: It allows policies to declare intent (e.g., "forget this span" or "amortize this edit") without the policy needing to understand the underlying kernel mechanics (RoPE, MLA, radix trees).
• Programmable Memory: The authors argue that this transforms KV cache management from a reactive, system-side guessing game (eviction) into a cooperative scheduling problem where the agent declares context fate, and the storage layer executes.
• Scope: The paper validates the splice verb. It acknowledges that the rotation kernel is currently MLA-specific but notes that the directive abstraction is architecture-agnostic and that extensions to GQA/MHA are feasible via boundary recomputation passes.

The paper concludes that while the mechanism (splice) enables the policy class without re-prefill costs, the policy class itself delivers the deployment-level win (higher solve rates). The vocabulary of the directive interface (including future verbs like PIN, DECAY, SCRATCH) represents the agenda for future agentic memory management.