acceptodds
Under review as a conference paper at ICLR 2027

GMPROP: A LEARNED IMPORTANCE-SAMPLING PROPOSAL FOR PRF ATTENTION

Abstract

Softmax attention is powerful but expensive: its cost grows quadratically with sequence length. Positive random features (PRF) can approximate softmax attention and reduce its computational cost to linear time. To date, most methods used a standard normal distribution to sample random features. However, such an approach may poorly reflect the query and key distribution of a pretrained Transformer and therefore require many features for good accuracy. In this work we introduce GMProp. GMProp learns a sampling distribution from which the PRF are sampled. It represents the sampling distribution as a small mixture of Gaussians learned offline from the model’s query and key representations. At inference time, no fine-tuning or input-dependent optimization is required: the resulting method has the same linear-time attention computation as standard PRF attention and keeps its constant cost per generated token. Importance weights keep the kernel estimate unbiased for any learned proposal and any number of features. We provide theoretical justification for the design of GMProp and provide a thorough empirical investigation of the method. Across three pretrained language models, GMProp consistently improves over existing PRF baselines, and the learned proposals continue to perform well on a held-out corpus without being refit.

Primary area:
foundation or frontier models, including LLMs
Keywords:
natural language processing, computational linguistics, softmax attention, efficient attention, approximation algorithms, transformer theory

Reviews

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

This paper proposes GMProp, a learned importance-sampling distribution for positive random-feature attention. It fits a Gaussian mixture to each attention head while keeping the pretrained model weights frozen. An additional learned coordinate transformation preserves query–key inner products while improving approximation quality. Importance weighting maintains an unbiased kernel estimator, and the fixed sampling distribution supports linear-time prefill and constant-state decoding.

Critical strengths
  1. The method adapts random-feature sampling to pretrained models for kernel approximation.

  2. The paper provides a theoretical characterization of the variance-optimal proposal and motivates the Gaussian mixture approximation.

  3. The proposed method consistently improves over the evaluated PRF baselines.

Critical weaknesses
  1. The quality gap to exact attention remains substantial. Despite improvements over PRF baselines, the paper does not demonstrate a configuration that adequately preserves model quality.

  2. Quality evaluation is limited to models up to 1B parameters and contexts of at most 512 tokens. There are no long-context retrieval or generation evaluations, leaving it unclear whether the learned proposals remain effective as context length increases.

  3. The accuracy-efficiency trade-off is not practical. The cost experiments mainly use 256 features at a sequence length of 2K, where quality degradation is already substantial.

The results support an improvement in random-feature approximation, but it is not a useful attention replacement for pretrained models.

Questions for authors

please see weakness

Reviewer_oyUdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes GMProp, a learned sampling distribution for positive-random-feature (PRF) attention in frozen pretrained language models. Instead of drawing features from a standard normal, each head draws them from a mixture of Gaussians learned offline, and every draw is reweighted by its importance weight, so the kernel estimate stays unbiased. A learned "input gauge" transforms queries and keys without changing their dot products, so that a few mixture components can cover them. The mixtures are fit on the first layer's kernel error or on the frozen model's next-token loss, without updating the model's weights. The method is evaluated on Pythia-70M, Pythia-410M and OLMo-1B with contexts of up to 512 tokens, and the paper claims consistent gains over five training-free PRF baselines at the same linear-time cost.

Critical strengths
  1. Clear gains at equal inference cost: With the same number of features and about the same attention cost as FAVOR+ and its coupled variants (Table 12), GMProp lowers the next-token loss on all three models, and it also beats FAVOR#, which re-solves its features for every input. The margins are large: with 16 features, GMProp reaches a lower next-token loss than every baseline with 4096 features (Table 8). Learning the sampling distribution offline is therefore a real improvement within the random-feature family, and it leaves the pretrained weights untouched.
Critical weaknesses
  1. Tested only at short contexts: Every quality result uses contexts of at most 512 tokens (l.336), although the paper runs the same models at 2048 tokens to measure cost (Table 12). At this length no setting comes close to exact attention. Even with 4096 features, Pythia-410M running GMProp has a higher next-token loss than the smaller Pythia-70M with exact attention on the same test data (Table 8). Short contexts are where exact attention is affordable, so the paper shows no setting where the trade-off pays off. Long contexts are where linear attention is needed, and also where a fixed-size approximation is most at risk, but they are never tested.
  2. Only GMProp is trained: Every baseline is training-free (l.1840), while the GMProp proposals of Table 2 are trained by backpropagating the frozen model's next-token loss (App. G, Table 11). The rule for admitting baselines (l.342-345) excludes the methods that spend such a budget on a frozen model, such as learned feature maps fit to the frozen attention (e.g., the first stage of LoLCATs, which the paper describes in App. I). The rule requires an unbiased kernel estimate, but the paper never measures whether that helps the attention output. So the comparison shows that a trained proposal beats untrained ones, not that it beats other uses of the same training.
Questions for authors
  1. [Experiment] Please compare with a learned feature map trained on the frozen model with a similar budget and feature count, such as the attention-transfer stage of LoLCATs, and report its next-token loss next to Table 2.

  2. [Experiment] Please train the same mixture and gauge on the next-token loss without the importance weight. This tests whether the unbiased kernel estimate, the basis of the baseline selection, helps the attention output.

  3. [Experiment] Please report next-token loss and a long-context retrieval test (e.g., passkey) at 2048 tokens, the length used for the cost measurements, with the proposals fit at 512 tokens.

Reviewer_2ecfOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper proposes Gaussian Mixture Proposal (GMProp), a learned importance-sampling distribution for positive random-feature (PRF) attention with the pretrained language-model weights fixed. Specifically, GMProp draws random features from a per-head Gaussian mixture with deterministic per-component sample counts and reweights each draw by its importance weight so that the softmax kernel estimator remains unbiased. Moreover, a learned invertible linear transformation, called the input gauge, transforms queries and keys while preserving their inner products. The authors characterize the variance-optimal proposal distribution theoretically and evaluate log-kernel mean squared error (MSE), next-token cross-entropy (CE), cross-corpus transfer, and inference latency across Pythia-70M, Pythia-410M, OLMo-1B, and SmolLM3-3B.

Critical strengths
  1. Learning the feature-sampling distribution while keeping the pretrained model weights fixed is a clean design. Because the importance weights preserve kernel unbiasedness for any positive component counts, a single trained proposal can be evaluated across different feature budgets mm without retraining.

  2. GMProp consistently lowers log-kernel MSE and next-token CE relative to existing unbiased PRF baselines across all tested models (Tables 1 and 2). Furthermore, proposals trained on each model's pretraining mixture maintain this accuracy advantage on the United Nations Parallel Corpus without refitting (Tables 7 and 8).

Critical weaknesses
  1. [Resolved in revision] In the initial submission, the mixture-weight update was not the exact gradient of the training objective because detaching the sampled component omitted the derivative of its sampling probability. In the revised manuscript, the authors modified the estimator to assign a fixed draw count nc=max⁡(1,round(mλc))n_c = \max(1, \mathrm{round}(m\lambda_c)) to each component cc (Section 3.2, Equations 8 and 9). Consequently, no component index is sampled, and the pathwise gradient with respect to the mixing-coefficient logits ν\nu is exact outside a tie set of measure zero (Section 3.5, Equation 17, and Appendix B). All GMProp results were retrained with this exact gradient, and the ablation in Appendix J.3 (Table 11) confirms that training the mixing coefficients reduces test CE by 0.012 to 0.036 nats on SmolLM3-3B.
  2. [Addressed in revision] In the initial submission, the runtime comparison charged FAVOR++ and FAVOR# for materializing the full L×LL \times L attention matrix, and quality evaluations were limited to 512 tokens where exact attention is faster and far more accurate. In the revision, Appendices H.3 and H.4 (Figures 2 and 3) benchmark FAVOR++ and FAVOR# on the same fused Flash Linear Attention (FLA) Triton prefix-sum kernels as GMProp. Under matched bfloat16 settings on SmolLM3-3B up to 65,536 tokens (Section 4.5, Figure 1, and Tables 11 and 12), GMProp achieves 3.1 to 4.0 nats lower test CE than FAVOR# while running 1.32 times faster than FlashAttention-3 at 65,536 tokens (10,958 versus 14,421 ms at batch size 8). In addition, Appendix K shows that low-rank adaptation (LoRA) narrows the CE gap to exact attention to 1.6 nats (Table 14), and training Pythia-70M and Pythia-410M from scratch narrows the gap to 0.19 and 0.15 nats at m=256m = 256 (Tables 15 and 16). A remaining limitation is that drop-in PRF estimators with fixed model weights still fail on exact passkey retrieval (0 of 30 prompts in Table 13).
Questions for authors
  1. How do the results change when the mixing coefficients are held fixed or trained with an exact gradient, and does the runtime advantage over FAVOR++ and FAVOR# hold when both baselines use factored attention under matched settings? [Answered in Section 3.5, Section 4.5, Appendix H, and Appendix J.]

  2. In the initial Appendix C, the text stated A−⊤=OBA^{-\top} = OB and then wrote A=B−⊤O⊤A = B^{-\top}O^\top instead of A=OB−⊤A = OB^{-\top}. Was this a typographical error or an implementation bug? [Resolved in Appendix C, Equation 44: confirmed as a typographical error and corrected to A=ΠB−⊤A = \Pi B^{-\top}.]

Comments on the paper

4 comments
AuthorsOpenReview ↗

Summary of the revision

Since our first revision, the revised PDF adds the experiments we committed to and makes these changes:

Training with GMProp (2ecf, oyUd, nsQh). New Appendix K, summarized in Section 4.2. Low-rank adapters on Pythia-410M and OLMo-1B with each estimator in place (Appendix K.1, Table 14), and the architectures of Pythia-70M and Pythia-410M trained from scratch with exact attention and with each estimator, under the same recipe (Appendix K.2, Tables 15 and 16).

Training without the importance weight (oyUd). Appendix K.3: the mixtures of Table 2 trained without the weight, with the model frozen (Table 17) and with Pythia-70M from scratch (Table 18), the kernel the estimate then converges to (Eq. 55), and its relation to KL-Transformer and DARKFormer (Table 19).

Baseline details. Section 4 corrects which FAVOR# variant its authors used in their experiments and explains why we run SDERF. Appendix G states that FAVOR# is re-solved under a stop-gradient during training, and that the FAVOR++ and FAVOR# solves leave out the attention-sink key. The caption of Table 3 states that decode costs are derived for each method as published.

Presentation. The abstract, introduction and conclusion are rewritten. The introduction now states the cost of refitting the sampling distribution at inference and in training, and summarizes the results.

The Pythia-410M run with FAVOR# is still training, and we will post its result as soon as it ends.

AuthorsOpenReview ↗

Summary of the revision

This revision completes the comparison at the size of Pythia-410M with the FAVOR# run, which our previous revision reported as still training.

  • Table 16: FAVOR#'s validation cross-entropy to the end of training, and its test cross-entropy at m = 16, 256 and 4096: 3.42, 2.93 and 2.95.
  • Appendix K.2: FAVOR# ties GMProp at m = 256 and 4096 and trails it by 0.29 nats at m = 16. On the same GPU it took 136 hours to train, against 70 for FAVOR+ and 57 for GMProp. The Pythia-70M training times are not compared, since those runs used different GPUs.
  • Section 4.2: the note that this run was still training is replaced by its training time, 2.4 times that of GMProp.

Thank you for the additional experiments and the detailed answers. As a drop-in, GMProp improves on the other random-feature methods, but most of the lead disappears when every estimator is trained, and it shares their main limitations. So I keep my rating.

Long contexts. The main problem is retrieval: in the passkey test, every random-feature method tested fails to retrieve the key, even at 512 tokens, the length GMProp's proposal was fit at, while exact attention answers every prompt (Table 13). GMProp's loss also rises outside the fitted positions: in the position-shift test of Appendix J.5, on the same 512-token contexts, it more than doubles while that of exact attention is unchanged. In my view, without long-range retrieval the method offers little beyond local attention, which keeps its perplexity roughly constant as the context grows.

Training budget. When every estimator is trained from scratch, GMProp and FAVOR# are within 0.02 nats at 256 features on both model sizes (Tables 15 and 16), against a drop-in lead of 1.0 to 2.3 nats. This suggests that most of the drop-in margin comes from training only GMProp. With the gauge, Table 17 also suggests that the importance weight does not help at the feature counts tested.

Credit. GMProp leads FAVOR# at 16 features in both from-scratch runs, and at the size of Pythia-410M it trains 2.4 times faster. I credit these as real results.

Thank you for the careful reading, and for crediting the results at 16 features and the training cost. We agree that retrieval is out of reach for every random-feature estimator we tested, as Appendix J.5 states, including GMProp, whose proposal there was trained on the next-token cross-entropy rather than for retrieval.

On the training budget, we agree that most of the quality lead at 256 features disappears when every estimator is trained, but we read the reason differently. A model trained with an estimator adapts to it, as Table 14 shows for the adapters, which move the model toward its estimator and away from its own attention. Trained from scratch, the model can adapt fully, so the choice of estimator matters much less there, while the drop-in setting measures how well each estimator fits a model that cannot adapt.

We would add that GMProp keeps a lead in cost when every estimator is trained. FAVOR# refits its sampling distribution for every input, so it trained 2.4 times slower than GMProp, as you note, and its forward on SmolLM3-3B is 1.4 to 5.6 times slower (Table 12). In decoding on OLMo-1B, FAVOR++ and FAVOR# take 0.13 to 1.3 s per token, against less than 8 ms for GMProp (Figure 3), which runs at the inference cost of FAVOR+.

We agree that the importance weight does not lower the loss at the feature counts tested. What the weight buys is consistency. With it, the loss keeps falling toward that of exact attention as mm grows, while without it the loss flattens toward that of another attention, 1.6 nats above exact attention on Pythia-70M (Table 17). Trained from scratch without the weight, the model scores 8.51 nats under exact attention, against 4.31 with it (Table 18).

Thank you again for engaging so closely throughout the discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.