Source-linked AI summary
Tangram: Unlocking Non-Uniform KV Cache Compression for Efficient Multi-turn LLM Serving
Hyungmin Kim, Minsoo Kim, Hongseok Kim, Jungwook Choi
TL;DR
Multi-turn LLM serving is constrained by growing KV caches, while non-uniform compression remains impractical because serving stacks assume identical per-head cache lengths. Tangram statically calibrates and manages heterogeneous head budgets, delivering up to 2.6× higher throughput than the full-KV baseline while matching compression accuracy.
Problem
Non-uniform KV compression preserves accuracy under heterogeneous per-head budgets, but serving stacks assume identical KV lengths across heads, making such compression impractical.
Method
Tangram uses offline head-retention calibration with budget reservation, ragged paging, and ahead-of-time load balancing to serve non-uniform KV compression.
Results
Up to 2.6× higher end-to-end throughput than the full-KV baseline is achieved while preserving the accuracy of existing non-uniform compression methods.
Takeaways & Limitations
Tangram makes non-uniform KV cache compression practical for real LLM serving stacks without sacrificing the underlying compression methods’ accuracy.
Takeaways & Limitations
Existing monolithic pages cannot reclaim memory freed by heterogeneous head retention because pages are shared across heads and released only when every head releases them.
Abstract
from arXiv · showhide
Multi-turn LLM serving accumulates dialogue history whose Key-Value (KV) cache grows with every turn and every user, quickly exceeding the model weights themselves and making memory -- not compute -- the binding constraint on throughput. Non-uniform KV compression, which allocates heterogeneous budgets across attention heads, preserves accuracy far better than uniform schemes, yet remains impractical: modern serving stacks assume identical KV lengths across heads, so heterogeneity traps freed memory as page fragmentation, spends up to 25% of prefill time reclaiming scattered pages, and skews GPU workloads that inflate decode latency by up to $1.7\times$ or burn 15--20% of each decode step on re-planning. We observe that this heterogeneity need not be discovered at runtime: head-wise retention follows a two-level structural regularity -- an input-invariant head ranking with narrowly bounded per-head ratios -- that can be calibrated offline from as few as 50 samples. Building on this insight, we present Tangram, a serving framework that statically resolves what prior systems handle dynamically: Budget Reservation fixes each head's post-compression footprint at scheduling time, eliminating page reclamation; Ragged Paging clusters similar-budget heads into independent page tables, turning fragmentation into reclaimable memory; and Ahead-of-Time Load Balancing precomputes balanced GPU partitions with zero runtime planning. Implemented on vLLM, Tangram serves as a drop-in substrate for existing non-uniform compression methods, matching their accuracy while improving end-to-end throughput by up to $2.6\times$ over the full-KV baseline. Our implementation is publicly available at https://github.com/aiha-lab/TANGRAM.
1 Introduction
Multi-turn serving makes the KV cache a growing memory bottleneck, while uniform compression wastes accuracy-sensitive head capacity and non-uniform compression conflicts with current serving stacks. Tangram exploits offline-stable head-wise retention patterns to statically eliminate the resulting memory-management and load-balancing overheads.
- Motivation: The KV cache grows linearly with conversation turns and concurrent users, surpassing Qwen2.5-32B’s model-weight size within ten turns at 16 concurrent requests.The cache continues growing unboundedly thereafter.
- Motivation: Uniform compression assigns every attention head the same token budget, starving retrieval heads that preserve critical long-range information.Other heads may attend only locally, so equal truncation can damage accuracy disproportionately.
- System challenge: Non-uniform compression violates serving stacks’ assumption of identical per-head KV lengths, causing page-management and GPU-load imbalance overheads.Scattered-page control-plane churn consumes up to 25% of prefill time, static partitioning inflates decode attention latency by up to 1.7×, and dynamic re-planning burns 15–20% of each decode step.
- Key insight: Head-wise retention has input-invariant rankings and narrowly bounded per-head ratios, enabling offline calibration from as few as 50 samples.This two-level structural regularity is intrinsic to the model rather than driven by the input.
- Tangram: Tangram statically addresses non-uniform serving bottlenecks through Budget Reservation, Ragged Paging, and Ahead-of-Time Load Balancing.Budget Reservation reserves post-compression pages at scheduling time and eliminates the compress-and-reclaim path; Ragged Paging uses finer-grained per-group page tables for similar-budget heads.
2 Background
Multi-turn serving maintains growing dialogue histories in KV caches, whose size scales with accumulated context across layers and heads. Because attention heads have diverse concentration patterns, non-uniform compression preserves this heterogeneity while uniform budgets can discard critical tokens or over-retain unnecessary ones.
- KV-cache background: KV caches store attention states for every token across layers and heads, so their size grows with accumulated dialogue length.Under grouped-query attention, multiple query heads may share one KV head.
- Compression strategies: Attention heads differ substantially in concentration, causing the number of critical tokens to vary across heads.Some heads focus on small token subsets, while others distribute attention broadly across the context.
- Compression strategies: Uniform compression assigns every head the same ⌈𝜌N⌉ token budget, ignoring head-wise diversity in importance distributions.This can discard critical tokens for broadly attending heads while over-retaining tokens for narrowly attending heads.
- Compression strategies: Non-uniform compression enforces the target retention ratio at the layer level, producing heterogeneous per-head retention ratios that mirror attention concentration patterns.The ratios arise from globally selecting top-scoring tokens after flattening importance scores across heads.
- Serving-system background: Serving frameworks such as vLLM and SGLang coordinate schedulers, block tables, KV-cache pages, and attention kernels under tightly integrated execution pipelines.These components support batching and memory management for KV-cache execution.
3 Motivation
Non-uniform KV compression preserves accuracy but conflicts with serving stacks built for uniform per-head lengths, causing fragmentation, reclamation overhead, and decode imbalance. Tangram exploits stable head-wise retention structure to resolve these costs statically through reservation, ragged paging, and ahead-of-time balancing.
- Serving-system limitations: Uniform page allocation provisions every head up to the longest-retaining head, leaving gaps between actual retention and the allocation ceiling.This monolithic structure causes page fragmentation under non-uniform compression.
- Serving-system limitations: 25% of total prefill execution time can be consumed by runtime compress-and-reclaim, which identifies freed pages, returns them, and updates page tables.The overhead scales linearly with the number of reclaimed pages.
- Serving-system limitations: Non-uniform retention creates skewed decode workloads because fixed-size KV partitions are applied uniformly despite differing per-head KV lengths.Dynamic planning must recompute partitions per layer and decoding step because retained lengths differ independently across layers.
- Structural regularity: Head-wise retention exhibits input-invariant rankings and narrowly varying absolute retention ratios, enabling offline calibration of each head’s retention budget.Across 50 samples, each head shows a largely stable retention level across inputs, despite moderate task-dependent shifts in absolute values.
- Static resolution: Tangram statically fixes head budgets, groups similarly retained heads into independent page tables, and precomputes GPU workload partitions.These decisions respectively support Budget Reservation, Ragged Paging, and Ahead-of-Time Load Balancing.
4 Methodology
Tangram statically plans non-uniform KV compression around model-intrinsic, input-invariant head retention, integrating compression into prefill and fixing each head’s post-compression footprint before execution. Ragged paging and ahead-of-time workload partitioning then convert heterogeneous budgets into reclaimable memory and balanced decode execution.
- Static Budget Calibration: Tangram calibrates each head’s budget ratio offline, preserving each compression method’s scoring function while adding no serving-path cost.Calibration uses sample contexts under a target global retention ratio and fixes per-head ratios with a safety margin.
- Fused Prefill Compression: Compression is fused into chunked prefill and continuous batching, with each prefill chunk compressed immediately after its KV cache is generated.The underlying scoring function rates every KV entry, while Tangram preserves that scoring mechanism.
- Precise Page Allocation: Static footprint reservation allocates exactly the required pages at scheduling time, eliminating over-provisioning and scattered-page reclamation from the serving path.Every page enters the cache already in its post-compression state, removing the associated TTFT cost.
- Robustness and Overflow Handling: Overflow beyond a reserved head budget retains the highest-scoring entries within capacity, degrading into slightly stronger compression rather than a stall or correctness failure.End-to-end accuracy results include any residual truncation caused by overflow.
- Ragged Paging: Ragged paging gives each head group an independent page table sized by its local maximum budget, while clustering similar-budget heads improves memory efficiency.Packing short-retention heads together frees the most pages; unused group slack can retain extra KV without reclamation.
- Ahead-of-Time Load Balancing: Ahead-of-time workload partitioning preserves fixed work proportions across requests, keeping decode plans near-optimal across context lengths and batch sizes.Dynamic planning spends 15–20% of every decode step rediscovering this balance.
5 Evaluation
Tangram is evaluated across five long-context models and SCBench workloads spanning short, mid, and long contexts. It preserves the underlying compression methods’ accuracy while improving throughput and eliminating major runtime overheads through static memory management and load balancing.
- Evaluation Setup: Tangram is evaluated on five dense and Mixture-of-Experts models with context windows exceeding 100K tokens, using SCBench multi-turn workloads across three context-length categories.The categories are Short (< 20K), Mid (20K–100K), and Long (> 100K) tokens.
- Accuracy: Tangram preserves each underlying non-uniform compression method’s original accuracy while matching its calibrated per-head retention and absorbing input variation with a safety margin.The framework changes serving rather than compression, acting as a faithful systems substrate.
- Throughput: 2.6× throughput improvement is achieved over the vLLM Full-KV baseline, with gains increasing as context length grows from Short to Long.The improvement combines capacity freed by compression with Tangram’s system efficiency.
- Memory Management: 25% of prefill execution time can be consumed by dynamic page reclamation, whereas Tangram’s Budget Reservation eliminates this overhead by allocating required pages before execution.Dynamic compression tracks and reclaims scattered pages; static reservation defines the exact memory footprint in advance.
6 Related Works
Prior work establishes non-uniform KV compression as more accurate than uniform retention but leaves deployment challenges unresolved. Tangram addresses this gap by exploiting cross-head retention regularity for practical heterogeneous memory management in high-throughput serving.
- Multi-turn LLM Serving: Prior multi-turn LLM serving work emphasizes long-horizon context and retrieval augmentation but largely overlooks serving efficiency for memory-intensive workloads.Tangram is positioned as addressing this gap.
- KV Cache compression: Non-uniform compression improves accuracy by allowing heterogeneous retention budgets, whereas uniform schemes simplify management but may discard context essential for specific heads.This contrast motivates system support for heterogeneous KV-cache footprints.
- Heterogeneous Memory Management: Tangram exploits cross-head structural regularity by clustering heads with similar intrinsic retention into ragged pages, aligning page boundaries with retention distributions.This makes head-level heterogeneous memory management practical for high-throughput serving, unlike prior systems that do not exploit this regularity.
7 Conclusion
Tangram brings non-uniform KV cache compression to real LLM serving stacks by statically exploiting head-wise retention regularity. It reserves post-compression budgets, reclaims fragmented memory with budget-clustered ragged pages, and precomputes GPU workload balancing.
- Conclusion: Tangram brings non-uniform KV cache compression to real LLM serving stacks.The system is designed for practical deployment in existing serving infrastructure.
- Conclusion: Tangram reserves exact post-compression budgets at scheduling time.This statically resolves budget assignment that prior systems handle at runtime.
- Conclusion: Tangram reclaims fragmented memory through budget-clustered ragged pages.Ragged pages are organized around clustered budgets to address fragmentation from non-uniform compression.
- Conclusion: Tangram balances GPU workloads with a precomputed Workload Split Map.The map removes the need to perform workload balancing dynamically at runtime.
A Retention Regularity across Compression Methods
Across KVzip and three integrated non-uniform compression methods, head-wise retention exhibits input-invariant rankings and narrowly varying per-head ratios. Static budgets cover observed retention spreads with marginal overhead, while retention profiles remain method-specific.
- Evidence across methods: KVzip, Ada-SnapKV, FastKVzip, and Expected Attention consistently reproduce two-level head-wise retention regularity across model families and SCBench tasks.Figure 5 establishes the pattern with KVzip; Figure 16 repeats it for the three integrated methods.
- Retention regularity: Narrow, task-aligned per-head boxes confirm input-invariant head rankings and narrowly bounded absolute retention ratios.The overlaid static budget (𝜇+2𝜎) covers each head’s observed spread.
- Method-specific profiles: Retention profiles are method-specific: Ada-SnapKV distributes budget relatively evenly, whereas FastKVzip and Expected Attention concentrate retention on a small subset of heads.The remaining heads are heavily pruned under FastKVzip and Expected Attention; Tangram calibrates budgets per model and method.