Reward Model Generalization for Compute-Aware Test-Time Reasoning
Zeen Song, Wenwen Qiang, Siyu Zhao, Changwen Zheng, Gang Hua · 2025
Read Reward Model Generalization for Compute-Aware Test-Time Reasoning by Zeen Song, Wenwen Qiang, Siyu Zhao, Changwen Zheng, Gang Hua (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18065.txt.
Introduction
Zeen Song and co-authors ask how well the judge of a word model's work holds up when compute is tight in a 2025 paper. At use time, the model drafts many paths and a judge scores them, so the best path wins. The prize is the most right answers for a fixed spend.
Math in a learn-from-data frame ties the judge's error rate to how many drafts a right answer needs. A tree search scheme then steers the spend: one part sets draft knobs from score spread, the other grades their worth. On math test sets, the scheme beat rival ways across models and judges.
Catalog record
| CREATOR | Zeen Song, Wenwen Qiang, Siyu Zhao, Changwen Zheng, Gang Hua |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-18065
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reward Model Generalization for Compute-Aware Test-Time Reasoning Zeen Song, Wenwen Qiang, Siyu Zhao, Changwen Zheng, Gang Hua Abstract External test-time reasoning enhances large language models (LLMs) by decoupling generation and selection. At inference time, the model generates multiple reasoning paths, and an auxiliary process reward model (PRM) is used to score and select the best one. A central challenge in this setting is test-time compute optimality (TCO), i.e., how to maximize answer accuracy under a fixed inference budget. In this work, we establish a theoretical framework to analyze how the generalization error of the PRM affects compute efficiency and reasoning performance. Leveraging PAC-Bayes theory, we derive generalization bounds and show that a lower generalization error of PRM leads to fewer samples required to find correct answers. Motivated by this analysis, we propose Compute-Aware Tree Search (CATS), an actor-critic framework that dynamically controls search behavior. The actor outputs sampling hyperparameters based on reward distributions and sparsity statistics, while the critic estimates their utility to guide budget allocation. Experiments on the MATH and AIME benchmarks with various LLMs and PRMs demonstrate that CATS consistently outperforms other external TTS methods, validating our theoretical predictions. 1 Introduction In recent years, chain-of-thought (CoT) prompting has substantially improved the performance of large language models (LLMs) on complex reasoning tasks such as math problem solving, question answering, and multi-hop retrieval [ 1 , 2 , 3 ] . To support more effective CoT reasoning, recent works have explored test-time scaling (TTS) strategies that allocate more compute during inference [ 4 , 5 , 6 , 7 , 8 , 9 ] . These approaches can be broadly divided into internal and external ones, with external methods attracting increasing attention due to their flexibility and ability to enhance performance without modifying the base model [ 7 , 8 , 9 ] . The external TTS framework typically consists of three components: a frozen policy model, a scaling algorithm, and a process reward model (PRM). It generates multiple candidate reasoning paths using the policy model guided by the scaling algorithm (e.g., Best-of-N or Beam Search), and reranks these paths using the PRM to select the most promising one [ 3 , 10 ] . A central challenge in this setting is test-time compute optimality (TCO), which aims to select the optimal hyperparameters that maximize answer accuracy with a fixed policy model and given compute budget [ 7 , 8 , 11 ] . Empirical studies suggest that among these components, the PRM often plays a critical role in determining TCO performance [ 8 ] . However, most PRMs are trained via supervised learning on limited datasets [ 12 , 13 ] , and their ability to generalize to unseen reasoning paths significantly affects the accuracy of path selection. Despite their growing importance, the effects of the generalization error of PRM on downstream reasoning performance remain underexplored. To systematically characterize the role of PRMs in achieving TCO, we propose a unified theoretical framework. We first show that the generalization error of the PRM is upper-bounded via PAC-Bayesian analysis. Then, we establish the relationship between the generalization error, the final answer accuracy, and the available computing budget. One of our key insights is to quantify the risk of mis-ranking candidate reasoning paths due to generalization error. Our analysis shows that the answer accuracy of external TTS is lower-bounded by three components: (i) the probability that the policy model generates a correct answer, (ii) the reward gap between the selected path and the discarded ones, and (iii) the upper bound of the generalization error. While our theoretical framework provides a target for optimizing inference-time accuracy, it also reveals two key practical challenges. First, the generalization error of the PRM significantly affects answer accuracy under a fixed compute budget, yet it is unobservable at test time. Second, although the reward gap can be influenced by tuning sampling parameters such as top- k , top- p , and temperature, its effect varies across different PRMs. To address these challenges, we use parameter sparsity as a proxy for the generalization error of the PRM and propose Compute-Aware Tree Search (CATS), a dynamic reasoning control strategy based on the Advantage Actor-Critic (A2C) framework. CATS formulates the inference process as a Markov Decision Process (MDP) and controls the search configuration by learning an actor network. At each step, the actor network outputs a search configuration based on candidate rewards and model sparsity, while the critic estimates the value of the current state via a temporal-difference (TD) objective. By jointly training on multiple PRMs, CATS learns to adaptively adjust the number and selection of candidate reasoning paths, effectively improving the answer accuracy under limited compute. To validate our theoretical analysis and the effectiveness of the proposed CATS strategy, we conduct extensive experiments on two challenging mathematical reasoning benchmarks: MATH500 [ 14 , 12 ] and AIME24 [ 15 ] . We evaluate CATS under multiple frozen policy models, including Qwen 2.5 [ 16 ] , Llama 3.1 [ 17 ] , and Llama 3.2 [ 18 ] , and incorporate a diverse set of PRMs [ 19 , 13 , 20 , 21 ] . The results demonstrate that CATS consistently achieves higher accuracy than other external TTS methods across different model combinations and compute budgets. These results provide strong empirical support for our theoretical predictions. Our contributions can be summarized as follows: • We present a unified theoretical framework that establishes a quantitative relationship between the generalization error of the PRM, compute budget, and answer accuracy in external TTS. By analyzing the risk of mis-ranking candidate reasoning paths, we derive an explicit lower bound on answer accuracy in terms of the reward gap, sampling coverage, and the generalization error. • Motivated by our theoretical analysis, we propose CATS, a reasoning control strategy based on the A2C framework. CATS dynamically allocates compute across inference steps by adjusting path selection and generation parameters, using sparsity as a proxy signal for the generalization error of PRM. • We evaluate CATS across diverse challenging reasoning benchmarks, different policy models, and several PRMs. Results show that CATS consistently improves accuracy across all settings, validating our theoretical predictions. 2 Related Works Scaling of Test-time Compute . CoT prompting is first proposed as a prompting technique that enables LLMs to decompose problems into intermediate steps [ 1 ] . Recently, the OpenAI o1 series [ 4 ] demonstrate that increasing the length of CoT during inference yields substantial performance gains on tasks like MATH [ 14 ] and AIME [ 15 ] . TTS approaches can be broadly categorized into internal and external methods [ 7 , 8 , 22 ] . Internal TTS encourages models to extend CoT reasoning via supervised fine-tuning (SFT) or reinforcement learning (RL). Some methods construct training data to promote step-wise self-refinement [ 23 , 24 ] . DeepSeek-R1 [ 5 ] combines formatting-based and rule-based rewards, and optimizes the model using GRPO [ 25 ] . In contrast, external TTS improves the reasoning performance via sampling or search-based methods with fixed LLMs and an external verifier [ 12 , 9 , 7 , 3 , 26 , 10 , 27 , 28 ] . Specifically, Tree - of