acceptodds
Under review as a conference paper at ICLR 2027

On the Expressive Power of Transformers for Contextual Relations

Abstract

Transformers have revolutionized machine learning by making attention a central mechanism for modeling interactions within a context. Despite the central role of attention, the theoretical capabilities of Transformers for representing contextual relations remain unclear. In this work, we address this question by developing a mathematical framework based on probability and optimal transport. We view a text as a distribution of its representations and attention as a probabilistic relation between them. This perspective reveals a connection between attention normalization and optimal transport: standard softmax normalization produces conditional relations, while Sinkhorn normalization produces joint relations with prescribed marginals. Thus, both mechanisms provide structured probabilistic relations from attention scores. Under mild conditions, we establish universal approximation results for both settings. We show that Transformer architectures with Sinkhorn normalization can approximate arbitrary contextual relations represented as joint probabilities, while standard softmax Transformers can approximate arbitrary contextual relations represented as conditional probabilities. These results provide a mathematical characterization of the expressive power of Transformers for contextual relations and show how the choice of normalization determines the probabilistic structure of the relations represented by attention.

Primary area:
learning theory
Keywords:
Transformers, Attention mechanisms, Expressive power, Universal approximation, Optimal transport.

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_TFUmOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

Furuya et al. proved that Transformers can approximate arbitrary continuous vector-valued functions of a token and its context, uniformly over contexts of arbitrary length. The present paper extends this framework to attention matrices between two input sequences. The output is a probability-valued function: either a conditional distribution over target tokens for each source token, or a joint distribution with prescribed marginals equal to the input measures.

The authors study an architecture comprising two independent Transformer encoders, followed by pairwise dot products and either softmax or Sinkhorn normalization. Combining Furuya et al.’s encoder universality theorem with approximation results for these normalized probability distributions, they establish universality for the corresponding classes of continuous relation-valued maps. The guarantee is uniform over input measures and uses Wasserstein distance between joint distributions.

Critical strengths

The problem formulation is coherent and the presentation is generally rather good.

Critical weaknesses
  1. As far as I understand their results can be obtained by a combination of some standard techniques from outside ML research with the universality result of Furuya et al. 2024. Therefore, I am not sure the contribution is strong mathematically.
  2. The setting seems very niche and not well motivated (at least to me). This applies both to the problem and the architecture they choose. There are several aspects one could complain about. On the one hand, we could ask if Wasserstein distance is appropriate for length-independent universality as for large input and large attention matrices a small W_d is consistent with large variation on individual rows. On the other hand, their continuity assumption excludes simple positional rules, such as using the first token to switch the attention pattern across the sequence, uniformly over unbounded lengths. Positional embeddings do not resolve this because each token receives mass 1/n1/n. The paper could explain this restriction more.
Questions for authors

Would it be possible to strengthen the result to convergence in total variation rather than just Wasserstein distance?

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

In the spirit of universal function approximation theorems, this paper asks whether a (slightly modified) Transformer can represent any attention-like pattern of token-to-token interactions.

To make the analysis tractable, they consider a few modifications to the standard architecture: Input and output embeddings are represented as probability measures, sums of the delta distributions supported at the token embeddings (possibly with position encodings). For the final output distribution, they consider both ordinary softmax normalization, and Sinkhorn normalization, which forces both marginals. They ignore causal masking and mostly treat the seq2seq case, with input and output texts supplied.

The main result is that for any continuous target rule F specifying token-token relations, if F obeys the relevant support and marginal conditions, then there is some stack of Transformer layers that uniformly approximates F to within epsilon Wasserstein distance.

Critical strengths
  • The writing is clear, and well-structured. Even as a non-specialist, I was able to follow the aims and argument.
  • The fact that they achieve uniform approximation with a single model across input contexts, and particularly input lengths, is impressive, and was the most surprising result to me.
Critical weaknesses
  • There appears to be a mistake in Proposition C7, and its claim as currently stated is not true (flagged by GPT 6.1 Astra Ultra and checked by me and a mathematician colleague). The following is a short counterexample. Let X = {0,1}, Y be a singleton, and F be the product coupling. Let μ₀ put all mass at 0, and μₙ put masses 1−1/n and 1/n at 0 and 1, for n ≥ 2. The density s₀ = (1,2) is admissible at μ₀: its value at 1 is irrelevant, and it produces exactly F. But at every μₙ, the marginal constraint forces the density to be (1,1). Thus every admissible density stays uniform distance 1 from s₀, despite μₙ converging to μ₀.
  • I found it difficult to connect these results to real models in practice. In particular, the addition of some bound on the width or depth of the model, in terms of epsilon and complexity of the target rule, would have been substantially more compelling: which kinds of rule-like attention patterns are approximable with different model sizes? An analysis like this would have also helped to give even a rough order-of-magnitude estimate of the model sizes required to approximate certain rule sets well. Treatment of causal masking would also help connect to real models. All of this said, I recognize that (a) giving size bounds would require substantial new work, and (b) the stated contribution is theoretical rather than practical.
  • One might argue that approximating attention patterns is important insofar as it leads to approximating outputs. Of course, though, we already have input-output universality results for Transformers. Can the authors further motivate the need for the separate attention-only result?
  • This could be a limitation of my own understanding, but I didn’t fully understand the motivation for including (and treating at length) the separate Sinkhorn case. The paper cites the Sinkformers paper as saying that attention is often close to doubly stochastic in practice. But given that these empirical results are obtained with ordinary softmax attention, will these not be covered by the present paper’s softmax results? Sinkhorn guarantees exact marginals, but so far I have missed the motivation for wanting them, at least in the common Transformer setting.
Questions for authors

Is it possible to repair C7?

Reviewer_iqhqOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This work frames the softmax inner produces of transformers in probabilistic/measure-theoretic language. A text, represented as a sequence of embeddings (x1,...,xn)(x_1, ..., x_n) is represented as the empirical measure μ=1n∑iδxi\mu = \tfrac{1}{n} \sum_i \delta_{x_i}. Then, the summation in the normalization of a softmax is written as an integral over this discrete measure. A transformer is represented in measure-theoretic terms through this process. The main result and contribution of this work is to show that softmax scores (of arbitrary functions of the input) can approximate any continuous mapping F:P(X)×P(Y)→K(Y∣X)F: P(X) \times P(Y) \to K(Y|X) (a "conditional system").

Critical strengths
  • The probabilistic / measure-theoretic perspective
  • The softmax vs sinkhorn distinction is potentially interesting and is stated cleanly.
  • The proofs appear to be mostly correct and are generally organized and clearly written (Proofs in the appendix were checked primarily by an AI agent. I also checked certain key steps, and verified its findings. There is one fixable issue stated below)
Critical weaknesses
  • The biggest concern is that the technical contribution appears to be limited compared to the prior work of Furuya, which establishes a universal approximation for any "in-context map" Λ:P(Ω)×Ω→Rd\Lambda: P(\Omega) \times \Omega \to \reals^d. This is a core ingredient of the analysis in this work, and also seems to be the only part of the analysis that is truly transformer-specific. The paper understates this, saying that Furuya et al's result "restricts its universality bounds to the codomain Rd\mathbb R^d", but this result is a critical part of the analysis in the paper. This should be discussed in the main text.
  • Beyond the application of Furuya et al's Theorem 1, the analysis has limited connection to real transformers. The transformer encoder is used as a blackbox universal approximator of functions Λ:P(Ω)×Ω→Rd\Lambda: P(\Omega) \times \Omega \to \reals^d, and the analysis mainly just shows "a softmax of an arbitrary continuous function of (x,μ,y,ν)(x, \mu, y, \nu) can approximate any continuous kernel system".
  • The results are crude, as they lack any quantitative statement about the size of the transformer needed to approximate a given coupling system or conditional system. This seems to be because Stone-Weierstrass can only provide density, but not a quantitative bound on the size or complexity needed to approximate.
  • The "Contextual Transformer" deviates from how transformers are applied in practice, and it's not clearly argued why one should be interested in such a model. Too much emphasis is placed on the "two-text" case, which doesn't align with autoregressive transformer language model.
  • Writing and presentation issues: Section 3 "Problem Statement" was hard to follow because it was too high-level, yet frequently referred to jargon such as "Contextual relation" before it was defined. It can probably be cut out, or at least the preliminaries of Section 4 should be presented first. Figure 2 is also unclear. I think it is trying to justify the "contextual transformer" by arguing that the encoder-decoder transformer of Vaswani et al include inside them something like it, but this point was not made clearly.
  • There is potentially an issue with the statement of Proposition C.7. Condition (2) in the definition of Γ(μ,ν)\Gamma(\mu,\nu) only constrains ff on the support of μ⊗ν\mu \otimes \nu. But lower hemicontinuity is claimed in on all of X×YX \times Y (i.e., uniformly). This seems fixable, e.g., by requiring ff to be normalized at every point, which holds in later results.

Formatting: the font seems different from iclr format font. It looks lighter.

Questions for authors
  • Can the results be made more quantitative? I.e., to give a bound on the size of the transformer needed to achieve a given approximation error.
  • Can the authors clarify what they view to be novel in their analysis over Furuya et al., and, in particular, if anything would change if transformer encoders are replaced by any other universal approximator of continuous in-context maps P(Ω)×Ω→RmP(\Omega)\times\Omega\to R^m? Does the analysis use anything specific about transformers, beyond the application of the Furuya et al theorem?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.