One pool of 16-token blocks serves every request
The KV cache is a pool of 16-token blocks. Each request has a block table that maps its token positions to block numbers anywhere in the pool. Full blocks are listed in a hash map for prefix hits. Free blocks wait in a queue, and the least recently used cached block is evicted first.
BLOCK POOL ON THE GPU
#0
#1
#2
#3
#4
#5
#6
#7
#8
#9
#10
#11
#12
#13
#14
#15
BLOCK TABLES
request A
#2, #3, #7
request B
#5, #6, #10
cached prefix
#11, #12 by hash
Dashed blocks are free and wait in a queue. A request takes one block each time it fills 16 tokens.
When the queue is empty, the least recently used cached block is evicted first.