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

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.

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