Skip to main content

i built a profiler to figure out why coding agents lose their prefix cache

•18 min read

kv blocks, hash chains, and how your harness might break the cache.

a coding agent sent the model its own reply back, word for word, and the engine still had to process it all over again.

that shouldn't happen. every turn, an agent sends back the system prompt, the task, every file it's read, all your rants, and the model's last reply. the prompt keeps growing while the output stays small, so most of the work the inference engine (vLLM, in my case) does is prefill: chewing through tokens it has already chewed on before.

prefix caching is what's supposed to prevent that. the engine keeps the keys and values it has already computed, and if the next request starts with the same tokens, it skips straight to the new part. an agent is the textbook case for it (it's why i went on about keeping the stable stuff at the top of your prompt in my last post), so almost all of the prompt should come straight from cache.

funnily enough, agents are weirdly good at breaking it. a chat template that renders history slightly differently from how the model generated it, a harness that rewrites every tool call with a random id, sessions crowding into one cache until eviction kicks in. and when it breaks, the engine only tells you how much was lost (one number, cached_tokens), not why. if a 6,000-token prompt comes back with 4,000 cached, that number won't tell you whether the other 2,000 were new content, a changed prompt, or evicted blocks.

i wanted to know what i'd have to record to tell the difference. so i built a lil profiler, cachino: a go proxy that sits between a coding agent and the vLLM server i control and saves every request byte for byte, plus some python that predicts what the cache should reuse for each request. i checked each prediction against what the engine actually reported. across nine concurrent runs, assuming every matching prefix was still cached put the predictions off by 8,320 tokens in total. modeling which blocks were still in memory brought that down to 352.

this post is all about that: i'll go over how prefix caching works, what decides whether a token gets reused, and where coding agents break it. the four missing tokens behind that reply turned out to be the small problem. the bigger one, once sessions shared a cache, was eviction.

setup. i don't have a GPU. almost everything here ran on my mac's CPU: vLLM built from source at one pinned commit, two small models (Qwen3-0.6B and 1.7B), two open source harnesses (mini-swe-agent and smolagents), and one bug fix task. that's fine here, since which tokens get reused is pure bookkeeping, not speed. the one thing a CPU couldn't tell was how much time a cache miss costs and for that i borrowed a Tesla T4 from kaggle. the exact numbers depend on this setup, but we're focusing on the mechanisms, which apply everywhere. experiment setup

vLLM server startup banner, running Qwen3-0.6B with block_size 32 and prefix caching enabled

what the KV cache stores

when a model gets a prompt, it runs the input through its layers. this is prefill. along the way it computes a key and a value for every token at every layer. as it generates a reply, each new token's attention uses the keys and values from earlier positions. the KV cache keeps those vectors around so the model can read them before the next decode step.

prefix caching keeps those vectors around between requests too.

there's a fair amount of memory behind making that little shortcut happen though.

how big is the cache

for every token, the model stores one key and one value, in every layer and for every KV head. so the math multiplying out for Qwen3-1.7B looks something like this:

KV cache size math for a single token in Qwen3-1.7B

that's about 112 KiB for a single token. a 5,000-token agent prompt is gonna be roughly 550 MiB of KV, for one session, before the model has even generated anything.

and that's already with a saving baked in: Qwen3 shares each set of keys and values between two query heads (grouped-query attention), which halves this. without it, the same 5,000 tokens would take about 1.1 GiB.

grouped-query attention vs multi-head attention memory comparison

what the engine gets to skip

for 5,000 tokens that's roughly 14 trillion operations of work, and a prefix hit skips all of it for the cached positions. the prefix isn't completely free though: every new token still has to look back over the cached keys and values, so it still gets read every turn. it just doesn't have to be built again from scratch.

what a prefix hit skips versus what it still computes

why it has to be a prefix

take token 50 in a prompt. the first attention layer computes its key and value before that token has had a chance to look back at anything. then attention lets it read tokens 1 through 49 and folds information from them into its hidden state. layer 2 computes fresh keys and values from that updated state. by then, it's working with token 50 in this particular context.

token 50's key and value depend on the tokens before it, layer by layer

now change token 10 and leave the rest of the prompt alone. token 50 is still the same token in the same position, but it can now pick up different information in the first layer. that can change the key and value it produces in the second layer. the same goes for any token after the edit.

tokens 1 through 9 are safe to reuse. they could never see token 10 in the first place. that's why the cache looks for a prefix. it can reuse KV up to the first mismatch.

say the model asks to read main.go. on the next turn, the agent sends back both the tool call and the file contents. the file contents are new, so the engine has to compute them. the tool call isn't: the engine already computed most of its KV while generating it. so why does it get processed again?

the reply came back but the prompt changed

after the harness sends the model a list of messages, the server runs it through a chat template, a small Jinja program (Jinja is the python templating language that chat templates are written in) that turns messages into one long string with role markers and special tokens, and the tokenizer turns that string into token IDs. the cache only ever compares token IDs and not the content directly. this is where a lot of the problems with cache reuse stem from.

so "the same conversation" doesn't really mean anything to the cache if the rendered tokens aren't identical. a timestamp, an extra space, or a generated id can break the match if it changes the token IDs the model sees. tokenization means the same word with and without a leading space results in completely different tokens.

agents add two sneakier ways to break it.

template asymmetry. Qwen3 with thinking turned off is the one i measured. when the model is generating, the prompt ends with an empty thinking block, <think>\n\n</think>\n\n, which is 4 tokens. but when the reply gets rendered back as history on the next turn, the template leaves the empty block out. so the history no longer matches with what the model actually saw, and the mismatch sits right before the reply.

the same reply as generated and as rendered back into history, with the think block dropped

(the same reply, as the model generated it and as it comes back in history. the 4-token think block is gone, so the reply now starts at position 12 instead of 16, and nothing from there on matches what's cached.)

this doesn't snowball though. once a reply has been rendered as history, it stays in that form and keeps matching on every later turn, as long as the rendered history stays stable. only the newest reply mismatches, so every turn pays for the previous reply twice. that was about 16 to 77 tokens per follow-up turn across the three runs, since the agent's replies were short tool calls, so the cost is small. (apparently this template behavior was already reported in Qwen3 issue #1826.)

harness re-serialization. smolagents (huggingface's agent library) rewrites every tool call the model generates into a different text format when it puts it back into history, with a random call ID from the server. a call the model generated in 19 to 36 tokens comes back as 52 to 66 tokens of different text, so it can never match what's cached.

similar problem to template asymmetry but this time the change is happening at the harness level.

how much of a matching prompt can the engine reuse?

when a request starts, vLLM has no idea how long it'll end up. the prompt might be 5,000 tokens, and the reply could be 10 tokens or 2,000. if it reserved one contiguous chunk of memory per request, it'd have to reserve for the worst case, and most of that would sit empty while other requests wait for memory.

so instead it does what an OS does with RAM: it splits KV memory into tiny blocks (32 tokens each in my runs) and hands them out one at a time as the request grows. each request keeps a block table which tells what tokens for the request are in which block. this is paged attention and this is for memory management, not caching.

paged attention splits KV memory into fixed-size blocks tracked by a block table

prefix caching is built on top of these blocks, so blocks are also the unit of reuse. a block will only get a hash once it's full and until then, tokens are still being added to it, so its contents would keep changing. no hash means nothing to look up which means a partial block can never be reused.

so a 150-token shared prefix gives you 128 cached tokens, four full blocks. the other 22 get recomputed.

the engine always computes at least the last prompt token, because the first output token comes from it. and since hits count in whole blocks, a fully cached prompt whose length is an exact multiple of 32 loses its whole last block, not just one token.

the same goes for tokens the model generates. once a block of output fills up, it gets hashed just like a prompt block, so the model's previous reply should be sitting in the cache, ready to be reused next turn.

how i checked. i sent the engine repeated prompts and prompts with single-token changes at different positions. the reported cache hits matched the block-aligned predictions on all 17 calibration steps.

why four tokens cost a whole reply

here's the actual function in vLLM. look at the return statement at the bottom. the hash takes the current block's token IDs, the previous block's hash, and any extra keys.

vLLM's hash_block_tokens function, with the parent hash as its first input

vLLM's hash_block_tokens.

if you've ever edited a commit three back in an interactive rebase and watched every commit after it get a new hash, you've seen the same idea. change one token in block two and its hash changes. block three can contain the exact tokens, but it uses block two's new hash as an input, so its key changes too. vLLM stops reusing the prefix at the first miss.

that's why dropping Qwen3's four-token thinking cue costs more than four tokens. the cache match ends before the reply. even though the reply comes back word for word, the engine computed its KV with the cue in front of it. the reply's tokens also moved from position 16 to 12, and keys depend on position, so even their first-layer KV wouldn't match.

what if every token still matches?

matching the hash only helps if the block is still in memory. the engine has a fixed number of slots, and another request can take one before the agent comes back.

in the vLLM build i ran, blocks in use by a request are reference-counted. when a block's last reference goes away, it goes back on a free queue and keeps its hash. another request can still hit it. when the engine needs that slot for something else, it takes a block from the front of the queue and evicts the old entry. blocks from a finished request are released tail first, so its later blocks are put up for eviction before its earlier ones.

a miss still stops the lookup. if the second block is gone and the third is still sitting there, the engine can't skip over the gap and report the third as a prefix hit. this time the prompt can be exactly what you expected, down to every token ID.

an evicted middle block stops the prefix lookup even when later blocks survive

one block short

i recorded 30 requests from three agent sessions that ran at the same time. then i took those exact prompt token sequences and replayed them one at a time in the recorded order, resetting the cache before each size. i used one output token per replayed request so i could compare the same prompts under different amounts of cache.

cache sizeextra tokens recomputed due to evictionrequest predictions that matched vLLM
488 blocks030 / 30
487 blocks3230 / 30

the three sessions were captured on Qwen3-1.7B and replayed on Qwen3-0.6B on the mac. the two share the same tokenizer and the same KV bytes per token, so the block math is identical.

at 488 blocks, roughly 1.67 GiB of KV capacity, the trace got all the reuse it could get without eviction. take away one block and one request has to recompute 32 extra tokens. drop to 438 blocks and it's 4,512 extra tokens across the trace. at 384 blocks it's 12,832.

extra tokens recomputed as cache capacity drops

the useful number here is how many blocks the sessions need to keep around between turns, their working set. counting sessions alone misses that two sessions can carry very different amounts of context. across nine seeded runs at the same capacity, two had eviction. the estimate from each trace correctly called which runs would see it.

how much did it matter?

first, a result that surprised me. with one session and no eviction, 64% to 91% of the tokens recomputed across the three runs were new content. the Qwen3 mismatch was easy to see, but most of the computation was work the engine had to do anyway.

to see what eviction cost in time, i borrowed a Tesla T4 and replayed the same 30 prompts. summed across those requests, time to first token went from 23.6 s with no eviction to 30.9 s at 438 blocks and 43.9 s at 384. that's +31% and +86% on this trace. the 487-block run was only done on the mac, not the T4.

i tried making sessions wait

once i could predict when eviction would start, i tried the obvious fix: let fewer sessions use the cache at once. i tried two ways of doing that in the proxy, with four sessions sharing a 438-block cache, across five seeds.

a fixed cap. only two sessions can be active at a time. once a session gets in, it keeps its spot between turns until it goes idle (5 seconds without a request, by default), and everyone else waits for a spot to free up. this removed eviction in all three seeds that had it. in the worst uncapped run, eviction had cost 66,528 tokens. the downside is waiting: in a seed with no eviction to begin with, the cap just made the run 26% slower. (the wall times are rough. these were live CPU runs, and the worst uncapped run also had a session blow past its context limit, which inflates the gap.)

a token budget. instead of counting sessions, the proxy estimated how much cache each one needed from the size of its latest request, and let in as many as fit. that lets more small sessions run at once, but a session that grows past its share gets paused between turns. on one seed this beat the cap: no eviction, and far less waiting (125 s total vs 414 s). on another it backfired: it lost 3,616 tokens to eviction, where running with no limit at all had lost only 256.

the awkward part was whose tokens those were. they belonged to the sessions the budget itself had paused. a paused session's blocks go back on the free queue, and other sessions grab them. so pausing a session to protect the cache is exactly what got its cache evicted.

A fixed cap admits two sessions and makes the others wait. A token budget admits more sessions, but a paused session can lose its cache blocks.

so a limit has to decide at the door, before a session starts. pausing one halfway through costs it the very cache you were trying to protect.

how i figured out where the tokens went

the proxy records the request and response bytes and when requests start and finish. i use the pinned tokenizer and template to reconstruct the prompt IDs, then compare the whole ID sequence with what vLLM reports on replay. i wanted this check because matching token counts can hide a change at exactly the spot i'm trying to explain.

reconstructing the prompt token IDs from the recorded bytes

once the IDs agree, i can compare the new prompt with earlier sequences, including replies the model generated. that tells me how much of the prompt could match in full blocks. the simulator then walks the requests in order and models the engine's allocation and free queue to predict which blocks are still available. i compare each prediction with the reported hit. when the engine leaves the metric out, Cachino records it as unknown.

the predictor matched every sequential replay in the study. with live overlapping requests it matched 710 of 738. my best guess is that some misses come from when the engine allocates blocks during decode, but i'd need allocation events from inside the engine to check.

the comparison i cared about most was against a shortcut that assumes any matching earlier prefix is still cached. in a nine-run concurrent matrix, that shortcut was off by 8,320 tokens in total absolute error. the predictor that modeled cache residency was off by 352. the shortcut's entire error in that matrix came from overestimating reuse in runs with eviction. the released tables include the per-request counts and predictions behind it.

so back to those 2,000 uncached tokens. for a given request i'd first check where the exact token sequence diverged and how many full blocks that leaves. then i'd check what had happened to those blocks since the previous turn. the engine's one number can tell me the outcome. i need the capture and the cache model to explain it.

if you're building a harness

a few lil things to keep in mind: put whatever changes least at the top, never edit what you already sent (send updates as new messages instead), don't add or remove tools mid-session, serialize JSON the same way every time, put the model's tool calls back exactly as it wrote them, and don't switch models halfway. if you serve the model yourself, also check the chat template at the reply boundary, and size the cache for what your sessions hold between turns, not for how many sessions you run. none of it is new, but it's easy to break without noticing.

byebye

i used to see a low cache hit and assume something in the prompt had changed. now i also check what was still in memory when the next turn arrived. vLLM gives you one number for both, which is how i ended up spending this much time on one integer. anyway, that's it for me. hope you got something out of this.

thanks for reading. see ya :)