Paper deep dive
Sample, Don't Search: Rethinking Test-Time Alignment for Language Models
Gonçalo Faria, Noah A. Smith
Models: Tülu3
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/12/2026, 6:48:37 PM
Summary
The paper introduces QAlign, a test-time alignment method for language models that uses Markov chain Monte Carlo (MCMC) sampling to converge to an optimal aligned distribution. Unlike existing methods like best-of-n (BoN) or majority voting, which can suffer from over-optimization of imperfect reward models as compute scales, QAlign provides consistent performance improvements without requiring model finetuning or logit access.
Entities (6)
Relation Signals (3)
QAlign → evaluatedon → GSM8K
confidence 100% · We demonstrate the effectiveness of QAlign on mathematical reasoning benchmarks (GSM8K and GSM-Symbolic)
QAlign → outperforms → DPO
confidence 95% · QAlign outperforms direct preference optimization (DPO), best-of-n, majority voting, and weighted majority voting
QAlign → uses → Markov chain Monte Carlo
confidence 95% · By adopting recent advances in Markov chain Monte Carlo for text generation, our method enables better-aligned outputs
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
Trouble viewing inline? Open PDF directly →
Full Text
72,158 characters extracted from source content.
Expand or collapse full text
Preprint SAMPLE, DON’T SEARCH: RETHINKING TEST-TIME ALIGNMENT FOR LANGUAGE MODELS Gonçalo Faria 1 , Noah A. Smith 1,2 1 University of Washington, 2 Allen Institute for AI gfaria@cs.washington.edu ABSTRACT Increasing test-time computation has emerged as a promising direction for improv- ing 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 sam- pling from the optimal aligned distribution for each 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 reason- ing 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. When applied with more realistic RMs trained on the TÜLU 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 practi- cal 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. 1INTRODUCTION Language models (LMs) have demonstrated remarkable capabilities through learning from human preferences (Stiennon et al., 2022; Fernandes et al., 2023; Kaufmann et al., 2023; Peters & Schaal, 2007; Peng et al., 2019; Korbak et al., 2022b;a; Go et al., 2023). However, there are a number of problems with deploying a single aligned model: alignment approaches typically average multiple human preferences, constructing a monolithic preference model and target policy. Furthermore, approaches to adapting these models through finetuning have become increasingly impractical, requiring enormous computational resources. They are entirely impossible when model weights are private, as with many state-of-the-art models (OpenAI, 2024; Anthropic, 2024; Gemini, 2024). While conventional alignment methods optimize a single model for aggregate performance across a distribution of prompts and then produce a random generation during inference, researchers have found great improvement from scaling the amount of compute expended at test time for each prompt (Brown et al., 2024; Snell et al., 2024). Here, multiple outputs are generated and then used to produce a final answer either via reward maximization (known as “best-of-n,” or BoN; Gao et al., 2022; Stiennon et al., 2020; Fernandes et al., 2022), majority voting (MV; Wang et al., 2023b) or weighted majority voting (WMV; Li et al., 2023). While promising, existing search-based methods face fundamental limitations (Liu et al., 2024; Wu et al., 2024; Zhang et al., 2023; Xie et al., 2023): as inference compute scales, these methods over-optimize learned reward models (RMs), which are inherently imperfect proxies (Gao et al., 2022). 1 arXiv:2504.03790v2 [cs.CL] 18 Dec 2025 Preprint 2 1 2 3 2 5 2 7 2 9 2 11 Inference FLOPS per question (×10 12.9 ) 0.35 0.40 0.45 0.50 0.55 Avg Test Error SFT-BoN SFT-MV SFT-WMV DPO-MV SFT-QAlign Figure 1: Average error rate across multiple evaluation datasets (GSM8K, MATH500, MMLU-Redux, TruthfulQA, and IFEval) as a function of inference-time floating point operations (FLOPS) in log scale. We compare • QALIGN with TÜLU3-8B-SFT against four baselines:▲majority vote (MV) TÜLU3-8B-DPO, and applied to TÜLU3-8B-SFT the methods • best-of-n (BoN), • MV, and • weighted MV (WMV) . All experiments use temperature 1.0 with reasoning included in model outputs. The TÜLU3-8B-DPO model results from preference finetuning TÜLU3-8B-SFT (approximately 1.75× 10 19 FLOPs). The costs of this process are not accounted for in this plot. In this paper, we introduce QALIGN, a test-time alignment method that converges to sampling from the optimal aligned distribution (defined in §1 as the true target for existing RLHF methods) for each prompt, individually, as the test-time compute budget is increased. This enables more aligned responses without requiring access to the logits or training any underlying LM (only sampling from it). Specifically, we adapt QUEST (Faria et al., 2024). QUEST was designed to repurpose a language model, creating a Markov chain converging toward a (Gibbs) distribution defined by machine translation quality estimation metrics. In this work, we show that we can use QUEST to align LMs at test time according to an RM learned from preference data (in place of the quality estimation metric) and to provide a single good final prediction. In our experiments (§4), we compare QALIGN with existing test-time compute methods on mathe- matical reasoning benchmarks (GSM8K, Cobbe et al., 2021, and GSM-Symbolic, Mirzadeh et al., 2024), by training a task-specific RM (§4.1), and using it to increase the capability of LLAMA3.1- 8B-INSTRUCT (Llama, 2024). We obtain a consistent reduction in error as we scale inference time computation across scales, as shown in Figure 2. Unlike BoN, QALIGN’s performance does not degrade as we increase the compute per question. Furthermore, when applied with more realistic RMs (§ 4.2), trained on the TÜLU3 (Lambert et al., 2024) preference dataset, where over-optimization starts to appear at a lower inference budget, and applied to TÜLU3-8B-SFT, our experiments show that QALIGN can consistently outperform direct preference optimization (DPO; Rafailov et al., 2024), which updates the model weights, as well as BoN, MV, and WMV on a diverse range of datasets in mathematical reasoning (GSM8K and MATH500; Hendrycks et al., 2021; Lightman et al., 2023), knowledge recall (MMLU-Redux; Gema et al., 2025), TruthfulQA (Lin et al., 2022) and instruction following (IFEval; Zhou et al., 2023b), as shown in Figure 1. 1 Our contributions are: •We propose QALIGN, a method for making local approximations of the optimal aligned distribution at test time. • We show a28.4%increase in accuracy on GSM8K and78.34%on GSM-Symbolic relative to a single generation, using a task-specific RM, beating BoN, MV, and WMV. •We show that QALIGN outperforms DPO when applied to TÜLU3 family of models, in general RMs trained on the TÜLU3 preference dataset, even when compared with the same 1 Website with code and additional resources will be provided upon acceptance. 2 Preprint compute budget at test-time via MV, achieving a47.85%increase in average accuracy relative to a single generation across a suite of benchmarks. 2BACKGROUND: LANGUAGE MODEL ALIGNMENT Finetuning a pretrained LMp LM (y | x)to align with preferences encoded by a reward function r(y,x)can be cast as Bayesian inference (Korbak et al., 2022a). We seekπ(y | x), which is initially equal to a priorp LM (y | x), and updated to conform to evidence provided by the human preferences model. Letγ = 1denote the event that responseyis maximally preferred for promptx(i.e.,y ⪰ y ′ for ally ′ ∈Y). Assuming the reward function is bounded, we can model the likelihood of this event asp(γ = 1| y,x) = exp ((r(y,x)− max y ′ r(y ′ ,x))/β). Using Bayes’ rule, the posterior takes the following form: π(y | x) ≜ p(y | γ = 1,x) = 1 Z β (x) p LM (y | x) exp r(y,x) β .(1) It is both intractable to compute the partition functionZ β (x) = P y∈Y p LM (y | x) exp(r(y,x)/β), and to sample from the distribution in Eq. 1 exactly. To approximateπ(y | x), many methods have been proposed (Stiennon et al., 2022; Fernandes et al., 2023; Kaufmann et al., 2023; Peters & Schaal, 2007; Peng et al., 2019; Korbak et al., 2022b;a; Go et al., 2023). Given a dataset of promptsD, one common approach is to estimate a parameterized variational approximation q θ (y | x)(see Appendix B for details): max θ E x∼D E y∼q θ (y|x) [r φ (y,x)/β]− D KL (q θ (y | x)∥ p LM (y | x)) .(2) Methods like PPO (Schulman et al., 2017) and others (Shao et al., 2024; Rafailov et al., 2024; Ahmadian et al., 2024) optimize this objective with low-variance gradient estimates, resulting in stable optimization. Importantly, q θ (y | x) is a newly trained LM initialized with p LM (y | x). 3TEST-TIME ALIGNMENT VIA MCMC Casting language model alignment as posterior inference decouples our target goal from the procedure used to achieve it. While current approaches rely on variational inference to learn a single model q θ (y | x)(Eq. 2), this strategy faces four limitations. First, it requires expensive model finetuning, which is costly with large models. Second, many models’ weights are not openly shared, including those of state-of-the-art models like GPT-4 (OpenAI, 2024) and Gemini (Gemini, 2024). Third, amortizing the approximation across all prompts necessarily sacrifices the quality of approximation for any individual promptxto achieve good average performance. Fourth, the approach assumes a monolithic notion of human preferences encoded inr(y,x), offering no flexibility to adapt to varying user preferences or contexts at inference time. These limitations motivate a shift toward local posterior approximations, where we achieve a better approximation as we increase the compute budget at test time on a single promptx. As we will describe in (§3.1), our key insight is that rather than estimating a single parametric approximation, we can use recent advancements in Markov chain Monte Carlo (MCMC) sampling with LMs (Faria et al., 2024) and obtain a sequence of samplesS =⟨y 0 ,y 1 ,...,y T ⟩fromπ(y | x)and use them for optimal decision-making. A principled way to select a final response from the generated candidate setSfromπ(y | x)is by selecting the most common element (mode) i.e., via majority voting (MV; Wang et al., 2023b). However, this only works for tasks with well-defined answers, such as mathematical reasoning or multiple-choice questions. For open-ended generation tasks, we apply a generalization of this approach through the minimum Bayes risk (MBR) principle (Kumar & Byrne, 2002; Eikema & Aziz, 2020; Farinhas et al., 2023; Bertsch et al., 2023). The MBR framework selects the outputˆythat maximizes the expected task-specific utility u(y,y ′ ): ˆy = arg max y∈S E y ′ ∼π(y ′ |x) u(y,y ′ ) ≈ arg max y∈S 1 T + 1 P T t=0 u(y,y t ).(3) When the utility metricu(y,y ′ )is defined as an exact match over the final answer, MBR amounts to a MV strategy overS. We employ ROUGE (Lin, 2004) as our utility metric for open-ended generation 3 Preprint tasks, following Bertsch et al. (2023). While this results inO(T 2 )similarity computations, ROUGE is computationally lightweight. In the following sections, we describe two practical approaches to obtain a final answer based on MBR to samples fromπ(y | x). First, QALIGN (§3.1), our novel MCMC-based approach to sample from the aligned distributionπ(y | x)at test time, allowing us to apply MBR directly to these samples. Second, in §3.2, we present importance sampling, a classical alternative that circumvents direct sampling from the aligned distribution by reweighting samples from the base modelp LM (y | x) to approximate MBR as if they were drawn fromπ(y | x). Finally, in §3.3, we describe best-of-n sampling (BoN), a simple and widely used baseline approach for test-time alignment that does not explicitly optimize an MBR objective but instead selects a single high-reward sample from the base model. 3.1MCMC FOR TEXT GENERATION With the goal of generating a sequence of samples fromπ β (y | x), we will construct a Markov chain (y 0 ,y 1 ,...,y T )that hasπ β (y | x)as its equilibrium distribution. The chain starts from a hypothesis y 0 ∼ p LM (y | x). On thetth iteration, it draws a new hypothesisyfrom a proposal distribution q(y | y t ,x), and this hypothesis is accepted with an acceptance probabilityα β (y,y t )∈ [0, 1]. The proposal distributionq(y | y t ,x)we use is the one proposed by QUEST (Faria et al., 2024). It is based on a LM that samples suffixesp LM (y i:N | y <i ,x)starting at uniformly sampled indexi. This proposal can be written as q(y | y t ,x,i) = p LM (y i:N | y t <i ,x)× 1y 1:i = y t 1:i ,(4) Following the Metropolis-Hastings algorithm (MH; Hastings, 1970), the acceptance probability is α β (y,y t ) = min 1, π β (y | x)q y t | y,x π β y t | x q y | y t ,x .(5) If the candidateyis accepted, the next state in the chain becomesy t+1 = y; if rejected, the chain stays aty t+1 = y t . The process repeats for some number of stepsT. In the end, it returns the set of accepted samples. Note that, while computing the likelihoodπ β (y | x)of a particular hypothesis yunder the target distribution is intractable (due to the partition functionZ β (x)), evaluating the acceptance criterionα β (y,y t )is easy, because it depends only on the likelihood ratio, in which the normalization constants cancel out: π β (y | x) π β (y t | x) = exp r(y,x)−r ( y t ,x ) β p LM (y | x) p LM (y t | x) .(6) MH converges to the unique stationary distributionπ β (y | x), regardless of the initial distribution, because the transition distribution of the Markov chain,p(y t | y t−1 ,x)which results from generating a candidate fromq(y t | y t−1 ,x)followed by an accept/reject step, satisfies the Markov chain ergodic theorem (Neal, 2011)(see Appendix C for a detailed proof). Note that, under samples from the proposal from Eq. 4, the likelihood ratio from Eq. 6 is proportional to the inverse of the probability of returning: q(y t | y,x,i) q(y | y t ,x,i) = p LM (y t i:N | y t <i ,x) p LM (y i:N | y t <i ,x) ,(7) this allows simplifying the criterion as: α β (y,y t ) = min 1, exp r(x,y)−r ( x,y t ) β |y t |/|y| .(8) The length ratio|y t |/|y|comes from the ratio between the uniform index distributions. Note that this means that we can sample from the aligned distribution in Eq. 1 without any access to logits or parameter weights. In summary, we propose a simple and effective procedure for sampling fromπ(y | x). We characterize the QALIGN sampling process as repeating the following for T steps: 1. Given an instance y t with length|y t |, sample an index i uniformly. 4 Preprint 2. Generate a completion y i:N from p LM (y i:N | y t <i ,x). 3. Compute the probability of acceptance on the reward difference in Eq. 8. Sample a random boolean based on this probability. If we reject, y t+1 = y t ; if we accept, y t+1 = y ′ . The QUEST proposal is simple and relies solely on the model’s ability to generate text left-to-right, with the consequence that successive samples are only conditionally dependent up to the indexi, which limits the speed at which we can explore (i.e., the effective sample size). While more complex proposals could be built based on LMs prompted to self-refine (Zhou et al., 2023a; Madaan et al., 2023; Yao et al., 2023), recent work demonstrates that even strong LMs often fail to improve reasoning due to models’ inability to gauge the correctness of their outputs and localize errors (Huang et al., 2024). Because of this, a growing body of research tries to teach LMs how to self-correct by creating data-augmentation recipes (Welleck et al., 2022; Havrilla et al., 2024) or new datasets (Wang et al., 2023a; Chen et al., 2024; Lee et al., 2024; Saunders et al., 2022; Schick et al., 2022). However, when the proposal is different from the base model, we lose the simplicity of the acceptance criterion in Eq. 8 and need to keep track of two sets of logits to calculate the acceptance criterion in Eq. 5. As our approach only requires access to the ability to generate continuations given a prefix (not access to base model parameters or logits), it can also be used with closed LMs through an API. However, we limit our experiments to open-weight models. We provide in Appendix D an analysis of the computational cost associated with running QALIGN. 3.2IMPORTANCE SAMPLING A natural competing approach to QALIGN for approximating the intractable expectation in Eq. 3 is to use importance sampling (IS; Kahn, 1950). Rather than attempting to directly sample from the target distributionπ(y | x), IS generates samples from the base LMp LM (y | x)and reweights them to match the target distribution π(y | x): E y∼π(y|x) [u(y,y ′ )] =E y∼p LM (y|x) π(y | x) p LM (y | x) u(y,y ′ ) =E y∼p LM (y|x) " exp( 1 β r(y,x)) Z β (x) u(y,y ′ ) # . The partition functionZ β (x)can be reframed as an expectation over samples from the base model: Z β (x) = P y∈Y p LM (y | x) exp(r(y,x)/β) =E y∼p LM (y|x) [exp(r(y,x)/β)] . This motivates a self-normalizing importance sampling approach, where we approximate both the numerator and denominator using samplesy (i) K i=1 ∼ p LM (y | x). The self-normalized estimator is consistent, but introduces bias due to the correlation between the numerator and denominator (Owen, 2013). In the end, making this approximation boils down to the following steps: 1. Sample y (0) ,...,y (T) ∼ p LM (y | x). 2. Evaluate the generations with the reward model r(y,x) resulting in r (0) ,...,r (T) . 3. Obtain the importance weights w (i) = exp(r (i) /β) . P T j=0 exp(r (j) /β) . 4. For each hypothesis y ′ , computeE y∼π(y|x) [u(y,y ′ )]≈ P T i=0 w (i) u(y,y (i) ). In the LM literature, this procedure, for the specific case of tasks with well-defined final answers (i.e., the utility metricu(y,y ′ )is defined as an exact match), the MBR output is the same as weighted majority voting (WMV; Li et al., 2023). Similar to QALIGN, WMV is guaranteed to converge to the optimal decision rule as computational resources increase. However, because it relies solely on independent samples drawn from the base LM, the generation process cannot be directly steered toward more promising regions of the output space. This limitation becomes particularly problematic when the base LM infrequently produces high-reward responses. In such cases, the approximation of the target expectation, and corresponding final decision, will be compromised. 3.3BEST-OF-n SAMPLING Best-of-n(BoN) sampling is a simple approach for aligning language model predictions at test time. BoN has emerged as a strong baseline in the literature, requiring no additional training, while still 5 Preprint achieving compelling performance. Unlike QALIGN and IS, which explicitly optimize for a MBR objective, BoN uses a heuristic selection process. Given a promptx, we generatencandidate responsesy 1 ,y 2 ,...,y n independently from the base LMp LM (y | x). Each response is evaluated using the RMr(x,y), and the candidate with the highest reward is chosen as the final output: y ∗ (n) = arg max y i r(x,y i ).(9) This procedure implicitly biases the output distribution toward higher-reward responses. It is easy to see that in the limit ofn, we are sampling from the maximum reward distribution; however, BoN is remarkably performant even whennis small (Fernandes et al., 2022; Gao et al., 2022; Llama, 2024). With some strong assumptions, we can show that the probability density of the BoN distribution can be approximated by our target distributionπ(y | x)from Eq. 1 in the special case whenβtakes the form: β(n) = σ d (x) √ 2 logn d − (log logn d +log(4π)) 2 √ 2 logn d .(10) whereσ d (x)is the standard deviation of the dominant component of the distribution of reward, under the assumption of Gaussian mixture, which we empirically observe (see Appendix E), when evaluated on samples from our base LM conditioned onx, andn d = w d (x)n, the dominant component’s sample size, wherew d (x)is the weight of the dominant component. A full derivation of this approximation is provided in Appendix A. This rough equivalence, not noted in past literature to our knowledge, provides a new insight into a key distinction between BoN and the other methods we have discussed, including QALIGN. In QALIGN, we explicitly define a target distributionπ(y | x), and increasing the test-time budgetn refines our approximation of this fixed objective. In contrast, BoN does not converge to a predefined distribution; instead, increasingnprogressively shifts the selection process toward responses with higher rewards and deviating further fromp LM (y | x). Insofar as the reward model is well-aligned with human preferences, this should make BoN highly effective. However, in realistic settings where the reward is imperfect, increasingncan lead to over-optimization, i.e., selecting responses that score well under the reward model but degrade in actual quality. As a result, BoN can suffer from diminishing returns or even performance degradation as test-time compute increases, which we observe in our experiments (§4.1–4.2) and previous work (Gao et al., 2022). 4EXPERIMENTS Our experiments are centered around two main questions. First, task-specific tuning: given a powerful task-specific RM trained on preference data derived from ground-truth evaluations of base model outputs, can QALIGN outperform BoN and WMV (§4.1)? Second, general alignment: when applied as an alternative to DPO, where the preference dataset encompasses multiple tasks aimed at improving the instruction-following capabilities of chat models, can QALIGN outperform state-of-the-art alignment methods (§4.2)? 4.1TASK-SPECIFIC TUNING We evaluate QALIGN for task-specific tuning using LLAMA-3.1-8B-INSTRUCT (Llama, 2024) as the base model and a custom Bradley & Terry (1952) RM trained on our preference dataset for mathematical reasoning (training details in Appendix H). This RM was initialized with LLAMA-3.1- 8B-INSTRUCT and trained on 64 model-generated response pairs per prompt. We selected pairs based on ground truth answers. 2 Baselines We compare against BoN, and WMV sampling applied to LLAMA-3.1-8B-INSTRUCT using our trained RM and MV from samples from LLAMA-3.1-8B-INSTRUCT. For each of the methods we generate 1024 solutions per problem. 2 Data and RM will be provided upon publication. 6 Preprint Datasets We evaluate on GSM8K (Cobbe et al., 2021), a dataset of grade school math problems, and GSM-Symbolic (Mirzadeh et al., 2024), a new benchmark designed to assess out-of-distribution generalization in mathematical reasoning. As demonstrated by Mirzadeh et al. (2024), GSM-Symbolic exposes substantial performance degradation across state-of-the-art LLMs exhibiting drops of up to 65%compared to their GSM8K scores when faced with simple variations like changed numerical values and extra redundant clauses. Sampling configurations We sampled both datasets with temperature1.0andβ = 1. Since the acceptance rate is a function ofσ r (x)/β(whereσ r (x)is the distribution of rewards under the base model), we selected this value to achieve approximately50%acceptance rate based on tuning with 128 samples from the GSM8K training data. This relatively high acceptance rate ensures the chain mixes well and avoids getting stuck in a single mode. Results The results of the task-specific tuning experiments are summarized in Figure 2. QALIGN shows progressively lower error rates across both problems as we spend more computational resources. In contrast, on GSM8K, MV shows initial improvement but quickly saturates, while BoN displays improvement with additional compute, temporarily outperforming QALIGN, but eventually reaches an inflection point, after which error rates begin to increase. This behavior aligns with the observations from Gao et al. (2022) and theoretical results from §3.3. WMV performs well on GSM8K but becomes relatively worse after a budget of approximately 2 8 × 10 12.51 FLOPs. While all methods show some performance drop on GSM-Symbolic compared to GSM8K, the magnitude varies significantly. BoN and WMV, which rely on the RM, struggle more with the distribution shift, likely because the RM is fit to particular GSM8K-specific patterns. Relative to these two, MV shows greater robustness to these changes. This is primarily because under the distribution shift the RM becomes less reliable, and since MV does not use it, MV’s performance degrades less. However, even under these circumstances, QALIGN is able to leverage the RM and outperform MV on this dataset with enough compute. This suggests that QALIGN is robust to imperfections in the RM and able to extract a useful signal even when the RM’s reliability is compromised. 2 1 2 3 2 5 2 7 2 9 2 11 Inference FLOPS per question (×10 12.51 ) 0.10 0.15 0.20 0.25 GSM8K Test Error BoN MV WMV QAlign 2 1 2 3 2 5 2 7 2 9 2 11 Inference FLOPS per question (×10 12.53 ) 0.20 0.25 0.30 0.35 0.40 0.45 0.50 0.55 GSM8K-Symbolic Test Error BoN MV WMV QAlign Figure 2: Average accuracy vs. floating point operations (FLOPS) in log scale. We compare • QALIGN with LLAMA-3.1-8B-INSTRUCT against three baselines also applied to LLAMA-3.1-8B- INSTRUCT: • best-of-n(BoN), • majority vote (MV), and • weighted MV (WMV). Left: Error rate (lower is better) on GSM8K test dataset. Right: Error rate on GSM-Symbolic test dataset. All experiments use temperature 1.0 with reasoning included in model outputs. 4.2GENERAL ALIGNMENT We evaluate QALIGN for more general alignment using TÜLU3-8B-SFT as the base model and TÜLU3-8B-RM as the RM. The TÜLU3 model family (Lambert et al., 2024) was selected for being fully open source, providing instruction-tuned, and aligned versions, along with their corresponding training code and datasets. This enables direct comparison of QALIGN on top of the instruction-tuned model to the aligned model, sharing the initial starting point. Additionally, they provide an RM trained on the data used to train the DPO model, which we use in our experiments. 7 Preprint MethodMATH500 GSM8KTQAMMLU-ReduxIFEvalAvg (0 shot, CoT)(0 shot, CoT)(MC2, 0 shot, CoT)(0 shot, CoT)(prompt loose) TÜLU3-8B-SFT BON31.674.345.357.159.353.5 MV49.486.343.759.472.662.3 WMV53.085.246.162.249.559.2 QALIGN60.488.248.562.277.667.4 TÜLU3-8B-DPO MV55.887.945.462.776.265.6 Table 1: Overview of the results on general alignment. Results show accuracy percentages with fixed 1024 sampled solutions across different methods and models. Our proposed QALIGN outperforms other approaches on most benchmarks, achieving the highest scores on all datasets when applied to TÜLU3-8B-SFT, and attaining an average performance better than TÜLU3-8B-DPO. The highlighted cells indicate best result per benchmark. BaselinesWe compare against (1) MV applied to TÜLU3-8B-DPO, (2) BoN sampling applied to TÜLU3-8B-SFT using TÜLU3-8B-RM, (3) WMV applied to TÜLU3-8B-SFT using TÜLU3-8B- RM, and (4) MV applied to TÜLU3-8B-SFT. Note that TÜLU3-8B-DPO model is the result of doing preference finetuning on the TÜLU3-8B-SFT with 271k preference pairs (approximately1.75× 10 19 FLOPs). Comparing against DPO with MV additionally allows for an inference FLOPs-adjusted comparison between a model explicitly optimized for alignment and our QALIGN approach. This allows us to test whether QALIGN is not only a better test-time alignment approach, but a better overall alignment approach when significant compute is available at test-time. Datasets We evaluate again on GSM8K; we add MATH500, a verified subset of the MATH test dataset that contains advanced mathematical problems across algebra, geometry, and calculus (Hendrycks et al., 2021), MMLU-Redux (Gema et al., 2025), a refined subset of commonsense and academic knowledge questions, TruthfulQA (Lin et al., 2022), which contains misleading questions designed to elicit truthful responses, and IFEval (Zhou et al., 2023b), which measures adherence to complex multi-step instructions. Among these datasets, IFEval is an open-ended generation and, therefore, requires the use of MBR with ROUGE-1instead of MV and WMV. For simplicity, we still refer to the method as MV and WMV to denote MBR from base model samples and the weighted version with importance sampling, respectively, in our comparisons. Sampling Configurations For all datasets, we sampled the model with a temperature of 1.0 and prompted it to provide reasoning. Complete prompts are available in Appendix F. As with the mathematical reasoning experiments, we tuned theβparameter (in this case,β = 0.5), for TÜLU3- 8B-RM, using128samples from the GSM8K training data to achieve an average acceptance rate of 50%, and using the same β for all datasets. Results The results of the general alignment experiments are summarized in Table 1. Figure 1 plots the average error rate across all of the datasets as a function of the floating point operations (FLOPS), and Appendix G contains all of the error plots for each individual problem. Similar to our task-specific findings, QALIGN, MV, and WMV consistently reduce error rates across all five general alignment datasets as computation increases, with MV exhibiting early saturation. However, similar to the results from GSM-Symbolic, MV outperforms both WMV and BoN. MV applied to the DPO model begins with lower error rates but saturates earlier, ultimately reaching error rates that are worse than QALIGN’s final results. Furthermore, we observe that BoN’s inflection point occurs at a lower computational budget than observed in task-specific experiments. This suggests that for real-world alignment problems, BoN is not an effective test-time approach, while QALIGN maintains its improvement trajectory even with general RMs. 8 Preprint 5RELATED WORK MCMC for Text Generation.Our work builds on QUEST (Faria et al., 2024), which uses MCMC to sample diverse translations. While QUEST successfully generates multiple translations, its ef- fectiveness as a selection mechanism for a single high-quality response remained unexplored until now. Earlier works have applied MCMC approaches to both autoregressive and masked language models (MLMs). For instance, Miao et al. (2018) and Zhang et al. (2020) use MH with a proposal distribution that makes token-level modifications for constrained generation tasks. In the case of MLMs, previous works have explored various forms of Gibbs sampling (Berglund et al., 2015; Su et al., 2018; Wang & Cho, 2019; Yamakoshi et al., 2022). However, as Goyal et al. (2022) show, the conditional distributions from MLMs result in invalid Gibbs samplers. In response, they propose an MH correction on the masked conditionals, resulting in higher quality generations. Building on this, Mireshghallah et al. (2022) and Forristal et al. (2023) apply MLMs for controlled text generation. Furthermore, several works have adapted Hamiltonian MCMC algorithms originally designed for high-dimensional continuous distributions (Duane et al., 1987; Neal, 2011) to discrete text generation (Kumar et al., 2022; Qin et al., 2022; Amini et al., 2023; Du et al., 2023). Test-Time Scaling.Test-time scaling methods have emerged as an important approach for improv- ing LM performance without additional training. While our work focuses on local approximations to the optimal aligned distribution from Eq. 1, a parallel line of research explores heuristic search strategies. Best-of-n(BoN; Gao et al., 2022; Stiennon et al., 2020), majority voting (MV; Wang et al., 2023b), weighted majority voting (WMV; Li et al., 2023) are examples of such approaches. As we outline in§ 3.2–3.3, BoN and WMV can be interpreted as doing test-time alignment. The RMs we consider in this work are outcome-based RMs, they only work on full generations. Several recent methods use process-based RMs (PRMs) that evaluate partial generations (Lightman et al., 2023; Wang et al., 2024; Uesato et al., 2022). Many techniques have been developed to take advantage of PRMs through guided beam search (Xie et al., 2023), Monte-Carlo tree search (MCTS; Liu et al., 2024; Zhang et al., 2023), and REBASE (Wu et al., 2024). However, as outlined in DeepSeek-AI (2025), PRMs face significant practical limitations. Furthermore, recent theoretical work has analyzed test-time scaling methods, particularly BoN sampling. Farinhas et al. (2025); Schaeffer et al. (2025) derive BoN scaling laws relating the number of generated samples to performance gains. Gui et al. (2024) prove that BoN is optimal for the trade- off between win-rate against the base model and KL divergence from the base model. Beirami et al. (2025) provide win-rate guarantees and derive a closed-form probability mass function for the BoN policy, along with a new KL estimator. Yang et al. (2024) show that BoN is asymptotically equivalent to the optimal policy for reward maximization under KL constraints, assuming a memoryless LM and linear reward function. Our work extends this research direction by establishing a novel approximation connecting the BoN distribution withnsamples to the optimal aligned distribution with parameterβ (§ 3.3). 6CONCLUSION AND FUTURE WORK We introduced QALIGN, a test-time alignment method that can sample from the optimal aligned distribution without any model retraining (requiring only a reward model). Our empirical results consistently demonstrate that QALIGN outperforms both search-based approaches that attempt to maximize imperfect reward models (like BoN) and principled alternatives that rely on independent samples from the base LM (such as WMV and MV). Additionally, QALIGN outperforms DPO-tuned models even when they are allowed to match QALIGN’s compute budget at test-time. By enabling strong alignment results without model retraining, QALIGN opens new possibilities for deploying and improving language models in resource-constrained environments and enabling the use of private RMs with closed-source LMs. Looking ahead, we believe this work sets the stage for further exploration of test-time alignment methods. While we have demonstrated success across several benchmarks, several important direc- tions remain unexplored. These include the development of more sophisticated proposal distributions 9 Preprint and using MCMC as a tool to understand the meta-generation strategies that emerge in RL-trained reasoning models. REFERENCES Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadaee, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back to basics: Revisiting reinforce style optimization for learning from human feedback in llms, 2024. URL https://arxiv.org/abs/2402.14740. Afra Amini, Li Du, and Ryan Cotterell. Structured voronoi sampling, 2023. Anthropic. The claude 3 model family: Opus, sonnet, haiku. 2024. URLhttps://api. semanticscholar.org/CorpusID:268232499. Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander D’Amour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees on the best-of-n alignment policy, 2025. URL https://arxiv.org/abs/2401.01879. Mathias Berglund, Tapani Raiko, Mikko Honkala, Leo Kärkkäinen, Akos Vetek, and Juha Karhunen. Bidirectional recurrent neural networks as generative models - reconstructing gaps in time series, 2015. Amanda Bertsch, Alex Xie, Graham Neubig, and Matthew R. Gormley. It’s mbr all the way down: Modern generation techniques through the lens of minimum bayes risk, 2023. URL https://arxiv.org/abs/2310.01387. Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952. ISSN 00063444, 14643510. URL http://w.jstor.org/stable/2334029. Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling, 2024. URL https://arxiv.org/abs/2407.21787. Angelica Chen, Jérémy Scheurer, Tomasz Korbak, Jon Ander Campos, Jun Shern Chan, Samuel R. Bowman, Kyunghyun Cho, and Ethan Perez. Improving code generation by training with natural language feedback, 2024. URL https://arxiv.org/abs/2303.16749. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems, 2021. URLhttps://arxiv.org/ abs/2110.14168. F. N. David and Emil Julius Gumbel. Statistics of extremes. Biometrika, 47:209, 1960. URL https://api.semanticscholar.org/CorpusID:123509308. DeepSeek-AI. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning, 2025. Li Du, Afra Amini, Lucas Torroba Hennigen, Xinyan Velocity Yu, Jason Eisner, Holden Lee, and Ryan Cotterell. Principled gradient-based markov chain monte carlo for text generation, 2023. Simon Duane, A.D. Kennedy, Brian J. Pendleton, and Duncan Roweth.Hybrid monte carlo. Physics Letters B, 195(2):216–222, 1987. ISSN 0370-2693. doi: https://doi.org/ 10.1016/0370-2693(87)91197-X. URLhttps://w.sciencedirect.com/science/ article/pii/037026938791197X. Bryan Eikema and Wilker Aziz. Is MAP decoding all you need? the inadequacy of the mode in neural machine translation. In Donia Scott, Nuria Bel, and Chengqing Zong (eds.), Proceedings of the 28th International Conference on Computational Linguistics, p. 4506–4520, Barcelona, Spain (Online), December 2020. International Committee on Computational Linguistics. doi: 10.18653/v1/2020. coling-main.398. URL https://aclanthology.org/2020.coling-main.398/. 10 Preprint Gonçalo R. A. Faria, Sweta Agrawal, António Farinhas, Ricardo Rei, José G. C. de Souza, and André F. T. Martins. Quest: Quality-aware metropolis-hastings sampling for machine translation, 2024. URL https://arxiv.org/abs/2406.00049. António Farinhas, José G. C. de Souza, and André F. T. Martins. An empirical study of translation hypothesis ensembling with large language models, 2023. URLhttps://arxiv.org/abs/ 2310.11430. António Farinhas, Haau-Sing Li, and André F. T. Martins. Reranking laws for language genera- tion: A communication-theoretic perspective, 2025. URLhttps://arxiv.org/abs/2409. 07131. Patrick Fernandes, António Farinhas, Ricardo Rei, José G. C. de Souza, Perez Ogayo, Graham Neubig, and André F. T. Martins. Quality-aware decoding for neural machine translation, 2022. Patrick Fernandes, Aman Madaan, Emmy Liu, António Farinhas, Pedro Henrique Martins, Amanda Bertsch, José G. C. de Souza, Shuyan Zhou, Tongshuang Wu, Graham Neubig, and André F. T. Martins. Bridging the Gap: A Survey on Integrating (Human) Feedback for Natural Language Generation. Transactions of the Association for Computational Linguistics, 11:1643–1668, 12 2023. ISSN 2307-387X. doi: 10.1162/tacl_a_00626. URLhttps://doi.org/10.1162/ tacl_a_00626. R. A. Fisher and L. H. C. Tippett. Limiting forms of the frequency distribution of the largest or smallest member of a sample. Mathematical Proceedings of the Cambridge Philosophical Society, 24(2):180–190, 1928. doi: 10.1017/S0305004100015681. Jarad Forristal, Niloofar Mireshghallah, Greg Durrett, and Taylor Berg-Kirkpatrick. A block metropolis-hastings sampler for controllable energy-based text generation, 2023. Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization, 2022. URL https://arxiv.org/abs/2210.10760. Aryo Pradipta Gema, Joshua Ong Jun Leang, Giwon Hong, Alessio Devoto, Alberto Carlo Maria Mancino, Rohit Saxena, Xuanli He, Yu Zhao, Xiaotang Du, Mohammad Reza Ghasemi Madani, Claire Barale, Robert McHardy, Joshua Harris, Jean Kaddour, Emile van Krieken, and Pasquale Minervini. Are we done with mmlu?, 2025. URLhttps://arxiv.org/abs/2406.04127. Team Gemini. Gemini: A family of highly capable multimodal models, 2024. URLhttps: //arxiv.org/abs/2312.11805. Dongyoung Go, Tomasz Korbak, Germán Kruszewski, Jos Rozen, Nahyeon Ryu, and Marc Dymet- man. Aligning language models with preferences through f-divergence minimization, 2023. Kartik Goyal, Chris Dyer, and Taylor Berg-Kirkpatrick. Exposing the implicit energy networks behind masked language models via metropolis–hastings, 2022. Lin Gui, Cristina Gârbacea, and Victor Veitch. Bonbon alignment for large language models and the sweetness of best-of-n sampling, 2024. URL https://arxiv.org/abs/2406.00832. Peter Hall. On the rate of convergence of normal extremes. Journal of Applied Probability, 16(2): 433–439, 1979. ISSN 00219002. URL http://w.jstor.org/stable/3212912. W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57:97–109, 1970. URLhttps://api.semanticscholar.org/CorpusID: 21204149. Alex Havrilla, Sharath Raparthy, Christoforus Nalmpantis, Jane Dwivedi-Yu, Maksym Zhuravinskyi, Eric Hambro, and Roberta Raileanu. Glore: When, where, and how to improve llm reasoning via global and local refinements, 2024. URL https://arxiv.org/abs/2402.10963. Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. NeurIPS, 2021. 11 Preprint Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot self-correct reasoning yet, 2024. URLhttps: //arxiv.org/abs/2310.01798. H Kahn. Random sampling (monte carlo) techniques in neutron attenuation problems. i. Nucleonics (U.S.) Ceased publication, Vol: 6, No. 5, 05 1950. URLhttps://w.osti.gov/biblio/ 4441935. Timo Kaufmann, Paul Weng, Viktor Bengs, and Eyke Hüllermeier. A survey of reinforcement learning from human feedback. arXiv preprint arXiv:2312.14925, 2023. Tomasz Korbak, Hady Elsahar, Germán Kruszewski, and Marc Dymetman. On reinforcement learning and distribution matching for fine-tuning language models with no catastrophic forgetting, 2022a. Tomasz Korbak, Ethan Perez, and Christopher L Buckley. Rl with kl penalties is better viewed as bayesian inference, 2022b. Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. Gradient-based constrained sampling from language models, 2022. Shankar Kumar and William Byrne. Minimum bayes-risk word alignments of bilingual texts. In Proceedings of the ACL-02 Conference on Empirical Methods in Natural Language Processing - Volume 10, EMNLP ’02, p. 140–147, USA, 2002. Association for Computational Linguistics. doi: 10.3115/1118693.1118712. URL https://doi.org/10.3115/1118693.1118712. Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James V. Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, Yuling Gu, Saumya Malik, Victoria Graf, Jena D. Hwang, Jiangjiang Yang, Ronan Le Bras, Oyvind Tafjord, Chris Wilhelm, Luca Soldaini, Noah A. Smith, Yizhong Wang, Pradeep Dasigi, and Hannaneh Hajishirzi. Tulu 3: Pushing frontiers in open language model post-training, 2024. URLhttps://arxiv.org/ abs/2411.15124. Ariel N. Lee, Cole J. Hunter, and Nataniel Ruiz. Platypus: Quick, cheap, and powerful refinement of llms, 2024. URL https://arxiv.org/abs/2308.07317. Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Anna Rogers, Jordan Boyd- Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 5315–5333, Toronto, Canada, jul 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.acl-long.291. URL https://aclanthology.org/2023.acl-long.291/. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step, 2023. URL https://arxiv.org/abs/2305.20050. Chin-Yew Lin. ROUGE: A package for automatic evaluation of summaries. In Text Summarization Branches Out, p. 74–81, Barcelona, Spain, July 2004. Association for Computational Linguistics. URL https://aclanthology.org/W04-1013/. Stephanie Lin, Jacob Hilton, and Owain Evans. Truthfulqa: Measuring how models mimic human falsehoods, 2022. URL https://arxiv.org/abs/2109.07958. Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi, and Asli Celikyilmaz. Don’t throw away your value model! generating more preferable text with value- guided monte-carlo tree search decoding, 2024. URLhttps://arxiv.org/abs/2309. 15028. Team Llama. The llama 3 herd of models, 2024. URLhttps://arxiv.org/abs/2407. 21783. 12 Preprint Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback, 2023. URL https://arxiv.org/abs/2303.17651. Nicholas C. Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, and A. H. Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21:1087–1092, 1953. URL https://api.semanticscholar.org/CorpusID:1046577. Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: constrained sentence generation by metropolis-hastings sampling. CoRR, abs/1811.10996, 2018. URLhttp://arxiv.org/ abs/1811.10996. Fatemehsadat Mireshghallah, Kartik Goyal, and Taylor Berg-Kirkpatrick. Mix and match: Learning- free controllable text generationusing energy language models. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 401–415, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653/v1/2022.acl-long.31. URL https://aclanthology.org/2022.acl-long.31. Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models, 2024. URL https://arxiv.org/abs/2410.05229. Radford M. Neal. Probabilistic inference using markov chain monte carlo methods. 2011. URL https://api.semanticscholar.org/CorpusID:9690330. OpenAI. Gpt-4 technical report, 2024. URL https://arxiv.org/abs/2303.08774. Art B. Owen. Monte Carlo theory, methods and examples.https://artowen.su.domains/ mc/, 2013. Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. Advantage-weighted regression: Simple and scalable off-policy reinforcement learning, 2019. Jan Peters and Stefan Schaal. Reinforcement learning by reward-weighted regression for opera- tional space control. In Proceedings of the 24th International Conference on Machine Learning, ICML ’07, p. 745–750, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595937933. doi: 10.1145/1273496.1273590. URLhttps://doi.org/10.1145/ 1273496.1273590. Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. Cold decoding: Energy-based constrained text generation with langevin dynamics, 2022. Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model, 2024. URL https://arxiv.org/abs/2305.18290. William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. Self-critiquing models for assisting human evaluators, 2022. URLhttps://arxiv. org/abs/2206.05802. Rylan Schaeffer, Joshua Kazdan, John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, Azalia Mirhoseini, and Sanmi Koyejo. How do large language monkeys get their power (laws)?, 2025. URL https://arxiv.org/abs/2502.17578. Timo Schick, Jane Dwivedi-Yu, Zhengbao Jiang, Fabio Petroni, Patrick Lewis, Gautier Izacard, Qingfei You, Christoforos Nalmpantis, Edouard Grave, and Sebastian Riedel. Peer: A collaborative language model, 2022. URL https://arxiv.org/abs/2208.11663. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017. URL https://arxiv.org/abs/1707.06347. 13 Preprint Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models, 2024. URLhttps://arxiv.org/abs/ 2402.03300. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling llm test-time compute optimally can be more effective than scaling model parameters, 2024. URLhttps://arxiv.org/abs/ 2408.03314. Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize from human feedback. In NeurIPS, 2020. Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize from human feedback, 2022. Jinyue Su, Jiacheng Xu, Xipeng Qiu, and Xuanjing Huang. Incorporating discriminator in sentence generation: a gibbs sampling method, 2018. Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process- and outcome-based feedback, 2022. URL https://arxiv.org/abs/2211.14275. Alex Wang and Kyunghyun Cho. BERT has a mouth, and it must speak: BERT as a markov random field language model. CoRR, abs/1902.04094, 2019. URLhttp://arxiv.org/abs/1902. 04094. Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifei Li, Deli Chen, Y. Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce llms step-by-step without human annotations, 2024. URL https://arxiv.org/abs/2312.08935. Tianlu Wang, Ping Yu, Xiaoqing Ellen Tan, Sean O’Brien, Ramakanth Pasunuru, Jane Dwivedi-Yu, Olga Golovneva, Luke Zettlemoyer, Maryam Fazel-Zarandi, and Asli Celikyilmaz. Shepherd: A critic for language model generation, 2023a. URLhttps://arxiv.org/abs/2308. 04592. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models, 2023b. URL https://arxiv.org/abs/2203.11171. Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct, 2022. URLhttps://arxiv.org/ abs/2211.00053. Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models, 2024. URL https://arxiv.org/abs/2408.00724. Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min-Yen Kan, Junxian He, and Qizhe Xie. Self-evaluation guided beam search for reasoning, 2023. URLhttps://arxiv.org/abs/ 2305.00633. Takateru Yamakoshi, Thomas Griffiths, and Robert Hawkins. Probing BERT‘s priors with serial reproduction chains. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Findings of the Association for Computational Linguistics: ACL 2022, p. 3977–3992, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653/v1/2022.findings-acl.314. URL https://aclanthology.org/2022.findings-acl.314/. Joy Qiping Yang, Salman Salamatian, Ziteng Sun, Ananda Theertha Suresh, and Ahmad Beirami. Asymptotics of language model alignment, 2024. URLhttps://arxiv.org/abs/2404. 01730. 14 Preprint Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, 2023. URLhttps://arxiv. org/abs/2210.03629. Maosen Zhang, Nan Jiang, Lei Li, and Yexiang Xue. Language generation via combinatorial constraint satisfaction: A tree search enhanced Monte-Carlo approach. In Trevor Cohn, Yulan He, and Yang Liu (eds.), Findings of the Association for Computational Linguistics: EMNLP 2020, p. 1286–1298, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v1/2020.findings-emnlp.115. URLhttps://aclanthology.org/2020. findings-emnlp.115. Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan. Planning with large language models for code generation, 2023. URLhttps://arxiv.org/ abs/2303.05510. Aojun Zhou, Ke Wang, Zimu Lu, Weikang Shi, Sichun Luo, Zipeng Qin, Shaoqing Lu, Anya Jia, Linqi Song, Mingjie Zhan, and Hongsheng Li. Solving challenging math word problems using gpt-4 code interpreter with code-based self-verification, 2023a. URLhttps://arxiv.org/ abs/2308.07921. Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. Instruction-following evaluation for large language models, 2023b. URL https://arxiv.org/abs/2311.07911. 15 Preprint ABEST-OF-n SAMPLING AS TEST-TIME ALIGNMENT Best-of-n(BoN) sampling is a widely used technique for improving model performance by selecting the highest scoring sample amongncandidates. In this section, we show that BoN sampling can be interpreted as an implicit form of test-time alignment that approximates the mode of the target distributionπ(y | x)in Eq. 1. In §A.1, we derive the probability density function (pdf) for BoN sampling. Next, in §A.2, we use extreme value theory to obtain a tractable approximation of rewards of this distribution, and in §A.3 derive an expression for the distribution of rewards of the target densityπ(y | x). Finally, in §A.4, employing a Laplace approximation of the reward distribution, we establish an explicit relationship betweennand the effective parameterβof the aligned distribution π(y | x). A.1DISTRIBUTION OF MAXIMUM REWARD In BoN sampling, given a promptx, we generatencandidate responsesy 1 ,y 2 ,...,y n independently from the base LMp LM (y | x). Each response is evaluated using the RMr(y,x), and the candidate with the highest reward is chosen as the final output: y ∗ (n) = arg max y i r(x,y i ).(11) Let us assume that the reward functionr(x,y)is (locally) injective, that is, eachymaps to a unique reward value. Then, if we denote byp(r | x)the probability density (pdf) of reward values for a particular x under the base LM p LM (y | x) a change of variables yields: p(r | x) = p LM y = r −1 (r,x)| x J r −1 (r) ,(12) where r −1 is the inverse mapping and|J r −1 (r)| is its Jacobian determinant. Givennindependent samples, the cumulative distribution function (cdf)F R (r|x)we can write the cdf for the maximum reward r max as F bon (r (n) max |x) = F R (r (n) max | x) n ,(13) and the respective pdf as p bon (r (n) max |x) = nF R (r (n) max | x) n−1 p(r = r (n) max | x).(14) Since each candidateycorresponds to a rewardr(x,y), the probability density over the best-of-n response can be written as: p(y ∗ (n)|x) = nF R r(x,y ∗ (n))| x n−1 p LM (y ∗ (n)|x).(15) Eq. 15 shows how the BoN procedure emphasizes the upper tail of the reward distribution. The term nF R (r | x) n−1 becomes increasingly significant asngrows, effectively pushing the probability mass towards reward values for which F R (r | x)≈ 1. A.2EXTREME VALUE THEORY Recall that our goal was to establish an explicit relationship between the number of samples we maximize overnand the parameterβof the aligned distribution in Eq. 1. One way to establish this relationship is through the reward distribution. However, even assumingp(r | x)is normal, the mode of the distribution in Eq. 14 lacks a closed-form expression. Following classic results from extreme value theory (Fisher & Tippett, 1928; David & Gumbel, 1960), we know that the distribution of the maximum (appropriately rescaled) converges to a Gumbel distribution. For the specific case where we assume that for a given promptxthe reward function values are distributed as a mixture of two Normal distributions with meansμ 1 (x)andμ 2 (x), variances σ 2 1 (x)andσ 2 2 (x), and mixture weightsw 1 (x)andw 2 (x)(wherew 1 (x) + w 2 (x) = 1). Appendix E provides empirical evidence that this assumption is reasonable. The tail behavior is dominated by the Gaussian component with the heavier tail, typically the one with larger variance (or larger mean if variances are equal). 1− F r (n) max (r)≈ w d (x) 1− Φ r− μ d (x) σ d (x) ,(16) 16 Preprint whereΦis the standard normal CDF,dthe index of the component with the largest variance, i.e., d = arg max i σ 2 i (x) , or if variances are equal,d = arg max i μ i (x)is the index of the component with the largest mean. The work of Hall (1979) provides asymptotic expressions for location and scale parameters. In particular, one finds that the maximum reward is approximately: r (n) max ≈ a n ≡ μ d (x) + σ d (x) p 2 logn d − (log logn d + log(4π)) 2 √ 2 logn d ,(17) and fluctuations about this location are on the order ofb n ≈ σ d (x) √ 2 logn d , and wheren d = nw d (x) denotes the effective sample count from the dominant normal component. So in the limit ofn→∞ the distribution of maximum reward can be expressed as: p(r (n) max |x)≈ Gumbel(a n ,b n ).(18) Figure 3 compares this Gumbel approximation to the empirical distribution of maximum rewards, showing a close fit for n≥ 32. Figure 3: Distribution of the normalized maximum reward(r (n) max − a n )/b n for varyingn, overlaid with the standard Gumbel distribution. The empirical distribution is estimated using 10,000 trials, each consisting ofnrandom samples drawn from a Normal distribution. The fit between the empirical distribution and the Normal distribution improves asnincreases, showing good agreement for n≥ 32. A.3DISTRIBUTION OF REWARDS OF π(y | x) Given the aligned distributionπ(y | x)from Eq. 1, we want an expression for the distribution of rewards under samples fromπ. Following the empirical observations from Appendix E, let us assume that for a given promptx, the reward values under the base language modelp LM (y | x)follow a mixture of two Normal distributions with meansμ 1 (x)andμ 2 (x), variancesσ 2 1 (x) andσ 2 2 (x) , and mixture weights w 1 (x) and w 2 (x) (where w 1 (x) + w 2 (x) = 1), i.e.: p(r | x) = w 1 (x) 1 p 2πσ 2 1 (x) exp − (r− μ 1 (x)) 2 2σ 2 1 (x) +w 2 (x) 1 p 2πσ 2 2 (x) exp − (r− μ 2 (x)) 2 2σ 2 2 (x) . Underπ(y | x), the distribution of rewards can be derived through a change of variables. The probability density of rewards under the policy, denoted as π(r | x), is proportional to: π(r | x)∝ exp r β p(r | x).(19) Substituting the mixture form ofp(r | x)and combining terms in the exponent and through completion of the square in the exponents for each component, we can show that this is equivalent to: π(r | x)∝ w 1 (x)C 1 1 p 2πσ 2 1 (x) exp − 1 2σ 2 1 (x) r− μ 1 (x)− σ 2 1 (x) β 2 ! (20) + w 2 (x)C 2 1 p 2πσ 2 2 (x) exp − 1 2σ 2 2 (x) r− μ 2 (x)− σ 2 2 (x) β 2 ! ,(21) 17 Preprint where C 1 = exp μ 1 (x) β + σ 2 1 (x) 2β 2 and C 2 = exp μ 2 (x) β + σ 2 2 (x) 2β 2 . Therefore, the aligned distribution of rewards remains a mixture of Normals with adjusted mixture weights and means, and preserved variances: π(r | x) = w π,1 N (r;μ π,1 (x,β),σ 2 1 (x)) + w π,2 N (r;μ π,2 (x,β),σ 2 2 (x)),(22) whereμ π,i (x,β) = μ i (x) + σ 2 i (x)/βfori∈1, 2, and the adjusted mixture weights are given by: w π,1 = w 1 (x)C 1 w 1 (x)C 1 + w 2 (x)C 2 , w π,2 = w 2 (x)C 2 w 1 (x)C 1 + w 2 (x)C 2 .(23) This result shows thatβshifts the mean of each component by a factor proportional to that com- ponent’s variance and inversely proportional to the parameterβ, while preserving the variances of the original reward distributions. Additionally, asβapproaches zero, the mixture weight of the component with the larger variance (or larger mean if variances are equal) approaches 1, causing the aligned distribution to collapse to a single Gaussian with an increasingly high mean. For this reason, we write the reward target density expression as approximately only the dominant Gaussian: π(r | x)≈N (r;μ π,d (x,β),σ 2 d (x)),(24) whered = arg max i σ 2 i (x)is the index of the component with the largest variance, or if variances are equal, d = arg max i μ i (x) is the index of the component with the largest mean. A.4RELATING n AND β VIA MODE MATCHING The Gumbel approximation has a mode that can be explicitly expressed as its location parametera n , and the reward distribution of the aligned distribution in Eq. 24 as μ π,d (x,β). Following the results from Appendix A.3, the distribution of rewards under the target densityπ(r|x) is also normal, but with mean μ π,d (x,β) = μ d (x) + σ d (x) 2 /β. By matching this mode with the location parametera n of the Gumbel distribution for BoN sampling i.e.: μ d (x) + σ d (x) 2 β = μ d (x) + σ d (x) p 2 logn d − (log logn d + log(4π)) 2 √ 2 logn d ,(25) we obtain: β ∗ = σ d (x) √ 2 logn d − (log logn d +log(4π)) 2 √ 2 logn d .(26) Figure 4: Distribution of the normalized maximum reward(r (n) max − μ π,d (x,β ∗ ))/σ d (x)for varyingn, overlaid with the standard Normal distribution. The empirical distribution is estimated using 10,000 trials, each consisting ofnrandom samples drawn from a Normal distribution. While the mode of our approximation matches, the approximation does not capture the variance of the empirical distribution. Figure 4 compares the empirical reward distribution to the target distributionπ(r|x)whenβ = β ∗ . The approximation closely matches the mode of the empirical distribution of maximum rewards, 18 Preprint though it struggles to capture the variance accurately. The variance of the BoN reward distribution decreases as a function n, while the one from π(y | x) stays constant. 19 Preprint BRLHF AS BAYESIAN INFERENCE For a fixed prompt x, the RLHF objective from Eq. 2, i.e.: L(θ,x) =E x∼D E y∼q θ (y|x) [r φ (y,x)/β]− D KL (q θ (y | x)∥ p LM (y | x)) , where q θ (y | x) is the learned policy, is maximized by the posterior p(y | γ = 1,x) = 1 Z β (x) p LM (y | x) exp (r(y,x)/β), which we denote by π β (y | x). Proof. Following the definitions in § 2,γ = 1denotes a “preferred” response under the human preference model, andZ β (x)is the normalizing constant. To prove this, we follow the standard variational inference derivation starting from the log evidence logp(γ = 1| x). We begin by writing logp(γ = 1| x) =E y∼q θ (y|x) [logp(γ = 1| x)]. By Bayes’ rule we can rewrite the log evidence as logp(γ = 1| x) =E y∼q θ (y|x) log p(y,γ = 1| x) p(y | γ = 1,x) . We now multiply and divide inside the logarithm by q θ (y | x): logp(γ = 1| x) =E y∼q θ (y|x) log p(y,γ = 1| x)q θ (y | x) p(y | γ = 1,x)q θ (y | x) . This yields the standard variational decomposition: logp(γ = 1| x) =E y∼q θ (y|x) log p(y,γ = 1| x) q θ (y | x) + D KL q θ (y | x)∥ p(y | γ = 1,x) . Next we expand the joint distributionp(y,γ = 1 | x) = p(γ = 1 | y,x)p LM (y | x)which decomposes further into: logp(γ = 1| x) =E y∼q θ (y|x) [logp(γ = 1| y,x)]−D KL q θ (y | x)∥p LM (y | x) +D KL q θ (y | x)∥p(y | γ = 1,x) . We now plug in the preference model (§ 2) p(γ = 1| y,x) = exp (r(y,x)− max y r(y,x))/β , and note that bothmax y r(y,x)andlogp(γ = 1| x)are constants that depend only onx. Thus we can rewrite the previous identity as c =E y∼q θ (y|x) r(y,x) β − D KL q θ (y | x)∥ p LM (y | x) + D KL q θ (y | x)∥ p(y | γ = 1,x) , for some constant c depending only on x. Rearranging gives c−E y∼q θ (y|x) r(y,x) β + D KL q θ (y | x)∥ p LM (y | x) = D KL q θ (y | x)∥ p(y | γ = 1,x) . Since the left-hand side is exactly c−L(θ,x), minimizing the KL divergence D KL q θ (y | x)∥ p(y | γ = 1,x) 20 Preprint is equivalent to maximizing the RLHF objectiveL(θ,x). Therefore the maximizer in q θ is q θ (y | x) = p(y | γ = 1,x), i.e., the posterior distribution p(y | γ = 1,x) = 1 Z β (x) p LM (y | x) exp (r(y,x)/β). This shows that π β (y | x) is the optimal policy for a single prompt. CQALIGN CONVERGENCE PROOF Letπ β (y | x)be the target distribution, and consider the Metropolis–Hastings chain used by QALIGN with targetπ β and the QUEST proposal kernelq(y | y t ,x). Then the distribution ofy t converges in distribution to π β (y | x) as t→∞. Proof. The theory comes from the standard Metropolis–Hastings (MH; Metropolis et al. (1953)) together with the properties of the proposal distribution introduced in QUEST (Faria et al., 2024). Once we specify (i) the target distributionπ β (y | x)and (i) a valid proposal kernel, the MH theorem ensures that the resulting Markov chain converges to π β in the limit. The central requirement is that the MH transition kernel satisfies detailed balance with respect toπ β : π β (y t | x)T (y t → y) = π β (y | x)T (y → y t ), whereT (· → ·)denotes the one-step transition probability of the chain. For the standard MH acceptance rule, α β (y,y t ) = min 1, π β (y | x)q(y t | y,x) π β (y t | x)q(y | y t ,x) , Metropolis et al. (1953) shows that detailed balance holds automatically for any proposalq(y | y t ,x) that is irreducible and aperiodic. The work of QUEST (Faria et al., 2024) proves that the proposal distribution we use, defined using LLM-based random suffix resampling, is irreducible and aperiodic. An irreducible Markov chain is one that for any two responsesy,y ′ in the support of the LM, the proposal kernelq(y ′ | y,x)has non-zero probability of reachingy ′ fromyin a finite number of proposal steps. In our case, this is ensured by the fact that the proposal mechanism can always select index 0 and regenerate an entire response from scratch. An aperiodic Markov chain is one in which every state is aperiodic (equivalently, every state has period 1). A state is periodic if returns to that state can occur only after numbers of steps that are all multiples of some integer greater than 1, for example only after an even number of steps, or only after multiples of 3. Otherwise, the state is aperiodic, meaning there is no such mandatory multiple. A simple sufficient condition for aperiodicity is that each state has a non-zero probability of returning to itself in one transition (a self-loop). In our setting, this holds because with positive probability we sample index 0 (which occurs with probability1/|y|) and regenerate the entire response, and this regeneration can reproduce the current response with non-zero probability, giving a one-step self-return. Thus, combining detailed balance with irreducibility and aperiodicity, the Markov chain ergodic theorem(Neal, 2011) guarantees that the chain convergence to the optimal aligned distributionπ β in the limit t→∞. DCOMPUTATIONAL COST OF QALIGN As outlined in Faria et al. (2024), when using the suffix proposal distribution from QUEST, each step samples, on average, an index at the midpoint of the sentence from the uniform distribution. Assuming a fixed sentence lengthNfor simplicity, this requires generating only N 2 new tokens on 21 Preprint average per step. With typical transformer-based models, this allows us to reuse the majority of the key-value cache from previous iterations in both the base model and reward model. The reuse extends even beyond half of the computation due to the static prompt. However, unlike when generating independent samples, the computation for each prompt is sequential. We need to first generate the sentencey t before generating the sentencey t+1 . This means that regardless of the compute capability, compared with sampling independent samples, there is always an inherent latency overhead. In summary, for a chain ofTsteps, QALIGN is expected to generate (T+1)N 2 tokens in total:N tokens for the initial hypothesis, plus an average of N 2 tokens for each of the remainingT − 1steps. In comparison, generatingTindependent samples requires decodingT × Ntokens. Therefore, for an equal number of samples, QUEST requires approximately half as many tokens from generation alone than sampling independently, translating to roughly half the FLOPs. EEMPIRICAL OBSERVATIONS ON DISTRIBUTION OF REWARDS When analyzing reward model predictions across independently generated responses from the base model for individual prompts, we consistently observed a bimodal distribution forming a two- component Normal mixture with distinct means and variances (Figure 5). This pattern appeared across the reward models used. Figure 5: Histogram of rewards assigned by TÜLU3-8B-RM to1, 024responses generated by TÜLU3-8B-SFT for9randomly sampled prompts from GSM8K. For each prompt, we fit a two- component Gaussian mixture model to characterize the reward distribution. We suspect this bimodal structure directly relates to the Bradley-Terry training objective, which naturally tries to separate the responses into two clusters (preferred vs. non-preferred). The clusters appear to have a normal distribution most likely because of the central limit theorem, i.e., the predictions result from a neural net that is the sum of billions of random variables. FPROMPTS USED FOR EVALUATION This appendix documents the prompt templates used across different datasets in our experiments. The prompt for GSM8K is only used in the general alignment experiments. The placeholders (text within <...>) are dynamically replaced with specific content from each dataset during the experiments. 22 Preprint F.1GSM8K DATASET Solve the following grade school math problem step-by-step: <question> F.2MATH-500 DATASET Solve the following math problem step-by-step: <question> Present the answer in LaTex format: Your answer F.3MULTIPLE CHOICE DATASETS (TQA, MMLU) Choose the correct answer to the following multiple-choice question about <subject>. Question: <question> A). <choice_A> B). <choice_B> C). <choice_C> D). <choice_D> Provide your reasoning about the answer and finish your answer with the letter corresponding to the correct option (e.g., A, B, C, or D). 23 Preprint GFULL GENERAL ALIGNMENT PLOTS Figure 6 plots the average error rate across all of the datasets as a function of the floating point operations (FLOPS). 2 1 2 1 2 3 2 5 2 7 2 9 Inference FLOPS per question (×10 12.79 ) 0.500 0.525 0.550 0.575 0.600 0.625 0.650 0.675 TQA Test Error SFT-BoN SFT-MV SFT-WMV DPO-MV SFT-QAlign 2 1 2 3 2 5 2 7 2 9 2 11 Inference FLOPS per question (×10 12.79 ) 0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 MATH Test Error SFT-BoN SFT-MV SFT-WMV DPO-MV SFT-QAlign 2 0 2 2 2 4 2 6 2 8 2 10 Inference FLOPS per question (×10 12.79 ) 0.15 0.20 0.25 0.30 0.35 0.40 GSM Test Error SFT-BoN SFT-MV SFT-WMV DPO-MV SFT-QAlign 2 0 2 2 2 4 2 6 2 8 2 10 Inference FLOPS per question (×10 12.79 ) 0.25 0.30 0.35 0.40 0.45 0.50 IFEVAL Test Error SFT-BoN SFT-MV SFT-WMV DPO-MV SFT-QAlign 2 1 2 1 2 3 2 5 2 7 2 9 Inference FLOPS per question (×10 12.79 ) 0.375 0.400 0.425 0.450 0.475 0.500 0.525 0.550 0.575 MMLU Test Error Inference Scaling of Quest-RLHF SFT-BoN SFT-MV SFT-WMV DPO-MV SFT-QAlign Figure 6: Error rate across multiple evaluation datasets (GSM8K, MATH500, MMLU-Redux, TruthfulQA, and IFEval) as a function of the floating point operations (FLOPS) in log scale. We compare • QALIGN with TÜLU3-8B-SFT against four baselines:▲majority vote (MV) TÜLU3- 8B-DPO, and applied to TÜLU3-8B-SFT the methods • best-of-n(BoN), • MV, and • weighted MV (WMV) . All experiments use temperature 1.0 with reasoning included in model outputs. Note that TÜLU3-8B-DPO model is the result of doing preference finetuning on the TÜLU3-8B-SFT with 271k preference pairs. The costs associated with this process are not accounted for in this plot.[GF: change plot ] HREWARD MODEL TRAINING CONFIGURATION We trained a Bradley & Terry (1952) reward model using LLAMA-3.1-8B-INSTRUCT (Llama, 2024) as the base model on a preference dataset for mathematical reasoning. The dataset contained 64 model-generated responses per prompt from GSM8K (Cobbe et al., 2021) (on-policy data from LLAMA-3.1-8B-INSTRUCT), from which we constructed one preference pair per prompt by selecting one ground truth correct answer as preferred and one incorrect answer as dispreferred. Training hyperparameters are detailed in Table 2. 24 Preprint Table 2: Training Hyperparameters for the RM for the task-specific experiments. ParameterValue Model Configuration Fine-tuning TypeFull Chat Templatellama3 Dataset Validation Split5% Optimization Learning Rate1× 10 −5 Total Batch Size128 Training Epochs1.0 LR SchedulerLinear Decay Warmup Ratio0.03 Weight Decay0.0 Precisionbfloat16 Infrastructure Optimization FrameworkDeepSpeed ZeRO Stage 3 GPUS8 L40S 25