What are composition-invariant KV blocks?

They are KV cache blocks whose contents do not depend on what else is in the prompt. ReCache produces them for tool and skill schemas by removing cross-resource interactions, so one schema's tokens never attend to another's, and by assigning resource-local positions, so a schema's tokens are numbered from its own start rather than from the start of the prompt. The result is that the same schema encodes to the same block whether it is sent first, fourth, or alongside a completely different set of tools, which is what makes it reusable across an agent's varying tool selections.

Why does ordinary prefix caching fail for agents?

Prefix caching reuses cached keys and values only while two prompts agree token for token from the very first token, because that is the only condition under which the cached state is still correct. An agent decides each turn which tools to load and in what order, so its prompt's leading tokens keep changing arrangement even though the schema text is identical. Engines make this cheaper by hashing in fixed-size blocks rather than whole prompts, but in a scheme like vLLM's each block hash chains the hash of everything before it, so changing one block still invalidates every block after it.

How does ReCache relate to prompt caching in an agent harness?

Prompt caching at the harness level works by keeping the volatile parts of a prompt after the stable parts, so the stable prefix survives across turns, which is a discipline imposed on the agent. ReCache targets the same cost inside the serving engine instead: it changes what a cache block is, so a schema's block stays valid regardless of position, and the agent is free to send any subset in any order. The paper reports that this holds invocation accuracy roughly flat at 82.3% Inv-F1 against 82.4% for dense invocation, while reporting a 3.655-fold time-to-first-token speedup and a 1.423-fold attention acceleration in its own setting.

ReCache reuses tool-schema KV blocks across agent calls — Composition-invariant KV blocks

TL;DR

What is it: The news anchor is ReCache, an arXiv paper on serving tool-augmented agents; the concept it makes concrete is composition-invariant KV blocks — encoding each tool schema into a KV cache block that is identical no matter which other tools it is sent with, or in what order.
Why it’s needed: An agent re-sends the same tool and skill schemas on most calls, and those schemas can take up much of the prompt — so they are the part of the prefill that should not cost twice, but usually does, because prompt caching keys on the exact token sequence and the agent keeps changing it.
vs previous: Ordinary prefix caching reuses work only while the prompt matches token for token from the start, so adding, dropping, or reordering a single tool invalidates every block after the change; ReCache instead removes the cross-schema dependency entirely, so the cache is keyed per schema rather than per prompt.

Jargon

Tool schema: The machine-readable description of one tool — its name, what it does, and every argument it takes. The model needs it in the prompt to call the tool correctly, and it is the same text on every request. See how a schema is built →
KV cache: The keys and values the model computed for tokens it has already read, kept so it does not have to recompute them. Producing them is the expensive part of prefill; loading them back costs far less. Walk the KV cache →
Prefix caching: Reusing the KV cache of a prompt’s leading tokens across requests. It works only while two prompts agree from the very first token, which is why it is described as caching a prefix and not a set. Why hashing the prompt fails →
Composition-invariant: A block whose contents do not change when its neighbours change. ReCache gets this by removing cross-resource interactions — schema A’s tokens never attend to schema B’s — and by giving each schema resource-local positions.
Resource-local positions: Numbering each schema’s tokens from its own start rather than from the start of the prompt. Without this, moving a schema later in the prompt changes its position indices, which changes its keys and values — a different block for identical text.
Resource-wise attention: ReCache’s attention pattern: instead of every token seeing every other token, a schema’s block is visible only through selected layers and selected groups of attention heads — the paper calls these layer and KV-head-group routes. This is what lets the blocks stay independent and still be usable.
Structural and semantic pruning: Two ways ReCache shrinks a schema before caching it: structural pruning drops fields by their place in the schema, semantic pruning drops them by what they mean. What survives is what the paper calls the invocation-critical fields — the parts you actually need to call the tool correctly.
Inv-F1 and dense invocation: Inv-F1 is the paper’s invocation-accuracy score, and dense invocation is the comparison baseline it is reported against — dense meaning without the resource-wise restriction described below. Accuracy has to stay flat against that baseline, because a caching trick that speeds things up by making the model worse at using its tools is not a win.

The news. On August 21, 2026, an arXiv paper introduced ReCache, aimed at tool-augmented LLM agents that re-send the same tool and skill schemas in varying combinations and orders — a pattern that breaks ordinary prefix caching. ReCache removes cross-resource interactions and assigns resource-local positions, producing composition-invariant KV blocks per schema, then limits each schema’s visibility to selected layer and KV-head-group routes, keeping only invocation-critical fields through structural and semantic pruning. It reports 82.3% Inv-F1 against 82.4% for dense invocation, a 3.655× time-to-first-token speedup, and a 92.43% reduction in allocated KV-tensor memory. Read the paper →

Picture a reference library that keeps its material as one thick bound book. Chapter A runs pages 1–4, B runs 5–8, C runs 9–12, and the binding is what makes those numbers true. Now a reader asks for the same three chapters in a different order. Nothing about the content changed — but the moment you rebind with C in the middle, C is pages 5–8 instead of 9–12, and so is everything after it. The book has to be reprinted from the first changed page, even though every word was already on the shelf.

That is an agent's prompt under prefix caching, and the chapters are its tool schemas. A serving engine reuses cached work only while two prompts agree token for token from the very beginning, because that is the only condition under which the cached keys and values are still correct for the tokens that follow. Engines make this cheaper by hashing in fixed-size chunks rather than whole prompts; vLLM's block-hash chain, for one, hashes each block together with the hash of everything before it — and that chain has the same property as the binding: change one block and every hash after it changes too. The step on why full-prompt hashing fails is the same lesson from the other side.

Two prompts, different hashes

Prompt A

Youarehelpful.Alicesaidhi

hash: e93c

Prompt B

Youarehelpful.Bobsaidhi

hash: 8800

CACHE MISS — hashes differ, shared prefix wasted

Both prompts share 3 leading tokens, but one different token anywhere makes the full-prompt hash completely different.

For a chat prompt this is fine, because prompts genuinely do share long prefixes. For an agent it is close to the worst case. The agent's planner decides which tools this turn needs and in what order to list them, and it can decide differently from turn to turn — tool-loading strategy is a live decision, not a fixed header. So the one part of the prompt that never changes in content — the schemas — can arrive in a different arrangement; when it does, the cache treats that arrangement as a brand-new prompt. The schemas are the most cacheable text the agent has and the least cached, purely because of where they land.

Hold two variables fixed and the size of the problem is easy to see (illustrative — this arithmetic is mine, not the paper's). Say the agent has 20 tools registered and each turn loads 6 of them, in whatever order the planner picked. Because the cache key is the ordered token sequence, every distinct ordered selection is a distinct key: 20 × 19 × 18 × 17 × 16 × 15 = 27,907,200 possible prompts. Even ignoring order entirely, there are still 27,907,200 ÷ 720 = 38,760 distinct combinations — and a warm cache is not holding 38,760 prefixes. Now make each schema its own block, keyed on its own, and the cache needs about 20 entries, one per tool, however the planner arranges them. The same workload goes from 27,907,200 keys to 20 — not by caching harder, but by caching a different thing.

ReCache's move is to stop the schemas from depending on each other at all. Two changes do it. First, it removes cross-resource interactions: schema A's tokens are not allowed to attend to schema B's, so nothing in A's keys and values encodes what B was, or whether B was there. Second, it assigns resource-local positions — schema A's tokens are numbered from A's own start rather than from the start of the prompt — so A's block is the same whether A came first or fourth. Together those give a block that is byte-identical across every arrangement it appears in: each pamphlet numbering its own pages, so it prints once and joins any stack.

That independence has to be paid for, because ordinary attention is what would normally let the model relate one schema to another and to the user's request. ReCache pays for it with resource-wise attention: a schema's block is exposed through selected layer and KV-head-group routes rather than to every head at every layer, and structural and semantic pruning keeps only the fields that actually matter for invoking the tool. The reported check on whether that cost too much is the accuracy number: 82.3% Inv-F1 against 82.4% for dense invocation — the comparison run without the resource-wise restriction — so the agent still picks the right tool with the right arguments. The reported serving effects, in the paper's setting, are a 3.655× speedup in time to first token, a 92.43% reduction in allocated KV-tensor memory, and a 1.423× attention acceleration.

Caching an agent’s tool schemas	Ordinary prefix caching	ReCache
What the cache key depends on	the running prefix, token for token from the start	each schema on its own
Position numbering	global — a schema’s indices shift when it moves	resource-local — numbered from the schema’s own start
Reordering two tools	invalidates every block after the change	no effect — blocks are composition-invariant
How schemas see each other	full attention across the whole prompt	selected layer and KV-head-group routes only
Reported effect	baseline: dense invocation, 82.4% Inv-F1	82.3% Inv-F1, 3.655× faster time to first token, 92.43% less allocated KV memory

The reason this reads as a serving result rather than an agent-design one is where it moves the fix. The usual advice when tool schemas blow up your prompt cost is to change the prompt — pin the tool list, sort it, load fewer tools, put the volatile parts last so the stable prefix survives. ReCache leaves the agent free to send whatever subset it wants in whatever order and changes what a cache block is instead, so that order stops being information the cache is sensitive to. Once a schema's encoding no longer depends on its neighbours, "reuse the prefix" turns into "reuse the pieces" — and an agent's tool list is all pieces.

Goes deeper in: LLM Serving → Prefix Caching → Why Full-Prompt Hashing Fails

Related explainers

CacheWeaver — Prefix-cache-aware evidence reordering — the same problem attacked from the other end: reorder the content so it fits the prefix, instead of removing the prefix's order-sensitivity
Claude Opus 4.8 — Cache-preserving mid-task system messages — another way to keep a prompt cache alive across a mid-conversation change
AWS on tool design as context engineering — why tool schemas dominate an agent's prompt in the first place

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based