Hyungmin Kim, Minsoo Kim, Hongseok Kim, Jungwook Choi
5 min
Abstract
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.
Sam: Exactly. They call this "Ahead-of-Time" planning. By reserving the exact amount of memory each part needs before the conversation starts, they eliminate the constant background work the system usually does to shuffle and reorganize memory on the fly. That background work was previously consuming up to a quarter of the time the system spent just processing a new message.
Alex: So by moving the planning to before the conversation, they unlock a much faster system?
Sam: That's the key mechanism. By turning a dynamic, unpredictable management task into a pre-planned one, Tangram can more than double the number of conversations the system handles at once, all while keeping the AI's accuracy intact.
Alex: That is a significant improvement. But does this static blueprint ever get overwhelmed if the conversation takes an unexpected turn?
Sam: The researchers found that the relative importance of each memory section stays remarkably consistent across very different inputs. To handle any minor variation, they add what they call a "safety coefficient"—a small buffer of extra space built into the blueprint. It's a deliberate trade-off: they accept a tiny bit of over-allocation to ensure the system never runs out of room unexpectedly, which is far cheaper than trying to recalculate everything mid-conversation.
Alex: So it's a "better safe than sorry" buffer that's still much leaner than the old rigid approach?
Sam: Precisely. And because this ranking of memory needs is a property of the model itself—not of any particular user's question—they only have to run this clustering process once, offline. It becomes a static configuration that stays valid for as long as you're using that specific model.
Alex: So the system is essentially pre-sorted for maximum efficiency before it ever sees a real user request.
Sam: That's the primary benefit. By eliminating runtime calculations and the constant shuffling of memory pages, they remove what the paper calls "control-plane churn"—the background administrative work that was quietly eating into performance the whole time. The result is a much smoother experience, especially for long, complex interactions.
Alex: It's a meaningful shift in perspective—from managing memory reactively to planning it as a fixed blueprint ahead of time.
Sam: And that's what makes it a notable contribution. The authors have shown that efficiency doesn't always require more hardware. Sometimes, it just requires a better way to organize the resources you already have. Thanks for listening to ResearchPod.