- 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:
-
Unified error analysis. Existing positive random-feature methods (FAVOR+, FAVOR++, FAVOR#) are described in one coverage-based framework.
-
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.
-
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
-
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.
-
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
- 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.
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 Jo 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=256 and d=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.