Leyline: KV Cache Directives for Agentic Inference¶

🕒 Published (v1): 2026-05-31 07:13 UTC · Source: Arxiv · link

Why this paper was selected

KV cache directives for agentic inference; breaks chatbot-only append-only cache assumptions

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Leyline introduces a serving-side primitive for policy-driven KV cache mutation in agentic LLM inference. It exposes a declarative (span, replacement) directive that lets agent policies explicitly splice cached spans in place, correcting positional attention math via a closed-form \(\delta\)-rotation instead of re-prefilling everything downstream. This lifts replay cache-hit rate by +11.2 pp and agentic solve rate by +14.3 pp over baselines.

Problem¶

Modern KV cache management assumes prompts arrive once and the cache grows monotonically (prefix caching, streaming eviction). Agentic LLMs violate this: their policies must actively remove stale tool outputs, replace failed calls, and truncate aged context. No existing primitive supports policy-issued, in-place cache edits. Production agentic harnesses (e.g., Anthropic 2025) fall back to full re-prefill on every context edit, paying the full prefix-recomputation cost that prefix caching was meant to amortize. Kernel-level eviction methods (H2O, SnapKV, StreamingLLM) make autonomous decisions and cannot accept external directives from a policy layer.

Method¶

Leyline defines a 4-tuple directive \(D = (s_\text{start}, s_\text{end}, R, m)\): a token-index span \([s_\text{start}, s_\text{end})\) to replace, a replacement sequence \(R\) (often a short stub), and a semantic mode \(m \in \{\text{AMORTIZE}, \text{FORGET}\}\).

AMORTIZE mode applies the edit in place via a \(\delta\)-rotation. Under MLA, cached \(K\) splits into position-free \(K_\text{nope}\) and position-encoded \(K_\text{pe}\). After splicing, every downstream token at original position \(i \geq s_\text{end}\) shifts by \(\Delta = |R| - (s_\text{end} - s_\text{start})\). The RoPE closure \(R(a)R(b) = R(a+b)\) lets the kernel correct this in one matmul per slot:

\[K_\text{pe}^\text{new}[i] = R(\Delta) \cdot K_\text{pe}[i]\]

\(K_\text{nope}\) and \(V\) of downstream slots are left untouched (their attention to the original chunk content is what the policy wants to preserve). The radix prefix \([0, s_\text{start})\) is unaffected, surviving the edit for future cache hits.

FORGET mode routes to standard prefix-trimmed re-prefill for true content erasure (redaction, retention-mandated deletion), adding no new kernel work but providing the policy with declared-intent semantics.

The serving-stack integration is a ~200-LOC SGLang RadixCache patch. A thin Python Policy.transform(messages, turn_idx) → messages interface accepts any span-emitting policy (turn-counter, content-matcher, learned detector, etc.) and diffs turns to emit directives. Multiple non-overlapping directives per turn compose algebraically: \(R(\Delta_1)R(\Delta_2) = R(\Delta_1 + \Delta_2)\), \(\Delta\) of either sign.

Key Contributions¶

Mutation vs. reuse distinction: precisely separates the two agentic KV cache sub-problems, locating prior work (Irminsul/Ma et al. 2026) on reuse and identifying mutation as the open sub-problem.
Directive abstraction: the 4-tuple (span, replacement, mode) contract decouples what to edit (policy) from how to splice it (kernel), making the primitive signal-agnostic across policy families.
Semantic-edit channel: a new serving-stack interface layer sitting above block-level KV storage; decomposes span-level agent intent into block-level operations schedulable by storage backends (e.g., LMCache).
Two-leg empirical validation: mechanism benchmarks on live SGLang scheduler; policy benchmarks on debug-gym agentic tasks, validated independently then read jointly.

Results¶

Cache-hit rate: splice arm lifts replay cache-hit by +11.2 pp over the standard radix baseline, uniform across concurrencies \(C \in \{1, 4, 8, 16\}\); validated on DeepSeek-V2-Lite and JoyAI-LLM Flash at \(\approx 17\text{K}\)-token prompts.
Latency: end-to-end latency reduction peaks at −241 ms at \(C=8\) (where prefill contention is on the critical path).
Agentic solve rate: ten-line truncation policy via directive lifts solve rate by +14.3 pp over a no-truncation baseline on debug-gym mini_nightmare (8 tasks × 4 seeds × 2 policies) on JoyAI-LLM Flash.
Correctness (single-prompt microbenchmark): Leyline predicts '34' (tracking full-context reference); re-prefill predicts '0' (loses the calculation); confirms the contract that AMORTIZE tracks the full-context cache, not re-prefill.
Correctness (50-step trajectories): 48/50 first-token matches against full-prefill reference; 2 mismatches on prompts with top-1/top-2 logit gap below bf16 noise floor, with no directional bias.
Cross-architecture: 12-step counter-trajectory replay across four MLA models (DSv2-Lite, JoyAI-LLM Flash, GLM-4.7-Flash, Moonlight-16B-A3B); kernel never changes tool selection (15/15 tool-name matches reported).

Limitations¶

MLA-only kernel: the \(\delta\)-rotation mechanism is specific to MLA's \(K_\text{pe}/K_\text{nope}\) split; GQA extension requires a boundary-recomputation pass (analogous to CacheBlend/EPIC) and is only sketched, not implemented.
AMORTIZE semantics are weaker than re-prefill: downstream \(K_\text{nope}\) and \(V\) retain attention influence from the evicted chunk content, which is by design but means the cache state is not equivalent to having re-prefilled the substituted prompt—a subtle trap for policies that expect true forgetting.
Policy evaluation is narrow: the +14.3 pp result is from a single benchmark (debug-gym mini_nightmare), a ten-line rule, and two policy variants; generalization to other agentic benchmarks is not demonstrated.
bf16 precision floor: bit-faithfulness only holds above the bf16 logit-margin noise floor; fp32 rotation mitigates the rotation contribution but not the KV storage contribution.
vLLM integration not implemented: the serving integration targets SGLang only; the paper notes four open vLLM RFCs requesting similar primitives but does not provide a vLLM path.

Relevance to Harnesses / Meta-Harnesses¶

Leyline directly targets the serving-side gap that agentic harnesses expose: today, any harness that edits its message list (clearing failed tool calls, truncating stale outputs, summarizing aged context) forces a full re-prefill, erasing the cache amortization that makes multi-turn agents tractable at scale. Leyline provides a primitive that harness engineers can call declaratively—the Policy.transform interface is explicitly designed to plug into a harness's turn-management loop with ten lines of code. The AMORTIZE/FORGET mode distinction gives harness authors control over the semantic guarantee they need (efficient amortization vs. true erasure), which maps directly onto common harness operations like context compression vs. privacy-mandated redaction. The paper's framing of the directive layer as the missing interface boundary between agent intent and KV storage positions it as infrastructure that harness meta-layers should sit above, composing with storage backends like LMCache below.