arXiv:2606.06302v1 [cs.LG] 4 Jun 2026
Tangram: Unlocking Non-Uniform KV Cache for Efficient Multi-turn LLM Serving Hyungmin Kim∗
Minsoo Kim∗†
Hanyang University Seoul, Republic of Korea [email protected]
Hanyang University Seoul, Republic of Korea [email protected]
Hongseok Kim
Jungwook Choi‡
Rebellions Republic of Korea [email protected]
Hanyang University Seoul, Republic of Korea [email protected]
Abstract
every turn [12, 20, 26, 34]. To avoid re-computing this history at every step, serving systems persist the attention states in the Key-Value (KV) cache [30]. However, this introduces a severe system challenge: as the number of turns increases, the KV cache footprint grows rapidly, often exceeding the model weights themselves even with moderate batch sizes. This exploding memory consumption has become the primary bottleneck limiting system scalability and serving throughput [2, 38]. To resolve the conflict between limited GPU memory and linear context growth, KV compression has become a standard compression strategy. Existing approaches generally fall into two categories: Uniform KV compression [14, 18, 22, 37, 42], which forces every attention head to retain an identical number of tokens, and Non-uniform KV compression [9, 10, 16, 32, 36], which allows for heterogeneous retention lengths. While Uniform methods are simpler to implement, they often degrade accuracy in multi-turn scenarios because they fail to capture the Retrieval Head [10] property of attention, in which critical information is localized within a subset of specific attention heads. In contrast, Non-uniform KV compression permits heterogeneous retention lengths per head, enabling critical attention heads to retain more information. This approach maintains model accuracy even under substantial KV cache reduction. However, despite its algorithmic superiority, Non-uniform compression remains impractical on current hardware due to severe system-level inefficiencies. State-of-the-art serving systems like vLLM [19] and SGLang [43] rely on a tightly integrated software stack optimized under the assumption that all attention heads maintain uniform KV cache sizes. This includes PagedAttention for noncontiguous memory management [19], Continuous Batching for non-blocking request scheduling [39], and kernel optimizations like FlashAttention [5] and FlashInfer[38]. However, non-uniform KV cache compression breaks this assumption. Consequently, integrating it into LLM serving systems reveals three fundamental limitations: (1) Monolithic
Multi-turn Large Language Model (LLM) serving is critical for consistent user experiences, yet the linear growth of the Key-Value (KV) cache imposes significant pressure on GPU memory and bandwidth. Non-uniform KV compression effectively preserves more information by considering the individual importance of each KV cache. However, such KV cache heterogeneity introduces various systemic challenges—including memory fragmentation, scheduling complexities, and diminished kernel utilization—which collectively lead to significant inefficiencies in existing LLM serving systems. To overcome these challenges, we present Tangram, a novel serving system designed to make Non-uniform KV caches practical. Tangram addresses systemic inefficiencies through three core techniques: (1) Deterministic Budget Allocation assigns a static memory footprint to each head based on its intrinsic pattern, entirely eliminating dynamic scheduling overhead and prefill stalls; (2) Head Group Page clusters attention heads with similar retention demands and manages them with independent, vectorized page tables, thereby maximizing physical memory reclamation; and (3) Ahead-ofTime (AOT) Load Balancing leverages static budget profiles to ensure uniform GPU utilization without runtime overhead. Experimental results show that Tangram improves throughput by up to 2.6× compared to existing baselines, while fully preserving model accuracy. Our implementation is publicly available at https://github.com/aiha-lab/TANGRAM.
1
Introduction
Multi-turn LLM Serving is emerging as a critical workload where AI assistants must engage with users over extended periods, accumulating history to deliver consistent and tailored responses [1, 3, 24, 27]. Unlike single-turn tasks, these applications require the model to condition its generation on the full dialogue history (𝐻𝑡 ), which grows linearly with ∗ Equal contribution † Currently at Apple ‡ Corresponding author
1
Hyungmin Kim, Minsoo Kim, Hongseok Kim, and Jungwook Choi
Page Structure, where unified page architectures fundamentally prohibit independent, head-wise heterogeneous memory reclamation, thereby locking compressed memory into massive Page Fragmentation (§ 3.1.1); (2) Dynamic Reclamation Bottleneck, where the on-the-fly reclamation of scattered pages incurs prohibitive control-plane overhead, severely degrading overall system throughput (§ 3.1.2); and (3) Workload Imbalance, where heterogeneous KV caches cause “straggler" effects across GPU SMs, making existing attention kernels ineffective and leading to significant GPU under-utilization (§ 3.1.3). To bridge this gap, we present Tangram, a holistic framework designed to make non-uniform KV compression practical for high-throughput serving. The core philosophy of Tangram is rooted in a key observation: head-wise KV cache retention patterns are highly stable and model-intrinsic. By leveraging this deterministic nature, Tangram uses these stable patterns as a foundational blueprint to co-design scheduling, memory management, and kernel execution. Ultimately, Tangram successfully translates theoretical KV cache reductions into actual system-level performance gains, improving end-to-end throughput by up to 2.6×. Overall, Tangram make the following contributions in this paper:
10 15 20 25 30 Session Number
Head Index
5
200 100 2
4 8 16 32 64 # Requests
(a)
0.7
0.6
0.5
0.3
0.2
0.1
0.4
0.2
0.1
0.1
0.1
0.1
0.9
0.8
0.7
0.6
0.5
0.4
Non-Uniform KV Compression
300
0
Retained KVs
Uniform KV Compression
Head Index
Size (GB)
Size (GB)
Comp. KVs
250 200 150 100 50 0
0.7
0.6
0.5
0.3
0.2
0.1
0.4
0.2
0.1
0.1
0.1
0.1
0.9
0.8
0.7
0.6
0.5
0.4
Context Length
(b)
Figure 1. (a) KV cache size growth for Qwen2.5-32B with the number of conversation sessions (top, # requests = 16) or with the # of requests (bottom, session number = 10). The dashed line indicates the model weight size. (b) Comparison of uniform and non-uniform KV compression strategies at a 50% compression rate, where the numbers in each box denote the importance score of each KV entry.
• Deterministic Memory Scheduling. Directly applying our key observation, we propose Deterministic Budget Allocation (§ 4.1.1). By converting dynamic, on-the-fly compression into a predetermined static memory footprint, this method completely bypasses the severe control-plane overheads associated with tracking and recovering scattered pages at runtime. • Head Group Page. To break the monolithic memory layout, we introduce a decoupled paging architecture (§ 4.2.2). Because the head-wise retention budgets are stable and known in advance, we can strategically cluster attention heads with similar capacity demands into independent page tables. This budget-aware grouping maximizes physical memory reclamation and eliminates page fragmentation. Furthermore, we implement a Vectorized Block Table using CPU SIMD units to process these operations in parallel, preventing CPU bottlenecks. • Ahead-of-Time (AOT) Load Balancing. Heterogeneous KV lengths can cause massive workload skew across GPU SMs. Since the structural “shape" of the non-uniform KV cache is fixed and predictable, we shift the load-balancing burden entirely offline (§ 4.3). By precomputing optimal GPU workload distributions based on the static budget profiles, we guarantee uniform SM utilization and prevent straggler effects with zero runtime planning latency.
2
Background
2.1
Non-uniform KV Cache Compression for Multi-Turn LLM Serving
2.1.1 KV Cache Bottleneck in Multi-Turn LLMs. Multiturn interactions have emerged as the dominant LLM workload, where a model must engage with users over extended periods while maintaining contextual coherence. We formalize each exchange as an interaction unit (𝑢𝑖 , 𝑎𝑖 ), consisting of a user utterance 𝑢𝑖 and the corresponding model response 𝑎𝑖 in a token sequence. The system then maintains a cu𝑡 −1 for each user mulative dialogue history H𝑡 = {(𝑢𝑖 , 𝑎𝑖 )}𝑖=1 request, which serves as the essential context for generating the response at turn 𝑡 [13, 34]. Serving systems maintain this history with the Key-Value (KV) cache, which incrementally stores attention states to avoid redundant re-computation of H𝑡 [30]. For an 𝐿-layer, 𝐻 -head Transformer, this requires storing Key and Value tensors for every token across all layers and heads, causing the cache size to scale with the length of the accumulated dialogue [11, 17]. As the number of concurrent user requests (i.e., batch size) grows and H𝑡 accumulates across turns, this scaling pressure compounds rapidly. As illustrated in Figure 1(a), the KV cache footprint often surpasses the model size even with a few concurrent requests. Consequently, memory capacity—rather than compute—becomes the primary constraint on system throughput, necessitating efficient compression strategies. 2.1.2 Non-Uniform KV Cache Compression. KV compression reduces the cache footprint by retaining only the 2
Tangram: Unlocking Non-Uniform KV Cache for Efficient Multi-turn LLM Serving
H0 H1 H2 H3 H4 H5 H6 H7
10
Relative Per-Head KV Budget (×)30 20
1 Scheduler (§ 2.2.1)
40
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
100
Layer Index
(a)
LLaMA3.1-8B
Qwen2.5-7B
40 0.9
Qwen2.5-14B
Non-uniform Uniform 0.7
0.5
0.3
Relative KV Size
0.1 0.9
0.7
0.5
0.3
Relative KV Size (b)
0.1 0.9
0.7
0.5
0.3
Relative KV Size
Scheduler
Running Reqs
Req Manager
Block Pool
GPUWorker Worker GPU GPU Worker
3 Generate KV Cache (§ 2.2.2)
80 60
:CPU Control
Waiting Reqs
2 Block Table (§2.2.1) Request Sequence Block Table ID Length 1 8192 [1, 2, 3, ..., 8192] 2 N [8193, .., 8192+N] ... ... ...
4 KV Cache Blocks (§2.2.2)
Input Chapter Context:
one
...
end.
Chapter
one
...
End.
Chapter
one
...
End.
Chapter
one
...
Chapter
one
...
Attention Head Idx
Relative Accuracy (%)
Attention Head Idx
1
Block 1
Block 2
...
Block 8192
Block 8193
Chapter
one
...
End.
...
Chapter
one
...
End.
...
End.
Chapter
one
...
End.
...
End.
Chapter
one
...
End.
...
5 Attention Kernel (§2.2.3)
0.1
Attention Metadata Block Table sequence length # splits = 2
Figure 2. (a) Distribution of KV cache entries capturing the top 50% attention scores on Qwen3-4B, averaged over 50 samples from the SCbench [23]. (b) Comparative accuracy on long-term conversation QA benchmarks [20] using KVzip [16] with Uniform and non-uniform KV compression.
... SM 0
SM 1
SM 2
SM 3
SM N
Figure 3. Main components of vLLM.
under aggressive KV size compression, confirming that nonuniform KV compression is essential for efficient yet accurate multi-turn LLM serving. 2.2
LLM Serving System
State-of-the-art serving frameworks such as vLLM [19] and most critical tokens per head—those that receive high cuSGLang [43] rely on a tightly integrated execution pipeline mulative attention weights and thus contribute most to the to manage memory and compute. As illustrated in Figure 3, attention output. Formally, the importance score 𝑠 ℓ,ℎ ∈ R𝑁 this pipeline is driven by five core components: a scheduler, aggregates the attention weights each token receives at head block tables, KV cache generation, KV cache blocks, and the ℎ in layer ℓ, and compression selects the top-𝑘 tokens accordattention kernel to enable efficient batching and memory ingly: 𝐼 ℓ,ℎ = Top(𝑘, 𝑠 ℓ,ℎ ) [22, 42]. A fundamental property of management [2, 21, 29, 30, 39, 45]. Crucially, this entire systhe attention mechanism, however, is that heads exhibit ditem structure is built under the implicit assumption that KV verse concentration patterns: some heads sharply concentrate cache lengths remain uniform across all attention heads. their attention weights on a small subset of tokens, while others distribute them broadly across the context [35, 36], 2.2.1 Continuous Batching. The scheduler manages the causing the number of critical tokens to vary substantially lifecycle of incoming and active user requests through iterationacross heads. As illustrated in Figure 1(b), Uniform KV comlevel continuous batching [39]. At each scheduling step, it pression [22, 28, 42] ignores this diversity by allocating a inspects the current status of the Block Pool of requests fixed budget 𝑀 identically to all heads (|𝐼 ℓ,ℎ | = 𝑀/𝐻 ), unito make admission and execution decisions (❶). Once a reformly truncating each head’s context regardless of its actual quest is considered runnable, the scheduler allocates physiattention distribution. In contrast, Non-uniform compression cal pages to accommodate its KV cache via the Block Table, mirrors the heterogeneous structure of attention—assigning which maps physical page addresses to specific Request IDs more budget to broadly-attending heads and less to narrowly(❷). For every iteration, the scheduler allocates the required attending ones—thereby aligning the retained tokens with pages, computes their physical addresses, and dynamically each head’s intrinsic concentration pattern and avoiding the adjusts the overall KV cache usage, all orchestrated by the systematic output deviation induced by uniform truncation. host CPU as part of the control plane. The block table tracks Non-uniform KV compression [9, 10, 16] addresses this misthe total number of allocated pages, which dictates the effecalignment by removing the uniform-budget constraint. It flattive KV cache size required for attention operation, implicitly flat tens importance scores across all heads (𝑠 ℓ = concatℎ (𝑠 ℓ,ℎ ) ∈ assuming a static, uniform per-token memory cost. R𝐻 𝑁 ) and selects tokens via a layer-wide budget: 𝐼 ℓ = Top(𝑀, 𝑠 ℓflat ). As shown in Figure 2(a), this yields a highly irregular per2.2.2 PagedAttention. In the Generate KV Cache stage, head KV cache budget—some heads retain their full histhe GPU worker materializes the KV cache slots pre-allocated tory of tokens while others are heavily pruned, resulting by the scheduler through the forward pass (❸–❹ in Figure 3), in up to a 42× disparity in per-head KV cache sizes. Cruwriting generated KV entries into KV Cache Blocks based on cially, Figure 2(b) demonstrates that this head-wise budgetthe pre-determined block addresses. To eliminate memory heterogeneity preserves high conversational accuracy even fragmentation, these entries are stored non-contiguously in 3
Hyungmin Kim, Minsoo Kim, Hongseok Kim, and Jungwook Choi
modern LLM serving—Continuous Batching, PagedAttention, and optimized attention kernels—are all architected under the assumption that KV cache lengths are uniform across attention heads. Non-uniform compression breaks this assumption, leading to three major limitations: Monolithic Page Structure (§3.1.1), Dynamic Page Reclamation Bottleneck (§3.1.2), and Workload Imbalance (§3.1.3). We analyze each in turn, establishing the motivation for the three corresponding techniques proposed in §4.
: Retained KV : Fragmentation
Req ID # Pages .. ..
(a) H1 H2 H3 H4 H1 H2 H3 H4 ... H1 H2 H3 H4 Layer 1 Layer 2 ... Layer L
(b)
Page Usage: Running Request
Usage: 40%
Yes Running Reqs
Scheduling Workflow
...
Blk2
Blk3
Blk4
BlkN-1
GPU Thread Blocks
BlkN
(Runtime)
Extra Cost
Compressed Pages
...
(c)
100% Non-uniform Compression
calc usage() Runnable?
Blk1
4
Block Table 60%
Waiting Reqs
No (Stall)
N
Usage: 10%
3.1
Page Pool
Return to Page Pool
// Each Head is split into num splits TBs int head idx = blockIdx.x / num splits; Launch int split idx = blockIdx.x % num splits; Kernel int tid = threadIdx.x; // Load partitioned K, V for this split shared float smem[...]; // Compute Partial Attention Score compute attn(head idx, split idx, tid);
Figure 4. Challenges posed by non-uniform KV compression. (a) Monolithic Page Structure: unified pages span all heads, causing page fragmentation (red dashed line: pages allocated per request). (b) Dynamic Page Reclamation: reclaiming scattered pages at runtime incurs severe control-plane overhead. (c) Workload Imbalance: uniform KV splits across thread blocks cause stragglers under different per-head KV lengths.
3.1.2 Dynamic Page Reclamation Bottleneck. The second limitation stems from the interaction between nonuniform compression and the scheduler’s control plane (§2.2.1). As illustrated in Figure 4(b), the scheduler must evaluate current page usage to make admission decisions at each scheduling step. However, under non-uniform compression, the specific KV cache entries to be compressed are determined dynamically based on token importance scores during the runtime forward pass. Because this compression profile remains unknown until execution, the scheduler’s static memory estimation becomes invalid, forcing a costly “compressand-reclaim” process: identifying scattered physical pages, returning them to the block pool, and updating page tables while the request is in flight. As the number of pages to be reclaimed grows, this overhead scales linearly, potentially consuming up to 25% of the total prefill execution time(as quantified in Figure 11), directly limiting overall throughput.
fixed-size blocks. A key design constraint of PagedAttention [19] is its unified page structure: a single physical block spans all layers and all attention heads simultaneously, holding 𝐿 × 𝐻 × 2 × 𝑃 × 𝑑 elements for 𝑃 consecutive tokens, making granular head-wise memory reclamation impossible. 2.2.3 Attention Kernel Optimization. FlashAttention2 [5] reduces redundant HBM–SRAM traffic via tiled, fused attention computation along the query dimension. For longcontext decoding, FlashDecoding [6] and FlashInfer [38] further introduce KV-dimension parallelism (❺ in Figure 3), where the number of splits determines how each attention head is partitioned and distributed across SMs during decode attention. While FlashDecoding [6] relies on static heuristics for partitioning, FlashInfer [38] employs a runtime planning phase to identify optimal workload strategies. This planning cost can be amortized through plan reuse: since all layers typically share identical KV structures, the system computes a single plan and reuses it across all 𝐿 layers to reduce planning overhead.
3
Limitations on existing system
3.1.1 Monolithic Page Structure. The first limitation arises directly from PagedAttention’s unified page structure (§2.2.2). Non-uniform compression produces heterogeneous retention lengths 𝐿ℓ,ℎ across heads, yet the current abstraction lacks any mechanism to manage these varying lengths per head. Because the page is the smallest unit of allocation and is shared across the entire head dimension, the system cannot granularly reclaim memory from individual heads that retain fewer tokens. Consequently, the memory savings from pruned heads remain “locked” within the unified page structure, creating what we term page fragmentation. Figure 4(a) illustrates this pathology: under unified paging, every attention head is allocated the same number of pages regardless of its actual retention, resulting in large page fragmentation.
3.1.3 Workload Imbalance. The third limitation occurs at the GPU kernel level during decode attention. GPU architectures achieve peak efficiency under the SIMT paradigm only when parallel threads process uniform workloads. Non-uniform KV compression breaks this uniformity in two distinct ways.
Motivation
While non-uniform KV compression is effective at preserving multi-turn accuracy (§2.1), deploying it on production serving systems such as vLLM [19] reveals severe systemlevel inefficiencies. As described in §2.2, the three pillars of
Straggler Effect from Static Partitioning. As shown in Figure 4(c), FlashDecoding [6] parallelizes attention by dispatching fixed-size KV chunks to GPU SMs based on a 4
64
ThreadBlock Index
96
0
32
ThreadBlock Index
(a) Uniform 1.5× 2
96
(b) Non-uniform
1.6×
Uniform Non-uniform 1.4× 1
64
1.4× 4
1.7× 8
# Requests
16
32
# Layers
Load Balancing Time (ms)
Proportion
28 32 64 80
5.64 6.48 13.27 17.13
20.20% 17.33% 15.48% 16.43%
LLaMA3.1-8B-Instruct
Figure 5. Workload imbalance on decode attention. (a) Uniform KV compression, (b) Non-uniform KV compression, (c) attention latency across different number of requests configurations on Qwen3-4B. The dashed line indicates the maximum workload among all thread blocks.
Qwen2.5-7B Llama-3.1-8B Qwen3-32B Llama-3.1-70B
100
100
1.7×
(c) Decode Latency Overhead
Model
Retention Rate (%) Code-Repo LongDocument
32
Qwen2.5-7B-Instruct
0
100
Retention Rate (%) Code-Repo LongDocument
Max
Qwen3-4B-Instruct
240 200 160 120 80 40 0
Max
Retention Rate (%) Code-Repo LongDocument
6000 4000 2000 0
Attention Latency (ms)
KV cache Size
Tangram: Unlocking Non-Uniform KV Cache for Efficient Multi-turn LLM Serving
Layer 16
Layer 17
Layer 22
50 0 100
0
1
2
3
0
1
2
3
0
1
2
3
0
1 2 Layer 17
3
0
1 2 Layer 20
3
0
1 2 Layer 24
3
50 0 50 0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
100 50
0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Layer 13 Layer 14 Layer 16
50 0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
100 50
0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Head Index Head Index Head Index
Figure 6. Per-head KV retention rates (%) under nonuniform compression across three model families (Qwen2.57B, Qwen3-4B, LLaMA3.1-8B) and two long-context domains (LongDocument, Code-Repo) from SCBench [23], shown for three selected layers per model. Each box plot aggregates results over 50 input samples.
Table 1. Load balancing overhead. Proportion denotes the fraction of the total decode inference step time spent on the load balancing phase.
num_splits parameter applied uniformly across all heads— a heuristic valid only when every head has the same context length. Under non-uniform compression, per-head KV lengths can vary by up to 42×. As illustrated in Figure 5(a–b), this heterogeneity produces highly skewed per-thread-block workloads: blocks mapped to long-context heads become heavy while short-context blocks finish early and idle. The overall decoding step is gated by the few SMs executing the heaviest blocks, increasing decode attention latency by up to 1.7× compared to the uniform baseline under the same total KV cache size (Figure 5(c)).
3.2
Key Observation and System Design
The three limitations identified in §3.1 share a common root assumption: that the per-head KV retention profile is unpredictable at scheduling time, forcing the system to defer all memory and compute decisions to runtime. Our empirical analysis challenges this assumption. As shown in Figure 6, per-head retention rates are highly heterogeneous within a layer, yet each head exhibits a largely stable retention level across inputs—the narrow box widths for each head indicate low variance across the 50 samples. While the absolute retention values may shift moderately across domains (LongDocument vs. Code-Repo), the relative ranking among heads within a layer is consistently preserved, and this pattern holds across all three model families (Qwen2.5-7B, Qwen34B, LLaMA-3.1-8B). This confirms that the per-head retention profile is input-independent and model-intrinsic—each head demands a different budget, but that budget is a stable property of the model rather than the input. This stability fundamentally reframes the three limitations in §3.1: what appeared to be rigid structural constraints and unavoidable runtime uncertainty are, in fact, a statically resolvable property. By profiling each head’s budget offline
Prohibitive Cost of Dynamic Rebalancing. FlashInfer [38] addresses workload imbalance through a runtime planning phase before each decoding step. Under uniform settings, plan reuse amortizes this cost: a single plan is computed once and reused across all 𝐿 layers. Non-uniform compression invalidates this optimization—retained KV lengths differ independently across layers, forcing the planner to recompute a unique partition for every layer at every decoding step. As shown in Table 1, this per-layer planning overhead consumes 15–20% of the total decode iteration time, negating the GPU utilization gains that dynamic balancing is meant to provide. 5
Hyungmin Kim, Minsoo Kim, Hongseok Kim, and Jungwook Choi
once per model, all three sources of overhead can be converted into deterministic, pre-scheduled decisions:
estimates stable across inputs and thus directly compatible with offline profiling. Its lightweight gate (<1% of model parameters) further keeps the runtime compression overhead negligible. Given a small set of sample contexts, we run compression under a target global budget 𝑀 and record each head’s retained length. From these samples, we compute the per-head mean 𝜇ℓ,ℎ and standard deviation 𝜎ℓ,ℎ . While the budget concentration pattern is consistent, providing critical heads with only their mean allocation leaves no room for input-dependent fluctuations. We therefore adopt a static budget allocation that adds a controlled safety margin to each head’s budget:
1. Deterministic Budget Allocation (§4.1): Since each head’s memory footprint is statically known, the scheduler can allocate exactly the required pages before execution, entirely eliminating the dynamic compressand-reclaim bottleneck. 2. Head Group Page (§4.2): With fixed per-head budgets known in advance, heads with similar retention demands can be clustered into independent page tables, enabling true physical memory reclamation and breaking the monolithic page fragmentation. 3. Ahead-of-Time (AOT) Load Balancing (§4.3): Since the computational shape of each head group is fixed, optimal GPU workload partitions can be precomputed offline, achieving balanced SM utilization with zero runtime planning overhead.
4
𝐵 ℓ,ℎ = min 𝐿input, 𝜇ℓ,ℎ + 𝛼 · 𝜎ℓ,ℎ , where 𝛼 is a safety margin coefficient and 𝐿input is the input sequence length. Because critical heads have inherently high 𝜇ℓ,ℎ , this formulation concentrates the additional margin where it matters most—ensuring sufficient capacity for the heads that dominate accuracy—while keeping the remaining heads tightly compressed. At inference, given the key and value tensors 𝐾ℓ,ℎ , 𝑉ℓ,ℎ ∈ R𝑁 ×𝑑 and per-token importance scores 𝑠 ℓ,ℎ , compression reduces to a simple per-head top-𝑘 selection using the predetermined budget: Given the per-token importance scores 𝑠 ℓ,ℎ :
Methodology
We present Tangram, a holistic serving framework designed to reconcile the theoretical efficiency of non-uniform KV cache compression with the practical constraints of highthroughput serving. By leveraging the intrinsic stability of head-wise importance (§ 3.2), Tangram transforms KV cache heterogeneity into a deterministic optimization target. To achieve this, we systematically optimize the three fundamental stages of the serving pipeline—scheduling, memory management, and execution—through the following core techniques:
𝐼 ℓ,ℎ = Top(𝐵 ℓ,ℎ , 𝑠 ℓ,ℎ ), eℓ,ℎ = 𝐾ℓ,ℎ [:, 𝐼 ℓ,ℎ , :], 𝐾 𝑉eℓ,ℎ = 𝑉ℓ,ℎ [:, 𝐼 ℓ,ℎ , :]. Since each head’s budget 𝐵 ℓ,ℎ is a static value, the postcompression memory footprint is fully predictable before execution.
System Overview. Tangram is composed of three main components: (1) Deterministic Budget Allocation, which uses offline-profiled head-wise budgets 𝐵 ℓ,ℎ to replace dynamic, input-dependent compression with a fixed memory allocation (§ 4.1). (2) Head Group Page, which clusters attention heads with similar retention demands and assigns each group its own page table, thereby maximizing memory reclamation under non-uniform KV cache (§ 4.2). (3) Ahead-of-Time (AOT) Load Balancing, which leverages these predetermined budgets to ensure balanced GPU execution with zero runtime planning overhead (§ 4.3). 4.1
Robustness of Static Budget. A natural concern is whether profiles derived from a small pilot set generalize to unseen data. As shown in Figure 6, the narrow per-head variance across 50 random samples from diverse tasks confirms that a handful of profiling samples suffice, and the allocation generalizes well beyond the profiling set. Furthermore, as shown in §5.2, profiles calibrated on these pilot samples maintain high conversational accuracy across diverse, independent multi-turn benchmarks.
Deterministic Budget Allocation
Precise Page Allocation. By using the offline-calibrated per-head budgets {𝐵 ℓ,ℎ }, Tangram transforms the dynamic memory requirement into a known constant. This eliminates the unnecessary page management overhead caused by unpredictable post-compression memory sizes. As illustrated in Figure 7(a), the scheduler allocates memory based on the pre-determined budgets, removing the need for runtime page reclamation entirely:
Tangram eliminates the dynamic evict-and-reclaim bottleneck by replacing runtime-decided compression with a deterministic budget allocation derived from offline profiling of per-head KV retention profiles. 4.1.1 Offline Profiling and Static Assignment. Rather than deciding per-head budgets at runtime, we determine them through a one-time offline profiling step. We adopt FastKVzip [15], which matches the accuracy of state-of-theart non-uniform compression [7, 16] while remaining queryagnostic—a property that makes its per-head importance
M (𝑟 ) = 6
𝐿 ∑︁ 𝐻 ∑︁ ℓ=1 ℎ=1
𝐵 ℓ,ℎ × 𝐷 head · Sdtype
(1)
(c) Prefill + Compression
(a) Deterministic Budget Allocation
H8
Compress
Full KV Cache (b) Scheduling Policy Ad
H1
...
H8
Non-uniform KV
Head Group Index
: Retained KV
budget
budget
...
(d) Head Group Page
Execution Timeline
GPU SMs G1
G2
G3
G4
G1
G2
G3
G4
G1
G1
G1
G1
G1
G1
G2
G3
G4
G4
G4
G4
G4
G4
Group ID
KV Length
1
8192
Load-Balanced Attention
2
256
Group Idx Budget
.. .
3
200
Head Group Page Pool
N
GPU KV Blocks
Token Index Reshape and Cache Update retained KV only
d: decode, c: compression, p: prefill
+
(e) AOT Load Balancing
Total KV Length
: Request B Entered
Ad , Bp +c Ad , Bp +c Ad , Bp +c Ad , Bp +c 1 1 2 2 2 3 4 4
: Compressed KV
LM Head
FFN Layer
+
LayerNorm
Out Proj
Attention (Prefill + Decode)
Harry ... Room 402... room number?
H1
RoPE
forward
Worker
QKV Proj
Scheduler
LayerNorm
Request
Embedding
Tangram: Unlocking Non-Uniform KV Cache for Efficient Multi-turn LLM Serving
0%
. . .
100%
3072
Head Group Page Table
Splits
1 2 3
8K 1K 1K
6 1 1
𝑁
2K
2
. . .
. . .
. . .
Split-KV Table
Figure 7. System overview of Tangram. where 𝐷ℎ𝑒𝑎𝑑 is the head dimension and S𝑑𝑡 𝑦𝑝𝑒 is the size of the data type (e.g., FP16). This formulation empowers the scheduler to perform precise resource planning. Since M (𝑟 ) represents the guaranteed maximum memory footprint required for the prefill and compression phase, the scheduler can aggressively batch requests up to the true physical limit of the GPU. As depicted in Figure 7(c), a prefill request generates the KV cache and unnecessary entries are immediately compressed. Consequently, the page pool allocates only the exact number of pages required, avoiding any over-provisioning. This effectively unlocks the full potential of integrating non-uniform KV compression with continuous batching, particularly in multi-turn workloads characterized by a massive KV cache footprint.
For each layer ℓ, we utilize the offline-calibrated budget tensor B to cluster the 𝐻 total heads into 𝑁 = 𝐻 /𝐺 groups. We achieve this by sorting the entire set of heads globally according to their static budgets 𝐵 ℓ,ℎ . Formally, let 𝜋ℓ be a permutation of the head indices for layer ℓ such that their retention budgets are monotonically increasing: 𝐵 ℓ,𝜋ℓ (0) ≤ 𝐵 ℓ,𝜋ℓ (1) ≤ · · · ≤ 𝐵 ℓ,𝜋ℓ (𝐻 −1) The 𝑖-th head group, Gℓ,𝑖 , is then constructed by taking 𝐺 elements from this sorted sequence: Gℓ,𝑖 = {𝜋ℓ ( 𝑗) | 𝑗 ∈ [𝑖 · 𝐺, (𝑖 + 1) · 𝐺 − 1]} By clustering heads with similar static retention rates, the maximum budget within any group closely approximates the individual budgets of its members. This tightly bounds the required physical memory allocation and effectively minimizes intra-group variance.
4.1.2 Deterministic Resource Scheduling. As discussed in §3.1.2, dynamic page reclamation introduces prohibitive control-plane overhead that directly degrades throughput. With each head’s budget statically determined, Tangram integrates compression directly into the prefill phase, as shown in Figure 7(b), allowing them to execute together. Consequently, the system allocates exactly the predetermined number of pages from the outset, completely bypassing any costly “compress-and-reclaim” operations and eliminating the scheduling bottleneck. 4.2
4.2.2 Head Group Page Table. Following the clustering phase, we decouple the global memory management by assigning an independent page table to each clustered group Gℓ,𝑖 . Instead of maintaining a monolithic global page table that enforces a rigid, uniform memory layout across all attention heads, this architecture isolates allocation decisions down to the head group level. Consequently, the physical page allocation for a specific group is strictly determined by the local maximum requirement within that cluster, rather than the global maximum across the entire layer:
Head Group Page
4.2.1 Head Group Clustering. To optimally enable physical memory reclamation, Tangram introduces a budgetaware Head Group Clustering strategy. Because a page table must structurally accommodate the shared KV cache length within its group, combining heads with drastically different retention requirements forces heads with small budgets to allocate unnecessary capacity. Therefore, we group attention heads based on their budget similarity.
Target Capacity(Gℓ,𝑖 ) ∝ max 𝐵 ℓ,ℎ ℎ∈ Gℓ,𝑖
As depicted in Figure 7(d), this decoupled architecture manages each head group with its own distinct KV cache length, ensuring that short-retaining heads are no longer 7
Hyungmin Kim, Minsoo Kim, Hongseok Kim, and Jungwook Choi
(a)
Free Page
Algorithm 1 AOT Workload Partitioning with Head Group
40
6.0
Require: Calibrated budget tensor B ∈ N𝐿×𝐻 where 𝐿 is the number of layers and 𝐻 is the number of KV heads, available CTAs 𝑁 CTA , head group size 𝐺 Ensure: Static split map S ∈ N𝐿× (𝐻 /𝐺 ) 1: S ← 1𝐿× (𝐻 /𝐺 ) ⊲ initialize split factors per head group 2: for ℓ ← 1 to 𝐿 do Í𝐻 3: Ωℓ ← ℎ=1 𝐵 ℓ,ℎ ⊲ total KV budget of layer ℓ 4: if Ωℓ = 0 then continue 5: end if 6: 𝜏ℓ ← max 1, ⌈Ωℓ /𝑁 CTA ⌉ ⊲ target per-split budget 7: for 𝑖 ← 0 to 𝐻 /𝐺 − 1 do ⊲ iterate over head groups 8: G𝑖 ← {ℎ | ℎ ∈ [𝑖 · 𝐺, (𝑖 + 1) · 𝐺 − 1]} ⊲ heads in group 𝑖 Í 9: Φℓ,𝑖 ← ℎ∈ G𝑖 𝐵 ℓ,ℎ ⊲ aggregated group budget 10: 𝑆 ℓ,𝑖 ← max 1, ⌈Φℓ,𝑖 /𝜏ℓ ⌉ ⊲ split factor for group 𝑖 11: end for 12: end for 13: return S
Unified Page(vLLM)
4 2 0
# Pages (K)
6
(b)
Head Group Page (G=4)
4 2 0
0
20
40
60
80
100
Attn Head Index (Sorted)
30
Block Table Vectorized Block Table Page Fragmentation
4.0
20
3.0 2.0
10 0 1
5.0
Fragmentation (GB)
# Pages (K)
6
Page Fragmentation
Normalized Overhead (x)
KV Cache
1.0 2 4 8 16 32 64
0.0
Head Group Size (G) (c)
Figure 8. Comparison of Unified Page and Head Group Page on Qwen2.5-7B under 100K single-request input with 25% KV cache compression: (a) Unified Page (vLLM), where all heads share a single page; (b) Head Group Page (𝐺 = 4), where each head group maintains its own independent page; and (c) page fragmentation versus management overhead as a function of head group size 𝐺.
Maximizing CPU Efficiency. To resolve this bottleneck, we replace sequential CPU computation with a Vectorized Execution Model. Instead of iterating through each group’s page table sequentially, we aggregate the block mappings of multiple groups into a vectorized format, utilizing OpenMP to parallelize block-table operations across head groups and CPU SIMD intrinsics (e.g., AVX-512) to process data within each group. As shown in Figure 8(c), this design exposes the trade-off between page fragmentation and management overhead as a function of 𝐺, while the Vectorized Block Table substantially reduces CPU-side overhead, effectively shifting this curve downward. This enables the use of fine-grained group sizes to maximize memory savings without degrading end-to-end serving throughput.
structurally bound by the memory demands of the longestretaining ones. As illustrated in Figure 8, when the management granularity collapses to a single global group (Figure 8(a)), allocation is dictated by the single longest attention head. In contrast, with Head Group Page (Figure 8(b)), page allocation and reclamation are resolved independently per head group, immediately reclaiming freed capacity from short-retention groups and maximizing effective GPU memory. Balancing Memory Gain and Management Overhead. The group size 𝐺 introduces a fundamental trade-off: • Memory Efficiency: Larger 𝐺 reduces metadata overhead but increases intra-group budget disparity, leading to residual fragmentation. Smaller 𝐺 tightens budget alignment, minimizing dead space and maximizing memory efficiency. • Block Management Overhead: Smaller 𝐺 necessitates maintaining more distinct page tables (up to 𝐻 in the extreme case of 𝐺 = 1), increasing allocation, compression, and block table update operations by 𝐻 /𝐺 per request, which can become a host-side bottleneck.
4.3 Ahead-of-Time (AOT) Load Balancing: Mitigating Workload Imbalance Finally, we address the computational bottleneck caused by workload skew across GPU Streaming Multiprocessors (SMs) on decode attention operation (§ 3.1.3). Existing dynamic load balancing schemes fail in non-uniform KV cache due to the prohibitive cost of per-layer runtime planning, which must be repeated 𝐿 times for every decoding step. Tangram circumvents this overhead by leveraging the stability of the fixed budget allocation mechanism described in § 4.1. Because the memory footprint per head is static, the computational load is fully predictable, allowing us to shift the load-balancing burden entirely from the critical runtime path to an offline stage.
To resolve this challenge, we select an appropriate group size 𝐺 that offers a balanced operating point, and introduce a Vectorized Block Table to mitigate the management complexity arising from multiple page tables. 4.2.3 Vectorized Block Table Management. In a naive implementation, block-table complexity scales with the number of groups, raising the per-step scheduling cost to O (𝑁𝑟𝑒𝑞 × 𝐻 /𝐺). For fine-grained grouping (small 𝐺), this makes blocktable management a bottleneck in the CPU-side scheduler.
4.3.1 Ahead-of-Time (AOT) Workload Partition Map. As shown in Figure 7 (e), Since the per-head budget 𝑘ℎ is determined offline and remains constant across requests, the 8
Tangram: Unlocking Non-Uniform KV Cache for Efficient Multi-turn LLM Serving
Evaluation
5.1
Evaluation Setup
30 50
75
100
Retention Rate (%) Avg. Score
40 20
25
50
75
100
Retention Rate (%)
Avg Score 25
50
75
TANGRAM Qwen2.5-32B (TP=2) 40 30
100
Retention Rate (%) Avg. Score
50 40 30
60
Avg Score
60
Short
100
40
25
Avg Score
75
20
Retention Rate (%) Avg. Score
Avg Score
Mid
Avg Score
50
50
30
Avg Score
20
40
25
50
75
Retention Rate (%) Avg. Score
40 25
50
75
50
75
100
25
50
75
100
25
50
75
100
50 45 40
70
100
Retention Rate (%)
25
Retention Rate (%) Avg. Score
100
Avg Score
40
25
Retention Rate (%) Avg. Score
60 50
Retention Rate (%)
Figure 9. Accuracy performance across Short, Mid, and Long context scales under varying KV cache retention rates. All results are based on non-uniform compression.
budgets derived from offline 50 pilot samples, setting the safety coefficient 𝛼 to 2 across all evaluations. To systematically quantify the performance gains of our framework across varying context scales, we partition the evaluation tasks into three categories: (1) Short (< 20K tokens), including Many-Shot, LoCoMo, and RealTalk (2) Mid (20K–100K tokens), covering RepoQA, Multi-Choice QA, and MathFind tasks that exercise moderate-to-heavy context accumulation and require selective retrieval over substantial histories; and (3) Long (> 100K tokens), encompassing Retrieve Prefix-Suffix, KV, Summary, and LongMemEval, where the KV cache footprint of even a few requests dominates GPU memory. Together, these workloads comprehensively evaluate the scalability and efficiency of Tangram across the full spectrum of context lengths encountered in multi-turn LLM serving.
Runtime Execution. As depicted in Figure 7(e), during the decoding phase, Tangram simply retrieves this precalculated table S to configure the attention kernel. Unlike dynamic schedulers that incur significant CPU latency calculating partitions for every layer at every step, our approach incurs zero runtime scheduling overhead. By reusing the static plan across all decoding steps, Tangram achieves the high GPU utilization of load-balanced execution without the latency penalty associated with online planning.
5
KVzip Fast KVzip Qwen2.5-7B-Instruct-1M Avg Score
Long
Static Partitioning Strategy. To maximize hardware utilization, we first leverage the CUDAMaxOccupancy API to determine the total number of Cooperative Thread Arrays (CTAs), denoted as 𝑁 CTA , that the target GPU can execute concurrently for the attention kernel. This value represents the device’s aggregate parallelism capacity. We then employ an Ahead-of-Time (AOT) Workload Partitioning algorithm (Algorithm 1) to distribute these CTAs across head groups proportional to their aggregated computational weight. Specifically, each head group’s budget Φℓ,𝑖 is computed by summing the retained KV cache entries across all heads within the group. Head groups with large aggregated budgets are assigned higher partition factors, while groups with small aggregated budgets are assigned fewer partitions. The output is stored in the static Workload Partition Table S, where each entry 𝑆 ℓ,𝑖 dictates exactly how many thread blocks should be allocated for head group 𝑖 in layer ℓ. This ensures that the total work assigned to each SM is approximately equal, thereby eliminating tail latency in which the entire system stalls while waiting for a single overloaded SM to complete.
Avg Score
SnapKV Qwen3-4B
"shape" of the computation is known before inference. We pre-calculate a static Workload Partition Table S ∈ N𝐿× (𝐻 /𝐺 ) to enforce perfectly balanced parallelism.
Models and Workloads. We evaluate Tangram on three models—Qwen3-4B, Qwen2.5-7B-Instruct-1M, and Qwen2.532B—each supporting context lengths exceeding 100K context windows, which is necessary for capturing the massive context accumulation that arises in multi-turn LLM serving. To rigorously assess performance under such scenarios, we adopt four benchmarks: SCBench [23], LoCoMo [26], RealTalk [20], and LongMemEval [34], each specifically designed to evaluate long-context capabilities through sharedcontext, multi-turn interactions. Together, these benchmarks provide a diverse suite of tasks spanning retrieval, reasoning, summarization, and code understanding over extended dialogue histories, making them well suited for stress-testing both the accuracy and efficiency of KV cache management strategies in realistic serving conditions. For Tangram’s deterministic budget allocation, we utilize pre-determined
System Setup. We implement Tangram on top of vLLM [19], a state-of-the-art high-throughput serving framework. To support our proposed non-uniform KV cache compression, we integrate specialized CUDA kernels developed based on FlashAttention [5], ensuring our custom operators remain fully compatible with standard attention interfaces 1 . All end-to-end experiments are conducted on a dedicated server node equipped with an Intel(R) Xeon(R) Gold 6326 CPU @ 2.90GHz (16 physical cores) and four NVIDIA A100 GPUs (80GB Memory each). We emphasize that all reported results—including throughput, latency, and fragmentation 1 Our customized vLLM implementation remains fully compatible with the
open-source frameworks and will be released to the community to accelerate innovation. 9
Hyungmin Kim, Minsoo Kim, Hongseok Kim, and Jungwook Choi TANGRAM (w/ Det. Budget, Head Group Page) TANGRAM (w/ Det. Budget, Head Group Page, Load Balancing)
Qwen3-4B Short Throughput (Req/s)
1.00 ×2.5 0.75 0.50 0.25 0.00 0%
Qwen2.5-7B-1M
25%
50%
75%
×2.1
Mid Throughput (Req/s)
0.100 0.075 0.050 0.025 0.000 0%
Long Throughput (Req/s)
0.03
0.04
0.2
25%
50%
75%
25%
50%
75%
×2.3
0.00 0%
25%
50%
75% 0.000 0%
Eviction Rate (%)
25%
50%
75%
25%
50%
75%
0.005 75% 0.000 0%
Eviction Rate (%)
600
+13.3%
0 Ours Dyn. Comp 25%.
Comp 50%.
400 200 Ours Dyn.
Qwen3-4B
Model Execution +24.9% 800
etc.
+10.4%
+15.3%
600 400 200 0 Ours Dyn. Ours Dyn. Comp 75%. Comp 25%.
Comp 50%.
Ours Dyn.
Qwen2.5-7B
Page Reclaim +20.0%
Ours Dyn.
Comp 75%.
Figure 11. Latency breakdown across various compression rates. While dynamic allocation incurs significant page reclamation overhead that scales with the eviction rate, Tangram’s deterministic budget allocation completely eliminates this extra cost, operating with zero page reclaim overhead.
0.010
50%
Eviction +19.3%
75%
0.015 ×2.0
25%
Page Allocation
×2.5
75% 0.000 0%
0.005 50%
50%
0.002
0.010 25%
25%
0.004
0.015
0.01
0.0 0% 0.006
0.020 ×1.8
×2.1
×2.0
0.1
0.02
0.02 0.00 0%
0.8 ×2.1 0.6 0.4 0.2 0.0 0%
Qwen2.5-32B(TP=2)
Latency (ms)
vLLM TANGRAM (only Det. Budget)
Eviction Rate (%)
Throughput (req/s)
Figure 10. Throughput performance breakdown on the multi-turn [20, 23, 26, 34] benchmark across various compression rates. Results are measured with a head group size of 𝐺 = 4, where the compression rate denotes the percentage of the KV cache removed.
Qwen3-4B
Evict 25%
0.12
0.05
0.1
0.04
0.08 0.06
Evict 50%
Qwen2.5-7B-1M
Evict 75%
0.03 1 2 4 8 16 32 64
Head Group Size (G)
Qwen2.5-32B(TP=2)
0.007 0.006 0.005 0.004 1 2 4 8 16 32 64
Head Group Size (G)
1 2 4 8 16 32 64
Head Group Size (G)
Figure 12. Throughput across various compression rates by head group size (𝐺). Small 𝐺 minimizes fragmentation but incurs high management overhead, while large 𝐺 fails to effectively reclaim memory.
rates—are empirical measurements obtained from actual runtime execution on this hardware, rather than analytical estimates or simulations.
proposed technique to the end-to-end throughput improvement; (2) Prefill Latency Breakdown to analyze the efficiency gains from Deterministic Budget Allocation; (3) Decode Attention Latency to validate the effectiveness of AOT Load Balancing; and (4) TTFT and Effective Batch Size to verify serving performance under realistic multi-turn scenarios.
Baselines. To rigorously evaluate the effectiveness of our proposed load balancing and memory management, we compare Tangram against two primary baselines representing the state-of-the-art in attention optimization. First, we compare against FlashAttention-2 [5], which utilizes a Split-KV strategy to parallelize attention. While effective for uniform KV cache, this baseline highlights the inefficiencies caused by static, heuristic-based partitioning in non-uniform KV cache where workload skew leads to severe straggler issues. Second, we compare against FlashInfer [38], which employs a sophisticated run-time planning algorithm to minimize imbalance. This baseline serves to demonstrate the "Plan Reuse" bottleneck: we show that while FlashInfer is efficient for uniform workload, the necessity of recalculating unique scheduling plans for every heterogeneous layer in non-uniform workload introduces prohibitive CPU latency (approx. 10% of decoding time) that negates the benefits of GPU parallelism.
5.2
Multi-turn Accuracy Evaluation
We first evaluate the impact of different KV compression strategies on Multi-turn benchmark accuracy. The primary objective of this experiment is to quantify the accuracy degradation trade-off associated with aggressive KV cache compression. As summarized in Figure 9, Tangram achieves performance parity with KVzip [16], a state-of-the-art nonuniform KV compression method [7]. Notably, even when we enforce a deterministic budget for each Attention Head Group, our method maintains performance levels comparable to, or in some cases exceeding, baseline non-uniform compression strategies. We attribute this robustness to the stabilizing effect of our static budget allocation. Dynamic compression can produce extreme budget disparity across heads, where certain critical heads are occasionally assigned disproportionately low budgets. Because Tangram fixes each head’s budget to its offline-calibrated value, such pathologically low allocations are structurally prevented. The deterministic assignment effectively acts as a lower bound guarantee, ensuring that no individual head is critically starved of context. Consequently, Tangram successfully reconciles
Performance Metrics. Our evaluation relies on a comprehensive set of metrics covering both model quality and system efficiency. For Multi-turn LLM Serving capability, we report the average score across Short, Mid, and Long categories for each model, based on the accuracy metrics provided by each benchmark. For system performance, we focus on four key indicators: (1) Throughput (requests per second), which demonstrates overall system capacity under varying load conditions and isolates the contribution of each 10
Tangram: Unlocking Non-Uniform KV Cache for Efficient Multi-turn LLM Serving
Attention Latency (ms)
FlashInfer
FlashAttn
Qwen3-4B
15 10 5 0
0%
25% 50% 75% Eviction Rate (%)
AOT-LB
Qwen2.5-7B 20 15 10 5 0
30
Impact of Head Group Page. Head Group Page is the key mechanism that translates non-uniform compression into actual memory savings by enabling independent page reclamation at the head group level. However, as discussed in §4.2.2, the choice of head group size 𝐺 introduces a fundamental trade-off: excessively small 𝐺 proliferates the number of page tables, increasing management overhead that degrades system performance, while excessively large 𝐺 prevents the system from reclaiming evicted pages, as the group’s allocation remains dictated by its longest-retaining head. As shown in Figure 12, we observe that a group size of 𝐺 = 4–8 strikes the optimal balance, yielding the highest end-to-end throughput across all configurations.
Qwen2.5-32B(TP=2)
20 10 0%
25% 50% 75% Eviction Rate (%)
0
0%
25% 50% 75% Eviction Rate (%)
Figure 13. Attention latency evaluated under the impact of AOT (Ahead-Of-Time) load balancing (fixed batch size of 4).
TANGRAM Qwen2.5-7B 100 75 50 25 0
RPS (Request Per Second)
Efficient Load Balancing. As shown in Figure 13, our AOT Load Balancing consistently achieves the lowest decode attention latency. FlashDecoding suffers from straggler effects due to its heuristic static partitioning, while FlashInfer incurs significant overhead from recomputing per-layer partitions at every decoding step. Tangram avoids both issues by pre-calculating optimal workload partitions offline, achieving balanced SM utilization with zero runtime cost.
0.0 2 0.05 5 0 0.1.1 5 0 0.3.2 5 0 0.7.5 5 1.0 1.5 2.0
0.0 2 0.05 5 0 0.1.1 5 0 0.3.2 5 0 0.7.5 5 1.0 1.5 2.0
Mean TTFT (s)
100 75 50 25 0
vLLM Qwen3-4B
RPS (Request Per Second)
Figure 14. TTFT (Time-To-First-Token) under increasing throughput pressure with 30K average request lengths is maintained through deterministic budget allocation and Head Group Page with a 75% compression rate.
6 high accuracy with efficient memory management, providing a robust foundation for high-throughput multi-turn LLM serving. 5.3
Related Works
Multi-turn LLM Serving. As LLMs evolve into persistent assistants, maintaining user-specific context across sessions has become critical [1, 3, 27, 31]. Recent benchmarks like SCbench [23], RealTalk [20] and LoCoMo [26] highlight the difficulty of recalling long-horizon details, motivating algorithmic solutions such as retrieval augmentation [4, 17, 44]. However, prior work largely overlooks the serving efficiency of these memory-intensive workloads. Our work bridges this gap by addressing the system bottlenecks of managing the rapidly scaling KV cache required for robust long-term memory.
End-to-end Performance
We evaluate the serving throughput of Tangram against the vLLM baseline. As shown in Figure 10, Tangram successfully translates non-uniform KV compression into practical system-level gains, achieving up to a 2.6× throughput improvement with effective memory management and iteration-based non-uniform compression strategy. This capacity gain also translates into better latency under heavy load: under 75% compression, Tangram sustains low TTFT as the request rate grows, whereas vLLM’s TTFT rises sharply (Figure 14). To isolate the contribution of each proposed technique, we incrementally apply Deterministic Budget Allocation(§ 4.1), Head Group Page(§ 4.2), and AOT Load Balancing(§ 4.3). The results confirm that each component provides additive throughput gains, collectively bridging the gap between theoretical KV cache reduction and realized system performance.
KV Cache compression. Compression techniques are essential for reducing memory pressure. Uniform compression enforces uniform retention across all attention heads [14, 18, 22, 28, 42], simplifying management but often discarding context essential for specific heads. In contrast, non-uniform compression improves accuracy by allowing heterogeneous retention budgets [9, 10, 16, 36]. While algorithmically superior, non-uniform methods have been impractical for deployment due to system-level incompatibilities. We identify and resolve the core barriers—fragmentation, scheduling uncertainty, and workload imbalance—to make non-uniform compression viable in production.
Eliminating Page Reclamation Overhead. As shown in Figure 11, dynamic compression imposes severe overhead, with page reclamation consuming up to 25% of prefill execution time to track and reclaim scattered pages. In contrast, Tangram incurs zero extra cost. Because Deterministic Budget Allocation defines the exact memory footprint before execution, our system allocates only the required pages from the outset, completely eliminating the need to perform any page reclamation.
Heterogeneous Memory Management. While traditional serving systems strictly assume uniform KV cache allocations, recent efforts have begun exploring heterogeneous memory management to accommodate diverse model architectures and compression schemes. For instance, Jenga [40] manages KV heterogeneity across layer types in hybrid [8, 11
Hyungmin Kim, Minsoo Kim, Hongseok Kim, and Jungwook Choi
25, 33] models, but does not target the explosive KV cache growth that dominates multi-turn serving. DiffKV [41] compresses the KV caches with sparsity and quantization, yet manages each head independently and does not capture the structural regularity across heads. Tangram instead exploits the observation that the set of critical heads is stable and model-intrinsic, clustering heads with similar retention demands into Head Group Pages, each managed by an independent page table. This grouping mechanism structurally aligns the page boundary with the actual retention distribution, converting compressed tokens into physically reclaimable memory rather than trapped fragmentation. By tuning the group size to balance fragmentation reduction against pagetable proliferation, Tangram keeps the CPU-side controlplane overhead bounded, making head-level heterogeneous memory management practical for high-throughput serving.
7
hybrid-head architecture for small language models. arXiv preprint arXiv:2411.13676 (2024). [9] Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, and S Kevin Zhou. 2024. Ada-kv: Optimizing kv cache eviction by adaptive budget allocation for efficient llm inference. arXiv preprint arXiv:2407.11550 (2024). [10] Yu Fu, Zefan Cai, Abedelkadir Asi, Wayne Xiong, Yue Dong, and Wen Xiao. 2025. Not All Heads Matter: A Head-Level KV Cache Compression Method with Integrated Retrieval and Reasoning. In The Thirteenth International Conference on Learning Representations. https://openreview.net/forum?id=FJFVmeXusW [11] Ravi Ghadia, Avinash Kumar, Gaurav Jain, Prashant J. Nair, and Poulami Das. 2025. Dialogue Without Limits: Constant-Sized KV Caches for Extended Response in LLMs. In Forty-second International Conference on Machine Learning. https://openreview.net/forum?id= SuYO70ZxZX [12] Abhiram Rao Gorle, Amit Kumar Singh Yadav, and Tsachy Weissman. 2025. Quantifying Information Gain and Redundancy in MultiTurn LLM Conversations. In First Workshop on Multi-Turn Interactions in Large Language Models. https://openreview.net/forum?id= 5gpABTkcUJ [13] Yuanzhe Hu, Yu Wang, and Julian McAuley. 2026. Evaluating Memory in LLM Agents via Incremental Multi-Turn Interactions. In The Fourteenth International Conference on Learning Representations. https: //openreview.net/forum?id=DT7JyQC3MR [14] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2023. Mistral 7B. arXiv:2310.06825 [cs.CL] https://arxiv.org/abs/2310.06825 [15] Jang-Hyun Kim, Dongyoon Han, and Sangdoo Yun. 2026. Fast KVzip: Efficient and Accurate LLM Inference with Gated KV Eviction. arXiv preprint arXiv:2601.17668 (2026). [16] Jang-Hyun Kim, Jinuk Kim, Sangwoo Kwon, Jae W Lee, Sangdoo Yun, and Hyun Oh Song. 2025. KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction. Advances in Neural Information Processing Systems (2025). [17] Minsoo Kim, Arnav Kundu, Han-Byul Kim, Richa Dixit, and Minsik Cho. 2025. EpiCache: Episodic KV Cache Management for Long Conversational Question Answering. arXiv:2509.17396 [cs.CL] https: //arxiv.org/abs/2509.17396 [18] Minsoo Kim, Kyuhong Shim, Jungwook Choi, and Simyung Chang. 2024. InfiniPot: Infinite Context Processing on Memory-Constrained LLMs. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Yaser Al-Onaizan, Mohit Bansal, and YunNung Chen (Eds.). Association for Computational Linguistics, Miami, Florida, USA, 16046–16060. doi:10.18653/v1/2024.emnlp-main.897 [19] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles. 611–626. [20] Dong-Ho Lee, Adyasha Maharana, Jay Pujara, Xiang Ren, and Francesco Barbieri. 2025. Realtalk: A 21-day real-world dataset for long-term conversation. arXiv preprint arXiv:2502.13270 (2025). [21] Wonbeom Lee, Jungi Lee, Junghwan Seo, and Jaewoong Sim. 2024. {InfiniGen}: Efficient generative inference of large language models with dynamic {KV} cache management. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). 155–172. [22] Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. 2024. SnapKV: LLM Knows What You are Looking for Before Generation. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. https://openreview.net/forum?id=poE54GOq2l
Conclusion
We present Tangram, a serving system that makes nonuniform KV cache compression practical for multi-turn LLM serving. It integrates three core techniques: (1) Deterministic Budget Allocation, which converts dynamic compression into a static memory footprint, eliminating page reclamation overhead; (2) Head Group Page, which clusters heads with similar retention demands into independent page tables, translating theoretical KV cache reduction into actual memory savings; and (3) Ahead-of-Time Load Balancing, which pre-computes optimal workload partitions offline, ensuring balanced GPU utilization with zero runtime cost. Tangram delivers up to 2.6× higher throughput with minimal accuracy degradation.
References [1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 (2023). [2] Amey Agrawal, 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 (2023). [3] Anthropic. 2024. Using Claude’s Chat, Search, and Memory to Build on Previous Context. https://support.claude.com/en/articles/11817273. [4] Prateek Chhikara, Dev Khant, Saket Aryan, Taranjeet Singh, and Deshraj Yadav. 2025. Mem0: Building production-ready ai agents with scalable long-term memory. arXiv preprint arXiv:2504.19413 (2025). [5] Tri Dao. 2023. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691 (2023). [6] Tri Dao, Daniel Haziza, Francisco Massa, and Grigory Sizov. 2023. Flash-Decoding for long-context inference. https://crfm.stanford.edu/ 2023/10/12/flashdecoding.html. [7] Alessio Devoto, Maximilian Jeblick, Simon Jégou, et al. 2025. KVPress Leaderboard: Benchmarking KV Cache Compression for LLMs. https: //huggingface.co/spaces/nvidia/kvpress-leaderboard. [8] Xin Dong, Yonggan Fu, Shizhe Diao, Wonmin Byeon, Zijia Chen, Ameya Sunil Mahabaleshwarkar, Shih-Yang Liu, Matthijs Van Keirsbilck, Min-Hung Chen, Yoshi Suhara, et al. 2024. Hymba: A 12
Tangram: Unlocking Non-Uniform KV Cache for Efficient Multi-turn LLM Serving
[23] Yucheng Li, Huiqiang Jiang, Qianhui Wu, Xufang Luo, Surin Ahn, Chengruidong Zhang, Amir H Abdi, Dongsheng Li, Jianfeng Gao, Yuqing Yang, et al. 2024. Scbench: A kv cache-centric analysis of long-context methods. arXiv preprint arXiv:2412.10319 (2024). [24] Yubo Li, Xiaobin Shen, Xinyu Yao, Xueying Ding, Yidi Miao, Ramayya Krishnan, and Rema Padman. 2025. Beyond Single-Turn: A Survey on Multi-Turn Interactions with Large Language Models. arXiv:2504.04717 [cs.CL] https://arxiv.org/abs/2504.04717 [25] Opher Lieber, Barak Lenz, Hofit Bata, Gal Cohen, Jhonathan Osin, Itay Dalmedigos, Erez Safahi, Shaked Meirom, Yonatan Belinkov, Shai Shalev-Shwartz, et al. 2024. Jamba: A hybrid transformer-mamba language model. arXiv preprint arXiv:2403.19887 (2024). [26] Adyasha Maharana, Dong-Ho Lee, Sergey Tulyakov, Mohit Bansal, Francesco Barbieri, and Yuwei Fang. 2024. Evaluating Very Long-Term Conversational Memory of LLM Agents. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Lun-Wei Ku, Andre Martins, and Vivek Srikumar (Eds.). Association for Computational Linguistics, Bangkok, Thailand, 13851–13870. doi:10.18653/v1/2024.acl-long.747 [27] OpenAI. 2024. Memory and New Controls for ChatGPT. https:// openai.com/index/memory-and-new-controls-for-chatgpt/. [28] Matanel Oren, Michael Hassid, Nir Yarden, Yossi Adi, and Roy Schwartz. 2024. Transformers are Multi-State RNNs. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (Eds.). Association for Computational Linguistics, Miami, Florida, USA, 18724– 18741. doi:10.18653/v1/2024.emnlp-main.1043 [29] Pratyush Patel, Esha Choukse, Chaojie Zhang, Aashaka Shah, Íñigo Goiri, Saeed Maleki, and Ricardo Bianchini. 2024. Splitwise: Efficient generative llm inference using phase splitting. In 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA). IEEE, 118–132. [30] Reiner Pope, 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 5 (2023), 606–624. [31] Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap, Jean-baptiste Alayrac, Radu Soricut, Angeliki Lazaridou, Orhan Firat, Julian Schrittwieser, et al. 2024. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint arXiv:2403.05530 (2024). [32] Hanlin Tang, Yang Lin, Jing Lin, Qingsen Han, Danning Ke, Shikuan Hong, Yiwu Yao, and Gongyi Wang. 2025. RazorAttention: Efficient KV Cache Compression Through Retrieval Heads. In The Thirteenth International Conference on Learning Representations. https: //openreview.net/forum?id=tkiZQlL04w [33] Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, et al. 2024. Gemma 2: Improving open language models at a practical size. arXiv preprint arXiv:2408.00118 (2024). [34] Di Wu, Hongwei Wang, Wenhao Yu, Yuwei Zhang, Kai-Wei Chang, and Dong Yu. 2025. LongMemEval: Benchmarking Chat Assistants on Long-Term Interactive Memory. In The Thirteenth International Conference on Learning Representations. https://openreview.net/forum? id=pZiyCaVuti [35] Wenhao Wu, Yizhong Wang, Guangxuan Xiao, Hao Peng, and Yao Fu. 2025. Retrieval Head Mechanistically Explains Long-Context Factuality. In The Thirteenth International Conference on Learning Representations. https://openreview.net/forum?id=EytBpUGB1Z [36] Guangxuan Xiao, Jiaming Tang, Jingwei Zuo, junxian guo, Shang Yang, Haotian Tang, Yao Fu, and Song Han. 2025. DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads. In The Thirteenth International Conference on Learning Representations.
https://openreview.net/forum?id=cFu7ze7xUm [37] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. 2024. Efficient Streaming Language Models with Attention Sinks. In The Twelfth International Conference on Learning Representations. https://openreview.net/forum?id=NG7sS51zVF [38] Zihao Ye, Lequn Chen, Ruihang Lai, Wuwei Lin, Yineng Zhang, Stephanie Wang, Tianqi Chen, Baris Kasikci, Vinod Grover, Arvind Krishnamurthy, et al. 2025. Flashinfer: Efficient and customizable attention engine for llm inference serving. arXiv preprint arXiv:2501.01005 (2025). [39] Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. 2022. Orca: A distributed serving system for {Transformer-Based} generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 521–538. [40] Chen Zhang, Kuntai Du, Shu Liu, Woosuk Kwon, Xiangxi Mo, Yufeng Wang, Xiaoxuan Liu, Kaichao You, Zhuohan Li, Mingsheng Long, et al. 2025. JENGA: Effective memory management for serving LLM with heterogeneity. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles. 446–461. [41] Yanqi Zhang, Yuwei Hu, Runyuan Zhao, John CS Lui, and Haibo Chen. 2025. DiffKV: Differentiated Memory Management for Large Language Models with Parallel KV Compaction. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles. 431– 445. [42] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Re, Clark Barrett, Zhangyang Wang, and Beidi Chen. 2023. H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models. In Thirty-seventh Conference on Neural Information Processing Systems. https://openreview.net/forum?id=RkRrPp7GKO [43] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody_Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. 2023. Efficiently Programming Large Language Models using SGLang. arXiv preprint arXiv:2312.07104 (2023). [44] Wanjun Zhong, Lianghong Guo, Qiqi Gao, He Ye, and Yanlin Wang. 2024. Memorybank: Enhancing large language models with long-term memory. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38. 19724–19731. [45] Yinmin Zhong, 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. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). 193–210.
13