CarryKV: Logarithmic Branch Routing for Sparse Attention with Additive States on a Carry Forest

Efficient hierarchical sparse attention requires identifying useful regions without scanning the full history. We introduce CarryKV, a training-free retriever with compact, mergeable branch summaries. Each branch partitions post-RoPE keys into cells storing counts and key sums; weighted log-sum-exp over cell means estimates attention mass. States merge additively in a persistent hierarchy, and final attention uses original K/V selected at the leaves. We cast HiP's implicit interval pruning and CarryKV's persistent hierarchy in a common bounded-refinement framework, exposing how branch information determines pruning quality. Multi-cell summaries weakly improve the one-sided mass estimate over a single mean, and lower residuals strengthen a same-frontier retained-mass guarantee. The remaining residual has a reverse-KL interpretation; a merge decomposition separates inherited residual from new readout error. Controlled branch experiments measure the resulting mass estimates and pruning decisions across scales. On Qwen3-8B at native 32K, CarryKV improves RULER by 13.37 points over HiP and 6.80 over InfiniteHiP. On Qwen3-1.7B, it outperforms InfiniteHiP on RULER and PG19 from 4K to 128K. At fixed budgets, routing requires $O(\log N)$ work per query block and sparse-prefill retrieval requires $O(N\log N)$ work over a length-$N$ context.