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

# Input-Conditional Pattern Routing forBudgeted Long-Context Prefilling
Source: [https://arxiv.org/html/2608.29058](https://arxiv.org/html/2608.29058)
## RouteSparse: Input\-Conditional Pattern Routing for Budgeted Long\-Context Prefilling

Yifan JiAffiliation:College of Computer Science, Chongqing UniversityZiyan ZhangAffiliation:School of Information Science and Engineering, Chongqing Jiaotong UniversityKai SongAffiliation:School of Information Science and Engineering, Chongqing Jiaotong UniversityFei LinAffiliation:College of Computer Science, Chongqing University

###### 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 introduceRouteSparse, 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,RouteSparseachieves6\.5×6\.5\\timesdense prefill speed with a 0\.2\-point RULER drop relative to dense attention, compared with7\.3×7\.3\\timesspeed 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\.

## 1Introduction

Long\-context language models enable document question answering, repository understanding, and retrieval over hundreds of thousands of tokens\([Xiong et al\., 2026](https://arxiv.org/html/2608.29058#bib.bib19)\)\. Their context windows, however, expose the quadratic cost of self\-attention during prefilling, the phase that processes a prompt before the first token is generated\. Existing models obtain longer windows through position interpolation and rescaling\([Chen et al\., 2023](https://arxiv.org/html/2608.29058#bib.bib5);[Peng et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib6);[Ding et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib7)\), or distribute exact blockwise attention across devices\([Liu et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib8)\)\. These techniques expand capacity without removing the per\-device systems bottleneck\. Even memory\-efficient exact kernels such as FlashAttention and FlashAttention\-2\([Dao et al\., 2022](https://arxiv.org/html/2608.29058#bib.bib3);[Dao, 2024](https://arxiv.org/html/2608.29058#bib.bib2)\)still compute every causal query–key pair\. Consequently, time to first token can become the dominant user\-visible cost\([Fu, 2024](https://arxiv.org/html/2608.29058#bib.bib4)\)\.

Sparse attention avoids work by evaluating only selected pairs\. Patterns such as local windows, global tokens, and strided connections are effective when incorporated during training\([Child et al\., 2019](https://arxiv.org/html/2608.29058#bib.bib9);[Beltagy et al\., 2020](https://arxiv.org/html/2608.29058#bib.bib10);[Zaheer et al\., 2020](https://arxiv.org/html/2608.29058#bib.bib11)\)\. Applying sparsity after training is harder because important locations depend on the prompt\. Dynamic sparse attention\([Liu et al\., 2022](https://arxiv.org/html/2608.29058#bib.bib13)\)and query\-aware key selection\([Tang et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib15);[Ribar et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib14)\)provide evidence that these locations can be approximated online\. MInference\([Jiang et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib1)\)addresses this problem with three GPU\-efficient pattern families: A\-shape, vertical\-slash, and block\-sparse attention\. It searches offline for one family and one budget per head, then estimates the corresponding indices online\. Across several long\-context models and benchmarks, the authors report substantial prefill speedups with limited task degradation\.

This approach separates a stable*head\-level pattern family*from input\-dependent*indices*\. The separation is economical, but a single offline assignment may be brittle\. A head that is local in narrative text may attend to delimiters in code, repeated keys in synthetic retrieval, or dispersed evidence in multi\-document question answering\. Likewise, a fixed budget cannot respond when a prompt is either easy to sparsify or unusually diffuse\. The original MInference analysis reports broad stability, so we test whether this failure mode appears in practice and whether input\-conditional routing mitigates it\.

We presentRouteSparse, which preserves the kernel\-friendly pattern library while making pattern and budget selection conditional on the current input\.RouteSparseuses a sampled attention probe to score candidate masks, estimates uncertainty from omitted attention mass, and solves a small per\-layer routing problem under a measured latency budget\. High\-uncertainty heads receive a larger budget or dense fallback\. Our contributions are:

- •We propose an input\-conditional router over structured sparse kernels, with selection overhead included in the latency objective;
- •We design a computable certificate that upper\-bounds attention\-output error using omitted probability mass and value\-vector norms; and
- •We perform an empirical evaluation that tests quality, latency, calibration, and robustness under domain and length shift, with preregistered ablations and stress tests\.

## 2Preliminary

### 2\.1Prefill Attention

For one causal attention head, letQ,K,V∈ℝn×dQ,K,V\\in\\mathbb\{R\}^\{n\\times d\}\. Exact attention is

O=A​V,A=softmax⁡\(Q​K⊤/d\+C\),O=AV,\\qquad A=\\operatorname\{softmax\}\\left\(QK^\{\\top\}/\\sqrt\{d\}\+C\\right\),\(1\)whereCCis the causal mask\. Computing Equation[1](https://arxiv.org/html/2608.29058#S2.E1)requiresO⁡\(n2​d\)O\(n^\{2\}d\)arithmetic\. A binary sparse maskMMreplaces unselected logits by−∞\-\\inftyand producesA~​\(M\)\\widetilde\{A\}\(M\)andO~​\(M\)=A~​\(M\)​V\\widetilde\{O\}\(M\)=\\widetilde\{A\}\(M\)V\. A useful mask must reduce realized kernel latency, not merely floating\-point operations, while keepingO~\\widetilde\{O\}close toOO\.

MInference identifies one structured pattern for each head offline and constructs its indices online\([Jiang et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib1)\)\. A\-shape combines initial and local tokens; vertical\-slash selects content\-dependent columns and diagonals; block\-sparse selects coarse query–key blocks\. These structures map to efficient GPU kernels and form the pattern library used here\.RouteSparsechanges the decision granularity, not the underlying observation: structured sparsity is useful only when index estimation plus sparse execution is faster than exact attention\.

### 2\.2Why Route Per Input?

The same head can encounter prompts with different information topology\. Repeated key–value pairs favor vertical columns, locally coherent prose favors a window, and evidence aggregation can require separated blocks\. Offline selection minimizes average loss on calibration prompts:

ph⋆=arg⁡minp∈𝒫​𝔼x∼𝒟cal​\[ℓ⁡\(h,x,p,bh\)\]\.p\_\{h\}^\{\\star\}=\\arg\\min\_\{p\\in\\mathcal\{P\}\}\\mathbb\{E\}\_\{x\\sim\\mathcal\{D\}\_\{\\mathrm\{cal\}\}\}\[\\ell\(h,x,p,b\_\{h\}\)\]\.\(2\)When the best pattern varies withxx, this commits to the best constant decision\. An input\-conditional router can instead approximateph⋆​\(x\)p\_\{h\}^\{\\star\}\(x\), but is worthwhile only if its quality gain exceeds probe and routing overhead\. We test three hypotheses:

#### H1: Conditional routing\.

At matched end\-to\-end prefill latency, input\-conditional routing improves task quality over a fixed per\-head pattern assignment on heterogeneous inputs\.

#### H2: Shift robustness\.

The improvement is larger when evaluation domain or context length differs from the offline calibration set\.

#### H3: Selective fallback\.

An uncertainty\-triggered dense fallback reduces worst\-case quality loss more efficiently than uniformly increasing every head’s sparse budget\.

## 3RouteSparse

### 3\.1Pattern and Budget Library

For each layer and head, the candidate set contains A\-shape, vertical\-slash, block\-sparse, and dense masks\. Each sparse family has a discrete budget gridℬp\\mathcal\{B\}\_\{p\}defined in units that match its kernel: local\-window width and global columns, selected vertical/diagonal lines, or selected blocks\. We profile every\(p,b,n\)\(p,b,n\)tuple on the target hardware and store measured kernel timetker​\(p,b,n\)t\_\{\\mathrm\{ker\}\}\(p,b,n\)\. This avoids treating equal theoretical FLOPs as equal latency\.

Candidate index builders follow the corresponding MInference approximations: recent queries score global columns and diagonals, while pooled queries and keys score coarse blocks\. The A\-shape candidate requires no content\-dependent index construction\. Our implementation reuses the original kernels; the novel component is choosing among them online\.

### 3\.2Shared Attention Probe

Running a separate estimator for every pattern would erase the expected speedup\.RouteSparsetherefore constructs a shared probe\. It selectsrrqueries using a deterministic mixture of recent, uniformly spaced, and boundary\-adjacent positions, and pools keys into blocks of widthgg:

Sh=Qh​\[I\]​poolg​\(Kh\)⊤/d,\|I\|=r≪n\.S\_\{h\}=Q\_\{h\}\[I\]\\,\\operatorname\{pool\}\_\{g\}\(K\_\{h\}\)^\{\\top\}/\\sqrt\{d\},\\qquad\|I\|=r\\ll n\.\(3\)The softmax ofShS\_\{h\}is not used as the final attention distribution\. It is a low\-resolution signal from which each candidate builder extracts its indices\. The probe is shared across all candidates within a head and can be batched across heads\.

For candidate\(p,b\)\(p,b\), letm^h,p,b\\widehat\{m\}\_\{h,p,b\}denote probe mass covered by its coarse mask\. We also compute three inexpensive descriptors: entropy of the probe distribution, concentration in the local band, and agreement between recent and uniformly sampled query groups\. These features expose diffuse or nonstationary attention for which aggressive sparsity is risky\.

### 3\.3Risk Score and Error Certificate

The router estimates candidate risk as

R^h​\(p,b∣x\)=1−m^h,p,b\+α​uh,p,b\+β​eh,p,b,\\widehat\{R\}\_\{h\}\(p,b\\mid x\)=1\-\\widehat\{m\}\_\{h,p,b\}\+\\alpha u\_\{h,p,b\}\+\\beta e\_\{h,p,b\},\(4\)whereuumeasures disagreement among probe subsets andeeis an optional calibrated predictor of output error\. The predictor is a small monotone regressor fitted offline from dense calibration runs; it consumes only the probe descriptors and candidate metadata\. Settingβ=0\\beta=0yields a training\-free router\.

Omitted attention mass gives a simple certificate\. For one exact attention rowaa, let a candidate retain index setSSwith massm=∑j∈Sajm=\\sum\_\{j\\in S\}a\_\{j\}, and leta~\\widetilde\{a\}renormalizeaaonSS\. Ifmaxj⁡∥vj∥2≤Vmax\\max\_\{j\}\\lVert v\_\{j\}\\rVert\_\{2\}\\leq V\_\{\\max\}, then

‖a​V−a~​V‖2≤2​\(1−m\)​Vmax\.\\left\\lVert aV\-\\widetilde\{a\}V\\right\\rVert\_\{2\}\\leq 2\(1\-m\)V\_\{\\max\}\.\(5\)The result follows because∥a−a~∥1=2​\(1−m\)\\lVert a\-\\widetilde\{a\}\\rVert\_\{1\}=2\(1\-m\)\. The probe supplies only an estimate ofmm, so Equation[5](https://arxiv.org/html/2608.29058#S3.E5)is not a formal certificate unless the estimation error is bounded\. We therefore calibrate a one\-sided residual quantileδq\\delta\_\{q\}on held\-out dense runs and usem¯=max⁡\(0,m^−δq\)\\underline\{m\}=\\max\(0,\\widehat\{m\}\-\\delta\_\{q\}\)\. We report coverage of this empirical certificate on every evaluation domain\.

### 3\.4Latency\-Constrained Routing

Letzh,p,b∈\{0,1\}z\_\{h,p,b\}\\in\\\{0,1\\\}indicate one choice per head\. For each layer, the router solves

minz\\displaystyle\\min\_\{z\}\\quad∑h∑p,bzh,p,b​R^h​\(p,b∣x\)\\displaystyle\\sum\_\{h\}\\sum\_\{p,b\}z\_\{h,p,b\}\\widehat\{R\}\_\{h\}\(p,b\\mid x\)\(6\)s\.t\.∑p,bzh,p,b=1∀h,\\displaystyle\\sum\_\{p,b\}z\_\{h,p,b\}=1\\quad\\forall h,\(7\)tprobe\+∑h∑p,bzh,p,b​tker​\(p,b,n\)≤Tℓ\.\\displaystyle t\_\{\\mathrm\{probe\}\}\+\\sum\_\{h\}\\sum\_\{p,b\}z\_\{h,p,b\}t\_\{\\mathrm\{ker\}\}\(p,b,n\)\\leq T\_\{\\ell\}\.\(8\)Because choices and budgets are discrete, a multiple\-choice knapsack solver would be exact but unnecessarily costly online\. We begin with the lowest\-risk dense choices and greedily apply the risk\-per\-microsecond substitution that meets the layer budget\. The number of candidates is small and routing runs on the CPU concurrently with projection kernels or as a fused GPU reduction\.

If the lower confidence massm¯\\underline\{m\}falls below thresholdτ\\tau, the router first expands the budget, then switches to dense attention if no sparse candidate satisfies the threshold\. To reduce kernel\-launch fragmentation, heads with the same selected pattern and budget are grouped before execution\. The complete procedure is summarized below\.

Table 1:RouteSparseinference procedure\. Probe, index construction, routing, and regrouping time are included in end\-to\-end latency\.
### 3\.5Offline Calibration

Calibration has two roles\. First, hardware profiling records median and tail latency for all candidate kernels at each context\-length bucket\. Second, dense attention on a modest prompt set provides true retained mass and output error for calibratingδq\\delta\_\{q\}and, when used,eh,p,be\_\{h,p,b\}\. Calibration prompts are disjoint from evaluation prompts\. To test generalization rather than memorization, we use one in\-domain calibration split and two held\-out domains\. No model weight is changed\.

## 4Evaluation

### 4\.1Experiment Setup

Our primary experiments use Llama 3\.1\-8B\-Instruct in bfloat16 with a 128K\-token context window on a single A100 80GB GPU\. The protocol is designed to extend to additional publicly available decoder\-only models with native or extended context windows of at least 128K tokens and to multiple GPU generations\. RULER\([Hsieh et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib23)\)measures retrieval, tracking, and aggregation across controlled lengths\. InfiniteBench\([Zhang et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib26)\)adds long\-document question answering, summarization, code, and synthetic retrieval\. PG\-19\([Rae et al\., 2020](https://arxiv.org/html/2608.29058#bib.bib27)\)measures long\-form language modeling\. Reporting task categories separately is important because an average can hide a retrieval collapse\. LongBench\([Bai et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib24)\)and L\-Eval\([An et al\., 2023](https://arxiv.org/html/2608.29058#bib.bib25)\)are included as secondary suites to broaden language, domain, task, and evaluation\-metric coverage\.

Baselines are dense FlashAttention\-2; MInference with its fixed per\-head assignment; a uniformly enlarged MInference budget matched toRouteSparse’s latency; and a global router that chooses one pattern per layer\. Static local\-plus\-global attention provides a structural reference, although it is not expected to be a drop\-in quality\-preserving baseline\. All methods use identical model weights, precision, decoding settings, and prompt tokenization\.

### 4\.2Metrics

The primary systems metric is end\-to\-end prefill latency, measured from resident token IDs to the first\-token logits after warm\-up\. We report median, 95th percentile, peak allocated memory, index\-building time, routing time, and kernel time at 32K, 64K, 128K, and the largest supported length\. The primary quality metric is each benchmark’s official score; PG\-19 uses perplexity\. We also report attention\-output relative error on a dense\-audited subset:

Erel=∥O−O~∥F∥O∥F\+ϵ\.E\_\{\\mathrm\{rel\}\}=\\frac\{\\lVert O\-\\widetilde\{O\}\\rVert\_\{F\}\}\{\\lVert O\\rVert\_\{F\}\+\\epsilon\}\.\(9\)
Comparisons use paired prompts and at least three timing repetitions after warm\-up\. Quality differences receive paired bootstrap 95% confidence intervals\. Latency–quality Pareto curves varyTℓT\_\{\\ell\}andτ\\taurather than reporting a single operating point\. A method dominates only when it is no slower and no worse in quality within uncertainty\.

### 4\.3Ablations

We consider the following ablations: No input routing, No uncertainty, No dense fallback, One fixed budget, Recent queries only, Predicted FLOPs, Per\-head launches\. H1 is rejected if conditional routing does not improve quality at matched latency on the mixed test set\. H2 is rejected if the relative gain does not increase under either domain or length shift\. H3 is rejected if uniform budget expansion matches or beats selective fallback in both mean quality and worst\-decile prompt loss\.

Additional stress tests concatenate unrelated domains, place evidence near chunk boundaries, vary repeated\-token frequency, and transfer calibration from prose to code\. For every split, we report router choices by layer and head, fallback rate, certificate coverage, and the largest observed quality drop\. A high fallback rate can preserve quality while eliminating speedup; it is therefore a failure mode, not a successful safety result\.

## 5Results & Analysis

### 5\.1Main Results

Table[2](https://arxiv.org/html/2608.29058#S5.T2)reports end\-to\-end 128K\-token prefill performance for Llama 3\.1\-8B\-Instruct in bfloat16 on a single A100 80GB\. Latency includes probe, index construction, routing, regrouping, and attention kernels\.

Table 2:128K\-token prefill performance\. Bold marks the strongest sparse result in each column; dense attention remains the quality reference\.Fixed MInference remains the fastest sparse method, butRouteSparserecovers 1\.4 RULER points at 0\.7 seconds of additional latency\. Uniformly increasing the fixed budget recovers only 0\.9 points while becoming slower than conditional routing\. These results support H1: routing improves quality at a matched or lower latency than indiscriminate budget expansion\. Fixed MInference remains preferable for latency\-only workloads\.

Figure[1](https://arxiv.org/html/2608.29058#S5.F1)expands the single operating point into measured latency–quality curves\. Conditional routing is most useful in the middle regime: at very aggressive budgets both methods omit too much mass, while near\-dense budgets leave little quality to recover\. Confidence intervals and routing overhead are included in the plotted points\.

Figure 1:RULER–latency Pareto frontier at 128K tokens\.
### 5\.2Shift and Selective Fallback

Figure[2](https://arxiv.org/html/2608.29058#S5.F2)shows quality loss relative to dense attention under in\-domain evaluation and combined domain\-and\-length shift; lower is better\. Fixed routing loses 1\.6 points in\-domain and 6\.4 points when domain and length shift are combined\. Conditional routing with fallback limits the corresponding losses to 0\.2 and 2\.0 points, supporting H2\.

Figure 2:Quality loss relative to dense attention under distribution shift\.
### 5\.3Ablations

Table[3](https://arxiv.org/html/2608.29058#S5.T3)reports the preregistered ablations\. Removing uncertainty or fallback reduces average latency but increases the worst\-decile prompt loss, illustrating why mean score alone is insufficient\. Replacing hardware profiles with predicted FLOPs preserves quality but costs 0\.8 seconds because the router selects kernel mixtures that are theoretically cheap but poorly utilized\. Per\-head launches are slower still, emphasizing that routing and execution cannot be evaluated independently\.

Table 3:Ablation study at 128K tokens\. Worst\-decileΔ\\Deltais the score change relative to dense attention on the 10% of prompts harmed most\.Selective fallback recovers 0\.6 average points and 2\.8 worst\-decile points over no fallback at a cost of 0\.8 seconds\. Uniform budget expansion in Table[2](https://arxiv.org/html/2608.29058#S5.T2)does not match this tradeoff, supporting H3\. The measured 6\.8% fallback rate preserves most of the speed advantage; a substantially higher rate would erode it\.

## 6Related Work

#### Exact attention and serving systems\.

FlashAttention makes exact attention IO\-aware through tiling\([Dao et al\., 2022](https://arxiv.org/html/2608.29058#bib.bib3)\); FlashAttention\-2 improves work partitioning and parallelism\([Dao, 2024](https://arxiv.org/html/2608.29058#bib.bib2)\)\. Ring Attention distributes blockwise attention and communication across devices\([Liu et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib8)\)\. At the serving layer, PagedAttention and vLLM reduce KV\-cache fragmentation and improve batching\([Kwon et al\., 2023](https://arxiv.org/html/2608.29058#bib.bib16)\)\. These methods are complementary baselines: they improve the execution or memory management of exact attention, whereasRouteSparsereduces the set of query–key pairs computed during prefill\.

#### Structured sparse attention\.

Sparse Transformers, Longformer, and BigBird use local, global, random, or strided connectivity to reduce quadratic attention\([Child et al\., 2019](https://arxiv.org/html/2608.29058#bib.bib9);[Beltagy et al\., 2020](https://arxiv.org/html/2608.29058#bib.bib10);[Zaheer et al\., 2020](https://arxiv.org/html/2608.29058#bib.bib11)\)\. Reformer uses locality\-sensitive hashing to cluster compatible queries and keys\([Kitaev et al\., 2020](https://arxiv.org/html/2608.29058#bib.bib12)\)\. These architectures primarily concern training or model design\. Subsequent dynamic sparse attention systems predict token and head importance online\([Liu et al\., 2022](https://arxiv.org/html/2608.29058#bib.bib13)\)\.RouteSparseinstead targets post\-training prefill acceleration with a small set of deployable kernels\.

#### Dynamic post\-training sparsity\.

SparQ retrieves likely keys from a subset of query dimensions to reduce memory traffic during generation\([Ribar et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib14)\), while QUEST selects pages using query\-aware sparsity\([Tang et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib15)\)\. MInference identifies spatial attention patterns and dynamically constructs their indices during prefilling\([Jiang et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib1)\); InfLLM uses a training\-free memory mechanism for extreme contexts\([Xiao et al\., 2024a](https://arxiv.org/html/2608.29058#bib.bib22)\)\. Recent work on dynamic hierarchical sparse attention further studies adaptive structured sparsity for memory\-constrained long\-context inference\([Xiong et al\.,](https://arxiv.org/html/2608.29058#bib.bib18)\)\.RouteSparsedirectly builds on the MInference pattern library, replacing fixed per\-head family selection with input\-conditional, latency\-constrained routing and explicit fallback\.

#### KV\-cache compression\.

StreamingLLM retains attention sinks and recent tokens for stable streaming\([Xiao et al\., 2024b](https://arxiv.org/html/2608.29058#bib.bib17)\); H2O preserves heavy hitters\([Zhang et al\., 2023](https://arxiv.org/html/2608.29058#bib.bib20)\); and SnapKV selects prompt positions using an observation window\([Li et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib21)\)\. These methods primarily reduce decode\-time KV\-cache memory or bandwidth\. They can be combined with prefill sparsity, but they do not by themselves remove the quadratic prefill attention evaluated here\.

#### Context\-window extension\.

Position interpolation\([Chen et al\., 2023](https://arxiv.org/html/2608.29058#bib.bib5)\), YaRN\([Peng et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib6)\), and LongRoPE\([Ding et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib7)\)extend pretrained models through modifications to positional treatment and targeted fine\-tuning\. Ring Attention instead scales exact context processing across devices\([Liu et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib8)\)\. These approaches determine which lengths a model can represent;RouteSparseconcerns the cost of executing an already long\-context model\.

#### Long\-context evaluation\.

RULER shows that advertised context length need not equal effective context length\([Hsieh et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib23)\), while InfiniteBench evaluates diverse tasks at very long lengths\([Zhang et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib26)\)\. LongBench provides a bilingual multitask suite\([Bai et al\., 2024](https://arxiv.org/html/2608.29058#bib.bib24)\), and L\-Eval studies both long\-document datasets and evaluation metrics\([An et al\., 2023](https://arxiv.org/html/2608.29058#bib.bib25)\)\. These findings motivate category\-level reporting and shift tests\. Our evaluation also measures attention approximation and system latency, because task score alone cannot identify whether routing works for the intended reason\.

## 7Conclusion

RouteSparseshows that the useful spatial structure identified by MInference is better selected per input than fixed once per head\. The method shares a low\-resolution attention probe across candidate patterns, chooses pattern and budget under measured latency constraints, and allocates dense computation to uncertain cases\. On 128K\-token prefilling,RouteSparseachieves quality close to dense attention at6\.5×6\.5\\timesspeed, with larger robustness gains under domain and length shift than fixed routing\. The ablations confirm that hardware profiling, input\-conditional routing, and selective fallback each contribute measurably to the final tradeoff\.

## Limitations

The sampled probe can miss rare but essential query–key interactions, and empirical quantile calibration does not provide a distribution\-free guarantee under arbitrary shift\. Output\-error bounds are local to one attention operation and do not tightly bound final generation quality\. Performance is hardware\- and implementation\-dependent\. Pattern heterogeneity can reduce batching efficiency, and discrete kernel variants increase maintenance cost\. Dense auditing at extreme lengths is expensive, limiting the size of calibration and certificate studies\. Our primary experiments use one model size and one GPU generation; broader scaling studies remain future work\.

## References

- Anet al\.\(2023\)C\. An, S\. Gong, M\. Zhong, X\. Zhao, M\. Li, J\. Zhang, L\. Kong, and X\. QiuL\-Eval: instituting standardized evaluation for long context language models\.arXiv preprint arXiv:2307\.11088\.External Links:[Link](https://arxiv.org/abs/2307.11088)Cited by:[§4\.1](https://arxiv.org/html/2608.29058#S4.SS1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px6.p1.1)\.
- Baiet al\.\(2024\)Y\. Bai, X\. Lv, J\. Zhang, H\. Lyu, J\. Tang, Z\. Huang, Z\. Du, X\. Liu, A\. Zeng, L\. Hou, Y\. Dong, J\. Tang, and J\. LiLongBench: a bilingual, multitask benchmark for long context understanding\.arXiv preprint arXiv:2308\.14508\.External Links:[Link](https://arxiv.org/abs/2308.14508)Cited by:[§4\.1](https://arxiv.org/html/2608.29058#S4.SS1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px6.p1.1)\.
- Beltagyet al\.\(2020\)I\. Beltagy, M\. E\. Peters, and A\. CohanLongformer: the long\-document transformer\.InarXiv preprint arXiv:2004\.05150,External Links:[Link](https://arxiv.org/abs/2004.05150)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p2.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px2.p1.1)\.
- Chenet al\.\(2023\)S\. Chen, S\. Wong, L\. Chen, and Y\. TianExtending context window of large language models via positional interpolation\.arXiv preprint arXiv:2306\.15595\.External Links:[Link](https://arxiv.org/abs/2306.15595)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px5.p1.1)\.
- Childet al\.\(2019\)R\. Child, S\. Gray, A\. Radford, and I\. SutskeverGenerating long sequences with sparse transformers\.arXiv preprint arXiv:1904\.10509\.External Links:[Link](https://arxiv.org/abs/1904.10509)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p2.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px2.p1.1)\.
- Daoet al\.\(2022\)T\. Dao, D\. Y\. Fu, S\. Ermon, A\. Rudra, and C\. RéFlashAttention: fast and memory\-efficient exact attention with IO\-awareness\.InAdvances in Neural Information Processing Systems,External Links:[Link](https://arxiv.org/abs/2205.14135)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px1.p1.1)\.
- Dao \(2024\)T\. DaoFlashAttention\-2: faster attention with better parallelism and work partitioning\.InInternational Conference on Learning Representations,External Links:[Link](https://arxiv.org/abs/2307.08691)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px1.p1.1)\.
- Dinget al\.\(2024\)Y\. Ding, L\. L\. Zhang, C\. Zhang, Y\. Xu, N\. Shang, J\. Xu, F\. Yang, and M\. YangLongRoPE: extending LLM context window beyond 2 million tokens\.InInternational Conference on Machine Learning,External Links:[Link](https://arxiv.org/abs/2402.13753)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px5.p1.1)\.
- Fu \(2024\)Y\. FuChallenges in deploying long\-context transformers: a theoretical peak performance analysis\.arXiv preprint arXiv:2405\.08944\.External Links:[Link](https://arxiv.org/abs/2405.08944)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p1.1)\.
- Hsiehet al\.\(2024\)C\. Hsieh, S\. Sun, S\. Kriman, S\. Acharya, D\. Rekesh, F\. Jia, Y\. Zhang, and B\. GinsburgRULER: what’s the real context size of your long\-context language models?\.arXiv preprint arXiv:2404\.06654\.External Links:[Link](https://arxiv.org/abs/2404.06654)Cited by:[§4\.1](https://arxiv.org/html/2608.29058#S4.SS1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px6.p1.1)\.
- Jianget al\.\(2024\)H\. Jiang, Y\. Li, C\. Zhang, Q\. Wu, X\. Luo, S\. Ahn, Z\. Han, A\. H\. Abdi, D\. Li, C\. Lin, Y\. Yang, and L\. QiuMInference 1\.0: accelerating pre\-filling for long\-context LLMs via dynamic sparse attention\.InAdvances in Neural Information Processing Systems,External Links:[Link](https://arxiv.org/abs/2407.02490)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.29058#S2.SS1.p2.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px3.p1.1)\.
- Kitaevet al\.\(2020\)N\. Kitaev, Ł\. Kaiser, and A\. LevskayaReformer: the efficient transformer\.InInternational Conference on Learning Representations,External Links:[Link](https://arxiv.org/abs/2001.04451)Cited by:[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px2.p1.1)\.
- Kwonet al\.\(2023\)W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. E\. Gonzalez, H\. Zhang, and I\. StoicaEfficient memory management for large language model serving with PagedAttention\.InProceedings of the 29th Symposium on Operating Systems Principles,pp\. 611–626\.External Links:[Link](https://arxiv.org/abs/2309.06180)Cited by:[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px1.p1.1)\.
- Liet al\.\(2024\)Y\. Li, Y\. Huang, B\. Yang, B\. Venkitesh, A\. Locatelli, H\. Ye, T\. Cai, P\. Lewis, and D\. ChenSnapKV: LLM knows what you are looking for before generation\.arXiv preprint arXiv:2404\.14469\.External Links:[Link](https://arxiv.org/abs/2404.14469)Cited by:[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px4.p1.1)\.
- Liuet al\.\(2024\)H\. Liu, M\. Zaharia, and P\. AbbeelRing Attention with blockwise transformers for near\-infinite context\.InInternational Conference on Learning Representations,External Links:[Link](https://arxiv.org/abs/2310.01889)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px5.p1.1)\.
- Liuet al\.\(2022\)L\. Liu, Z\. Qu, Z\. Chen, F\. Tu, Y\. Ding, and Y\. XieDynamic sparse attention for scalable transformer acceleration\.IEEE Transactions on Computers71\(12\),pp\. 3165–3178\.Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p2.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px2.p1.1)\.
- Penget al\.\(2024\)B\. Peng, J\. Quesnelle, H\. Fan, and E\. ShippoleYaRN: efficient context window extension of large language models\.InInternational Conference on Learning Representations,External Links:[Link](https://arxiv.org/abs/2309.00071)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px5.p1.1)\.
- Raeet al\.\(2020\)J\. W\. Rae, A\. Potapenko, S\. M\. Jayakumar, C\. Hillier, and T\. P\. LillicrapCompressive transformers for long\-range sequence modelling\.InInternational Conference on Learning Representations,External Links:[Link](https://arxiv.org/abs/1911.05507)Cited by:[§4\.1](https://arxiv.org/html/2608.29058#S4.SS1.p1.1)\.
- Ribaret al\.\(2024\)L\. Ribar, I\. Chelombiev, L\. Hudlass\-Galley, C\. Blake, C\. Luschi, and D\. OrrSparQ attention: bandwidth\-efficient LLM inference\.InInternational Conference on Machine Learning,External Links:[Link](https://arxiv.org/abs/2312.04985)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p2.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px3.p1.1)\.
- Tanget al\.\(2024\)J\. Tang, Y\. Zhao, K\. Zhu, G\. Xiao, B\. Kasikci, and S\. HanQUEST: query\-aware sparsity for efficient long\-context LLM inference\.InInternational Conference on Machine Learning,External Links:[Link](https://arxiv.org/abs/2406.10774)Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p2.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px3.p1.1)\.
- Xiaoet al\.\(2024a\)C\. Xiao, P\. Zhang, X\. Han, G\. Xiao, Y\. Lin, Z\. Zhang, Z\. Liu, S\. Han, and M\. SunInfLLM: unveiling the intrinsic capacity of LLMs for understanding extremely long sequences with training\-free memory\.arXiv preprint arXiv:2402\.04617\.External Links:[Link](https://arxiv.org/abs/2402.04617)Cited by:[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px3.p1.1)\.
- Xiaoet al\.\(2024b\)G\. Xiao, Y\. Tian, B\. Chen, S\. Han, and M\. LewisEfficient streaming language models with attention sinks\.InInternational Conference on Learning Representations,External Links:[Link](https://arxiv.org/abs/2309.17453)Cited by:[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px4.p1.1)\.
- Xionget al\.\(2026\)S\. Xiong, O\. Gungordu, J\. C\. Kerce, and F\. FekriAdaptive information control for search\-augmented llm reasoning\.arXiv preprint arXiv:2602\.01672\.Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p1.1)\.
- \[24\]S\. Xiong, J\. Zou, F\. Fekri, and Y\. J\. ChoLong\-context modeling with dynamic hierarchical sparse attention for memory\-constrained llm inference\.InForty\-third International Conference on Machine Learning,Cited by:[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px3.p1.1)\.
- Zaheeret al\.\(2020\)M\. Zaheer, G\. Guruganesh, K\. A\. Dubey, J\. Ainslie, C\. Alberti, S\. Ontañón, P\. Pham, A\. Ravula, Q\. Wang, L\. Yang, and A\. AhmedBig Bird: transformers for longer sequences\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2608.29058#S1.p2.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2024\)X\. Zhang, Y\. Chen, S\. Hu, Z\. Xu, J\. Chen, M\. Hao, X\. Han, Z\. Thai, S\. Wang, Z\. Liu, and M\. SunInfiniteBench: extending long context evaluation beyond 100k tokens\.arXiv preprint arXiv:2402\.13718\.External Links:[Link](https://arxiv.org/abs/2402.13718)Cited by:[§4\.1](https://arxiv.org/html/2608.29058#S4.SS1.p1.1),[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px6.p1.1)\.
- Zhanget al\.\(2023\)Z\. Zhang, Y\. Sheng, T\. Zhou, T\. Chen, L\. Zheng, R\. Cai, Z\. Song, Y\. Tian, C\. Ré, C\. Barrett, Z\. Wang, and B\. ChenH2O: heavy\-hitter oracle for efficient generative inference of large language models\.InAdvances in Neural Information Processing Systems,External Links:[Link](https://arxiv.org/abs/2306.14048)Cited by:[§6](https://arxiv.org/html/2608.29058#S6.SS0.SSS0.Px4.p1.1)\.