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

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).