Research map / Architectures and efficiency / Attention and transformers

Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling

NeurIPS 2024 · Architectures and efficiency › Attention and transformers · approach: Sparse efficient transformers for long context · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Theoretically characterizes the approximation rates of Transformers (with dot-product-free attention, log/linear relative positional encodings, and FFN width) for sequence modeling with fixed, adaptive, and essentially sparse long-range memories, with validating experiments.

Problem

Understanding what Transformer components (dot-product attention, positional encoding, FFN, depth, heads, width) contribute to expressive power for sequence modeling with long, sparse, and complicated memory.

Approach

Establishes explicit approximation rates for Transformers on three memory classes (fixed sparse, adaptive/nested sparse, essentially sparse via convolution kernels), showing attention heads extract memory tokens via RPE kernels, FFNs approximate readout and memory functions, depth handles nested memory, dot-product is unnecessary for fixed memory but needed for adaptive memory, and log-RPE overcom

Key results

• For fixed M-sparse memories, one-layer dot-product-free Transformer approximates with error E_FFN + ||f||_Lip E_Attn, where head requirement grows exponentially in T for lin-RPE and polynomially for log-RPE.
• Proposition shows one-layer DP-free attention has a uniform lower bound of 2/3 on a target that DP attention approximates arbitrarily well.
• Log-RPE Transformers handle polynomially decaying memory kernels with polynomially many heads, overcoming the curse of memory faced by RNNs.

Surprising findings

• One-layer dot-product-free Transformers can model fixed sparse memories, challenging the view that dot-product is needed for sparse Boolean functions.
• Depth reduces the required number of heads and width for memories without nesting, with M+1 layers needing max rather than sum complexity.

Limitations

• Results are approximation-theoretic upper bounds and do not address training dynamics or optimization.
• Experimental validation is deferred to the appendix and is limited to toy models and small pre-training in the provided text.

Experimental setup

Metrics: approximation error bound

Baselines: RNN LSTM standard dot-product Transformer

Builds on: Barron space approximation theory T5 relative positional encoding KERPLE Alibi

Closest papers by meaning

• Approximation Rate of the Transformer Architecture for Sequence Modeling (NeurIPS 2024 · similarity 0.92)
• Dynamical Properties of Tokens in Self-Attention and Effects of Positional Encoding (NeurIPS 2025 · similarity 0.90)
• Counting in Small Transformers: The Delicate Interplay between Attention and Feed-Forward Layers (ICML 2025 · similarity 0.89)
• Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators? (ICLR 2024 · similarity 0.89)
• Prompting a Pretrained Transformer Can Be a Universal Approximator (ICML 2024 · similarity 0.89)
• What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Tasks (ICML 2024 · similarity 0.88)