Archimedes Talk by Prof. Noah Golowich

On Wednesday 22 July, 2026, at 1:30 pm, Noah Golowich, Assistant Professor of Computer Science at the University of Texas at Austin, USA, gave the final talk of this year’s Archimedes study group on "Parallel Reasoning and Test-time Training in Language Model Inference." The talk was also available online via Microsoft Teams.

Abstract:

Efficiently sampling from a complex probability distribution is a fundamental problem across machine learning and theoretical computer science. It has become increasingly pertinent in recent years with the rise of generative AI, as sophisticated sampling procedures from large language models (LLMs) have been proposed to solve challenging reasoning problems spanning domains such as mathematics and coding. For the most part, however, we lack a principled understanding of the accuracy–cost tradeoffs for such procedures. In this talk, we propose a formalization for such tasks as the problem of producing a sample from a target probability measure, given an oracle which yields approximate density estimates for the target measure. Depending on the context, this oracle may be interpreted as an approximate verifier or a process reward model for a particular language modeling task. This setup is closely related to the problem of reducing sampling to approximate counting studied in seminal works of Jerrum, Valiant & Vazirani (1986) and Jerrum & Sinclair (1989).

Generalizing results from existing literature, we establish provable guarantees for the Sequential Monte Carlo algorithm and related particle filtering approaches, which have recently found success empirically in the context of both language modeling and diffusion. In particular, our theory identifies a few properties of the oracle which suffice for efficient sampling. We conduct experiments to show that these properties indeed correlate with sampling performance for certain language modeling tasks.

The efficacy of such sampling algorithms, however, is limited by the relationship between the underlying LLM and the particular sampling task at hand, which has motivated the framework of Test-Time Training (TTT). In particular, TTT updates a model's weights in response to partial generations and reward feedback received at inference time. In the latter half of the talk, we will discuss some provable benefits of TTT in the context of our sampling framework.

Based on: arxiv.org/pdf/2603.07887 (joint work with Fan Chen, Dhruv Rohatgi, Raghav Singhal, Carles Domingo-Enrich, Dylan J. Foster, and Akshay Krishnamurthy) and arxiv.org/abs/2606.11437 (joint work with Ankur Moitra and Dhruv Rohatgi).

Biography:

Noah Golowich is an Assistant Professor of Computer Science at the University of Texas at Austin. Before that, he was a postdoctoral researcher at Microsoft Research. He received his Ph.D. from MIT in 2025, advised by Constantinos Daskalakis and Ankur Moitra, and his A.B. and S.M. from Harvard University in 2019. His research focuses on multi-agent learning, reinforcement learning, and game theory.