CommunityKV is a training-free framework that improves long-context decoding efficiency by reformulating as a community detection problem. It constructs a token graph from attention scores computed during prefill, partitions it into semantically coherent communities using the Leiden algorithm, and retrieves only those communities during generation. A constant-time local update rule assigns new tokens to communities without needing to re-partition globally.
On Qwen3 and Llama-3.1 models across three long-context benchmarks, CommunityKV achieves up to 1.25x end-to-end throughput for per-query-head configurations and up to 1.71x throughput with query-group aggregation, while adding modest memory overhead (17-29% per head, 0.5-8.5% with aggregation) and maintaining comparable accuracy. This approach avoids the need for large-scale training or expensive reclustering during decoding, making it practical for streaming applications.