Prompt caching

Deep dive

How it works

In: token sequence of a prompt, tenant salt · Out: block table plus the count of cached prefix tokens · State: hash-to-block map, refcounts, LRU of free blocks · Cost: O(prompt tokens) hashing, O(1) per block lookup

1. Tokenize; split into blocks of B tokens (vLLM-style servers; hosted APIs hide B).
2. h_i = H(h_{i-1}, tokens_i, extra), with extra = tenant salt, LoRA id, image hashes. Chaining makes the hash depend on the whole prefix.
3. Walk blocks from the start; stop at the first miss. Matched blocks get their refcount raised and are reused; the rest are prefilled and inserted.
4. Only full blocks are shared. The partial tail is always recomputed.
5. On request end, refcounts drop. Blocks with refcount 0 stay in the map until memory pressure, then the least recently used is evicted, tail before parent.
6. Hosted API: you mark the end of the stable prefix (cache_control, or automatic mode); the provider finds the longest cached prefix at or before it, up to the lookback limit.

[tools][system][doc A][turn1][turn2] | [turn3 new]
 hit hit   hit    hit     hit         prefill only here
change one tool description ⇒ everything to its right misses

Code

use std::collections::{BTreeMap, HashMap};

/// FNV-1a over (parent hash, tokens). Real servers use SHA-256 or xxhash and verify tokens.
fn chain_hash(parent: u64, toks: &[u32]) -> u64 {
    let mut h = 0xcbf29ce484222325u64 ^ parent.rotate_left(17);
    for t in toks {
        for b in t.to_le_bytes() {
            h = (h ^ b as u64).wrapping_mul(0x100000001b3);
        }
    }
    h
}

struct Block {
    hash: Option<u64>, // None: partial or unshared block, never in the map
    parent: u64,
    toks: Vec<u32>,
    refs: u32,
    tick: u64, // key in `evictable` while refs == 0
}

pub struct PrefixCache {
    bs: usize,
    cap: usize,
    blocks: Vec<Block>,
    by_hash: HashMap<u64, usize>,
    free: Vec<usize>,                // never-used or unhashed blocks
    evictable: BTreeMap<u64, usize>, // tick -> block with refs == 0, oldest first
    tick: u64,
}

pub struct Admission { pub blocks: Vec<usize>, pub cached_tokens: usize }

impl PrefixCache {
    pub fn new(block_size: usize, capacity: usize) -> Self {
        PrefixCache {
            bs: block_size, cap: capacity, blocks: Vec::new(), by_hash: HashMap::new(),
            free: Vec::new(), evictable: BTreeMap::new(), tick: 0,
        }
    }

    fn alloc(&mut self) -> Option<usize> {
        if let Some(i) = self.free.pop() { return Some(i); }
        if self.blocks.len() < self.cap {
            self.blocks.push(Block { hash: None, parent: 0, toks: vec![], refs: 0, tick: 0 });
            return Some(self.blocks.len() - 1);
        }
        let (&t, &i) = self.evictable.iter().next()?; // LRU victim
        self.evictable.remove(&t);
        if let Some(h) = self.blocks[i].hash.take() { self.by_hash.remove(&h); }
        Some(i)
    }

    /// Reserve KV blocks for a prompt. Only FULL blocks are shared; None = out of memory.
    pub fn admit(&mut self, salt: u64, prompt: &[u32]) -> Option<Admission> {
        let mut out: Vec<usize> = Vec::new();
        let mut parent = salt; // per-tenant salt seeds the chain: no cross-tenant hits
        let mut hit = true;
        let mut cached = 0;
        for chunk in prompt.chunks(self.bs) {
            let full = chunk.len() == self.bs;
            let h = chain_hash(parent, chunk);
            if hit && full {
                if let Some(&i) = self.by_hash.get(&h) {
                    let b = &self.blocks[i];
                    if b.parent == parent && b.toks == chunk { // guard against hash collisions
                        if b.refs == 0 { self.evictable.remove(&b.tick); }
                        self.blocks[i].refs += 1;
                        out.push(i);
                        cached += self.bs;
                        parent = h;
                        continue;
                    }
                }
            }
            hit = false;
            let Some(i) = self.alloc() else { self.release(&out); return None };
            self.blocks[i] = Block { hash: full.then_some(h), parent, toks: chunk.to_vec(), refs: 1, tick: 0 };
            if full { self.by_hash.insert(h, i); }
            out.push(i);
            parent = h;
        }
        Some(Admission { blocks: out, cached_tokens: cached })
    }

    /// Drop a request's references. Released in reverse so the tail is evicted before its parents.
    pub fn release(&mut self, blocks: &[usize]) {
        for &i in blocks.iter().rev() {
            let b = &mut self.blocks[i];
            b.refs -= 1;
            if b.refs == 0 {
                if b.hash.is_some() {
                    self.tick += 1;
                    b.tick = self.tick;
                    self.evictable.insert(self.tick, i);
                } else {
                    self.free.push(i);
                }
            }
        }
    }
}

admit returns the block table plus cached_tokens; a real server prefills only prompt[cached_tokens..]. Verified by tests: a shared 8-token system prompt hits across requests, a change at token 1 gives 0 hits, a different salt gives 0 hits, and a pool with all blocks pinned returns None.

Complexity and constants

• Lookup: hash each full block once, O(n) in prompt tokens; a few ns per token for a fast hash, negligible next to prefill.
• KV size per token = 2 x layers x KV heads x head dim x bytes. Llama-2-7B shape (32, 32, 128, fp16): 512 KiB per token (computed), so a 10k-token prefix holds about 5 GiB. Grouped-query attention divides this by the group factor.
• Prefill costs about 2 x parameters FLOPs per token (order of); decode is memory-bound. A hit removes prefill compute and time to first token, not decode time.
• Billing break-even (Anthropic multipliers, n requests inside the TTL): cached cost = 1.25 + 0.1(n-1) vs n uncached, so it wins from the 2nd request (1.35 vs 2). With the 1 h TTL (2x write) it wins from the 3rd (2.2 vs 3).

Efficiency

• Cost: a lookup hashes each full block once (O(n) in prompt tokens, a few ns per token, order of). A hit skips prefill (about 2 x parameters FLOPs per token, order of) but not decode. The cache costs memory: 512 KiB per token for the Llama-2-7B shape (computed above). Billing on Anthropic: 0.1x per read token by default, 1.25x per write. Bound: prefill compute versus cache memory capacity.
• Levers:
  • append-only context, stable content first — every turn reuses the previous turn's full prompt — agent loops
  • breakpoint at the end of the last stable block and one at the end of the growing history — stays inside the 20-block lookback (Anthropic docs) — hosted APIs
  • route requests with a shared prefix to one replica — hit rate survives scale-out (OpenAI prompt_cache_key is a routing hint) — multi-replica serving
  • tree-structured reuse (RadixAttention) — up to 6.4x throughput over other systems on prefix-heavy workloads (SGLang paper) — branching prompts, few-shot, multi-turn chat
  • offload cold blocks to host RAM instead of evicting — hit rate survives memory pressure — long, rarely reused prefixes
• Naive → standard → state of the art:
  • resend and re-prefill the whole prompt every call · full prefill cost every turn
  • exact-prefix block cache, ref-counted LRU · prefill only the new suffix
  • radix tree, tiered offload, prefix-aware routing · shared prefixes across requests and replicas

Implementation notes

• Block size trades hit granularity against hash and table overhead; 16 tokens is a common server default (paged KV cache). Hosted APIs round down to their own granularity.
• Never trust the hash alone: store the block's tokens and parent and compare on a hit (as the code does), or use a cryptographic hash such as SHA-256.
• Keep a free queue ordered by last use. Insert a finished request's blocks tail first so deep, request-specific blocks go before the shared system prompt.
• Salt the first block per tenant: timing differences between hit and miss otherwise leak whether another user sent a given prefix.
• Check the usage fields on every call: cache_read_input_tokens, cache_creation_input_tokens, input_tokens (Anthropic; total input is their sum) or input_tokens_details.cached_tokens (OpenAI). A hit rate of 0 means a silent invalidation bug.
• Lifetime counts from the start of the request that wrote or read the entry, so a long streamed response eats TTL.

Pitfalls

• Timestamps, request ids, random ordering of tool lists or JSON keys in the prefix: every request misses.
• Editing a tool definition, toggling thinking or effort parameters, or changing tool_choice/images invalidates the cache from that level on (Anthropic documents which level).
• Compacting or truncating old history rewrites the prefix: you pay a full write and lose the savings. Compact rarely and in batches.
• Prefix shorter than the model's minimum is silently not cached; no error.
• Sending the first parallel requests before the first has finished writing: all of them miss. Warm the cache with one request, then fan out.
• More than 20 blocks of new content after the last hit exceeds the lookback and misses; add an intermediate breakpoint.
• Reading a hit as free: cache reads still cost 0.1x (default) per token and still occupy context.

Variants and alternatives

In production

Anthropic API (explicit breakpoints and automatic mode), OpenAI API (automatic), vLLM automatic prefix caching, SGLang RadixAttention, llama.cpp prompt/slot cache reuse, TensorRT-LLM KV block reuse.

Implementations

Sources

• Anthropic, Prompt caching, API docs. docs
• OpenAI, Prompt caching, API docs. docs
• vLLM project, Automatic Prefix Caching, design docs. docs
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023. paper · code
• Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs, NeurIPS 2024. paper · code
• Gim et al., Prompt Cache: Modular Attention Reuse for Low-Latency Inference, MLSys 2024. paper