CommunityKV: Efficient Long-Context Decoding via Graph Partitioning

arXiv:2610.00418v1 Announce Type: new 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.25imes the end-to-end generation throughput of dense attention, while query-group graph aggregation yields up to 1.71imes with comparable accuracy.

Related

• ThinKV: Thought-Adaptive KV Cache Compression for Efficient Reasoning Models
• Grouped Value Attention: Efficient KV Caching via On-Demand Key Reconstruction
• Physically Partitioned KVCache Format for CPU--GPU Load Balancing in MoE Inference

Source: arXiv cs.LG | 2026-10-02