acceptodds
Under review as a conference paper at ICLR 2027

HiRouter: Efficient Maximum Inner Product Search for Top- Attention via Hierarchical Routers

Abstract

Attention enables parallel token retrieval but at a quadratic memory and computation cost relative to sequence length, limiting its applicability to long contexts. Sparse top- attention alleviates this issue by reducing computation while maintaining competitive accuracy. However, existing sparse top- methods rely on k-means clustering or locality-sensitive hashing (LSH) to avoid computing the full attention matrix. While GPU-friendly, these approaches employ approximate and often decoupled partition-based routing, which can limit retrieval accuracy. To this end, we propose Hierarchical Router (HiRouter), a sparse top- attention mechanism that that leverages a learned routing function within a hierarchical structure, coupling retrieval with attention by co-training queries, keys, and routing functions end-to-end. To make the learned router effective, we design two routing rules: relevant tokens should co-route with the query, and bucket occupancy should remain balanced to avoid collapse and support uniform GPU workloads. By optimizing two surrogate losses over a learned multi-level hierarchy, HiRouter realizes these rules, partitioning tokens into discrete buckets in linear time and enabling accurate per-sequence retrieval with GPU-friendly bucket layouts. On standard benchmarks, HiRouter matches full-attention performance, while matching/surpassing full-attention accuracy on sequences beyond 4K tokens with up to 2 faster inference than FlashAttention.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Top-K Attention, Efficient Attention

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_U1WUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces HiRouter, a sparse attention mechanism that uses learned hierarchical routing to retrieve candidate keys for attention. It jointly trains query/key representations and routing centroids with entropy-based objectives that encourage confident assignments and balanced bucket occupancy. A hierarchical beam search selects candidate buckets, and custom Triton kernels support efficient execution. Experiments evaluate language modeling, downstream tasks, long-context retrieval, and runtime against full attention and efficient sequence models.

Critical strengths

HiRouter jointly learns hierarchical routing and attention representations, directly addressing retrieval quality and bucket balance within a unified training objective. Its custom Triton implementation also demonstrates practical efficiency gains on long sequences.

Critical weaknesses

Q1. Could the authors report long-context Needle-in-a-Haystack results at the 1B-parameter scale, alongside relevant baselines, at least NSA, under matched training and evaluation settings? This would help establish whether the gains in Table 5 persist at a larger model scale.

Q2. Could the authors provide training scaling curves comparing HiRouter with full attention and, especially, NSA under matched model sizes and training settings?

Q3. Could the authors provide an apples-to-apples comparison of end-to-end training time and cost across different model sizes against full attention and NSA? Please report throughput and GPU-hours under matched hardware, context lengths, batch sizes, and training-token budgets, together with the cost of reaching comparable validation loss.

Questions for authors

See weaknesses.

2 comments

Q1. Long-context NIAH at larger scale

Could the authors report long-context Needle-in-a-Haystack results at the 1B-parameter scale, alongside relevant baselines, at least NSA, under matched training and evaluation settings?

Setting. We ran this evaluation on pre-trained Qwen3-4B and Qwen3-8B as some checkpoints of Tables 14–15 are no longer available and due to some computational limitations during the discussion period. All models share frozen weights and prompts, and we train only the router in HiRouter. Any difference comes from the keys that each query reads. NSA needs pretraining from scratch, so its comparison stays at 410M (Tables 5 and 30).

BackboneMethod8K16K32K64K
4BFull attention99.8 ± 0.499.8 ± 0.499.4 ± 0.699.8 ± 0.4
4BHiRouter99.6 ± 0.499.2 ± 0.696.2 ± 1.391.9 ± 1.9
4BMoBA98.5 ± 0.896.2 ± 1.391.9 ± 1.886.6 ± 2.1
8BFull attention100.0 ± 0.099.5 ± 0.598.8 ± 0.8—
8BHiRouter100.0 ± 0.098.5 ± 0.995.2 ± 1.5—
8BMoBA99.8 ± 0.497.5 ± 1.192.9 ± 1.8—

Accuracy is the mean ± SE over four RULER needle-retrieval tasks with 50 prompts each. In all sparse runs, each query also attends to its local segment, and the final 256 prompt rows use full attention. Qwen3-8B stops at 32K, because its native position range ends at 40,960 tokens.

On both backbones, HiRouter stays within one point of full attention up to 16K. The gap then grows to 3.2 and 3.6 points at 32K, and to 7.9 points at 64K on the 4B backbone. In return, prefill is 1.3 times faster at 32K on the 8B backbone and 2.2 times faster at 64K on the 4B backbone. Moreover, HiRouter scores 4.3 points above MoBA at 32K on the 4B backbone, whereas the 2.3-point difference on the 8B backbone is within noise.

Q2. Training scaling curves

Could the authors provide training scaling curves comparing HiRouter with full attention and, especially, NSA under matched model sizes and training settings?

Matched training setup. We compare at 50M, 125M, and 360M scales on WikiText-103. Only the attention mechanism differs. We report mean ± standard deviation of test perplexity over two seeds.

PPL ↓50M125M360M
Full attention25.61 ± 0.1622.19 ± 0.1419.15 ± 0.02
NSA27.61 ± 0.6622.55 ± 0.3219.34 ± 0.07
HiRouter26.89 ± 0.1222.09 ± 0.0119.14 ± 0.04

HiRouter consistently outperforms NSA and only trails full attention at 50M parameters. We further check 125M training trajectory and see that HiRouter reaches lower perplexity earlier. Its advantage is most pronounced at 33M tokens and gradually narrows as the other methods converge.

PPL ↓33M tokens98M tokens197M tokens328M tokens
Full attention104.535.725.422.4
NSA89.533.724.922.3
HiRouter76.032.724.522.3

Overall, the matched experiments show faster early progress per training token at 125M, followed by comparable final performance to full attention and NSA at the two larger scales. We have added the scaling curves into the revised paper (Figure 5).

Q3. End-to-end training time and cost

Apples-to-apples comparison of end-to-end training time and cost across different model sizes against full attention and NSA; throughput and GPU-hours under matched hardware, context lengths, batch sizes, and training-token budgets, together with the cost of reaching comparable validation loss.

Matched training cost. Complete training-step throughput was measured on one H100 using bf16, 2,048-token sequences, 8 sequences per micro-batch, with gradient accumulation of 32. HiRouter's training path uses fused GPU kernels while preserving the model architecture and objective. GPU-hours for longer runs are projected from the measured throughput.

Throughput (tokens/s)50M125M360MGPU-hours for 10B tokens at 360M
Full attention365K205K90K30.9
NSA270K139K64K43.4
HiRouter267K166K74K37.5

HiRouter matches NSA throughput at 50M and is 19% and 16% faster at 125M and 360M, respectively. Full attention remains fastest at 2K, where sparse routing overhead offsets its attention-computation savings.

Cost to comparable perplexity. The 125M convergence results in Q2 provide a checkpoint-based comparison. Using a perplexity threshold of 25, full attention reaches this at 328M tokens, while both NSA and HiRouter do so at 197M tokens. Combined with measured throughput, these correspond to projected costs of 0.44, 0.39, and 0.33 GPU-hours, respectively.

Thus, HiRouter shows a lower estimated cost of training, despite lower throughput than full attention. The estimates use test-perplexity checkpoints, with the exact crossing times and corresponding validation-loss costs requiring finer-grained training records.

Reviewer_U1WUOpenReview ↗

Official Comment by Reviewer U1WU

Thank you for addressing my concerns. I will maintain my score of 2.

Reviewer_V9FEOpenReview ↗
Rating
1(−1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper presents HiRouter, a heirarchical routing scheme for sparse attention. Rather than scoring each query against all previous keys, the method walks down a learned tree and picks out a reduced set of candidate keys. The router is trained together with the attention reprsentations, using losses that push for confident assignments and for buckets of roughly equal size.

The problem is a relevant one. At each routing step a token is compared only to a few children instead of to all of the leaf centroids. The authors also look at the two practical issues that motivate the design, namely (a) relevant keys getting missed during routing and (b) some buckets ending up overloaded.

There is useful evidence in the experiments. In Table 2 the average on commonsense-reasoining tasks is higher than full attention. Table 6 shows a sizable drop in attention forward time at 32K tokens. Keeping quality aproximately the same while cutting compute is the outcome one wants from this kind of method.

My main concern is whether the routing in Sec 3.2 is causally correct. The full sequence is sorted by routing assignment and the sorted buffer is then split into groups of equal capacity, and the authors state openly that this alters some of the assignments. Those groups are then used as parents at the next level of routing. As far as I can tell this opens a path for future tokens to influence representations of earlier ones. If only later tokens change, an earlier key can be pushed across a physical group boundary, so it sees different centroids or lands in a different candidate set. Masking future positions in the attention scores doesnt by itself gaurantee causality, since the future tokens have already influenced which earlier keys get considered. For an autoregressive LM this is an important question, and it affefcts the the quality/speed tradeoff the paper reports.

I would like authors to describe how logical assignments map onto physical groups. There is a simple test that would settle it: fix a prefix and the total sequence length, vary only the suffix, and check that attention outputs and logits for the prefix stay identical. I'd also ask for a check that parallel prefill and step-by-step decoding give matching outputs, run on the same implementation used for the timing numbers.

My rating is borderline reject until this point is clarified. If the authors give a convincing explanation and show that the implementation is correct, I am willing to reconsider my score.

Some other feedback and relevant baselines/related work to discuss:

  • MoBA: Mixture of Block Attention for Long-Context LLMs, Neurips 2025
  • Figures are small and hard to read (fig 1, 4)
Critical strengths

See above

Critical weaknesses

See above

Questions for authors

See above

3 comments

Main concerns

C1. Causal correctness of routing

(a) Can future tokens change an earlier key’s physical group and subsequent routing?

(b) Does masking future attention scores prevent this dependence?

(c) What does this mean for the reported quality/speed trade-off?

(a) Where the dependence enters and how we remove it. Yes, in the equal-size implementation. There, the kernel sorts the keys and splits them into equal-sized groups, and these groups become the parents at the next level. A change in later tokens can therefore move an earlier key into another group and change its route. In contrast, the variable-size kernel of App. B.2 keeps every key in its router-assigned bucket, so later tokens cannot move it. Cached decoding behaves in the same way. Each new key enters its assigned bucket, and a full bucket only drops its oldest entry.

(b) What the mask and the tests establish. The mask excludes the values of future positions, but it cannot prevent later tokens from changing which past keys a query reads. Our tests confirm this (R2). On the submitted 125M model, replacing the suffix changes 4.0% to 6.5% of the prefix next-token predictions and shifts the prefix NLL by at most 0.013 nats. We then ran your test on the variable-size implementation at two levels. At the attention-layer level, every prefix row reads the same candidates in the same order with and without the suffix change. At the full-model level, with all 36 layers sparse, we replaced the suffix in 24 cases. In every case, all prefix rows keep exactly the same logits, except the rows in the single 64-row query group that spans the prefix/suffix boundary. Moreover, when this boundary coincides with a group boundary, the whole prefix is bit-exact in all 16 cases. When the boundary falls inside a group, the prefix rows of that group differ by at most 0.5 in their logits, and the prefix NLL changes by less than 2×10−52\times10^{-5} nats. This residual comes from bf16 accumulation over a candidate list whose length changes, because the candidates themselves are identical.

(c) Consequences for the reported trade-off. The dependence gave the model no systematic advantage. If the model had exploited future tokens, replacing the suffix would consistently hurt the prefix. Instead, the prefix NLL moves in both directions, between −0.009 and +0.013 nats (R2), which corresponds to at most about 1% in perplexity. The reported quality therefore does not rest on this dependence. Furthermore, the speed benefit does not rely on equal-sized groups. In our frozen Qwen3-4B study, the variable-size implementation prefills 1.4 times faster than full attention at 32K and 2.1 times faster at 64K, with RULER accuracy of 96.2% against 99.4% and 91.9% against 99.8%. In this study, each query also attends to its own 4,096-token segment, and the final 256 prompt rows use full attention.

Requests

Logical-to-physical mapping

I would like authors to describe how logical assignments map onto physical groups.

Equal-size bucket implementation. A logical assignment is the bucket a key chooses; a physical group is where the kernel places it for computation. These can differ.

At level ll, each key chooses a child bucket by argmax (straight-through Gumbel-softmax during training). Within each parent, the kernel sorts keys by their chosen child, then cuts the buffer into CC equal groups of T/ClT/C^l keys. The physical group determines the parent and centroids used at the next level.

For example, suppose eight keys choose two children: three choose A and five choose B. Sorting places the A keys first, but splitting into groups of four puts three A keys and one B key in the first group. That B key then follows the first group’s router, despite having selected B.

When every child has exactly the required number of keys, the assignments match. Otherwise, equal-size cuts can change assignments. Later tokens can change earlier keys’ sorted positions relative to these cuts. Queries read physical leaves using the indices selected by beam search.

Variable-size buckets and cached decoding. The variable-size kernel stores each bucket using its actual count and offset. Keys remain in their chosen buckets, so physical storage does not change their routing parent. Cached decoding likewise preserves bucket identity; FIFO eviction removes entries without moving retained keys between buckets.

Prefix/suffix test

Fix a prefix and the total sequence length, vary only the suffix, and check that attention outputs and logits for the prefix stay identical.

We run this by fixing the prefix and the total length, replacing only the suffix either with random tokens or another text. The unchanged-suffix controls are bit-exact for both.

ImplementationCasesPrefix rows that changeGreedy predictions changedPrefix NLL change (nats)
Equal-size (125M)8All4.0–6.5%−0.009 to +0.013
Variable-size, boundary between two query groups16None00
Variable-size, boundary 12 rows inside a query group8Those 12 rowsAt most one token≤ 1.8 × 10⁻⁵

Equal-size. The prefix depends on the suffix, as you expected. On the full 125M model (one 2,048-token window, prefixes of 1,024 and 1,536 tokens), every prefix row changes.

Variable-size. In contrast, the implementation of our frozen-backbone study leaves the prefix unchanged, except for the rows that share a query group with the suffix. The kernel processes queries in groups of 64 rows. We tested the full Qwen3-4B model with all layers sparse, on sequences of 9,192 and 17,384 tokens. When the prefix/suffix boundary lies between two groups, the whole prefix is bit-exact. When it lies inside a group, only the 12 prefix rows of that group change, and their logits move by at most 0.53.

We further check at the attention-layer level (layers 0, 17 and 35, 18 cases), each of these rows reads the same candidate keys in the same order with and without the suffix change, and its output differs by at most 0.3% of its magnitude. The difference arises because the kernel sums the keys of a group in one shared list in bf16, and the suffix rows change the length of that list.

Prefill vs. step-by-step decoding

A check that parallel prefill and step-by-step decoding give matching outputs.

We ran this check on both implementations, with 20 windows each. We prefill a prefix, decod the next tokens one at a time with the cache, and compare the predictions with a parallel pass over the same sequence. Each implementation runs on the model that uses it: the equal-size kernel on the paper's 125M model, and the variable-size kernel on the frozen Qwen3-4B model, with full attention as the reference.

ImplementationIdentical greedy predictions
Full attention (reference)98.7%
Equal-size96.8%
Variable-size98.9%

Reference. Full attention is causal by definition, yet its two paths agree on only 98.7% of the predictions, because bf16 rounding differs between them. An exact implementation therefore reaches this level in the test.

Equal-size implementation. Its two paths agree less, because parallel prefill cuts the sorted keys into equal-sized groups, whereas cached decoding puts each key into its own bucket. Their NLL is nevertheless equal (3.578 against 3.577). This test runs the code that the paper's timing tables measure.

Variable-size implementation. It reaches the level of full attention, because the router assigns each key to its bucket once. Moreover, the cached keys and values of all sparse prefix positions are bit-identical between the two paths. Here both paths compute the new tokens with the same attention. In our frozen-backbone study, decoding uses full attention whereas a prefill uses sparse attention, so the two differ there by design, and their NLL is equal (2.153 against 2.154).

Other feedback

Related work / Baseline

MoBA: Mixture of Block Attention for Long-Context LLMs, NeurIPS 2025.

Relation to MoBA. Both methods select groups of keys according to the query, and they differ in how the groups form. MoBA fixes the groups by position and ranks each block by the query's dot product with its mean key, so it needs no routing parameters. In contrast, HiRouter learns the grouping. Specifically, learned centroids define a content-based hierarchy, queries search this hierarchy, and the balance objective keeps the occupancy even. We add MoBA and this distinction to Sec. 2.

Comparison. We further compared the two selection rules on the frozen Qwen3-4B backbone at 64K. The baseline ranks 1,024-token positional blocks by their mean keys, and it runs inside our attention kernels with the same read budget.

Method (64K)RULER average (%)Multi-value retrieval (%)
Full attention99.8 ± 0.499.5
MoBA86.6 ± 2.159.0
HiRouter91.9 ± 1.980.5

On average, HiRouter scores 5.3 points above MoBA, with gains particularly from multi-value retrieval (+21.5 points), a task that requires several needles at different positions. In contrast, the two methods are on par when we average the other three tasks. These results therefore suggest that learned grouping helps most when the relevant keys lie far apart in the context.

Figures

We have expanded our figures to render them more legible.

I appreciate the authors' response and clarifications. It seems that the implementation (in the main body of the submission) in inherently non-causal in design, and what the rebuttal seems to suggest is that despite the non-causal nature, it still performs fine. The rebuttal is hard to understand, but I'd appreciate the authors' clarification about this point.

Reviewer_h6YtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents HiRouter, a learned hierarchical router for sparse attention. Keys follow a single path into leaf buckets, while queries use beam search to select candidate buckets. The router is trained alongside query and key representations, with entropy objectives encouraging confident assignments and balanced bucket usage. Experiments cover synthetic retrieval, language modeling, and long-context tasks, showing competitive performance with full attention and gains on selected retrieval benchmarks.

Critical strengths
  • The paper aims to address a practical bottleneck that how to find relevant tokens efficiently without sacrificing retrieval quality.

  • The evaluation covers multiple tasks and model scales, with useful ablations on routing losses and architectural choices.

  • The theoretical analysis explicitly acknowledges that confident, balanced assignments alone do not guarantee relevant query–key pairs will co-route.

Critical weaknesses
  • The link between the training objectives and retrieval quality remains incomplete. The guarantees depend on query–key routing compatibility, which the entropy losses do not directly enforce. The paper provides limited evidence that joint training improves this quantity or that the bounds are informative on trained models.

  • The long-context comparison is difficult to interpret. Models are primarily trained at length 2,048, while the full-attention baseline fails completely on the 4K and 8K NIAH settings. Without clearer positional encoding details and equally adapted baselines, it is difficult to separate routing benefits from differences in length extrapolation.

  • The gains are task-dependent, and their stability is unclear. Some language modeling and retrieval results improve, while several QA and code results decline. Small average differences lack uncertainty estimates. The scalability claim also needs qualification: linear routing does not imply linear overall attention cost when the number of leaf buckets is fixed.

Questions for authors
  • Can the authors measure routing mismatch and the recall bounds on trained models, and compare joint training against training only the router on frozen, pre-trained Q/K representations?

  • What positional encoding and context-extension settings are used? Do the long-context gains persist when full attention receives the same long-context adaptation budget?

  • Does changing a future suffix leave prefix outputs unchanged, and does full-sequence evaluation match cached decoding? How much retrieval quality is lost through equal-capacity layouts, query grouping, and cache eviction?

3 comments

Weaknesses

Objectives vs. retrieval quality

(a) The link between the training objectives and retrieval quality remains incomplete.

(b) The guarantees depend on query–key routing compatibility, which the entropy losses do not directly enforce.

(c) The paper provides limited evidence that joint training improves this quantity…

(d) …or that the bounds are informative on trained models.

(a) Objectives and retrieval quality. The theory links each objective to one guarantee. LsmpL_{\mathrm{smp}} lowers the routing entropy in the recall bound, and LbalL_{\mathrm{bal}} lowers the occupancy imbalance in the candidate-load bound (Prop. 4.5). Since Tables 22 and 28 do not isolate these effects, we measure both bounds on a trained router. We froze a pretrained Qwen3-4B, training only the router. At 32K, this router reads 5% of the keys outside the query's own segment, retaining 44% of each query's true top-16 keys (the 16 keys with the highest full-attention scores) and 46% of the attention mass. A random read of the same size retains 6%. Moreover, its occupancy is close to balanced (κL=0.43\kappa_L=0.43 nats out of a possible 6.1).

(b) Query–key compatibility. The two losses act on distinct terms. LsmpL_{\mathrm{smp}} targets the key-routing entropy, which also bounds the slack of the retention certificate (Lemma R1 in our reply to jAaD W1(c)), while LbalL_{\mathrm{bal}} targets the occupancy imbalance (Prop. 4.2). The remaining term is the query–key mismatch, which HiRouter shapes by training the representations and the centroids jointly. Our measurements confirm that this term decides retention. The mismatch averages 1.6 nats for the top-16 keys that the router retains and 3.9 nats for those missed, whereas their entropies are close (1.2 versus 1.6 nats).

(c) Evidence for joint training. Table 28 shows that joint training reaches 1.8 to 2.9 times the Recall@128 of the same router on untrained representations. We further ran the matched comparison at 125M, with the same initialization, data, objectives and update budget.

TrainingTest perplexityRecall@16Random-read Recall@16Mismatch of retained keys (nats)
Router only23.8340.4%18.2%2.52
Joint21.9543.6%20.8%2.42

Joint training therefore improves quality substantially, while it changes retrieval compatibility only slightly.

(d) Informativeness of the bounds. We compared what the theory guarantees with what the trained router retrieves on the same queries.

Recall@16 of the true top-16 keys (%)16K32K64K
Retained by the beam53.247.642.4
Guaranteed by the per-key certificate (Eq. A.15)52.146.741.7
Averaged bound rqr_q (Prop. 4.5)17.815.012.4

The per-key certificate stays within about one point of the retained recall at every length, so the recall guarantee is informative on a trained router. In contrast, the averaged bound rqr_q is much lower, and the revision therefore presents the per-key form as the certificate. Finally, the candidate-load bound (Prop. 4.2) holds for every query and is looser. It allows about 5,900 keys at 32K, where the router reads about 1,000. The beam retains 47.6% at 32K, and the 1,024-key read cap of the implementation lowers this to the 44% reported in (a).

Long-context comparison

(a) Models are primarily trained at length 2,048, while the full-attention baseline fails completely on the 4K and 8K NIAH settings.

(b) Without clearer positional encoding details and equally adapted baselines it is difficult to separate routing benefits from differences in length extrapolation.

(a) Original comparison. All relevant models use RoPE (θ=104\theta=10^4), trained with 2,048 token sequences, and use no interpolation, NTK scaling, or YaRN at evaluation. Table 5 therefore combines routing effects with length extrapolation.

(b) Controlled comparison. We add a complementary study using Qwen3-4B-Instruct-2507, which supports 256K context. For a fair comparison, full attention and HiRouter share identical frozen backbone weights, prompts, and positional encoding. Only HiRouter’s 1.6M router parameters are trained. All sparse variants retain dense local attention and the final 256 prompt rows, and use the same candidate-key budget.

HiRouter remains close to full attention up to 16K. At longer contexts:

Method32K64K
Full attention99.4 ± 0.699.8 ± 0.4
HiRouter96.2 ± 1.391.9 ± 1.9
MoBA91.9 ± 1.886.6 ± 2.1

These report RULER accuracy (%, mean ± SE) across four tasks with 50 prompts per task and length. At 64K, HiRouter achieves 2.2× faster whole-model prefill and scores 5.3 points above positional selection using the same kernels. We replace the claim of surpassing full attention beyond 4K with this measured accuracy–efficiency trade-off.

Task-dependent gains, stability, and scalability

(a) Some language modeling and retrieval results improve, while several QA and code results decline.

(b) The gains are task-dependent, and their stability is unclear. Small average differences lack uncertainty estimates.

(c) Linear routing does not imply linear overall attention cost when the number of leaf buckets is fixed.

(a) Task-wise results. We acknowledge the pattern varies by task (ex. LongBench, Table4). However, the prompts of Table 4 exceed the 2,048-token training length, so that pattern also reflects length extrapolation (see W2). We add a controlled comparison on a frozen Qwen3-4B backbone, where full attention and HiRouter share the same weights. In this setting, HiRouter stays within one point of full attention on all five LongBench tasks, showing how the router can be helpful.

LongBench taskHotpotQAQasperPassageRetrievalLCCRepoBench-P
Full attention58.944.8100.064.357.5
HiRouter59.844.0100.064.357.6

(b) Uncertainty and stability. We add sample sizes and standard errors to the result tables. For Table 2, the per-task standard errors are 0.5 to 1.4 points (n=1,172n=1{,}172 to 10,04210{,}042), and the eight-task average has a standard error of 0.37 points. The averages of the Transformer (47.17), HiRouter (47.01) and NSA (46.75) are therefore statistically similar, and we now describe them as such. Furthermore, both methods answer the same prompts in the frozen-backbone study. We therefore compute the score difference on each prompt and report its average with a bootstrap interval.

RULER16K32K64K
Paired difference in points [bootstrap interval]+0.5 [−0.2, +1.2]+3.1 [+1.5, +5.1]+7.9 [+5.4, +10.8]

HiRouter is thus within noise of full attention at 16K and below it from 32K on. Finally, we checked stability across training seeds. Three seeds give RULER scores of 96.2, 97.5 and 96.1 at 32K and 91.9, 91.6 and 91.5 at 64K, and their perplexities agree within 0.04. Seed variation is therefore smaller than the evaluation uncertainty.

(c) Attention cost. You are right that linear routing alone gives quadratic attention when the leaf count is fixed (App. E). The cost becomes near-linear when the leaf count grows with TT while the beam width MM and the leaf capacity bb stay fixed. Each query then reads at most MbMb keys, so attention costs O(TMbD)O(TMbD), which is linear in TT. Routing adds O(TMCDlog⁡T)O(TMCD\log T), and this term is small in practice. For example, with C=M=L=4C=M=L=4 and b=256b=256, routing takes at most 80D80D operations per token against 2,048D2{,}048D for attention, which is about 4%. The overall cost is therefore O(Tlog⁡T)O(T\log T), and we state these assumptions explicitly in Appendix E.

Questions

Routing mismatch, bounds on trained models, joint vs. frozen training

(a) Can the authors measure routing mismatch…

(b) …and the recall bounds on trained models…

(c) …and compare joint training against training only the router on frozen, pre-trained Q/K representations?

(a) Routing mismatch. We measure this on the trained router in our frozen Qwen3-4B study, with 256 held-out queries per layer. For each query we take its true top-16 keys among the keys outside its own segment.

ContextRecall@16Attention massRandom readMismatch of retained keys (nats)Mismatch of missed keys (nats)
16K50%53%10%1.84.3
32K44%46%6%1.63.9
64K38%35%4%1.43.4

The router retains five to nine times more of the top-16 keys than a random read of the same size. Moreover, the mismatch ∑lξqi(l)\sum_l\xi_{qi}^{(l)} separates the keys it retains from the keys it misses. Missed keys carry 2.0 to 2.5 nats more mismatch, and this gap is positive in all 36 layers. In contrast, the routing entropies of the two groups differ by only 0.4 nats. Retrieval failures therefore come from query–key mismatch, as the theory predicts.

(b) Bounds on trained models. We compared the guarantee with the actual retrieval on the same queries (table in W1(d)). At 32K, the per-key certificate guarantees 46.7% of the true top-16 keys, and the beam retains 47.6%. The certificate therefore covers 98% of the keys that the beam retains, and it stays within about one point of the retained recall at 16K and 64K as well.

(c) Joint versus frozen training. We compared joint training with router-only training at 125M under the same initialization, data, objectives and update budget (table in W1(c)). Joint training lowers perplexity from 23.83 to 21.95, whereas recall relative to a random read stays about the same. Co-adaptation therefore mainly improves quality. Router-only adaptation remains a cheap and viable option. On Llama-3-8B, it preserves LongBench performance (27.76 against 27.61 for the original model, Table 32).

Positional encoding and context extension

(a) What positional encoding and context-extension settings are used?

(b) Do the long-context gains persist when full attention receives the same long-context adaptation budget?

(a) Positional settings. All submitted models use RoPE (θ=104\theta=10^4), train at 2,048 tokens, and apply no position interpolation, NTK scaling, or YaRN at evaluation. Table 5 therefore measures robustness beyond the training context.

(b) Long-context comparison. Because we could not retrain the baselines within the rebuttal period, we ran the comparison on a pretrained backbone that already supports long contexts (Qwen3-4B-Instruct-2507, 256K native context). The dense baseline therefore needs no adaptation. Full attention and HiRouter share identical frozen backbone weights, positional settings and evaluation prompts, and we train only the router of HiRouter, so the comparison isolates the effect of routing.

HiRouter stays within 0.6 RULER points of full attention at 8K–16K. At longer contexts:

MethodRULER 32KRULER 64KPrefill 64K
Full attention99.4 ± 0.699.8 ± 0.44.68 s
HiRouter96.2 ± 1.391.9 ± 1.92.16 s

Accuracy (%, mean ± SE), four tasks, 50 prompts per task and length. At 64K, perplexity is 1.9% higher on WikiText-103 and 5.0% higher on PG-19. The benefit is near-parity at 8K–16K and 2.2× faster prefill at 64K with a 7.9-point RULER accuracy cost.

Q3. Causality, prefill versus decoding, and approximation costs

(a) Does changing a future suffix leave prefix outputs unchanged?

(b) Does full-sequence evaluation match cached decoding?

(c) How much quality is lost through equal-capacity layouts?

(d) How much quality is lost through query grouping?

(e) How much quality is lost through cache eviction?

(a) Suffix invariance. In the submitted prefill kernel, no. Changing future tokens can move earlier keys between buckets. On the full 125M model, this changes 4.0% to 6.5% of the prefix next-token predictions and shifts the prefix NLL by at most 0.013 nats. With the variable-size bucket layout of App. B.2, yes. This is the implementation that we use in our frozen-backbone study. It keeps each key in its router-assigned bucket, and it orders the nodes that a group of queries reads by the first row that selects them. A row's candidates therefore depend only on rows at or before it. We verified this in 18 cases: all prefix outputs outside the 64-row query group that spans the prefix/suffix boundary are bitwise unchanged. Inside that group, every prefix row reads the same candidates in the same order, and the outputs differ by at most 0.06, which is 0.3% of their magnitude and comes from bf16 accumulation.

(b) Prefill versus decoding. In the submitted implementation, the two modes agree closely but not exactly. After a 1,024-token prefill on the 125M model, their next-token predictions agree at 59 of 64 positions, with a mean KL divergence of 0.013 nats. The reason is that prefill and decoding group past keys differently there. In our frozen-backbone study, decoding instead uses full attention over the cache. Keys are therefore assigned to buckets only once, during prefill, and this mismatch cannot arise.

(c) Equal-capacity layout. This layout mainly costs retrieval. When we force equal-sized buckets on our trained router, about 65% of the keys leave their router-assigned bucket, and Recall@16 falls from 50 / 44 / 38% to 28 / 23 / 18% at 16K / 32K / 64K. Perplexity is less sensitive and rises by less than 1%. We therefore use variable-size buckets in our frozen-backbone study.

(d) Query grouping. In the paper, query grouping shares one bucket selection among the query heads of a GQA group (App. B.1), and Table 20 measures its cost. Perplexity is 18.5 without grouping, and 18.6, 18.8 and 19.1 with groups of 2, 4 and 16 heads. Grouping therefore costs at most 0.6 perplexity points.

(e) Cache eviction. During decoding, each new key is routed once into its bucket, and it replaces the oldest entry when the bucket is full. Retained keys are never regrouped. We measured the effect on the 125M model with the cache of Tables 7 and 8 (64 buckets of 16 entries). After a 1,024-token prefill, we decoded the next 1,024 tokens one at a time and compared them with one full pass without eviction.

Decoded tokensNLL, full passNLL, with evictionGreedy agreement
1,025 to 1,2803.3403.33294.5%
1,793 to 2,0483.5713.56792.4%
Control without eviction (last 64 tokens)3.5773.57896.8%

Eviction therefore costs no measurable perplexity on this model, because the NLL stays within 0.012 nats of the full pass. The token-level agreement declines slowly as more of the prefill is evicted.

Reviewer_jAaDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes HiRouter, a sparse attention method that uses a learned hierarchical partition to select keys for each query. Unlike techniques based on locality-sensitive hashing (LSH) or online k-means, HiRouter trains its partition by gradient descent together with the model. The aim is for the selected buckets to contain the query’s top-k keys (the keys with the highest attention scores). The buckets should also be balanced, so that a query only needs to look at a small fraction of the keys.

Technically, the buckets are the leaves of a tree of learned centroids. Keys are routed greedily down the tree to a single leaf, while queries select M leaves using beam search. The authors add two entropy-based routing losses to the language-modeling loss: the first encourages each key to commit to one bucket, and the second encourages the keys to spread evenly over the buckets. The paper also proves lower bounds on the recall of the top-k keys.

In experiments, HiRouter stays close to full attention in perplexity and zero-shot accuracy from 125M to 1B parameters. It even achieves slightly lower perplexity than full attention on WikiText-103 at 125M. For long contexts, the authors also report advantage over full attention on LongBench and on needle-in-a-haystack (NIAH) retrieval, and up to 2× faster inference than FlashAttention.

Critical strengths
  • Learning the router with the model. Training the partition by gradient descent jointly with the queries and keys is an interesting and natural step beyond routing with LSH or online k-means, and the experiments suggest that it is also practical.

  • A practical design. Each key is routed only once, when it enters the KV cache, and is never routed again when new tokens are generated. Assigning a key to a leaf only requires comparing it with the few child centroids at each level of the tree, rather than with every leaf.

Critical weaknesses
  • The paper does not show whether its recall bounds are informative for the trained models. The bounds depend on how confidently keys are assigned, which the first routing loss encourages, but also on the probabilities that a query assigns to the paths taken by its relevant keys, which neither routing loss directly controls. The authors acknowledge this limitation in Appendix A.1, where both losses can be arbitrarily close to optimal even though the query and its most relevant key favor different buckets.

  • The long-context claims are not particularly convincing. The full-attention baseline is trained on 2K-token inputs, and the paper does not say that it was adapted to longer inputs, for example by position interpolation. In Table 5, full attention scores zero on all three NIAH tasks for 4K- and 8K-token inputs, while outperforming HiRouter in five of the six 1K- and 2K-token settings. So the results suggest that HiRouter degrades more gracefully on inputs longer than those seen in training, but they do not isolate the advantage of learned routing.

Questions for authors
  • How were the results in Table 24 obtained? All eight accuracies drop by exactly 0.04 percentage points between the 100% and 75% rows, and again between the 75% and 50% rows, even though the benchmarks have different numbers of examples. Are these numbers averages over several runs?

  • Adding the two routing losses improves WikiText-103 perplexity at 125M from 24.6 to 18.5 (Table 21), but at 410M the best WikiText perplexity is obtained without them (Table 23). How do the authors explain this?

  • Is there a condition on the queries and keys under which minimizing the two routing losses guarantees that the buckets selected for a query contain its top-k keys? The example in Appendix A.1 suggests that a large gap between the highest attention score and the others is not enough.

  • In the experiments, the routing tree has 256 leaves and each query selects 4 of them. The attention for each query is therefore still computed over about 1/64 of all keys, and the total cost of processing a sequence remains quadratic in its length, as Appendix E notes. How should the number of leaves and M depend on the sequence length to make this cost subquadratic, and what recall does the analysis guarantee in that case?

5 comments

Weaknesses

Informativeness of the recall bounds on trained models

(a). The paper does not demonstrate whether the theoretical recall bounds are informative for trained models. (b). The routing losses encourage confident key assignments and balanced bucket occupancy, but neither directly controls query–key compatibility ξqi\xi_{qi} (c). Appendix A.1 provides a counterexample where both losses approach their optima, yet a query and its most relevant key are routed to different buckets.**

(a) We agree that the two routing losses do not directly control query–key compatibility ξqi\xi_{qi}, as acknowledged in Appendix A.1. Our propositions establish three complementary results:

(i) Candidate load. For any set BB of the CLC^L leaves, NB≤T U(∣B∣/CL,κL)N_B \leq T\,U(|B|/C^L,\kappa_L), where κL\kappa_L is the observed occupancy imbalance encouraged to decrease by LbalL_{\text{bal}}. This bound is unconditional, and the envelope UU is tight given the imbalance and selected leaf fraction (Prop. 4.2, App. A.2).

(ii) Retention. Under Assumption 4.1, key ii is retained whenever ∑l=1L[H(pi(l))+ξqi(l)]<log⁡(M+1)\sum_{l=1}^{L}[H(p_i^{(l)})+\xi_{qi}^{(l)}]<\log(M+1). This sufficient condition separates assignment uncertainty, which LsmpL_{\text{smp}} encourages to decrease, from query–key mismatch ξqi\xi_{qi}, which neither loss directly controls (Prop. 4.4). The tighter certificate uses actual beam-pruning thresholds through ψqi<1\psi_{qi}<1.

(iii) Attention output. For fixed representations, values, and gating, the routed attention-output error is bounded by 2grV2g_rV times the missed attention mass, before any additional token filtering (App. A.7).

Thus, the recall bound is a conditional, per-key certificate, not an unconditional consequence of the two losses. Its practical informativeness must be assessed on trained routers.

(b) We evaluate the frozen-backbone HiRouter instance described in the global response (C2), where the router is trained on fixed Q/K representations. We sample 256 queries per layer across 36 layers on held-out 16K/32K/64K contexts. For each query, we compute the exact top-kk keys among eligible far-context keys (k=16,64,256k=16,64,256), their retention in selected nodes, and the covered attention mass. The oracle scores each eligible node by the total full-attention weight of its far-context keys, then selects the highest-scoring nodes under the same node-selection budget.

Table R1. Results at 32K (mean over layers, %). All methods use the same routing tree and node-selection budget, although the resulting numbers of keys read differ.

Node selectionKeys readRecall@16Recall@64Recall@256Far attention mass
Random (analytic)9896666
Key-mean1,12343342625
HiRouter98944423646
Oracle1,13071513581

HiRouter achieves 7.3× the random Recall@16 and 7.7× the random attention-mass coverage. Compared with key-mean selection, it achieves comparable Recall@16 (44% vs. 43%) while covering 1.8× more attention mass (46% vs. 25%), despite reading fewer keys. These results establish that the learned router retains substantially more relevant information than random selection.

(c) Yes, the per-key bound is informative on a trained router. It predicts almost every key that the router actually retrieves.

We tested this as follows. For each query, we took its true top-16 keys, which are the 16 far-context keys with the highest full-attention scores. We then counted how many of them the beam search actually retains, and how many each bound guarantees in advance. A bound is informative when these two are close.

Table R1b. Share of the true top-16 keys (%), on the queries of Table R1 (beam width M=16M=16).

16K32K64K
Actually retained by the beam search53.247.642.4
Guaranteed by the per-key bound, sharper form (Eq. A.15)52.146.741.7
Guaranteed by the per-key bound, entropy form (Prop. 4.4)37.633.630.1
Guaranteed by the averaged bound rqr_q (Prop. 4.5)17.815.012.4
Read by the implementation49.643.937.7

The sharper per-key bound guarantees almost every key that the beam retains. The gap is about one point at every length, and no guaranteed key was missed. The entropy form is more conservative. At 32K, it guarantees 33.6% of the true top-16 keys, against 47.6% actually retained. Lemma R1 (App. A.4 of the revision) shows that this extra conservatism is at most the key's routing entropy, which is exactly the quantity that LsmpL_{\text{smp}} reduces. In contrast, the averaged bound rqr_q is valid but far below the actual recall. The revision therefore presents the sharper per-key form as the main guarantee.

Finally, the implementation reads about 4 to 5 points fewer than the beam retains, because it also caps each query at 1,024 far-context keys. This cap is the only step that the bound does not cover.

Long-context claims

(a) Training-context limitation. The full-attention baseline is trained on 2K-token inputs.

(b) Missing context-extension details. The paper does not clarify whether the baseline was adapted to longer contexts, for example through position interpolation.

(c) Accuracy and extrapolation. In Table 5, full attention outperforms HiRouter in five of six settings at 1K–2K but scores zero on all three NIAH tasks at 4K–8K. This suggests that HiRouter degrades more gracefully beyond its training length.

(d) Isolating learned routing. The long-context comparisons do not establish whether the observed advantage comes from learned routing rather than differences in length extrapolation.

(a) Training context and (b) context extension. Both models in Tables 4–5 were trained at 2,048 tokens using RoPE (θ=104\theta=10^4). Neither model received position interpolation or other context-extension techniques. Consequently, evaluations beyond 2K measure length extrapolation. These settings will be clarified in Appendix B.1.

(c) Accuracy and extrapolation. Table 5 indeed shows that HiRouter degrades more gracefully beyond the training length. To examine its performance independently, we extend the evaluation to a pretrained backbone with native long-context support below. The additional experiment uses Qwen3-4B-Instruct-2507, which supports contexts up to 256K. All pretrained backbone parameters remain frozen for fair comparisons, and only the 1.6M-parameter HiRouter is trained for 300 updates. The sparse methods use the same attention kernels and matched read budgets. HiRouter achieves high needle-retrieval accuracy with noticable prefill speedups over full attention. These results establish the accuracy–efficiency trade-off on a backbone that already supports the evaluated lengths.

Table R2. RULER needle-retrieval accuracy (%), averaged over four tasks with 50 prompts each. Standard errors are shown in parentheses.

Method32K64K
FlashAttention99.4 (0.6)99.8 (0.4)
HiRouter96.2 (1.3)91.9 (1.9)
MoBA91.9 (1.8)86.6 (2.1)

(d) Isolating learned routing.

With length extrapolation removed, HiRouter retains 96.2% accuracy at 32K and 91.9% at 64K, compared with 99.4% and 99.8% for full attention. More importantly for routing, HiRouter exceeds MoBA by 4.3 and 5.3 percentage points at the same read budget. This provides evidence that the learned hierarchical routing design improves retrieval over block-based selection on an already long-context-capable backbone. The comparison evaluates the complete routing design, including its learned components and selection mechanism.

Cost and accuracy trade-off. At 64K, prefill time decreases from 4.68 s with full attention to 2.16 s with HiRouter, giving a 2.17× speedup. The corresponding WikiText-103 perplexities are 8.36 and 8.52, while PG-19 perplexities are 13.65 and 14.33.

Questions

Reliability of Table 24

(a) Experimental protocol. How were the results in Table 24 obtained?

(b) Suspiciously uniform changes. All eight accuracies drop by exactly 0.04 percentage points between the 100% and 75% rows, and again between the 75% and 50% rows, even though the benchmarks have different numbers of examples.

(c) Multiple runs. Are these numbers averages over several runs?

(a) Experimental protocol. Table 24 was intended to measure how performance changes when a fraction of the reference top-kk keys is replaced by random keys. For each query, we identify the exact causal top-kk keys under full attention, retain pp% of them, and replace the rest with randomly selected keys outside the reference set. Here kk equals the beam width used at the input length (2 for inputs up to 128 tokens, 4 up to 512, and 8 beyond), and we round the number of replaced keys to the nearest integer.

Unfortunately, the intermediate rows contained placeholders inserted while the experiment was still running. We overlooked them when compiling the results and failed to replace them with the completed measurements before submission. We apologize for this error.

(b) Corrected measurements. We have rerun the experiment using a fixed 410M checkpoint and report the new measurements.

KeptWiki pplLMB pplLMB accPIQAHellaWinoARC-eARC-cSIQABoolQAvg
100%36.3424.0738.9565.7240.8151.0758.9227.9939.6659.6347.84
75%36.0724.0939.0165.6140.8151.0758.9627.9939.6659.7247.85
50%35.7526.4036.9766.5440.9651.5459.4327.8238.7959.6047.71
25%35.9449.3830.2366.2740.4452.8060.5628.8439.3058.5647.13
0%35.7549.8230.2266.3240.4152.8060.5628.8439.3057.6547.01

Some rows repeat because most short-context inputs use k=2k=2. With two keys, rounding keeps both at the 75% level and neither at the 25% level, so these rows match the 100% and 0% rows. Only BoolQ and Wiki use larger kk and therefore show five distinct levels. The results show that LAMBADA is most sensitive to reference-key retention: its perplexity increases from 24.07 to 49.82 and accuracy decreases from 38.95% to 30.22%. In contrast, Wiki perplexity changes by less than 2%, while the seven multiple-choice tasks exhibit smaller, mixed changes.

(c) Multiple runs and statistical reporting. Each reported value comes from a single evaluation over the corresponding benchmark examples. Task sample sizes follow Table 2. In addition, we ran a long-context recall-corruption experiment in which we measure the actual Recall@16. At 32K, reducing Recall@16 from 44% to 5% lowers RULER accuracy from 88.1% to 33.1%, which shows that retrieval matters far more at long contexts.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.