Paper deep dive

GraniKV: Asymmetric Granularity KV-Cache Paging for Multi-Agent Systems with Long Shared Prefix

Jinhyun Jeon, Sungjoo Yoo

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 85

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%

Last extracted: 8/22/2026, 2:32:57 AM

Summary

GraniKV is a KV-cache paging layer for multi-agent LLM systems that applies asymmetric granularity: a contiguous HOT pool for shared prefixes and a token-level COLD pool for per-request suffixes. It features a per-step dispatcher selecting between a dense backend (for compute-bound regimes) and a cascade backend (for memory/communication-bound regimes), achieving up to 2.16x throughput improvement over production baselines like SGLang.

Entities (11)

GraniKV · system · 100%COLD Pool · component · 95%HOT Pool · component · 95%LLaMA-3.1-8B · model · 95%Qwen 2.5 14B · model · 95%Qwen-2.5-32B · model · 95%Cascade Backend · component · 90%Dense Backend · component · 90%FlashInfer · library · 90%Nvidia A100 · hardware · 90%SGLang · system · 90%

Relation Signals (10)

GraniKV → evaluatedon → Qwen-2.5-32B

confidence 95% · 1.57x ... on Qwen-2.5-32B/TP=4

GraniKV → evaluatedon → Qwen 2.5 14B

confidence 95% · 1.98x ... on Qwen-2.5-14B/TP=2

GraniKV → evaluatedon → LLaMA-3.1-8B

confidence 95% · GraniKV reaches 2.16x ... on Llama-3.1-8B/TP=1

GraniKV → extends → SGLang

confidence 95% · GraniKV extends SGLang ... with ~5,000 lines of Python

Cascade Backend → ispartof → GraniKV

confidence 95% · GraniKV therefore provides two kernels ... Cascade backend

Dense Backend → ispartof → GraniKV

confidence 95% · GraniKV therefore provides two kernels ... Dense backend

GraniKV → uses → COLD Pool

confidence 95% · the suffix in a token-level COLD pool

GraniKV → uses → HOT Pool

confidence 95% · allocates the shared prefix in a contiguous HOT pool

GraniKV → achievesthroughputimprovementover → SGLang

confidence 90% · GraniKV reaches 2.16x ... output-token throughput over the production baseline

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Production paged-serving engines apply uniform paging granularity to the KV cache, even though the two regions of a multi-agent workload have opposite storage requirements: a long shared prefix demands contiguity, while the per-request suffix demands fine-grained allocation. We present \textbf{GraniKV}, a KV-cache layer that allocates the shared prefix in a contiguous HOT pool and the suffix in a token-level COLD pool, combined with a per-step dispatcher which selects the appropriate backend among dual backends for each regime (compute-, memory-, or communication-bound). To the best of our knowledge, GraniKV is the first system to apply asymmetric paging granularity to the KV cache of a production paged-serving engine. At $L_p{=}16$\,K shared tokens GraniKV reaches $\mathbf{2.16\times}$, $\mathbf{1.98\times}$, and $\mathbf{1.57\times}$ output-token throughput over the production baseline on Llama-3.1-8B/TP=1, Qwen-2.5-14B/TP=2, and Qwen-2.5-32B/TP=4. The gain decomposes: cascade attention integration contributes the majority at saturation; the asymmetric storage layer adds $1.05$--$1.15\times$ end-to-end while being what makes the batched-GEMM prefix backend possible at all. Under heterogeneous multi-agent serving with \emph{distinct} prompts of different lengths, the attribution inverts: GraniKV sustains $\mathbf{1.95\times}$ while batch-global cascade collapses to parity --- the storage layer alone carries the win in the regime that motivates the paper.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

82,193 characters extracted from source content.

Expand or collapse full text

GraniKV: Asymmetric Granularity KV-Cache Paging for Multi-Agent Systems with Long Shared Prefix Jinhyun Jeon Affiliation: Seoul National University Email: journewki@gmail.com Sungjoo Yoo Affiliation: Seoul National University Email: sungjoo.yoo@gmail.com Abstract Production paged-serving engines apply uniform paging granularity to the KV cache, even though the two regions of a multi-agent workload have opposite storage requirements: a long shared prefix demands contiguity, while the per-request suffix demands fine-grained allocation. We present GraniKV, a KV-cache layer that allocates the shared prefix in a contiguous HOT pool and the suffix in a token-level COLD pool, combined with a per-step dispatcher which selects the appropriate backend among dual backends for each regime (compute-, memory-, or communication-bound). To the best of our knowledge, GraniKV is the first system to apply asymmetric paging granularity to the KV cache of a production paged-serving engine. At Lp=16L_p=16 K shared tokens GraniKV reaches 2.16×2.16×, 1.98×1.98×, and 1.57×1.57× output-token throughput over the production baseline on Llama-3.1-8B/TP=1, Qwen-2.5-14B/TP=2, and Qwen-2.5-32B/TP=4. The gain decomposes: cascade attention integration contributes the majority at saturation; the asymmetric storage layer adds 1.051.05–1.15×1.15× end-to-end while being what makes the batched-GEMM prefix backend possible at all. Under heterogeneous multi-agent serving with distinct prompts of different lengths, the attribution inverts: GraniKV sustains 1.95×1.95× while batch-global cascade collapses to parity — the storage layer alone carries the win in the regime that motivates the paper. 1 Introduction Multi-agent LLM systems — RAG pipelines, agentic orchestrators, and enterprise assistants with shared system prompts — have become the dominant production deployment pattern for large language models (Liu et al. 2026; Kumar et al. 2025; Lewis et al. 2020). These workloads share one defining feature: a long shared-prefix KV block (system prompt, retrieved document, dialogue history) is identical across many concurrent requests, while each request also carries a unique suffix. Production paged-serving engines — SGLang (Zheng et al. 2024), vLLM (Kwon et al. 2023), and TensorRT-LLM (NVIDIA 2024) — all apply the same paging granularity to both regions even though they have opposite storage requirements: the shared prefix demands contiguity (so a shared-prefix attention kernel can read it without gather), while the per-request suffix demands fine-grained allocation. We introduce GraniKV, an asymmetric-granularity KV-cache paging layer that splits the KV pool into a contiguous HOT pool for shared prefixes and a token-level COLD pool for per-request suffix and decoded tokens. To the best of our knowledge, GraniKV is the first system to apply asymmetric paging granularity to the KV cache of a production paged-serving engine, and the first to make fat-GEMM shared-prefix attention (Juravsky et al. 2024) usable inside such an engine. We pair this storage with two attention backends — a dense backend and a cascade backend — and a per-step dispatcher that selects the appropriate backend from the two on every decode step. None of the constituent kernels is our claim; the contribution is making them coexist in a production engine: asymmetric KV granularities under one RadixAttention index with engine-integrated admission, eviction, and paged fallback (§3.4, §3.2); and a hardware-fitted per-step backend dispatcher (§3.6, Appendix B). On ShareGPT-V3 under Poisson arrivals at saturation, the gain grows monotonically with LpL_p and peaks at long prefixes. At Lp=16KL_p=16K, GraniKV reaches 2.16×2.16×, 1.98×1.98×, and 1.57×1.57× the output-token throughput of the production baseline on Llama-3.1-8B/TP=1, Qwen-2.5-14B/TP=2, and Qwen-2.5-32B/TP=4, at parity (≥0.97×≥0.97×) at short prefixes. The gain decomposes (§4.5): cascade-attention integration contributes the majority at saturation on a single shared prefix; the asymmetric storage layer adds 1.051.05–1.15×1.15× end-to-end, becomes the entire win under heterogeneous multi-prefix load (1.95×1.95× while cascade collapses to parity, Appendices B.8–B.8b), and is the architectural prerequisite for the batched-GEMM prefix backend (Appendix B). 2 Related Work 2.1 Attention, KV Cache, and Paged Allocation Transformer LLMs (Vaswani et al. 2017) compute multi-head attention at every layer, producing query, key, and value vectors (Q, K, V) per token. Autoregressive decoding must attend over all previous tokens, so the keys and values of every past token are retained throughout generation—forming the KV cache—which grows linearly with batch size and context length and dominates HBM consumption in production serving. Early serving systems allocated a contiguous KV-cache region per request, typically sized to the maximum output length. This caused substantial memory waste from over-reservation and external fragmentation, limiting serving concurrency. Kwon et al. 2023 address this with PagedAttention, which partitions the KV cache into fixed-size P-token pages allocated on demand and maps logical token indices to physical pages through a per-request block table. PagedAttention resolves external fragmentation while bounding internal fragmentation to at most P−1P\!-\!1 unused tokens per request. PagedAttention is now the standard KV-cache management mechanism in LLM serving systems. 2.2 Multi-Agent Systems and Shared-Prefix Serving Multi-agent LLM pipelines have become the dominant production deployment pattern (Liu et al. 2026; Kumar et al. 2025). Across these deployments a long shared prefix appears in many forms — the retrieved document RAG injects into every batched query (Lewis et al. 2020), the common system prompt enterprise services embed across users, the dialogue history an agentic orchestrator accumulates and replays each turn — and sits identically in front of many concurrent requests. The shared prefix is already significant in deployed systems — production traces report prefixes reaching 23K23K tokens with 85−97%85-97\% of prompt tokens shared (Srivatsa et al. 2025), and Anthropic’s prompt-caching design sets the minimum cacheable prefix at 1,0241,024–4,0964,096 tokens (Anthropic 2026). The engine therefore repeatedly processes the same prefix KV block, while each request carries its own unique suffix. SGLang (Zheng et al. 2024) addresses prefix sharing with RadixAttention: a radix tree keyed on token-id sequences indexes cached KV tensors. Incoming requests traverse the tree to find the longest matching prefix and reuse its KV slots, skipping prefill for those tokens; reference-counted tree nodes keep cached prefixes resident as long as any active request holds them. Recent prefix-aware serving designs — ChunkAttention (Ye et al. 2024a), Mooncake’s prefix-cache-aware scheduling (Qin et al. 2025), and hot-prefix replication (Li et al. 2025) — all build on this prefix-reuse idea. 2.3 Attention Optimization for Shared Prefixes Two works exploit the shared-prefix structure by separating prefix from suffix attention. Both methods share the same divide-and-conquer structure—a shared-prefix pass followed by a per-request suffix pass, merged via log-sum-exp —and differ only in which prefix-side inefficiency they target. HydraGen recovers compute utilization while cascade inference recovers memory bandwidth. Shared-prefix matmul (HydraGen). During decode, each of B requests issues an independent query against the shared prefix, producing B separate matrix-vector products that underutilize Tensor Cores. Juravsky et al. 2024 batch these queries into a single matrix-matrix multiply: if the prefix is stored as a contiguous dense tensor Kp∈ℝLp×Hkv×dK_p ^L_p× H_kv× d (Table 1 lists all symbols used in the paper), prefix attention becomes Op=softmax⁡(QKp⊤d)Vp,O_p=softmax\! ( QK_p d )V_p, where Q stacks all B query vectors, exposing the full contraction to Tensor Cores. Per-request suffix attention is computed separately and merged with the prefix output via log-sum-exp. Cascade inference. A complementary bottleneck is redundant HBM traffic: in standard paged decode each of B requests independently reads the full prefix, repeating the same transfer B times per step. Ye et al. 2025 resolve this with a multi-query prefix pass that reads the prefix once per step, a per-request suffix pass, and a log-sum-exp merge: O=eℓp−mOp+eℓs−mOseℓp−m+eℓs−m,m=max⁡(ℓp,ℓs),O= e _p-mO_p+e _s-mO_se _p-m+e _s-m,\ m= ( _p, _s), (1) cutting prefix HBM reads from O⁡(B)O(B) to O⁡(1)O(1). 3 GraniKV Table 1 summarizes the notation used throughout this section. Sym Meaning Sym Meaning LpL_p prefix len. (tok) d per-head dim LsL_s suffix len. (tok) fpf_p HOT frac. (0.20.2) LoutL_out output len. (tok) MeffM_eff B⋅nq/kvB· n_q/kv B batch size MsatM_sat sat. threshold (10241024, A100) (Op,ℓp)(O_p, _p) prefix out, LSE TP TP rank cnt (Os,ℓs)(O_s, _s) suffix out, LSE HkvH_kv KV heads/rank nq/kvn_q/kv GQA group size Table 1: Notation. 3.1 Design Goals The methods reviewed in §2 all operate over a KV cache paged with uniform granularity. Cascade inference reduces HBM traffic but still reads the prefix from scattered pages; the shared-prefix matmul achieves Tensor Core saturation only under a contiguous layout that no production paged engine provides. The underlying issue is that both regions of the KV cache are treated identically, even though they have opposite storage requirements—the shared prefix demands contiguity while the per-request suffix demands fine-grained allocation. GraniKV resolves this by asymmetric granularity KV-cache paging, guided by three goals: 1. Contiguous prefix storage. The shared prefix KV must occupy a single contiguous memory region for each layer so the attention kernel can load it with a single dense read, with no gather or page-table indirection. 2. Token-level suffix allocation. The per-request suffix must be allocated at token granularity to eliminate internal fragmentation. 3. Regime-adaptive backend dispatch. The system must pair a compute-optimal and a bandwidth-optimal attention backend with a per-step dispatcher that picks the appropriate one for the live regime. The first two goals deliver a strict end-to-end improvement over both baselines: GraniKV outperforms the production default (SGLang with FlashInfer) and SGLang with cascade inference once two conditions are satisfied — the shared prefix is long and the in-flight batch saturates the matmul tile. Both conditions are the norm in production multi-agent serving (large system prompts or retrieved contexts, high concurrency to amortize fixed costs), and in that regime GraniKV reaches up to 2.16×2.16× the production baseline on Llama-3.1-8B/TP=1 ShareGPT (§4). The third goal guarantees that outside this regime — short prefixes or low concurrency — the dispatch preserves parity for GraniKV rather than causing regressions. 3.2 HOT Pool: Contiguous Prefix Storage The HOT pool is a contiguous bump-pointer allocator over a statically reserved region of GPU HBM. At server boot, a configurable fixed fraction of the total KV budget is carved out for the HOT pool; the remainder is assigned to the COLD pool. Each HOT allocation services a single shared prefix. When the RadixAttention tree inserts a new prefix node, it requests a contiguous block of LpL_p token slots from the HOT pool. The allocator advances a bump pointer and returns the base slot index; the prefix KV for layer l and head h is then located at +l×Lp×Hkv+h×Lpbase+l× L_p× H_kv+h× L_p—a simple stride computation with no indirection. The tree node records this base index; any attention backend that matches on this prefix receives the base index and prefix length directly. When a prefix’s reference count drops to zero its slab becomes evictable, and the engine’s standard LRU eviction reclaims it under memory pressure: the range [,+Lp)[base,\ base+L_p) is returned to a free list and merged with adjacent free ranges. A subsequent allocation can reuse a freed range without fragmentation. There is no internal fragmentation within an allocation: a prefix either occupies its full contiguous range or is absent. 3.3 COLD Pool: Token-Level Suffix Allocator The COLD pool is a token-level free-list allocator (page size = 1) occupying the KV budget not assigned to the HOT pool. Each generated suffix token receives exactly one slot; there is no intra-page wasted capacity and no partial-page fragmentation. Token-level allocation is appropriate for the suffix because suffix tokens are unique per request: unlike the shared prefix, they are never referenced by more than one request, so larger pages would not enable any cross-request reuse. Address-mapping overhead is negligible at decode time. The per-token page-table indirection cost is empirically small. Ye et al. 2025 report the gap between sparse-gather (page_size=1=1) and dense-contiguous attention as within 1%1\% for decode kernels, and we confirm this at the system level (Appendix B). We adopt page size 11 as the simpler default in order to eliminate internal fragmentation. 3.4 Engine Integration GraniKV extends SGLang (Zheng et al. 2024) — the multi-agent serving engine on which we report all measurements in §4 — with ∼5,000 5,000 lines of Python (including the Triton (Tillet et al. 2019) kernels). The host’s RadixAttention tree carries one extra piece of metadata per node — a pool identity, either a HOT base index or a COLD marker — set at admission and read at decode. Mixed batches are handled in a single kernel; the tree’s matching, eviction, and reference-counting logic are unchanged. Figure illustrates the layout of GraniKV. Any paged-serving system with a prefix-sharing can adopt the same HOT/COLD split by adding a contiguous-allocation primitive and wiring its attention backend to read from either region. 3.5 Dual Backends Production multi-agent deployments span three performance regimes — compute-bound (a small model at low TP with a wide batch saturates Tensor Cores), memory-bound (a large model at low TP, where KV-cache headroom caps the realizable batch), and communication-bound (the same large model at multi-rank TP, where NCCL all-reduce consumes most of decode time and leaves the attention kernel a thin slice). No single kernel is right for all three: compute-bound regimes need fat-contraction Tensor-Core saturation, while memory- and communication-bound regimes leave Tensor Cores idle and need a bandwidth-optimal kernel with a single prefix read per step. GraniKV therefore provides two kernels over the same HOT/COLD storage, one matching each profile. The two backends. Both consume the HOT pool and produce numerically equivalent outputs (Figure ), but differ in prefix contraction: • Dense backend (inspired by HydraGen). Per layer, one fat batched matmul against the prefix K, a softmax, then one fat batched matmul against the prefix V — covering all requests at once, with no inner loop over the prefix and no online softmax. Suffix runs as paged decode over COLD slots; partial outputs are merged via log-sum-exp (Eq. 1). • Cascade backend. Builds on FlashInfer Cascade (Ye et al. 2024b; Ye et al. 2025), a two-level attention kernel that reads a shared KV region once per step and the per-request suffix separately, merging the two via log-sum-exp; we place the HOT pool as Cascade’s level-0 (shared) input. The level-0 kernel remains a FlashAttention-style (Dao et al. 2022; Dao 2024) tiled loop over BLOCK_N-token chunks with online softmax; the HOT layout only eliminates the paged_kv_indices gather of the paged cascade path. The two differ along one axis—matmul fatness. The dense backend issues one M=BQHM=BQH, N=LpN=L_p contraction per layer; cascade issues ⌈Lp/BLOCK_N⌉ L_p/BLOCK\_N contractions of shape M=QM=Q, N=BLOCK_N=BLOCK\_N. Only the dense backend saturates Tensor Cores at a single contraction; cascade trades peak Tensor Core utilization for tolerance to small effective batches and short prefixes. Concretely, the dense backend wins in the compute-bound regime, cascade wins in the memory-bound regime, and the two split the step in the communication-bound regime (dense on saturated bursts, cascade on smaller follow-on steps). The per-step dispatch rule that realizes this mapping is given in §3.6, and how each regime is identified empirically is detailed in §4. Both backends apply only to decode; prefill is delegated unchanged to FlashInfer’s prefill kernel, which already reads the HOT pool as a contiguous tensor and the COLD pool through its paged path. 3.6 Per-Step Dispatch The two backends each dominate a regime, but a production serving engine does not see a single steady-state regime. The realized in-flight batch varies step-to-step as requests arrive and complete, and decode steps follow prefill bursts of yet different shapes. A boot-time backend choice would lose on every step that falls on the wrong side of the regime curve. GraniKV avoids this by dispatching per step. A thin wrapper instantiates both children sharing the same HOT/COLD pool, and at each decode step computes the effective matmul M-dimension from the realized batch: Meff(step)=Bstep×nq/kv,M_eff(step)=B_step× n_q/kv, (2) where BstepB_step is the step’s realized in-flight batch — the number of requests actually being decoded on that step, which can exceed the admission batch when prefill bursts from newly arriving requests overlap with ongoing decode — and nq/kvn_q/kv is the GQA group size. We empirically measured the saturation threshold MsatM_sat on the A100 used throughout our evaluation and found that Tensor Cores saturate at Meff≥Msat=1024M_eff≥ M_sat=1024 (sweep in Appendix B); below this the matmul tile cannot keep all Tensor Core lanes active. The wrapper routes to the dense backend when Meff≥MsatM_eff≥ M_sat and to cascade otherwise. Because BstepB_step is measured each step rather than fixed at admission, sub-threshold cells (e.g. B=128B=128 at nq/kv=4n_q/kv=4, nominal Meff=512M_eff=512) can still route a small fraction of steps to dense whenever the realized batch transiently crosses the threshold; Appendix B (B.4) quantifies this fraction across the synthetic grid. The threshold itself is a hardware property depending on warp count, MMA-instruction shape, and the Tensor Core generation—and would need to be re-fitted on other GPUs. The dispatch rule is hardware-agnostic, only the numeric threshold changes. Two ceilings, one rule. Production deployments hit two non-compute-bound ceilings: a KV-memory ceiling (weights crowd out KV cache, capping the realized batch) and a communication ceiling (all-reduce consumes a growing share of decode time under TP). The MeffM_eff criterion handles both: memory-bound configurations stay sub-threshold and route every step to cascade, while communication-bound ones cross on saturated bursts (dense) and fall below on smaller steps (cascade) — capturing the dense win where it fires while preserving cascade parity elsewhere. See Appendix B for the per-configuration breakdown. Dispatch overhead is negligible. The wrapper itself adds only sub-microsecond CPU work per decode step (<0.2%<0.2\% of per-step wall time at the headline cell); full measurement in Appendix B. 4 Experiments 4.1 Research Questions Section 4 answers two questions, each mapped to a subsection below. Q1 (§4.5) — Headline results. How large are the wins on the three winning configurations under realistic Poisson arrivals, including multi-prefix serving? Q2 (§4.6) — Why GraniKV wins. What kernel-level mechanism explains the win? 4.2 Setup Hardware and software. We evaluate on a single host with 4×NVIDIA A100-SXM4-40GB (driver 570.195.03, CUDA 12.9, SM clocks locked at 14101410 MHz). GPUs are interconnected via NVLink 3.0 (600600 GB/s aggregate per GPU); NCCL collectives run over the available NVLink topology. The software stack is PyTorch 2.9.1, Triton 3.5.1, FlashInfer 0.6.8, and NCCL 2.21. Models and TP configurations. We present results on three (model, TP) configurations using Llama-3.1 (Dubey et al. 2024) and Qwen-2.5 (Team 2024) checkpoints (Table 2): Llama-3.1-8B/TP=1, Qwen-2.5-14B/TP=2, and Qwen-2.5-32B/TP=4. On our 4×4×A100-SXM4-40GB testbed each TP value hits one of two opposing constraints: low TP leaves too little per-rank HBM for KV cache, so the runtime caps the realized batch below the dense backend’s saturation threshold; high TP pays a growing NCCL all-reduce share of decode time, which caps the fraction of the step that shortening attention can recover. We therefore evaluate only the best-fitting TP for each model — the lowest one whose weights fit with enough KV headroom for the target peak concurrency. We report the full TP sweep in Appendix B. Model TP nq/kvn_q/kv KV heads / rank Llama-3.1-8B 1 4 8 Qwen-2.5-14B 2 5 4 Qwen-2.5-32B 4 5 2 Table 2: Evaluation configurations. TP is tensor-parallel rank count; nq/kvn_q/kv is the GQA query-per-KV-head ratio (see Table 1); “KV heads / rank” is the per-rank KV-head count after TP sharding. Decoding. All systems decode greedily with output tokens capped at 256256, so every request deterministically generates the same number of tokens. 4.3 Systems Compared • SGLang default — the production default: unmodified SGLang on 1616-token paged storage with FlashInfer batched decode. • SGLang-Cascade — FlashInfer Cascade kernel on 1616-token paged storage. SGLang-Cascade is exactly GraniKV without the asymmetric-granularity storage layer, providing the ablation of the storage-layer contribution. SGLang upstream has no merged cascade-attention backend, so we implemented the integration ourselves, which is also our standalone contribution. • GraniKV — the per-step adaptive system from §3.6, dispatching each decode step to either the HOT/COLD dense backend or the cascade backend on HOT/COLD storage. 4.4 Workload and Metrics Workload (ShareGPT under Poisson arrivals). A realistic multi-agent serving trace that combines heterogeneous user turns with stochastic arrival — representative of the production workloads GraniKV is designed for. For each configuration we pair a deterministic LpL_p-token system prompt with 500500 ShareGPT-V3 user turns (filtered to 16≤|user turn|≤51216≤|user turn|≤ 512 tokens, deterministic seed 4242), generating up to 256256 output tokens. We sweep Lp∈512,1K,2K,4K,8K,16KL_p∈\512,1K,2K,4K,8K,16K\ crossed with Poisson arrival rates spanning sub-saturation. The headline cells used in §4.5 are saturation-rate cells from this sweep. To further emulate multi-tenant deployments where distinct shared prefixes share the engine concurrently, we additionally sweep a mixed-prefix variant with k distinct LpL_p-token shared prefixes active simultaneously. We sweep k∈1,4,16,64k∈\1,4,16,64\ under the same Poisson regime (full sweep in Appendix B). Metrics. We measure output throughput in tokens per second along with median (p50) latencies for both TTFT (time-to-first-token) and TPOT (time-per-output-token) in milliseconds. 4.5 Results ShareGPT under Poisson arrivals is the operating point that matters most for production multi-agent serving — and the long-shared-prefix regime in particular is where GraniKV’s upside is largest. Real multi-agent workloads operate on long shared prefixes such as system prompts, retrieved documents, and accumulated dialogue histories, so the LpL_p ladder below is the relevant evaluation axis; Table 3 sweeps it at the saturation rate of each cell on the three winning configurations, and the full per-cell distribution appears in Appendix B. LpL_p SGL SGL-C GKV × SGL × SGL-C Llama-3.1-8B / TP=1 4K4K 34783478 42094209 46844684 1.35×1.35× 1.11×1.11× 8K8K 22262226 34763476 38013801 1.71×1.71× 1.09×1.09× 16K16K 13621362 28002800 29432943 2.16×2.16× 1.05×1.05× Qwen-2.5-14B / TP=2 4K4K 37023702 39813981 44574457 1.20×1.20× 1.12×1.12× 8K8K 24892489 34493449 39023902 1.57×1.57× 1.13×1.13× 16K16K 15671567 27062706 31093109 1.98×1.98× 1.15×1.15× Qwen-2.5-32B / TP=4 4K4K 36293629 33943394 35973597 0.99×0.99× 1.06×1.06× 8K8K 26202620 30363036 32923292 1.26×1.26× 1.08×1.08× 16K16K 17261726 23622362 27072707 1.57×1.57× 1.15×1.15× Table 3: ShareGPT throughput at B=256B=256 (output tok/s, 33-rep means) on the long-prefix region of the LpL_p ladder. SGL = SGLang default; SGL-C = SGLang-Cascade; GKV = GraniKV. Full LpL_p sweep in Appendix B. The wins grow with LpL_p and are largest at long prefixes. GraniKV reaches 2.16×2.16× SGLang default at Lp=16KL_p=16K on Llama-3.1-8B / TP=1, 1.98×1.98× on Qwen-2.5-14B / TP=2, and 1.57×1.57× on Qwen-2.5-32B / TP=4. On Llama-3.1-8B the win first exceeds 1.5×1.5× at Lp=4KL_p=4K and roughly doubles by Lp=16KL_p=16K; the same monotone-in-LpL_p scaling holds on both Qwen configurations. The win amplifies under Poisson arrivals because longer prefixes occupy the in-flight batch for more steps, and the dense backend’s per-step savings accumulate accordingly. No regression at short prefixes. At the headline B=256B=256, GraniKV is at worst 0.97×0.97× SGLang default (Llama-3.1-8B, Lp=512L_p=512) and monotone non-decreasing along the LpL_p axis. The Poisson workload mixes short and long user turns within each in-flight batch, so the decoder sees requests at different stages on every step; the per-step dispatch routes correctly under this heterogeneity. Regressions at the small-LpL_p / high-B corners that fall outside the design’s effective regime are characterized in Limitations. Implication for production multi-agent serving. The monotone-in-LpL_p scaling places GraniKV’s largest gains exactly in the regime production multi-agent deployments occupy — e.g., Anthropic’s Claude Code agent sending its long system prompt, tool definitions, and CLAUDE.md on every API call— supporting GraniKV as a strong fit for these workloads. Multi-prefix serving: where the storage layer carries the entire win. With several distinct system prompts in flight — the multi-agent pattern of one sub-agent prompt per role — the attribution of Table 3 inverts. Cascade attention deduplicates a batch-global shared level, which is empty across distinct prefixes, so SGLang-Cascade collapses to parity with the default (0.99×0.99×); GraniKV’s slabs are per prefix class, so the dense backend keeps batching each class against its own slab. Table 4 summarises the result (full data in Appendix B; uniform cardinality sweep in Appendix B). System k=4k=4 k=8k=8 SGLang default 1.00×1.00× 1.00×1.00× SGLang-Cascade 0.99×0.99× 0.97×0.97× GraniKV 1.95×1.95× 1.82×1.82× Table 4: Heterogeneous multi-prefix throughput (vs. SGLang default), Llama-3.1-8B/TP=1, B=256B=256. k=4k=4: Lp∈2,4,8,16L_p∈\2,4,8,16\K; k=8k=8: LpL_p ladder 11–1616K. Full results in Appendix B. 4.6 Why GraniKV Wins: a Kernel-Level Microbench GraniKV’s contribution traces to a single mechanism: the contiguous HOT pool turns the dense backend’s QKp⊤QK_p contraction from memory-bound into compute-bound. We use a CUDA-event microbench to isolate this by launching the same dense prefix kernel at the headline (B=256B=256, Lp=8KL_p=8K, Llama-3.1-8B head) against two storage layouts with identical kernel and tile shape: shared (HOT) reads each K/V once per step, while unique (paged-equivalent) reads the same prefix 256256 times. Storage Wall (μ ) Effective HBM traffic (GB/s) Speedup shared (HOT) 449 0449 71 071 15.6×15.6× unique (paged) 69886988 11701170 1×1× Table 5: Kernel-isolated microbench (CUDA-event timing, mean of 2020 launches) of the dense prefix kernel at B=256B=256, Lp=8KL_p=8K on Llama-3.1-8B head shape. “Effective HBM traffic” is total K+V bytes read from HBM divided by wall time. The HOT case’s 7171 GB/s is low because the kernel reads K/V from HBM only once (subsequent tiles hit L2), not because HBM bandwidth is throttled. Table 5 reports the headline: storage layout alone moves the dense kernel from HBM-bound to compute-bound, a 15.6×15.6× speedup at fixed kernel and problem. The gap between this 15.6×15.6× kernel speedup and the measured end-to-end gain is explained by Amdahl’s law (Amdahl 1967): Spred=1(1−α)+α/s,S_pred\;=\; 1(1-α)+α/s, (3) where SpredS_pred is the predicted end-to-end speedup over the SGLang-default baseline, α is the fraction of decode wall-time spent in the prefix-attention kernel (measured via torch.profiler on the SGLang-default), and s=15.6s=15.6 is the prefix-attention kernel speedup from Table 5. Across all three configurations the Amdahl prediction with the kernel-isolated s over-shoots the measured end-to-end speedup. A trace-measured decomposition (Appendix B) attributes the residual to three terms: host-side gaps (up to 5.6%5.6\% of step wall time, dominant at TP=1, where adding them closes the residual to +5.8%+5.8\%), NCCL all-reduce (growing to 7.9%7.9\% at TP=4), and — dominant at TP>1TP>1 — the in-engine effective kernel speedup, which falls with KV heads per rank (9.4×/4.1×/2.6×9.4×/4.1×/2.6× at 8/4/28/4/2 heads/rank vs. the microbench’s 15.6×15.6× at 88 heads), consistent with the head-fused-tile floor of Appendix B. A roofline analysis of both storage layouts, with hardware performance counters validating the byte model and bounding the paged kernel’s remaining tuning headroom at ≤1.27×≤1.27×, appears in Appendix B. 5 Conclusion GraniKV applies asymmetric granularity KV cache paging to a production paged-serving engine — a contiguous HOT pool for the shared prefix, a token-level COLD pool for the suffix, and a per-step dispatcher between two attention backends. On the long-shared-prefix, high-concurrency regime of modern multi-agent serving, GraniKV reaches 2.16×2.16×, 1.98×1.98×, and 1.57×1.57× the baseline at Lp=16L_p=16 K across three (model, TP) configurations, with no regression at short prefixes — matching the prefix regime of real multi-agent products. The gains grow as production shared prefixes lengthen. Limitations GraniKV has several limitations that we leave to future work. High-tenancy multi-prefix deployments. GraniKV targets the small-k, long-LpL_p regime exemplified by the production deployments of §2.2 (Claude Code, RAG, long-context QA) — typically one to a handful of distinct system prompts active at a time. In multi-tenant settings with many concurrent distinct prompts (e.g. k=64k=64 at Lp=8L_p=8 K = 512512 K active tokens; see Appendix B) the active prefix set exceeds the engine’s KV budget and all paged engines thrash equally; GraniKV offers no specific benefit in this corner. A hotness-weighted HOT-pool eviction policy (vs. the current LRU release of refcount-zero slabs) could narrow the gap when k exceeds the HOT pool’s headroom; we leave this to future work. Static HOT/COLD pool fraction. The fraction fpf_p of the KV budget reserved for the HOT pool is set once at server boot (default 0.20.2) and not adjusted. Workloads with shifting prefix-to-suffix ratios across the day — e.g. a daytime mix of long shared system prompts and a nighttime mix dominated by free-form user generation — would benefit from re-sizing fpf_p online. We leave a dynamic allocator that monitors HOT-pool occupancy and COLD-pool admission pressure and re-partitions the underlying KV buffer between bursts as future work. Limited model and hardware coverage. All measurements come from 55 (model, TP) configurations on a single A100-SXM4-40GB host. The qualitative shape of the per-step dispatch should carry to other architectures, but the numeric saturation threshold (M≥1024M≥ 1024 on A100) is hardware-specific and would need to be re-fitted for H100, MI300X, B200, or future GPUs (§3.6). We also do not evaluate Mixture-of-Experts models, models below 8B, models above 32B, sequence-parallel or expert-parallel deployments, or configurations where the model weights themselves exceed a single rank’s HBM (which would foreclose Qwen-32B/TP=1, Llama-70B/TP=4, and similar). Broadening the deployment matrix is straightforward future work but does not change the design. Small-LpL_p / small-B regime. The asymmetric storage introduces fixed per-step bookkeeping (HOT-pool admission, pool-identity lookup in the radix tree) that does not amortize over short decode runs without compensating prefix savings. In this regime GraniKV is at parity at the B≤256B≤256 short-prefix cells (worst case 0.97×0.97× SGLang default on Llama-3.1-8B at Lp=512L_p=512, B=256B=256) but degrades further at the small-LpL_p / high-B corners — up to a 30%30\% regression on Qwen-2.5-14B at Lp=512L_p=512, B=512B=512 (0.70×0.70× SGLang default; see Table 10) — where the prefix is too short for the dense backend to saturate Tensor Cores and there is no shared-prefix benefit to amortize the storage layer’s per-step costs. Operationally, because GraniKV is activated per server instance via a single --granikv CLI flag (§3), deployments that know they will operate in this corner can simply launch without the flag and fall back to the stock paged path; the regression therefore acts as a deployment-time configuration choice rather than a runtime constraint. The mechanism is well-understood, and an admission heuristic that defers HOT promotion until a prefix has accumulated enough references would close the gap inside the GraniKV path itself, but is again left to future work. Ethics Statement GraniKV is an infrastructure-level optimization to the KV-cache layout used by LLM serving engines. It changes how cached attention state is laid out in GPU memory and which kernel computes attention; it does not modify model weights, training data, generation behavior, or any externally visible output of the served model. Bit-exactness against the unmodified baseline serving stack is preserved (§3). We use publicly released model checkpoints (Llama-3.1-8B, Qwen-2.5-14B, Qwen-2.5-32B) and the publicly available ShareGPT V3 conversation dataset for evaluation; no new data is collected, annotated, or released. The shared-prefix workload generator is synthetic. The societal impact of more efficient LLM serving is dual-use: lower serving cost makes LLM-backed services more broadly accessible but also lowers the cost of any negative use of those services. The contribution here is at the level of GPU-memory layout, comparable to other inference-optimization work (e.g. PagedAttention, FlashInfer), and inherits the same societal-impact considerations as that body of work. Acknowledgements We thank the SGLang and FlashInfer maintainers for the open-source serving stacks on which this work builds, and our colleagues for many helpful discussions and their support during this project. An open Pull Request toward a FlashInfer Cascade attention backend in SGLang upstream was in progress at the time of this submission but had not been merged; our integration was implemented independently, and we plan to submit it as a separate upstream PR. We used AI assistants (large language models) during this work to support literature search, code drafting, and manuscript revision. References Amdahl (1967) Gene M. Amdahl. 1967. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the AFIPS Spring Joint Computer Conference, pages 483–485. Anthropic (2026) Anthropic. 2026. Prompt caching. https://platform.claude.com/docs/en/build-with-claude/prompt-caching. Official Claude API documentation; minimum cacheable prefix 1,0241,024–4,0964,096 tokens depending on model. Dao (2024) Tri Dao. 2024. FlashAttention-2: Faster attention with better parallelism and work partitioning. In Proceedings of the 12th International Conference on Learning Representations (ICLR). Dao et al. (2022) Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022. FlashAttention: Fast and memory-efficient exact attention with IO-awareness. In Advances in Neural Information Processing Systems (NeurIPS). Dubey et al. (2024) Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, and 1 others. 2024. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783. Juravsky et al. (2024) Jordan Juravsky, Bradley Brown, Ryan Ehrlich, Daniel Y. Fu, Christopher Ré, and Azalia Mirhoseini. 2024. Hydragen: High-throughput LLM inference with shared prefixes. arXiv preprint arXiv:2402.05099. Kumar et al. (2025) Madabattula Rajesh Kumar, Srinivasa Rao Aravilli, Mustafa Saify, and Shashank Srivastava. 2025. From attention to disaggregation: Tracing the evolution of LLM inference. arXiv preprint arXiv:2511.07422. Kwon et al. (2023) Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. 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 (SOSP). Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems (NeurIPS). Li et al. (2025) Yuhang Li, Rong Gu, Chengying Huan, Zhibin Wang, Renjie Yao, Chen Tian, and Guihai Chen. 2025. HotPrefix: Hotness-aware KV cache scheduling for efficient prefix sharing in LLM inference systems. Proceedings of the ACM on Management of Data (PACMMOD), 3(4):250:1–250:27. Liu et al. (2026) Jiacheng Liu, Xiaohan Zhao, Xinyi Shang, and Zhiqiang Shen. 2026. Dive into Claude code: The design space of today’s and future AI agent systems. arXiv preprint arXiv:2604.14228. NVIDIA (2024) NVIDIA. 2024. TensorRT-LLM: A TensorRT toolbox for optimized large language model inference. https://github.com/NVIDIA/TensorRT-LLM. Qin et al. (2025) Ruoyu Qin, Zheming Li, Weiran He, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. 2025. Mooncake: A KVCache-centric disaggregated architecture for LLM serving. In Proceedings of the 23rd USENIX Conference on File and Storage Technologies (FAST). Srivatsa et al. (2025) Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, and Yiying Zhang. 2025. Preble: Efficient distributed prompt scheduling for llm serving. In International conference on learning representations, volume 2025, pages 37057–37082. Team (2024) Qwen Team. 2024. Qwen2.5 technical report. arXiv preprint. Tillet et al. (2019) Philippe Tillet, H. T. Kung, and David Cox. 2019. Triton: An intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages. Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS). Ye et al. (2024a) Lu Ye, Ze Tao, Yong Huang, and Yang Li. 2024a. ChunkAttention: Efficient self-attention with prefix-aware KV cache and two-phase partition. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (ACL). Ye et al. (2025) Zihao Ye, Lequn Chen, Ruihang Lai, Junru Shao, Yilong Zhao, Size Zheng, Hongyi Jin, and 1 others. 2025. FlashInfer: Efficient and customizable attention engine for LLM inference serving. In Proceedings of the 13th International Conference on Learning Representations (ICLR). Ye et al. (2024b) Zihao Ye, Ruihang Lai, Bo-Ru Lu, Chien-Yu Lin, Size Zheng, Lequn Chen, Tianqi Chen, and Luis Ceze. 2024b. Cascade inference: Memory bandwidth efficient shared prefix batch decoding. Zheng et al. (2024) Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. 2024. SGLang: Efficient execution of structured language model programs. In Advances in Neural Information Processing Systems (NeurIPS). Appendix Appendix A Source Code and Reproducibility Repository. The full source code and measurement data are available as an anonymized repository: https://anonymous.4open.science/r/GraniKV_ARR_26. It contains the patched fork (storage layer, both attention backends, and the per-step dispatcher), the standalone kernel microbenchmark reproducing Table 5 and the hardware counters of Appendix B (scripts/bench_granikv_kernel_v2.py), the sweep drivers and pre-generated workloads for Appendices B and B, the raw per-cell result files behind every reported number (results/, ncu_reports/), and a step-by-step reproduction guide from environment setup to each table (REPRODUCE.md). A permanent public release under the authors’ account is in preparation. Appendix B Full Evaluation Results B.1 Full synthetic shared-prefix grid. Tables 6–8 report the full synthetic-grid sweep for the three winning configurations: Lp∈512,1K,2K,4K,8KL_p∈\512,1K,2K,4K,8K\ crossed with B∈8,32,128,256B∈\8,32,128,256\ (2020 cells per configuration). Throughputs are 33-rep means in output tok/s; the rightmost column is GraniKV / SGLang default. At the headline cell (B=256B=256, Lp=8L_p=8 K) on Llama-3.1-8B / TP=1, TPOT p50 drops from 109109 ms (SGLang default) to 4242 ms (GraniKV) — a ≈2.6×≈2.6× per-token speedup. TTFT is comparable across all three systems (within ∼10% 10\% at dense-favourable cells such as Lp=8L_p=8 K, B=256B=256; looser at sub-saturation cells where small absolute durations amplify ratios) because prefill is always delegated to FlashInfer’s batched prefill. Why Lp=16L_p=16 K is omitted from the synthetic grid. The synthetic burst injector issues each request via a non-streaming call. For prompts up to Lp=8L_p=8 K the per-request response time is short enough that the non-streaming round-trip captures total wall time correctly, and mean_ttft_ms grows monotonically with LpL_p and B as expected. At Lp=16L_p=16 K, however, the captured TTFT collapses to 00\,ms across all three configurations and all batch sizes, and the reported per-cell durations drop to 44–10×10× shorter than the Lp=8L_p=8 K row at the same B — physically impossible given the longer prefix. The cause is that the non-streaming injector returns the full completion in one HTTP response, so the bench-side first-token timestamp defaults to 00, and the duration-based throughput calculation incorporates only a fraction of the prefill work. We therefore drop the Lp=16L_p=16 K row from the synthetic grid. This artifact does not affect any headline number in the paper: all Lp=16L_p=16 K results in §4.5 (Table 3) and Appendix B B.2 (Tables 9–11) come from the ShareGPT path, which uses bench_serving with proper streaming TTFT capture and yields physically consistent Lp=16L_p=16 K numbers (TTFT 1.91.9–2222\,s; duration 8080–9696\,s at B∈128,256,512B∈\128,256,512\). Output (tok/s) TPOT (ms) TTFT (s) LpL_p B SGL SGL-C GKV × SGL SGL SGL-C GKV SGL SGL-C GKV 512 8 540 488 491 0.91×0.91× 14 15 15 0.13 0.16 0.16 512 32 1439 1339 1314 0.91×0.91× 17 19 19 0.58 0.56 0.61 512 128 2846 2456 2452 0.86×0.86× 33 40 40 1.44 1.38 1.48 512 256 3435 2892 3394 0.99×0.99× 51 64 52 2.90 2.95 2.81 1K 8 533 489 484 0.91×0.91× 14 15 15 0.16 0.16 0.18 1K 32 1353 1273 1235 0.91×0.91× 18 19 19 0.58 0.62 0.66 1K 128 2577 2321 2260 0.88×0.88× 35 41 41 1.57 1.60 1.68 1K 256 3121 2876 3257 1.04×1.04× 55 65 52 3.00 2.87 2.97 2K 8 511 477 480 0.94×0.94× 14 15 15 0.20 0.19 0.17 2K 32 1259 1310 1288 1.02×1.02× 21 20 20 0.58 0.55 0.57 2K 128 2414 2322 2287 0.95×0.95× 39 42 41 1.70 1.63 1.78 2K 256 2816 2701 3172 1.13×1.13× 65 68 54 3.15 3.18 3.22 4K 8 484 461 459 0.95×0.95× 15 16 16 0.22 0.21 0.22 4K 32 1062 1194 1226 1.15×1.15× 24 21 21 0.68 0.66 0.59 4K 128 1970 2185 2158 1.10×1.10× 49 43 43 1.83 1.84 1.89 4K 256 2270 2568 2955 1.30×1.30× 83 70 56 3.72 3.61 3.83 8K 8 436 432 434 1.00×1.00× 16 16 16 0.26 0.27 0.25 8K 32 839 1105 1126 1.34×1.34× 30 21 22 1.03 0.96 0.83 8K 128 1469 1913 1853 1.26×1.26× 63 41 39 2.95 3.25 3.69 8K 256 1629 2208 2664 1.64×1.64× 109 63 42 6.03 6.62 6.64 Table 6: B.1 Synthetic grid: Llama-3.1-8B / TP=1. TPOT is median time-per-output-token; TTFT is median time-to-first-token. Lp=16L_p=16 K omitted (see B.1 prose for the measurement artifact). Output (tok/s) TPOT (ms) TTFT (s) LpL_p B SGL SGL-C GKV × SGL SGL SGL-C GKV SGL SGL-C GKV 512 8 495 441 445 0.90×0.90× 15 17 16 0.20 0.20 0.20 512 32 1402 1261 1289 0.92×0.92× 17 19 20 0.66 0.69 0.67 512 128 2466 2011 2021 0.82×0.82× 38 50 49 1.66 1.68 1.76 512 256 3217 2758 2828 0.88×0.88× 53 66 63 3.24 3.22 3.34 1K 8 487 442 439 0.90×0.90× 15 16 17 0.21 0.21 0.21 1K 32 1323 1222 1273 0.96×0.96× 18 20 20 0.68 0.70 0.70 1K 128 2471 1941 1999 0.81×0.81× 37 50 48 1.74 1.73 1.82 1K 256 2946 2639 2730 0.93×0.93× 57 68 63 3.59 3.47 3.47 2K 8 474 434 430 0.91×0.91× 15 17 17 0.23 0.22 0.25 2K 32 1257 1221 1232 0.98×0.98× 19 20 20 0.76 0.76 0.76 2K 128 2263 1965 1957 0.87×0.87× 41 49 50 1.87 1.97 1.83 2K 256 2766 2629 2787 1.01×1.01× 64 69 62 3.53 3.48 3.57 4K 8 448 420 418 0.93×0.93× 16 17 17 0.27 0.27 0.28 4K 32 1116 1174 1195 1.07×1.07× 22 20 20 0.81 0.83 0.82 4K 128 1899 1862 1912 1.01×1.01× 49 51 49 2.14 2.10 2.13 4K 256 2289 2414 2617 1.14×1.14× 80 75 67 3.79 3.81 3.74 8K 8 416 398 397 0.96×0.96× 17 18 18 0.29 0.30 0.29 8K 32 893 1001 1074 1.20×1.20× 28 22 21 0.95 1.22 0.96 8K 128 1427 1695 1711 1.20×1.20× 65 53 52 2.95 2.75 2.86 8K 256 1740 2170 2419 1.39×1.39× 98 71 62 6.16 5.79 5.54 Table 7: B.1 Synthetic grid: Qwen-2.5-14B / TP=2. TPOT is median time-per-output-token; TTFT is median time-to-first-token. Lp=16L_p=16 K omitted (see B.1 prose for the measurement artifact). Output (tok/s) TPOT (ms) TTFT (s) LpL_p B SGL SGL-C GKV × SGL SGL SGL-C GKV SGL SGL-C GKV 512 8 411 371 370 0.90×0.90× 18 20 20 0.25 0.25 0.26 512 32 1072 985 985 0.92×0.92× 24 26 26 0.80 0.79 0.81 512 128 2298 2112 2104 0.92×0.92× 39 43 43 2.11 2.24 2.19 512 256 2758 2308 2326 0.84×0.84× 61 80 78 3.96 3.94 3.99 1K 8 406 367 365 0.90×0.90× 18 20 20 0.27 0.26 0.27 1K 32 1061 977 976 0.92×0.92× 24 27 26 0.80 0.80 0.80 1K 128 2253 2121 2110 0.94×0.94× 39 43 43 2.18 2.13 2.17 1K 256 2638 2250 2294 0.87×0.87× 65 82 80 4.02 3.99 3.98 2K 8 399 362 362 0.91×0.91× 18 20 20 0.28 0.28 0.29 2K 32 1023 964 969 0.95×0.95× 24 27 26 0.87 0.85 0.85 2K 128 2087 2072 2069 0.99×0.99× 43 44 44 2.23 2.22 2.22 2K 256 2499 2259 2300 0.92×0.92× 69 80 77 4.18 4.16 4.28 4K 8 389 355 355 0.91×0.91× 18 20 20 0.33 0.31 0.31 4K 32 968 939 927 0.96×0.96× 26 27 27 0.93 0.90 0.94 4K 128 1831 1973 1973 1.08×1.08× 51 47 46 2.37 2.31 2.36 4K 256 2190 2104 2190 1.00×1.00× 82 86 81 4.36 4.40 4.44 8K 8 367 344 345 0.94×0.94× 19 21 21 0.34 0.33 0.31 8K 32 857 884 875 1.02×1.02× 29 28 28 1.05 1.01 1.12 8K 128 1459 1812 1772 1.21×1.21× 66 48 50 2.74 2.79 2.77 8K 256 1767 1979 2064 1.17×1.17× 101 85 79 5.60 5.63 5.74 Table 8: B.1 Synthetic grid: Qwen-2.5-32B / TP=4. TPOT is median time-per-output-token; TTFT is median time-to-first-token. Lp=16L_p=16 K omitted (see B.1 prose for the measurement artifact). B.2 Full ShareGPT Lp×BL_p× B matrix. Tables 9–11 report the full ShareGPT Lp×BL_p× B sweep at saturation rate. Output (tok/s) TPOT (ms) TTFT (s) LpL_p B SGL SGL-C GKV × SGL SGL SGL-C GKV SGL SGL-C GKV 512 8 586 532 531 0.91×0.91× 13 15 15 0.1 0.1 0.1 512 32 1882 1696 1692 0.90×0.90× 16 18 18 0.2 0.2 0.3 512 128 4556 3666 3602 0.79×0.79× 25 32 32 0.7 0.8 0.7 512 256 6284 4859 5151 0.82×0.82× 34 46 42 1.4 1.3 1.4 512 512 5928 4796 5915 1.00×1.00× 63 82 63 2.1 2.2 2.2 512 1024 5954 4765 4563 0.77×0.77× 63 82 89 2.1 2.1 2.2 1K 8 577 527 526 0.91×0.91× 13 15 15 0.1 0.1 0.1 1K 32 1789 1679 1680 0.94×0.94× 17 18 18 0.2 0.3 0.2 1K 128 4233 3576 3581 0.85×0.85× 27 32 33 0.7 0.8 0.8 1K 256 5559 4716 5087 0.92×0.92× 39 47 40 1.6 1.4 1.7 1K 512 5206 4511 5859 1.13×1.13× 70 84 63 2.3 2.3 2.4 1K 1024 5222 4540 4472 0.86×0.86× 70 85 90 2.3 2.7 2.3 2K 8 563 520 520 0.92×0.92× 14 15 15 0.1 0.1 0.1 2K 32 1624 1639 1641 1.01×1.01× 18 18 18 0.3 0.3 0.3 2K 128 3669 3488 3502 0.95×0.95× 31 33 33 0.8 0.8 0.8 2K 256 4741 4606 5030 1.06×1.06× 46 48 40 1.8 1.6 1.6 2K 512 4295 4357 5758 1.34×1.34× 84 85 62 3.1 3.1 3.1 2K 1024 4421 4113 4394 0.99×0.99× 83 85 88 3.2 3.1 3.1 4K 8 533 500 500 0.94×0.94× 14 15 15 0.1 0.1 0.2 4K 32 1385 1581 1569 1.13×1.13× 22 19 19 0.3 0.4 0.4 4K 128 2823 3309 3278 1.16×1.16× 41 34 34 1.2 1.0 1.1 4K 256 3478 4209 4684 1.35×1.35× 63 50 38 2.5 2.6 2.5 4K 512 3311 3920 5359 1.62×1.62× 111 86 58 4.9 4.8 4.9 4K 1024 3258 3932 4117 1.26×1.26× 111 87 87 4.9 5.1 5.2 8K 8 488 483 484 0.99×0.99× 16 16 16 0.2 0.2 0.2 8K 32 1054 1466 1470 1.39×1.39× 28 19 19 0.4 0.6 0.6 8K 128 1940 2791 2752 1.42×1.42× 58 37 38 2.2 2.2 2.1 8K 256 2226 3476 3801 1.71×1.71× 97 55 47 5.0 5.1 5.5 8K 512 2110 3091 3485 1.65×1.65× 173 98 96 9.4 9.5 9.8 8K 1024 2101 3076 3379 1.61×1.61× 172 104 95 9.6 9.3 9.7 16K 8 416 446 449 1.08×1.08× 18 17 17 0.2 0.3 0.3 16K 32 722 1194 1278 1.77×1.77× 42 24 23 0.3 0.3 0.3 16K 128 1231 2349 2355 1.91×1.91× 98 47 47 0.6 0.8 0.5 16K 256 1362 2800 2943 2.16×2.16× 160 65 59 10.8 10.1 10.5 16K 512 1339 2671 2960 2.21×2.21× 262 85 73 20.2 20.0 20.2 16K 1024 1331 2663 2767 2.08×2.08× 262 86 71 20.3 19.9 20.3 Table 9: B.2 ShareGPT Lp×BL_p× B at saturation rate: Llama-3.1-8B / TP=1. TPOT is median time-per-output-token; TTFT is median time-to-first-token. Output (tok/s) TPOT (ms) TTFT (s) LpL_p B SGL SGL-C GKV × SGL SGL SGL-C GKV SGL SGL-C GKV 512 8 538 480 479 0.89×0.89× 14 16 16 0.1 0.1 0.1 512 32 1842 1591 1621 0.88×0.88× 16 19 19 0.3 0.3 0.3 512 128 3725 2870 2881 0.77×0.77× 31 41 41 0.9 0.8 0.8 512 256 5797 4390 4710 0.81×0.81× 37 50 47 1.6 1.6 1.6 512 512 6581 5042 4603 0.70×0.70× 64 87 97 2.6 2.6 2.7 512 1024 6494 5025 4581 0.71×0.71× 64 88 96 2.7 2.6 2.8 1K 8 533 478 479 0.90×0.90× 15 16 16 0.1 0.1 0.1 1K 32 1758 1613 1609 0.91×0.91× 17 19 19 0.3 0.3 0.3 1K 128 3738 2803 2795 0.75×0.75× 30 42 42 0.9 0.9 0.9 1K 256 5465 4288 4654 0.85×0.85× 39 52 47 1.7 1.6 1.7 1K 512 6084 4953 4556 0.75×0.75× 70 88 97 2.7 2.8 2.8 1K 1024 6066 5009 4493 0.74×0.74× 70 87 97 2.7 2.7 3.0 2K 8 514 474 471 0.92×0.92× 15 16 16 0.1 0.1 0.1 2K 32 1626 1585 1586 0.98×0.98× 18 19 19 0.3 0.3 0.3 2K 128 3532 2828 2817 0.80×0.80× 32 41 42 1.0 0.9 0.9 2K 256 4719 4244 4567 0.97×0.97× 46 52 48 1.9 1.8 1.8 2K 512 5218 4777 4835 0.93×0.93× 83 91 90 3.1 3.2 3.1 2K 1024 5191 4770 4881 0.94×0.94× 83 91 89 3.2 3.1 3.0 4K 8 498 465 463 0.93×0.93× 15 17 17 0.1 0.1 0.1 4K 32 1405 1531 1522 1.08×1.08× 21 19 20 0.3 0.3 0.4 4K 128 2862 2718 2682 0.94×0.94× 40 43 44 1.1 1.1 1.1 4K 256 3702 3981 4457 1.20×1.20× 58 53 47 2.5 2.6 2.5 4K 512 4033 4467 4292 1.06×1.06× 105 91 96 4.8 5.0 5.0 4K 1024 4012 4433 4281 1.07×1.07× 104 93 96 4.9 5.0 5.2 8K 8 465 442 443 0.95×0.95× 16 17 17 0.2 0.2 0.2 8K 32 1107 1419 1422 1.28×1.28× 27 20 20 0.6 0.5 0.6 8K 128 2017 2450 2403 1.19×1.19× 56 45 47 1.8 1.7 1.5 8K 256 2489 3449 3902 1.57×1.57× 85 57 48 4.3 4.3 4.4 8K 512 2607 3652 3755 1.44×1.44× 155 99 97 8.9 9.1 8.6 8K 1024 2649 3676 3789 1.43×1.43× 153 100 96 8.7 8.7 8.8 16K 8 410 418 416 1.01×1.01× 18 18 18 0.3 0.3 0.3 16K 32 783 1251 1254 1.60×1.60× 39 23 23 0.5 0.6 0.7 16K 128 1320 2137 2141 1.62×1.62× 91 53 53 0.7 0.8 0.9 16K 256 1567 2706 3109 1.98×1.98× 138 69 59 8.7 8.8 9.1 16K 512 1635 2866 3009 1.84×1.84× 229 97 93 17.5 17.8 17.1 16K 1024 1621 2870 3010 1.86×1.86× 232 98 92 17.7 17.6 17.3 Table 10: B.2 ShareGPT Lp×BL_p× B at saturation rate: Qwen-2.5-14B / TP=2. TPOT is median time-per-output-token; TTFT is median time-to-first-token. Output (tok/s) TPOT (ms) TTFT (s) LpL_p B SGL SGL-C GKV × SGL SGL SGL-C GKV SGL SGL-C GKV 512 8 445 399 397 0.89×0.89× 17 19 20 0.1 0.1 0.1 512 32 1320 1186 1181 0.89×0.89× 23 26 26 0.4 0.4 0.4 512 128 3718 3309 3261 0.88×0.88× 30 34 35 1.1 1.1 1.1 512 256 4813 3646 3703 0.77×0.77× 44 61 60 2.0 1.9 2.0 512 512 5883 4615 3929 0.67×0.67× 71 94 112 3.2 3.3 3.3 512 1024 5825 4608 3942 0.68×0.68× 71 94 112 3.2 3.3 3.3 1K 8 443 398 398 0.90×0.90× 17 20 20 0.1 0.1 0.1 1K 32 1297 1177 1180 0.91×0.91× 23 26 26 0.4 0.4 0.4 1K 128 3550 3237 3240 0.91×0.91× 32 35 35 1.0 1.1 1.0 1K 256 4823 3656 3746 0.78×0.78× 44 61 59 2.0 2.0 1.9 1K 512 5540 4494 3891 0.70×0.70× 76 96 114 3.3 3.3 3.4 1K 1024 5541 4556 3965 0.72×0.72× 75 95 111 3.3 3.2 3.3 2K 8 436 394 395 0.90×0.90× 18 20 20 0.2 0.1 0.2 2K 32 1256 1164 1171 0.93×0.93× 24 26 26 0.4 0.4 0.4 2K 128 3255 3229 3195 0.98×0.98× 35 35 35 1.2 1.2 1.1 2K 256 4410 3422 3623 0.82×0.82× 49 67 61 2.0 2.1 2.0 2K 512 5024 4455 4275 0.85×0.85× 84 97 101 3.4 3.4 3.6 2K 1024 4994 4417 4356 0.87×0.87× 84 98 99 3.5 3.4 3.5 4K 8 429 390 390 0.91×0.91× 18 20 20 0.2 0.2 0.2 4K 32 1174 1149 1148 0.98×0.98× 25 26 26 0.4 0.5 0.4 4K 128 2732 3045 3015 1.10×1.10× 42 37 38 1.3 1.3 1.1 4K 256 3629 3394 3597 0.99×0.99× 60 64 60 2.6 2.6 2.6 4K 512 4147 4222 3765 0.91×0.91× 100 99 113 5.1 4.9 5.0 4K 1024 4149 4208 3741 0.90×0.90× 100 99 114 5.0 5.0 5.0 8K 8 407 380 379 0.93×0.93× 19 20 20 0.2 0.2 0.2 8K 32 1050 1095 1085 1.03×1.03× 28 27 27 0.6 0.6 0.6 8K 128 2061 2724 2678 1.30×1.30× 56 41 41 1.6 1.5 1.6 8K 256 2620 3036 3292 1.26×1.26× 78 66 59 4.5 4.5 4.6 8K 512 3015 3466 3294 1.09×1.09× 130 106 113 8.6 9.1 9.2 8K 1024 3007 3608 3336 1.11×1.11× 130 102 113 8.7 8.7 8.9 16K 8 374 358 357 0.95×0.95× 20 21 21 0.3 0.3 0.3 16K 32 877 1009 1001 1.14×1.14× 34 28 28 0.9 1.0 1.0 16K 128 1382 2159 2162 1.56×1.56× 86 52 51 1.1 1.4 1.5 16K 256 1726 2362 2707 1.57×1.57× 121 79 69 9.4 9.0 8.9 16K 512 1938 2815 2660 1.37×1.37× 185 103 114 17.1 17.1 17.5 16K 1024 1934 2774 2685 1.39×1.39× 184 104 113 17.5 17.6 17.4 Table 11: B.2 ShareGPT Lp×BL_p× B at saturation rate: Qwen-2.5-32B / TP=4. TPOT is median time-per-output-token; TTFT is median time-to-first-token. B.2b Concurrency saturation: peak is at B=256B=256. Across all three configurations the GraniKV output throughput is at or near its peak at B=256B=256; pushing concurrency to 512512 and 10241024 yields no further gain and on Qwen-2.5-14B / TP=2 and Qwen-2.5-32B / TP=4 a measurable regression (Table 12). The mechanism is twofold: the per-step dispatcher holds both attention backends simultaneously and pre-allocates CUDA-graph buffers for each, which costs a few hundred MB at B=1024B=1024 and squeezes the KV-cache budget; and once Meff≥1024M_eff≥1024 is crossed at B=256B=256 the dense kernel already saturates Tensor Cores, so additional concurrency adds scheduling and dispatch overhead without improving the kernel’s arithmetic intensity. We take B=256B=256 as the operating point throughout §4.5–§4.6. Config B=256B=256 B=512B=512 B=1024B=1024 Peak B Llama-8B/TP=1 29432943 29602960 27672767 512512 Qwen-14B/TP=2 31093109 30093009 30103010 256256 Qwen-32B/TP=4 27072707 26602660 26852685 256256 Table 12: B.2b GraniKV output throughput at Lp=16L_p=16K (tok/s, 3-rep means) across B∈256,512,1024B∈\256,512,1024\. B=256B=256 is the peak for two of three configurations and within 0.6%0.6\% of the Llama peak at B=512B=512. Pushing B higher costs throughput on Qwen-14B (−3%-3\%) and gives a marginal regression on Qwen-32B/TP=4 (−1-1 to −2%-2\%). B.3 Cross-Configuration Validity. The kernel-isolated microbench in §4.6 is by construction kernel-only; we confirm it reproduces in an end-to-end serving setup by capturing torch.profiler traces at the B=256B=256, Lp=8KL_p=8K cell on two configurations — the Llama-3.1-8B / TP=1 headline (Table 13) and a structurally different Qwen-2.5-32B / TP=4 (Table 14, Meff=1280M_eff=1280) — for all four systems. SGLang-Cascade reduces prefix-attention kernel time by 3.66×3.66× on Llama-3.1-8B / TP=1 (11058→302111058→ 3021 ms) and by 1.24×1.24× on Qwen-2.5-32B / TP=4 (20298→1642320298→ 16423 ms); the smaller reduction at the larger configuration is consistent with its lower Hkv/rank=2H_kv/rank=2, which leaves fewer heads for the multi-query cascade kernel to deduplicate across. SGL-C/GKV (SGLang-Cascade run on GraniKV’s HOT/COLD storage) tracks SGLang-Cascade within trace-noise on every category at both configurations — within 1.5%1.5\% at Qwen-32B/TP=4 and within 5%5\% at Llama-3.1-8B/TP=1 (max 4.5%4.5\% on the Linear GEMM category, where short per-step kernels make ratios noisier) — confirming the storage layer is kernel-agnostic. GraniKV’s dense-backend contribution does not surface in either CUPTI capture because its Triton-compiled kernel is invisible to the in-server profiler hook; nsys (Table 17) confirms the kernel fires by direct CUDA-event capture. Category SGL SGL-C SGL-C/GKV GKV Prefix attention 1105811058 3021 03021 3005 03005 3040 03040 Decode attention 95 0095 286 00286 279 00279 281 00281 Linear GEMM 9558 09558 1001110011 9563 09563 9766 09766 Total kernel 2136521365 1408814088 1358513585 1385513855 Table 13: Kernel-time category breakdown at Llama-3.1-8B / TP=1, B=256B=256, Lp=8KL_p=8K (ms, summed over the trace window). Columns as in Table 14. Category SGL SGL-C SGL-C/GKV GKV Prefix attention 2029820298 1642316423 1667116671 1634516345 Decode attention 612 0612 10661066 10761076 10691069 Linear GEMM 2939629396 2961829618 2979129791 2978429784 Total kernel 127914127914 136525136525 138822138822 139422139422 Table 14: Kernel-time category breakdown at Qwen-2.5-32B / TP=4, B=256B=256, Lp=8KL_p=8K (ms, summed over the trace window). SGL = SGLang default; SGL-C = SGLang-Cascade; SGL-C/GKV = SGLang-Cascade kernel run on GraniKV’s HOT/COLD storage. B.4 Per-Step Dispatch Trace. Table 15 reports the fraction of decode steps routed to the dense backend on Llama-3.1-8B / TP=1 across the synthetic-grid (Lp,B)(L_p,B) cells. Cells crossing Meff=B⋅nq/kv≥1024M_eff=B· n_q/kv≥ 1024 route almost entirely to matmul, sub-threshold cells to cascade — empirical evidence that routing follows the realized batch, not a static boot-time choice. Matmul-routed fraction at B LpL_p 8 32 128 256 majority 512 00% 00% 44% 9898% cascade 2K 00% 00% 77% 9999% cascade 8K 00% 00% 1111% 100100% mixed 16K 00% 00% 1313% 100100% mixed Table 15: B.4 Fraction of decode steps the per-step wrapper routes to the dense backend, on Llama-3.1-8B / TP=1 (nq/kv=4n_q/kv=4). At B=256B=256 the saturation threshold Meff≥1024M_eff≥ 1024 is met on every step; at B<256B<256 the realized concurrency under prefill bursts occasionally crosses the threshold and matmul fires opportunistically. B.4b Empirical fit of the dispatch threshold. The Meff≥1024M_eff≥1024 threshold of §3.6 was selected by examining the per-token kernel cost of the dispatcher’s two children at fixed Lp=8L_p=8 K on Llama-3.1-8B / TP=1 (nq/kv=4n_q/kv=4; Table 16, drawn from the same synthetic-grid runs as Table 6). Below Meff=1024M_eff=1024 the dense backend’s per-token TPOT is within 3%3\% of cascade and the dispatcher routes ≤13%≤13\% of steps to dense (Table 15); at Meff=1024M_eff=1024 the dense backend’s per-token TPOT drops to 0.67×0.67× cascade and the dispatcher routes 98−100%98-100\% of steps to dense. The knee is sharp and sits at Meff∼1024M_eff 1024 on A100, justifying the threshold; on other hardware it would be re-fit by re-running this sweep. B MeffM_eff GKV TPOT (ms) SGL-C TPOT (ms) GKV / SGL-C 8 008 32 00032 1616 1616 1.00×1.00× 32 032 128 00128 2222 2121 1.02×1.02× 128128 512 0512 3939 4141 0.97×0.97× 256256 10241024 4242 6363 0.67×0.67× Table 16: B.4b Empirical fit of the dispatch threshold: Llama-3.1-8B / TP=1, Lp=8L_p=8 K synthetic-grid cells. Meff=B⋅nq/kvM_eff=B· n_q/kv with nq/kv=4n_q/kv=4. The crossover from cascade-parity to a clear dense win occurs between Meff=512M_eff=512 and Meff=1024M_eff=1024, justifying the ≥1024≥ 1024 dispatcher cutoff. B.5 Per-Step Dispatch Overhead. The thin Python wrapper that selects the kernel each step is not on the critical path. An nsys capture under --trace=cuda,nvtx,osrt on the dense-backend microbench over a 1515-second window measures the values in Table 17: the dense-backend prefix kernel fires 8383 times at 442μ442\, per launch (CUPTI direct capture), and the Python wrapper adds <1μ<1\, of CPU work per decode step — under 0.2%0.2\% of the per-step wall time at the headline cell. The same nsys trace serves as direct evidence that the dense backend actually fires under per-step dispatch (the kernel is invisible to the in-server torch.profiler hook — see Table 14). Quantity Value Dense-backend launches in 1515 s 8383 Kernel wall / launch 442μ442\, Wrapper CPU / step <1μ<1\, Wrapper % of step <0.2%<0.2\% Table 17: Per-step dispatch overhead from nsys on the dense-backend microbench. B.6 COLD Page-Size Sensitivity. We verify that token-level COLD allocation (page size 11) does not regress throughput relative to coarser paging by sweeping the COLD page size ∈1,4,16∈\1,4,16\ on the headline cells of two configurations, holding HOT pool and attention kernels fixed (Table 18). End-to-end throughput is flat within ±0.2%± 0.2\% across the sweep — well inside our per-cell 33-rep noise floor. The per-token indirection overhead introduced by page size 11 does not materialize in end-to-end measurement. Config PS=1 PS=4 PS=16 |Δ|max| |_ Llama-8B / TP=1 26642664 26612661 26592659 0.19%0.19\% Qwen-32B / TP=4 20642064 20652065 20622062 0.15%0.15\% Table 18: B.6 COLD page-size sensitivity at the headline cell (B=256B=256, Lp=8L_p=8K) of two configurations. Throughput in output tok/s (33-rep mean); |Δ|max| |_ is the largest spread within each row. All three page sizes track within ±0.2%± 0.2\%. B.7 TP Regime Envelope. GraniKV’s benefit depends on two structural ceilings that move in opposite directions with tensor-parallel rank count. The KV-memory ceiling shrinks as TP shrinks: at low TP, weights consume more per-rank HBM, leaving less room for KV cache, so the runtime caps the realized batch below the matmul-saturation threshold. The NCCL Amdahl ceiling shrinks as TP grows: the all-reduce share of decode time grows with rank count, capping the fraction of the step that shortening attention can recover. A related head-fused-tile floor, Hkv/rank=Hkv/TPH_kv/rank=H_kv/TP, collapses at Hkv/rank=1H_kv/rank=1 and prevents the dense backend from saturating Tensor Cores at all. Table 19 summarizes the empirical pattern across five (model, TP) configurations, all measured at the synthetic-grid headline cell (Lp=8L_p=8 K, B=256B=256). The three configurations that also appear in B.1 (Llama-8B/TP=1, Qwen-14B/TP=2, Qwen-32B/TP=4) match the corresponding B.1 88K/256256 rows exactly; Qwen-14B/TP=4 and Qwen-32B/TP=2 are additional cells run at the same point to mark the NCCL-Amdahl and KV-memory ceiling boundaries, respectively, and are not part of the headline B.1 sweep. Config Hkv/rkH_kv\!/\!rk NCCL KV mem GKVSGL GKVSGL Regime Llama-8B / TP=1 8 none abund. 1.64×1.64× peak Qwen-14B / TP=2 4 2-way comf. 1.39×1.39× modest NCCL Qwen-14B / TP=4 2 4-way comf. 1.18×1.18× NCCL-bound Qwen-32B / TP=4 2 4-way tight 1.17×1.17× NCCL+mem Qwen-32B / TP=2 4 2-way v.tight 0.99×0.99× KV-ceil Table 19: TP regime envelope across five (model, TP) configurations at the synthetic-grid headline cell (Lp=8L_p=8 K, B=256B=256). The Qwen-32B/TP=2 row is the parity case that bounds GraniKV’s contribution from below. Why TP=8 is not evaluated. At TP=8 on a 4×4× or 8×8×A100 host, every model in our matrix lands at Hkv/rank=1H_kv/rank=1, putting it on the wrong side of the head-fused-tile floor regardless of model size. The per-step dispatch correctly routes every step to cascade, so a TP=8 experiment would only measure the cascade-integration sub-contribution (already characterized in §4.5) at a more communication-heavy operating point. There is no recommended single TP: the operator should pick the lowest TP that fits the model’s weights with sufficient KV headroom for the target peak concurrency, and GraniKV’s per-step dispatch then maximizes the available kernel choice within that envelope. B.8 Multi-prefix sensitivity. The ShareGPT setup of §4.5 prepends a single fixed system prompt to every request — the most favourable case for the HOT pool. To more deeply simulate realistic production workloads, we also evaluate GraniKV under a multi-shared-prefix setting that mirrors a multi-tenant deployment where several distinct shared prefixes share the engine concurrently. We sweep the prefix-set cardinality k∈1,4,16,64k∈\1,4,16,64\ on Llama-3.1-8B / TP=1 at the Lp=8L_p=8 K, B=256B=256 headline cell. For each k, we generate k lexically-distinct synthetic system prompts of length LpL_p with deterministic seeds; every incoming user turn is deterministically assigned one of the k prompts. Because the system prompts here are synthetically generated rather than the ShareGPT-derived fixed prompt of §4.5, the k=1k=1 row is the within-experiment single-prefix baseline for this variant and is numerically close to but not identical to the Lp=8L_p=8 K, B=256B=256 row of Table 9 (within ∼4% 4\% across all three systems); the discrepancy reflects differing token-level prompt content at fixed LpL_p, not a methodological change. System k=1k=1 k=4k=4 k=16k=16 k=64k=64 SGLang default 23002300 22392239 13341334 304304 SGLang-Cascade 36023602 22012201 13141314 295295 GraniKV 38813881 30343034 14171417 296296 GraniKV / SGL 1.69×1.69× 1.36×1.36× 1.06×1.06× 0.97×0.97× GraniKV / SGL-C 1.08×1.08× 1.38×1.38× 1.08×1.08× 1.00×1.00× Table 20: B.8 Multi-prefix sensitivity at Llama-3.1-8B / TP=1, Lp=8L_p=8 K, B=256B=256. Output tok/s, 33-rep means. k is the cardinality of the distinct-system-prompt set; each request is deterministically assigned one of the k prompts. The k=1k=1 row recovers the single-prefix headline. Findings. GraniKV retains a solid win at k=4k=4 (1.36×1.36× over SGLang default, 1.38×1.38× over SGLang-Cascade — in fact a larger cascade margin than k=1k=1, because 4-way prefix split reduces in-batch cascade sharing while the HOT pool still holds all four prefixes simultaneously). At k=16k=16 all three systems converge to near-parity as 16×Lp=128K16× L_p=128K tokens compete for the HOT/KV budget; at k=64k=64 all three collapse together (≈300≈ 300 tok/s, an 87%87\% drop from k=1k=1) because 64×Lp=512K64× L_p=512K tokens exceed the realizable working set under B=256B=256 concurrency. The collapse at k=64k=64 is a paged-engine-wide phenomenon, not a GraniKV-specific limitation: every system thrashes when the active prefix set exceeds the engine’s KV budget. B.8b Heterogeneous-length multi-prefix. The B.8 sweep varies prefix cardinality at uniform length; this section additionally varies length, matching the multi-agent deployment pattern in which sub-agents carry system prompts that differ in both content and size. Four content-distinct agent personas are sized to Lp∈2K,4K,8K,16KL_p∈\2K,4K,8K,16K\ tokens and interleaved round-robin in one ShareGPT serving stream (512512 requests, 128128 per class, B=256B=256 at saturation, Llama-3.1-8B/TP=1, 33 reps; GraniKV at fp=0.3f_p=0.3 so all four slabs, 30,72030,720 tokens total, admit — cf. Appendix B). System tok/s ×default TPOT p50/p99 (ms) TTFT p50 (s) k=4k=4: Lp∈2K,4K,8K,16KL_p∈\2K,4K,8K,16K\ (30.730.7K slab tokens) SGLang default 23232323 1.00×1.00× 93.093.0 / 104.6104.6 4.54.5 SGLang-Cascade 23032303 0.99×0.99× 93.993.9 / 104.9104.9 4.44.4 GraniKV 4538 1.95×1.95× 38.038.0 / 49.449.4 4.64.6 k=8k=8: LpL_p ladder 11K–1616K (53.253.2K slab tokens) SGLang default 24282428 1.00×1.00× 90.890.8 / 99.6 099.6 3.93.9 SGLang-Cascade 23482348 0.97×0.97× 91.391.3 / 105.9105.9 4.04.0 GraniKV 4424 1.82×1.82× 38.338.3 / 53.153.1 3.73.7 Table 21: B.8b Heterogeneous-length multi-prefix: k distinct system prompts of different lengths interleaved under ShareGPT saturation, Llama-3.1-8B/TP=1, B=256B=256 (33-rep means). GraniKV at fp=0.3f_p=0.3 (k=4k=4) / 0.40.4 (k=8k=8) so all slabs admit (cf. Appendix B). Findings. The regime inverts the single-prefix attribution of Table 3. Cascade attention deduplicates a batch-global shared level; with four distinct prefixes in flight that common level is empty, and SGLang-Cascade collapses to parity with the production default (0.99×0.99×). GraniKV’s benefit is per prefix class: the radix tree tags each sub-agent’s prefix independently, each class receives its own contiguous HOT slab, and the dense backend batches the requests of each class against their slab — so batched-GEMM prefix attention survives exactly where batch-global deduplication dies, and GraniKV serves 1.95×1.95× the production default’s throughput at k=4k=4 (2.45×2.45× lower TPOT p50) and 1.82×1.82× at k=8k=8 with 5353K slab tokens live across eight size classes — a gradual taper toward the KV-budget wall that the uniform sweep (Table 20) bounds at k=16k=16–6464, not a cliff. In this regime the asymmetric storage layer accounts for essentially the entire end-to-end win, establishing the single-prefix cells — where cascade alone captures most of the gain — as the floor of the storage layer’s contribution, not its typical value in multi-agent serving. The mixed slab sizes also exercise the HOT pool’s first-fit packing with heterogeneous allocation sizes: all classes admit at both k values and no fragmentation-related degradation is observed (TTFT at parity with both baselines). B.9 Amdahl residual breakdown. The Amdahl prediction in §4.6 over-predicts the measured end-to-end gain. To attribute the residual we measure a three-term decomposition on the SGLang-default kineto traces at the headline cell (steady-state decode windows, per-rank interval-merged kernel timelines): the NCCL all-reduce share β, the host-gap share γ (wall time with the GPU idle, waiting on Python dispatch and scheduling — invisible to kernel-time profiling, which is why it also corrects the denominator of α), and the in-engine effective kernel speedup seffs_eff: S=1(1−α−β−γ)+α/seff+β+γ.S\;=\; 1(1-α-β-γ)\;+\;α/s_eff\;+\;β\;+\;γ. (4) Table 22 reports the measured terms. Three observations. First, β grows monotonically with rank count (0%/4.5%/7.9%0\%/4.5\%/7.9\%), as expected. Second, γ does not: it is largest at TP=1 (5.6%5.6\%) and vanishes at TP=4 (0.3%0.3\%), where the GPU is ∼99.7% 99.7\% occupied and host gaps hide behind kernel execution; adding β+γβ+γ closes the TP=1 residual from +14.5%+14.5\% to +5.8%+5.8\%. Third, at TP>1TP>1 the dominant term is seffs_eff: the kernel-isolated s=15.6s=15.6 of Table 5 is measured at 88 KV heads, and the speedup realized inside the engine falls with KV heads per rank — implied seff=9.4×/4.1×/2.6×s_eff=9.4×/4.1×/2.6× at 8/4/28/4/2 heads/rank — which is the head-fused-tile floor of Appendix B appearing inside the Amdahl bridge. The residual is therefore host gaps at TP=1 and predominantly head-geometry-limited kernel realization (plus NCCL) at TP>1TP>1. Config α β γ S (s=15.6s=15.6) S (+β,γ+β,γ) Meas. seffs_eff Llama-8B/TP=1 60.1%60.1\% 0.0%0.0\% 5.6%5.6\% 2.47×2.47× 2.29×2.29× 2.16×2.16× 9.4×9.4× Qwen-14B/TP=2 65.6%65.6\% 4.5%4.5\% 6.5%6.5\% 2.91×2.91× 2.59×2.59× 1.98×1.98× 4.1×4.1× Qwen-32B/TP=4 59.1%59.1\% 7.9%7.9\% 0.3%0.3\% 2.25×2.25× 2.24×2.24× 1.57×1.57× 2.6×2.6× Table 22: Measured three-term Amdahl decomposition at the headline ShareGPT cell (Lp=16L_p=16 K, B=256B=256), SGLang default. α = prefix-attention share of decode wall time; β = NCCL share; γ = host-gap (GPU-idle) share. S⁡(s=15.6)S(s=15.6) uses the kernel-isolated microbench speedup; S⁡(+β,γ)S(+β,γ) adds the two measured non-shrinking terms; seffs_eff is the in-engine effective kernel speedup implied by the measurement, falling with KV heads/rank (8/4/28/4/2). B.10 Cross-pool admission and promotion policy. At admission, GraniKV’s allocator tries the HOT pool (§3.2) first. If the HOT pool lacks contiguous capacity for the requested LpL_p — either because the pool is full or because free fragments are too small — the prefix is placed in the COLD pool, with no demotion of any existing HOT prefix. The no-demotion rule keeps the dense backend’s stride-math addressing into the HOT pool statically valid: a request mid-decode that holds a HOT base index can continue without re-checking residency on every step. A prefix that lands in COLD stays in COLD for its lifetime — we do not promote on subsequent reference, because the per-decode-step KV copy required to move the prefix’s K/V tensors between pools exceeds the per-step kernel advantage the move would unlock on the workloads we measure. Hotness-aware admission heuristics (e.g. deferring HOT promotion until a prefix has accumulated enough references) could refine this policy and are noted as future work in the Limitations section. B.11 Roofline analysis with hardware counters. This section places both storage layouts of the Table 5 microbench on the A100 roofline using NVIDIA Nsight Compute (ncu) hardware counters, and bounds how much of the 15.6×15.6× gap kernel tuning could ever recover. Counters were captured on the same A100-SXM4-40GB at the headline shape (B=256B=256, Lp=8KL_p=8K, Llama-3.1-8B head; 34.434.4 GFLOP of useful QKp⊤QK_p /PVPV work per launch); wall times use CUDA-event timing with SM clocks locked at 14101410 MHz, reproducing Table 5 within 1.3%1.3\%.11 1 ncu replays kernels at base clocks for counter stability; byte and hit-rate counters are clock-invariant. Metrics: dram__bytes_read.sum, lts__t_sector_hit_rate.pct, sm__pipe_tensor_op_hmma_cycles_active (pct of peak), launch__waves_per_multiprocessor; mean of 5 steady-state launches. Measured (ncu) shared (HOT) unique (paged) DRAM bytes read / launch 36.736.7 MB 8.618.61 GB vs. byte model +9%+9\% (Q, meta) +0.24%+0.24\% L2 hit rate 89.1%89.1\% 26.1%26.1\% Tensor-core pipe active 24.7%24.7\% 25.9%25.9\% Waves per SM 4.74.7 75.975.9 Wall time (14101410 MHz) 455μ455\, 7004μ7004\, Useful throughput 75.575.5 TF/s 4.914.91 TF/s Achieved DRAM bandwidth 8181 GB/s 12291229 GB/s Arithmetic intensity 936936 F/B 3.993.99 F/B Table 23: A100 hardware counters for the two storage layouts of Table 5 (same kernel, same tile shape). The measured DRAM traffic matches the analytical byte model within 0.24%0.24\% on the paged side, and tensor-core activity is nearly identical across layouts, isolating the layout effect from any kernel-utilization confound. Figure 1: Roofline placement of the two layouts (A100: 312312 TFLOP/s BF16, 15551555 GB/s, ridge ≈201≈201 FLOP/B). The paged layout pins arithmetic intensity at ≈2nq/kv=4≈2\,n_q/kv=4 FLOP/byte, imposing a memory roof of 6.26.2 TFLOP/s (2%2\% of tensor-core peak); the measured kernel achieves 79%79\% of that roof. The contiguous layout raises intensity ≈235×≈235×, crossing the ridge into the compute-bound region. Table 23 and Figure 1 support three claims. First, the byte model is exact: the paged-equivalent layout reads 8.618.61 GB from DRAM per launch against 8.598.59 GB predicted by B⋅Lp⋅2⋅Hkv⋅dh⋅2B· L_p· 2· H_kv· d_h· 2 bytes — each request re-reads the shared prefix — while the contiguous layout reads the prefix once (36.736.7 MB, the excess over 33.633.6 MB being query and tile-metadata reads). Second, the paged kernel has little tuning headroom: at 3.993.99 FLOP/byte the memory roof is 1555GB/s×3.99=6.21555\,GB/s× 3.99=6.2 TFLOP/s, and the kernel achieves 4.914.91 TFLOP/s — 79%79\% of the roof, i.e. a maximum attainable gain of 1.27×1.27× from any further tuning, versus 15.4×15.4× from changing the layout. The bottleneck is the roof itself, which only a storage-layout change can raise. Third, the speedup is not a utilization artifact: tensor-core pipe activity is nearly identical across layouts (24.7%24.7\% vs. 25.9%25.9\%) and occupancy is healthy in both (4.74.7 and 75.975.9 waves/SM). The paged layout in fact executes ∼16× 16× more tensor-core instructions for the same useful work — per-request M=1M=1 query tiles are padded to the M=16M=16 tile floor — so scattered storage wastes both memory bandwidth (256×256× redundant reads, L2 hit rate 26%26\% vs. 89%89\%) and tensor-core issue slots (15/1615/16 padding), both consequences of the same layout constraint. B.12 Sensitivity to the HOT-pool fraction fpf_p. The HOT-pool fraction fpf_p is set once at boot; this section measures its sensitivity at the synthetic headline cell (Llama-3.1-8B/TP=1, B=256B=256, Lp=8L_p=8 K, 3 reps per point), sweeping fp∈0.05,0.1,0.2,0.4,0.6,0.8f_p∈\0.05,0.1,0.2,0.4,0.6,0.8\ with a cascade-only run (same engine, no HOT/COLD storage or dense backend) as reference. fpf_p tok/s ×Cascade TPOT p50/p99 (ms) TTFT p50 (s) 0.050.05† 29872987 1.16×1.16× 34.134.1 / 38.738.7 5.95.9 0.10.1 29832983 1.16×1.16× 32.932.9 / 36.636.6 6.16.1 0.20.2 30053005 1.17×1.17× 34.434.4 / 38.738.7 5.85.8 0.40.4 30063006 1.17×1.17× 33.133.1 / 35.835.8 6.06.0 0.60.6 30033003 1.17×1.17× 32.932.9 / 35.735.7 6.06.0 0.80.8 30143014 1.17×1.17× 32.832.8 / 35.535.5 6.06.0 Cascade 25742574 1.00×1.00× 48.448.4 / 51.451.4 6.06.0 Table 24: fpf_p sensitivity at the synthetic headline cell (mean of 3 reps; between-rep sd ≈6%≈6\%). †At fp=0.05f_p=0.05 the HOT pool (7,4207,420 slots) is smaller than the 8,1928,192-token prefix. Throughput is flat within ±1%± 1\% across fp∈[0.05,0.8]f_p∈[0.05,0.8] — well inside between-rep noise — and the per-step advantage over cascade (1.47×1.47× TPOT p50, consistent with Appendix B) is preserved at every setting. Two mechanisms explain the insensitivity. First, the benefit requires only that the HOT pool admit the active prefix set: once the LpL_p-token slab fits, additional HOT capacity is idle headroom, not additional speed. Second, mis-provisioning in either direction is absorbed by design — unused HOT capacity is donated to the COLD free list under suffix-allocation pressure (§3.2), and a prefix that cannot be admitted contiguously falls back to the paged path (Appendix B). The fp=0.05f_p=0.05 row exercises the second mechanism: the HOT pool is deliberately provisioned smaller than the prefix, and the system degrades gracefully (TPOT p50 +4%+4\% relative to fp≥0.1f_p≥0.1; no failure) rather than falling off a cliff. In deployment, fpf_p therefore needs only to be large enough for the expected concurrent distinct-prefix set — k⋅Lpk· L_p tokens — and errors in either direction are benign.

Instant research discovery