Universal Sims of Attraction
This research paper investigates the theoretical expressivity of transformer encoders by proving that a unified, data-agnostic network can algorithmically simulate any single-layer attention mechanism without relying on traditional probabilistic training. To achieve this, the authors utilize a formal framework called Restricted Access Sequence Processing (RASP) to construct universal transformer-based simulators capable of executing fundamental linear algebra operations, such as matrix transposition, multiplication, and inversion, alongside various activation functions like softmax and MaxMin sorting. By establishing these exact, constant-depth constructions, the study bridges a critical gap between learnability and expressivity, demonstrating that certain tasks previously thought to require data-driven learning can instead be reliably solved through exact algorithmic simulation.
