1 · Memory layout: paged vs. asymmetric
Same pool, two layouts. Hover a cell. Illustrative 4-cell pages stand in for SGLang's real 16-token pages; sizes are made up for the drawing.
Prefix placement flow
Step through what happens when the radix tree creates a node. Per the episode: no promotion or demotion afterwards.
2 · Reuse saves prefill, not decode reads
Every decode step, each request needs the whole prefix K/V. Pick how the kernel reads it.
requests in flight16
Relative prefix reads per step: paged = N, read-once = 1 Illustrative (counts, not bytes).
Measured kernel launch (256 requests)Reported
Same dense kernel on two layouts. "Unique" ≈ paged storage; "shared" = prefix stored and read once.
8.6 GB vs 37 MB ≈ 230× less traffic · 449 µs vs nearly 7 ms ≈ 15.6× · paged kernel already at 79% of its memory limit, so tuning buys ≤1.27×.
3 · Per-step dispatcher
M_eff = realized batch × GQA group size (queries per KV head). M_eff ≥ 1024 → dense (Hydragen-style Triton matmul); otherwise → cascade (FlashInfer-style tiled loop). Threshold fitted on A100; refit for other GPUs.
batch
GQA group
M_eff mapIllustrative
Computed from the formula above, not a measurement. Colour = M_eff (capped at 2048); outlined cells go dense. Hover for values.
Reported backend factsReported
One Llama cell: dense 42 ms/token vs cascade 63. Dispatcher costs under 1 µs per step.
4 · Results
Llama-3.1-8B on 1×A100-40GB unless noted; ShareGPT turns, 256 in flight, 256 output tokens, 3 repetitions. SGLang-Cascade is the authors' own baseline.
Where does the 16K gain come from?Derived from reported tok/s
(2800−1360)/(2943−1360) ≈ 91% of the added throughput comes from cascade on plain paged storage. The table has no error bars; the paper reports ~6% spread elsewhere.
5 · Why 15.6× becomes 2.16×
Amdahl's law: speedup = 1 / ((1−f) + f/s). The episode puts prefix attention at about 60% of a decode step.
prefix share f
kernel speedup s
End-to-end vs kernel speedup by modelReported
Llama-8B (1 GPU, 8 KV heads/GPU), Qwen-14B (2 GPUs, 4), Qwen-32B (4 GPUs, 2). Amdahl predicts roughly 2.3–2.9×.
Short prefixes regressReported
Text says "at worst 0.97×" (synthetic grid); ShareGPT tables at 512-token prefixes show ~0.77–0.82×; 0.67× at 512 concurrent on 32B.