KV cache, prompt caching, and inference economics

• Token — the unit of text the model reads and writes (a word or word piece with an integer id).
• Autoregressive generation — producing output one token at a time, each token conditioned on all the previous ones.
• Q / K / V (query, key, value) — three vectors computed for every token at every layer; a token’s query is compared with other tokens’ keys, and the resulting weights mix their values. Full treatment in Self-attention and positional structure.
• KV cache — stored K and V vectors of tokens already processed, kept so they need not be recomputed at each generation step.
• Layer (n_layers) — one repeated transformer block; the model has dozens of them and each keeps its own K/V per token.
• Head / KV head (n_kv_heads) — attention is split into several parallel heads; “KV heads” are the heads that have their own K and V vectors.
• d_head — the vector width inside one head (commonly 64 or 128).
• MHA / MQA / GQA — multi-head attention (every query head has its own K/V head) / multi-query (all query heads share one K/V head) / grouped-query (groups of query heads share one K/V head).
• bf16 / fp16 / fp8 — number formats using 16 / 16 / 8 bits (2 / 2 / 1 bytes) per value.
• Prefill — the first phase: the whole prompt is processed in one parallel pass.
• Decode — the second phase: tokens are generated one at a time.
• TTFT (time to first token) — delay from sending the request until the first output token appears; roughly the prefill time.
• TPOT (time per output token) — average time between output tokens during decode.
• HBM (high-bandwidth memory) — the GPU’s large main memory (tens of GB). Fast, but still the bottleneck during decode.
• Compute-bound / memory-bandwidth-bound — limited by arithmetic speed / by the speed of moving bytes from memory to the arithmetic units.
• Arithmetic intensity — FLOPs performed per byte read from memory. High = compute-bound, low = bandwidth-bound.
• FLOPs — floating-point operations, a count of arithmetic work.
• Prompt (prefix) caching — a provider feature that stores the KV cache for a repeated prompt prefix so later requests skip prefilling it.
• TTL (time to live) — how long a cache entry survives without being used.
• Batching — running several requests through the GPU together.
• Continuous (in-flight) batching — changing the batch membership after every decode step instead of once per whole batch.
• PagedAttention — storing the KV cache in small fixed-size blocks (like OS memory pages) so memory is not wasted on fragmentation.
• Speculative decoding — a small draft model guesses several tokens ahead and the big model checks them all in one pass.
• Rejection sampling — accept a proposed sample with a probability chosen so that the accepted samples follow a target distribution exactly.
• Medusa / EAGLE / n-gram (prompt-lookup) drafting — ways to produce draft tokens without (or with a lighter-weight) separate draft model.
• Disaggregated serving — running prefill and decode on separate GPU pools.
• A/B test — sending comparable traffic to two variants (here, two models) and comparing measured outcomes.
• Model routing — a cheap classifier or rule that sends each request to the smallest model likely to handle it, escalating hard or low-confidence cases to a larger one.

The problem it removes

Generation is autoregressive: to produce token t+1, the model runs attention over tokens 1..t, and attention needs, for every earlier token, its key and its value at every layer. Recomputing them at each step would be pure waste, because of one property of the causal mask (see Self-attention and positional structure):

Without cache: step t recomputes K,V for tokens 1..t       work per step ~ t   -> total ~ n^2/2
With cache:    step t computes K,V for token t only,        work per step ~ 1   -> total ~ n
               appends them, and READS the stored 1..t-1

Illustration: generating 1,000 tokens from an empty prompt, the no-cache approach computes K/V projections for 1+2+…+1000 = 500,500 token-positions; the cached approach computes 1,000.

The idea

During generation each new token must attend to all previous tokens. Because of the causal mask, the key and value of position j depend only on tokens 0..j, never on later tokens, so once computed they never change. The model therefore stores K and V for every past position (the KV cache) and, at each step, computes q, k, v only for the one new token, appends k, v to the cache, and attends over the cache.

step t (t = number of tokens already cached)

  new token x_t ──> q_t, k_t, v_t        (3 small matmuls on ONE row)
                     │    │
        K_cache [t, d_k] + k_t ──> [t+1, d_k]
        V_cache [t, d_k] + v_t ──> [t+1, d_k]
                     │
  weights = softmax(q_t · K_cacheᵀ / sqrt(d_k))      shape [1, t+1]
  out_t   = weights · V_cache                         shape [1, d_k]

No mask is needed at decode time: the cache only contains the past (and the current token), so there is nothing to hide. What is not cached: the queries of past tokens (a past query is never needed again; only past keys and values are read by later tokens) and the final outputs.

Runnable check: cached decoding equals full recomputation

The following NumPy script computes causal attention for 6 tokens twice, once over the whole sequence at once, once token by token with a cache, and compares them.

import numpy as np
rng = np.random.default_rng(0)
d_model, d_k, n = 8, 4, 6
Wq, Wk, Wv = [rng.standard_normal((d_model, d_k)) for _ in range(3)]
X = rng.standard_normal((n, d_model))

def softmax(z):
    z = z - z.max(-1, keepdims=True)
    e = np.exp(z)
    return e / e.sum(-1, keepdims=True)

def full(X):                                   # recompute everything, with the causal mask
    Q, K, V = X @ Wq, X @ Wk, X @ Wv
    S = Q @ K.T / np.sqrt(d_k)
    S = np.where(np.triu(np.ones((len(X),) * 2, bool), 1), -np.inf, S)
    return softmax(S) @ V

ref = full(X)

K_cache = np.zeros((0, d_k))
V_cache = np.zeros((0, d_k))
outs = []
projections = 0
for t in range(n):                             # one token per step
    x = X[t:t + 1]                             # [1, d_model]
    q, k, v = x @ Wq, x @ Wk, x @ Wv           # each [1, d_k]
    projections += 3
    K_cache = np.vstack([K_cache, k])          # [t+1, d_k]
    V_cache = np.vstack([V_cache, v])
    w = softmax(q @ K_cache.T / np.sqrt(d_k))  # [1, t+1]  no mask needed
    outs.append(w @ V_cache)                   # [1, d_k]
    print(t, K_cache.shape, w.shape)
# 0 (1, 4) (1, 1)
# 1 (2, 4) (1, 2)
# ... 
# 5 (6, 4) (1, 6)

print(np.allclose(np.vstack(outs), ref))       # True
print(projections, "projections vs", sum(3 * m for m in range(1, n + 1)), "without a cache")
# 18 projections vs 63 without a cache

Walkthrough: at step t the cache has t+1 rows after appending, the weight row has t+1 entries, and the output equals row t of the full computation. The cache is exactly “the K and V rows that the full computation would have produced anyway”, so the result is identical, not approximate. The last line counts the work: 18 projections instead of 63 for just 6 tokens, a gap that grows quadratically with length. In a real model there is one such cache per layer and per KV head (see grouped-query attention above), and the output of layer l feeds the next layer’s x.

Work saved and memory paid

	Without cache	With cache
K and V projections at step t	t rows (the whole prefix)	1 row
K/V row projections over n generated tokens	1 + 2 + ... + n = n(n+1)/2 (quadratic)	n (linear)
Attention score entries at step t	t²	t
Extra memory	none	2 · L · g · d_k · n · b bytes

The trade is compute for memory: the cache must be held for every active sequence until that sequence finishes. Symbols: L layers, g KV heads, d_k head width, n cached tokens, b bytes per number, the 2 for K and V. For a Llama-3-8B-shaped model that is 128 KiB per token, so 1 GiB at 8k tokens and 16 GiB at 128k, per sequence; the next concept derives these numbers and the capacity-planning consequences.

Pitfalls

• The cache is valid only for an identical prefix: change one earlier token (edit a system prompt, reorder messages) and every later K and V is stale. This is why provider prompt caching rewards stable prefixes.
• Decode steps are memory-bandwidth-bound: each step reads the entire cache plus all weights to produce one token, so longer contexts mean slower tokens even though the FLOPs per step are small.
• Prefill (processing the prompt) fills the cache in one parallel pass; decode appends one row per step. The two phases have different bottlenecks. Cache sizes, prefill vs decode, paged allocation and provider prompt caching are covered in the concepts below.

For every transformer layer, every attention head, and every token position processed so far, the cache holds the key vector and the value vector produced by that layer’s K and V projections. Size:

kv_bytes = 2 (K and V)
         * n_layers
         * n_kv_heads * d_head        (= d_model, or less with GQA/MQA)
         * seq_len
         * bytes_per_element          (2 for fp16/bf16, 1 for fp8/int8)

Every term

Term	Meaning	Where the value comes from
2	one K vector plus one V vector per token	fixed by attention
n_layers	number of transformer blocks	model design (e.g. 32, 80)
n_kv_heads	number of K/V heads	model design; with GQA smaller than the query-head count
d_head	width of each head	model design (often 128)
seq_len	tokens currently in context (prompt + generated)	your request
bytes_per_element	storage precision	serving config (bf16 = 2, fp8 = 1)

For a ~70B model (80 layers, d_model 8192, but say 8 KV heads x 128 = 1024 with GQA) at 8k tokens in bf16: 2 * 80 * 1024 * 8192 * 2 ≈ 2.7 GB for one sequence. Without GQA it would be ~8x that. This is per concurrent request, on top of the weights, and it grows linearly with context length — which is why long-context serving is a memory problem before it is a compute problem, and why GQA/MQA (few KV heads) and KV quantization exist.

Calculator and a table

def kv_bytes(n_layers, n_kv_heads, d_head, seq_len, bytes_per=2):
    return 2 * n_layers * n_kv_heads * d_head * seq_len * bytes_per

GiB = 2**30
for name, L, kvh in [("8B-like, GQA (8 KV heads)", 32, 8), ("8B-like, MHA (32 KV heads)", 32, 32),
                     ("70B-like, GQA (8 KV heads)", 80, 8), ("70B-like, MHA (64 KV heads)", 80, 64)]:
    per_tok = kv_bytes(L, kvh, 128, 1) / 1024
    print(f"{name:30s} {per_tok:7.0f} KiB/token  "
          f"{kv_bytes(L, kvh, 128, 8192)/GiB:6.1f} GiB @8k  {kv_bytes(L, kvh, 128, 131072)/GiB:6.1f} GiB @128k")
# 8B-like, GQA (8 KV heads)         128 KiB/token     1.0 GiB @8k    16.0 GiB @128k
# 8B-like, MHA (32 KV heads)        512 KiB/token     4.0 GiB @8k    64.0 GiB @128k
# 70B-like, GQA (8 KV heads)        320 KiB/token     2.5 GiB @8k    40.0 GiB @128k
# 70B-like, MHA (64 KV heads)      2560 KiB/token    20.0 GiB @8k   320.0 GiB @128k

(The configurations are Llama-style shapes used for illustration; check a model’s config.json for its real values.) Reading it: a single 128k-token conversation on a 70B GQA model needs about 40 GiB of cache in bf16, on top of ~131 GiB of bf16 weights. Storing the cache in fp8 halves it (the 8k, 70B GQA case drops from 2.5 to 1.25 GiB), at some quality risk worth testing.

Consequence for capacity planning

Free memory after weights, divided by per-request cache, is roughly how many concurrent sequences fit. If an 80 GiB GPU holds 40 GiB of quantized weights and has ~30 GiB left after overhead, it fits about 12 sequences at 8k context of a 70B-like GQA model (30 / 2.5), but a single 128k-token sequence (about 40 GiB) would not fit at all without a smaller cache format or more GPUs. See VRAM and running LLMs locally for the wider memory budget.

Ways the cache is shrunk

• Fewer KV heads (GQA/MQA): set at model design time; the biggest lever (8x in the table above).
• KV quantization (fp8/int8, sometimes 4-bit): halves or quarters bytes per element.
• Sliding-window attention in some layers: keep only the last w tokens’ K/V there.
• PagedAttention: does not shrink the cache but stops fragmentation from wasting it (see below).
• Evicting or compressing old tokens: research-stage and lossy; test carefully before relying on it.

• Prefill — process the entire input prompt in one forward pass, computing and caching K/V for all n prompt tokens. This is one big matmul over n positions: compute-bound, parallel, high GPU utilization. Its latency determines time to first token (TTFT) and scales with prompt length.
• Decode — generate output tokens one at a time; each step runs the full stack for a single new token, reading the entire KV cache and the full weight matrices to produce one token. Almost no parallelism within a step; you move gigabytes of weights from HBM to produce one token: memory-bandwidth-bound, low arithmetic intensity. Its speed is time per output token (TPOT) and is roughly constant per token regardless of how you got there.

Consequences: a long prompt with a short answer is dominated by prefill; a short prompt with a long answer is dominated by decode. Batching helps decode enormously (amortize the weight reads across many sequences) but helps prefill less. Serving stacks now often disaggregate the two onto different hardware pools.

Timeline

request:  [ prompt: 2000 tokens ................. ][ answer: 300 tokens ]
phase:    |<-------- PREFILL (one pass) -------->|<-- DECODE: 300 sequential steps -->|
GPU:      |  big matmuls, compute saturated      |  tiny matmuls, waiting on memory   |
metric:   |<------- TTFT ----------------------->|  each step = 1 TPOT                |

Why decode is bandwidth-bound — the arithmetic

A model with N parameters does about 2N FLOPs per token (one multiply-accumulate per weight). In decode with batch size B (B sequences, one new token each), the GPU must read all N weights once (2N bytes in bf16) and performs 2N * B FLOPs:

arithmetic intensity (decode)  ~  (2 N B FLOPs) / (2 N bytes)  =  B FLOPs per byte

A modern data-centre GPU can do on the order of a few hundred FLOPs per byte of HBM traffic before arithmetic, not memory, becomes the limit (peak FLOPs divided by memory bandwidth; roughly 300 for an H100-class card in bf16, approximate). So at B = 1 the chip is limited by memory by a factor of a few hundred. In prefill with a 2,000-token prompt the same weights are used for 2,000 positions at once, giving an intensity of around 2,000 (that is B replaced by n): compute-bound.

Runnable estimate (illustrative: 3.35 TB/s bandwidth, weights only, ignoring the cache and overheads, so a real system is slower):

bw = 3.35e12                          # bytes/second of HBM bandwidth (illustrative)
weights_8b = 8.03e9 * 2               # bf16 bytes
for B in [1, 8, 32, 64]:
    print(B, round(B * bw / weights_8b), "tokens/s aggregate upper bound")
# 1 209  | 8 1669  | 32 6675  | 64 13350   (aggregate across all B sequences, ideal)
print(2 * 8.03e9 * 2000 / 1e12, "TFLOP for a 2000-token prefill")   # -> 32.12

Reading it: at B = 1 an 8B bf16 model cannot exceed ~209 tokens/s on this card however fast the arithmetic units are, because each token needs the 16 GB of weights streamed once. Raising B raises aggregate throughput almost linearly until the compute ceiling or the KV-cache reads (which grow with B * seq_len) take over. Per-sequence speed stays about the same, which is why batching is the main economic lever and why per-token latency is “roughly constant”.

Practical implications

• Quantizing weights speeds up decode mostly because it cuts bytes read, not arithmetic (see Quantization and inference efficiency).
• Long contexts make decode slower: the per-step read includes the whole KV cache, which can rival the weights at large B * seq_len.
• Prefill can starve decode when both share a GPU (a long prompt stalls others’ tokens): that is why chunked prefill and disaggregation exist.

Prompt caching stores the computed KV cache for a prefix of your prompt server-side, so a later request that begins with the byte-identical prefix skips prefill for that portion — large latency and cost reduction (cached input tokens are billed at a fraction of the normal rate; writing to the cache sometimes costs a small premium).

The rule: it is a strict prefix match. The cache hits only up to the first token that differs. Anything that changes early in the prompt invalidates everything after it. So:

• Put the stable content first — system prompt, tool definitions, few-shot examples, pinned documents — and the variable content (the user’s new question, the latest turn) last.
• Never inject a timestamp, request id, or randomly-ordered context into the prefix.
• Append to the conversation; do not rewrite earlier turns.
• Cache entries have a short TTL (minutes) and are usually scoped to your account/organization; a cold cache just falls back to normal prefill.

Providers may require a minimum prefix length and offer explicit cache-breakpoint markers.

Good vs bad prompt layout

GOOD (stable first)                              BAD (variable early)
[system prompt          ]  \                     [ "Today is 2026-10-14 14:03:22" ]  <- changes every call
[tool definitions       ]   > identical each     [system prompt          ]
[few-shot examples      ]  /  call -> cached     [tool definitions       ]   all of this is a MISS
[conversation so far    ]  <- append-only        [conversation so far    ]   because token #1 differs
[new user message       ]  <- the only new part  [new user message       ]

Worked cost example

Illustrative rates only (check your provider’s current price list; some providers also charge nothing extra for cache writes or cache automatically): input $3 per million tokens, cache write 1.25x input, cache read 0.1x input, output $15 per million. A request with a 10,000-token stable prefix, 200 new input tokens, 500 output tokens:

base, out = 3.0, 15.0                   # $ per million tokens (illustrative)
cache_write, cache_read = 1.25 * base, 0.1 * base
sys_t, new_t, out_t = 10_000, 200, 500
plain  = (sys_t + new_t) * base / 1e6 + out_t * out / 1e6
first  = sys_t * cache_write / 1e6 + new_t * base / 1e6 + out_t * out / 1e6
later  = sys_t * cache_read  / 1e6 + new_t * base / 1e6 + out_t * out / 1e6
print(round(plain, 4), round(first, 4), round(later, 4))   # -> 0.0381 0.0456 0.0111
print(round(first + 99 * later, 2), "vs", round(100 * plain, 2))   # 100 requests -> 1.14 vs 3.81

Walkthrough: the first request pays a 25% write premium on the prefix (0.0456 vs 0.0381); every later request within the TTL pays a tenth of the rate on those 10,000 tokens (0.0111). Over 100 requests the cached run costs about 30% of the uncached one, and TTFT also drops because the prefix is not prefilled. The break-even is almost immediate: one reuse within the TTL pays back the premium.

Pitfalls

• Silent misses: a single differing byte (a reordered JSON key in a tool definition, a changed whitespace, a different tool list) misses the whole cache. Check the usage fields in the API response (cache-read vs cache-write token counts) to confirm hits.
• TTL expiry: low-traffic endpoints may never hit a short-lived cache.
• Minimum length: prefixes below a provider-specific token minimum are not cached at all.
• Scope: caches are generally not shared across organisations; do not rely on someone else’s warm cache.
• Changing model or settings that affect the prefix (model version, tool set, some feature flags) can invalidate it.

Prompt caching reuses the stored attention keys and values (K/V) for the start of a prompt. Whether it works for your next request is decided by one question: how long is the longest common token prefix between the new request and what is cached? This concept derives why only a prefix can be reused, shows the effect on a token diagram, runs a tiny model to demonstrate the propagation, and does the cost arithmetic.

Why only a prefix can be reused: the dependency rule

With causal attention, the K/V entries at position i in layer l depend only on tokens 1..i (the mask forbids looking right; see Self-attention and positional structure). Consequences:

• Append tokens at positions n+1, n+2, ...: positions 1..n do not depend on them, so their cached K/V are still exactly right.
• Edit the token at position k: positions 1..k-1 are unaffected, but every position j >= k depends on token k (directly or through earlier layers), so their K/V are now wrong.
• Insert or delete at k: every later token shifts position. Positional information (RoPE rotation or position embeddings) is part of the K/V, so even identical tokens after k have different K/V.

The token-prefix diagram

position:   1    2    3    4    5    6    7    8    9   10   11   12   13
cached :   [S1] [S2] [S3] [S4] [U1] [U2] [U3] [A1] [A2] [U4] [U5]
request A:  S1   S2   S3   S4   U1   U2   U3   A1   A2   U4   U5   A3   U6      <- appended
            ----------------- HIT (11 tokens) ------------------   NEW (2)

request B:  S1   S2   S3   S4   U1   U2*  U3   A1   A2   U4   U5   A3   U6      <- U2 edited
            ------- HIT (5) -----  ^ first difference: MISS from position 6 to 13 (8 tokens)

The cache compares token by token from the start and stops at the first mismatch. Everything after it is recomputed even though 7 of those 8 tokens are textually identical to before. The distance from the end of the prompt to the first changed token is what you pay for.

Demonstration: watch the invalidation spread

The following toy causal transformer (random weights, 2 layers, 6 tokens) records the K matrix of each layer, edits the vector of token 2 (0-indexed), and reports which positions’ K changed:

import numpy as np
rng = np.random.default_rng(0)
d, n, L = 8, 6, 2
Wq = [rng.standard_normal((d, d)) / 3 for _ in range(L)]
Wk = [rng.standard_normal((d, d)) / 3 for _ in range(L)]
Wv = [rng.standard_normal((d, d)) / 3 for _ in range(L)]

def forward(X):
    Ks = []
    for l in range(L):
        Q, K, V = X @ Wq[l], X @ Wk[l], X @ Wv[l]
        Ks.append(K)                                    # this is what the KV cache would store
        S = Q @ K.T / np.sqrt(d)
        S[np.triu_indices(n, 1)] = -np.inf              # causal mask
        P = np.exp(S - S.max(1, keepdims=True)); P /= P.sum(1, keepdims=True)
        X = X + P @ V                                   # residual connection
    return Ks

X = rng.standard_normal((n, d))
X2 = X.copy(); X2[2] += 1.0                             # "edit" the token at position 2
K_old, K_new = forward(X), forward(X2)
for l in range(L):
    changed = [i for i in range(n) if np.abs(K_old[l][i] - K_new[l][i]).max() > 1e-12]
    print("layer", l + 1, "K changed at positions:", changed)
# layer 1 K changed at positions: [2]
# layer 2 K changed at positions: [2, 3, 4, 5]

Walk-through: in layer 1, K is computed straight from the input vectors, so only the edited position 2 changes. But layer 1’s attention output at positions 3, 4, 5 mixes in the edited token’s V, so their hidden states (the input to layer 2) change. Hence in layer 2 the K at positions 2, 3, 4, 5 all differ. Positions 0 and 1 never change. With 32 or 80 layers the corruption reaches every later position by the second layer, which is why a cache entry is either valid or must be fully recomputed: there is no “mostly valid” state.

Cache-hit calculation in code

def common_prefix_len(a, b):
    n = 0
    for x, y in zip(a, b):
        if x != y:
            break
        n += 1
    return n

READ, WRITE = 0.1 * 3.0, 1.25 * 3.0     # $ per million tokens, illustrative: cache read 0.1x, write 1.25x of $3 input

def request_cost(cached, request):
    hit = common_prefix_len(cached, request)
    miss = len(request) - hit            # these must be prefilled (and written to the cache)
    return hit, miss, (hit * READ + miss * WRITE) / 1e6

sys_prompt = "You are a support bot . Answer briefly .".split()                 # 9 tokens (words stand in for tokens)
turn1      = "User : my invoice total looks wrong".split()                       # 7
asst1      = "Assistant : which invoice number ?".split()                        # 6
turn2      = "User : INV-204".split()                                            # 3
cached     = sys_prompt + turn1 + asst1 + turn2                                  # 25 tokens cached last time

appended = cached + "Assistant : found it".split() + "User : thanks".split()     # 32 tokens
edited   = (sys_prompt + "User : my invoice total looks incorrect".split() + asst1 + turn2
            + "Assistant : found it".split() + "User : thanks".split())           # 32 tokens, one word changed in turn 1

for name, req in [("append", appended), ("edit turn1", edited)]:
    hit, miss, cost = request_cost(cached, req)
    print(f"{name:10s} total={len(req)} hit={hit} miss={miss} hit%={hit/len(req):.0%} cost=${cost*1e6:.1f}e-6")
# append     total=32 hit=25 miss=7 hit%=78% cost=$33.8e-6
# edit turn1 total=32 hit=15 miss=17 hit%=47% cost=$68.2e-6

Walk-through: common_prefix_len is the rule providers apply (at token or block granularity). In the append case all 25 cached tokens match and only the 7 new ones are prefilled: 78% of the request is a cache read and the cost is $33.8e-6. In the edit case the first difference is the word wrong -> incorrect, the 16th token (15 tokens come before it: 9 of system prompt plus 6 of User : my invoice total looks), so 15 tokens hit and 17 are recomputed although only one word changed. The cost doubles to $68.2e-6 even though the edit changed a single word. Use the function on your own token lists (from your provider’s token counter) to predict hit rates.

The same thing at realistic scale

Illustrative: system prompt 1,200 tokens, tool definitions 800, then a conversation: user1 150, assistant1 400, user2 100, assistant2 600, user3 80 (3,330 total; the first 3,250 are cached from the previous request). Rates as above: cache read $0.30/M, cache write/uncached-then-written $3.75/M, plain input $3/M.

scenario	cached-prefix hit	recomputed	cost of input side	note
append user3	3,250 (97.6%)	80	about $0.0013	the intended pattern
no caching at all	0	3,330	$0.0100	baseline
edit one token inside user1 (token 2,010)	2,010 (60.4%)	1,320	about $0.0056	system + tools still reused
change one token in the system prompt (token 5)	5 (0.15%)	3,325	about $0.0125	worse than no caching because of the write premium

The last row is the important surprise: an invalidated cache is not just “no benefit”, it can cost more than not caching, because you pay the write premium on tokens that will never be read. Providers differ in whether and how they charge for writes; check yours.

Practical rules

• Append-only histories. Never “tidy up” earlier turns (trimming, re-summarising, reformatting) on every call. If you must compact, do it rarely and in one step so the cache is rebuilt once and then stable.
• Stable prefix first. Keep system prompt, tool definitions (in a fixed order), and pinned documents at the very start; put timestamps and per-request data at the end (in the last user message).
• Sliding windows hurt. Dropping the oldest turns shifts every later token, so the whole cache is invalid every time. Prefer tail-only changes, or summarise once.
• Serialisation matters. A re-serialised JSON tool definition with keys in a different order is a different byte string; the cache misses from there on.
• Verify with usage fields. Compare cache-read versus cache-write token counts in the response; a sudden drop in reads after a deploy usually means someone changed the prefix.

A small, fast draft model proposes the next k tokens cheaply. The large target model then does one forward pass that scores all k proposed positions in parallel (this is cheap — decode is memory-bound, so verifying k tokens costs almost the same as generating 1). A rejection-sampling-based acceptance rule accepts the longest correct prefix of the draft and resamples the first mismatch. Because the acceptance rule is designed to be distribution-preserving, the final output is distributed exactly as if the target model had sampled every token itself — it is an exact-sampling speedup, not an approximation. Speedup depends on draft/target agreement (often 2–3x). Variants: Medusa (extra heads on the target model instead of a separate draft), EAGLE, n-gram / prompt-lookup drafting (no draft model at all, just copy from the prompt).

Step by step

context: "The capital of France is"
1. draft (small model) proposes k=4 tokens:      " Paris" "," " a" " city"
2. target runs ONE pass over context + 4 tokens, giving its own distribution at each of the 4 positions (+1 bonus position)
3. walk left to right:
     " Paris" -> accept (target agrees)
     ","      -> accept
     " a"     -> reject: target preferred " the"; sample the replacement from an adjusted distribution
4. output this round: " Paris" "," " the"   (3 tokens for the price of one target pass)
5. repeat from the new end of the context

Even if the first draft token is rejected you still get one correct token (the resample), so a round never yields fewer than one token.

The acceptance rule (and why it is exact)

Let p(x) be the target model’s probability for token x at this position and q(x) the draft’s. The draft sampled token x ~ q. Then:

• Accept x with probability min(1, p(x) / q(x)).
• If rejected, resample from the residual distribution r(x) ∝ max(0, p(x) - q(x)) (normalised so it sums to 1).

Where the symbols come from: p and q are the two models’ ordinary softmax outputs at that position, nothing learned for this purpose. Numeric check with a 3-token vocabulary:

p = [0.6, 0.3, 0.1]    # target distribution
q = [0.3, 0.5, 0.2]    # draft distribution
acc = [min(1, pi / qi) for pi, qi in zip(p, q)]           # [1.0, 0.6, 0.5]
res = [max(0, pi - qi) for pi, qi in zip(p, q)]; s = sum(res)
res = [r / s for r in res]                                # [1.0, 0.0, 0.0]
reject_mass = sum(q[y] * (1 - acc[y]) for y in range(3))  # chance the first stage rejects
final = [q[x] * acc[x] + reject_mass * res[x] for x in range(3)]
print(final)   # -> [0.6, 0.3, 0.1]  == p exactly (to float rounding)

Walkthrough: token 0 is under-proposed by the draft (q 0.3 < p 0.6), so it is always accepted when proposed (contributing 0.3) and the residual stage tops it up to 0.6. Tokens 1 and 2 are over-proposed, so they are accepted only partly. The final distribution equals p, which is the proof of exactness in miniature.

How much speedup?

If each draft token is accepted with probability a (a simplification: real acceptance varies by token), the expected tokens produced per target pass with k drafts is (1 - a^(k+1)) / (1 - a):

k = 4:   a=0.5 -> 1.94    a=0.7 -> 2.77    a=0.8 -> 3.36    a=0.9 -> 4.10   tokens per target pass

Real speedup is lower, since the draft model costs time too. A good draft model (same tokenizer, trained on similar data, often a smaller sibling of the target) pushes a up.

Trade-offs and pitfalls

• Gains are largest at small batch sizes (memory-bound decode). At large batch, the GPU is already busy and speculation’s extra verification work can reduce throughput.
• Draft and target must share a vocabulary.
• Predictable text (code, structured output, quoting the prompt) is accepted far more often than creative text; prompt-lookup drafting shines on tasks that copy from the input, such as editing and summarising documents.
• Exactness holds for sampling with the same temperature and truncation settings applied consistently; implementation bugs in the acceptance rule are the usual way it silently stops being exact.

Static batching groups N requests, runs them together until all finish, then takes the next batch. Because output lengths vary wildly, short requests wait for the longest one and the GPU idles. Continuous batching (vLLM, TGI, TensorRT-LLM) operates at the iteration level: after every decode step, finished sequences leave the batch and waiting requests join immediately. This keeps the batch full and GPU utilization high, dramatically improving throughput and tail latency under mixed load. It is the default in modern serving stacks and is the reason a single GPU can serve many concurrent users economically. PagedAttention complements it by allocating the KV cache in fixed-size blocks (like OS virtual memory pages) so the cache does not need to be contiguous and fragmentation does not waste memory.

Picture

STATIC (batch of 3, runs until the longest ends)      CONTINUOUS (slots refilled each step)
slot A: [req1 ........ ][ idle ............]          slot A: [req1 ........ ][req4 ....]
slot B: [req2 ...      ][ idle ............]          slot B: [req2 ...][req5 ......][req7 ..]
slot C: [req3 ................]  <- longest            slot C: [req3 ................][req6 ..]
        next batch cannot start until C finishes              no waiting; slots never sit idle if requests queue

Simulation

32 requests, each needing between 5 and 100 output tokens (illustrative random lengths), 8 slots on one GPU, one decode step = one token for every active slot:

import random, heapq
random.seed(1)
lens = [random.randint(5, 100) for _ in range(32)]
B = 8
static = sum(max(lens[i:i + B]) for i in range(0, 32, B))     # each batch lasts as long as its longest request
slots = [0] * B
for l in lens:
    heapq.heapreplace(slots, slots[0] + l)                    # give the next request to the slot that frees first
print(sum(lens), "tokens; static steps", static, "continuous steps", max(slots))
# -> 1489 tokens; static steps 350 continuous steps 233

Continuous batching finishes the same work in about two-thirds of the steps (233 vs 350). The lower bound is 1489 / 8 = 186; the gap is the tail while the last requests finish. The larger the spread in output lengths, the larger the saving.

PagedAttention, concretely

A naive server reserves a contiguous block for the maximum possible length per request, wasting the unused part (internal fragmentation) and leaving unusable gaps between requests. PagedAttention splits each sequence’s cache into fixed-size blocks (e.g. 16 tokens), keeps a per-sequence table mapping logical block -> physical block, and allocates on demand. Memory use then tracks real lengths, and identical prompt prefixes can share physical blocks between requests (the server-side basis of prefix caching).

Pitfalls

• Continuous batching raises throughput but can raise per-request latency under heavy load (you share the GPU with more sequences); serving stacks expose max-batch and scheduling knobs.
• A request that arrives during a long prefill may wait; chunked prefill splits big prefills into pieces interleaved with decode steps.

• TTFT ≈ prefill cost ≈ f(input tokens), discounted heavily for any cached prefix. Long system prompts and big RAG payloads hurt here; prompt caching is the main lever.
• Total generation time ≈ output_tokens * TPOT, and TPOT is roughly fixed by the model and serving stack. The main lever is generating fewer tokens — ask for concise output, use stop sequences, avoid making the model restate the input.
• Cost ≈ input_tokens * in_rate + output_tokens * out_rate, with output usually 3–5x the input rate and cached input at ~0.1x. So a verbose reasoning trace is expensive twice: it is output tokens now and input tokens on the next turn.
• Streaming does not reduce total time but moves perceived latency to TTFT, which is why it is almost always worth enabling for user-facing use.

Worked estimate

Illustrative numbers: TTFT of 0.8 s for a 10,000-token uncached prompt, TPOT of 25 ms, 500 output tokens.

latency (non-streamed) ≈ TTFT + output_tokens * TPOT = 0.8 + 500 * 0.025 = 13.3 s
latency (cached prefix, TTFT ~0.2 s)                = 0.2 + 12.5       = 12.7 s   (prefill saving is small here)
latency if output cut to 150 tokens                 = 0.8 + 3.75       = 4.55 s   (output length is the big lever)

The lesson from this calculation: for answer-heavy requests, caching mainly saves money; for latency, cut output tokens. For prompt-heavy, short-answer requests (classification over a long document) the balance flips and caching dominates both cost and latency.

Quick diagnosis

Symptom	Likely cause	Fix
Slow first token, fast stream after	long uncached prompt	prompt caching, shorter prompt, retrieval of fewer chunks
Fast first token, long total time	long output	ask for concision, stop sequences, smaller max_tokens
Bill higher than expected on agent runs	context re-sent and re-billed every turn	stable cached prefix, compact tool results
Throughput collapses at high concurrency	KV-cache memory or large prefills crowding decode	fewer long contexts, KV quantization, chunked prefill

The real decision process weighs several concrete factors rather than reflexively reaching for the most capable available model: task complexity — does the task genuinely require the larger model’s deeper reasoning ability, or is it a comparatively simple classification/extraction/formatting task a smaller, cheaper model handles just as well; latency requirements — a user-facing, chat-style feature has a very different acceptable-latency budget than a background batch job processing thousands of records overnight; cost at actual production volume — a marginal quality improvement from a larger model can be economically indefensible once multiplied across real request volume, even if it looked like an obviously “better” choice in a small-scale demo comparison; and a genuine willingness to A/B test or formally evaluate smaller/cheaper models against the task rather than assuming bigger is categorically better without checking. A common, real production pattern worth naming explicitly: routing — sending the bulk of simpler requests to a cheap/fast model, and only escalating to a larger, more expensive model for requests that are actually detected as harder or where the cheaper model’s output looks uncertain/low-confidence.

Each turn appends: the assistant’s tool-call tokens, then the tool-result tokens, then the next assistant message. The context grows monotonically and so does the KV cache (memory) and the prefill cost of anything not yet cached. Practical consequences:

• Prompt caching is doing heavy lifting — the stable prefix (system prompt, tool defs) must stay byte-stable or every turn pays full prefill.
• Tool results are often the bulk of the tokens. Truncate or summarize large tool outputs before they enter context; do not dump a 50k-token file if the agent needs 10 lines.
• Long agent runs eventually hit the window — this is where compaction, sub-agents with fresh context, and externalizing state to files (see Context, long conversations, and attention decay) become necessary rather than optional.
• KV-cache memory per request caps how many agents you can run concurrently on a GPU, independent of compute.

Why the cost grows quadratically without caching

Take a 10-step agent loop with a 5,000-token starting context where every step adds 2,000 tokens (tool call plus result). Each step re-sends the whole context:

ctx, sent = 5000, 0
for step in range(10):
    sent += ctx          # input tokens processed this step
    ctx += 2000          # the tool result and call are appended
print(sent, "input tokens sent;", ctx - 2000, "tokens of unique content in the final request")
# -> 140000 input tokens sent; 23000 tokens of unique content in the final request

Without any caching the loop processes 140,000 input tokens for 23,000 tokens of real content (about 6x). With a perfect prefix cache you pay roughly 23,000 tokens at the full rate plus the rest at the discounted read rate. That is the economic case for append-only history and for keeping tool outputs short: every extra tool-result token is re-read on all later steps.

Agent checklist

1. Freeze the system prompt and tool list (same order, same text) for the whole session.
2. Append only; never rewrite earlier turns. If you must compact, do it once, deliberately.
3. Cap tool output (head/tail, summaries, pagination) before it enters the transcript.
4. Watch cache-read vs cache-write token counts per call; a sudden drop to zero reads means the prefix changed.
5. For many parallel agents sharing one model, budget concurrency by KV memory (see the size calculator above), not only by compute.