Lesson 15: The block KV cache and the state cache
Part 1 changed what a layer caches. This lesson opens Part 4 and asks where a serving engine puts those entries in GPU memory when many requests run at once.
Source: the DeepSeek-V4 report (arXiv 2606.19348), section 3.5.1 and figure 6; the DeepSeek-V4.1-Flash report (arXiv 2609.19969), abstract and section 3.2.1; the DeepInfer deployment document (doc/inference_deployment_qa.md), section "KV cache storage". Every number in the worked examples comes from lesson15_check.py in this folder.
1. What Part 1 left for the engine
Chapter 2 of the book keeps the KV cache as one tensor per layer for one sequence, and the tensor grows by one row for every token. Part 1 changed the rows. A CSA layer of DeepSeek-V4 stores one compressed entry and one index key for every m = 4 tokens, and an HCA layer one entry for every m' = 128 tokens. Every layer also needs the uncompressed entries of the newest 128 tokens for its sliding window. In DeepSeek-V4.1-Flash, the Full layers of CSA2 store an entry for every 2 tokens or for every token.
Lesson 5 quoted the report's 890 bytes per token for V4.1-Flash, which is 933,232,640 bytes for a request of 1,048,576 tokens. A GPU serves many requests at once, of different lengths, and each grows while it decodes.
Three neighbouring topics have their own lessons. Lesson 16 moves finished blocks to SSD. Lesson 17 recomputes a lost window by bounded replay. Lesson 18 counts the bytes of an FP4 entry.
2. Attempt 1: one growing tensor per request
A tensor is contiguous: its rows lie next to each other in memory. We take 32 rows of memory, where a row holds the entry of one token in one layer. Three requests arrive: A with the 6 tokens of "The next day is bright and", B with 4 tokens and C with 8. Each takes the first gap that is long enough.
rows 0 to 31
A, B, C arrive AAAAAABBBBCCCCCCCC.............. 14 rows free
A adds one token ......BBBBCCCCCCCCAAAAAAA....... 6 rows copied
B finishes ..........CCCCCCCCAAAAAAA....... 17 rows free, in gaps of 10 and 7
D arrives, 12 tokens does not fit
When A decodes "sunny", the next row belongs to B. A's tensor has to move to rows 18 to 24, so one new token costs 6 copied rows. After B finishes, 17 rows are free, and a request D with our twelve-token sentence cannot start, because the largest gap has 10 rows. Free memory in pieces too small to use is called fragmentation (figure 15.1).
The usual way out is to reserve the maximum length for every request. For V4.1-Flash that is 933,232,640 bytes each. Without the reservation, moving a request of 100,000 tokens to add one token copies 89,000,000 bytes.

3. Attempt 2: pages, a block table and a free list
The known repair is paging. The V4 report names its form for KV caches, PagedAttention, without describing it or giving a reference.
A page is a piece of memory of one fixed size. We cut the 32 rows into 8 pages of 4 rows. A request now owns a block table: a short list that says which page holds its tokens 0 to 3, which holds tokens 4 to 7, and so on. We call such a range of tokens a block. The free list names the pages that belong to nobody.
block tables free list
A, B, C arrive A: [0, 1] B: [2] C: [3, 4] [5, 6, 7]
A adds one token A: [0, 1] B: [2] C: [3, 4] [5, 6, 7] 0 rows copied
B finishes A: [0, 1] C: [3, 4] [5, 6, 7, 2]
D arrives, 12 tokens A: [0, 1] C: [3, 4] D: [5, 6, 7] [2]
A's seventh token goes into the third place of page 1. Nothing moves. When B finishes, its page returns to the free list, and D takes three pages that need not be neighbours. Finding a token takes one division: token 9 of D lies in block 9 // 4 = 2, the table says block 2 is page 7, and the place inside the page is 9 mod 4 = 1 (figure 15.2).
The price is that the last page of a request may be partly empty: 28 rows are taken here and 27 hold a token.

4. Why plain pages do not fit V4
A block table assumes that every layer adds one row for every token. The report says V4's hybrid attention breaks the assumptions behind PagedAttention: it brings several types of KV entries, with different cache sizes and update rules. With the toy sizes of lessons 3 and 4, m = 2, m' = 4 and a window of 4:
tokens so far 1 2 3 4 5 6 7 8 9 10 11 12
CSA entries 0 1 1 2 2 3 3 4 4 5 5 6
HCA entries 0 0 0 1 1 1 1 2 2 2 2 3
window entries needed 1 2 3 4 4 4 4 4 4 4 4 4
tokens in no CSA entry 1 0 1 0 1 0 1 0 1 0 1 0
tokens in no HCA entry 1 2 3 0 1 2 3 0 1 2 3 0
Four things go wrong (figure 15.3).
- Different rates. If every page holds 2 entries, a CSA page covers 4 tokens and an HCA page 8. Token 9 lies in page 2 of one layer and page 1 of the other, so the layers cannot share a block table.
- A window that forgets. A paged cache only appends. Kept in pages, the window of one layer would hold 1,048,576 entries after 1,048,576 tokens, and the attention reads 128. The report says these layers have their own rules for cache hits and for eviction, the removal of entries from a cache.
- Tails. The last two rows count tokens that have arrived and do not yet fill a block: up to 3 in a real CSA layer and 127 in an HCA layer. The report says they are held in a buffer, with their hidden states, until the compression can run.
- Index keys. The lightning indexer adds keys of another width to the cache.
The report names two obstacles to one paged cache for all layers: differing cache policies, with the sliding window as its example, and the constraints of fast attention kernels. Sections 5 to 9 answer the first and section 10 the second.

5. Two caches for one request
The report splits the cache by update rule. Its figure 6 shows two parts, and figure 15.4 draws them for the toy.
- The classical KV cache is paged. A request owns several blocks. Each covers lcm(m, m') original tokens and holds k₁ = lcm(m, m') / m compressed CSA entries and k₂ = lcm(m, m') / m' compressed HCA entries.
- The state cache gives each request one block of fixed size. Its SWA segment holds the entries of the newest
n_wintokens, and its CSA/HCA segment holds the uncompressed tail states that are not ready for compression. A pool of these, of fixed and limited size, is reserved in advance.
The report does not say where the index keys go. DeepInfer describes the block KV cache of V4.1-Flash as the main KV plus the indexer K, so the toy puts them into the pages. We call the block of the state cache a state slot, DeepInfer's word.

6. Why a block covers lcm(m, m') tokens
lcm is the least common multiple, the smallest number that both rates divide. In the toy, lcm(2, 4) = 4, so a block of 4 tokens holds k₁ = 2 CSA entries and k₂ = 1 HCA entry. To see what the rule prevents, we try other block sizes on 24 tokens.
tokens per block CSA entries in each block HCA entries in each block HCA entries cut by a boundary
4 2, 2, 2, 2, 2, 2 1, 1, 1, 1, 1, 1 none
6 3, 3, 3, 3 1, 2, 1, 2 entries 1 and 4
8 4, 4, 4 2, 2, 2 none
Six is a multiple of 2 and not of 4. HCA entry 1 is built from tokens 4 to 7, of which 4 and 5 lie in block 0 and 6 and 7 in block 1 (figure 15.5). Two things break. The blocks hold 1, 2, 1, 2 HCA entries, so the place of an entry can no longer be found by a division. And when block 0 has all six tokens, two of them still wait in a tail. With a common multiple, the last token of a block completes an entry in every layer, and the page is final.
For V4, lcm(4, 128) = 128: a block holds 32 entries of each CSA layer and 1 of each HCA layer, and a request of 1,048,576 tokens owns 8,192 blocks. The report allows any multiple of the lcm and does not say which it runs. In V4.1-Flash the rates are 2 and 1, and DeepInfer gives the block as 128 tokens, 64 times their lcm.

7. Walkthrough: twelve tokens
The toy has one CSA layer and one HCA layer. Both receive the hidden states H of lesson 3, where a real model has different states in every layer. A page holds 2 CSA entries, their 2 index keys and 1 HCA entry, 10 numbers in all. A request takes a page when the first entry of a block is written, a rule we chose.
The state slot has three segments.
- The window ring, 4 places for each layer. A ring buffer is a fixed array written in a circle: token
tgoes to placet mod 4and overwrites what was there. - The CSA tail: the hidden-state row of a token that waits for its block to fill, at most 1 row. Lesson 3's entry also reads the 2 tokens before its block, so the toy keeps those rows too. The report does not say where the real system keeps them.
- The HCA tail: at most
m'- 1 = 3 rows.
after token ring, places 0 to 3 next CSA tail HCA tail moved to a page
write
0 The The - - - 1 The The
1 next The next - - 2 The next CSA 0 → page 0
2 day The next day - 3 day The next day
3 is The next day is 0 CSA 1, HCA 0 → page 0
4 bright bright next day is 1 bright bright
5 and bright and day is 2 bright and CSA 2 → page 1
6 sunny bright and sunny is 3 sunny bright and sunny
7 and bright and sunny and 0 CSA 3, HCA 1 → page 1
8 the the and sunny and 1 the the
9 sun the sun sunny and 2 the sun CSA 4 → page 2
10 is the sun is and 3 is the sun is
11 shining the sun is shining 0 CSA 5, HCA 2 → page 2
Token 3: a tail becomes an entry. Before "is" arrives, the HCA tail holds three raw rows:
The [ 1 0 0 1 ]
next [ 0 1 1 0 ]
day [ 2 1 0 0 ]
"is" completes the block. Lesson 4's compressor weights the four tokens 0.1345, 0.3655, 0.3655 and 0.1345 in channel 1, and the result is [0.7311, 1.2311], the HCA entry of block 0 in lesson 4. It goes to place 0 of page 0, and the three rows are dropped: 12 numbers leave the state and 2 enter the page. The same token completes CSA entry 1, [0.9446, 1.1243]. Page 0 is full, and nothing will be written into it again.
Token 4: the ring wraps. 4 mod 4 = 0, so "bright" overwrites "The".
place 0 1 2 3 next write
after "is" The [1, 0] next [0, 2] day [2, 1] is [-1, 1] 0
after "bright" bright [1, 3] next [0, 2] day [2, 1] is [-1, 1] 1
after "and" bright [1, 3] and [1, 1] day [2, 1] is [-1, 1] 2
To read the window from oldest to newest, we start at the write place. After "and" that is places 2, 3, 0, 1: "day is bright and" (figure 15.6).
After twelve tokens the block table is [0, 1, 2], and the script checks that the entries and index keys in these pages equal those of lessons 3 and 4.

8. A state and a list
The report treats the window and the tail tokens "as a state-space model". Such a model reads a sequence while carrying a memory of fixed size, and each new token overwrites part of it, as in a recurrent network. A KV cache is the other kind of memory: a list that grows with every token and forgets nothing. The report describes the cache for the window and the tails as a per-sequence state that depends only on the current position.
after token 0 1 2 3 4 5 6 7 8 9 10 11
numbers in pages 0 4 4 10 10 14 14 20 20 24 24 30
numbers in the slot 12 24 36 24 32 32 40 24 32 32 40 24
slot capacity 40 40 40 40 40 40 40 40 40 40 40 40
The slot never holds more than 40 numbers: 16 for the two window rings, 12 for the CSA rows and 12 for the HCA rows. After tokens 3, 7 and 11 its contents have the same shape: the write place is 0 and both tails are empty. The pages grow by 10 numbers for every 4 tokens, and after 1,048,576 tokens the slot would still have 40 (figure 15.7).
Since the size is known before a request arrives, the slots can be reserved once. The cost is that overwritten rows are gone, and the pages hold compressed entries only, so a lost slot cannot be read back from them.

9. Many requests at once
The toy engine has a pool of 8 pages and a pool of 4 state slots. Three requests advance in turn, one token each: A with all 12 tokens, B with the first 6 and C with the first 9.
request tokens state slot block table CSA tail HCA tail
A 12 0 [0, 3, 6] 0 0
B 6 1 [1, 4] 0 2
C 9 2 [2, 5] 1 1
Seven of 8 pages and 3 of 4 slots are taken, and the pages of one request are scattered. When B finishes, pages 1 and 4 and slot 1 return to the free lists (figure 15.8). The report does not say what happens when the pool of slots is empty.
V4.1-Flash. DeepInfer places the in-flight block KV cache and the state KV cache in GPU memory. Each sequence occupies one fixed-size slot, a StateBlock, split into a stored region and a dropped region. The stored region holds the windows of the first 20 layers, the encoder of lesson 6. The dropped region holds the windows of what the document calls the consumer layers and two compression accumulators, ca_state and ica_state, which it does not define. The stored region has the size state_size_to_disk:
ring places per layer 128 + 6 = 134
one layer 134 x 528 bytes = 70,752 bytes
stored region 20 layers x 70,752 = 1,415,040 bytes, 1.35 MiB
128 is the window. The ring has 6 extra places, which the document assigns to 6 tokens of speculative backtracking; lesson 24 covers speculative decoding. 528 bytes is one window entry in the MXFP8 format. The document gives no breakdown, and lesson 12 read it as 512 one-byte numbers and 16 scale bytes. The dropped region, the whole slot and the number of slots are not sized.
A block covers 128 tokens, which at 890 bytes per token is 113,920 bytes by our multiplication.
| Request | Blocks | Bytes in blocks | Bytes of stored state | State / blocks |
|---|---|---|---|---|
| 1,048,576 tokens | 8,192 | 933,232,640 | 1,415,040 | 0.0015 |
| 131,072 tokens | 1,024 | 116,654,080 | 1,415,040 | 0.0121 |
| 2,048 tokens | 16 | 1,822,720 | 1,415,040 | 0.7763 |
For the longest request the state is a rounding error. Below 1,590 tokens it is the larger part.
V4. At 128 tokens, a block holds 32 × 576 = 18,432 bytes of entries for each CSA layer and 576 bytes for each HCA layer, in lesson 4's format.

10. The kernel reads the layout
An attention kernel is the GPU routine that computes attention for a batch of queries. In a CSA layer the indexer of lesson 1 hands it a list of selected entries, which lie in scattered pages. The kernel turns each index e into an address:
page = block_table[ e // k₁ ]
place = e mod k₁
In lesson 3, "shining" selected CSA entries 2 and 3. With k₁ = 2 both lie in block 1, which is page 3 of request A, at places 0 and 1. The HCA layer reads place 0 of pages 0 and 3, and the window comes from the ring. Read this way, the CSA layer returns [1.2531, 1.5550] and the HCA layer [1.2556, 1.4427], the outputs of lesson 4.
In V4-Pro, k₁ = 32. Entry 77,777 lies in block 2,430 at place 17, and the 1,024 selected entries of one query lie in at least 32 pages and at most 1,024.
So the kernel must know how many entries a block holds, which is the second obstacle. The report says conventional fast kernels expect one fixed number B of entries per block. With B = 32, a CSA block would cover 128 tokens and an HCA block 4,096, and the boundaries would disagree as in section 4. V4's sparse attention kernel accepts a different number in different layers, 32 and 1 here, and the report says this costs no speed. One block of lcm(m, m') tokens then serves every layer.
The report's one example of designing layout and kernel together is padding. Memory is fetched in cache lines, units of fixed size. Take a line of 8 numbers and our page of 10:
page of 10 numbers pages start at 0, 10, 20, 30 page 1 touches lines 1 and 2, and shares line 1 with page 0
page of 16 numbers pages start at 0, 16, 32, 48 page 1 touches lines 2 and 3, and shares none
Padding costs 6 unused numbers per page, and reading a page then fetches nothing of a neighbour. The report gives no line size, no layout and no measurement.
11. The cache in code
The listing is the class Request and the function gather from lesson15_check.py, without the lines that print.
import torch
class Request:
def __init__(self):
self.t, self.table = 0, []
self.slot = FREE_SLOTS.pop(0) #A
self.ring = torch.zeros(2, N_WIN, C_DIM)
self.prev, self.tail_csa, self.tail_hca = [], [], []
def page(self, block):
if block == len(self.table):
self.table.append(FREE_PAGES.pop(0)) #B
return self.table[block]
def advance(self, h):
t = self.t
self.ring[:, t % N_WIN] = h @ W_KV #C
self.tail_csa.append(h) #D
self.tail_hca.append(h)
if len(self.tail_csa) == M: #E
i = t // M
p = self.page(i // K1)
POOL_CSA[p, i % K1], POOL_KEY[p, i % K1] = csa_entry(self.prev, self.tail_csa)
self.prev, self.tail_csa = self.tail_csa, [] #F
if len(self.tail_hca) == M2: #G
i = t // M2
p = self.page(i // K2)
POOL_HCA[p, i % K2] = hca_entry(self.tail_hca)
self.tail_hca = []
self.t += 1
def gather(pool, table, idx, per_block):
pages = torch.tensor(table)[idx // per_block] #H
return pool[pages, idx % per_block] #I
#A One state slot for the whole request, taken from the pool.
#B A new block needs a page: the first one on the free list.
#C The ring: the window entry of token t overwrites place t mod n_win, in both layers.
#D The hidden-state row waits in both tails.
#E The CSA tail is full: build the entry and its index key, and write them into the page.
POOL_CSA has shape (8, 2, 2): pages, entries per block, numbers per entry.
#F The rows just compressed are kept for the overlap of the next CSA entry.
#G The HCA tail is full: one entry goes to the page, and m' rows leave the state.
#H From entry index to block, and through the block table to a page.
#I One indexed read returns the selected entries, shape (k, c).
csa_entry and hca_entry compress one block as in lessons 3 and 4.
12. What the real system adds
| Toy | V4 | V4.1-Flash | |
|---|---|---|---|
| Compression rates | 2 and 4 | 4 and 128 | 2 and 1, no HCA |
| Tokens per block | 4 | a multiple of 128, not published | 128 |
| Entries per block and layer | 2 CSA, 1 HCA | 32 CSA, 1 HCA, at 128 tokens | 64 or 128 |
| Blocks at 1,048,576 tokens | 8,192, at 128 tokens | 8,192 | |
| Window ring, places per layer | 4 | 128 entries, ring not stated | 134 |
| Largest tail | 1 and 3 tokens | 3 and 127 tokens | accumulators, not sized |
| State slot | 40 numbers | not published | 1,415,040 bytes stored, rest not sized |
| Global KV per token | not published in bytes | 890 bytes |
Not published: how layers are arranged inside a block, where V4 keeps its index keys and the overlap rows of CSA, the bytes of V4's index keys, state cache and pool, the size of the dropped region, the cache-line size, and any measurement of the kernel. The V4.1-Flash report describes no in-memory layout: beyond the 890 bytes, everything here about V4.1-Flash comes from DeepInfer.
13. What is still open
- Pages and slots live in GPU memory while a request runs. Lesson 14 assumed that a long prefix is still cached when a conversation continues hours later, and GPU memory cannot be held that long for an idle user.
- Requests A, B and C of section 9 begin with the same tokens. The script confirms that page 0 of A and page 1 of B hold the same numbers, so the engine computed and stored them twice.
Lesson 16 follows the finished blocks out of GPU memory: onto SSD in the 3FS file system, found again by matching the prefix of a new request, and kept for a set time to live.