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

• URL: http://arxiv.org/abs/2609.07237v1
• Date: Mon, 07 Sep 2026 08:56:47 GMT
• Title: CEDAR: Error-Bounded Residual Routing for Efficient Long-Context Attention
• Abstract summary: Post-hoc sparse attention accelerates long-context prefill by routing each query to a small set of token-level interactions.<n>We introduce Coarse-to-fine Error-aware Dynamic Attention (CEDAR)<n>CEDAR is a coarse-to-fine method that keeps the language model frozen while preserving global coverage.
• Score: 19.273437346867595
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• RouteSparse: Input-Conditional Pattern Routing for Budgeted Long-Context Prefilling [9.844467613008392]
  We introduce RouteSparse, which routes each head and prompt segment among a small library of GPU-efficient sparse patterns.<n>A low-cost probe estimates pattern utility and uncertainty; a latency-aware router then selects a pattern and budget, while uncertain cases fall back to a denser mask.<n>On Llama 3.1-8B-Instruct with 128K-token prompts, RouteSparse achieves $6.5times$ dense prefill speed with a 0.2-point RULER drop relative to dense attention.
  arXiv  Detail & Related papers  (2026-08-29T05:23:41Z)
• Recall Before You Rank: Similarity-Guided Top-$K$ Reuse for Efficient Long-Context Attention [4.6833133124119275]
  ReTopK is a training-free method that accelerates dynamic Top-$K$ attention by reusing historical retrieval decisions.<n>At 128K with $K=512$, ReTopK incurs only a 0.50% perplexity increase over Exact Top-$K$ while accelerating attention computation by $3.07times$.
  arXiv  Detail & Related papers  (2026-07-30T05:25:23Z)
• Surprise Forcing: What to Remember, When to Skip in Long Video Generation [65.0022589149937]
  Streaming autoregressive diffusion makes minute-scale video synthesis practical, but its bounded context and fixed denoising schedule allocate resources uniformly.<n>We introduce Surprise Forcing, a training-free framework that treats both limitations as online resource-allocation problems.<n> Experiments on VBench, VBench-Long, and VBench-2.0 show that the proposed allocation strategy improves long-horizon consistency and visual quality while retaining real-time streaming throughput.
  arXiv  Detail & Related papers  (2026-07-20T18:37:58Z)
• TriRoute: Unified Learned Routing for Joint Adaptive Attention, Experts, and KV-Cache Allocation [0.0]
  TriRoute is a single lightweight controller shared across all three axes.<n>It trains end-to-end via a heterogeneous relaxation.<n>It allocates full attention and high-precision cache to sentence-initial positions, rare subwords, and named entities.
  arXiv  Detail & Related papers  (2026-07-07T00:12:46Z)
• You Only Index Once: Cross-Layer Sparse Attention with Shared Routing [61.29627714699688]
  Cross-layer sparse attention (A) is built on top of KV-sharing architectures such as YOCO.<n>A single indexer computes token-level top-k selection once and reuses the resulting index across layers.<n>Results show CLSA is both accurate and efficient, achieving up to 7.6x decoding speedup and 17.1x overall throughput improvement at 128K context.
  arXiv  Detail & Related papers  (2026-06-04T17:54:04Z)
• Full Attention Strikes Back: Transferring Full Attention into Sparse within Hundred Training Steps [12.944531570933854]
  Long-context inference in large language models is bottlenecked by the quadratic cost of full attention.<n>We show that full-attention LLMs are already intrinsically sparse and can be transformed into highly sparse models with only minimal adaptation.<n>By exploiting the model's intrinsic sparsity, RTPurbo achieves sparsification with only a few hundred training steps.
  arXiv  Detail & Related papers  (2026-05-16T10:51:58Z)
• Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
  We study episodic RL from emphmulti-source imperfect preferences through a cumulative imperfection budget.<n>We propose a unified algorithm with regret $tildeO(sqrtK/M+)$, which exhibits a best-of-both-regimes behavior.
  arXiv  Detail & Related papers  (2026-03-20T19:34:53Z)
• Scaling Attention via Feature Sparsity [50.64995497733461]
  Scaling Transformers to ultra-long contexts is bottlenecked by the $O(n2 d)$ cost of self-attention.<n>We propose Sparse Feature Attention, where queries and keys are represented as $k$-sparse codes that preserve high-dimensional expressivity.<n>Across GPT-2 and Qwen3 pretraining, SFA matches dense baselines while improving speed by up to $2.5times$ and reducing FLOPs and KV-cache by nearly 50%.
  arXiv  Detail & Related papers  (2026-03-17T08:41:50Z)
• SVG-EAR: Parameter-Free Linear Compensation for Sparse Video Generation via Error-aware Routing [77.91660464664615]
  Diffusion Transformers (DiTs) have become a leading backbone for video generation, yet their quadratic attention cost remains a major bottleneck.<n>In this paper, we show that the missing contributions can be recovered without training.<n>We introduce SVG-EAR, a parameter-free linear compensation branch that uses the centroid to approximate skipped blocks and recover their contributions.
  arXiv  Detail & Related papers  (2026-03-09T22:15:31Z)
• RRAttention: Dynamic Block Sparse Attention via Per-Head Round-Robin Shifts for Long-Context Inference [13.524332723947703]
  We present RRAttention, a novel dynamic sparse attention method.<n>It simultaneously achieves all desirable properties through a head underlineround-underlinerobin (RR) sampling strategy.<n>Our method reduces complexity from $O(L2)$ to $O(L2/S2)$ and employs adaptive Top-$$ selection for optimal sparsity.
  arXiv  Detail & Related papers  (2026-02-05T16:37:41Z)
• SkipKV: Selective Skipping of KV Generation and Storage for Efficient Inference with Large Reasoning Models [25.509962883211]
  Large reasoning models (LRMs) often cost significant key-value (KV) cache overhead, due to their linear growth with the chain-of-thought (CoT) reasoning process.<n>We present textbfSkipKV, a KV compression method for selective textiteviction and textitgeneration operating at a coarse-grained sentence-level sequence removal.
  arXiv  Detail & Related papers  (2025-12-08T19:32:06Z)
• R-Stitch: Dynamic Trajectory Stitching for Efficient Reasoning [80.104336426172]
  Chain-of-thought (CoT) enhances problem-solving ability of large language models.<n>CoT incurs substantial inference cost due to long autoregressive trajectories.<n>We introduce R-Stitch, a training-free hybrid decoding framework.
  arXiv  Detail & Related papers  (2025-07-23T08:14:36Z)
• Sparsity Forcing: Reinforcing Token Sparsity of MLLMs [40.93786579652003]
  We explicitly reinforce token sparsity in well-posed multimodal large language models (MLLMs) through a simple RL-based post-training framework named textitSparsity Forcing.<n>Our method explores the efficiency-accuracy trade-off by running multiple rollouts with different token budgets, where both efficiency (token reduction ratio) and performance (answer correctness) are formulated as joint rewards.
  arXiv  Detail & Related papers  (2025-04-23T01:45:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.