Positional Attention: Expressivity and Learnability of Algorithmic Computation

• URL: http://arxiv.org/abs/2410.01686v2
• Date: Sat, 01 Feb 2025 04:14:51 GMT
• Title: Positional Attention: Expressivity and Learnability of Algorithmic Computation
• Authors: Artur Back de Luca, George Giapitzakis, Shenghao Yang, Petar Veličković, Kimon Fountoulakis,
• Abstract summary: This work aims to better understand the role of attention in Transformers for algorithmic execution.<n>We prove that Transformers with positional attention (positional Transformers) maintain the same expressivity of parallel computational models.<n>Our results show that positional Transformers introduce a learning trade-off: while they exhibit better theoretical dependence on parameter norms, certain tasks may require more layers.
• Score: 6.181408276896225
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There is a growing interest in the ability of neural networks to execute algorithmic tasks (e.g., arithmetic, summary statistics, and sorting). The goal of this work is to better understand the role of attention in Transformers for algorithmic execution. Its importance for algorithmic execution has been studied theoretically and empirically using parallel computational models. Notably, many parallel algorithms communicate between processors solely using positional information. Inspired by this observation, we investigate how Transformers can execute algorithms using positional attention, where attention weights depend exclusively on positional encodings. We prove that Transformers with positional attention (positional Transformers) maintain the same expressivity of parallel computational models, incurring a logarithmic depth cost relative to the input length. We analyze their in-distribution learnability and explore how parameter norms in positional attention affect sample complexity. Our results show that positional Transformers introduce a learning trade-off: while they exhibit better theoretical dependence on parameter norms, certain tasks may require more layers, which can, in turn, increase sample complexity. Finally, we empirically explore the out-of-distribution performance of positional Transformers and find that they perform well in tasks where their underlying algorithmic solution relies on positional information.

Related papers

• Toward Relative Positional Encoding in Spiking Transformers [52.62008099390541]
  Spiking neural networks (SNNs) are bio-inspired networks that model how neurons in the brain communicate through discrete spikes. In this paper, we introduce an approximate method for relative positional encoding (RPE) in Spiking Transformers.
  arXiv  Detail & Related papers  (2025-01-28T06:42:37Z)
• Continual Low-Rank Scaled Dot-product Attention [67.11704350478475]
  We introduce a new formulation of the Scaled-product Attention based on the Nystr"om approximation that is suitable for Continual Inference. In experiments on Online Audio Classification and Online Action Detection tasks, the proposed Continual Scaled Dot-product Attention can lower the number of operations by up to three orders of magnitude.
  arXiv  Detail & Related papers  (2024-12-04T11:05:01Z)
• DAPE V2: Process Attention Score as Feature Map for Length Extrapolation [63.87956583202729]
  We conceptualize attention as a feature map and apply the convolution operator to mimic the processing methods in computer vision. The novel insight, which can be adapted to various attention-related models, reveals that the current Transformer architecture has the potential for further evolution.
  arXiv  Detail & Related papers  (2024-10-07T07:21:49Z)
• Contextual Counting: A Mechanistic Study of Transformers on a Quantitative Task [40.85615657802704]
  This paper introduces the contextual counting task, a novel toy problem aimed at enhancing our understanding of Transformers. We present theoretical and empirical analysis using both causal and non-causal Transformer architectures.
  arXiv  Detail & Related papers  (2024-05-30T20:52:23Z)
• Understanding Transformer Reasoning Capabilities via Graph Algorithms [25.08208816144745]
  We study which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems. Our results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks.
  arXiv  Detail & Related papers  (2024-05-28T18:31:14Z)
• CRoFT: Robust Fine-Tuning with Concurrent Optimization for OOD Generalization and Open-Set OOD Detection [42.33618249731874]
  We show that minimizing the magnitude of energy scores on training data leads to domain-consistent Hessians of classification loss. We have developed a unified fine-tuning framework that allows for concurrent optimization of both tasks.
  arXiv  Detail & Related papers  (2024-05-26T03:28:59Z)
• Transformers, parallel computation, and logarithmic depth [33.659870765923884]
  We show that a constant number of self-attention layers can efficiently simulate, and be simulated by, a constant number of communication rounds of Massively Parallel Computation.
  arXiv  Detail & Related papers  (2024-02-14T15:54:55Z)
• Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions [32.59746882017483]
  We show that Transformers can learn to implement two distinct algorithms to solve a single task. We also show that extant Large Language Models (LLMs) can compete with nearest-neighbor baselines on prediction tasks.
  arXiv  Detail & Related papers  (2023-10-04T17:57:33Z)
• DIVERSIFY: A General Framework for Time Series Out-of-distribution Detection and Generalization [58.704753031608625]
  Time series is one of the most challenging modalities in machine learning research. OOD detection and generalization on time series tend to suffer due to its non-stationary property. We propose DIVERSIFY, a framework for OOD detection and generalization on dynamic distributions of time series.
  arXiv  Detail & Related papers  (2023-08-04T12:27:11Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  This work first provides a comprehensive statistical theory for transformers to perform ICL. We show that transformers can implement a broad class of standard machine learning algorithms in context. A emphsingle transformer can adaptively select different base ICL algorithms.
  arXiv  Detail & Related papers  (2023-06-07T17:59:31Z)
• Representational Strengths and Limitations of Transformers [33.659870765923884]
  We establish both positive and negative results on the representation power of attention layers. We show the necessity and role of a large embedding dimension in a transformer. We also present natural variants that can be efficiently solved by attention layers.
  arXiv  Detail & Related papers  (2023-06-05T14:05:04Z)
• On the Importance of Feature Separability in Predicting Out-Of-Distribution Error [25.995311155942016]
  We propose a dataset-level score based upon feature dispersion to estimate the test accuracy under distribution shift. Our method is inspired by desirable properties of features in representation learning: high inter-class dispersion and high intra-class compactness.
  arXiv  Detail & Related papers  (2023-03-27T09:52:59Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• Self-supervised debiasing using low rank regularization [59.84695042540525]
  Spurious correlations can cause strong biases in deep neural networks, impairing generalization ability. We propose a self-supervised debiasing framework potentially compatible with unlabeled samples. Remarkably, the proposed debiasing framework significantly improves the generalization performance of self-supervised learning baselines.
  arXiv  Detail & Related papers  (2022-10-11T08:26:19Z)
• Invariant Causal Mechanisms through Distribution Matching [86.07327840293894]
  In this work we provide a causal perspective and a new algorithm for learning invariant representations. Empirically we show that this algorithm works well on a diverse set of tasks and in particular we observe state-of-the-art performance on domain generalization.
  arXiv  Detail & Related papers  (2022-06-23T12:06:54Z)
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding [63.539333383965726]
  We propose a novel way to accelerate attention calculation for Transformers with relative positional encoding (RPE) Based upon the observation that relative positional encoding forms a Toeplitz matrix, we mathematically show that kernelized attention with RPE can be calculated efficiently using Fast Fourier Transform (FFT)
  arXiv  Detail & Related papers  (2021-06-23T17:51:26Z)
• Predicting Deep Neural Network Generalization with Perturbation Response Curves [58.8755389068888]
  We propose a new framework for evaluating the generalization capabilities of trained networks. Specifically, we introduce two new measures for accurately predicting generalization gaps. We attain better predictive scores than the current state-of-the-art measures on a majority of tasks in the Predicting Generalization in Deep Learning (PGDL) NeurIPS 2020 competition.
  arXiv  Detail & Related papers  (2021-06-09T01:37:36Z)
• Translational Equivariance in Kernelizable Attention [3.236198583140341]
  We show how translational equivariance can be implemented in efficient Transformers based on kernelizable attention. Our experiments highlight that the devised approach significantly improves robustness of Performers to shifts of input images.
  arXiv  Detail & Related papers  (2021-02-15T17:14:15Z)
• Learning Hard Retrieval Decoder Attention for Transformers [69.40942736249397]
  Transformer translation model is based on the multi-head attention mechanism, which can be parallelized easily. We show that our hard retrieval attention mechanism is 1.43 times faster in decoding.
  arXiv  Detail & Related papers  (2020-09-30T13:18:57Z)
• MUTANT: A Training Paradigm for Out-of-Distribution Generalization in Visual Question Answering [58.30291671877342]
  We present MUTANT, a training paradigm that exposes the model to perceptually similar, yet semantically distinct mutations of the input. MUTANT establishes a new state-of-the-art accuracy on VQA-CP with a $10.57%$ improvement.
  arXiv  Detail & Related papers  (2020-09-18T00:22:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.