Every time an agent picks up a new request, it may be re-memorizing tool documentation it has already seen thousands of times. A paper submitted to arXiv on August 20, titled ReCache, points out that tool and skill schemas recur across requests in different combinations and orders, while standard prefix caching only hits when prefixes match exactly — making the mechanism nearly useless for agents.

Why Prefix Caching Fails for Agents

Traditional prefix caching has strict reuse conditions: KV states can only be reused when two contexts are token-for-token identical from the start. But agents actually run differently — the same set of tools gets assembled into the prompt as A, B, C this time, C, A, B next time, plus two new skills the time after. Once the combination shifts, the prefix breaks, the cache is invalidated, and the model re-encodes every schema from scratch. The paper frames this as pure redundant computation: the same tool description may be encoded countless times across a serving cluster.

The Approach: Composition-Invariant KV Blocks

ReCache's core idea is to cache each resource (schema) as an independent unit rather than as an appendage of a whole prompt. It lands in three layers:

  • Resource-wise attention: removes cross-resource interactions and assigns resource-local positions, so a resource's KV block stays identical no matter which combination or order it appears in — the paper calls this composition invariance. This is the precondition that makes independent caching possible.
  • Contribution-selected routing: restricts a resource's visibility to contribution-selected layer–KV-head-group routes. Not every layer and every head needs to see every resource.
  • Structural and semantic pruning: retains only invocation-critical fields, trimming redundant parts of tool descriptions at the caching stage.

Results: Three Key Numbers

The paper evaluates on a benchmark assembled from seven public tool- and skill-use datasets, including resource-disjoint tests:

  • Resource-wise attention alone matches dense invocation performance at 82.3% versus 82.4% Inv-F1, while delivering a 3.655x time-to-first-token speedup;
  • The complete framework reduces allocated KV-tensor memory by 92.43%;
  • Attention computation itself accelerates by 1.423x.

In other words, roughly 0.1 percentage points of invocation accuracy trades for massive reductions in memory and latency.

Our Read

The paper's value lies not in any single number but in puncturing an industry assumption: everyone treats caching as a "prefix" problem, but in the agent era resources combine dynamically, so cache granularity must sink to the resource level. It sits in the same lineage as non-prefix KV reuse and KV quantization work in the community, yet the "composition-invariant KV block" design relaxes the reuse condition from "prefix match" to "resource match," which fits real agent invocation patterns. For teams running agent inference services, this is a paper worth reading against your own cache hit rates: if your agent business chronically shows low prefix hit rates, the problem may not be your cache implementation but the caching model itself. Code is open-sourced at github.com/EIT-NLP/ReCache; paper: https://arxiv.org/abs/2608.19662