TokenDance: Scaling Multi-Agent LLM Serving via Collective KV Cache Sharing

1 Introduction

• On an 80 GB A100, multi-agent sessions used 41.5 GiB of KV Cache (99.3% of the pool), versus 24.8 GiB (59.2%) for 250 independent requests.Multi-agent sessions reached a P99 latency of 136 s, while independent requests rose gradually to 125 s.Source: §1 · p. 1, Figure 2 · p. 2
• Private histories and reordered shared output blocks place identical content at different prompt offsets, so prefix caching misses overlap after histories diverge.Position-independent caching can reuse those blocks but repeats the reuse pass for each agent.Source: §1 · p. 2
• After reuse, pairwise KV Cache block similarity in an 8-agent GenerativeAgents round ranges from 91% to 97%, leaving most cached data duplicated.Only privately recomputed positions differ, so storing a full cache per agent wastes memory.Source: §1 · p. 2, Figure 3 · p. 2
• TokenDance amortizes shared-block reuse across the round and stores only inter-agent cache differences, making storage grow with the differences rather than agent count.The system targets both the repeated reuse computation and the redundant cache copies.Source: §1 · pp. 2–3
• Up to 2.7× more concurrent agents under the same latency target, with 2.3× lower end-to-end latency and 94% less KV Cache storage than vLLM with prefix caching.TokenDance also achieves a 1.9× prefill speedup over CacheBlend.Source: §1 · p. 3

2.1 The All-Gather Pattern

• Each agent’s next-round prompt combines its private history with the same shared output blocks, which can appear at different absolute positions across requests.The scheduler determines the layout of shared output blocks for each agent.Source: §2.1 · p. 3

2.2 KV Cache Reuse in LLM Serving

• Prefix caching requires an exact shared prefix, while position-independent caching can reuse blocks at arbitrary offsets by rotating cached Keys and selectively recomputing important positions.PIC adds rotation and recomputation work, with a minor accuracy trade-off at positions reused without recomputation.Source: §2.2 · p. 3

2.3 Limitations of Existing Serving Systems

• Existing schedulers manage request timing and cache-centric engines reuse per request, but neither shares reuse work or dense cache storage across an All-Gather round.Figure 4 contrasts repeated per-request processing with TokenDance’s collective alternative.Source: §2.3 · pp. 3–4

• TokenDance performs common operations once per All-Gather round and handles only per-agent differences individually.This round-level design targets both redundant reuse computation and redundant KV Cache storage.Source: §3 · p. 4
• The round-aware prompt interface preserves block boundaries so shared content remains identifiable across prompts.Collective reuse then shares reuse work across compatible requests, while diff-aware storage and fused restore represent and apply cache differences.Source: §3 · p. 4, Figure 5 · p. 4
• Diff-aware storage encodes sibling caches as sparse differences against a shared Master copy.Fused restore applies the differences during GPU transfer rather than requiring a separate reconstruction step.Source: §3 · p. 4, Figure 5 · p. 4

4 TokenDance Design

• The design addresses a mismatch in which serving systems flatten round-based prompts and treat requests independently, obscuring shared blocks and retaining dense cache copies.These inefficiencies inflate per-agent KV Cache cost, directly capping concurrent agents.Source: §4 · p. 4

4.1 Round-Aware Prompt Interface

• Segment-based hashing indexes shared updates by content segment, allowing the runtime to identify them even when private histories differ in length.The interface inserts reserved separators between logical prompt blocks; diff-aware storage then represents sibling caches against a Master and applies their differences during restore.Source: §4.1 · p. 5

4.2 Collective KV Cache Reuse

• For compatible requests, the KV Collector shares RoPE rotation and key-difference analysis across the group, while refreshing each request’s differing positions.This amortizes reuse-analysis work across agents; compatible groups require the same active prompt length and cached span, plus non-overlapping slot mappings.Source: §4.2 · pp. 5–6

4.3 Diff-Aware Storage

• Diff-Aware Storage keeps one dense Master cache and stores each Mirror as a block-sparse difference, with Mirrors occupying 10–20% of a full cache.The reuse plan helps identify the Master and differing positions; the layout’s strength depends on the shared-to-private prompt balance, and diverging shared-output subsets weaken its fit.Source: §4.3 · p. 6, §4.2 · p. 6

4.4 Fused Diff Restore

• Fused restore applies sparse corrections during the existing layerwise transfer into paged GPU memory, avoiding separate dense Mirror materialization.Additional per-layer correction work is proportional to differing blocks, typically 10–20% of the total; the prototype fuses before attention, not inside the attention tile loader.Source: §4.4 · p. 7, Figure 9 · p. 7

• The implementation adds approximately 3K lines of Python and 500 lines of CUDA/C++ across four system components.Those components are round-aware segment indexing, collective KV Cache reuse, diff-aware storage, and fused sparse restore.Source: §5 · p. 7
• The runtime indexes prompt segments at separator boundaries and dispatches request groups to the collective path from the vLLM V1 adapter.The KV Collector creates compute and retrieval generators per request and drives them in lockstep across layers.Source: §5 · p. 7
• The diff-aware backend serializes Mirror chunks as block-sparse K/V differences and returns lightweight mirror objects on read.The GPU connector merges differences during layerwise transfer, before RoPE recovery and paged-memory writeback; it falls back to dense restore when sparse metadata is not well aligned.Source: §5 · p. 8

6.1 Setup and Metrics

• On an A100 80 GB, two Qwen models and two workloads are compared with vLLM prefix caching and two CacheBlend paths using 1500 ms agent-capacity metrics.The capacity views measure maximum supported agents below a fixed latency target and maximum agents at a given QPS before exceeding it.Source: §6.1 · p. 8

6.2 Main Result: Scaling the Number of Active Agents

• At QPS=16, TokenDance supports 8 vs. CacheBlend’s 4 and vLLM’s 2 agents on GenerativeAgents/Qwen2.5-7B; on AgentSociety/Qwen2.5-14B, it supports 2 where baselines barely sustain 1.TokenDance also keeps all 10 agents below the SLO on GenerativeAgents with both models, while baselines cross the SLO at lower agent counts.Source: §6.2 · p. 8, Figure 10 · p. 9

6.3 Why Scale Improves: Collective Reuse Compute

• Collective reuse amortizes RoPE and important-position selection across the round, making reuse-analysis overhead sublinear in agent count rather than linear.The paper links this sublinear scaling to the lower latency curve and greater agent capacity under the SLO.Source: §6.3 · p. 9
• 2.57× peak collective-reuse speedup occurs at 10 agents and QPS=1; reuse stays above 1.0× across the QPS range.At QPS=16, collective reuse still provides 1.3–1.5× speedup; beyond 10 agents, scheduling overhead partially offsets amortization gains.Source: §6.3 · p. 9, Figure 11 · p. 10

6.4 Why Scale Improves: KV Cache Footprint and Storage Redundancy

• 11.2× compression for Qwen2.5-7B and 17.5× for Qwen2.5-14B comes from encoding Mirrors as diffs against a Master.For 10 agents, this layout reduces KV Cache memory 5.6× on 7B and 6.7× on 14B compared with 10 full caches.Source: §6.4 · p. 10, Figure 12 · p. 10

6.5 End-to-End Retrieval Cost

• 1.3×–2.6× fused-retrieval speedup over dense restore preserves the storage gains during online serving.Fused diff retrieval applies sparse corrections during layerwise GPU transfer without materializing a separate dense copy.Source: §6.5 · pp. 10–11, Figure 13 · p. 11

6.6 Accuracy Influence

• Across eight scenarios, three match exactly and five differ by 3.3%–11.9% because of CacheBlend’s PIC perturbations, not TokenDance.The evaluation attributes no additional accuracy degradation to TokenDance beyond that of the underlying PIC method.Source: Figure 14 · p. 11, §6.6 · p. 11

Request-Centric KV Cache Reuse

• Existing serving and reuse methods optimize individual requests, while TokenDance uses the agent round as the reuse unit and compresses the resulting sibling caches.Request-centric methods include prefix matching and arbitrary-position reuse, but still analyze one request at a time.Source: §7 · p. 12

KV Cache Compression and Movement

• Prior compression, eviction, and quantization methods shrink individual caches; TokenDance targets cross-cache redundancy, and per-cache compression can be applied on top.Its Master-Mirror layout and fused diff path are designed around similarity among sibling caches.Source: §7 · p. 12

Attention Kernels and Sparse Backends

• The fused diff kernel aligns sparse diff blocks with attention tiles to use compressed caches without an extra dense reconstruction pass.This design follows the data-movement concerns emphasized by efficient attention and block-sparse backends.Source: §7 · p. 12

Multi-Agent LLM Systems

• Agent-aware systems schedule, prefetch, or reorder execution, while multi-agent frameworks provide round-based applications that TokenDance optimizes at the KV Cache layer.The related work also describes KV sharing across multi-LoRA agents through shared and adapter-specific cache components.Source: §7 · p. 12

8 Conclusion

• TokenDance combines collective KV Cache reuse, Master-Mirror storage, and fused diff retrieval for multi-agent serving.The design responds to request-level reuse inefficiency and the compressibility of caches after round-level reuse.Source: §8 · p. 12
• On representative workloads, TokenDance reduces end-to-end latency by up to 2.3× and KV Cache storage by 94% versus vLLM with prefix caching.These are the reported comparisons for multi-agent workloads.Source: §8 · p. 12
• The paper argues that communication structure should be a first-class concept in LLM serving, with All-Gather as a starting point for finding further opportunities.It suggests other recurring communication patterns may also expose opportunities as agent systems diversify.Source: §8 · p. 12