# The Power of Test-Time Training for Approximate Sampling

arXiv: https://arxiv.org/abs/2606.11437 · HTML: https://mlsanity.com/paper/2606.11437/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 41 references that are in the map.
- First posted on arXiv 9 Jun 2026.

## Builds on (most cited first, 25 of 25)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Gemini: A Family of Highly Capable Multimodal Models](https://mlsanity.com/paper/2312.11805/) (2023)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [TTRL: Test-Time Reinforcement Learning](https://mlsanity.com/paper/2504.16084/) (2025)
- [A General Framework for Inference-time Scaling and Steering of Diffusion Models](https://mlsanity.com/paper/2501.06848/) (2025)
- [Learning to Discover at Test Time](https://mlsanity.com/paper/2601.16175/) (2026)
- [Test-Time Training with Self-Supervision for Generalization under Distribution Shifts](https://mlsanity.com/paper/1909.13231/) (2019)
- [Test-Time Learning for Large Language Models](https://mlsanity.com/paper/2505.20633/) (2025)
- [Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration](https://mlsanity.com/paper/2503.07453/) (2025)
- [Rollout Roulette: A Probabilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methods](https://mlsanity.com/paper/2502.01618/) (2025)
- [TTCS: Test-Time Curriculum Synthesis for Self-Evolving](https://mlsanity.com/paper/2601.22628/) (2026)
- [Learning to (Learn at Test Time)](https://mlsanity.com/paper/2310.13807/) (2023)
- [Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking](https://mlsanity.com/paper/2510.03149/) (2025)
- [Value-Guided Search for Efficient Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.17373/) (2025)
- [Guided Speculative Inference for Efficient Test-Time Alignment of LLMs](https://mlsanity.com/paper/2506.04118/) (2025)
- [On the Power of (Approximate) Reward Models for Inference-Time Scaling](https://mlsanity.com/paper/2602.01381/) (2026)
- [Spectral Independence via Stability and Applications to Holant-Type Problems](https://mlsanity.com/paper/2106.03366/) (2021)
- [Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference](https://mlsanity.com/paper/2603.07887/) (2026)
- [Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests](https://mlsanity.com/paper/2004.07220/) (2020)

## Built on by (most cited first, 1 of 1)

- [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026)

## Abstract (arXiv)

Efficiently sampling from a complex probability distribution is a fundamental problem which has become increasingly pertinent in recent years with the rise of generative AI, as sophisticated sampling procedures from LLMs have been proposed to solve challenging reasoning problems. The efficacy of such sampling algorithms is limited, however, by the relationship between the LLM and the particular sampling task at hand, which has motivated the framework of test-time training (TTT). TTT works by updating a model's weights in response to partial generations and reward feedback received at inference time, thus adapting to the particular problem. In this work, we propose a formalization for TTT as the problem of producing a sample from a given probability measure μ^star belonging to a known class F of distributions, given an oracle hat μ which yields approximate density estimates for μ^star. This 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): namely, when F is the class of all distributions, it coincides exactly with the aforementioned counting-to-sampling reduction. In this paper, we first show a quadratic lower bound on the query complexity of sampling from μ^star given query access to hat μ (for sufficiently large classes F), thus showing that the random walk approach proposed by Jerrum & Sinclair (1989) and refined by Hayes & Sinclair (2010), is optimal. This answers an open question posed by Hayes & Sinclair. We then show that this lower bound can be circumvented if the size of F is bounded appropriately. As we discuss, this latter result can be viewed as an abstraction of TTT, and thus represents a starting point for the development of a principled theoretical framework for TTT.