TILOS-HDSI Seminar: Inference-Time Algorithms: A Theoretical Lens on Tractability and Error Propagation
Andrej Risteski, Carnegie Mellon University
Abstract: Modern AI systems are increasingly built by placing trained models inside larger computational loops. Inference-time algorithms are a basic instance of this idea: they use one or more trained models at test time to incorporate new information, exploit pretrained models as priors, and trade computational effort for accuracy, sample quality, or control. Examples include generator-verifier search for reasoning, diffusion models for solving inverse problems, and reward-guided generation. Theoretically, this revisits a classical question from optimization and theoretical computer science: what can be done with access to an oracle? Here, however, the oracles are new and non-standard: they model the capabilities of large pretrained models, making them powerful, but also imperfect because they are learned. This combination leads to new questions about algorithm design and error propagation.
This talk studies two central aspects of this paradigm: computational efficiency and error propagation. The first vignette considers generator-verifier systems, and shows how stochastic backtracking can trade additional computation for accuracy, giving a principled version of test-time scaling even with imperfect learned oracles. The second vignette studies diffusion steering: when can we efficiently bias a pretrained diffusion model toward higher-reward samples while staying close to the original model? We show that tractability depends strongly on both the reward structure and the alignment objective, and that simple primitives—such as sampling from linear tilts—can be surprisingly useful for handling richer reward classes.
Based on https://arxiv.org/abs/2510.
Andrej Risteski is an Associate Professor at the Machine Learning Department in Carnegie Mellon University. Prior to that, he was a Norbert Wiener Research Fellow jointly in the Applied Math department and IDSS at MIT. Dr. Risteski received his PhD in the Computer Science Department at Princeton University under the advisement of Sanjeev Arora.
Dr. Risteski’s research interests lie in the intersection of machine learning, statistics, and theoretical computer science, spanning topics like (probabilistic) generative models, algorithmic tools for learning and inference, representation and self-supervised learning, out-of-distribution generalization and applications of neural approaches to natural language processing and scientific domains. The broad goal of his research is principled and mathematical understanding of statistical and algorithmic problems arising in modern machine learning paradigms.