🤖 AI

Average Attention Transformers and Arithmetic Circuits

This paper demonstrates that transformer encoders equipped with arithmetic circuits and average hard attention possess the computational power to simulate constant-depth arithmetic circuits with unbounded addition, binary multiplication, and sign gates over real, rational, and intermediate rings.

Original authors: Lena Ehrmuth, Laura Strieker

Published 2026-05-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lena Ehrmuth, Laura Strieker

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have two different kinds of super-computers trying to solve the same puzzle.

Computer A is a Transformer. You might know these as the brains behind modern AI chatbots. They are famous for looking at a whole sentence at once, figuring out which words are most important to each other (a process called "attention"), and then mixing that information together to create a new sentence.

Computer B is an Arithmetic Circuit. Think of this as a giant, rigid factory assembly line made of math machines. It has input slots for numbers, and inside, there are gears that only do specific things: add numbers together, multiply them, or check if a number is positive or negative.

This paper asks a simple question: If we give these two computers the same job, are they equally powerful?

The Big Discovery

The authors found that if you tweak the Transformer just a little bit, it becomes a perfect match for a specific type of Arithmetic Circuit.

Here is the "secret sauce" they used to make them match:

The "Average" Trick: Instead of the Transformer picking just one most important word (like a strict teacher picking the top student), they made it pick all the words that are equally important and take their average.
The "Math" Swap: Usually, Transformers have a "brain" inside them (called a feed-forward network) that does complex, messy calculations. The authors replaced this messy brain with a clean, simple Arithmetic Circuit.

The Analogy: The Factory vs. The Chef

Imagine you are trying to build a complex machine.

The Arithmetic Circuit is like a Factory. You feed in raw materials (numbers). The materials go down a conveyor belt. At each stop, a machine either adds two things together, multiplies them, or checks if they are zero. The factory is very fast and very precise, but it has a fixed depth; it can't do an infinite number of steps in a single pass.
The Standard Transformer is like a Chef who tastes a soup, decides which ingredient is the "best," and then adds a little bit of that. This is great for flavor, but it's hard to use a chef to build a factory.
The "Average Attention" Transformer (the one in this paper) is like a Chef who is also a Factory Manager.
- Instead of picking just one ingredient, the Chef looks at all the ingredients that are tied for "best," mixes them together (averages them), and then uses a Factory Machine (the arithmetic circuit) to process that mix.

The paper proves that this "Chef-Manager" can do exactly the same things as the "Factory" (the Arithmetic Circuit), and vice versa.

What Can They Do?

The authors show that this specific type of Transformer can simulate circuits that:

Add up huge lists of numbers instantly.
Multiply numbers together.
Check if a number is positive, negative, or zero.

They call this power class FSAC0. Think of it as a "super-fast math club" that can do these specific jobs in a fixed, short amount of time, no matter how big the list of numbers is.

The Catch (The "Rules of the Game")

There are a few rules for this magic to work:

The Numbers: The math works best if you are using "perfect" numbers (like fractions or real numbers), not just the rounded numbers computers usually use.
The Encoding: To prove the Transformer can do the circuit's job, the authors had to write the circuit's instructions into a long list of numbers first. It's like translating a blueprint into a grocery list before the Chef can cook it.
No "Soft" Attention: If the Transformer tries to be "soft" (giving small weights to many things instead of just averaging the top ones), it loses this specific super-power. It needs to be "hard" and decisive about which numbers to average.

The Bottom Line

The paper doesn't say this will make your phone faster or cure diseases. Instead, it's a theoretical breakthrough. It draws a straight line between two very different ways of thinking about math and AI.

It tells us: "If you build a Transformer that uses 'average attention' and swaps its brain for a simple math circuit, you have built a machine that is mathematically identical to a specific type of arithmetic factory."

This helps scientists understand the true limits and powers of AI models by comparing them to the well-understood rules of math factories.

Technical Summary: Average Attention Transformers and Arithmetic Circuits

Problem Statement
Existing theoretical analyses of Transformer expressivity have primarily focused on decision problems over finite alphabets, comparing Transformers to Boolean circuit classes (e.g., $AC^0$ , $TC^0$ ) or logical formalisms. These results are limited to language recognition. This paper addresses a gap in understanding the computational power of Transformers as sequence-to-sequence functions operating on vectors of real or rational numbers. The authors aim to characterize the expressivity of Transformer encoders by comparing them directly to arithmetic circuits, which compute functions over semirings using operations like addition, multiplication, and the sign function.

Methodology
The authors adapt a generalized Transformer model (based on Hao et al., 2022) to operate over arbitrary semirings. Key methodological choices include:

Model Definition: They define "average attention circuit transformers," where the standard feed-forward networks are replaced by arithmetic circuits, and the attention mechanism utilizes "average hard attention" (attending to all vectors with maximal attention scores).
Circuit Families: They analyze three classes of arithmetic circuit families with constant depth and polynomial size:
- $FNC^0_R$ : Bounded fan-in.
- $FSAC^0_R$ : Semi-unbounded fan-in (unbounded addition, binary multiplication).
- $FAC^0_R$ : Unbounded fan-in (unbounded addition and multiplication).
  These classes are extended with the sign function to handle discontinuous operations.
Simulation Construction:
- Circuits to Transformers: To simulate a circuit, the authors encode the circuit's graph structure (gates and edges) into a sequence of vectors. Each vector represents an edge or a gate, containing indices for predecessors/successors, gate types, and values.
- Attention Mechanisms: They design specific attention functions ( $f^{att}_E$ and $f^{att}_V$ ) that allow vectors to attend to their predecessors based on index matching.
- Pooling and Activation: They utilize average hard attention pooling to aggregate values from predecessors. Crucially, they construct activation functions that select the appropriate operation (addition, multiplication, or identity) based on the gate type encoded in the vector.
- Handling Scaling: Since average attention scales results by $1/k$ (where $k$ is the number of attended vectors), the construction includes mechanisms to count predecessors and rescale the output to recover the correct arithmetic value.

Key Results
The paper establishes a precise correspondence between the computational power of these specific Transformers and arithmetic circuit classes:

Upper Bound: For any semiring $R$ , the functions computed by average attention circuit transformers are contained within the class $FSAC^0_R[\text{sign}]$ . This holds even for standard Transformers with typical average attention, provided their activation functions are restricted to the same circuit class.
Lower Bound (Simulation): If the underlying semiring $R$ $R$ is a $\mathbb{Z}$ $Z$ -ordered ring extension of the rationals ( $\mathbb{Q}$ $Q$ ), then for any circuit family in $FSAC^0_R[\text{sign}]$ $F S A C_{R}^{0} [sign]$ with depth $K$ $K$ , there exists a Transformer with $2K$ $2 K$ layers that can simulate the entire family.
- The simulation works for unbounded fan-in circuits using average attention.
- For semi-unbounded fan-in circuits, the construction can be adapted to use standard dot-product attention.
- For bounded fan-in circuits, the construction can be further restricted to use leftmost or rightmost hard attention.
Specific Theorems:
- Theorem 4.5: A Transformer with dimension 7 and $2K$ layers can simulate any unbounded fan-in $R$ -circuit of depth $\le K$ (where $R$ is a $\mathbb{Z}$ -ordered extension of $\mathbb{Q}$ ).
- Theorem 4.11: A Transformer with dimension 9 and $2K$ layers can simulate any $FSAC^0_R[\text{sign}]$ -circuit.

Significance and Claims
The authors claim that their results provide a new perspective on Transformer expressivity by bridging the fields of machine learning theory and algebraic computation.

Theoretical Equivalence: They demonstrate that average attention Transformers are computationally equivalent to the class of constant-depth arithmetic circuits with unbounded addition, binary multiplication, and sign gates ( $FSAC^0_R[\text{sign}]$ ).
Limitations: The paper explicitly notes that this equivalence relies on the Transformer using arithmetic circuits (or equivalent functions) as activation functions. Standard Transformers with feed-forward networks cannot simulate these circuits because feed-forward networks cannot inherently perform the multiplication of two arbitrary inputs required for the simulation.
Non-Uniformity: The authors clarify that while Transformers can simulate specific circuit families, this does not imply that every function in $FSAC^0_R[\text{sign}]$ is computed by a single Transformer, as circuit families are a non-uniform model of computation.
Future Potential: The paper suggests that theoretical advances in algebraic computation could benefit machine learning theory and vice versa, and that theoretical results may inspire practical developments, though no specific applications are proposed.

The work is presented as a preprint (May 2026) from the Institute for Theoretical Computer Science at Leibniz University Hanover.