VizuaraLearn DeepSeek by Vizuara

Curriculum  /  Part 4: The KV cache

Lesson 15: The block KV cache and the state cache

Part 4: The KV cacheFree lessonDownload lesson15_check.py

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.

Figure 15.1 One contiguous tensor per request. Growing A copies it, and 17 free rows cannot hold a request of 12.
Figure 15.1 One contiguous tensor per request. Growing A copies it, and 17 free rows cannot hold a request of 12.

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.

Figure 15.2 The same four events with pages. D fits into three pages that are not neighbours.
Figure 15.2 The same four events with pages. D fits into three pages that are not neighbours.

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).

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Figure 15.3 One sentence in three kinds of layer: page boundaries that disagree, window entries nobody reads, and tail tokens without a place.
Figure 15.3 One sentence in three kinds of layer: page boundaries that disagree, window entries nobody reads, and tail tokens without a place.

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 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.

Figure 15.4 The two parts for the toy: pages with finished entries, and one state slot with a window ring and two tails.
Figure 15.4 The two parts for the toy: pages with finished entries, and one state slot with a window ring and two tails.

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.

Figure 15.5 Blocks of 4 tokens hold whole entries of both kinds. Blocks of 6 tokens cut HCA entries 1 and 4 in two.
Figure 15.5 Blocks of 4 tokens hold whole entries of both kinds. Blocks of 6 tokens cut HCA entries 1 and 4 in two.

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.

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.

Figure 15.6 The state slot and the pages after tokens 2, 3, 4 and 5.
Figure 15.6 The state slot and the pages after tokens 2, 3, 4 and 5.

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.

Figure 15.7 Left: numbers in the pages and in the state slot of the toy. Right: bytes in the blocks and in the stored state of V4.1-Flash.
Figure 15.7 Left: numbers in the pages and in the state slot of the toy. Right: bytes in the blocks and in the stored state of V4.1-Flash.

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.

Figure 15.8 Top: three requests on one pool of pages and one pool of state slots. Bottom: what "shining" reads in request A, found through the block table.
Figure 15.8 Top: three requests on one pool of pages and one pool of state slots. Bottom: what "shining" reads in request A, found through the block table.

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

  1. 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.
  2. 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.

Keep going

This is one of 30 lessons

Members get every lesson, every lecture, the assignments and direct contact with me for a year. Founding members pay ₹4,999.