Average Attention Transformers and Arithmetic Circuits
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits
Transformers have emerged as a widely used neural network model for various natural language processing tasks. Previous research explored their relationship with constant-depth threshold circuits, making two assumptions:…
Hard AttentionConvolutional Rectifier Networks as Generalized Tensor Decompositions
Convolutional rectifier networks, i.e. convolutional neural networks with rectified linear activation and max or average pooling, are the cornerstone of modern deep learning. However, despite their wide use and success, …
Towards Empirical Interpretation of Internal Circuits and Properties in Grokked Transformers on Modular Polynomials
Grokking has been actively explored to reveal the mystery of delayed generalization and identifying interpretable representations and algorithms inside the grokked models is a suggestive hint to understanding its mechani…
Hierarchical Sparse Circuit Extraction from Billion-Parameter Language Models through Scalable Attribution Graph Decomposition
Extracting sparse circuits from billion-parameter transformers is constrained by $O(2^n)$ search cost and pervasive feature reuse across co-active pathways. Hierarchical Attribution Graph Decomposition (HAGD) addresses t…
Coreference ResolutionTowards Verifiable Transformers: Solver-Checkable Circuit Explanations
Mechanistic interpretability typically discovers circuits and then argues what they do from examples and ablations. We introduce Verifiable Transformers, a framework for turning task-localized circuits into bounded, solv…