PagedAttention and RadixAttention: Let's Talk About KV Cache
In our previous piece on AITalk, we opened with an uncomfortable number: Llama-3.1-70B, in BF16 precision, accumulates roughly 0.31 megabytes of cache for every processed token, which means that a context of 128,000 tokens already costs 40 gigabytes of GPU memory, before loading even a single concurrent request. We covered three responses to this problem—TurboQuant, OSCAR, and EpiCache—three different ways to make that data smaller by acting on the number of bits per value or on which portions of a conversation are worth holding in memory.
However, compressing the data solves only half of the problem. It is like managing to pack archive folders into thinner boxes without changing how the archive itself is organized: if shelves remain allocated in bulk to every file regardless of how voluminous it actually is, and if every new file identical to a previous one is recopied from scratch instead of retrieved, the efficiency gained on the weight of individual folders is lost along the way regardless. This article covers the two techniques that addressed precisely this second problem: not how much a token weighs in cache, but how it is allocated and how it is reused. They are called PagedAttention and RadixAttention, and they are not alternatives to compression: they operate at a different layer, and in mature production systems, they coexist alongside it.
Two Independent Problems, Not Just One
Even with a cache that is already compressed, an inference engine runs into two inefficiencies that have nothing to do with each other. The first concerns memory allocation. The traditional method, adopted by early serving systems, reserved a contiguous block of GPU memory for each incoming request, sized for the maximum context length the model could theoretically reach. The problem is that the system has no way of knowing in advance how long the actual response will be, so the safety margin almost always ended up being oversized. This leads to two distinct forms of waste. There is internal fragmentation, when a request reserves space for thousands of future tokens but generates only a few dozen, leaving most of the allocated memory unused. And there is external fragmentation, when requests of different lengths finish at different times, leaving scattered holes in GPU memory: the sum of free space might be plentiful, but no single fragment is large and contiguous enough to host a new substantial request. The practical result, measured by the researchers who first tackled the issue, was that systems at the time wasted between 60 and 80 percent of allocated memory—a figure worth keeping in mind when evaluating the magnitude of subsequent gains.
The second problem is conceptually distant from the first and concerns computation, not memory. In real workloads, requests are rarely independent of one another. Thousands of users querying the same assistant share the same system prompt, a multi-turn conversation re-submits the entire previous history at every exchange, and an agent reasoning in a loop continuously appends new steps to a context that largely remains identical to the previous turn. In all these cases, the inference engine finds itself recalculating from scratch, during the prefill phase, the exact same key and value tensors that it had already produced moments earlier for another request, or for the same user on a previous turn. It is purely redundant work, and in scenarios involving prolonged chats or RAG systems, it can represent the heaviest share of the response time perceived by the user.
These two inefficiencies arose from different needs and received different solutions. PagedAttention addresses the first; RadixAttention addresses the second.
PagedAttention: Memory Like an Operating System
The underlying idea of PagedAttention, introduced by the group that created vLLM, borrows almost directly a concept decades old: paged virtual memory in operating systems. Anyone who has ever looked under the hood of a computer knows that programs do not receive a contiguous physical block of RAM, but an illusion of contiguity built on top of scattered pages managed by a translation table. PagedAttention applies the exact same logic to the attention cache.
The mechanism unfolds in four steps. First, the cache for each sequence is divided into fixed-size logical blocks, typically sixteen or thirty-two tokens each, rather than being treated as a single monolithic container. Second, the system maintains a page table, a map translating each logical block into its real physical location scattered across GPU memory: during attention calculation, the engine consults this table to gather the required blocks, and to the model, the sequence appears continuous even if physically it is not at all. The third step is growth on demand: memory is no longer reserved in bulk at the start, but allocated one block at a time as generation proceeds, so that a sixty-token response occupies only the space of sixty tokens, not that reserved for a maximum context that might never be reached. The fourth element, perhaps the most elegant, is block sharing with copy-on-write: if multiple requests start with the same prompt, as happens daily with a system prompt shared by thousands of users, the corresponding physical blocks are referenced in common rather than duplicated, and only at the precise moment a request diverges from the others is the affected block actually copied.
The result of this architecture is that fragmentation drops virtually to zero, with waste margins in published benchmarks falling below 4 percent compared to 60–80 percent in previous systems, allowing a much higher number of concurrent requests to be served on the same hardware. It is interesting to note that PagedAttention does not alter the attention algorithm in any way, nor does it modify model outputs: its innovation is purely architectural, concerning where and how data is physically placed, not what the model computes.
RadixAttention: A Tree That Does Not Forget
If PagedAttention solves where, RadixAttention solves what. The idea, introduced by the SGLang team, stems from an observation as simple as it was overlooked: in traditional systems, once a request completed, its cache was simply discarded, as if every conversation were born and died without leaving any useful trace for subsequent ones. RadixAttention turns this logic on its head by transforming the cache into a persistent and searchable structure—a radix tree, which is a compressed trie in which each unique token prefix is stored only once, and different requests sharing the same prefix traverse the same branch of the tree, branching off only at the exact point where their tokens begin to differ.
Imagine three users starting a conversation with the same system message, each followed by a different question. Instead of storing three nearly identical copies of the same prefix, the tree maintains it once and creates three separate leaves only for the final part, which is genuinely specific to each question. When a new request arrives, the engine traverses the tree token by token looking for the longest matching prefix already present, immediately retrieves the corresponding key and value tensors without recalculating them, and finally computes only the unseen suffix, inserting the new path into the tree so it can be reused in the future. An aspect often understated is that the structure cannot grow infinitely: when GPU memory saturates, RadixAttention applies an eviction policy based on least recently used (LRU) that removes the least recently used leaves first, while protecting the shared internal nodes upon which multiple requests depend, preserving the very prefixes that make the entire mechanism profitable.
The primary benefit is not about memory size per se, but Time to First Token—how much time passes before the user sees the first word of the response. If nineteen hundred out of two thousand tokens are already present in the tree, the model needs to process only the remaining hundred, directly impacting perceived latency. This is particularly evident in chatbots, RAG systems, and agentic workflows where contexts grow incrementally instead of being rewritten from scratch every time. For those familiar with niche video game narrative design, the mechanism recalls the structure of 80 Days, Inkle's narrative game where thousands of travel paths share entire stretches of common plot and branch only at points of actual choice: the game engine does not rewrite every possible branch from scratch, but builds it by grafting it onto a shared narrative trunk.
Two Layers, Not Two Rivals
A common mistake, fueled in part by how the two projects are often presented in opposition, is thinking of PagedAttention and RadixAttention as competing technologies between which one must choose. In reality, they answer different questions. PagedAttention decides where cache blocks physically live in GPU memory; RadixAttention decides whether those blocks already exist and can be reused. In a system integrating both techniques, the radix tree simply points to blocks that are themselves managed by the paged allocator: they are two stacked layers of the same infrastructure, not two alternative paths.
Returning to the example of three users with the same system prompt, without RadixAttention the engine would recalculate that prefix three times, and without PagedAttention each of those three requests would still reserve an oversized portion of memory. Combining both techniques, the prefix is computed only once, stored in compact paged blocks, and reused by every request that shares it.
It is worth noting that RadixAttention is not the only path toward automatic prefix reuse. vLLM, the project that introduced PagedAttention, now also supports automatic prefix caching, albeit with a different data structure: instead of a radix tree, it uses a chained hashing mechanism, in which each completed block receives a hash calculated from the parent block's hash, the tokens contained in the block itself, and any additional metadata. Because each hash depends on the previous one, the entire chain uniquely represents the prefix leading to that block; if another request produces the exact same sequence of tokens, it generates the exact same hash chain, immediately finding the pre-calculated blocks. In practice, for most applications, the difference between the two implementations remains more architectural than functional: both engines achieve the same outcome—skipping the prefill of previously seen prefixes—even if backed by different data structures.
Beyond the Two Techniques: Where Cache Management Is Heading
PagedAttention and RadixAttention tackled the two foundational issues, but contexts continue to expand, and with them, new requirements have emerged that neither technique, on its own, was originally designed to cover.
The first direction is hierarchical memory. Treating the GPU as the sole available cache tier becomes unsustainable when contexts exceed hundreds of thousands of tokens: projects like LMCache and Mooncake now organize cache across multiple tiers, with the hottest blocks in high-bandwidth GPU memory, recently used ones in host RAM, and older but potentially still useful blocks offloaded to distributed storage or NVMe drives, retrieved automatically when needed again. For those who have read Zafón, it is an architecture that closely mirrors the Cemetery of Forgotten Books: nothing is permanently destroyed, but less frequently consulted volumes are moved to increasingly remote shelves, ready to be retrieved when someone needs them again.
The second direction is cache-aware routing. In a multi-node distributed infrastructure, a standard load balancer distributing requests in a purely round-robin fashion risks sending two turns of the same conversation to two different GPUs, negating any prefix caching advantage even when the shared prefix exists. Systems like the llm-d router address this by routing requests to the replica that already holds the requested prefix cache, balancing not only load but also data locality.
The third direction, less discussed but critical for multi-tenant infrastructure operators, concerns security. Prefix caching introduces a potential side-channel: if a prefix is served noticeably faster because it is already present in cache, a malicious actor observing unusually low response times might deduce that another user previously sent the same prompt, even if the response content is never directly exposed. The most widespread countermeasure is cache salting, which includes a tenant-specific element in the hash used to identify blocks, ensuring that identical requests from different customers still generate different cache keys. This eliminates cross-tenant hit possibilities while preserving latency benefits within the same tenant.
Compression and Management: Two Sides of the Same Coin
Returning to where we started in the previous article, the complete picture of modern KV cache management emerges only by bringing both fronts together. Compression—recently embodied by TurboQuant, OSCAR, and EpiCache—reduces the size of the problem by addressing how many bits are needed to represent each token and which portions of conversational history are worth retaining. Management—led by PagedAttention and RadixAttention—optimizes its structure, determining where that data physically resides and whether it can be reused instead of recalculated. A state-of-the-art production system today integrates both approaches: it compresses what must remain in memory and efficiently organizes space and computation around that compressed memory.
For anyone designing or evaluating an inference infrastructure, this means the choice is no longer merely which model to serve, but how to serve it: mastering the mechanics of PagedAttention and RadixAttention has become as vital today as knowing the architecture of the model that cache is actively supporting.
Technical note: the data cited in this article originates from the original vLLM and SGLang papers and from the documentation of their respective open-source projects; it has not been independently reproduced by this editorial team, and as always in this field, laboratory numbers do not automatically guarantee the same performance in production scenarios with real-world workloads.