B-STaR: Monitoring and Balancing Exploration and Exploitation in Self-Taught Reasoners
Authors: Weihao Zeng
Yuzhen Huang
Lulu Zhao
Yijun Wang
Zifei Shan
Junxian He
Venue: ICLR 2025 Poster (2025)
Keywords: large language models
self-improvement
complex reasoning
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: In the absence of extensive human-annotated data for complex reasoning tasks, self-improvement -- where models are trained on their own outputs -- has emerged as a primary method for enhancing performance. Recently, the approach to self-improvement has shifted toward a more dynamic, online fashion through iterative training processes. However, the critical factors underlying the mechanism of these self-improving methods remain poorly understood, such as under what conditions self-improvement is effective, and what are the bottlenecks in the current iterations.
In this work, we identify and propose methods to monitor two pivotal factors in this iterative process: (1) the model's ability to explore and generate high-quality responses among multiple candidates (exploration); and (2) the reliability of external rewards in selecting the best responses from the generated outputs (exploitation).
These factors are inherently moving targets throughout the self-improvement cycles, yet their dynamics are rarely discussed in prior research -- It remains unclear what impedes continual model enhancement after only a few iterations. 
Using mathematical reasoning as a case study, we begin with a quantitative analysis to track the dynamics of exploration and exploitation, discovering that a model's exploratory capabilities rapidly deteriorate over iterations, and the effectiveness of exploiting external rewards diminishes as well due to shifts in distribution from the original policy.
Motivated by these findings, we introduce B-STaR, a Self-Taught Reasoning framework that autonomously adjusts configurations across iterations to Balance exploration and exploitation, thereby optimizing the self-teaching effectiveness based on the current policy model and available rewards.
Our experiments in mathematical reasoning demonstrate that B-STaR not only enhances the model's exploratory capabilities throughout training but also achieves a more effective balance between exploration and exploitation, leading to superior performance. Crucially, this work deconstructs the opaque nature of self-training algorithms, elucidating the interpretable dynamics throughout the process and highlighting current limitations for future research to address.

Published as a conference paper at ICLR 2025
B-STAR: MONITORING AND BALANCING EXPLORATION AND EXPLOITATION IN SELF-TAUGHT REASONERS
Weihao Zeng"! Yuzhen Huang" Lulu Zhao² Yijun Wang
Zifei Shan
Junxian He
The Hong Kong University of Science and Technology (wzengak, yhuanghi, junxi anh) @cse.ust.hle .st.
2BAA
Tencent
ABSTRACT
In the absence of extensive human-annotated data for complex reasoning tasks, self-improvement- where models are trained on their own outputs - has emerged primary method for enhancing performance. Recently, the approach to self- improvement has shifted toward a more dynamic, online fashion through iterative training. However, the critical factors underlying the mechanism of these iterative self-improving methods remain poorly understood, such as under what conditions self- seff-improvementt is effective, and what the bottlenecks in the current iterations. In this work, we identify and propose methods to monitor two pivotal factors in this iterative process: (1) the model's ability generate sufficiently diverse responses (exploration); and (2) the effectiveness of external rewards in distinguish- ing high-quality candidates from lower-quality ones (exploitation). These factors are inherently dynamic throughout the iterative process, yet prior research rarely discusses their evolution - leaving unclear why models often stagnate after only a few iterations. Using mathematical reasoning as case study, we begin with a quantitative analysis to track the dynamics of exploration and exploitation, dis- covering that model's exploratory capabilities rapidly deteriorate over iterations, and the effectiveness of exploiting external rewards diminishes as well. Motivated by these findings, introduce B-STAR, Telfht Reasoning framework that autonomously adjusts configurations across iterations to Balance exploration and exploitation, thereby optimizing the self-improving effectiveness based the current policy model and available rewards. Our experiments on mathematical reasoning, coding, and commonsense reasoning demonstrate that B-STAR not only enhances the model's exploratory capabilities throughout training but also achieves a more effective balance between exploration and exploitation, leading to superior performance. Crucially, this work deconstructs the opaque nature of self- trainini algorithms, providing interpretable insights into their dynamics and highlighting current limitations to guide future research
INTRODUCTION
Large language models possess advanced reasoning capabilities such mathematical problem- solving (Cobbe et al.) 202T), coding challenges (Chen et al., (02T) or commonsense reasoning (Clark et al.) 2018). However, the challenge of acquiring extensive, high-quality human-curated datasets remains a significant barrier to further enhancing these reasoning abilities. As tasks grow in complexity, the reliance on Human-genneatee data becomes increasingly unsustainable, necessitating alternative approaches to training.
To tackle this issue, methods rooted in the concept of "self ispro-improveemet" (Huang et al. 2022). such as STaR (Zelikman et al. 2022), RFT (Yuan et al. (003), and ReST (Gulcchre et al. 2023 Singh et al. 2023), provide cost-effective and scalable solutions. Seff-improvement follows an iterative process where the model generates responses, from which the better are selected to create
"Equal Contribution.
We open-source our code http:://ghthhh..oommhttsssssssaa

---

Published as a conference paper at ICLR 2025
17-
23
SFT
SFT
SFT
SFT
1i RIT
Octre
OrEnc
Orlnn MPT
STAVISTT-
100
2000
1000
4200
2006 201
3001
2003
210
61
602
600
100
100
200
270
(a) GSM8K
(b) MATH
(c) APPS
(d) ARC-C
Figure 1: Pass accuracy over training steps on GSM8K, MATH, APPS, and ARC-Challenge. The GSM8K, MATH, and ARC-C results are from Mistral-7B, while the APPS scores are obtained based on Llama3-8B We compare multiple baselines. including SFT. Online RFT. STaR/ReST-EM, and Iterative RFT, against our proposed B- B-STAR. For further details on the experimental settings, please refer $4.1
higher-quality data for further refinement (Hosseini et al. 2024 This continuous loop allows the model to improve its performance data. Ultimately, this approach enhances the model's ability to handle complex reasoning tasks, pushing the limits of its capabilities (Havrilla al. 2024).
time, reducing the need for large amounts of human-generated
Despite significant advancements, we still lack a deep understanding of the key factors that drive successful improimmpeeeeeet and the internal optimization mechanisms remain largely opaque. Un- derstanding the critical components and bottlenecks of these self- ceff-imrrovnng methods is particularly important given that performance of current self-improving approaches does not scale well with increased compute and saturates very quickly after merely 3 to 5 iterations (Singh et al.) 20233 Wu (ct al. 2024). In this paper, we address the following questions: (1) What key factors play decisive role in the self-improvement process? (2) How can these factors be used to analyze the limitations of current self-improvement methods from a unified perspective? and (3) How can we leverage these factors to guide the self- ceff-improveeentt process, ultimately maximizing performance gains?
To this end, we identify two crucial capabilities of the model during its self inlfffemroveenttt process: (1) Exploration - the model's 's ability to generate correct and diverse responses among multiple generated candidates (Singh et al. 2023 Wang et al. 2024a), and (2) Exploitation - the effectiveness of external rewards (e.g., reward model final answer supervision) in selecting high-quality solutions from these candidates (Wang et al., 2024b Sun et al., 2024). Intuitively, these two factors are dynamic, evolving throughout the training process, phenomenon that remains underexplored despite its critical importance. In this work, we first conduct empirical analysis to quantitatively monitor the dynamics of exploration and exploitation during iterative training processes. We observe that both capabilities may stagnate or even decline, and imbalances between them can hinder the model's ongoing improvement.
Motivated by these insights, we propose novel approach for self- eef-iimprovement that automatically monitors and balances these dynamic factors optimize the use the current policy and reward. This involves adjusting configurations that influence exploration and exploitation, such sampling temperature and reward thresholds. These configurations are adaptively modified throughout training in terms of our proposed metric, balance score. This new metric assesses the potential of query based on the current model's 's exploration and exploitation capabilities, and our method automatically balances exploration and exploitation behaviors maximize the average balance scores. We refer to this method as B-STAR, a Balanced Self-Taught Reasoner.
The experimental results from mathematical mroblem-solving coding challenges and commonsense reasoning demonstrate that B-STAR significantly surpasses other self-improvement methods through balanced exploration and exploitation. For instance, B-STAR achieves significant improvement in @ass@1 I on both GSM8K and MATH, surpassing various self-improving variants while maintaining steady upward trajectory, as depicted in Figure Furthermore, we demonstrate that exploration- related metrics, such as Pass @ 32, are continuously improving without any notable degradation.
2

---

Published as a conference paper at ICLR 2025
Balanced Configurations
Pi
ti
Ti
Exploration
Exploitation
Improve
y rl > ye <Ti
Di
Pi-1
RM
Pi
Figure Illustration of the B-STAR approach. In each iteration, first identify the configurations temperature and reward threshold 7. that maximize the average balance scores using small subset of training queries. Next, we apply the optimal temperature and threshold to generate and reward the full set of training queries. Finally, we update the model based on the selected data.
2
MONITORING EXPLORATION AND EXPLOITATION IN SELF-IMPROVENT
2.1
BACKGROUND: BELF-IMPROVEMEN
Given a pre-trained model Po and training set D == (x;, where denotes the training query and y/ represents the response, the goal of self-immproeement to iteratively generate high- quality responses from the current model and update the model with these gelf-geeerated data. Let T represent the total number of iterations, with the model at the start of the t-th iteration denoted as Pt-1. In the first iteration, Po is typically fine-tuned the initial dataset D, then each subsequent iteration involves three critical steps generally (Yuan et al. 2023 Gulcehre et al. 2023):
(1) Generating (Sampling): For each query Ty,, the model P generates K candidate responses, forming new, self-generated dataset.
(2) Rewarding (Verifying): A reward function r(x; y) is applied score and select the high-quality responses from the self-generated dataset. This reward can be binary and utilize additional supervision, for example, in problem-solving tasks in the math and code domains, is common use the final answer matching or the result of passing unit tests as binary feedback (Yuan et al., 2023 Chen et al. 2022). In a more sophisticated case, r(x, y) can be parameterized by a reward model outputting continuous scores, using outcome-bart based reward models (ORMs) (Li et al. (022) or process-basee based
reward models (PRMs) (Uesato et al. 2022 Lightman al. 2023 Havrilla et al. 2024).
(3) Improving: The selected dataset is used to update P:-1, producing Pt. To differentiate the generation model M from the reward model, is also referred to as the policy model following RL literature. In reasoning tasks that we are going to focus on, SFT loss is commonly used in the Improving step due to its robustness and scalability (Pang et al. 2024 Dubey et al. 2024), ) as more sophisticated RL losses Rewarding step aims to reject low-quality responses and use remaining high-quality data for training. thus this process is also referred to rejection fine-tuning (RFT, Yuan et al. (2023)). In Appendix C we provide detailed explanations of self-improvement, including reward functions and RFT.
be unstable to optimize and scale up. When SFT loss is adopted, the
Discussion on Online Learning. The iterative procedure described above can be contextualized within the reinforcement learning framework (Singh et al. 2023), and the iterative design shifts the vanilla offline training towards more dynamic online variant when iteration intervals are short and the optimizer is inherited between iterations, the training essentially transforms into fully online learning algorithm. Iterative RFT implementations in previous works typically adopt long iteration intervals where each iteration processes all available queries (Zelikman al. 2022 Sun et al. 2024). Sometimes, these implementations opted to restart the training from the initial checkpoint rather than from the last saved model (Zeikman et al. 2022: Singh et al. 2023). ) However, starting from the beginning is not scalable for large datasets, particularly in a streaming setting, instead, continuous training approach more aligned with RL principles is preferable. Transitioning from offline to online training, online RFT (Shao et al., 22024) has demonstrated its superiority over traditional offline RFT methods by switching iterations more frequently, ensuring that the synthetic data remains on policy. In this study, we explore online RFT as our primary framework.
argue that always
3

---

Published as a conference paper at ICLR 2025
2.2 THE CRITICAL FACTORS- EXPLORATION AND EXPLOITATION
To maximize the gains from self-improvement training and fundamentally enhance the model's ability using its own outputs, the key is achieve scalable self-improvement training, where the model's performance scales with increased computational investment in the training algorithm. However, all previous works show quick saturation after merely 3-5 self relf-improvement iterations (Singh et al. [023] Wu et al. 2024). hypothesizing that the model's ' own outputs can only lead to limited gains. In this work, we seek to dive deeper into the currently opaque process of ieff-improveeent, to understand the critical factors that determine whether self-imprrvement succeeds or fails.
Intuitively, for a certain iteration of training, we argue that two high-level conditions must be met for the model to make progresses: (1) Diverse Exploration for High-Que Quality Responses: When multiple candidates are sampled from the model, a portion of them must be high-quality responses. This is particularly important for queries where the model fails to produce satisfactory outputs using greedy decoding. Such diversity enables the discovery of responses that cannot be reached through greedy decoding. (2) Effective Reward Function Discrimination: The reward function r(z, y) must reliably distinguish high-quality candidates from lower-qualin ones. We refer to the two conditions as exploration and exploitation respectively, and provide their analogies to RL in Appendix G If either of these conditions is unmet such as when the model produces responses overly similar (i.e. lack of diversity), or when the reward function fails to identify high-quality responses the self-improvement will be limited on the gains.
Exploration and Exploitation are Moving Targets. Both exploration and exploitation are dy- namically influenced by the policy model during the self-improvement process. On one hand, after multiple iterations, the policy model may overfit the task, failing to explore diverse responses and instead generating highly similar outputs (i.e., lack of exploration). Training similar responses is unlikely to yield significant improvements. On the other hand, if the model generates excessively diverse responses, resulting in distribution that deviates significantly from the training data distribution of the reward model, it becomes challenging for the reward model to reliably distinguish high-quality responses (i.e., lack of exploitation). Thus, maintaining a dynamic balance between exploration and exploitation is essential throughout the self-improving process. However, such dynamics are rarely discussed in prior research, Next, we propose methods to quantify exploration and exploitation, enabling us to monitor their dynamics during training and deepen our understanding of the mechanisms underlying self infroipproeettt.
these highly
Quantifying Exploration and Exploitation. In this work, we mainly focus on complex problem- solving tasks such as math and coding domains, where the correctness of the responses can be easily verified labeled datasets This property facilitates the quantification of exploration and exploitation, for which we detail the metrics below:
Exploration: Pass@K, K, which measures whether there is least one correct response during K sampled candidates, is straightforward metric for assessing exploration, as it directly reflects whether the model is able to explore correct solutions. However, Pass @ K can be noisy, as it only counts single correct response, while it is desirable to assess whether the model can explore multiple correct response as well. To this end, we propose to track Pass @ K-S as well, which measures whether there are at least S unique correct responses among K sampled candidates.
Pass K-S serves as a more stable proxy to exploration than Pass @ K. Pass @ K is essentially Pass@ K-1 following such a definition. Besides Pass@ K and Pass K-S, we also track diversity of the generations using Distinct Equations proposed by Wu et al. (2024), which measures the proportion of unique equations among all correct generated responses.
Best-of-K accuracy measures whether the top one response ranked by the reward function is correct, directly reflecting how well the reward can potentially select a good response. Since it is typically required to select multiple responses rather than one in self-improving training, we are interested in the reward's 's exploitation to select multiple responses as well. To this end, we come up with the Reward @ K-S metric. which measures whether the top S candidates ranked by the reward are all correct or not. Best-of-K accuracy is special case of Reward @ K-S when S
Exploitation:
"Strictly speaking, the response may contain incorrect steps even though the final answer is correct, we do further distinguish this difference following others (Zelikman et al. 2022) it not the focus of this work.
4

---

Published as a conference paper at ICLR 2025
23
50
22
21
45
20
19
18
17
Answer
Answer
knaw lid (030-2
16
Arower+ 1910
AnswarrPPP
Kiame (200)-2
1000
2000
3000
4000
1000
2000
4000
(a) P on MATH
(b) Diversity on MATH
(c) Kass@K-S on MATH (d) Reward@ MATH
Figure 3: Pass@1 I, Diversity, Pass@K-S and Reward@K-S K-S over training steps on MATH. SFT refers to direct fine-tuning using the original dataset, "Answer" indicates matching against the ground-truth final answer, and "Answer PRM" combines ground-truth final answer matching with PRM reward.
is equal 1. One might think that Reward K-S would be equivalent Pass @ K-S if only the final answer used to select responses, potentially making Reward @ K-S less useful in such cases. However, we emphasize that the exploitation metries are mainly used to measure the effectiveness when additional reward models are integrated, as we will show next in $2.3 3 that our reward function combines final answer supervision and reward model.
Next, we conduct case study to dive into self-improving training through tracking these metrics.
2.3 DYNAMICS OF EXPLORATION AND EXPLOITATION A CASE STUDY IN MATHEMATICAL PROBLEM SOLVING
In this section, we perform mathematical reasoning task. Specifically, we follow Singh et al. (2023) to adopt MATH (Hendrycks) al. 202T) training as the training data, evaluating on the test split of MATH. We also conduct evaluation on the test split of GSM8K, with experimental results shown in the Appendix A.2
study analyze the dynamics of exploration and exploitation in
Setup. As introduced in 2.1 we adopt the online RFT training framework in our implementation. We use Mistral-7B (Jiang et al. 2023) our base model. We run the SFT baseline on MATH for 3 epochs, and use the checkpoint at the first epoch as the initial checkpoint to run self-improving training. We experiment with two different types of reward functions:
Answer: we just match the predicted answer with the ground-truth final answer and keep the responses with correct answers, following (Singh al., 2023):
= (a a²),
Answer + PRM: we train a process reward model (PRM) using the approach in Wang et al. (2024b) based on Mistral-7B. Then we combine the final answer reward and the PRM reward as:
( a²) + Tprm (x, ú),
where à, a" are the predicted answer and the ground-trui answer respectively, 1()) is the indicator function, is the predicted solution. Tprm (-) is the PRM score. Since PRM is designed to score every step of the solution, we choose the minimal score across all steps as the score for the entire solution, following Lightman al. (2023). We only keep responses with and is a threshold. We found 7 is a good hyperparameter in our early trials with different thresholds, thus we keep
train the model,
in all the experiments dynamics analysis.
We train all methods for 4500 training steps. For our online RFT, we adopt an iteration interval of 500 steps, resulting total of iterations significantly higher than the typical 3-5 iterations reported in prior work (Singh et al. 2023). We sample 32 candidate solutions per query during training with temperature of 1.0. We include the SFT baselines, which are trained for 3 epochs on MATH. Please see Appendix A. for more setup details.
Observation 1: Exploration decreases over training, and PRM helps retain the exploration ability. As demonstrated in Figure 3(a) the seff-improvement method significantly outperforms
5

---

Published as a conference paper at ICLR 2025
SFT in enhancing the model's ability generate accurate responses through greedy decoding. However, for both methods, the performance improvements diminish over time as the number of iterations increases. From Figure 3(b) the diversity metric decreases dramatically, similar phenomenon is observed in WW et al. (2024). Notably, the Answer+PRM reward is able to overcome the declining trend and retain exploration. We hypothesize that filtering responses solely based on answer correctness often results in homogeneous reasoning paths, whereas the fine-grained reward strategy encourages the selection of high-quality paths, thereby preserving diversity. Examining the Pass @ K-S metrics in Figure 3(c) Pass Tas@@-S K-S initially increases, indicating an improvement in model exploration. However, Pass K-S subsequently declines, with Pass @ K- accuracy falling close to the SFT baseline. The plateau pattern of exploration is not good sign, as it suggests that the model may not learn new things to explore better. Since the reward model remains fixed during training, the model's is ability stagnates once exploration halts.
Observation 2: Exploitation keeps improving on MATH. As shown in Figure 3(d) we observe Reward @ K-S continues to improve on MATH, potentially because are training with the MATH dataset. Since our our reward remains fixed during training, the exploitation performance closely related to exploration of the policy model, which is moving target discussed in 22. However, as shown in our previous analysis, the model's 's exploration does not continually improve in all cases. We hypothesize that this is the key factor that bottlenecks self-improving training. Exploration is related to configurations such as how we sample responses from the model, how many samples to draw. Similarly, exploitation depends on how we utilize the reward to select responses. While all previous works have treated these configurations as static during training, as far as we know, the question arises: Can we adjust them dynamically to better align exploration and exploitation? We investigate this question next.
3 B-STAR BALANCED SELF-TAUGHT REASONERS
In this section, we firstly introduce metric to evaluate the interplay effect between exploration and exploitation. Next, we analyze its relationship with different configurations. Finally, we present our complete algorithm, which automatically adjusts the exploration and exploitation abilities.
3.1 BALANCE SCORE
highlights the importance of a model's exploration and exploitation capabilities for self- improvement, emphasizing their continuous evolution during training. Now we seek a metric that could capture the interplay of these two factors. Intuitively, we hope the model can explore a diverse range of high-quality responses and with the reward function distinguishing between them. Specifically, given a query, two conditions to be satisfied for the selected responses to effectively contribute to training: (1) substantial absolute number of high-quality responses, and (2) a high proportion of high-quality responses among the selected ones. The first condition ensures there sufficient quantity of high-quality data for training, while the second prioritizes maintaining high proportion of good responses to prevent contamination of the training set with low-quality data. For example, selecting only two correct responses may result in a perfect 100% quality ratio but provide insufficient data for training. Conversely, selecting all 64 candidates of which 16 are correct- - yields a higher absolute number of high-quality responses but lowers the quality ratio to 25%, introducing too many incorrect responses into the training process. Therefore, these two capture different aspects of the data. Following these two intuitions, we propose a metric, balance score, to measure the balance effect or in other words, the overall contribution of the synthetic data given the exploration- and exploitation-related configurations. We detail it below.
For each query F;, let n; represent the total number of selected responses for it, and n' denote the number of unique, correct responses among them, then the balance score is defined as follows:
T2 T
n2
bs:
min
where (3,, 1) is discount factor that encourages the number of correct solutions to be larger than a pre-specified parameter n* there no discount when we have more than n' correct responses. We impose cap of 1, rather than encouraging ni to be as large as possible, because otherwise the

---

Published as a conference paper at ICLR 2025
1.0
0.2
0.7
11
0.8
0.1
0.6
0.6
0.0
0.4
-0.1
# Sample
0.2
Sample
Sample
Sample
500 1000
1500 2000
2500
500
1000
1500 2000
2500
1000
1300
2000
2500
(a) Best Temperature
(b) Best Threshold
(c) Sample Size
Figure 4: Left: the best sampling temperature achieve the average balance scores different training steps: Middle: the best reward threshold to achieve the max average balance scores at different training steps; Right: the average balance scores on 600 MATH training queries at different training steps, varying the number of samples to draw per query; Every 500 steps corresponds to one iteration for example, step 500 corresponds to the st iteration, while step 1500 corresponds to the 3 rd iteration.
number responses among queries will be severely imbalanced (Tong et al. 2024), where the easy queries will occupy most of the correct responses to maximize the average balance score. The second term, /n,,, is the ratio of the correct responses. We note that this ratio is always 100% if only the final-answer reward is used. n' is the only hyperparameter in this metric, and it roughly implies the number of correct responses that we aim to have per query. Suppose we aim to select N samples per iteration, and each iteration we feed in M queries where N M, then we simply decide n 3r As N and M are just general training hyperparameters related to data loader, we never tune them in the paper and just set them as reasonable numbers as we will describe later. This means, the balance score does not introduce additional hyperparameters for us to tune.
Intuitively, the exploration and exploitation are desired be controlled to maximize the average balance score - the max value of bs; is 1 and the average balance score is maximized when all the selected responses are correct and there are at least n² correct responses for each query. Controlling exploration and exploitation is non-trivial and there could be different approaches, in this work we focus on a simple method where we manipulate the balance through certain hyperparameter configurations such the sampling temperature and reward threshold, which we discuss next.
3.2 DYNAMIC OR STATIC ON THE CONFIGURATIONS EXPLORATION AND EXPLOITATION
The balance score provides a straightforward signal on how we should manipulate exploration and exploitation to be optimal. In this work, we mainly focus on adjusting some hyperparameter configurations to control exploration and exploitation. Here, we conduct preliminary analysis to investigate whether the optimal configurations which maximize the averaged balance score are static should be dynamically changing. Specifically, we obtain the policy model checkpoints and reward model checkpoints from different iterations of online RFT with the final Answer PRM reward run, with 500 steps between each iteration. We then apply different configurations to these checkpoints, and compute the average balance scores on 600 randomly sampled MATH training queries. Below detail the configurations we study.
Exploration temperature. Sampling temperature, an important configuration influencing explo- ration, first examined for its impact on balance score. With the reward threshold fixed at 0.0 and sample size of 32, we adjust the sampling temperature to 0.5, 0.7, 0.9, and 1.1. In Figure ((a) 4a))we we show the optimal temperature we obtained that maximizes the average balance score at different iterations (training steps). In this particular setting. lower temperatures are preferred in the beginning while higher temperatures are better later on. This phenomenon can be explained by the model's 's shifting limitations during training. In the early stages, the model's ability generate correct solutions is limited, so lower temperatures help sample more accurately (Yang et al. (0023). As training advances, the challenge shifts to preserving diversity in the generated solutions, requiring higher temperatures to ensure broader sampling.
7

---

Published as a conference paper at ICLR 2025
GSM 8K
MATH
APPS
ARC-C
Methods
P@
P@ 32
P@3224
P@!
P@32
P@32-4
P@ 1
P@32
P@32-4
P@
SFT
36.6
88.5
62.2
17.0
60.8
31.2
9.3
43.5
25.5
Rest-EM (wlo RM)
40.5
89.9
69.8
22.8
60.0
33.6
14.5
43.9
28.2
70.7
Rest-EM (w/ RM)
46.3
90.7
72.2
24.2
62.8
37.4
Iterative RFT (wlo RM)
42.8
88.9
71.3
63.4
15.2
44.3
28.0
70.3
lterative RFT (w/ RM)
46.6
90.2
74.9
24.4
62.6
39.0
Online RFT (wlo RM)
44.0
88. 1
69.7
23.0
$7.2
38.2
17.3
45.8
27.8
71.2
Online RFT (w/ RM)
46.8
91.4
76.5
23.2
62.6
39.2
B-STAR
53.8
93.6
81.0
27.8
67.2
42.2
19.6
49.3
30.7
73.0
Table Comparison of self imfrrovepeeeeenttt methods across MATH, GSM8K, APPS and ARC-Challenge. Methods include variants with without a reward model ("w/ RM" and "w/o RM"). The results are hased on Mistral-7B model except for APPS that is from Llama-3-8B.
Exploitation threshold. We investigate the impact of reward thresholds balance score, which determines how the reward exploits the responses. high reward threshold indicates that the reward model strictly exploits responses, whereas a low threshold suggests more relaxed selection criteria. In our experiments, we fix the sampling temperature at 1.0 and the sample size at 32, while varying the reward threshold and selecting responses that exceed the threshold. Figure 44b) presents the optimal threshold that maximizes the average balance score. It indicates that a higher threshold is preferred in the beginning, but it may need decrease training progresses. Intuitively, this suggests that more rigorous filtering should be applied in the beginning, when the model is weaker, and the threshold should be relaxed slightly as the model becomes stronger.
3.3 B-STAR
Building the findings from [3.2 that the optimal configurations to maximize balance score is dynamically changing. we propose B-STAR, short for Balanced Self-Taught Reasoners, a method that maximizes the average balance score by dynamically adjusting configurations balance exploration and exploitation. We also include related work on dynamically adjusting configurations in the Appendix F Specifically, we adjust temperature and threshold automatically at every iteration, to maximize the average balance score. Notably, we only need to compute the balance score on a small subset of training queries to decide the balanced configurations, thus incurring negligible additional costs compared to the baselines. For example, we only use 600 MATH queries in our experiments. Our B-STAR algorithm is illustrated in Figure[]and summarized Algorithm|]] [ There are other configurations affecting balance score, such the number of responses drawn per query (sample size) that will influence the exploration.
our preliminary trials in Figure 4(c) larger sample size tends be generally helpful. Therefore, just use the maximum sample size according to computing budget and fix it, and mainly focus on dynamic adjustments of temperature and threshold.
MAIN EXPERIMENTS
4.1
SETUP
We evaluate B-STAR's effectiveness in enhancing self-improvement for mathematical problem- solving, coding challenges and commonsense reasoning. Our evaluation compares several baseline methods: WTaR/ResT-EM (Zelikman et al. 2022, Singh et al., 2023), Iterative RFT, and Online RFT (Shao et al. 2024). Additionally, we implement these methods with two types of reward function: "without RM" (Answer) and "with RM" (Answer+PRM), as described in $2.3 We also provide
detailed baseline methods and experimental setup in Appendix B
4.2 RESULTS
Main Results. Table [ provides comprehensive comparison of B-STAR with various self- improvement methods, including Rest-EM, Iterative RFT, online RFT, and their reward model variants mathematical rooliin-solving, coding challenges and commonsense reasoning. The re- sults show that B- B-STRR consistently achieves higher Pass@ I scores across all scenarios, highlighting its ability to effectively steer the model toward correct responses via greedy decoding. Moreover,
8

---

Published as a conference paper at ICLR 2025
70
25-
28
30
STORRISTEM
SToRReST EM
50
Eurattre
B-TTAR
1900
2000
2000
4200
1006
2000
2000
4000
1000
2000
2000
4000
(a) GSM8K
(b) MATH
(c) APPS
Figure 5: Pass K-S over training steps on GSM8K, MATH and APPS. ARC-Challenge, due to the limited response space of multiple-choice questions, Pass @ and Pass@K-S metrics (where K > 1) provide no additional insights and are therefore excluded.
60
70
60
50
50
14
39
STACTWSTIMM
Staatftad Online RFT
Rerative IFT
Onlne
iterative RFT
Onlne RFT
20
Iterative RFT
B-S
STOR
B 3.5TRR
1003
2000
3000
4030
1000 2005
3000
4003
10
1000
2000
3003
4030
(a) GSM8K
(b) MATH
(c) Balance Score
Figure 6: Reward K-S training steps GSM8K (left), MATH (middle). For coding challenges and commonsense reasoning. we not use reward model, but instead use unit tests and ground truth answers respectively as binary rewards, so we do not report Reward @ K Balance Score over training steps (right).
Step
500
1000
1500
2000
2500
3000
3500
4000
4500
Temperature
0.5
0.9
1.1
1.1
Reward threshold
-0.1
-0.1
Balance Score
0.470
0.538
0.589
0.621
0.646
0.660
0.673
0.678
0.679
Table Dynamic configuration adjustments by B-STAR mathematical problem-solving. The temperature
increment and reward threshold increment are both set to 0.1. Additionally. finer-grained increments for these parameters explored in detail in Appendix D and summarized in Table
B-STAR demonstrates significantly better Pass@ K-S values, reflecting enhanced exploration capacity that facilitates the generation of wider range of high- responses. Notably, online RFT outperforms predominantly offline methods like Rest-EM, illustrating that dynamic, on-policy approaches strike more effective balance between learning efficiency and performance gains.
As shown Figure all the self-improvement methods exhibit significant performance improvement after the first iteration. However, as the number of iterations increases, the growth trends of other baseline methods slows down and eventually stagnate. contrast, B-STAR maintains a substantial growth rate and consistently outperforms other baselines. This suggests that balancing exploration and exploitation is crucial for achieving stable and efficient self-imprrvement.
Moreover, in Figures and throughout the self- celf-improvement process in mathematical problem-solving Figure 6(c) highlight B B-S'' effectiveness in balancing exploration and exploitation- configurations, resulting in a markedly higher balance score. This optimal balance drives the consistently higher Pass @ K-S and Reward @ K-S scores observed in Figures 5 and 6 across both datasets. These results suggest that B-STAR not only encourages the model to generate a diverse range of accurate responses but also efficiently incorporates feedback from the reward model.
present the dynamic evolution of B-STAR and Online RFT

---

Published as a conference paper at ICLR 2025
Methods
GSM 8K
MATH
Online RFT
46.8
23.2
B- B-STAR (Temperature Adjustment Only)
53.1
25.0
B-STAR (Reward Threshold Adjustment Only)
49.1
24.6
B-STAR (Temperature + Reward Threshold)
53.8
27.8
Table 3: Ablation study on dynamic adjustment in mathematical prohlem-solving, including temperature adjustment only and reward threshold adjustment only.
Methods
GSM8K
MATH
APPS
ARC-C
SFT
49.4
18.8
15.6
78.8
Rest-EN EM (w/RM)
60.2
28.2
16,4
85.5
Iterative RFT (w/RM)
55.3
27.2
17.1
85.2
Online RFT (w/RM)
59.7
27.8
16.9
85.2
B-STAR
61.6
29.2
18.1
86.3
Table comparison of self self-improvement methods trained on Llama-3. across MATH, GSM8K, APPS, and ARC-Challent showing the highest Pass @ results. For ARC-Challenee we start from Llama-3.1-88 Instruct and omit the SFT stage due to the absence of CoT data for this dataset.
Dynamic Configuration Adjustments by B-STAR. Table 2 presents the configurations automati- cally adjusted by B-STAR at various training stages, along with the resulting balance scores. Early in training, B-S B-STAR employs lower sampling temperature, typically around 0.5, which gradually increases as training advances. This gradual increase promotes cautious exploration during the initial phases, allowing the model to stabilize before expanding to broader sampling in later stages. Concurrently, B- STAR enforces stricter reward thresholds at the start, relaxing them as the model becomes more proficient. These strategies, discussed in Section 3.2) enable B-STAR to maintain an effective balance between exploration and exploitation throughout the training process.
4.3 ABLATION STUDY AND ADDITIONAL RESULTS
Ablation on Dynamic Adjustments. Table I and Table illustrate the impact of dynamically adjusting both the temperature and reward threshold on balance score and overall performance. To emphasize the importance of each configuration, we perform experiments where one configuration remains at the default settings of online RFT while the other adjusts dynamically. As shown in Table dynamic adjustments to both configurations are critical, with performance significantly deteriorating when either configuration is fixed individually. To demonstrate that B-STAR's improvements stem from dynamic configuration adjustments rather than from suboptimal configuration settings, we compare B-STAR with online RFT using various fixed configuration combinations in the Appendix Even the best fixed configurations from grid search underperform compared to B-STaR, underscoring the crucial role of dynamic adjustments.
Generalizing to More Powerful Models. To assess the generalization capability of B-STAR on more powerful models, we train the model using Llama-3.1-88 and evaluate its performance across MATH, GSM8K, APPS and ARC-Challenge. Due to computational resource constraints, we set the sample size for math reasoning to 48, and the sample size for APPS and ARC-Challenge to 32, while keeping all other parameters consistent with $42 The results in Table ssow that B-STAR successfully generalizes to more powerful models.
5 DISCUSSION
In this paper, we reveal the importance of the balance between exploration and exploitation in self-improving training, and we propose B-STAR, a novel algorithm to strike better balance and achieve superior performance on reasoning and coding tasks. While we adopt a simple method that manipulates exploration and exploitation through hyperparameter configurations, we expect more flexible control of these two factors can be achieved in the future to strike a better balance, such as advanced decoding approaches directly control the exploration of the generated data, and reward model update to improve exploitation.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
We thank the anonymous reviewers for their feedback to help improve this paper. This work is supported by NSFC with Grant No. 62306177.
REFERENCES
Hui Bai and Ran Cheng. Generalized population-based training for hyperparameter optimization in reinforcement learning. IEEE Transactions on Emerging Topics in Computational Intelligence, 2024.
Sungyong Baik, Myungsub Choi, Janghoon Choi, Heewon Kim, and Kyoung Mu Lee. Meta- learning with adaptive hyperparameters. Advances in neural information processing systems, 33: 20755-20765, 2020.
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. arXiv preprint 17X3::1703.00 2017.
Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. Codet: Code generation with generated tests. arXiv preprint arXiv:2207. 10397, 2022.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03377 2021.
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv: 000..0003355555 2018.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2 10. 14168, 2021.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXhv:2477.21783, 2024.
Jörg KH Franke, Gregor Köhler, André Biedenkapp, and Frank Hutter. Sample-efficient automated deep reinforcement learning. arXiv preprint arXiv:2009.0155: 2020.
Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjie Gu. et al. Reinforced self-training (rest) for language modeling. arXiv preprint arXiv:2308. 08998, 2023.
Alex Havrilla, Yuqing Du, Sharath Chandra Raparthy, Christoforos Nalmpantis, Jane Dwivedi- Yu, Maksym Zhuravinskyi, Eric Hambro, Sainbayar Sukhbaatar, and Roberta Raileanu. Teaching large language models to reason with reinforcement learning. arXiv preprint arXiv:2403. 04642, 2024.
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. arXiv preprint 1..Xi:22003.3300 2021.
Arian Hosseini, Xingdi Yuan, Nikolay Malkin, Aaron Courville, Alessandro Sordoni, and Rishabh Agarwal. V-star: Training verifiers for self-taught reasoners. arXiv preprint 2024:2402.006557 2024.
Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large language models self-improve. arXiv preprint 10. 2022.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czamecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based training of neural networks. arXiv preprint arXiv: 1.09846, 2017.
11

---

Published as a conference paper at ICLR 2025
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
Hadi S Jomaa, Josif Grabocka, and Lars Schmidt-Thieme. Hyp-rl: Hyperparameter optimization by reinforcement learning. arXiv preprint arXiv: 1127,, 2019.
Mariam Kiran and Melis Ozyildirim. Hyperparameter tuning for deep reinforcement learning applications. arXiv preprint arXiv:2201. 2022.
Yifei Li, Zeqi Lin, Shizhuo Zhang. Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making large language models better reasoners with step-aware verifier. arXiv preprint 2xXiv:206.022366, 2022.
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. arXiv preprint arXiv:2305.20050, 2023.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv: 03983, 2016.
Aditya Mohan, Carolin Benjamins, Konrad Wienecke, Alexander Dockhor, and Marius Lindauer. Autorl hyperparameter landscapes. arXiv preprint arXhv:2304.02236, 2023.
Richard Yuanzhe Pang, Weizhe Yuan, Kyunghyun Cho, He He, Sainbayar Sukhbaatar, and Jason
Weston. Iterative reasoning preference optimization. arXiv preprint 24Xx::2404.19733 2024.
Zhihong Shao, Peiyi Wang. Qihao Zhu, Runxin Xu, Junxiao Song, Mingchuan Zhang, YK Li, Yu Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300 2024.
Özgür Şimşek and Andrew G Barto. An intrinsic reward mechanism for efficient exploration. In Proceedings of the 23rd international conference on Machine learning, pp. 833-840, 2006.
Avi Singh, John D Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil. Peter Liu, James Harrison, Jachoon Lee, Kelvin Xu, Aaron Parisi, al. Beyond human data: Scaling self self-training for problem-solving with language models. arXiv preprint arXiv:2312.06585 2023.
Leslie N Smith. A disciplined approach to neural network hyper-parameters: Part 1 1-learning rate, batch size, momentum, and weight decay. arXiv preprint arXiv: 1803.09800 2018
Zhiqing Sun, Longhui Yu, Yikang Shen, Weiyang Liu, Yiming Yang, Sean Welleck, and Chuang Gan. hasy generalization: Scalable alignment beyond human supervision. arXiv preprint arXiv:2403.09472 2024.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Yuxuan Tong, Xiwen Zhang, Rui Wang, Ruidong Wu, and Junxian He. Dart-math: Difficulty- rejection tuning for mathematical problem-solving, arXiv preprint arXiv:2407.13690, 2024.
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. arXiv preprint xxXiv:221..14273 2022.
Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx, Summer Yue, and Hugh Zhang. Planning natural language improves 11m search for code generation. arXiv preprint arXiv:2409.03733 2024a.
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce llms step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9426-9439, 2024b.
12

---

Published as a conference paper at ICLR 2025
Lilian Weng. weng.github.io. io. 2018.
The multi-armed bandit problem and its solutions. lilian-
URL
Wikipedia contributors. Exploration-exploitation dilemma Wikipedia, the free en-
http://ppppaaaaaaa//aaaa/a//aaa/ wnw.i...px....i..... Exploraation-exooottaaaa oea.aaoo..c..ccmaoooooooe1111111 [Online; accessed 26- November-2024).
cyclopedia, 2024.
URL
Ting Wu, Xuefeng Li, and Pengfei Liu. Progress regress? self-improvement reversal in post- training. arXiv preprint urXiv:2407.05013 2024.
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc Le, Denny Zhou, and Xinyun Chen. Large language models optimizers. arXiv preprint arXiv:2309. 20t.:233993999 2023.
Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Keming Lu, Chuanqi Tan, Chang Zhou, and Jingren Zhou. Scaling relationship on learning mathematical reasoning with large language models. XrXiv preprint arXiv:2308.01825. 2023.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning, Advances in Neural Information Processing Systems, 11115546-154888 2022.
13

---

Published as a conference paper at ICLR 2025
50-
477
70
42
40
72
32
35
Answer
Arewers
1910
40
Answer
AnamerrPPPM
bnow 1ld jone (010-1
30
1000
2000
3000
4000
30
1000
2000
4000
(a) Pass GSM8K
(b) Diversity on GSM8K (c) Pass K-S on GSM8K (d) Reward GSM8K
Figure 7: Pass@1 I, Diversity, Pass@ and Reward K-S over training steps on GSMSK. SFT refers to direct fine-tuning using the original dataset, "Answer" indicates matching against the ground-truth final answer, and "Answer PRM" combines ground-truth final answer matching with PRM reward.
Step
500
1000
1500
2000
2500
3000
3500
4000
45(H)
Temperature
0.65
0.75
1.05
0.95
1.05
0.85
1.05
1.15
1.05
Reward Thresholds
-0.04
-0.09
-0.09
-0.14
-0.14
-0.15
-0.06
Balance Score
0.500
0.557
0.591
0.626
0.652
0.665
0.679
0.682
0.684
Table Finer-grained dynamic configuration adjustments by B-STAR mathematical problem-solving.
A EXPERIMENTS FOR THE CASE STUDY
A.1 EXPERIMENT SETUP
Datasets We use the MATH dataset for training and validate the model's mathematical reasoning ability using test sets from both the MATH (Hendrycks al. (222I) and GSM 8K (Cobbe et al. [02
datasets. For the MATH dataset, we follow previous settings (Lightman et al. 2023 Wang ct al.
2024b Sun al. 2024 by using subset of 500 representative problems (MATH500)
test
data. We uniformly sample an additional 500 problems for validation and use the remaining 4,000
problems from the MATH test along with the original 7,500 training problems our training data.
Implementation details For SFT, we use Mistral-7B (Jiang et al. 2023) the base model with learning rate of 5e-6, a batch size of 128, and train for 3 epochs. After the first epoch, the model (denoted Po) is used as the starting point for self-improvement. We then proceed with iterations, where each iteration consists of 500 training steps with a batch size of 128. At the beginning of each iteration, we sample 32 candidate responses for each query, using temperature of 1.0.
For the Process Reward Model (PRM), we automatically generate process annotations following the MATH-SIN Shethedde approach (Wang et al.) 2024b). Using the SFT model trained for epoch, we sample 15 responses for each query in the training set. The SFT model trained for 3 epochs serves as the completer, decoding 8 solutions per step to annotate the sampled data. This process results in approximately 270 K process reward annotations. We train the reward model using the Mistral-7B base, with a learning rate of 2c-6, for 2 epochs. During rewarding, we use the lowest step score the solution the PRM Reward, normalize form the final reward score. We set the reward threshold to 0.0, selecting only those responses with final reward scores exceeding this threshold.
range of [-1, and combine it with sparse reward to
A.2 RESULTS ON GSM8K
we present the changes in Pass@1. Diversity, Pass@K-S, and Reward K-S metrics on GSM8K. Our results indicate that incorporating PRMs leads to additional improvements on GSM8K. However, these improvements are less pronounced on MATH. We hypothesize that this is due to the difficulty of MATH problems, which may exceed the discriminative capabilities of the 7B reward model.
In Figure 7
14

---

Published as a conference paper at ICLR 2025
Algorithm B-STAR
Require: Iterations I, initial policy Po. reward model R.M, dataset D, temperature E T, sample size k, threshold E θ, optimizer Ou. scheduler Le.
Ensure: Final updated model Pr.
1: for to do
Step 1: Balance Exploration Exploitation
3: // BS())): the average balance score 43.
4: 4.74 T4 arg max B)(t,
5: Step 2: Generate Candidates
M Draw M queries [=;]}=1 C D
7:
for j = 1 to M do
8:
for = 1 to & do
9:
M. P-- 2z5t,)
10:
end for end for
11:
12:
// Step 3: Evaluate via Reward Model
13:
D; {(I). (i.m))mm]]; 7imm (M,.)
14:
D {(I):85m) Tymm n
Step 4: Improve Policy Model Pt = Up, ,, O-- L(-1)
16:
17:
// Step 5: Inherit Optimizer & Scheduler
18:
O, O,-1, Li +- L,-1
19:
end for
B EXPERIMENT SETUP FOR MAIN EXPERIMENTS
B.I BASELINE
Our evaluation compares several baseline methods: STaR/ResT-EM (Zelikman et al.) 2022 Singh et al., (202)). Iterative RFT, and Online RFT (Shao et al. 2024). The STaR/ResT-EM approach involves multiple iterations, where each iteration samples from the latest policy model but resets and retrains the model from scratch. In contrast, Iterative RFT builds on each previous iteration by inheriting the checkpoint and resuming training from that point. Online RFT goes a step further by not only inheriting the checkpoint but also the optimizer state and learning rate schedule, ensuring a smoother transition across iterations.
B.2 MATHEMATICAL WOBLEM-SOLLVIE
We use the Mistral-7B model as our base and conduct SFT on the MATH training dataset for three epochs. The first epoch serves the starting point for the model's self-improvement phase. We set the number of samples per iteration (N) to 67,500 and feed 1 11,500 MATH training queries (M) per iteration. We sample size 64 for all methods. We vary temperature from 0.5 1.2 in 0. increments and reward threshold from -1.0 to 1.0 in 0.1 increment. Additionally, finer increments for both the temperature and reward threshold are explored in Appendix [ Throughout the self-im eef-impprveeentt process, we use Pass@) 1, Pass @ K-S, S, and Reward @ K-S metrics to track changes in the performance and model's exploration and exploitation capabilities.
For mathematical problem-solving, largely maintain the experimental setup from 2.3
B.3 CODING CHALLENGES
On coding challenges, follow (iighh al. (2023) and adopt the APPS (Hendrycks et al.) 2021 dataset for both training and testing. To balance the number responses per question, we sample responses per question from the original APPS training set forming dataset with 13K examples. We use Llama-3-8B Dubey et al. 2024) as our base model ( keeping the rest of the settings consistent with those of the math domain. For baselines, we uniformly sample 32 candidate responses per query with a temperature of 0.4. For B-STAR, we explore temperatures 0.4 to 1.1 in 0.1 increment to determine the optimal configuration. We set the number of samples per iteration (N) to 13,500 and
We do not use Mistral-7B as in the math domain because we found it performs poorly on coding tasks.
15

---

Published as a conference paper at ICLR 2025
feed 2627 APPS training queries (M) per iteration. We do not apply reward models the coding task and instead use unit tests as the binary reward, which means only the sampling temperature is automatically adjusted in B STAR..
B.4 COMMONSENSE REASONING
For commonsense reasoning. following Pang et al. (2024). we conduct experiments on ARC- Challenge (Clark et al., 2018), a dataset consisting of multiple-hoicee science questions designed to evaluate commonsense reasoning beyond mathematics and coding challenges. We start with the Mistral-7b-instruct model and omit the SFT stage due to the absence of the CoT data for this dataset. Other configurations, such sample size and temperature, are the same as those used in the coding tasks. The ground-truth answer serves as the binary reward, and we report only Pass@) I results for the ARC-Challenge dataset. Given the constrained response space inherent to multiple-choice questions, Pass @ K and Pass K-S metrics (where > 1) yield no additional insights and are therefore excluded.
C DETAILS OF SELF-IMPROVEMENT
Fixed Reward Function
A fixed reward function r(z 3) is predefined, static function that does not adapt based on the training process or model parameters. For instance, binary feedback (c.g.. whether math problem is solved correctly unit test passes) is example of fixed reward function. The fixed reward function can be represented as:
1,
if satisfies predefined condition (e.g., test passes),
r(x, v)
(4)
0, otherwise.
Reward Model
A trained reward function r(æ, yi () is parameterized by & and adapts based on the training process. These reward functions (such output-based reward models (ORMs) process-basse reward models (PRMs)) are learned from data, where the model learns to assign continuous scores based on supervision signals.
The trained reward model can be represented as:
r(z, y: Φ) = f(x, σ)
(5)
where [x, yi Φ) a learned function (e.g., a neural network) that maps the input and the response to a continuous reward score.
Rejection Sampling Fine-tuning
Rejection Sampling Fine-tuning (RFT) first samples multiple outputs from the supervised fine-tuned LLMs for each query and then trains LLMs on the sampled responses with the correct answer. Formally, the objective of RFT is to maximize the following objectives:
(RFT(()
(6) EL-D [T()) log p(y x; 0)]
The indicator function I(y) is defined as:
I(y) [1, if the answer of is correct,
if the answer of y is incorrect.
Our evaluation compares several baseline methods: RTa,/ResT-EM, Iterative RFT. and Online RFT. The STaR/ResT-EN approach involves multiple iterations, where each iteration samples from the latest policy model but resets and retrains the model from scratch. In contrast, Iterative RFT builds on each previous iteration by inheriting the checkpoint and resuming training from that point. Online RFT goes a step further by not only inheriting the checkpoint but also the optimizer state and learning rate schedule, ensuring smoother transition across iterations. Additionally, we evaluate two variants: "without RM" (Answer) and "with RM" (Answer+PRM)) as described in Section 2.3
16

---

Published as a conference paper at ICLR 2025
24
-0.4
42.0
48.4
48.7
39.2
50
19.4
23.0
23.6
19.6
23
-0.2
42.7
45.7
50.9
42.0
48
0.2
20.6
23.6
23.2
18.0
22
Threshold 0.0
Threshold 0.0
40.9
46.1
49.0
42.6
21.8
21.8
21.0
20.8
0.2
40.7
47 2
50.0
40.9
0.2
19.8
22.6
22.8
19.4
-20
42
-19
0.4
0.4
21.6
23.8
40
18
Temp
Temp
Temp
Temp
Temp
Temp
1.1
(a) GSM 8K
(b) MATH
Figure 8: Performance of online RFT using different configuration combinations, where the horizontal axis represents changes in temperature and the vertical axis represents changes in reward threshold. B-STAR's GSM8K accuracy is 53.1% %, while its MATH accuracy is 27.8%.
Configuration
GSM 8K
MATH
Temp 1.0; Threshold = 0.0
46.8
23.2
Temp 1.1; Threshold = -0.1
40.4
18.2
B-STaR
53.1
27.8
Table Comparison of Online RFT using specific configurations and B-STaR Performance. This table reports the results with stable hyperparameter combinations we found in our B-STaR experiments (Temperature 1.1, Reward thresholds -0.1) (Table
D MORE TINE-GRAINED CONFIGURATION ADJUSTMENTS
In Section we initially set the increments for both the temperature and reward threshold to 0.1. To explore the effects of using finer- finer-graine grained increments on B-STAR, further conduct finer-grained hyper-parameters search with the granularity of 0.05 for temperature and 0.01 for reward threshold in mathematical problem-solving setting. TaableSjilluusraaee how B-STAR dynamically adjusts its configuration and the resulting impact on balance score. A comparison of Table Table reveals that finer-grained configuration adjustments introduce more dynamic changes to temperature and reward thresholds throughout the training process, resulting in significantly higher balance score.
E IMPACT OF FIXED CONFIGURATION COMBINATIONS
To confirm that the improvements achieved by B-STAR are due to its dynamic configuration ad- justments rather than suboptimal configuration settings, we conduct a grid search to evaluate dif- ferent configuration combinations for online RFT. The temperature values selected from the set (0..90.7.0.9.11. 1] and the reward thresholds are chosen from -.0.4.0022.00000.2.00 For comparison, also include specific configurations: the default combination from our paper, (1.0,0.0), and the parameters obtained from B-STAR'S 's final iteration, (1.1,-0.1).
Figure and Table 6 illustrate that while grid search-based configuration combinations offer some performance improvements for online RFT, they remain less effective compared to the dynamic con- figuration adjustments enabled by B-STAR. This further emphasizes the critical need for dynamically balancing exploration and exploitation throughout the training process.
17

---

Published as a conference paper at ICLR 2025
F RELATED WORK OF DYNAMIC HYPERPARAMETER ADJUSTMENT
Dynamic hyperparameter optimization addresses the shortcomings of static configurations, which cannot adapt the evolving dynamics of machine learning. Early work by Loshchilov & Hutter (2016) introduced the use of a cosine function to modulate learning rates, ensuring smoother conver- gence. Building on this, Baydin et al. (017) proposed gradient-based methods dynamically adjust learning rates in real-time by analyzing gradient trends, significantly accelerating convergence. Ex- panding the scope, |Smihh (2018) introduced a systematic approach to setting hyperparameters, such as learning rate, batch size, momentum, and weight decay, while highlighting their interdependence to improve training efficiency. Subsequently, Daderberg et al. (2017) integrated model and hyperpa- rameter optimization by asynchronously evolving population of models through performance-brce selection and mutation. Jomaa et al. (2019) framed hyperparameter tuning as a sequential decision- making problem, leveraging reinforcement learning to learn a policy for efficient hyperparameter selection. More recently, Baik et al.] (2020) adopted a meta-learning framework to dynamically generate task- and step-specific hyperparameters. improving inner-loop optimization in few-shot learning tasks. Inspired by these innovations, our approach focuses on dynamically monitoring and balancing configurations between exploration and exploitation, optimizing the synergy between current policies and reward mechanisms to drive further performance gains.
Dynamic adjustment of hyperparameters has also proven be crucial in pure reinforcement learning (RL) settings. For instance, Kiran & Ozyildirim (022) highlights how adapting hyperparameters can significantly influence both the learning process and processing times deep RL problems. Sim- ilarily, Franke et al. (2020) proposes a population- based automated RL framework that concurrently optimizes hyperparameters and neural architectures during agent training. Furthermore, MMohan et al.) (2023) examines the dynamic nature of hyperparameter landscapes in RI, offering empirical evidence that these landscapes evolve over time, varying across algorithms and environments. To enhance adaptability, [aii & Cheng (2024) introduces refined framework that emphasizes granularity and flexibility in hyperparameter adjustments, incorporating a Pairwise Learning approach to provide comprehensive guidance for improving the performance of underperforming agents.
G THEORETICAL JUSTIFICATION FOR EXPLORATION AND EXPLOITATION
The objective of self- self-iimproeement can be expressed in the framework of reinforcement learning as follows:
1+1 H
arg max DD..y*>D.gvriil [R(,, v²)]
(8)
n
where DD represents the dataset, x and y" denote the sampled input and corresponding ground-truth answer, respectively, and ÿ is the sampled response. Here, z corresponds to the language model in the 1-th iteration. R is the reward function. According to the policy gradient algorithm:
V Vg [R(ú.")
- V Re. y log <b[00>]]
When R(G, v²) ) is binary, the above equation turns to be simple data selection and supervised training loss that is exactly what we are doing. Thus, self-improvement can be viewed as a form of reinforcement learning, where maintaining a balance between exploration and exploitation is crucial and has been studied for years (Simşek & Barto 2006 /Sttton Barto 2018: Weng 2018 Wikipedia contributors] 2024). Conceptually in classic RI,, exploration involves exploring the environment (analogous to reasoning tasks in our paper) by trying random actions (corresponding to sampling multiple candidates in our work) to gather more information about the environment. Exploitation, on the other hand, involves utilizing the known information to maximize the reward (similar to how we use the reward function to select data samples). Insufficient exploration may cause the training process to stagnate, while insufficient exploitation can lead to instability and large variance during training.
18


Reviews:
[{"review_id": "82WsNXM8wu", "reviewer": "Reviewer_Gb3F", "summary": "The paper is addressing how to improve self-taught reasoners. It addresses the challenges of iterative self-improvement for reasoning tasks in AI models, particularly in mathematical problem-solving. With limited access to high-quality, human-annotated data, models are trained to refine themselves via generated outputs. However, performance gains often stagnate after a few iterations, with degradation in exploratory diversity and effectiveness of rewards. To counter these issues, B-STAR introduces a dynamic framework that monitors and balances exploration (generating high-quality candidate responses) and exploitation (selecting optimal responses using reward mechanisms).\n\nKey innovations include metrics like \"Pass@K\" for exploration and \"Best-of-K\" for exploitation, which quantify the model's ability to generate diverse and correct outputs while ensuring selected outputs are useful for training. B-STAR adapts configurations such as sampling temperature and reward thresholds, adjusting them based on \"query effect\" scores to optimize exploration-exploitation balance iteratively. In each iteration, the algorithm dynamically adjusts configurations, specifically sampling temperature and reward thresholds, to maximize the \"query effect\" score, which ensures an effective balance. The model then generates multiple responses per query, selecting only those with high rewards to use as training data for the next iteration. This process is repeated across iterations, inheriting the optimizer and learning rate to maintain consistency in online training and continually improve model performance.\n\nThe experiments in B-STAR evaluate its effectiveness on mathematical reasoning and coding tasks, comparing it against other self-improvement methods like Iterative RFT and Online RFT. B-STAR consistently outperforms these baselines in generating accurate responses, as shown by higher Pass@1 and Pass@K-S scores, which indicate both accuracy and diversity in responses. In mathematical tasks, B-STAR maintains exploration across iterations, unlike other methods where diversity declines, highlighting its balanced approach to exploration and exploitation. For coding challenges, B-STAR achieves steady improvement across iterations, suggesting that dynamic configuration adjustments improve response quality over time. The experiments validate B-STAR’s approach in sustaining a higher growth rate in performance by adaptively balancing exploration and exploitation.", "questions": "- address weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Dynamic Balancing of Exploration and Exploitation\n- Comprehensive Metrics for Monitoring\n- Empirical Validation with strong results\n- Insightful Analysis of Self-Improvement Dynamics", "weaknesses": "- Reliance on fixed reward models\n- complexity of configuration tuning\n- limited generalization across task types\n- potenitalluy saturate in long iterative training", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m2rkuHBBci", "reviewer": "Reviewer_hcTF", "summary": "This paper introduces B-STAR, a framework aimed at improving the self-improvement process of large language models in complex reasoning tasks, such as mathematical problem-solving and coding. The primary challenge addressed is the difficulty in balancing exploration (the model's ability to generate diverse, high-quality responses) and exploitation (the model's ability to effectively select the best responses) in iterative training processes without extensive human-labeled data.", "questions": "**1.Ablation and Related Work**: From figure 4, it seems that after 1000 iterations, parameters like temperature and threshold remain constant. So essentially the dynamics freeze. *Does this imply that original hyperparameter is simply not set to optimal?* It is important to see how static shift of hyperparameter can help to fully verify the effectiveness and necessity of the proposed method. Also, there lacks an explicit discussion and reference to the line of work that dynamically change the hyperparameter.\n\n**2.Query Effect Metric Validity**: How robust is the query effect metric across different tasks beyond mathematical reasoning and code generation? Without a theoretical foundation, is there a risk that this metric might not generalize well to other domains that require different types of exploration-exploitation balances?\n\n**3.Reward Model Dependency**: The paper relies heavily on reward models (both answer-based and process-based). How does the performance of B-STAR change if the reward model is not well-aligned with task objectives? In cases where defining an accurate reward model is challenging, can B-STAR still maintain its effectiveness?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**1.Identification of Balance Problem and Innovative Framework.** The introduction of dynamic parameter adjustment based on the \"query effect\" metric is an innovative approach to optimize performance across training iterations.\n\n**2.Clear Explanation of Exploration and Exploitation Dynamics**: By quantifying exploration and exploitation using metrics such as Pass@K and Reward@K-S, the paper provides insights into the dynamics of these factors, which are often overlooked in self-improvement research. This deepens understanding of the critical factors for model self-improvement.", "weaknesses": "**Limited Applicability Beyond Specific Tasks**: The paper focuses primarily on mathematical reasoning and code generation tasks, which limits the perceived applicability of B-STAR to other domains (e.g., open-domain question answering, language understanding) that query effect is hard to evaluate. And since QE is critical for following dynamical adjustment, this greatly limits the application.\n\n**Lack of Theoretical Foundation for Query Effect Metric**: Although the query effect metric is practical for optimizing exploration and exploitation, the paper lacks a rigorous theoretical justification for this metric. This could raise questions about its generalizability and effectiveness across a broader range of tasks and model architectures.\n\n**Unkown advantage over hyperparameter shift.** It seems that the final dynamics of the parameters do not fluctuate a lot. It should the excluded that most of the benefit is gain by adding an offset rather that dynamically change these parameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iyXbfPQZjy", "reviewer": "Reviewer_YTy3", "summary": "The paper is concerned with the field of self-improvement of LLMs in the context of complex reasoning tasks. Inspired by the classical RL literature, the authors identify the notions of exploration and exploitation, with their definitions adapted to the new domain, as important factors in this training procedure. They propose the B-STaR framework to address them in a dynamic way. The work first identifies factors responsible for the performance collapse observed in the self-improvement regime and then proposes to automatically adapt the training procedure to overcome it. This is done by automatically adapting two influential hyperparameters, the temperature and the reward threshold, based on the introduced query effect metric. The experimental evaluation is based on mathematical reasoning and coding tasks, showing that B-STaR leads to improved performance.", "questions": "I have blended the questions into the Weaknesses part, hence will be happy if the authors address those extensively. My general impression is that the paper describes a nice idea of transfering the notions of exploration and exploitation into self-improvement regime, but struggles with clear communication along the way. Introducing the query effect and showing that it may be incorporated during training to adaptively modify two important hyperparameters seems to be a very interesting contribution to the field, but the empirical evidence does not clearly indicate the connection between the metric and the hyperparameters, and if it could not be simplified with just simple heuristical schedulers. Overall, the authors could elaborate more extensively on the theoretical and formal background of the paper's topic as well as the obtained results. As I am not an expert in this field, I am open to raising my rating if solid and broad arguments are provided.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. The paper describes the underexplored notions of exploration and exploitation in the current research on self-improvement in complex reasoning tasks and empirically detects factors that are responsible for a balance between them. Based on that, a query effect metric is proposed to automatically adjust the related hyperparameters throughout training, which is shown to improve the performance in comparison to previous approaches.\n\nS2. The intuitive approach to balancing the trade-off between exploration and exploitation is nicely supported with a series of experiments (Sections 2 and 3) that guide the reader to better understand the influential factors.\n\nS3. A general overview of the approach is well summarized well with the pseudocode provided.", "weaknesses": "W1. My main concern about the paper is its generalizability to a broader spectrum of complex reasoning tasks. The empirical evidence is provided for two cases, one for mathematical reasoning and the other connected to coding tasks. As I am not an expert in the field, I am not aware of the number of other benchmarks that could extend the evaluation. Could the authors provide a summary of the scale of the experimental evaluation of the main papers that they compare with?\n\nW2. The paper would strongly benefit from a more principled approach of introducing specific concepts related to self-improvement training. I would appreciate if the main or supplementary text included the definition of the SFT loss, a more detailed description of RFT, some formalization of greedy decoding, clear distinctions of trained and fixed reward functions etc. In general, formulating the paper's concepts in a mathematical language would greatly improve clarity.\n\nW3. Some ambiguous statements are included throughout the paper which makes it difficult to follow the reasoning of the authors. For example, despite going through lines 155-160 multiple times, I was not able to grasp what the authors had in mind. Lines 167-168 mention that the distribution of candidates impacts how the reward model differentiates them, which suggests the distribution somehow influencing the reward function. I assume that the reward function is fixed and the authors meant that the distribution of candidates influences the distribution of the corresponding reward values? Or this depends on the case whether the reward is actually trained or not? I also found it hard to distinguish between the two points mentioned in lines 321-323. What is the difference between stating that `(the number of) high-quality respones among the selected ones cannot be too small' and `the percentage of the high-quality responses among the selected ones must be large enough'?I am certain that the phrasing could be improved in all of these cases.\n\nW4. I have some concerns regarding the methodology of the empirical evaluation which is not per-se the weakness of the paper but rather of the research field. Lines 214-215 mention that, in mathematical problems, the responses are evaluated according to only the final answer and not the entire series of reasoning steps. Do I understand correctly that such evaluation would classify as correct a mathematical proof that follows wrong reasoning but arrives at some form of correct conclusion?\n\nW5. The conclusions from Section 3.2 are based on modifying individual hyperparameters while keeping the others fixed. My concern is that the fixed values could be simply cherry-picked to fit the conclusions. Could the authors provide further motivation on why these exact fixed values should be chosen and maybe extended empirical results showing the trend for other fixed values?\n\nW6. Tables like Table 2. should be described more extensively, along with more examples for other cases, since the adaptability of the author's approach is the main contribution of the paper. Based on Table 2. alone, it seems questionable whether any adaptation of the reward threshold parameter is necessary, since only in the beginning its value differs from other stages of the training. The increasing trend of the query effect is promising, but because only single example is provided, I am not convinced that this is always the case.\n\nW7. Figure 6. is missing the plot for the APPS dataset. Typos: `answewrs` (line 253), `Exploration decreases over training and PRM helps retain` (line 282) <- retain what specifically?, `keeps improve` (line 295). For clarity of presentation and improved readability, the plots in Figures 5. and 6. should have the y-axis starting at zero. One could first think that plot (c) from Fig. 5 shows a higher relative improvement than plot (a) from the same figure, which does not seem to be the case after further inspection. I also strongly encourage the authors to open-source their code to allow for easy reproducibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)