CoChat
Sign Up
PreprintCited by 2Topic ModelingExplainable Artificial Intelligence (XAI)Domain Adaptation and Few-Shot Learning

The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.

An Analysis of Attention via the Lens of Exchangeability and Latent Variable Models

Open access
Zhang, Yufeng, Liu, Boyi, Cai, Qi, Wang, Lingxiao, Wang, Zhaoran·2022·arXiv
DOI 10.48550/arxiv.2212.14852arXiv 2212.14852
Open this paper in CoChat — free accountOpen PDF

Abstract

With the attention mechanism, transformers achieve significant empirical successes. Despite the intuitive understanding that transformers perform relational inference over long sequences to produce desirable representations, we lack a rigorous theory on how the attention mechanism achieves it. In particular, several intriguing questions remain open: (a) What makes a desirable representation? (b) How does the attention mechanism infer the desirable representation within the forward pass? (c) How does a pretraining procedure learn to infer the desirable representation through the backward pass? We observe that, as is the case in BERT and ViT, input tokens are often exchangeable since they already include positional encodings. The notion of exchangeability induces a latent variable model that is invariant to input sizes, which enables our theoretical analysis. - To answer (a) on representation, we establish the existence of a sufficient and minimal representation of input tokens. In particular, such a representation instantiates the posterior distribution of the latent variable given input tokens, which plays a central role in predicting output labels and solving downstream tasks. - To answer (b) on inference, we prove that attention with the desired parameter infers the latent posterior up to an approximation error, which is decreasing in input sizes. In detail, we quantify how attention approximates the conditional mean of the value given the key, which characterizes how it performs relational inference over long sequences. - To answer (c) on learning, we prove that both supervised and self-supervised objectives allow empirical risk minimization to learn the desired parameter up to a generalization error, which is independent of input sizes. Particularly, in the self-supervised setting, we identify a condition number that is pivotal to solving downstream tasks.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2212.14852

Cites

0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Softmax attention block can be reformulated as a non-parametric solution to the l2 regression with Nadaraya-Watson estimators.

    “Softmax attention block can also be reformulated as a non-parametric solution to the ℓ 2 (·) regression with Nadaraya-Watson estimators (Fan 2018; Zhang et al. 2022):”

    From ATLAS: Learning to Optimally Memorize the Context at Test Time (2025) · cites this paper as Zhang et al. 2022

    Section 4.2 (pp. 18–19) describes softmax attention as a conditional kernel density estimator and says it approaches the conditional mean E[V | K = q] as sequence length grows. Section 5 (p. 20) discusses squared-error regression, but our copy does not identify softmax attention as a Nadaraya–Watson estimator or present it as the nonparametric solution to that regression problem. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Softmax attention block can be reformulated as a non-parametric solution to the l2 regression objective with Nadaraya-Watson estimators.

    “Softmax attention block (Bahdanau 2014; Vaswani et al. 2017) can be reformulated as a non-parametric solution to the ℓ 2 (·) regression objective with Nadaraya-Watson estimators (Fan 2018; Zhang et al. 2022):”

    From Nested Learning: The Illusion of Deep Learning Architectures (2025) · cites this paper as Zhang et al. 2022

    Section 4.2 (pp. 18–19) describes softmax attention as a conditional kernel density estimator and says it approaches a conditional mean as sequence length grows. Section 5 (p. 20) separately defines a squared-error regression objective for an attention network. Our copy does not identify softmax attention as a Nadaraya–Watson estimator or present the attention block itself as a nonparametric solution to that objective. (LLM, conf=0.83)

    Experimental — accuracy not yet measured

  • Global softmax attention and its more expressive higher-order variants are perfect memories with frequency update of infinity, as they are non-parametric solutions for optimizing local L2-regression objective with Nadaraya-Watson estimators.

    “global softmax attention or its more expressive higher-order variants are perfect memories (forcing to cache all past tokens) with frequency update of infinity as they are non-parametric solutions for optimizing (local) 𝐿 2 -regression objective with Nadaraya-Watson estimators (Fan 2018; Zhang et al. 2022) (see Equation 62).”

    From Nested Learning: The Illusion of Deep Learning Architectures (2025) · cites this paper as Zhang et al. 2022

    Split into 2 atoms — 0 confirmed, 2 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 73

  1. Allen-Zhu, Z., Li, Y. and Liang, Y. (2019a). Learning and generalization in overparameterized neural networks, going beyond two layers. In Neural Information Processing Systems .
  2. Allen-Zhu, Z., Li, Y. and Song, Z. (2019b). A convergence theory for deep learning via over-parameterization. In International Conference on Machine Learning .
  3. Allen-Zhu, Z., Li, Y. and Song, Z. (2019c). On the convergence rate of training recurrent neural networks. In Neural Information Processing Systems .
  4. Arora, S., Du, S., Hu, W., Li, Z. and Wang, R. (2019). Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning .
  5. Bartlett, P. (1996). For valid generalization the size of the weights is more important than the size of the network. Neural Information Processing Systems .
  6. Bartlett, P., Helmbold, D. and Long, P. (2018a). Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks. In International Conference on Machine Learning .
  7. Bartlett, P. L., Evans, S. N. and Long, P. M. (2018b). Representing smooth functions as compositions of near-identity functions with implications for deep network optimization. arXiv preprint arXiv:1804.05012 . · arXiv
  8. Bartlett, P. L., Foster, D. J. and Telgarsky, M. J. (2017). Spectrally-normalized margin bounds for neural networks. Neural Information Processing Systems .
  9. Bartlett, P. L. and Mendelson, S. (2002). Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research .
  10. Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R. et al. (2018). Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261 . · arXiv
  11. Bloem-Reddy, B. and Teh, Y. W. (2020). Probabilistic symmetries and invariant neural networks. Journal of Machine Learning Research .
  12. Bronstein, M. M., Bruna, J., Cohen, T. and Veliˇ ckovi´ c, P. (2021). Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478 . · arXiv
  13. 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. Neural Information Processing Systems .
  14. Cao, Y. and Gu, Q. (2019). Generalization bounds of stochastic gradient descent for wide and deep neural networks. Neural Information Processing Systems .
  15. Chen, L., Lu, K., Rajeswaran, A., Lee, K., Grover, A., Laskin, M., Abbeel, P., Srinivas, A. and Mordatch, I. (2021). Decision transformer: Reinforcement learning via sequence modeling. Neural Information Processing Systems .
  16. Chizat, L., Oyallon, E. and Bach, F. (2019). On lazy training in differentiable programming. Neural Information Processing Systems .
  17. Dai, Z., Yang, Z., Yang, Y., Carbonell, J., Le, Q. V. and Salakhutdinov, R. (2019). Transformer-XL: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901.02860 . · arXiv
  18. Diaconis, P. and Freedman, D. (1980). Finite exchangeable sequences. Annals of Probability .
  19. Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S. et al. (2020). An image is worth 16 × 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929 . · arXiv
  20. Du, S., Lee, J., Li, H., Wang, L. and Zhai, X. (2019). Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning .
  21. Du, S. S., Zhai, X., Poczos, B. and Singh, A. (2018). Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054 . · arXiv
  22. Edelman, B. L., Goel, S., Kakade, S. and Zhang, C. (2021). Inductive biases and variable creation in self-attention mechanisms. arXiv preprint arXiv:2110.10090 . · arXiv
  23. Elesedy, B. (2021). Provably strict generalisation benefit for invariance in kernel methods. Neural Information Processing Systems .
  24. Fisher, R. A. (1922). On the mathematical foundations of theoretical statistics. Philosophical Transactions of the Royal Society A , 222 309-368.
  25. Fukumizu, K. (2015). Nonparametric bayesian inference with kernel mean embedding. In Modern Methodology and Applications in Spatial-Temporal Modeling . Springer, 1-24.
  26. Garg, S., Tsipras, D., Liang, P. and Valiant, G. (2022). What can transformers learn incontext? A case study of simple function classes. arXiv preprint arXiv:2208.01066 . · arXiv
  27. Han, J., Rong, Y., Xu, T. and Huang, W. (2022). Geometrically equivariant graph neural networks: A survey. arXiv preprint arXiv:2202.07230 . · arXiv
  28. Hardt, M. and Ma, T. (2016). Identity matters in deep learning. arXiv preprint arXiv:1611.04231 . · arXiv
  29. Hron, J., Bahri, Y., Sohl-Dickstein, J. and Novak, R. (2020). Infinite attention: NNGP and NTK for deep attention networks. In International Conference on Machine Learning .
  30. Hutchinson, M. J., Le Lan, C., Zaidi, S., Dupont, E., Teh, Y. W. and Kim, H. (2021). Lietransformer: Equivariant self-attention for Lie groups. In International Conference on Machine Learning .
  31. Jacot, A., Gabriel, F. and Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. Neural Information Processing Systems .
  32. Jiang, Y., Neyshabur, B., Mobahi, H., Krishnan, D. and Bengio, S. (2019). Fantastic generalization measures and where to find them. arXiv preprint arXiv:1912.02178 . · arXiv
  33. Keriven, N. and Peyr´ e, G. (2019). Universal invariant and equivariant graph neural networks. Neural Information Processing Systems .
  34. Kossen, J., Band, N., Lyle, C., Gomez, A. N., Rainforth, T. and Gal, Y. (2021). Selfattention between datapoints: Going beyond individual input-output pairs in deep learning. Neural Information Processing Systems .
  35. Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces: isoperimetry and processes , vol. 23. Springer Science & Business Media.
  36. Lee, J., Lee, Y., Kim, J., Kosiorek, A., Choi, S. and Teh, Y. W. (2019). Set transformer: A framework for attention-based permutation-invariant neural networks. In International Conference on Machine Learning .
  37. Li, Y. and Liang, Y. (2018). Learning overparameterized neural networks via stochastic gradient descent on structured data. Neural Information Processing Systems .
  38. Malladi, S., Wettig, A., Yu, D., Chen, D. and Arora, S. (2022). A kernel-based view of language model fine-tuning. arXiv preprint arXiv:2210.05643 . · arXiv
  39. Maurer, A. (2016). A vector-contraction inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory . Springer.
  40. Mei, S., Misiakiewicz, T. and Montanari, A. (2019). Mean-field theory of two-layers neural networks: Dimension-free bounds and kernel limit. In Annual Conference on Learning Theory .
  41. Mei, S., Montanari, A. and Nguyen, P.-M. (2018). A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences .
  42. Mohri, M., Rostamizadeh, A. and Talwalkar, A. (2018). Foundations of machine learning . MIT press.
  43. Muandet, K., Fukumizu, K., Sriperumbudur, B. and Sch¨ olkopf, B. (2016). Kernel mean embedding of distributions: A review and beyond. arXiv preprint arXiv:1605.09522 . · arXiv
  44. Nguyen, P.-M. (2019). Mean field limit of the learning dynamics of multilayer neural networks. arXiv preprint arXiv:1902.02880 . · arXiv
  45. Pearl, J. (2009). Causality . Cambridge University press.
  46. Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C., Radford, A., Chen, M. and Sutskever, I. (2021). Zero-shot text-to-image generation. In International Conference on Machine Learning .
  47. Romero, D. W. and Cordonnier, J.-B. (2020). Group equivariant stand-alone self-attention for vision. arXiv preprint arXiv:2010.00977 . · arXiv
  48. Rotskoff, G. and Vanden-Eijnden, E. (2018). Parameters as interacting particles: Long time convergence and asymptotic error scaling of neural networks. Neural Information Processing Systems .
  49. Satorras, V. G., Hoogeboom, E., Fuchs, F. B., Posner, I. and Welling, M. (2021). E ( n ) equivariant normalizing flows. arXiv preprint arXiv:2105.09016 . · arXiv
  50. Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M. and Monfardini, G. (2008). The graph neural network model. IEEE Transactions on Neural Networks .
  51. Schulz, E., Speekenbrink, M. and Krause, A. (2018). A tutorial on Gaussian process regression: Modelling, exploring, and exploiting functions. Journal of Mathematical Psychology .
  52. Shawe-Taylor, J., Cristianini, N. et al. (2004). Kernel methods for pattern analysis . Cambridge University Press.
  53. Singh, R., Sahani, M. and Gretton, A. (2019). Kernel instrumental variable regression. Advances in Neural Information Processing Systems .
  54. Song, L., Anandkumar, A., Dai, B. and Xie, B. (2014). Nonparametric estimation of multiview latent variable models. In International Conference on Machine Learning .
  55. Song, L., Huang, J., Smola, A. and Fukumizu, K. (2009). Hilbert space embeddings of conditional distributions with applications to dynamical systems. In International Conference on Machine Learning .
  56. Tsai, Y.-H. H., Bai, S., Yamada, M., Morency, L.-P. and Salakhutdinov, R. (2019). Transformer dissection: A unified understanding of transformer's attention via the lens of kernel. arXiv preprint arXiv:1908.11775 . · arXiv
  57. Valle-P´ erez, G. and Louis, A. A. (2020). Generalization bounds for deep learning. arXiv preprint arXiv:2012.04115 . · arXiv
  58. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, glyph[suppress] L. and Polosukhin, I. (2017). Attention is all you need. In Neural Information Processing Systems .
  59. Vuckovic, J., Baratin, A. and Combes, R. T. d. (2020). A mathematical theory of attention. arXiv preprint arXiv:2007.02876 . · arXiv
  60. Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint . Cambridge University Press.
  61. Wasserman, L. (2000). Bayesian model selection and model averaging. Journal of Mathematical Psychology , 44 92-107.
  62. Wei, C., Chen, Y. and Ma, T. (2021). Statistically meaningful approximation: A case study on approximating Turing machines with transformers. arXiv preprint arXiv:2107.13163 . · arXiv
  63. Xie, S. M., Raghunathan, A., Liang, P. and Ma, T. (2021). An explanation of in-context learning as implicit Bayesian inference. arXiv preprint arXiv:2111.02080 . · arXiv
  64. Yang, G. (2020). Tensor programs II: Neural tangent kernel for any architecture. arXiv preprint arXiv:2006.14548 . · arXiv
  65. Yang, G. and Littwin, E. (2021). Tensor programs IIb: Architectural universality of neural tangent kernel training dynamics. In International Conference on Machine Learning .
  66. Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R. and Smola, A. J. (2017). Deep sets. Neural Information Processing Systems .
  67. Zhang, F., Liu, B., Wang, K., Tan, V. Y., Yang, Z. and Wang, Z. (2022a). Relational reasoning via set transformers: Provable efficiency and applications to MARL. arXiv preprint arXiv:2209.09845 . · arXiv
  68. Zhang, X., Yu, Y., Wang, L. and Gu, Q. (2019). Learning one-hidden-layer ReLU networks via gradient descent. In International Conference on Machine Learning .
  69. Zhang, Y., Backurs, A., Bubeck, S., Eldan, R., Gunasekar, S. and Wagner, T. (2022b). Unveiling transformers with LEGO: A synthetic reasoning task. arXiv preprint arXiv:2206.04301 . · arXiv
  70. Zhang, Y., Duchi, J. and Wainwright, M. (2015). Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates. The Journal of Machine Learning Research , 16 3299-3340.
  71. Zhu, S., An, B. and Huang, F. (2021). Understanding the generalization benefit of model invariance from a data perspective. Neural Information Processing Systems .
  72. Zou, D., Cao, Y., Zhou, D. and Gu, Q. (2018). Stochastic gradient descent optimizes overparameterized deep ReLU networks. arXiv preprint arXiv:1811.08888 . · arXiv
  73. Zou, D. and Gu, Q. (2019). An improved analysis of training over-parameterized deep neural networks. Neural Information Processing Systems .

Cited by

Sorted by citations

Related

Metadata

Authors
Zhang, Y., Liu, B., Cai, Q., Wang, L., & Wang, Z.
Affiliations
Northwestern University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2022
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2212.14852
arXiv
2212.14852
OpenAlex
W4313447747
Cited by
0
References
0
Type
posted content
Language
en
Open access
Licence
creativecommons.org/publicdomain/zero/1.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University) (public-domain)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Explainable Artificial Intelligence (XAI)
  • Physical Sciences › Computer Science › Artificial Intelligence › Domain Adaptation and Few-Shot Learning
Keywords
attention mechanism, transformer models, exchangeability, latent variable models, relational inference, positional encoding, posterior distribution, empirical risk minimization, self-supervised learning, condition number, generalization error, representation learning, BERT, vision transformer

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review