10 papers
Communication Complexity of Universal Features
Lunjia Hu, Anish Jayant, Peter Li +2
Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we…
Can AI agents conduct open-ended AI research? Early evidence from two case studies
Peter Kirgis, Sayash Kapoor, Andrew Schwartz +21
Forecasts of explosive AI progress hinge on AI agents automating AI research. But evidence on whether agents can carry out open-ended AI research is thin. Current evaluations eithe…
Life After Benchmark Saturation: A Case Study of CORE-Bench
Nitya Nadgir, Sayash Kapoor, Kangheng Liu +11
When a benchmark's accuracy saturates, it is often retired and replaced with a more challenging version. We show that this approach privileges accuracy and misses the opportunity t…
Learning with Simulators: No Regret in a Computationally Bounded World
Sasha Voitovych, Abhishek Shetty, Noah Golowich +1
Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some…
Subliminal Effects in Your Data: A General Mechanism via Log-Linearity
Ishaq Aden-Ali, Noah Golowich, Allen Liu +3
Training modern large language models (LLMs) has become a veritable smorgasbord of algorithms and datasets designed to elicit particular behaviors, making it critical to develop te…
Provably Learning from Modern Language Models via Low Logit Rank
Noah Golowich, Allen Liu, Abhishek Shetty
While modern language models and their inner workings are incredibly complex, recent work (Golowich, Liu & Shetty; 2025) has proposed a simple and potentially tractable abstraction…
Sequences of Logits Reveal the Low Rank Structure of Language Models
Noah Golowich, Allen Liu, Abhishek Shetty
A major problem in the study of large language models is to understand their inherent low-dimensional structure. We introduce an approach to study the low-dimensional structure of…
Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
Dhruv Rohatgi, Abhishek Shetty, Donya Saless +4
Test-time algorithms that combine the generative power of language models with process verifiers that assess the quality of partial generations offer a promising lever for elicitin…
Omnipredictors for Regression and the Approximate Rank of Convex Functions
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra +2
Consider the supervised learning setting where the goal is to learn to predict labels given points from a distribution. An \textit{omnipredictor} for a clas…
Smooth Nash Equilibria: Algorithms and Complexity
Constantinos Daskalakis, Noah Golowich, Nika Haghtalab +1
A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, in…