Skip to content

CEDAR: Error-Bounded Residual Routing for Efficient Long-Context Attention

Sep 2026 · 0 citations · 33 references
Computer Science

TL;DR

This work introduces Coarse-to-fine Error-aware Dynamic Attention Routing (CEDAR), a coarse-to-fine method that keeps the language model frozen while preserving global coverage and derives an output-error bound governed by within-chunk key/value dispersion and uses it to allocate a variable refinement budget.

Abstract

Post-hoc sparse attention accelerates long-context prefill by routing each query to a small set of token-level interactions. Hard selection, however, assigns zero probability to every omitted chunk: a routing miss cannot be recovered, and a fixed expansion budget spends the same work on easy and ambiguous queries. We introduce Coarse-to-fine Error-aware Dynamic Attention Routing (CEDAR), a coarse-to-fine method that keeps the language model frozen while preserving global coverage. Each semantic chunk contributes a cheap key--value summary to a residual attention path; chunks with high estimated approximation error are then expanded to exact token attention. Exact and summarized contributions are combined in a single softmax normalization, so refinement replaces, rather than duplicates, coarse evidence. We derive an output-error bound governed by within-chunk key/value dispersion and use it to allocate a variable refinement budget. A controlled clustered-attention study shows that residual summaries reduce reconstruction error by more than 98% relative to hard dropping at equal exact-chunk budgets. Experiments on long-context benchmarks demonstrate that CEDAR recovers most of the quality lost by hard sparse routing while maintaining approximately $3\times$ kernel speedup at 128K context.

View source

Similar papers

#natural language process... Preprint Aug 2026

RouteSparse: Input-Conditional Pattern Routing for Budgeted Long-Context Prefilling

RouteSparse is introduced, which routes each head and prompt segment among a small library of GPU-efficient sparse patterns, andlations confirm that input-conditional routing, hardware profiling, and selective dense fallback each contribute to the quality--latency tradeoff.

Chao Zhang, Yi Ji, Zi-Yan Zhang et al. · 1 citation
#natural language process... Preprint Sep 2026

RouteRelay: Event-Triggered Cross-Layer Route Reuse for Efficient Dynamic Sparse Attention

This work introduces RouteRelay, a router-agnostic method that reuses only route metadata across depth while continuing to compute attention with the current layer's queries, keys, and values and gives a top-$k$ stability condition, a probabilistic bound on missed challengers, and a row-selective GPU execution design.

Bin Li, Si Liu, Chen-Yang Hu et al. · 0 citations
#machine learning Preprint Aug 2026

LoGo: Token-Level Dynamic Local-Global Attention

LoGo, a token-level dynamic local-global attention mechanism that uses attention span as a direct proxy for attention budget allocation, is proposed and results suggest that learned token-level span allocation is an effective and scalable way to improve the long-context performance-compute trade-off.

Yu-Qi Pan, Zheng Li, Bo-Hao Tang et al. · 1 citation
#artificial intelligence Preprint Sep 2026

RBS-Attention: Radius-Bounded Sparse Prefill for Long-Context Large Language Models

RBS-Attention is proposed, a training-free sparse-prefill method with two complementary selection branches that controls the contribution of rescue blocks while preserving regular block-sparse FlashAttention execution and supports radius-adaptive dual-branch selection as an effective approach to long-context prefill.

Chu-Xu Song, Jiu-Qi Wei, Zhen-Can Peng · 0 citations

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
#machine learning Preprint Sep 2026

CommunityKV: Efficient Long-Context Decoding via Graph Partitioning

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.

J. McKenna, Anastasios Alexandridis, Nathan Susanj et al. · 0 citations

Related blog posts

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