Biting the Bullet: Predictive Speculative KV Replication for Bursty LLM Inference

Background

When an inference server receives an LLM request, it first hits a router such as SGLang Model Gateway or Dynamo, which decides which cluster to send its request to based on a routing policy. Then it hits a queue in that particular cluster, which may be one GPU or a tensor-parallel group of GPUs serving the same copy of one model.

You next need to understand KV cache management. In LLM generation, every request is a sequence of words. As long as two requests have the exact same prefix, they can reuse a lot of the computed math (the KV). It is important to note that the prefix must match exactly, so even a single token difference near the start of a request will break the KV cache.

This shared prefix is called the prefix KV cache. For Llama-3.3-70B, it is about 320 KiB per token, so even a 1,000-token cached prefix is roughly 320 MiB of KV. Typically, the system prompt and initial definitions are cached and heavily reused across many users.

This prefix KV can be stored in a few different places. First, it can be stored in GPU HBM, which is the fastest to access. It can also be stored in host RAM, which is the CPU RAM connected to multiple GPUs. Finally, it can be stored on disk or NVMe, which is the slowest tier and may be shared across multiple clusters. RDMA is a special data-transfer method that allows one node's GPU to access and directly read from another GPU's HBM, bypassing CPU and OS overhead, which makes it very fast. This is what BTB uses to quickly preload another GPU with the cache it needs.

The cost of regenerating the KV depends on the length of the prefix that was matched. The longer the prefix, the bigger the cost of generating compared to replicating or moving from an already existing source like RAM. The table below reports milliseconds to make the matched prefix KV available for one request at each prefix length, on the standard setup: one node = 4xH100 tensor-parallel, serving Llama-3.3-70B fp16 (KV ~320 KiB/token, MFU 0.5).

Clearly, prefill is much more expensive than keeping KV cache ready. This gives us the motivation: if we can see a burst incoming, it would be much faster to prewarm it with already computed KV.

Large, Batched Requests Break Routers

There are a few routing policies that routers such as Dynamo and SGLang Model Gateway provide out of the box, the most popular by far being cache-aware routing. Each has tradeoffs that show up under bursty workloads.

Least Load

The router selects the GPU with the lowest load (lowest incoming flight of requests). This is great when requests are unrelated, because it spreads work evenly. It is bad for same-prefix bursts, because it scatters the burst across cold replicas. Each cold replica then recomputes the same long prefix from scratch.

The best case is when many unrelated requests get evenly spread out, preventing any node hot spots.

The worst case is when a burst of same-prefix requests gets scattered across cold nodes, so none hit cached KV and each node has to do a full prefill.

Cache Aware

Cache-aware routing sends a request to the replica with the best prefix-cache match, then falls back to load balancing when the cluster is too imbalanced.

The best case is a steady trickle of similar-prefix requests, similar to many agentic chats, because each request keeps reusing the KV left warm by the previous request.

The worst case is a burst of same-prefix requests. Cache affinity pulls the whole burst toward the replica with the KV warm, which keeps a high cache hit rate but grows the queue size.

In both routers, you can see how a burst of same-prefix requests causes issues that hurt the end-user experience. In least-load routing, you are not utilizing the KV you already created. In cache-aware routing, bursts cause you to build up a huge queue.

Dataset Creation and Workload Pattern

When reading other papers that built routing algorithms or KV cache management algorithms, we found they often used Mooncake traces to backtest their theories. However, when we checked these datasets, we found that they were missing key pieces for this workload.

After going through them, we found two different problems. Some datasets did not contain arrival timestamps, so they could not fully recreate a burst scenario. Others had timestamps, but did not include prefix hashes or content, so we could not tell whether the requests were actually sharing the same KV. Of the datasets that contained both, the pattern barely showed up: Mooncake only reached a 2-request deep-prefix fanout, and ART-Chat reached 25.

We hypothesize this happens because public traces are often made from toy/demo traffic, chat tools, or internal employee coding/chat workloads. These traces are useful, but they do not fully cover real enterprise LLM workloads like data labeling, parsing PDFs, batch extraction, or sub-agent fanout, where many requests can share the same long prompt or document. That is what motivated us to create our own dataset, Bursted-ART. You can read more about how we created it in the appendix.

Biting the Bullet

What if, instead of waiting for a queue to build up before splitting across GPUs, or instead of blindly distributing requests across multiple GPUs without warmed KV cache, we could predict as soon as we saw a stream of requests coming in that a burst was incoming, then automatically share the prefix using RDMA?

We tested this in Infer-Sim, our open-source simulator for routing algorithms and cache policies for inference workloads. The implementation is intentionally simple and lives in 2-bite-the-bullet/bite_the_bullet.py.

The Detection System

The prototype has four constants:

The algorithm works like this: if the same Y-block-length prefix arrives X times within Z seconds, BTB marks that prefix as active and warms M replicas by using RDMA to send the KV to other GPUs. Later requests with the same prefix can then route to the least-loaded warm replica instead of all queueing on one cache-owning node or spreading blindly to cold nodes.

If the prefix is too short, the burst count has not fired, or no resident copy exists yet, BTB falls back to the normal cache-aware router. The animation below shows how BTB gets triggered and warms other GPUs as a burst comes in.

The best-case scenario is a sustained same-prefix burst where the first few requests reveal the pattern and the rest of the burst arrives after RDMA copies have finished. In that case, BTB keeps the cache-hit benefit of cache-aware routing, but gives the burst multiple warm queues instead of one hot queue.

The worst-case scenario is a burst that is too short, arrives too quickly, or starts from a brand-new prefix. If the model is extremely compute-heavy, or if the burst ends before copies finish, warming helps less because the latency is dominated by compute or queueing that KV movement cannot remove, or because there are not enough later requests left to amortize the RDMA copy.

The results were extremely positive on the Bursted-ART dataset:

Note: these are simulated results from Infer-Sim using the Bursted-ART workload, not live production traffic.

The result speedup is shown below:

Related Work

BTB is an project at the intersection of predictive resource managemment and cache-aware routing.

On the predictive side, PreServe proposes a load anticipator that forecasts incoming request load and maintains a KV cache memory usage projection map to guide proactive scaling. Although similar to BTB, this operates at cluster scale over longer timescales rather than per-burst replication over seconds. Cachewise predicts KV block reuse times for coding agents from the tool-call metadata and then evicts less aggressively when reuse is more likely. Learned Prefix Caching trains a small model on prompt content to predict whether a conversation will continue and uses that to decide what to evict. These papers show that predictive signals help, but they do not address the same prefix burst case with RDMA replication.

On the routing side, Preble and Mooncake discuss prefix cache reuse across many nodes, but they respond to load imbalance after it happened by moving KV around. The idea of duplicating work to cut tail latency goes back to Jeff Dean and Luiz Barroso's "The Tail at Scale". BTB is the specialization of that idea for KV replication over RDMA triggered on burst detection.

Future Work

1. We used Infer-Sim and the Bursted-ART dataset, which includes synthetic bursts. This was great for testing the mechanism, but the next step is to test BTB in a production serving stack with real inference requests, real queues, real scheduler behavior, and real cache pressure.
2. Speculative prefill. The idea here is to predict the burst before any requests actually arrive, then spend idle compute to start prefilling the shared prefix on extra replicas. Unlike RDMA warming, this does not require KV to already exist somewhere. This can be better because it could spin up new KV earlier, but it can also be worse because false positives spend real compute. One version we tested was partial fake prefill: instead of prefilling the entire shared prefix, prefill a certain percentage of it or prefill in chunks.
3. More cache actions beyond replicate, such as pin, evict, demote, and promote.
4. Make detection thresholds adaptive to burst size, queue load, and cache pressure.
5. Use the actual user query as a hint for when bursts are coming. For example, the router could look at whether the request includes a system prompt that looks like a data labeling job, a batch extraction job, or another prompt that is likely to be reused many times.

Appendix: Reproducing Bursted-ART

Bursted-ART starts with the original ART-Chat-2.5M replay windows, keeps normal ART traffic intact, and adds synthetic windows with synchronized long-prefix bursts. Each synthetic window models a data labeling job, batch scoring job, or sub-agent fanout: many requests arrive over the same 60-second window and share a 65,536-token prefix, while each request keeps its own suffix. We also add decoy jobs so the detector does not fire on any repeated prefix; it needs sustained reuse with enough future traffic to make warming worth it.

The generated rows preserve the request-level fields Infer-Sim needs for replay: arrival time, input length, output length, prefix block hashes, request/session/group IDs, source, trace ID, and metadata. The current split is 10 train windows and 30 test windows, or 25,600 train rows and 76,800 test rows.

The dataset construction code lives in the BTB repo. The important files are:

• Dataset generator: 3-workload/generate/generate_combined_dataset.py
• Dataset upload helper: 3-workload/generate/upload_to_hf.py
• Public dataset: shreybirmiwal/Bursted-ART
• Original ART dataset: alessiotoniolo/ART-Chat-2.5M
• Simulator replay loader: inference-sim/workload.py

To regenerate the dataset locally from the BTB repo:

python3 3-workload/generate/generate_combined_dataset.py \
  --synthetic-burst-window-s 60 \
  --out-dir 3-workload/generate/out/Bursted-ART