Deqing Fu

Unlike traditional computers, which run the programs we write, foundation models built on the Transformer architecture learn their programs from data. In this talk, I show that on three problems with textbook solutions, Transformers learn algorithms that nobody programmed into them and that differ from the textbook ones, and that the training data decides whether they learn an algorithm at all. I first present evidence that Transformers trained for in-context linear regression implement Iterative Newton’s method rather than gradient descent, which explains their second-order convergence rate and their robustness to ill-conditioned data. I then turn to graph connectivity, where a simplified L-layer Transformer provably decides reachability by powering the adjacency matrix, with a capacity of exactly 3^L in graph diameter. Training graphs beyond this capacity add a shortcut based on node degrees alongside the algorithm, and surprisingly, restricting the training data to within capacity removes the shortcut, so that even standard Transformers learn the clean matrix-powering algorithm. Finally, pretrained language models add numbers using Fourier features, which emerge across architectures by convergent evolution. Building these features directly into number embeddings improves arithmetic, and now encodes numbers in tabular foundation models, including Google’s TabFM, which I co-developed. Together, these findings suggest that Transformers are best understood through the algorithms they learn. Reverse-engineering these mechanisms opens new opportunities for algorithm discovery, and for designing the data and representations that shape them.