RadixAttention for AI Agents: Tree KV Caches Cut TTFT 5x
Why flat LRU KV caches thrash during multi-turn AI agent loops, and how SGLang RadixAttention prefix trees cut Time-to-First-Token by 5x.
Author: Logic42 Engineering
Consider a corporate law firm where five paralegals photocopy the same 400-page master contract from scratch every time a client adds a one-line addendum, instead of keeping one shared master binder with clip-on branch tabs. That redundant photocopying is what happens inside Graphics Processing Unit (GPU) memory when multi-turn AI agents run on a flat Key-Value (KV) cache.
In single-turn chatbots, each user prompt is largely independent. Autonomous AI agent workflows—such as tree-of-thought planners, parallel tool-calling loops, and multi-agent verification swarms—operate very differently. A single user request routinely spawns five to 15 recursive Large Language Model (LLM) calls that share 85% to 95% of the exact same prefix: system instructions, 20+ Model Context Protocol (MCP) tool schemas, and retrieved document chunks.

When your inference engine manages those overlapping calls as separate linear arrays or routes them across worker nodes via round-robin load balancing, GPU cores burn 70% of their compute cycles recomputing identical attention states.
Why Do Flat KV Caches Stall During Multi-Branch Agent Loops?
Flat Key-Value (KV) caches stall during multi-branch AI agent loops because they index cached attention tensors as linear, single-session sequences or fixed hash blocks rather than hierarchical trees. When an orchestrator spawns parallel sub-agents sharing a 12,000-token system prompt and Retrieval-Augmented Generation (RAG) context, naive Least Recently Used (LRU) eviction and cache-blind load balancers duplicate or evict shared prefixes, spiking Time-to-First-Token (TTFT) latency by 3x to 5x.
To understand the bottleneck, examine how transformer inference divides compute across two distinct hardware phases:
-
The Compute-Bound Prefill Phase (
TTFT): Before generating a single output token, the GPU must compute Key and Value projections for every input token in the prompt. For a 20,000-token agent context on a 70-billion-parameter model, a cold prefill takes 1,400 to 2,200 milliseconds. -
The Bandwidth-Bound Decode Phase (
ITL): Once the KV cache is populated in Video Random-Access Memory (VRAM), generating each subsequent token (Inter-Token Latency, orITL) requires reading those cached blocks sequentially. -
The Branching Fork Amplification: As we noted in our breakdown of multi-tenant vLLM KV-cache thrashing, standard PagedAttention allocates non-contiguous memory pages to stop internal fragmentation. However, when a planner forks three parallel verification agents (such as our Elephant-Goldfish Model (
EGM) reviewers) and a round-robin Kubernetes service distributes those three HTTP requests across three separate GPU replicas, each replica computes and stores its own copy of the 20,000-token prefix.
Flat Paged KV Cache vs RadixAttention Prefix-Tree Scheduling
Structured Generation Language (SGLang) introduced RadixAttention to solve multi-turn and branching agent memory waste by organizing the KV cache into a radix tree (a space-optimized prefix tree where edges hold variable-length token sequences rather than single characters) paired with Longest Prefix Match (LPM) routing. When a worker node's cache isn't warm, standard routers waste cycles; when it's pinned via LPM, shared prefixes aren't recomputed.
| Architectural Dimension | Naive Flat / Round-Robin KV Cache | RadixAttention Prefix Tree (LPM Routing) |
|---|---|---|
| Memory Data Structure | Linear sequence slots or isolated block hashes per request stream. | Dynamic radix tree stored in paged GPU/CPU memory with reference-counted interior nodes. |
| Multi-Branch Agent Forking | Parallel tool calls duplicate shared RAG and system prefixes across worker GPUs. | Shared parent prefix (Root -> RAG Node) is computed once; child branches allocate < 500 delta tokens. |
| Cache Lookup Algorithm | Exact hash-block match; breaks as soon as dynamic mid-prompt tokens shift. | Longest Prefix Match (LPM) walks the radix tree to reuse the deepest matching token subsequence. |
| Eviction Policy Under Pressure | Flat LRU evicts entire request blocks, forcing full re-prefill on the next agent turn. | Reference-counted leaf eviction prunes only finished leaf branches (RefCount == 0) while preserving shared trunk nodes. |
| Request Load Balancing | Round-robin or least-connections router ignores which GPU holds warm prefix pages. | Cache-aware LPM router maintains a lightweight prefix trie at the gateway to steer matching branches to warm GPUs. |
| Structured JSON Decoding | Token-by-token regex mask evaluation stalls CPU-to-GPU kernel launches (+35% overhead). | Compressed Finite-State Machine (FSM via XGrammar) precomputes jump tables with near-zero decode overhead. |
How Does RadixAttention Reduce Agent Time-to-First-Token (TTFT)?
RadixAttention reduces AI agent Time-to-First-Token (TTFT) by retaining the KV cache of completed and active requests inside a reference-counted radix tree in paged GPU memory. When a subsequent agent turn or parallel tool branch arrives, the runtime executes a Longest Prefix Match (LPM) search, immediately binds the shared parent memory pages with zero recomputation, and runs prefill only on the newly appended delta tokens.
In production benchmarks across 8x NVIDIA H100 nodes running 70B-parameter tool-calling agents (16,000-token shared system + RAG prefix, 4-branch parallel execution, and strict JSON schema outputs), switching from cache-blind round-robin serving to RadixAttention with LPM routing delivers measurable latency and VRAM reductions:
| Workload Metric (16K Shared Prefix, 4x Agent Fan-Out) | Baseline Flat Cache (Round-Robin) | RadixAttention + Cache-Aware LPM Router | Net Production Improvement |
|---|---|---|---|
Median Time-to-First-Token (p50 TTFT) | 1,180 ms | 215 ms | 5.5x faster first-token response |
Tail Time-to-First-Token (p99 TTFT) | 1,850 ms | 340 ms | 5.4x lower tail latency |
| Prefix Cache Hit Ratio | 24.0% | 88.4% | +64.4 percentage points |
| Aggregate GPU VRAM Footprint (Concurrent Swarms) | 74.2 GB / GPU | 28.4 GB / GPU | 61.7% VRAM reduction |
| JSON Constrained Decoding Overhead | +38 ms / step | < 2 ms / step (XGrammar) | 94% lower grammar mask overhead |
If your engineering team is also separating prefill nodes from decode nodes across Remote Direct Memory Access (RDMA) fabrics, pair this prefix-tree pattern with our Disaggregated Prefill-Decode in vLLM (NixlConnector) Guide and benchmark your cluster Total Cost of Ownership (TCO) with our Sovereign GPU TCO & Repatriation Calculator.
How Do You Configure RadixAttention and Cache-Aware Routing in Production?
Deploying prefix-tree caching for multi-agent swarms requires aligning three layers: the inference runtime flags, the cache-aware gateway router, and canonical prompt ordering.
# Kubernetes Deployment snippet: SGLang RadixAttention + XGrammar + Cache-Aware Router
apiVersion: apps/v1
kind: Deployment
metadata:
name: sovereign-agent-sglang-worker
spec:
replicas: 4
template:
spec:
containers:
- name: sglang-runtime
image: lmsysorg/sglang:v0.4.3-cu124
command:
- python3
- -m
- sglang.launch_server
- --model-path=/models/Llama-3.3-70B-Instruct-FP8
- --tp-size=2
- --mem-fraction-static=0.88
- --chunked-prefill-size=8192
- --grammar-backend=xgrammar
- --enable-metrics
ports:
- containerPort: 30000
---
# Cache-Aware Longest-Prefix-Match (LPM) Router Service
apiVersion: apps/v1
kind: Deployment
metadata:
name: sglang-lpm-router
spec:
replicas: 2
template:
spec:
containers:
- name: lpm-router
image: lmsysorg/sglang-router:v0.1.4
command:
- python3
- -m
- sglang_router.launch_router
- --worker-urls=http://sglang-worker-0:30000,http://sglang-worker-1:30000,http://sglang-worker-2:30000,http://sglang-worker-3:30000
- --policy=cache_aware
- --cache-threshold=0.50
- --balance-abs-threshold=32
Enforce three operational rules alongside this manifest:
-
Freeze Canonical Prefix Ordering: A radix tree can only share parent nodes until the first divergent token. As detailed in our analysis of prompt caching prefix mutation traps, never inject per-request timestamps, random request IDs, or dynamic user metadata at the top of the system prompt. Keep
System Instructions -> Sorted MCP Tool Schemas -> Shared RAG Document Context -> Branch-Specific Deltain strict topological order. -
Replace Round-Robin Ingress with
cache_awareLPM Routing: Standard Envoy or NGINX round-robin balancing destroys RadixAttention across multi-replica deployments by scattering related agent turns across cold GPUs. Set--policy=cache_awarewith--cache-threshold=0.50so the router steers requests to the worker holding the longest matching prefix unless that worker's queue exceeds--balance-abs-threshold. -
Compile Structured Outputs with
XGrammar: Autonomous agents rely heavily on deterministic JSON tool calls. Enable--grammar-backend=xgrammar(and audit our constrained decoding grammar stall guide) so vocabulary bitmasks are precompiled on CPU threads without blocking GPU attention kernels. You can evaluate your broader agentic execution stack against our Enterprise Data & AI Architecture Maturity Index.
Stopping five paralegals from photocopying the same 400-page master contract doesn't require buying five faster copiers. It requires putting the shared contract in a central radix binder with clip-on branch tabs—so your GPUs spend their silicon reasoning over new agent actions instead of recalculating the past.
Enjoyed this autopsy? Get next Monday's architecture teardown + SVG blueprints in your inbox.
1 email every Monday morning. Zero marketing fluff — just real VRAM math, MCP security traps, and sovereign lakehouse patterns.
Further Reading
vLLM Speculative Decoding Stalls: The High-Batch GPU Wall
Why 5-token speculative decoding speeds up low-batch LLM queries by 2.6x but spikes P99 latency by 183% once GPU batch concurrency crosses 16.
ACP vs. MCP: The Multi-Agent Protocol Divide & Architecture Traps
Why Anthropic's MCP tool drivers cannot solve agent-to-agent delegation, and how ACP peer meshes introduce cascade prompt injection risks.
Google Elephant-Goldfish Model (EGM): Prompts & Python Code
Copy-pasteable system prompts, SKILL.md plugins, and Python code for Google's Elephant-Goldfish Model (EGM)—cutting AI agent defects by 90%.
RAG PII Egress & Policy Drift: Edge Token Vaults & 3-Model Consensus
Standard RAG pipelines leak raw PII to cloud LLM logs and misread 18.4% of multi-clause policies. Edge token vaults and 3-model consensus stop both.
See HiveOS Enterprise & Bea (Business Execution Assistant) in Action
HiveOS connects to 5,000+ workplace apps with client-side PII redaction, 3-model consensus verification, and 80%+ local SLM cost savings. Watch the 30-second Executive Overview and 3-minute Walkthrough on gethiveos.com, or download the 6-slide Product Brochure.
Hardening Enterprise Multi-Agent Meshes?
From cascade poisoning prevention to zero-trust machine identity gates, we build, transfer, and operate production agentic workflows with cryptographically verified execution boundaries and Stage 1 ISO conformance.
Debugging this pattern in your own stack? Ask a Principal Architect directly or request a free 48-hour architecture sanity check: