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

• URL: http://arxiv.org/abs/2608.29058v1
• Date: Sat, 29 Aug 2026 05:23:41 GMT
• Title: RouteSparse: Input-Conditional Pattern Routing for Budgeted Long-Context Prefilling
• Abstract summary: 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.
• Score: 9.844467613008392
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dynamic sparse attention can reduce the quadratic cost of long-context prefilling without changing model weights. MInference assigns each attention head one pattern offline and estimates that pattern's sparse indices for every prompt. This design is efficient, but it assumes that a head's preferred pattern and sparsity budget remain suitable across inputs. We introduce RouteSparse, which routes each head and prompt segment among a small library of GPU-efficient sparse patterns. 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. We formulate routing as constrained risk minimization, derive an attention-output error certificate from omitted probability mass, and evaluate the method on long-context retrieval, question answering, summarization, and language modeling. On Llama 3.1-8B-Instruct with 128K-token prompts, RouteSparse achieves $6.5\times$ dense prefill speed with a 0.2-point RULER drop relative to dense attention, compared with $7.3\times$ speed and a 1.6-point drop for fixed per-head routing. Ablations confirm that input-conditional routing, hardware profiling, and selective dense fallback each contribute to the quality--latency tradeoff.

Related papers

• CEDAR: Error-Bounded Residual Routing for Efficient Long-Context Attention [19.273437346867595]
  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.
  arXiv  Detail & Related papers  (2026-09-07T08:56:47Z)
• CRISP: Cliff-awaRe Input-adaptive Sparse Prefilling with Structural-Mass-Motivated Routing [90.63350360476294]
  We present CRISP (Cliff-awaRe Input-adaptive Sparse Prefilling), which identifies and addresses two structural challenges in this dynamic routing paradigm.<n>We show that the routing decision can be read directly off the structure of the proxy attention map.<n>We formalize the post-softmax mass cliff and demonstrate theoretically that strictly cumulative coverage thresholds accumulate O(n) background noise at long contexts.
  arXiv  Detail & Related papers  (2026-09-01T22:49:46Z)
• Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees [0.5735035463793009]
  This study shows that Dijkstra's algorithm can remain an exact planning engine under a condition that is much weaker than the causality condition often invoked in the literature.<n>Building on this characterization, an online learner DORA is proposed for robot navigation that calls a shortest path oracle a fixed number of times per episode.
  arXiv  Detail & Related papers  (2026-08-18T12:26:17Z)
• Efficient and Trainable Language Model Test-Time Scaling via Local Branch Routing [65.59464371673623]
  Local Branch Routing (LBR) is a token-level test-time scaling framework.<n>It expands a small local lookahead tree, forwards all sampled branches through the language model, and uses a lightweight router to select the depth-1 subtree to commit.<n>LBR allows each token decision to use evidence beyond the root next-token distribution while avoiding full solution-level search.
  arXiv  Detail & Related papers  (2026-06-24T03:42:44Z)
• BUDDY: BUdget-Driven DYnamic Depth Routing for Adaptive Large Language Model Inference [8.041559188948003]
  Buddy is a budget-driven dynamic depth routing framework for large language models.<n>It supports strict budget control, decode-time rerouting, and multiple budgets within a single trained model.
  arXiv  Detail & Related papers  (2026-06-08T14:06:35Z)
• VSPrefill: Vertical-Slash Sparse Attention with Lightweight Indexing for Long-Context Prefilling [0.0]
  Existing sparse attention methods face a trade-off among context adaptivity, sampling overhead, and fine-tuning costs.<n>We propose VSPrefill, a mechanism requiring lightweight training that uses the vertical-slash structural pattern in attention distributions.<n>VSPrefill preserves 98.35% of the full attention accuracy while delivering a 4.95x average speedup at a context length of 128k.
  arXiv  Detail & Related papers  (2026-03-03T09:24:58Z)
• SparseD: Sparse Attention for Diffusion Language Models [98.05780626106555]
  diffusion language models (DLMs) offer a promising alternative to autoregressive models (ARs)<n>Existing open-source DLMs suffer from high inference latency.<n>We propose SparseD, a novel sparse attention method for DLMs.
  arXiv  Detail & Related papers  (2025-09-28T18:10:10Z)
• 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)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• ETS: Efficient Tree Search for Inference-Time Scaling [61.553681244572914]
  One promising approach for test-time compute scaling is search against a process reward model.<n> diversity of trajectories in the tree search process affects the accuracy of the search, since increasing diversity promotes more exploration.<n>We propose Efficient Tree Search (ETS), which promotes KV sharing by pruning redundant trajectories while maintaining necessary diverse trajectories.
  arXiv  Detail & Related papers  (2025-02-19T09:30:38Z)
• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  We propose Edge Pruning as an effective and scalable solution to automated circuit discovery.<n>Our method finds circuits in GPT-2 that use less than half the number of edges compared to circuits found by previous methods.<n>Thanks to its efficiency, we scale Edge Pruning to CodeLlama-13B, a model over 100x the scale that prior methods operate on.
  arXiv  Detail & Related papers  (2024-06-24T16:40:54Z)
• MoA: Mixture of Sparse Attention for Automatic Large Language Model Compression [22.038650467915176]
  We propose the Mixture of Attention (MoA), which automatically tailors distinct sparse attention configurations to different heads and layers. MoA adapts to varying input sizes, revealing that some attention heads expand their focus to accommodate longer sequences, while other heads consistently concentrate on fixed-length local contexts.
  arXiv  Detail & Related papers  (2024-06-21T06:58:37Z)

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.