A Compositional Theory of Causally Masked Transformers

• URL: http://arxiv.org/abs/2607.26988v1
• Date: Wed, 29 Jul 2026 14:47:19 GMT
• Title: A Compositional Theory of Causally Masked Transformers
• Abstract summary: We develop a formalization that derives expressivity directly from the model's implemented dynamics.<n>Each attention head updates its own state independently within a layer.<n>A modified form of soft attention supports irreversible, checklist-like state.
• Score: 50.88598486616582
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: What types of decision problems can a causally masked, finite-precision transformer solve for inputs of arbitrary length? Existing answers often rely on idealized arithmetic, but under finite precision, rounding and evaluation order can change what information attention retains and therefore what the model can compute. We develop an algebraic formalization that derives expressivity directly from the model's implemented dynamics. Its central object is its memory; the finite internal state computed by attention that summarizes the information from the prefix available to all future queries. Each attention head updates its own state independently within a layer, while layers compose hierarchically, providing a uniform route from model assumptions to expressivity bounds. Applying this method to transformers without positional embeddings, we obtain an expressivity hierarchy governed by the attention type under specific numerical semantics. Width-one sliding-window attention supports bounded-suffix memory, while a modified form of soft attention supports irreversible, checklist-like state, and combining the two mechanisms provides an interplay of both. Ordinary left-to-right floating-point soft attention can realize more expressive memory operations than any of the above. Algebraically, the four cases correspond to definite, R-trivial, locally R-trivial, and aperiodic semigroups. Under an explicit free-wiring assumption, all four bounds are tight.

Related papers

• A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits [17.425526755350948]
  We project discrete trajectories into a metric space to quantify domain shifts.<n>Invoking Kantorovich duality, we bound OOD generalization via architectural Lipschitz continuity and functional approximation limits.
  arXiv  Detail & Related papers  (2026-05-19T15:00:51Z)
• Geometric Factual Recall in Transformers [57.48371649045765]
  A common view casts internal weight matrices as associative memories over pairs of embeddings, requiring memorization counts that scale linearly with the number of facts.<n>We develop a theoretical and empirical account of an alternative, emphgeometric form of memorization in which learned embeddings encode structure directly.<n>In a controlled setting where a single-layer transformer must memorize random vectors from subjects to a shared attribute set, we prove that a logarithmic embedding dimension suffices.<n>We extend these results to the multi-hop setting, providing constructions with and without chain-of-thought that exhibit a provable
  arXiv  Detail & Related papers  (2026-05-12T17:22:22Z)
• Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification [45.85698554568285]
  We develop a deterministic zeroth-order mirror descent framework by replacing gradients with a general vector field.<n>Our analysis provides an evaluation template for last-rate inequality evaluations.<n>Together, these results expose a hidden geometric linking Bregman identities, deterministic certification, and robust conic geometry in zeroth-order mirror descent.
  arXiv  Detail & Related papers  (2026-01-31T10:05:05Z)
• The Minary Primitive of Computational Autopoiesis [0.0]
  We introduce Minary, a computational framework designed as a candidate for the first formally provable autopoietic primitive.<n>We derive exact formulas for the mean and variance of the normalized consensus conditioned on the activation of a given semantic dimension.<n>We argue that Minary is organizationally closed yet operationally open in the sense of Maturana and Varela.
  arXiv  Detail & Related papers  (2026-01-08T02:12:04Z)
• Transformers Are Universally Consistent [14.904264782690639]
  We show that Transformers equipped with softmax-based nonlinear attention are uniformly consistent when tasked with executing Least Squares regression.<n>We derive upper bounds on the empirical error which, in the regime, decay at a provable rate of $mathcalO(t-1/2d)$, where $t$ denotes the number of input tokens and $d$ the embedding dimensionality.
  arXiv  Detail & Related papers  (2025-05-30T12:39:26Z)
• EulerFormer: Sequential User Behavior Modeling with Complex Vector Attention [88.45459681677369]
  We propose a novel transformer variant with complex vector attention, named EulerFormer. It provides a unified theoretical framework to formulate both semantic difference and positional difference. It is more robust to semantic variations and possesses moresuperior theoretical properties in principle.
  arXiv  Detail & Related papers  (2024-03-26T14:18:43Z)
• An Analysis of Attention via the Lens of Exchangeability and Latent Variable Models [64.87562101662952]
  We show that input tokens are often exchangeable since they already include positional encodings. We establish the existence of a sufficient and minimal representation of input tokens. We prove that attention with the desired parameter infers the latent posterior up to an approximation error.
  arXiv  Detail & Related papers  (2022-12-30T17:59:01Z)
• Combiner: Full Attention Transformer with Sparse Computation Cost [142.10203598824964]
  We propose Combiner, which provides full attention capability in each attention head while maintaining low computation complexity. We show that most sparse attention patterns used in existing sparse transformers are able to inspire the design of such factorization for full attention. An experimental evaluation on both autoregressive and bidirectional sequence tasks demonstrates the effectiveness of this approach.
  arXiv  Detail & Related papers  (2021-07-12T22:43:11Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)

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.