acceptodds
Under review as a conference paper at ICLR 2027

Rix: Reusable Attention Indexing

Abstract

Indexer-based sparse attention replaces full O(L^2) attention with a learned index plus a top-k pass, but as contexts grow longer the indexer's own score computation becomes the bottleneck. Existing accelerations cluster keys into blocks or share indices across layers. Reusing indices across query positions is orthogonal to both, yet unsafe to exploit directly. We observe that adjacent queries' index sets coincide strongly, but rare query pairs drift sharply, so query-side reuse requires a safety assurance. Our proposed method, Reusable Indexing (Rix), provides one with an O(Hd) closed-form reusability metric, derived from attention score estimation under a uniform key model, and applies reusable indexing coherently: an indexer design the metric mandates, a distillation recipe that keeps the metric faithful across reuse rates, and an inference-time scheduler that places fresh anchors only where the metric demands. In our evaluation, Rix consistently outperforms fixed reuse scheduling at matched reuse rates.

Primary area:
foundation or frontier models, including LLMs
Keywords:
sparse attention, long-context language models, attention index reuse, efficient inference

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Y23mOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work find that reusing indices across query positions is orthogonal to both, yet unsafe to exploit directly. And this work find that adjacent queries' index sets concide strongly, but rare query paris drift sharply. This work propose Reusable Indexing (Rix), which provides one with an O(Hd) closed-form reusability metric. The experient support that the Rix is useful.

Critical strengths
  1. This work proposes to use the accumulated attention mass to choose a key set, which is interesting.
  2. The work seems the simple and effective.
  3. The experiments support the effectiveness of Rix.
  4. This work discusses the effect of ReLU and Exp.
  5. This work provides the code to reproduce the results, which increases the reliability.
Critical weaknesses
  1. This work involves several concerps, such as von Mises–Fisher, which may make the paper requires theory background. This work should further and explain the notation for the theory.
  2. It seems that the work does not compare with baselines? It mainly compare with Rix variants.
  3. For equation 5, the softplus may make the w to be zero, so that the attention becomes uniform distribution. This work should disucss the effect of w with softplus in Equation.
Questions for authors

NA

2 comments
AuthorsOpenReview ↗

Reply to reviewer Y23m

We thank the reviewer for the constructive comments.

Theoretical concepts. Appendix C.1 now provides a self-contained derivation from uniform spherical keys to the per-head vMF distribution and the multi-head KL bound. It defines the mean direction, concentration, mean resultant length, Bessel and hypergeometric functions, and the exp–erf approximation used for efficient evaluation.

Comparison with baselines. Rix is not an incremental modification of an existing reuse method. It introduces calibrated per-pair reuse-error estimation and optimal adaptive anchor placement, while remaining compatible with anchor construction methods and other reuse axes. Consequently, we fail to find baseline that represents the full framework. We therefore use component-wise and compositional comparisons: Table 2 compares dense attention, full indexing without reuse, fixed-period placement, the external PIVOT-reuse method, and ORS; Tables 4–5 isolate the indexer activation and training objective. Rix composes with PIVOT's anchor synthesis, and Table 2 shows that combining ORS with PIVOT-reuse further improves over fixed pooling.

We also establish target-weighted head cosine (THC), a simplified variant of the proposed gate, to isolate the contribution of the reuse predictor. THC replaces the proposed vMF divergence with directional cosines and head-weight/norm corrections. Define per-head directional cosines, target-side head shares, and head-concentration vectors as

a_h(j)=\frac{w_{j,h}\\|q_{j,h}\\|}{\sum_{h'}w_{j,h'}\\|q_{j,h'}\\|},\qquad \boldsymbol\kappa(q)=(\\|q_1\\|,\ldots,\\|q_H\\|).$$ With $\boldsymbol w(q)=(w_1,\ldots,w_H)$ and $\operatorname{cos}(u,v)=u^{\top}v/(\\|u\\|\\,\\|v\\|)$, the mixture-corrected THC distance is $$\begin{aligned} D_{\mathrm{THC}}(i,j)={}&1-\sum_h a_h(j)c_h(i,j)\\ &+\lambda_w\bigl[1-\operatorname{cos}(\boldsymbol w(q_i),\boldsymbol w(q_j))\bigr]\\ &+\lambda_\kappa\bigl[1-\operatorname{cos}(\boldsymbol\kappa(q_i),\boldsymbol\kappa(q_j))\bigr]. \end{aligned}$$ The first term emphasizes heads carrying the target query's index energy; the other two capture head-weight and concentration-profile reallocation. The coefficients $\lambda_w,\lambda_\kappa$ and the affine map $\beta\ln D_{\mathrm{THC}}+c$ are fitted with the same realized-KL calibration target as the proposed gate. THC also costs $O(Hd)$, but its central cosine term is insensitive to a uniform rescaling of all query heads. Both predictors use strictly matched training and calibration recipes and are evaluated on all 1,300 RULER-32k cases. Proxy metrics use probe offsets 1–4 and zero-slack 75% iso-reuse; generation uses top-$k$ 2048, $W=8$, and exactly 75% realized ORS reuse. | Predictor | $L_{\mathrm{mono}}$ ↓ | Rejection (%) ↓ | Decision error (%) ↓ | KL regret ↓ | idx | ORS 75% | |---|---:|---:|---:|---:|---:|---:| | THC | 0.141188 | 6.671 | 10.007 | 0.009527 | **87.23** | 77.08 | | vMF (ours) | **0.140648** | **6.482** | **9.722** | **0.008472** | 87.16 | **77.71** | The vMF gate improves every oracle-aligned metric. The 95% paired intervals for THC minus vMF are $[-0.887,0.635]$ for idx and $[-0.500,1.962]$ for ORS 75%, so the end-task scores do not significantly separate them. **Zero head weights.** This is a well-taken concern. We indeed observed zero-weight heads with ReLU during training, which directly motivated our use of softplus. In exact arithmetic, $\operatorname{softplus}(x)>0$ for every finite $x$, avoiding ReLU's absorbing zero-weight state; empirically, this change resolved the failure mode. We explain this motivation in Appendix D.4.

After the the above response, I keep the positive score.

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

The paper proposes Rix, a framework for reusing sparse attention indices across queries to reduce indexing overhead. It combines a learned indexer, a query-pair reusability metric derived under a uniform spherical key assumption and calibrated during training, and an Optimal Reuse Scheduler (ORS) that selects where to compute fresh indices. Evaluations on RULER and LongBench generally show improved downstream accuracy over fixed-period reuse at matched reuse rates. The paper also reports indexer acceleration and evaluates a fixed-threshold deployment setting.

Critical strengths
  1. The paper addresses the important problem of indexer overhead in long-context sparse attention by exploring index reuse across queries. At matched reuse rates, the proposed scheduler generally improves downstream accuracy over fixed-period reuse.

  2. The proposed query-pair metric evaluates reuse without scanning cached keys, making the gating computation inexpensive relative to recomputing index scores.

Critical weaknesses
  1. The role and necessity of jointly training the indexer with the calibration objective are insufficiently established. The frozen backbone’s attention distributions do not become more reusable through calibration; rather, Lcalib\mathcal{L}_\text{calib} trains the indexer-based metric to estimate reuse error. This is a plausible objective, but the paper does not clearly isolate the benefit of updating the indexer itself, rather than fitting calibration parameters with the indexer frozen. Moreover, the reported fidelity of the jointly trained, calibrated metric does not establish the contribution of its uniform-sphere derivation relative to a simpler learned predictor. Controlled comparisons would be needed to substantiate these design choices. This matters because the metric and its associated training procedure are central contributions, whereas improvements over fixed scheduling alone do not establish their necessity.

  2. The core algorithm and training objective are insufficiently specified, making the method difficult to reproduce and assess. In particular, Equation (7) defines the calibration target without clearly specifying how the support S\mathcal{S} is constructed during training, the exact distributions and operations used to construct p~\tilde p. It is also unclear how the union of top-kk indices and a local window in Equation (5) corresponds to the total key-budget allocation described in Section 3.3. These ambiguities go beyond presentation: different interpretations can change the calibration targets and selected key sets, directly affecting reproducibility and the interpretation of the experimental results.

Questions for authors
  1. Clarification and supporting evidence: Table 2 primarily compares reuse strategies using the proposed indexer, demonstrating the benefit of ORS over fixed scheduling at matched reuse rates. However, it does not isolate the contribution of the indexer design and calibration training from that of the scheduler. Could the authors clarify which existing comparisons establish these separate contributions? In particular, does the proposed indexer improve downstream accuracy under fixed scheduling, and how much of the ORS gain depends on jointly training the indexer with Lcalib\mathcal{L}_\text{calib}, compared with freezing the indexer and fitting only the calibration parameters?

  2. Could the authors provide an ablation showing whether including Lcalib\mathcal{L}_\text{calib} during indexer training improves downstream task accuracy at matched reuse rates?

  3. Validity of the reusability approximation. The reuse metric is derived under a uniform spherical key assumption. Does the paper provide evidence that this assumption reasonably approximates the learned key distributions? Beyond the calibrated correlations reported in Figure 3, how closely do the resulting gate decisions and ORS schedules match those obtained using the oracle reuse error in Equation (7) on held-out data? A comparison at matched reuse rates would help assess the practical impact of the approximation.

5 comments
AuthorsOpenReview ↗

Reply to reviewer hw9w #1/3

We thank the reviewer for identifying the missing specifications and controls. We have clarified the method and added the requested comparisons.

Notation and training target. Section 3.2 and Appendix D.3 now define the calibration support explicitly as S=Ti∪{i+1,…,j}\mathcal S=T_i\cup\{i+1,\ldots,j\}, where TiT_i is the full causal prefix in stage 1 and the backbone's oracle top-2048 keys in stage 2. The deployed p~\tilde p uses the anchor's backbone row on TiT_i and the served query's own row on the causal gap; both distributions are restricted to S\mathcal S and renormalized, with reference mass outside S\mathcal S included in the KL target. Section 3.3 also gives the exact inference support Ti∪LjT_i\cup L_j and its size k+W−∣Ti∩Lj∣k+W-|T_i\cap L_j|, distinguishing the global top-kk budget from the trailing window.

Oracle agreement (Questions 3). To test the uniform-sphere approximation beyond correlation, we compare gate decisions directly with decisions from realized oracle reuse KL on all 1,300 held-out RULER-32k cases. For each layer and case, the gate and oracle each admit their lowest-scoring 75% of pairs. Rejection is P(oracle rejects∣gate admits)P(\text{oracle rejects}\mid\text{gate admits}); decision error is gate–oracle disagreement over all pairs; KL regret is the excess realized KL of gate-admitted pairs over oracle-admitted pairs. We report detailed results below.

AuthorsOpenReview ↗

Reply to reviewer hw9w #2/3

Alternative predictor (Weakness 2) We established target-weighted head cosine (THC), a simplified query-only predictor that replaces the vMF divergence with directional cosines and head-weight/norm corrections. Define per-head directional cosines, target-side head shares, and head-concentration vectors as

a_h(j)=\frac{w_{j,h}\|q_{j,h}\|}{\sum_{h'}w_{j,h'}\|q_{j,h'}\|},\qquad \boldsymbol\kappa(q)=(\|q_1\|,\ldots,\|q_H\|).$$ With $\boldsymbol w(q)=(w_1,\ldots,w_H)$ and $\operatorname{cos}(u,v)=u^{\top}v/(\|u\|\,\|v\|)$, the mixture-corrected THC distance is $$\begin{aligned} D_{\mathrm{THC}}(i,j)={}&1-\sum_h a_h(j)c_h(i,j)\\\\ &+\lambda_w\bigl[1-\operatorname{cos}(\boldsymbol w(q_i),\boldsymbol w(q_j))\bigr]\\\\ &+\lambda_\kappa\bigl[1-\operatorname{cos}(\boldsymbol\kappa(q_i),\boldsymbol\kappa(q_j))\bigr]. \end{aligned}$$ The first term emphasizes heads carrying the target query's index energy; the other two capture head-weight and concentration-profile reallocation. The coefficients $\lambda_w,\lambda_\kappa$ and the affine map $\beta\ln D_{\mathrm{THC}}+c$ are fitted with the same realized-KL calibration target as the proposed gate. THC also costs $O(Hd)$, but its central cosine term is insensitive to a uniform rescaling of all query heads. Both predictors use strictly matched training and calibration recipes. The main results are: | Predictor | $L_{\mathrm{mono}}$ ↓ | Rejection (%) ↓ | Decision error (%) ↓ | KL regret ↓ | idx | ORS 75% | |---|---:|---:|---:|---:|---:|---:| | THC | 0.141188 | 6.671 | 10.007 | 0.009527 | **87.23** | 77.08 | | vMF (ours) | **0.140648** | **6.482** | **9.722** | **0.008472** | 87.16 | **77.71** | The vMF gate improves every oracle-aligned metric. Proxy metrics use probe offsets 1–4 and zero-slack 75% iso-reuse; generation uses top-$k$ 2048, $W=8$, and exactly 75% realized ORS reuse. However, the 95% paired intervals for THC minus vMF are $[-0.887,0.635]$ for idx and $[-0.500,1.962]$ for ORS 75%, so the end-task scores do not significantly separate them.
AuthorsOpenReview ↗

Reply to reviewer hw9w #3/3

Calibration training (Questions 1 and 2). We interpret freezing the indexer with respect to Lcalib\mathcal L_{\mathrm{calib}} as stopping its gradient through the query projections and head weights, while retaining ordinary indexer distillation. The two Qwen3-8B checkpoints have strictly matched recipes except for this stop-gradient choice. Full RULER-32k results are:

CalibrationLmonoL_{\mathrm{mono}} ↓Rejection (%) ↓Decision error (%) ↓KL regret ↓idxORS 75%
w/ stop-gradient0.13612014.39121.5860.03748687.8780.14
w/o stop-gradient0.1406487.27710.9150.01035487.1677.71

Here proxy metrics use probe offsets 1–8, a different protocol from the THC table, so only within-table comparisons are meaningful. Joint calibration substantially improves rejection, decision error, and KL regret, although w/ stop-gradient has slightly better LmonoL_{\mathrm{mono}}. The downstream ordering does not follow these proxies. w/ minus w/o stop-gradient is +0.708+0.708 for idx (95% paired interval [0.138,1.446][0.138,1.446]) and +2.433+2.433 for ORS 75% ([−2.506,7.843][-2.506,7.843]). The idx difference is below one suite point and the ORS interval crosses zero.

For completeness, the KimiLinear-48B reference training and RULER-32k evaluations show the opposite downstream ordering, although all six differences are below one point.

CalibrationdenseidxFirstAnchor 50%FirstAnchor 75%ORS 50%ORS 75%
w/ stop-gradient95.4095.5194.7794.4795.3894.83
w/o stop-gradient95.8895.8895.5895.3395.6695.26

Together with the matched Qwen3-8B result, it indicates that the downstream effect is backbone-dependent. For Question 2, joint calibration shows insignificant and backbone-dependent influence on downstream accuracy, at fixed or ORS scheduling. Its demonstrated benefit is improved gate–oracle agreement.

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

As context windows in LLMs expand toward 1M tokens, the compute overhead of learned attention indexers (used in sparse attention) becomes a major performance bottleneck. While prior work addresses this by sharing indices across layers or clustering keys, RIX targets the orthogonal query axis. It mitigates the risk of direct index reuse across adjacent query positions—where rare "corner queries" exhibit sharp attention drift—by introducing an adaptive scheduling system guided by a key-agnostic reusability metric.

Contributions

  1. Key-Agnostic Reusability Metric: Derived an O(Hd) closed-form metric based on a uniform spherical key model utilizing modified Bessel functions. It incorporates a novel mixture correction term to accurately track head-weight and norm drift at long anchor ages.
  2. Aligned Indexer & Calibration Design: Tailored a multi-query indexer using exp activation, unparameterized K-norm, and a softplus weight parameterization to perfectly mirror the mathematical properties of the metric. Introduced a joint Huber-style calibration loss to ensure the metric accurately bounds real-world attention damage.
  3. Optimal Reuse Scheduler: Formulated index reuse as a "jump game" and proved that a sequential greedy strategy yields the minimum possible number of fresh anchors. Developed a parallelized binary-lifting scheduler to optimize prefill latency on GPUs.
Critical strengths
  1. Prior attempts at query-side index reuse often relied on loose heuristics (like basic cosine similarity) or uniform fixed-period grouping, which either fail to catch catastrophic "corner cases" or forfeit potential FLOPS savings. RIX solves this by deriving a highly rigorous, closed-form divergence metric under a uniform spherical key model (using a von Mises–Fisher formulation). By successfully introducing the mixture correction term, the metric mathematically binds head-weight and norm drift at large anchor ages. This allows the system to accurately evaluate reuse safety with an exceptionally low O(Hd) compute footprint—completely bypassing the need to read cached keys or materialize expensive score rows. It transforms query-level reuse from a risky heuristic into a mathematically verifiable operation.

  2. A common pitfall for theoretical deep learning papers is proposing elegant mathematics that prove too slow or ragged for actual hardware deployment. RIX stands out by enforcing absolute alignment across the entire stack: the mathematical constraints dictate the indexer’s architectural primitives (exp activation, unparameterized key norm), the training objective enforces metric calibration via a Huber loss, and the inference logic implements custom fused Triton/TileLang kernels. Furthermore, the authors recognized that a sequential greedy scheduler would bottleneck GPU prefill latency, and elegantly solved it by building a parallelized binary-lifting scheduler. Demonstrating an end-to-end wall-clock speedup of ~9× at 1M context on a production-ready stack proves the method's immediate, practical utility for scaling long-context LLM deployment.

Critical weaknesses
  1. The indexer architecture is highly constrained and tightly coupled (lacking generalizability).
  2. Heavy reliance on a limited "indexing budget" (acceleration gains vanish rapidly with larger top-k values).
Questions for authors
  1. The closed-form reusability metric is derived by assuming that the indexer keys follow a uniform distribution on a sphere (von Mises–Fisher law). How robust is this metric when real-world key clouds exhibit severe clustering or high anisotropic behavior? To what extent does the learned per-layer scale correction successfully mitigate the gap between the uniform assumption and actual empirical token distributions?

  2. The end-to-end acceleration of RIX is highly sensitive to the index budget (Siz), where the performance advantage degrades sharply or even reverses when Siz > 4096. For downstream tasks that fundamentally demand high retrieval precision and larger key capacities (e.g., repository-level code reasoning), how can RIX bypass this "budget trap" without letting dense sparse attention dominate the wall-clock execution time?

2 comments
AuthorsOpenReview ↗

Reply to reviewer zuak

We thank the reviewer for the thoughtful questions.

Generalization. Rix reuses the open-source DSA-style indexer rather than introducing a new indexing stack. The modification is small: ∑hwhReLU⁡(sh)\sum_h w_h\operatorname{ReLU}(s_h) becomes ∑hsoftplus⁡(wh)exp⁡(sh)\sum_h\operatorname{softplus}(w_h)\exp(s_h), together with fixed key normalization. These changes align the existing indexer with the closed-form metric while preserving its learned-indexer structure. The same recipe works on both GQA-based Qwen3 and MLA-based KimiLinear backbones (Table 2), supporting its generalization across attention architectures.

Distribution assumption. The uniform sphere is an analytical prior, not an assumption that real keys are uniform. Still, the proposed modeling reflects real distribution and is further improved through calibration training. The uncalibrated checkpoint shows a log-linear relation between the proposed score and realized reuse KL on held-out training data, RULER, and LongBench (R2=0.46R^2=0.46–0.550.55 after the same per-layer affine fit). Calibration training w/o stop-gradient strengthens this relation substantially (R2=0.83R^2=0.83–0.880.88; Appendix D.8). Thus, the analytical metric already provides a useful signal, while calibration adapts it to empirical key distributions. Inference remains key-agnostic.

For every checkpoint and layer, we independently fit ln⁡KLoracle=βln⁡s+c\ln \mathrm{KL}_{\mathrm{oracle}}=\beta\ln s+c and evaluate on disjoint held-out samples. The resulting R2R^2 / log-KL RMSE (nats) values are:

CheckpointTraining distributionRULERLongBench
Uncalibrated + affine fit0.460 / 0.5590.539 / 0.4760.545 / 0.547
w/ stop-gradient + affine fit0.484 / 0.5460.563 / 0.4640.556 / 0.538
w/o stop-gradient + affine fit0.827 / 0.3160.873 / 0.2500.877 / 0.283

All domains use anchor offsets 1–4. Calibration w/o stop-gradient gives the best fit on every domain, while w/ stop-gradient also improves over the uncalibrated checkpoint. Since the oracle-target constructions differ across domains, these results compare checkpoints within each domain, not absolute values across domains. See figure 5 in the revised paper.

Index budget. Sparse-attention cost and reuse-based indexer acceleration are separate. Top-kk selection, KV gathering, and gathered attention are costs of the sparse-attention backbone. Rix instead skips fresh indexer computation at reused queries and passes the existing index plan to them; this saving does not disappear as kk increases. The dense-versus-sparse end-to-end ratio can nevertheless decrease because the backbone's budget-dependent attention cost grows. For example, Qwen3-32B prefill at 128k remains 1.66×1.66\times faster than dense at k=4096k=4096 (Appendix E). Improvements to large-kk sparse attention are therefore orthogonal and can be combined with Rix.

Thank you for your response. I will maintain my positive score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.