PACE: Keeping the Right Tokens in the KV Cache Is Not Enough for Long-Horizon LLM Agents

📌 Highlights

PACE reframes long-context KV management around a distinction between residency and retrievability. The paper's central observation is that an agent can retain nearly all tokens needed for a later step while still applying their definitions incorrectly when the rotary distance between those definitions and the current query becomes large. In the Qwen3-8B distance sweep, retention-only accuracy falls from 93% at a 2K logical gap to 64% at a 90K gap even though needed-token residency remains approximately 0.996.

The proposed engine addresses both sides of the problem. A planner identifies future dependencies and supplies a foresight signal for retention; bounded positions then renumber the retained tokens and exactly re-rotate their keys so the model sees a short physical distance. In the pre-registered 100K-token comparison, PACE passes 145 of 150 hidden checks, or 97%, compared with 42% for H2O and 3% for SnapKV in the fresh-session evaluation. Its strongest evidence is the length study: PACE records 99% at 1M tokens and 100% at 2M tokens on one 24 GB GPU.

The main caveat is scope. The benchmark deliberately isolates memory of randomized coding definitions, and most runs use an oracle dependency graph. The paper therefore establishes a compelling mechanism and controlled result for planned workloads, but it does not yet establish universal long-context reliability or production-scale serving throughput.

• Core claim: keeping the right tokens is necessary but not sufficient when rotary distance becomes large.
• Strongest Qwen3-8B result: 97% of hidden checks for PACE versus 42% for H2O at 100K tokens and B = 2,048.
• Scale result: 99% at 1M tokens and 100% at 2M tokens, with 0.3 GB resident KV plus at most 0.3 GB of reference keys.
• Most important uncertainty: performance outside synthetic, planned coding sessions and beyond the tested model and hardware range.

🎯 Introduction

Long-horizon agents do not answer one isolated prompt; they execute sessions in which each turn appends instructions, retrieved material, tool output, or model-generated content. Later steps may depend on definitions established many turns earlier. The paper notes that sessions of 10^5 to 10^6 tokens are routine for repository-scale coding and long tool-use traces, while the KV cache grows linearly with the session. For Qwen3-8B, the stated cost is 144 KiB per token, implying 14.7 GB at 100K tokens and 147 GB at 1M tokens. A 24 GB accelerator therefore requires eviction or offloading.

Prior eviction policies differ in how they select survivors. H2O uses cumulative attention, SnapKV uses current-query attention, and StreamingLLM-style methods preserve sinks plus a recent window. Agent-aware systems can use workflow knowledge to predict future reuse. Yet these approaches share an implicit objective: ensure that a later-needed token remains cached. PACE argues that this objective is incomplete because a resident token can be physically far from the current query under rotary embeddings. Its paper-level objective is consequently to control both residency and rotary gap, using planner information for the former and bounded physical positions for the latter.

🔬 Methodology

PACE sits inside the inference engine's KV-cache manager and changes which tokens survive, which physical positions they carry, and how session state persists across turns and memory tiers. The planner sends a blueprint listing earlier message spans and the future steps that will read them. For a span with next reference s⋆, PACE adds a foresight bonus to the cumulative attention score. The reported scale is σ = 10^5, giving a floor of σ/2 = 50K, above the observed unreferenced cumulative-attention maximum of 25K in the 2M-token sessions. Thus planned spans outrank unreferenced tokens, while the soonest-needed span receives the highest priority. After a span's last planned reader runs, its bonus becomes zero.

Bounded positions maintain a physical position p for every resident slot and a shift c for newly written tokens. When a limit L is approached, resident tokens are assigned new positions in logical order, gaps from evicted tokens collapse, and each cached key is re-rotated from its old position p to its new position p′. The paper recommends L > Bmax + H; with B = 2,048 and 4,096-token chunks, L = 8,192 is the smallest admissible power of two. To avoid compounding bf16 rounding error across hundreds of renumbers, PACE stores a first-renumber reference key and derives later positions from that reference in fp32. Persistent sessions append only new messages, and tiered rehydration can restore planned spans from host memory, local storage, or a Valkey-compatible remote cache.

The implementation is a subclass of the H2O cache manager in SparseEngine. PACE and H2O share the prefill schedule, eviction schedule, decode path, persistent-session behavior, and greedy decoding, making the ablations operationally comparable. The method supports full-rotary and split-half RoPE with static frequency scaling, including default, linear, YaRN, and Llama-3-style configurations. The key engineering tradeoff is that PACE changes what the model sees by collapsing gaps between retained tokens, although the paper reports no measurable perplexity cost in its targeted tests.

📊 Experiments

The paper evaluates a custom execution-scored long-horizon coding benchmark rather than a conventional static long-context dataset. Each session begins with three randomized definition steps specifying classes, fields, fee constants, an exception code, status values, and a fee rule. Approximately 2,000-token Python standard-library filler chunks then lengthen the session. Three late probes request fee_for, settle, and a complete module. Hidden unit tests execute the generated code, while a separate recall metric checks whether the answer contains the session's names, values, rounding mode, quantum, and status facts. The no-eviction 8K-token control reaches 100% on Qwen3-8B, supporting the interpretation that long-session failures arise from cache behavior. The primary model is Qwen3-8B; Mistral-7B-Instruct-v0.3 provides a second-model analysis. All runs use one NVIDIA L4 GPU with 24 GB and 128 GiB of host memory.

The headline Qwen3-8B comparison uses 100K-token sessions, a 2,048-token budget, ten fresh sessions, and three probes per session. PACE passes 145/150 checks, fully passes 28/30 probes, recalls all 250 session facts, and beats H2O on 22 paired probes with none worse. In the five-session replication with non-repeating, non-topic filler, PACE reaches 75/75 checks while H2O reaches 33/75. The 2 × 2 ablation shows that positions-only and retention-only each reach 94/150 checks, or 63%, while PACE reaches 97%; PACE beats each component with p < 10^-4 in the reported paired comparisons. SnapKV reaches 2/75 checks, or 3%, in the additional fresh-session comparison.

The distance sweep fixes the 100K session length and moves definitions from 2K to 90K tokens before the probes. Retention-only reaches 93% at 2K but 64% at 90K despite 0.992–0.996 residency, while PACE with L = 8K remains between 97% and 100%. The pooled rotary-gap analysis reports 96–100% below 8K, 87% at 8–16K, and 69–77% beyond 16K at residency 0.995–0.996. With an LLM planner whose dependency-edge recall is 0.9, PACE reaches 92% against H2O's 41% under the earlier L = 40K setting.

The quality-at-length study reports 100% at 300K, 99% at 1M, and 100% at 2M for PACE. At 1M, PACE passes 74/75 checks and recalls 125/125 facts; positions-only reaches 33% and 74% recall. At 2M, PACE passes 75/75 while positions-only falls to 13% and 50% recall. The full cache would require about 147 GB at 1M and 295 GB at 2M, whereas the resident KV state remains about 0.3 GB plus at most 0.3 GB of reference keys. PACE adds 9% wall time in the 100K comparison, taking 1,047 seconds versus H2O's 963 seconds.

Figure 2

Caption: Figure 2: PACE inside the engine’s KV-cache manager. The planner’s dependency graph becomes a per-span foresight bonus that decides which tokens stay; bounded positions renumber the kept tokens so their rotary distance to the query stays below L; persistent sessions carry the cache across steps; evicted context is tiered and restored when the plan needs it.

Why It Matters: This is the clearest system-level view of how planning, bounded positions, persistence, and multi-tier restoration fit together inside the serving engine.

Figure 1

Caption: Figure 1: Keeping the right tokens is not enough. 100K-token coding sessions, Qwen3-8B, KV budget 2,048 tokens. Planner-guided retention keeps 99.6% of the tokens each late step needs, yet its accuracy falls as those tokens recede; H2O loses them outright. PACE adds bounded positions, holding the rotary distance to the query below 8K, and stays at 97–100%. Five randomized sessions per point, three probes each.

Why It Matters: It directly visualizes the paper's central claim: retention-only accuracy degrades with logical distance even when needed tokens remain resident, whereas PACE remains stable.

Figure 3

Caption: Figure 3: Accuracy tracks rotary distance at full residency. All 225 probes of the three PACE-family arms in the Qwen3-8B distance sweep, binned by the reconstructed distance from the query to the definitions. Bars: checks passed. Residency of the needed tokens is 0.995–0.996 in every bin. Probes per bin, left to right: 47, 58, 30, 38, 22, 15, 15. No probe fell in 32–40K.

Why It Matters: The figure isolates rotary distance as a predictor of successful use under nearly constant residency, supporting the proposed mechanism beyond a single configuration.

🔮 Conclusion

PACE's conclusion is that a retained token is not necessarily a usable token in a long-horizon agent session. Under a fixed 2,048-token budget, planner-guided retention preserves the needed definitions but leaves them increasingly distant in rotary-position space. PACE addresses this by retaining planned dependencies and periodically renumbering resident keys so their physical distance remains bounded.

The strongest evidence is internally consistent: Qwen3-8B rises from 42% for H2O to 97% for PACE at 100K tokens, then maintains 99% and 100% at 1M and 2M tokens. The paper also reports a 9% wall-time increase and no measurable perplexity cost in its tested settings. These results support the residency-gap diagnosis and the usefulness of combining planning with position control, while remaining conditional on the benchmark, model, planner, and serving configuration.

🛠️ Future Research Improvements

The most important next experiment is workload expansion. The current benchmark intentionally makes early-definition recall the path to a correct answer, so evaluations should add real repositories, tool traces, multi-document research, multi-agent hand-offs, and open-ended conversation where future dependencies are incomplete or unknown. These settings can test whether bounded positions help when the planner is uncertain and whether planned retention harms arbitrary historical recall.

Planner robustness also needs a systematic study. The reported LLM planner has edge recall of 0.9 in the tested sessions, but the paper does not map performance as missed, stale, contradictory, or dynamically introduced dependencies accumulate. A useful extension would compare oracle, static LLM, online learned, and retrieval-triggered planners while measuring both fact recall and execution success.

Finally, the fixed 50K bonus floor should be replaced or stress-tested with adaptive scaling as sessions approach and exceed the estimated 5M-token regime. Future systems should isolate the source of the 2M-token per-turn slowdown, evaluate concurrent sessions and absolute throughput, and test larger models whose coding ability may use distant context differently.

🏭 Potential Industry Use Scenarios

PACE is most naturally suited to production agents with explicit workflow structure. Repository-scale coding assistants can use dependency graphs to preserve early API definitions, data models, and business rules while unrelated files and tool outputs fill the session. Tool-use agents and data pipelines can similarly mark the outputs that later stages will consume, allowing a fixed GPU working set while older state remains in host or remote tiers.

Multi-agent hand-offs are another plausible use case: a planner can identify which prior messages a downstream specialist will need, and the cache can preserve those spans while collapsing irrelevant gaps. Persistent sessions also reduce repeated prefill work because each turn sends only new messages. These scenarios require careful validation, however. Open-ended chat, arbitrary historical questions, concurrent traffic, and workflows with unreliable plans may need retrieval or full-context serving rather than PACE's dependency-driven working set.

Operational adoption should therefore begin with workloads where dependencies are explicit, hidden-test or task-success metrics are available, and planner mistakes can trigger measured rehydration. The reported remote restore time of about 2.7 seconds versus 2.3 milliseconds from host memory also makes tier placement a product and latency decision, not merely a memory-saving implementation detail.

💬 Critical Analysis

The paper's strongest methodological feature is the separation of memory from use. The distance sweep holds needed-token residency near 0.992–0.996 across PACE-family arms while varying the rotary gap, and Figure 3 shows pass rates falling as that gap grows. The ablation also supports a complementary mechanism: positions-only keeps context close but often evicts the required details, while retention-only keeps details but can leave them 30–80K positions away. The pre-registered fresh-task comparison, paired sessions, hidden tests, fact-recall metric, and no-eviction control make the central Qwen3-8B result substantially more informative than a single long-context accuracy number.

The evidence is nevertheless narrower than the headline numbers suggest. The benchmark is synthetic coding with controlled filler, only two 7–8B models are tested, and the strongest test-pass separation appears on Qwen3-8B rather than Mistral, whose no-eviction ceiling is about 40%. Most evaluations use an oracle plan, while the one LLM-planner study has limited scope. The paper also reports no concurrent serving evaluation, no full-context 100K reference, and no isolation of the per-turn slowdown observed at 2M tokens. Exact re-rotation is theoretically well motivated and empirically checked, but gap collapse changes the model's temporal geometry; tasks that depend on elapsed distance or chronology could behave differently. PACE is therefore a persuasive systems hypothesis with strong controlled evidence, not yet a general replacement for retrieval, full context, or adaptive memory across all agent workloads.