Pith. sign in

REVIEW 1 major objections 5 minor 2 cited by

Transformers Meet In-Context Learning: A Universal Approximation Theory

T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that a single fixed-weight transformer can perform in-context learning for every task in a broad, potentially nonconvex function class, with squared prediction error that vanishes as the number of examples and the model's…

desk verdict Solid constructive idea undermined by a query-dependence gap in the proof; likely repairable, but Theorem 1 is not established as written. read the letter →

arxiv 2506.05200 v2 pith:ACZNFCNI submitted 2025-06-05 cs.LG math.STstat.MLstat.TH

Gen Li , Yuchen Jiao , Yu Huang , Yuting Wei , Yuxin Chen This is my paper
classification cs.LGmath.STstat.MLstat.TH MSC 68T0741A3062J07
keywords in-contextlearningtransformeruniversalapproximationBarronparameterLassoproximalgradientmethodnonconvexfunctionclassespredictionrisk
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to prove that in-context learning is not a special property of linear or convex problems: a single fixed transformer, with no weight updates at test time, can predict from a handful of noisy input-output examples for every function in a broad class of tasks. The class is allowed to be nonconvex, and its only requirement is a finite Barron parameter, a Fourier-moment measure of how complex the functions' gradients are. The main theorem gives an explicit bound on the squared prediction error that vanishes as the number of examples N grows and as the transformer's depth and width increase. If correct, this establishes a universal approximation theory for transformers as in-context learners that goes beyond the linear-regression settings of earlier analyses.

What carries the argument

The proof rests on two ingredients. First, Barron-style approximation: for any function class with finite $C_F$, there is a finite set of universal features, sigmoidal ridge functions $\phi_i^{\mathrm{feature}}(x)$ with random orientations, such that every $f\in\mathcal{F}$ is approximately a linear combination of these features and the coefficients have $\ell_1$ norm at most $4C_F$. Second, the transformer is explicitly constructed to find those coefficients at test time by running an inexact proximal gradient method that solves a Lasso problem; each block of attention and feed-forward layers emulates one soft-thresholded gradient step. The input matrix carries the examples, the features, the current coefficients, and the current prediction in $d+2n+7$ rows, which is what lets a constant number of attention heads execute the updates.

What would settle it

Fix a function class with finite Barron parameter and run the constructed transformer on prompts in which the query $x_{N+1}$ is chosen adversarially as a function of the $N$ examples, such as the mirror image of $x_1$, while keeping the marginal distribution of each input uniform on the unit ball; a prediction error that fails to vanish as $N\to\infty$ would show that the i.i.d. exchangeability assumption in Lemma 2 is load-bearing.

Watch

Extended reading notes

Core claim

Theorem 1 states that for any function class $\mathcal{F}$ with finite Barron parameter $C_F$, one can construct a transformer with $L$ layers and input dimension $d+2n+7$, where $n$ grows logarithmically with the covering number $|\mathcal{N}_\varepsilon|$ of the task class, such that every $f\in\mathcal{F}$ is handled by the same network. Given $N$ noisy examples generated as $y_i=f(x_i)+z_i$ and a new query $x_{N+1}$, all drawn independently from a fixed distribution supported on the unit ball, the prediction error satisfies $\mathbb{E}[(\hat{y}_{N+1}-f(x_{N+1}))^2] \lesssim \sqrt{\log N/N}\,C_F(C_F+\sigma) + C_F^2\log|\mathcal{N}_\varepsilon|/n + nC_F^2/L$ with probability at least $1-O(N^{-10})$. The risk can be made arbitrarily small by taking $N$ large and choosing $n$ and $L$ large enough, so a single pretrained transformer is a universal in-context learner for the whole class $\mathcal{F}$.

Load-bearing premise

The prompts must be generated by drawing the in-context inputs and the new query independently from a fixed input distribution on the unit ball, with independent zero-mean sub-Gaussian noise; if the examples and query are correlated or adversarially chosen, the vanishing-risk guarantee does not go through.

Editorial extensions

If this is right

  • If Theorem 1 is correct, in-context learning is representable for general nonconvex task classes, not just linear regression or convex loss minimization.
  • A single fixed-weight transformer can serve all tasks in a class, with model width and depth growing only logarithmically in the covering number of the class.
  • Prediction error can be made arbitrarily small by combining more in-context examples with a wider and deeper transformer, providing a concrete scaling recipe.
  • The construction identifies Lasso as the test-time computation, so the transformer's role is to solve a convex denoising problem on universal features.
  • The approximation guarantee no longer inherits the convergence limitations of the optimization algorithm being mimicked, because the hard learning problem is absorbed by the universal features.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One implication the authors leave implicit is a design principle: pretraining could aim to learn universal features of the pretraining task distribution plus a mechanism that implements Lasso at inference, rather than learning per-task predictors.
  • The exchangeability assumption on prompts is the most fragile point for real language-model use; testing the construction on correlated, non-exchangeable prompts would reveal how much of the guarantee survives outside the i.i.d. model.
  • The risk bound suggests a depth-width-examples trade-off that could be tested empirically: for a fixed number of examples, wider and deeper models should show decreasing in-context error, which is a falsifiable scaling prediction.
  • A natural extension would be to replace the Euclidean unit-ball input model with structured sequence data, where the universal features would need to respect the data geometry; the paper does not address this.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. This paper develops a universal approximation theorem for transformers in in-context learning. For a general class F of functions with finite Barron-type parameter C_F, the authors construct a fixed-weight transformer with L layers and input dimension d+2n+7, where n is at least a constant times log|N_ε|, such that for every f in F and every random prompt of N noisy examples, with probability at least 1-O(N^{-10}) the squared prediction risk at a new input is O(sqrt(log N/N) C_F(C_F+sigma) + n C_F^2/L + C_F^2 log|N_ε|/n). The proof combines Barron's feature expansion with a Lasso/proximal-gradient viewpoint: Lemma 1 supplies universal features with l1-bounded coefficients, Lemma 2 gives a Lasso risk bound, Lemma 3 gives convergence of an inexact proximal gradient method, and Lemma 4 provides explicit attention and feed-forward parameter matrices. The construction is analytic and does not fit constants to the target risk.

Significance. If the theorem is correct, this is a substantial advance: it extends ICL approximation theory beyond convex linear regression and, unlike prior algorithm-approximation results, does not tie the guarantee to the convergence of a mimicked optimization algorithm. The paper gives explicit formulas for all weight matrices and attention heads, and the model complexity scales logarithmically with the covering number of the function class. The result is a credible existence theorem for universal in-context prediction. The main caveat is the proof gap described below, which concerns the statistical independence condition in Lemma 2.

major comments (1)
  1. [§4 Step 5 and §A.4.3 (Eqs. (101), (103), (111); Lemma 2 and Remark 2)] Step 5 (Eq. (44)) invokes Lemma 2 with bρ = ρ(L), but Lemma 2 and Remark 2 require bρ to be statistically independent of x_{N+1}. The construction in §A.4 does not enforce this. The gradient update in Attn1 (Eq. (101)) sums attention over all N+1 columns; the intended cancellation of the query contribution uses the term 4τ[σ_attn(τ^{-1}η(1-w_i)ŷ_i) - σ_attn(0)]φ_i, which for i=N+1 involves ŷ_{N+1}. Attn2 (Eq. (93)) sets ŷ_{N+1} = φ_{N+1}^Tρ + e͂, with e͂ itself a function of φ_{N+1} (Eq. (108)). Therefore the residual between the second and third sums in Eq. (101), which is absorbed into e^{(l-1)}, depends on x_{N+1} through φ_{N+1}; Eqs. (103) and (111) make this dependence explicit. Consequently ρ(L) is a proximal iterate with query-dependent errors e_t, not a query-independent estimator. The concentration argument in Lemma 6 factors ρ out of expectations over x_{N+1}, which is valid only when ρ is independent of x_{N+1}; with ρ depending on x_{N+1}, the term E[(ρ⋆-ρ)^T φ_{N+1}(f(x_{N+1})-φ_{N+1}^Tρ⋆)] cannot be bounded by the empirical process as in Eq. (75). The theorem is likely repairable, for example by masking attention in Attn1 so that only i=1,...,N contribute to the gradient, or by a leave-one-out/exchangeability argument, but as written the proof of Theorem 1 contains a load-bearing gap.
minor comments (5)
  1. [Theorem 1 and Lemma 4] Theorem 1 and Lemma 4 state 'L layers' without a parity condition, but the proof of Lemma 4 in §A.4.5 explicitly requires L = 2T+1; the statement should either require L odd or use floor((L-1)/2) and adjust the bound accordingly.
  2. [§A.3 (paragraph after Eq. (83))] The text writes ε_dis = C_F(√ε + (log|N_ε|/n)^{1/3}), but Eq. (25) defines ε_dis with (log|N_ε|/n)^{1/2}; the exponent 1/3 appears to be a typo and should be 1/2.
  3. [Eq. (21)] The function ϕ defined in Eq. (21) is called a sigmoid function, but it is a shifted difference of ReLUs; a different name would avoid confusion with the logistic attention activation.
  4. [Eq. (101)] Eq. (101) uses τ and η before the parameter choices for those quantities are stated; it would improve readability to recall τ = 1/√ε and η = 1/(2n) immediately before the equation.
  5. [Notation in §A.4] The superscripts on H and on the intermediate variables (e.g., l-1/2, l+1/2) are terse and sometimes conflict with the layer index l; a small table of the intended layer-to-update correspondence would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the transformer construction is analytic and the theorem's constants are problem-class inputs, not fitted outputs.

full rationale

I walked the proof chain Lemma 1 to Lemma 3 to Lemma 4 to Theorem 1. The Barron-style parameter C_F, the noise level σ, and the covering number |N_ε| are stipulated properties of the function class and sampling model; they are not estimated from the in-context data or from the target risk. The transformer parameters, such as λ in (41a) and τ in Lemma 7, are chosen analytically with explicit formulas, and the Lasso coefficients ρ^(L) are computed from the in-context examples rather than back-fitted to force the bound (19). There is no fitted parameter renamed as a prediction, and no definition of a key quantity in terms of the quantity being proved. The proof relies on external mathematical results (Barron 1993; Beck 2017) that are independently checkable, not on self-citations. The skeptical concern about Lemma 2's independence condition — that the constructed Attn1/Attn2 residuals may make ρ^(L) depend on x_{N+1} — is a possible correctness gap in the proof, not a circularity: the theorem's conclusion is not being assumed, and the gap is repairable in principle by masking. The only self-citations in the related-work section (e.g., Huang et al. 2025) are non-load-bearing. I therefore find no significant circularity, and score 0.

Assumptions & free parameters 6 free parameters · 4 assumptions · 0 invented entities

No data-fitted constants appear; all construction parameters are analytic functions of problem quantities such as C_F, sigma, and the covering number. The only externally assumed inputs are the Barron parameter, the noise scale, the covering number, and the i.i.d. sampling model.

free parameters (6)
  • attention scaling tau = chosen >= C N n^2 (L+n)(N+n) C_F (Lemma 7)
    Controls the accuracy of the logistic approximation x approx 4 tau (sigma_attn(tau^{-1} x) - sigma_attn(0)); too small ruins Lemma 7, too large is allowed because the feature-level tau is chosen separately.
  • Lasso regularization lambda = Eq. (41a): lambda approx (logN/N)^{1/6} C_F^{-1/3} b_eps^{2/3} + sqrt(logN/N)(C_F+sigma) + C_F^{-1} eps_dis^2
    Chosen to balance estimation and optimization errors in Lemma 2 and Lemma 3.
  • proximal step size eta = eta = 1/(2n) (Eq. 35)
    Standard choice matching the smoothness of the Lasso objective; fixed in the construction.
  • number of universal features n = n >= c0 log|N_eps| (Lemma 1, Theorem 1)
    Feature dictionary size; larger n reduces representation error log|N_eps|/n but raises the depth requirement.
  • cover precision eps = eps <= sqrt(logN/N + n/L) (after Eq. 49)
    Controls discretization error in Lemma 1; coupled to n and L.
  • depth L = L = 2T+1 with T=(L-1)/2 proximal iterations (Eq. 35, Theorem 1)
    Depth determines optimization accuracy n C_F^2/L and is a design parameter.
assumptions (4)
  • domain assumption F is a class of absolutely integrable functions on the unit Euclidean ball with finite Barron parameter C_F = sup_f |f(0)| + integral ||omega|| F_sup(omega) d omega < infinity.
    Invoked in Eq. (14) and throughout Lemma 1; if C_F is infinite the error bounds are trivial.
  • domain assumption In-context inputs x_i are i.i.d. from D_X supported on the unit ball, and noise z_i are independent zero-mean sub-Gaussian with norm at most sigma (Eqs. (1b)-(3)).
    Lasso generalization in Lemma 2, concentration of empirical sums, and the final risk bound depend on this exchangeability and noise tail model.
  • domain assumption An eps-cover N_eps of F x B exists with finite cardinality under the metric in Eq. (18).
    Used to union-bound sampled features in Lemma 1 and to define log|N_eps| in the theorem; requires compactness or a covering finiteness condition.
  • standard math Fourier inversion, sub-Gaussian concentration inequalities, and standard proximal gradient convergence results hold.
    Used in Lemma 1 and Appendix A.1 for feature representation and in Lemma 3 for optimization convergence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Transformers Meet In-Context Learning: A Universal Approximation Theory." pith.science (2026). https://pith.science/paper/ACZNFCNI

@misc{pith2026250605200,
  author       = {Pith},
  title        = {Pith review of: Transformers Meet In-Context Learning: A Universal Approximation Theory},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ACZNFCNI}},
  note         = {Machine review of arXiv:2506.05200}
}
abstract

Large language models are capable of in-context learning, the ability to perform new tasks at test time using a handful of input-output examples, without parameter updates. We develop a universal approximation theory to elucidate how transformers enable in-context learning. For a general class of functions (each representing a distinct task), we demonstrate how to construct a transformer that, without any further weight updates, can predict based on a few noisy in-context examples with vanishingly small risk. Unlike prior work that frames transformers as approximators of optimization algorithms (e.g., gradient descent) for statistical learning tasks, we integrate Barron's universal function approximation theory with the algorithm approximator viewpoint. Our approach yields approximation guarantees that are not constrained by the effectiveness of the optimization algorithms being mimicked, extending far beyond convex problems like linear regression. The key is to show that (i) any target function can be nearly linearly represented, with small $\ell_1$-norm, over a set of universal features, and (ii) a transformer can be constructed to find the linear representation -- akin to solving Lasso -- at test time.

Figures

Figures reproduced from arXiv: 2506.05200 by the authors.

Figure 1
Figure 1. Structure of the desirable transformer. Step 4: constructing the transformer to emulate proximal gradient iterations. To build a trans￾former with favorable in-context learning capabilities, our design seeks to approximate the above proximal gradient iterations, which we elucidate in this step. Let us begin by describing the input structure for each layer of our constructed transformer. For the l-th hidden layer (0 … view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Provable Low-Frequency Bias of In-Context Learning of Representations

    cs.LG 2025-07 conditional novelty 7.0 of 10

    In-context learning biases hidden representations toward low-frequency eigenvectors of a reweighted graph Laplacian, a phenomenon the authors prove and test.

  2. How Does the Pretraining Distribution Shape In-Context Learning? A Fundamental Trade-Off

    cs.LG 2025-10 conditional novelty 6.0 of 10

    Heavy-tailed pretraining distributions improve in-context task selection under distribution shift but worsen ICL generalization, especially in low-data regimes.

Reference graph

Works this paper leans on

71 extracted references · 42 canonical work pages · cited by 2 Pith papers

  1. [1]

    Ahn, K., Cheng, X., Daneshmand, H., and Sra, S. (2023). Transformers learn to implement preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems , 36:45614--45650

    work page 2023

  2. [2]

    Ahuja, K., Panwar, M., and Goyal, N. (2023). In-context learning through the bayesian prism. arXiv preprint arXiv:2306.04891

    arXiv 2023

  3. [3]

    Aky \"u rek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D. (2023). What learning algorithm is in-context learning? investigations with linear models. In International Conference on Learning Representations

    work page 2023

  4. [4]

    Bach, F. (2017). Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research , 18(19):1--53

    work page 2017

  5. [5]

    Bai, Y., Chen, F., Wang, H., Xiong, C., and Mei, S. (2023). Transformers as statisticians: Provable in-context learning with in-context algorithm selection. Advances in neural information processing systems , 36:57125--57211

    work page 2023

  6. [6]

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

    work page 1993

  7. [7]

    Beck, A. (2017). First-order methods in optimization . SIAM

    work page 2017

  8. [8]

    A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M

    Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al. (2021). On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258

    arXiv 2021

Show all 71 references
  1. [9]

    D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al

    Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances in neural information processing systems , 33:1877--1901

    2020

  2. [10]

    Candes, E. J. and Tao, T. (2006). Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE transactions on information theory , 52(12):5406--5425

    2006

  3. [11]

    Chen, L., Peng, B., and Wu, H. (2024a). Theoretical limitations of multi-layer transformer. arXiv preprint arXiv:2412.02975

    2024 arXiv

  4. [12]

    and Li, Y

    Chen, S. and Li, Y. (2024). Provably learning a multi-head attention layer. arXiv preprint arXiv:2402.04084

    2024 arXiv

  5. [13]

    Chen, S., Sheen, H., Wang, T., and Yang, Z. (2024b). Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality. arXiv preprint arXiv:2402.19442

    2024 arXiv

  6. [14]

    Cheng, X., Chen, Y., and Sra, S. (2024). Transformers implement functional gradient descent to learn non-linear functions in context. In International Conference on Machine Learning , pages 8002--8037

    2024

  7. [15]

    Cole, F., Lu, Y., O'Neill, R., and Zhang, T. (2024). Provable in-context learning of linear systems and linear elliptic pdes with transformers. arXiv preprint arXiv:2409.12293

    2024 arXiv

  8. [16]

    Cole, F., Lu, Y., Zhang, T., and Zhao, Y. (2025). In-context learning of linear dynamical systems with transformers: Error bounds and depth-separation. arXiv preprint arXiv:2502.08136

    2025

  9. [17]

    Dai, D., Sun, Y., Dong, L., Hao, Y., Ma, S., Sui, Z., and Wei, F. (2022). Why can gpt learn in-context? language models implicitly perform gradient descent as meta-optimizers. arXiv preprint arXiv:2212.10559

    2022 arXiv

  10. [18]

    Dong, Q., Li, L., Dai, D., Zheng, C., Ma, J., Li, R., Xia, H., Xu, J., Wu, Z., Liu, T., et al. (2022). A survey on in-context learning. arXiv preprint arXiv:2301.00234

    2022 arXiv

  11. [19]

    E, W., Ma, C., and Wu, L. (2022). The B arron space and the flow-induced function spaces for neural network models. Constructive Approximation , 55(1):369--406

    2022

  12. [20]

    Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., DasSarma, N., Drain, D., Ganguli, D., Hatfield-Dodds, Z., Hernandez, D., Jones, A., Kernion, J., Lovitt, L., Ndousse, K., Amodei, D., Brown, T., Clark, J., Kaplan...

    2021

  13. [21]

    Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., and Wang, L. (2023). Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems , 36:70757--70798

    2023

  14. [22]

    Fu, D., Chen, T.-q., Jia, R., and Sharan, V. (2024). Transformers learn to achieve second-order convergence rates for in-context linear regression. Advances in Neural Information Processing Systems , 37:98675--98716

    2024

  15. [23]

    V., and Peyr \'e , G

    Furuya, T., de Hoop, M. V., and Peyr \'e , G. (2024). Transformers are universal in-context learners. arXiv preprint arXiv:2408.01367

    2024 arXiv

  16. [24]

    S., and Valiant, G

    Garg, S., Tsipras, D., Liang, P. S., and Valiant, G. (2022). What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems , 35:30583--30598

    2022

  17. [25]

    D., and Papailiopoulos, D

    Giannou, A., Rajput, S., Sohn, J.-y., Lee, K., Lee, J. D., and Papailiopoulos, D. (2023). Looped transformers as programmable computers. In International Conference on Machine Learning , pages 11398--11442. PMLR

    2023

  18. [26]

    Giannou, A., Yang, L., Wang, T., Papailiopoulos, D., and Lee, J. D. (2024). How well can transformers emulate in-context newton's method? arXiv preprint arXiv:2403.03183

    2024 arXiv

  19. [27]

    Gillioz, A., Casas, J., Mugellini, E., and Abou Khaled, O. (2020). Overview of the transformer-based models for nlp tasks. In 2020 15th Conference on computer science and information systems (FedCSIS) , pages 179--183. IEEE

    2020

  20. [28]

    Guo, T., Hu, W., Mei, S., Wang, H., Xiong, C., Savarese, S., and Bai, Y. (2024). How do transformers learn in-context beyond simple functions? a case study on learning with representations. In International Conference on Learning Representations

    2024

  21. [29]

    Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics , 8:156--171

    2020

  22. [30]

    and Goyal, N

    Hahn, M. and Goyal, N. (2023). A theory of emergent in-context learning as implicit structure induction. arXiv preprint arXiv:2303.07971

    2023 arXiv

  23. [31]

    Hataya, R., Matsui, K., and Imaizumi, M. (2024). Automatic domain adaptation by transformers in in-context learning. arXiv preprint arXiv:2405.16819

    2024 arXiv

  24. [32]

    Hornik, K., Stinchcombe, M., White, H., and Auer, P. (1994). Degree of approximation results for feedforward networks approximating unknown mappings and their derivatives. Neural computation , 6(6):1262--1275

    1994

  25. [33]

    Huang, Y., Cheng, Y., and Liang, Y. (2024). In-context convergence of transformers. In International Conference on Machine Learning , pages 19660--19722

    2024

  26. [34]

    Huang, Y., Wen, Z., Singh, A., Chi, Y., and Chen, Y. (2025). Transformers provably learn chain-of-thought reasoning with length generalization

    2025

  27. [35]

    M., and Malach, E

    Jelassi, S., Brandfonbrener, D., Kakade, S. M., and Malach, E. (2024). Repeat after me: Transformers are better than state space models at copying. arXiv preprint arXiv:2402.01032

    2024 arXiv

  28. [36]

    Ji, Z., Telgarsky, M., and Xian, R. (2020). Neural tangent kernels, transportation mappings, and universal approximation. In International Conference on Learning Representations

    2020

  29. [37]

    and Nemirovski, A

    Juditsky, A. and Nemirovski, A. (2000). Functional aggregation for nonparametric regression. The Annals of Statistics , 28(3):681--712

    2000

  30. [38]

    W., Khan, F

    Khan, S., Naseer, M., Hayat, M., Zamir, S. W., Khan, F. S., and Shah, M. (2022). Transformers in vision: A survey. ACM computing surveys (CSUR) , 54(10s):1--41

    2022

  31. [39]

    and Suzuki, T

    Kim, J. and Suzuki, T. (2024). Transformers learn nonlinear features in context: Nonconvex mean-field dynamics on the attention landscape. In Forty-first International Conference on Machine Learning

    2024

  32. [40]

    and Sanguineti, M

    Kurkov \'a , V. and Sanguineti, M. (2002). Bounds on rates of variable-basis and neural-network approximation. IEEE Transactions on Information Theory , 47(6):2659--2665

    2002

  33. [41]

    M., Xu, A

    Kwon, S. M., Xu, A. S., Yaras, C., Balzano, L., and Qu, Q. (2025). Out-of-distribution generalization of in-context learning: A low-dimensional subspace perspective. arXiv preprint arXiv:2505.14808

    2025 arXiv

  34. [42]

    Lee, H., Ge, R., Ma, T., Risteski, A., and Arora, S. (2017). On the ability of neural nets to express distributions. In Conference on Learning Theory , pages 1271--1296. PMLR

    2017

  35. [43]

    Li, H., Wang, M., Lu, S., Cui, X., and Chen, P.-Y. (2024a). Training nonlinear transformers for efficient in-context learning: A theoretical learning and generalization analysis. arXiv preprint arXiv:2402.15607

    2024 arXiv

  36. [44]

    E., Papailiopoulos, D., and Oymak, S

    Li, Y., Ildiz, M. E., Papailiopoulos, D., and Oymak, S. (2023). Transformers as algorithms: Generalization and stability in in-context learning. In International conference on machine learning , pages 19565--19594. PMLR

    2023

  37. [45]

    Li, Z., Liu, H., Zhou, D., and Ma, T. (2024b). Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402.12875 , 1

    2024 arXiv

  38. [46]

    Likhosherstov, V., Choromanski, K., and Weller, A. (2021). On the expressive power of self-attention matrices. arXiv preprint arXiv:2106.03764

    2021 arXiv

  39. [47]

    Lin, T., Wang, Y., Liu, X., and Qiu, X. (2022). A survey of transformers. AI open , 3:111--132

    2022

  40. [48]

    T., Goel, S., Krishnamurthy, A., and Zhang, C

    Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. (2022). Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749

    2022 arXiv

  41. [49]

    V., Hashimoto, T., and Ma, T

    Mahankali, A. V., Hashimoto, T., and Ma, T. (2024). One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. In International Conference on Learning Representations

    2024

  42. [50]

    and Sabharwal, A

    Merrill, W. and Sabharwal, A. (2024). The expressive power of transformers with chain of thought. In International Conference on Learning Representations

    2024

  43. [51]

    Nichani, E., Damian, A., and Lee, J. D. (2024). How transformers learn causal structure with gradient descent. In International Conference on Machine Learning , pages 38018--38070

    2024

  44. [52]

    Peng, B., Narayanan, S., and Papadimitriou, C. (2024). On limitations of the transformer architecture. In First Conference on Language Modeling

    2024

  45. [53]

    P \'e rez, J., Marinkovi \'c , J., and Barcel \'o , P. (2019). On the turing completeness of modern neural network architectures. arXiv preprint arXiv:1901.03429

    2019 arXiv

  46. [54]

    Sanford, C., Hsu, D., and Telgarsky, M. (2024). Transformers, parallel computation, and logarithmic depth. arXiv preprint arXiv:2402.09268

    2024 arXiv

  47. [55]

    J., and Telgarsky, M

    Sanford, C., Hsu, D. J., and Telgarsky, M. (2023). Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems , 36:36677--36707

    2023

  48. [56]

    W., Khan, M

    Shamshad, F., Khan, S., Zamir, S. W., Khan, M. H., Hayat, M., Khan, F. S., and Fu, H. (2023). Transformers in medical imaging: A survey. Medical image analysis , 88:102802

    2023

  49. [57]

    Shen, L., Mishra, A., and Khashabi, D. (2023). Do pretrained transformers learn in-context by gradient descent? arXiv preprint arXiv:2310.08540

    2023 arXiv

  50. [58]

    Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology , 58(1):267--288

    1996

  51. [59]

    N., Kaiser, ., and Polosukhin, I

    Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, ., and Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems , 30

    2017

  52. [60]

    Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science , volume 47. Cambridge university press

    2018

  53. [61]

    Vladymyrov, M., Von Oswald, J., Sandler, M., and Ge, R. (2024). Linear transformers are versatile in-context learners. Advances in Neural Information Processing Systems , 37:48784--48809

    2024

  54. [62]

    Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M. (2023). Transformers learn in-context by gradient descent. In International Conference on Machine Learning , pages 35151--35174

    2023

  55. [63]

    von Oswald, J., Schlegel, M., Meulemans, A., Kobayashi, S., Niklasson, E., Zucchet, N., Scherrer, N., Miller, N., Sandler, M., Vladymyrov, M., et al. (2023). Uncovering mesa-optimization algorithms in transformers. arXiv preprint arXiv:2309.05858

    2023 arXiv

  56. [64]

    Wang, Z., Jiang, B., and Li, S. (2024). In-context learning on function classes unveiled for transformers. In Forty-first International Conference on Machine Learning

    2024

  57. [65]

    Wen, K., Dang, X., and Lyu, K. (2024). Rnns are not transformers (yet): The key bottleneck on in-context retrieval. arXiv preprint arXiv:2402.18510

    2024 arXiv

  58. [66]

    Wen, K., Li, Y., Liu, B., and Risteski, A. (2023). Transformers are uninterpretable with myopic methods: a case study with bounded dyck grammars. Advances in Neural Information Processing Systems , 36:38723--38766

    2023

  59. [67]

    M., Raghunathan, A., Liang, P., and Ma, T

    Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. (2022). An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations

    2022

  60. [68]

    Yang, T., Huang, Y., Liang, Y., and Chi, Y. (2024). In-context learning with representations: Contextual generalization of trained transformers. arXiv preprint arXiv:2408.10147

    2024 arXiv

  61. [69]

    Yao, S., Peng, B., Papadimitriou, C., and Narasimhan, K. (2021). Self-attention networks can process bounded hierarchical languages. arXiv preprint arXiv:2105.11115

    2021 arXiv

  62. [70]

    Zhang, R., Frei, S., and Bartlett, P. L. (2024). Trained transformers learn linear models in-context. Journal of Machine Learning Research , 25(49):1--55

    2024

  63. [71]

    Zhang, Y., Zhang, F., Yang, Z., and Wang, Z. (2023). What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization. arXiv preprint arXiv:2305.19420

    2023 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.