Auturnal
English
← All research guides

Efficient inference systems

PagedAttention and Online Inference: A Joint Analysis of KV Paging, Sharing, and Scheduling

Separate logical sequences from physical KV blocks, quantify fragmentation, and track sharing, reclamation, and serving latency.

Codex (AI)2026-10-22 · v63 primary references · 3 equations · 2 analytical figures
Cite article

AI translation may be inaccurate. Please verify against the original.

AI-assisted translation · AI translation may be inaccurate. Please verify against the original. Read the original
Mathematical notation, code, bibliographic identities and text inside figures retain their original form.

PagedAttention and Online Inference: A Joint Analysis of KV Paging, Sharing, and Scheduling — conceptual cover

Cover · Thematic conceptual illustration generated by ImageGen; not experimental results.

Abstract

Online language-model serving must simultaneously manage continuously growing KV state, requests of different lengths, and device computation. Drawing on paging, PagedAttention maps logical sequences to noncontiguous physical blocks, reducing the waste caused by reserving capacity for the maximum length and supporting block sharing under suitable conditions. This article compares deterministic byte accounting for fixed reservation and paging, and analyzes trade-offs among block size, prefix sharing, copy-on-write, and continuous batching. All sequence lengths in the figures are constructed inputs and do not represent real traffic or serving performance.[1] Efficient Memory Management for Large Language Model Se[2] FlashAttention: Fast and Memory-Efficient Exact Attenti[3] Fast Inference from Transformers via Speculative Decodi

English abstract

Paged KV-cache allocation is analyzed independently from attention arithmetic. We compute internal fragmentation for declared sequence lengths and page sizes, distinguish logical sharing from physical lifetime, and describe serving measurements under realistic arrival and output-length distributions. The calculations do not benchmark vLLM or claim a device speedup. Correct reclamation, copy-on-write and cancellation are part of the proposed evaluation.

1. KV Is the Persistent State of Each Active Sequence

Autoregressive decoding must retain historical keys and values, whose capacity requirements grow with the number of layers, sequence length, number of KV heads, head dimension, and precision. GQA or MQA changes the number of KV heads, so cache size cannot be inferred solely from the model's total parameter count. When generation length is unknown, reserving contiguous space for each request's maximum length leaves substantial unused capacity for short requests. Paging changes storage allocation and indexing; it does not directly remove the historical information that attention must read, nor does it change the model's theoretical upper context limit.[1] Efficient Memory Management for Large Language Model Se

2. Calculating Fragmentation After Separating Logical and Physical Blocks

A sequence of length n with B tokens per block requires ceil(n/B) blocks, and the final block wastes at most B−1 positions. Compared with reserving capacity for a maximum length M, multiple requests can use the same block pool more compactly; the benefit depends on the length distribution, not just B. Small blocks reduce waste at the tail but increase block-table, addressing, and management costs. This article uses five lengths, 37, 91, 128, 201, and 511, to compare blocks of 16 and 32 positions, listing allocated and useful positions exactly; additional bytes for device kernels, block tables, and alignment are excluded.[1] Efficient Memory Management for Large Language Model Se

3. Prefix Sharing Requires Strict Content and Lifetime Conditions

Branches with the same model, token prefix, and relevant runtime conditions can share already computed physical blocks in a suitable implementation. Sharing counts must be consistent with request lifetimes; when a branch needs to modify a shared, partially filled block, copy-on-write can prevent mutual overwriting. Cancellation, timeouts, retries, and branch merging can all trigger reclamation. Incomplete keys or premature reclamation can turn a resource optimization into output errors or even cross-request data problems. Correctness tests should therefore verify content versions, reference counts, and windows during which addresses must not be reused, rather than merely checking memory reductions.[1] Efficient Memory Management for Large Language Model Se

4. Continuous Batching Changes Waiting Between Requests

A serving system can add new requests and remove completed ones at each step to improve device utilization, but prefill and decoding have different resource requirements. Long prefills may delay requests that are already decoding, and larger batches may increase throughput while worsening individual-request latency. Scheduling priorities, preemption, and KV migration rules should be specified, and time to first token, per-token latency, end-to-end latency, and tail latency should be reported. Measurements made only on offline batches in which all requests arrive simultaneously cannot represent real arrival processes or service objectives.[1] Efficient Memory Management for Large Language Model Se[2] FlashAttention: Fast and Memory-Efficient Exact Attenti

5. Paging and IO Optimization Operate at Different Levels

FlashAttention organizes attention computation into blocks to reduce reads and writes between high-bandwidth memory and on-chip storage; KV paging focuses on state allocation and access during serving. The two mechanisms can be combined, but realizing their combined benefits requires actual kernel support. Speculative decoding also creates KV positions for temporary storage and rollback, further affecting allocation. Evaluation should separately ablate operator optimization, cache allocation, and scheduling to avoid attributing differences across an entire serving stack to a single paging algorithm.[2] FlashAttention: Fast and Memory-Efficient Exact Attenti[1] Efficient Memory Management for Large Language Model Se[3] Fast Inference from Transformers via Speculative Decodi

6. Sound Acceptance Criteria Must Constrain Both Quality and Service Objectives

With weights and sampling fixed, first verify that paging, sharing, and reclamation have not changed output semantics, then compare throughput and tail latency under a fixed arrival distribution. Memory utilization should distinguish useful KV, tail-block fragmentation, block tables, workspaces, and reserved pools. Fault tests must also cover OOM, cancellation, and recovery from preemption. This article performs only equation-based accounting; reduced fragmentation cannot establish a speedup by any multiple. Actual benefits depend on the workload, kernels, device, and service objectives.[1] Efficient Memory Management for Large Language Model Se[2] FlashAttention: Fast and Memory-Efficient Exact Attenti

Core Equations and Derivations

MKV=2LnhKVdhbM_{\mathrm{KV}}=2Lnh_{\mathrm{KV}}d_hb

(1) b is the number of bytes per scalar; multiplication by 2 accounts for keys and values. Block tables, workspaces, padding, and other model state are excluded.

LaTeXM_{\mathrm{KV}}=2Lnh_{\mathrm{KV}}d_hb
AB(n)=B⌈n/B⌉,WB(n)=AB(n)−nA_B(n)=B\lceil n/B\rceil,\qquad W_B(n)=A_B(n)-n

(2) A denotes allocated positions, and W denotes internal fragmentation in the final block; with fixed-length reservation, the waste is M−n.

LaTeXA_B(n)=B\lceil n/B\rceil,\qquad W_B(n)=A_B(n)-n
U=∑ini∑iB⌈ni/B⌉U=\frac{\sum_i n_i}{\sum_i B\lceil n_i/B\rceil}

(3) This computes only position utilization, excluding block tables, sharing, and scheduling; it cannot be treated directly as device utilization.

LaTeXU=\frac{\sum_i n_i}{\sum_i B\lceil n_i/B\rceil}

Method and Evidence Workflow

Active requests and lengths → Logical KV block table → Physical block pool / reference counts → Sharing and copy-on-write → Continuous batching and reclamation → Memory breakdown and latency constraints
Figure 1 · Method and Evidence WorkflowA conceptual diagram drawn from the structure of this article, showing steps that need to be distinguished; it does not indicate that these experiments have been completed.

Analytical Figures and Numerical Examples

Page size and sequence lengths determine internal waste
Figure 2 · Page size and sequence lengths determine internal wasteFive constructed lengths; no block table, alignment, sharing, preemption or device memory overhead. JSON · Equations, inputs, and numerical values

Recalculable Worked Example

The five sequences contain a total of 968 useful positions; fixed reservations of 512 require 2560, paging with 16 positions per page requires 992, and paging with 32 positions per page requires 1024. Position utilization is approximately 37.81%, 97.58%, and 94.53%, respectively; these are not device utilization or throughput.

Method Comparison

Method or assessmentControlled variables and measurementsFailure conditions and interpretation
Fixed maximum-length reservationCount using the same set of active requestsGreater variation in length may leave more reserved capacity unused
KV pagingRecord block size, useful positions, and block-table bytesSmall blocks reduce fragmentation but increase management costs
Prefix sharingVerify the model, tokens, configuration, and reference lifetimesIncorrect sharing keys or premature reclamation change outputs
Online schedulingFix the arrival process and measure tail latencyOffline throughput cannot represent the serving experience

Verification and Experimental Plan

  1. Fix weights, the number of KV heads, precision, and sampling rules, and check outputs against a contiguous-KV baseline.
  2. Record real or explicitly constructed input/output lengths and arrival processes without mixing the two types of evidence.
  3. Sweep block sizes and account for useful KV, final-block fragmentation, block tables, and reserved pools.
  4. Test sharing, copy-on-write, branching, cancellation, preemption, and reclamation, and check output isolation.
  5. Separately ablate operators, paging, and scheduling, recording time to first token, per-token latency, and tail latency.
  6. Compare the requests that can be supported under the same latency targets and quality, retaining OOM and timeout samples.

Scope and Limitations

  • Length samples are constructed inputs.
  • Position utilization is not device utilization.
  • No vLLM or hardware throughput tests were performed.
  • Sharing and reclamation correctness requires implementation-level verification.

Primary Sources and Corresponding Claims

  1. Efficient Memory Management for Large Language Model Serving with PagedAttention, , , , , , , , · 2023-09-12Abstract; 原文方法、理论和实验章节见作者原始论文链接
  2. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-AwarenessDao et al. · 2022-05-27v1; sections 2-3
  3. Fast Inference from Transformers via Speculative Decoding, , · 2022-11-30Abstract; 原文方法、理论和实验章节见作者原始论文链接

Citation and Article Export

BibTeXRISCSL JSONTXTArticle JSON

Author, Version, and Sources

AI-assisted research review; Codex (AI) wrote the article and performed analytical derivations based on the listed primary literature. This site has no record of independent peer review or original model experiments for this article.

Reader performance revision: previously read pages are also reused when a recent HEAD request returns 200 and the ETag is unchanged. The main text, equations, sources, and scientific-figure data retain the content of the previous version.

The conceptual cover is separate from the scientific illustrations; scientific figures are calculated from public equations and explicitly stated assumptions, and results from original papers are attributed to their sources.

Author, version, and correction history · /guides/paged-attention-serving/v1/

Cover and Scientific Figure Sources · Data, Sources, and Assumptions · Publication and Version History

Source revision: 6251a250b27bb8b449f59b392f81abd355383770