acceptodds
Under review as a conference paper at ICLR 2027

Transformers Can Implement Preconditioned Richardson Iteration for In-Context Gaussian Kernel Regression

Abstract

Mechanistic studies of in-context learning (ICL) have connected transformer computations to iterative optimization algorithms for linear regression and related tasks, often using linear or ReLU attention variants. For nonlinear ICL, prior work has related softmax and kernelized attention to functional gradient descent, but it remains unclear whether a standard transformer with softmax attention can implement a convergent solver with an end-to-end prediction-error guarantee. In this paper, we study in-context kernel ridge regression (KRR) with Gaussian kernels and show, both theoretically and empirically, that a standard softmax-attention transformer can approximate the KRR predictor during its forward pass. Under bounded-data assumptions, we construct a single-head transformer whose forward pass approximately implements preconditioned Richardson iteration on the associated kernel system. The construction uses blocks and MLP width to achieve -accurate prediction for prompts of length . Our construction reveals a functional decomposition within the transformer architecture: softmax attention produces a row-normalized Gaussian-kernel operator needed for cross-token interactions, while MLP layers act locally to approximate the intra-token scalar arithmetic required by the update. Empirically, we train GPT-2-style transformers on Gaussian-process regression tasks and observe that they progressively align with the exact Gaussian KRR estimator across depth in terms of both prediction error and induced weights, with ablations further supporting this trend. Comparisons with classical KRR solvers also show that deeper layers align with later solver iterates. Together, we empirically demonstrate that the pretrained transformers exhibit progressive refinement toward exact Gaussian KRR across depth, and theoretically establish inexact preconditioned Richardson iteration as a concrete mechanism for approximating this predictor within an explicitly constructed softmax-attention transformer.

Primary area:
learning theory
Keywords:
In-context learning, transformers, kernel ridge regression, softmax attention, preconditioned Richardson iteration

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_mek8OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the representational power of Transformer models in nonlinear in-context learning tasks. Specifically, the paper shows that Transformers can solve Gaussian-kernel ridge regression with an explicit construction that approximates a pre-conditioned Richardson iteration. This construction shows that the accuracy of the resulting Transformer model scales with the MLP hidden width dd on the order of 1/d21/d^2 and the number of layers LL on the order of exp⁡(−L)\exp(-L). The paper concludes with empirical study that directly trains a GPT-2 style model on the Gaussian-kernel ridge regression task and demonstrates that the theoretical finding can translate to a more practical setting.

Critical strengths

I find this paper well-written and enjoyable to read. The notations are clean and the main theorem statement is easy to understand.

The technical contributions of this paper is somewhat reasonable for a premier conference paper (albeit at the lower end of the spectrum) , as it contributes to the understanding of the standard softmax attention without attaching restrictive assumptions. The results of this work clearly demonstrated the interplay between the softmax activation and MLP layers in enabling a nonlinear in-context learning task.

Critical weaknesses

While I don’t think there are any fatal issues with this paper, there are a places where there is some room for improvement.

I feel that the proof outline given in Appendix C.1 should be moved to the main text. That part of proof has a lot of details that would be helpful for the readers’ understanding.

  • The definitions of softmax on lines 77 and 195 do not match. I think they are equivalent if the norm features ∥xi∥2\| x_i \|^2 are included. So, the discussion about this augmentation (on line 254) should be brought forward and displayed more prominently.

  • The attention masks are not specified in the main text. There should be a short discussion in the main text emphasizing that they are non-causal and only used to mask out the dummy and test tokens.

  • The construction is far from economical and quite wasteful, where about half of the attention layers would have to be zeroed out if the construction is put into the standard Transformer blocks consisting of alternating attention and MLP blocks. I would be interested to see if the authors could provide some concrete evidence or justification for such choices.

  • The proof is heavily tied to the correspondence between the Gaussian kernel and the softmax function. I am interested in seeing if the work could be extended to more general classes of kernels.

  • While the results are fairly interesting, the technical principles in this paper seem to be heavily borrowed from Bai et al (Neurips 2023). In light of this, I think it is most appropriate to recommend a weak accept.

Questions for authors

I posed my questions as points in the above section.

4 comments

We thank the reviewer for the careful reading and the positive assessment. We have revised the draft to address the concerns below. The revisions in the draft are marked in red.

W0: Proof outline

I feel that the proof outline given in Appendix C.1 should be moved to the main text. That part of proof has a lot of details that would be helpful for the readers’ understanding.

We added further details from Appendix C.1 to the construction overview after the theorem in Section 4 (lines 292--303). We hope these additions help readers understand the construction while keeping the main text concise. We welcome the reviewer’s feedback on whether the added details are sufficient.

W1: Softmax attention and squared-norm features

The definitions of softmax on lines 77 and 195 do not match. I think they are equivalent if the norm features ∣xi∣2|x_i|^2 are included. So, the discussion about this augmentation (on line 254) should be brought forward and displayed more prominently.

Definition 1 (lines 189--196) gives the formal definition of softmax attention. The expression in the introduction is a special case in which softmax normalization yields the row-normalized Gaussian kernel matrix. We now state explicitly that this specialization uses squared-norm features and suitable query and key matrices (Introduction, lines 73--76).

W2: Attention masks

The attention masks are not specified in the main text. There should be a short discussion in the main text emphasizing that they are non-causal and only used to mask out the dummy and test tokens.

We added the mask description to Section 4 (lines 293--294). The construction uses noncausal masks that exclude only dummy or test tokens, or both.

W3: Economy of the construction

The construction is far from economical and quite wasteful, where about half of the attention layers would have to be zeroed out if the construction is put into the standard Transformer blocks consisting of alternating attention and MLP blocks. I would be interested to see if the authors could provide some concrete evidence or justification for such choices.

We thank the reviewer for this question. Our MLP uses two linear maps with one ReLU activation layer, which follows the standard transformer feedforward structure.

In our staged construction, some computations take the output of an earlier MLP as their input. Since we retain one hidden layer per MLP, we implement these dependent operations in separate transformer blocks. The additional stages need no further interaction between tokens, so we use MLP-only blocks.

We believe that deeper MLPs could combine some stages into fewer blocks. In this work, we retain one hidden ReLU layer per MLP to follow the standard transformer feedforward structure. Our main goal is to establish an approximation guarantee within this architecture and explain the separate roles of attention and MLP layers. We agree that more economical constructions within the same architecture may be possible.

W4: Other kernels

The proof is heavily tied to the correspondence between the Gaussian kernel and the softmax function. I am interested in seeing if the work could be extended to more general classes of kernels.

We thank the reviewer for this suggestion and agree that extending the result to other kernels would be valuable. We chose the Gaussian kernel because its close connection to softmax allows us to give an explicit construction. We believe that a similar approach may work for exponential dot-product kernels. For more general continuous kernels, it may be worth exploring whether approximating these kernels with Gaussian basis functions by multiple attention heads could help extend our softmax construction. The feasibility of this approach and its effect on the final KRR prediction would need further analysis.

W5: Relation to Bai et al. (2023)

While the results are fairly interesting, the technical principles in this paper seem to be heavily borrowed from Bai et al (Neurips 2023). In light of this, I think it is most appropriate to recommend a weak accept.

We agree that both papers use explicit transformer constructions, but there are several important design differences. Bai et al.’s linear-regression constructions use ReLU attention, whereas we use standard softmax attention for Gaussian KRR.

Their general gradient construction implements ReLU approximation terms through attention heads. Our construction uses one softmax attention head and controls scalar approximation accuracy through MLP width. This choice is motivated by practical architectures with relatively few heads but wide MLPs (for example, 8 heads and MLP width 1024 in our experiments).

In our construction, using MLPs for tokenwise approximation lets us reduce the required arithmetic to approximations of smooth one-dimensional functions (the square, reciprocal, and x/(1−x)x/(1-x)). Explicit linear splines then achieve error δ\delta with MLP width O(δ−1/2)O(\delta^{-1/2}) on fixed intervals. Bai et al.’s general bound for multivariate smooth functions yields a sufficient ReLU-attention head count of O(δ−2log⁡(1/δ))O(\delta^{-2}\log(1/\delta)) in their general gradient construction.

Bai et al.’s linear-regression construction uses an attention-only transformer to implement exact gradient steps. Our Gaussian KRR construction uses both attention and MLP layers, making their complementary roles explicit in implementing inexact preconditioned Richardson updates.

In addition to these theoretical distinctions, we would like to emphasize that the experimental study is a second main contribution. Our theory establishes that transformers can approximate Gaussian KRR. The experiments address the complementary question of whether and how KRR behavior emerges in GPT-2-style models trained without a prescribed solver. Studying both predictions and induced weights across depth helps reveal how this agreement develops, while the controls help assess whether it reflects the learned model’s behavior.

We hope the reviewer will consider both the theoretical and experimental contributions in the overall assessment of the paper.


Reference

Bai et al. (2023). Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection. NeurIPS.


We sincerely appreciate your constructive comments, which have helped us improve our work. If our responses have addressed your concerns, we would appreciate it if you could revisit your assessment in light of these updates, and we welcome any further questions or feedback.

Thank you for your explanations. I will maintain my score.

Thank you for your comments. I will maintain my score.

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

This paper investigates whether transformer can solve in-context kernel ridge regression with Gaussian kernels. Specifically, this paper train a GPT-2 style transformer on Gaussian-process regression tasks, and try to study whether the prediction error is close to the oracle estimator and whether the learned algorithm can be interpreted as an iterative algorithm. The empirical results show that transformer progressively aligns with the Gaussian KRR estimator along with the the depth increase. The mechanism of the learned transformer is also be interpreted as an preconditioned Richardson iteration.

Critical strengths
  • The paper is well-constructed and provides the clear, comprehensive empirical and theoretical proofs and explanations about the the framework.
  • The experiments of this paper strongly support to the claims and conclusions, and the proof of the theorem in section4 is detailed and rigorous.
Critical weaknesses
  • The experiments in this paper only conduct on a single dimension, which may lack of the generality.
  • The essential difference among this work and the most related works on in-context kernel ridge regression remains not very clear. Although it is discussed in the end of the section 2, the comparisons about the conclusions and study objectives are unclear.
Questions for authors
  • Could authors add experiments on larger dimension, and larger std σtrain2\sigma^2_{train} of the noise in training. I want to see the robustness of the interpreted algorithms and conclusions.
  • Could authors discuss about the differences between this paper and other related literature on in-context kernel ridge regression? For example, what are the conclusions of the previous studies, what is the motivation of the new settings, and whether the previous conclusions exist in the new experiment settings in this paper?
  • Is the theorem in this paper based on the population-limit assumption? In other words, will the sequence length N influence the conclusion? Do we need to choose a large N in training and inference for the stable conclusions?
3 comments

We thank the reviewer for the careful reading, positive assessment, and helpful suggestions. We have revised the manuscript to address the concerns raised and provide our responses below. The revisions in the manuscript are marked in red.

W1/Q1: Higher input dimension and training noise

The experiments in this paper only conduct on a single dimension, which may lack of the generality. Could authors add experiments on larger dimension, and larger std of the noise in training. I want to see the robustness of the interpreted algorithms and conclusions.

The experiments in Figure 1 use input dimension d=5d=5 and training-noise standard deviation σtrain=0.05\sigma_{\mathrm{train}}=0.05. In the revision, We have added experiments on spherical inputs with larger input dimensions, $d\in ${10,2010,20}, and training-noise standard deviations σtrain∈\sigma_{\mathrm{train}}\in{0.05,0.1,0.50.05,0.1,0.5} using kernel bandwidth v=2v=2. For each setting, we retrain both the transformer backbone and the layer-wise probes.

In the additional settings tested here, we observe the same qualitative alignment trends at both dimensions across all three training-noise levels. Prediction MSE generally decreases with depth, while the induced weights become increasingly aligned with the exact-KRR coefficients.

We describe the added experiments in Section 5.2 (lines 459--468) and present the full results in Figures 14 and 15 of Appendix F.3.

W2/Q2: Differences between our work and literatures

The essential difference among this work and the most related works on in-context kernel ridge regression remains not very clear. Although it is discussed in the end of the section 2, the comparisons about the conclusions and study objectives are unclear. Could authors discuss about the differences between this paper and other related literature on in-context kernel ridge regression? For example, what are the conclusions of the previous studies, what is the motivation of the new settings, and whether the previous conclusions exist in the new experiment settings in this paper?

Our work focuses on whether standard softmax attention and MLP layers can jointly approximate the regularized Gaussian KRR predictor with controlled prediction error, and whether trained GPT-2-style models learn to approximate this predictor in context. The following table compares our work with related studies in terms of the regression tasks considered, theoretical constructions, and numerical experiments.

WorkICL problem: Gaussian KRR (λ>0\lambda>0)Theoretical construction: standard TFTheoretical construction: depth unrolls an iterative solverTheoretical construction: explicit depth and MLP-width boundsNumerical experiments: standard TF
Ours✓✓✓✓✓
Cheng et al.(2024)✗ (λ=0\lambda=0)✗✓✗✗
NW-type works✗variesN/Avariesvaries
Kang et al.(2026)✓✗✓depth only✗

By "NW" we mean the Nadaraya--Watson smoothing kernel regression, including works of Goel & Bartlett (2024); Collins et al. (2024); Han et al.(2025); Shen et al.(2026).

By “standard TF”, we mean a standard transformer composed of blocks, each consisting of a softmax attention layer followed by an MLP layer, with residual connections around both layers.

References

Goel & Bartlett (2024). Can a transformer represent a Kalman filter? L4DC.

Collins et al. (2024). In-Context Learning with Transformers: Softmax Attention Adapts to Function Lipschitzness. NeurIPS.

Han et al. (2025). Understanding Emergent In-Context Learning from a Kernel Regression Perspective. TMLR.

Shen et al. (2026). Understanding In-Context Learning on Structured Manifolds: Bridging Attention to Kernel Methods. ICLR.

Cheng et al. (2024). Transformers Implement Functional Gradient Descent to Learn Non-Linear Functions In Context. ICML.

Kang et al. (2026). Transformers Can Learn Posterior Predictive Distributions In-Context. ICML.

Q3: Population limit and context length

Is the theorem in this paper based on the population-limit assumption? In other words, will the sequence length N influence the conclusion? Do we need to choose a large N in training and inference for the stable conclusions?

Our theorem does not rely on a population limit or require large NN. Theorem 1 is a deterministic approximation guarantee that holds for every prompt of any finite length NN satisfying the bounded-data assumption; its target is the KRR predictor computed from the given context, not a population quantity.

The context length NN affects only the required network size. For fixed λ\lambda, the sufficient depth becomes increasing with NN (Section 4, lines 328–337). Empirically, our models are trained with context lengths up to 40 and evaluated at lengths from 2 to 40. We observe progressive alignment with exact KRR at all evaluated lengths, with longer contexts generally requiring more layers to reach comparable alignment (Figures 1(a) and 7, discussion in Section 5.1, lines 396-400), which is qualitatively consistent with the theoretical prediction. Thus a large NN is not needed in either training or inference for our conclusions to hold.


We appreciate your constructive comments. If our responses and additional evidence have changed your view of the work, we would be grateful if you could update your assessment accordingly. We would be happy to address any remaining questions or concerns.

Thanks for your explanations, my concerns have been fully solved, and I will raise my score to 4.

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

This paper constructs a softmax-attention transformer that approximates Gaussian kernel ridge regression by implementing inexact, row-sum-preconditioned Richardson iteration. A dummy token makes normalization information accessible through standard attention, while ReLU MLPs approximate the necessary scalar operations. The analysis provides explicit bounds on sufficient depth and width. Separately, experiments with GPT-style models trained on Gaussian-process regression tasks show increasing agreement with KRR across depth, supported by probing controls and comparisons with several iterative solvers.

Critical strengths
  • The construction addresses a concrete architectural obstacle: recovering normalization information without direct access to the softmax denominator. Together with the analysis of how approximation errors propagate through the solver, this gives the theorem substance beyond an analogy between attention and normalized kernels.

  • The paper carefully distinguishes between the two regularization regimes. This distinction matters because the favorable logarithmic-depth guarantee does not carry over unchanged under the regularization convention used in the experiments.

  • The empirical controls address plausible alternative explanations for the observed KRR alignment. These include random-backbone controls, native-readout comparisons, and kernel-mismatch experiments. Section 5.3 also appropriately acknowledges that agreement with several convergent solvers does not identify a unique internal algorithm.

Critical weaknesses
  • The experiments provide evidence that trained transformers approximate KRR, but do not establish that they implement Richardson iteration. Since all five solvers converge to the same solution, similarity in their outputs cannot by itself identify the algorithm learned by the transformer.

  • The theoretical bounds are not quantitatively connected to the 12-layer models used in the experiments. Their strong dependence on regularization and data bounds makes it difficult to assess how well the construction explains the observed depth requirements.

  • The induced-weight analysis expresses model outputs in a chosen kernel basis and evaluates alignment using cosine similarity, which does not capture differences in coefficient magnitude. Reporting reconstruction errors on held-out queries would help establish how faithfully these weights describe the transformer's predictions.

Questions for authors
  • After recovering the induced weights, what are the relative reconstruction errors on fresh queries? Does the same depth trend appear when measuring squared differences directly between transformer and KRR predictions?

  • Could the authors instantiate the theorem's sufficient depth and width bounds for one of the reported experimental settings, while clearly distinguishing this conservative guarantee from the capacity needed empirically?

  • Is there an intermediate-state or update-level measurement that could distinguish Richardson iteration from the other solvers before they approach their common solution?

2 comments

We thank the reviewer for the comments. We have revised the manuscript to address the concerns raised and provide our responses below. The revisions in the manuscript are marked in red.

Q1/W3: Reconstruction error and direct prediction differences

The induced-weight analysis expresses model outputs in a chosen kernel basis and evaluates alignment using cosine similarity, which does not capture differences in coefficient magnitude. Reporting reconstruction errors on held-out queries would help establish how faithfully these weights describe the transformer's predictions. After recovering the induced weights, what are the relative reconstruction errors on fresh queries? Does the same depth trend appear when measuring squared differences directly between transformer and KRR predictions?

We thank the reviewer for suggesting these checks. We have added both analyses to Section 5.1 (lines 369--371 and 396--400), with full results in Appendix F.2.

Figure 9 shows that the mean relative reconstruction error (MRRE) on fresh queries is generally low, particularly in the later layers for longer contexts. Figure 8 shows that the mean squared difference (MSD) between transformer and exact-KRR predictions generally decreases with depth across all three input distributions and the tested context lengths. We believe these results support the fidelity of the induced-weight representation and provide further evidence of progressive agreement with KRR across depth.

Q2/W2: Theoretical bounds and empirical model size

The theoretical bounds are not quantitatively connected to the 12-layer models used in the experiments. Their strong dependence on regularization and data bounds makes it difficult to assess how well the construction explains the observed depth requirements. Could the authors instantiate the theorem's sufficient depth and width bounds for one of the reported experimental settings, while clearly distinguishing this conservative guarantee from the capacity needed empirically?

As discussed after Theorem 1 (Section 4, lines 328--337), for fixed λ\lambda, the sufficient depth in our construction increases with context length. Figures 1(a) and 7 show a qualitatively consistent trend: longer contexts generally require more layers to reach comparable agreement with exact KRR.

Our depth and width bounds give sufficient capacity for the explicit construction; they do not estimate the minimum capacity needed by trained models. The empirical trends therefore provide a qualitative connection to the theory, but do not establish how conservative the bounds are or quantitatively explain the performance of the 12-layer models.

Q3/W1: Identifying the learned update rule

The experiments provide evidence that trained transformers approximate KRR, but do not establish that they implement Richardson iteration. Since all five solvers converge to the same solution, similarity in their outputs cannot by itself identify the algorithm learned by the transformer. Is there an intermediate-state or update-level measurement that could distinguish Richardson iteration from the other solvers before they approach their common solution?

We do not have an intermediate-state or update-level measurement that distinguishes preconditioned Richardson iteration from the other solvers in our trained models.

Our theory establishes the standard softmax-attention transformer’s ability to approximate in-context Gaussian KRR. Just as approximation results establish the expressive power of single-hidden-layer neural networks (Barron, 1993), this existence result does not imply that practical training recovers the construction used in its proof. Preconditioned Richardson iteration is the algorithm we use in our constructive proof to establish this ability; trained models in practice may not follow the same computation.

Our experiments complement the theory by examining whether trained transformers progressively approximate the exact KRR predictor, instead of identifying a particular solver as the learned update rule.


Reference

A.R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930--945, 1993.


We hope these clarifications and additional results address your concerns. If they do, we would be grateful if you would consider updating your assessment, and we are happy to answer further questions.

Thank you for the response. Most of my concerns have been addressed, so I will raise my rating to 3.

Comments on the paper

1 comment

We appreciate the reviewers’ constructive feedback. We summarize the main revisions below; all changes are marked in red in the manuscript.

  1. Expanded the proof overview in Section 4 (lines 292–303), as suggested by Reviewer mek8.
  2. Clarified the relationship between the softmax formulations in the Introduction and Definition 1 (lines 73–76), as suggested by Reviewer mek8.
  3. Added analyses of direct transformer–KRR prediction differences and reconstruction errors on fresh queries (Section 5.1, lines 369–371 and 396–400; Appendix F.2, Figures 8–9), as suggested by Reviewer ARUz. We find that the mean squared prediction differences generally decrease with depth, and the relative reconstruction errors are generally low.
  4. Added experiments with higher input dimensions and larger training noise (Section 5.2, lines 459–468; Appendix F.3, Figures 14–15), as suggested by Reviewer 6FW5. We observe the same qualitative trends of progressive alignment with KRR across the additional settings.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.