Chapter 08

Prefix caching

Same beginning, one copy.

Two requests arrive with the same first 512 tokens: the same system prompt. Same tokens at the same positions give exactly the same k and v. Paged as before, each gets its own copy: the same numbers written twice.

← KV memory

01 / 08

The prefix arithmetic, once

Position $i$ ‘s key and value are functions of tokens $1..i$ , so two requests can share cache exactly for their longest common prefix $m$ and nothing past it. A shared prefix of $s$ tokens across $r$ requests costs $s$ tokens of cache instead of $r \cdot s$ , and a newcomer prefills $P - m$ tokens:

\text{TTFT} \approx \max\!\left(t_{\text{mem}},\; 2(P - m)\,t_{\text{tok}}\right)

In a chat of $T$ turns with question $q_t$ and answer $a_t$ , prefill without caching sums to $\sum_t (q_t + \sum_{u<t}(q_u + a_u))$ and with it to $\sum_t q_t$ . SGLang’s RadixCache is the tree, reference counts pin the pages of running requests, eviction is least-recently-used over unreferenced nodes, and schedule_policy=lpm orders the waiting list by matched length.