Reproduce “Transformers As Approximations of Solomonoff Induction” on OpenResearch

About this paper

Nathan Young, Michael Witbrock

Researchers at the University of Auckland hypothesize that Transformer models approximate Solomonoff Induction, an incomputable but theoretically optimal sequence predictor. The work aims to provide a unifying theoretical framework for understanding Transformer mechanisms and capabilities, addressing the 'black box' problem in AI interpretability. The paper synthesizes existing evidence, noting both the computational universality of Transformers that supports this view, and practical limitations like finite memory and SGD biases that suggest a more nuanced approximation of simpler computational schemes.

Key insights

• Transformers, like other neural networks, exhibit computational universality, theoretically capable of emulating arbitrary Turing Machines, which forms a basis for approximating Solomonoff Induction.
• The 'Lottery Ticket Hypothesis' aligns with the idea that training identifies and weights specific subnetworks within a Transformer, similar to how Solomonoff Induction probabilistically selects programs.
• Despite theoretical capabilities, practical Transformers show limitations in fully approximating Solomonoff Induction, particularly in generalizing to tasks high on the Chomsky hierarchy, due to finite memory, precision, and biases introduced by Stochastic Gradient Descent.

Summary by alphaXiv.