You’re seeing GPU OOM errors on long-context workloads despite ‘efficient’ paged attention, or your prefix caching hit rate is 15% when you expected 60%. SGLang’s RadixAttention achieves 5.4x throughput improvement on multi-turn conversations, but paged layout adds 8-12% memory overhead per sequence. The root cause is often a mismatch between your workload’s access patterns and your chosen RadixAttention memory layout strategy. After reading this, you’ll diagnose exactly why your KV cache layout choice is killing latency or wasting VRAM, and have a decision framework to pick the right strategy for your workload.
Table of Contents
- What is RadixAttention and how does it differ from PagedAttention?
- Contiguous KV cache: when does it still win?
- Paged KV cache: fragmentation trade-offs quantified
- RadixAttention’s hybrid approach: trie-structured block management
- Memory layout comparison: 4 quantitative dimensions
- Production failure modes and diagnostics
What is RadixAttention and how does it differ from PagedAttention?
RadixAttention is SGLang’s prefix caching mechanism that uses a radix tree (trie) to de-duplicate and reuse KV cache blocks across requests with shared prompts. Unlike vLLM’s PagedAttention, which manages per-request KV blocks, RadixAttention tracks block reuse globally with reference counting, enabling automatic memory sharing without explicit copying. This architecture bridges the gap between memory efficiency and computational overhead in LLM inference memory optimization.
Core abstraction: radix tree node to KV block mapping
The fundamental unit in RadixAttention is the radix tree node. Each node represents a token sequence prefix and contains a pointer to a physical KV cache block. When a new request arrives, SGLang traverses the tree character-by-character (token-by-token) to find the longest matching prefix. The implementation in github.com/sgl-project shows this structure:
# Conceptual structure based on SGLang v0.4+ implementation
class RadixTreeNode:
def __init__(self):
self.children: Dict[int, RadixTreeNode] = {}
self.block_id: Optional[int] = None
self.ref_count: int = 0
self.last_access_time: float = 0.0
self.hash_value: int = 0 # xxHash64 of token sequenceThis mapping decouples logical sequence representation from physical memory layout. Multiple logical sequences can share the same physical block if their token prefixes match, reducing redundant computation.
Reference counting and garbage collection semantics
RadixAttention uses reference counting to determine when a block can be safely evicted. Every time a request uses a node, its reference count increments. When the request completes, the count decrements. A block becomes eligible for eviction only when its reference count reaches zero.
This differs from vLLM’s PagedAttention block manager github.com/vllm-project, which ties block lifetimes to specific sequence states. The global view in RadixAttention enables cross-request sharing but introduces complexity in garbage collection. Long-running servers must monitor for reference count leaks, where blocks remain marked as “in use” indefinitely due to improper decrement logic.
Does RadixAttention work with multi-GPU deployments? Yes, SGLang supports RadixAttention with tensor parallelism across GPUs. The radix tree is replicated on each rank, with KV blocks sharded by layer. Cross-GPU block sharing requires NVLink for efficient peer access, as the memory bandwidth benefits diminish quickly over PCIe interconnects.
Version compatibility: vLLM PagedAttention vs SGLang RadixAttention
Comparing vLLM RadixAttention vs PagedAttention requires understanding their different scope. PagedAttention in vLLM (as of v0.6.x) focuses on memory allocation within a single request, using a block table to map logical blocks to physical memory. RadixAttention extends this concept across requests. [VERIFY: vLLM v0.6.x is latest stable?]
The following table summarizes key architectural differences:
| Feature | vLLM PagedAttention | SGLang RadixAttention |
|---|---|---|
| Scope | Per-request memory | Cross-request sharing |
| Data structure | Block table array | Radix tree (trie) |
| Sharing mechanism | Copy-on-write pointer | Reference-counted nodes |
| Lookup complexity | O(1) block access | O(prefix_length) tree walk |
| Eviction policy | LRU per sequence | Global LRU with ref counts |
| Best for | Variable-length single requests | Multi-turn with shared prefixes |
Contiguous KV cache: when does it still win?
Contiguous allocation places all tokens for a sequence in consecutive GPU memory addresses. This maximizes memory bandwidth utilization by eliminating scatter-gather overhead, achieving up to 1.15x higher throughput on short sequences (<512 tokens) where TCO (Tensor Core Operation) calculation dominates latency.
Memory coalescing and bandwidth efficiency
GPU memory controllers achieve peak bandwidth when access patterns are sequential. When thread blocks in an attention kernel read from contiguous addresses, memory transactions coalesce efficiently. Each memory fetch retrieves 128 bytes in a single transaction rather than issuing multiple partial transactions.
For short sequences where the entire KV cache fits in a single memory page, contiguous layout eliminates the page table walk overhead entirely. This becomes significant on memory-bandwidth-bound workloads. The H100’s 3.35 TB/s theoretical bandwidth translates to real throughput only when access patterns align with hardware expectations.
TCO (Tensor Core Operation) friendly access patterns
Tensor Cores on NVIDIA GPUs perform matrix multiply-accumulate operations most efficiently when data aligns to 128-byte boundaries. Contiguous KV cache layout naturally provides this alignment. When computing attention scores:
$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$
The K and V matrices read sequentially from contiguous memory, allowing the GPU to prefetch data into shared memory tiles without bank conflicts. This is particularly relevant for FlashAttention-3 github.com/Dao-AILab, which optimizes for Hopper architecture’s TMA (Tensor Memory Accelerator) units. [VERIFY: Has FlashAttention-3 replaced FlashAttention-2 in SGLang default?]
Cases where fragmentation dominates: variable-length prefixes
Contiguous allocation fails when workloads have high variance in sequence length. If a batch contains sequences ranging from 100 to 8000 tokens, memory fragmentation becomes severe. Allocating and freeing variable-sized contiguous chunks leaves gaps that cannot be reused.
Consider a scenario where you allocate space for an 8000-token sequence, then free it. A subsequent allocation for 4000 tokens might not fit in the freed space if the 8000-token block was split or merged incorrectly. Memory allocators like PyTorch’s caching allocator handle this partially, but long-running inference servers eventually exhaust largest-contiguous-block size, causing OOM despite having adequate total free memory.
Paged KV cache: fragmentation trade-offs quantified
Paged allocation splits KV cache into fixed-size blocks (typically 16-64 tokens) that can be non-contiguous. This reduces memory waste from internal fragmentation by 40-60% on long-context workloads, but introduces 2-4% overhead from page table lookups and scattered memory access.
Block size selection: 16 vs 64 tokens
The block size parameter directly tunes the trade-off between internal fragmentation and metadata overhead. What block size should you use for RadixAttention? Use 16 tokens for highly variable prefix lengths (chat), 64 tokens for document processing with long common prefixes. Smaller blocks reduce internal fragmentation but increase metadata overhead.
Quantitative impact of block size on a 4096-token sequence with BFloat16 KV cache:
| Block Size | Blocks Needed | Internal Fragmentation | Metadata Overhead | Page Table Size |
|---|---|---|---|---|
| 16 tokens | 256 blocks | ~0-15 tokens waste | 256 × 8 bytes = 2KB | 2KB |
| 32 tokens | 128 blocks | ~0-31 tokens waste | 128 × 8 bytes = 1KB | 1KB |
| 64 tokens | 64 blocks | ~0-63 tokens waste | 64 × 8 bytes = 512 bytes | 512 bytes |
For a system handling multi-turn chat with prefixes varying by 5-10 tokens between requests, 16-token blocks achieve ~15% better memory utilization. For document Q&A where prefixes differ by hundreds of tokens, 64-token blocks reduce page table overhead without sacrificing utilization.
External fragmentation and compaction strategies
Paged allocation eliminates internal fragmentation (waste within a block) but introduces external fragmentation (scattered physical blocks). The memory allocator must find free blocks for each allocation request, which becomes a bin-packing problem.
vLLM handles this through its block manager, which maintains freelists of available blocks. When memory pressure rises, the system can compact blocks by moving them to contiguous regions, similar to memory defragmentation. This operation has non-trivial cost: copying KV cache blocks between GPU memory regions saturates memory bandwidth.
SGLang’s approach differs by accepting non-contiguous blocks and optimizing the access pattern in the kernel. The Triton-based attention kernels github.com/sgl-project use block tables to compute physical addresses at runtime, adding pointer indirection but avoiding compaction entirely.
Copy-on-write overhead for shared blocks
When multiple sequences share a prefix block and one needs to modify it (implausible for pure autoregressive generation, but possible in speculative decoding or tree-based search), copy-on-write semantics trigger a block copy. The system duplicates the block, assigns a new block ID, and updates references.
This operation costs approximately 2μs per block on H100 for BFloat16 KV cache. While negligible per block, a speculative decoding burst touching 100 shared blocks adds 200μs to latency. Production systems should monitor COW event frequency via SGLang’s metrics endpoint.
# Monitoring COW events via SGLang metrics
import requests
metrics_response = requests.get("http://localhost:30000/metrics")
# Look for sglang_radix_cache_cow_events_total
# High values indicate prefix collision requiring duplicationRadixAttention’s hybrid approach: trie-structured block management
RadixAttention stores KV blocks in a radix tree keyed by token IDs, enabling O(matched_prefix_length) sharing detection. Each tree node contains a block ID, reference count, and hash for verification. This decouples logical (token sequence) from physical (GPU memory) layout.
Radix tree construction and matching algorithm
When a new request arrives with token sequence [t1, t2, t3, ..., tn], the tree traversal proceeds as follows:
flowchart TD
A[New Request] --> B[Start at Root]
B --> C{Node exists for t1?}
C -->|Yes| D[Follow Edge, Check ref_count]
C -->|No| E[Cache Miss: Allocate New Branch]
D --> F{Node exists for t2?}
F -->|Yes| G[Continue Traversal]
F -->|No| H[Partial Match: Reuse Prefix, Allocate Remaining]
E --> I[Compute New KV for All Tokens]
H --> J[Reuse KV for Prefix, Compute New KV for Remainder]
G --> K[Full Match: Reuse All KV Blocks]
The tree depth equals the maximum sequence length divided by block size. For a system with 128K context length and 16-token blocks, worst-case depth reaches 8000 levels. SGLang implements path compression to reduce effective depth for common prefixes.
Does RadixAttention increase latency for cache misses? Yes, 0.3-0.8ms overhead for radix tree traversal plus hash verification on miss path. This is amortized across cache hits. Disable with --disable-radix-cache for latency-sensitive, non-repeating workloads. The traversal happens on CPU while GPU computes attention for previous tokens, so the overhead often overlaps with useful work.
Write-back policies: eager vs lazy eviction
SGLang supports two eviction policies for radix cache nodes. Eager eviction frees blocks immediately when reference count reaches zero. This maximizes memory availability but thrashes the allocator when workloads exhibit temporal locality.
Lazy eviction (default in newer versions) keeps zero-reference blocks in cache until memory pressure triggers cleanup. A background thread periodically sweeps the tree, evicting least-recently-used nodes. This approach improves hit rates for workloads where the same prefixes reappear within seconds.
Configuration via environment variables:
export SGLANG_RADIX_CACHE_POLICY="lazy"
export SGLANG_RADIX_CACHE_EVICT_INTERVAL="5.0" # seconds between sweepsHash collision handling and verification cost
RadixAttention uses xxHash64 for block content hashing. The theoretical collision probability is approximately $1 – e^{-n^2/(2 \times 2^{64})}$ for n blocks, which remains negligible (below $10^{-18}$) for practical deployments handling billions of unique prefixes.
However, SGLang implements content verification on match to guarantee correctness. When a tree walk finds a matching hash, the system computes a lightweight checksum of block contents before reuse. This adds approximately 0.1ms latency per matched block but prevents silent correctness bugs from collisions.
Why is my prefix hit rate low with RadixAttention? Common causes include tokenization differences between cached and new requests, temperature/random_seed causing divergent token generation, or eviction policy set too aggressive. Verify with --log-level=debug to see tree traversal. The debug output shows prefix match lengths, helping identify whether tokenization or eviction is the culprit.
Memory layout comparison: 4 quantitative dimensions
Compare contiguous, paged (vLLM), and radix-paged (SGLang) across memory overhead per sequence, prefix sharing latency, worst-case fragmentation, and implementation complexity. Radix-paged excels when prefix hit ratio exceeds 30% and sequences exceed 1K tokens.
Per-sequence metadata overhead
Every memory layout requires bookkeeping data structures. The overhead per sequence varies significantly:
| Layout | Metadata Size (per sequence) | Calculation |
|---|---|---|
| Contiguous | 16 bytes | Start pointer + length |
| Paged (vLLM) | 8 × num_blocks + 64 bytes | Block table + sequence header |
| Radix-paged (SGLang) | 48 × matched_prefix_blocks + 8 × new_blocks | Tree nodes for prefix + new blocks |
For a 4096-token sequence with 16-token blocks, paged layout uses 2KB metadata. RadixAttention with 75% prefix hit requires only 48 bytes for cached prefix nodes plus 512 bytes for new blocks, totaling 560 bytes. However, radix approach carries global tree overhead amortized across all sequences.
Approximately 48 bytes per radix tree node (token hash, block ID, reference count, pointers). For 1M cached tokens, ~46MB overhead plus block storage. Negligible compared to KV cache (typical 2-8GB).
Prefix matching latency: O(n) vs O(prefix_length)
Latency for prefix matching differs fundamentally. Contiguous layout requires no matching: each sequence is independent. Paged layout in vLLM does not support cross-request sharing natively, requiring explicit cache management.
RadixAttention performs tree traversal with complexity O(prefix_length / block_size). For a 1024-token prefix with 16-token blocks, traversal visits 64 nodes. Each node access is a hash table lookup (amortized O(1)), so total matching time is approximately O(num_blocks_matched).
Benchmarks on ShareGPT dataset lmsys.org show average traversal time of 0.4ms for typical multi-turn prefixes. This cost appears in the critical path for cache-hit requests but overlaps with other operations for cache-miss requests.
Worst-case fragmentation scenarios
Each layout has distinct failure modes under adversarial inputs:
- Contiguous: 50% memory waste possible when alternating allocations of size N and N+1 tokens, causing checkerboard fragmentation.
- Paged: Internal fragmentation bounded by block size. 16-token blocks waste at most 15 tokens (<5% for sequences >300 tokens). External fragmentation handled by block allocator.
- Radix-paged: Tree depth explosion possible with adversarial inputs that create single-token divergent prefixes. Each unique 1-token prefix spawns a new tree branch. 1M unique prefixes consume significant CPU memory for tree structure independent of GPU memory.
SGLang v0.4.1 implements path compression to mitigate depth explosion. Adjacent single-child nodes merge into a single node with longer token sequences, reducing tree size by 10-100x for adversarial inputs.
Code complexity and debugging difficulty
Production deployments must consider maintainability. Contiguous allocation maps directly to GPU memory addresses, making debugging straightforward with tools like cuda-gdb or NVIDIA Nsight. Paged allocation adds indirection through block tables, requiring tooling to resolve virtual-to-physical mappings.
RadixAttention introduces the most complexity. Debugging requires understanding both tree structure and GPU memory layout. A production failure might manifest as incorrect generation due to shared block reuse but root cause analysis requires correlating CPU-side tree state with GPU-side block contents.
For teams without dedicated ML infrastructure engineers, simpler layouts reduce operational risk. The decision matrix in the next section provides guidance on when complexity justifies benefits.
Production failure modes and diagnostics
Common failures include reference count leaks causing premature eviction, hash collisions producing incorrect KV reuse, and radix tree depth overflow on adversarial inputs. All manifest as silent degradation or generation divergence, not crashes.
Detecting reference count leaks via memory profiling
Reference count leaks occur when increment and decrement operations become unbalanced. A request might increment a node’s ref_count during initialization but fail to decrement on error exit paths. Over time, leaked blocks accumulate, reducing available memory.
Symptoms: GPU memory usage grows steadily despite constant request rate. nvidia-smi shows increasing memory consumption while sglang.metrics.active_sequences remains bounded.
Detection requires correlating radix cache metrics with GPU allocator state:
import subprocess
import requests
import json
# Get GPU memory usage
nvidia_smi = subprocess.run(
["nvidia-smi", "--query-gpu=memory.used", "--format=csv,noheader,nounits"],
capture_output=True, text=True
)
gpu_memory_used_mb = int(nvidia_smi.stdout.strip())
# Get SGLang radix cache metrics
metrics = requests.get("http://localhost:30000/metrics").text
for line in metrics.split("\n"):
if "sglang_radix_cache_size_bytes" in line:
radix_cache_size = int(line.split(" ")[-1])
if "sglang_radix_cache_ref_count_sum" in line:
ref_count_sum = int(line.split(" ")[-1])
# Alert if ref_count indicates leak
if ref_count_sum > 10000: # Threshold depends on deployment scale
print(f"Potential ref count leak: {ref_count_sum} blocks marked in-use")The fix requires auditing all code paths that modify reference counts, ensuring proper exception handling. Similar to [debugging memory leaks in production Python apps](https://nileshblog.tech/debugging-memory-leaks-production-python-apps/
