Optimizing LLM Inference: From PagedAttention to AI Infra

A recent Silicon Valley 101 episode, ‘Squeezing the Silicon Limit: How to Keep GPUs Busy?’ [https://www.youtube.com/watch?v=cB_X6AImPjQ], featured discussions on SGLang (Structured Generation Language), RadixArk, and Artificial Intelligence Infrastructure (AI Infra). These conversations compelled me to revisit a seemingly simple question: when Graphics Processing Units (GPUs) are already expensive and models are sufficiently large, why do inference systems still leave substantial compute power in a waiting state?

Intuitively, we often perceive large language model (LLM) inference as purely a compute problem: larger models require more GPUs; faster GPUs lead to quicker generation. However, in real-world online services, a GPU functions more like an expensive production line. The efficiency of this line depends not just on the speed of the machinery, but also on whether raw materials arrive on time, how work-in-progress (WIP) is stored, and how different orders are queued.

In LLM inference, the “work-in-progress” is the Key-Value Cache (KV cache). If GPU memory allocation is inefficient, the system might be unable to expand its batch size to accommodate more requests, even if the compute units have spare capacity. In such scenarios, the GPU isn’t truly unable to compute; it’s being “starved” by inefficient memory management.

This is precisely where vLLM’s significance lies. It didn’t alter the mathematical definition of the Transformer or invent new model architectures. Instead, it borrowed the decades-old concepts of virtual memory and paging from operating systems to redesign KV cache management. This seemingly low-level change, later combined with continuous batching, prefix caching, and cluster scheduling, gradually formed the foundational framework for modern LLM inference services.

What Modern LLM Serving Aims to Solve: A Summary #

If we conceptualize an online inference system as a factory, then several representative technologies address problems at different layers:

In the table below, P/D refers to the Prefill/Decode stages; TTFT (Time to First Token) indicates the latency until the first token is generated, and TPOT (Time per Output Token) represents the average generation time per output token.

These are not merely different names for the same technology, nor do they represent a simple sequential replacement. More precisely, they optimize scheduling, storage, reuse, and cluster resource configuration, respectively. Only when combined can the saved GPU memory and compute truly translate into higher effective goodput.

Understanding KV Cache Before Diving into PagedAttention #

Large models typically generate text in two stages.

The first stage is Prefill. The model processes the entire input prompt at once, computes the intermediate states for all input tokens, and generates output scores (logits) for sampling the first output token. Since many tokens can be processed in parallel, this stage involves substantial matrix operations and is typically compute-intensive.

The second stage is Decode. In standard autoregressive decoding, each round usually generates one token per active sequence. Every new token generated requires referencing the previous context. Recomputing all historical tokens at each step would be prohibitively expensive. Therefore, the system stores the Key and Value pairs already computed by the attention mechanism at each layer, allowing subsequent steps to read them directly. This stored state is the KV cache.

Imagine a chef preparing a dish with continuously added ingredients. The KV cache is like the chef’s operational log: it records which ingredients were used previously and up to what point the preparation has progressed. With each new ingredient, the chef only needs to read the log and continue, rather than re-preparing the entire dish from scratch.

However, this “log” is not small. The KV cache size for a single sequence can be roughly expressed as:

Where $2$ accounts for Key and Value, $L$ is the number of model layers, $H_{kv}$ is the number of KV heads, $D$ is the dimension of each head, $T$ is the number of context tokens, and $B_{dtype}$ is the byte size per numerical value. More concurrent requests and longer contexts require more KV cache to be stored.

The vLLM paper provides an illustrative example: OPT-13B (Open Pretrained Transformer, approximately 13 billion parameters) in FP16 (16-bit floating-point format) requires about 800 KiB (kibibyte) of KV cache per token. If the sequence length reaches 2048, a single request’s KV cache can occupy approximately 1.6 GiB (gibibyte, roughly 1.7 GB) of GPU memory [1], not including alignment, metadata, and other runtime overheads. When dozens of users simultaneously generate long texts, the KV cache quickly becomes a more dynamic and challenging GPU memory burden than the model weights themselves.

The true complexity here isn’t just “large,” but unknown and continuously growing length. A request might yield only 20 tokens, or it might generate 2000; the system usually cannot accurately predict the generation endpoint at the start of a request.

Why Contiguous Pre-allocation Wastes GPU Memory #

In early inference frameworks, a common practice was to pre-allocate a contiguous block of GPU memory based on the maximum possible length a request might reach. This approach was simple to implement because each request’s KV cache behaved like a fixed-size array, with relatively straightforward access paths.

The problem is akin to a hotel demanding that guests, upon check-in, immediately book and pay for 30 full days, based on a “maximum possible stay of 30 days.” Even if the guest checks out on the second day, no other guest can use those reserved rooms before that initial 30-day period expires.

Consider a highly simplified example. Suppose three requests all have a maximum generation length set to 2048 tokens, but they ultimately generate 32, 256, and 1024 tokens, respectively:

• System-reserved capacity: $3 \times 2048 = 6144$ token positions;
• Actually used capacity: $32 + 256 + 1024 = 1312$ token positions;
• On these outputs, the actual utilization rate is only about 21%.

This structural waste from contiguous pre-allocation was one of the design goals PagedAttention sought to address [1].

This example ignores input prompts, alignment methods, and runtime reclamation, serving merely to illustrate the structural issue: as long as output length is unpredictable, reserving for maximum length easily renders a large portion of space temporarily unusable by other requests throughout their lifecycle.

Specifically, traditional contiguous allocation leads to three types of waste:

• Reserved space: Capacity held during a request’s execution for future tokens, temporarily unavailable to other requests.
• Internal fragmentation: Allocated space that ultimately does not store valid tokens, caused by allocation granularity or maximum length estimation.
• External fragmentation: Free capacity scattered into non-contiguous regions, unable to satisfy new requests for contiguous memory.

External fragmentation is much like a parking lot with many scattered empty spaces, but a large bus requiring four contiguous spots still cannot park.

Figure 1: Comparison between traditional contiguous pre-allocation and paged KV cache management. Fixed-size blocks allow free GPU memory to be repurposed faster for other requests.

Experiments in the vLLM paper show that with the compared traditional methods, the actual proportion of KV cache GPU memory storing valid token states was only 20.4%–38.2% [1]. This doesn’t mean the rest of the GPU memory permanently “disappears,” but under dynamic online loads, large capacities become unavailable to new requests in time due to reservation and fragmentation.

The result is a counter-intuitive phenomenon: the GPU might still have compute capacity, yet it cannot expand its batch size because it lacks space for more requests’ KV caches. The production line can still operate, but warehouse management prevents new orders from entering.

PagedAttention: Decoupling Logical Context from Contiguous GPU Memory #

The core idea of PagedAttention can be summarized in one sentence: logical contiguity does not necessitate physical contiguity.

Operating systems have long employed a similar approach. Programs perceive a continuous virtual address space, yet this data can be physically dispersed in memory, with the OS mapping virtual pages to different physical pages via a page table.

vLLM divides the KV cache into fixed-size blocks and uses a block table to establish a mapping between logical blocks and physical blocks:

Logical KV Block 0  ──→  Physical Block 7
Logical KV Block 1  ──→  Physical Block 1
Logical KV Block 2  ──→  Physical Block 12

Figure 2: PagedAttention decouples the continuity of logical context from the continuity of physical GPU memory, requesting blocks on demand as new tokens arrive.

From the model’s perspective, these tokens still belong to the same contiguous context; from the GPU memory’s perspective, they don’t need to be adjacent. The PagedAttention kernel, when executing attention, locates the corresponding physical blocks via the block table and completes the computation.

If we extend the warehouse analogy, traditional approaches demand each order occupy a contiguous block of warehouse space. PagedAttention, conversely, places goods into uniformly sized standard containers, storing them wherever space is available, with a manifest recording each container’s location. The order remains logically intact, while physical storage gains significantly greater flexibility.

On-Demand Allocation: Only Request What’s Needed #

vLLM no longer pre-allocates an entire contiguous block of GPU memory for an unknown maximum output length. Instead, it progressively requests physical blocks during generation.

Assuming a block size of 16, if a request currently has a KV cache of 35 tokens, it only needs 3 blocks: the first two are full, and the third contains 3 tokens. At this point, only 13 positions in the last block are temporarily unused, rather than reserving the remaining space for a potential 2048 tokens.

The original paper used 16 tokens as the default block size in practice. Too small a block size increases mapping, scheduling, and kernel access overhead; too large a block size increases internal fragmentation in the last block, reducing sharing opportunities. Thus, the block size itself is a trade-off between hardware parallelism efficiency and memory utilization [1].

Copy-on-Write: No Need to Store Identical Parts Repeatedly #

Paging also naturally facilitates KV cache sharing.

Consider a scenario where the same 1000-token prompt needs to generate four candidate responses. A naive approach might reserve a separate copy of the prompt’s KV cache for each of the four generation paths. In reality, before the first output token is produced, the history of all four paths is identical. vLLM can have them reference the same set of physical blocks; new blocks are allocated for divergent tokens only when the answers begin to branch.

This copy-on-write mechanism first shares read-only content and only copies it when actual modifications occur. For parallel sampling and beam search, this can significantly reduce redundant storage [1].

Paging Is Not Without Cost #

PagedAttention is not a “free lunch” abstraction. The block table introduces indirect addressing, and the kernel must handle non-contiguous memory and varying sequence lengths. The original vLLM paper reported that, for the evaluated models and workloads, the complete vLLM system achieved 2–4x higher throughput compared to FasterTransformer and Orca while maintaining similar latency levels. The performance gains were more significant for long sequences, large models, and complex decoding scenarios [1]. The paper reported end-to-end results for the complete system relative to specific baselines, which cannot be solely attributed to a single kernel optimization.

This leads to a typical systems engineering conclusion: local speedups do not always equate to global speedups; a minor local overhead can sometimes yield significant global benefits. Focusing solely on the latency of individual kernels would miss the fundamental problem PagedAttention truly aims to solve.

Beyond Accommodation: Efficient Request Scheduling #

Higher GPU memory utilization merely creates the possibility of accommodating more requests. To keep the GPU truly busy, the scheduler must promptly dispatch requests into the compute queue.

When discussing system design, it’s essential to distinguish between GPU utilization and goodput: the former focuses on the degree to which resources are employed, while the latter emphasizes the number of requests completed by the system per unit of time, contingent on meeting Service-Level Objectives (SLOs) [4].

Traditional static batching is like a shuttle bus that must wait for all passengers to reach their destination before any can disembark or new ones can board. As long as a single long request in the same batch hasn’t finished, new requests remain queued, even if other slots become free.

Orca, in 2022, introduced iteration-level scheduling: the scheduler reorganizes the batch after each generation round, allowing completed requests to exit and new waiting requests to enter [2]. The concept commonly referred to as continuous batching today is an evolution of this fine-grained scheduling philosophy.

For instance, if a batch contains four requests, three of which complete after the current generation round, and the fourth needs to generate another 500 tokens. Static batching might leave those three positions idle; continuous batching, however, can immediately fill those three slots with new requests in the next round.

Figure 3: Continuous batching reorganizes the batch after each generation round, allowing completed requests to exit and waiting requests to enter promptly.

Therefore, it’s more accurate to say that PagedAttention and continuous batching solve complementary problems:

• Continuous batching determines “which requests should participate in the current computation round”;
• PagedAttention determines “how these continuously entering, exiting, and growing requests utilize GPU memory.”

Without flexible scheduling, saved GPU memory is difficult to translate into throughput in a timely manner; without efficient memory management, the scheduler might not find enough space even if it intends to add more requests. vLLM’s value lies in co-designing the attention compute kernel, block manager, and request scheduler into a complete inference serving engine.

From Efficient Storage to Cache Reusability: SGLang’s RadixAttention #

PagedAttention primarily solves “how to efficiently store KV cache.” However, in chat, Retrieval-Augmented Generation (RAG), and agent workflows, another question is becoming increasingly critical: can already computed KV cache be reused by subsequent requests?

Consider a retail customer service agent. Every request might begin with three identical segments:

1. A fixed system prompt;
2. The same return/exchange policy and product catalog;
3. The current user’s specific question.

The first two parts could comprise thousands of tokens and be repeatedly used by numerous users. If each request executes Prefill from scratch, it’s like reprinting and rereading the entire employee manual for every customer interaction. The model’s output remains unchanged, but the computation is needlessly duplicated.

SGLang’s RadixAttention organizes token sequences and KV cache into a radix tree, combined with Least Recently Used (LRU) eviction and cache-aware scheduling for cache management [3]. It not only reuses predefined fixed prompts but also automatically discovers multi-layered, dynamic common prefix structures.

For example, the following three requests exhibit prefixes that diverge layer by layer:

system prompt → Return Policy → Product A → Question 1
                            └→ Question 2
                 └→ Shipping Policy → Question 3

Figure 4: RadixAttention enables hierarchical reuse of common token prefixes, combining hit paths, reference states, and eviction policies to manage the KV cache.

A radix tree allows the identical system prompt to be stored only once, and content like “Return Policy” and “Product A” can continue to be shared by their respective branches. When the cache is insufficient, the system evicts branches that haven’t been used for a long time and are not referenced by active requests, based on policies like LRU.

The focus of PagedAttention versus RadixAttention can be understood as:

• PagedAttention focuses on the paged layout of the KV cache, on-demand allocation, and block sharing among generation branches.
• RadixAttention, built upon paged storage, uses a radix tree to store and index common token prefixes across calls and requests, combining eviction and cache-aware scheduling to improve reuse.

For single-turn short Q&A, the benefits of prefix caching might be limited. However, for multi-turn conversations, few-shot prompting, RAG, self-consistency sampling, and agent workflows, the longer the repeating prefixes and the more branching, the more significant the value of cache reuse [3]. In such cases, the scheduling problem also evolves from “first-come, first-served” to “how to order requests to balance latency fairness with cache hit rate.”

This implies that AI Infra is evolving from stateless model calls towards systematic management of inference states.

Scaling from Single-Device Engines to Clusters: The Rationale for Prefill/Decode Disaggregation #

As service scale continues to expand, GPU memory optimization within a single GPU is no longer sufficient. Although Prefill and Decode belong to the same inference process, they exhibit distinctly different resource characteristics [4]:

• Prefill processes the entire prompt at once, involving larger matrix operations, and is typically more compute-intensive.
• Decode, in standard autoregressive decoding, usually generates one token per active sequence per round, but it repeatedly reads model weights and the continuously growing KV cache, making it more susceptible to memory bandwidth and scheduling jitter.

Imagine two users simultaneously utilizing the service. User A uploads a long contract and requests a summary, triggering a large Prefill. User B is engaged in real-time chat, expecting stable output for each token. If both share the same set of GPUs, User A’s large Prefill might interrupt User B’s Decode process, causing an abrupt “pause before continuing.” Average throughput might still be acceptable, but User B’s perceived tail latency has deteriorated.

Works like DistServe thus propose Prefill–Decode disaggregation: placing the two stages on different GPUs or resource pools, optimizing TTFT and TPOT separately, and then transmitting the KV cache via high-speed interconnects [4].

In standard autoregressive Decode, TPOT better reflects the average decoding speed at the request level, while Inter-Token Latency (ITL) measures the actual interval and jitter between adjacent output tokens.

Figure 5: P/D disaggregation allows Prefill and Decode to be independently configured and scaled, but the latency isolation benefits must outweigh the KV cache transfer costs.

This is analogous to separating a restaurant’s prep area from its service counter: prep can prioritize batch efficiency, while serving focuses on a stable rhythm. When separated, these two types of work can employ different parallel strategies, scale independently, and reduce the direct interference of large Prefills on Decode.

However, P/D disaggregation is not a free lunch. After Prefill completes, the KV cache must be transferred to the Decode node, consuming bandwidth and adding complexity in synchronization, routing, and fault handling. When service scale is small, prompts are short, the network is slow, or the load is unstable, the transfer cost might negate the isolation benefits [4].

vLLM’s documentation explicitly states that its experimental Disaggregated Prefilling implementation does not increase overall throughput, but primarily serves to adjust TTFT and ITL independently, and to control tail ITL [5]. However, this does not negate the results of systems like DistServe improving goodput under SLO constraints through optimized resource allocation [4].

The Evolution of AI Infra: Insights from vLLM #

From Orca’s iteration-level scheduling to vLLM’s PagedAttention, then to SGLang’s RadixAttention and cluster-level P/D disaggregation, a remarkably clear evolutionary path emerges:

1. Dynamic Batching: Requests can dynamically enter and exit between token iterations.
2. Flexible GPU Memory: KV cache shifts from contiguous pre-allocation to paged, on-demand allocation.
3. State Reusability: Common prefixes are no longer recomputed, and caching begins to influence scheduling.
4. Stage Disaggregation: Prefill and Decode can be independently configured and scaled.
5. SLO-Driven System Optimization: The goal shifts from pursuing peak Floating-Point Operations per Second (FLOPS) to a comprehensive trade-off between TTFT, TPOT, throughput, goodput, and cost per token.

There’s a subtle yet significant shift often overlooked: the optimization target is continuously moving upwards.

Initially, the focus was on making a single operator faster. Then, it shifted to whether a single GPU could accommodate larger batches. Later, the problems evolved to how cross-request caches could be reused, how different GPUs could divide labor, how networks could transmit KV cache, and whether the entire cluster could complete more effective requests within latency constraints.

This also explains why the same model and the same number of GPUs can exhibit vastly different concurrency capabilities, tail latencies, and cost structures across different inference serving systems. Owning GPUs doesn’t equate to efficient GPU utilization; a runnable model doesn’t guarantee stable, cost-effective service for real users.

Beyond a Single Metric: The Nuances of GPU Utilization in Engineering Practice #

“How to keep GPUs busy” can easily be simplified to chasing higher GPU utilization. However, this concept itself encompasses multiple measurement criteria: GPU busy time indicates the proportion of time the device spends executing tasks; Streaming Multiprocessor Activity (often denoted as SM Active) represents the proportion of time within a sampling interval that at least one warp is active, but even warps waiting for memory might be counted as active [6]; Model FLOPs Utilization (MFU) measures the ratio of actual model computation to the hardware’s theoretical peak [7]. MFU is typically more relevant for training or controlled benchmarks; in online inference scenarios, it’s also crucial to clarify the model FLOPs estimation method and specific workload definitions. Any single metric can be misleading.

For example, creating very large batches often increases throughput and compute utilization but can also make new requests wait longer. Retaining all prefix caches might increase hit rates but could also hog KV cache space needed by active requests. Forcibly implementing P/D disaggregation might improve Decode tail latency but could make network transfer the new bottleneck.

Therefore, a production-grade inference system needs to observe at least the following concurrently:

• TTFT (Time to First Token): When the user sees the first token.
• TPOT (Time per Output Token): The average time taken by a request to generate subsequent tokens during the decoding phase.
• ITL (Inter-Token Latency): The actual time interval between adjacent output tokens, whose tail latency distribution can indicate stuttering and jitter.
• Throughput: The total number of tokens or requests processed per unit of time.
• Goodput: The number of requests a system can complete per unit of time while meeting Service-Level Objectives (SLOs) such as TTFT, TPOT, or tail ITL [4].
• Prefix Cache Hit Rate: The ratio of tokens hit in the prefix cache to the total number of tokens queried. A higher hit rate generally means more Prefill computations can be avoided [8].
• Cost per token: Whether throughput improvements genuinely translate into reduced resource costs.

Truly mature AI Infra isn’t about stacking the most technical buzzwords or pushing a single monitoring metric to 100%; it’s about selecting the right combination based on request length, concurrency patterns, cache hit rates, network topology, and business SLOs.

Conclusion: Cutting-Edge System Innovation Often Springs from Recombining Classical Ideas #

In my view, the most insightful aspect of PagedAttention isn’t merely how much it improved GPU memory utilization, but how it showcased a recurring pattern of innovation in computer science: ideas that truly transform cutting-edge systems don’t always arise from entirely new mathematical formulas, but can also stem from a fresh reinterpretation of classical abstractions.

Virtual memory, paging, copy-on-write, caching, scheduling, and resource isolation are not new concepts. Yet, when recontextualized within LLM inference, they form the bedrock of modern AI Infra.

“Squeezing the Silicon Limit” isn’t about keeping every kernel perpetually saturated, nor is it about pushing a single GPU utilization metric to 100%. Precisely, it means aligning compute, GPU memory, bandwidth, and request scheduling to accomplish more effective work with fewer resources under real-world latency constraints.

The next phase of competition won’t just be about who can train larger models; it will also be about who can transform every model computation into a more reliable, cost-effective, and scalable service.

References #

[1] Kwon, W. et al. Efficient Memory Management for Large Language Model Serving with PagedAttention, Symposium on Operating Systems Principles (SOSP 2023).

[2] Yu, G.-I. et al. Orca: A Distributed Serving System for Transformer-Based Generative Models, USENIX Symposium on Operating Systems Design and Implementation (OSDI 2022).

[3] Zheng, L. et al. SGLang: Efficient Execution of Structured Language Model Programs, Conference on Neural Information Processing Systems (NeurIPS 2024).

[4] Zhong, Y. et al. DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving, USENIX Symposium on Operating Systems Design and Implementation (OSDI 2024).

[5] vLLM Documentation. Disaggregated Prefilling (experimental), v0.26.0.

[6] NVIDIA Data Center GPU Manager (DCGM) Documentation. Profiling Metrics.

[7] NVIDIA NeMo Documentation. Performance Summary.

[8] vLLM Documentation. Metrics: Prefix Cache Metrics, v0.11.0.

Further Reading #

• Silicon Valley 101: ‘Squeezing the Silicon Limit: How to Keep GPUs Busy? | A Deep Dive into AI Infra Technology and the Hundred-Billion-Dollar Market with SGLang and RadixArk’