An Algebra of Transformers

Yong Wang; Zhiyan Wang; Hexiao Kang

cs.LOOct 27, 2026

An Algebra of Transformers

Authors: Yong Wang, Zhiyan Wang, Hexiao Kang

Abstract

On the theoretic analyses on transforms, they mainly focus on the computability analysis, such the Turing-completeness of unbounded precision transformers, the advantage of parallelizability of unbounded precision transformers and the limitations of bounded precision transformers. This paper give transformers an algebra for reasoning, which relies heavily on the functional decomposition results of transformers. This algebra uses functional decompositions as atomic actions, includes sequential composition and parallel composition, recursion for feedback and abstraction for hidden layers. As we know, it is the first attempt to model transformers logically and can be used to verify the correctness of transformer based applications.

Figures & tables

Names	Functions	Types
$\alpha_{1}$	word embedding	$\Sigma\rightarrow\mathbb{R}^{d}$
$\alpha_{2}$	position embedding	$\mathbb{N}\rightarrow\mathbb{R}^{d}$
$\alpha_{3}$	identity	$\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$
$\alpha_{4}$	min/max	$\mathbb{R}^{2}\rightarrow\mathbb{R}$
$\alpha_{5}$	add/subtract	$\mathbb{R}^{2}\rightarrow\mathbb{R}$
$\alpha_{6}$	multiply by $c$	$\mathbb{R}\rightarrow\mathbb{R}$

Table 1: Decomposition of Transformers

No.	Axioms
$A1$	$x+y=y+x$
$A2$	$(x+y)+z=x+(y+z)$
$A3$	$x+x=x$
$A4$	$(x+y)\circ z=x\circ z+y\circ z$
$A5$	$(x\circ y)\circ z=x\circ(y\circ z)$
$A6$	$x+\mathbf{0}=x$

Table 2: Axioms of BAT

No.	Rewriting rules
$RA3$	$x+x\rightarrow x$
$RA4$	$(x+y)\circ z\rightarrow x\circ z+y\circ z$
$RA5$	$(x\circ y)\circ z\rightarrow x\circ(y\circ z)$
$RA6$	$x+\mathbf{0}\rightarrow x$
$RA7$	$\mathbf{0}\circ x\rightarrow\mathbf{0}$
$RA8$	$\mathbf{I}\circ x\rightarrow x$

Table 3: Rewriting rules of BAT

\frac{}{\langle\mathbf{I},s\rangle\rightarrow\langle\surd,s\rangle}

Table 4: Transition rules of BAT

\frac{x\xrightarrow{\alpha}\surd\quad y\xrightarrow{\alpha^{\prime}}\surd}{x\oplus y\xrightarrow{\{\mskip-4.0mu|\alpha,\alpha^{\prime}|\mskip-4.0mu\}}\surd}\quad\frac{x\xrightarrow{\alpha}x^{\prime}\quad y\xrightarrow{\alpha^{\prime}}\surd}{x\oplus y\xrightarrow{\{\mskip-4.0mu|\alpha,\alpha^{\prime}|\mskip-4.0mu\}}x^{\prime}}

Table 5: Transition rules of APT

No.	Axioms
$P1$	$\alpha\oplus(\alpha^{\prime}\circ y)=(\alpha\oplus\alpha^{\prime})\circ y$
$P2$	$(\alpha\circ x)\oplus\alpha^{\prime}=(\alpha\oplus\alpha^{\prime})\circ x$
$P3$	$(\alpha\circ x)\oplus(\alpha^{\prime}\circ y)=(\alpha\oplus\alpha^{\prime})\circ(x\oplus y)$
$P4$	$(x+y)\oplus z=(x\oplus z)+(y\oplus z)$
$P5$	$x\oplus(y+z)=(x\oplus y)+(x\oplus z)$
$P6$	$\mathbf{0}\oplus x=\mathbf{0}$

Table 6: Axioms of APT

No.	Rewriting rules
$RP1$	$\alpha\oplus(\alpha^{\prime}\circ y)\rightarrow(\alpha\oplus\alpha^{\prime})\circ y$
$RP2$	$(\alpha\circ x)\oplus\alpha^{\prime}\rightarrow(\alpha\oplus\alpha^{\prime})\circ x$
$RP3$	$(\alpha\circ x)\oplus(\alpha^{\prime}\circ y)\rightarrow(\alpha\oplus\alpha^{\prime})\circ(x\oplus y)$
$RP4$	$(x+y)\oplus z\rightarrow(x\oplus z)+(y\oplus z)$
$RP5$	$x\oplus(y+z)\rightarrow(x\oplus y)+(x\oplus z)$
$RP6$	$\mathbf{0}\oplus x\rightarrow\mathbf{0}$

Table 7: Rewriting rules of APT

\frac{t_{i}(\langle X_{1}|E\rangle,\cdots,\langle X_{n}|E\rangle)\xrightarrow{U}\surd}{\langle X_{i}|E\rangle\xrightarrow{U}\surd}

Table 8: Transition rules of guarded recursion

No.	Axioms
$RDP$	$\langle X_{i}\|E\rangle=t_{i}(\langle X_{1}\|E\rangle,\cdots,\langle X_{n}\|E\rangle)\quad(i\in\{1,\cdots,n\})$
$RSP$	if $y_{i}=t_{i}(y_{1},\cdots,y_{n})$ for $i\in\{1,\cdots,n\}$ , then $y_{i}=\langle X_{i}\|E\rangle\quad(i\in\{1,\cdots,n\})$
end of Recursive definition and specification principle

Table 9: Recursive definition and specification principle

\frac{}{\langle\tau_{\phi},s\rangle\rightarrow\langle\surd,s\rangle}\mbox{ if }test(\tau_{\phi},s)

Table 10: Transition rule of the silent step

No.	Axioms
$B1$	$U\circ\tau=U$
$B2$	$U\circ(\tau\circ(x+y)+x)=U\circ(x+y)$
$B3$	$x\oplus\tau=x$
$B4$	$\tau\oplus x=x$
$G26$	$\tau_{\phi}\cdot x=x$
$G19$	$x\cdot\tau_{\phi}=x$

Table 11: Axioms of silent step

\frac{\langle x,s\rangle\xrightarrow{\alpha}\langle\surd,s^{\prime}\rangle}{\langle\tau_{I}(x),s\rangle\xrightarrow{\alpha}\langle\surd,s^{\prime}\rangle}\quad\alpha\notin I\quad\quad\frac{\langle x,s\rangle\xrightarrow{\alpha}\langle x^{\prime},s^{\prime}\rangle}{\langle\tau_{I}(x),s\rangle\xrightarrow{\alpha}\langle\tau_{I}(x^{\prime}),s^{\prime}\rangle}\quad\alpha\notin I

Table 12: Transition rule of the abstraction operator

No.	Axioms
$TI1$	$\alpha\notin I\quad\tau_{I}(\alpha)=\alpha$
$TI2$	$\alpha\in I\quad\tau_{I}(\alpha)=\tau$
$TI3$	$\tau_{I}(\mathbf{0})=\mathbf{0}$
$TI4$	$\tau_{I}(\mathbf{I})=\mathbf{I}$
$TI5$	$\tau_{I}(x+y)=\tau_{I}(x)+\tau_{I}(y)$
$TI6$	$\tau_{I}(x\circ y)=\tau_{I}(x)\circ\tau_{I}(y)$

Table 13: Axioms of abstraction

No.	Axioms
$CFAR$	If $X$ is in a cluster for $I$ with exits
	$\{(\alpha_{11}\oplus\cdots\oplus\alpha_{1i})Y_{1},\cdots,(\alpha_{m1}\oplus\cdots\oplus\alpha_{mi})Y_{m},\beta_{11}\oplus\cdots\oplus\beta_{1j},\cdots,\beta_{n1}\oplus\cdots\oplus\beta_{nj}\}$ ,
	then $\tau\circ\tau_{I}(\langle X\|E\rangle)=$
	$\tau\circ\tau_{I}((\alpha_{11}\oplus\cdots\oplus\alpha_{1i})\langle Y_{1}\|E\rangle+\cdots+(\alpha_{m1}\oplus\cdots\oplus\alpha_{mi})\langle Y_{m}\|E\rangle+\beta_{11}\oplus\cdots\oplus\beta_{1j}+\cdots+\beta_{n1}\oplus\cdots\oplus\beta_{nj})$
end of Cluster fair abstraction rule

Table 14: Cluster fair abstraction rule

Transformer

Transformers are neural architectures that use attention to model relationships among sequence elements in language, vision, and scientific data.

See all 544 papers

A Compositional Theory of Causally Masked Transformers
Jul 29, 2026Franz Nowak, Ryan Cotterell, Reda BoumasmoudTransformer Expressivity Transformer
1ETH Zürich
Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
May 28, 2026Anej Svete, William Merrill, Ryan Cotterell +1Transformer Expressivity Transformer
1. ETH Zürich · 2. Allen Institute for AI
On the Expressive Power of Transformers
Aug 13, 2026Phokion Kolaitis, Rik SenguptaTransformer Expressivity Circuit Complexity
University of California Santa Cruz Santa Cruz, CA · IBM Research Cambridge, MA

Jul 29, 2026J/K move · Enter open · S save

A Compositional Theory of Causally Masked Transformers

Franz Nowak, Ryan Cotterell, Reda Boumasmoud

1ETH Zürich

Transformer Expressivity Transformer Attention Mechanisms

Open paper AskPDF arXiv

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.

Abstract

Transformer

Explore similar work

A Compositional Theory of Causally Masked Transformers

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't

On the Expressive Power of Transformers