Search papers, labs, and topics across Lattice.
This paper analyzes the computational power of transformer encoders with average attention, demonstrating they can simulate arithmetic circuits with constant depth and unbounded addition, binary multiplication, and sign gates when the circuit is provided as input. The key finding is that transformers using arithmetic circuits instead of feed-forward networks can compute the same class of circuit families with typical average attention. This result holds for transformers operating over reals, rationals, and rings in between.
Transformers with average attention can natively execute arithmetic circuits, suggesting a new architectural direction for reasoning and computation.
We analyse the computational power of transformer encoders as sequence-to-sequence functions on vectors. We show that average hard attention can be used to simulate arithmetic circuits if they are given as an input to an encoder. The circuit families that can be simulated this way have constant depth while using unbounded addition, binary multiplication and sign gates. The transformers we use have arithmetic circuits instead of feed-forward networks. With typical average attention the functions they compute are also computed by the same class of circuit families. Our results hold for transformers over the reals, rationals and any ring in between the two.
