Skip to content

CommunityKV: Efficient Long-Context Decoding via Graph Partitioning

Sep 2026 · 0 citations · 50 references
Computer Science

TL;DR

CommunityKV, a framework that formulates sparse attention as a community detection problem, is introduced, a framework that formulates sparse attention as a community detection problem and is evaluated on Qwen3 and Llama-3.1 models across three long-context benchmarks.

Abstract

Scaling Transformers to long contexts is constrained by the quadratic cost of self-attention and the linear growth of key-value cache memory transfer. Sparse attention mitigates this by retrieving only relevant tokens, but current approaches either require large-scale training or, within the training-free regime, rely on semantically coarse heuristics or expensive clustering that is difficult to update efficiently during decoding. We introduce CommunityKV, a framework that formulates sparse attention as a community detection problem. CommunityKV constructs a token graph from the $QK^T$ scores already computed during standard prefill, and partitions the graph into communities to enable retrieval of semantically coherent token groups. A local update rule assigns newly generated tokens to communities in constant time, enabling sparse retrieval throughout streaming decoding without global re-partitioning. We evaluate CommunityKV on Qwen3 and Llama-3.1 models across three long-context benchmarks. With one graph per query head, CommunityKV delivers up to $1.25\times$ the end-to-end generation throughput of dense attention, while query-group graph aggregation yields up to $1.71\times$ with comparable accuracy.

View source

Similar papers

Book Open access Nov 2026

Beyond Locality: Multi-scale Structural Tokenization for Unsupervised Community Search

Community Search (CS) aims to retrieve query-dependent cohesive subgraphs from networks, playing a crucial role in modern applications such as computing power networks and biological systems. Given the high cost of labeling, unsupervised CS has emerged as a scalable paradigm. However, existing approaches often suffer f...

Xi Yue, Chuan-Hou Sun, Ying Yin et al. · 0 citations
#natural language process... Preprint Oct 2026

Joint Subspace Sparse Attention for Efficient Long-Context Decoding

Sparse attention reduces the KV-cache traffic that dominates long-context LLM decoding, but practical methods largely operate at coarse granularity. Token-level selection offers finer control, yet presents two challenges: low-dimensional scoring may lose query--key structure needed for accurate ranking, while gathering...

Jiwon Song, Yoon Kim, Jae-Joon Kim · 0 citations

PatchKV: Weight-Space Compensation of KV Cache

Long-context inference with Large Language Models (LLMs) is bottlenecked by the linearly growing memory of the key-value (KV) cache. Existing compression methods reduce the cache through token eviction or approximation, but degrade sharply at aggressive compression budgets. We propose PatchKV, a training-free framework...

Chanryeol Lee, Chanhyuk Lee, Yeonwoo Choi et al. · 1 citation

Block-Sparse Attention with Semantic-Geometric Decoupled Routing

Semantic-Geometric Decoupled Routing is proposed, a training-free block routing framework that shifts semantic aggregation to the pre-RoPE space and reconstructs geometric bias with an offline structural prior and relative block distances and yields an explicit closed-form block routing score without token-level search...

Xin-Wei Long, Wei-Gao Sun, Weibo Gao et al. · 0 citations

Distance-KV: Exploiting Relative Distance for Efficient Long-Context Inference

The memory usage and decoding latency of LLM inference grow rapidly with context length. To reduce these costs, key-value (KV) cache compression methods selectively retain cached states based on token importance or differences in attention patterns across heads. However, we discover that retrieval capability varies sub...

Xian-Peng Shang, Can-Bin Huang, Jiang Li et al. · 0 citations
#machine learning Preprint Oct 2026

OVAL: Output-Aware Local Page Bases for KV Cache Retrieval

Long context inference with large language models becomes increasingly expensive as attention must operate over an ever growing KV cache. Page sparse attention reduces this cost by representing each KV page compactly and retrieving only a subset for each query. Existing retrieval methods are designed to estimate attent...

Ashkan Shahbazi, Chayne Thrash, Soheil Kolouri · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.