Distributed LLM Serving: Prefix Caching and Prefill-Decode Disaggregation
A technical guide to Preble's prefix-aware scheduling and DistServe's goodput-driven disaggregation, connecting cache placement, KV-transfer cost, fairness, and tail latency.
Modern LLM serving is no longer only a problem of fitting a model onto GPUs and batching requests. Many applications spend most of their tokens on long, repeated prompts, then generate only a short answer. The expensive work therefore shifts from output generation toward prompt prefill, KV-cache management, and routing. A cluster can leave a large share of that work unused if identical prompt prefixes are recomputed, or it can create a new bottleneck if every request is sent to the GPU holding the longest prefix.
This article follows UCSD CSE 291 Lecture 13, using Preble as the primary paper and DistServe as the complementary prefill-decode disaggregation study. The two systems answer different parts of the same question: where should KV state live, when is it worth moving or reusing, and which scheduling policy keeps average latency, tail latency, and per-GPU efficiency acceptable at the same time?
The central distinction is between a cache hit and a good placement. A cache hit removes computation. A good placement also accounts for the queue that the request joins, the memory it may evict, the fairness of the waiting room, and the cost of moving KV state if the phases run on different workers.
1. Prompt-heavy workloads make serving a cluster problem
Prompt engineering, few-shot prompting, tool descriptions, agent system messages, retrieved documents, and long video or code contexts all increase the amount of context sent before the model produces its answer. A conventional request-level round-robin scheduler sees only that a request arrived. It does not see that two requests already share 8,000 prompt tokens, or that keeping their common prefix on one GPU would avoid most of the prefill computation.
Preble's workload study gives the lecture its concrete motivation. Across five prompt-heavy workloads, prompts were 37 to 2,494 times longer than generated outputs. Between 85% and 97% of prompt tokens were shared with at least one other request, and a common sequence was reused by 8.6 to 126 requests on average.
These traces break two assumptions behind simple load balancing. First, requests are not exchangeable units of work: a 12,000-token request that hits 10,000 cached tokens is much cheaper than an equal-sized request with no match. Second, the best server for one request is not necessarily the least loaded server in terms of active requests. It is the server whose saved prefill work, current compute load, and potential eviction cost produce the best end-to-end latency.
| Observed property | Serving consequence | Naive policy failure |
|---|---|---|
| Prompts dominate output length | TTFT and prefill compute become a large part of cost. | Optimizing only generated tokens per second ignores most of the work. |
| Most prompt tokens are shared | KV reuse can remove repeated prefill work. | Round-robin routing scatters related requests and recomputes the same prefix. |
| Popularity is skewed | Caches for hot prefixes become hot compute resources. | Longest-prefix-first routing overloads one GPU and inflates queueing delay. |
| Arrival load changes quickly | Placement must adapt without losing useful state. | A one-time optimal assignment becomes imbalanced minutes later. |
2. Prefill and decode have different bottlenecks
An autoregressive request has two execution phases. Prefill processes the prompt tokens in parallel, builds the KV cache for every layer, and produces the first output token. Decode then generates one token per iteration, reading the model weights and the growing KV cache at every step. Prefill typically has more parallel arithmetic per byte and can become compute-bound; decode performs much less work per loaded byte and is generally memory-bandwidth-bound.
Applications expose this difference through two latency objectives:
- TTFT, or time to first token, includes prompt processing, queueing, and first-token generation.
- TPOT, or time per output token, measures the average delay between subsequent generated tokens.
For a request with $N_{\mathrm{out}}$ output tokens, a useful first-order latency model is:
$$T_{\mathrm{req}}=\mathrm{TTFT}+(N_{\mathrm{out}}-1)\mathrm{TPOT}$$
The model is intentionally simple, but it explains why one throughput number is insufficient. A batch containing a long prefill can improve token throughput while delaying every active decode. Conversely, a decode-heavy batch may use memory bandwidth efficiently while making a newly arrived user wait for prompt processing. The tail of either distribution can violate an application's SLO even when average throughput looks healthy.
The KV cache is also large enough that caching policy is a first-class resource decision. Its size can be written as:
$$S_{\mathrm{KV}}=2\,N_{\mathrm{layer}}N_{\mathrm{kv}}d_hTb$$
Here the leading factor 2 accounts for K and V, $N_{\mathrm{kv}}$ is the number of KV heads, $d_h$ is the head dimension, $T$ is the sequence length, and $b$ is the number of bytes per element. The lecture's Llama 2 7B example uses FP16 and a 4,096-token request to reach about 2 GB. Caching is therefore not a small software index beside a model. It is another large, structured working set that must be allocated, located, evicted, and sometimes transferred.
This is where LLM caching differs from a conventional key-value store. Compute and state are co-located in GPU memory, only a prefix that exactly matches earlier model state is useful, and the computation needed to recreate an evicted entry is not known precisely until the request runs. The scheduler is managing both memory and future computation.
3. Preble: exploit a long hit or explore a lighter GPU
Preble targets distributed serving of long and shared prompts. Its central algorithm is called E2, for exploration plus exploitation. The intuition is simple:
- Exploit when an existing GPU already owns most of the prompt, because recomputing that prefix elsewhere would waste more work than queueing locally.
- Explore when the match is small relative to the missing suffix, because a less loaded GPU may finish the request sooner even after recomputing more tokens.
If a prompt contains $T$ tokens and $h$ of them match a cached prefix, the saved computation is proportional to $h$, while the missing computation is proportional to $T-h$. In the lecture's simplified token-count view, the greedy exploitation test is:
$$L_{\mathrm{saved}}>L_{\mathrm{miss}}\quad\Longleftrightarrow\quad h>T-h$$
When this condition holds, routing to the GPU with the longest match is often preferable. If several GPUs have the same match, Preble chooses the one with the lowest prompt-aware load. When the condition fails, it compares all GPUs using a cost model rather than allowing the cache to make the decision.
The full exploration cost for assigning request $R_k$ to GPU $i$ can be summarized as:
$$C_i=L_i+M_i+P_i$$
Each term answers a different question:
- $L_i$ is recent prefill and decode work on GPU $i$, estimated over a history window. Preble's default window is three minutes.
- $M_i$ is the estimated recomputation cost of cache entries that would be evicted, weighted by how frequently they are reused.
- $P_i$ is the prefill cost of the unmatched tokens in the new request.
This structure is more useful than a generic load average. A GPU with many active requests may still be the right destination if it owns a 10,000-token prefix. A lightly loaded GPU may be the wrong destination if admitting the request would evict a highly reused tool schema. Preble keeps token counts and profiled timing models rather than instrumenting every kernel inside the data path.
Global placement, local iteration scheduling
Preble uses a two-level scheduler. The global scheduler maintains a prefix tree spanning the cluster, observes request history and cache ownership, and performs coarse-grained request placement. Each GPU then runs a local scheduler that forms the next batch after every model iteration. This division matters. Prompt locality is a cluster-wide property, while batch composition, KV-memory pressure, eviction, and active decode state change locally at iteration granularity.
The global layer must not become a centralized performance bottleneck. Preble uses parallel tokenization, asynchronous request handlers, lock-free radix-tree reads, atomics for ownership and request counters, and background work for rebalancing and eviction bookkeeping. In the paper's measurements, the global scheduler processes requests fast enough that it is not the serving bottleneck for the tested workloads.
Placement is also not permanent. When one GPU becomes substantially hotter than the lightest GPU, Preble redirects future exploitation traffic. If a hot prefix remains overloaded, it can replicate that prefix and split its subtree across GPUs. This is an important transition from a storage question to a compute question: the cache entry is copied because its popularity has turned it into a bottleneck.
4. Why a longer prefix match can increase latency
The counterintuitive case is easy to construct. Suppose GPU 1 caches a popular agent system prompt plus branch A. Every request for branch A has the longest match on GPU 1, and a locality-only router sends all of them there. GPU 2 and GPU 3 are idle. The cache hit is real, but GPU 1 still has finite prefill capacity and a growing queue. At some arrival rate, the time spent waiting behind other exploitative requests exceeds the milliseconds saved by avoiding recomputation on GPU 2.
Always exploiting the longest match can therefore increase mean latency and, more sharply, p99 latency. The policy favors requests belonging to hot prefixes, which receive repeated cache hits and can dominate the waiting queue. A rare request that shares only the common system prompt may be pushed behind them even when its own branch is cheap to compute elsewhere.
Preble's local scheduler addresses fairness with prioritized waiting queues. Requests are grouped by cached-token percentage and assigned quotas at the next batching decision. This avoids both extremes: strict first-come-first-served ignores readily reusable prefixes, while longest-prefix-match can starve lower-hit requests. The point is not to maximize the cache-hit rate. It is to maximize useful request completion while preserving bounded waiting time across request classes.
A workload where reuse harms tail latency
Consider three classes sharing an 8,000-token system prompt:
- Class A follows with a 200-token popular tool instruction and arrives at 100 requests per second.
- Class B follows with a 400-token rare customer-specific instruction and arrives at 5 requests per second.
- Class C has only the common prefix and arrives at 20 requests per second.
If GPU 1 caches A and B during a warm period, a longest-prefix rule sends nearly all A and B traffic to GPU 1. During a burst, A saturates the queue. B waits behind a class whose reuse ratio is higher but whose arrival rate is far greater. C may also be sent to GPU 1 because even the common-prefix match is the longest available, despite the fact that recomputing it on an idle GPU would finish much sooner.
A good evaluation should not report only aggregate cache-hit percentage or average latency. It should sweep prefix popularity skew, cache capacity, and burst intensity while reporting:
- TTFT and end-to-end latency per request class, including p95 and p99;
- SLO attainment for each class, not only across the whole trace;
- queueing delay separately from prefill and decode time;
- eviction and recomputation cost caused by each placement;
- a fairness measure such as Jain's index or the maximum normalized slowdown.
This is the practical meaning of the lecture's first discussion question. Prefix reuse is beneficial only after accounting for the load carried by the cache owner. The optimal router may deliberately sacrifice a small amount of reuse to protect tail latency and long-term cluster balance.
5. Co-locating prefill and decode creates interference
Prefix caching reduces repeated work, but it does not solve the conflict between the two phases. In a shared batch, a long prefill step occupies the GPU while decode requests are waiting to advance by one token. The decode work is frequent and latency-sensitive; the prefill work is large and throughput-oriented. Mixing them can make both objectives harder to meet.
There are two broad responses:
| Approach | Mechanism | Main benefit | Main cost |
|---|---|---|---|
| Chunked prefill | Split a prompt into ordered chunks and interleave them with decode iterations. | Retains a shared GPU pool and uses compute capacity left idle by decode. | More kernel launches, repeated prefix reads, and a later final prefill chunk for TTFT. |
| P/D disaggregation | Run prefill and decode workers separately, then transfer KV state. | Allows different batching, parallelism, replication, and SLO targets for each phase. | Adds KV transfer, placement constraints, minimum fleet size, and burst imbalance between pools. |
Chunking changes the granularity of prefill, not the final size of the KV cache. A chunk attends to the cached state from earlier chunks while adding new K/V entries. Small chunks give decode requests more frequent opportunities to run, but increase launch overhead and repeated reads. Large chunks improve intra-step parallelism but create longer stalls. A mixed batch can exploit idle compute inside decode, yet the first token still waits for all prompt chunks to finish.
6. DistServe optimizes goodput, not raw throughput
DistServe starts from an observation that prefill-only and decode-only workers have very different capacity curves. A goodput objective captures this better than aggregate tokens per second. For a TTFT target $S_T$, a TPOT target $S_O$, and a target attainment rate $\alpha$, per-GPU goodput is the largest request rate that satisfies both latency constraints for at least the required fraction of requests:
$$\Gamma=\max\left\{\lambda:\Pr(\mathrm{TTFT}\le S_T)\ge\alpha\ \mathrm{and}\ \Pr(\mathrm{TPOT}\le S_O)\ge\alpha\right\}$$
This definition is stronger than throughput. A system can process many requests per second by allowing a long tail to miss latency targets. Goodput counts only a request rate that remains useful under the service contract.
The lecture uses a concrete A100 example for a 13B model with 512 input tokens and 64 output tokens. Co-located serving reaches about 1.6 requests per second per GPU under the stated 90% SLO attainment target. Serving prefill alone reaches 5.6 requests per second, while serving decode alone reaches 10. Allocating two prefill GPUs and one decode GPU gives a system rate of:
$$\min(2\times5.6,\ 1\times10)=10\ \mathrm{requests/s}$$
The per-GPU rate is therefore $10/3=3.3$ requests per second, about 2.1 times the co-located result. The general two-pool expression is:
$$\Gamma_{\mathrm{system}}(g_p,g_d)=\frac{\min(g_p\Gamma_p,\ g_d\Gamma_d)}{g_p+g_d}$$
The equation looks simple, but every term depends on a placement. The best number of prefill GPUs, decode GPUs, tensor-parallel degree, pipeline-parallel degree, and even node location must be selected together. DistServe searches this space using workload characteristics, latency objectives, and simulated phase performance. It then scales replicas to the requested traffic rate.
The paper reports up to 7.4 times more requests or 12.6 times tighter SLOs while meeting latency targets for more than 90% of requests. These headline numbers should be read as workload-dependent results, not constants. Their meaning depends on the selected TTFT and TPOT thresholds, arrival pattern, model, network, and SLO attainment target.
7. KV transfer is the tax on disaggregation
Disaggregation moves the prompt's KV cache from a prefill worker to a decode worker. Even if the transfer is fast, it changes the architecture. The scheduler now needs producer-consumer handoff, memory ownership, buffer lifetime, failure handling, and placement constraints in addition to request routing.
For average request rate $\lambda$ and KV-cache size $S_{\mathrm{KV}}$ per request, the required transfer bandwidth is approximately:
$$B_{\mathrm{KV}}\approx\lambda S_{\mathrm{KV}}$$
DistServe's lecture example makes the scale clear. The KV cache of one 512-token request on OPT-66B is about 1.13 GB. At 10 requests per second, the cluster must move about 11.3 GB per second, or 90 Gbps. This is not a reason to reject disaggregation, but it is a reason to place prefill and decode workers close together.
DistServe's pull-based design opens an IPC handle on the prefill side and lets the decode worker copy through that handle, backed by a CUDA kernel and NCCL. Placement tries to keep the transfer on NVLink where possible. On clusters with lower network affinity, the placement algorithm can require overlapping model stages to remain on the same node, and it avoids sending the KV cache across nodes that cannot support the bandwidth.
On the paper's OPT-175B and ShareGPT experiment, KV transfer accounted for less than 0.1% of total latency, and more than 95% of transfers completed in under 30 ms. Those results depend on the testbed and placement policy. They demonstrate that transfer can be hidden when the topology is controlled, not that network cost disappears on every cluster.
There are also compatibility constraints. A receiving worker must use a model version, tokenizer, adapter configuration, positional setup, tensor layout, and model-parallel stage that makes the transferred KV state valid. A cache entry should not be reused merely because the token IDs match if the model or attention state differs.
When separation can lose
Prefill-decode disaggregation is not universally better than a shared pool. It raises the minimum GPU count: even a model that fits on one GPU needs separate prefill and decode resources. Short requests may save little decode time and cannot amortize the transfer. Bursty or skewed traffic can leave one pool idle while the other queues. A fair comparison should therefore include a well-tuned chunked-prefill system, not only a poorly configured co-located baseline.
8. From two systems to a production cache architecture
Mooncake extends the disaggregated idea to a KVCache-centric architecture. It separates prefill and decode clusters, builds a cache across GPU memory, CPU DRAM, and SSD, uses an SLO-aware scheduler, and performs prediction-based early rejection when overload cannot be served within latency targets. Its reported results include up to a 525% throughput increase in simulated scenarios and 75% more requests on a real workload. The architectural lesson is broader than the percentages: KV state becomes a managed tier between computation and storage, and admission control becomes part of serving quality.
The lecture also shows convergence in production systems: Preble's ideas sit in the lineage of prefix-aware serving, while DistServe's separation is visible in newer systems such as SGLang's prefill-decode disaggregation and NVIDIA Dynamo. The design space is not a binary choice between caching and disaggregation. A production system may use prefix-aware prefill placement, transfer KV state to a decode pool, then reuse hot prefixes on multiple prefill replicas.
That combined design raises additional questions:
- Who owns a cache entry while it is being transferred to another worker?
- Can an eviction race with a live decode or an in-flight transfer?
- Should a hot prefix be replicated, migrated, or recomputed?
- Does a shared prefix cross a tenant boundary or reveal that another tenant used the same content?
- When demand makes the SLO impossible, which requests should be rejected early instead of waiting for a guaranteed timeout?
These are the places where a serving paper becomes an operational design. The cache cannot be treated as a transparent optimization. It has ownership, lifetime, security, and failure semantics.
9. How to read the results and what to test
The lecture's systems are evaluated on different models and workloads: Preble used Mistral 7B on two- and four-A6000 configurations and Llama-3 70B on eight H100 GPUs; DistServe evaluated models from 13B to 175B on A100 clusters. Their headline speedups therefore answer different questions. Preble mainly asks how to avoid recomputation without overloading a hot GPU. DistServe asks how to allocate and place separate phase-specific resources under TTFT and TPOT constraints.
A credible evaluation should compare at least four policies: round-robin with recomputation, locality-only routing, cost-aware routing, and a well-tuned co-located or chunked-prefill baseline. It should sweep prefix-sharing ratio, popularity skew, context length, KV transfer bandwidth, and queue load. The output should include TTFT, TPOT, end-to-end latency, p99, SLO attainment, transfer bytes, cache-hit ratio, eviction cost, and per-GPU goodput.
A practical design review can use the following checklist:
- Define TTFT and TPOT SLOs separately, including the target attainment rate.
- Measure the real prompt-length, output-length, and prefix-sharing distributions.
- Key cached state by model, tokenizer, adapter, prompt template, and relevant attention configuration.
- Track queueing delay, eviction cost, and recomputation cost, not only cache-hit percentage.
- Evaluate fairness and per-class p99 under hot-prefix bursts.
- Place prefill and decode workers using measured network topology, not nominal cluster diagrams.
- Define cache ownership and eviction rules for asynchronous transfers and active decodes.
- Compare against chunked prefill before paying the complexity cost of disaggregation.
10. The lecture's discussion questions
Why can routing to the longest matching prefix increase latency?
The match reduces prefill work but says nothing about the queue at the cache owner. If every request for a popular prefix exploits the same GPU, queueing delay can grow faster than the saved computation. Preble balances the two by exploiting only when the matched prefix dominates the remaining prompt, choosing the lightest owner among equal matches, and otherwise exploring the cluster with a cost that combines recent load, eviction cost, and new-request prefill cost.
How do global placement and local scheduling interact?
The global scheduler decides which GPU should receive a request using cluster-wide prefix location and load history. The local scheduler decides which waiting requests run in the next iteration using cache locality, fairness quotas, memory pressure, and chunk size. Placement determines what locality is available; local scheduling determines whether that locality is used efficiently without starving other requests.
When can greater prefix reuse hurt fairness or tail latency?
It hurts when a high-hit class consumes the capacity of a small set of cache-owning GPUs, while lower-hit requests wait behind it despite having cheaper alternatives elsewhere. The right response is to evaluate the tradeoff per class under skewed popularity and bursts, using SLO attainment and p99 rather than aggregate hit rate alone.
Bottom line
Prefix caching and prefill-decode disaggregation both try to avoid wasted work, but neither is a local optimization. Prefix reuse changes where computation and state should live. Disaggregation changes which kinds of GPUs should perform each phase and what network path must carry the handoff. A production serving system needs a joint answer: cache placement, request routing, iteration scheduling, KV ownership, and admission control all influence the same latency SLO.
The most durable design rule from the lecture is to optimize the contract, not a proxy. Cache-hit rate, tokens per second, and GPU utilization can all improve while users experience worse tail latency. TTFT, TPOT, per-class SLO attainment, and per-GPU goodput make the tradeoffs visible enough to make a defensible choice.
Sources
- Primary lecture: UCSD CSE 291, Lecture 13: Distributed LLM Serving I, Yiying Zhang, November 10, 2026.
- Vikranth Srivatsa, Zijian He, Reyna Abhyankar, and Yiying Zhang, Preble: Efficient Distributed Prompt Scheduling for LLM Serving, ICLR 2025.
- Yinmin Zhong et al., DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving, OSDI 2024.
- Ruoyu Qin et al., Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving.
- Preble and DistServe figures in this article are page crops from the lecture slides. Numerical claims are attributed to the corresponding paper or slide.
Source:UCSD CSE 291A Lecture 13https://cseweb.ucsd.edu/~yiying/cse291a-fall26/slides/lecture13-distributed-llm-serving-i.pdf