SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills

ArXiv: 2308.16369

🎯 Pitch

Decode tokens can cost 200x more than prefill tokens, yet SARATHI makes decodes up to 10x faster by letting them piggyback on prefill’s heavy compute—turning a fundamental GPU waste into a free ride. This not only slashes per-token cost but also eliminates pipeline bubbles, unlocking up to 1.91× end-to-end speedup for giant models like GPT-3.

---

1. Executive Summary

This paper introduces SARATHI, an LLM inference system that addresses GPU underutilization during the memory-bound decode phase and pipeline bubbles in multi-GPU deployments through two techniques: chunked-prefills (splitting a long prefill into equal-sized compute-saturating chunks) and decode-maximal batching (constructing each batch from one prefill chunk plus as many decode requests as memory allows, so decodes "piggyback" on the prefill's weight fetches). On LLaMA-13B with an A6000 GPU, SARATHI improves decode throughput by up to 10× and end-to-end throughput by up to 1.33×; on LLaMA-33B with an A100 GPU, decode throughput rises by up to 4.25× with a 1.25× end-to-end gain. When applied to GPT-3 with 8-way pipeline and 8-way tensor parallelism across 64 simulated A100 GPUs, decode-maximal batching reduces pipeline bubbles by 6.29×, yielding a 1.91× end-to-end speedup — establishing that pipeline parallelism becomes a viable deployment strategy only when micro-batch compute times are rendered uniform by these techniques.

2. Context and Motivation

The Core Problem: LLM Inference Has Two Radically Different Phases That Don't Play Well Together

Every LLM inference request goes through two distinct phases, and they have fundamentally mismatched compute characteristics. The prefill phase processes the entire input prompt in parallel — all tokens at once — producing the key-value (KV) cache that subsequent generation will need. Because this involves large matrix-matrix multiplications, the prefill phase saturates GPU compute even at tiny batch sizes. The decode phase generates output tokens one at a time autoregressively, where each step processes only a single token per request against the accumulated KV cache. This involves vector-matrix multiplications that leave the GPU severely memory-bound: the arithmetic intensity (compute operations per byte of memory traffic) drops by more than two orders of magnitude compared to prefill.

The paper's motivating measurements (Figure 3) quantify just how extreme this mismatch is. On a single LLaMA-13B layer running on an A6000 GPU with a sequence length of 1024:

"the decode cost per-token is 200×, 100×, and 16.7× that of prefill at batch size of 1, 2 and 18, respectively."

This means a token generated during decoding costs up to 200 times more GPU time than a token processed during prefill. Since every request goes through exactly one prefill pass but potentially hundreds of decode passes (one per generated token), the decode phase dominates total inference cost, yet it runs at the lowest GPU utilization. The paper captures this tension: the prefill is "bursty" and compute-efficient, while the decode is a "potentially long tail of inefficient decodes which results in poor overall GPU utilization."

Why This Problem Matters: The Infrastructure Implications Are Enormous

Four factors make this mismatch critically important in practice.

First, the scale of LLM deployment has made inference the dominant GPU workload. The paper opens by citing the explosion of LLM-powered applications — conversational engines (ChatGPT, Claude, Character AI), search (Bing AI, Google Bard, Perplexity AI), and code assistants (GitHub Copilot, Amazon CodeWhisperer, Replit Ghostwriter) — and argues that "the significant GPU compute required for inference on these large models, coupled with their widespread usage, has made LLM inference the dominant GPU workload." Optimizing inference throughput therefore translates directly to infrastructure cost savings at massive scale.

Second, the decode phase is memory-bound precisely in the batch-size regime that fits on real hardware. Figure 4's arithmetic intensity analysis reveals the fundamental limitation: while prefill operations have high arithmetic intensity even at batch size 1 (all operations are compute-bound), decode operations need absurdly large batch sizes to become compute-bound. For LLaMA-13B on A6000 with 1K sequence length, the paper profiles a single layer to bypass memory constraints and finds that "decode saturates at a much larger batch (e.g., 256 with 1024 sequence length)." But such large batches are "infeasible to run with the full model" — the actual maximum batch size with the full model is only 18 requests at 1K sequence length. There is a yawning gap between the batch size that fits in GPU memory (constrained by model weights and KV cache) and the batch size needed for compute saturation. This means decodes are structurally inefficient, not just a matter of tuning.

Third, increasing batch size through model parallelism introduces its own problems. The obvious solution — shard the model across more GPUs so each GPU's memory pressure decreases, allowing larger per-GPU batch sizes — requires careful design. Tensor parallelism (TP) shards each layer across GPUs within a node, dividing both model weights and KV cache. This scales the per-GPU batch size linearly but requires two all-reduce operations per layer (one in attention, one in FFN) on the critical path, demanding expensive high-bandwidth interconnects like NVLink. Pipeline parallelism (PP) splits the model layer-wise across GPUs, with much lower communication overhead (only point-to-point activation passing) and a superior compute-to-communication ratio. The paper explicitly notes that PP is "the only viable model-parallelism approach when high-bandwidth connectivity like NVLink is unavailable at cluster-scale." But PP has its own Achilles' heel: pipeline bubbles.

Fourth, pipeline bubbles in LLM inference have been systematically underestimated. Most prior work assumed that since inference involves only forward passes (no backward pass like training), micro-batching could eliminate pipeline bubbles entirely. The paper directly challenges this assumption. Orca [48], a state-of-the-art iteration-level inference scheduler, claimed that iteration-level scheduling "eliminates bubbles in pipeline scheduling" (citing Orca's Figure 8). SARATHI demonstrates that this claim is incorrect: even with iteration-level scheduling, heterogeneous batch composition creates significant bubbles.

Prior Approaches and Their Specific Failures

The paper builds its case by identifying three categories of prior approaches and showing precisely where each falls short.

1. Request-Level Scheduling (FasterTransformer, and historically most inference engines)

Request-level schedulers pick a batch of requests, execute all of them to completion, and only then pick the next batch. To handle variable-length requests, shorter requests must be padded to match the longest one in the batch, which "does wasteful work instead of exiting early." But the deeper problem is the binary separation of prefill and decode: the system processes entire batches that are either entirely in prefill or entirely in decode. During a decode-only batch, the GPU operates at drastically low utilization because the batch size is memory-constrained below the compute-saturation point. The paper quantifies this in Table 2: a decode-only batch of 4 requests with 1K sequence length spends 12.49 milliseconds per token, while the corresponding prefill-only batch spends only 0.229 milliseconds per token — a 54× difference. Request-level scheduling accepts this inefficiency as structural.

2. Iteration-Level Scheduling (Orca, vLLM, HuggingFace TGI)

Iteration-level schedulers allow requests to dynamically enter and exit the batch at each forward pass, eliminating padding waste. Because requests arrive and depart at different times, newly arriving requests (in prefill) can sometimes overlap with existing requests (in decode). The paper acknowledges this is an improvement: "we expect that iteration-level scheduling would do better than the baseline — at least in some cases."

However, the paper identifies three specific failures of iteration-level scheduling that SARATHI addresses:

Failure 1: Incidental overlap, not structural overlap. The overlap between prefills and decodes in iteration-level scheduling is "more of a side-effect" that depends on the arbitrary timing of request arrivals and departures. A batch could be purely prefill (when many requests arrive simultaneously), purely decode (when no new requests arrive), or mixed — there is no explicit mechanism to ensure that batches always contain the right mix of prefill and decode tokens for maximum compute utilization. The paper shows this concretely in Figure 11b: Orca's best-case performance (where one new prefill always overlaps with ongoing decodes) improves throughput by only 1.11× over the baseline, and only at low P:D ratios.

Failure 2: Full-sequence prefills limit piggybacking opportunities. Current iteration-level schedulers "submit the entire input sequence of a request in a single prefill phase." If the prefill is long (e.g., 2K tokens), it appears in only one batch. Decodes that arrive later — after that single prefill batch has completed — cannot piggyback with prefills and must run in decode-only batches. The number of decode tokens that can overlap with prefills is fundamentally limited by the number of prefill tokens available at any given time. The paper formalizes this: for a given P:D ratio (average prefill tokens to decode tokens per request), if P:D is low relative to the full prefill size, Orca "soon runs out of the prefill tokens, at which point it processes the remaining decode tokens similar to the baseline, making even the best-case version inefficient." Figure 11a confirms this: as sequence length increases from 1K to 3K (which also reduces the maximum batch size), Orca's best-case improvement collapses from 1.11× to virtually zero.

Failure 3: Latency spikes from variable-length prefills. When a long prefill request enters an ongoing batch of decodes, the prefill's computation time can delay the next decode iteration for all other requests in the batch. Since iteration-level scheduling processes the whole prompt at once, a 4K-token prefill landing in a batch of ongoing 1K-context decodes will substantially increase that iteration's latency. SARATHI avoids this because "the use of smaller chunk prefills" bounds the maximum latency impact of any single prefill insertion.

Failure 4: Pipeline bubbles persist with mixed batches. Even when iteration-level scheduling does overlap prefills and decodes, it does not guarantee uniform batch compute times. The paper identifies three distinct types of pipeline bubbles that arise with iteration-level scheduling (Figure 5):

• PB1: Bubbles due to "varying number of prefill tokens in two consecutive micro-batches" — when one micro-batch has a large prefill and the next has a small prefill (or none), the stage processing the small micro-batch finishes early and waits.
• PB2: Bubbles due to "different compute times of prefill and decode stages when one is followed by the other" — when a prefill-heavy micro-batch follows a decode-heavy micro-batch (or vice versa), the compute time mismatch creates stalls at pipeline stage boundaries.
• PB3: Bubbles due to "difference in decode compute times between micro-batches since the accumulated context length (KV cache length) varies across requests" — even two decode-only micro-batches can have different compute times if the requests have different accumulated KV cache lengths, since attention cost grows with context length.

These bubbles are not theoretical corner cases. The paper's simulation of a 64-GPU GPT-3 deployment (Section 5.3, Figure 12a) shows that with Orca-style iteration-level scheduling on a TP+PP setup, the median pipeline bubble time per request is 6.29× higher than with SARATHI. This bubble time translates directly to wasted throughput: the same TP+PP deployment with Orca scheduling is "1.28× slower" than simply running 8 independent TP replicas (no PP), despite supporting a 2.45× larger batch size. Pipeline parallelism becomes counterproductive — the bubbles cost more than the batch-size gain saves.

3. System Optimizations from Prior Work (Orca, vLLM, FlashAttention, FlexGen, FasterTransformer)

The paper positions its contributions relative to a range of prior systems. Each addresses a different aspect of LLM inference efficiency, but none solves the core prefill-decode mismatch:

• Memory management (vLLM [20], FlexGen [42]): vLLM introduces dynamic, non-contiguous KV cache allocation (inspired by virtual memory) to reduce memory waste from over-provisioning, enabling larger effective batch sizes when sequence lengths vary. FlexGen focuses on maximizing throughput under extreme memory constraints via offloading and scheduling. These are complementary to SARATHI — they increase the maximum batch size, which increases the number of decodes that can piggyback in a decode-maximal batch. The paper explicitly notes this: "dynamic memory allocation will help in supporting larger batch sizes."

• Attention optimization (FlashAttention [29], FlashAttention-2 [28], Rabe and Staats [40], xformers [21]): These algorithms reduce the memory footprint and I/O cost of self-attention, enabling longer sequences or larger batch sizes. The paper uses xformers for attention in its own implementation but notes that "more optimized attention implementations will enable scaling SARATHI to longer sequence lengths."

• Kernel-level optimizations (FasterTransformer [6]): Fused kernels, optimized matrix multiplication, and other low-level GPU techniques improve the absolute performance of both prefill and decode. These are orthogonal — they reduce the constant factor but don't change the structural mismatch between phases.

• Scheduling frameworks (Triton [13], Clipper [27], FastServe [46]): These separate the serving layer from model execution, focusing on request routing, queuing, and preemption policies. The paper positions SARATHI at the execution layer, arguing that "our current work focuses on optimizing the execution layer and can be used with different scheduling policies proposed by such systems."

• Model innovations (multi-query attention [41], mixture-of-experts [23, 33, 36], quantization [30–32, 47], Retentive Networks [44]): Multi-query attention reduces KV cache size by sharing keys and values across attention heads, which increases the maximum batch size — again, complementary to SARATHI's techniques. Mixture-of-experts and quantization reduce the model's parameter footprint or per-token compute. The paper explicitly states these are "orthogonal to our work."

The critical gap unaddressed by all prior work: how to construct batches that are uniformly compute-intensive regardless of whether they contain prefill or decode work. No prior system explicitly controls the ratio of prefill to decode tokens within each batch, nor does any prior system split prefills into chunks to enable sustained overlap across multiple iterations. This gap is what SARATHI fills.

How SARATHI Positions Itself

The paper's central positioning is that LLM inference efficiency requires rethinking batch composition at the most fundamental level. The key insight (Section 3.3) is stated directly:

"it is possible to construct uniformly compute-intensive batches by (1) slicing a large prefill request into smaller compute-efficient and uniform chunks using chunked-prefills and (2) creating a hybrid batch of a prefill chunk and piggybacking decodes alongside this chunk."

This is not an incremental improvement on existing schedulers — it is a different paradigm for what a batch is. In SARATHI, every batch is a hybrid of one prefill chunk and as many decodes as the GPU memory allows. The prefill chunk's size is chosen to saturate GPU compute, so the matrix multiplications for the prefill chunk are compute-bound. By fusing the decodes' linear operations with the prefill's linear operations into a single matrix-matrix multiplication, the decodes effectively reuse the model weights that were already fetched for the prefill — eliminating the separate memory-bound weight loads that make decode-only batches so inefficient. The decodes' attention operations still execute separately (they have different KV cache dependencies), but attention is a small fraction of total runtime compared to the linear layers (as shown in Table 2).

The paper frames this as converting decodes from memory-bound to compute-bound:

"decode-maximal batching converts decoding from being in a memory-bound phase to being in a compute-bound phase. This way, decodes, when piggybacked with prefills come at a marginal cost."

Table 2 provides the empirical anchor: in a mixed batch with one 1021-token prefill and 3 decodes, per-token decode time drops from 12.49 ms (decode-only batch) to 1.2 ms — a factor of 10.4×. The prefill's per-token cost remains unchanged at 0.229 ms.

The chunked-prefills mechanism is what makes this paradigm sustainable across an entire request's lifetime. A single long prefill, processed all at once, provides only one opportunity for decodes to piggyback. By chunking the prefill into multiple equal-sized pieces, the system creates a pipelined sequence of decode-maximal batches: each chunk becomes the prefill of a new hybrid batch, carrying a new cohort of decodes with it. The number of decode tokens that can piggyback scales with the number of prefill chunks, not with the prefill length. The paper quantifies this: for a prefill of length P split into chunks of size C, and a batch supporting B requests (1 prefill + B-1 decodes), the system can piggyback P/C × (B-1) decodes total. At P:D = C/(B-1), every decode token in the workload can piggyback with a prefill chunk — there are no leftover decode-only batches.

The paper also positions chunked-prefills as solving the pipeline bubble problem that prior work had missed. Because every decode-maximal batch has essentially the same compute time (one prefill chunk of fixed size + a fixed number of decodes), micro-batches in pipeline-parallel execution become uniform. This eliminates the three bubble types (PB1, PB2, PB3) that arise from heterogeneous batch composition. The paper is explicit: "if we can ensure that each micro-batch performs uniform computation, we can mitigate these pipeline bubbles."

A subtle but important design choice: SARATHI does not attempt to make the prefill chunk itself variable. There is exactly one prefill chunk per batch (not zero, not two), and its size is fixed (except for the tile-quantization adjustment in Section 4.4). This ensures strict uniformity — a design constraint that enables the pipeline-parallelism benefits. The tradeoff is that if a request's prefill is not an exact multiple of the chunk size, the final chunk will be smaller, producing a batch with slightly different compute time — but this is a bounded effect that affects at most one batch per request.

Finally, the paper positions its difficulty estimator (the ideal chunk size selection) as workload-aware rather than one-size-fits-all. The chunk size is chosen based on the expected P:D ratio of the deployment workload — smaller chunks maximize decode piggybacking at the cost of some prefill efficiency, while larger chunks preserve prefill efficiency at the cost of covering fewer decodes. The paper explores this tradeoff empirically (Figure 9, Figure 13) rather than providing a closed-form solution, acknowledging that the optimal chunk size depends on model architecture, GPU characteristics, and workload composition.

3. Technical Approach

3.1 Reader Orientation

SARATHI is an LLM inference scheduling system that restructures how GPU batches are composed during autoregressive generation. It solves the problem that LLM decodes are memory-bound and therefore dramatically underutilize GPU compute, while also eliminating pipeline bubbles in multi-GPU deployments, by ensuring that every batch processed by the GPU contains exactly one prefill chunk (which saturates compute) plus as many decode tokens as memory allows (which piggyback on the prefill's weight fetches at marginal cost), creating uniformly compute-intensive work units throughout the entire inference lifetime of every request.

3.2 Big-Picture Architecture (Diagram in Words)

SARATHI consists of three principal components that operate together:

1. Chunked-Prefills — a prefill-splitting mechanism that takes each incoming request's input prompt and divides it into equal-sized chunks of a fixed, pre-determined size (e.g., 256 or 512 tokens). Each chunk becomes a self-contained unit of prefill work that can be scheduled independently. The attention mask is carefully constructed for each successive chunk so that the chunked computation is mathematically identical to processing the full prompt at once. This component transforms a single long prefill into a stream of smaller, uniform prefill work units.

2. Decode-Maximal Batching — a batch-construction policy that, at each iteration, takes exactly one prefill chunk and fills the remaining slots in the batch with as many ongoing decode requests as GPU memory permits (up to $B-1$ decodes, where $B$ is the maximum batch size). The linear operations (matrix multiplications in the attention projections and feed-forward network) are fused: the prefill chunk's tokens and the decode tokens are concatenated into a single matrix multiplication, so the model weights are fetched from GPU global memory once and applied to both prefill and decode tokens simultaneously. The attention operations remain separate (prefill attention vs. decode attention, since they have different KV cache dependencies). This component eliminates the memory-bound weight-fetch bottleneck that makes decode-only batches inefficient.

3. Ideal Chunk Size Selection — a workload-aware configuration step that chooses the prefill chunk size $C$ to maximize end-to-end throughput given the expected P:D ratio (ratio of prefill tokens to decode tokens) of the deployment workload. The chunk size trades off two factors: smaller chunks allow more decode tokens to piggyback (since each prefill generates more chunks, creating more opportunities for decode-maximal batches) but operate at lower arithmetic intensity (reducing per-token prefill efficiency and increasing KV cache re-read overhead). The selection also accounts for tile quantization — the GPU hardware constraint that matrix multiplications achieve peak efficiency only when the relevant inner dimension (total tokens per batch: chunk size + number of piggybacked decodes) is a multiple of the GPU's tile size (128 in the paper's experiments).

Information flows as follows: requests arrive at the scheduler → the scheduler maintains queues of requests awaiting their first prefill chunk and requests in decode → at each iteration, the scheduler selects one prefill chunk (from a request that still has unprocessed prompt tokens) and as many decode requests as memory allows → the fused linear operations process the prefill + decode tokens together, while attention is computed separately for the prefill chunk and each decode → the prefill chunk's output (including its KV cache) is stored for the request's subsequent chunks or decode passes → if the prefill chunk was the last one for that request, the request transitions to decode mode → decode requests that generate an end-of-sequence token exit the batch.

3.3 Roadmap for the Deep Dive

• First, the chunked-prefills mechanism — how a long prompt is split into chunks, how the attention mask is set to preserve correctness, and what overheads chunking introduces. This is the foundation: it creates the uniformly-sized work units that everything else depends on.
• Second, decode-maximal batching — how a hybrid batch of one prefill chunk and multiple decodes is constructed, how the linear operations are fused, and why this reduces per-token decode cost by an order of magnitude. This is the core efficiency mechanism.
• Third, the memory constraint that determines batch size — the equation that governs how many decodes can piggyback in a given GPU memory budget, since memory (not compute) limits the batch size in practice.
• Fourth, ideal chunk size selection — the tradeoff between prefill efficiency and decode coverage, including the tile quantization effect that constrains chunk sizes to specific values. This is where the system is tuned for a specific workload.
• Fifth, the implementation details — what framework SARATHI is built on, what attention kernel it uses, and how KV cache memory is managed. These choices affect the absolute performance numbers.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a systems design and empirical evaluation paper whose core idea is that by restructuring batch composition to always include exactly one compute-saturating prefill chunk alongside as many decode tokens as memory allows, the decode phase—which dominates total inference cost—can be transformed from memory-bound to compute-bound, and the resulting uniform batch compute times eliminate pipeline bubbles in multi-GPU deployments.

---

Chunked-Prefills: Splitting Long Prompts into Uniform Compute Units

The chunked-prefills mechanism is built on two empirical observations that the paper establishes through profiling (Section 4.2). First, for a given model and GPU, the throughput of the prefill phase—measured in tokens processed per millisecond—shows diminishing returns as the total number of prefill tokens increases. Specifically, Figure 4a shows that for LLaMA-13B on an A6000 GPU, prefill throughput saturates when $B \times L \geq 512$ (where $B$ is batch size and $L$ is sequence length). A single prefill request with 512 tokens already achieves near-peak throughput; going from 512 to 1024 tokens adds minimal additional efficiency. At a chunk size of 256, the paper reports "a marginal reduction of 12.5% in the peak throughput." Second, in production LLM workloads, input prompts are often reasonably large—"ranging from 1K–4K"—meaning there are ample tokens to split into multiple chunks.

The chunking procedure works as follows. A request arrives with a prompt of length $P$ tokens. The system selects a pre-determined chunk size $C$ (e.g., 256 or 512 tokens—the selection process is described in Section 4.4). The prompt is divided into $\lceil P/C \rceil$ chunks: all chunks except possibly the last contain exactly $C$ tokens; the final chunk contains the remainder $P \bmod C$ tokens (or also $C$ if $P$ is an exact multiple of $C$). Each chunk is processed as an independent prefill unit in a separate forward pass of the model. The key to correctness is the attention mask.

Attention mask construction for chunked-prefills. For a standard (unchunked) prefill, the attention mask is a triangular matrix: each query token at position $i$ can attend to all key/value tokens at positions $j \leq i$, and cannot attend to tokens at positions $j > i$ (since those tokens have not been processed yet—this is causal attention). For chunked-prefills, the same causal property must hold across chunk boundaries. The paper illustrates this with an example in Figure 6: consider a prompt split into chunks of 4 tokens each, and suppose the first chunk contains query tokens $q_0$ through $q_3$ with corresponding key/value tokens at the same positions. During the first chunk's forward pass, the attention mask is a standard 4×4 causal mask: $q_0$ attends to $k_0$ only; $q_1$ attends to $k_0, k_1$; $q_2$ attends to $k_0, k_1, k_2$; and $q_3$ attends to $k_0, k_1, k_2, k_3$. The KV pairs for these four token positions are saved to the KV cache.

During the second chunk's forward pass, the chunk contains query tokens $q_4$ through $q_7$. In addition to computing new key/value tokens for positions 4–7 (which are added to the KV cache), the attention operation must allow these new queries to attend to the cached key/value tokens from positions 0–3 as well as the new tokens within the second chunk. The mask is therefore: $q_4$ attends to all $k_0$ through $k_4$; $q_5$ attends to all $k_0$ through $k_5$; and so on. The third chunk ($q_8$ through $q_{11}$) extends this further: each new query attends to all keys from position 0 up to its own position. Figure 6 shows these progressively expanding triangular masks for three consecutive chunks.

The paper explicitly states: "Setting the attention mask this way ensures that chunked-prefills computation is mathematically equivalent to the full prefill." The equivalence holds because the attention operation is a weighted sum over the available key/value pairs—as long as each query can access exactly the same set of preceding tokens it would have accessed in a single-pass prefill, the output is identical. What changes is only the scheduling of when those key/value pairs are computed and stored.

Overhead analysis of chunked-prefills. Splitting a prefill into chunks introduces two sources of overhead that the paper quantifies in Section 5.4 (ablation study) and discusses conceptually in Section 4.2.

Overhead 1: Reduced arithmetic intensity. A smaller prefill chunk processes fewer tokens in its matrix multiplications, which reduces the arithmetic intensity (FLOPs per byte of memory traffic). This effect is visible in Figure 4b: the arithmetic intensity of prefill operations scales with the number of tokens being processed. When the chunk size drops below the GPU's saturation threshold, the prefill computation itself becomes partially memory-bound, increasing per-token cost. The paper quantifies this in Figure 13b: for LLaMA-13B on A6000, a chunk size of 64 is approximately 5× slower per token than the full (un-chunked) prefill; a chunk size of 128 is about 2× slower; a chunk size of 256 is within about 20% of full prefill efficiency; and a chunk size of 512 is within about 10%.

Overhead 2: Repeated KV cache reads for attention. During a standard prefill, every token's key and value vectors are computed once, stored in the KV cache, and used in that same forward pass for attention. In chunked-prefills, the KV cache for earlier chunks must be loaded from GPU global memory during each subsequent chunk's attention computation. For a request split into $N$ chunks, the first chunk's KV cache is loaded $N$ times (once during each of the $N$ chunk forward passes—including the first pass where it is computed), the second chunk's KV cache is loaded $N-1$ times, and so on. The paper notes this overhead explicitly: "the attention kernel in every subsequent chunk after the first will have to reread all the KV pairs of the prior tokens from the GPU memory."

However, the paper argues—and validates experimentally—that this attention overhead is manageable because attention computation is a "small fraction of the overall forward pass time." Table 2 provides the evidence: in a prefill-only batch with 1024-token sequences and batch size 4, the linear operations (preproj + postproj + FFN) take 224.8 ms total, while attention takes only 10 ms—about 4.3% of the total prefill time. Even if attention time increases by a factor of 3–5× due to repeated KV cache reads (as Figure 13a shows for small chunk sizes), the total prefill time increase is bounded. For chunk sizes of 256 and 512, Figure 13a shows the attention overhead is well under 2×, and the overall prefill overhead stays within 10–20% (Figure 13b).

The critical design insight is that this prefill overhead is intentionally traded off against the decode efficiency gain from piggybacking. The paper demonstrates this in Figure 13c: even for a chunk size of 128, which incurs a 2× prefill slowdown, the end-to-end throughput is up to 1.16× higher than the baseline because the improved decode efficiency more than compensates. For chunk size 64 (5× prefill slowdown), end-to-end throughput approximately matches the baseline—the decode gain exactly offsets the prefill loss. This tradeoff is the central mechanism that the chunk size selection process (Section 4.4) optimizes.

---

Decode-Maximal Batching: Piggybacking Decodes on Prefill Weight Fetches

Decode-maximal batching is the mechanism by which SARATHI constructs each batch to maximize GPU utilization. The name "decode-maximal" reflects the goal: given that one slot in the batch is always occupied by a prefill chunk, fill the remaining slots with as many decode requests as possible—up to the memory limit—to maximize the number of decode tokens that benefit from the prefill's weight fetches.

Batch composition constraints. Each batch in SARATHI consists of exactly:

• 1 prefill chunk: A fixed-size chunk (of $C$ tokens, or fewer for the final chunk of a request) from a single request's input prompt. There is never more than one prefill chunk per batch, and never zero (unless there are no pending prefills at all, in which case the system falls back to decode-only batches—this is the tail case when the P:D ratio is very high and all prefills have been processed).
• Up to $B-1$ decode requests: Each decode request contributes exactly 1 token (the next autoregressive token to generate). The number of decode requests is limited by the GPU memory available after accounting for the prefill chunk's KV cache allocation.

Why exactly one prefill chunk? The paper's insight is that a single prefill chunk with a sufficiently large $C$ (chosen to saturate GPU compute, as discussed in Section 4.4) provides enough arithmetic intensity to make the linear operations compute-bound. Adding a second prefill chunk would increase the batch's total compute time without adding more decode-slots-to-piggyback. Conversely, having zero prefill chunks reverts to a decode-only batch, which is memory-bound and inefficient. The "exactly one" design is what guarantees both compute saturation and uniform batch compute times—the uniformity property that eliminates pipeline bubbles.

How fusion works. The linear operations in a transformer block are matrix multiplications with fixed model weights. In the prefill phase, the input to each linear layer is a tensor of shape [B_prefill, L, H] where $B\_\text{prefill}$ is the number of prefill requests, $L$ is the prefill sequence length, and $H$ is the hidden dimension. In the decode phase, the input is of shape [B_decode, 1, H]. SARATHI concatenates the prefill and decode tokens along the batch dimension, producing an input of shape [B_prefill + B_decode, L (or 1), H], and then executes a single matrix multiplication with the weight tensor. Concretely, for the preproj operation (which multiplies the input by the combined [H, 3H] weight matrix to produce Q, K, V), the input tensor $\mathbf{X}$ of shape [1 + (B-1), L (or 1), H] (where the first row corresponds to the $C$ prefill tokens and the remaining rows correspond to the $B-1$ decode tokens) is multiplied by $\mathbf{W}$ of shape [H, 3H] in a single batched matrix multiplication.

The crucial consequence is that the model weights $\mathbf{W}$ are loaded from GPU global memory (HBM) exactly once for the entire batch, rather than once for the prefill and then separately for each decode-only batch. During a decode-only batch, loading the weights dominates the runtime because the compute per byte of data loaded is tiny (vector-matrix products have low arithmetic intensity). By fusing, the weight-fetch cost is amortized over all tokens in the batch—both the $C$ prefill tokens (which provide the bulk of the compute) and the $B-1$ decode tokens (which add marginal extra compute at virtually zero incremental memory cost).

Attention is NOT fused. The paper explicitly notes that "the attention computations for the prefill and decodes happen separately." This is because prefill attention and decode attention have fundamentally different shapes and dependencies:

• Prefill attention: Computes self-attention over all $C$ query tokens against all $C$ key/value tokens (and any cached KV tokens from earlier chunks). This is a dense attention operation.
• Decode attention: Each decode request computes attention for its single new query token against its entire accumulated KV cache (all previously generated tokens plus the original prompt tokens). This is a batched operation across decode requests, but each request's attention is with its own private KV cache of potentially different lengths.

The separate attention paths mean that while the linear layers benefit from fusion, the attention cost for decodes is still incurred independently. However, as Table 2 shows, attention is only a small fraction of total runtime: in a decode-maximal batch with one 1024-token prefill and 3 decodes, attention takes 15.2 ms out of 238.4 ms total (about 6.4%), while the fused linear operations take 223.2 ms (about 93.6%). The linear operations are where the efficiency gain lives.

Why decode cost drops by an order of magnitude. Table 2 provides the empirical anchor. The paper compares three batch compositions for LLaMA-13B on an A6000 GPU:

• Prefill-only batch (batch size 4, sequence length 1024): 234.8 ms total, or 0.229 ms per prefill token.
• Decode-only batch (batch size 4, sequence length 1024): 49.96 ms total for 4 tokens, or 12.49 ms per decode token.
• Decode-maximal batch (1 prefill of 1021 tokens plus 3 decodes): 238.4 ms total. The per-token prefill cost remains 0.229 ms (223.2 ms / (1021 + 3) ≈ 0.218 ms for linear operations; attention is separate). The marginal cost of the 3 decode tokens is the difference between the decode-maximal batch time and a prefill-only batch of the same prefill size: approximately 238.4 − 234.8 ≈ 3.6 ms for 3 decodes, or 1.2 ms per decode token.

This represents a 10.4× reduction in per-token decode time compared to the decode-only batch (12.49 ms → 1.2 ms). The paper describes this as converting decoding "from being in a memory-bound phase to being in a compute-bound phase." The decodes are still technically doing vector-matrix products (their input is [1, H] per request), but because these vector-matrix products are concatenated with the prefill's matrix-matrix product, the weights are already in registers or shared memory from the prefill computation, and the decode tokens ride on the prefill's compute wave.

---

The Memory Constraint: What Determines the Maximum Batch Size

The number of decode requests that can piggyback in a decode-maximal batch is determined by GPU memory capacity, not by compute. The paper formalizes this in Section 4.3.1 with a simple capacity model.

The total GPU memory $M_G$ (e.g., 48 GB on A6000, 80 GB on A100) is consumed by three categories of data:

1. Model parameters ($M_S$): The weights of the transformer (all layers' projection matrices, feed-forward network weights, layer normalization parameters, etc.). This is a fixed cost that depends only on the model architecture and the degree of model parallelism. For LLaMA-13B in full precision (FP16), the parameters require approximately 26 GB (13 billion parameters × 2 bytes each).

2. KV cache for the prefill chunk: The single prefill chunk contributes key and value tensors for its $C$ tokens. Each token produces a key vector and a value vector of size $H$ per layer, so the per-token KV cache size per layer is $2H$. Across all layers and the chunk size $C$, this is a fixed allocation. However, this allocation persists until the request completes decoding, not just during its prefill chunks—the KV cache must be retained for all subsequent decode attention operations.

3. KV cache for all active requests: Each request (whether currently in the prefill chunk being processed or in the decode piggyback slots) has an accumulated KV cache equal to its total sequence length so far (prompt tokens processed + decode tokens generated). The maximum sequence length per request is $L$ (a deployment parameter). Let $m_{kv}$ be the memory required per pair of key and value vectors for a single token across all layers.

The paper defines the maximum permissible batch size $B$ (the total number of requests that can coexist in GPU memory) as:

$B = \left\lfloor \frac{M_G - M_S}{L \cdot m_{kv}} \right\rfloor$

where $M_G$ is total GPU memory, $M_S$ is the model parameter memory, $L$ is the maximum supported sequence length per request, and $m_{kv}$ is the per-token KV cache memory footprint.

What it computes: the number of requests the GPU can hold simultaneously, assuming each request is pre-allocated KV cache space for the maximum possible sequence length $L$ (a worst-case allocation policy). The numerator $M_G - M_S$ is the memory available for KV caches after model weights are loaded. Dividing by $L \cdot m_{kv}$ gives the number of requests that can be accommodated at full capacity. The floor operation ensures we don't exceed memory.

Why this form: this is a conservative (over-provisioned) allocation scheme. The paper pre-allocates KV cache to the maximum sequence length to avoid dynamic reallocation overhead during inference (though it notes that vLLM's dynamic allocation [20] could increase the effective batch size). In SARATHI with decode-maximal batching, one of the $B$ slots is occupied by the current prefill chunk's request, leaving $B-1$ slots for decode requests. The paper explicitly writes: "the number of decodes can be at most $B-1$ as they piggyback along with one prefill chunk."

For LLaMA-13B on A6000 with $L = 1024$ (1K sequence length), the paper reports a maximum batch size of 18 requests. This means 17 decodes can piggyback with each prefill chunk. For 2K sequences, $B$ drops to 10 (9 decodes piggybacking). For 3K sequences, $B$ drops to 6 (5 decodes piggybacking). These values appear in Table 4 and throughout Figure 10.

KV cache pre-allocation implementation. The paper notes in Section 4.5 that to "avoid allocating memory for KV caches in each decode iteration, we pre-allocate the KV cache as per the maximum sequence length for each experiment and update respective KV pairs in place when required." This means the KV cache is allocated once at request creation and reused in-place during decode, which avoids GPU memory allocation overhead on the critical path.

---

Identifying the Ideal Chunk Size: Trading Prefill Efficiency for Decode Coverage

The chunk size $C$ is the single most important configuration parameter in SARATHI. It controls the tradeoff between two competing objectives: prefill efficiency (larger chunks have higher arithmetic intensity, hence better per-token prefill performance) and decode coverage (smaller chunks produce more chunks from a given prompt, hence more opportunities for decodes to piggyback). The paper develops this tradeoff conceptually in Section 4.4 and validates it empirically in Section 5.1.3 (Figure 9) and the ablation study in Section 5.4 (Figure 13).

The P:D ratio as the workload's key characteristic. The paper introduces the "P:D ratio," defined as the ratio of the number of prefill tokens to the number of decode tokens in a given workload or batch. For a single request with a prompt of $P$ tokens and a generated response of $D$ tokens, the P:D ratio is $P/D$. Across a deployment, the average P:D ratio characterizes the workload. A low P:D ratio (e.g., 10) means decodes dominate—the model generates many output tokens per input token. A high P:D ratio (e.g., 200) means prefills dominate—inputs are long relative to outputs.

The piggybacking condition. For a prefill of length $P$ split into chunks of size $C$, the number of prefill chunks is approximately $P/C$ (rounding up for the last partial chunk). Each prefill chunk provides one decode-maximal batch carrying $B-1$ decodes. The total number of decode tokens that can piggyback over the request's entire lifetime is therefore $(P/C) \times (B-1)$. All $D$ decode tokens can be perfectly piggybacked (i.e., there are never any leftover decode-only batches) when:

$\frac{P}{C} \times (B-1) \geq D$

Rearranging in terms of the P:D ratio:

$\frac{P}{D} \geq \frac{C}{B-1}$

Why this matters: when $P/D = C/(B-1)$, every single decode token in the workload coincides with a prefill chunk—the system operates in a perfect steady state of decode-maximal batches from the first prefill chunk until the last decode token. The paper refers to this as the condition where "all decode tokens are perfectly piggybacked with prefills." At this point, the throughput gain from SARATHI peaks.

If $P/D < C/(B-1)$ (P:D ratio is too low), the system runs out of prefill chunks before all decode tokens are processed. The remaining decodes must be executed in decode-only batches (or the prefill chunk size must be reduced so that $C/(B-1)$ matches the lower P:D ratio). If $P/D > C/(B-1)$ (P:D ratio is too high), the system finishes all decodes before exhausting the prefill chunks, and some prefill chunks run with fewer than $B-1$ piggybacked decodes—wasting the opportunity.

This relationship explains the peaked behavior in Figure 9: for a fixed chunk size and batch size, throughput improvement is maximized at the P:D ratio where perfect piggybacking occurs, and tapers off on both sides.

Example from the paper. Using a chunk size of $C = 256$ at batch size $B = 18$ for LLaMA-13B on A6000 with 1K sequence length, the perfect-piggybacking P:D ratio is:

$\frac{P}{D} = \frac{256}{18-1} = \frac{256}{17} \approx 15$

Figure 9a shows that throughput improvement peaks at approximately P:D = 14–15 with chunk size 256, confirming the theory. With chunk size 512 at the same batch size, the peak shifts to $P/D = 512/17 \approx 30$, which Figure 9a also confirms. With chunk size 128, the peak would be at $P/D = 128/17 \approx 7.5$, but Figure 9a shows that the absolute gain is lower because the prefill efficiency loss from such small chunks dominates.

The tile quantization effect. The paper discovers an additional hardware constraint that influences the ideal chunk size. Modern GPUs compute matrix multiplications by partitioning the operand matrices into fixed-size tiles (typically 128×128 on NVIDIA GPUs) and distributing these tiles across thread blocks. Each thread block computes the same number of arithmetic operations. If the matrix dimension is not a multiple of the tile size, some thread blocks process padding elements—wasted computation.

Figure 7 demonstrates this effect dramatically for LLaMA-13B on A6000. The iteration time for a prefill with 256 tokens is 69.8 ms. Adding just one token (257 tokens) increases the iteration time to 92.33 ms—a 32% jump. This happens because 257 is just past a multiple of 128 (256 = 2×128, 257 requires 3 tiles, but the third tile is mostly empty). In contrast, going from 128 to 256 (exactly 2 tiles) increases time by only 27%, which is roughly linear with the increased work.

The practical implication is that the prefill chunk size $C$ should be chosen so that the total number of tokens in the fused linear operations—the prefill chunk size $C$ plus the number of piggybacked decode tokens $B-1$—is a multiple of the tile size. The paper formalizes this:

"if the chosen chunk size is 256, the tile size is 128, and the maximum permissible batch size is $B$, then the prefill chunk size should be $256 - (B-1)$."

For example, with $B = 18$, the tile-aligned chunk size would be $256 - 17 = 239$, which rounds down the chunk slightly but ensures that $C + (B-1) = 256$, a multiple of 128. The paper observes the effect in Figure 13c: "chunk size 256 shows better speedup than 320" because 256 is a multiple of 128 while 320 is not.

Why not always choose the smallest chunk size that saturates compute? The paper argues against this naive approach explicitly. If the goal were only to saturate compute, one would pick the smallest chunk size that achieves near-peak prefill throughput—perhaps around 256 for LLaMA-13B/A6000. But the optimal chunk size for end-to-end throughput also depends on the workload's P:D ratio. When decodes dominate (low P:D ratio), optimizing decodes is more important than preserving perfect prefill efficiency. The paper states this tradeoff directly:

"decoding time increases as the P:D ratio goes down. Therefore, beyond a certain point, optimizing decodes becomes more important than executing prefills at peak efficiency. For example, if the prefill and decode phases consume 10% and 90% of the total time, respectively, then even a 5× overhead in prefills is acceptable if the decodes can be optimized by 2× or more."

This explains why SARATHI tolerates the prefill overhead of smaller chunk sizes—the overall end-to-end win is determined by the weighted sum of prefill and decode improvements.

A two-step chunk selection procedure. Synthesizing the discussion, the paper implies a two-step chunk size selection process:

1. Workload-driven tradeoff: Based on the expected P:D ratio and the available batch size $B$, identify the chunk size $C$ that places the workload at the perfect-piggybacking point ($C \approx (P/D) \times (B-1)$), or as close as practical. Smaller $C$ covers more decodes but loses prefill efficiency; larger $C$ is prefill-efficient but may leave decode tokens uncovered.

2. Tile-quantization adjustment: Round $C$ so that $C + (B-1)$ is a multiple of the GPU's tile size (128 in the paper's experiments), avoiding the wasted work from partial tiles.

The paper does not provide a closed-form optimization function, but the empirical exploration in Figure 9 and Figure 13 demonstrates that chunk sizes of 256 and 512 provide the best results across a range of workloads, with 256 being preferable when P:D is low-to-medium and 512 being preferable when P:D is high. This is a practical design guideline rather than a theoretical optimum.

---

Implementation: The nanoGPT Codebase and Attention Kernels

SARATHI is implemented on the nanoGPT codebase [12], a lightweight transformer implementation that the authors extended with support for chunked-prefills and decode-maximal batching (Section 4.5). The paper provides specific architectural configurations for the three evaluated models:

• LLaMA-13B: 40 layers, unknown number of attention heads (implied by the standard LLaMA architecture), hidden size 5120.
• LLaMA-33B: 60 layers, 52 attention heads, hidden size 6656.
• GPT-3 (for the pipeline parallelism simulation): 96 layers, 96 attention heads, hidden size 12288.

These configurations are "as per the publicly available architectural parameters of these models [10, 14]."

Attention kernel choice. The paper uses the xformers memory-efficient attention implementation [21] for all attention computations. The authors state that "in our setup, it outperformed PyTorch 2.0's in-built attention implementations: i.e., flash attention, memory-efficient attention, and math attention kernels." This choice is independent of SARATHI's scheduling techniques—any attention kernel could be used—but it affects the absolute runtime numbers reported in Table 2 and Figures 3, 10. The paper notes that "more optimized attention implementations will enable scaling SARATHI to longer sequence lengths" (Section 6), suggesting that attention efficiency is a scaling bottleneck for very long contexts.

KV cache pre-allocation. To avoid the overhead of dynamic memory allocation on the critical inference path, the paper pre-allocates the KV cache for each request at its maximum possible sequence length $L$ when the request is created. During decode iterations, the new key and value tensors are written in-place into the pre-allocated cache. This is a conservative memory policy (as discussed earlier—vLLM's dynamic allocation could improve utilization), but it eliminates allocation latency and simplifies the implementation. The authors acknowledge this tradeoff implicitly by referencing vLLM as complementary future work.

Comparison to Orca's iteration-level scheduling. To ensure a fair comparison, the paper implements Orca's iteration-level scheduling within its own codebase by using "our mixed batching mechanism, with no constraint on the number of prefills allowed per batch." This means the baseline against which SARATHI is compared (Figure 11) runs the exact same code, but with SARATHI's chunking and decode-maximal constraints disabled—allowing any number of prefills (including multiple or zero) in any batch. This controls for implementation differences and isolates the effect of the proposed batching policy.

Simulation infrastructure for pipeline parallelism. The GPT-3 pipeline parallelism experiments (Section 5.3) use a custom simulator rather than a physical 64-GPU deployment. The simulator is built as follows:

1. Profiling: The authors profile the runtime of each transformer operation (the six operations in Table 1) in both prefill and decode phases across various batch sizes and sequence lengths on a real A100 GPU.
2. Network profiling: Communication costs for tensor-parallel all-reduces and pipeline-parallel point-to-point transfers are profiled separately.
3. Regression model: A regression model is fitted to the profiled data to extrapolate runtimes for configurations not explicitly profiled.
4. Validation: The paper reports that "the estimated runtimes by the simulator are within 5% of the empirical values on an 8-GPU, 80GB A100 DGX box."

The simulation processes 10,000 requests with sequence lengths sampled from a Zipf distribution (parameter $\theta = 0.4$) between 1K and 4K tokens. The P:D ratio is fixed at 10. The chunk size for SARATHI is set to 256. The maximum batch size is 27 for the TP+PP configuration and 11 for the TP-only configuration. These parameters determine the absolute throughput numbers in Figure 12b and the bubble-time distribution in Figure 12a.

4. Key Insights and Innovations

Innovation 1: Rejecting the Implicit Assumption That Prefill and Decode Are Separate Scheduling Entities

The dominant assumption across all prior LLM inference systems—from request-level schedulers like FasterTransformer [6] to iteration-level schedulers like Orca [48], vLLM [20], and HuggingFace TGI [17]—is that prefill and decode are fundamentally different phases that happen to different requests at different times. A batch may coincidentally contain both, but this overlap is incidental: a new request arriving while existing requests are decoding. No prior system makes the compositional leap that every batch should contain both a prefill and decodes by construction, and that this hybrid composition should be the scheduling primitive rather than an accident of arrival timing.

SARATHI's decode-maximal batching makes this leap explicit. The paper's conceptual move is to treat the prefill chunk not merely as work to be completed for a request, but as a compute catalyst—a unit of GPU-saturating work that, when present in a batch, transforms the economics of every decode token that shares that batch. The prefill chunk's matrix-matrix multiplications load the model weights from GPU global memory and keep them in on-chip memory (registers/shared memory). The decode tokens, whose vector-matrix products would normally each require a separate, memory-bound weight fetch, instead ride the prefill's memory transaction. The weights are fetched once and applied to all tokens. This is a structural redesign of what a batch means in LLM inference: not an aggregation of similar-phase requests, but a deliberately heterogeneous unit where one compute-saturating component amortizes the memory cost for all memory-bound components.

The field missed this not because fusion is novel—fusing operations that share weights is standard compiler optimization—but because the dominant framing treated the prefill-decode mismatch as a problem to be tolerated (by increasing batch sizes through model parallelism) rather than exploited (by always pairing them). The paper's innovation is in recognizing that the prefill's excess compute intensity can be lent to the decode's deficit, and that the scheduler should enforce this pairing as a structural invariant. This reframes the inference scheduling problem from "how to keep the GPU busy despite decode inefficiency" to "how to eliminate decode inefficiency by never allowing decodes to run alone."

The empirical validation is stark: Table 2 shows a 10.4× reduction in per-token decode time (from 12.49 ms to 1.2 ms) with no change to the hardware, model, or attention implementation—purely from restructuring batch composition. The conceptual reframing is what makes this more than a kernel optimization; it is a scheduling paradigm shift.

Innovation 2: Chunked-Prefills as a Mechanism for Decoupling Prefill Granularity from Prompt Length

A second implicit assumption that SARATHI overturns is that a prefill is an atomic unit: a request's entire input prompt must be processed in a single forward pass. This assumption is so ingrained that it appears in every prior inference system—including those that otherwise innovate on scheduling granularity. Orca [48] introduced iteration-level scheduling to allow requests to enter and exit batches dynamically, but still "submit[s] the entire input sequence of a request in a single prefill phase" (Section 5.2). The consequence, which the paper identifies as a fundamental limitation, is that a long prompt provides exactly one opportunity for decodes to piggyback—the single batch in which that full prefill is processed. After that, the request transitions to decode and can no longer serve as a compute catalyst for other requests.

Chunked-prefills breaks the atomicity assumption. By splitting a prompt of length P into P/C chunks, the system creates P/C opportunities for decode-maximal batching rather than one. The number of decode tokens that can piggyback scales with the number of chunks, not with the prefill length. The paper formalizes this: at the perfect-piggybacking point P/D = C/(B-1), every decode token in a request's lifetime is covered by a prefill chunk. This condition is achievable precisely because chunked-prefills makes C a tunable parameter—if the workload's P:D ratio is known, the chunk size can be chosen to match it.

The intellectual distinction here is that chunked-prefills is not simply a workaround for memory constraints or a batching convenience. It is a mechanism for decoupling prefill granularity from prompt length, which in turn makes the decode-piggybacking opportunity a controllable variable. Without chunking, the system is at the mercy of the workload's prompt lengths: a deployment with short prompts (e.g., 128 tokens) offers many prefill-batch opportunities but each carries few tokens and may not saturate compute; a deployment with long prompts (e.g., 4096 tokens) gets compute saturation but provides only one piggybacking opportunity per request. Chunked-prefills breaks this coupling: the system can have both compute-saturating prefill work (by choosing C large enough) and many piggybacking opportunities (by choosing C small enough relative to P). The tradeoff is tunable via the single parameter C.

The fact that chunked-prefills requires careful attention mask construction to preserve mathematical equivalence (Figure 6) is implementation detail. The conceptual contribution is the recognition that prefills can be subdivided without semantic loss, and that this subdivision transforms the degrees of freedom available to the scheduler. The overhead analysis in Figure 13—showing that even a 5× prefill slowdown from aggressive chunking can be net-beneficial when decodes dominate—validates that this tradeoff space is worth exploring and non-obvious: the naive intuition would be to preserve prefill efficiency at all costs.

Innovation 3: Pipeline Bubbles as a Batch-Composition Problem, Not a Scheduling Problem

Prior work on pipeline parallelism for inference—including Orca [48] and FasterTransformer [6]—assumed that iteration-level scheduling with micro-batches would eliminate pipeline bubbles because inference has only forward passes (no backward pass to create the classic training bubble between forward and backward). The paper directly refutes this assumption by identifying three distinct bubble types (PB1, PB2, PB3 in Figure 5) that arise from heterogeneous batch composition, not from the forward-backward structure that micro-batching was designed to address.

The conceptual move here is to diagnose pipeline bubbles as a batch-composition uniformity problem rather than a scheduling problem. PB1 (varying prefill tokens between consecutive micro-batches), PB2 (prefill-decode compute time mismatch), and PB3 (varying KV cache lengths affecting attention cost) all share the same root cause: different batches take different amounts of time, so pipeline stages that finish early must wait. The standard solution for LLM inference—use iteration-level scheduling and hope that overlapping requests smooth out the differences—is fragile and workload-dependent. In the worst case (all requests start and end simultaneously), Orca's scheduling behaves identically to request-level scheduling with zero overlap (Section 5.2, Figure 11a: worst-case Orca matches baseline).

SARATHI's solution is not a smarter scheduling algorithm but a structural guarantee of uniformity. Because every decode-maximal batch contains exactly one prefill chunk of fixed size C (plus a variable but bounded number of decodes), the compute time per batch is approximately constant. The pipeline stages receive uniformly-sized work units, and the bubbles collapse. Figure 12a quantifies this: median bubble time per request drops by 6.29×. The consequence is that pipeline parallelism—previously counterproductive for inference (the TP-PP setup with Orca scheduling was 1.28× slower than TP-only despite supporting 2.45× larger batch sizes, per Figure 12b)—becomes a net win with SARATHI, achieving 1.48× speedup over TP-only.

This is a fundamental finding rather than an incremental improvement because it changes the viability of pipeline parallelism as an inference strategy. Prior to SARATHI, the prevailing view (codified in the literature's focus on tensor parallelism and the widespread use of expensive NVLink interconnects) was that pipeline parallelism's communication advantages were offset by its bubble overhead, making it attractive only when tensor parallelism was infeasible. SARATHI shows that the bubbles are an artifact of poor batch composition, not inherent to pipeline parallelism, and that with uniform batches, pipeline parallelism becomes the preferred scaling strategy for cross-node deployment. This is a reframing of the inference parallelism design space.

Innovation 4: Tile Quantization as a First-Order Constraint on Inference Batching Design

The paper surfaces a GPU architectural detail—tile quantization—that prior inference systems treated as a second-order effect, and elevates it to a first-order design constraint. The phenomenon is that matrix multiplications on GPUs achieve peak efficiency only when the relevant matrix dimensions are multiples of the hardware tile size (128 on the A6000/A100 GPUs studied). When a dimension crosses a tile boundary by even one element, a new, mostly-empty tile is allocated, and the GPU wastes compute on padding. Figure 7 demonstrates the effect: going from 256 tokens to 257 tokens increases iteration time by 32%, far more than the 0.4% increase in actual work.

Prior work on transformer inference (Orca, FasterTransformer, FlashAttention) does not discuss tile quantization as a batching constraint. The assumption is that batch sizes and sequence lengths are continuous variables that can be scaled arbitrarily. SARATHI shows that this assumption is quantitatively wrong at the scales that matter for throughput optimization: the choice between a chunk size of 256 and 257 can be the difference between a 20% overhead and a 50% overhead, purely from tile-boundary effects.

The paper's insight is to incorporate this constraint into the chunk size selection process: choose C such that C + (B-1) is a multiple of the tile size. This is not an optimization that squeezes out an extra 2–3%—it is the difference between a configuration that works well and one that is substantially worse, as Figure 13c demonstrates (chunk size 256 outperforms chunk size 320 despite both being in the same efficiency ballpark by standard measures). The significance is that this constraint interacts with the other design choices (P:D ratio, batch size, model architecture) in non-obvious ways, and ignoring it can lead to systematically suboptimal configurations. This is a negative result with design implications: the inference system designer must reason about hardware tile boundaries, not just abstract FLOP counts or memory bandwidths.

The tile quantization finding is a secondary contribution, but it is intellectually distinctive because it demonstrates that the gap between "reasonable intuition" and "hardware-efficient design" widens when batching is restructured as SARATHI proposes. In a standard decode-only batch, the batch dimension is determined by memory capacity, and tile quantization is a minor effect. In SARATHI's fused hybrid batches, the combined token count across prefill and decode determines the matrix dimensions, and the interaction between chunk size, decode count, and tile boundaries becomes a central design parameter. This is a new category of constraint that future inference systems using hybrid batching will need to account for.

Innovation 5: Empirical Demonstration That Pipeline Parallelism for Inference Is Viable Only with Uniform Batches

While this is partly a corollary of Innovation 3, it merits separate treatment because of its practical significance and because it overturns a specific, published claim. Orca [48], the leading iteration-level inference scheduler, claimed in its Figure 8 that iteration-level scheduling "eliminates bubbles in pipeline scheduling." SARATHI demonstrates that this claim is incorrect in the realistic setting where batch composition is heterogeneous. Figure 12b provides the decisive evidence: a TP-PP deployment with Orca-style scheduling, despite supporting 2.45× larger batch sizes than a TP-only deployment, is 1.28× slower end-to-end. The pipeline bubbles (median 6.29× higher than SARATHI, per Figure 12a) cost more throughput than the batch-size gain provides.

The intellectual contribution here is not the speedup number (1.91× over baseline TP-PP) but the refutation of a widely-held assumption and the establishment of a necessary condition for pipeline parallelism to be beneficial. The paper shows that pipeline parallelism for LLM inference is contra-indicated without uniform batch composition. This is a strong, falsifiable claim that changes how practitioners should think about multi-GPU deployment strategies. Prior to SARATHI, the decision to use pipeline parallelism was based primarily on interconnect availability (no NVLink → use PP). After SARATHI, the decision must also account for whether the scheduling system can guarantee uniform micro-batch compute times. If it cannot, pipeline parallelism may be worse than simply replicating tensor-parallel instances, even when the latter supports smaller batch sizes.

This finding also provides the intellectual bridge between SARATHI's two techniques. Chunked-prefills and decode-maximal batching were motivated primarily by single-GPU decode inefficiency (Innovations 1 and 2). But their joint application produces the uniform-batch property that makes pipeline parallelism viable. The paper could have presented these as two separate contributions—a batching technique for single-GPU efficiency and a scheduling technique for multi-GPU pipeline bubbles. Instead, it shows they are two manifestations of the same underlying principle (uniform, compute-saturating work units), and that the multi-GPU benefit is a natural consequence of the single-GPU design. This unification is conceptually elegant and distinguishes SARATHI from work that addresses single-GPU and multi-GPU efficiency as separate problems.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper does not use a traditional benchmark dataset in the sense of evaluating model accuracy. Instead, the evaluation measures inference system throughput under controlled workload parameters. The "dataset" is the set of workload configurations—sequence lengths (1K, 2K, 3K tokens), P:D ratios (ratio of prefill to decode tokens, varied from 1 to 200), and batch sizes (varying up to the memory limit for each configuration)—that define the inference requests processed by the system. For the pipeline parallelism simulation (Section 5.3), 10,000 requests are generated with sequence lengths sampled from a Zipf distribution (θ = 0.4) between 1K and 4K tokens, with a fixed P:D ratio of 10. No train/test split applies; this is a systems performance evaluation, not a model accuracy evaluation.

• Base model(s). Three models are evaluated, spanning two orders of magnitude in parameter count. LLaMA-13B (40 layers, hidden size 5120) is evaluated on a single NVIDIA A6000 GPU (48 GB). LLaMA-33B (60 layers, 52 attention heads, hidden size 6656) is evaluated on a single NVIDIA A100 GPU (80 GB). GPT-3 (96 layers, 96 attention heads, hidden size 12288) is evaluated in simulation across 64 A100 GPUs with 8-way tensor parallelism within each node and 8-way pipeline parallelism across nodes. The architectural configurations are "as per the publicly available architectural parameters of these models [10, 14]." The models are chosen to span a range of scales and hardware configurations, demonstrating that the techniques generalize beyond a single model-GPU pairing.

• Metrics. The paper reports three primary metrics. Decode throughput speedup: the factor by which per-token decode time is reduced compared to the baseline, computed by dividing the baseline's average decode time per token by SARATHI's marginal decode time per token. The marginal decode time is measured as the difference in runtime between a decode-maximal batch (prefill chunk + d decodes) and a prefill-only batch of the same prefill size, divided by d. End-to-end throughput gain: the factor by which total tokens processed per unit time (tokens/ms) improves over the baseline, reflecting both prefill and decode phases together. Pipeline bubble time: the sum of idle time across all micro-batches and iterations for a given request in pipeline-parallel execution, measured in seconds (Section 5.3). Request completion time: the wall-clock time to process a fixed number of requests (10,000 in the simulation), used for end-to-end pipeline-parallelism comparison (Figure 12b).

• Baselines. The paper uses several baselines in different contexts. For single-GPU experiments (Sections 5.1 and 5.2): (1) Baseline (request-level scheduling): the system processes prefill-only batches and decode-only batches separately, as in FasterTransformer [6] and similar request-level schedulers. Prefill and decode never appear in the same batch. (2) Orca (best-case): iteration-level scheduling as described in Yu et al. [48], where one full prefill request overlaps with ongoing decodes in every batch. This represents the maximum possible overlap under Orca's scheduling policy. (3) Orca (worst-case): all requests begin and end at the same time, so there is no incidental overlap between prefills and decodes—functionally equivalent to the request-level baseline. For pipeline-parallelism experiments (Section 5.3): (4) TP+PP with Orca-style scheduling: 8-way tensor parallelism within a node, 8-way pipeline parallelism across nodes, with iteration-level scheduling and no constraints on batch composition. (5) TP-only (8 replicas): 8 independent replicas, each with 8-way tensor parallelism, serving simultaneously—no pipeline parallelism. For all baselines, the maximum batch size that fits in GPU memory is used.

• Generation budget / compute accounting. The paper does not use a "generation budget" in the sense of limiting model outputs; it evaluates system throughput under steady-state workloads where all parameters (sequence length, batch size, P:D ratio, chunk size) are fixed for each experimental configuration. Compute is accounted in terms of wall-clock time (milliseconds per iteration, seconds to complete N requests) and throughput (tokens per millisecond). For the decode-maximal batching experiments, the cost of the prefill chunk is the full hybrid-batch time, and the marginal decode cost is the difference between the hybrid-batch time and a prefill-only batch of the same prefill size—this isolates the incremental cost of the piggybacked decodes. For lookahead-style comparisons (none in this paper; this is a standard note about fairness—the paper does not use variable-cost methods like tree search). In the pipeline-parallelism simulation, compute accounting includes both computation time (from profiling on real A100 GPUs) and network communication time (from profiling NCCL operations), and the simulation is validated to be within 5% of empirical measurements on an 8-GPU A100 DGX box.

• Cross-validation / statistical protocol. No cross-validation applies; this is a deterministic systems measurement, not a statistical learning evaluation. Throughput numbers are measured empirically on physical GPUs (Sections 5.1, 5.2, 5.4) or estimated by a validated simulator (Section 5.3). The paper reports point measurements without confidence intervals, which is standard for systems performance papers but limits the ability to assess variance. The simulation processes 10,000 requests to ensure stable aggregate timing; the per-request bubble time CDF (Figure 12a) is plotted across all requests.

Main Quantitative Results

Single-GPU Decode Speedup (Section 5.1.1)

The headline result: SARATHI improves decode throughput by up to 10× over the baseline request-level scheduler. Figure 8 plots decode speedup as a function of batch size for LLaMA-13B on an A6000 GPU with a chunk size of 256 and three sequence lengths (1K, 2K, 3K). At batch size 2 with 1K sequence length, the speedup exceeds 10×. The speedup decreases as batch size increases—at the maximum batch size of 18 (1K sequence length), the speedup is approximately 2.8×. This decline is expected because the baseline decoder becomes more efficient at larger batch sizes (more tokens per weight fetch reduces the per-token memory-bound penalty), leaving less room for improvement. The speedup also decreases with longer sequence lengths: at 3K sequence length, the maximum speedup is approximately 3.5× at the smallest batch size that fits, compared to ~4× at 2K and ~10× at 1K. This is attributed to the growing attention cost at longer sequences: "the cost of attention increases quadratically with the sequence length: since all our improvements come from optimizing the linear operations, a higher attention cost reduces our scope for improvement."

The paper emphasizes that even the "reduced" speedups are substantial: "our decode throughput improvement is still significant in all cases (2.8×−10×)." This range—never below 2.8×—is important because it establishes that the benefit does not vanish even at the largest practical batch sizes.

Peak End-to-End Throughput Gains (Section 5.1.2)

Table 4 presents the peak end-to-end throughput gains across two model-GPU combinations and three sequence lengths. For LLaMA-13B on A6000: at 1K sequence length (batch size 6, P:D ratio 50:1, chunk size 256), decode speedup is 5.45× and end-to-end throughput gain is 1.33×. At 2K sequence length (batch size 6, P:D ratio 50:1), decode speedup drops to 3.26× and end-to-end gain to 1.26×. At 3K (batch size 6, P:D ratio 50:1), decode speedup is 2.51× and end-to-end gain is 1.22×. For LLaMA-33B on A100: at 1K (batch size 10, P:D ratio 28:1), decode speedup is 3.83× and end-to-end gain is 1.25×. At 2K (batch size 5, P:D ratio 63:1), decode speedup is 4.25× and end-to-end gain is 1.22×. At 3K (batch size 3, P:D ratio 127:1), decode speedup is 3.51× and end-to-end gain is 1.14×.

Two patterns stand out. First, the end-to-end throughput gain (1.14×–1.33×) is much smaller than the decode speedup (2.51×–5.45×). The paper explains this directly: "our technique only improves decodes and not prefills." Since the prefill phase still runs at its baseline efficiency (modulo the chunking overhead), the overall gain is the decode gain weighted by the fraction of total time spent in decode. Second, the A100 gains are systematically lower than the A6000 gains (1.25× vs. 1.33× at 1K). The paper attributes this to the A100's higher FLOPs-to-memory-bandwidth ratio (~156 vs. ~53, ignoring caches), which means the A100's decode phase is less severely memory-bound than the A6000's at the same batch size, leaving less room for improvement. Larger chunk sizes or larger models (with larger hidden dimensions, which increase arithmetic intensity) would be needed on the A100 to achieve the same relative gain. Nevertheless, "SARATHI still consistently outperforms the baseline by 1.14×-1.25× on the A100 GPU."

Effect of Varying P:D Ratio (Section 5.1.3)

Figure 9 presents normalized throughput (tokens/ms) as a function of P:D ratio for three sequence lengths (1K, 2K, 3K) and three chunk sizes (128, 256, 512) on LLaMA-13B/A6000. The key finding is that throughput improvement from SARATHI is non-monotonic in P:D ratio: it rises to a peak and then falls.

At 1K sequence length with batch size 18 (Figure 9a), the peak occurs at P:D ≈ 14 for chunk size 256 and at P:D ≈ 28 for chunk size 512. These values match the theoretical perfect-piggybacking condition: P/D = C/(B-1) = 256/17 ≈ 15 and 512/17 ≈ 30, respectively. The peak throughput gain at chunk size 256 is approximately 1.27×; at chunk size 512, approximately 1.23×; at chunk size 128, approximately 1.10×. The chunk size 128 peak is lower because "splitting prefills into very small chunks leads to lower arithmetic intensity i.e. less efficient matmuls and higher overheads (due to multiple reads of KV cache), resulting in reduced end-to-end performance."

At 2K sequence length with batch size 10 (Figure 9b), the peaks shift leftward (to lower P:D ratios) because B-1 = 9, making C/(B-1) larger for the same C. At 3K sequence length with batch size 6 (Figure 9c), the peaks shift further left.

The paper notes that the throughput gain is "around 10% over a large range of P:D ratios" even away from the peak—this is visible in the relatively flat regions of the curves away from the optimum. When the P:D ratio is very low (decode-dominated), SARATHI runs out of prefill chunks and some decodes must execute in decode-only batches, reducing the gain. When the P:D ratio is very high (prefill-dominated), SARATHI processes prefill chunks with fewer than B-1 piggybacked decodes (because decodes complete early), wasting the piggybacking opportunity.

Effect of Varying Batch and Chunk Sizes (Section 5.1.4)

Figure 10 breaks down the per-operation runtime (preproj, attention, postproj, FFN) for LLaMA-13B/A6000 across three sequence lengths, two chunk sizes (256 and 512), and varying batch sizes, in the balanced regime where P:D = C/(B-1) and all decodes are perfectly piggybacked.

The headline finding is that the FFN linear layer sees the largest runtime reduction from decode-maximal batching. At 1K sequence length with chunk size 256 and batch size 18, the FFN runtime drops by approximately 1.5× compared to the baseline (orange vs. blue bars in the top-left panel). For smaller batch sizes, "most of the throughput improvement is due to the higher efficiency of ffn computation." The preproj and postproj operations see smaller reductions (1.05×–1.38×). The attention time increases slightly or stays roughly constant—it is not fused and derives no benefit from decode-maximal batching. At 2K sequence length with chunk size 256 and batch size 10, the FFN speedup is approximately 1.4×. At 3K with chunk size 256 and batch size 6, the speedup is approximately 1.3×.

Comparing chunk sizes: chunk size 256 consistently provides higher gains than chunk size 512 at the same P:D-balanced point. For example, at 1K with batch size 18, the FFN speedup with chunk size 256 is visually approximately 1.5× versus approximately 1.3× with chunk size 512. The paper explains: "using a chunk size of 256 doubles the number of decodes that can be piggybacked compared to using 512 as the chunk size. Therefore, in the optimal configurations (P:D = C/(B-1)), for chunk size of 256, decodes constitute a higher fraction of total runtime, compared to the optimal configuration when chunk size is 512. Therefore, our throughput gains are higher when using chunk size of 256."

The aggregate total time bars (rightmost pair in each subplot) confirm the acceleration: SARATHI processes the same total tokens (prefill + decode) in substantially less time than the baseline, with the gap widening at larger batch sizes.

Comparison to Iteration-Level Scheduling (Orca) (Section 5.2)

Figure 11 directly compares SARATHI against Orca's iteration-level scheduling for LLaMA-13B/A6000. Figure 11a fixes P:D = C/(B-1) with C=256 and varies sequence length. At 1K sequence length, the baseline (normalized to 1.0) is improved by Orca best-case to approximately 1.11× and by SARATHI to approximately 1.27×. Orca worst-case matches the baseline (1.0×), as expected when no incidental overlap occurs. At 2K sequence length, Orca best-case drops to near-baseline while SARATHI maintains approximately 1.25×. At 3K sequence length, Orca best-case is essentially at baseline (no gain) while SARATHI delivers approximately 1.23×.

The collapse of Orca's best-case performance with increasing sequence length is explained by the reduction in batch size B (from 18 at 1K to 10 at 2K to 6 at 3K). At 3K with B=6, the optimal P:D for SARATHI is C/(B-1) = 256/5 ≈ 51. Orca, which submits the entire prefill as one chunk, "soon runs out of the prefill tokens, at which point it processes the remaining decode tokens similar to the baseline, making even the best-case version inefficient." The higher the optimal P:D ratio, the faster Orca exhausts its single prefill and reverts to decode-only batches.

Figure 11b sweeps the P:D ratio at 1K sequence length with batch size 18, comparing SARATHI at three chunk sizes against Orca best-case. SARATHI with chunk size 256 peaks at P:D ≈ 14 with approximately 1.27× gain. SARATHI with chunk size 512 peaks at P:D ≈ 28 with approximately 1.23× gain. SARATHI with chunk size 128 peaks at a lower value but with a lower absolute gain (~1.10×). Orca best-case shows flatter gains across the range, peaking at approximately 1.11× at a high P:D ratio (where prefill tokens are abundant and decodes are few). The paper interprets Orca best-case as "a special case of SARATHI, where the chunk size, C, is set to the maximum sequence length"—the entire prefill is one chunk, so the peak shifts far to the right and the absolute gain is limited by the small number of decode tokens that fit in a single batch.

The paper also identifies a latency benefit of SARATHI over Orca that is not captured in the throughput numbers: "since the prefill time increases with the length of the input sequence, adding a longer prefill sequence in a running batch can delay the ongoing decodes, which in turn increases the latency of these ongoing requests in Orca scheduling. SARATHI avoids this due to the use of smaller chunk prefills." This is a qualitative claim without quantified latency measurements in the paper—a gap in the experimental evaluation.

Pipeline Parallelism Results (Section 5.3)

The pipeline-parallelism experiments use the GPT-3 model simulated across 64 A100 GPUs (8 nodes × 8 GPUs each, with 8-way TP within each node and 8-way PP across nodes, connected via InfiniBand). The workload is 10,000 requests with sequence lengths sampled from a Zipf distribution (θ = 0.4, range 1K–4K), P:D ratio fixed at 10, and SARATHI chunk size set to 256.

Figure 12a plots the CDF of pipeline bubble time per request. SARATHI reduces the median bubble time by 6.29× compared to the TP+PP baseline with Orca-style scheduling. The distribution for SARATHI is tightly concentrated near zero, while the baseline distribution is much wider, with a long tail. This directly validates the paper's claim that uniform batch compute times eliminate pipeline bubbles.

Figure 12b plots the time to complete all 10,000 requests for three configurations. The baseline TP+PP (Orca-style) completes in approximately 3200 seconds. TP-only (8 replicas, no PP) completes in approximately 2500 seconds—28% faster than the baseline TP+PP, despite supporting only 1/2.45 of the batch size (11 vs. 27). This is the critical negative result: pipeline parallelism with heterogeneous batches is worse than simply running additional independent replicas. SARATHI-enabled TP+PP completes in approximately 1680 seconds—1.91× faster than the baseline TP+PP and 1.48× faster than TP-only.

The paper interprets these numbers as evidence that SARATHI "makes pipeline parallel execution an attractive option for LLM inference by significantly minimizing pipeline bubbles." The 1.48× speedup over TP-only is particularly significant because PP has lower communication overhead than TP (point-to-point vs. all-reduce), which means it can scale better across nodes where high-bandwidth interconnects are unavailable. The baseline TP+PP's underperformance (1.28× slower than TP-only) shows that without uniform batches, the communication advantage is overwhelmed by bubble overhead.

Ablation Studies and Robustness Checks

Chunk size vs. prefill attention overhead (Figure 13a): For LLaMA-13B/A6000, the self-attention time during chunked-prefills increases as chunk size decreases, relative to a full prefill baseline. At chunk size 64 with 1K sequence length, attention time is approximately 1.3× the baseline (not 3× as the text might suggest—the "3× overhead" mentioned in Section 5.4 applies only to "the chunk size of 64" and "for attention," but Figure 13a shows the speedup (baseline/chunked), so a value below 1.0 indicates overhead. Reading the figure: the y-axis is "Speedup (prefill-attention)" where values below 1.0 indicate slowdown. At chunk size 64, 1K sequence length, the speedup is approximately 0.33, corresponding to a 3× overhead. At chunk size 128, speedup is approximately 0.62 (1.6× overhead). At chunk size 256, speedup is approximately 0.85 (1.18× overhead). At chunk size 512, speedup is approximately 0.96 (1.04× overhead). The overhead is larger for longer sequences because there are more KV cache entries from prior chunks to re-read.

Chunk size vs. overall prefill time (Figure 13b): The total prefill time (including attention and linear operations) shows the same trend with larger magnitude. At chunk size 64, the speedup is approximately 0.2 (5× overhead). At chunk size 128, approximately 0.5 (2× overhead). At chunk size 256, approximately 0.83 (1.2× overhead). At chunk size 512, approximately 0.91 (1.1× overhead). This confirms that the linear operations' reduced arithmetic intensity (not just attention re-reads) contributes significantly to the overhead at small chunk sizes.

Chunk size vs. end-to-end throughput (Figure 13c): When chunked-prefills is used in tandem with decode-maximal batching at the balanced P:D ratio, the end-to-end throughput tells a different story. Chunk size 64 approximately matches the baseline (speedup ~1.0×)—the 5× prefill slowdown is fully offset by decode gains. Chunk size 128 achieves approximately 1.16× speedup—the decode gain more than compensates for the 2× prefill overhead. Chunk size 256 achieves approximately 1.27× speedup. Chunk size 320 performs worse than chunk size 256 (speedup ~1.20× vs. 1.27×) despite being "larger and therefore more prefill-efficient" in theory—this is the tile quantization effect, since 320 is not a multiple of 128. Chunk size 384 achieves approximately 1.24×, and chunk size 512 achieves approximately 1.23×. The finding is that the optimal chunk size for end-to-end throughput is not the smallest size that saturates compute, nor the largest that preserves prefill efficiency, but rather a size that balances prefill efficiency against decode coverage, subject to tile-quantization constraints.

Varying sequence length in pipeline simulation (Figure 12): The pipeline simulation uses a Zipf distribution of sequence lengths (θ = 0.4) rather than fixed lengths, demonstrating that SARATHI's uniform-batch property holds under realistic request-length variation. The CDF in Figure 12a shows that even with variable-length requests, SARATHI keeps bubble times tightly clustered, while the baseline's bubble times vary widely. This is an implicit robustness check: chunked-prefills and decode-maximal batching do not require all requests to have the same length.

Model scale robustness (Table 4, implicitly): The evaluation spans LLaMA-13B (hidden size 5120) on A6000, LLaMA-33B (hidden size 6656) on A100, and GPT-3 (hidden size 12288) on simulated A100, demonstrating that the techniques work across a range of model scales and hidden dimensions. The gains are larger on the A6000 than the A100 (1.33× vs. 1.25× at 1K), which is attributed to the A6000's lower FLOPs-to-memory-bandwidth ratio. This suggests that SARATHI's benefits are larger on commodity GPUs with lower memory bandwidth—precisely the hardware where decode inefficiency is most severe. This is a positive robustness result: the technique is most beneficial where it is most needed.

Negative result: Orca's claimed bubble elimination (Figure 12): The paper directly tests and refutes Orca's claim that iteration-level scheduling eliminates pipeline bubbles (Figure 8 in Yu et al. [48]). Figure 12a shows that with Orca-style scheduling on a realistic workload, pipeline bubbles are substantial—the median bubble time per request is 6.29× higher than with SARATHI. This is a negative result for the prior state-of-the-art and validates the paper's central motivation that heterogeneous batch composition is a first-order problem.

Critical Assessment

Do the experiments demonstrate that SARATHI "improves decode throughput by up to 10×"?

Yes, conditionally. Figure 8 shows decode speedup exceeding 10× at batch size 2 with 1K sequence length. However, this is at a very small batch size—one that would not be used in practice because it leaves GPU memory and compute underutilized. At the maximum batch size that fits in memory (18 for 1K sequences), the speedup is approximately 2.8×. The "up to 10×" claim is therefore a best-case headline number that applies to configurations that are far from deployment-optimal. A more representative range is 2.8×–5.5× (Table 4, the "Decode Speedup" column at the maximum feasible batch sizes). The paper is transparent about this—Figure 8 clearly shows the decline with batch size—but the "up to 10×" framing in the abstract and Section 1 risks misinterpretation.

Do the experiments demonstrate "up to 1.33× end-to-end throughput improvement"?

Yes, and with appropriate caveats. Table 4 reports a 1.33× end-to-end gain for LLaMA-13B/A6000 at 1K sequence length, batch size 6, P:D ratio 50:1. This is measured at the workload configuration that maximizes the gain—specifically, at the P:D ratio where decode tokens perfectly piggyback with prefill chunks. At other P:D ratios, the gain is lower (Figure 9 shows a broad peak around 1.27× at 1K with chunk size 256, and Figure 11a shows 1.27× at the optimal P:D). The real-world applicability depends on whether actual deployment workloads have P:D ratios near the optimum. The paper does not characterize P:D ratios of real LLM serving workloads (e.g., from production traces), which is a significant gap: the 1.33× figure is an achievable upper bound, not a guarantee for any particular deployment.

Do the experiments demonstrate "up to 4.25× higher decode throughput" for LLaMA-33B/A100?

Yes. Table 4 reports 4.25× decode speedup at 2K sequence length, batch size 5, P:D ratio 63:1. The accompanying end-to-end gain is 1.22×. Notably, the decode speedup is higher at 2K (4.25×) than at 1K (3.83×), even though the absolute baseline decode time is higher at 2K—this reflects that the piggybacking efficiency depends on the P:D ratio and batch size, not just sequence length.

Do the experiments demonstrate that SARATHI "reduces bubbles by 6.29×"?

Yes, for the specific configuration simulated. Figure 12a shows that the median pipeline bubble time per request is reduced by a factor of 6.29×. However, this is a simulation—not a physical deployment—and the paper validates the simulator only against an 8-GPU box (within 5% error), not against a 64-GPU cluster. The qualitative finding (uniform batches dramatically reduce bubbles) is well-supported by the single-GPU micro-benchmarks showing uniform batch compute times (Section 4), but the exact 6.29× multiplier is specific to the simulated workload (GPT-3, 64 A100 GPUs, Zipf-distributed sequence lengths 1K–4K, P:D=10). Different workload parameters would yield different bubble-reduction factors.

Do the experiments demonstrate "end-to-end throughput improvement of 1.91×" with pipeline parallelism?

Yes, in simulation. Figure 12b shows SARATHI-enabled TP+PP completing the 10,000-request workload in approximately 1680 seconds versus approximately 3200 seconds for baseline TP+PP—a 1.91× speedup. However, the baseline for this comparison is a TP+PP deployment with Orca-style scheduling, which the paper has already shown is worse than TP-only (1.28× slower). The more informative number is the 1.48× speedup over TP-only, since TP-only is the practical alternative when PP's bubbles make it unattractive. The 1.91× claim is technically correct as stated (baseline TP+PP vs. SARATHI TP+PP), but the 1.48× over TP-only is the more meaningful practical comparison.

Are there experiments that would have strengthened the paper but were not run?

Several gaps are notable. First, there is no latency evaluation. SARATHI claims a latency benefit over Orca (Section 5.2: "adding a longer prefill sequence in a running batch can delay the ongoing decodes... SARATHI avoids this due to the use of smaller chunk prefills"), but no time-to-first-token or per-token latency measurements are reported. Since SARATHI serializes a request's prefill into multiple chunks, it necessarily delays the completion of the full prefill compared to processing it in one pass—which could increase time-to-first-token for that request. The tradeoff between throughput and latency is not explored.

Second, there is no comparison against vLLM's PagedAttention memory management [20], which could increase the maximum batch size by reducing KV cache memory waste. The paper acknowledges this as complementary (Section 7.1), but an experiment combining SARATHI's batching with vLLM's memory management would quantify the combined benefit and establish whether the techniques are additive or overlapping.

Third, the evaluation does not vary the tile size constraint or test on GPUs with different tile sizes (e.g., older architectures). The tile quantization finding is validated only on A6000/A100 GPUs with 128×128 tiles. The generalizability to other hardware is untested.

Fourth, the pipeline parallelism experiments are simulation-only. A physical deployment on 64 A100 GPUs would validate the simulator's fidelity and surface any real-world effects (network contention, stragglers, NUMA effects) not captured in the model.

Fifth, there is no ablation on the number of prefill chunks per batch. The paper asserts that exactly one prefill chunk per batch is optimal, but does not test configurations with two or more chunks per batch. A workload with very short prefills (e.g., 128 tokens) might benefit from two chunks per batch to increase the prefill compute intensity further, and this design choice is not explored.

Sixth, the paper does not evaluate end-to-end model accuracy or output quality. Since chunked-prefills is mathematically equivalent to full prefill (Section 4.2), accuracy should be unchanged—but this is an assertion, not a measurement. If floating-point non-associativity or attention-mask implementation bugs affect the chunked computation differently, this would surface only in accuracy tests, which are absent.

Do the experiments support the claim that "pipeline parallelism becomes a viable deployment strategy only when micro-batch compute times are rendered uniform"?

Yes, with the strong evidence in Figure 12b: the baseline TP+PP is 1.28× slower than TP-only, while SARATHI's TP+PP is 1.48× faster than TP-only. The viability reversal is clear. However, "only when" is a stronger claim than the experiments fully support—it implies that no other technique could make pipeline parallelism viable, which is not tested. A more precise statement would be "uniform micro-batch compute times are sufficient to make pipeline parallelism viable and 1.48× faster than TP-only in this configuration; without them, PP is 1.28× slower than TP-only."

Are there workload regimes where SARATHI provides no benefit or is detrimental?

The paper identifies these implicitly. When P:D is very high (prefill-dominated, e.g., P:D > 200), decode time is a small fraction of total inference time, so improving decode efficiency provides marginal end-to-end gain. When P:D is very low (decode-dominated, e.g., P:D < 5), SARATHI runs out of prefill chunks and reverts to decode-only batches for many iterations, reducing the benefit. The paper also shows that chunk size 64 produces no net end-to-end gain (Figure 13c, speedup ~1.0×)—the prefill overhead exactly cancels the decode benefit. At chunk sizes below 64 (not tested), the end-to-end throughput would likely drop below baseline. These are not presented as "failure modes" but are visible in the experimental data. A more explicit characterization of the crossover point where SARATHI becomes detrimental (e.g., for what P:D ratio and chunk size does throughput fall below 1.0×) would strengthen the practical guidance.

6. Limitations and Trade-offs

The Difficulty Estimation Cost Is Not Accounted for in the Headline Efficiency Numbers

The assumption or constraint. SARATHI's ideal chunk size selection (Section 4.4) requires knowing the workload's P:D ratio — the average ratio of prefill tokens to decode tokens — to choose the chunk size C that places the system at the perfect-piggybacking point (where P/D ≈ C/(B−1)). The paper treats this as a known workload parameter: "the ideal chunk size depends on the expected P:D ratio and the split between prefill and decode times for a given application." However, the P:D ratio of an LLM deployment is not a static, known quantity. It varies across applications, across time (as user behavior changes), and across individual requests within a single deployment.

The paper explicitly acknowledges this in Section 6:

"we leave it to future work to explore how to pick an optimal chunk size as it depends on several factors like the hardware, model characteristics, sequence length, and the composition of prefill-decode tokens, especially in scenarios where the P:D ratio may not be known ahead of time."

The consequence. If the actual P:D ratio deviates substantially from the assumed value, the chunk size C will be mismatched to the workload. There are two failure modes. If the actual P:D ratio is lower than assumed (more decode-heavy than expected), SARATHI will run out of prefill chunks before all decodes are processed, and the remaining decodes must execute in decode-only batches — reverting to baseline inefficiency for that fraction of the workload. If the actual P:D ratio is higher than assumed (more prefill-heavy), SARATHI will process prefill chunks with fewer than B−1 piggybacked decodes, wasting the opportunity. Figure 9 shows that throughput falls off on both sides of the optimal P:D ratio, but the paper does not characterize how steep this falloff is in realistic deployment scenarios where the P:D ratio is estimated rather than known exactly.

More importantly, the P:D ratio can change over a deployment's lifetime. A chatbot application might see short-prompts-with-long-responses (low P:D) during one hour and long-prompts-with-short-responses (high P:D) during another hour, as user behavior shifts. SARATHI provides no mechanism for dynamically adapting the chunk size in response to changing workload characteristics — chunk size is a static configuration parameter. If the P:D ratio drifts, the system operates at suboptimal efficiency until an operator manually re-tunes C.

What evidence exists in the paper. Figure 9 provides the relevant evidence: for a fixed chunk size, the throughput improvement over baseline varies with P:D ratio, peaking at the perfect-piggybacking point and declining on both sides. At chunk size 256 with 1K sequence length and batch size 18, the improvement is approximately 1.27× at P:D ≈ 14, but drops to approximately 1.10× at P:D ≈ 1 and approximately 1.05× at P:D ≈ 200. The "around 10% over a large range of P:D ratios" claim implies that the curve is relatively flat away from the peak, but a 10% gain versus a 27% gain is a meaningful difference — it means more than half the potential benefit can be lost to P:D mismatch. The paper does not measure the sensitivity of end-to-end throughput to P:D estimation error explicitly.

Mitigation status. The paper acknowledges this as a limitation and flags it for future work (Section 6), but provides no mechanism — even a heuristic one — for online estimation of P:D ratio or dynamic chunk size adaptation. A practitioner deploying SARATHI today would need to measure their workload's P:D ratio offline, select a chunk size based on that measurement, and accept that any workload drift reduces efficiency. This is a significant practical gap between the paper's controlled experimental conditions (where P:D ratio is fixed and known) and real deployment conditions (where P:D ratio is unknown and time-varying).

---

Latency Implications Are Not Evaluated, Despite a Throughput-Latency Tradeoff Inherent in Chunking

The assumption or constraint. SARATHI is evaluated exclusively on throughput metrics — tokens per millisecond, decode speedup, end-to-end throughput gain, and request completion time in batch settings. There is no evaluation of request-level latency: time-to-first-token (TTFT), per-token decode latency, or end-to-end request latency for individual requests. The paper makes one qualitative latency claim in Section 5.2:

"since the prefill time increases with the length of the input sequence, adding a longer prefill sequence in a running batch can delay the ongoing decodes, which in turn increases the latency of these ongoing requests in Orca scheduling. SARATHI avoids this due to the use of smaller chunk prefills."

This claims a latency benefit over Orca, but it is not quantified.

The consequence. Chunked-prefills introduces a structural latency tradeoff that the paper does not discuss. A request with a prompt of length P must wait for ⌈P/C⌉ sequential prefill chunk passes before its full prefill is complete. During this time, the request's tokens are being processed incrementally, but the request cannot begin generating output tokens (decode) until all prefill chunks have been processed. For a request with a 2K prompt and a chunk size of 256, this means 8 sequential forward passes before the first decode token can be generated — each at the full hybrid-batch latency. In the baseline system, the same request's prefill is completed in a single forward pass. This means SARATHI may substantially increase time-to-first-token for long-prompt requests, even as it improves aggregate decode throughput.

Conversely, the paper's claim about SARATHI reducing decode latency jitter (by avoiding large prefill insertions in running batches) is plausible but unmeasured. A fair comparison would require latency measurements under realistic request arrival patterns — e.g., Poisson arrivals with variable prompt lengths — to assess whether SARATHI's worst-case TTFT, median TTFT, and tail latency are better or worse than Orca's. Throughput alone does not determine user experience; latency does, especially for interactive applications like chatbots and code assistants that the paper cites as motivating use cases (Section 1).

What evidence exists in the paper. None. There is not a single latency measurement in the entire evaluation. Table 2 reports per-iteration runtime for specific batch compositions but does not translate these into request-level latency metrics. The pipeline simulation (Section 5.3) reports "time to complete N requests" (Figure 12b), which is an aggregate throughput metric, not a per-request latency distribution. The claim that "SARATHI avoids this due to the use of smaller chunk prefills" (regarding decode latency jitter in Orca) is asserted without evidence.

Mitigation status. The paper does not acknowledge the latency tradeoff, does not measure latency, and does not suggest how to balance throughput against latency in SARATHI. The Section 6 discussion mentions that "real-world deployments need to optimize an inference serving infrastructure simultaneously along multiple dimensions e.g., latency, queuing delays, fairness, etc." and that "meeting these goals with SARATHI requires revisiting scheduling policies," but this is a forward-looking statement, not a mitigation. For a practitioner, the absence of latency evaluation means there is no guidance on whether SARATHI is suitable for latency-sensitive deployments. If TTFT matters (as it does for interactive chat), the chunked-prefills approach may be contra-indicated for long-prompt requests, and the paper provides no data to assess this risk.

---

The Pipeline Parallelism Experiments Are Simulation-Only with Unvalidated Scale-Up

The assumption or constraint. The GPT-3 pipeline parallelism evaluation (Section 5.3) is conducted entirely in a custom simulator, not on physical hardware at the scale claimed. The simulator was built by profiling individual transformer operations on a single A100 GPU, profiling NCCL communication costs for tensor-parallel all-reduces and pipeline-parallel point-to-point transfers, and then fitting a regression model to extrapolate to configurations beyond the profiled range. The paper validates this simulator against an 8-GPU A100 DGX box:

"We confirmed that the estimated runtimes by the simulator are within 5% of the empirical values on an 8-GPU, 80GB A100 DGX box."

The full-scale experiments, however, simulate 64 A100 GPUs across 8 servers connected via InfiniBand — an 8× scale-up from the validated configuration.

The consequence. Several real-world effects that could materially affect pipeline parallelism performance at scale are not captured by the 8-GPU validation. Network congestion across InfiniBand links becomes significant at the 8-node scale — multiple servers injecting traffic simultaneously can saturate switch buffers, causing communication time variance not present in a single-node profile. NUMA effects within multi-socket servers can introduce memory access asymmetry that a single-node profile smooths over. Straggler effects — one GPU in the pipeline occasionally taking longer due to hardware variance, thermal throttling, or OS jitter — compound across pipeline stages: a delay at stage k propagates to stages k+1 through K as pipeline bubbles. These effects are notoriously difficult to simulate accurately and are the primary reason physical-at-scale evaluations carry more weight in systems research.

The 5% error bound on the 8-GPU validation does not guarantee 5% error at 64 GPUs. The paper does not report how the simulation error scales with GPU count, nor does it conduct sensitivity analysis (e.g., perturbing communication times by ±10% to see if the 1.91× speedup is robust). The specific headline numbers — 6.29× bubble reduction, 1.91× end-to-end speedup, 1.48× over TP-only — are therefore best interpreted as simulator estimates whose real-world accuracy is unverified at the scale claimed.

What evidence exists in the paper. The validation is described in one sentence in Section 5.3, with the 5% error claim. There is no figure showing the simulator's predictions versus empirical measurements across multiple configurations. The bubble-time CDF (Figure 12a) and completion-time plot (Figure 12b) are simulation outputs, not measurements. The single-node baseline TP+PP and SARATHI TP+PP curves in Figure 12b are distinguishable by large margins (~3200s vs. ~1680s), so even a substantial simulation error (e.g., 20–30%) would not change the qualitative finding that SARATHI reduces pipeline bubbles and improves throughput. However, the exact multipliers (6.29×, 1.91×) would change under realistic network and system noise.

Mitigation status. The paper does not claim these are physical measurements — the text and Table 3 clearly label the GPT-3 experiments as "Simulation." However, the abstract and introduction report the 6.29× and 1.91× numbers without the "simulated" qualifier, which could mislead a casual reader. The paper does not discuss the limitations of simulation-based evaluation or propose a physical at-scale validation as future work. For a practitioner considering deploying SARATHI with pipeline parallelism on a large cluster, the simulation provides a directionally encouraging signal but no guarantee of the specific speedup magnitude in a real deployment.

---

Single-Request, Fixed-Length Assumption for Most Experiments

The assumption or constraint. In all single-GPU experiments (Sections 5.1, 5.2, 5.4), the paper assumes that every request in a batch has the same total sequence length (prefill + decode tokens) and the same P:D ratio. For example, Table 4 reports results at "sequence length = 1K" with a fixed P:D ratio of 50:1 — meaning every request has exactly the same number of prefill tokens and decode tokens. The paper acknowledges this in Section 6:

"we make a simplistic assumption in this paper that each request in a batch has the same number of prefill and decode tokens (except the simulation experiments) whereas, in the real world, the sequence lengths can vary significantly across different LLM inference requests."

The pipeline simulation (Section 5.3) does use variable-length requests (sampled from a Zipf distribution), but only for GPT-3 in simulation — and even there, all requests share the same P:D ratio of 10.

The consequence. In real deployments, requests vary in both prompt length and generation length. This variability affects SARATHI in at least two ways. First, variable prompt lengths mean that the number of prefill chunks per request varies — some requests contribute many chunks (long prompts), others few (short prompts). The system's ability to maintain the perfect-piggybacking steady state depends on having a balanced mix of prefill chunks arriving to match the decode demand. If all concurrent requests have short prompts (e.g., a sudden burst of "Hello, how are you?" queries), there may be insufficient prefill chunks to cover all decodes, and the system temporarily reverts to decode-only batches — reducing throughput. The paper's fixed-length experiments cannot capture this transient behavior.

Second, variable KV cache lengths (because different requests generate different numbers of decode tokens) create variable attention costs that affect batch compute uniformity. The paper identifies this as pipeline bubble type PB3 (Section 3.2): "bubbles like PB3 that occur due to difference in decode compute times between micro-batches since the accumulated context length (KV cache length) varies across requests." When requests within a decode-maximal batch have different accumulated KV cache lengths, their attention operations take different amounts of time. Since attention is not fused and runs separately per request, the slowest request determines the batch's iteration time — the requests with shorter KV caches wait. This introduces compute-time variance into batches that SARATHI's uniform-chunk design aims to eliminate. The paper's fixed-length experiments suppress this effect by construction.

What evidence exists in the paper. The pipeline simulation (Figure 12) is the only experiment that tests variable-length requests. The CDF in Figure 12a shows that even with variable-length requests, SARATHI's bubble times remain tightly clustered — suggesting that PB3 may be less severe than PB1 and PB2 in practice. However, this is only tested for GPT-3 in simulation with a single P:D ratio (10), and the mechanism by which SARATHI mitigates PB3 (beyond making prefills uniform) is not explained. The single-GPU experiments provide no data on variable-length behavior. The paper does not report, for example, how throughput degrades when sequence lengths are drawn from a realistic distribution with high variance.

Mitigation status. The authors acknowledge this assumption explicitly in Section 6 and present it as future work: "we are actively investigating these challenges." They do not propose a mechanism for handling variable-length requests, such as grouping requests by KV cache length to minimize within-batch attention variance, or dynamically adjusting batch composition based on request lengths. For a practitioner, the fixed-length results should be understood as an upper bound on SARATHI's benefits — real-world variability will reduce the realized throughput gains, but the paper provides no quantitative estimate of by how much.

---

The Tile Quantization Constraint Is Validated Only on A6000/A100 GPUs with a Single Tile Size

The assumption or constraint. The paper elevates tile quantization — the requirement that matrix dimensions be multiples of the GPU's tile size (128) for peak efficiency — to a first-order design constraint for chunk size selection (Section 4.4). The evidence comes entirely from measurements on NVIDIA A6000 and A100 GPUs, both of which use the Ampere architecture with 128×128 matrix-multiply tiles. The paper states the constraint as a general principle:

"GPUs compute matmuls by partitioning the given matrices into tiles and assigning them to different thread blocks for parallel computation... matmuls achieve maximum GPU utilization when the matrix dimensions are divisible by the tile size."

This is correct as stated — all modern GPUs use tiled matrix multiplication — but the specific tile size, the magnitude of the quantization penalty, and the optimal strategy for handling misaligned dimensions vary across GPU architectures (e.g., NVIDIA Volta uses different tile dimensions; AMD GPUs and specialized accelerators like TPUs have different tiling strategies entirely).

The consequence. A practitioner deploying SARATHI on non-Ampere hardware cannot rely on the paper's specific numerical findings about chunk size optimality. The paper's recommendation to round the chunk size so that C + (B−1) is a multiple of 128 is correct for A6000/A100 GPUs but may be suboptimal or actively harmful on other hardware. On a GPU with 64×64 tiles, for example, the optimal alignment would be to multiples of 64, and the magnitude of the misalignment penalty might be different. On hardware without tile-based matmul (e.g., some embedded GPUs or older architectures), the constraint may not apply at all.

More subtly, the paper's observation that chunk size 256 "shows better speedup than 320" (Figure 13c) because 320 is not a multiple of 128 while 256 is — this specific comparison is architecture-dependent. If a future GPU architecture uses larger tiles (e.g., 256×256), the optimal chunk sizes would shift accordingly. The paper does not characterize how sensitive the tile quantization effect is to tile size, nor does it test on GPUs with different tile dimensions to establish the generality of the finding.

What evidence exists in the paper. The tile quantization effect is demonstrated in Figure 7 (iteration time jumps by 32% when sequence length increases from 256 to 257) and Figure 13c (chunk size 256 outperforms 320). Both measurements are on the A6000 GPU (Ampere architecture). The paper does not profile on other GPU architectures, does not identify the tile size of the A6000/A100 explicitly (the "128" number appears without citation to NVIDIA documentation), and does not discuss how the effect would generalize.

Mitigation status. The paper does not acknowledge this as an architecture-specific finding — it presents tile quantization as a universal GPU behavior, which is true at the conceptual level but whose quantitative impact and specific alignment targets are architecture-dependent. A practitioner targeting non-Ampere hardware would need to re-profile the tile quantization effect on their target GPU to determine the appropriate alignment constraint. This is a minor practical hurdle (profiling matmul throughput across sequence lengths is straightforward), but the paper provides no guidance on how to do so, nor does it caution that the specific alignment rules (multiples of 128) may not transfer.

---

No Combination of Chunked-Prefills with Other Complementary Optimizations Is Evaluated

The assumption or constraint. The paper evaluates SARATHI as a standalone system, comparing it against baselines that do not use chunked-prefills or decode-maximal batching. However, the paper explicitly lists several complementary techniques in Section 7 that could compound SARATHI's benefits: vLLM's PagedAttention for dynamic KV cache memory management [20] ("dynamic memory allocation will help in supporting larger batch sizes"), FlashAttention-2 for faster attention [28], and model innovations like multi-query attention [41] that reduce KV cache size. None of these are combined with SARATHI in the evaluation.

The consequence. The maximum batch size B — and therefore the number of decodes B−1 that can piggyback in each decode-maximal batch — is directly limited by GPU memory available for KV caches, as formalized in the equation in Section 4.3.1. vLLM's PagedAttention can increase the effective batch size by reducing KV cache memory waste from over-provisioning, especially when sequence lengths vary across requests. If vLLM increases B from 18 to, say, 25 for LLaMA-13B/A6000 at 1K sequence length, then SARATHI can piggyback 24 decodes per prefill chunk instead of 17 — a 41% increase in piggybacking capacity, which would shift the optimal P:D ratio and likely increase the throughput gain. The paper's evaluation does not measure this combined benefit, so the reported 1.33× end-to-end gain for LLaMA-13B/A6000 should be understood as a lower bound — a system using both SARATHI and PagedAttention could achieve higher gains. Conversely, if the two techniques' benefits overlap (e.g., both primarily increase effective batch size), the combined gain might be sub-additive. The paper provides no data to distinguish these scenarios.

What evidence exists in the paper. None. The paper mentions these techniques as complementary in Section 7.1 but does not integrate any of them into the SARATHI evaluation. The memory constraint equation in Section 4.3.1 assumes conservative, pre-allocated KV cache (the paper "pre-allocate[s] the KV cache as per the maximum sequence length for each experiment"), which is exactly the policy that vLLM improves upon. The paper's experimental results are therefore specific to this memory-allocation policy, and the extent to which improved memory management would increase SARATHI's gains is unknown.

Mitigation status. The paper acknowledges these techniques as orthogonal and complementary — "our current work focuses on optimizing the execution layer and can be used with different scheduling policies proposed by such systems" — but does not attempt to combine them. This is reasonable for a paper introducing a new batching paradigm, since the goal is to isolate the effect of chunked-prefills and decode-maximal batching. However, for a practitioner deciding whether to adopt SARATHI, the key question is not "how much does SARATHI improve over a baseline without dynamic memory management?" but "how much does SARATHI improve over a baseline with dynamic memory management?" — i.e., what is the incremental benefit of SARATHI when deployed alongside current best practices? The paper does not answer this question. It compares SARATHI against Orca (which also uses conservative KV cache allocation) and a request-level baseline, but not against a system combining Orca-style scheduling with PagedAttention, nor against a system combining SARATHI with PagedAttention. The absence of these head-to-head comparisons limits the paper's ability to guide practical deployment decisions where multiple optimizations would be deployed simultaneously.

7. Implications and Future Directions

How This Work Changes the Landscape

SARATHI reframes LLM inference scheduling from a problem of "how to keep the GPU busy despite decode inefficiency" to "how to eliminate decode inefficiency by making every batch structurally hybrid." This is not an incremental scheduling tweak — it is a paradigm shift in what constitutes a batch. Prior to SARATHI, the field treated the prefill-decode mismatch as an inherent characteristic of autoregressive generation to be tolerated (by increasing batch sizes through model parallelism) or opportunistically amelorated (by hoping requests arrive at convenient times for incidental overlap). SARATHI demonstrates that the mismatch is exploitable: the prefill's excess compute intensity can be systematically lent to the decode's deficit, and the scheduler should enforce this pairing as a structural invariant rather than an accident of arrival timing.

The magnitude of this shift is substantial but bounded. It is not a new model architecture or a fundamentally different way of doing attention — it is a rethinking of how GPU work units are composed within the existing transformer inference framework. The 10× decode speedup at small batch sizes and 1.33× end-to-end gain on LLaMA-13B/A6000 establish that the ceiling on inference throughput is meaningfully higher than the field assumed, achievable purely through smarter batching with no hardware or model changes. The finding that pipeline parallelism becomes viable only with uniform batch composition — flipping from 1.28× slower than TP-only to 1.48× faster (Figure 12b) — changes the calculus for multi-GPU deployment and makes pipeline parallelism a first-class scaling strategy rather than a fallback when tensor parallelism is infeasible.

SARATHI also resolves the implicit contradiction between prior work that championed pipeline parallelism for inference (Orca [48], which claimed iteration-level scheduling "eliminates bubbles") and the practical observation that pipeline-parallel inference rarely matches tensor-parallel throughput at scale. The paper demonstrates that this contradiction was an artifact of batch heterogeneity: with Orca-style scheduling, pipeline bubbles are severe (6.29× higher median bubble time per request than SARATHI, Figure 12a), making pipeline parallelism worse than TP-only replication. The claim that iteration-level scheduling eliminates bubbles is shown to be incorrect in the realistic setting of variable batch composition. SARATHI resolves the contradiction by identifying the missing necessary condition — uniform micro-batch compute times — and providing a mechanism (decode-maximal batching with chunked-prefills) that satisfies it.

Several research directions become more attractive as a consequence of these results. Hybrid batching as a scheduling primitive — not just mixing prefill and decode opportunistically, but mandating a specific ratio — opens a new design space for inference schedulers. The paper's demonstration that chunk size is a tunable parameter that controls the prefill-efficiency-vs-decode-coverage tradeoff suggests that future systems might treat batch composition as an optimization variable, dynamically adjusted based on workload characteristics. Hardware-aware batching — where chunk sizes and batch dimensions are chosen not just based on memory capacity but on tile quantization constraints and arithmetic intensity thresholds — becomes a first-order concern rather than a micro-optimization. The tile quantization finding (Figure 7: a 32% runtime jump from adding one token past a tile boundary) establishes that ignoring hardware tiling when designing batching strategies can cost more than the algorithmic improvements being proposed.

Conversely, some research directions become less attractive. Iteration-level scheduling alone — adding dynamic request admission to the batch without controlling batch composition — is shown to have limited upside (1.11× best-case gain for Orca at 1K, collapsing to near-zero at 3K in Figure 11a) because it does not address the fundamental memory-boundedness of decode. The paper's evidence suggests that further refinements to iteration-level scheduling (e.g., more sophisticated admission policies) will hit a ceiling determined by batch composition, not scheduling granularity. Pipeline parallelism for inference without uniform-batch guarantees is shown to be counterproductive — the baseline TP+PP deployment is slower than TP-only despite supporting a 2.45× larger batch size (Figure 12b). This finding should shift research attention from "how to schedule pipeline stages" to "how to construct uniform micro-batches," since the latter is the bottleneck that makes the former viable.

The paper also provides a diagnostic framework for evaluating future inference systems: does the system guarantee that every batch is compute-saturating, and are the batch compute times uniform across pipeline stages? Systems that fail these criteria will suffer from the same inefficiencies (memory-bound decodes, pipeline bubbles) that SARATHI addresses, regardless of other innovations.

Follow-Up Research This Work Enables

Dynamic chunk size adaptation for unknown or time-varying P:D ratios. The paper's ideal chunk size selection (Section 4.4) requires knowing the workload's P:D ratio, but real deployments have unknown and time-varying ratios. A natural follow-up is an online estimation mechanism: maintain an exponentially weighted moving average of recent prefill and decode token counts, compute the estimated P:D ratio, and periodically adjust the chunk size to track the perfect-piggybacking condition (C ≈ (P/D) × (B−1)). A strong evaluation would deploy this on production LLM traces (e.g., from the Chatbot Arena or LMSYS datasets) and measure end-to-end throughput against both a static-chunk-size SARATHI baseline and vanilla Orca. The key question is how quickly the adaptive system converges after a workload shift and whether the overhead of chunk-size transitions (reconfiguring attention masks, potentially flushing in-flight batches) erodes the benefit.

Integration of SARATHI with PagedAttention (vLLM) to measure the combined throughput ceiling. SARATHI's maximum batch size B — and therefore the number of piggybacked decodes B−1 — is limited by GPU memory for KV caches, with the paper using conservative pre-allocation (Section 4.5). vLLM's PagedAttention [20] reduces KV cache memory waste through dynamic, non-contiguous allocation. The combination is theoretically complementary: PagedAttention increases B, which increases B−1, which increases per-batch decode coverage and shifts the optimal P:D ratio. A concrete experiment would implement decode-maximal batching on top of vLLM's kernel and memory manager, measure the resulting maximum batch size for LLaMA-13B/A6000 and LLaMA-33B/A100, and report the combined end-to-end throughput gain relative to (a) SARATHI alone, (b) vLLM alone, and (c) the vanilla baseline. The hypothesis is that the gains are super-additive because SARATHI's efficiency improvement per decode token multiplies with vLLM's increase in the number of decode tokens per batch.

End-to-end latency characterization of chunked-prefills under realistic arrival patterns. The paper evaluates throughput exclusively. Chunked-prefills introduces a structural latency penalty: a request with a prompt of length P must complete ⌈P/C⌉ sequential prefill chunk passes before generating its first token. For a 2K prompt with C=256, that is 8 forward passes — each at the full hybrid-batch latency — before time-to-first-token (TTFT). A rigorous latency evaluation would deploy SARATHI with Poisson request arrivals, variable prompt lengths (drawn from a production distribution, e.g., ShareGPT or LMSYS traces), and variable generation lengths, then measure the TTFT distribution, per-token decode latency distribution, and tail latency (p95, p99) against Orca with iteration-level scheduling. The experiment would reveal whether SARATHI's throughput gain comes at an unacceptable latency cost for interactive applications. A variant worth testing is tiered chunking: use smaller chunks for the first few prefill passes (to minimize TTFT for short prompts) and larger chunks for subsequent passes (to maximize throughput), creating a latency-throughput Pareto frontier that operators can tune.

Application of decode-maximal batching to encoder-decoder models and multi-modal LLMs. SARATHI targets decoder-only transformer architectures (LLaMA, GPT-3). Encoder-decoder models (T5, Flan-T5) have a different inference pattern: the encoder processes the full input once (analogous to prefill), and the decoder generates autoregressively with cross-attention to the encoder outputs. Multi-modal LLMs (LLaVA, GPT-4V) add image or audio encoders whose outputs feed into the autoregressive decode. The core insight — that one compute-saturating component can amortize weight fetches for memory-bound components — should transfer, but the details differ: in an encoder-decoder model, could the encoder's compute-saturating forward pass be chunked (e.g., processing the encoder input in segments) and paired with decoder tokens in hybrid batches? A strong follow-up would implement SARATHI-style batching for Flan-T5-XXL or LLaVA-13B, profile the arithmetic intensity of encoder, decoder, and cross-attention operations, and measure end-to-end throughput gains over the respective baselines. A negative result (e.g., cross-attention's memory access pattern prevents effective piggybacking) would refine our understanding of when hybrid batching works and when it doesn't.

Training a lightweight P:D-ratio predictor to enable closed-loop chunk size control. The paper's Section 6 notes that the optimal chunk size depends on the P:D ratio, which "may not be known ahead of time." A concrete approach: train a small neural predictor (e.g., a 2-layer MLP or a tiny transformer) that takes as input recent request metadata (prompt length, generation length so far, arrival rate) and predicts the average P:D ratio for the next time window. The predictor could be trained on historical deployment traces. The predicted P:D ratio feeds into the chunk-size formula (C ≈ (P/D) × (B−1), adjusted for tile quantization) to set the chunk size dynamically. The experiment would compare the throughput of this closed-loop system against (a) a static chunk size chosen based on the global average P:D ratio and (b) an oracle that knows the true P:D ratio. The key metric is how close the predictor gets to oracle throughput, and whether the prediction overhead (inference time of the predictor itself) is negligible relative to the batching benefit.

Stress-testing SARATHI on very long sequences (10K–100K tokens) where attention dominates runtime. The paper acknowledges in Section 6 that "very long sequences (e.g., 10s-100s of thousands) may pose new challenges as the cost of attention grows quadratically with the number of tokens." SARATHI's benefits come entirely from optimizing linear operations — attention is not fused and receives no improvement (Table 2: attention time is unchanged). For sequences where attention dominates (e.g., 32K context windows), the linear-operation speedup from decode-maximal batching becomes a smaller fraction of total runtime, and the KV cache re-read overhead from chunked-prefills becomes more severe (since earlier chunks' KV caches are larger and must be loaded during each subsequent chunk's attention). A stress-test would evaluate SARATHI on a model supporting 32K–128K context (e.g., LLaMA-2-7B with RoPE scaling or a recent long-context model), measure the crossover sequence length where SARATHI's end-to-end gain drops below 1.0× (i.e., becomes detrimental), and identify whether combining SARATHI with FlashAttention-2 or RingAttention changes the crossover point. This experiment would establish the applicability boundary of the technique.

Practical Applications and Downstream Use Cases

Cost-efficient batch inference for LLM API providers. For companies serving LLM inference at scale (e.g., OpenAI, Anthropic, Together AI, Fireworks), GPU cost is the dominant operational expense. SARATHI's 1.33× end-to-end throughput improvement on LLaMA-13B/A6000 and 1.25× on LLaMA-33B/A100 (Table 4) translates directly to a ~25–33% reduction in GPU-hours per query — meaning the same hardware can serve 25–33% more requests, or the same workload can run on 20–25% fewer GPUs. For a provider running thousands of GPUs, this represents millions of dollars in annual savings. The technique requires no model retraining, no hardware changes, and no accuracy tradeoff (since chunked-prefills is mathematically equivalent to full prefill). The integration surface is the batching layer of the inference engine, making it feasible to deploy without rearchitecting the serving stack. The primary risk for providers is the latency impact (unmeasured in the paper) and the need to tune chunk size per model-hardware-workload combination. For offline batch workloads (evaluation, embedding extraction, synthetic data generation) where latency is not a constraint, SARATHI can be adopted immediately at low risk.

Enabling pipeline parallelism for cross-node LLM deployment on commodity interconnects. Organizations that lack NVLink or high-bandwidth InfiniBand between nodes (e.g., academic labs, startups using cloud GPU instances without tight node grouping, edge deployments) cannot effectively use tensor parallelism across nodes due to all-reduce communication overhead. Pipeline parallelism is the only option, but the paper shows it is counterproductive without uniform micro-batch composition (Figure 12b: TP+PP with Orca is 1.28× slower than TP-only). SARATHI's 1.48× speedup of pipeline-parallel deployment over TP-only (Figure 12b) makes cross-node LLM serving viable on hardware that previously could not serve large models efficiently. Concretely: a research lab with access to 8 cloud GPU instances (each with 8 GPUs and standard Ethernet between instances) could deploy a large model across the 8 instances using SARATHI-enabled pipeline parallelism and achieve throughput exceeding what they would get by running 8 independent tensor-parallel replicas — effectively converting cheap inter-node bandwidth into serving capacity. This broadens the hardware configurations that can serve LLMs economically.

On-device or edge inference for small models with constrained batch sizes. The paper's largest decode speedups occur at small batch sizes (10× at batch size 2, Figure 8) — precisely the regime where memory-constrained edge and on-device deployments operate. A small model (e.g., LLaMA-7B or a distilled variant) running on a consumer GPU or even a high-end mobile SoC with limited memory might support a maximum batch size of only 2–4 requests. At these batch sizes, the decode phase is severely memory-bound (the paper shows a 200× per-token cost ratio between decode and prefill at batch size 1, Figure 3), and SARATHI's decode-maximal batching provides the largest relative gain. For an on-device assistant that processes one user query at a time but generates long responses (low P:D ratio), chunking the prompt and piggybacking decodes with each chunk could substantially accelerate generation. This is speculative — the paper evaluates only on server-class GPUs — but the arithmetic intensity analysis (Figure 4b) is architectural, not model-specific, and the technique should transfer to smaller GPUs where the memory-bandwidth bottleneck is even more severe relative to compute.

When to Prefer This Method

The paper positions SARATHI against two concrete alternatives — request-level scheduling (FasterTransformer-style, where prefill and decode are processed in separate batch types) and iteration-level scheduling (Orca-style, where requests dynamically enter and exit batches but batch composition is unconstrained). The choice between these is not equally balanced; SARATHI is presented as a strict improvement over both under most workload conditions, with the tradeoffs being about how much improvement rather than whether the method is preferable. The paper does identify specific workload characteristics where the benefit is maximized or minimized:

• Prefer SARATHI when the P:D ratio is moderate (roughly 10–100 for the tested configurations) and the workload has a mix of prefill and decode work that allows sustained hybrid batching. At these ratios, SARATHI achieves its peak 1.23×–1.33× end-to-end gain (Figure 9). Most conversational LLM applications (chatbots, code assistants, writing tools) operate in this regime.

• Prefer SARATHI, potentially with smaller chunk sizes, when the workload is decode-dominated (low P:D ratio). Decodes constitute the majority of runtime, so even a large prefill overhead from aggressive chunking can be net-beneficial (Figure 13c: chunk size 128 achieves 1.16× end-to-end gain despite 2× prefill slowdown). The limiting factor is whether there are enough prefill tokens to generate sufficient chunks — at very low P:D (<5), SARATHI may revert to frequent decode-only batches and the gain diminishes.

• Prefer SARATHI with pipeline parallelism when deploying across nodes without high-bandwidth interconnects. SARATHI's uniform-batch property makes pipeline parallelism viable (1.48× over TP-only, Figure 12b), whereas Orca-style scheduling makes PP counterproductive (1.28× slower than TP-only).

• Consider the baseline (or SARATHI with very large chunk sizes approaching full-prefill) when the workload is heavily prefill-dominated (P:D > 200). Decodes are a small fraction of total time, so the decode efficiency gain provides negligible end-to-end benefit. In the limit of pure prefill workloads (e.g., embedding extraction, classification), there are no decodes to piggyback and SARATHI's mechanisms provide no benefit — the system should use standard large-batch prefill processing.

• SARATHI provides no benefit — and may be slightly detrimental — when chunk sizes are too small (below ~128 tokens on the tested hardware). Figure 13c shows that chunk size 64 merely matches baseline throughput, and the trend suggests smaller chunks would underperform. The prefill overhead from low arithmetic intensity and repeated KV cache reads overwhelms the decode gain.

• For latency-sensitive interactive applications, the choice is unresolved by the paper. SARATHI may increase time-to-first-token for long prompts due to serialized prefill chunks, even as it improves aggregate throughput. The paper provides no latency measurements, so practitioners must evaluate this tradeoff on their specific workload before adopting SARATHI for latency-critical deployments.