5 KV Cache Management
Purpose
Agent stack focus for this chapter.
Why can an agent that is generating nothing still exhaust the memory of the machine serving it?
An agent spends much of its life waiting. While a test suite runs or a remote service responds, the model generates nothing, yet the attention state computed from the request’s prefix can stay resident in accelerator memory, holding capacity that another request could put to work. That state is large, it grows with every token the trajectory carries, and its size is fixed by the model’s geometry rather than by any choice the agent makes. A serving engine that reserves room for the longest request it might see strands much of its memory, and one that copies a shared prefix into every branch pays for the same state many times over. At each pause the engine must choose among keeping the state resident, moving it to slower memory, and dropping it to rebuild from the tokens when the agent resumes. Each option trades memory against the delay before the next output token, and the right one depends on how long the wait will last. Capacity is therefore set less by how many contexts fit at once than by how long each one stays, because a context that holds memory through a long tool wait serves no turns while it keeps its place. Managing retained attention state turns the state an agent carries into a priced claim on the machine serving it, sized against the turn rate the service must sustain.
Learning Objectives
- Calculate retained attention-state memory and resident fit from model geometry, token count, and storage precision
- Calculate the memory that block allocation and prefix sharing recover from full-cap reservation and duplicated prefixes
- Distinguish compatible, available prefix reuse from the applicability of the underlying information
- Calculate the token-weighted prefix hit rate of a radix prefix cache under leaf-first eviction
- Select a chunked-prefill token budget that bounds the gap between output tokens for ongoing requests
- Evaluate keep, move, and recompute policies for paused state against memory pressure, resume latency, and lossy approximation risk
- Analyze how residence time converts a memory-fit bound into a sustainable turn rate
5.1 Attention State as a Serving Resource
The connection-pool repair agent (Four lighthouse workloads) has reached a candidate revision, r18. Its targeted reproducer passes, prompting the harness to submit a fully serialized request of 32,768 tokens and launch an integration test suite that runs for 45 seconds. That length, a power of two that keeps the block and pool arithmetic round, is shorter than the staged request of the context-engineering examples, and every per-request footprint and transfer time below scales linearly with it. If the serving engine holds the request’s attention state in accelerator memory throughout that entire wait, the device does no work for that workflow. The model generates zero tokens during the test suite, yet its retained state pins memory that another concurrent request could put to work. This is the tool-wait problem named in the turn lifecycle of The six phases of a turn. Preserving that state is a deliberate systems policy, and running an agentic service requires pricing that policy against its alternatives.
State becomes a physical resource claim inside the serving system.
Earlier abstractions stop short of that physical commitment. Context Engineering established how the harness selects and refreshes prompt context for each call, and its prefix-layout calculation priced a cached prefix as a discounted line on the bill. Neither abstraction captures the physical footprint of the underlying computation: how many gigabytes of memory that retained attention state consumes, how many concurrent trajectories an accelerator can hold at once, or what the serving engine should do with that state when an agent pauses to await tool execution. Those mechanical questions dictate whether an inference node that comfortably supports a single repair workflow can scale to sustain dozens.
↩︎ Pricing a reused prompt prefix at a discounted cached-input rate is established in Preserving an exact prefix.
Managing retained attention state is not solely an internal serving problem; it spans an operational boundary between two parties. The application caller controls its submitted context, tool execution timing, and any cache-management hints the serving API exposes. The serving operator controls physical device allocation, memory placement, compute scheduling, and retention policies. When the two belong to separate organizations, as with hosted commercial model APIs, the caller cannot manage physical accelerator memory directly. Instead, the application influences retention only through the interfaces and pricing tiers the service exposes. Distinguishing where these responsibilities divide clarifies which performance levers belong to the agent harness and which belong to the serving engine, the inference software that executes model calls and manages accelerator memory. The word “runtime” keeps its earlier meaning here, the agent runtime that runs the loop around the model.
The chapter follows the r18 request’s attention state through its life in the serving engine, and each stage raises the question the next one answers. Sizing the state from model geometry shows how few 32,768-token contexts fit in the memory left after the weights (section 5.2). Allocating that state naively strands much of the pool (section 5.3), which fixed-size blocks recover while letting forked candidates share a prefix (section 5.4). Sharing within one request invites reuse across turns, which needs an index over retained prefixes and a rule for what to evict (section 5.5). Whatever the cache misses must be prefilled without stalling other requests’ generation (section 5.6). The test wait itself forces a choice among keeping, moving, and dropping the paused state (section 5.7). Finally, residence time turns a count of resident contexts into a sustainable turn rate (section 5.8).
5.2 The Footprint of Retained Attention State
The r18 request’s 32,768 tokens do not reach the accelerator as raw text. During causal self-attention in a Transformer decoder, each newly generated token attends to earlier tokens through their key and value projections (Vaswani et al. 2017). Recomputing these projections at every decode step would repeat the linear transformations over the entire historical prefix, creating an unsustainable quadratic compute bottleneck. Serving engines avoid this recomputation by retaining the computed key and value tensors in accelerator memory across decode cycles.1 While autoregressive decoding relies on retained attention state, sustaining long-horizon agent execution requires managing its physical capacity, allocation overhead, and multi-tenant residency.
1 Memory-Limited Inference: Caching keys and values trades quadratic recomputation for persistent memory capacity, and that memory quickly becomes the primary serving bottleneck. An analytical study of large-model serving revealed that sharing a single key-value head across all query heads allowed an identical deployment to serve contexts more than an order of magnitude longer, precisely because retained attention state, rather than compute throughput, bounded context length and batch concurrency (Pope et al. 2023).
Pope, Reiner, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. 2023. “Efficiently Scaling Transformer Inference.” Proceedings of Machine Learning and Systems (MLSys) 5: 606–24.
↩︎ Retained attention state in autoregressive decoding is established in Token-by-token generation.
Definition 5.1: KV cache
KV cache is the per-sequence store of attention keys and values that the model has computed for already processed tokens, retained so that later tokens can attend to them without recomputing their projections.
- Significance: Its payload scales linearly with retained tokens; consequently, sequence context length, rather than static model parameter count, determines how many concurrent requests can share the memory pool remaining after loading model weights.
- Distinction: It represents intermediate projected state rather than a raw copy or semantic compression of input text. Reconstructing it requires executing the exact token sequence through identical model weights and layer configurations.
- Common pitfall: Budgeting only for input prompts. Every newly decoded output token appends key and value states at every layer, so a request reaches its maximum memory footprint at completion rather than during initial prefill.
For a decoder employing causal self-attention with uniform layer geometry, every retained token contributes both a key vector and a value vector across all layers. Let \(\LayerCount\) represent the number of layers, \(\KvHeadCount\) the number of key-value heads per layer, \(\AttentionHeadDimension\) the dimension of each head, and \(\ElementStorageSize\) the storage size in bytes per element. Accounting for both vectors yields the memory footprint per token:
\[\KvCacheBytesPerToken = 2 \cdot \LayerCount \cdot \KvHeadCount \cdot \AttentionHeadDimension \cdot \ElementStorageSize \tag{1}\]
A sequence retaining attention state across \(\SequenceLength\) tokens requires an aggregate cache payload of \(\KvCacheMemory = \SequenceLength \cdot \KvCacheBytesPerToken\). Here \(\SequenceLength\) counts only the tokens whose keys and values have already been evaluated; each newly sampled token increments \(\SequenceLength\) once the model completes its forward pass.
The key-value head count \(\KvHeadCount\) in equation 1 represents the number of stored attention heads, which often falls below the query head count. Multi-query attention pushed this reduction to its structural extreme by sharing a single key-value head across all query heads2 (Shazeer 2019). Grouped-query attention strikes an intermediate balance: several query heads share one key-value head, dividing the stored key-value head count by the group size relative to a standard multi-head design (Ainslie et al. 2023), a scaling quantified across attention designs in Attention State by Attention Design. Because this head grouping is established during pretraining, a serving allocator cannot dynamically drop heads from an existing checkpoint without changing the model’s computations.
2 Multi-Query Attention: Motivated primarily by memory bandwidth rather than storage capacity (incremental decoding reloads stored key and value tensors at each generation step), sharing key-value tensors across query heads drastically reduces memory bus traffic alongside physical storage with minimal quality loss (Shazeer 2019). Grouped-query attention subsequently recovered nearly all multi-head attention quality while preserving the bulk of these memory savings (Ainslie et al. 2023).
Shazeer, Noam. 2019. “Fast Transformer Decoding: One Write-Head Is All You Need.” arXiv Preprint arXiv:1911.02150.
Ainslie, Joshua, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebr’on, and Sumit Sanghai. 2023. “GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.” Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (EMNLP).
While equation 1 accounts for the raw tensor payload under dense causal attention, physical memory consumption in production serving engines exceeds this theoretical bound. Allocation block granularities, memory alignment, page table metadata, and quantization scales all add runtime overhead. Non-uniform architectures, such as sliding-window attention or compressed latent representations, require their own capacity models.
The worked estimate uses a representative configuration: the Llama 3 70B model geometry, with 70.6B parameters, and a DGX H100 node containing 8 accelerators. While specific hardware platforms and checkpoint dimensions vary, the underlying capacity arithmetic remains unchanged. Unlike the single-device, 8-bit illustration in Estimating per-call hardware work, both weights and KV cache tensors use 16-bit storage here, with the model weights sharded across the node’s accelerators by tensor parallelism. The aggregate high-bandwidth memory remaining after provisioning model weights and a runtime reserve constitutes the KV pool. The number of active sequences whose KV payloads can reside simultaneously within this pool defines the resident-fit bound. This aggregate derivation assumes perfectly balanced shards without redundant weight replication; in production, memory limits must be satisfied on every individual accelerator device. None of the r18 context’s internal structure survives into this accounting. System prompt, tool schemas, workspace state, turn history, and latest observation all become key and value tensors at every layer, so the whole 32,768-token context costs 10.7 GB whatever its zones contain (figure 1). The figure’s zones follow the change-rate order of context staging. Its shared invariant prefix is the root of instructions and tool schemas together with the slow-changing workspace description, its growing trajectory state is the rest of the trunk, and its active turn is the leaf.
Napkin Math 5.1: Sizing the attention state of an agent trajectory
Problem: Consider a server node of 8 accelerators, each with 80 GB (vendor-rated in binary gigabytes, about 85.9 GB in the decimal units used throughout this chapter), for 687.2 GB of aggregate accelerator memory. Model weights occupy 141.2 GB, and the runtime reserves 20 GB for dynamic activations and scratch buffers. Under full causal attention without prefix sharing, how many independent sequences can simultaneously reside in the remaining memory across different context lengths?
Table 1: Payload and resident fit: Each sequence stores its own full-attention state; the calculation excludes allocator overhead and additional headroom.
Math: Evaluating equation 1 for this architecture yields \(\KvCacheBytesPerToken = 2 \times 80 \times 8 \times 128 \times 2 = 327,680\;\text{bytes/token}\). For an agent trajectory retaining 32,768 tokens, the footprint becomes \(\KvCacheMemory = 32,768 \times 327,680\;\text{bytes} \approx 10.7\;\text{GB}\).
Subtracting model parameters and runtime buffers isolates the usable capacity: \(687.2 - 141.2 - 20 \approx 526.0\;\text{GB}\). Dividing this available pool by the footprint per sequence and taking the floor determines the resident-fit bound. Using exact floating-point values prior to display rounding yields \(\left\lfloor 525.994767360 / 10.737418240 \right\rfloor = 48\). Table 1 evaluates this bound across three operational context regimes.
| Retained tokens | KV payload per sequence | Sequences that fit |
|---|---|---|
| 8,192 | 2.7 GB | 195 |
| 32,768 | 10.7 GB | 48 |
| 131,072 | 42.9 GB | 12 |
Systems insight: Resident capacity scales inversely with retained context length. Because model weights occupy a fixed memory slice regardless of context, expanding sequence length directly cannibalizes the cache pool. Each fourfold increase in sequence length (from 8,192 to 32,768, and onward to 131,072 tokens) reduces the resident sequence capacity by roughly 75 percent. Retained context length is the primary control lever governing serving capacity, and the agent runtime directly governs it. Maintaining an active working set rather than accumulating unbounded historical observations (principle 4) keeps requests operating in the high-density rows of table 1. These figures are raw tensor payloads; physical memory allocators, page fragmentation, and safety headroom further reduce actual capacity, while translating instantaneous resident capacity into sustainable request throughput requires analyzing sequence residence times (section 5.8.2).
Because model weights incur a one-time memory cost amortized across all concurrent requests, every independent sequence adds its private attention state to the pool unless the serving engine caches and reuses common prefixes across turns. Within each sequence, model architecture and numerical precision set the per-token payload before memory allocation even begins. An architecture trained with fewer key-value heads or compressed latent representations3 reduces the state generated per token, while quantizing keys and values to 8-bit or 4-bit representations halves or quarters the raw element bytes \(\ElementStorageSize\) at the cost of dequantization scale metadata and potential numerical degradation that engineers must validate against target task benchmarks. Regardless of compression, every retained byte remains allocated physical memory tied to an active execution lifecycle, and how much the architecture moves that payload is easiest to see across published geometries: figure 2 evaluates equation 1, and its latent-attention counterpart, for six registered models: one with full multi-head attention, four with grouped-query attention, and one with multi-head latent attention.
3 Latent KV Compression: Multi-head latent attention compresses keys and values into a single low-rank latent vector per token and dynamically reconstructs per-head tensors during attention, exchanging additional projection arithmetic for a substantially smaller memory footprint (DeepSeek-AI et al. 2024). Although this technique modifies the calculation of \(\KvCacheBytesPerToken\) in equation 1, it preserves the same system dynamics: latent cache tensors must still be paged, allocated, retained across idle periods, and evicted under memory pressure.
DeepSeek-AI, Aixin Liu, Bei Feng, Bin Wang, Bingxuan Wang, et al. 2024. “DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model.” arXiv Preprint arXiv:2405.04434, ahead of print. https://doi.org/10.48550/arXiv.2405.04434.
The spread in figure 2 is fixed at pretraining; the serving engine can work within it but cannot change it. Full multi-head attention in the GPT-3 (175B) geometry retains 4,718.6 KB per token, 67× the 70.3 KB of the latent-attention DeepSeek-V3; even the grouped-query Llama-3.1-70B of the worked estimate retains 4.7× as much. At the 131,072 tokens of the long regime, that is 42.9 GB against 9.2 GB for one session. The choice of model therefore fixes the slope of every capacity line in this chapter, and the runtime’s levers (retained tokens, sharing, precision, and eviction) act only along that slope. Whatever the slope, each retained byte stays allocated for as long as its sequence holds the prefix, which is where the lifecycle decisions begin.
In the running repair agent scenario, deciding whether to keep attention state resident while waiting for an external test suite to run exemplifies this lifecycle tension. Holding the attention state in accelerator memory avoids restoration of the retained prefix when the tool returns observations, but keeping gigabytes of memory pinned for an idle agent deprives concurrent requests of accelerator resources. Before exploring eviction and caching policies, however, the serving engine must translate theoretical tensor footprints into physical memory allocations. Statically pre-allocating contiguous buffers for a sequence’s maximum potential context wastes the memory pool through severe internal fragmentation long before actual tensor payloads fill device capacity.
5.3 Memory Fragmentation
When the repair agent runs an integration test and receives a compiler traceback or test log, its next generation step needs KV cache space for both its accumulated history and the newly ingested output, yet neither the harness nor the serving engine knows in advance how many tokens the model will generate or how many tool turns will follow. While a static footprint calculation sizes the tokens processed so far, the memory allocator governs what happens as sequences grow: how much spare buffer to reserve at admission, whether an expanding sequence must be copied to a larger region in memory, and how quickly freed capacity returns to the shared pool.
5.3.1 Reservation and growth
Provisioning a contiguous memory buffer for the full configured token cap (\(\ContextWindow\)) the moment a request arrives guarantees that a growing sequence never stalls for reallocation or runs out of memory mid-generation, but it locks every unpopulated slot for the entire life of the request so no concurrent sequence can use that capacity. This upfront policy is static reservation: because the maximum buffer is secured at admission, the sequence expands in place within its pre-allocated envelope. The reservation covers only KV cache state; activation tensors and temporary runtime scratchpads draw from separate memory pools.
In the 526.0 GB KV pool modeled above, an admission cap of 32,768 tokens requires 10.74 GB for each reservation. Dividing the pool by this single-request footprint bounds concurrency to at most 48 resident reservations, assuming balanced tensor-parallel sharding across accelerators and no auxiliary overhead beyond the baseline runtime reserve. The count matches the 32,768-token row of table 1 because a full-cap reservation is exactly that context’s footprint, whether or not the tokens ever arrive.
Now consider the resulting capacity utilization for a mixed request population, mostly short turns with occasional long trajectories like r18, all admitted under the same cap. If those requests finish at a mean length of 2,048 tokens, each reservation is only 6.25 percent populated even upon completion, holding 2,048 valid token states out of 32,768 allocated slots. During earlier decoding steps, utilization is lower still. Empirical evaluations confirm that this structural waste dominates naive serving systems: when Kwon et al. (2023) profiled early systems, actual token state accounted for only 20.4 to 38.2 percent of allocated KV memory, with the remainder lost to reservation slack and fragmentation.
A second strategy grows a contiguous allocation incrementally as tokens arrive. When adjacent capacity is unavailable in the allocator’s address space, the memory manager cannot simply extend the buffer in place. Instead, it must allocate a larger buffer elsewhere, copy all existing key and value entries from the old buffer to the new buffer, and then release the original space. This approach incurs two severe penalties: the allocator must hold both buffers simultaneously during the transfer, causing transient memory spikes, and the synchronous copy consumes substantial memory bandwidth. Contiguity here refers to an unbroken span in the allocator’s virtual address space, which the accelerator already translates to physical memory in hardware. The restriction therefore comes from software, not from the memory hardware. Standard attention kernels locate a token’s keys and values by a fixed stride from the start of one buffer, so each sequence’s KV tensor must occupy a single span. Removing that requirement calls for an indirection the serving engine itself controls, because the decisions that matter belong to the engine: how many tokens a unit of allocation holds, how many sequences reference each unit, and when a shared unit must be copied before a write. The remedy is a software table the attention kernel reads directly (section 5.4).
5.3.2 Two kinds of unused capacity
A contiguous allocator can fail to admit a new sequence even when the memory pool holds more than enough free capacity in total, or it can run out of room because active sequences hold thousands of reserved slots they have not yet filled. Unused slots locked inside an active reservation constitute internal fragmentation; free capacity split across disconnected extents too small to satisfy a contiguous request constitutes external fragmentation. This classic distinction originates in early storage allocation research for multiprogrammed systems4 (Randell 1969). Table 2 separates them because each condition demands a distinct systems remedy: eliminating reservation slack cures the first, whereas changing the allocation granularity cures the second.
4 Internal and External Fragmentation: The analysis of storage allocation that named the two losses also measured their trade: rounding requests up to fewer standard sizes cost more storage in internal fragmentation than it recovered in external fragmentation (Randell 1969). Paged KV allocation makes the same trade on purpose, accepting at most one partial block per sequence in exchange for a pool in which any free block fits any request.
Randell, Brian. 1969. “A Note on Storage Fragmentation and Program Segmentation.” Communications of the ACM 12 (7): 365–69, 372. https://doi.org/10.1145/363156.363158.
| Condition | Where capacity is unavailable | Consequence |
|---|---|---|
| Internal fragmentation | Inside an allocation, beyond its initialized entries | Other requests cannot use the reserved slots |
| External fragmentation | In separate free extents of a variable-size allocation pool | A contiguous request can fail even when aggregate free capacity is sufficient |
Suppose an allocator has three free extents of 256 token slots each, separated by live allocations, when a new sequence arrives requesting 512 contiguous slots. Even though the allocator holds 768 free slots in aggregate (more than enough capacity to satisfy the request), the allocation fails because no single extent can hold 512 contiguous slots. The failure stems entirely from the contiguity requirement rather than an absolute shortage of memory.
In an agentic repair workload, this memory pressure becomes acute because a paused trajectory retains its allocation under naive retention policies while waiting for tool execution, even as concurrent requests demand memory to grow. A robust serving system therefore requires two complementary architectural mechanisms: first, a space-efficient allocation unit, which fixed-size blocks provide, and second, an explicit lifecycle and eviction policy, which section 5.7 develops.
5.4 Paged KV Allocation
When an integration-test log extends an agent’s repair context, the serving engine need not relocate the existing KV tensor to find a larger contiguous buffer. Instead, it allocates additional fixed-size physical blocks and appends their identifiers to the request’s block table. The attention kernel dereferences that table when reading earlier token positions. PagedAttention demonstrated this combination of dynamic block allocation and noncontiguous attention over KV storage (Kwon et al. 2023). Its lineage traces directly to paged virtual memory. The Manchester Atlas one-level store introduced paging in 1962 to decouple a program’s contiguous virtual address space from scattered physical page frames (Kilburn et al. 1962). The block table applies this same indirection to token positions, allowing sequences to grow dynamically without requiring contiguous physical allocations.
Definition 5.2: Paged KV block table
Paged KV block table is a per-sequence software mapping from logical token blocks to the physical KV blocks that store their initialized key and value entries.
- Significance: A sequence can grow by acquiring another block without relocating its existing blocks.
- Distinction: The table maps token positions for the attention kernel; it is not the accelerator’s hardware page table.
- Common pitfall: A mapped block has allocated capacity, but only its initialized token entries may be read as valid KV state.
5.4.1 Token-to-block mapping
Once physical blocks sit scattered across accelerator memory, the attention kernel can no longer locate a token’s keys and values by adding a fixed stride to a single base pointer; it must resolve each token position through the sequence’s block table. Consider an illustrative block size of four tokens, chosen to make the mapping concrete rather than to recommend a production configuration. A ten-token prefix occupies logical blocks 0, 1, and 2. Its block table contains [3, 7, 9]: token positions 0–3 reside in physical block 3, positions 4–7 in block 7, and positions 8–9 in the first two slots of block 9. Physical block IDs are pool indices managed by the allocator, not raw memory addresses or token sequence numbers.
For any token position, the attention kernel determines its logical block index via integer division by the block size, consults the block table to locate the physical block, and calculates the token’s offset within that block using the modulo remainder. For token position 9 with a four-token block size, the kernel calculates logical block \(\lfloor 9 / 4 \rfloor = 2\), looks up physical block 9, and determines offset \(9 \bmod 4 = 1\) (the second slot). Computing the final byte offset in device memory incorporates the model layer, KV head index, and tensor stride conventions. This software lookup preserves logical sequence ordering even when physical blocks are scattered across high-bandwidth memory among other requests’ blocks, as panel (a) of figure 3 traces for position 9.
Because every block in the allocator’s pool is interchangeable and of identical size, any free block satisfies an allocation request. Paging thereby eliminates external memory fragmentation at block granularity. The remaining memory overhead consists of block-table metadata, temporary scratchpad buffers, and unallocated slots in each sequence’s final block.
5.4.2 Block size and tail waste
Because sequence lengths rarely align with block boundaries, the final block of a sequence typically contains uninitialized slots. This internal fragmentation constitutes the tail waste \(\KvBlockTailWaste\). For a block holding \(\KvBlockSize\) tokens, tail waste is bounded by \(0 \leq \KvBlockTailWaste \leq \KvBlockSize-1\), with an expected value of \((\KvBlockSize-1)/2\) when sequence lengths yield uniformly distributed remainders modulo \(\KvBlockSize\). A sequence whose length is an exact multiple of \(\KvBlockSize\) incurs zero tail waste.
Block size trades allocation granularity against indexing overhead. Smaller blocks (for example, 16 tokens) reduce worst-case tail waste and permit fine-grained prefix sharing and copy-on-write duplication, though they inflate block-table metadata and increase indexing overhead for the attention kernel. Larger blocks (for example, 64 tokens) amortize bookkeeping costs and align more effectively with memory bus transactions and tensor core tile dimensions on modern accelerators, at the cost of greater tail waste and copy overhead during branch forks. Selecting an appropriate block size therefore requires balancing sequence length distributions, tree-search branching patterns, and hardware memory access characteristics.
Napkin Math 5.2: Converting block size into KV storage
Problem: Given the Llama 3 70B geometry and a 16-bit KV representation, what physical storage granularity and maximum tail slack result from two candidate block sizes?
Math: Each token requires 327680 bytes across all model layers and attention heads. Multiplying that unit footprint by 16 tokens yields 5.24 MB per block. Multiplying by 64 tokens yields 20.97 MB. These values are node-wide footprints summed across all model shards, not the local allocation on a single accelerator.
The maximum unused tail contains one fewer slot than a full block. A 16-token block can therefore leave at most 15 slots (4.92 MB) unused, while a 64-token block can leave at most 63 slots (20.64 MB) unused.
For a 32,768-token agent context, even the larger block’s worst-case tail waste represents only 0.2 percent of the sequence’s total memory footprint.
Systems insight: Because tail slack is bounded by at most one block per unshared sequence, its relative overhead diminishes as sequence length increases. At multi-thousand-token agent context lengths, tail waste ceases to be the governing constraint. Engineers should select block sizes primarily to optimize attention kernel throughput and sharing granularity, revisiting tail waste only when serving workloads dominated by short sequences.
The final-length snapshot estimate is about 16× the full-cap reservation count.
Translating these worst-case bounds into expected memory overhead requires evaluating the workload’s sequence length distribution. Consider final sequence lengths modeled as a capped exponential distribution with a mean of 2,048 tokens, bounded by the 32,768-token ceiling established for static reservation. Under this distribution, 16-token blocks leave 0.4 percent of allocated KV memory unused, whereas 64-token blocks leave 1.5 percent.
Dividing the same pool, which accommodated only 48 static worst-case reservations, by the expected paged footprint gives a planning estimate of approximately 780 final-length request snapshots, a 16× increase over full-cap reservation. This capacity multiplier represents the core payoff of paging: memory allocation expands incrementally as tokens are generated, rather than reserving buffer space for an upper bound that most requests never reach. This estimate describes a hypothetical population sampled at completion; the requests resident in a running service have a length distribution that also depends on growth and residence time. Actual admission must account for current unique blocks and the generation growth the controller promises. The gain is close to the ratio of the cap to the mean final length, 32,768 to 2,048, so it measures how far the population falls short of the cap. A request like r18 that actually grows to the cap gains no resident capacity from paging. What paging still buys it is growth without relocation, block-level sharing with forked candidates, and memory that is claimed only as tokens arrive rather than at admission.
5.4.3 Copy-on-write prefix sharing
When a repair agent samples parallel candidate patches from the same prompt and tool-execution prefix to verify them empirically (principle 3), giving each branch its own contiguous KV buffer duplicates gigabytes of identical prefix state across every candidate. The breadth allocation of Parallel sampling along the breadth axis already priced this difference: with the prompt stored once, peak KV demand grows as the shared prefix plus each candidate’s private tokens, whereas without sharing every candidate carries its own copy of the prompt. Paged allocation delivers the shared form by pointing every candidate’s block table to the same physical blocks across the common prefix whenever the model architecture and runtime configuration allow block sharing.
The difference is large at agent context scales. Under contiguous allocation, giving each of four candidate branches its own copy of an 8,192-token prefix requires writing 10.7 GB of KV state for the Llama 3 70B geometry, counting the four new copies and not the parent’s original. That is the footprint of one full 32,768-token context, since four copies of 8,192 tokens hold that many token positions. Under paged allocation, duplicating the block tables avoids copying any tensor payload whatsoever. The engine merely updates software metadata and increments reference counters; cloning a block table requires work proportional to the number of block entries rather than the roughly ten gigabytes of underlying KV data.
A shared sequence tail requires special handling when branches diverge. If the final block of a shared prefix is only partially filled, two concurrent candidates cannot independently append new tokens into its remaining empty slots without overwriting each other. In the ten-token example, both candidates initially share the block table [3, 7, 9]. Physical block 9 contains only two valid tokens (positions 8 and 9 in slots 0 and 1). Before candidate B writes token position 10, the engine allocates a fresh physical block 14, copies the two initialized entries from block 9 into block 14, and updates candidate B’s final block-table entry to point to block 14. Candidate B then writes token 10 into slot 2 of its private block 14. This copy-on-write5 operation leaves candidate A’s state unchanged, as panel (b) of figure 3 draws. Table 3 records the ownership transition, assuming these two candidates are the sole owners of the prefix.
5 Copy-on-Write: The TENEX time-sharing system of the early 1970s gave each page a status bit that let processes share large parts of an address space and obtain private copies of only the pages they changed (Bobrow et al. 1972). Forked candidates reuse the idea at block granularity, which is why a fan-out of sampled repairs costs private blocks in proportion to what each candidate writes, not to the prefix they share.
Bobrow, Daniel G., Jerry D. Burchfiel, Daniel L. Murphy, and Raymond S. Tomlinson. 1972. “TENEX, a Paged Time Sharing System for the PDP-10.” Communications of the ACM 15 (3): 135–43. https://doi.org/10.1145/361268.361271.
| State | Candidate A table | Candidate B table | Physical ownership |
|---|---|---|---|
| Before append | [3, 7, 9] |
[3, 7, 9] |
Blocks 3, 7, and 9 each have two owners |
| After B’s private-tail append | [3, 7, 9] |
[3, 7, 14] |
Blocks 3 and 7 retain two owners; 9 and 14 each have one |
Copy-on-write is necessary only when mutating a shared, partially filled block. When a candidate branches at an exact block boundary (for instance, after a twelve-token prefix using four-token blocks), token position 12 initiates a new logical block (\(\lfloor 12 / 4 \rfloor = 3\)). The generating candidate simply allocates an unshared block from the free pool and appends its ID to its block table, requiring no data copying. Similarly, if a partial tail block is already privately owned (reference count of 1), the candidate appends subsequent tokens directly into the remaining slots without allocation or copying. The engine selects the appropriate operation based on two state variables: the occupancy of the target block and its current reference count.
When an agent discards an unpromising candidate trajectory, the engine decrements the reference counts of its constituent physical blocks. A block returns to the free pool when its reference count reaches zero and all outstanding device operations (tracked via asynchronous completion events) have finished. A dormant prefix-cache entry (section 5.5) may also retain physical blocks even after an active request completes, preserving them across subsequent agent turns. Total physical memory consumption is therefore governed by the number of unique physical blocks resident on the accelerator, not the aggregate logical token count across all active candidates.
Checkpoint 5.1: Reasoning about KV allocation
The allocation policy must preserve each sequence’s state while managing capacity shared by many requests.
Paged allocation decouples logical sequence expansion from physical memory layout, eliminating external fragmentation while enabling zero-copy prefix sharing across concurrent trajectories. Sharing state across independent requests or across subsequent turns of an agent session requires a complementary mechanism, prefix caching, in which the serving engine identifies matching historical prefixes across disparate requests and manages cache retention under memory pressure.
5.5 Prefix Caching Across Turns
In the connection-pool repair scenario, the agent invocation that processes an integration-test result often begins with the identical system prompt, tool definitions, and historical observations present in the preceding turn. If the serving engine retained the corresponding key-value (KV) activations from that earlier call, it can attach those existing tensors directly to the new request, prefilling only the newly arrived tokens. On the bill, this saving appears as a discounted cached-input rate; in system implementation, it translates into a concrete serving architecture governed by an index, an explicit ownership contract, and an eviction policy.
Definition 5.3: Prefix cache
Prefix cache is the serving system’s index of retained KV state, keyed by exact token prefix and computation configuration, allowing subsequent requests sharing that initial sequence to attach existing state instead of recomputing it during prefill.
- Significance: It converts repeated prefill work into an index lookup across request boundaries. The computational savings grow with the length of the matched prefix and recur on every turn that preserves that prefix, making stable prompt layouts essential across long trajectories.
- Distinction: Block sharing reuses state among candidates that the engine forks from one request and therefore knows to be related; a prefix cache must find reusable state, by content, for requests that arrive independently over time, and it can offer only what memory pressure and eviction have left resident.
- Common pitfall: Assuming a cache hit guarantees semantic freshness. Matching cached tokens verifies identical historical inputs and execution settings, but it does not check whether the real-world state described by those tokens has changed.
5.5.1 Prefix compatibility
Attaching cached KV blocks from an earlier turn corrupts generation if a single upstream token, adapter weight, or positional encoding differs between the two calls, because under causal full attention every token’s keys and values depend on the exact token prefix and execution configuration that produced them (principle 5). Matching token identifiers from the very first position of the sequence is merely the first prerequisite. The cached KV tensors remain mathematically valid only when generated under identical execution parameters: the same base model weights, active low-rank adaptation (LoRA) adapters (lightweight fine-tuned weight adjustments), positional encodings, and attention masks. For multimodal requests containing images, audio, or structured embeddings, matching the synthetic placeholder tokens in the text prompt is insufficient; the underlying tensor inputs and projection parameters must match exactly. A production serving engine must encode these operational dependencies directly into its cache keys or validate them before binding cached blocks to a request.
Even when a cached prefix is mathematically compatible, the engine still has to verify that its blocks are physically resident and permitted to the caller. Computationally compatible tensors may have already been evicted from accelerator high-bandwidth memory (HBM), or they may reside in host memory or on solid-state drives, requiring an explicit page-in transfer before the model can consume them. Conversely, tensors residing directly in local accelerator memory may belong to a different tenant or security domain, making them ineligible for sharing under isolation rules. The reusable prefix length is the longest contiguous token sequence that simultaneously satisfies compatibility, physical residency, and access permissions. That sequence is frequently shorter than the longest match found in the prefix tree. Furthermore, newly generated tokens qualify for subsequent prefix matching only after their corresponding KV blocks have been fully materialized in memory and committed to the index.
These structural requirements operate independently of semantic validity. Updating a target repository from commit r17 to r18 does not alter or invalidate the KV activations previously computed for an older prompt describing r17. Those tensors remain numerically identical and computationally compatible with the stale prompt, even though the context no longer reflects the current state of the code. The harness’s context-selection policies govern which evidence to provide to the model. When the agent harness updates or replaces outdated logs in the serialized prompt, the prefix matcher detects the divergence, immediately terminates the match at the first altered token, and triggers a fresh prefill for the updated text. The prompt layout, rather than the cache layer, enforces freshness.
↩︎ How the harness withdraws a stale observation, such as the r17 test failure, while keeping it as history is established in Context Invalidation.
5.5.2 Radix prefix lookup
Matching a new request against thousands of retained multi-thousand-token agent prompts token by token would build a deep, pointer-heavy index, so a radix prefix cache compresses chains of single-child token transitions into variable-length sequence edges in a radix tree (Zheng et al. 2024).6 To resolve a cache match, the scheduler walks the tree from the root, matching prompt tokens along successive edges until reaching a divergence point. This traversal simultaneously identifies the longest common prefix and the physical KV blocks storing its activations. Once a match is identified, the engine must acquire explicit ownership of those memory blocks before the background eviction thread can reclaim them. Lookup overhead scales with the prefix length examined, remaining on the order of microseconds on host CPUs. Alternatively, systems can implement an equivalent reuse contract using chained hash tables, where each fixed-size block is keyed by a cryptographic hash of its token content concatenated with the hash of its parent prefix.
6 Compressed Prefix Tree: The trie stored one symbol per edge, so a shared prefix was found by walking from the root (Fredkin 1960). PATRICIA collapsed chains of single-child nodes into one edge, so index size grows with the number of stored keys rather than their length (Morrison 1968). The same compression matters for KV reuse, because agent prefixes run to thousands of tokens and a one-token-per-edge index would spend a node on each of them.
Fredkin, Edward. 1960. “Trie Memory.” Communications of the ACM 3 (9): 490–99. https://doi.org/10.1145/367390.367400.
Morrison, Donald R. 1968. “PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric.” Journal of the ACM 15 (4): 514–34. https://doi.org/10.1145/321479.321481.
The tree’s shape follows from the causal dependence that context staging already turned into a layout rule. Every position’s keys and values depend on the full history before it, so a node’s KV state is valid only beneath its exact ancestors, and an identical passage that follows a modified token lives on a different branch with no reusable state. The layout rule is the harness’s half of the same constraint. Staging volatile components (dynamic counters, tool outputs, scratchpad notes) toward the end of the prompt keeps the long invariant prefix on one path from the root, and compaction that rewrites only trailing turns leaves that path intact.
↩︎ Stable-prefix layout rules for prompt staging are established in Staging the Next Invocation.
Physical memory allocation introduces a practical policy choice at block boundaries without altering the underlying definition of compatibility. Suppose a later request matches the ten-token prefix whose blocks [3, 7, 9] were traced earlier, with block 9 holding two initialized entries. A serving engine that supports partial-tail reuse preserves all ten tokens and resolves the new turn’s divergent append with the same copy-on-write step recorded in table 3. An engine that caches only complete blocks reuses eight tokens and prefills the remaining two. Both designs are valid. The partial-tail strategy minimizes redundant prefill at the expense of copy-on-write buffer management, while the full-block strategy simplifies allocation by trading a modest amount of recomputation for uniform block lifecycles.
5.5.3 Retention and eviction under pressure
Keeping finished requests’ KV blocks around as dormant cache entries allows subsequent turns to reuse them, but those dormant blocks eventually fill the KV pool and force the allocator to evict old entries without racing active kernels or breaking shared tree paths. When an inference request finishes, the serving engine releases the request’s execution handles while the cache manager retains its own structural references to the blocks. The system’s retention policy then determines whether the next turn finds that KV state still resident in accelerator memory, pages it back from host RAM, or recomputes it from tokens.
Reusing and reclaiming memory blocks requires strict ownership tracking across concurrent threads and hardware streams. When a request matches a cached prefix, the memory manager increments reference counts on the corresponding blocks before dispatching execution kernels. Conversely, before reclaiming a physical block under memory pressure, the allocator must sever the cache’s indexing reference, confirm that active execution references have dropped to zero, and synchronize with outstanding device streams that might still be reading or writing those memory addresses. The allocator must also synchronize index modifications and reference changes so that a concurrent lookup cannot bind to a block while background eviction is tearing it down.
In tree-structured prefix caches, leaf-first eviction maintains structural consistency by preserving contiguous paths from the root and evicting unused leaf nodes first. Because internal nodes store common prefix state shared across multiple conversation branches, evicting an ancestor would invalidate all of its downstream descendants. An internal node becomes eligible for reclamation only after all of its descendant children have been evicted. Within the set of eligible leaves, systems frequently adopt a least-recently-used (LRU) policy (Zheng et al. 2024), operating on the premise that recent access predicts near-term reuse (Belady 1966).7 Reclamation therefore cascades upward. An inactive parent cannot be reclaimed while its child remains cached, but once the child leaf is evicted, the parent itself becomes an eligible leaf and can be freed if memory pressure persists (figure 4).
7 Replacement with Foresight: The classic study of page replacement showed that the optimal policy evicts the page whose next use lies furthest in the future, a rule no online system can apply because it needs the future reference string (Belady 1966). Recency-based policies approximate it. An agent harness sometimes holds part of that future, such as a tool launch that will idle a prefix for minutes, which is why a retention hint from the caller can beat recency alone.
Belady, Laszlo A. 1966. “A Study of Replacement Algorithms for a Virtual-Storage Computer.” IBM Systems Journal 5 (2): 78–101. https://doi.org/10.1147/sj.52.0078.
Leaf-first eviction keeps residency prefix-closed, meaning that every resident node’s ancestors are also resident, and in full-attention models that property is an operational necessity. While freeing an upstream prefix block leaves the numeric values of a retained downstream suffix physically untouched, causal attention requires the entire preceding context to evaluate subsequent tokens. An orphaned suffix block is useless on the accelerator until its missing ancestral prefix is either reloaded from auxiliary storage or recomputed through a new prefill pass.
Retention policies therefore balance occupied accelerator capacity against the computational cost a future hit would eliminate. Recency alone provides an imperfect signal: an agent may generate a speculative branch that is never visited again, whereas a system prompt shared by hundreds of concurrent agent workers remains valuable despite sporadic gaps between calls. More resilient eviction schemes score cached nodes by balancing their expected reuse probability and recomputation cost against their physical memory footprint, adapting the retention weights to match dynamic workload demands.
5.5.4 Prefix hit rate and the reuse contract
Counting raw matching tokens in a prompt overstates real-world system benefits whenever matching blocks have been evicted, tenant isolation policies prohibit sharing, or memory allocators round matches down to physical block boundaries. Systems engineers evaluate caching efficacy by measuring the tokens actually served from reusable KV state without recomputation. Across a specified workload window, the token-weighted prefix hit rate is defined as
\[\PrefixHitRate = \frac{\sum_{i} \ReusedPrefixLength^{(\WorkloadRequestIndex)}}{\sum_{i} \PromptLength^{(\WorkloadRequestIndex)}} \tag{2}\]
where \(\PromptLength^{(\WorkloadRequestIndex)}\) represents the prompt token count of request \(\WorkloadRequestIndex\), and \(\ReusedPrefixLength^{(\WorkloadRequestIndex)}\) counts the prompt tokens whose compatible KV activations were attached without recomputation after enforcing availability, security permissions, and block-alignment constraints. In the earlier four-token block example, a request matching ten tokens under a full-block-only caching policy yields \(\ReusedPrefixLength = 8\), leaving two tokens to be prefilled. A production telemetry pipeline should also distinguish warm hits (state already resident in accelerator HBM) from cold hits (state that must be restored across PCIe from host memory).
The concrete computational value of a prefix hit follows directly from prefill arithmetic. Consider a deliberately small 4,096-token prefix of invariant system instructions and tool definitions; the longer shared zone of the r18 context would save more. Retaining this sequence in memory occupies 1.34 GB of KV activations distributed across the server node. Reconstructing that state from scratch requires roughly 578 trillion operations for linear projection layers, plus approximately 22 trillion operations for causal self-attention (equation 4). If the node sustains 45 percent of its peak 16-bit floating-point throughput (about 3,560 trillion operations per second), rebuilding that prefix incurs 169 ms of prefill latency on every single cache miss. In contrast, a turn that scores a cache hit and appends only a 32-token suffix bypasses the prefix prefill entirely, requiring only a single memory-bandwidth-bound pass over the model weights. Because a 32-token suffix provides too little parallel arithmetic to saturate the accelerator’s matrix units, execution time is bounded by the weight-read floor of roughly 5 ms. Both numbers come from one step-time model that the rest of the chapter reuses. A forward pass over \(\ForwardPassTokenCount\) token positions takes \(\WeightOnlyStepTime(\ForwardPassTokenCount) = \max\left(\PerDeviceWeightReadTime,\; 2\Parameters \ForwardPassTokenCount/\AttainableComputeRate\right)\), the larger of the time \(\PerDeviceWeightReadTime\) to read the weights once from accelerator memory and the time to perform \(2\Parameters \ForwardPassTokenCount\) weight operations at the sustained rate \(\AttainableComputeRate\). These are the two per-token floors of equation 2.7 applied to a whole pass; equation 5 derives the bound and its assumptions. The rebuild estimate above adds the attention term, which this weight-only model omits. The hit thus replaces 169 ms of prefix prefill with a pass of about 5 ms, and a trajectory that keeps its invariant prefix stable collects that saving on every turn, in both latency and aggregate prefill work.
Although equation 2 measures the computational work avoided during prefill, end-to-end request latency also includes novel suffix prefill, autoregressive token generation, batch scheduling delays, and memory transfers. Once a hit eliminates prefix compute, any of these can dominate total response time. When monitoring production clusters, a declining prefix hit rate warrants investigating both sides of the client-service interface. On the client side, minor modifications in prompt serialization (such as altered whitespace, injected timestamps, or reordered JSON schema keys) prematurely truncate prefix matches. On the server side, heightened memory pressure, poor cross-node routing, or mismatched runtime configurations can render compatible state unavailable or physically inaccessible.
When using hosted model APIs, application developers require an explicit reuse contract rather than relying on unverified assumptions about the provider’s internal memory allocator. This contract must clearly define eligible token inputs, compatible execution configurations, tenant isolation boundaries, and supported retention lifetimes. In agentic workflows, cache expiration tightly couples this reuse contract to tool execution latency. If an external tool call blocks longer than the provider’s idle eviction threshold, the subsequent turn discovers that its cached prefix has been purged and incurs a full prefill penalty, the remote equivalent of the drop-and-recompute policy described in section 5.7. An agent harness aware of these eviction horizons can anticipate cache misses during long tool waits rather than absorbing unexpected latency spikes. The cached-token metric returned in API usage records is the client’s primary telemetry signal, though interpreting it requires understanding its precise operational scope.
Systems Perspective 5.1: Reading a cached-token count
A usage record that reports cached input tokens indicates how many prompt tokens the provider served from reusable KV state, which is the numerator of equation 2 for that specific request. However, this metric remains silent on where those tensors resided (accelerator HBM vs. host DRAM), how the provider indexed them, or how long they will remain unevicted before the next invocation.
Its diagnostic value emerges when tracked across successive turns of an agent trajectory. Dividing the cached-token count by the total prompt tokens yields the caller’s observed prefix hit rate. A count that abruptly plunges to zero following an extended tool execution is consistent with cache expiration under idle eviction, but memory pressure, routing changes, and incompatible execution settings can produce the same observation. A count that stabilizes below the expected value may indicate an early prompt serialization divergence. Comparing submitted token prefixes and checking request routing and execution settings helps distinguish that client-side cause from unavailable or ineligible cached state. A confirmed layout divergence is an issue the client application can resolve directly in its prompt assembly pipeline.
An agent application must maintain functional correctness regardless of whether a request hits or misses the cache; the serialized context, not the cache, dictates the model’s true prompt input. A cache hit simply eliminates redundant arithmetic. When an agent turn introduces a voluminous test log or extensive retrieval chunk, it inevitably injects new prefill compute into the execution engine. Scheduling that compute-heavy prefill alongside ongoing, memory-bandwidth-bound token generation for existing requests is the next serving problem.
5.6 Chunked Prefill Scheduling
Prefix reuse eliminates redundant computation on shared prompt prefixes, but new observations inevitably introduce fresh work. When the repair agent submits selected integration-test output, the serving engine must process the uncached suffix of the serialized request before generating the next response token. Other requests may already be generating tokens on the same accelerators. If the engine schedules the entire new prefill as one uninterrupted monolithic batch, those ongoing decode streams must wait for that pass to finish before executing their next decode step. In interactive agent workflows, that stall translates directly into noticeable inter-token latency spikes.
Trimming the observation reduces the raw number of tokens to process, but once the request reaches the server, scheduling determines how execution time is shared among active streams. The engine does not need to execute a long prefill as an all-or-nothing unit. Continuous batching already re-forms the batch at every forward step, admitting and retiring requests between token-generation steps (Yu et al. 2022), and that per-iteration boundary is exactly where a slice of one request’s prefill can be combined with other requests’ decodes. By splitting long prefills into smaller token chunks that co-run alongside ongoing decodes, the scheduler bounds how long any single iteration can stall active generation streams (Agrawal et al. 2023, 2024).
Agrawal, Amey, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, Alexey Tumanov, and Ramachandran Ramjee. 2024. “Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve.” 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), 117–34.
↩︎ Prefill, decode, time to first token, and continuous batching are established in Where a call spends its time.
Definition 5.4: Chunked prefill
Chunked prefill is a scheduling policy that splits a request’s uncached prompt into token spans processed over several engine iterations, each iteration also advancing ongoing decodes, while preserving causal order.
- Significance: It bounds the gap between consecutive output tokens for ongoing requests to the duration of a single chunked iteration rather than a full monolithic prefill, at the expense of a modest delay in time to first token for the new request.
- Distinction: A chunk represents an execution quantum for the scheduler rather than a physical storage layout. The memory allocator maps the resulting KV activations into memory blocks whose page sizes operate independently of chunk boundaries.
- Common pitfall: Treating the per-iteration token budget as an exact wall-clock time limit. Iteration latency depends on attended context length, memory bandwidth, and batch composition, so operators must calibrate the budget against measured gaps between output tokens under realistic workloads.
5.6.1 Causal correctness across chunks
Splitting a prompt across several iterations would change the model’s outputs if a later chunk attended only to tokens inside its own slice or used reset position indices. To preserve exact causal attention across chunks, each query token in the active chunk must attend to the compatible per-layer KV state produced by all earlier prefixes as well as the prior and concurrent tokens within its own chunk, enforced by the causal mask, while remaining blind to subsequent tokens. The engine preserves continuous positional encodings and mask logic as it extends the stored KV state, loading previously computed keys and values from memory rather than recomputing their projections from raw token embeddings. Chunking therefore alters the temporal execution schedule while preserving exact causal semantics, modulo minor floating-point non-associativity across kernel tiling and batching configurations. This scheduling flexibility incurs two physical costs: subsequent chunks must repeatedly stream earlier KV activations from high-bandwidth memory, increasing aggregate memory traffic, and smaller prefill slices introduce additional kernel-launch and scheduling overheads.
5.6.2 The per-iteration token budget
Admitting too many prefill tokens into one iteration stalls active decode streams, while admitting too few stretches a new prompt across dozens of small, overhead-heavy steps. To bound the work of each forward pass, a scheduler establishes an iteration-level token budget \(\IterationTokenBudget\). In standard autoregressive decoding, each scheduled decode request contributes one token position, whereas each scheduled prefill contributes the token count of its next chunk. An engine iteration admitting prefill chunks of size \(\PrefillAllocatedTokenCount_i\) alongside a set \(\DecodeRequestSet\) of active decode requests must satisfy
\[\sum_{i} \PrefillAllocatedTokenCount_i + \lvert\DecodeRequestSet\rvert \le \IterationTokenBudget \tag{3}\]
while ensuring that the admitted combination fits within available accelerator memory. A request whose prompt spans multiple chunks retains its partially computed prefix KV state in memory across iterations while waiting for its subsequent slices to run.
A common scheduling policy prioritizes ongoing decoding requests by reserving \(\lvert\DecodeRequestSet\rvert\) slots first, dedicating the remaining capacity \(\IterationTokenBudget - \lvert\DecodeRequestSet\rvert\) to prefill chunks. This decoding-first priority ensures steady token generation for active streams without requiring them to wait for an entire multi-thousand-token prompt. However, the arriving request may require several iterations to complete its prefill, particularly if heavy decode traffic restricts the available chunk size. Conversely, allocating too much budget to prefill chunks can starve decode streams and trigger latency spikes. A robust scheduler must balance decode responsiveness against prefill completion progress to avoid both stream stalls and prompt starvation.
The weight-only step-time model \(\WeightOnlyStepTime(\ForwardPassTokenCount)\) of the prefix-hit estimate gives the scale of this trade-off, with \(\ForwardPassTokenCount\) the token positions that equation 3 admits in one iteration. With 32 ongoing decodes and nothing else, each step sits at the weight-read floor of about 5 ms. Admitting a 4,096-token prefill as one unit adds about 162 ms of arithmetic before those decodes run again (weight work only, so slightly below the 169 ms prefix rebuild, which includes attention), stretching their gap between tokens to about 168 ms.
Dividing that prompt into 512-token chunks reshapes execution. Each iteration now carries 544 positions and takes about 22 ms. Because the decodes advance in each of the eight iterations, their worst gap is about 8× smaller, while the new prompt completes after about 173 ms instead of 162 ms. Chunking buys existing streams a much shorter gap for a modest delay in the new request’s first token: on one time axis, the monolithic schedule leaves a single long gap between two output tokens, while the chunked schedule places a token at every iteration boundary and finishes the prompt only slightly later (figure 5). Both schedules omit attention traffic, which grows with each chunk’s context, and per-iteration overhead, so measured iterations run longer and the budget must come from measurement.
Characterizing these trade-offs requires replaying representative arrival traces across candidate token budgets while tracking key systems metrics: time to first token for newly admitted requests, inter-token latency for active decode streams, aggregate token throughput, and accelerator memory occupancy. High-percentile latency measurements, such as the p99 inter-token gap, expose transient scheduling hiccups far better than arithmetic averages, which easily conceal the disruptive stalls of occasional large prefills. Operators must also distinguish server iteration step times from client-perceived streaming intervals; downstream buffering, transport serialization, and network round-trip times introduce variances that server-side metrics do not capture.
Selecting the token budget \(\IterationTokenBudget\) ultimately balances hardware execution efficiency against service responsiveness. Smaller chunks provide frequent scheduling checkpoints that protect inter-token deadlines, yet they extend total prompt completion times and add kernel-launch overhead. Larger chunks maximize tensor-core utilization by providing wider matrix dimensions during attention and feed-forward operations, but they penalize concurrent decode streams with longer stalls. In practice, operators configure the token budget to the largest chunk size whose corresponding iteration duration comfortably satisfies the target inter-token latency objective for active streams. On the reference node, the weight-only estimate gives the starting point. An inter-token target comfortably above 22 ms admits the 512-token chunk alongside 32 decodes. A tighter target forces smaller chunks and a later first token for the new request, while running the prompt unchunked exposes the decodes to the full 168 ms gap. Measured attention traffic and per-iteration overhead then shrink the admissible chunk from that estimate.
Prefill-decode disaggregation, introduced with the call-latency decomposition of Where a call spends its time, takes the structural alternative to chunking and places the two phases on separate worker pools (Patel et al. 2024; Zhong et al. 2024). It replaces compute contention on one worker with a transfer of each prompt’s KV state from the prefill pool to a decode worker before generation starts, and when the interconnect saturates or queues build at either pool, that transfer can cost more than phase isolation saves. For an agent calling a hosted endpoint, that topology stays behind the serving API and appears only as request latency, streaming variance, and concurrency limits.
Chunking and disaggregation govern how active requests share compute resources during model execution. Once generation completes and an agent suspends execution to invoke an external tool or inspect an environment, the operational challenge changes from scheduling compute to managing idle memory. Deciding whether that trajectory’s KV state remains resident in accelerator memory, spills to host memory, or evicts entirely becomes the governing concern.
5.7 Paused-State Policies
The r18 request’s 45-second integration test is the tool-wait problem in its plainest form. When an agent invokes an external tool, such as a long-running test or a query to a remote database, the serving system faces an extended idle period before the tool returns its output. Although the model performs no active generation during this pause, retaining its key-value cache in accelerator memory ties up scarce HBM. To prevent idle requests from starving active generation, the serving engine must execute a paused-state policy: retain the state in device memory, offload it to host memory or secondary storage, or drop it entirely and reconstruct it when the tool output arrives. Systems research on tool-augmented generation evaluated these same three mechanisms (preserve, swap, and discard), selecting dynamically among them per request to minimize wasted accelerator memory (Abhyankar et al. 2024). This choice balances device memory capacity against host storage, interconnect transfer time, and recomputation latency. It belongs below the model. Invariant closure (principle 1) closes mechanical bounds below the model, and the pool is such a bound. The model cannot observe how full the pool is, nothing in a proposal can enforce a release, and the correctness of the next turn never depends on where the state was kept. The serving engine therefore executes the policy and decides keep, move, or drop. The agent runtime may supply hints, such as the expected length of the wait or whether the trajectory is likely to resume at all, and a hosted service exposes them only through its API. The model neither makes the decision nor supplies the hints, and its proposals never touch the lifecycle.
↪ Harness supervision of resources retained during external tool waits is developed in Resources retained while waiting.
5.7.1 Reclaimable state
Evicting or offloading a paused trajectory frees far less memory than its logical token count suggests whenever its prefix blocks are still shared with active requests or pinned by in-flight transfers. Prefix blocks shared with concurrent trajectories, such as common system prompts or branching execution paths, must remain allocated on the accelerator as long as another request holds a valid reference. Similarly, blocks currently committed to in-flight asynchronous direct memory access (DMA) copies or active kernel operations cannot be freed until those transfers complete. The uniquely reclaimable footprint consists solely of unshared blocks with no pending operations, and every pause calculation must use this private footprint as its baseline.
Offloading state requires available capacity at the target tier and a coordinated handoff protocol. To maintain memory safety, the engine must preserve source blocks in accelerator memory until the outbound DMA transfer to host memory verifies successfully. During the transfer window, the state consumes both device HBM and host DRAM concurrently. The host-memory budget must therefore accommodate these transient transfer buffers alongside already parked trajectories. Upon resumption, the sequence reverses: the scheduler must allocate accelerator blocks, initiate an inward transfer, and update page tables before attention kernels can resume execution.
Discarding the KV cache relinquishes the computed state while preserving the underlying information, provided the raw input sequence and environment observations remain recorded in durable logs. Because attention state is derived from the token prefix (principle 5), state lost this way can be derived again. If the request resumes, the engine reconstructs the missing attention state by re-running prefill across the historical prompt. This reconstruction requires exact provenance: the precise token sequence, active LoRA adapters, position encodings, attention masks, and multimodal embeddings. A compressed conversation summary cannot substitute for the raw token history. Reconstruction typically reuses any compatible prefix blocks that remain in memory and prefills only the missing suffix. In managed inference platforms, callers can exploit these trade-offs only to the degree that the hosting service exposes explicit prefix caching or session controls.
5.7.2 Keep, move, and drop policies
For those uniquely reclaimable blocks, the serving engine has three choices while the tool runs: keep them on the accelerator at the cost of HBM capacity, move them to host memory at the cost of interconnect bandwidth, or drop them and rebuild the suffix through prefill when the tool returns. Table 4 compares how the three policies trade accelerator memory against restoration work.
| Policy | Accelerator capacity released | Work needed on return | Principal constraint |
|---|---|---|---|
| Keep | None from the retained blocks | No restoration of those blocks | Retention competes with other allocations |
| Move | Reclaimable source blocks after a successful copy | Allocate and reload compatible state | Destination capacity and contested transfer paths |
| Drop | Reclaimable blocks after safe release | Reconstruct missing state from retained inputs | Input availability and prefill capacity |
Each policy targets a distinct operational regime. Retaining state on the accelerator is optimal when the memory pool has ample headroom and the agent anticipates an immediate return: holding the blocks incurs zero marginal cost if no competing work requires memory, and it guarantees zero restoration latency when generation resumes. Under memory pressure, moving state to host DRAM releases critical accelerator capacity without discarding the completed prefill computation. Dropping state becomes the preferred choice when the probability of resumption is low, host DRAM is exhausted, or the context is short enough that recomputing prefill is faster than transferring the data across the bus. Whichever policy runs, the engine must enforce memory isolation boundaries so that retained, offloaded, or evicted blocks remain protected from unauthorized access by other tenants.
When pause durations extend across minutes or hours, as for workflows waiting for human approval, the engine can migrate state beyond host DRAM to non-volatile storage. Hierarchical serving systems organize storage across host memory and NVMe drives, prefetching cached layers sequentially so that retrieval from disk overlaps with execution of earlier layers (Gao et al. 2024). At data center scale, distributed architectures pool the host memory and solid-state storage of thousands of nodes into a shared cluster-wide KV cache (Qin et al. 2024). Across all storage tiers, cached attention tensors represent derived, transient state; the durable history of user inputs, tool actions, and execution evidence resides in the runtime’s authoritative event log.
5.7.3 Comparing reload and recompute during the test wait
To quantify these choices, consider an agent holding 32,768 tokens of context while pausing for a 45 s integration test on an eight-accelerator node. In this scenario, all historical KV entries have already been materialized, each 16-token block is completely filled, and no blocks are shared or committed to in-flight transfers. The uniquely reclaimable cache footprint is therefore 10.74 GB (excluding auxiliary page tables and transfer buffers, which the runtime budgets separately).
The transfer and recompute durations derive directly from hardware specifications. Because tensor parallelism partitions key-value heads evenly across the eight accelerators, each device holds one-eighth of the total state and transfers data over its own 64 GB/s PCIe link. When all eight links operate concurrently, the node moves state at an aggregate bandwidth of \(\HostLinkBandwidth =\) 512 GB/s. Offloading the complete 10.74 GB payload across this interface requires 21 ms, and restoring it upon resumption takes an identical 21 ms.
Reconstruction instead repeats the prefill pass. For a model with \(\Parameters\) parameters and a sequence of \(\SequenceLength\) tokens, evaluating the feed-forward and projection weights requires \(2\Parameters \SequenceLength\) floating-point operations. At the sustained prefill rate assumed for the reference system, recomputing this context demands 1.3 s, and including the quadratic attention term of equation 4 would lengthen it further. (Because every policy must eventually process the incoming test observation once the wait concludes, that downstream prefill is common to all policies and omitted from this comparison.)
In this weight-only comparison, both transfer duration and recompute duration scale linearly with sequence length \(\SequenceLength\), so their ratio is independent of context size:
\[\frac{\KvReloadTime}{\KvRecomputeTime} = \frac{\SequenceLength \, \KvCacheBytesPerToken / \HostLinkBandwidth}{2 \Parameters \SequenceLength / \AttainableComputeRate} = \frac{\KvCacheBytesPerToken \, \AttainableComputeRate}{2 \Parameters \, \HostLinkBandwidth} \tag{4}\]
Reloading paused state beats rebuilding it by about 62× in the linear reference comparison.
Here \(\AttainableComputeRate\) represents the sustained prefill throughput, and \(\KvCacheBytesPerToken\) is the cache footprint per token. Equation 4 applies the reload-versus-reconstruction comparison of Queueing for Trajectories to this reference architecture. Reloading retained state is approximately 62× faster than recomputing from raw tokens. Even when heavy bus contention degrades link bandwidth to a quarter of its rated capacity, reloading remains 15× faster than prefill. Under this linear reference comparison, recomputation becomes advantageous when host DRAM capacity or PCIe bandwidth is sufficiently constrained by competing workloads, leaving accelerator compute as the less congested resource.
Retaining the cache on-chip throughout the 45 s wait ties up 10.74 GB \(\times\) 45 s \(\approx\) 483.18 GB·s of memory-time capacity (calculated using the unrounded payload). This cumulative occupancy translates into lost serving capacity whenever concurrent requests queue for device memory. Counted in request slots rather than bytes, that occupancy is a residence. Little’s law, the queueing identity that equates mean occupancy with arrival rate times mean residence, converts it into a lost turn rate in section 5.8.2, where the same wait divides the memory-bound rate by the ratio of the whole turn cycle to its generation time.
Moving the state to host memory immediately upon entering the pause releases those accelerator blocks as soon as the 21 ms outbound copy completes. The freed blocks can serve other queries for 45 s \(-\) 21 ms \(=\) 44.98 s before the test returns. The policy incurs 42 ms of total transfer work across the bus, but only the inbound reload sits on the critical path of the resuming query, adding 21 ms of restoration delay. Dropping the state avoids bus transfer entirely, but forces 1.3 s of prefill work onto the critical path before generation can restart.
If the engine can predict the tool completion timestamp accurately, typically from a hint the agent runtime supplies, asynchronous prefetching can schedule the inward transfer to complete precisely as the test finishes. Reserving the destination device blocks at the start of that inbound copy yields an accelerator release window of 45 s \(-\) 21 ms \(-\) 21 ms \(=\) 44.96 s. Prefetching hides restoration latency completely while maintaining both transfer stages, though it requires reliable advance knowledge of return times.
The same reasoning extends to every context length and wait. The round-trip transfer time, which scales linearly with context length and equals 42 ms in this configuration, sets a necessary condition. A pause shorter than the round trip ends before offloading can move the state out and back without delaying resumption. Keeping it avoids restoration work when memory permits; under pressure, moving or dropping it may still be necessary. Above the round trip, offloading becomes possible, and whether it pays depends on whether other requests are queued for the freed memory and how much reload delay the resuming turn tolerates. For long pauses under memory pressure, offloading reclaims device memory for almost the entire wait at the cost of a sub-second reload. The worked 32,768-token, 45 s test sits far beyond that round trip. It also sits short of the much longer waits at which parked state accumulates enough to fill host memory, a boundary set by host capacity and by how fast paused trajectories arrive rather than by a fixed duration. The example therefore falls squarely in the offload regime (figure 6). When pauses stretch into minutes or hours, as for operations awaiting human review, parked state accumulates in host memory, and the decision turns on host capacity, secondary storage bandwidth, or eventual recomputation.
5.7.4 Uncertain returns and competing transfers
External tool runs vary widely in duration: a test suite may fail immediately on a syntax error, finish early, or stall on an environmental hang, and this variance complicates offload and prefetch decisions. If a tool completes earlier than forecasted while offloading is still in flight, the engine must either wait for the outbound transfer to finalize before reloading or cancel the transfer mid-stream, exposing unbuffered restoration latency. Conversely, premature prefetching followed by a delayed return re-occupies accelerator memory while the model remains idle, negating the capacity reclaimed during the pause, and if a paused trajectory is canceled or times out, an anticipatory inward reload wastes interconnect bandwidth outright. A robust pause policy must therefore evaluate the full probability distribution of return times alongside client latency service-level objectives (SLOs), rather than relying on mean wait times and uncontended transfer estimates.
Furthermore, transfers rarely occur in isolation. Multiple paused trajectories frequently finish their external tasks in close temporal proximity, triggering a surge of concurrent reloads across shared host-memory buses, PCIe switches, and storage links. Summing nominal per-accelerator link rates is valid only if interconnect topologies and memory controllers maintain non-blocking throughput under concurrent load.
Suppose 32 paused repairs on a node finish their external tasks simultaneously. Their combined attention state totals 344 GB, which requires at least 0.67 s to reload even when the eight host links sustain their maximum aggregate throughput. The final reload in the queue therefore experiences a restoration delay roughly 32× longer than the isolated 21 ms reload latency, and any congestion on shared bus root complexes lengthens the tail further. System engineers must provision transfer queues, admission controls, and accelerator headroom specifically to absorb these burst-induced restoration delays.
Pipelining can overlap data transfers with computation, but strict causal dependencies dictate which operations can run concurrently. In standard full-attention models, generating or processing new observation tokens requires access to all historical key and value tensors. An engine cannot compute attention for layer \(\LayerIndex\) until the historical KV blocks for layer \(\LayerIndex\) reside in accelerator memory. Transfer latency can therefore be hidden only if the engine streams state in layer by layer (reloading layer \(\LayerIndex+1\) while executing attention on layer \(\LayerIndex\)) or if the node schedules unrelated generation requests while the paused state reloads in the background. Both techniques require careful engine coordination: layer-wise streaming requires fine-grained synchronization across DMA engines, while concurrent execution requires reserve accelerator memory to host the in-flight requests alongside incoming reload buffers.
5.7.5 Reclamation vs. approximation
Dropping individual tokens from an active KV cache or quantizing its keys and values shrinks memory occupancy without waiting for a tool pause, but unlike keeping, offloading, or recomputing, these lossy approximations alter the model’s forward pass and can silently break a multi-turn repair when an evicted token turns out to matter ten turns later. Because selective token eviction, local sliding windows, and low-precision KV quantization change the underlying model computation, their efficacy cannot be judged by memory savings alone; they require empirical validation against task accuracy. In agentic workflows, an eviction policy cannot assume that low attention weight during past decoding steps implies irrelevance in future turns.
The mechanics of attention sinks demonstrate why naive eviction schemes break down. Because softmax normalizes attention weights to sum to one across the sequence, transformer layers deposit residual attention mass on the initial sequence positions whenever a query has no strong semantic match among current tokens. A sliding-window policy that evicts those initial tokens removes this stabilizing mass, causing generation perplexity to degrade sharply once context length exceeds the window size. Retaining a small set of initial sink tokens alongside the sliding window restores numerical stability across long sequence streams (Xiao et al. 2024). More sophisticated pruning strategies retain tokens that accumulate high cumulative attention mass (Zhang et al. 2023) or that receive significant attention within a recent temporal window (Liu et al. 2023).
Liu, Zichang, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasia Mazur, Chen Dun, and Anshumali Shrivastava. 2023. “Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression.” Advances in Neural Information Processing Systems (NeurIPS).
While past attention predicts future utility reasonably well in conventional conversation, agent trajectories routinely violate this assumption in three distinct ways:
- Dormant constraints: Instructions defined early in an execution trace (such as environment constraints, security policies, or API rules) often receive negligible attention across dozens of intermediate tool turns. When the agent produces its final edit or synthesis, violating those dormant instructions causes silent task failure.
- Exact identifiers: Unique entities like commit hashes, process IDs, file paths, and cryptographic nonces may appear once during environment exploration and remain unreferenced for many turns. If an eviction heuristic prunes these tokens because intermediate turns ignored them, the agent cannot quote them accurately in subsequent shell or API calls.
- Tool-schema syntax: Schema definitions and JSON delimiters in the system prompt govern the grammar of every tool call. Individual decoding steps frequently assign weak attention mass to structural delimiters like brackets and colons. Pruning them produces malformed syntax that crashes downstream parsers rather than a graceful degradation in output quality.
Cache approximation in agentic systems must therefore be evaluated against hard semantic dependencies rather than aggregate perplexity. The lossless policies (keep, move, and drop) cost interconnect bandwidth and tiered memory capacity, but they preserve the full-attention computation for the same recorded inputs and compatible configuration, subject to numerical differences across implementations. They decide where one paused trajectory’s state lives. They leave open how many trajectories a node can carry when each one holds memory for its whole residence, waits included, and answering that requires putting time into the capacity accounting.
5.8 Capacity for Agent Workloads
A paused repair task can hold key-value state in accelerator memory for minutes without executing a single forward pass, while an incoming request demands both memory capacity and execution time immediately. How an engine handles paused state dictates how many concurrent agent trajectories can fit in memory. Converting that static concurrency into a sustainable throughput, however, requires modeling how long each session holds its memory. Capacity planning therefore first establishes physical occupancy bounds and then couples those bounds to residence time.
Tracking memory demand in agentic serving differs from tracking standard batch inference, where every active sequence holds a private cache. In an agent workload, logical contexts overlap through shared system prompts and tool descriptions while continuations allocate private blocks and dormant prefixes wait to be reused or paged out. Summing the logical key-value footprints of all active trajectories therefore double-counts shared prefix blocks, whereas counting only the requests currently decoding tokens ignores the dormant KV state that still occupies HBM. Capacity planning must instead count unique physical blocks across the pool.
5.8.1 A resident-fit bound
Sizing a node by dividing raw HBM by a prompt’s token footprint overestimates how many requests can safely run at once, because each admitted request also needs room for its generated output, rounds its allocation to whole blocks, and shares part of the pool with runtime headroom. To build a capacity model that accounts for these bounds, consider a set of equal-length requests with input prompt length \(\SequenceLength\) and a maximum generation allowance of \(\OutputLimit\) tokens. Because paged allocation hands out fixed-size blocks of \(\KvBlockSize\) tokens, each private allocation rounds up to the nearest whole block. Without prefix sharing, every resident request must independently provision memory for its full prompt and output allowance. When requests share an identical, compatible prefix, however, the memory pool allocates those prefix blocks once and pays only for each request’s private remainder. For this simple decomposition, assume that the common prefix aligns cleanly with a block boundary; any trailing partial block follows the copy-on-write accounting described earlier.
The memory available for key-value caching is whatever high-bandwidth memory remains after allocating model weights and reserving memory for execution runtimes:
\[\KvPoolMemory = \NodeHbmCapacity - \WeightMemory - \RuntimeReserveMemory \tag{5}\]
Production deployments typically withhold an additional headroom fraction \(\KvPoolHeadroomFraction\) of this pool to absorb bursty intermediate activations and memory fragmentation. Given block size \(\KvBlockSize\), a block-aligned common prefix of \(\SharedPrefixLength\) tokens, and a cache footprint of \(\KvCacheBytesPerToken\) bytes per token across all layers, the total physical block demand across \(\BatchSize\) resident requests (every request whose state is resident, whether decoding or paused) must satisfy
The resident-fit bound of section 5.2, refined for blocks, headroom, and sharing, is the maximum integer \(\BatchSize\) that satisfies equation 6. Setting \(\SharedPrefixLength = 0\) yields the unshared baseline. Because the common prefix is allocated only once, sharing delivers its largest gains when common instructions represent a dominant fraction of the total prompt, and when private working memory (the unique turn history and generation allowance) remains small. Notebook 5.3 grounds these formulations on the same eight-accelerator DGX H100 node serving Llama 3 70B: rather than optimistically assuming an average generation length, the sizing calculation reserves the full \(\OutputLimit\) token allowance to guarantee that resident requests cannot trigger out-of-memory aborts during decoding, treating the headroom fraction as a deliberate provisioning reserve.
Napkin Math 5.3: From logical contexts to physical fit
Problem: How many complete request snapshots fit when a common prefix is stored once rather than copied for every request?
Variables: The Llama 3 70B model uses 16-bit weights and KV state on the DGX H100 node. After weights and the stipulated 20 GB runtime reserve, its KV pool (equation 5) is 526.0 GB. Withhold an additional 10 percent. Each request has 32,768 input tokens and an allowance of 2,048 output tokens. The requests come from a fleet of repair workers on one repository snapshot, so their first 24,576 input tokens (instructions, tool schemas, and the shared workspace state) are identical and form the common prefix. Blocks hold 16 tokens, or 5.243 MB of KV state across the node.
Math: Divide the remaining pool by bytes per block and round down, giving 90,292 usable blocks. An unshared request occupies 2,176 blocks (11.41 GB). Dividing the usable block count by that request count and rounding down gives 41 resident requests, down from the 48 of table 1 because each request also reserves its output allowance, the headroom is withheld, and allocation rounds to whole blocks. With sharing, subtract the common prefix’s 1,536 blocks (8.05 GB) once, then divide by 640 private blocks per request (3.36 GB). Rounding down gives 138 resident requests.
Systems insight: The common prefix covers 70.6 percent of each request’s blocks, and sharing it raises the fit 3.4×, close to the large-pool limit \(1/(1-\SharedPrefixFraction) \approx\) 3.4× for a shared fraction \(\SharedPrefixFraction\). In that limit, the gain depends on \(\SharedPrefixFraction\) alone, making prompt layout and the scope of sharing the primary architectural levers. A prefix shared only across one deployment’s instructions covers far less of each request than one that also spans a common workspace, as the archetype comparison below shows. Within a given scope, keeping invariant tokens at the very front of the serialized input, strictly ahead of any volatile turn history, maximizes \(\SharedPrefixFraction\). Although sharing does not reduce the decoding work per token or change any request’s logical context, it multiplies concurrent capacity. These values are physical fit bounds for the designated memory partition, not runtime admission limits.
The sharing gain \(1/(1-\SharedPrefixFraction)\) steepens as the shared fraction of each request grows.
In production environments, requests arrive with varied lengths and different degrees of prefix overlap. An admission controller must therefore balance committed blocks, anticipated generation growth, and temporary staging buffers required during KV transfers or eviction copies. Furthermore, an aggregate node-wide memory bound is necessary but not sufficient: multi-GPU deployments distribute KV cache blocks across tensor-parallel shards, meaning a free physical block on one accelerator cannot alleviate memory exhaustion on another. Admission decisions must satisfy physical capacity constraints across every individual device.
5.8.2 Residence time and service rate
A node that fits 41 unshared agent contexts in memory at once can still sustain fewer than one turn per second if every slot stays occupied across a 45 s integration test. A static fit bound counts only how many slots can exist in memory simultaneously; translating that capacity into sustainable throughput requires dividing by how long each request holds its slot, and classical queueing theory supplies the identity that links capacity, residence, and throughput.
Theorem 5.1: Occupancy equals rate times residence (Little's law)
In any stable system where items arrive, reside for a while, and leave, the long-run averages obey one identity, whatever the arrival pattern, service order, or residence distribution. Little’s law (Little 1961) states
\[\MeanSlotOccupancy = \ArrivalRate \MeanHoldTime \tag{7}\]
- Mean occupancy (\(\MeanSlotOccupancy\)): average number of items resident, here KV slots held.
- Throughput (\(\ArrivalRate\)): long-run arrival rate, equal to the completion rate when unfinished work does not accumulate.
- Mean residence (\(\MeanHoldTime\)): average time an item holds its slot, counting every phase in which the slot stays allocated.
A slot held in accelerator memory while an agent waits for external tool execution remains resident throughout that wait; omitting idle waiting time from \(\MeanHoldTime\) artificially deflates the denominator and drastically overstates sustainable system throughput.
The law’s generality has a price. Its proof assumes nothing about how items arrive or how long they stay, only that the long-run averages exist, and for that reason it fixes the mean occupancy and says nothing about the peak. A burst of arrivals, or residences that end together, can hold far more slots than \(\MeanSlotOccupancy\) for as long as the backlog lasts, so capacity is sized from the arrival and residence patterns, not from the mean identity alone.
Little, John D. C. 1961. “A Proof for the Queuing Formula: \(L = \lambda W\).” Operations Research 9 (3): 383–87. https://doi.org/10.1287/opre.9.3.383.
Rearranging the relation as \(\ArrivalRate = \MeanSlotOccupancy/\MeanHoldTime\) expresses the achievable service rate as a function of allocated capacity and residence duration. Here each resident item is one turn’s generation-and-tool-wait cycle, not a complete multi-turn trajectory. Let \(\ModelTime\) be the time a turn spends generating and \(\ToolTime\) the time it then waits on its tool. A slot kept through the wait resides for \(\ModelTime + \ToolTime\), while a slot released for the wait resides for \(\ModelTime\) alone, so for the same number of slots the two policies’ turn rates differ by the factor \(1 + \ToolTime/\ModelTime\). That factor is the residency tax of a synchronous tool wait, and notebook 5.4 prices it for the repair turn.
↪ Little’s law applied to whole multi-turn trajectories with tool waits is developed in Queueing for Trajectories.
Napkin Math 5.4: The residency tax of a tool wait
Problem: The node holds 41 unshared request slots. Each repair turn resides 5 s while generating and, under the keep policy, another 45 s while its integration test runs. What turn rate can memory sustain with the wait held resident, and with the slot released for the wait?
Math: By equation 7, \(\ArrivalRate = \MeanSlotOccupancy/\MeanHoldTime\). Keeping state through the wait gives \(\MeanHoldTime =\) 50 s and \(\ArrivalRate =\) 0.82 turns/s. Releasing the slot for the wait gives \(\MeanHoldTime =\) 5 s and \(\ArrivalRate =\) 8.2 turns/s. The ratio is \(1 + \ToolTime/\ModelTime\), or 10×.
Systems insight: Holding paused state through an idle tool wait penalizes the memory-bound turn rate by a factor of \(1 + \ToolTime/\ModelTime\). The economic viability of keeping state in accelerator memory depends on the ratio of wait duration to generation time, not the wait duration alone. Once the wait dominates, moving the state out to host memory, at a restoration latency of about 21 ms, becomes the better default whenever memory is contested. This same factor scales the memory term of every attempt’s cost, expanding \(\mathbb{E}[\AttemptCost]\) in equation 1.2 across the entire unevicted residence.
A kept slot is paid for across the whole cycle, rather than only while it generates.
The turn rate calculated from releasing slots is an ideal upper bound imposed strictly by memory capacity. In practice, prefill computation, state restoration bandwidth, PCIe bus contention, and scheduling queues introduce additional bottlenecks; compute throughput or interconnect bandwidth often saturates before memory is fully exhausted. Furthermore, if multiple trajectories share prefix blocks, those blocks remain pinned in memory even if one trajectory enters an idle wait.
Because Little’s law fixes only the mean, the residency calculation also hides the peaks that agent workloads produce. Tool executions frequently complete together, as in the correlated return burst of section 5.7.4, and tree-search agents fan out into many candidate paths at once, so instantaneous memory demand rises well above the average for as long as the burst lasts. Robust capacity planning must therefore stress-test the empirical distributions of prompt length, dynamic output expansion, search branching, and tool latencies against both device-level physical boundaries and strict service-level latency objectives.
These dynamics manifest differently across agent architectures. The software repair agent operates in a batch-like regime characterized by deep context windows and prolonged tool waits during test suite runs. By contrast, the customer support agent services numerous concurrent, short sessions where users wait interactively for low-latency responses. These contrasting profiles place divergent demands on the key-value pool and require distinct sharing and retention strategies.
Lighthouse 5.1: Attention-state residency by archetype
Table 5 puts the repair agent beside a support agent on the same node and pool. Both deployments share a 6,144-token prefix of system prompt and tool schemas across all their sessions; that prefix carries no customer or repository data, so isolation permits sharing it across sessions. The scope is narrower than in notebook 5.3, where repair workers on one repository snapshot also share their workspace state. The support agent’s inputs are scenario values, not measurements.
Table 5: Residency by archetype: Payload fits use the unrounded KV pool of table 1 without headroom or output allowance, so they exceed the block-rounded bounds computed earlier; resume times use the node’s host links and sustained prefill rate from the paused-state comparison.
| Quantity | Repair agent | Support agent |
|---|---|---|
| Retained tokens per session | 32,768 | 8,192 |
| Shared fraction of each session | 18.8% | 75% |
| Resident sessions, unshared | 48 | 195 |
| Resident sessions, prefix shared | 60 | 780 |
| Generation, then idle wait per turn | 5 s, then 45 s test | 2 s, then 20 s reply |
| Residency tax if kept | 10× | 11× |
| Resume by reload vs. recompute | 21 ms vs. 1.3 s | 5 ms vs. 0.32 s |
| Who waits on the resume | The harness, behind a long test | A customer, for the first token |
Systems insight: Prefix sharing yields dramatically asymmetric benefits across these two archetypes. Sharing the common prompt prefix expands the support agent’s resident session capacity 4×, yet yields only a 1.25× expansion for the repair agent, because the shared prefix constitutes a far larger fraction of each support session’s total context. Repair sessions recover a large sharing gain only when the scope widens to a common workspace, which raised the fit 3.4× in the capacity notebook. While both workloads pay a similar residency tax, the optimal pause policy diverges based on who waits for the resume. The repair agent should migrate its state to host memory during tests, as the regime analysis of figure 6 recommends, and it can fall back to dropping the state when host memory is tight, since recomputation adds only 2.6 percent to a 50 s turn cycle where an automated test harness waits. In contrast, the support agent should keep or move its state and avoid dropping it, because recomputation lands directly in front of an interactive user as added delay to the first token. For support workloads, the decision that matters most is therefore what happens to each session’s private history beyond the shared prefix. Rebuilding that history is what the customer waits for, so keeping or moving it, not enlarging the shared prefix, protects the first token.
5.8.3 KV pool telemetry
A single aggregate metric such as occupied pool fraction cannot distinguish healthy, amortized caching from an impending allocation failure. A memory pool at high utilization composed mostly of discardable dormant prefixes can easily admit a new request through cheap reclamation. Conversely, that same utilization level with all blocks pinned by active decoding leaves no headroom for context expansion. Table 6 establishes the physical categories required to interpret these operational states.
| Pool state | Accounting and consequence |
|---|---|
| Active or pinned | Count each physical block once, even when several requests reference it. It cannot be reclaimed while any required owner or operation still uses it. |
| Reserved or in flight | Count additional blocks unavailable for admission because they are reserved or being populated, copied, or transferred. Exclude blocks already counted as active or pinned. |
| Reclaimable dormant cache | Count retained blocks that have no required active or in-flight use and can be discarded under the service’s policy. Reclaiming them can remove a future reuse opportunity. |
| Genuinely free | Count blocks immediately available to allocate, with no live owner, unfinished operation, or reservation. |
Evaluating blocks in this strict order ensures that every physical block belongs to exactly one state at any given instant. For instance, while a paused trajectory’s private blocks are being copied out to host memory, each source block stays in the first row, pinned by the transfer that still reads it, and becomes reclaimable only when the copy completes. On the return trip, the device blocks allocated to receive the reload sit in the second row until the transfer lands. Similarly, a dormant prefix is reclaimable only when all dependent references and asynchronous operations have cleared. This taxonomy exposes true admission capacity without double-counting shared blocks or assuming that eviction requests free memory instantaneously.
Physical pool accounting provides only the static half of the operational picture; it must be coupled with continuous telemetry on throughput, work volume, and latency. A production telemetry pipeline should record offered request rates, prompt and completion token volumes, the token-weighted prefix hit rate of equation 2, eviction and restoration bandwidth, recomputed tokens, and the distribution of tool wait and resumption intervals. Operators must evaluate these metrics alongside concrete latency targets: admission delay in the scheduling queue, time to first token, inter-token latency, and state resumption delay. Hit rates in isolation can mislead. A high reuse fraction can coexist with long scheduling queues, while high eviction counts may be entirely benign if the discarded prefixes represent cold sessions that will never be queried again.
The definitive signature of memory thrashing is cache churn: the rapid cycle of evicting blocks only to reload or recompute them shortly thereafter.8 When cache churn coincides with degrading tail latency or falling completed work under sustained offered load, it signals that the aggregate working set of active trajectories has overrun physical memory capacity. Resolving this collapse requires adjusting admission policies, offload thresholds, or scheduling priorities. Because the critical memory occupancy threshold at which churn begins varies across allocators and workload compositions, operators must correlate physical pool states with queue dynamics rather than relying on a static utilization ceiling. Furthermore, this diagnostic boundary matters across system layers: client applications consuming remote API endpoints observe only black-box latency and error codes, whereas infrastructure operators have access to the physical block states, page tables, and transfer telemetry required to perform root-cause remediation. Coupling resident-fit bounds with telemetry across those block states lets operators see which KV blocks must stay pinned, which can be reclaimed or offloaded, and what restoration delay each choice adds to end-to-end execution.
8 Thrashing: Multiprogrammed virtual-memory systems of the 1960s encountered this exact pathology: when the aggregate working sets of resident programs exceeded main memory, page faults forced continuous eviction of recently used pages, and processors spent their execution cycles servicing I/O rather than executing instructions (Denning 1968b). The solution was explicit load control: restricting the multiprogramming level until the working sets of admitted programs fit comfortably in physical memory. In agentic KV cache serving, the corresponding remedy is admission control against the retained state of active trajectories, rather than tuning eviction algorithms to page faster.
Denning, Peter J. 1968b. “Thrashing: Its Causes and Prevention.” Proceedings of the Fall Joint Computer Conference, Part i (AFIPS ’68), 915–22. https://doi.org/10.1145/1476589.1476705.
Checkpoint 5.2: Fit, pressure, and completed work
Two runs report the same occupied fraction, but one holds mostly dormant prefixes and the other holds mostly active state.
5.9 Fallacies and Pitfalls
Most KV-cache failures in production agent deployments come from two mistakes: treating an instantaneous memory-fit count as a throughput guarantee while idle tool waits hold slots for tens of seconds, or treating a fast prefix-cache hit as proof that the underlying environment state is still current. Each fallacy and pitfall below pairs the failure mode with its concrete cost on the reference node.
Fallacy: Model size, not retained context, decides how many sequences a node can serve.
Static model weights consume a fixed footprint allocated at initialization, leaving a 526.0 GB pool dedicated to dynamic attention state on the reference node. While model parameters establish the initial baseline headroom, the active context length of running sequences overwhelmingly governs dynamic memory consumption. Holding the model constant, that memory pool accommodates 195 unshared sequences when context is kept to 8,192 tokens, but capacity plunges to just 12 concurrent sequences once context expands to 131,072 tokens (section 5.2). Retained context length serves as the primary operational lever governing system concurrency, and the agent harness dictates that length through its prompt construction, tool history, and conversation buffering. Swapping in a smaller model only increases concurrent serving capacity to the extent that it reduces the per-token memory footprint \(\KvCacheBytesPerToken\) or frees up additional accelerator memory for the KV pool.
Pitfall: Reserving every request’s maximum context.
Allocating contiguous memory upfront for each request’s worst-case context length severely throttles system throughput through internal fragmentation. When a serving system sizes every slot for a 32,768-token cap while requests average a final length of only 2,048 tokens, barely 6.25 percent of the allocated memory actually holds valid attention state upon completion. Under this static reservation regime, the reference pool can admit only 48 concurrent sequences. In contrast, paged virtual memory allocation dynamically allocates physical blocks on demand, giving the final-length snapshot estimate of approximately 780 over the same physical memory (section 5.4). Systems should allocate memory blocks incrementally as tokens arrive during prefill and generation, reserving the output allowance the admission controller promises, as the capacity notebook does, rather than the full context cap.
Fallacy: Compatible cached attention state proves that its evidence is current.
Prefix caching operates strictly at the level of token identifiers and model configurations, without semantic awareness of environment state or external reality. On the reference node, a prefix match on the agent repair loop’s 4,096-token invariant prompt saves roughly 169 ms of prefill computation per turn (section 5.5). The inference engine achieves that speedup regardless of whether those cached tokens reflect stale diagnostics from revision 17 (r17) or up-to-date observations from the current repository source. Prefix match compatibility only confirms that the token sequence and attention architecture match bit-for-bit. Determining whether an earlier r17 failure supports a claim about revision 18 (r18) requires semantic validation in the agent harness before serializing the prompt. Updating the prompt with fresh r18 observations breaks prefix reuse at the first modified token and forfeits part of that computational saving. That forfeited saving is the correct price of grounding the next decision in current evidence (principle 6). Under that principle, no cached, staged, or derived copy supersedes the designated source for the claim it represents, which here is the repository at r18.
↪ Every staged or cached claim is validated against a designated source of record, whose role is developed in Record roles.
Pitfall: Always moving paused state out of accelerator memory.
Blindly offloading KV cache blocks to host memory whenever an agent pauses to execute an external tool wastes interconnect bandwidth and inflates resumption latency. Evacuating the 10.74 GB attention state for a paused repair agent requires 42 ms of link transfer, which adds 21 ms of overhead before the model can resume generation. When the memory pool contains plenty of free blocks, this offload latency provides zero benefit to the system. Conversely, under heavy contention, offloading that same state frees valuable high-bandwidth accelerator memory for 44.98 s across an extended 45 s tool invocation (section 5.7). Serving schedulers must evaluate eviction dynamically based on uniquely reclaimable blocks, active queue pressure, and expected resumption deadlines. An external tool call marks an opportunity for scheduling decisions rather than an automatic eviction trigger.
Fallacy: A resident-fit count is a throughput guarantee.
Calculating how many concurrent request snapshots fit into physical accelerator memory establishes an instantaneous capacity limit, not a sustained throughput guarantee. The reference node fits 41 unshared repair trajectories in memory simultaneously. However, if those sessions hold their memory allocations across an idle 45 s tool pause, the node sustains a maximum of only 0.82 turns/s from memory alone. If the engine instead releases those memory slots during the pause, the memory-only throughput bound rises to 8.2 turns/s (notebook 5.4). Memory fit dictates maximum concurrency (\(\MeanSlotOccupancy\)), but Little’s law (\(\MeanSlotOccupancy = \ArrivalRate \MeanHoldTime\)) dictates that arrival throughput (\(\ArrivalRate\)) is governed equally by mean residence time (\(\MeanHoldTime\)). When agent turns involve long execution pauses or queueing delays, residence time inflates and throughput collapses even though memory looks full. Occupancy stays high, but most of the resident state is idle, so the turn rate is low. Schedulers must validate admission against offered traffic distributions, burst arrivals, and latency targets rather than relying on static slot counts.
Pitfall: Treating KV storage as the authoritative task record.
The KV cache is a hardware-bound optimization artifact, not a durable system of record. Dropping the 10.74 GB repair state from accelerator memory costs approximately 1.3 s of prefill compute to rebuild from raw tokens, and it forfeits zero evidence needed by the task. Retaining or serializing KV cache tensors merely preserves intermediate, activation-level computation tied to a specific hardware layout, model architecture, and numerical precision. It does not record the authoritative code revisions, environment observations, or validation evidence that govern an agent’s task progression. Systems must persist trajectory history, tool outputs, and verification state in a durable application runtime. The KV cache should always be treated as an ephemeral, recomputable cache over that authoritative token log, reproducible up to floating-point differences across distinct implementations.
5.10 Summary
Retained key-value (KV) attention state is a cache of intermediate computation. Like any cache, its cost has two parts, capacity and residency. Capacity is the bytes it occupies in high-bandwidth memory, which grow with the model’s tensor geometry and the active sequence length. Allocation decides how many of those bytes do useful work, since coarse blocks strand bytes in internal fragmentation and branches that do not share a common prefix store it twice. Residency is how long a sequence holds those bytes. It is what turns capacity into throughput, because an agent blocked on a tool call still occupies accelerator memory, and every byte it holds is a byte another request cannot use. Every memory management policy examined in this chapter (paged block tables, tree-based prefix eviction, offloading, and recomputation) trades memory footprint against recomputation work and scheduling delay. Cache mechanisms manage physical storage, but they cannot assess whether cached tokens remain semantically valid; context validity stays the responsibility of the agent harness and the context it supplies. Table 7 summarizes the primary analytical relations used throughout this chapter to size, share, schedule, and reclaim key-value cache storage.
| Equation | What it bounds or decides | Where derived |
|---|---|---|
| \(\KvCacheBytesPerToken = 2 \cdot \LayerCount \cdot \KvHeadCount \cdot \AttentionHeadDimension \cdot \ElementStorageSize\), \(\; \KvCacheMemory = \SequenceLength \cdot \KvCacheBytesPerToken\) | Bytes retained per token and per sequence; retained sequence length serves as the primary capacity driver | equation 1 |
| \(0 \le \KvBlockTailWaste \le \KvBlockSize - 1\) | Per-sequence internal fragmentation slack in paged allocation; dictates the capacity impact of block size \(\KvBlockSize\) | section 5.4 |
| \(\PrefixHitRate = \sum_{i} \ReusedPrefixLength^{(\WorkloadRequestIndex)} / \sum_{i} \PromptLength^{(\WorkloadRequestIndex)}\) | Effective prefix hit rate: the proportion of prompt tokens served directly from reusable cached state | equation 2 |
| \(\sum_{i} \PrefillAllocatedTokenCount_i + \lvert\DecodeRequestSet\rvert \le \IterationTokenBudget\) | Chunked prefill admission budget alongside active decodes; controls inter-token generation latency | equation 3 |
| \(\KvReloadTime / \KvRecomputeTime = \KvCacheBytesPerToken \AttainableComputeRate / (2 \Parameters \, \HostLinkBandwidth)\) | Crossover ratio determining whether paused state is restored faster via interconnect reload or local recomputation | equation 4 |
| \(\KvPoolMemory = \NodeHbmCapacity - \WeightMemory - \RuntimeReserveMemory\) | Dynamic high-bandwidth memory available for the KV cache pool after allocating model weights and runtime workspace | equation 5 |
| \(\lceil \SharedPrefixLength/\KvBlockSize \rceil + \BatchSize \lceil (\SequenceLength + \OutputLimit - \SharedPrefixLength)/\KvBlockSize \rceil \le \lfloor (1-\KvPoolHeadroomFraction) \KvPoolMemory / (\KvBlockSize \, \KvCacheBytesPerToken) \rfloor\) | Maximum resident concurrency \(\BatchSize\) under block quantization, memory headroom, and a shared prefix | equation 6 |
| \(1/(1-\SharedPrefixFraction)\) | Theoretical upper bound on capacity gain from prefix sharing in large memory pools with shared fraction \(\SharedPrefixFraction\) | section 5.8.1 |
| \(\MeanSlotOccupancy = \ArrivalRate \MeanHoldTime\) | Turn throughput sustained by a fixed pool of resident slots (via Little’s law) | equation 7 |
| \(1 + \ToolTime/\ModelTime\) | Residency tax factor: capacity lost when sequences occupy memory slots during idle tool waits | section 5.8.2 |
Key Takeaways: Managing derived attention state
- Retained length is the capacity knob: With model weights occupying a static allocation, resident capacity scales inversely with retained sequence length, falling from 195 sequences at 8,192 tokens down to 12 sequences at 131,072 tokens on the reference node. A context length that easily satisfies the model architecture’s maximum context window can still quickly exhaust the serving node’s physical memory pool.
- Physical blocks, not logical references, consume capacity: Paged attention rounds private sequence state up to fixed-size blocks, whereas identical prefix sequences share physical blocks through reference counting. Reclaiming a finished trajectory frees only those physical blocks whose reference count drops to zero, ensuring active sequences and asynchronous transfer operations remain protected.
- Prefix reuse requires both structural compatibility and memory availability: Matching token prefixes permit KV cache reuse only when the corresponding physical blocks remain resident and accessible under tenant-isolation rules. A cache hit guarantees neither the freshness of underlying external data nor the semantic validity of the trajectory; preserving cache affinity must never prevent an agent harness from invalidating stale context.
- Retention policies and compute schedulers manage complementary resources: Chunked prefill schedules incoming prompt tokens alongside active decodes to prevent high latency spikes during token generation. Similarly, each way of handling a paused agent trajectory (retaining its blocks in accelerator memory, offloading them to host RAM or secondary storage, or recomputing them on demand) exchanges memory footprint for interconnect bandwidth and resumption latency. The optimal strategy depends on the link bandwidth and the expected wait duration.
- Idle tool waits impose a severe residency tax on throughput: Static resident-fit bounds govern instantaneous occupancy rather than sustained request throughput. Holding physical cache blocks resident while an agent waits on external tools or human feedback depresses sustainable turn throughput by the residency tax factor \(1 + \ToolTime/\ModelTime\). Production admission and eviction policies must therefore optimize for end-to-end task completion rates and tail latency rather than raw accelerator memory utilization.
Attention state derived from the token prefix (principle 5) enables the serving engine to reuse previous computation rather than evaluating redundant prompt tokens. Precise block tracking and residency accounting quantify the trade-off between retaining that state and freeing high-bandwidth memory for active generation. Throughout these optimizations, authority stays with the source (principle 6): an inexpensive continuation never justifies serving an obsolete observation when the underlying system or environment has changed.
5.11 Historical Perspective and Further Reading
Almost every memory management technique in this chapter resolves an architectural problem that time-sharing operating systems encountered decades ago. When early programs outgrew physical core memory, the Manchester Atlas one-level store introduced paging (Kilburn et al. 1962): an address translation table mapped a program’s contiguous virtual address space onto scattered physical page frames, freeing programmers from managing manual overlays and allowing memory to allocate without contiguous physical reservations. Decoupling virtual addresses from physical layout promptly exposed new systems trade-offs. Randell (1969) formalized the distinction between internal fragmentation (storage lost inside rounded-up allocations) and external fragmentation, where free memory sits stranded between allocations. Belady (1966) demonstrated that optimal offline page replacement requires clairvoyant knowledge of future memory references, establishing that practical online policies must rely on heuristics. When memory pressure mounted, time-sharing systems routinely collapsed into thrashing, spending virtually all cycles swapping pages rather than executing user code. Denning’s working-set model clarified the dynamics of this failure and proved that the only dependable remedy was admission control: admitting fewer concurrent processes rather than swapping pages more aggressively (Denning 1968a, 1968b). Operating systems also pioneered fine-grained memory sharing. The TENEX system introduced copy-on-write sharing so that multiple processes could reference identical pages safely until one attempted a mutation (Bobrow et al. 1972), while Morrison’s PATRICIA trees indexed strings through shared prefixes (Morrison 1968). Denning (1970) gathered these foundations into the virtual-memory discipline that computer systems curricula teach to this day.
Kilburn, Tom, David B. G. Edwards, Michael J. Lanigan, and Frank H. Sumner. 1962. “One-Level Storage System.” IRE Transactions on Electronic Computers EC-11 (2): 223–35. https://doi.org/10.1109/TEC.1962.5219356.
Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. “Attention Is All You Need.” Advances in Neural Information Processing Systems (NeurIPS) 30: 5998–6008.
Modern inference serving collided with these identical capacity limits when the autoregressive Transformer architecture made each generated token attend to key and value tensors from all prior tokens (Vaswani et al. 2017). Early efforts mitigated this growth by modifying the neural network architecture itself. Multi-query attention (Shazeer 2019) and grouped-query attention (Ainslie et al. 2023) reduced the memory footprint by sharing key-value heads across multiple query heads. In parallel, Pope et al. (2023) developed an analytical framework showing that accelerator memory capacity and memory bandwidth, rather than floating-point compute throughput, impose the primary bottleneck on context length and batch concurrency.
Subsequent innovations in serving systems recapitulated the operating-systems lineage directly. Orca introduced iteration-level scheduling, enabling fine-grained preemption and dynamic batching where requests join and leave running batches on individual token boundaries (Yu et al. 2022). PagedAttention adapted classical virtual paging directly to key-value cache management, using block tables and copy-on-write mechanisms to eliminate external fragmentation and reclaim the memory previously wasted by reserving contiguous worst-case sequence lengths (Kwon et al. 2023). SGLang introduced radix-tree prefix caching with leaf-first eviction, enabling structural cache reuse across independent requests that share common system prompts or few-shot exemplars (Zheng et al. 2024). To prevent lengthy prompt ingestions from stalling generation, Sarathi introduced chunked prefill, bounding the latency spikes that prefill operations impose on active decode iterations (Agrawal et al. 2023). Finally, DistServe and Splitwise extended this decoupling across physical hardware nodes through phase disaggregation, placing the prefill and decode stages on separate, specialized worker pools (Patel et al. 2024; Zhong et al. 2024).
Yu, Gyeong-In, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. 2022. “Orca: A Distributed Serving System for Transformer-Based Generative Models.” 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), 521–38.
Agrawal, Amey, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, and Ramachandran Ramjee. 2023. “SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills.” arXiv Preprint arXiv:2308.16369, August.
Patel, Pratyush, Esha Choukse, Chaojie Zhang, Aashaka Shah, Íñigo Goiri, Saeed Maleki, and Ricardo Bianchini. 2024. “Splitwise: Efficient Generative LLM Inference Using Phase Splitting.” 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA), 118–32. https://doi.org/10.1109/isca59077.2024.00019.
Zhong, Yinmin, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. 2024. “DistServe: Disaggregating Prefill and Decoding for Goodput-Optimized Large Language Model Serving.” 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), July, 193–210.
Gao, Bin, Zhuomin He, Puru Sharma, Qingxuan Kang, Djordje Jevdjic, Junbo Deng, Xingkun Yang, Zhou Yu, and Pengfei Zuo. 2024. “Cost-Efficient Large Language Model Serving for Multi-Turn Conversations with CachedAttention.” 2024 USENIX Annual Technical Conference (USENIX ATC 24), 111–26.
Qin, Yeqi, Yufan Shen, Zeyu Shi, Chen Sun, Wei Wang, Xiao Wang, Xiaobo Wang, et al. 2024. Mooncake: A KVCache-Centric Disaggregated Architecture for LLM Serving.
Xiao, Guangxuan, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. 2024. “Efficient Streaming Language Models with Attention Sinks.” International Conference on Learning Representations (ICLR).
Zhang, Zhenyu, Sheng Shen, Derek Zhiyuan Cheng, Xingli Dong, and Kurt Keutzer. 2023. “H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models.” Advances in Neural Information Processing Systems (NeurIPS) 36.
Agent workloads introduce the memory dilemma at the center of this chapter: execution state that idles during tool execution and subsequently resumes. When an agent invokes an external tool, its execution thread pauses while waiting for external API responses or environment feedback. During this idle window, the retained KV cache ties up expensive accelerator high-bandwidth memory. Work on tool interception formalized this challenge by framing KV cache lifecycle management around three primary operations: keeping the state resident in device memory, swapping it to host memory or storage, or dropping it entirely to recompute upon resumption (Abhyankar et al. 2024). This trade-off balances idle memory capacity against host-to-device transfer bandwidth and compute recomputation costs. Multi-turn serving systems such as CachedAttention and Mooncake expanded this design space into multi-tier memory hierarchies, paging dormant KV caches out to host DRAM and disaggregated solid-state storage clusters (Gao et al. 2024; Qin et al. 2024). Lossy approximation techniques pursued an alternative path, trading mathematical fidelity for reduced memory footprints through attention sinks (Xiao et al. 2024) and score-based eviction policies (Zhang et al. 2023). However, whether lossy cache approximation can reliably preserve the intricate, long-range dependencies required across extended agent trajectories remains an open systems and modeling challenge.
For readers seeking to trace the lineage from classical memory management to agent serving infrastructure, six works are especially illuminating:
- Denning (1970) provides the foundational survey of paging, replacement algorithms, and locality of reference, showing how modern KV-cache management problems mirror classical virtual memory challenges transposed onto a new architectural storage unit.
- Denning (1968a) introduces the working-set model, establishing the formal link between program locality and resource allocation. It provides the theoretical foundation for admission control, explaining why multi-tenant model servers must reject or queue requests when aggregate memory demand exceeds physical accelerator capacity.
- Pope et al. (2023) develops an analytical model for large-model inference, demonstrating rigorously how attention head sharing, tensor partitioning, and memory bandwidth dictate whether a deployment is bounded by arithmetic throughput or memory capacity.
- Kwon et al. (2023) introduces PagedAttention, adapting classical operating system paging, virtual block tables, and copy-on-write mechanisms to eliminate KV cache fragmentation in serving engines. It serves as an exemplary case study in translating classical systems principles to modern accelerator architectures.
- Zheng et al. (2024) structures prompt cache management through radix trees, treating token prefix reuse as a first-class scheduling and eviction problem in multi-turn and agentic serving workloads.
- Abhyankar et al. (2024) formalizes the tool-wait problem in agent workloads, quantifying the engineering trade-offs among retaining, swapping, and discarding KV cache state during external tool execution.
Denning, Peter J. 1970. “Virtual Memory.” ACM Computing Surveys 2 (3): 153–89. https://doi.org/10.1145/356580.356581.
Denning, Peter J. 1968a. “The Working Set Model for Program Behavior.” Communications of the ACM 11 (5): 323–33. https://doi.org/10.1145/363095.363141.
Kwon, Woosuk, Zhuohan Li, Siyuan Zhuang, et al. 2023. “Efficient Memory Management for Large Language Model Serving with Pagedattention.” Proceedings of the 29th Symposium on Operating Systems Principles, 611–26.
Zheng, Lianmin, Liangsheng Ying, Zhenghao Yin, Cody Hao Liu, Eric Yu, Prakhar Patel, Zhipeng Yang, Anthony K. Joseph, and Ion Stoica. 2024. “SGLang: Efficient Execution of Structured Language Model Programs.” arXiv Preprint arXiv:2312.07104, ahead of print. https://doi.org/10.48550/arXiv.2312.07104.
Abhyankar, Reyna, Zijian He, Vikranth Srivatsa, Hao Zhang, and Yiying Zhang. 2024. “InferCept: Efficient Intercept Support for Augmented Large Language Model Inference.” Proceedings of the 41st International Conference on Machine Learning (ICML), Proceedings of machine learning research, vol. 235: 81–95.
5.12 Exercises
Unless a problem states otherwise, use the hypothetical reference deployment in table 8. Its values are problem inputs chosen for round arithmetic, not measurements of any system. Take GB as \(10^9\) bytes, count \(2\Parameters\) weight operations per processed token, and model one engine iteration over \(\ForwardPassTokenCount\) token positions with the chapter’s weight-only estimate, \(\WeightOnlyStepTime(\ForwardPassTokenCount) = \max\left(5\;\text{ms},\; 2 \Parameters \ForwardPassTokenCount / \AttainableComputeRate\right)\).
| Quantity | Symbol | Given |
|---|---|---|
| Model parameters | \(\Parameters\) | \(50 \times 10^{9}\) |
| Layers, key-value heads, head dimension | \(\LayerCount\), \(\KvHeadCount\), \(\AttentionHeadDimension\) | 48, 8, 128 |
| Bytes per stored KV element | \(\ElementStorageSize\) | 2 |
| KV pool after weights and runtime reserve | \(\KvPoolMemory\) | 400 GB |
| Sustained prefill rate | \(\AttainableComputeRate\) | \(2 \times 10^{15}\) operations/s |
| Weight-read floor of one iteration | 5 ms | |
| Aggregate host-link bandwidth, each direction | \(\HostLinkBandwidth\) | 400 GB/s |
1. Sizing retained state for a session target (Basic). An operator must hold 200 unshared sessions resident at once, each retaining 16,384 tokens.
- Compute \(\KvCacheBytesPerToken\) from equation 1, the payload \(\KvCacheMemory\) of one session, and the resident-fit bound in the pool.
- A multi-head variant of the same model stores 64 key-value heads per layer instead of 8. Compute its fit, and explain why no allocator policy can recover the difference.
- Two proposals would meet the target: storing KV at one byte per element, or having the harness cap retained context. Find the longest retained length that meets the target at two bytes per element. Then argue which proposal to try first and what evidence each must produce before it ships.
2. When paging pays (Basic). Static reservation sizes every request for a cap of 8,192 tokens. The request population’s mean final length is 3,072 tokens.
- What fraction of a reservation holds state at completion, and how many reservations fit in the pool?
- Paged allocation uses 32-token blocks, and final lengths have uniformly distributed remainders modulo the block size. Estimate the mean tail waste per sequence, its share of allocated KV memory, and the final-length snapshot count estimated by dividing the pool by the mean allocation. Repeat for 256-token blocks. Does this estimate alone determine live admission capacity?
- If the mean final length rose to 7,000 tokens under the same cap, how much of paging’s capacity advantage over static reservation would remain? Name one benefit of block allocation that does not depend on the length distribution.
3. Moving one field (Basic). A session sends four requests of 6,000 prompt tokens each. The first 4,500 tokens are invariant instructions and tool schemas, except for a request timestamp serialized after the first 300 tokens. The service reuses only complete 256-token blocks; the first request finds nothing cached, and each later request finds the earlier state resident, compatible, and permitted.
- Compute \(\PrefixHitRate\) from equation 2 over the four requests.
- Recompute it after the harness moves the timestamp to follow the invariant prefix.
- For layout (b), how much weight-only prefill does each hit avoid, and how much more would a service that also reuses partial tail blocks avoid? Which change should the team make first?
4. Choosing a chunk budget (Intermediate). Forty-eight requests are decoding when an 8,000-token uncached prompt arrives.
- If the engine runs the prompt as one unit, what gap between tokens do the ongoing decodes see?
- The ongoing streams must see at most 25 ms between tokens. Using equation 3 with one position per decode, find the largest budget \(\IterationTokenBudget\) and chunk size that meet the target, the number of iterations the prompt needs, and the time until its prefill completes.
- Ignoring the smaller final chunk, show that prefill completion is approximately \(\left(2 \Parameters \UncachedPromptLength/\AttainableComputeRate\right) \cdot \Time / \left(\Time - 2 \Parameters \lvert\DecodeRequestSet\rvert / \AttainableComputeRate\right)\) for an inter-token target \(\Time\) above the weight-read floor, where \(\UncachedPromptLength\) is the uncached prompt length. Find the tightest \(\Time\) that still completes the prompt within 500 ms.
- Explain why a target approaching \(2 \Parameters \lvert\DecodeRequestSet\rvert / \AttainableComputeRate\) is unworkable, and propose a design change for a service whose streams need 8 ms between tokens while new prompts need their prefill within 500 ms.
5. Reload, recompute, and a return burst (Intermediate).
- Evaluate equation 4 for the reference deployment. How much faster is reload than recomputation, and why does the answer not depend on retained length?
- Below what sustained link bandwidth would recomputation become the faster way back?
- Forty paused sessions of 32,768 tokens each return at the same instant. Compute each session’s state, its isolated reload time, the reload completion time of the last session when reloads share the full aggregate link rate, and the time to recompute all forty sequentially from weight work alone.
- Each returning session must be restored within 250 ms. How many of the forty meet that target if reloads share the link fairly, and how many if they are served one at a time in arrival order at the full link rate? Propose two design changes that would serve the rest.
6. Shared prefix and residence time (Intermediate). Requests carry 24,576 prompt tokens and an output allowance \(\OutputLimit = 1{,}024\). A block-aligned common prefix of 16,384 tokens is compatible and shareable across all of them. Blocks hold \(\KvBlockSize = 16\) tokens, and the planner withholds headroom \(\KvPoolHeadroomFraction = 0.10\). Each turn generates for 4 s and then waits 36 s for a tool.
- Using equation 6, compute the usable blocks and the resident-fit bound without and with sharing. Compare the gain with \(1/(1-\SharedPrefixFraction)\).
- The operator wants memory to sustain 10 turns/s. Using the shared fit and equation 7, what rate does keeping state through the wait sustain, and how many resident slots would the target require under that policy?
- Instead, each paused turn moves its private blocks to host memory and reloads them when the tool returns, while the common prefix stays resident for the other requests. Compute the memory-bound rate, the host-link traffic at 10 turns/s, and the restoration delay per turn. Is the link the binding resource?
7. Fan-out over a shared source bundle (Advanced). The research agent retrieves a 60,000-token bundle of source documents and fans the question out to 12 workers. Each worker’s input is the bundle followed by a 2,000-token private instruction, and each may generate up to 3,000 tokens. A synthesis call then reads the bundle followed by all 12 worker outputs. Ignore block rounding and headroom.
- A contiguous allocator deep-copies the bundle’s state into every worker. How much KV state does it copy? Compute the KV footprint of one question with and without block sharing, and how many questions each policy keeps resident in the pool.
- A developer serializes each worker’s private instruction before the bundle so that the model reads its task first. What happens to the shared footprint in (a), and what layout serves both goals?
- For the synthesis call, how much weight-only prefill does a hit on the bundle avoid, and how much new prefill remains? Contrast the constraint that binds this workload with the one that binds the repair agent in this chapter.
- A platform team proposes reusing the bundle’s KV state across different users’ questions that retrieve the same documents. State the conditions under which that reuse is compatible, available, and permitted, and explain why a hit says nothing about whether the documents are current or trustworthy.
8. Paused state through a human approval (Advanced). The remediation agent proposes a production change and waits for human approval. During a major incident, 60 trajectories await approval at once. Each retains 20,000 tokens: an 8,000-token invariant prefix, identical and shareable across trajectories, followed by 12,000 tokens of incident-specific diagnostics. Each turn generates for 6 s, approval takes 10 minutes, and the host can hold 1 TB of parked state.
- Under the keep policy, what share of the pool do the 60 trajectories hold without sharing and with the prefix shared, and what residency tax does the approval wait impose?
- Suppose the private blocks move to host memory and the shared prefix stays resident. Compute the host footprint, and compare the time to restore 20 trajectories whose approvals arrive together by reload with the time to recompute their private regions sequentially.
- Before acting on an approval, the harness must re-observe production state (principle 6), and the refreshed observations replace the diagnostics from token 8,000 onward. How much of the parked state remains usable? Recommend a paused-state policy, and say how the recommendation changes if refreshed observations were only appended after the existing diagnostics.
- Compared with the repair agent, what binds this workload, and how large is its restoration cost relative to the wait?
What’s Next: From reusable computation to durable information
Dropping the r18 request’s attention state forfeits no evidence, because the serving engine can rebuild it from the token log. The repair’s next session still needs that evidence once this serving session ends: the candidate at r18, the r17 failure, the passing reproducer, and the integration checks that remain unresolved. KV state can itself be moved or serialized, so storage location alone does not separate a cache from a memory. The unresolved problem is which information should persist, how it is identified and updated as its sources change, and how a later session retrieves evidence appropriate to its task. Long-Term Memory develops that durable-information contract.