Your MCP Tool List Reshuffles and Kills the Prompt Cache

A team I was helping had an agent wired to three MCP servers, maybe forty tools in total, and a cache hit rate that looked fine in the staging harness and then fell off a cliff in production. Same model, same system prompt, same kind of task. The only thing that changed between the two environments was that production pointed the agent at the real tool servers instead of a local stub, and the real servers were under load.

The bill told the story before the traces did. Input tokens per step were two to three times what the staging numbers predicted. When we finally logged the serialized request body and diffed two consecutive steps that should have shared almost everything, the system prompt was identical, the history was identical, and the tool block at the top was a different order every time. One server was returning its tools in whatever order its internal map happened to iterate that request, and that map was not stable under concurrency.

That reorder, by itself, was enough to turn off caching for the entire rest of the prompt.

Where the tool list sits in the request

Prompt caching is a prefix match. The provider hashes the front of your request and reuses the computed attention state up to the point where this request stops matching the last one. Anthropic's documentation is blunt about the granularity: a cache hit requires one hundred percent identical segments up to the cached block. OpenAI says the same thing in different words, that cache reuse requires the entire rendered prefix to match.

The part that catches people is the order in which the request is assembled. The prefix is built as tools, then system, then messages, and each level builds on the one before it. Tools are not somewhere in the middle of your prompt that you can ignore. They are the very first thing the provider sees. Anthropic's own invalidation table lists tool definitions as invalidating the tools, system, and messages caches all at once, because a change at the first level moves the boundary for everything downstream. The exact wording is that modifying tool definitions invalidates the entire cache.

So the tool list is the single most leveraged block in the whole request. It is small relative to a long history, but it sits in front of everything, and the cost of getting it wrong is not the size of the tool block. It is the size of everything after it that now has to be reprocessed. This is the same economics as the broader problem of paying full input price and full prefill latency on every agent step, except here the trigger is a block most people never think to hold still.

Why an MCP tool list is the least stable part of your prefix

A hand-written tool array in your own code is stable by default. You declare the tools in a list, the list is in source control, and it serializes the same way every time. MCP breaks that assumption in three ways.

First, the list is assembled at runtime. The client calls tools/list on each connected server, merges the responses, and only then builds the request. The order of the merged list depends on the order the servers answered in, which depends on network timing.

Second, each server decides its own order. Many implementations build the response from a dictionary or a map, and plenty of languages make no ordering guarantee for those. The server is free to hand you the same tools in a different sequence on the next call, and nothing in the older protocol said it should not.

Third, the client often refetches. If the client calls tools/list at the start of every turn to stay current, and any server's order is unstable, then every turn gets a freshly shuffled tool block. The agent that resends the same enormous prompt on every step is now resending a prompt whose first block is different every step, which is the worst possible place for instability to live. The same byte-for-byte discipline that keeps prefix caching alive applies here, and the tool list is the part MCP makes hardest to hold still.

The spec finally admits the problem

The 2026-07-28 MCP revision, the same spec that made MCP servers stateless, added two small changes that exist entirely to protect the cache.

The first is a recommendation that servers SHOULD return tools from tools/list in a deterministic order, with the stated reason being to enable client-side caching and improve LLM prompt cache hit rates. That is the spec naming the exact failure in this essay.

The second is a new CacheableResult shape on the list endpoints. Results from tools/list now carry ttlMs, a freshness hint in milliseconds, and cacheScope, which is public or private. The point is to let the client cache the list and stop polling, so there are fewer opportunities for a refetch to hand back a different order. These complement the existing listChanged notification, which tells the client when the list actually changed and a refetch is warranted.

Both are worth reading as a pair. Deterministic order makes a given list serialize identically. The cache hint makes the client stop asking for the list so often. One holds the bytes still, the other reduces how often you touch them.

Pin a stable ordering on the server

If you own the server, sorting is a one-line habit with an outsized payoff. Do not return tools in insertion or map order. Sort by a stable key, usually the tool name, right before you serialize the response. Attach the cache hint while you are there.

# MCP server: return tools in a deterministic order and tell the client
# how long it may trust the list. The sort key never changes between calls.
def handle_tools_list(registry) -> dict:
    tools = sorted(registry.all_tools(), key=lambda t: t.name)
    return {
        "tools": [t.to_schema() for t in tools],
        # CacheableResult fields from the 2026-07-28 spec.
        "ttlMs": 300_000,        # client may reuse this list for five minutes
        "cacheScope": "private", # per-session, no shared intermediary caching
    }

Sorting by name is the simplest stable key, but the rule is only that the key is total and does not depend on request timing. If you expose tools in a deliberate order for the model's benefit, store that order as an explicit integer on each tool and sort on it. What you must not do is let the order fall out of a data structure that reorders itself.

The ttlMs is a promise about how often the list can change. Set it to how long you are comfortable with a client holding a stale view before listChanged corrects it. Five minutes is a reasonable default for a tool set that only changes on deploy. Use cacheScope: "private" when the list depends on who is asking, which it usually does once per-tenant tool filtering is in play.

Cache the list on the client and stop refetching

The client side is where most of the churn actually happens, because the client is what builds the request the provider caches. The job is to fetch the list once, keep it until ttlMs expires or a listChanged notification arrives, and sort defensively in case an upstream server ignored the SHOULD.

# MCP client: cache the merged tool list, sort it defensively, and only
# rebuild when the ttl expires or the server says the list changed.
class ToolListCache:
    def __init__(self, client, default_ttl_ms=60_000):
        self.client, self.default_ttl_ms = client, default_ttl_ms
        self._tools, self._expires_at = None, 0.0

    def get(self, now_ms) -> list:
        if self._tools is not None and now_ms < self._expires_at:
            return self._tools
        result = self.client.call("tools/list")
        ttl = result.get("ttlMs", self.default_ttl_ms)
        # Sort even if the server already did: a SHOULD is not a guarantee.
        self._tools = sorted(result["tools"], key=lambda t: t["name"])
        self._expires_at = now_ms + ttl
        return self._tools

    def invalidate(self):  # call this on a listChanged notification
        self._tools, self._expires_at = None, 0.0

Two details matter here. The defensive sort is not redundant. The spec says SHOULD, so a server you do not control may still hand you an unstable order, and sorting on the client is your only guarantee once you merge lists from several servers. And the cache must be invalidated on listChanged rather than on a timer alone, or you will keep calling a tool that no longer exists. The point is not to never refetch. It is to refetch only when the list genuinely changed, so the tool block stays identical across the many steps where nothing changed.

Caching the list is a different problem from caching the result of a tool call, where the hard part is knowing when a cached answer has gone stale. Here the list rarely changes and the server tells you when it does, so the caching is simple and the win is large.

The parts that bite

A stable order fixes the most common cause, not every cause, and a few related traps will undo the win if you stop here.

Per-tenant tool sets fragment the cache. If each customer sees a different subset of tools, each subset is its own prefix with its own cache entry, and a tenant who sends one request an hour never warms anything. That is sometimes unavoidable for isolation, but if the differences are cosmetic, a shared superset of tools with authorization enforced at call time keeps one warm prefix for everyone. Decide this deliberately rather than discovering it in the bill.

A mid-run model switch resets everything. Caches are scoped per model, so the moment a router moves a conversation to a different model, the warm prefix is gone and the next step pays full freight, which is a real cost of routing across models and provider failover that has to be weighed against the reason you switched. The stable tool order does not help across that boundary, it only helps within one model's cache.

Schema churn is the quiet one. If your tool schemas are generated, and the generator emits fields in a different order, or flips a default, or re-serializes a nested object differently between versions, the tool block changes even though the tools are conceptually the same. This matters doubly because constrained decoding reads the exact tool schema to shape the model's output, so an unstable schema is both a cache problem and a correctness surface. Freeze the serialization, not just the set of tools.

Large tool sets amplify all of this. When an agent carries hundreds of tools, the tool block is a big fraction of the prefix, the probability that something in it is unstable goes up, and the reprocessing cost when it breaks is highest. If you are in that regime, retrieving a small stable subset of tools per task is both a context and a caching decision, and the two reinforce each other.

Finally, measure before you believe any of this worked. Log cache_read_input_tokens across consecutive steps of a real run. If it is zero when it should be high, something in the prefix is still moving, and the tool block is the first place to diff.

The takeaway

The tool list feels like configuration, so it gets treated as an afterthought, and in an MCP setup it is the least stable block in a place where instability is most expensive. It renders first, so a reshuffle moves the cache boundary for the entire request, and MCP assembles that block at runtime from servers that historically felt free to reorder it. The 2026-07-28 spec finally gave you two levers for this, a deterministic order and a cache hint, and both are cheap to adopt on either side of the connection.

Sort the list, cache it with the ttl the server gives you, invalidate on listChanged, and freeze how your schemas serialize. Then watch the cache-read number across steps and confirm the prefix is actually holding. If your agent runs on MCP tools and your cache hit rate is quieter than it should be, this block is usually where the leak is, and I am happy to look at a request trace with you and point at the byte that moves. You can reach me here if that would help.