How I Got 53% Input Token Reuse on an LLM Gateway

At Colate I built the gateway that sits between our products and the model providers. It speaks the OpenAI, Anthropic and Gemini formats over one shared request representation, so a caller picks a model and the translation happens underneath.

Once traffic grew, the dominant cost was not the tokens we generated. It was the tokens we sent in, over and over, on prompts that barely changed between calls.

Where the waste is

An agent request is mostly preamble. System instructions, tool schemas, retrieved context, conversation history: all of it resent on every turn, all of it billed every time. The genuinely new part of turn twenty is the user's latest message, a rounding error against everything above it.

Providers expose prefix caching for exactly this, but you only benefit if your prompts are byte identical from the front. That sounds trivial. It is not, and the reasons it fails are boring:

• Tool schemas serialised with non deterministic key order.
• A timestamp or request id injected near the top of the system prompt.
• Retrieved context concatenated in whatever order the vector store returned it.
• Whitespace differences from template rendering.

Any one of these moves a byte near the start and the entire prefix misses.

Making prompts stable

The fix was to treat the prompt as a structured artifact rather than a string, and to give it a deliberate layout: the most stable content first, the most volatile last.

Concretely:

1. Canonical serialisation. Tool schemas and any structured block get sorted keys and fixed formatting, so the same logical schema always produces the same bytes.
2. Volatile fields moved to the tail. Timestamps, request ids and anything per call sits after the stable preamble, never inside it.
3. Deterministic context ordering. Retrieved chunks are sorted by a stable key rather than by retrieval order, so the same result set renders identically.
4. One renderer. Every caller goes through the same prompt builder, because two code paths producing "the same" prompt will eventually disagree by a space.

That is essentially the whole technique. It is unglamorous, and it moved input token reuse to 53 percent across 6.05 billion cached input tokens, with 35 percent lower inference latency because a cached prefix does not need reprocessing.

The bug that mattered

The first invalidation scheme keyed on the prompt content. That is correct for the prompt and wrong for everything else, because two requests with identical prompts are not necessarily interchangeable: different model versions and different sampling parameters produce different outputs from the same input.

For a short window, a cache hit could return a response generated under settings the caller had not asked for. It surfaced as a handful of responses that were subtly not what the caller configured, which is the worst kind of bug because nothing errors.

The fix was to make the key describe the entire determinant of the output: prompt bytes, model identifier, model version, sampling parameters, and tool definitions. If any of those differ, it is a different request.

The rule I took away: a cache key must cover everything that can change the answer. Leave one thing out and the cache stops being an optimisation and starts being a correctness bug that only appears under load.

What generalises

Caching an LLM gateway is not really a caching problem. It is a determinism problem. The cache is easy once identical requests actually produce identical bytes, and almost all the engineering is in removing the small accidental sources of variation that nobody put there on purpose.