# Sample, Don't Search: Rethinking Test-Time Alignment for Language Models

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 46 of its 83 references that are in the map.
- First posted on arXiv 4 Apr 2025.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)
- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)

## Builds on (most cited first, 30 of 46)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Gemini: A Family of Highly Capable Multimodal Models](https://mlsanity.com/paper/2312.11805/) (2023)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Self-critiquing models for assisting human evaluators](https://mlsanity.com/paper/2206.05802/) (2022)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [Generating Sequences by Learning to Self-Correct](https://mlsanity.com/paper/2211.00053/) (2022)
- [A Survey of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2312.14925/) (2023)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [Are We Done with MMLU?](https://mlsanity.com/paper/2406.04127/) (2024)
- [BERT has a Mouth, and It Must Speak: BERT as a Markov Random Field Language Model](https://mlsanity.com/paper/1902.04094/) (2019)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [Solving Challenging Math Word Problems Using GPT-4 Code Interpreter with Code-based Self-Verification](https://mlsanity.com/paper/2308.07921/) (2023)

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

- [RewardBench 2: Advancing Reward Model Evaluation](https://mlsanity.com/paper/2506.01937/) (2025)
- [Scaling Test-time Compute for LLM Agents](https://mlsanity.com/paper/2506.12928/) (2025)
- [Security Challenges in AI Agent Deployment: Insights from a Large Scale Public Competition](https://mlsanity.com/paper/2507.20526/) (2025)
- [Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling](https://mlsanity.com/paper/2504.05410/) (2025)
- [AdaBoN: Adaptive Best-of-N Alignment](https://mlsanity.com/paper/2505.12050/) (2025)
- [Textual Bayes: Quantifying Prompt Uncertainty in LLM-Based Systems](https://mlsanity.com/paper/2506.10060/) (2025)
- [Enhancing Large Language Model Reasoning with Reward Models: An Analytical Survey](https://mlsanity.com/paper/2510.01925/) (2025)
- [Rare Event Analysis of Large Language Models](https://mlsanity.com/paper/2602.06791/) (2026)
- [Demystifying LLM-as-a-Judge: Analytically Tractable Model for Inference-Time Scaling](https://mlsanity.com/paper/2512.19905/) (2025)
- [Less Data Less Tokens: Multilingual Unification Learning for Efficient Test-Time Reasoning in LLMs](https://mlsanity.com/paper/2506.18341/) (2025)
- [Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment](https://mlsanity.com/paper/2603.06797/) (2026)
- [Reliable Chain-of-Thought via Prefix Consistency](https://mlsanity.com/paper/2605.07654/) (2026)
- [Tree Reward-Aligned Search for TReASURe in Masked Diffusion Language Models](https://mlsanity.com/paper/2509.23146/) (2025)
- [Kad: A Framework for Proxy-based Test-time Alignment with Knapsack Approximation Deferral](https://mlsanity.com/paper/2510.27017/) (2025)
- [STARS: Synchronous Token Alignment for Robust Supervision in Large Language Models](https://mlsanity.com/paper/2511.03827/) (2025)
- [Probabilistic Programs of Thought](https://mlsanity.com/paper/2604.17290/) (2026)
- [DecompressionLM: Deterministic, Diagnostic, and Zero-Shot Concept Graph Extraction from Language Models](https://mlsanity.com/paper/2602.00377/) (2026)
- [On the Rejection Criterion for Proxy-based Test-time Alignment](https://mlsanity.com/paper/2604.16146/) (2026)
- [Multimodal Diffusion to Mutually Enhance Polarized Light and Low Resolution EBSD Data](https://mlsanity.com/paper/2604.22212/) (2026)
- [Gradient-Guided Reward Optimization for Inference-time Alignment](https://mlsanity.com/paper/2606.09635/) (2026)
- [Best-of-Better-N: Generating Pre-Aligned Responses with In-Context Learning](https://mlsanity.com/paper/2607.03453/) (2026)
- [Flow-Support-Weighted Proposals for Test-Time Verified VLA Policies](https://mlsanity.com/paper/2610.14588/) (2026)

## Abstract (arXiv)

Increasing test-time computation has emerged as a promising direction for improving language model performance, particularly in scenarios where model finetuning is impractical or impossible due to computational constraints or private model weights. However, existing test-time search methods using a reward model (RM) often degrade in quality as compute scales, due to the over-optimization of what are inherently imperfect reward proxies. We introduce QAlign, a new test-time alignment approach. As we scale test-time compute, QAlign converges to sampling from the optimal aligned distribution for each individual prompt. By adopting recent advances in Markov chain Monte Carlo for text generation, our method enables better-aligned outputs without modifying the underlying model or even requiring logit access. We demonstrate the effectiveness of QAlign on mathematical reasoning benchmarks (GSM8K and GSM-Symbolic) using a task-specific RM, showing consistent improvements over existing test-time compute methods like best-of-n and majority voting. Furthermore, when applied with more realistic RMs trained on the Tulu 3 preference dataset, QAlign outperforms direct preference optimization (DPO), best-of-n, majority voting, and weighted majority voting on a diverse range of datasets (GSM8K, MATH500, IFEval, MMLU-Redux, and TruthfulQA). A practical solution to aligning language models at test time using additional computation without degradation, our approach expands the limits of the capability that can be obtained from off-the-shelf language models without further training.