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 with an $L$ -token prompt prefills $L - m$ tokens:

\text{TTFT} \approx \max\!\left(t_{\text{mem}},\; (L - 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. The default policy is fcfs, and lpm itself falls back to it past 128 waiting requests; a newcomer’s prefix is matched when it is admitted under any policy. Matching works in whole pages, so with page size $p$ up to $p - 1$ tokens at a boundary are prefilled again, and an answer’s last token always is, because its k and v were never written.