LLM agent TTFT tripled: a timestamp in the system prompt broke prefix caching

Our internal support agent runs on a self-hosted vLLM deployment. On a Tuesday, p50 time to first token (TTFT) for agent steps went from about 0.5 s to 1.6 s and p95 from 1.1 s to 4.2 s, right after a release. Nothing in that release touched the model, the GPUs or vLLM. GPU utilisation went up, not down, and queue depth on the vLLM side grew during business hours.

The vLLM periodic stats log told us where to look:

INFO [loggers.py] Engine 000: Avg prompt throughput: 41210.6 tokens/s, Avg generation throughput: 1203.4 tokens/s, Running: 38 reqs, Waiting: 11 reqs, GPU KV cache usage: 71.2%, Prefix cache hit rate: 2.1%

The same line from the previous week showed a prefix cache hit rate of 85 to 88% and prompt throughput around 6,000 tokens/s. We were now computing roughly seven times as many prompt tokens for the same traffic.

Reproducing it

We captured two consecutive requests for one conversation from the agent service and replayed them against a staging vLLM instance with the cache cleared:

curl -s localhost:8000/reset_prefix_cache -X POST   # dev-only endpoint, enabled in staging
python replay.py step1.json step2.json

Step two should have reused the cached prefix of step one (same system prompt, same tools, same conversation plus one new turn). Its TTFT was the same as a cold request.

What we ruled out

• Cache too small. KV cache usage at 71% leaves room; eviction would show high usage and a gradual decline, not an instant drop to 2%.
• Prefix caching disabled. The flag was unchanged and the startup log still reported prefix caching enabled. A synthetic test with two identical prompts hit the cache.
• Routing. We run four replicas behind a router with session affinity. Pinning a conversation to one replica did not help.

Root cause

We diffed the fully rendered prompts (after the chat template) for two consecutive steps. They differed in the first 40 tokens. The release had added a line to the top of the system prompt so the model knew the current time:

Current time: 2026-04-14T09:31:07Z
You are the support assistant for ...

The timestamp changes every second, so every request had a different first block. Prefix caching only reuses the cache for an identical prefix from the very first token, so one changing line at the top invalidated the 7,000 tokens of instructions and tool schemas below it.

A second, smaller cause appeared in the same diff: the tool definitions were built from a Python set, and their order differed between worker processes. That had been costing us some hits for months, hidden under the high overall hit rate.

What is happening under the hood

vLLM splits each prompt into fixed-size blocks of tokens (16 tokens by default). For prefix caching, every full block gets a hash computed from its own tokens and the hash of the block before it. Two prompts share cached block N only if blocks 0 to N are identical. That chaining is what makes reuse safe: the keys and values for a token depend on every token before it, so a cached block is only valid after an identical history.

The consequence is strict: a change in block 0 changes every hash after it. Moving a dynamic value from the top of the prompt to the bottom turns a full miss into a near-full hit.

SGLang's RadixAttention uses a radix tree instead of chained hashes, but the rule is the same: reuse covers the longest shared prefix. Hosted APIs with prompt caching follow the same principle and document it as "static content first".

Environment

Minimal reproduction

# repro_prefix.py: run against a vLLM server with prefix caching enabled
import time
from datetime import datetime, timezone

from openai import OpenAI

client = OpenAI(base_url="http://localhost:8000/v1", api_key="sk_test_xxx")
STATIC = "You are a support assistant. " + ("Policy text. " * 1500)


def ttft(system: str) -> float:
    start = time.perf_counter()
    stream = client.chat.completions.create(
        model="Qwen/Qwen2.5-32B-Instruct-AWQ",
        messages=[{"role": "system", "content": system},
                  {"role": "user", "content": "Where is my order?"}],
        max_tokens=16, stream=True,
    )
    for _ in stream:
        return time.perf_counter() - start


def now() -> str:
    return datetime.now(timezone.utc).isoformat(timespec="seconds")


for label, build in [
    ("time first", lambda: f"Current time: {now()}\n{STATIC}"),
    ("time last ", lambda: f"{STATIC}\nCurrent time: {now()}"),
]:
    ttft(build())            # warm the cache
    time.sleep(1.1)          # make sure the timestamp changes
    print(label, round(ttft(build()), 3))

On our staging GPU the output was:

time first 0.912
time last  0.081

Who is affected

Any self-hosted vLLM or SGLang deployment, and any hosted API with prompt caching, where request-specific content (timestamps, request IDs, user names, retrieved documents, A/B flags) appears before long static content. Agents and multi-turn chat are hit hardest because their prompts are long and almost entirely shared between steps.