PaperlayerView exact revision on arXiv

Source-linked AI summary

GrowPage: On-Demand KV Budgeting for Efficient LLM Reasoning Serving

Qiankun Ma, Yanjiang Zhou, Zinan Xiong, Haofei Wang, Zhen Song, Yang Xiang, Ziyao Zhang, Hairong Zheng

arXiv:2609.03494v1cs.AI

TL;DR

Long-output reasoning makes KV-cache capacity a serving bottleneck, while fixed per-request budgets cannot match heterogeneous and evolving demands. GrowPage estimates demand with dual-timescale query summaries and dynamically compresses or expands page allocation through PagedAttention. Across reasoning benchmarks, it improves the reasoning performance–throughput trade-off while preserving continuous batching and prefix caching.

  • Problem

    Reasoning workloads require heterogeneous and changing KV capacities, but existing methods typically keep total per-request capacity fixed, creating a mismatch for efficient serving.

  • Method

    GrowPage uses dual-timescale query summaries to estimate demand evolution and chooses between compression within the current allocation and incremental physical-page allocation.

  • Results

    GrowPage consistently improves the reasoning performance–throughput trade-off across diverse benchmarks and model architectures while preserving continuous batching and prefix caching.

  • Takeaways & Limitations

    Treating KV capacity as a runtime resource enables page-level adaptation to evolving reasoning demand within PagedAttention-based serving.

Abstract

from arXiv · show

Long-output reasoning has made the key--value (KV) cache a critical memory bottleneck for efficient LLM serving. Existing KV compression methods usually rely on a predefined per-request budget and adjust only which KV states are retained, leaving the total capacity fixed throughout decoding. However, reasoning workloads exhibit substantial demand variation: different requests require different KV capacities, and the attention demand of an individual request evolves during generation. We introduce \textbf{GrowPage}, an on-demand KV budgeting framework that treats KV capacity as a runtime resource. GrowPage maintains lightweight dual-timescale query summaries to capture recent and long-term attention behaviors, and uses their relative attention working sets to estimate demand evolution. At each capacity boundary, GrowPage either compresses KV states within the current allocation or acquires an additional physical page when broader demand emerges. By integrating with PagedAttention's page-level memory abstraction, GrowPage preserves continuous batching and prefix caching. Experiments on reasoning benchmarks across multiple models show that GrowPage achieves a superior performance--throughput trade-off over existing approaches.

1 INTRODUCTION

Long chain-of-thought generation makes KV-cache memory a major serving bottleneck, while fixed per-request capacities mismatch heterogeneous and evolving reasoning demands. GrowPage treats capacity as an online resource, using demand estimates to choose compression or page expansion while preserving serving optimizations.

  • Motivation: Long reasoning outputs continuously expand KV caches, limiting how many concurrent requests can remain resident on GPU.This makes the KV cache a major bottleneck for efficient LLM serving.
  • Limitations of prior work: Existing KV compression methods often struggle to integrate with continuous batching and prefix caching, limiting their serving-efficiency gains.They may reduce algorithmic memory usage without translating those savings into higher serving efficiency.
  • Problem: Fixed per-request capacity bounds under-provision demanding requests or over-provision low-demand requests, because total capacity remains static.Adaptive methods may change retained states or budget distribution while leaving total capacity fixed.
  • Motivation: KV demand varies across requests and within decoding, motivating runtime capacity control based on attention concentration and relative working-set changes.These observations provide the basis for treating capacity as a runtime quantity rather than a static reservation.
  • Approach and outcome: GrowPage uses dual-timescale query summaries to estimate demand, then compresses within the current allocation or acquires a physical page as demand broadens.Its PagedAttention integration preserves continuous batching and prefix caching, and experiments report improved reasoning performance–throughput trade-offs across diverse benchmarks.

2 WHY ON-DEMAND KV BUDGETING?

The paper motivates on-demand KV budgeting by showing that required capacity differs across requests and changes during decoding. These patterns make a fixed reservation unnecessarily conservative at some stages and insufficient at others.

  • Framing: Static KV budgeting assumes one capacity can represent memory demand throughout decoding, despite both inter-request heterogeneity and intra-request temporal variation.The paper examines these two sources of mismatch separately.
  • Inter-request heterogeneity: Minimum sufficient KV budgets vary substantially across reasoning requests, so small fixed budgets can under-provision demanding requests while large ones waste memory.The minimum sufficient budget is defined using correctness across all larger tested budgets to reduce occasional non-monotonic outcomes.
  • Intra-request variation: Attention sparsity repeatedly shifts between concentrated and diffuse regimes throughout decoding, indicating that historical KV requirements are non-stationary within a request.A fixed capacity can therefore be unnecessarily conservative at some stages yet insufficient at others.
  • Implication: Together, the observations motivate treating KV capacity as an on-demand resource and formally connecting attention concentration with the capacity needed to preserve attention outputs.This provides the theoretical basis for GrowPage’s online capacity control.

3 METHODOLOGY

GrowPage formalizes how attention concentration determines KV capacity and uses dual-timescale summaries to adapt capacity online. At capacity boundaries, it either compresses retained states or grows by one physical page according to estimated demand trends.

  • Theoretical analysis: The p-coverage demand D_p is the smallest number of top-attention KV states whose cumulative mass reaches target coverage p.Concentrated attention yields smaller D_p, while diffuse attention requires a larger working set.
  • Theoretical analysis: Theorem 3.1 shows that guaranteeing approximation error at most δ requires retaining attention mass of at least 1 − δ/(2Vmax).The result is a worst-case capacity requirement under bounded value-vector norms; realized requests may require less capacity.
  • Online demand estimation: GrowPage maintains short- and long-timescale query summaries to estimate evolving attention demand from their relative historical working sets.The long-timescale summary provides historical reference, while the short-timescale summary captures recent behavior.
  • Trend-guided capacity control: At each capacity boundary, a positive demand trend selects Grow by One Page; otherwise GrowPage selects Compress & Hold.The default threshold is τ = 0, and the decision aligns adaptation with PagedAttention’s page granularity.
  • Trend-guided capacity control: Compress & Hold frees one page by independently selecting important KV states for each layer–head pair, combining recent and long-term importance.The retained historical-token budget is derived from the target allocation, while local retention prevents over-concentration in a few historical regions.
  • Trend-guided capacity control: Grow by One Page appends one physical KV page when recent demand becomes more diffuse, allowing decoding to continue until the next capacity boundary.This expands the request’s allocation instead of further compressing its historical working set.

4 SYSTEM INTEGRATION

GrowPage integrates online demand estimation with PagedAttention while preserving page-based serving behavior. It uses lightweight reusable state, boundary-triggered estimation, and memory-aware fallback to compression when page growth is unavailable.

  • Runtime state: GrowPage stores short- and long-timescale summaries in request metadata, with state size independent of sequence length.Summary storage is pre-allocated for active request slots, updated during decoding, and recycled when requests complete.
  • Runtime state: The runtime updates summaries during the regular decoding path and invokes expensive attention-based demand estimation only at capacity boundaries.This avoids frequent GPU-side allocation and limits additional control overhead during continuous batching.
  • PagedAttention integration: Compress & Hold compacts selected KV states within existing physical pages, while Grow by One Page appends a page from the global free-page pool.Both decisions map directly onto PagedAttention’s block table and physical-page abstraction.
  • Memory-aware allocation: Under memory pressure, GrowPage falls back to compression when safely allocating another page would reduce availability for concurrent requests.Page growth is granted immediately when a free physical page exists.
  • PagedAttention integration: GrowPage preserves compatibility with continuous batching, prefix caching, and CUDA Graph execution by retaining PagedAttention’s page/block abstraction.It also inherits Zipage’s asynchronous compression pipeline to overlap compaction with serving execution.

5 EXPERIMENTS

Across reasoning models and workloads, GrowPage improves the performance–throughput trade-off by adapting KV capacity online. Its demand signal tracks evolving attention needs, while capacity expansion and compression provide measurable serving benefits with low runtime overhead.

  • GrowPage improves average decoding throughput over full KV inference by 64.3% on DeepSeek-R1-Distill-Llama-8B and 60.2% on Qwen3-8B while maintaining comparable pass@1 accuracy.
  • 84.9% pass@1 at 2213 tokens/s, with average KV budget 3442 and C = 121, outperforms Zipage-4096 across accuracy, throughput, and resident concurrency.GrowPage approaches Zipage-8192 accuracy of 85.1% with nearly 1.9× higher throughput and 1.8× more resident requests.
  • ρ = 0.78 and 80.3% sign agreement show that ∆t tracks future attention-demand change on Qwen3-8B with AMC23.The future-demand change compares current and upcoming-page attention working sets.
  • Growth advantage consistently increases with ∆t, indicating that the signal identifies when allocating an additional KV page reduces replayed-token prediction loss.The analysis compares Compress & Hold with Grow by One Page using teacher-forced negative log-likelihood on a shared reference trajectory.
  • The default dual-timescale setting achieves the highest pass@1 accuracy of 91.4% on AMC23 and 73.8% on AIME24 in the ablation.Moderate short-term smoothing and a longer-term reference improve the accuracy–throughput trade-off relative to less suitable smoothing choices.
  • Demand estimation and capacity control add less than 0.32% of corresponding decoding time, with KV Compaction the largest overhead.Per-event costs are 5.84, 8.54, 0.70, 8.72, and 19.05 ms for Online Demand, Attention Score, Window Mask, Top-k Selection, and KV Compaction.

6 RELATED WORK

KV-cache compression research spans token-retention methods for long-context and reasoning inference and system-aware approaches that integrate cache management with serving infrastructure.

  • Token-level compression: Recent KV-cache compression methods retain important tokens under limited budgets and extend eviction into decoding to control cache growth during long-form generation.Representative approaches include StreamingLLM, SnapKV, PyramidKV, and newer decoding-stage methods.
  • System-aware KV optimization: PagedAttention provides a page-based memory abstraction for efficient KV management under continuous batching.System-level work builds on this abstraction to study page organization and KV scheduling for long-sequence inference.
  • System-aware KV optimization: Zipage integrates token-level KV eviction with PagedAttention-oriented serving, connecting compression decisions to practical memory management.The passage identifies Zipage as part of recent system-level KV management work.

7 CONCLUSION

GrowPage treats KV capacity as a runtime resource for reasoning serving, using demand estimation to choose between compression and page expansion while preserving efficient serving trade-offs.

  • Conclusion: GrowPage addresses heterogeneous and evolving KV demands by replacing fixed per-request capacity budgets with runtime capacity control.The paper frames fixed budgets as unable to accommodate different requests and changing demands during decoding.
  • Conclusion: Dual-timescale query summaries estimate demand evolution, guiding online KV compaction within the current allocation or incremental physical-page expansion.The method uses short- and long-timescale summaries to choose between the two actions.
  • Conclusion: GrowPage integrates with PagedAttention-based serving while preserving continuous batching and prefix caching.The integration retains these system optimizations while applying dynamically determined page capacity.
  • Sensitivity analysis: Demand-threshold sensitivity experiments vary τ from −0.003 to 0.003 on Qwen3-8B using AMC23 and AIME24.The study focuses on the interval around [−0.005, 0.005], where the benefit of extra capacity changes noticeably.

E SYSTEM IMPLEMENTATION DETAILS

The implementation combines pre-allocated query-state management, boundary-triggered demand estimation, prefix-preserving compression, and asynchronous execution within the serving system.

  • Query-state management: GrowPage pre-allocates a fixed query-state tensor and stores short- and long-timescale EMA queries for up to 512 concurrent sequences by default.The tensor dimensions include attention layers, query slots, query heads, and head dimension.
  • Query-state management: Query slots are assigned only to running requests and returned when requests finish or are preempted, avoiding repeated underlying GPU tensor allocation.Waiting requests consume no query-state slot, while resumed requests acquire a new slot.
  • Demand estimation: During decoding, the two EMA summaries update in place with βS = 0.9 and βL = 0.999; at capacity boundaries, summaries are calibrated before demand estimation.Newly assigned slots initialize both states from the current normalized pre-RoPE query.
  • Demand estimation: Calibrated summaries are transformed by RoPE at the current position, preserving temporal information while aligning them with the current attention frame.This transformation occurs after RMS-scale calibration.
  • Demand estimation: Historical attention working sets exclude the most recent 256-token physical block and use Top-p coverage p = 0.99 to compute short- and long-timescale working-set ratios.Native GQA head mapping is preserved when matching query heads to KV heads.
  • KV compression and execution: Prefix-preserving compression avoids overwriting shared blocks, while Compress & Hold compacts retained states within the current allocation and leaves one page of free slots.Compression targets are adapted to GrowPage’s dynamic capacity.
  • KV compression and execution: Selected compactions run asynchronously so other decode-ready requests continue decoding instead of waiting for synchronous compression.This preserves overlap between decoding and compression workloads.

F.1 DATASETS AND EVALUATION PROTOCOL

The evaluation covers five reasoning benchmarks and a balanced mixed workload, then tests whether the observed accuracy–efficiency trade-off extends across model architectures.

  • Datasets and protocol: GrowPage is evaluated on five reasoning benchmarks spanning mathematical reasoning and code generation, with Pass@1 averaged across independent sampled generations.The protocol uses temperature 0.6 unless otherwise specified and records benchmark sizes, generation counts, output limits, and baseline KV budgets.
  • Datasets and protocol: AMC23 and AIME24 use 32 independent generations per question, while MATH500, GSM8K, and LiveCodeBench use fewer repetitions based on dataset size and difficulty.LiveCodeBench receives a larger KV budget because its code-generation trajectories are substantially longer.
  • Mixed workload: The heterogeneous workload combines AMC23, AIME24, and GSM8K with balanced sampling to prevent GSM8K from dominating, producing 3559 requests capped at 32768 tokens.The mixed workload evaluates Zipage across multiple fixed budgets against GrowPage’s accuracy–throughput frontier.
  • Cross-architecture evaluation: The mixed-workload experiment is repeated on DeepSeek-R1-Distill-Llama-8B using the same workload and fixed Zipage budgets from 1024 to 8192 tokens.GrowPage is compared with FullKV and Zipage under this cross-architecture protocol.
  • Cross-architecture evaluation: On DeepSeek-R1-Distill-Llama-8B, GrowPage reaches 64.3% Pass@1 at 2451 tokens/s with an average KV budget of 3234 tokens and resident concurrency C = 135.Against Zipage-4096, it improves accuracy from 63.5% to 64.3% and throughput from 2098 to 2451 tokens/s.

G.2 DETAILED SERVING METRICS

GrowPage improves serving efficiency by adapting KV capacity to demand rather than relying solely on fixed budgets. Its demand-guided policy improves throughput and accuracy over fixed, random, inverse, and aggressive-shrink alternatives.

  • Serving efficiency: GrowPage achieves the lowest total inference time across all five benchmarks on both models.Average inference time falls from 3.13 to 2.51 hours on DeepSeek-R1-Distill-Llama-8B and from 3.08 to 2.70 hours on Qwen3-8B versus Zipage.
  • Serving efficiency: GrowPage reduces average TPOT from 160.2 to 132.4 ms/token on DeepSeek-R1-Distill-Llama-8B and from 156.8 to 131.0 ms/token on Qwen3-8B relative to Zipage.It achieves the lowest TPOT across all five evaluated datasets.
  • Capacity-control ablations: Compared with GROWPAGE-FIXED, GrowPage reduces average KV budget from 4096 to 3164 tokens while increasing TPS from 1874 to 2261 and Pass@1 from 89.9% to 91.4%.The comparison indicates that static capacity with repeated compression does not reproduce the default policy’s trade-off.
  • Capacity-control ablations: GROWPAGE-RANDOM reaches 88.3% Pass@1 at 2008 tokens/s, versus 91.4% at 2261 tokens/s for GrowPage, despite similar compression-and-growth frequencies.The random policy also maintains a larger average KV budget of 3728 tokens.
  • Capacity-control ablations: GROWPAGE-INVERSE increases average KV budget to 6167 tokens and reduces throughput to 1340 tokens/s while achieving lower accuracy than GrowPage.The result supports using the direction of Δt for capacity allocation rather than as a generic activity signal.
  • Capacity-control ablations: GROWPAGE-SHRINK attains the smallest average KV budget and highest raw throughput but lowers Pass@1 to 84.2%, 7.2 percentage points below GrowPage.GrowPage therefore uses Compress & Hold instead of aggressively reclaiming pages from active reasoning requests.

H.2 SYSTEM-LEVEL EVENT ANALYSIS

System-level analysis shows that decision timing, not merely action frequency, drives the benefit of GrowPage. Dynamic expansion adds memory-manager pressure, while inverse or aggressive resizing causes waste, churn, preemptions, or information loss.

  • Decision timing: GrowPage and GROWPAGE-RANDOM grow at nearly identical rates, 30.9% and 30.4%, yet GrowPage achieves substantially higher accuracy and throughput.The demand-guided policy also has fewer fallback and preemption events than the random counterpart.
  • Dynamic adaptation cost: GrowPage triggers 597 fallbacks and 1361 preemptions, unlike GROWPAGE-FIXED, which incurs almost no such events because it never requests new pages.Despite this system-level cost, GrowPage reaches 2261 versus 1874 tokens/s and 91.4% versus 89.9% accuracy with a smaller average KV budget.
  • Policy direction: GROWPAGE-INVERSE raises the growth ratio from 30.9% to 66.7%, increasing KV residency without improving reasoning accuracy.The added capacity therefore wastes shared GPU memory.
  • Resizing stability: GROWPAGE-SHRINK performs 8927 explicit shrinks, 17909 subsequent growth operations, and 4668 preemptions, versus 1361 preemptions for GrowPage.Aggressive reclamation is associated with capacity churn, irreversible information loss, and significant accuracy degradation.

I REQUEST-LEVEL CAPACITY ALIGNMENT

GrowPage’s adaptive capacity generally tracks request-level KV demand while varying online during decoding. High-demand stages can receive additional pages without requiring high fixed capacity throughout the entire generation.

  • Request-level alignment: GrowPage records each request’s average allocated KV capacity over its decoding trajectory and reports class means with 95% confidence intervals.Requests are grouped by their minimum sufficient fixed budget B⋆_i under the same random seed.
  • Request-level alignment: Requests requiring larger fixed budgets generally receive larger adaptive capacities from GrowPage across populated budget classes.The trend is especially clear on LiveCodeBench, where average capacity rises from the 512-token class to the 8K-token class.
  • Online allocation: B⋆_i is the minimum fixed capacity required throughout generation, whereas GrowPage changes allocated capacity online as demand evolves.A high-budget-class request can therefore maintain a smaller average capacity and acquire pages only during high-demand stages.
  • Request-level alignment: Unresolved requests tend to receive relatively large adaptive capacities, suggesting that GrowPage responds to elevated attention demand rather than eventual correctness.This provides request-level evidence that the demand signal differentiates heterogeneous reasoning requirements.
Loading 2609.03494v1…