PaperlayerView exact revision on arXiv

Source-linked AI summary

UlaCache: Unified Logical Addressing for Sparse LLM Serving

Isaac Zhu, Alan Cao, Hugh Yin, Rocky Wang, Orion Wang, Hscos Zhang, Jack Li, Jason Zhao

arXiv:2610.29820v1cs.DC

TL;DR

Long-context sparse attention reads selected KV, but the retained history must remain available as future selections change, making cache storage a constraint for LLM decoding. UlaCache manages KV through stable logical addresses across GPU and optional CPU storage, with shared interfaces for DP and TP and local buffers for TP. With speculative decoding and matched CPU/GPU memory budgets, it reports peak throughput speedups over HiSparse on H200 and B300.

  • Problem

    Sparse attention reduces KV reads per decoding step, but retained histories still grow with context and active requests, constraining concurrent decoding under fixed memory.

    Source: §1 · pp. 1–2

  • Method

    UlaCache uses stable logical KV addresses across GPU and optional CPU pools, with common DP/TP allocation and sparse-access interfaces and local TP buffers for selected KV.

    Source: §1 · p. 2, §4.3 · p. 6

  • Results

    1.16× (DP) and 1.70× (TP) on 8×H200, and 1.73× (DP) and 2.51× (TP) on 8×B300: peak decoding throughput speedups over HiSparse with speculative decoding and matched CPU/GPU memory budgets.

    Source: §1 · p. 2, §8 · p. 10

  • Takeaways & Limitations

    UlaCache coordinates KV transfers and mapping updates while retaining stable logical references, and reuses selected KV in TP local buffers across decoding steps.

    Source: §4.3 · p. 6, §8 · p. 10

Abstract

from arXiv · show

Long contexts increase the memory cost of the key-value (KV) cache in large language model (LLM) inference. Sparse attention reduces attention computation and memory traffic by selecting historical tokens, but the retained KV cache must remain available for later decoding steps. We present UlaCache, a KV cache management system built around a unified logical address space spanning GPU KV pools and optional CPU memory. Stable logical references let the inference engine allocate and select KV independently of physical placement. Common allocation and sparse-access interfaces support data-parallel (DP) and tensor-parallel (TP) attention. For distributed storage, local GPU buffers retain selected KV across decoding steps, so only missing entries require transfers. When CPU storage is enabled, Parallel Bucketed LRU (PB-LRU) manages a GPU pool shared across requests. It updates recency metadata and selects eviction victims in parallel. UlaCache transfers KV and then updates the address mappings. With speculative decoding enabled under matched CPU and GPU memory budgets, UlaCache achieves peak decoding throughput speedups of 1.16 $\times$ (DP) and 1.70 $\times$ (TP) on H200, and 1.73 $\times$ (DP) and 2.51 $\times$ (TP) on B300, compared with the state-of-the-art baseline.

1 INTRODUCTION

UlaCache addresses the storage challenge of sparse attention by separating stable logical KV references from physical placement across GPU and optional CPU memory. It combines shared allocation and sparse-access interfaces with parallel cache management, and reports higher peak throughput than HiSparse under the stated speculative-decoding setup.

Introduction

  • Sparse attention reads selected historical KV, but the full retained history must remain available as selections can change, leaving storage capacity a constraint on concurrent decoding.CPU storage does not by itself resolve the constraint when active histories still occupy GPU slots or GPU and CPU hold duplicate history.Source: §1 · pp. 1–2

Unified KV addressing and storage organization

  • UlaCache uses stable logical references across GPU and optional CPU pools, with common allocation and sparse-access interfaces for rank-local DP and distributed TP storage.It resolves selected addresses, transfers KV, and updates mappings as physical placement changes.Source: §1 · p. 2

Parallel bucketed LRU and address mapping updates

  • Parallel Bucketed LRU groups GPU slots into recency buckets and parallelizes address translation, hit detection, recency updates, and replacement-slot selection.After transfers complete, UlaCache updates mappings; shared-layer access plans can be reused to reduce repeated management work.Source: §1 · p. 2

System implementation and evaluation

  • 1.16× (DP) and 1.70× (TP) on 8×H200, and 1.73× (DP) and 2.51× (TP) on 8×B300: UlaCache’s peak decoding throughput speedups over HiSparse with speculative decoding and matched CPU/GPU budgets.The evaluation implements UlaCache in SGLang.Source: §1 · p. 2

2 BACKGROUND AND MOTIVATION

Sparse attention reduces per-step KV reads, but retained histories still require storage and may be duplicated across devices. The section contrasts CPU-storage uses and fixed cache quotas as constraints on decode concurrency.

2.1.1 Sparse Attention and KV History

  • For a history of L positions and k selected positions, sparse attention reads k entries, while the remaining history must stay available because later queries can select different entries.The indexer’s compact selection state is separate from the KV records consumed by attention.Source: §2.1.1 · p. 3

2.1.2 Attention Parallelism and KV Placement

  • Under TP, ranks can store replicated MLA history, while DP avoids that replication but makes a request’s usable capacity depend on its assigned rank.Free slots on another DP rank are not directly available without an additional placement and access mechanism.Source: §2.1.2 · p. 3

2.1.3 CPU Storage for KV Cache

  • CPU prefix caches restore reusable KV into GPU slots, whereas sparse KV offloading retains active histories in CPU memory and fetches selected entries for attention.GPU caching can retain selected entries across steps to reduce repeated transfers.Source: §2.1.3 · p. 3

2.2.1 KV Storage and Decode Concurrency

  • HiSparse stores complete active histories in CPU memory but duplicates cached entries in GPU memory; its 53.3 million physical slots hold only 30.0 million unique history positions.In eight-rank TP, only 12.5% of SGLang and HiSparse history allocation stores unique history, while 87.5% holds replicas.Source: §2.2.1 · p. 4

2.2.2 Fixed Per-Request Cache Quotas

  • At 8×B300 DP with speculative decoding, GPU capacity can hold all active history at BS1, yet HiSparse’s fixed per-request buffer retains only its quota and has 23.5% higher TPOT than GPU-resident SGLang.The fixed quota can leave GPU capacity idle and cause selected entries to be fetched from CPU.Source: §2.2.2 · p. 4

3 SYSTEM OVERVIEW

UlaCache coordinates logical-to-physical KV placement and access in DP and TP modes. Optional CPU storage uses PB-LRU to manage transfers and mapping updates.

3 SYSTEM OVERVIEW

  • UlaCache decouples inference-engine KV references from physical placement, keeping logical addresses stable as KV moves between GPU and CPU slots.The address space covers a rank’s pools in DP or aggregates GPU-group pools in TP.Source: §3 · p. 4
  • After sparse selection, UlaCache reuses TP local-buffer hits and resolves remaining addresses to GPU pools; selected CPU data is first moved to its storage GPU pool.The selected KV is then read from that pool or fetched into a local buffer for attention.Source: §3 · p. 4
  • With CPU storage enabled, PB-LRU updates recency in parallel and selects replacement slots; mappings are updated after the planned transfers complete.It manages a GPU KV pool shared across requests.Source: §3 · p. 4

4 UNIFIED KV STORAGE AND ACCESS

UlaCache provides stable logical KV addressing across DP and TP storage, with common allocation and sparse-selection interfaces. TP local buffers reuse selected copies, while distributed index scoring partitions keys across ranks.

4 UNIFIED KV STORAGE AND ACCESS

  • Stable logical addresses resolve to current physical locations in both DP rank-local pools and TP distributed pools.In TP, the ranks’ GPU pools and optional CPU pools form a distributed address space.Source: §4 · p. 4

4.1 Unified Logical Address Space

  • In TP, GPU pools store distinct history portions, and cached copies in local buffers do not add capacity for unique retained history.The address mapping changes on migration while preserving logical addresses.Source: §4.1 · p. 5

4.2 KV Allocation and Access

  • The engine allocates logical slots for prefill and decoding; sparse selections resolve to physical slots, with selected CPU data promoted to a GPU pool before attention.TP computing ranks reuse local-buffer hits and fetch missing KV from local or peer GPU pools.Source: §4.2 · p. 5

4.3 Local GPU Buffer

  • TP local GPU buffers retain selected KV copies across decoding steps, so overlapping selections can reduce repeated transfers; only buffer misses fetch from global pools.For layers sharing selections, UlaCache reuses lookup and allocation plans and prefetches data on a separate stream.Source: §4.3 · pp. 5–6

4.4 Distributed Indexer

  • TP ranks score their local Index keys and all-gather scores for TopK selection, reducing key replication and redundant scoring but adding communication and synchronization overhead.DP scores each rank’s local-request keys without cross-rank score exchange.Source: §4.4 · p. 6

5 CPU MEMORY EXPANSION AND PB-LRU

UlaCache uses a shared GPU pool and optional CPU storage, with PB-LRU selecting KV to retain or replace. Transfers complete before address mappings are updated, while logical KV addresses remain stable.

5 CPU MEMORY EXPANSION AND PB-LRU

  • PB-LRU keeps recently accessed KV in a GPU pool shared across requests and selects GPU slots for incoming CPU data.It prioritizes free slots, then replacement candidates from the cold bucket followed by recent buckets from oldest to newest; the current bucket is protected.Source: §5 · p. 6, §5.1 · p. 7

5.1 Parallel Bucketed LRU

  • PB-LRU groups GPU slots by recency bucket, enabling parallel address lookup, hit detection, and recency updates.Repeated references are deduplicated, and hierarchical summary bitmaps help locate replacement candidates.Source: §5.1 · pp. 6–7

5.2 KV Exchange and Mapping Updates

  • For CPU-to-GPU exchanges, UlaCache transfers KV before updating mappings, preserving logical addresses throughout the exchange.When a destination GPU slot is occupied, its outgoing KV can reuse the incoming data’s CPU source slot.Source: §5.2 · p. 7

6 EVALUATION

The evaluation compares UlaCache with SGLang and HiSparse on H200 and B300 systems across DP and TP attention. It measures latency, throughput, KV capacity, and scheduler behavior under long-context workloads.

6.1 Experimental Setup

  • The evaluation uses GLM-5.3 with 64K–128K-token Multi-LexSum inputs, matched GPU allocations, and DP or TP attention with and without speculative decoding.H200 uses 256 requests; B300 extends the frozen request order to each configuration’s admitted concurrency, up to 578 requests.Source: §6.1 · p. 7

6.2 Latency under Low Concurrency

  • At batch size 1, UlaCache is faster than HiSparse and slower than SGLang in all eight configurations.At these loads, UlaCache’s shared GPU pool can retain active-request KV, reducing CPU-history fetches.Source: §6.2 · pp. 7–8, Figure 6 · p. 8

6.3 Throughput Scaling

  • With speculative decoding enabled, UlaCache achieves peak throughput speedups over HiSparse of 1.16× (DP) and 1.70× (TP) on 8×H200, and 1.73× (DP) and 2.51× (TP) on 8×B300.Source: §6.3 · p. 8

6.4 KV Allocation and Capacity

  • Under matched memory budgets, UlaCache stores request histories across GPU and CPU memory in DP and distributes history across GPUs in TP, supporting higher admitted concurrency.Figure 8 compares effective KV capacity with admitted concurrency; its capacity bars exclude replicas and buffers.Source: §6.4 · p. 9, Figure 8 · p. 9

6.5 Scheduler Ablation

  • PB-LRU and timestamp-based naive LRU differ by less than 0.10 percentage points in GPU hit rate on paired replayed traces.UlaCache’s shared GPU pool also lets active requests use capacity outside fixed per-request buffer quotas.Source: §6.5 · p. 9, Figure 10 · p. 9

7 RELATED WORK

Related work addresses KV addressing, reuse, distributed storage, and sparse-attention serving through different mechanisms. UlaCache focuses on stable logical references and managing sparse KV placement and access across GPU and optional CPU storage.

KV addressing and reuse

  • PagedAttention maps logical KV blocks to physical GPU blocks, while vAttention preserves contiguous virtual addresses; UlaCache preserves logical references as sparse-attention history migrates across GPU and CPU pools.SGLang reuses prefixes, and Mooncake extends reuse through distributed storage.Source: §7 · pp. 9–10

Hierarchical caching and decode capacity

  • HiCache and LMCache restore reusable prefixes into GPU allocation, whereas UlaCache pools distinct GPU and CPU history slots for concurrently decoding requests.LoongServe pools KV for elastic sequence parallelism, and Helix shards KV and attention computation across GPUs; UlaCache’s TP mode distributes history and fetches selected KV into local buffers.Source: §7 · p. 10

Hierarchical sparse-attention serving

  • Sparse-attention systems vary in cache management and history representation; UlaCache integrates PB-LRU replacement with migration and mapping updates while retaining historical KV without semantic compression.HiSparse uses fixed per-request GPU caches, Spin provides GPU bucketed LRU, and SeKV uses learned routing and reconstructs selected spans from CPU low-rank factors.Source: §7 · p. 10

8 CONCLUSION

UlaCache provides stable logical KV addressing across GPU and optional CPU storage, with PB-LRU managing replacement and migration. With speculative decoding and matched CPU and GPU budgets, it achieves higher peak decoding throughput than the state-of-the-art baseline.

8 CONCLUSION

  • 1.16× (DP) and 1.70× (TP) on 8×H200, and 1.73× (DP) and 2.51× (TP) on 8×B300: peak decoding throughput speedups over the state-of-the-art baseline with speculative decoding.The comparison uses matched CPU and GPU memory budgets.Source: §8 · p. 10

Related papers

Loading 2610.29820v1…