PaperlayerView exact revision on arXiv

Source-linked AI summary

Inductive Biases and Variable Creation in Self-Attention Mechanisms

Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Cyril Zhang

arXiv:2110.10090v2cs.LGstat.ML

TL;DR

Self-attention’s empirical success leaves open which functions its architecture prefers and how its capacity depends on context length. The paper analyzes this question through covering-number bounds, sparse-function representation constructions, and synthetic Boolean-learning experiments. It finds that bounded-norm self-attention creates sparse variables, with sample complexity scaling logarithmically in context length.

  • Problem

    The paper asks which functions and long-range dependencies self-attention networks prefer, addressing a lack of formal statistical analysis.

  • Method

    The paper combines norm-based covering-number capacity bounds, constructions representing sparse functions, and synthetic experiments on sparse Boolean functions.

  • Results

    Bounded-norm self-attention can represent sparse functions while requiring sample complexity that scales logarithmically with context length.

  • Takeaways & Limitations

    The analysis provides a theoretical account of how attention models can learn long-range dependencies without overfitting.

  • Takeaways & Limitations

    The theory does not resolve the computational analogue of learning sparse parities or the roles of depth and optimization trajectories.

Abstract

from arXiv · show

Self-attention, an architectural motif designed to model long-range interactions in sequential data, has driven numerous recent breakthroughs in natural language processing and beyond. This work provides a theoretical analysis of the inductive biases of self-attention modules. Our focus is to rigorously establish which functions and long-range dependencies self-attention blocks prefer to represent. Our main result shows that bounded-norm Transformer networks "create sparse variables": a single self-attention head can represent a sparse function of the input sequence, with sample complexity scaling only logarithmically with the context length. To support our analysis, we present synthetic experiments to probe the sample complexity of learning sparse Boolean functions with Transformers.

1 Introduction

The paper frames self-attention as a successful architecture whose inductive biases remain theoretically underformalized. It proposes sparse variable creation as an explanation for how bounded-norm attention can learn sparse long-range dependencies, supported by theory and synthetic experiments.

  • Self-attention has achieved broad empirical success across sequence modeling, representation learning, and multiple data modalities.
  • The paper addresses the missing formal analysis of which functions and dependencies self-attention networks prefer to represent.
  • Bounded-norm self-attention heads can learn sparse functions of length-T contexts with sample complexity scaling as log(T).
  • Synthetic experiments train Transformers on randomly indexed sparse Boolean functions and corroborate the predicted logarithmic sample-complexity scaling.
  • The work develops a norm-based capacity analysis for attention models that complements prior neural-network generalization theory.

2 Background and notation

This section establishes notation for length-T embedding sequences and introduces covering numbers as the capacity measure used to derive generalization bounds. The relevant covering-number dependence is logarithmic in sample size, supporting later attention analyses.

  • The context X is a length-T sequence of d-dimensional embeddings, and m denotes the number of such sequences in a dataset.
  • A covering number is the smallest size of a function collection approximating every function in a class within a specified norm tolerance.
  • The supremum covering number takes the worst case over collections of m input points.
  • For linear functions, the covering-number bound depends only logarithmically on the sample size m.
  • Log-covering-number bounds imply uniform generalization bounds through a standard probabilistic argument.

3 Abstractions of (self-)attention

The paper formalizes attention as context-dependent mixing: alignment scores are normalized into weights that combine transformed inputs. Self-attention specializes this mechanism by deriving context from the sequence itself, while Transformer layers share parameters across output heads.

  • 3.1 Attention: An attention head uses a learned context-dependent score to select and mix parts of an input sequence.
  • 3.1 Attention: An attention head maps transformed inputs through normalized alignment scores and position-wise input and output maps.
  • 3.2 Self-attention and Transformers: A self-attention head obtains its context from an input element, so pairwise interactions determine which sequence elements affect its output.
  • 3.2 Self-attention and Transformers: A Transformer layer is a collection of T attention heads whose parameters are shared across the layer.
  • 3.2 Self-attention and Transformers: The formal Transformer layer uses quadratic alignment scores, a linear output map with a Lipschitz activation, and T-dimensional softmax normalization.
  • 3.2 Self-attention and Transformers: A special [CLS] input can provide a scalar linear readout from a Transformer layer for real-valued prediction.

4 Capacity bounds for attention modules

The paper analyzes attention capacity with covering-number bounds while controlling dependence on sequence length. These bounds are designed to yield sample-complexity guarantees that scale logarithmically with context length.

  • The capacity analysis covers generic attention heads, Transformer heads, and full depth-L Transformer networks using covering numbers.
  • The resulting Transformer sample-complexity guarantees scale only logarithmically in the context length T.
  • The analysis assumes each input embedding has bounded Euclidean norm, while allowing the Frobenius norm of the sequence matrix to grow with T.
  • The proof constructs covers that avoid factors involving norms summed over the sequence dimension.
  • The scalar attention class is formed by applying a bounded-norm linear readout to vector-valued attention-head outputs.

3. Norm is continuously differentiable and its Jacobian satisfies

The paper develops covering-number capacity bounds for attention heads and Transformer networks, showing that context-length dependence can remain logarithmic under bounded norms. The analysis also identifies how architectural components and norm assumptions affect these bounds.

  • Capacity bounds: Theorem 4.2 bounds attention-head capacity using covering numbers of the score and input-function classes.The proof uses Lipschitzness to combine covers for these component classes.
  • Capacity bounds: Logarithmic dependence on T follows because the relevant covering number scales logarithmically with the number of samples used to cover the context.The bound otherwise depends on dimensions such as d and k rather than directly on T.
  • Capacity bounds: Unbounded-norm Transformer self-attention heads have pseudo-dimension at least ⌊log T⌋ when d = 3.This establishes nonconstant capacity growth with context length even for a single head.
  • Architectural components: Fixed positional embeddings preserve the analysis, but training them from a sufficiently large class can make the log-covering-number dependence on T linear.Residual connections change the bounds by at most a constant factor, whereas multiple heads introduce a poly(H) factor.
  • Deep networks: For deeper Transformer networks, dependence on d and T remains logarithmic, while dependence on matrix (2,1)-norms is quadratic.Bounded spectral norms and a 1-Lipschitz activation avoid exponential dependence on depth L.

5 Attention approximates sparse functions

The paper shows that bounded-norm Transformer blocks can represent sparse Boolean functions by selecting relevant input coordinates and processing their values. These constructions provide exact or approximate representations with norms scaling modestly in context length and sparsity.

  • Representational results: Transformer blocks can represent all Boolean functions depending on any fixed s-coordinate subset of a length-T input.The attention head keeps the relevant coordinates while the feedforward network memorizes function values on them.
  • Representational results: A single Transformer head can approximate a monotone symmetric s-sparse Boolean function with ∥WQ∥F ≤ O(log(Ts)) and other Transformer norms O(s).The guarantee applies under each of the paper’s input mappings.
  • Representational results: The Transformer-plus-MLP construction exactly represents symmetric s-sparse functions with feedforward weights bounded by O(poly(s)).The Transformer weight norms remain those given for the sparse-variable construction.
  • Representational results: The Transformer-plus-MLP construction exactly represents general s-sparse functions with feedforward weights bounded by O(2^s · poly(s)).The exponential dependence appears in the feedforward network rather than the stated Transformer weight norms.
  • Implications: For s ≪ log T, the representation and capacity results jointly imply sparse-regression-like sample complexity in the context length.For s = 2, a single head can implement a logical gate with embedding dimension and weight norms scaling as log T.

6 Experiments

Synthetic experiments test whether Transformers learn randomly located sparse Boolean functions efficiently as context length grows. The experiments reproduce logarithmic sample-complexity scaling, show attention suppression of irrelevant coordinates, and reveal successful learning of sparse parities beyond the statistical analysis.

  • Experimental setup: The synthetic benchmark measures the smallest sample size at which Transformer training succeeds with non-negligible probability for randomly selected sparse Boolean functions.The main conjunction experiments use fixed sparsity s = 3 and i.i.d. Bernoulli inputs.
  • Sparse conjunctions: Reducing the sample size below threshold increases overfitting, even when training accuracy reaches 100%.For T = 300, the figure compares m = 200 above and m = 50 below a threshold of approximately 70.
  • Sparse conjunctions: Attention weights vanish on the T − s irrelevant coordinates, and trained models converge to sparse solutions despite large input support and parameter count.The reported scaling plots required extensive variance reduction because training near the statistical threshold was extremely unstable.
  • Sparse parities: Transformers can learn sparse parity functions from i.i.d. samples, although the paper leaves the computational mechanism behind this success unresolved.The authors frame this as a computational question beyond the current statistical analysis.

7 Conclusion and future work

The work identifies sparse variable creation as an inductive bias of bounded-norm self-attention and supports it with capacity analysis and constructions. It also highlights unresolved questions about theory-practice alignment and connections to empirical Transformer interpretability.

  • Conclusion: Bounded-norm self-attention exhibits sparse variable creation: it can represent sparse functions while its capacity bounds scale logarithmically with context length.The analysis uses covering-number arguments and constructions demonstrating sparse-function representation.
  • Future work: The paper identifies open challenges in refining covering and representation bounds and understanding the roles of depth and optimization trajectories.The authors note that their representation analysis does not exploit MLP structure beyond exhaustive memorization.
  • Future work: The authors connect their theoretical sparsity analysis to empirical work interpreting attention activations in Transformer language models.They describe reconciliation with BERTology as an avenue for future synthesis.
  • Capacity: Unbounded Transformer self-attention heads have pseudo-dimension that grows at least logarithmically with context length, even with embedding dimension 3.The result shows why parameter counting alone does not determine capacity.
  • Capacity: The lower-bound construction uses binary positional encodings so attention weights select a coordinate and different choices induce shattering.The construction indexes positions through binary expansions of their integer indices.

A.4 Covering number upper bounds

The covering-number analysis decomposes attention into score and input components, then aggregates their approximation errors to obtain capacity bounds. This construction preserves only logarithmic dependence on context length for a Transformer self-attention layer.

  • Cover construction: The cover construction separates approximation of score functions from approximation of input transformations before combining them into a head cover.The resulting head cover approximates every admissible parameter choice on the collection of samples.
  • Context-length dependence: Logarithmic dependence on context length follows because score and input covers aggregate jointly over samples and token positions.The aggregation trick lets the covering number avoid a separate multiplicative dependence on T.
  • Optimization: The proof balances separate cover precisions for score and value parameters to optimize the resulting capacity bound.The optimization is performed under the constraint imposed by the combined approximation error.
  • Matrix covering: The argument builds matrix covers by first covering row norms and then covering rows independently as linear function classes.This decomposition uses norm-controlled linear-function covers for the rows of the parameter matrix.

A.5 Capacity with positional embeddings

Positional embeddings enter the capacity analysis as part of the Transformer input, so the bounds extend to fixed positional embeddings. Training the positional embedding matrix can instead introduce dependence on context length.

  • Capacity bound: The positional-embedding bound depends on the combined input norm BX + BP.The displayed bound scales through the Lipschitz factor evaluated at the sum of the input and positional-embedding norm bounds.
  • Fixed embeddings: Fixed positional embeddings preserve the covering-number bounds because they can be incorporated into the input representation.The positional-embedding case is reduced to the ordinary head bound by evaluating the head on X + P.
  • Trainable embeddings: Training positional embeddings from a sufficiently large class can make the dependence of the log-covering number on T linear.The limitation arises because trainable embeddings require a much finer cover.

A.6 Capacity of multiple parallel heads

The analysis extends covering arguments from one head to parallel heads and deeper Transformer networks by composing per-head and per-layer covers. The construction uses norm control and aggregation across samples and context positions.

  • Parallel heads: Parallel-head capacity is obtained by taking Cartesian products of individual head covers and allocating approximation errors across heads.The resulting bound explicitly depends on the number of heads H.
  • Parallel heads: For equal weight bounds across heads, the covering-number bound includes an H^3 factor.The displayed result gives the dependence for multi-head self-attention when head bounds are identical.
  • Deep networks: The layerwise argument bounds how outputs change when weights and inputs change, using Lipschitz and norm-control estimates.These bounds enable finite covers for each layer and their composition.
  • Deep networks: Deep Transformer covers are constructed inductively by composing covers for successive layers and the final linear output.Layer normalization maintains the required norm bound on intermediate inputs.
  • Input representations: Boolean inputs are mapped to Transformer representations through deterministic, trainable, or permutation-symmetric positional constructions.The bag-of-vectors construction supports swapping positional indicator vectors and composing sparse Boolean functions.

B.2 Results

The results show that bounded-norm Transformer architectures can represent sparse Boolean functions across several input mappings and architectural variants. Self-attention first selects or encodes sparse information, while feedforward networks can extend these representations to arbitrary sparse functions.

  • General representational guarantees: Transformer function classes contain broad families of sparse Boolean functions, including all I-sparse functions under the stated constructions.The formal results are summarized through scalar and multi-head Transformer classes, with precise approximation statements supplied in the appendices.
  • Deterministic positional embeddings: Deterministic positional embeddings support exact representation of symmetric sparse functions with one head and arbitrary sparse functions with s heads.The corresponding feedforward network norms scale as O(poly(s)) for symmetric functions, while the multi-head construction uses vector-valued representations.
  • Trainable positional embeddings: Trainable positional embeddings provide the same one-head and s-head representation pattern, while also learning the positional embedding matrix P.The Transformer and positional-embedding norms follow the constructions for the corresponding approximation lemmas.
  • Bag of vectors: Bag-of-vectors embeddings allow one head to represent arbitrary s-sparse functions, with feedforward network norms scaling as O(poly(s) · 2^s).The same setting also supports symmetric sparse functions with feedforward norms scaling as O(poly(s)).
  • Construction strategy: The construction retains a selected s-dimensional subset of inputs and uses a feedforward network to memorize the function values on those inputs.The self-attention component approximates monotone symmetric or injective sparse functions, after which robust MLP constructions yield arbitrary sparse functions.
  • Scope: The capacity results apply to any input domain with embeddings bounded in the ∥·∥2,∞ norm.This scope condition is noted alongside the observation that Transformers are predominantly used with discrete inputs.

B.5 Proofs

The proofs construct attention heads that select sparse input coordinates, then use feedforward networks to represent Boolean functions of those coordinates. They analyze deterministic and trainable positional embeddings, single and multiple heads, and several input-output formulations.

  • Sparse-coordinate selection: The constructions make softmax attention select the sparse index set I, allowing the head to retain relevant coordinates and discard the rest.The proofs consider deterministic and trainable positional embeddings, as well as scalar and vector-valued inputs and outputs.
  • Head and positional-embedding variants: Single-head and multi-head constructions are analyzed for deterministic and trainable positional embeddings, with multiple heads assigning heads to individual coordinates in I.The multi-head constructions state that each head selects one coordinate in I.

C Details for experiments

The experiments use synthetic sparse Boolean-function tasks to test the predicted logarithmic dependence of sample complexity on context length. Additional descriptions cover training behavior, attention patterns, parity experiments, and the paper’s relationship to prior Transformer research.

  • Sample-complexity experiments: The experiments directly test the predicted log T sample-complexity dependence using synthetic supervised tasks for learning 3-sparse conjunctions.The task grid varies sample size m and context length T under randomly selected sparse index subsets and balanced Bernoulli inputs.
  • Training protocol: A 1-layer Transformer is trained with full-batch Adam and repeated randomized trials, restarts, and holdout validation.The setup uses 40 independent trials, up to five restarts per trial, and cross-validation on held-out samples.
  • Observed training behavior: As the sample size m decreases, trained models overfit more often and show larger variation in validation accuracy when overfitting occurs.Figure 3 compares training curves at T = 300 with m = 200 and m = 50.
  • Attention patterns: At T = 50 and m = 300, a one-head model achieved 100% validation accuracy on 104 holdout samples while producing varied attention weights across validation examples.The attention-weight visualization uses a one-head model with embedding dimensions d = k = 64.
  • Relation to prior work: The related-work discussion distinguishes this paper’s statistical and representational analysis from prior work on universal approximation, attention interpretation, gradient behavior, and synthetic Transformer tasks.The paper describes its analysis as a finer-grained hierarchy of function classes indexed by sparsity s, with tight statistical guarantees in T.
Loading 2110.10090v2…