Event Details

Foundation models built on the Transformer architecture are a new form of computational machine whose programs are learned 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 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 an 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 drive the model toward a heuristic based on node degrees, and surprisingly, restricting the training data to within capacity makes Transformers learn the matrix-powering algorithm. Finally, pretrained language models add numbers using Fourier features that emerge across architectures, and building these features into the embeddings improves arithmetic, and helps build powerful foundation models for tabular data. Together, these findings suggest that Transformers are best understood through the algorithms they learn, and that reverse-engineering these mechanisms opens new opportunities for algorithm discovery and for designing the data that shapes them.

Zoom Link
Host: Ruth-Ann Armstrong
POC: Maura Covaci

Speaker Bio

Deqing Fu is a final-year PhD candidate in computer science at the University of Southern California, advised by Vatsal Sharan and Robin Jia. His research develops theoretical foundations for large language models and multimodal LLMs, showing that transformers learn algorithms, and using these mechanisms to build better models. His work has received a ICLR Spotlight and a SoCalNLP Best Paper Award. He has interned at Google Research and Meta during his PhD studies. Previously, Deqing completed his undergraduate degree in mathematics, computer science, and statistics at the University of Chicago.