Research map / Architectures and efficiency / Attention and transformers
Positional Attention: Expressivity and Learnability of Algorithmic Computation
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.
Introduces positional Transformers whose attention depends only on fixed positional encodings, proves they can simulate MPC with O(log n) depth overhead, gives a norm-based generalization bound, and empirically compares ID/OOD performance with standard Transformers on algorithmic tasks.
Problem
Understanding whether Transformers can execute parallel algorithmic computation when attention weights depend only on positional information, and how this affects expressivity, learnability, and out-of-distribution generalization.
Approach
Decouple attention from input values: attention matrices are computed solely from fixed positional encodings P (constant across layers), while values come from the layer input. This mirrors data-agnostic communication in many parallel algorithms, is shown to match MPC expressivity with logarithmic depth overhead, and removes the dependence of the generalization bound on key/query spectral norms.
Key results
- Positional Transformers match standard Transformers in-distribution on the five algorithmic tasks, with loss decreasing as training samples grow (n=8, 5k-50k samples).
- On k-hop induction heads, standard Transformers reach near-zero in-distribution loss with about three layers, while positional Transformers generally perform worse and need more layers.
- Positional Transformers achieve more stable OOD performance than standard Transformers across scale factors on the algorithmic tasks and outperform standard Transformers on the mixed-type input task, but both fail on k-hop induction heads OOD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use positional attention instead of standard self-attention | Positional Transformer · Cumulative sum, cumulative min, cumulative median, sorting, and cumulative maximum sum subarray (OOD) | loss | Helped |
| Use positional attention instead of standard self-attention | Positional Transformer · k-hop induction heads (in-distribution) | loss | Hurt |
| Increase the number of training samples | Standard and positional Transformers · Cumulative sum, cumulative min, cumulative median, sorting, and cumulative maximum sum subarray (in-distribution) | loss | Helped |
| Use positional attention instead of standard self-attention | Positional Transformer · k-hop induction heads (OOD) | loss | Hurt |
| Use positional attention instead of standard self-attention | Positional Transformer · Mixed-type input task (OOD; minimum, sum, and multi-task min/max) | loss | Helped |
Surprising findings
- Positional Transformers perform poorly on k-hop induction heads, even OOD, suggesting that tasks requiring dynamic, input-dependent communication are hard for positional attention.
- The expressivity result carries a quadratic node-count overhead when simulating standard Transformers, and the authors note the theorem's head count was inconsistent across versions (s vs 2s).
Limitations
- Fixed positional encodings limit applicability to longer inputs and length generalization.
- Positional attention performs poorly on tasks requiring dynamic, input-dependent communication such as k-hop induction heads.
- Existing OOD generalization bounds are not tight; the simulation of standard Transformers incurs quadratic node overhead.
Experimental setup
Datasets: synthetic algorithmic task data (cumulative sum, cumulative min, cumulative median, sorting, cumulative max sum subarray k-hop induction heads (synthetic) mixed-type category-value task (synthetic)
Benchmarks: in-distribution loss on five algorithmic tasks k-hop induction heads out-of-distribution scale-factor tests on algorithmic tasks mixed-type input task (min, sum, min/max)
Metrics: loss (MSE) MAPE
Baselines: standard Transformer with self-attention Transformer with RoPE fine-tuned GPT-2
Builds on: Transformers simulate MPC (Sanford et al.) Benes networks norm-based Transformer generalization bounds (Edelman et al.) position-based attention (Shaw/Luong-style)
Closest papers by meaning
- On the Emergence of Position Bias in Transformers (ICML 2025 · similarity 0.87)
- Fast attention mechanisms: a tale of parallelism (NeurIPS 2025 · similarity 0.87)
- Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases (NeurIPS 2026 · similarity 0.87)
- Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure (NeurIPS 2024 · similarity 0.87)
- Learning Linear Attention in Polynomial Time (NeurIPS 2025 · similarity 0.86)
- Transformers Converge to Invariant Algorithmic Cores (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.