Why naive prefix-sticky routing makes tail latency 2.8x worse under parallel agent bursts, how capacity-aware routing and disaggregated Cloud TPUs fix it, and the distributed systems war stories uncovered along the way.
At KubeCon NA 2026, I gave a fifteen-minute talk on serving multi-agent workloads on Google Kubernetes Engine (GKE) and Cloud TPU v6e (Trillium). Fifteen minutes on stage is just enough time to frame the bottleneck, sketch the architecture, and show a benchmark table. It leaves almost no room to explore why standard prefix-caching setups break down in production, or to unpack the distributed systems traps that emerge once concurrent streaming traffic hits a cluster.
This post is the written companion to that talk. It dives into the design of FleetKV, an open-source, capacity-aware Key-Value (KV) routing architecture built on the Kubernetes Gateway API Inference Extension, and walks through how our inference stack had to evolve when sequential chat turned into parallel agent trees.
1. Why multi-agent fan-out breaks linear chat assumptions
Most LLM serving stacks were built around a simple assumption: conversations are linear. A user submits a prompt, reads the streamed response, pauses for a few seconds, and asks a follow-up. Context grows predictably, one turn at a time. Memory pressure climbs gradually, and standard load balancers—whether stateless round-robin or least-request—keep the cluster balanced.
Multi-agent systems break that assumption completely, turning a gentle linear ramp into an aggressive branching tree.
Imagine an incident-response or code-generation orchestrator handling an alert. To diagnose the problem, it first compiles a massive shared context: API schemas, service dependency graphs, runbooks, and recent logs, easily reaching 16,000 to 24,000 tokens before any reasoning happens. Instead of testing hypotheses sequentially, the orchestrator fans out. It spawns up to eight parallel sub-agents—specialized workers like log parsers, query planners, dependency checkers, patch generators, and verifiers. Every sub-agent inherits that exact same 20,480-token trunk, appends a brief role prompt, and hits the inference gateway in the same millisecond. Over a full multi-turn run where each branch ingests additional pod logs before joining, shared prefix blocks account for over 85% of all prompt tokens across the tree.
For a 30B-parameter model, 20,480 tokens of KV attention state occupy roughly 5 GiB of accelerator High-Bandwidth Memory (HBM). Behind a standard stateless Kubernetes service, those eight parallel branches scatter randomly across replicas. Seven out of the eight land on cold workers, forcing the TPU systolic arrays to recompute the entire 5 GiB trunk from scratch. Valuable accelerator cycles burn, and downstream tasks sit waiting for their first tokens.
Under an eight-way agent fork storm, naive longest-prefix routing concentrates every branch onto a single warm worker, inflating queue depth and evicting the shared trunk. FleetKV checks free HBM headroom first and spills excess branches before queues build up.
The obvious fix that makes tail latency worse
When platform teams realize how much compute goes into duplicate prefill work, the obvious instinct is to turn on prefix caching in the model server and make the gateway prefix-sticky. If one replica already holds that 5 GiB trunk in memory, why not steer every branch that shares it to that same worker?
Under light, sequential traffic, sticky prefix routing works well. But under an eight-way agent burst, it triggers a devastating thundering-herd stall that leaves tail latency far worse than plain round-robin.
Every sibling branch matches the warm trunk on the primary replica and piles into its execution queue, while neighboring accelerators sit completely idle. In our four-replica testbed, switching from stateless round-robin to naive prefix-sticky routing caused P95 Time to First Token (TTFT) to spike from 12.08 seconds to 33.38 seconds—nearly 2.8x slower at the tail under the exact same load.
Queue delay is only half the damage. Traditional aggregated servers run compute-heavy prompt prefill and memory-bandwidth-heavy token generation on the exact same TPU Matrix Multiply Units (MXUs). When a massive prefill burst arrives, it monopolizes the systolic arrays, starving active token decode streams and pushing P99 Inter-Token Latency (ITL) to 141.4 ms.
At the same time, as eight branches append thousands of reasoning tokens onto that single replica, they quickly exhaust its free memory. To make room for active generation, the cache manager begins evicting older blocks—frequently discarding pieces of the very 20,480-token parent trunk that attracted the requests in the first place. Across a 416-request run, naive sticky routing triggered 10,585 self-inflicted KV block evictions.
Serving benchmarks often obscure architectural tradeoffs by changing model weights between runs, testing tiny synthetic prompts, or reporting peak token throughput without tail-latency limits. Across all three stages in this study, we kept the workload strictly controlled: 30B-class weights paged in 256-token KV blocks, driven by two waves of eight concurrent orchestrators each launching an eight-way sub-agent burst (64 active branches, 416 streaming requests per stage) over a shared 20,480-token trunk. We measured usable goodput—tokens delivered within our 40 ms P99 latency target—rather than raw volume.
Because reserving multi-host Cloud TPU slices just to explore routing algorithms gets expensive quickly, we paired our GKE manifests with a trace-calibrated local digital twin modeled on Trillium prefill, HBM, and host-DMA timings, allowing the entire three-stage progression to be reproduced on a laptop in minutes.
2. Pairing capacity-aware routing with disaggregated TPUs
Fixing parallel fan-out takes coordination across two layers: the gateway has to know where a new branch will fit before forwarding it, and the TPU pool has to separate prompt ingestion from token generation so bursts cannot stall active streams.
FleetKV evaluates incoming branches at the gateway against a live two-tier radix index of on-chip HBM and host RAM. Dedicated prefill chips absorb heavy prompt bursts and stream KV state across jumbo-frame networking to isolated decode chips.
Admission gating at the inference gateway
Standard load balancers only see open HTTP connections and response times. They have no visibility into which 256-token prefix blocks reside in an accelerator's memory, or how close a worker is to triggering an eviction.
Built on Envoy's external processing filter within the Kubernetes Gateway API Inference Extension on GKE, FleetKV sits directly in the data path and maintains an in-memory radix tree of cached prefix blocks across the cluster. Rather than guessing cache state from past traffic, the router subscribes to real-time telemetry streams published by the inference workers whenever KV blocks are created, demoted to host memory, or evicted. The index tracks memory tiers separately: blocks cached in high-speed on-chip TPU memory save the most prefill time, followed by blocks staged in host memory, while both substantially outperform recomputing 20,480 tokens from cold weights.
When an eight-way agent burst arrives, FleetKV chunks the incoming prompt into 256-token blocks, walks the radix tree to count matched blocks on each worker, and evaluates a two-stage decision:
- A hard memory admission gate: Before cache locality is factored in, the router calculates how much new cache capacity the incoming branch will require across its uncached prompt tokens and generation budget. If a worker lacks sufficient unallocated memory headroom (including a safety reserve), or if its pending prefill queue exceeds a saturation threshold, that replica is bypassed immediately.
- Net latency scoring: Among workers with available headroom, the router estimates net latency in milliseconds: the compute time saved by cache hits minus the queuing delay behind in-flight prefill jobs and running streams.
When eight sibling branches arrive together, the first few route to the warm worker and reuse the 5 GiB trunk instantly. But as soon as that worker's memory buffer tightens, the admission gate trips. The gateway diverts remaining branches to peer workers, while the primary worker demotes idle blocks to host memory over high-speed interconnects rather than stacking requests into a thirty-second queue.
Host memory tiers and prefill-decode disaggregation
Even smart routing eventually hits a hardware ceiling if servers run compute-heavy prefill and bandwidth-heavy decode on the exact same silicon, or drop KV state whenever accelerator memory fills up.
On GKE with Cloud TPU v6e, our Stage 3 topology reshapes an eight-chip Trillium slice in two key ways:
First, each worker pairs its on-chip high-bandwidth memory with a 64 GiB shared-memory tier in host RAM. Under burst concurrency, older KV blocks demote over high-speed host DMA into system memory instead of being discarded. Pulling cached blocks back across PCIe takes a fraction of the time needed to recompute 256-token attention blocks on the matrix units, cutting lost block evictions to zero.
Second, rather than deploying two identical four-chip aggregated servers, we split the eight chips into two specialized pools: a four-chip Prefill pool and a four-chip Decode pool, connected over jumbo-frame VPC networking. Prefill workers absorb ragged prompt bursts using custom attention kernels tuned for 256-token blocks, then stream the resulting KV state across the network to a Decode worker with available headroom. Because Decode chips never have to pause to crunch twenty-thousand-token prompts, P99 inter-token latency drops to a rock-steady 27 ms on real hardware.
3. Three distributed-systems traps from testing
Architectural diagrams always look clean once everything is running. But bringing up the gateway router, the digital twin, and the GKE pools under burst concurrency surfaced three subtle distributed systems bugs that initially masqueraded as model-server performance drops.
Trap 1: Holding prefill reservations during token streaming
Cache telemetry travels asynchronously from workers back to the gateway. If eight sub-agents arrive in the same millisecond, all eight see the same idle snapshot and stampede toward the same replica unless the router registers an optimistic reservation the moment it assigns each request.
In our first implementation, the router held that entire reservation—accounting for both memory capacity and pending prefill compute—until the client HTTP stream closed. For a 500-token streamed answer, an HTTP connection stays open for ten to fifteen seconds, even though prompt prefill finishes in roughly 300 milliseconds. Because the router continued counting those 20,480 prompt tokens as active prefill load throughout the entire decode phase, its queue estimator assumed idle prefill chips were saturated and routed new requests away from warm caches.
Splitting reservations into two distinct phases solved the problem. In streaming inference, the arrival of HTTP response headers back at the gateway marks the exact moment Time to First Token is achieved, confirming that prefill is complete. By releasing the prefill compute lease on response headers while retaining the lightweight memory block reservation until stream termination, queue accounting immediately aligned with physical hardware reality.
Trap 2: The Kubernetes virtual-IP blind spot
To keep its radix tree in sync with worker memory, the router subscribes to cache-event streams published by the prefill fleet. Early on, we pointed the router at a standard Kubernetes Service virtual IP fronting those workers.
Virtual IPs work great for short-lived HTTP calls, but they fail silently for long-lived messaging sockets. Kubernetes performs load balancing on a virtual IP only once, during the initial TCP handshake. When the router opened its persistent subscription socket, kernel connection tracking locked that connection to a single random prefill pod. The router diligently indexed every block cached on that one pod while remaining completely blind to cache changes across the rest of the fleet.
Switching worker discovery to a headless Kubernetes service eliminated virtual-IP translation from the telemetry path. DNS queries return the individual pod IPs of every active prefill worker, allowing the router to establish and maintain direct, parallel subscriptions across the entire fleet as pods scale up or down.
Trap 3: Block-boundary drift and randomized hash seeds across turns
During multi-turn testing, first-turn agent forks hit the prefix cache reliably, but second- and third-turn follow-ups kept missing unexpectedly, sending tail latency soaring back up.
Two distinct mismatches caused these phantom cache misses:
First, paged KV caches chunk token sequences into fixed 256-token blocks, chaining each block's cryptographic digest to its predecessor. Real conversation turns rarely end on clean multiples of 256. If Turn 1 ends at 20,600 tokens, it completely fills eighty blocks and leaves a 120-token remainder. When Turn 2 appended tool output, an early indexing shortcut began hashing the new turn starting at index zero instead of prepending the 120-token remainder to complete block eighty-one. This shifted every subsequent block boundary out of phase with the model server's memory allocator. Preserving an unaligned token buffer across turns restored boundary alignment.
Second, runtime environments like Python randomize string hash seeds at process startup by default. Unless deterministic hashing is explicitly enforced across every worker and gateway container, two processes evaluating the exact same sequence of 256 tokens calculate different block keys and can never agree on a cache hit.
4. Benchmark results: local digital twin and Cloud TPU v6e
Running all three stages under the same 64-branch fork-storm workload puts the latency and goodput trade-offs in plain numbers. Below are both the 416-request sweep from our local digital twin and reference hardware runs on an eight-chip Cloud TPU v6e slice comparing two four-chip aggregated servers (Stages 1 and 2) against one four-chip Prefill pool plus one four-chip Decode pool (Stage 3).
Stage 2 doubles cache hits on paper while stalling tail latency past 33 seconds and cutting usable goodput by 41%. Stage 3 removes lost evictions, lifting usable goodput 4.26x on the digital twin and 2.55x on Cloud TPU v6e hardware.
| Metric | Stage 1: Stateless Round-Robin | Stage 2: Naive Prefix-Sticky | Stage 3: FleetKV + Disaggregated P/D | Net Shift (S3 vs. S1) |
|---|---|---|---|---|
| Digital Twin · Prefix Hit Rate | 30.8 % | 62.5 % (HBM thrash) | 86.1 % | +55.3 pts |
| Digital Twin · Median TTFT (P50) | 6,498 ms | 5,581 ms | 1,153 ms | -82.3 % |
| Digital Twin · Tail TTFT (P95) | 12,083 ms | 33,377 ms (herd stall) | 2,507 ms | -79.2 % |
| Digital Twin · Decode Jitter (P99 ITL) | 133.1 ms | 141.4 ms | 33.1 ms | -75.1 % (< 40 ms SLO) |
| Digital Twin · Cluster Goodput | 31.6 tok/s (1.0x) | 18.5 tok/s (0.59x) | 134.7 tok/s | 4.26x Goodput |
| Digital Twin · Lost KV Evictions | 17,377 | 10,585 (self-eviction) | 0 | Eliminated |
| Cloud TPU v6e · Prefix Hit Rate | 19.4 % | 52.8 % (thrashing) | 91.6 % | +72.2 pts |
| Cloud TPU v6e · Median TTFT (P50) | 2,710 ms | 1,180 ms | 315 ms | -88.4 % |
| Cloud TPU v6e · Tail TTFT (P95) | 3,420 ms | 3,890 ms (herd stall) | 485 ms | -85.8 % |
| Cloud TPU v6e · Decode Jitter (P99 ITL) | 116 ms | 98 ms | 27 ms | -76.7 % |
| Cloud TPU v6e · Cluster Goodput | 1.0x | 1.35x | 2.55x | 2.55x Goodput |
The vanity metric trap
Watching cache hit rate in isolation would have led us straight into the Stage 2 trap. Naive sticky routing more than doubled prefix hits compared to stateless round-robin (jumping from 30.8% to 62.5% on the twin, and from 19.4% to 52.8% on hardware). A dashboard tracking only cache reuse looks fantastic.
Yet actual usable goodput on the twin collapsed by 41%—plummeting from 31.6 down to 18.5 tokens per second—while P95 TTFT blew past 33 seconds because all eight branches queued behind a single replica.
Adding the memory admission gate and host spillover in Stage 3 delivered real cache locality without the stampede. Prefix hit rates climbed to 86.1% on the twin and 91.6% on Cloud TPU v6e with zero lost block evictions, pulling hardware P95 TTFT down to 485 ms. Isolating decode workloads onto dedicated chips slashed hardware P99 decode jitter from 116 ms to 27 ms, ensuring smooth token streams even when neighboring orchestrators launch heavy prompt bursts.
5. Four architectural rules for serving agent trees
Teams scaling multi-agent workflows, tree search, or parallel tool calls on Kubernetes can avoid these pitfalls by keeping four practical principles in mind:
- Gate prefix stickiness on memory headroom: Routing on longest prefix match without verifying available memory turns shared system prompts into hot-spot magnets. Always balance saved compute against live queue depth, and spill requests to peer workers before a busy replica is forced to evict warm blocks.
- Synchronize block boundaries and hashing: Gateways and model servers must partition token streams on identical boundaries and share deterministic hashing. On Cloud TPU v6e, 256-token blocks keep attention kernels well within scalar memory limits while keeping radix trees fast and compact.
- Use headless discovery for stateful telemetry: Standard Kubernetes virtual IPs pin persistent pub/sub connections to a single pod. Use headless discovery filtered to prefill workers for telemetry streams, and enable jumbo frames across the VPC so large cross-pool KV transfers never fragment.
- Decouple prefill from decode: Treat prompt ingestion and token generation as two entirely separate workloads—both physically (in dedicated prefill and decode pools) and logically (releasing prefill compute leases the moment first-token response headers arrive).
Slides, Digital Twin, and GKE Reference Manifests
All Kubernetes manifests, gateway routing components, fork-storm workload generators, and the local TPU digital twin from the KubeCon NA 2026 talk are available under Apache 2.0 in our Google Developer Expert reference repository:
Labels: AI Systems, Cloud TPU, Envoy, GKE, Google Developer Expert, KubeCon, Kubernetes, LLM Serving, OpenXLA, vLLM

Comments
Post a Comment