RadixAttention (SGLang)

RadixAttention is the KV-cache management technique at the heart of the SGLang inference engine. Instead of throwing away the KV cache when a request finishes, the server keeps the cached keys and values for every recent prompt and generated output in a radix tree, a compressed prefix tree in which each edge carries a run of tokens. When a new request arrives, the server walks the tree, finds the longest prefix the request shares with anything already processed, reuses those cached tensors, and computes only the new suffix. The reason it matters is that real LLM traffic is shaped like a tree: thousands of requests share a system prompt, many of those share few-shot examples, a chat session extends its own history one turn at a time, and an agent branches into parallel attempts that all share the same context. A tree is the natural structure for storing that overlap exactly once.

This entry goes deeper on the data structure, the request lifecycle, eviction and scheduling than the broader treatment in prefix caching and position-independent caching, which compares radix trees with vLLM’s block hashing and covers provider-level prompt caching. If you want to know how to lay out a prompt so any prefix cache hits, start there. If you want to know what the SGLang server is doing underneath, read on.

Why a Tree and Not a Table?

A flat cache keyed by “the full prompt” only hits when two prompts are identical. A cache keyed by “the first N tokens for a fixed N” only hits when the overlap is exactly that long. Real overlap is neither. Consider four kinds of traffic that SGLang’s authors designed around:

• Shared system prompts. Every request in a product starts with the same instructions.
• Few-shot prompting. Many requests share the same examples, and different tasks share different example sets that themselves often share an introduction.
• Multi-turn chat. Each turn’s prompt is the previous prompt plus the model’s reply plus a new user message, so a session is a growing path.
• Branching programs. Self-consistency sampling, tree-of-thought search and agent loops fork one context into several continuations.

All four are tree-shaped: a trunk of shared tokens with branches where requests diverge. A radix tree stores the trunk once and lets each branch hang off the exact token where it diverges, at any depth. Contrast that with a hash-per-block design (the other common approach, built on PagedAttention), where sharing is determined by fixed-size block boundaries.

The Data Structure

A radix tree (also called a compressed trie or Patricia trie) differs from a plain trie in one way that matters: an edge can be labeled with a sequence of tokens, not just one. A plain trie over a 6,000-token system prompt would need 6,000 nodes in a chain. A radix tree stores it as one node.

In SGLang each node holds three things that matter here: a key (the run of token IDs on its edge), a value (the indices of the GPU KV-cache slots holding the keys and values for those tokens, stored in a paged layout), and a reference count recording how many in-flight requests are currently using it. Each node also tracks when it was last accessed, which drives eviction.

%%{init: {'theme': 'base'}}%%
graph TD
    classDef default fill:#ffffff,stroke:#4338CA,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef data    fill:#EEF0F7,stroke:#0D9488,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef process fill:#F7F8FC,stroke:#6366F1,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef output  fill:#4338CA,stroke:#4338CA,stroke-width:2px,color:#ffffff,rx:8px,ry:8px;

    R[root]:::process --> S["System prompt (8 tokens)"]:::data
    S --> FA["Few-shot set A (8 tokens)"]:::data
    S --> FB["Few-shot set B (8 tokens)"]:::data
    FA --> A1["Question a1 (3 tokens)"]:::default
    FA --> A2["Question a2 (3 tokens)"]:::default
    FB --> B1["Question b1 (3 tokens)"]:::default
    FB --> B2["Question b2 (3 tokens)"]:::output

Two operations keep the tree compact. Splitting: when a new request matches only the first part of an existing edge, the edge is cut at the divergence point, a new intermediate node takes the shared part, and the old node keeps the remainder as its child. That is how a single stored prompt becomes a trunk with two branches the moment a second prompt arrives that shares only its opening. Insertion: whatever part of the request did not match is attached as a new child node. The sketch below implements both, plus the lookup, in about thirty lines:

# Scenario: the core of a radix cache, stripped to the essentials. Keys are
# token lists, values would be KV-slot handles in a real engine. A lookup
# walks edges, splitting a node if the match ends in the middle of its key.
class Node:
    def __init__(self, key, parent=None):
        self.key, self.parent = key, parent
        self.children = {}          # first token of the child's key -> child
        self.last_used = 0
        self.lock = 0               # in-flight requests using this node

def match(root, tokens, now):
    node, i = 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):                      # match ends mid-edge: split it
            mid = Node(child.key[:k], node)
            node.children[mid.key[0]] = mid
            child.key, child.parent = child.key[k:], mid
            mid.children[child.key[0]] = child
            child = mid
        child.last_used = now
        node, i = child, i + k
    return node, i                                  # deepest matched node, tokens matched

def insert(root, tokens, now):
    node, matched = match(root, tokens, now)
    if matched < len(tokens):                       # attach only the unmatched suffix
        leaf = Node(tokens[matched:], node)
        leaf.last_used = now
        node.children[leaf.key[0]] = leaf
        node = leaf
    return node, matched                            # `matched` tokens were free

The Life of a Request

The tree is not a side table; it sits in the scheduler’s path. Roughly, for each request the server does the following:

%%{init: {'theme': 'base'}}%%
flowchart LR
    classDef default fill:#ffffff,stroke:#4338CA,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef data    fill:#EEF0F7,stroke:#0D9488,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef process fill:#F7F8FC,stroke:#6366F1,stroke-width:2px,color:#0F172A,rx:8px,ry:8px;
    classDef output  fill:#4338CA,stroke:#4338CA,stroke-width:2px,color:#ffffff,rx:8px,ry:8px;

    A[New request]:::process --> B[Match longest prefix in tree]:::data
    B --> C[Lock matched nodes]:::process
    C --> D[Prefill only the unmatched suffix]:::default
    D --> E[Decode new tokens]:::default
    E --> F[Insert prompt and output into tree]:::data
    F --> G[Unlock nodes, now evictable]:::output

1. Match. The scheduler looks up the waiting request in the tree and records the deepest matched node and the cache slots for the matched tokens.
2. Lock. Every node on the matched path has its reference count incremented, which protects it from eviction while this request is running.
3. Prefill the suffix. Only the unmatched tokens go through the model. The matched portion’s keys and values are read straight from the cache, so a request whose prompt is 95% shared costs roughly 5% of a cold prefill.
4. Decode. Output tokens are generated as usual, extending the cache.
5. Insert. The request’s tokens, including the generated output, are added to the tree. Keeping the output is what makes multi-turn chat hit: the next turn’s prompt begins with this turn’s prompt and reply.
6. Unlock. Reference counts drop, and the nodes become candidates for eviction if memory is needed.

The SGLang paper reports that the whole mechanism adds negligible overhead (under 0.3%) on workloads with no reuse at all, which is why it is on by default rather than a flag you opt into.

Eviction: Leaf-First LRU With Reference Counts

GPU memory is finite, so the tree cannot grow forever. SGLang’s default policy is least-recently-used eviction applied to leaves: the oldest leaf goes first, and once all of a node’s children are gone the node itself becomes a leaf and joins the candidate pool. Two properties fall out of this. First, shared trunks outlive private branches, because a node near the root has descendants and cannot be a leaf until every branch below it has been evicted; the system prompt used by everyone is the last thing to go. Second, a node is evictable only when its reference count is zero, so a running request can never have its cache pulled out from under it.

# Scenario: freeing memory when the cache is over budget. Only unlocked leaves
# are candidates, and the least recently used one goes first.
def evict(root, size, capacity):
    freed = []
    while size > capacity:
        victim = None
        stack = list(root.children.values())
        while stack:                                    # find the LRU unlocked leaf
            n = stack.pop()
            if n.children:
                stack.extend(n.children.values())
            elif n.lock == 0 and (victim is None or n.last_used < victim.last_used):
                victim = n
        if victim is None:                              # everything left is in use
            break
        del victim.parent.children[victim.key[0]]
        size -= len(victim.key)
        freed.append(victim)
    return size, freed

The eviction policy is configurable in current versions of SGLang: --radix-eviction-policy accepts lru (the default), lfu, slru and priority. LRU is a sensible default for chat and agent traffic, where recency predicts reuse. A frequency-based policy can suit workloads with a stable set of hot prefixes that are interleaved with a long tail of one-off prompts that would otherwise push them out.

Cache-Aware Scheduling

A cache is only as good as the order in which you ask it questions. If requests from three different prefix families arrive interleaved and memory only holds one family’s prefix, serving them first-come-first-served makes each request evict what the next one needed. SGLang addresses this with a cache-aware scheduling policy. Rather than serving the waiting queue in arrival order, the scheduler orders it by matched prefix length, longest first (the lpm policy, for longest prefix match). Requests that share a prefix with something already in the cache run while that prefix is still resident, and requests that share a prefix with each other end up adjacent.

The paper gives this a theoretical footing. Visit the radix tree of the waiting requests in depth-first order, and you achieve the optimal cache hit rate as long as the cache can hold at least the longest single request. Longest-shared-prefix-first is exactly that depth-first traversal when the whole workload is known, and for streaming arrivals it greedily approximates it on the part of the tree that has newly appeared. SGLang also offers dfs-weight, which makes the depth-first idea explicit by weighting subtrees by how many requests are waiting under them, and several other policies for different goals. The full list in current documentation is lpm, random, fcfs (the default), dfs-weight, lof, priority and routing-key.

Interactive: Does Scheduling Order Change the Cache Hit Rate?

The widget below replays a small workload through a real radix tree: twelve requests from three families that all share a system prompt, with each family adding its own few-shot examples and each request adding a unique question. Arrival order is interleaved (A, B, C, A, B, C, and so on). You control how much cache the server has and which order the scheduler serves requests in.

Start at the default (a 40-token budget, FCFS, all 12 requests) and look at the tree: only the shared system prompt and the branches of the two most recent families survive, because each family’s few-shot examples are evicted before that family’s next request arrives (the last request reuses only the 8 system-prompt tokens). The two bars at the top show the consequence: FCFS reuses a minority of all tokens while LPM reuses about 70%. Switch the policy to LPM and step the slider one request at a time to watch the tree split at the shared prompt, then at each family’s examples, with every new question hanging off a branch that stays resident. Now drag the budget up toward 80 tokens and the two bars converge: once the cache holds all three families, serving order no longer matters. The model is deliberately small (one request at a time, 19-token prompts, no output tokens), so read it as a picture of the mechanism, not a throughput forecast.

Co-Design With the Frontend Language

RadixAttention was published as one half of a system. The other half is SGLang’s frontend, a Python-embedded language for writing LLM programs with multiple generation calls, and the two were designed to help each other. When a program calls fork, the frontend tells the runtime that several continuations share everything before the fork point, which lets the runtime insert that shared prefix into the tree correctly and schedule the branches together instead of discovering the overlap by accident.

# Scenario: self-consistency on a support question. Sample three independent
# answers from the same context, then ask the model to pick the best. The
# system prompt, the ticket and the shared context are prefilled once; the
# three branches only pay for their own generated tokens.
import sglang as sgl

@sgl.function
def best_of_three(s, ticket):
    s += sgl.system("You are a support agent for Acme. Follow the refund policy exactly.")
    s += sgl.user("Ticket: " + ticket)
    forks = s.fork(3)                                   # three branches share everything above
    for f in forks:
        f += sgl.assistant(sgl.gen("answer", max_tokens=200, temperature=0.8))
    forks.join()
    s += sgl.user("Candidate answers:\n" + "\n---\n".join(f["answer"] for f in forks)
                  + "\nReply with the best one.")
    s += sgl.assistant(sgl.gen("final", max_tokens=200))   # also reuses the prefix

sgl.set_default_backend(sgl.RuntimeEndpoint("http://localhost:30000"))
state = best_of_three.run(ticket="I was charged twice for order 4417.")
print(state["final"])

If you only use the OpenAI-compatible endpoint, you get the radix cache and the scheduler but not the explicit fork hint; the tree finds the shared prefixes anyway, because it matches on tokens, but it only learns about them when requests arrive.

RadixAttention Versus Block Hashing

Both RadixAttention and vLLM’s automatic prefix caching deliver exact prefix reuse on top of paged KV memory, and for a stable system prompt they perform alike. The practical differences show up at the edges:

SGLang’s --page-size setting lets you trade granularity for efficiency: at 16, only complete 16-token pages are cached and a trailing partial page is always recomputed, which is how a radix tree is made to behave like block-aligned caching when an attention kernel or a storage backend wants aligned pages. The original comparison numbers in the SGLang paper and blog were measured against older versions of other engines, before they shipped their own prefix caching, so treat them as the case for the idea rather than a current head-to-head result.

Scaling Beyond One GPU

A radix tree lives in one engine’s GPU memory, and that creates two problems at fleet scale. The first is that the cache is private to a replica: a request only benefits if the load balancer sends it to a replica that holds its prefix. The second is that GPU memory is the smallest and most expensive tier, so the cache holds only the most recent working set.

Cache-aware routing. SGLang’s router (introduced with v0.4 in December 2024) keeps an approximate radix tree for each worker, built from the requests it has sent there, and uses it to predict which worker holds the longest matching prefix, without querying the workers’ real caches. The tree is updated lazily. When the fleet is balanced, the router sends a request to the best-matching worker; when load becomes imbalanced, it falls back to load balancing, so a popular prefix cannot turn one replica into a hot spot. LMSYS reported up to a 1.9x throughput increase and a 3.8x higher cache hit rate (hit rate rising from 20% to 75% in their benchmark) from this routing alone.

# Scenario: four SGLang replicas behind one router. Same-prefix requests are
# steered to the replica that already holds the prefix; the router balances
# load when the fleet gets lopsided.
python -m sglang_router.launch_router \
    --worker-urls http://gpu-0:30000 http://gpu-1:30000 http://gpu-2:30000 http://gpu-3:30000 \
    --policy cache_aware

HiCache. Announced by LMSYS in September 2025, HiCache extends the radix tree across three memory tiers: GPU memory (L1), host CPU memory (L2) and an external storage backend such as Mooncake, 3FS, NIXL or AIBrix (L3). The “HiRadixTree” tracks where each page of cache lives, much like a page table, and the engine can evict a page from GPU memory to host memory instead of discarding it, then bring it back when a later request matches. LMSYS reported up to 6x higher throughput and up to 80% lower time to first token on long-context and multi-turn workloads, with GPU-assisted I/O kernels delivering up to 3x higher CPU-to-GPU transfer throughput than naive copies. It is opt-in:

# Scenario: a long-context assistant where the working set of conversation
# histories is much larger than GPU memory. Spill evicted KV pages to host
# memory (2x the GPU pool here) rather than throwing them away.
python -m sglang.launch_server --model-path meta-llama/Llama-3.1-8B-Instruct \
    --enable-hierarchical-cache \
    --hicache-ratio 2 \
    --hicache-write-policy write_through \
    --hicache-io-backend kernel

The write policy decides when pages move down the hierarchy: write_through copies on creation, write_back copies on eviction, and write_through_selective copies only pages that have proved popular. A related direction is prefill-decode disaggregation, where the KV cache is moved between machines on purpose.

Where RadixAttention Falls Short

• It is still an exact-prefix cache. One changed token near the top of a prompt invalidates everything after it. A timestamp in the first line defeats the radix tree as thoroughly as it defeats any other prefix cache. The remedy is the same prompt discipline described in the prefix caching entry, and the same research frontier (position-independent caching) applies.
• Content that moves is a miss. A retrieved document that appears at a different position, or an agent observation that is edited out of history, shifts every following token. See agentic RAG and context engineering for how to keep context append-only.
• Memory is the real budget. Every cached token occupies GPU memory that could otherwise hold a larger running batch. A cache that is too greedy can lower throughput, which is why the share of memory given to the static pool (--mem-fraction-static) and the eviction policy are worth tuning for your traffic.
• Cache-aware ordering can starve cold requests. If requests with long cached prefixes keep arriving, a request with no prefix match can be pushed back repeatedly under LPM. Check which policies and priority options your SGLang version offers if tail latency matters more than hit rate.
• It leaks through timing if shared across tenants. As with any shared cache, a hit is faster than a miss, so isolating tenants matters when prompts are confidential.

What’s New (2025-2026)

• From research project to infrastructure company. SGLang, which began as a UC Berkeley and LMSYS research project, spun out as RadixArk, which launched with a $100 million seed round at a $400 million valuation. The company’s announcement says SGLang runs on hundreds of thousands of GPUs and generates trillions of tokens daily for companies including Google, Microsoft, NVIDIA, Oracle, AMD and xAI.
• The cache grew a hierarchy. HiCache (September 2025) made the radix tree span GPU, host memory and external storage, turning “evicted” from “gone” into “demoted”.
• Routing became cache-aware. The v0.4 release added the cache-aware load balancer, a Rust router that approximates each worker’s tree, so prefix reuse works across a fleet and not only inside one engine.
• Scheduling research is building on the tree. Rathi et al. (May 2026) show that smaller, prefix-homogeneous batches can decode faster than larger, mixed ones because they touch less KV memory, and propose a scheduler (integrated with vLLM and SGLang) that balances batch size against prefix similarity, reporting 2x to 10x higher end-to-end throughput on prefix-sharing workloads. TOPAS (Ni et al., 2026) schedules for multi-agent workflows by deciding jointly which agent prefixes to keep cached and which requests to run, reporting up to 39.8% lower mean job completion time on synthetic workflows.
• Agents made prefix reuse the default workload. Agent loops resend a growing context on every step, so hit rate has become the main lever on both latency and cost for agent products. See agent harness for the loop that generates this traffic.

Practical Guidance

The through-line is that RadixAttention treats the KV cache as a data structure to be managed, not a buffer to be discarded: store each shared token once, keep what is likely to be needed again, evict what is not from the outside in, and order the work so the cache sees its best questions first.

# Launch the server first (radix cache is on by default; --schedule-policy lpm
# makes the scheduler serve the best-matching waiting requests first):
#
#   python -m sglang.launch_server --model-path meta-llama/Llama-3.1-8B-Instruct \
#       --port 30000 --schedule-policy lpm --enable-cache-report
from openai import OpenAI

client = OpenAI(base_url="http://localhost:30000/v1", api_key="unused")

# Scenario: a code-review bot. Every request starts with the same 6,000-token
# style guide and differs only in the diff, so the style guide should be
# computed once and then served out of the radix tree.
STYLE_GUIDE = open("style_guide.md").read()

def review(diff: str):
    resp = client.chat.completions.create(
        model="meta-llama/Llama-3.1-8B-Instruct",
        messages=[
            {"role": "system", "content": STYLE_GUIDE},   # shared prefix goes first
            {"role": "user", "content": f"Review this diff:\n{diff}"},
        ],
        max_tokens=300,
    )
    u = resp.usage
    # With --enable-cache-report the usage block reports how many prompt
    # tokens were served from the radix cache instead of being prefilled.
    print(u.prompt_tokens, u.prompt_tokens_details.cached_tokens)
    return resp.choices[0].message.content

review(open("pr_101.diff").read())   # cold: cached_tokens is small
review(open("pr_102.diff").read())   # warm: cached_tokens covers the style guide