Paged KV Cache and Prefix Caching

Every token a model has read leaves behind a small piece of stored data, the KV cache (key-value cache), which the model needs again for every later token. With many users, this memory is the scarcest resource of a server. It decides how many requests can run at once. A server that wastes it serves fewer people, and a server that recomputes the same prompt again and again wastes arithmetic too.

This lesson builds the memory manager of an inference server step by step. It starts with the simplest design and shows its two kinds of waste. It then introduces blocks, which remove that waste, and the bookkeeping that lets many requests share blocks: block tables, reference counts, and copy-on-write. After that it shows how a server recognizes that a new prompt starts with text it has seen before, and reuses the stored work. That second idea is called prefix caching.

After this lesson, you can explain why vLLM stores KV in 16-token blocks, predict which part of a prompt a server will find in its cache, lay out prompts so that the cache works, and read llama-server's cache counters.

The lesson uses the KV bytes per token from Memory Math, the scheduler and preemption from Batching and Scheduling, and the prompt-cache endpoints of llama-server: Endpoints, Slots, and Prompt Cache. A quick reminder of the key terms: the prefill phase is where the model reads a whole prompt, and its result is the KV cache; the decode phase produces new tokens one by one and adds one entry to the KV cache for each.

vLLM facts come from the 0.30.0 source (vllm/v1/core/block_pool.py, kv_cache_utils.py, kv_cache_manager.py), SGLang facts from srt/mem_cache/radix_cache.py in 0.5.21, and llama.cpp facts from commit 0c1e57098 and from real runs on tiny models with random weights.

Example 1: contiguous KV allocation and fragmentation

The problem. A server must give each request some memory for its KV cache. The obvious design gives each request one continuous stretch of memory. This has a hidden cost, and the example measures it.

The idea. The output length of a request is unknown when it starts. The model might stop after 20 tokens or run to the maximum. With one continuous region per request, the server must reserve space for the worst case, the maximum length. Most requests then use only part of what they reserved. And when requests finish and leave, the free memory is left in pieces between the regions that are still in use. A new request needs one piece that is big enough, and no single piece may be.

The program models a pool of 8,192 token slots. One slot holds the keys and values of one token in every layer. Part one reserves 2,048 slots per request, for requests that actually reach only 300 to 1,200 tokens. Part two reserves exactly prompt + max_tokens per request with a first-fit allocator (it uses the lowest gap that is large enough), lets two requests finish, and then tries to place a new request. Look at how much of the pool really stores KV in part one, and at the gaps in part two.

import java.util.ArrayList;
import java.util.List;

public class ContiguousKv {
    record Region(String id, int start, int size) {}

    // first-fit: the lowest free gap that is large enough
    static Region allocate(List<Region> used, String id, int size, int pool) {
        int pos = 0;
        for (Region r : used) {
            if (r.start() - pos >= size) break;
            pos = r.start() + r.size();
        }
        if (pos + size > pool) return null;
        Region region = new Region(id, pos, size);
        used.add(region);
        used.sort((a, b) -> Integer.compare(a.start(), b.start()));
        return region;
    }

    public static void main(String[] args) {
        int pool = 8192, maxLen = 2048;
        int[] actual = {300, 1200, 150, 700, 500};
        List<Region> used = new ArrayList<>();
        int stored = 0;
        for (int i = 0; i < actual.length; i++) {
            Region r = allocate(used, "r" + i, maxLen, pool);        // reserve the maximum length
            System.out.println("r" + i + " (" + actual[i] + " tokens): " + (r == null ? "rejected, no 2048-slot region" : "reserved [" + r.start() + ", " + (r.start() + maxLen) + ")"));
            if (r != null) stored += actual[i];
        }
        System.out.printf("reserved %d of %d slots, holding %d tokens: %.1f%% of the pool stores KV%n", used.size() * maxLen, pool, stored, 100.0 * stored / pool);

        used.clear();                                                // now reserve exactly prompt + max_tokens
        int[] sizes = {1500, 600, 1800, 400, 2000, 1000};
        for (int i = 0; i < sizes.length; i++) allocate(used, "q" + i, sizes[i], pool);
        used.removeIf(r -> r.id().equals("q1") || r.id().equals("q3"));   // two requests finish
        int free = pool - used.stream().mapToInt(Region::size).sum();
        System.out.println("after q1 and q3 finish: free slots " + free + " in gaps " + gaps(used, pool));
        System.out.println("request of 900 slots: " + (allocate(used, "q6", 900, pool) == null ? "rejected" : "placed"));
    }

    static List<Integer> gaps(List<Region> used, int pool) {
        List<Integer> g = new ArrayList<>();
        int pos = 0;
        for (Region r : used) { if (r.start() > pos) g.add(r.start() - pos); pos = r.start() + r.size(); }
        if (pool > pos) g.add(pool - pos);
        return g;
    }
}

r0 (300 tokens): reserved [0, 2048)
r1 (1200 tokens): reserved [2048, 4096)
r2 (150 tokens): reserved [4096, 6144)
r3 (700 tokens): reserved [6144, 8192)
r4 (500 tokens): rejected, no 2048-slot region
reserved 8192 of 8192 slots, holding 2350 tokens: 28.7% of the pool stores KV
after q1 and q3 finish: free slots 1892 in gaps [600, 400, 892]
request of 900 slots: rejected

In part one, four requests fill the pool, because 4 x 2,048 = 8,192. The fifth request is rejected, although the four stored only 2,350 tokens. Only 28.7% of the pool holds keys and values. The rest is reserved and unused. This waste inside a reservation is internal fragmentation.

In part two, reservations are tighter, but another problem appears. After q1 (600 slots) and q3 (400 slots) finish, 1,892 slots are free, but in three gaps of 600, 400, and 892. A request for 900 slots is rejected because no single gap is large enough. Free memory that is split into gaps that are each too small is external fragmentation. Moving live regions to close the gaps would mean copying gigabytes of KV on the GPU while requests are running, which is too slow.

The PagedAttention paper (Kwon et al., 2023), which introduced vLLM, measured this problem in the serving systems of its time. It reported that most of their KV memory did not hold token states. Both kinds of waste come from the same requirement: one sequence must occupy one continuous range of memory. The next example removes that requirement.

Example 2: 16-token blocks and per-sequence block tables

The problem. The requirement of one continuous range causes both kinds of waste. If a sequence could live in memory pieces that are not next to each other, any free piece would be usable.

The idea. The solution comes from operating systems. A program sees continuous memory, but the operating system stores it in fixed-size pages scattered anywhere in RAM, and a page table translates addresses. Paged KV cache does the same for the KV cache. It divides KV memory into blocks of a fixed number of tokens. In vLLM 0.30.0, CacheConfig.DEFAULT_BLOCK_SIZE is 16. An attention backend that prefers another size changes it, with the log line Setting kv cache block size to %d for %s backend. Each sequence gets a block table: the list of physical block ids that hold its tokens, in order. The position of a block in the table is its logical number, and the id stored there is its physical location.

The program gives two sequences blocks from a free list in arbitrary order and translates token positions to physical locations. Look at how the block tables are not in ascending order, and how a token position turns into a physical slot.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class BlockTables {
    static final int BLOCK = 16;

    public static void main(String[] args) {
        Deque<Integer> free = new ArrayDeque<>(List.of(7, 2, 9, 4, 0, 5, 11, 3));   // free physical blocks
        Map<String, List<Integer>> tables = new LinkedHashMap<>();
        Map<String, Integer> lengths = Map.of("A", 37, "B", 20);
        for (String seq : List.of("A", "B")) {
            List<Integer> table = new ArrayList<>();
            int blocks = (lengths.get(seq) + BLOCK - 1) / BLOCK;
            for (int b = 0; b < blocks; b++) table.add(free.poll());
            tables.put(seq, table);
            System.out.println("sequence " + seq + ": " + lengths.get(seq) + " tokens, block table " + table);
        }
        for (Object[] q : new Object[][] {{"A", 0}, {"A", 15}, {"A", 16}, {"A", 36}, {"B", 19}}) {
            String seq = (String) q[0];
            int pos = (int) q[1];
            int logical = pos / BLOCK, offset = pos % BLOCK;
            int physical = tables.get(seq).get(logical);
            System.out.printf("%s token %2d -> logical block %d, offset %2d -> physical block %2d, slot %3d%n",
                    seq, pos, logical, offset, physical, physical * BLOCK + offset);
        }
        System.out.println("free blocks left: " + free);
    }
}

sequence A: 37 tokens, block table [7, 2, 9]
sequence B: 20 tokens, block table [4, 0]
A token  0 -> logical block 0, offset  0 -> physical block  7, slot 112
A token 15 -> logical block 0, offset 15 -> physical block  7, slot 127
A token 16 -> logical block 1, offset  0 -> physical block  2, slot  32
A token 36 -> logical block 2, offset  4 -> physical block  9, slot 148
B token 19 -> logical block 1, offset  3 -> physical block  0, slot   3
free blocks left: [5, 11, 3]

Sequence A has 37 tokens, so it needs ceil(37 / 16) = 3 blocks. It receives physical blocks 7, 2, and 9, the first three on the free list. Sequence B (20 tokens) receives blocks 4 and 0. The blocks of a sequence are not adjacent, and they do not need to be.

Each position translates in two steps. Take token 36 of A. Its logical block is 36 / 16 = 2 (integer division), and its offset inside the block is 36 mod 16 = 4. The block table maps logical block 2 to physical block 9. The slot is 9 x 16 + 4 = 148, the index of that token's entry in the whole KV pool. vLLM computes the same value, called the slot mapping, in vllm/v1/worker/block_table.py (slot_ids = block_numbers * block_size + slot_offsets). The model writes each new key and value at its slot. The attention kernel (the GPU program that computes attention) receives the block table so it can find all of a sequence's keys. This is the "PagedAttention" kernel of the paper: attention that reads keys and values through a block table instead of from one continuous array.

Tokens 15 and 16 of A sit in different physical blocks (7 and 2), although they are neighbours in the sequence. The kernel handles the jump between blocks. The cost is one extra lookup per block, which is small next to reading 16 tokens of keys and values.

Example 3: allocation from a free list, and utilization

The problem. Blocks should remove the waste of Example 1. This example measures how much they remove.

The idea. With blocks, a sequence takes one block when it needs one, from a free list of unused blocks, and it returns all its blocks when it finishes. Nothing is reserved in advance. Any free block fits any sequence, so external fragmentation disappears. The only waste left is the unused part of each sequence's last block. A sequence of 17 tokens uses 2 blocks and wastes 15 slots. A sequence of 32 tokens fits 2 blocks exactly and wastes none.

The program generates 40 requests with seeded lengths between 100 and 1,500 tokens. It fills an 8,192-slot pool in two ways: 2,048 reserved slots per request, and 16-token blocks allocated on demand. Compare the number of requests and the percentage of the pool that stores tokens.

import java.util.Locale;
import java.util.Random;

public class PagedUtilization {
    public static void main(String[] args) {
        int pool = 8192, block = 16, maxLen = 2048;
        Random random = new Random(5);
        int[] lengths = new int[40];
        for (int i = 0; i < lengths.length; i++) lengths[i] = 100 + random.nextInt(1400);

        int contiguous = 0, contiguousTokens = 0;                       // reserve maxLen per request
        while (contiguous < lengths.length && (contiguous + 1) * maxLen <= pool) contiguousTokens += lengths[contiguous++];

        int freeBlocks = pool / block, paged = 0, pagedTokens = 0, wasted = 0;   // allocate blocks on demand
        while (paged < lengths.length) {
            int need = (lengths[paged] + block - 1) / block;
            if (need > freeBlocks) break;
            freeBlocks -= need;
            pagedTokens += lengths[paged];
            wasted += need * block - lengths[paged];
            paged++;
        }
        System.out.printf(Locale.ROOT, "contiguous, 2048 reserved each: %2d requests, %5d tokens stored, %.1f%% of pool%n",
                contiguous, contiguousTokens, 100.0 * contiguousTokens / pool);
        System.out.printf(Locale.ROOT, "paged, 16-token blocks:         %2d requests, %5d tokens stored, %.1f%% of pool%n",
                paged, pagedTokens, 100.0 * pagedTokens / pool);
        System.out.printf(Locale.ROOT, "paged waste: %d slots in last blocks = %.1f per request (at most 15)%n",
                wasted, (double) wasted / paged);
    }
}

contiguous, 2048 reserved each:  4 requests,  3077 tokens stored, 37.6% of pool
paged, 16-token blocks:          8 requests,  7533 tokens stored, 92.0% of pool
paged waste: 51 slots in last blocks = 6.4 per request (at most 15)

With reservations, 4 requests fit, and the pool stores 3,077 tokens (37.6%). With blocks, 8 requests fit, and the pool stores 7,533 tokens (92.0%). The remaining 8% is the free space that could not fit the ninth request, plus the waste in last blocks: 51 slots over 8 requests, which is 6.4 per request. The waste per request is at most 15 slots (a sequence that is one token into a new block), whatever its length.

Twice the number of concurrent requests means about twice the decode throughput, by the arithmetic of Batching and Scheduling, Example 1, because the batch was limited by memory. That is the practical result of paging.

The block size is a trade-off. Smaller blocks waste less in the last block and match prefixes more finely (Example 5). But the block tables grow, and each kernel lookup covers fewer tokens. vLLM sets the default per platform and attention backend. Memory Math, Example 13, computes the number of blocks from the memory budget, and the vLLM startup log reports the cache size in tokens.

Example 4: reference counts and copy-on-write for parallel sampling

The problem. Sometimes several sequences start with identical content. A request with n = 3 asks for three different completions of one prompt, which is called parallel sampling. Storing the prompt's KV three times wastes memory, because the three copies are identical.

The idea. The three sequences can point to the same blocks. This creates a new problem: when one sequence changes a shared block, the others must not see the change. Two rules solve it. First, each block gets a reference count: the number of block tables that contain it. A block with a count above 1 must not be modified, because another sequence reads it. Second, when a sequence needs to write into a shared block, it first makes its own copy. This is copy-on-write: sharing is free, and copying happens only at the moment of a write.

The program forks a 40-token prompt (2 full blocks and a third block with 8 tokens) into three samples. Then each sample writes its first generated token at position 40, which falls into the shared third block. Watch the reference counts before and after.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CopyOnWrite {
    static final int BLOCK = 16;
    static final Map<Integer, Integer> refCount = new HashMap<>();
    static int nextBlock = 0;

    static int newBlock() { refCount.put(nextBlock, 1); return nextBlock++; }

    public static void main(String[] args) {
        int promptLen = 40;                                            // 2 full blocks + 8 tokens in a third
        List<Integer> prompt = new ArrayList<>();
        for (int i = 0; i < (promptLen + BLOCK - 1) / BLOCK; i++) prompt.add(newBlock());
        List<List<Integer>> samples = new ArrayList<>();
        for (int s = 0; s < 3; s++) {                                  // n = 3: fork the table, share the blocks
            samples.add(new ArrayList<>(prompt));
            if (s > 0) for (int b : prompt) refCount.merge(b, 1, Integer::sum);
        }
        System.out.println("after fork: tables " + samples + ", ref counts " + refCount);

        int last = prompt.size() - 1;
        for (int s = 0; s < 3; s++) {                                  // each sample writes its first token at position 40
            int b = samples.get(s).get(last);
            if (refCount.get(b) > 1) {                                 // shared: copy before writing
                int copy = newBlock();
                refCount.merge(b, -1, Integer::sum);
                samples.get(s).set(last, copy);
                System.out.println("sample " + s + " writes into shared block " + b + ": copy to block " + copy + " (copies 8 token entries)");
            } else {
                System.out.println("sample " + s + " writes into block " + b + ": ref count 1, written in place");
            }
        }
        System.out.println("tables " + samples + ", ref counts " + refCount);
        System.out.println("blocks used: " + refCount.size() + " instead of " + 3 * prompt.size() + " for three private copies");
    }
}

after fork: tables [[0, 1, 2], [0, 1, 2], [0, 1, 2]], ref counts {0=3, 1=3, 2=3}
sample 0 writes into shared block 2: copy to block 3 (copies 8 token entries)
sample 1 writes into shared block 2: copy to block 4 (copies 8 token entries)
sample 2 writes into block 2: ref count 1, written in place
tables [[0, 1, 3], [0, 1, 4], [0, 1, 2]], ref counts {0=3, 1=3, 2=1, 3=1, 4=1}
blocks used: 5 instead of 9 for three private copies

After the fork, the three block tables are identical, [0, 1, 2], and each block has a reference count of 3. One prompt's worth of memory serves three sequences.

The first generated token goes to position 40, which is offset 8 of block 2. Sample 0 finds block 2 shared, so it allocates block 3, copies the 8 existing token entries, decreases block 2's count to 2, and writes into its copy. Sample 1 does the same with block 4. Sample 2 now finds block 2 with a count of 1. It is the only user, so it writes in place without copying.

The final tables share blocks 0 and 1 (count 3) and differ only in the last block. Five blocks are in use instead of nine for three private copies. The full blocks never need copying, because they are never written again. Only the partially filled block where generation continues is copied. The PagedAttention paper uses the same mechanism for parallel sampling and for beam search, where candidates also share long prefixes.

vLLM 0.30.0 reaches the same sharing by a different route. The engine splits a request with n > 1 into child requests (ParentRequest in vllm/v1/engine/parallel_sampling.py). Each child is scheduled as its own request, and its full prompt blocks are found in the prefix cache of Example 6, so the children hold the same physical blocks with increased reference counts. The partial last block is not shared. Each child computes it, in the way each sample here computed a copy.

Example 5: prefix sharing between two requests with the same system prompt

The problem. Parallel sampling shares a prompt inside one request. In practice, many different requests start with the same text. Every request to a coding agent begins with the same system prompt and the same tool descriptions. Processing that text again for each request wastes arithmetic and memory.

The idea. Prefix caching shares across requests. A server keeps the blocks of finished prompts, and gives them to any later request whose prompt starts with the same tokens. The reuse has one strict rule. A full block is reused only when the whole prefix up to and including that block matches, and only while every earlier block also matched. The reason is that the KV of a token depends on all the tokens before it. If an earlier token differs, a later block with the same tokens holds different values.

The program admits two requests that start with the same 70-token system prompt, followed by different questions (20 and 33 tokens). It prints the block table of each request and how many tokens were reused.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SharedSystemPrompt {
    static final int BLOCK = 16;
    static final Map<String, Integer> cachedBlockByContent = new HashMap<>();   // full-block content -> block id
    static final Map<Integer, Integer> refCount = new HashMap<>();
    static int nextBlock = 0;

    static List<Integer> admit(String name, int[] tokens) {
        List<Integer> table = new ArrayList<>();
        int reused = 0;
        StringBuilder prefix = new StringBuilder();
        for (int start = 0; start < tokens.length; start += BLOCK) {
            int end = Math.min(start + BLOCK, tokens.length);
            for (int i = start; i < end; i++) prefix.append(tokens[i]).append(',');
            String key = prefix.toString();                           // the whole prefix up to this block
            Integer hit = end - start == BLOCK && reused == start ? cachedBlockByContent.get(key) : null;
            int b = hit != null ? hit : nextBlock++;
            refCount.merge(b, 1, Integer::sum);
            if (hit != null) reused = end;
            else if (end - start == BLOCK) cachedBlockByContent.put(key, b);
            table.add(b);
        }
        System.out.println(name + ": " + tokens.length + " tokens, table " + table + ", reused " + reused + " tokens, computed " + (tokens.length - reused));
        return table;
    }

    static int[] prompt(int system, int question, int seed) {
        int[] t = new int[system + question];
        for (int i = 0; i < system; i++) t[i] = 1000 + i;
        for (int i = 0; i < question; i++) t[system + i] = seed + i;
        return t;
    }

    public static void main(String[] args) {
        admit("request 1", prompt(70, 20, 5000));
        admit("request 2", prompt(70, 33, 6000));
        System.out.println("ref counts " + refCount);
        System.out.println("blocks in use " + refCount.size() + " (without sharing: " + (6 + 7) + ")");
    }
}

request 1: 90 tokens, table [0, 1, 2, 3, 4, 5], reused 0 tokens, computed 90
request 2: 103 tokens, table [0, 1, 2, 3, 6, 7, 8], reused 64 tokens, computed 39
ref counts {0=2, 1=2, 2=2, 3=2, 4=1, 5=1, 6=1, 7=1, 8=1}
blocks in use 9 (without sharing: 13)

Request 1 finds nothing in the cache and receives blocks 0 to 5 for its 90 tokens. Its full blocks (0 to 4) are registered in the cache under their prefixes. Block 5 is partly filled, so it is not registered.

Request 2 has 103 tokens. Its first four blocks (tokens 0 to 63) contain only system-prompt tokens, so their prefixes equal request 1's, and it receives blocks 0, 1, 2, and 3 again. Block 4 of request 2 holds tokens 64 to 79: the last 6 system-prompt tokens and the first 10 question tokens. The question tokens differ from request 1's, so that block is new, and so is everything after it. Request 2 reuses 64 tokens and computes 39.

The reference counts show the sharing: blocks 0 to 3 have a count of 2, and the others have a count of 1. Nine blocks are in use instead of 13. The saving is double. There are 4 fewer blocks of memory, and 64 fewer tokens of prefill arithmetic, which shortens request 2's time to first token (TTFT).

The 6 system-prompt tokens in block 4 are not reused, because a block is matched only as a whole. A system prompt that ends on a block boundary, or a smaller block size, would share them too.

Example 6: hash-chained block hashes

The problem. Example 5 used the whole prefix text as the key to find a block. A real prompt can have thousands of tokens, so such a key would be huge. The server needs a short key, and the key must still identify the whole prefix.

The idea. A hash is a short fixed-size fingerprint of some data. Equal data always gives an equal hash, and different data gives a different hash with overwhelming probability. vLLM computes a block hash for each full block from three inputs: the hash of the previous block, the token ids of this block, and extra keys (a LoRA adapter, multimodal inputs, a per-request cache_salt). The function hash_block_tokens in vllm/v1/core/kv_cache_utils.py returns hash_function((parent_block_hash, curr_block_token_ids_tuple, extra_keys)). The first block uses a fixed seed value, NONE_HASH, as its parent. Because each hash includes the previous one, the hashes form a chain, and the hash of a block identifies the whole prefix up to that block, not only the block itself.

The program builds such a chain with SHA-256 (vLLM's default, --prefix-caching-hash-algo sha256) over 4-token blocks and prints the first 4 bytes of each hash. It builds the chain for a base sequence, for a sequence with a token changed in block 2, for a sequence with a token changed in block 0, and for the base sequence with a cache salt.

import java.nio.ByteBuffer;
import java.security.MessageDigest;
import java.util.ArrayList;
import java.util.HexFormat;
import java.util.List;

public class BlockHashChain {
    static final int BLOCK = 4;

    // hash(parent hash, this block's token ids, extra key), like vLLM's hash_block_tokens
    static byte[] hash(byte[] parent, int[] tokens, int from, String extraKey) throws Exception {
        MessageDigest sha = MessageDigest.getInstance("SHA-256");
        sha.update(parent);
        ByteBuffer buf = ByteBuffer.allocate(4 * BLOCK);
        for (int i = from; i < from + BLOCK; i++) buf.putInt(tokens[i]);
        sha.update(buf.array());
        if (extraKey != null) sha.update(extraKey.getBytes());
        return sha.digest();
    }

    static List<String> chain(int[] tokens, String extraKey) throws Exception {
        List<String> out = new ArrayList<>();
        byte[] parent = MessageDigest.getInstance("SHA-256").digest("NONE".getBytes());   // fixed seed for block 0
        for (int start = 0; start + BLOCK <= tokens.length; start += BLOCK) {             // full blocks only
            parent = hash(parent, tokens, start, extraKey);
            out.add(HexFormat.of().formatHex(parent, 0, 4));
        }
        return out;
    }

    public static void main(String[] args) throws Exception {
        int[] base = {11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42};
        int[] lateEdit = base.clone();
        lateEdit[9] = 99;                                              // change a token in block 2
        int[] earlyEdit = base.clone();
        earlyEdit[1] = 99;                                             // change a token in block 0
        System.out.println("base        " + chain(base, null));
        System.out.println("late edit   " + chain(lateEdit, null));
        System.out.println("early edit  " + chain(earlyEdit, null));
        System.out.println("cache salt  " + chain(base, "tenant-b"));
        System.out.println("full blocks: " + base.length / BLOCK + " of " + base.length + " tokens; the last " + base.length % BLOCK + " tokens are not hashed");
    }
}

base        [6cfd527e, 9f569157, e0297480]
late edit   [6cfd527e, 9f569157, 6417173d]
early edit  [f896424a, becafd48, 11e3be4a]
cache salt  [6057b827, 793c15f6, 099ad05f]
full blocks: 3 of 14 tokens; the last 2 tokens are not hashed

The base sequence of 14 tokens has 3 full blocks and 3 hashes. The last 2 tokens form a partial block, which is not hashed, because its content will still change as tokens are appended.

The late edit changes token 9, inside block 2. Blocks 0 and 1 keep their hashes (6cfd527e, 9f569157), so a cache lookup still finds them, and only block 2's hash changes. The early edit changes token 1, inside block 0, and all three hashes change, because each later hash includes the changed one. A cache lookup for the early-edited sequence finds nothing, even though blocks 1 and 2 contain the same tokens as before.

This chaining is what makes a hash safe as a prefix key. Two blocks with the same tokens at different places in different prompts have different hashes. This is correct, because their keys and values differ too: attention made each token's KV depend on everything before it.

The salted chain differs from the first block on. vLLM accepts cache_salt in a request so that requests from one tenant never share cached blocks with another tenant's. Without it, a client could measure response times to learn whether another user sent a given prompt, because a cache hit is faster (Serving with vLLM, Example 8).

Two details of vLLM's lookup follow from the source:

• A request never hits on its entire prompt. get_computed_blocks limits the hit to prompt_length - 1 tokens, because the last prompt token must be computed to produce the logits (the model's scores for the next token). Since hits are whole blocks, a prompt of exactly 64 tokens can reuse at most 48. The source comment notes that this "can trigger recomputation of an entire block".
• With a non-cryptographic hash such as xxhash, vLLM picks a random NONE_HASH seed per process unless PYTHONHASHSEED is set. Block hashes then differ between server processes.

Example 7: LRU eviction of cached blocks

The problem. The cache cannot grow forever. Cached blocks of finished requests sit in memory that new requests also need. When memory runs out, the server must decide which cached block to give up.

The idea. A finished request's blocks are not erased. They stay in the cache with their hashes, as free blocks that still hold valid KV. When memory is needed, the allocator takes free blocks in an order that evicts the least useful content first. The usual rule is LRU (least recently used): the block that was used longest ago goes first, on the guess that it is the least likely to be needed again.

vLLM keeps one free queue (FreeKVCacheBlockQueue, a doubly linked list). Allocation takes blocks from the front. A freed cached block goes to the back, so the front always holds the least recently used blocks. A request's blocks are freed in reverse order, so the last block of a prefix chain is evicted before its first block. This order is deliberate: the beginning of a prompt is shared by more future requests than its end. A cache hit on a free block removes it from the queue (touch), so it is not evicted while in use.

The program follows four requests through a pool of 6 blocks. Request A and B finish, C reuses part of A, and D needs three new blocks and forces evictions. Watch the order of the free queue after each step.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class LruBlockEviction {
    static final LinkedList<Integer> freeQueue = new LinkedList<>(List.of(0, 1, 2, 3, 4, 5));
    static final Map<String, Integer> cache = new HashMap<>();      // block hash -> block id
    static final Map<Integer, String> hashOf = new HashMap<>();
    static final Map<Integer, Integer> refCnt = new HashMap<>();

    static List<Integer> request(String name, List<String> blockHashes) {
        List<Integer> table = new ArrayList<>();
        StringBuilder log = new StringBuilder(name + ":");
        boolean prefix = true;
        for (String h : blockHashes) {
            Integer b = prefix ? cache.get(h) : null;
            if (b != null) {                                         // hit: touch removes it from the free queue
                if (refCnt.getOrDefault(b, 0) == 0) freeQueue.remove(b);
                log.append(" hit ").append(h).append("->").append(b);
            } else {
                prefix = false;
                b = freeQueue.removeFirst();                         // the front is the LRU block
                String old = hashOf.remove(b);
                if (old != null) { cache.remove(old); log.append(" evict ").append(old).append(" from ").append(b).append(','); }
                log.append(" new ").append(h).append("->").append(b);
                cache.put(h, b);
                hashOf.put(b, h);
            }
            refCnt.merge(b, 1, Integer::sum);
            table.add(b);
        }
        System.out.println(log);
        return table;
    }

    static void finish(List<Integer> table) {                        // free in reverse: the chain's tail is evicted first
        for (int i = table.size() - 1; i >= 0; i--) {
            int b = table.get(i);
            if (refCnt.merge(b, -1, Integer::sum) == 0) freeQueue.addLast(b);
        }
        System.out.println("  free queue (front = evicted first): " + freeQueue);
    }

    public static void main(String[] args) {
        finish(request("A", List.of("a1", "a2", "a3")));
        finish(request("B", List.of("b1", "b2")));
        List<Integer> c = request("C", List.of("a1", "a2", "c3"));
        request("D", List.of("d1", "d2", "d3"));
        finish(c);
    }
}

A: new a1->0 new a2->1 new a3->2
  free queue (front = evicted first): [3, 4, 5, 2, 1, 0]
B: new b1->3 new b2->4
  free queue (front = evicted first): [5, 2, 1, 0, 4, 3]
C: hit a1->0 hit a2->1 new c3->5
D: evict a3 from 2, new d1->2 evict b2 from 4, new d2->4 evict b1 from 3, new d3->3
  free queue (front = evicted first): [5, 1, 0]

Request A takes blocks 0, 1, 2 for hashes a1, a2, a3 and finishes. Its blocks go to the back of the queue in reverse order, 2, 1, 0, behind the never-used blocks 3, 4, 5. Request B takes 3 and 4 from the front and frees them in reverse order, so the queue is [5, 2, 1, 0, 4, 3].

Request C starts with A's first two blocks. The lookup finds a1 in block 0 and a2 in block 1. Both are free with a count of 0, so they are removed from the queue and reused without computation. C's third block is new and takes block 5 from the front.

Request D shares nothing and needs 3 blocks. The queue front is now 2, 4, 3. Block 2 holds a3, which was freed before B's blocks, so it is the least recently used. D evicts a3, then b2, then b1, and drops their hashes from the cache. b2 goes before b1 because of the reverse-order free. The tail of a chain is evicted first, which keeps the shared beginnings of prompts, the most reusable part, in the cache longest.

When C finishes, its blocks return to the back in reverse order, 5, 1, 0. Blocks 0 and 1 (a1, a2) were used twice, and they are again the most recently used. vLLM's free_blocks adds one rule that the program leaves out: blocks without a hash (partial blocks) go to the front of the queue, because they can never produce a cache hit and are the cheapest to reuse.

Example 8: a radix tree for prefix matching

The problem. The hash table of vLLM finds prefixes in whole blocks. Another design finds them token by token, with a data structure made for prefixes.

The idea. A radix tree is a tree in which each edge holds a run of several tokens, instead of one token. Prompts that share a prefix share the nodes of that prefix, so the shared text is stored once. A request walks down from the root as far as its tokens match. If the match stops inside a run, the node is split into two nodes at the point of difference.

SGLang stores cached prefixes in such a tree (RadixCache in srt/mem_cache/radix_cache.py). Each node holds the token ids of its run and the KV locations for those tokens. Each node also has a lock reference count for running requests (inc_lock_ref walks from a node up to the root) and a last-access time. Eviction (evict) removes leaves with a lock count of 0, in the order of an eviction policy, LRU by default. A running request locks its path so that its KV cannot be evicted while it is in use. The Engine Landscape and How Ollama Works, Example 7, matched prefixes with an uncompressed tree of single tokens. This program adds runs, splits, locks, and eviction.

The program inserts three prompts, prints the tree, matches a new request, locks its path, evicts one leaf, and prints the tree again. In the printed tree, indentation shows depth, and t= is the last access time.

import java.util.ArrayList;
import java.util.List;

public class RadixCache {
    static class Node {
        List<Integer> key = new ArrayList<>();                       // the token run on the edge into this node
        List<Node> children = new ArrayList<>();
        Node parent;
        int lockRef;
        long lastAccess;
    }

    static final Node root = new Node();
    static long clock = 0;

    static int common(List<Integer> a, List<Integer> b) { int i = 0; while (i < a.size() && i < b.size() && a.get(i).equals(b.get(i))) i++; return i; }

    // returns the deepest node matched; splits a node when the match ends inside its run
    static Node match(List<Integer> tokens, int[] matched) {
        Node node = root;
        int pos = 0;
        clock++;
        while (pos < tokens.size()) {
            Node next = null;
            for (Node c : node.children) if (c.key.get(0).equals(tokens.get(pos))) next = c;
            if (next == null) break;
            int n = common(next.key, tokens.subList(pos, tokens.size()));
            if (n < next.key.size()) next = split(next, n);
            next.lastAccess = clock;
            pos += n;
            node = next;
        }
        matched[0] = pos;
        return node;
    }

    static Node split(Node child, int at) {
        Node mid = new Node();
        mid.key = new ArrayList<>(child.key.subList(0, at));
        mid.parent = child.parent;
        mid.lockRef = child.lockRef;
        child.parent.children.set(child.parent.children.indexOf(child), mid);
        child.key = new ArrayList<>(child.key.subList(at, child.key.size()));
        child.parent = mid;
        mid.children.add(child);
        return mid;
    }

    static void insert(List<Integer> tokens) {
        int[] m = new int[1];
        Node node = match(tokens, m);
        if (m[0] == tokens.size()) return;
        Node leaf = new Node();
        leaf.key = new ArrayList<>(tokens.subList(m[0], tokens.size()));
        leaf.parent = node;
        leaf.lastAccess = clock;
        node.children.add(leaf);
    }

    static void print(Node n, String indent) {
        for (Node c : n.children) {
            System.out.println(indent + c.key + (c.lockRef > 0 ? " locked" : "") + " t=" + c.lastAccess);
            print(c, indent + "  ");
        }
    }

    static int evictOneLeaf() {                                      // the least recently used leaf without a lock
        Node best = null;
        List<Node> stack = new ArrayList<>(root.children);
        while (!stack.isEmpty()) {
            Node n = stack.remove(stack.size() - 1);
            stack.addAll(n.children);
            if (n.children.isEmpty() && n.lockRef == 0 && (best == null || n.lastAccess < best.lastAccess)) best = n;
        }
        best.parent.children.remove(best);
        return best.key.size();
    }

    public static void main(String[] args) {
        insert(List.of(1, 2, 3, 4, 5, 6, 10, 11));                   // system prompt 1..6 + question A
        insert(List.of(1, 2, 3, 4, 5, 6, 20, 21, 22));               // same system prompt + question B
        insert(List.of(1, 2, 3, 4, 5, 6, 10, 11, 30, 31));           // turn 2 of conversation A
        print(root, "");
        int[] m = new int[1];
        Node hit = match(List.of(1, 2, 3, 4, 5, 6, 20, 21, 22, 40), m);
        System.out.println("new request matches " + m[0] + " tokens");
        for (Node n = hit; n != root; n = n.parent) n.lockRef++;     // a running request locks its path
        System.out.println("evicted a leaf of " + evictOneLeaf() + " tokens");
        print(root, "");
    }
}

[1, 2, 3, 4, 5, 6] t=3
  [10, 11] t=3
    [30, 31] t=3
  [20, 21, 22] t=2
new request matches 9 tokens
evicted a leaf of 2 tokens
[1, 2, 3, 4, 5, 6] locked t=4
  [10, 11] t=3
  [20, 21, 22] locked t=4

The first prompt creates one leaf with all 8 tokens. The second prompt shares 6 tokens and then differs, so the leaf splits at 6. The result is a node [1..6] with two children: [10, 11] from the first prompt and [20, 21, 22] from the second. The third prompt continues the first conversation, so it walks [1..6] and [10, 11] and adds a leaf [30, 31]. The tree stores 13 token entries for 27 prompt tokens.

The printed t= values are access times. The third insert touched its whole path at time 3. The [20, 21, 22] branch was last used at time 2.

A new request with 10 tokens matches 9: the system prompt and question B, which is the whole [20, 21, 22] run. The server would compute only 1 token. The request is running, so its path is locked: [1..6] and [20, 21, 22] get a lock count of 1. Eviction then looks for leaves with a lock count of 0 and removes the least recently used one, [30, 31] (2 tokens). It cannot remove [20, 21, 22], even though that leaf is older, because a running request needs it.

The radix tree and vLLM's hash chain give the same reuse at different granularity and cost. The tree matches at token granularity (with a page size of 1), so request 2 of Example 5 would reuse all 70 system-prompt tokens instead of 64. The hash table matches whole blocks, but finds each block with one hash lookup. SGLang's match_prefix docstring adds that entries with different extra_key values (LoRA adapters, salts) never share nodes. This is the same isolation that vLLM's extra keys give.

Example 9: prompt layout and cache hit rates

The problem. Prefix caching only works when prompts really share a prefix. A small change at the start of a prompt can make every block miss. The order of the parts in a prompt therefore decides the hit rate.

The idea. Because each block hash includes all the blocks before it (Example 6), the cache can reuse only the part of a prompt before the first difference. Anything that differs from request to request, such as a timestamp, must come late. Anything that is identical every time must come first, in a fixed order.

The program simulates 10 turns of an agent session. Each prompt has a 300-token system prompt, 10 tool definitions of 50 tokens each, the conversation history (growing by 120 tokens per turn), and a 30-token new user message. Three layouts are compared: stable (fixed parts first, in a fixed order), a 10-token timestamp before the system prompt, and the same tools in a different order each turn. Hits are counted with chained 16-token block hashes, as a server counts them. Compare the hit rates.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Locale;
import java.util.Random;
import java.util.Set;

public class PromptLayoutHits {
    static final int BLOCK = 16;

    static List<Integer> range(int from, int n) { List<Integer> l = new ArrayList<>(); for (int i = 0; i < n; i++) l.add(from + i); return l; }

    static void run(String layout) {
        Set<Long> cache = new HashSet<>();
        Random random = new Random(1);
        List<Integer> history = new ArrayList<>();
        long total = 0, hits = 0;
        for (int turn = 0; turn < 10; turn++) {
            List<List<Integer>> tools = new ArrayList<>();
            for (int t = 0; t < 10; t++) tools.add(range(20_000 + t * 100, 50));
            if (layout.equals("tools in random order")) Collections.shuffle(tools, random);
            List<Integer> prompt = new ArrayList<>();
            if (layout.equals("timestamp first")) prompt.addAll(range(90_000 + turn * 10, 10));
            prompt.addAll(range(10_000, 300));                       // system prompt
            for (List<Integer> t : tools) prompt.addAll(t);          // tool definitions
            prompt.addAll(history);
            prompt.addAll(range(50_000 + turn * 1000, 30));          // the new user message
            long h = 17;
            boolean prefix = true;
            for (int start = 0; start + BLOCK <= prompt.size(); start += BLOCK) {
                h = h * 1_000_003 + prompt.subList(start, start + BLOCK).hashCode();   // chained block hash
                if (prefix && cache.contains(h)) hits += BLOCK; else prefix = false;
                cache.add(h);
            }
            total += prompt.size();
            history.addAll(range(50_000 + turn * 1000, 30));         // the user message stays in history
            history.addAll(range(60_000 + turn * 1000, 90));         // the answer and tool results are appended
        }
        System.out.printf(Locale.ROOT, "%-22s prompt tokens %6d, cached %6d, hit rate %5.1f%%%n", layout, total, hits, 100.0 * hits / total);
    }

    public static void main(String[] args) {
        run("stable prefix");
        run("timestamp first");
        run("tools in random order");
    }
}

stable prefix          prompt tokens  13700, cached  11696, hit rate  85.4%
timestamp first        prompt tokens  13800, cached      0, hit rate   0.0%
tools in random order  prompt tokens  13700, cached   2736, hit rate  20.0%

With the stable layout, 11,696 of 13,700 prompt tokens are cached (85.4%). Each turn reuses the whole previous prompt up to the last full block before the new message. Only the new message and the tail of the history are computed.

With a timestamp first, nothing is ever cached. The first block contains the timestamp, its hash changes every turn, and every later hash includes it (Example 6). The system prompt, tools, and history are identical across turns, yet all 13,800 tokens are computed again.

With tools in random order, 2,736 tokens are cached (20.0%). These are the system prompt blocks before the first tool. Everything after the first differently ordered tool misses. This happens in practice when a client builds the tool list from an unordered map, or when a framework adds tools in a different order on each call.

The rules for prompt layout follow from the hash chain. Content that never changes goes first, in a deterministic order. Content that changes per request (dates, request ids, retrieved documents) goes as late as possible. A conversation grows only at its end. The hit rate translates directly into time to first token: at 85% cached, a 1,400-token prompt computes about 210 tokens.

Example 10: llama.cpp prompt cache: cache_n across agent turns

The problem. The previous examples used simulations. This example checks the same effect on a real server, llama-server, which does not use blocks and hashes but still reuses prefixes.

The idea. llama-server keeps the KV of the last request in each slot, and reuses the longest common prefix with the next request on that slot (llama-server: Endpoints, Slots, and Prompt Cache, Examples 9 and 10). The request field cache_prompt (default true, server flag --cache-prompt or --no-cache-prompt) turns this on. The flag --cache-reuse N additionally moves matching chunks after a removed part. The response reports two counters in its timings object: cache_n, the number of prompt tokens taken from the cache, and prompt_n, the number of prompt tokens the server had to process.

The experiment runs an agent-like conversation against llama-server with one slot and --cache-ram 0, so only the slot's own cache counts. It makes four turns to /v1/chat/completions. Each turn sends the full history plus a new user message, with max_tokens 8 and temperature 0, and appends the returned assistant message to the history. A second run puts a clock time ("Time: 10:00:00.", then 10:01:00, and so on) at the start of the system prompt.

llama-server -m tiny-random-qwen2vocab-f32.gguf -np 1 -c 4096 --cache-ram 0 --port 18432

Real values from each response (usage.prompt_tokens, timings.cache_n, timings.prompt_n), first for the append-only run, then for the timestamp run:

turn 1: prompt_tokens  34  cache_n   0  prompt_n  34
turn 2: prompt_tokens  56  cache_n  41  prompt_n  15
turn 3: prompt_tokens  78  cache_n  63  prompt_n  15
turn 4: prompt_tokens 100  cache_n  85  prompt_n  15

turn 1: prompt_tokens  46  cache_n   3  prompt_n  43
turn 2: prompt_tokens  68  cache_n  10  prompt_n  58
turn 3: prompt_tokens  90  cache_n  10  prompt_n  80
turn 4: prompt_tokens 112  cache_n  10  prompt_n 102

The program explains the append-only numbers from the slot's contents, and sums the work of both runs.

public class TurnCacheArithmetic {
    public static void main(String[] args) {
        int maxTokens = 8;
        int[] promptTokens = {34, 56, 78, 100};                      // usage.prompt_tokens of four turns
        int[] observedCacheN = {0, 41, 63, 85};                      // timings.cache_n from the server
        for (int t = 0; t < promptTokens.length; t++) {
            // the slot holds the previous prompt and the generated tokens, except the last sampled one
            int predicted = t == 0 ? 0 : promptTokens[t - 1] + maxTokens - 1;
            int newTokens = promptTokens[t] - (t == 0 ? 0 : promptTokens[t - 1]);
            System.out.printf("turn %d: +%2d tokens, predicted cache_n %3d, observed %3d, processed %3d%n",
                    t + 1, newTokens, predicted, observedCacheN[t], promptTokens[t] - observedCacheN[t]);
        }
        int[] stampCacheN = {3, 10, 10, 10};                         // the same turns with a clock in the system prompt
        int[] stampPrompt = {46, 68, 90, 112};
        int sumAppend = 0, sumStamp = 0;
        for (int t = 0; t < 4; t++) { sumAppend += promptTokens[t] - observedCacheN[t]; sumStamp += stampPrompt[t] - stampCacheN[t]; }
        System.out.println("tokens processed over 4 turns: append-only " + sumAppend + ", timestamp in system prompt " + sumStamp);
    }
}

turn 1: +34 tokens, predicted cache_n   0, observed   0, processed  34
turn 2: +22 tokens, predicted cache_n  41, observed  41, processed  15
turn 3: +22 tokens, predicted cache_n  63, observed  63, processed  15
turn 4: +22 tokens, predicted cache_n  85, observed  85, processed  15
tokens processed over 4 turns: append-only 79, timestamp in system prompt 283

In the append-only run, each turn adds 22 tokens: the assistant reply from the previous turn, the template tokens around it, and the new user message. The slot still holds the previous prompt and the 8 generated tokens, except the last one. A sampled token is added to the cache only when the next step processes it, and the request stopped after sampling it. So cache_n = previous prompt + 8 - 1, which gives 41, 63, and 85, exactly as observed. The reply text came back from the server and was sent again inside the history, and it tokenized to the same ids, so the match continued through the reply. Each turn processes only 15 tokens.

In the timestamp run, the first turn matches 3 tokens left in the slot from the previous run (<|im_start|>system\n, the start of every prompt with this template). From turn 2 on, the match always stops after 10 tokens: the template tokens and "Time: 10:0", followed by the minute digit that changes. Everything after it, the whole conversation, is processed again. Over four turns, the timestamp run processed 283 tokens against 79, and the gap grows with every turn, because the reprocessed part is the whole history.

A slot holds one conversation. With several clients on one slot, each new conversation replaces the last one. The RAM prompt cache (--cache-ram, default 8,192 MiB) is the second level that keeps earlier states (llama-server: Endpoints, Slots, and Prompt Cache, Example 9). With -np N slots, the server places a request on the slot with the longest common prefix when that prefix exceeds --slot-prompt-similarity (default 0.10) of the prompt, so concurrent conversations tend to keep their own slots.

Example 11: KV offload and saving slots across restarts

The problem. The GPU holds the KV cache, but GPU memory is small. Cached prefixes that are not in use, or a prefix that should survive a server restart, could live somewhere cheaper.

The idea. KV memory can live in other places than the GPU cache. Each engine has its own switches:

• llama.cpp's -kvo and -nkvo ("whether to enable KV cache offloading (default: enabled)") decide whether the KV cache of GPU-offloaded layers is placed on the GPU (-kvo) or kept in host memory (-nkvo). Host memory saves GPU memory at the cost of moving data each step.
• vLLM 0.30.0 can move evicted blocks to CPU memory. --kv-offloading-size sets the buffer in GiB (default none, which disables it), and --kv-offloading-backend chooses native or lmcache (CacheConfig in vllm/config/cache.py).
• SGLang has --enable-hierarchical-cache for a host-memory level behind its radix tree.
• llama-server can also write a slot's KV to a file with --slot-save-path, and read it back later, including in a new server process.

The run below tests the last item. It processes a 748-token agent prefix (a system prompt with 40 tool descriptions), saves it, stops the server, starts a new one, restores the file, and sends a request that begins with the prefix.

llama-server -m tiny-random-qwen2vocab-f32.gguf -np 1 -c 4096 --cache-ram 0 --slot-save-path ./slots --port 18432
curl -s localhost:18432/completion -d "{\"prompt\": \"$PREFIX\", \"n_predict\": 0}"
curl -s -X POST 'localhost:18432/slots/0?action=save' -d '{"filename": "agent-prefix.bin"}'
# stop the server, start it again with the same flags, then:
curl -s -X POST 'localhost:18432/slots/0?action=restore' -d '{"filename": "agent-prefix.bin"}'
curl -s localhost:18432/completion -d "{\"prompt\": \"$PREFIX User: read Main.java\", \"n_predict\": 2}"

Real output (the /completion lines show extracted fields):

prefix tokens_evaluated 748 prompt_n 748
{"id_slot":0,"filename":"agent-prefix.bin","n_saved":748,"n_written":778060,"timings":{"save_ms":0.637}}
{"id_slot":0,"filename":"agent-prefix.bin","n_restored":748,"n_read":778060,"timings":{"restore_ms":0.646}}
request tokens_evaluated 753 cache_n 748 prompt_n 5

The first line shows the prefix being processed: 748 tokens evaluated, all 748 computed. The next two lines are the save and the restore, each reporting 748 tokens. The last line is the request after the restart. It evaluates 753 tokens, takes 748 from the restored cache, and processes only 5.

The program checks the file size against the per-token layout found in the llama-server lesson, and computes what the same file means for an 8B model.

import java.util.Locale;

public class SlotFileArithmetic {
    public static void main(String[] args) {
        long tokens = 748, written = 778_060;
        long tinyKv = 2L * 4 * 2 * 32 * 2;                           // K and V, 4 layers, 2 KV heads x 32, F16
        System.out.println("tiny model: " + tinyKv + " B KV + 4 B token id + 12 B cell metadata = " + (tinyKv + 16) + " B per token");
        System.out.println("predicted " + tokens * (tinyKv + 16) + " B + header; written " + written + " B");

        double kv8b = 131072;                                        // 8B shape, F16
        double fileBytes = tokens * kv8b;
        double flops = tokens * 2 * 8.03e9;
        System.out.printf(Locale.ROOT, "8B shape: %.1f MiB file; read at 3 GB/s: %.1f ms%n", fileBytes / (1 << 20), fileBytes / 3e9 * 1000);
        System.out.printf(Locale.ROOT, "recompute on an 8-core CPU at 1.02 TFLOP/s peak: %.1f s; on an RTX 4090 at 50%% of 165.2 TFLOP/s: %.1f ms%n",
                flops / 1.02e12, flops / (165.2e12 * 0.5) * 1000);
    }
}

tiny model: 1024 B KV + 4 B token id + 12 B cell metadata = 1040 B per token
predicted 777920 B + header; written 778060 B
8B shape: 93.5 MiB file; read at 3 GB/s: 32.7 ms
recompute on an 8-core CPU at 1.02 TFLOP/s peak: 11.8 s; on an RTX 4090 at 50% of 165.2 TFLOP/s: 145.4 ms

The new server process restored all 748 tokens, and the request processed only its 5 new tokens. The file holds 778,060 bytes. The tiny model's KV is 1,024 bytes per token (4 layers, 2 KV heads of 32 values, K and V, 2 bytes each). The file adds a 4-byte token id and 12 bytes of cell metadata per token, which makes 1,040 bytes per token, as in llama-server: Endpoints, Slots, and Prompt Cache, Example 11. That is 777,920 bytes for 748 tokens, and the remaining 140 bytes are the header and per-layer fields.

For an 8B model (128 KiB per token), the same prefix is a 93.5 MiB file. Reading it from an SSD at 3 GB/s takes about 33 ms. Recomputing 748 tokens costs 12 TFLOP of arithmetic. That takes about 11.8 s at the full peak of the 8-core desktop CPU from FLOPs, Bandwidth, and the Roofline Model, or 145 ms on an RTX 4090 at half its peak. On a CPU-only machine, a saved prefix replaces seconds of prefill with milliseconds of disk reading. On a GPU the gap is smaller but still large.

A slot file is valid only for the exact model file and cache type that wrote it, because it stores raw KV values. Changing the model, the quantization, or -ctk and -ctv makes it useless. The server also rejects file names with path separators.

Example 12: prefix reuse with sliding-window layers: checkpoints and --swa-full

The problem. Prefix reuse assumes that the cache still holds the KV of every earlier token. Some models break that assumption on purpose.

The idea. Some models use sliding-window attention in some layers. A sliding window limits a layer to look only at the last n_swa tokens (the window size), so the layer keeps only the last window of positions and overwrites older ones (Attention Optimizations and Long Context, Examples 9 and 10). This saves memory, but it limits prefix reuse. To continue from position p, every local layer needs the keys of positions p - n_swa to p - 1, and those may already be overwritten. If they are gone, the server cannot continue from p, and it must recompute from the start unless it has a saved copy of the state from the right moment.

The run uses the tiny Gemma 3-style model from that lesson (window 128, 768 local cells at -c 4096) on llama-server with --cache-ram 0, in three configurations: context checkpoints off (-ctxcp 0), the default (-ctxcp 32), and --swa-full. Two requests share a 350-token prefix. The first continues with a long question (1,841 tokens in total), and the second with a short one.

llama-server -m tiny-gemma3-swa.gguf -np 1 -c 4096 --cache-ram 0 --port 18433 -v -ctxcp 0
llama-server -m tiny-gemma3-swa.gguf -np 1 -c 4096 --cache-ram 0 --port 18433 -v
llama-server -m tiny-gemma3-swa.gguf -np 1 -c 4096 --cache-ram 0 --port 18433 -v --swa-full -ctxcp 0

Real output per server (the two requests' counters, then selected log lines with timestamps removed):

== -ctxcp 0
tokens_evaluated 1841 cache_n 0 prompt_n 1841
tokens_evaluated 354 cache_n 0 prompt_n 354
I slot   operator(): id  0 | task 3 | forcing full prompt re-processing due to lack of cache data (likely due to SWA or hybrid/recurrent memory, ...)

== default
tokens_evaluated 1841 cache_n 0 prompt_n 1841
tokens_evaluated 354 cache_n 0 prompt_n 354
I slot create_check: id  0 | task 0 | created context checkpoint 1 of 32 (pos_min = 557, pos_max = 1324, n_tokens = 1325, size = 0.158 MiB)
I slot create_check: id  0 | task 0 | created context checkpoint 2 of 32 (pos_min = 1069, pos_max = 1836, n_tokens = 1837, size = 0.158 MiB)
I slot   operator(): id  0 | task 5 | checking checkpoint with [1069, 1836] against 222...
I slot   operator(): id  0 | task 5 | checking checkpoint with [557, 1324] against 222...
I slot   operator(): id  0 | task 5 | forcing full prompt re-processing due to lack of cache data (likely due to SWA or hybrid/recurrent memory, ...)

== --swa-full -ctxcp 0
tokens_evaluated 1841 cache_n 0 prompt_n 1841
tokens_evaluated 354 cache_n 350 prompt_n 4

For each server, the first line is the long request and the second is the short one. Look at cache_n of the second request: it is 0 for the first two servers and 350 for the --swa-full server.

The program repeats the server's decision with the rule from server-context.cpp: the threshold pos_min_thold = pos_next - n_swa, and a checkpoint is usable only if it ends at or before the reuse point and starts below the threshold.

public class SwaReuseCheck {
    record Checkpoint(int posMin, int posMax) {}

    public static void main(String[] args) {
        int nSwa = 128;
        int nPast = 350;                                             // common prefix with the cached prompt
        int posMinInCache = 1840 - 768 + 1;                          // 768 SWA cells ending at position 1840
        Checkpoint[] checkpoints = {new Checkpoint(557, 1324), new Checkpoint(1069, 1836)};

        int threshold = Math.max(0, nPast - nSwa);                   // server-context.cpp: pos_min_thold
        System.out.println("position " + nPast + " needs SWA entries from " + threshold + "; SWA cache starts at " + posMinInCache);
        boolean reuse = posMinInCache < threshold;
        for (int i = checkpoints.length - 1; i >= 0 && !reuse; i--) {
            Checkpoint c = checkpoints[i];
            boolean usable = c.posMax() <= nPast && (c.posMin() < threshold || c.posMin() == 0);
            System.out.println("checkpoint [" + c.posMin() + ", " + c.posMax() + "]: " + (usable ? "usable" : "not usable"));
            reuse = usable;
        }
        System.out.println(reuse ? "reuse " + nPast + " tokens" : "forcing full prompt re-processing: cache_n = 0");

        int appendPast = 1841, appendPosMin = 1840 - 768 + 1;        // 768 SWA cells hold positions 1073..1840
        System.out.println("append-only follow-up: needs SWA entries from " + (appendPast - nSwa) + ", cache starts at "
                + appendPosMin + " -> " + (appendPosMin <= appendPast - nSwa ? "reuse all " + appendPast + " tokens" : "reprocess"));
    }
}

position 350 needs SWA entries from 222; SWA cache starts at 1073
checkpoint [1069, 1836]: not usable
checkpoint [557, 1324]: not usable
forcing full prompt re-processing: cache_n = 0
append-only follow-up: needs SWA entries from 1713, cache starts at 1073 -> reuse all 1841 tokens

The second request shares 350 tokens with the cached one, so the server would like to continue at position 350. The local layers need the keys of positions 222 to 349 for that. After the first request, the 768 local cells hold positions 1,073 to 1,840, and position 222 is long gone. Without a full-size cache, the server must look for a checkpoint.

The default server had created two context checkpoints, which are copies of the slot's state (0.158 MiB each) taken while the long prompt was processed, at 1,325 and 1,837 tokens. Neither helps. Both end after position 350 and start far above 222. With no usable checkpoint, the server logs "forcing full prompt re-processing" and computes all 354 tokens. The -ctxcp 0 server reaches the same result without checking. With --swa-full, the local layers keep every position, so 350 tokens are reused and only 4 are computed. The price is the memory of full-size caches in the local layers.

The last line of the program is the case that works without --swa-full: a follow-up that appends to the first prompt. It continues at position 1,841 and needs positions 1,713 to 1,840, which the 768 cells still hold. For sliding-window models, a cache that only grows at its end loses nothing. Any reuse point far behind the end needs a checkpoint at the right place or the full-size cache. The server places checkpoints by rules (near the end of a prompt, at the last user message, with a minimum spacing), which suit conversations that branch near their end.

Example 13: what this means for agents: append-only history

The problem. A coding agent works in turns. On every turn it sends the whole conversation to the model: the system prompt, the tool definitions, and every tool call and result so far. The history keeps growing, and at some point it gets too long, so the agent must shorten it. The way it shortens the history decides whether the cache helps or fails.

The idea. The cache rewards prompts that only grow at the end. Anything that changes earlier in the prompt invalidates the cache from that point on. Cutting old messages from the start of a history is therefore expensive, although it makes the prompt shorter.

The program runs 20 agent turns, each adding a 400-token tool result after a 2,000-token fixed prefix. The cache keeps the previous prompt, like a llama-server slot, and the program counts how many tokens the server must process each turn. It compares three history policies: append-only, keeping only the last 5 tool results (dropping older ones from the start of the history), and append-only with one summary that replaces turns 1 to 12 at turn 13.

import java.util.ArrayList;
import java.util.List;

public class AgentHistoryCaching {
    // tokens the server must process when the cache keeps the longest common prefix of the last prompt
    static int processed(List<Integer> cached, List<Integer> prompt) {
        int i = 0;
        while (i < cached.size() && i < prompt.size() && cached.get(i).equals(prompt.get(i))) i++;
        return prompt.size() - i;
    }

    static void run(String name, int keepLastResults, boolean summarizeAt12) {
        List<Integer> cached = new ArrayList<>();
        List<List<Integer>> turns = new ArrayList<>();
        int total = 0, worst = 0, next = 100_000, last = 0;
        for (int turn = 0; turn < 20; turn++) {
            List<Integer> t = new ArrayList<>();
            for (int i = 0; i < 400; i++) t.add(next++);             // a tool call and its 400-token result
            turns.add(t);
            List<Integer> prompt = new ArrayList<>();
            for (int i = 0; i < 2000; i++) prompt.add(i);            // system prompt and tools
            int from = keepLastResults > 0 ? Math.max(0, turns.size() - keepLastResults) : 0;
            if (summarizeAt12 && turns.size() > 12) {
                for (int i = 0; i < 300; i++) prompt.add(900_000 + i);   // a summary replaces turns 1 to 12
                from = 12;
            }
            for (int k = from; k < turns.size(); k++) prompt.addAll(turns.get(k));
            int p = processed(cached, prompt);
            total += p;
            worst = Math.max(worst, p);
            cached = prompt;
            last = prompt.size();
        }
        System.out.printf("%-34s processed %6d tokens, worst turn %5d, final prompt %5d%n", name, total, worst, last);
    }

    public static void main(String[] args) {
        run("append-only", 0, false);
        run("keep only the last 5 tool results", 5, false);
        run("append-only, one summary at 12", 0, true);
    }
}

append-only                        processed  10000 tokens, worst turn  2400, final prompt 10000
keep only the last 5 tool results  processed  34000 tokens, worst turn  2400, final prompt  4000
append-only, one summary at 12     processed  10300 tokens, worst turn  2400, final prompt  5500

Append-only processes 10,000 tokens over 20 turns: 2,400 on the first turn, then 400 per turn. Every turn reuses the whole previous prompt.

Keeping only the last 5 tool results looks cheaper, since the final prompt is 4,000 tokens instead of 10,000. But it processes 34,000 tokens, 3.4 times more. From turn 6 on, each turn removes the oldest result from the start of the history. The prompt then diverges from the cached one right after the fixed prefix, and all 2,000 tokens of the remaining history are computed again on every turn. Trimming at the front turns an append into a rewrite. The option --cache-reuse (llama-server: Endpoints, Slots, and Prompt Cache, Example 10) can recover part of such a rewrite in llama-server by shifting chunks. vLLM's block hashes cannot do this, because every block after the change has a new hash.

The summary policy pays once. At turn 13, the prompt changes after the fixed prefix (a 300-token summary replaces 12 results), and that turn recomputes the summary and the new result, 1,100 tokens. After that, the history is append-only again. The total, 10,300 tokens, is close to append-only, and the final prompt is 5,500 tokens instead of 10,000. That saves KV memory and attention work on every later turn.

The rules for an agent's context follow:

1. Keep the system prompt and tool definitions byte-for-byte identical across turns, in a fixed order.
2. Append new messages and tool results at the end, and do not edit earlier messages.
3. When the context must shrink, compact rarely and in large steps (a summary that replaces many turns at once), and not a little on every turn.
4. Put per-turn volatile data (time, working directory listing, budget counters) in the newest message, not in the system prompt.

A later lesson on context management in coding agents builds loop agent's history on these rules.

Interview points

• Contiguous per-request KV regions waste memory twice. Reservations for the maximum length cause internal fragmentation, and gaps between regions cause external fragmentation.
• Paged KV cache stores KV in fixed-size blocks (16 tokens by default in vLLM, unless the attention backend prefers another size) and maps each sequence through a block table. The only waste is the last block, at most 15 tokens per sequence.
• The slot of a token is physical_block x block_size + offset. vLLM computes this slot mapping for every scheduled token.
• Reference counts let several sequences share blocks. Copy-on-write copies only the partially filled block that a sequence writes into.
• vLLM 0.30.0 implements n > 1 as child requests that share full prompt blocks through the prefix cache.
• vLLM's block hash covers the parent hash, the block's token ids, and extra keys (LoRA, multimodal, cache_salt). One changed token invalidates every later block.
• A prefix hit is limited to prompt_length - 1 tokens and to whole blocks. A 64-token prompt with 16-token blocks reuses at most 48.
• Freed cached blocks join the back of an LRU free queue in reverse order, so chain tails are evicted before shared beginnings. A hit removes a block from the queue.
• SGLang's radix tree matches at token granularity, splits nodes on partial matches, locks the paths of running requests, and evicts leaves with a lock count of 0 (LRU by default).
• Prompt layout decides hit rates. A timestamp at the start gives 0%, and shuffled tool definitions cut hits to the part before the first moved tool.
• llama-server reuses a slot's longest common prefix (cache_n), saves slots to disk with --slot-save-path, and for sliding-window models needs checkpoints or --swa-full to reuse a prefix far behind the end.
• Agents should keep histories append-only and compact rarely. Trimming a little from the front each turn recomputes the whole history every turn.

Summary

• Reserving 2,048 slots per request filled an 8,192-slot pool with 4 requests holding 2,350 tokens (28.7%). First-fit left 1,892 free slots that could not place a 900-slot request.
• With 16-token blocks, the same pool held 8 requests and 7,533 tokens (92.0%), against 4 requests and 37.6% with reservations.
• A 37-token sequence needs 3 blocks, and token 36 maps to logical block 2, offset 4.
• Forking a 40-token prompt into 3 samples with copy-on-write used 5 blocks instead of 9.
• Two requests sharing a 70-token system prompt reused 64 tokens (4 full blocks). The 6 tokens in the mixed block were computed again.
• vLLM hashes with SHA-256 by default (--prefix-caching-hash-algo), starts the chain from NONE_HASH, and hashes only full blocks.
• vLLM's free queue evicts from the front, appends freed cached blocks at the back in reverse order, and prepends blocks without a hash.
• In the layout simulation, a stable prefix gave an 85.4% hit rate, a leading timestamp 0%, and shuffled tools 20.0%.
• On llama-server, an append-only conversation had cache_n = previous prompt + max_tokens - 1 and processed 15 tokens per turn. A clock in the system prompt made every turn reprocess the history.
• A 748-token slot file (778,060 bytes on the tiny model) restored in a new server process gave cache_n 748. For an 8B model the file would be 93.5 MiB.
• On the sliding-window model, reusing a 350-token prefix after a 1,841-token prompt failed with default settings and succeeded with --swa-full (cache_n 350).
• vLLM 0.30.0 offloads KV to CPU with --kv-offloading-size and --kv-offloading-backend native|lmcache. llama.cpp's -nkvo keeps the KV cache in host memory.
• Over 20 agent turns, append-only processed 10,000 tokens, trimming the oldest results every turn processed 34,000, and one summary at turn 13 processed 10,300 with a 5,500-token final prompt.