SGLang and RadixAttention: Sharing the KV Cache Across Requests

Paged Attention stored the KV cache in blocks and named each full block by a hash of everything before it, so a new request can reuse blocks an earlier one computed. vLLM Architecture followed the scheduler that runs on top. SGLang (Zheng et al., 2024) came from the same observation pushed further: much of a server’s traffic repeats tokens it has already processed (a system prompt, few-shot examples, the history of a conversation, one prompt sampled many times), so the cache of computed prefixes should be a first-class structure that the scheduler plans around. Its answers are a radix tree of every cached prefix (RadixAttention), a scheduler that orders requests by how much of them is cached, and a decoder that skips the parts of a structured output the model has no choice about. This post measures what each of them buys.

Table of contents

What a cached prefix saves

A request’s prompt is prefilled before its first token: every prompt token goes through the model. If the first 2,048 tokens of the prompt were already processed for an earlier request and their keys and values kept, only the rest needs computing. Measured on Qwen2.5-1.5B-Instruct, on the Apple laptop GPU used throughout (lm.py loads the model as in Decoding):

@torch.no_grad()
def first_token(prefix_cache=None):
    if prefix_cache is None:
        cache, new = DynamicCache(), passage + question
    else:
        cache, new = copy.deepcopy(prefix_cache), question
    sync(); t0 = time.perf_counter()
    h = model.model(ids(new), past_key_values=cache, use_cache=True).last_hidden_state
    logits = model.lm_head(h[:, -1])
    sync()
    return time.perf_counter() - t0, logits

with torch.no_grad():
    prefix = DynamicCache()

Full script: prefill.py, with the prefix’s prefill and the timing. All of this post’s scripts, including the two that run the model on the GPU (prefill.py and jump.py), take about 2 minutes in all on an Apple M4 laptop, after the downloads.

time to first token, 2,176-token prompt: 2101.5 ms computed whole, 152.6 ms with the 2,048-token prefix cached (13.8x faster)
largest difference in the first token's logits: 0.0e+00; same first token: True

The cached prefix made the first token 13.8 times faster, and on the M4 the first token’s logits are identical to the full computation’s: the keys and values of a prefix depend only on the prefix (The KV Cache), so reusing them changes nothing in exact arithmetic. A rerun on an NVIDIA RTX 3090 (its saved outputs) chose the same first token, with logits up to 2.2e-02 apart: in 16-bit, the GPU adds up the same products in a different order when the prefix comes from the cache, and the rounding differs. Prompt Caching measured the same saving as an API price. The engine’s problem is to find the longest cached prefix of every new request, and to keep the right prefixes in a cache that is always too small.

The radix tree

A radix tree is a tree whose edges are labeled with runs of tokens: the path from the root to a node spells out a token sequence, and two sequences with a common prefix share the path for it. SGLang keeps one such tree for the whole server, mapping every cached token sequence to its keys and values, one token per page of the KV pool. A new request walks its tokens down from the root; how far it gets is how much is cached. A finished request’s prompt and answer are inserted, splitting an edge where the new sequence leaves an old one. In code:

    def _walk(self, tokens, split):
        """Follow tokens down the tree; return the deepest node reached and
        how many tokens matched. With split, cut an edge that matches only
        partly, so the match ends exactly at a node."""
        self.clock += 1
        node, i = self.root, 0
        while i < len(tokens) and tokens[i] in node.children:
            child = node.children[tokens[i]]
            k = 0
            while k < len(child.key) and i + k < len(tokens) and child.key[k] == tokens[i + k]:
                k += 1
            if k < len(child.key):
                if not split:
                    child.last = self.clock
                    return node, i + k
                mid = Node(node, child.key[:k])          # split the edge at k
                node.children[tokens[i]] = mid
                child.parent, child.key = mid, child.key[k:]
                mid.children[child.key[0]] = child
                child = mid
            child.last = self.clock
            node, i = child, i + k
        return node, i

    def match(self, tokens):
        return self._walk(tokens, split=False)[1]

    def insert(self, tokens):
        node, i = self._walk(tokens, split=True)
        if i < len(tokens):
            leaf = Node(node, tuple(tokens[i:]))
            leaf.last = self.clock
            node.children[tokens[i]] = leaf
            self.size += len(tokens) - i
        while self.size > self.capacity:
            self._evict_one()

When the pool is full, SGLang evicts leaves, least recently used first, so a prefix shared by many requests (an inner node) stays as long as anything below it is still in use. Running requests hold a reference count on their path, and a node is evictable only at zero. The cache isn’t a reserved region either: cached tokens and running requests share one pool, and as more requests run, cached tokens are evicted to make room.

    def _evict_one(self):
        leaves, stack = [], [self.root]
        while stack:
            n = stack.pop()
            stack.extend(n.children.values())
            if not n.children and n is not self.root:
                leaves.append(n)
        lru = min(leaves, key=lambda n: n.last)
        del lru.parent.children[lru.key[0]]
        self.size -= len(lru.key)

Full script: radix.py, with vLLM’s hashed blocks as a second cache with the same interface.

Radix tree or hashed blocks?

vLLM’s prefix cache, from Paged Attention, also finds the longest cached prefix: each full block’s hash covers everything before it, so a chain of hashes is a tree too, with 16 tokens to an edge. Two differences remain. The block cache matches only whole blocks, losing up to 15 tokens at the end of a match, and it evicts block by block where the radix tree evicts a whole leaf. How much do they matter? A real workload with heavy reuse is multi-turn chat: each turn’s prompt is the whole conversation so far. On ShareGPT conversations, interleaved as they would arrive at a server:

for cap in (16_384, 65_536, 262_144, 1_048_576, 10**9):
    hits = []
    for cache, usable in ((RadixCache(cap), lambda n: n - 1), (BlockCache(cap), lambda n: (n - 1) // 16 * 16)):
        matched = 0
        for _, prompt, reply in requests:
            matched += min(cache.match(prompt), usable(len(prompt)))
            cache.insert(prompt + reply)
        hits.append(matched / prompt_tokens)
    label = "unlimited" if cap == 10**9 else f"{cap:,}"
    print(f"{label:>18s}          {hits[0]:6.1%}                  {hits[1]:6.1%}")

Full script: hits.py, with how the conversations are built and timed.

2161 requests from 429 multi-turn conversations; 1,583,998 prompt tokens, 733 per request
cache size (tokens)    radix tree, any prefix    16-token blocks
            16,384           30.3%                   30.0%
            65,536           80.5%                   79.4%
           262,144           92.0%                   90.9%
         1,048,576           92.0%                   90.9%
         unlimited           92.0%                   90.9%

With room for everything, the radix tree reuses 92.0% of the prompt tokens and the block cache 90.9%: the difference, about one percentage point at every cache size, is the partial block at the end of each match, which the block cache recomputes. What decides reuse is the cache’s size against the working set: with 16,384 tokens, room for a few conversations, both reuse under a third, since a conversation’s history is evicted while its user is reading the last answer. On this workload the data structure is not what separates the two engines. (The replay is simplified: requests run one at a time, so each answer is cached before the next request arrives, and the cached answers are the replies ShareGPT recorded rather than a model’s.)

Cache-aware scheduling

What decides the hit rate when the cache is small is which requests run while their prefix is still cached. SGLang’s scheduler, by default in its first versions, sorts the waiting requests by the length of their cached prefix and runs the longest matches first (longest prefix match). The paper proves (its Theorem 3.1) that this order is equivalent to a depth-first walk of the tree of all requests, and, for a batch of requests known in advance and a cache at least as large as the longest request, that it maximizes the hit rate. Its cost is fairness: a request whose prefix isn’t cached can wait behind any number that are.

The test, built like SGLang’s own shared-prefix benchmark: 64 passages of 2,048 tokens, each with 16 different questions, all 1,024 requests waiting at once in random order, 32 requests admitted per round, and room for eight passages in the cache beside the running requests. As in SGLang, a round’s requests are all matched against the tree before they run, and cached after; a request’s wait is measured as the prompt tokens the server has computed by the time it is served, run for three random orders:

    cache, waiting, matched, computed, wait = RadixCache(16_384), list(range(len(requests))), 0, 0, {}
    while waiting:
        if policy == "lpm" or (policy == "lpm, as shipped" and len(waiting) <= 128):
            match = {i: cache.match(requests[i][0]) for i in waiting}
            waiting.sort(key=lambda i: -match[i])                   # stable: ties stay in arrival order
        run_now, waiting = waiting[:batch], waiting[batch:]
        hits = {i: min(cache.match(requests[i][0]), len(requests[i][0]) - 1) for i in run_now}   # match the batch,
        for i in run_now:                                                                         # then run it
            prompt, answer = requests[i]
            matched += hits[i]
            computed += len(prompt) - hits[i]
            wait[i] = computed                  # prompt tokens computed by the time it is served
        for i in run_now:
            cache.insert(requests[i][0] + requests[i][1])

Full script: schedule.py, with the workload and the three policies.

                   prompt tokens reused       first 128 arrivals served after this much prefill work
policy             seed 0  seed 1  seed 2     median (seed 0)     slowest (seed 0)
fcfs                 7.9%    8.9%    8.6%       137,343 tokens      262,140 tokens
lpm                 69.9%   57.8%   64.4%       216,775 tokens      507,556 tokens
lpm, as shipped     10.3%   11.7%   11.3%       137,343 tokens      262,140 tokens

In arrival order the cache churns: a passage is evicted before most of its 16 questions come around, and 8 to 9% of prompt tokens are reused. Longest prefix first runs each passage’s questions together while it is cached: 58 to 70% reused depending on the order requests arrived in, and two to three times fewer prompt tokens computed. The price is paid by requests whose passage isn’t cached: of the first 128 to arrive, the median was served after 216,775 prompt tokens of work instead of 137,343, and the slowest after 507,556 instead of 262,140, about twice as long.

Two things qualify that result in practice. SGLang now schedules in arrival order by default (--schedule-policy fcfs, since version 0.4.4), with longest prefix match an option. And even when chosen, it stops sorting while more than 128 requests are waiting, because matching every waiting request against the tree each round costs time; in this burst of 1,024 that leaves it close to arrival order, 10 to 12%. The large gain needs a queue short enough to sort, a cache that can’t hold everything, and requests that share long prefixes, all at once.

What the paper measured

The SGLang paper (NeurIPS 2024) reports up to 6.4 times the throughput and up to 3.7 times lower latency than Guidance, vLLM and LMQL, across 11 workloads, most of them built around prefix reuse (agents, reasoning, few-shot learning, retrieval and multi-turn chat) and one around JSON decoding, with Llama-2 7B to 70B, Mixtral and LLaVA on A10G and A100 GPUs. Not every workload gained: long-output multi-turn chat showed almost no speedup. The vLLM it compared was version 0.2.5, chosen, the paper says, because RadixAttention had by then been “partially integrated as an optional experimental feature into the latest version of vLLM”. On those benchmarks the cache hit rate ranged from 50% to 99%, and the cache-aware scheduler reached 96% of the best possible hit rate on average. The maintenance cost of the tree was 0.2 s of 74.3 s for 100 ShareGPT requests with no reuse at all, under 0.3%. In production, after a month of serving Chatbot Arena, the hit rates were 52.4% for LLaVA-NeXT-34B and 74.1% for Vicuna-33B, and Vicuna’s average time to first token fell 1.7 times.

Constrained decoding and jump-forward

An application that needs JSON constrains the model’s output to a grammar: at each step, tokens that would break the grammar are masked out. Much of a JSON object is then fixed: after a key’s value, the text ", "year": is the only thing that can follow. A constrained decoder still runs one forward pass per token of that fixed text, to produce a token the grammar had already decided. SGLang’s paper compiles the grammar into a compressed finite state machine, where a run of fixed text is one transition, and jumps forward: it appends the whole run at once and feeds it to the model in the next pass, as a short prefill.

A wrinkle: tokens don’t respect the grammar’s boundaries. The model’s natural way to end a string value is often the token ",, a quote and the comma that follows. A decoder that allows only a bare " to close a string pushes the model off its distribution: in a first version of the test below, the model, unable to use ",, kept writing until the string’s length limit. The paper handles such artifacts by retokenizing the text around a jump. The test below takes a simpler route of its own: it also allows closing tokens that begin the fixed text, which then continues after what they wrote:

    skip = 0                                                        # fixed text a closing token already wrote
    for n, (kind, arg) in enumerate(SEGMENTS):
        if kind == "text":
            ids = tok.encode(arg[skip:]) if arg[skip:] else []
            skip = 0
            if jump:                                                # append the whole run, no pass
                pending = pending + ids if logits is None else ids
                logits = None
                out.extend(ids)
            else:
                for t in ids:                                       # one pass per fixed token
                    mask = torch.zeros(len(pieces), dtype=torch.bool, device=DEVICE); mask[t] = True
                    choose(mask)
        elif kind == "str":
            close = CLOSE[n]
            for k in range(arg):
                t = choose(BODY | close)
                if close[t]:
                    skip = len(pieces[t]) - 1
                    break
            else:
                mask = torch.zeros(len(pieces), dtype=torch.bool, device=DEVICE); mask[QUOTE] = True
                choose(mask)

Full script: jump.py, with the token masks, the forward passes and the timing.

'{"title": "Paged Attention", "year": 2026, "summary": "This blog post discusses the concept of paged attention, which is a strategy for managing information overload by breaking down large amounts of data into smaller, more manageable chunks, allowing users to focus on specific aspects"}'
plain       : 317 output tokens in 312 forward passes, 16.3 s
jump-forward: 317 output tokens in 247 forward passes, 12.0 s
outputs identical to plain decoding: 4 of 5; first differing token: [None, 50, None, None, None]

Jump-forward needed 247 forward passes instead of 312, for 317 output tokens in each mode, 21% fewer, and 26% less time. The saving is the fixed share of the output: here two short values and a summary that ran to its 40-token cap (the sample above was cut there), so most tokens are the model’s own; a schema with many keys and short values saves more. The paper reports that the compressed state machine increased JSON decoding throughput 1.6 times. On the M4 one output in five differed from plain decoding, from token 50, and on the RTX 3090 rerun none did: feeding a run of tokens in one pass rounds 16-bit numbers differently from feeding them one at a time, which can flip a near tie in greedy decoding.

Grammar handling has since moved into dedicated libraries. SGLang’s default backend became xgrammar in version 0.4.4 (March 2025), with Outlines and llguidance as alternatives, and the speed of constrained decoding now comes mostly from computing token masks quickly: SGLang’s v0.4 announcement put xgrammar at up to 10 times faster than other open-source solutions for JSON decoding. The backends still implement a jump-forward step, but reading the current source, the scheduler does not appear to call it.

The programming model

SGLang began as a language as much as an engine: a Python front end in which a program calls gen to generate, select to choose among options, and fork to run several continuations of the same state in parallel. A fork tells the runtime in advance that several requests share a prefix, and the runtime sends that prefix first so the copies find it cached. The front end still exists and runs against an SGLang server, but most deployments today use SGLang as an OpenAI-compatible server, where the same reuse happens implicitly through the radix tree.

SGLang now

As of version 0.5.21 (October 2026):

• The radix cache is on unless turned off (--disable-radix-cache; a few model types turn it off themselves), one token per page, with larger pages as an option when exact reuse matters less. Its eviction policy is least recently used by default.
• Scheduling is first come, first served by default, with longest prefix match and several other policies selectable.
• The scheduler overlaps the CPU’s work with the GPU’s: it prepares the next batch while the current one runs (version 0.4, December 2024).
• Long prompts are prefilled in chunks, sized by GPU memory: 2,048 tokens below 20 GB, 8,192 on an H100.
• Scaling and memory: data-parallel attention for models with one key-value head, such as DeepSeek’s latent attention; separate prefill and decode servers (Serving Metrics and Prefill–Decode Disaggregation); an optional hierarchical cache that spills to host memory; speculative decoding with EAGLE (Speculative Decoding, Derived).
• Hardware: NVIDIA and AMD GPUs, TPUs, NPUs, CPUs and Apple silicon.

SGLang is hosted by LMSYS, the group behind Chatbot Arena, and joined the PyTorch ecosystem in March 2025, a listing rather than a transfer of governance. Users it has named include xAI, for Grok 3.

Limits

• Reuse needs an exact prefix. One different token early in the prompt, such as a date, and nothing after it matches.
• The tree’s advantage over hashed blocks is small on its own: on the chat workload above, one percentage point.
• Longest prefix first trades fairness for reuse, and is not the default.

Where this leads

• TensorRT-LLM follows NVIDIA’s engine.
• vLLM vs. SGLang vs. TensorRT-LLM compares the three.

Takeaways

• A cached prefix is most of a prompt’s cost: with 2,048 of 2,176 tokens cached, the first token came 13.8 times sooner and was the same token.
• RadixAttention keeps every cached prefix in one radix tree, matched to the token and evicted leaf first. On multi-turn chat it reused 92.0% of prompt tokens, about the same as vLLM’s hashed blocks (90.9%).
• The order requests run in can matter more than the structure: longest prefix first reused 58 to 70% against 8 to 9% on a shared-prefix burst with a small cache, while the slowest early arrival waited about twice as long. SGLang now defaults to arrival order and stops sorting long queues.
• Jump-forward feeds the text a grammar forces in one pass instead of one per token: 21% fewer passes on a small JSON schema. Tokens that cross the grammar’s boundaries, such as ",, must be allowed or the model is pushed off its distribution.

References

Start with the SGLang paper’s §3 for RadixAttention and its scheduling theorem, then the v0.4 announcement for what changed in the engine.

• Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs (NeurIPS, 2024): RadixAttention, cache-aware scheduling and the programming model, with the paper’s measurements.
• LMSYS, Fast JSON Decoding for Local LLMs with Compressed Finite State Machine (2024): jump-forward decoding with a compressed finite state machine.
• LMSYS, SGLang v0.4: Zero-Overhead Batch Scheduler, Cache-Aware Load Balancer, Faster Structured Outputs (2024): the overlapped scheduler and the xgrammar comparison.
• SGLang documentation, docs.sglang.io, and the scheduler and radix cache in sgl-project/sglang: the current defaults and server flags.
• PyTorch, SGLang Joins PyTorch Ecosystem (2025): SGLang’s PyTorch ecosystem listing.