Optimal Aggregation of LLM and PRM Signals for Efficient Test-Time Scaling

1. Problem Statement

Test-Time Scaling (TTS) is a paradigm designed to improve Large Language Model (LLM) reasoning by generating multiple candidate solutions and selecting the best one, rather than retraining the model. A common strategy, Best-of-N (BoN), uses a Process Reward Model (PRM) to score reasoning steps and select the highest-scoring response.

However, recent benchmarks reveal a counter-intuitive paradox: Simple Majority Voting (MV) (ignoring PRM scores entirely) often outperforms PRM-guided BoN. This suggests that current methods fail to effectively integrate the nuanced verification signals from PRMs. The core problem is: How can we optimally aggregate signals from both the LLM (generations) and the PRM (scores) to maximize TTS efficiency and accuracy?

2. Methodology

A. Theoretical Framework (MAP Estimation)

The authors formalize the aggregation task as a Maximum a Posteriori (MAP) estimation problem.

• Goal: Find the answer $\alpha_k$ that maximizes $P(\alpha_k | G, P, M, V)$, where $G$ are generations, $P$ are PRM scores, $M$ is the LLM, and $V$ is the PRM.
• Derivation: Under assumptions of conditional independence between generations and PRM scores, the optimal strategy is derived as a Weighted Majority Vote.
• The Optimal Weight ($w_i$): The weight for each response is not just the PRM score, but a sum of two components:
  1. PRM Signal Term: The log-likelihood ratio of the PRM score given the response is correct vs. incorrect ($\log \frac{P(p|c=1)}{P(p|c=0)}$).
  2. LLM Signal Term: A term derived from the LLM's intrinsic reliability ($q_M$) and the number of candidate answers.
  • Key Insight: The optimal weight function is non-linear and model-dependent. Crucially, it often assigns negative weights to low PRM scores, meaning a low score should actively penalize an answer, not just be ignored.

B. Empirical Analysis & Calibration

The authors empirically analyze the optimal weighting function $w^*(p)$ and find:

1. Model Dependence: The shape of the optimal function varies significantly across different LLM-PRM pairs. A fixed function (e.g., using raw PRM scores) is suboptimal.
2. Negative Weights: Optimal functions consistently map low PRM scores to negative weights. Standard methods like BoN (selecting max score) or MV (ignoring scores) fail to utilize this "negative evidence."

To address this, they propose Practical Calibration Methods using a small, one-time pre-computed dataset ($D_{cal}$):

• Non-Parametric Approach (KDE WV): Uses Kernel Density Estimation (KDE) in logit space to estimate the score distributions $P(p|c=1)$ and $P(p|c=0)$, then computes weights via the log-ratio.
• Parametric Approaches:
  • Logit Weighted Voting (Logit WV): $w(p) = \text{logit}(p) - \text{logit}(b)$.
  • Linear Weighted Voting (Linear WV): $w(p) = p - b$.
  • Both methods introduce a threshold parameter $b$ (calibrated via grid search) to enforce the zero-crossing point, ensuring low scores receive negative weights.

3. Key Contributions

1. Theoretical Framework: Established that the optimal aggregation of LLM and PRM signals is a weighted majority vote, not a simple selection of the highest score.
2. Discovery of Negative Weights: Identified that optimal strategies require assigning negative weights to low-quality responses, a signal neglected by existing methods.
3. Calibration Methods: Proposed efficient pre-computation methods (KDE and Parametric) to learn model-specific weighting functions without needing ground truth at test time.
4. Efficiency Gains: Demonstrated that intelligent aggregation can outperform brute-force scaling with significantly less computational cost.

4. Experimental Results

The methods were evaluated across 5 LLMs (Mistral, Qwen, DeepSeek) and 7 PRMs on the MATH and MATH500 datasets, as well as the MMLU-Pro-CoT-Eval dataset.

• Performance vs. Efficiency:
  • The proposed Logit Weighted Voting (Logit WV) consistently outperformed baselines (BoN, Majority Vote, Vanilla Weighted Vote).
  • Computational Savings: Logit WV achieved higher accuracy than the best baseline (Vanilla WV) while using only 21.3% (on MATH500) and 37.1% (on MATH) of the test-time computation.
• Ablation & Analysis:
  • Negative Weights: Grid search results confirmed that the optimal threshold $b$ is consistently $>0$, validating the necessity of negative weights.
  • Generalization: The calibrated methods showed strong transferability to out-of-domain tasks (e.g., Physics, Law, History) and different model pairs.
  • Parametric vs. Non-Parametric: Parametric methods (Logit/Linear WV) generally outperformed the non-parametric KDE approach, likely because estimating the LLM reliability term ($q_M$) per question is difficult, and parametric models generalize better with limited calibration data.

5. Significance

This work challenges the prevailing assumption that "more compute" (scaling $N$ in BoN) is the only path to better TTS performance. Instead, it argues that intelligent aggregation is a more efficient lever. By theoretically proving and empirically validating the need for model-specific, negative-weighted aggregation, the paper provides a blueprint for:

• Drastically reducing the inference cost of high-reasoning tasks.
• Better utilizing expensive Process Reward Models that were previously underperforming due to naive selection strategies.
• Shifting the focus from scaling compute to scaling the intelligence of the selection mechanism.

In summary, the paper demonstrates that investing in a calibrated aggregation strategy yields superior performance gains compared to simply scaling test-time computation.