Vocabulary In-Context Learning in Transformers: Benefits of Positional Encoding

AI summary

Overview

Research area: Theoretical machine learning — specifically approximation theory for Transformer architectures, in-context learning (ICL), and the role of positional encoding.

Technical level: Advanced. The paper is written in the language of functional analysis, universal approximation theorems, and formal proofs. Readers need comfort with vector spaces, dense sets, matrix partitions, and the distinction between element-wise and normalization-based activation functions.

Scope: The paper characterizes exactly when single-layer Transformers can universally approximate continuous functions when their in-context examples are drawn from a finite vocabulary, and shows that positional encoding is the deciding ingredient.

What This Paper Is About

Transformers can be controlled by the context they are given rather than by changing their weights, which is what makes in-context learning work in practice. Real language models receive inputs from a finite vocabulary of tokens, not arbitrary points in Euclidean space, so the paper asks whether a single-layer Transformer can approximate any continuous target function purely by choosing which vocabulary tokens appear in its context. The authors prove that without positional encoding this is impossible, and that adding positional encoding restores the ability to approximate anything.

Key Contributions

1. A bridge between feed-forward networks and Transformers. The authors prove (Lemma 3) that for any one-hidden-layer network with n hidden neurons there exist context matrices X and Y such that a single-layer Transformer satisfying their sparsity assumption produces exactly the same output. Lemma 4 turns this into a universal approximation statement for ICL, where the context acts as the control parameter while the Transformer's weights and biases stay fixed.

2. An impossibility result for finite vocabularies without positional encoding. Under the finite-vocabulary setting they call VICL (vocabulary in-context learning), they show that single-layer Transformers without positional encoding cannot achieve the universal approximation property (Theorem 6), following from the analogous result for finite-parameter feed-forward networks (Lemma 5).

3. A possibility result once positional encoding is added. Theorem 7 gives sufficient conditions under which single-layer Transformers with positional encoding do achieve the universal approximation property, using the Kronecker Approximation Theorem as the key auxiliary tool.

4. Relaxed conditions for specific activations. Theorem 8 shows that the density requirement on the positional encoding can be weakened considerably for Transformers with ReLU activation (density in the cube [-1, 1]^{d_x} suffices) and, even more so, for Transformers with exponential activation, where density in a neighborhood of a single point suffices.

Main Findings

• Without positional encoding, VICL fails to be universal. Theorem 6 states there exist a compact domain, a continuous target function f, and a fixed ε₀ > 0 such that the maximum error over the domain is at least ε₀ for every Transformer in the class. The result is first proved for finite-parameter feed-forward networks (Lemma 5) and then transferred to Transformers via Lemma 3.

• The obstruction is finite dimensionality. For element-wise activations, the span of the finite-parameter network class is a finite-dimensional function space, and finite-dimensional subspaces are closed in the sup norm, so functions outside that span cannot be arbitrarily approximated. For softmax networks, normalization prevents the class from being a simple linear combination of units; the authors introduce Proposition 12, which bounds how many zeros functions in the softmax class can have, and explicitly construct functions exceeding that bound.

• The impossibility result is robust. Theorem 6 holds even without imposing constraints on V, Q, and K such as the sparse partition used elsewhere; the authors state this relaxation in Appendix F.

• Positional encoding is sufficient for universality. Theorem 7 states that if the set S = V_x + P_x (vocabulary vectors plus positional encodings) is dense in ℝ^{d_x}, if {1, −1, √2, 0}^{d_y} is contained in the output vocabulary V_y, and if the output positional encoding P_y = 0, then the Transformer class achieves the universal approximation property.

• Density is achievable in practice only with unbounded encodings. Since the vocabulary V_x has finitely many elements and is therefore bounded, the authors note that for S to be dense in the whole space, the positional encoding P_x must be unbounded.

• ReLU and exponential activations need much weaker conditions. For ReLU networks, the positive homogeneity identity A·ReLU(Wx̃) = λ^{-1}A·ReLU(λWx̃) for λ > 0 lets the weight matrix be restricted to entries in [-1, 1] without losing approximation power, so density of S in [-1, 1]^{d_x} is enough. For exponential networks, density of S only in a neighborhood B(w*, δ) of some point w* with radius δ > 0 is enough, a relaxation the authors attribute to a property of derivatives of exponential functions.

• The construction is explicit. Given a target network with k hidden neurons, the authors approximate each weight vector w̃_i by vectors of the form x_P B^T C with x_P in S, and each output coefficient a_i by q√2 ± l for positive integers q and l. Positions where the vocabulary token is close to the target weight are marked "valid"; others are declared "invalid" and assigned y^(i) = 0 to nullify their contribution. Among the valid positions, y^(i) = √2 is assigned at q of them and y^(i) = ±1 at the other l.

• No empirical results are reported. The paper contains no experiments, benchmarks, datasets, or trained model evaluations; all results are lemmas, propositions, and theorems with proofs in the appendices.

Methodology in Plain English

The paper works entirely through mathematical proof rather than experiment. The authors start from the well-established fact that one-hidden-layer feed-forward networks can approximate any continuous function on a compact domain (Lemma 2). They then show algebraically that a single-layer Transformer, under a specific sparsity pattern on its query, key, and value matrices, computes exactly the same thing as such a network. The sparsity pattern assumes Q and K only act on the input part of each token, V has a block structure, and the parameter F is set to zero; it also assumes the matrices B, C, and U are non-singular, which the authors justify by noting that a randomly initialized square matrix is non-singular with probability one.

With that equivalence in hand, they can transport known facts about feed-forward networks to Transformers. Since a finite vocabulary yields only finitely many possible weight configurations, the resulting function class is limited, which gives the negative result. To get the positive result, they add positional encodings that grow with position, so the set of possible input-plus-position values becomes dense in the input space. They then invoke the Kronecker Approximation Theorem to find integers q and l making q√2 ± l arbitrarily close to any desired output coefficient, and build the context token by token until the desired network is reproduced. For ReLU and exponential activations they use scaling and derivative properties to shrink the region in which density is required.

Why This Matters

This work gives a theoretical reason why positional encoding is not merely a convenience for sequence order but a functional necessity for in-context learning with finite vocabularies. It provides a clear dividing line — universality is lost without it and recoverable with it — and it grounds the practical observation that context can substitute for weight updates in a rigorous approximation-theoretic framework.

Potential real-world applications (these follow from the paper's framing of ICL, prompting, chain of thought, and retrieval-augmented generation; the paper does not itself report deployed systems or evaluations):

• Prompt engineering for large language models, where the choice and ordering of in-context examples determines behavior.
• Retrieval-augmented generation, where grounding documents are prepended to the input and function as additional context.
• Few-shot and zero-shot adaptation, where a model's effective function is changed by presentation of input rather than by fine-tuning.
• Chain-of-thought style prompting, where intermediate tokens in the context steer the model's output.

Industry relevance: The result speaks to how much capability can be extracted from a frozen model by manipulating its input, which is the central economic argument for prompting and retrieval over retraining. The finding that unbounded positional encodings are needed for density also raises a design question about the encodings used in deployed systems.

Future Directions

• Other forms of positional encoding. The authors state that Theorem 7 assumes density of S and requires P_x to be unbounded; they discuss in Appendix E.4 whether other forms of positional encoding can also achieve the universal approximation property. Relative positional encodings are cited from prior work as lacking the property, which leaves the landscape of which encoding schemes suffice as an open question.

• Relaxing the architectural assumptions. The assumption F = 0 in the sparsity partition is stated to be relaxable, with discussion deferred to Appendix F. How far the block structure on Q, K, and V can be weakened without losing the results is left open.

• Extending beyond a single layer and a single head. The paper restricts attention to a single-layer self-attention encoder. Prior work cited on convergence and generalization of single-layer multi-head self-attention suggests a natural next target is the multi-head and multi-layer setting.

• Matching theory to practice. Because the sufficient condition requires an unbounded positional encoding, an open practical question is what weaker guarantees hold for the bounded encodings actually used in deployed language models.

Target Audience

This paper is aimed at theoretical machine learning researchers working on approximation theory, expressivity of neural architectures, and the mathematical foundations of in-context learning. It is also relevant to readers with a strong mathematical background who want to understand why positional encoding matters from first principles, and to practitioners who follow expressivity results to inform architecture and prompt design decisions.

Authors’ abstract

Numerous studies have demonstrated that the Transformer architecture possesses the capability for in-context learning (ICL). In scenarios involving function approximation, context can serve as a control parameter for the model, endowing it with the universal approximation property (UAP). In practice, context is represented by tokens from a finite set, referred to as a vocabulary, which is the case considered in this paper, \emph{i.e.}, vocabulary in-context learning (VICL). We demonstrate that VICL in single-layer Transformers, without positional encoding, does not possess the UAP; however, it is possible to achieve the UAP when positional encoding is included. Several sufficient conditions for the positional encoding are provided. Our findings reveal the benefits of positional encoding from an approximation theory perspective in the context of ICL.