iiinova — where your digital self keeps evolving

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

(12/12) Another algo example: We give some tournament-style methods for selecting checkpoints (motivated by coverage) that can beat cross-entropy based selection. See figure, where coverage-based selection finds model w/ best BoN performance.

110

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

(10/12) Perhaps the coolest part: the coverage perspective seems to have non-trivial algo design consequences: 1. Vanilla SGD can have poor coverage; gradient normalization (a-la Adam) fixes this 2. Test-time training (SGD on tokens during generation) provably improves coverage

110

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

(8/12) Our analysis is based on a phenomenon we call the coverage principle, where next-token prediction implicitly optimizes toward a model with good coverage. Neat consequence: Coverage generalizes faster as we go further into tail (corresponding to more test-time compute)

100

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

(7/12) Example (see figure): - Cross-entropy decreases throughout training. - Coverage improves to a point, but begins to drop as the model learns a spurious shortcut. - BoN performance follows trend of coverage, not CE (increasing initially, dropping as shortcut is learned).

110

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

(6/12) Our main result: 1) Next-token prediction (more generally, MLE) provably learns a model w/ good coverage, inheriting the training corpus’ coverage over tasks of interest. 2) Coverage generalizes *faster* than cross-entropy itself, and consequently can be more predictive.

100

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

(3/12) Our answer is a quantity we call the *coverage profile*, which captures the extent to which the pre-trained model "covers" the pre-training distribution: Cov_N = P_{π}[π(y|x)/\hat{π}(y|x) ≥ N], (π is pre-training dist, \hat{π} is pre-trained model, N is a param)

100

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

(1/12) Many have observed starting that from a better next‑token predictor (low cross-entropy) does not always give better downstream post-training/test-time perf. In some cases, CE can even be anti‑correlated with BoN success (see fig or arxiv.org/abs/2502.07154). Why is this?

100

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

Led by my amazing intern Fan Chen, with awesome team Audrey Huang (@ahahaudrey.bsky.social), Noah Golowich, Sadhika Malladi (@sadhika.bsky.social), Adam Block, Jordan Ash, and Akshay Krishnamurthy. Paper: www.arxiv.org/abs/2510.15020 Thread below.

110

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

The coverage principle: How pre-training enables post-training New preprint where we look at the mechanisms through which next-token prediction produces models that succeed at downstream tasks. The answer involves a metric we call the "coverage profile", not cross-entropy.

1181

Dylan Foster 🐢 @djfoster.bsky.social · 25/10/2025

000

Dylan Foster 🐢 @djfoster.bsky.social · 12/10/2025

Empirically, we have only tried this w/ small-ish scale so far, but find consistently that VGB outperforms textbook algos on either (1) accuracy; or (2) diversity when compute-normalized. Ex: for Dyck language, VGB escapes the accuracy-diversity frontier for baselines algos.

100

Dylan Foster 🐢 @djfoster.bsky.social · 12/10/2025

Main guarantee: - As long as you have exact/verifiable outcome rewards, always converges to optimal distribution. - Runtime depends on process verifier quality, gracefully degrading as quality gets worse.

100

Dylan Foster 🐢 @djfoster.bsky.social · 12/10/2025

VGB generalizes the Sinclair–Jerrum '89 random walk (people.eecs.berkeley.edu/~sinclair/ap...) from TCS (used to prove equivalence of apx. counting & sampling for self-reducible problems), linking test-time RL/alignment with discrete sampling theory. We are super excited about this connection.

100

Dylan Foster 🐢 @djfoster.bsky.social · 12/10/2025

We give a new algo, Value-Guided Backtracking (VGB), where the idea is to view autoregressive generation as a random walk on the tree of partial outputs, and add a *stochastic backtracking* step—occasionally erasing tokens in a principled way—to counter error amplification.

100

Dylan Foster 🐢 @djfoster.bsky.social · 12/10/2025

Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking. A totally new framework based on ~backtracking~ for using process verifiers to guide inference, w/ connections to approximate counting/sampling in theoretical CS. Paper: www.arxiv.org/abs/2510.03149

130

Dylan Foster 🐢 @djfoster.bsky.social · 11/08/2025

Announcing the first workshop on Foundations of Language Model Reasoning (FoRLM) at NeurIPS 2025! 📝Soliciting abstracts that advance foundational understanding of reasoning in language models, from theoretical analyses to rigorous empirical studies. 📆 Deadline: Sept 3, 2025

1103

Dylan Foster 🐢 @djfoster.bsky.social · 15/07/2025

For those at ICML, Audrey will be presenting this paper at the 4:30pm poster session this afternoon! West Exhibition Hall B2-B3 W-1009

030

Dylan Foster 🐢 @djfoster.bsky.social · 26/05/2025

Dhruv Rohatgi will be giving a lecture on our recent work on comp-stat tradeoffs in next-token prediction at the RL Theory virtual seminar series (rl-theory.bsky.social) tomorrow at 2pm EST! Should be a fun talk---come check it out!!

1105

Dylan Foster 🐢 @djfoster.bsky.social · 09/05/2025

Website (& CFP/instructions): fopt-workshop.github.io Submission link: openreview.net/group?id=lea... See you in Lyon!

001

Dylan Foster 🐢 @djfoster.bsky.social · 09/05/2025

Announcing the first workshop on Foundations of Post-Training (FoPT) at COLT 2025! 📝 Soliciting abstracts/posters exploring theoretical & practical aspects of post-training and RL with language models! 🗓️ Deadline: May 19, 2025

1165

Dylan Foster 🐢 @djfoster.bsky.social · 03/05/2025

Empirically, we find that InferenceTimePessimism is robust to reward hacking across tasks, base models, and reward models. 8/11

110

Dylan Foster 🐢 @djfoster.bsky.social · 03/05/2025

Result #2: To address these shortcomings, we propose a new method: InferenceTimePessimism. ITP leverages pessimism about reward model uncertainty to robustly avoid reward hacking. 5/11

110

Dylan Foster 🐢 @djfoster.bsky.social · 03/05/2025

Inference-time computation can boost language model performance, but scaling naively—like with Best-of-N sampling (selecting the top-scoring response from multiple candidates with a reward model)—can actually degrade results through reward hacking (eg, this fig from arxiv.org/abs/2210.10760). 2/11

120

Dylan Foster 🐢 @djfoster.bsky.social · 03/05/2025

Is Best-of-N really the best we can do for language model inference? New paper (appearing at ICML) led by the amazing Audrey Huang (ahahaudrey.bsky.social) with Adam Block, Qinghua Liu, Nan Jiang, and Akshay Krishnamurthy (akshaykr.bsky.social). 1/11

1215

Dylan Foster 🐢 @djfoster.bsky.social · 27/03/2025

Main result #4: Finally, we show that under additional representational assumptions, one can achieve improved runtime (replacing sequence-level coverage with action-level coverage) through multi-turn exploration, highlighting a provable (computational vs. statistical) benefit of multi-turn. 16/

100

Dylan Foster 🐢 @djfoster.bsky.social · 27/03/2025

Main result #3. Insufficiency of training-time interventions. We show that the use of inference-time compute above is fundamental, in the sense that purely training time interventions (e.g., modifications to DPO) that produce proper policies cannot achieve similar guarantees in polynomial time. 15/

100

Dylan Foster 🐢 @djfoster.bsky.social · 27/03/2025

Main result #2: Inference-time exploration. We introduce a new RL algorithm, SpannerSampling, which uses active exploration to achieve optimal data efficiency irrespective of whether the base model has good coverage. 13/

100

Dylan Foster 🐢 @djfoster.bsky.social · 27/03/2025

Main result #1: Coverage is necessary for computational efficiency. Coverage refers to the extent to which the base model covers near-optimal responses. We show that coverage, while not necessary for data efficiency, lower bounds the *runtime* of any algo in our framework. 12/

100

Dylan Foster 🐢 @djfoster.bsky.social · 27/03/2025

The basic idea premise behind language model reinforcement learning techniques is that by iteratively generating new proposals and refining them with verifiable feedback/rewards (e.g., from a formal proof checker), the language model can eventually discover useful behaviors and capabilities. 2/

120

Dylan Foster 🐢 @djfoster.bsky.social · 27/03/2025

Reinforcement learning has led to amazing breakthroughs in reasoning (e.g., R1), but can it discover truly new behaviors not already present in the base model? A new paper with Zak Mhammedi and Dhruv Rohatgi: The Computational Role of the Base Model in Exploration arxiv.org/abs/2503.07453

14313

Dylan Foster 🐢 @djfoster.bsky.social · 23/02/2025

Next-token prediction with the logarithmic loss is the basis of language model pre-training, but a popular criticism is that it can suffer from error amplification, where generation quality degrades as sequence length $H$ increases due to compounding errors. 2/11

130

Dylan Foster 🐢 @djfoster.bsky.social · 23/02/2025

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier arxiv.org/abs/2502.12465 New paper (another fun internship project!) with Dhruv Rohatgi, Adam Block, Audrey Huang (ahahaudrey.bsky.social), and Akshay Krishnamurthy (akshaykr.bsky.social). 1/11

1272

Dylan Foster 🐢 @djfoster.bsky.social · 20/02/2025

This builds on previous work by Dhruv, Noah Golowich, and Ankur Moitra (arxiv.org/abs/2404.03774), which shows that one-state regression (e.g., regression onto value functions) is insufficient for efficient RL on its own. 6/

100

Dylan Foster 🐢 @djfoster.bsky.social · 20/02/2025

Result 1: For the Block MDP, realizable regression for functions of two states (“two-state” or “two-context” regression) is both necessary and sufficient for computationally efficient RL. 5/

110

Dylan Foster 🐢 @djfoster.bsky.social · 20/02/2025

What are the minimal supervised learning primitives required to perform RL efficiently? New paper led by my amazing intern Dhruv Rohatgi: Necessary and Sufficient Oracles: Toward a Computational Taxonomy for Reinforcement Learning arxiv.org/abs/2502.08632 1/

1254

Dylan Foster 🐢 @djfoster.bsky.social · 14/12/2024

2) We introduce a new statistical framework for sharpening and use it give theoretical guarantees and fundamental limits for natural self-training/self-improvement schemes.

100

Dylan Foster 🐢 @djfoster.bsky.social · 14/12/2024

Main results: 1) We validate the sharpening mechanism empirically for some simple choices of self-rewards (e.g., log-likelihood) at inference-time and post-training.

100

Dylan Foster 🐢 @djfoster.bsky.social · 14/12/2024

In this paper, we study perhaps the simplest mechanism, "sharpening", through which this form of self-improvement can achieve meaningful gains in performance. Sharpening refers to using the model itself as a verifier to “sharpen” the model to one placing large mass on high-quality sequences.

100

Dylan Foster 🐢 @djfoster.bsky.social · 14/12/2024

Given a high-quality verifier, language model accuracy can be improved by scaling inference-time compute (e.g., w/ repeated sampling). When can we expect similar gains without an external verifier? New paper: Self-Improvement in Language Models: The Sharpening Mechanism arxiv.org/abs/2412.01951

3416

Dylan Foster 🐢 @djfoster.bsky.social · 13/12/2024

Preaching THE POWER OF RESETS with Zak! Poster 6402 in the West ballroom

0120

Dylan Foster 🐢 @djfoster.bsky.social · 08/12/2024

Heading to neurips! Stop by and say hi if you're around.

0371

Dylan Foster 🐢 @djfoster.bsky.social · 21/11/2024

As my first post on this platform, allow me to advertise the RL theory lecture notes I have been developing with Sasha Rakhlin: arxiv.org/abs/2312.16730 (shameless repost of my pinned tweet)

421135