Self-Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation

• URL: http://arxiv.org/abs/2602.00294v1
• Date: Fri, 30 Jan 2026 20:38:02 GMT
• Title: Self-Attention at Constant Cost per Token via Symmetry-Aware Taylor Approximation
• Abstract summary: We show that self-attention is efficiently computable to arbitrary precision with constant cost per token.<n>Our work enables token generation at modest fixed cost, substantially reducing the infrastructure and energy demands of large-scale Transformer models.
• Score: 1.7188280334580195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The most widely used artificial intelligence (AI) models today are Transformers employing self-attention. In its standard form, self-attention incurs costs that increase with context length, driving demand for storage, compute, and energy that is now outstripping society's ability to provide them. To help address this issue, we show that self-attention is efficiently computable to arbitrary precision with constant cost per token, achieving orders-of-magnitude reductions in memory use and computation. We derive our formulation by decomposing the conventional formulation's Taylor expansion into expressions over symmetric chains of tensor products. We exploit their symmetry to obtain feed-forward transformations that efficiently map queries and keys to coordinates in a minimal polynomial-kernel feature basis. Notably, cost is fixed inversely in proportion to head size, enabling application over a greater number of heads per token than otherwise feasible. We implement our formulation and empirically validate its correctness. Our work enables unbounded token generation at modest fixed cost, substantially reducing the infrastructure and energy demands of large-scale Transformer models. The mathematical techniques we introduce are of independent interest.

Related papers

• Learning to Recall with Transformers Beyond Orthogonal Embeddings [42.18876773867171]
  We analyze a transformer with random embeddings trained with gradient descent on a simple token-retrieval task.<n>Our analysis tracks the early phase'' of gradient descent and yields explicit formulas for the model's storage capacity.
  arXiv  Detail & Related papers  (2026-03-16T21:17:01Z)
• Fast and Simplex: 2-Simplicial Attention in Triton [30.500203127313576]
  We investigate the use of the 2-simplicial Transformer, an architecture that generalizes standard dot-product attention to trilinear functions.<n>For a fixed token budget, similarly sized models outperform their dot-product counterparts on tasks involving mathematics, coding, reasoning, and logic.
  arXiv  Detail & Related papers  (2025-07-03T16:16:34Z)
• Scaling Probabilistic Circuits via Monarch Matrices [109.65822339230853]
  Probabilistic Circuits (PCs) are tractable representations of probability distributions.<n>We propose a novel sparse and structured parameterization for the sum blocks in PCs.
  arXiv  Detail & Related papers  (2025-06-14T07:39:15Z)
• Token Reduction Should Go Beyond Efficiency in Generative Models -- From Vision, Language to Multimodality [29.531450446701175]
  This paper argues that token reduction should transcend its traditional efficiency-oriented role in the era of large generative models.<n>We argue that token reduction can facilitate deeper multimodal integration and alignment, maintain coherence over long inputs, and enhance training stability.<n>We outline promising future directions, including algorithm design, reinforcement learning-guided token reduction, token optimization for in-context learning, and broader ML and scientific domains.
  arXiv  Detail & Related papers  (2025-05-23T11:30:30Z)
• Token Statistics Transformer: Linear-Time Attention via Variational Rate Reduction [29.12836710966048]
  We propose a novel transformer attention operator whose computational complexity scales linearly with the number of tokens.<n>Our results call into question the conventional wisdom that pairwise similarity style attention mechanisms are critical to the success of transformer architectures.
  arXiv  Detail & Related papers  (2024-12-23T18:59:21Z)
• 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.<n>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)
• TokenFormer: Rethinking Transformer Scaling with Tokenized Model Parameters [102.1116808722299]
  We introduce TokenFormer, a scalable architecture for scaling Transformers.<n>By treating model parameters as tokens, we replace all the linear projections in Transformers.<n>Our model scales from 124M to 1.4B parameters by incrementally adding new key-value parameter pairs.
  arXiv  Detail & Related papers  (2024-10-30T16:19:00Z)
• Learning Linear Attention in Polynomial Time [127.14106124669645]
  We provide the first results on learnability of single-layer Transformers with linear attention.<n>We show that linear attention may be viewed as a linear predictor in a suitably defined RKHS.<n>We show how to efficiently identify training datasets for which every empirical riskr is equivalent to the linear Transformer.
  arXiv  Detail & Related papers  (2024-10-14T02:41:01Z)
• Softmax Attention with Constant Cost per Token [0.0]
  Instead of quantifying pairwise query-key similarity with scaled dot-products, we quantify it with the logarithms of scaled dot-products of exponentials. Our modification linearizes attention with exponential kernel feature maps, whose corresponding feature function is infinite dimensional.
  arXiv  Detail & Related papers  (2024-04-08T20:14:10Z)
• CoTFormer: A Chain-of-Thought Driven Architecture with Budget-Adaptive Computation Cost at Inference [36.753384415107774]
  Scaling language models to larger and deeper sizes has led to significant boosts in performance. We propose CoTFormer, a novel architecture which closely mimics Chain-of-Thought (CoT) at the token level. We show that it is possible to reduce the computation cost significantly without any reduction in accuracy.
  arXiv  Detail & Related papers  (2023-10-16T21:37:34Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Softmax-free Linear Transformers [90.83157268265654]
  Vision transformers (ViTs) have pushed the state-of-the-art for visual perception tasks. Existing methods are either theoretically flawed or empirically ineffective for visual recognition. We propose a family of Softmax-Free Transformers (SOFT)
  arXiv  Detail & Related papers  (2022-07-05T03:08:27Z)

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.