Basics
The whole idea first, then the terms the rest of this page uses.
1.1Whole idea
Many requests start with the same text: system prompt, few-shot examples, earlier chat turns. Prefix caching reuses KV blocks already computed for that text, so prefill skips those tokens and time to first token drops.
Chained block hashes skip prefill for shared system prompts, and salts keep tenants apart.
1.2Key concepts
One idea per card, in plain words.
Hashes each full block together with its parent's hash, so a block matches only if everything before it matches.
Caches whole blocks. A partly filled final block runs again.
Keeps finished requests' blocks until memory runs short, then frees the least recently used.
Mixes a tenant secret into the first hash, so one tenant cannot detect another's prompts through timing.
Question
What exactly you must answer, and what to settle before you start.
2.1Question
Your assistant sends a 1,500-token system prompt on every request, followed by user text. Time to first token sits at 900 ms. Cut it without changing the model.
Detailed answer
How it works, and how to build or explain it.
3.1Step by step
The mechanism, in the order you would explain it.
- Hash on arrival
Split the prompt into full blocks and compute the hash chain.
- Walk the chain
Reuse blocks until the first miss. Everything after the miss must run through prefill.
- Share by reference
Hits raise a block's reference count. Requests read the same physical memory.
- Evict least recently used
Finished requests leave their blocks cached and evictable. Active blocks never leave.
- Order the prompt
Put static content first: system text, tools, examples. A timestamp at the top destroys every hit.
3.2Code
Working code for the core of it.
Reusing a shared prompt prefix
Many requests start with the same system prompt, so its KV entries can be reused.
1/** vLLM-style prefix cache: each full block's key chains its parent's hash, its tokens and a salt. */2export class PrefixCache {3 private blocks = new Map<string, true>(); // Map order doubles as LRU order4 private blockTokens: number;5 private capacity: number;6 7 constructor(blockTokens = 16, capacity = 1024) {8 this.blockTokens = blockTokens;9 this.capacity = capacity;10 }11 12 private keys(tokens: number[], salt: string): string[] {13 // At least one token must still run through the model, so never cache the very last one.14 const whole = Math.floor((tokens.length - 1) / this.blockTokens);15 const out: string[] = [];16 let parent = salt;17 for (let b = 0; b < whole; b++) {18 parent = `${parent}|${tokens.slice(b * this.blockTokens, (b + 1) * this.blockTokens).join(",")}`;19 out.push(parent);20 }21 return out;22 }23 24 /** Number of prompt tokens the engine can skip. */25 lookup(tokens: number[], salt = ""): number {26 let hits = 0;27 for (const key of this.keys(tokens, salt)) {28 if (!this.blocks.has(key)) break;29 this.blocks.delete(key); // move to most recently used30 this.blocks.set(key, true);31 hits++;32 }33 return hits * this.blockTokens;34 }35 36 insert(tokens: number[], salt = ""): void {37 for (const key of this.keys(tokens, salt)) {38 this.blocks.delete(key);39 this.blocks.set(key, true);40 if (this.blocks.size > this.capacity) this.blocks.delete(this.blocks.keys().next().value as string);41 }42 }43}parent = `${parent}|...`- Each block's key includes its parent's, so a match means the whole prefix matches.
salt- Keeps tenants apart, because shared prefixes can otherwise leak through timing.
if (!this.blocks.has(key)) break- Stops at the first miss. Later blocks are useless without the earlier ones.
tokens.length - 1- At least one token must run through the model to produce the next one.
Tested by npm run test:modules.
Q&A
What interviewers ask next. Answer out loud, then open.
4.1Interview questions
Why chain the hashes?
Why must one token still run?
What is the security risk?
Extra depth
Edge cases, counterpoints and what to read next.
5.1Edge cases and counterpoints
Includes the strongest argument against this approach.
Show detailsHide details
- Routing
- The cache lives on each replica. Route requests with the same prefix to the same replica, or hits stay low.
- Adapters and images
- Include the LoRA id and image hashes in the block hash, or you serve wrong keys.
- Counterpoint
- Short, varied prompts see few hits. Measure the hit rate before building prefix-aware routing.