Skip to main content
← CONCEPTS / AI & MACHINE LEARNING SYSTEMS
An end-to-end domain learning journey

AI/LLM Prefix Caching &
RadixAttention (Zero-Copy KV Sharing).

RadixAttention indexes cached GPU KV-cache blocks in a compressed prefix trie (Radix Tree) with LRU eviction, enabling zero-copy prefix sharing across concurrent and sequential LLM requests.
Start the journey7 sections
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

RadixAttention indexes cached GPU KV-cache blocks in a compressed prefix trie (Radix Tree) with LRU eviction, enabling zero-copy prefix sharing across concurrent and sequential LLM requests.

TL;DR30-second simplified summary
▾

In production LLM workloads—multi-turn chat, RAG pipelines, agent tool-use loops, and few-shot prompting—requests repeatedly share long token prefixes (e.g., a 4,000-token system prompt + tool schema). Recomputing the Key-Value (KV) tensors for those prefix tokens on every request wastes massive GPU HBM bandwidth and inflates Time-To-First-Token (TTFT).

RadixAttention (pioneered in SGLang and vLLM Automatic Prefix Caching) replaces per-request ephemeral KV buffers with a persistent Radix Tree (compressed prefix trie) in GPU HBM. Each edge represents a sequence of token IDs pointing to physical PagedAttention KV blocks, annotated with a reference count (ref_count) and last-access timestamp.

When a new prompt arrives, the scheduler traverses the Radix Tree to find the longest matching prefix in O(prompt_len), increments ref_count on those shared physical pages (zero-copy!), and only runs prefill compute on the divergent user suffix. Completed pages with ref_count == 0 remain cached in HBM and are evicted lazily via leaf-first LRU only when GPU memory is needed.

From patterns to decisions.

Eliminate redundant quadratic prefill compute and cut Time-To-First-Token (TTFT) by sharing immutable KV-cache pages in a reference-counted Radix Tree.

Full walkthrough · 7 stages
01
STAGE 01 · CAUSAL INVARIANCEfoundation

Why Identical Token Prefixes Produce Bit-Identical KV Tensors.

In a causal decoder-only Transformer, token i's Key and Value vectors (K_i, V_i) depend strictly on tokens 0..i and never on tokens > i.

Therefore, if Request A and Request B share an identical prefix of 2,048 tokens (with identical LoRA adapter and positional encoding), their first 2,048 KV vectors are mathematically identical—allowing 100% zero-copy reuse.

STAGE 01 · CAUSAL INVARIANCE

Causal Mask Prefix Invariance

Causal Mask PrefixInvarIngress / BaselineCore EngineScale ConstraintGuard & VerifyBottleneck SignalProduction OutcomeTarget SLAexposes

1.Stage Objective: Understand the mathematical property of causal masking that makes prefix KV sharing exact.

2.Level (Foundation): In a causal decoder-only Transformer, token `i`'s Key and Value vectors (`K_i, V_i`) depend strictly on tokens `0..i` and never on tokens `>

3.Operational Invariant: Causal attention guarantees prefix KV tensors are independent of any divergent suffix tokens.

Caption: Causal attention guarantees prefix KV tensors are independent of any divergent suffix tokens.

02
STAGE 02 · RADIX TREE INDEXfoundation

Compressed Prefix Trie Mapping Token Edges to Physical KV Pages.

Each node in the Radix Tree represents a contiguous span of cached tokens mapped to fixed-size GPU KV pages (e.g., 16 tokens/page). When a new prompt diverges mid-edge (e.g., matching 1,000 of 1,500 tokens on an edge), the engine splits the edge at token 1,000 into a shared parent node and two child branches—without copying any GPU tensors.

STAGE 02 · RADIX TREE INDEX

Radix Tree Prefix Splitting

Radix Tree PrefixSplittInput StateCore EngineCore MechanismGuard & VerifyInvariant CheckProduction OutcomeOutput Statetransforms

1.Stage Objective: See how a Radix Tree merges linear chains and splits nodes dynamically on divergent suffixes.

2.Level (Foundation): Each node in the Radix Tree represents a contiguous span of cached tokens mapped to fixed-size GPU KV pages (e.g., 16 tokens/page). When a n

3.Operational Invariant: Splitting a tree edge on divergent suffixes shares parent KV pages with zero GPU memory copies.

Caption: Splitting a tree edge on divergent suffixes shares parent KV pages with zero GPU memory copies.

03
STAGE 03 · EVICTION & SCHEDULINGintermediate

Reference Counting & Leaf-First LRU Eviction.

Active requests pin their matched prefix path by incrementing ref_count += 1 on every ancestor node, preventing eviction mid-generation. When a request finishes, ref_count decrements.

Only leaf nodes with ref_count == 0 sit in the LRU eviction queue; evicting a leaf frees its KV pages and may turn its parent into an evictable leaf.

STAGE 03 · EVICTION & SCHEDULING

Leaf-First LRU Eviction

Leaf-First LRUEvictionValidated InputCore EngineAtomic StepGuard & VerifyError / Retry GuardProduction OutcomeCommitted Resultexecutes

1.Stage Objective: Manage finite GPU HBM safely across active requests and cached idle prefixes.

2.Level (Intermediate): Active requests pin their matched prefix path by incrementing `ref_count += 1` on every ancestor node, preventing eviction mid-generation. W

3.Operational Invariant: Active requests pin shared nodes via ref_count > 0 while idle leaves evict in LRU order.

Caption: Active requests pin shared nodes via ref_count > 0 while idle leaves evict in LRU order.

04
STAGE 04 · RADIX MATCHERintermediate

Implementing Longest-Prefix Match & Node Splitting.

from dataclasses import dataclass, field

@dataclass
class RadixNode:
    tokens: tuple[int, ...]
    kv_page_ids: list[int]
    ref_count: int = 0
    children: dict[int, 'RadixNode'] = field(default_factory=dict)

class RadixPrefixCache:
    def __init__(self) -> None:
        self.root = RadixNode(tokens=(), kv_page_ids=[])

    def match_prefix(self, prompt_tokens: tuple[int, ...]) -> tuple[list[int], int, list[RadixNode]]:
        if not prompt_tokens:
            return [], 0, []
        node = self.root
        idx = 0
        matched_pages: list[int] = []
        pinned_nodes: list[RadixNode] = []
        while idx < len(prompt_tokens):
            first_tok = prompt_tokens[idx]
            child = node.children.get(first_tok)
            if child is None:
                break
            common = 0
            limit = min(len(child.tokens), len(prompt_tokens) - idx)
            while common < limit and child.tokens[common] == prompt_tokens[idx + common]:
                common += 1
            if common < len(child.tokens):
                # Partial edge match: caller stops at split boundary
                break
            matched_pages.extend(child.kv_page_ids)
            child.ref_count += 1
            pinned_nodes.append(child)
            idx += common
            node = child
        return matched_pages, idx, pinned_nodes
STAGE 04 · RADIX MATCHER

Prefix Match & Pinning Flow

Prefix MatchHot PathPinning FlowPartition / IndexValidation GateLatency / RAM BoundProduction OutcomeScaled Statebounds

1.Stage Objective: Write the core Radix Tree prefix-matching and reference-pinning logic.

2.Level (Intermediate): from dataclasses import dataclass, field

3.Operational Invariant: Longest-prefix traversal pins matched nodes in O(prompt_len) and returns reusable GPU page IDs.

Caption: Longest-prefix traversal pins matched nodes in O(prompt_len) and returns reusable GPU page IDs.

05
STAGE 05 · CACHE-AWARE SCHEDULINGadvanced

Longest-Prefix-First Scheduling vs. FCFS Starvation.

In a busy queue, FCFS execution can thrash the LRU cache if unrelated prompts interleave. Longest-Prefix-First (LPF) scheduling batches requests sharing the same active Radix branch together, maximizing KV reuse.

To prevent starvation of unique prompts, pair LPF with an aging boost so requests waiting > max_wait_ms promote to the front.

STAGE 05 · CACHE-AWARE SCHEDULING

Longest-Prefix-First with Aging

Longest-Prefix-Fir…witFault TriggerCore EngineIsolation BoundaryGuard & VerifyFallback / QuarantineProduction OutcomeProtected Pathisolates

1.Stage Objective: Boost cache hit rates by reordering queued requests without starving unique prompts.

2.Level (Advanced): In a busy queue, FCFS execution can thrash the LRU cache if unrelated prompts interleave. **Longest-Prefix-First (LPF)** scheduling batches

3.Operational Invariant: Grouping queued prompts by shared prefix boosts hit rates while aging prevents tail starvation.

Caption: Grouping queued prompts by shared prefix boosts hit rates while aging prevents tail starvation.

06
STAGE 06 · BLOCK ALIGNMENT & CPU OFFLOADadvanced

Page-Boundary Alignment & Tiered CPU-DRAM Offloading.

PagedAttention aligns KV blocks to fixed sizes (e.g., 16 tokens). Partial trailing tokens (< 16) are either recomputed or padded at system-prompt boundaries.

When GPU HBM fills, hot evicted KV pages can asynchronously offload over PCIe/NVLink to CPU DRAM (L2 KV Cache) rather than discarding them, reloading 5x faster than cold prefill.

STAGE 06 · BLOCK ALIGNMENT & CPU OFFLOAD

GPU HBM -> CPU DRAM KV Tiering

GPU HBM - CPU DRAMKV TiCheckpoint / LogCore EngineReplay / SyncGuard & VerifyConsistency GateProduction OutcomeRecovered Stateverifies

1.Stage Objective: Handle unaligned token boundaries and extend cache capacity beyond GPU HBM.

2.Level (Advanced): PagedAttention aligns KV blocks to fixed sizes (e.g., 16 tokens). Partial trailing tokens (< 16) are either recomputed or padded at system-p

3.Operational Invariant: Async PCIe offload preserves evicted prefix pages in CPU DRAM for fast reload on future hits.

Caption: Async PCIe offload preserves evicted prefix pages in CPU DRAM for fast reload on future hits.

07
STAGE 07 · MULTI-TENANT SECURITYadvanced

Preventing Cross-Tenant Cache Leaks & Timing Side Channels.

Sharing a global Radix Tree without tenant isolation exposes a subtle TTFT timing side channel: Tenant B can probe whether Tenant A recently sent a secret system prompt by measuring faster TTFT on a cache hit! Always salt every Radix Tree root or block hash with tenant_id (and lora_id) so cross-tenant sharing is strictly disabled.

STAGE 07 · MULTI-TENANT SECURITY

Tenant-Salted Radix Isolation

Tenant-Salted RadixIsolTelemetry SignalCore EngineSLO ThresholdGuard & VerifyCircuit BreakerProduction OutcomeSafe Degradationtrips

1.Stage Objective: Isolate cached KV prefixes across tenants in shared inference clusters.

2.Level (Advanced): Sharing a global Radix Tree without tenant isolation exposes a subtle **TTFT timing side channel**: Tenant B can probe whether Tenant A rece

3.Operational Invariant: Prefixing keys with tenant_id + lora_id eliminates cross-tenant TTFT timing side channels.

Caption: Prefixing keys with tenant_id + lora_id eliminates cross-tenant TTFT timing side channels.

Practice · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why must only leaf nodes with `ref_count == 0` be evicted from the RadixAttention LRU queue?

Recommended Learning Flow