MARGE: Improving Math Reasoning with Guided Exploration
Authors: Jingyue Gao
Runji Lin
Keming Lu
Bowen Yu
Junyang Lin
Jianyu Chen
Venue: ICML 2025 poster (2025)
Keywords: LLM
Reasoning
Reinforcement Learning
Exploration
Primary area: deep_learning->large_language_models

Abstract: Large Language Models (LLMs) exhibit strong potential in mathematical reasoning, yet their effectiveness is often limited by a shortage of high-quality queries.
This limitation necessitates scaling up computational responses through self-generated data, yet current methods struggle due to spurious correlated data caused by ineffective exploration across all reasoning stages.
To address such challenge, we introduce **MARGE**: Improving **Ma**th **R**easoning with **G**uided **E**xploration, a novel method that enhances mathematical reasoning through hit-guided exploration.
MARGE systematically explores intermediate reasoning states derived from self-generated solutions, enabling adequate exploration and improved credit assignment throughout the reasoning process.
Notably, MARGE improves both single-shot accuracy and exploration diversity, mitigating a common trade-off in alignment methods.
These results demonstrate MARGE's effectiveness in enhancing mathematical reasoning capabilities and unlocking the potential of scaling self-generated training data.

MARGE: Improving Math Reasoning with Guided Exploration
Jingyue Gao
Runji Lin
Keming Lu
Bowen Yu?
Junyang Lin
Jianyu Chen 13
Abstract
Large Language Models (LLMs) exhibit strong potential in mathematical reasoning, yet their effectiveness is often limited by a shortage of high-quality queries. This limitation ne- cessitates scaling up computational responses through self-generated data, yet current methods struggle due to spurious correlated data caused by ineffective exploration across all reasoning stages. To address such challenge, we intro- duce MARGE: Improving Math Reasoning with Guided Exploration, novel method address this issue and enhance mathematical reasoning through hit-guided exploration. MARGE sys- tematically explores intermediate reasoning states derived from self-generated solutions, enabling adequate exploration and improved credit assign- ment throughout the reasoning process. Through extensive experiments across multiple backbone models and benchmarks, we demonstrate that MARGE significantly improves reasoning capa- bilities without requiring external annotations or training additional value models. Notably, MARGE improves both single-shot accuracy and exploration diversity, mitigating a common trade- off in alignment methods. These results demon- strate MARGE's effectiveness in enhancing math- ematical reasoning capabilities and unlocking the potential of scaling self-generate training data.
62
50
DP0
54
GRPO
Durs-MARGE
20
80
sell-geeeeated training respoases per query
Figure I. The y-axis represents the accuracy MATH100,, and the x-axis represents the number of self self-generated responses for train- ing Awen2-7B-Instreee
The dots and the star show when models start to converge. and the dashed line exhibits their scaling trends as the generation amount for training increases. The top-right zone is preferred, as we can easily scale generation and achieve better performance when queries limited. By improving the exploration process, MARGE enables the scaling of self- self-generated responses training and improves reasoning ability. We discuss more about the scaling trend in Appx. D.
Despite these advances, improving LLM performance in long-horizon reasoning tasks, particularly mathematical problem solving, remains challenging due to two funda- mental challenges: the scarcity of high-quality training data and the inherent difficulty of exploring the vast space of possible reasoning paths.
While Self-training approaches (Zelikman et al., 2022) par- tially address data searcity by self-generating abundant train- ing examples, they struggle to scale computation during training to improve reasoning. This limitation is evident in our observations: model performance initially improves during self-training but quickly plateaus training data increases. These trends, consistent with Setlur et al. (2024), indicate spurious correlations between reasoning steps in self self-generated datasets.
1. Introduction
declines
Large Language Models (LLMs) have demonstrated remark- able capabilities in text generation and instruction following through post-training techniques such as Reinforcement Learning (RL) (Stiennon al., 2022; Ouyang et al., 2022).
As explained below, we argue that insufficient exploration causes spurious correlated datasets. Our primary research question now becomes: How can we enhance exploration across all reasoning stages to generate higher-quality training data, improve credit assignments, and enable scaling of self- training pipelines?
Institute for Interdisciplinary Information Sciences, Ts- inghua University, Beijing, China Alibaba Group 'Shanghai Qi Zhi Institute, Shanghai. China. Correspondence to: Runji Lin <linrunji. clibaba-ine.com.. Jianyu Chen <jianyuchend @ wwwttsusiieduu.ooommm edu..n"..
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Fig. exhibits a challenge mathematical reasoning and helps explain why insufficient exploration causes spurious correlations: even when model correctly executes all pre-

---

MARGE: Improving Math Reasoning with Guided Exploration
vious steps, it still might fail the final steps on average. This highlights the need for reasoning data that accurately as- signs credits to later stages without introducing spurious correlations. As the number of reasoning steps increases, the whole search space grows exponentially. This grow- ing search space makes it exponentially complex to find this kind of data as the steps get progressively further back (e.g., for DPO, we will need data that only diverges at the particular step but remains the same at previous steps).
solutions, MARGE explicitly aims to understand both suc- cessful and unsuccessful reasoning patterns and provide better exploration strategy for LLM reasoning. Additionally, MARGE operates efficiently by only inferring from the base L.L,, eliminating the need for additional value models or searching computation required by MCTS.
We conduct extensive experiments across various base models to demonstrate the effectiveness of MARGE. When applied to Qwen2-7B-Instuu icant performance gains across benchmarks like MATH (+7.90%), GSM8k (+3.03%), CollegeMath (+13.64%) and OlympiadBench (-5. 5.3%%,, using pure chain-of- thought reasoning. Furthermore, MARGE improves in- trinsic exploration, as evidenced by the higher performance gaps on pass@64.
it achieves signif-
To address these limitations, we introduce MARGE (Math Reasoning with Guided Exploration), a framework that systematically improves mathematical reasoning through guided exploration. MARGE leverages existing solutions as guidance, completing intermediate reasoning steps to generate diverse, high-quality training datasets. This ap- proach decomposes the exponentially complex exploration problem into manageable sub-problems while efficiently utilizing computational resources. By constructing datasets with common solution prefixes and strategically selecting guidance (correct solutions for complex problems, incor- rect ones for simpler cases), MARGE achieves comprehen- sive coverage across reasoning stages and improves credit for later steps where traditional ap-
In summary, our contributions
follows:
We introduce MARGE, a novel framework for guided exploration in LLM mathematical reasoning, laying the foundation for scaling the self-training pipeline;
Leveraging solution solution-guided exploration, we make it pos- sible to find more high-quality data, resulting in better exploration and credit assignment for complex multi-step mathematic problems:
proaches often fail.
Our investigation reveals two fundamental insights about guided exploration in mathematical reasoning. First, itera- tively running MARGE demonstrates that strategic guidance improves exploration during senereeneration. It enables seal- able improvements across diverse tasks, surpassing the per- formance plateaus encountered by prior methods. Second, and more interestingly, unlike traditional post-training meth- ods that trade-off generation diversity (pass@) @ k) for single- shot accuracy (pass@1) 1) (Wang et al., 2024a), MARGE mit- igates the issue and even might enhance both abilities si- multaneously. This improvement arises from MARGE's systematic coverage of diverse reasoning strategies across all stages, effectively expanding the model's solution reper- toire while reinforcing successful reasoning patterns.
We demonstrate MARGE's efficacy in improving rea- soning accuracy and generation diversity across multiple base models and benchmarks.
2. Related Works
2.1. LLM for Mathematical Reasoning
Previous works have proposed various methods to enhance the long-horizon reasoning capabilities of L.LMs, particu- larly in mathematical problems. One line of research et al., 2023; Chen et al., 2023) focuses on eliciting the rea- soning potential of L.MS with carefully designed prompts without updating the model. On the other hand, some ap- proaches involve training LLMs with additional data. Lu et al. (2024a); Gou et al. (2024); Yu et al. (2024); Liu et al. (2024a) synthesize new problem-solution pairs to fine-tune a base model. Furthermore, employing process-level super- vision during RL or Best-of-N sampling has been explored (Wang et al., 2023; Jiao et al., 2024; Lightman et al., 2023; Wang et al., 2024b; Luo et al., 2024), which, while effec- tive, often necessitates extensive generation and verification efforts. Our approach leverages only the policy model to generate datasets, thus simplifying the acquisition process.
Several recent works that try to enhance the reasoning abili- ties of LLMs, though not explicitly focused on exploration across reasoning stages, share our insights into enforcing exploration at different stages. Setlur et al. (2024); Xie et al. (2024); Lai et al. (2024); Lu et al. (2024b) explored step- supervision, attempting to identify and correct er- roneous steps in reasoning. However, these approaches usu- ally depend on external supervision or heuristics, which may fail to capture the diversity at all reasoning stages compared to MARGE, limiting their scalability. Monte Carlo Tree Search (MCTS)-based methods (Chen et al., 2024; Zhang et al., 2024; Feng et al., 2023; Xie et al., 2024) generate high-quality datasets by rigorously searching and exploring reasoning strategies. While they focus finding optimal
Some recent reasoning models like ol (Jaech et al., 2024), QwQ-32B-previie (Qwen, 2024), and deepseek- rl (DeepSeek, 2024) greatly improve LLM's reasoning ca- pacity through test-time scaling. Some other methods (Yao et al., 2023; Qi et al., 2024; Xiang al., 2025) also discuss
2

---

MARGE: Improving Math Reasoning with Guided Exploration
how to achieve such test-time scaling through system-2 plan- ning or carefully designed reasoning pipelines, which ac- complish similar improvements with smaller general models. Our method is perpendicular to these works as we address exploration issues and help scale self-generated responses during training. We also believe that they can be combined with our method in the future to enhance LLM's reasoning ability further.
State-level mathematical reasoning Let a b represent the concatenation of strings and b. We conceptualize the reasoning process as Markov Decision Process (MDP) (S, A. P,r), where states s E S and actions E A sam- pled from policy no, and transition dynamics formulated as $t+1 = S + aq. Each response y can be decomposed into multiple reasoning steps y = mi @ .... + Min delineated by specific delimiters or simply splitting the response. An intermediate reasoning state 8;, also a prefix of y, can then be formulated as 8; mi ... + mi, including the first state so which is an empty string. The terminal state 8n. y encompasses the final answer and, therefore not considered an intermediate state. The reward function r(z: y) = 1 if the full response y correctly answers the question x. Corre- spondingly, the value of state 8;, which equals the value of (si-1, 1)),), can be computed as
2.2. Reinforcement Learning for LLM Reasoning
Reinforcement Learning (RL) has effectively been applied to align LLMs with human preferences across various tasks, including instruction-followee
and summarization (Ouyang et al., 2022; Stiennon et al., 2022). Recent works (Yang et al., 2024a;b; Jiao et al., 2024) apply these methods to mathe- matical reasoning tasks. Xi et al. (2024) introduces reverse curriculum learning into math reasoning.Setie et al. (2024); Lai et al. (2024); Lu et al. (2024b) generate pairwise prefer- ence datasets from intermediate states and employ DPO to train the model. Chen al. (2024); Feng et al. (2023); Xie et al. (2024); Zhang et al. (2024) either learn step-level value function or directly fine-tune LLM through sampling with Monte Carlo Tree Search. Our method proposes a more efficient and natural exploration process for LLM reasoning, yielding a simple yet effective training pipeline that does not need external supervision or extra models.
Q (xi-11, = (8:))) = Err (1)
3.2. Output Reward MC as Value Estimation
To estimate the value of an intermediate state s, we use the Monte Carlo (MC) simulation to calculate VT(s;) in Eq. I. Starting from state 8;, we generate n completions from the current policy т, which we denote as T = Mi+1 @ .... @ mn ~ ग (z + st). The correctness of these completions is assessed to estimate the true value V as
3. Methods
This section introduces our method. We first present our problem formulation in Sec. 3.1, followed by the three main components of our proposed method in Sec. 3.2, Sec. 3.3, and Sec. 3.4. The general pipeline of our method is illus- trated in Fig. 2 and Algo. We enable the policy to cover the solution space better, persistently improving its reason- ing ability as the generated responses scale when running MARGE iteratively. We provide additional theoretical anal- ysis on how MARGE works in Appendix C, examples in Appendix F, and failure analysis in Appendix G.
(st)) 1 Σ
r(z, Tty).
(2)
This MC estimation method has several advantages over training a separate value model, such as a Process Reward Model. First, employing MC simulation avoids the need for additional model training and simplifies implementa- tion(Wang et al., 2023; Jiao et al., 2024). Besides, MC estimation provides an on-policy estimation, allowing re- sponses to be used in later policy improvement.
3.1. Problem formulation
3.3. flit-guided Exploration
Reinforcement Learning for LLMs Reinforcement Learning (RL) in the field of LLMS mainly involves two stages: training a reward model and optimizing this model using RL algorithms such as PPO (Schulman et al., 2017) and REINFORCE (Sutton et al., 1999). An alternative ap- proach, Direct Preference Optimization (DPO) (Rafailov et al., 2024), simplifies this process by learning directly from a preference dataset. Given a dataset that consists of a chosen and a rejected response for all prompts, DPO directly updates the policy π with a loss analogous to RLHF.
In this subsection, we discuss how utilizing the intermediate states of a self- seff-generated hit can improve the exploration strategy of LLMs. Previous works (Salimans & Chen, 2018; Florensa al., 2017: Xi et al., 2024) on RL and LLM reasoning show that starting from a demonstration state that is close to the terminal can reduce the difficulty of acquiring reward signals. Inspired by these findings, we propose to sample responses by continuing from all intermediate states of a selected response, which we call hit-guided exploration. This enables better exploration over the entire reasoning horizon.
3

---

MARGE: Improving Math Reasoning with Guided Exploration
Gulding generation
Policy Improvement
T
Eq. or) Eq.
Rollout Buffer
Query
value estimation Hit guided exploration
Query
Queery
Va estimate incresses
Queyy
Duery
States in the guiding
generated
Connect
Incorrect responses
Rollout results. Color
accuracy
Guiding
selection
OPO/RLHF
Figure 2. Overview of method MARGE, which includes four stages. (a): Generate multiple responses from the current policy x+ candidates for guidance and judge their correctness. Starting from the second iteration, we can directly leverage sampled responses from stage (c). (b): Among all candidate solutions, we select for each query as guidance according Sec. 3.3. (c): Perform continuation of all states in the guide solution to complete the exploration (Sec.3.3) and value estimation (Sec.3.2). The collected data is utilized in stage (d) for training and stage (a) in next iteration as well. (d): Having fully explored the state space (c), we first form the rollout buffer, then optimize the current policy, and finally acquire the policy x (+++1) for the next iteration described in Sec. 3.4.
is greatly reduced, making exploration much easier.
0.7
Incorrect Hit
Correct Hit
Furthermore, hit-guided exploration can potentially increase the amount of valid training data. As illustrated in Fig. the precision of completing an intermediate state increases average the state gets closer the end of correct response. This result, also proven in Prop. C.I. indicates that hit-guided exploration with a correct response increases the ratio of correct responses among all generations. The opposite also holds for incorrect ones. This shows that we can improve the number of desired responses if appropriate solutions are leveraged guidance.
aocuracy
0.5
0.4
0.2
5.0
7.5
State Index
Figure Average accuracies when starting from different interme- diate states of correct solutions (blue) and incorrect ones (red) with Qwen2-7B-Instruue
larger state index indicates being closer to the end. On average, completing from a correct (incorrect) state increases portion correct (incorrect) answers, which boosts the exploration of more training data.
Hit Selection and Update When aligning LLMs, in par- ticular reasoning, datasets that contain both positive and negative responses are preferred. Such datasets provide rich contrastive information regarding possible reasoning failure and corrections, thereby greatly improving data ef- ficiency (Setlur al., 2024). Therefore, the guiding hit must be carefully selected to find more paired responses. To accomplish this, we design simple yet effective heuristic for selecting the guiding solution. We refer to queries with an estimated value greater than 0.5 as easy queries and the others as hard queries. We then randomly select a correct solution for each hard query and incorrect one for each
Hit-Guided Exploration We assume a guide solution available for each question, which can be acquired by sampling from the policy. Continuing from the solution's 's intermediate reasoning states, explored responses natu- rally share common prefixes. This pattern implicitly helps assign credits to generated parts since the first steps are shared between completions. The key differences in correct- ness can, therefore, be identified in the later steps. In the meantime, as the first few steps are fixed, the search space

---

MARGE: Improving Math Reasoning with Guided Exploration
easy question. This solution is based on the simple intuition of increasing the likelihood of finding the right answer difficult question and possible failure cases to an easy one. Although this is rather simple strategy, we demonstrate with experiments in Sec, 1 I and theoretical analysis in Ap- pendix C to show that, in most cases in reasoning, applying helps increase the number of positive-negative pairs.
is calculated using r, of the responses gathered from the same intermediate state, and /3 is a coeffi- cient that balances policy gradient and the KL penalty,
where , r-mean(r:) std
4. Experiments
We design experiments to investigate three key research questions:
Another key factor is the onpoolicyssss of generated data. Self-generate responses that are on-policy improve LLMs better as there is no distributional shift between responses and the optimized policy (Lai et al., 2024). Therefore, in each iteration from the first iteration, we update the guidance hit with the latest generation to ensure it is on-policy and that the explored data are equivalent to directly sampled from the latest policy.
1. Does MARGE improve over baselines, and in which aspects, when controlling data and model parameters? (Sec. 4.2)
2. What are the benefits brought by introducing the hit- guided exploration strategy? (Sec. 4.3.1)
3. How do design choices affect the overall results of MARGE? (Sec. 4.3.2)
3.4. Iterative Improvement
4.1. Experiment settings
Dataset Composition As the exploration process is done on all intermediate states of a response, all explored rollouts can be written as D = {(I;, Stj, Vijks (ijkk> riyk)), where Vijk means the k-th response generated from the j-th intermedi- ate state Sij of query z,. whose reward is Tijk- We directly utilize D with all rollouts for RL training. While for DPO training, one correct response y* and one incorrect response y are sampled for each intermediate state to construct a preference dataset D- (II) Sij. Vijo Viz)) for DPO. We filter states with estimated values that are either too high or too low to reduce noise and stabilize DPO training.
Models We utilize Qwen2-7B-Instruuc Qwen2.5- 7B-Instruct (Yang et al.. 2024a), LLaMa3.1-8B- Instruct Meta, 2024), and MetaMath-Mistral 7B (Jiang et al., 2023; Yu et al., 2023) as our backbone models to conduct experiments due to their widespread popularity and strong baseline performances. Additionally, we include Qwen2.5-Math 70 Instruct (Yang al., 2024b), strong math-specific model. They cover models of different types and math reasoning capacities, which we believe help demonstrate the effectiveness of our method.
Policy training Having collected the dataset, we update (1) and use it as the reference with RL or DPO. For DPO, we use the correct response as Mwin and the incorrect one as Vlose to calculate the DPO loss, which can be formulated as:
Baselines We first compare our method with algorithms applying vanilla exploration. We include SFT and DPO as our baselines on all models. Standard RL methods are also included compare our method with other baselines. In particular, we compare method with PPO (Schulman et al., 2017) and REINFORCE++ (Hu et al., 2024). We also include an updated version of REINFORCE that applies all the settings in our RL training, but with vanilla exploration. We describe it as GRPO in the following sections, as this objective is equivalent to GRPO (Shao et al., 2024) when the GRPO epoch is 1.
the current policy Tg
C
1
Σ
[log (3 log
( x ① s)
D
Tref (y"
x
(w, JED
To Ty
1 1
3 log
Fer 1r +
where a is the sigmoid function, and 33 is parameter con- trolling the discrepancy of m&.
We also consider other potential exploration methods, in- cluding recent works incorporating step-level supervision or MCTS. We contrast our method with StepDPO (Lai et al., 2024) on Moven2-BB-nsstrcct, which shares a similar idea of finding step-level supervision but through GPT-4 super- vision. On MettaMath-Mistral based exploration method, MCTS-DPO (Xie et al., 2024), as baseline to showcase the efficacy of our exploration strategy over different types of related methods.
For RL, we set the reward for the correct responses as and 0 for incorrect ones. In addition the vanilla RE- INFORCE loss, we add several modifications to improve training quality. We first replace the reward for the responses with their group relative advantages, which are calculated as in GRPO (Shao et al., 2024). We also add KI. Divergence penalty to stabilize training, resulting in a loss function as
we reproduce an MCTS-
C
Σ (DD
[-Alog no (y/r @ s)] + (BLBBKLLT (Te))
Besides controlled experiments above, we include several concurrent works (Cui et al., 2025; Liu et al., 2024b) that promote L.MM reasoning through different perspectives, like
D
(4)
5

---

MARGE: Improving Math Reasoning with Guided Exploration
Table 1. Performance (pass@1 and pass@66 accuracy %) of different algorithms. The best result of cach dataset is in bold, the second best one underscored, and our model is marked in blue We greedily sample the responses for each query and run them three times to report the average. Evaluation prompts listed in Appendix E. Our method outperfomss bascline methods almost all datascts. More interestingly, our method improves pass @ 64 accuracy by a larger margin, indicating improvement of models' exploration abilities.
MATH
MATH500
GSMSK
College Math
OlympiadBench
Accuracy %
pass
pass@64
pass@
pass @
pass 64
pass@
pass 64
Qwen2-7B Instrrcct
53.18
59.92
85.67
22.13
25.13
20.65
24.98
SFT
55.98
61.04
84.76
24.74
26.86
21.03
25.38
DPO
57.24
63.44
85.90
31.64
35.72
20.88
25.83
PPO
58.70
61.98
88.47
35.72
38.44
21.82
24.54
REINFORCE++
59.81
63.58
88.19
35.58
38.28
24.49
25.62
GRPO
59.89
62.92
88.07
35,02
37.09
23.85
25.72
StepDPO-HF
57.78
63.54
87.90
30.92
32.36
22.91
24.19
MARGE-DPO
59.92
66.84
88.60
34.68
36.58
21.48
24.69
MARGE-RL
61.08
68.20
88.70
35.77
40.10
25.88
27.31
SitaMath-MMssrad
28.68
34,66
75.28
17.56
21.67
7.10
12.09
SFT
28.60
38.28
75.94
17.31
21.72
6.67
14.07
DPO
26.70
38.68
74.50
14.84
20.94
5.43
15.10
PPO
27.78
32.54
78.11
17.81
20.90
7.06
10.56
REINFORCE++
30.33
34.38
78.19
18.32
20.98
7.85
9.87
GRPO
30.76
37.08
79.27
18.38
22.39
6.67
11.55
MCTS-DPO
29.92
37.44
77.53
17.85
20.84
6.57
11.68
MARGE-RL
32.13
41.34
81.81
19.76
24.28
8.14
14.32
Llama3.1-8B-Mn -8Stttrruuct
49.96
70.33
85.97
28.11
37.34
16.34
34.47
SFT
50.72
64.96
86.37
30.03
39.10
16.89
34.41
DPO
50.36
71.54
86.68
27.39
36.77
15.75
36.29
PPO
50.50
65.18
85.06
26.38
34.22
15.75
28.39
REINFORCE++
52.27
67.14
86.93
28.72
35.84
18.37
35.11
GRPO
51.22
71.00
86.58
28.04
37.82
15,41
34.37
MARGE-RL
54.23
72.36
88.36
28.94
38.19
17.33
38.61
Qwen2.5-7B ----BBI-ssttctt
75.30
79.62
91.89
40.41
44.48
36.00
41.77
SFT
75.17
80.33
92.27
41.09
44.39
38.12
41.23
DPO
75.03
76.97
92.06
40.57
44.78
38.23
42.76
GRPO
76.24
81.14
92.34
40.72
43.68
38.07
40.64
MARGE-RL
76.74
85.16
93.02
41.12
44.18
39.70
43.21
a revised multi-stage SFT process. MARGE enhances the underlying exploration process RL to enable the scaling of self- self-generated responses for training. Therefore, they can potentially be combined, not counterparts, for future enhancement in LLM reasoning.
We filter the queries for which no suitable response was found, resulting in curated dataset of approximately 8,500 questions paired with model godel--gneerted solutions. the fol- lowing rounds, the guidance solutions selected similarly but directly from those generated in the previous round with- out additional sampling. If no appropriate solution exists for guidance, the guidance solutions for these queries are not updated.
Datasets For training, we start with the same subsets of MetaMathQA (Yu et al., 2024) and AQuA (Ling et al., 2017) as in StepDPO. Considering already high performance in these tasks, we respectively randomly sample subset of Omni-Math (Gao et al., 2024) and Big-Math(Albass Albalak et al., 2025)'s is training set.
Breen..5-B-Inntruun
For evaluation, we our method on two widely adopted benchmarks: MATH (Hendrycks al., 2021) and GSM8k (Cobbe et al., 2021), which include questions from grade school level to challenging competition problems. We also incorporate two more challenging datasets, Olympiad- Bench (He et al., 2024) and CollegeMath (Tang et al., 2024), to further test our model's generalizability on out-of- distribution challenging problems.
and M-122-55MM-----III-
To find guide solution to each training query in our method, we generate 32 responses for each query in the training set the beginning and select one as described Sec. 3.3.
6

---

MARGE: Improving Math Reasoning with Guided Exploration
Table 2. Performance (average of 3 runs) of MARGE and concurrent works hased on Qwen2.5-Mathh models. The best result is in bold, and MARGE is marked in blue MARGE significantly improves both the pass@1 accuracy and exploration ability over 1ren2.5-Math--1 In-steet. It also showeases better or comparable performances to the most advanced works at 7B level.
MATH
MATH500
College MATH
OlympiadBench
Accuracy %
pass
pass@1
pass@ 64
pass
pass@ 64
pass@)
pass@ 64
Qwen2.5-Math-77 Ma-ah----Instructt
83.48
83.33
86.40
40.80
48.64
46.95
48.62
PPO
83.37
83.26
86.12
40.75
47.14
47.05
48.63
MARGE-RL
84.46
85.04
89.92
41.58
49.49
47.40
49.02
ACEMath-7B (Liu et al., 2024b)
83.13
83,42
85.72
42.76
50.32
48.68
50.45
PRIME-HURUS-7B (Cui al., 2025)
80.08
80.70
88.58
40.99
58.96
48.22
51.97
Implementation Our experiments are done on 8 A100- 80GB GPUs. When generating responses during training, we set the temperature at 0.8 and the top at 0.95 to generate diverse responses, which are used to create training data sets or find self- eeff-generated solutions. Specifically, we use the vLLM (Kwon et al., 2023) engine infer the policy model.
the necessity of adequately exploring challenging problems that require longer reasoning horizons.
Most notably in Tab. 1, Tab. 2 and Fig. 4, when MARGE improves both pass and pass k; the performance gap widens as ls increases, indicating enhanced exploration ca- pabilities. This finding is further validated through con- tinued training experiments. Running REINFORCE++ on the MARGF-traiine Qwen2 model improves MATH accu- racy to 62.34%, surpassing the 59.81% % ceiling achieved when starting from the base Instruct model. This sug- gests MARGE training enhances both reasoning capabilities and solution diversity, allowing access to previously unex- plorable response possibilities. This improvement suggests that during the MARGE training process, the model not only gains better reasoning capabilities but also develops additional diversity in its solution strategies, accessing pre- viously unexplorable response types for the original model.
For DPO training and baselines, we set B = 0.4 and global batch size of 256. For RL training and baselines, we set the coefficient for KL loss as 0.01 and sample 8 responses per state (or query for RL baselines). For both our methods and baselines, we run for 10 episodes and apply carly-stopping. More hyperparameters and implementation details are in Appendix B.
4.2. Results
Metrics We evaluate models using two key metrics. First, we test single-shot Chain-of-Thought (CoT) accuracy (pass@1) I) across all datasets. Second, we assess multishot accuracy (pass@) @ k) to measure model's exploration ability. Pass@k k represents the model's precision when given multi- ple attempts to solve questions, indicating its ability to ex- plore diverse reasoning paths. We visualize the exploration ability by comparing pass @ k improvement over pass @ in Fig. Due to computational constraints, we conduct pass @K k testing on MATH500 (Lightman et al., 2023), which found effectively represent the complete MATH test set. We also evaluate pass @K & on CollegeMath and OlympiadBench, excluding GSM8k due to its relative simplicity.
4.3. Ablation Study
To validate the effectiveness of MARGE, we conduct an extensive ablation study to justify key design decisions of our method. Ablation studies are conducted on the Qwen2- 7B- Instructt model with the same training query set.
4.3.1. BENEFITS OF HIT-GUIDEE EXPLORATION
It enables more training data First, show that exploration method helps find more effective training data than vanilla exploration. We measure the number of valid pairs with the entropy of training data. Higher entropy indicates a larger ratio of possible correct-incorres pairs among all data, which beneficial to improve L.LM as discussed in Sec. 3.3. We show how the entropy changes as the sampled responses grow in Fig. 5a. We compare vanilla exploration and hit-guided exploration with different hit selection strategies, including:
Main Results Our main results? 1 in Tab. and Tab. 2 demonstrate consistent performance gains across model ar- chitectures and benchmarks. MARGE also generalizes ef- fectively to more difficult
test sets. It outperforms its vanilla, externally supervised, and MCTS- based exploration strategy counterparts by large margin. As Tab. 1 shows, MARGE's improvements are relatively more significant on complex tasks like MATH, indicating
1. Ours: Selecting guidance with the heuristic discussed in Sec. 3.3, where we randomly select correct responses for hard questions and incorrect responses for easy ones.
For baseline methods, if an open-source model is available, we evaluate it as model. Otherwise, we reproduce their method on our models with our training queries.
2. Random: Randomly select response.
7

---

MARGE: Improving Math Reasoning with Guided Exploration
pooo0g 1/4 on MATH300
0.70
0.75
Method
0.40
0.70
0.85
SFT
DPO
0.60
0.60
0.80
REINPORCE++
0.30
0.55
GRPO
0.25
0.75
Qwen2
DettaMatb-Mistry
1Lama3.1
Qwen2.5
Figure 4. @ass@1 I (solid) and pass @4 (shaded) of different methods on the MATH100 test set. Pass indicates the ability to explore multiple reasoning paths. The figure displays the improvement pass@ 64 over pass@1 the shaded area, symbolizing the models' ability explore. When MARGE enhances both pass@1 and pass @k the performance gap larger as l grows. It demonstrates that, instead trading off exploration abilities for pass@1 improvement, MARGE also enables hetter exploration process than haselines and thus fundamentally improves exploration ability.
reasoning step. When applying the same amount of data, our method covers all reasoning horizons and explores more effective data for optimizing LLM, particularly as the steps go backwards.
training set entropy
0.3
Average Poliry Valuue
0.46
0.44
0.2
Vanilla
base
0.1
Ours-Raie Rand-Rand
hit tit-quidance
0.40
4.3.2. ABLATION STUDIES
Ours-Succ
w/ hit-quidance
0.0
Ours
0.38
Generation Amount Our method enables the discovery of more useful training data the same of queries, thus paving the way for successfully scaling self-generation for training. Therefore, to better control variables, we test how increasing the number of seff-generated data for training influences the results of different algorithms. For SFT and DPO, we increase the number responses (pairs) for each query; for RL baseline, we increase the number of rollouts per query. This done so that the total generated tokens roughly match those in the MARGE training.
100
5.0
average generated response:
Step
(a)
(b)
Figure 5. (a): The change of training dataset entropy with number of responses sampled. Our method continues to find new useful pairs when generating more responses. completing intermediate states does not yield full responses, we convert them based on the number of tokens. (b): Hit-guided explored data improves average state value at every reasoning step compared to vanilla exploration, particular later ones. The values are estimated over 32 Monte Carlo simulations.
Table 3. Ablation study on the amount of training data. We in- clude their best performance and the performance when they use the same amount of data as MARGE in Tab. We annotate the fraction data used to achieve the hest performance after best :. Results showcase the importance of exploration when scaling self- generated data.
3. Suce: Randomly select correct response.
The results demonstrate that hit-guided exploration con- tinues to uncover more pairs than vanilla exploration as more responses are generated. Besides, comparing different guidance selection strategies highlights the importance of selecting appropriate guidance for exploration. If not, the exploration performance might drop the vanilla level.
College Math
Olymplad Bench
MATH
GSM8k
best: 1/4
57.66
86.65
24.94
22.22
SFT
sume data
57.36
86.02
24.12
20.74
It helps improve on all reasoning steps To further demonstrate the benefits of hit- iit-guiied exploration, we aim
best:1/16 $7.24
85.90
31.64
20.88
DPO
data
$1.38
83.77
33.01
18.66
to validate that it improves over baselines at all reasoning steps, particularly the final ones. We test this hypothesis with two DPO experiments. The only difference the way training sets are collected: one uses hit-guided explo- ration, while the other uses vanilla collection. We estimate the policy state value V* of all intermediate steps from MATH500 collected by Qwen2-7B: In-trruct.t Aggregating over queries, we plot the estimated value of different steps in Fig. 5b and note that, while both versions of DPO sig- nificantly improve the state value on all steps, DPO with hit guidance data exhibit advantages starting from the third
best:2/5
88,32
35.58
24.49
REINFORCE
data
59.79
87.94
33.43
24.15
The results in Tab. 3 demonstrate that adding more data to the baseline methods does not constantly improve the reasoning ability. In contrast, it might even deteriorate spurious correlations occur. This further underscores the importance of efficient exploration and better credit assignment and the effectiveness of our method in achieving these goals.
8

---

MARGE: Improving Math Reasoning with Guided Exploration
Table 4. Ablation study different guidance selection strategies. The results are single-shot accuracy (%). The results indicate that better hit selection strategy achieves hetter exploration and improves the final result, and on-policy solutions play a crucial role in obtaining better exploration.
ploration ability allows it continue improving.
While our method utilizes more generation computation, it is our goal and contribution to scale up the computation to make the most of the current query set. High-quality prob- lems are getting harder to acquire. Therefore, we develop MARGE with a stronger exploration ability to find more high-quality training samples on the same query set. Possi- ble ways reduce the computation cost of MARGE exist, like removing unnecessary states from the Monte Carlo estimation.
College Math
Olympiad Bench
Strategies
MATH
GSM8k
Ours
61.08
88.70
35.77
25.88
Random
60.21
88.6
35.06
24.96
Suce
59.91
87,59
35,06
23.51
No Update
59.54
88.09
35.54
24.36
Hit Selection As demonstrated above, correctly selecting the guidance trajectory helps improve exploration efficiency by finding more valid preference pairs. Here, we further validate its effects on final performances and compare dif- ferent hit-selection strategies. We include another No Up- date off-policy baseline, where we fix the guidance solution once selected the same way as ours in the first round. We train MARGE with RL and calculate the accuracies of the four datasets as in Tab. 4. As we can infer from the table, our designed strategy performs better than other selection strategies. It can also be inferred that updating guidance helps improve performance, indicating the essentiality of on-policy solutions for exploration and policy improvement.
6. Conclusion and Future Work
In this work, we identify and tackle the challenges of enhanc- ing LLM reasoning through self-training. Our investigation identified ineffective exploration as critical bottleneck in generating high-quality reasoning data, particularly for complex, multi-step tasks. To address this, we introduced MARGE, a novel method that systematically leverages self- generated solutions to improve data exploration and credit assignment across reasoning stages. Extensive experiments and ablations demonstrate that MARGE achieves substantial performance gains. Moreover, our method surpasses exist- ing baselines by enhancing exploration diversity as well, exhibiting larger gains in pass @ k than pass@1. 1. These re- sults underscore the effectiveness of MARGE in improving exploration and scaling self-training pipelines for LLM rea- soning. We discuss the explicit scaling effects of MARGE detailedly in Appendix D.
5. Computation Cost
Compared to vanilla exploration methods, MARGE natu- rally introduces more generations when other parameters are controlled (like number of samples per prompt, training set size, etc.). It changes the coefficient of time complex- ity, but not its asymptotic behaviour. Once the number of intermediate states n is fixed, MARGE incorporates around (n + 1)/2 times more generation and training amount, as completing intermediate states generally requires fewer to- kens. Statistics show it is approximately 3.3 on Qwen2, Llama3. 1, and MetaMath, with around states per query, and 4.9 Qwen2.5, with around 8 states per query.
While MARGE demonstrates significant improvements, it still has several points for future improvements. First, MARGE's 's performance gains converge after adequate it- erations (though more than baselines), which is likely due to the deterioration of generation quality during optimiza- tion. Addressing this issue without compromising reasoning gains is an interesting topic for future research. Second, though validated to be effective for mathematical reasoning, MARGE's s exploration strategy is relatively simple and has not been tested in other domains. Extending it to diverse application tasks could further enhance its impact.
Table 5. The results of MARGE and some baselines are shown when MARGE uses less computation, such that the training time is roughly the same.
College Math
Olympiad Bench
Impact Statement
MATH
GSM8k
PPO
58.70
88.47
35.72
21.82
This paper presents work that aims to advance the fields of large language models (LLMs) and Reinforcement Learn- ing (RL), in particular LLM reasoning. In particular, the developed algorithm makes it easier to explore the large state space and refine credit assignment during LLM reason- ing. However, if our method is misused for inappropriate scenarios, might cause LLMs to behave and respond un- expectedly.
REINFORCE
59.81
88.32
35.58
24.49
MARGE 60.67
88.10
35.81
25.28
Tab. 5 presents the results of MARGE and some baselines Qwen2 when MARGE uses less computation, such that the training time is roughly the same. MARGE exhibits certain advantages over baselines. However, as shown in Tab. 3, with more generations, baseline methods performances saturate or even deteriorate, while MARGE's improved ex-
9

---

MARGE: Improving Math Reasoning with Guided Exploration
References
Twelfth International Conference on Learning Represen- lations, 2024. URL https:
Corum?id-Epott/yT https://openrevieww wpwnrevieeeeeeeeeeeeeeeeeeeeeeee
net/
Aeta. Llama 3 model card. 2024.
URL
https://github. wtt.:/i...oooooooooooooo.ooeeeet aas--lamaaalln blob/main /MODEL CARD.m
He, C., Luo, R., Bai, Y., Hu, S., Thai, I.., Shen, J., Hu, J., Han, X., Huang, Y., Zhang, Y., al. Olympiadbench: challenging benchmark for promoting agi with olympiad- level bilingual multimodal scientific problems. arXiv preprint arXiv:2402. 14008, 2024.
Albalak, A., Phung. D., Lile. N., Rafailov, R., Gandhi, K., Castricato, I.., Singh, A., Blagden, C., Xiang. V., Mahan, D., and Haber, N. Big-math: A large-scale, high-quality math dataset for reinforcement learning in language mod- cls, 2025. URL httph::////// /ttp///axvvvv... org/ aww.ab/.. /50 17387.
Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, Measuring math- ematical problem solving with the math dataset. NeurlPS, 2021.
Chen, G., Liao, Li, C., and Fan, K. Step-level value pref- erence optimization for mathematical reasoning, 2024.
URL https: pettps::/arxa/ /aaxiiiii..../.a.//aaaaa/aaaavva org/ a 6 10858.
Hu, J., Wu, X., Zhu, 7.,, Xianyu, Wang, W., Zhang, D., and Cao, Openrlhf: easy-to-use, scalable and high-performance rihf framework. arXiv preprint arXi::2405.11443 2024.
Chen, W. Ma, X., Wang. X., and Cohen, W. W. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks, 2023. URL https: /arxiv..vvvv.////// org/ abs 22122211111 12588.
Jaech, A., Kalai, A., Lerer, A., Richardson, A., El-Kishky, A., Low, A., Helyar, A., Madry, A., Beutel, A., Car- ney, A., et Openai ol system card. arXiv preprint arXh::2412.1677 2024.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert. M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers solve math word problems. arXiv preprint arXiv:2110.1444 14168, 2021.
Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, S., Casas, d. I., Bressand, F., Lengyel, G., Lample, G., Saulnier, L.., al. Mistral 7b, arXiv preprint arXiv:2310.06825, 2023.
Cui, G., Yuan, L., Wang, Z., Wang, H., Li, W., He, B., Fan, Y., Yu, T. Xu, Q. Chen, W., al. Process re- inforcement through implicit rewards. arXiv preprint arXiv:2502.01456, 2025.
Jiao, F., Qin, C., Liu, Z., Chen, N. F., and Joty, S. Learning planning- reasoning by trajectories collection and process reward synthesizing, 2024. URL https:// arxiv.org/aai /2002/40222222 00658.
DeepSeek.
Unleashing su- percharged reasoning power. https: //api-docs. deepseek. com/newst htt///wwsll. 1200, 2024. Accessed: 2024-12-29.
reepseck-rl-lite-preee
Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, H., Gonzalez, J. E., Zhang, H., and Stoica, Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium Operating Systems Principles, 2023.
Feng, X., Wan, Z., Wen, M., Wen, Y., Zhang, W., and Wang, Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17199 2023.
Florensa, C., Held, D., Wulfmeier, M., Zhang, M., and Abbeel, P. Reverse curriculum generation for reinforce- ment learning. Conference on robot learning, pp. 482- 495. PMLR, 2017.
Lai, X., Tian, Z., Chen, Y., Yang, S., Peng, X., and Jia, J. Step-dpo: Step-wise preference optimization for long- chain reasoning of llms, 2024. URL http:t//s://aae org /abs/////// www.a///..... 18629.
Gao, B., Song, F., Yang. Z., Cai, Z., Miao, Y., Dong, Q., Li, L., Ma, C., Chen, L., Xu, R., Tang, Z., Wang, B., Zan, D., Quan, S., Zhang, G., Sha, L., Zhang, Y., Ren, X., Liu, T., and Chang, B. Omni-math: A universal olympiad level mathematic benchmark for large language models, 2024. URL https:tt//..m / aawiiiiiii..////////.aaaaaaaaaiv org/ / 2410.44100. 07985.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike. J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step, 2023. URL https: //arxiv.orgge abs 2tabb//3300 2200 20050.
Ling, W., Yogatama, D., Dyer, C., and Blunsom, P. Program induction by rationale generation Learning to solve and explain algebraic word problems, 2017. URL https: / //arxiv. www./oaa/////oooooo..o........ee 1705. 04146.
Gou, Z., Shao, Z., Gong, Y., yelong shen, Yang. Y., Huang, M., Duan, N., and Chen, W. ToRA: tool-integrated rea- soning agent for mathematical problem solving. In The
10

---

MARGE: Improving Math Reasoning with Guided Exploration
Liu, H., Zhang, Y., Luo, Y., and Yao, A. C.- C. Augmenting math word problems via itera- tive question composing. ArXiv, abs/2401.09003, 2024a. URL https: stt.ap...attttccsoo....... #Te/CorrpuID:227000
Salimans, T. and Chen, R. Learning montezuma's re- venge from single demonstration. arXiv preprint 2018.
Schulman, J., Wolski, F. Dhariwal, P., Radford, A.. and Klimov, O. Proximal policy optimization algo- rithms, 2017. URL https:/ /arxiviiivv//v/////v//////////aa iisivooo orgg /
Liu, Z., Chen, Y., Shoeybi, M., Catanzaro, B., and Ping, W. Acemath: Advancing frontier math reasoning with post- training and reward modeling. arXiv preprint, 2024b.
1707.0633
Setlur, A., Garg, S., Geng, X., Garg, N., Smith, V., and Kumar, A. RI incorrect synthetic data scales the effi- ciency of llm math reasoning by eight-fold. arXiv preprint arXiv:2406.1 14532, 2024.
Lu, Z., Zhou, A., Ren, H., Wang, K., Shi, W., Pan, J., Zhan, M., and Li, Mathgenie: Generating synthetic data with question back-translation for enhancing math- ematical reasoning of Ilms. ArXiv, abs/2402.16352, 2024a. URL http::/:s//.p...mantnisiisssesss www.stticsccooll......... org
Shao, Z., Wang, P., Zhu, Q., Xu, R., Song. J., Bi, X., Zhang, H., Zhang, M., Li, Y. K., Wu, Y., and Guo, D. Deepseekmath: Pushing the limits of mathemat- ical reasoning in open language models, 2024. URL https: http://aaxvvvvv.. org/ abs 240.224222222 03300.
Lu, Z., Zhou, A., Wang, K., Ren, H., Shi, W., Pan, J., Zhan, M., and Li, H. Step-controlled dpo: Leveraging stepwise error for enhanced mathematical reasoning, 2024b. URL https: / /arxivv....///////////a/////aavl org/ abs 2407. 00782.
Stiennon, N., Ouyang, L., Wu, J., Ziegler, D. M., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. Learning to summarize from human feedback, 2022. URL https: //axxiv///vvv..////aa org/ /ttg/aa///////ooooo/////o///aaae wwtpaaaa...././ 2009. 01325.
Luo, L., Liu, Y., Liu, R., Phatale, S., Guo, M., Lara, H., Li, Y., Shu, L., Zhu, Y., Meng, L., Sun, J., and Rastogi, A. Improve mathematical reasoning in language models by automated process supervision, 2024. URL https: //arxiv. org/ abs / 2406.000000000 000666.666 0692.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, I.., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, Training language models follow instructions with human feedback, 2022. URL https: //arxiv. org/ /bs//200 02155.
Tang, Z., Zhang, X., Wang, B., and Wei, Mathscale: Seal- ing instruction tuning for mathematical reasoning, 2024. URL https: //tp///aaavvv///a////a//eaeeaaaa www.wawwww.aaaaaaaaeeeoooooooooe abs///a///// 24033. 22004.0804....... 02884.
von Werra, L., Belkada, Y., Tunstall, L., Beeching, E., Thrush, T., Lambert, N., Huang, S., Rasul, K., and Gallouédec, Q. Trl: Transformer reinforcement learn- ing. https://gittiee wtw.thu..coomheeee www.oo/ggoggaaeeeeoooooooooooeee trl, 2020.
Qi, Z., Ma, M., Xu, J., Zhang, L. L., Yang, F,, and Yang, M. Mutual reasoning makes smaller lims stronger problem- solvers, 2024. URL https:/ /ttp://aaavvv.//aa org/ abs/ 2408. 06195.
Wang, E., Cassano, F., Wu, C., Bai, Y., Song, W., Nath, V., Han, Z.,, Hendryx, S., Yue, S., and Zhang, H. Planning natural language improves I1m search for code generation. arXiv preprint arXiv:2409.03733 2024a.
Qwen. Qwq: Reflect deeply on the boundaries of the unknown, November 2024. URL https: //wwelmm. github. (ttthbb.hhhblllo/rrg------eeerer
Wang. P., Li, L., Shao, Z., Xu, R., Dai, D., Li, Y., Chen, D., Y.Wu. and Sui, Z. Math- shepherd: Verify and reinforce llms step-by-step without human annotations. ArXiv, abs/2312.08935. 2023. URL https: /ppi. semanticscholl org/ /ts///oopuIID:26620777
Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, C. D., and Finn, C. Direct preference optimization: Your language model is secretly a reward model, 2024. URL https: / /ttp///axvvvv//a org/ abgg/bb/////ooo 2305 18290.
Rasley, J., Rajbhandari, S., Ruwase, O., and He, Y. Deep- speed: System optimizations enable training deep learn ing models with over 100 billion parameters. In Proceed- ings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 3505-3506, 2020.
Wang. Z., Li, Y., Wu, Y., Luo, L., Hou, L., Yu, H., and Shang. J. Multi-step problem solving through verifier: An empirical analysis on model-induced process super- vision. In Al-Onaizan, Y., Bansal, M., and Chen, Y.N (eds.), Findings of the Association for Computational Lin- guistics: EMNLP 2024, pp. 7309-7319, Miami, Florida,

---

MARGE: Improving Math Reasoning with Guided Exploration
USA, November 2024b. Association for Computational
Zelikman, E., Wu, Y., Mu, J., and Goodman, N. Star: Boot- strapping reasoning with reasoning. Advances Neural Information Processing Systems, 15:15476-15488 2022.
Linguistics. doi: 10.1 10.:8653/112024.fnddnn------ 429. URL https:tp///// /a///alaanni Eindings-emm.p..499
Zhang, D., Zhoubian, S., Hu, Z.,, Yue, Y., Dong, Y., and Tang, Rest-mets*; Lim self-training via process reward guided tree search. arXiv preprint arXiv:2406.cm 240.:24006.., 2024.
Wei, J., Wang, X., Schuurmans, D., Bosma, M.. Ichter, B., Xia, F., Chi, E., Le, Q. and Zhou, D. Chain-of- thought prompting elicits reasoning in large language models, 2023. URL https://aaa /tatpi///axiv.... wrw. abs/ 2201. 11903.
Xi, Z., Chen, W., Hong, B., Jin, S., Zheng, R., He, W., Ding, Y., Liu, S., Guo, X., Wang, Guo, H., Shen, W., Fan, X., Zhou, Y., Dou, S., Wang. X., Zhang, X., Sun, P., Gui, T., Zhang. Q. and Huang, X. Training large language models for reasoning through reverse curriculum reinforcement learning. 2024.
Xiang, V., Snell, C., Gandhi, K., Albalak, A., Singh, A., Blagden, C., Phung, D., Rafailov, R., Lile, N., Mahan, D., Castricato, L., Franken, J.-P., Haber, N., and Finn, C. Towards system reasoning Ilms: Learning how think with meta chain-of-thought. 2025. URL https: //arxiv. org/ abs/ 2abb/2550 2501 04682.
Xie, Y., Goyal, A.. Zheng, W., Kan, M.-Y., Lillicrap, T. P., Kawaguchi, K., and Shieh, M. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint arXiv:2455.0045 2024.
Yang, A., Yang, B., Hui, B., Zheng, B., Yu, B., Zhou, C., Li, C., Li, C., Liu, D., Huang, F, et al. Qwen2 technical report. arXiv preprint MxXx::2477.167111 2024a.
Yang, A., Zhang, B., Hui. B., Gao, B., Yu, B., Li, C.,, Liu, D., Tu, J., Zhou, J., Lin, J., Lu, K., Xue, M., Lin, R., Liu, T., Ren, X., and Zhang, Z. Qwen2.5-math techni- cal report: Toward mathematical expert model via self- improvement, 2024b. URL https:: http::://axxx.orrrrp/p abs/2409.12122.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models, 2023. URL https: //wviv. org/ abs/ 2305. 10601.
Yu, L., Jiang, W. Shi, H. Yu, J., Liu, Z., Zhang, Y., Kwok, J. T., Li, Z.,, Weller, A., and Liu, W. Metamath: Boot- strap your own mathematical questions for large language models. arXiv preprint arXiv:2309.1222
2023.
Yu, L., Jiang, W. Shi, H., Yu, J., Liu, Z., Zhang, Y., Kwok, J. T., Li, Z., Weller, A., and Liu, W. Metamath: Bootstrap your own mathematical questions for large language mod- els, 2024. URL https:tp.............. / arxiv. org/ abs abs/2309. 2309. 12284.
12

---

MARGE: Improving Math Reasoning with Guided Exploration
A. Algorithm
Algorithm 1 MARGE
Input: Policy language model TT; training query set Dp; number of episodes M; query batch size B; KL. loss coefficient
3; Monte Carlo simulation number n; initial responses generation number n1; output reward function r.
1: D --eeerate policy(Dp, mT,
b Generating ni hit candidates for all queries
2: for 1. M do
3: select_guidance_son
Di Sec 3.3: select a guiding solution for each question
4: for query batch D; from D of size B do
5:
S < get (Da)
> get states of the guidance solutions in D; D Sec 3.3: generate n completions for all states in S with policy To b Sec 3.2: estimate state values D. Sec 3.4: train policy with objective Eq. for DPO or Eq. for RI. Sec 3.3: update guidance candidates with latest responses Use the updated policy
6:
A + generate Soteicty,pplicy(SSS, ne. n1)
7:
V f estimate state values(S..A)
8:
T/ f train( D,V)
9:
D update (its((A)
10: No T/B
11: end for
12: end for
Output: Trained policy T
B. More Implementation details
B.1. Our method
Our implementation is based on TRL (von Werra et al., 2020) and DeepSpeed (Rasley et al., 2020) framework. We utilize the vLLM (Kwon et al., 2023) engine to do inference.
We apply two ways to obtain the intermediate states of guidance hit. The first way is to divide the response with special delimiters within the response the models generate, like Step i: We leverage special prompts to generate such a pattern, as further discussed in Appendix E. In Qwen2-7B-Instruut, this way results in an average of 4.42 states per question. In Qwen2.5-7B Instructt,, more difficult problems incorporated for training, resulting in average of 9.08 states per question. Another way is to split the response directly based on the number of tokens. We evenly split 5 states from the guidance responses for other models. This is chosen based on the final performance of the models.
When collecting rollouts with hit-guided exploration, we set the following sampling parameters: temperature as 0.8, top as 0.95, top_k as 1. For each state, 8 responses are collected. During RL training, we set the learning rate as 10-6 and batch size as 1024 to stabilize training. We set the coefficient for KL divergence as 0.01 and train the model with context length of 2048. We train the collected dataset for epochs within each iteration. During DPO training, we ,3 to 0.4. We set the learning rate as 5 10-7 with batch size of 256. Within each iteration, we train on the collected dataset for 4 epochs, with maximum length of 2048.
B.2. RL baselines
We train PPO and REINFORCE+ baselines with OpenRLHF (Hu et al., 2024). Some key parameters listed in Tab. 6. Some parameters are different from our method we tuned them for better performance. For example, the sampling parameters are different as PPO and REINFORCE+ with OpenRLHF fail to converge when the same ones are applied. We implement GRPO with TRL (von Werra et al., 2020) similar to our method, only differing in the way collecting rollouts. The parameters GRPO are the same as our method.
B.3. DPO
The training data for DPO are collected in the same way as in our method. We form preference pairs by randomly selecting correct and incorrect responses collected. We train DPO baseline with TRL (von Werra et al., 2020). We set = 0.4 and a global batch size of 256. The learning rate is 10-?
13

---

MARGE: Improving Math Reasoning with Guided Exploration
Table Some key parameters for RL. haselines PPO and REINFORCE++.
value
KL penalty coefficient
0.01
Samples per prompt
Actor learning rate
5 10-7
Critic learning rate
9 10-6
Discount Factor
Training batch size
512
Rollout batch size
64(PPOy1 64(PPO)1 (28RREINFORCE)
Clip ratio Maximum length
0.2
2048
Sampling temperature
1.0
Sampling top P
1.0
SFT
The training data for SFT are collected in the same way as in our method. A randomly selected correct response for each query is used to run SFT. We set the learning rate to 5 x 10-5 batch size to 128.
B.5. Other baselines
StepDPO (Lai et al., 2024) We directly utilize the open-source model provided
MCTS-DPO (Xie et al., 2024) We reproduce MCTS-DPO using its official repository' on the same training set as ours. We reproduce on MetaMath-Misttrl--B in their paper, with their default parameters. We did include it in the Qwen models as we failed to run it successfully after many times of trials.
C. Theoretical Analysis
In this section, we aim to provide a theoretical analysis of the foundation and effectiveness of MARGE.
In Proposition C.1, we first demonstrate that using a correct (or incorrect) solution as guidance increases the expectation of acquiring correct (or incorrect) responses, which lays the foundation for the motivation of hit-guided exploration. This intuitive phenomenon is empirically demonstrated in both previous works in RL (Florensa al., 2017; Salimans & Chen, 2018) and in Figure 3. Here, we view such empirical conclusions from the viewpoint of theory.
fewatiffunntion Proposition C.1. Suppose S₁ @ . @ Sn is a generated response. R(g, S $ ..... @ S.)) is the reward function that gives 1 if and only if S1 + ... @ Sn is a correct solution to q; otherwise R = O. Under the condition that it a randomly sampled correct response, we have:
B| < E is from correct response] S... [ Sn are from correct response).
If it is incorrect response, then:
R 2 S is from an incorrect response)
SI ... Sn are are from an incorrect response).
Let's start with E < S for correct responses. As in language generation, the process is of a discrete setting. What's more, S, + + S, is randomly sampled from all correct responses, with little bit of notation abusing for abbreviation, we can denote [R is from correct response] E, E[ Es, P(R = 1|S)) 1). Consider
Proof.
14

---

MARGE: Improving Math Reasoning with Guided Exploration
[[ E[R] by Bayes' theorem, we have:
B[ E[R]
Σ P(R (1 Σ 1(R==1(S)P((S)
S1
81
Σ P(R 1|S)) P(R = 115:))(S))
Σ = ((R))()))P(())
P(R=1)
(5)
S1
Es, P(R =
(Es, P(R=11())P(STT
P(R=) =
Var(P(R = Var(P(R=1|5.) 1|5:))
P(R 20 O,
so [[R]S 2 B[R]. Similarly, we have ERR S1, .I.,... Sy] SI.......... Sy-1.. Therefore, for correct response.
E [ S E..
(6)
We denote a new reward function Rt for incorrect ones, such that R' 1 R all queries and responses. Therefore, similar to the deduction above, we have:
| 2 T[
Subsituting back R R', we will have B[R R). Iterating such process, we will have
E
> E R
E S..
for incorrect guidance solutions.
In the following part, aim to showcase the effectiveness in exploring more data of the hit-selection strategy in Section 3.3. First, under the hypothesis that the change of S1......... St Sjj in Proposition C.1 is linear to we show a sufficient condition
for exploring more correct and incorrect pairs within the same number of responses in Proposition C.2. This linearity hypothesis is generally reasonable, shown by the empirical results in Figure 3 and et al. (2024). The statistics in Figure show general compliance with the conditions in Proposition C.2. The results in Figure 5a that directly reflect the dataset's pairs further validate the reasonableness of the hypothesis and the effectiveness of our method.
Proposition C.2. Suppose S₁ O + Sn is the generated response sampled for hit- hit-guided exploration, and k is an intermediate state. Suppose A [ Sj] . is constant j changes. Let tut Guided be the number of valid correct-incorrec pairs introduced by hit-guided exploration, and Vanilla be the number of valid correct-incorrect pairs introduced by vanilla exploration. Then
2E[R]
2k(k + 1) n k
2A
is sufficient condition that hit- hit-guided exploration introduces more valid pairs than vanilla exploration, i.e.
EHit-Guided ivanilla-
(8)
Proof. Suppose we sample m responses in each state. As we only consider responses that share the same prefix, then the total number of valid pairs is
HHit-Guided min(EE E[R)mm + Σ min (Ei]) ..... S.), II ..... S.1)m.
For vanilla exploration, within m(n + 1) responses, the number of valid pairs is
Vanillaa = (n + 1) min(E[R] E[RR)m.
Let's first consider the E R case, where Evanilla (n + 1)mE
15

---

MARGE: Improving Math Reasoning with Guided Exploration
When $1 + ... + Sn incorrect response, in Proposition C.I, B[R[S ... S.] S B(R],
" Σ min S.], 1 StiDs..,,,,,mm Σ E| S.lm S nE|R
"
Therefore, using an incorrect response for hard queries with an estimated value smaller than 0.5 cannot improve exploration.
the other hand, let's consider the case when S @ ... + Sn correct response. Since A is the slope for linear improvement our hypothesis. by Proposition C.1, for arbitrary we have
+A. = E 5.] R
(9)
In addition, we denote Pa = R for clearity. Consider k
11 [1]2 2A
Then for all i S k. I , s 3. and for
all i > k; . 2 2. and
Hin-GGudded m
- m
p.).
1=0
i=
To make MHtt-Gidddd 2 Vanilla- need to ensure that
Eiti Guided
Vanilla
m
Pt
+ m > (1
p.) - (n 1)mp 2 0.
(10)
1=0
1=
Substitute Equation (9) into Equation (10), we have
1
HHit-Guided
Vanilla = m
1 + m Σ (1 2p iA).
(11)
imk
Therefore, we need to ensure that
Σ i (1 2po i
(12)
k-k 1)
(k+ 1 + n) k). A + (n--))( 2po) 2 0.
2
As Po S k. S simplifying Equation (12):
k(k: + 1)
(k + 1 n) - kk)
A (n k)(1 2po)
2
n²
=(k² + k:
)A + (n (m- -2p))
2
n n
2k2 +
A
2
Therefore, sufficient condition for the exploration be effective is
(1.2 + 4: n² + n2 A 2 0
2
(13)
n + 1) - 2k(k + 1).
In the E[R] > case, the same result can be obtained similarly. When S ① ... S, is an correct response, we have Pr. 2 ... 2 P1 2 Pa 2 1. Then dHic-Guided = m (1 -1-11111)) pt) < mmn+ +1)1=111111 - Po) #vanilla indicating that the hit-guided strategy worse than the vanilla strategy when using correct guidance.
2.
16

---

MARGE: Improving Math Reasoning with Guided Exploration
When S₁ ( ... + Sn is an incorrect response, under the linear hypothesis, we have p, Po -AA Considering the same k, have for i ki Pr 2 2. and for i > k. Ps 2- To make dita Guided
2 Vaaillla need to ensure that
Hut-Gedded
Vanilla
(1 pi) + m Σ Pi
(n 1)m ppo)
(14)
i=U
t=k
k
m
A m
(2po
1A) N
Equation (14) is anologous to Equation (12), only differing in the sign - 2po. Therefore, the condition in Equation (13) also sufficient in the case where po > Therefore, it is sufficient condition for the hit-selection strategy in Section 3.3 to find more valid pairs.
In the last part, we view the benefits of MARGE's s exploration strategy from the viewpoint of policy optimization. We aim to show in Proposition C.3 that, when using sampled self-generated solutions as guidance, the variance of the policy gradient estimation decreases in expectation, resulting in improved policy optimization. Our analysis is based on REINFORCE for simplicity, but similar results may also be found with other optimization algorithms.
Proposition C.3. Suppose Yo = $1 ① 82 @ ... @ 8M are gelf-geee guidance solutions for all queries E Q. Let ( denote the MARGE policy gradient estimator from the objective in Equation (4), conditioned on guidance solution Yo: Let g[0) denote the policy gradient estimator of vanilla exploration. When the number of rollouts T the same, the variance of the MARGE gradient estimation is lower in expectation, i.e.
By, Var [o S Var, [7].
(15)
Proof. For the objective in Eq 4, the vanilla policy estimator ]|0] can be written
Q Σ Σ
(r(q. v)) - log (B 4)) + log ( log (3(l))) VEQ:=I....
where ys are randomly sampled responses from the policy, and q is a query in the query set Q. Suppose yi can be written as the concatenation of random variables at different steps y: St @ ... @ Sar. In the following part, let f(g, v1) rqq. )4) log (yal)) + log (e(g))g) for simplicity.
The policy gradient estimator g[0] obtained with our method with guidance Yo can be written as
0 = MMN
Σ Σ
Σ Σ
f(g, so ① ... + sy ① Viy) Vo log so
VEQ i.........NN D.......-1
Here, we define so the empty string, and Viy represents a response sampled to complete from step j.
We define a random variable that conditions on Yo as follows:
g Yo
F(g, e D 1 Vo
s;).
Q
g ly, represents the gradient when given query q and the first i steps of corresponding guidance Yo (i.e. 80 ..... 8)).
...
In this case, we can represent Y and ğ(Ø) with gi as:
Σ
Σ
No:
MN
N
M
(16)
MN
0 =
Σ g:0)
MN
t=1
17

---

MARGE: Improving Math Reasoning with Guided Exploration
We modify the number of Monte Carlo samples N to MN of O match the number of samples of [ Since samples collected independently, the variance of the policy gradient estimator can be written
Var, vr.
Varlg (Yo,
M
5 a.......
Var- M
M M
Now we want to show that Ey, Varlg - Varlg for j 2 0. Let's consider the relation between g lr. and gy-
gu+t1lyo = gb)) Yo.8,11=93011
By the law of total variance, we have
Varlg [Yo Varlies, |g S3+1 sj+1ll + Bs, [Var S3+1 ss+ill.
As variance is non-negative, we have:
Varl 2 Es Varlg
Since the guidance solution Yo is randomly sampled from the policy's s generation, its transition probability the same the one during Monte Carlo samples. This means completing an intermediate state from the guidance equivalent directly sampling from the start. Thus, we have:
Var(g 2 Es, Varlg Yol 2 Es..s, Varlg 2 St..S....... Var(g [Y],
Varlg(0) 2 Ey, Var Yol, Vj = 0, 1........ M.
Therefore,
By, Var, Var,pro l0l%o I Var
Remark C.4. Based on the proof in Proposition C.3 (Equation (16)), may even conclude that, if the guidance solution Yo sampled from the policy, then the MARGE gradient estimation is unbiased in expectation over Y,. However, as only select one solution for each query, in our case, the bias of the MARGE estimator is not zero. Nevertheless, this issue can be mitigated by using multiple guidance solutions for each query when more computation is available.
D. Scaling Trends of Self-Training
Based on our results of training different algorithms on Qwen2-Instrucct we find that, before performance saturation, the logarithm function y e + 02 In best describes the scaling trend between consumed self-training samples and the resulting performance before performance saturation. When using the accuracy on MATH500 an indicator, we have the fitted trends shown in Tab. 7 and Fig. 6. The metrics above clearly showcase the effectiveness of MARGE in improving scaling training data. The other algorithms are excluded as they saturate too fast to gain enough datapoints for regression.
Table 7. The fitted coefficients for different methods
C1
C2
MARGE
2.287 GRPO
53.05
1.302 52.92
SFT(RFT)
54.89
0.99
18

---

MARGE: Improving Math Reasoning with Guided Exploration
MATH 500 accuracy %
62
60
MARGE
54
GRPO
RFT
52
60
80
self-generated training responses per query
Figure 6. The fitted line and datapoints for different methods
E. Prompts
For evaluation, we adopt their default chat template for Bwen2-7B-Instruce Qwen2.5-7B- ----truutt and Llama3, 1-8B-Instruch The prompt is adopted as follows.
Prompt for Evaluation
[Question]
Please reason step by step, and put your final answer within {boxed{).
For MetaMath-Miittrl-755 we use the same Alpaca format as their official repo*.
Prompt for Evaluating MetaMath Mistrall- model
Below is an instruction that describes a task. Write response that appropriately completes the request.
#### Instruction: ( [Question}
Please reason step by step, and put your final answer within \boxed
#### Response: Let's think step by step.
During training, divide guidance solution into multiple reasoning steps by identifying special tokens counting token number. In the case of identifying special delimiters like "Step i:", need ensure the model outputs in structured way. Here, add CoT prefix "Let's think step by step. \n Step 1: to the model's output. It ensures the output follows the format and contains the delimiters required. We apply this technique to the Qwen2-7B-Ingee Instructt and Qwen2.557BBIInttmee models.
F. Case Study
In this section, provide illustrative example of how MARGE works with Qwen2-7B Siven--BB-Instruct in Figure 7 and with -- in Figure 8.
G. Failure Analysis
Based on our theoretical analysis and empirical results above, MARGE is capable of improving the exploration process and finally the reasoning ability of L..M. However, there are still outlier cases when the model fails to accomplish such goals. Here, we focus on two typical types of failure, from the experiments on Qwen2-7B-Instruee
19

---

MARGE: Improving Math Reasoning with Guided Exploration
uery: In how many ways can 4 bl black and white chess pieces be arranged row such that they occupy alternat places? Assume that the pieces are distinct.
Guidance:
Rollouts
State O:state valuev
Let's think step by step.
Example rollout: wrong:
Strp Establish the pa pattom plac ement Given reguimeentt that pieces must occupy al tsmate places, if we place a piace first, W-B-W. B-.......uu to the fixed positions and distinct nature of the whi pi pinces, does not contribule addilionn permulalions for the white gi pieces (since they are fixed their 'odd' posilions) So, the lotal number of amagenents is the of araagements for each scenatto: 1/24 120 1441 The final mswer W'borred (144)1)
Step Understand the arrangement.
We have 4 black pieces and 5 white pieces, and they must be ananged in altemating fashion. Since there are more white pieces, we start with a white piece and then alternate.
sequece must follow
Step 2: Calculate the total spots for pieces. We h a total of spots for the pieces to be placed in (4 for black and 5 for white..
State 1: state value 0.375
Step 3: Calculate the ways to arrange the black and w white pieces. The black pieces will oocupy the ev spots and the white pieces will occupy the odd spots.
State 2: state value v 0.125
State 3: state value 0.625
Exa mple rollout: correct:
Step 4: Calculate the arrangements for black
Slep 4: Calculate the number of ways to amaage the black pieces. arranged in (/40)
black piaces, they can since each piece dislinc Slep 5: Calcul sto the num ber of to amange the whith pieces. There white pieces, and they can arranged VSS)) ways since each piece distinet Step Calcalate total wumber of ways to acrange both black and white pieces. Since the arrngern ent of bock multip
pieces.
There are 4 black pieces, and they need to be placed in the even spots out of 9. The number of ways to choose 4 spots out of 9 for these pieces is (C(9, 4).. Howev er, since each black piece is distinct, we sho uld calculate the araangemen as (4!)) ways instead of (C((, 4)1, given there are black pieces and they are distinct. So, for the black pieces, there are ((41) anangements
plecees and white piene are independent, the number of ways to araage each set. 1. text! Total arrage black pueces) VexttWWay Ways to amange while pieces) 1) Mext Total ways] #4 tá
ways -text
VSStep 7: Compute the factorials.
V. 41 = Vimes Wimes Mimes = 24 M 51 tá times 4 tá timess 3 tā 2 mes = 120 Stop 8:
Step Calculate the arrangements for white pieces.
Cal the total nomber arangements. texti Total ) = times 120 2880 ) Therefor: answer (2000d)
Similarty, there are white pieces, which need be placed the spots out number of way s to arange these 5 distinct pieces is ((51).
State state valuey 1.0
Step Combine arrangem ents InSince the arrangement of black pieces and white pieces are independent. ents, we multiply the number ways to amaage each set of pieces find the total number arangements. InluThus,
State 3: state value v 1.0
Example rollout: correct:
Step Calculate lotal arannements. arrangements is the product of the amangements black and white pieces, pieces can pair with each arangemeet of white gieces. il Total arrangements) - itmes 51 24 itims 120 2880, 1] Therefore,
number
each arangement black
total number of way' the pieces can be arranged in altematiig fashion is/m Witme litimes 120 2880.8))oimm RininSS, the answeris W (280X)
number of ways black and white chess pieces can be aranged row such that they occupy altemate places is 1 (2000)0, answer (s: $1bored
An illustrative example of how MARGE works with Qwen2-7B-Instreee In this example, we use the delimiter " Step i: to divide the guidance solution into reasoning steps. particular, to make sure the generated responses comply with the delimiter format, we add the CoT prefix for generation on all states. The arrows connect intermediate states with the exploration process from that state, including generated responses that complete prefixes and corresponding value estimation. hit, visualize 3 states in detail, showcasing randomly selected rollout at this state. On each state, sample 8 responses to complete and estimate the state value. display estimated value and randomly selected rollout an example. The example state 0 partially omitted for better visualization.
Figure 7.
intermediate states in the guidance
20

---

MARGE: Improving Math Reasoning with Guided Exploration
uery: sb lodat
(Mracc 2icdo fff Nycdotifracl (1c6)t(fac(166((1 Idotsm
(1024))))))))))))) (1) Jlimes((frac(])) (6)ooofffaccc (9)odoffrree1 H2 and $o 78, calculate value of $a lodot + c
G ance::e:
Rollouts
## Stop First, we need calculate the v value a, To find the value a we simply substitute the given expression into the equation. $a 5a=2%% 2-225 '5. So, Step 2: Next, let's simplify the value Looking at the expression for that there many fractions multiplied together. The first of fractions be simplified follows: 11
State Osstate value 0.125
Example rollout: wrong:
Strp Calculate value of 25S,, $a 12mnes Vtress 2 yames yames 2 326. Stop 2 Calculate
32s.
so 1679616 =11179052 as Step 8: Calculate the value of $2 sc = 496. AM Slep Calculale the final nesltt The value Sa $(1024) (11770332) (49)S. # Step 10: Perforn the addition find final result $1024 11770352 11 7804766 then add 49, $11 $11780476
lodot +c 2 equais
7805255.
The finel
(1788525)
lodotifrac 41 ceoo Bicdotifrac (16) Idotsm Ifrac (1 H512 2edottifrcccc (10oottfaaac1022200001 (1))).
This is pattem where every other fraction cancels out, leaving us with $tfrac (1)s after multiplication.
State 1: state value 0.125
## Step 3: Now continue simplifying the
State 2:
state value 0.625
value of by evaluating the remaining multiplication in its ex expresion. Next, we have
Example rollout: correct:
Mrac ( Prddatt 2152) Simplily this sequence of fractions which becomes $1fra (1) Step
S(Vfrac (B)
Combine the results from the prevtous steps to smplity the value Curther. the sets of fractions the expression
1frac (18 Medotifrac (1) (2 Simplifying this, we get $ifrac ss Step 4: Now we multiply the two simplified parts of b together. We multiply (4)rac(4))118 (1)S by $ifrac (1/22$$ which equals
combine the resulls of $273 0.58
(0/1) (1/21s. We revill this
equals Stpp Evaluste
7S. ## Step Plag the values of b and into the equation Su
25, We plag the calculated values the given equaion: 532
7 + #t Step 7: Perform expometiiaion and mul liplication. Calculal the expomeaationn $32"2 10248 and $7 495. thmbettcc operations Calculate product 16 and $16 1125. 40 Step 9. Add and subtract the calculated according A dd the num bers in the equation $ $1024 + 112 495. #* 10: Compute the addition. $1024
** Step 5: Calculate the value of Since $h 2h3 lodot 28, we can rewrite b $2
Continue wi
[3+1} = 2 So, sb 16$.
## Step 6: Calculate the value of c. Sc 7s, so we don't need to do any thing here. #* Step 7: Substibute the values of b, and into the original equation Sa '2 + lodot + c 2$.. Now we plug in our calculated values:
operstion.
496 equal to 1185. The final answer is $iboxed (1185)
$32"2 + 16 ledot??
State 3: state value 1.0
722$.
# Step 8 Evaluate each part of the equation.
State 4: state va value 1.0
First, we calculate $32"2 100==0200 1024$. Then wec alculate $16 lodot 7 112s. Finally, we calcul ate $7 495.
Example rollout: correct:
725, ## Stop & Perform the artthm attc in expression " lodot
Caloal dle each tem
sepanilely: $32"2 10245, $16 todol 1125 and $7 495. Then add thesr tomm together. #5 Stop Combime results the previous stop
#b Step 9: Plug these values back into equ ation and solve, $1024 + 112 + 49 1185s. answer is: Stboxe
solution. $1024 112 49 11856 The final answeris $ibooe
Figure 8. An illustrative example of how MARGE works with Llama3.1-8B- 1-8B--nnttruct. In this example, we split the guidance based on the total token number. We derive intermediate states such that the token number in each intermediate state forms an arithmetic sequence. The arrows connect intermediate states with the exploration process from that state, including generated responses that complcte the prefixes and corresponding value estimation. Of the intermediate states randomly selected rollout at this state. On each state, we sample 8 responses to complete it and estimate the state value. We display its estimated randomly selected rollout as an example. The example state partially omitted for better visualization.
guidance hit, we visualize 3 states detail, showcasing a

---

MARGE: Improving Math Reasoning with Guided Exploration
1. queries that trained model failed answer;
2. cases where our model failed find more preference pairs.
Wrong Solutions We select a sample from the MATH test set, which the trained Qwen2-7B-Inse checkpoint failed to solve, We mark wrong reasoning with red.
A Failed Case from MATH
Joe was charge lights for a dance. The red light blinks every two seconds, the yellow light every three seconds, and the blue light every five seconds. If include the very beginning and very end of the dance, how many times during seven minute dance will all the lights come the same time? (Assume that all three lights blink simultaneously at the very beginning of the dance.)
Question:
The three lights blink simultaneously seconds after the start of the dance and only is a common multiple of 2, 3, and 5. Recall the common multiples a set of integers are precisely the multiples of the least common multiple. Since 2, 3, and are relatively prime, their least common multiple is 2 5 = 30. Thus the light blinks seconds after the beginning of the song for 0, 2....... 14, and after 14 thirty-second periods, the song ends. Thus the lights blink unison a total of 15 times.
Correct Solution:
To find out how many times all three lights (red, yellow, and blue) come at the same time during seven-minute dance, we need to determine the least common multiple (L.M) of the blinking intervals of the three lights: 2 seconds, 3 seconds, and 5 seconds. This LCM will give us the interval at which all three lights blink simultancously.
Model Output:
Prime Factorization:
2
-3 -3=3 3
55
The LCM of set of numbers is found by taking the highest power of all prime numbers appearing in the factorization of these numbers.
2. Calculate LCM:
The prime numbers involved are 2. 3, and 5.
The highest power of each prime number in the factorizations is 2 31, and 5
Therefore, the LCM is x 3 5
x 3 x 30.
This means all three lights blink simultaneously every 30 seconds.
3. Convert Dance Duration to Seconds: A seven-minute dance lasts 7 60 420 seconds.
4. Calculate Number of Simultaneous Blinks: To find out how many times all three lights blink simultaneously during the 420 seconds, divide the total time by the interval:
420
14
30
Thus, all three lights come on the same time 14 times during the seven-minute dance. The final answer is
Invalid Guided Exploration As discussed in Appendix C, MARGE may not discover more valid training data when scaling generation unless the requirements are satisfied, especially when the intermediate state values increase (or decrease) too fast. Here, we showcase query, along with its intermediate states, that fails to gain the exploration bonus because of this. As demonstrated, this is caused by the fact that many later states have state values of 1 (or 0). Designing mechanisms filter out ineffective guidance unnecessary states potentially improve this framework.
Question: In a zoo there are 30 penguins, 22 zebras, and 8 tigers with some zookeepers. If the total number of heads are 132 less than the number of feet, the number of zookeepers
22

---

MARGE: Improving Math Reasoning with Guided Exploration
State (state value:0.125) Let's think step by step.
Step
State I: (state value:0.375) Understanding the information given:
There are 30 penguins. Penguins have feet each.
There are 22 zebras. Zebras have 4 feet each.
There are tigers. Tigers have 4 feet each.
-There are some zookeepers, but we don't 't know how many yet. Let's denote the number of zookeepers as Z.
Step 2:
State (state value: 1) Calculating the total number of feet:
Each animal and each zookeeper has feet each. So, the total number of feet is:
Total feet (30 2)
(22 4) (8 + (Z 2)
Total feet 60 88 + + 2Z
Total feet 180 22
Step 3:
State 3: (state value: 1) Calculating the total number of heads:
Each animal and each zookeeper has head. So, the total number of heads is:
Total heads = 30 + 22 + + Z
Total heads 60 + Z
Step 4:
State (state value: 1) Using the given information:
We're told that the total number of heads is 132 less than the number of feet. This gives the equation:
Total heads 132 Total feet
60 + 132 180 22
Step 5:
23


Reviews:
[{"review_id": "CfHLHODmAc", "reviewer": "Reviewer_GXc7", "summary": "The paper introduces a hit-guided exploration method to enhance LLMs’ mathematical reasoning by systematically exploring intermediate reasoning states. Using Monte Carlo simulations for better credit assignment, MARGE improves accuracy and reasoning diversity across multiple benchmarks without needing extra value models, making self-training more effective.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable reviews! We are more than happy to learn that you find our method to be well-motivated, contain reasonable and comprehensive results. Here we appreciate the chance to address your concerns.\n\n# W1: lacks failure analyses\n\nThank you for your advice to improve our work! We also believe adding failure analyses will further enhance our work. Here, we plan to add failure analyses on:\n\n1. special queries that our trained model failed to answer;\n2. special cases where our model failed to find more preference pairs.\n\nHowever, due to the limitation on the rebuttal length, we are unable to provide you full examples here. We will add this part as a chapter in the appendix in the updated version.\n\n# W2: does not show an explicit scaling trend\n\nThank you for your advice! An explicit trend can better showcase MARGE's improvement and we will update it in the revised paper. Based on our data points on Qwen2, we find the logarithm function $y=c_1+c_2\\ln(x)$ best fits the scaling trend between MATH500 accuracy $y$ and number of training samples $x$. We find the following coefficients for different methods:\n\n- MARGE: $c_1=53.05, c_2=2.287$;\n- GRPO: $c_1=52.92, c_2=1.302$;\n- RFT: $c_1=54.89, c_2=0.99$.\n\nThe metrics above clearly showcase the effectiveness of MARGE in scaling training data. We plot the data points as well as fitted scaling lines in the figure [(link)](https://anonymous.4open.science/r/MARGE-ACE8/explicit_scaling_trend.png). We only include three lines for clarity of the picture, and we will include the results of other algorithms in the paper.\n\n# Comment\n\nThank you for your suggestion! More explanation here will make our paper clearer. We will update the caption of Fig. 2 to the following:\n\n> Average accuracies when starting from different intermediate states of correct solutions (blue) and incorrect ones (red) with Qwen2-7B-Instruct. A larger state index indicates being closer to the end. On average, completing from a correct (incorrect) state increases the portion of correct (incorrect) answers, which boosts the exploration of more training data.\n\n# Q1: computation cost\nThank you for your advice! Adding a discussion on computation cost is important for the integrity and rigor of our work, and we will include this part in the revised version.\n\nCompared to vanilla ways (DPO, SFT, PPO, ...), our method increases the number of prompts to generate when other parameters are controlled. We argue that MARGE only changes the coefficient of the time complexity but **not its asymptotic behavior**, thus is acceptable in practice. This coefficient is determined by the number of intermediate states for each query. In our experiment results, it is ~3.3 on Qwen2, Llama3.1, and MetaMath where there are about 5 states per query, and ~4.9 on Qwen2.5 with about 8 states per query.\n\nPossible ways to reduce the computation cost of our method also exist, like removing unnecessary states from the Monte Carlo estimation. We believe this can be an interesting topic for future works.\n\nIn Tab. 2, we present the results of MARGE and some baselines on Qwen2 when MARGE uses **less** computation, such that the training GPU time is **roughly the same**. In such cases, our method still exhibits advantages over baselines.\n\n**Table2:**\n\n| Acc %     | MATH  | GSM8k | CollegeMATH | OlympiadBench |\n| --------- | ----- | ----- | ----------- | ------------- |\n| PPO       | 58.7  | 88.47 | 35.72       | 21.82         |\n| REINFORCE | 59.81 | 88.32 | 35.58       | 24.49         |\n| MARGE     | 60.67 | 88.10 | 35.81       | 25.28         |\n\nHere, we want to emphasize that, while our method utilizes more generation computation, it is our **goal and contribution** to **scale up** the computation to make the most use of the current query set. High-quality problems are getting harder to acquire. Therefore, we develop MARGE, with stronger exploration ability, to find more high-quality training samples.\n\nAs we demonstrate in Tab. 2 of our paper, adding more computation for baselines results in overfitting and degradation in performance. As recent progress in LLM inference, we believe adding up computation to automatically improve models is becoming the more feasible and promising way, highlighting the contribution of MARGE.\n\n# Q2\n\nHere we use n=8 samples for value estimation. Higher Monte Carlo samples (n) provides more accurate value estimation and may yield better results. But at the same time, it leads to a linear increase in the number of generated tokens, decreasing training efficiency. We choose n=8 to balance this two effects.\n\nWe hope these clarifications and additional illustrations address your concerns!", "claims_and_evidence": "Yes. Experiments support most claims in the paper.", "methods_and_evaluation_criteria": "Yes. Datasets are proper to the task.", "theoretical_claims": "It is in appendix C.", "experimental_designs_or_analyses": "Yes\nThe main result is comprehensive and reasonable.\nAblation study looks reasonable.", "relation_to_broader_scientific_literature": "The paper differs from most previous RL methods.\nThe hit-guided exploration strategy is well-motivated, ensuring better coverage of reasoning steps.\nThe use of Monte Carlo simulation is widely used in many methods and is computationally efficient.\nIterative guidance updates ensure on-policy data generation, improving model alignment.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. The paper compares against the most popular RL methods on widely used models.\n2. The ablation studies confirm that hit selection strategy and guidance updates significantly impact performance.\n\nWeaknesses:\n1. The paper lacks failure analyses.\n2. The paper claims MARGE enables scaling self-generated responses more effectively but does not show an explicit scaling trend.", "other_comments_or_suggestions": "1. The caption of Fig. 2 needs more explanation.", "questions_for_authors": "1. MARGE avoids additional value models, but how does its computational cost compare to DPO, PPO, or GRPO?\n2. How many Monte Carlo samples (n) are used for value estimation (Eq. 2)? How does it relate to training efficiency?", "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": "KtYNtYf8JD", "reviewer": "Reviewer_SZQi", "summary": "The paper introduces MARGE (Math Reasoning with Guided Exploration), a framework to enhance mathematical reasoning in Large Language Models (LLMs). It addresses two fundamental challenges in LLM reasoning: the scarcity of high-quality training data and the difficulty of exploring reasoning paths effectively. Unlike traditional self-training approaches, which often suffer from spurious correlations in self-generated datasets, MARGE introduces guided exploration to improve data diversity and reasoning accuracy. The core idea is hit-guided exploration, where intermediate reasoning states from self-generated solutions are systematically explored, leading to improved credit assignment and scalability in training. The paper provides extensive experimental results showing that MARGE improves both single-shot accuracy (pass@1) and exploration diversity (pass@k) across multiple benchmarks and backbone models.\n\nThe highlight to me is that the method can keep the reward on policy compared to other pretrained PRM, yet the problem is the on-line computation cost.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful review! We are glad to learn you find MARGE to be novel, keep reward on-policy, and be reasonably evaluated. Here, we appreciate the chance to address your questions.\n\n# Claims and Evidence: not convincingly significant\n\nWe conducted experiments with models of different abilities to demonstrate the effectiveness of our method. MARGE not only increases the pass@1 accuracy of models. More interestingly, it is capable of significantly increasing pass@k accuracy and improving the model's diversity, which is a trend not seen in most post-training methods.\n\nWe conduct new experiments using **Qwen2.5-Math-7B-Instruct**. As models like this often undergo extensive and successful RL post-training, achieving further gains can be challenging[1], making this a good test case to showcase MARGE's effects. Due to its high reasoning ability, we randomly sample ~14k queries from the BigMath[2] dataset as training queries. Results (average of 3 runs) are below. We didn't test pass@64 on MATH due to its large size.\n\n**Table 1**:Performance Comparison on Math Benchmarks  Pass@1 / Pass@64 Accuracy (%)\n\n| Pass1/64 Acc (%)         | MATH@1 | MATH500       | OlympiadBench | CollegeMath   |\n| ------------------------ | ------ | ------------- | ------------- | ------------- |\n| Qwen2.5-Math-7B-Instruct | 83.48  | 83.33 / 86.40 | 40.80 / 48.64 | 46.95 / 48.62 |\n| PPO                      | 83.37  | 83.26 / 86.12 | 40.75 / 47.14 | 47.05 / 48.63 |\n| **MARGE (Ours)**         | 84.46  | 85.04 / 89.92 | 41.58 / 49.49 | 47.40 / 49.02 |\n\nThese results show MARGE effectively improves performance even on strong, instruction-tuned models. Besides the improvement on pass@1, MARGE also yields large improvements on pass@k, indicating its benefit in enhancing **exploration diversity** and finding a wider range of correct solutions.\n\n# Missing references:\n\nThank you for your kind reminder of these works! We will include these two works in the first part of our related works, where we discuss process supervision methods in LLM reasoning.\n\n# W1: computation cost\n\nThank you for your advice! Adding a discussion on computation cost is important for the integrity and rigor of our work, and we will include this part in the revised version.\n\nCompared to vanilla ways (DPO, SFT, PPO, ...), our method increases the number of prompts to generate when other parameters are controlled. We argue that MARGE only changes the coefficient of the time complexity but **not its asymptotic behavior**, thus is acceptable in practice. This coefficient is determined by the number of intermediate states for each query. In our experiment results, it is ~3.3 on Qwen2, Llama3.1, and MetaMath where there are about 5 states per query, and ~4.9 on Qwen2.5 with about 8 states per query.\n\nPossible ways to reduce the computation cost of our method also exist, like removing unnecessary states from the Monte Carlo estimation. We believe this can be an interesting topic for future works.\n\nHere, in Tab. 2, we present the results of MARGE and some baselines on Qwen2 when MARGE uses **less** computation, such that the training GPU time is roughly the same. In such cases, our method still exhibits advantages over baselines. We compare the results when baselines utilize more computation in Tab. 2 of our paper.\n\n**Table2:**\n\n| Acc %     | MATH  | GSM8k | CollegeMATH | OlympiadBench |\n| --------- | ----- | ----- | ----------- | ------------- |\n| PPO       | 58.7  | 88.47 | 35.72       | 21.82         |\n| REINFORCE | 59.81 | 88.32 | 35.58       | 24.49         |\n| MARGE     | 60.67 | 88.10 | 35.81       | 25.28         |\n\nHere, we want to emphasize that, while our method utilizes more generation computation, it is our **goal and contribution** to **scale up** the computation to make the most use of the current query set. High-quality problems are getting harder to acquire. Therefore, we develop MARGE, with stronger exploration ability, to find more high-quality training samples.\n\nAs we demonstrate in Tab. 2 of our paper, adding more computation for baselines results in overfitting and degradation in performance. As recent progress in LLM inference, we believe adding up computation to automatically improve models is becoming the more feasible and promising way, highlighting the contribution of MARGE.\n\nWe believe MARGE contributes to enhancing LLM reasoning through improved exploration. We hope these clarifications and additional results address your concerns!\n\n[1] Gao, Jiaxuan, et al. \"On designing effective rl reward at training time for llm reasoning.\" arXiv preprint arXiv:2410.15115 (2024).\n\n[2] Albalak, Alon, et al. \"Big-Math: A Large-Scale, High-Quality Math Dataset for Reinforcement Learning in Language Models.\" arXiv preprint arXiv:2502.17387 (2025).", "claims_and_evidence": "Some of the statements are supported but may not be enough.\n\nBased on the numbers presented in the tables, the gain of MARGE is not convincingly significant. And the computation cost was not fully discussed in the paper.", "methods_and_evaluation_criteria": "The method and evaluation benchmarks, metrics are reasonable.\n\nThe benchmarks are mostly math but pretty comprehensive.", "theoretical_claims": "The Proof MERGA in the Appendix C to approve the method unbiased is correct.", "experimental_designs_or_analyses": "The design of experiments are valid.", "relation_to_broader_scientific_literature": "The paper builds on prior work in LLM self-training and reinforcement learning for reasoning.", "essential_references_not_discussed": "Multi-Step Problem Solving Through A Verifier: An Empirical Analysis on Model-Induced Process Supervision, EMNLP 2024\nImprove mathematical reasoning in language models by automated process supervision, 2024\n\nboth papers has similar ideas as Math-Shepherd of using monte carlo estimation (hit-guide) to rate the partial solutions for math problems. The cost of running the experiments are discussed in those papers.", "other_strengths_and_weaknesses": "Strength:\n1. The method keeps the reward on-policy which is critical for process supervision.\n\nWeakness:\n1. This method will increase the computation, yet not fully discussed in the paper.", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "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": "CHZLbsSoUM", "reviewer": "Reviewer_8oFv", "summary": "The paper presents MARGE, a method that improves the self-training of Large Language Models (LLMs) in math reasoning. MARGE relies on “guided exploration,” reusing partial solutions (“hits”)—correct or incorrect—to fix shared prefixes while varying subsequent steps. This stabilizes the generation of positive and negative examples in multi-step math tasks. Experiments show significant gains over baselines (SFT, PPO, DPO) on benchmarks like MATH, GSM8K, and OlympiadBench, with improved pass@1 and pass@k accuracy. ## update after rebuttal", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable review! We are glad to learn that you find MARGE to be effective, contains empirical gains, and has extensive ablations and theories. We appreciate the opportunity to clarify the points raised.\n\n# W1: choosing hit selection in cases where no correct or wrong answers are generated\n\nThank you for your question regarding the hit selection method.\n\n1. Cases with No Correct Answers Generated\n\nWe agree with your insightful point that promoting exploration, especially when no correct answers are initially found, is crucial. We believe this question contains two key points: at least get one answer correct, and decrease the difficulty to find them.\n\nThe first key point remains a fundamental challenge, dependent on both exploration strategies and the backbone model's capabilities. Our current approach, consistent with recent reasoning works[2,3], is to increase the number of i.i.d. samples generated per query to improve the probability of finding a correct trajectory. Empirical results on Qwen2 demonstrate:\n- At 32 samples: ~300/8888 questions lack correct answers\n- At 256 samples: only 20 questions remain without valid answers\n\nWe remove remaining unsolved cases from training, leaving them to more capable models.\n\nFor the second point, as shown in Fig. 5, once a valid answer is sampled, MARGE greatly improves the exploration efficiency and surpasses baselines.\n\n2. Cases with No Incorrect Answers\n\t- This indicates problems are \"too easy\" for the current model\n\t- We exclude them from training as they provide limited learning value, and focus more on challenging cases.\n\n# W2: failed cases as the guidance hits\n\nWe appreciate your concern about our rationale for using incorrect responses as guidance hits for easier questions. Here we answer your questions and clarify our motivation:\n\n*If we start from a wrong intermediate point, no matter how the latter process is, we still get a wrong answer*\n\nWe respectfully disagree based on our findings and concurrent works[1,2]. LLMs possess the potential to recover from wrong intermediate points and reach a correct final answer. Exploring data to reinforce such ability is a key goal of MARGE. We quantify this effect as follows.\n\nAs it is hard to decide the wrong states, we suppose states, where the estimated state value drops the most, are the false ones. We count the ratio of these states that could be recovered from, and the accuracies when completing them. We also count them when failures are at the first step.\n\n| | recoverable wrong step % | Acc % of recovery | recoverable wrong first step % | Acc % of recovery (first step) |\n| -- | -- | -- | -- | -- |\n| Qwen2 | 73 | 44 | 83 | 54 |\n| Llama3.1 | 74 | 36 | 88 | 46 |\n| MetaMath | 51 | 21 | 73 | 33|\n| Qwen2.5 (different queries) | 65| 35 | 80 | 62 |\n\n*If the failure point lies in the first step, does it mean that all generated roll-outs are wrong?*\n\nNo, as the table above demonstrates (columns 3 and 4), models can often recover even when the error occurs at the very first step.\n\nWhile wrong intermediate states do decrease the expected accuracy (as implied by the red line in Fig. 2), the possibility of recovery exists and is valuable. By selecting failed cases as negative guidance hits, we increase the portion of wrong rollouts for easy problems. These rollouts provide valuable learning targets for models' robustness: \n- Showcase common mistakes of models,\n- Demonstrate ways to avoid or even correct errors.\n\nWe validate the effectiveness of selecting wrong hits as guidance for exploration (Fig. 5) and final results (Tab. 3). Therefore, we believe this design choice is well-motivated and experimentally supported.\n\n# Q1: Assumption about the whole process is correct\n\nNo, we don't assume this. Here, we want to express that the reward (in Prop C.1) is 1 iff the final answer given by $(S_1\\oplus\\cdots\\oplus S_n)$ is correct. Trajectories with corrected intermediate errors are valid positive examples and help improve the model's reasoning abilities.\n\n# Q2: Handling queries without suitable hits found\n\nWe progressively sample more responses for queries with no suitable hits found, as discussed detailedly in W1. Currently, we sample up to 256 responses. We discard the queries if they still get no suitable hits, the same as concurrent works[2,3]. Once a suitable hit is found, MARGE greatly improves exploration.\n\nWe believe MARGE contributes to enhancing LLM reasoning through improved exploration. We hope this rebuttal clarifies our method and addresses your concerns that led to your decision not to recommend acceptance of our work. We look forward to your feedback!\n\n[1]Jaech, Aaron, et al. \"Openai o1 system card.\" arXiv preprint arXiv:2412.16720 (2024).\n\n[2]Guo, Daya, et al. \"Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning.\" arXiv preprint arXiv:2501.12948 (2025).\n\n[3]Cui, Ganqu, et al. \"Process reinforcement through implicit rewards.\" arXiv preprint arXiv:2502.01456 (2025).", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The paper relates to the training of reasoning capability of LLMs.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths** \n- Directly addresses spurious correlations in self-generated data. \n- Demonstrates clear empirical gains over various baselines. \n- Provides extensive ablations and theoretical insights on why guided exploration yields richer training data.\n\nWeaknesses:\n- The method of choosing hit selection is still ambiguous in cases where no correct or wrong answers are generated. Due to its high frequency, it is not trivial to skip this point, especially for cases with no correct generated answers where exploration should be promoted.\n- The statement “This solution is based on the simple intuition of increasing the likelihood of finding the right answer to a difficult question and possible failure cases to an easy one” does not hold all the time. If we start from a wrong intermediate point, no matter how the latter process is, we still get a wrong answer, right? It is a bit confusing why you chose the failed case as the hit. If the failure point lies in the first step, does it mean that all generated roll-outs are wrong?", "other_comments_or_suggestions": "No", "questions_for_authors": "- Do you assume that if the final answer is correct, then the whole process is correct? If yes, is it in conflict with Proposition C.1 at the point  “The reward function that gives 1 if and only if \\( S_1 \\oplus \\cdots \\oplus S_n \\) is a correct solution to \\( q \\).”\n- How do you handle queries where no suitable correct or incorrect “hit” is found?", "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": "Sa8iitf4nk", "reviewer": "Reviewer_QKKW", "summary": "This paper introduces MARGE, a framework for guided exploration in LLM mathematical reasoning for self-training pipeline.\nIt uses solution-guided exploration with MCTS and RL to find high-quality data, resulting in better exploration and credit assignment.\nSpecifically,\nfor each question it has a response, use rule based \\n to split the response into states then from each state to finish the response and collect correct/incorrect labels, and then estimate state values based on labels, then train the policy using RL and update response.\nIn experiment using different LLMs and on different math dataset, they show it improves accuracy compare to baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review! We are happy to know you found MARGE to be novel and contribute to math LLM RL. Here, we appreciate the chance to address your questions.\n\n# W1: lack of experiments using Qwen2.5 Math based model:\n\nThank you for your advice! To demonstrate MARGE's effectiveness on state-of-the-art math models, we conducted new experiments using **Qwen2.5-Math-7B-Instruct**. As models like this often undergo extensive and successful RL post-training, achieving further gains can be challenging[1], making this a good test case to showcase MARGE's effects. Due to its high reasoning ability, we randomly sample ~14k queries from the BigMath[2] dataset as training queries. Results (average of 3 runs) are below. We didn't test pass@64 on MATH due to its large size.\n\n**Table 1**:Performance Comparison on Math Benchmarks  Pass@1 / Pass@64 Accuracy (%)\n\n| Pass1/64 Acc (%)         | MATH@1 | MATH500       | OlympiadBench | CollegeMath   |\n| ------------------------ | ------ | ------------- | ------------- | ------------- |\n| Qwen2.5-Math-7B-Instruct | 83.48  | 83.33 / 86.40 | 40.80 / 48.64 | 46.95 / 48.62 |\n| PPO                      | 83.37  | 83.26 / 86.12 | 40.75 / 47.14 | 47.05 / 48.63 |\n| **MARGE (Ours)**         | 84.46  | 85.04 / 89.92 | 41.58 / 49.49 | 47.40 / 49.02 |\n| ACEMath                  | 83.13  | 83.42 / 85.72 | 42.76 / 50.32 | 48.68 / 50.45 |\n| PRIME-EURUS              | 80.08  | 80.70 / 88.58 | 40.99 / 58.96 | 48.22 / 51.97 |\n\nThese results show MARGE effectively improves performance even on strong, instruction-tuned models. Notably, MARGE also yields larger relative gains on pass@k compared to pass@1, underscoring its benefit in enhancing **exploration diversity** and finding a wider range of correct solutions.\n\n# W2: no reference results included\n\nThank you for pointing this out. Our initial tables focused on **controlled** comparisons within our experimental setup for clarity. We agree context is valuable and have now included reference results from recent literature (AceMath, PRIME-EURUS) in Table 1 above for comparison. We additionally test their pass@64 with open-source models. We will add them together in our revised paper.\n\nWhat's more, we also want to emphasize MARGE's specific contribution: **improving exploration efficiency** to enable **scaled self-training**, reflected in both pass@1 and pass@k gains. This contribution is complementary to concurrent methods like PRIME-EURUS (implicit rewards modeling), and AceMath (curated data/process supervision). rStar proposes a system for SLMs to reason and resembles the idea of test-time scaling, and we cited it in related works. MARGE enhances the underlying exploration process in RL and can potentially be combined with these approaches, not as counterparts, for future enhancement in LLM reasoning.\n\n# Question 1: Other ways to separate the reasoning process\n\nWe select these ways due to both their simplicity and their effectiveness. We also tested using \"\\n\\n\", which indicates new paragraphs in latex syntax, to separate the reasoning process. This yields more intermediate states than `Step i` or token counts but does not result in better final performance. Therefore, we believe when computation is not a constraint, simply more states aren't always better.\n\nAlternative segmentation strategies are indeed interesting future directions for exploration and process-based rewards research. Approaches could include:\n- Rule-based segmentation using logical structure (e.g., identifying equations, logical connectors), but it should also match the model's output style.\n- Using an auxiliary LLM to identify meaningful intermediate reasoning steps.\n\nOverall, exploring better segmentation is an interesting problem for not only our work but also the development of process rewards and PRMs, and thus can be further researched in the future.\n\nWe hope these clarifications and additional results address your concerns! We believe MARGE contributes to enhancing LLM reasoning through improved exploration.\n\n[1] Gao, Jiaxuan, et al. \"On designing effective rl reward at training time for llm reasoning.\" arXiv preprint arXiv:2410.15115 (2024).\n\n[2] Albalak, Alon, et al. \"Big-Math: A Large-Scale, High-Quality Math Dataset for Reinforcement Learning in Language Models.\" arXiv preprint arXiv:2502.17387 (2025).", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes, I checked the Table 1 main result.\nThe accuracy of Qwen2.5-7B-Instruct experiment on MATH is 75.3 and the MARGE improves to 76.74.\nI think the improvement is not that significant. However, the results on MATH500 with pass@64 does show significant improvements over the baseline (85 > 79).\nMy main concern is the lack of experiments using Qwen2.5 Math based model - would this lead to better accuracy or not?\nIn addition, the Table1 does not show any reference results from previous literature (7B model such as PRIME-EURUS, ACEMATH, rStar), it only compares the results under its own setting, which makes it hard for reader to understand how this method compares to the current literature and state of the art results at 7B level.\n\n============ Post rebuttal ============\n\nAuthor has added additional Qwen-math results and add references to other models. They have addressed my concerns and thanks for the effort.", "relation_to_broader_scientific_literature": "This contributes to math LLM RL using MCTS to provide state level supervision.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strength: novel framework\nWeaknesses: weak result", "other_comments_or_suggestions": "the definition of state for implementation seems quite simple: based on \"step i\" or based on token count...What would be a better way to separate the reasoning process into different steps if compute is not a constraint?", "questions_for_authors": "NA", "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:

Meta-review: The paper proposes MARGE (Math Reasoning with Guided Exploration), a method designed to enhance mathematical reasoning in large language models (LLMs). It addresses two challenges in LLM reasoning: the scarcity of high-quality training data and the difficulty of effectively exploring reasoning paths. In contrast with traditional self-training approaches, which often suffer from spurious correlations in self-generated datasets, the paper method employs hit-guided exploration to improve both data diversity and reasoning accuracy. The core idea involves  hit-guided exploration, where intermediate reasoning states from self-generated solutions are systematically explored, leading to improved credit assignment. Experiments demonstrate that MARGE improves single-shot accuracy (pass@1) and exploration diversity (pass@k) across benchmarks and backbone models.
An advantage of MARGE is its ability to maintain on-policy rewards, unlike other pre-trained PRM methods. However, this comes at the increased computation cost.

The reviewers highlighted several strengths of the paper, including its comprehensive experiments comparing MARGE against popular RL methods on widely used models, as well as ablation studies confirming that hit selection strategy and guidance updates improve performance. The paper provides theoretical insights into why the hit guided exploration yields richer training data. The method addresses spurious correlations in self-generated data, demonstrates  empirical improvements over baselines.

However, some weaknesses were initially noted in the reviews. These included a lack of failure analysis, insufficient evidence for MARGE’s scalability in self-generating responses (no explicit scaling trends were shown), and the increased computation overhead, which was not fully discussed. Reviewers also raised concerns about the hit selection mechanism in cases where no correct answers are generated, as well as the rationale for using incorrect responses as guidance hits for easier questions. Additionally, the paper did not include experiments using the Qwen2.5 Math-based model or comparisons to prior work on 7B models (e.g., PRIME-EURUS, ACEMATH, rStar).

At the end of the discussion, the authors provided access to the source code in an anonymized repository https://anonymous.4open.science/r/MARGE-ACE8 for reproducibility checks and stated that trained models and checkpoints would be open-sourced soon.

 Following a thorough rebuttal, most concerns were adequately addressed, and the reviewers agreed that the paper meets the acceptance threshold. Thus, acceptance is recommended, provided the proposed improvements are incorporated.
Decision: Accept (poster)