acceptodds
Under review as a conference paper at ICLR 2027

From Proposal Coverage to MINT: A Unified Analysis of Random-Feature Softmax Attention

Abstract

Efficient softmax approximation is important across deep learning, particularly for computing attention in large language models. Random-feature methods approximate softmax attention at linear cost, but can miss regions that contribute strongly to query–key interactions. Reducing kernel error or large-sample output variance need not reduce output error at a fixed feature count. We unify standard positive features and their geometry-adapted variants by relating kernel error to proposal coverage: how well sampling covers contributing regions. Attention normalizes these kernel estimates before combining values, so output error depends on changes in relative weights and differences between values. Following these errors through both operations yields an exact expression for expected squared output error at a fixed feature count under independent sampling. This leads to Mixture Importance-Tilted random features (MINT), which cover multiple contributing regions with a Gaussian mixture. MINT# additionally adapts the component shapes. Mixture weights are fitted using a numerical approximation of this expected squared output error at the chosen feature count. Importance correction preserves the softmax kernel in expectation. With component locations and shapes fixed, this weight calibration reduces output error compared with calibration based on coverage or large-sample output variance. At matched feature counts, MINT and MINT# improve next-token accuracy by 4.14–7.44 and 2.86–5.37 percentage points, respectively, over FAVOR# when replacing 25% of Qwen3-4B-Base's query heads. On OLMo 3, MINT# lowers mean error relative to FAVOR# in all 15 attention, logit, and decoding comparisons using six fixed heads. Code at: [https://anonymous.4open.science/r/mint-submission](https://anonymous.4open.science/r/mint-submission).

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Linear attention, random features, self-normalized importance sampling, proposal coverage, finite-budget output risk, proposal calibration

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_2VJyOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The authors study random-feature approximations of softmax attention, which reach linear cost by estimating the softmax kernel from a finite number of sampled features. They consider this as importance sampling: the estimate is accurate only if the sampling distribution covers the regions that contribute most to query-key interactions. Extending this view from single query-key pairs to full attention rows, they show that kernel or normalizer does not determine output accuracy. They use an exact expression for the expected output error and based on this analysis they propose:

  1. Unified error analysis. Existing positive random-feature methods (FAVOR+, FAVOR++, FAVOR#) are described in one coverage-based framework.

  2. The features that are sampled from a fixed Gaussian mixture whose components are placed where query-key contributions concentrate. Mixture weights are tuned to minimize the expected output error at the target feature count.

  3. Experiments. When 25% of the query heads of Qwen3-4B-Base are replaced, MINT and MINT# improve next-token accuracy over FAVOR# by up to 7.4 and 5.4 percentage points, although both remain well below exact softmax attention. On selected OLMo 3 7B heads, MINT# reduces output and logit errors relative to FAVOR# in all tested settings. An ablation shows that the proposed weight calibration outperforms simpler calibration criteria.

Critical strengths
  1. Clear theoretical structure and justification. The authors provide a well-motivated calibration criterion, and the controlled ablation (Table 3), where only the mixture weights change, shows that it reduces output error compared with simpler criteria.

  2. Practical compatibility with modern LLMs. Because the mixture proposal is calibrated once and shared across inputs, MINT keeps the inference cost of FAVOR-style methods, supports causal attention and KV-cache decoding, and requires no fine-tuning.

Critical weaknesses
  1. Despite applicability of the framework, the practical significance is poor. The apporximation seems to be far from the usable without further training. Also there is lack of comparison with the post-hoc linearization (e.g., Hedgehog, LoLCATs).
Questions for authors

Additional experiments. Could you show whether MINT provides a better starting point than FAVOR# for a short fine-tuning stage? It would also help to report accuracy as a function of the fraction of replaced heads, together with wall-clock time and memory at long context lengths.

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

This paper studies random-feature approximations of softmax attention from the perspective of proposal coverage and finite-budget output error. It derives error bounds and an exact expression for expected squared attention-output error under independent sampling. Based on this analysis, the authors propose MINT and MINT#, which use Gaussian mixture proposals and output-aware weight calibration to improve approximation quality. Experiments on synthetic data and pretrained language models show consistent improvements over FAVOR baselines at matched feature budgets.

Critical strengths
  1. The paper goes beyond kernel approximation error by explicitly considering attention normalization and value aggregation.
  2. MINT and MINT# consistently outperform the FAVOR baselines in the reported LLM experiments.
Critical weaknesses
  1. The LLM evaluations only replace 25% of the query heads in Qwen and six selected heads in OLMo. Even with partial replacement, a substantial gap remains relative to exact softmax attention. For example, at M = 1024, MINT achieves a perplexity of 46.73 versus 12.23 for exact attention (Table 4). Moreover, no measured inference latency or throughput is reported. These limitations make it difficult to assess the practical significance of the improvements.
  2. The connection between importance sampling and attention-output variance has already been explored in RA/LARA [1], while the exact finite-sample risk formulation builds on established self-normalized estimation techniques. Although the proposed calibration improves over several analytical objectives, Appendix E.5 (Table 9) shows no statistically significant improvement over direct validation-based candidate selection. Furthermore, the exact risk analysis assumes iid sampling, whereas the main LLM experiments use ORF. The distinct practical benefit of the finite-budget formulation is therefore not fully established.

[1] Linear complexity randomized self-attention mechanism. ICML 2022.

Questions for authors
  1. Can the authors provide results with a larger fraction of attention heads replaced, together with measured inference latency and memory usage? This would help determine whether the method offers a useful accuracy-efficiency trade-off beyond the current partial-replacement setting.
  2. How much of the improvement comes specifically from continuous finite-budget risk optimization rather than the initial proposal candidates or direct validation-based selection? Can this comparison be made under matched calibration costs and the ORF sampling scheme used in the main experiments?
Reviewer_oQJiOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper connects proposal coverage to the output error of random-feature softmax attention after normalization and value aggregation. It derives an exact finite-budget risk expression for iid sampling and uses its numerical approximation to calibrate Gaussian-mixture proposals, MINT and MINT#. Synthetic tests examine the analysis; partial-head replacements in Qwen and OLMo improve on FAVOR baselines, while fixed-geometry experiments examine weight calibration.

Critical strengths
  1. The analysis follows errors through normalization and value aggregation and provides an exact finite-budget risk that can guide calibration. This connection is useful: it explains why kernel variance can be a poor design target and gives MINT an objective tied to attention outputs.
  2. With geometry fixed, mean test errors averaged over six OLMo heads improve against pairwise, normalizer, KL and asymptotic objectives for both families at three budgets under iid sampling. Gains over normalizer and KL fitting also persist with ORF, supporting the overall calibration procedure.
Critical weaknesses

The benefit of continuous optimization beyond candidate selection is unclear. Optimization starts from the best of nine candidates under pilot risk. Against selection by validation output error from the same set, four of six mean-error comparisons improve under independent sampling, but all six pointwise 95% intervals include zero. Refinement lowers independent-bank calibration error relative to initialization in 23/36 fits; its additional ORF test benefit is unreported.

Questions for authors
  1. How much of the LLM improvement requires multiple centers? On the existing six OLMo heads at M=256, compare plain MINT with R=1,4,16 using the existing calibration procedure, keeping unit covariance, calibration/test data and base random draws fixed. Report relative attention MSE and gains over FAVOR# to distinguish a shared proposal shift from the additional benefit of multiple centers.
  2. Does continuous optimization improve ORF deployment? At M=256 on the same six OLMo heads, compare selection among the nine candidates by ORF validation error, initialization by pilot risk, and the optimized weights, holding geometry fixed. Reuse the validation/test split, evaluate on independent paired ORF test banks, and report relative MSE plus calibration time and memory.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised PDF: Summary of Changes

We thank the reviewers again for their constructive feedback. We have uploaded a revised PDF that incorporates the changes we committed to during the discussion, together with the new results reported there. The main text adds Sections 5.5, 5.6 and 6, the new proof and results are in App. A.4, F and G, and the table, section and appendix numbers cited in our earlier responses are unchanged.

1. Risk-based selection is now the default calibration (oQJi, qaYP)

Section 4.2, Algorithm 1 and App. C.2 now present selecting, among the nine candidate weight vectors, the one with the lowest finite-budget risk as the default calibration, with continuous refinement as an optional step; the protocol (Sec. 5.1) states that the main LLM comparisons include this optional step. App. F.1 (Table 10) compares the three strategies under ORF together with their calibration time and memory. Section 5.4 adds that the finite-budget risk, estimated on an independent pilot, ranks the nine candidates with mean Spearman correlation 0.850, versus 0.476 for JoJ_o and 0.406 for the pairwise criterion.

2. Exact finite-budget risk under ORF (qaYP)

The new App. A.4 proves the exact risk for feature banks made of independent blocks with arbitrary dependence inside each block (Theorem 2). Lemma 2 shows that the Gaussian-marginal ORF sampler used in all our LLM experiments, with mixture components and MINT#'s shared covariance, satisfies this assumption, and Corollary 1 gives the formulas for complete and partial blocks; at M=256M=256 and d=128d=128, a bank consists of two independent blocks. The abstract, introduction, Sec. 3.3 and conclusion now state the exact risk for both iid features and ORF. Calibration still uses the iid objective, as stated in our response.

3. New Limitations section (qaYP, 2VJy)

Section 6 states that, without training, MINT does not reach exact-attention quality and every random-feature method struggles when all heads are replaced, although MINT stays ahead of FAVOR#. It also reports the memory of our FP64 prototype at 256k tokens (5.3–12.2× FlashAttention's, App. F.3), whose overhead comes from implementation choices; the FP32 core in App. F.4 supports lower-precision computation.

4. Comparison with LoLCATs and the window baselines (2VJy)

The new Sec. 5.5 and App. G (Tables 14 and 15) compare all methods under the identical LoRA stage, including the window-only and FAVOR# + window baselines, and frame the comparison with LoLCATs as 2VJy suggested: at the same window, MINT features improve on window-only attention, FAVOR# features are neutral, and LoLCATs' learned features fall below window-only attention on PG-19. We note that PG-19 is out of domain for the WikiText LoRA stage, where learned features remain stronger. The paper uses 128 features, the state size of LoLCATs and Hedgehog: MINT + window lowers cross-entropy by 0.0213 nats relative to window-only, closing 14.9% of window-only attention's gap to exact attention; App. G also reports 256 features, as in our response (0.0224 nats, 15.7%). App. G further reports the comparison with Hedgehog at equal state size, where MINT matches Hedgehog without feature transfer.

5. Other results from the discussion (qaYP, 2VJy)

App. F collects the remaining new results: higher replacement fractions (F.2; Table A of our General Response), latency and memory (F.3; Table B, now with all eight lengths from 2k to 256k tokens), the FP32 core with BF16/FP16 interfaces (F.4), and the decoding state compared with the KV cache under grouped-query attention (F.5). Section 5.6 summarizes the prefill measurements. The introduction and related work now also discuss LARA's heuristic weights, Hedgehog, and mixture importance sampling (Elvira et al., 2019; Cappé et al., 2008).

The supplementary material has been updated with the data and scripts for the new tables.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.