- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2(+1)
Read review
Paper summary
The paper studies LLM-agent tasks with deterministic, resettable environments and verifiable outcomes. TROPIC stores states and actions from multiple attempts, including valid transitions from failed attempts. When two trajectories reach the same state, it concatenates a prefix from one trajectory with a suffix from another. The resulting complete path is replayed from the initial state and accepted by the verifier before being used for maximum-likelihood training.
The paper proposed a method named Tropical Reinforcement Learning. For each problem, TROPIC maintains a graph of valid transitions discovered across multiple attempts, including transitions from failed attempts. When two attempts reach the same state, TROPIC can join a prefix from one attempt with a suffix from another. It then replays the resulting complete path from the initial state and adds the path to the archive only if the verifier accepts it. TROPIC also starts new attempts from frontier states, namely states that are reachable in the graph but do not yet have a verified completion. During training, it selects the best archived path and, when available, a coverage path containing transitions that have been trained less often, and applies maximum-likelihood updates to these paths. The “tropical” part refers to how alternative verified paths are combined: their scores are combined by taking the maximum rather than summing their probabilities.
Experiments cover four environments and two model families. In Table 2, TROPIC outperforms the listed main baselines in every setting. At test time, archive, restarts, and composition are disabled, so the evaluation measures what has transferred into the model parameters. These results support the effectiveness of the complete TROPIC training procedure.
Critical strengths
-
The method design is coherent and matched to the target setting. The use of a graph, an archive, composition, replay, and verification is appropriate for deterministic, resettable environments with verifiable outcomes.
-
The empirical evaluation is broad and thorough. The paper covers four environments and two model families, reports results over three training seeds, and includes both main comparisons and component ablations.
Critical weaknesses
-
The ablations do not isolate the contributions of the individual components. Disabling a component changes the search trajectory and the set of verified paths available for training, so the current ablations compare end-to-end variants rather than holding the training data fixed. In particular, the No Composition result cannot distinguish the benefit of composition itself from the benefit of the additional training paths created by composition. To isolate the training objective, the authors should apply alternative training rules to the same fixed archive of verified paths. The comparison should also report matched generated tokens, verifier and environment calls, replays, and optimization updates.
-
The comparison with related work is incomplete. The paper compares against MaxRL, GiGPO, and GiGPO + T-STAR, but these comparisons do not use the same archive of verified paths, and Appendix C acknowledges that the actual compute is not matched. The paper also does not discuss [1] or [3], and does not provide a direct comparison with [2]. These works are not identical baselines, but they provide relevant search or self-training precedents that should be discussed when positioning the contribution.
[1] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. STaR: Bootstrapping Reasoning With Reasoning. NeurIPS 2022.
[2] Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. ReST-MCTS: LLM Self-Training via Process Reward Guided Tree Search.* NeurIPS 2024.
[3] Xinyu Guan, Li Lyna Zhang, Yifei Liu, Ning Shang, Youran Sun, Yi Zhu, Fan Yang, and Mao Yang. rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking. arXiv preprint arXiv:2501.04519, 2025.
- The tropical objective is not shown to align with task success rate. Equation 11 maximizes the log-probability of the most likely verified path, whereas task success rate depends on the sum of the probabilities of verified paths. Equation 10 gives only a lower bound and does not imply that task success rate must increase. The paper does not measure whether the maximum-path probability can increase while task success rate or the probability of other verified paths decreases. Moreover, the strongest theoretical guarantee assumes separate parameters at each state and a single-path update, which does not match the shared-parameter language model and the additional coverage path used in the implementation.
Questions for authors
-
Contribution clarification: Relative to search plus self-training, is the main contribution the composition, the maximum-based objective, or their combination? Which results distinguish these possibilities? What's the difference between related work?
-
Controlled comparison: Given a fixed archive of verified paths and a matched training budget, how does maximum-likelihood training on the best verified path compare with maximum-likelihood training on all deduplicated verified paths and with other ways of aggregating verified paths?
-
Objective alignment: During actual training, are there cases where the maximum-path probability increases while the task success rate decreases? Can you track the degradation of other verified paths for the same problem?
-
Root-Only clarification: Since Root-Only still permits composition between different root-started rollouts, please provide a concrete example of a Root-Only instance whose first verified solution was assembled from a prefix in one rollout and a suffix in another. And clarify how FIRST-SOLVE is counted in this case.
5 comments
Pt.2
W2: Related work
ReST-MCTS* is cited in Section 5 (Zhang et al., 2024) among the tree-search methods. We will add STaR and rStar-Math to that discussion. Their counterparts are already among our comparisons:
-
STaR generates attempts, keeps the correct ones, and fine-tunes on them. In our setting, this corresponds to No Composition, which Appendix C describes as archive-based exploration with rejection-sampling fine-tuning (40.8%), and to row C on the same archive (51.9%).
-
ReST-MCTS* and rStar-Math run a tree search guided by a separately learned process-reward or preference model. TROPIC differs in two ways:
- Tree versus graph. A tree keeps its branches separate. TROPIC merges identical states reached by different attempts into a graph, which is what allows a prefix from one attempt to be joined with a suffix from another.
- No additional learned model. TROPIC uses the actor's own log-probabilities and the verifier.
A direct run of ReST-MCTS* would add a learned reward model that none of the compared methods uses.
On the same-archive and matched-compute points:
- MaxRL: row D is the MaxRL objective on the same archive and budget (54.0% vs. 58.6%).
- GiGPO and T-STAR: both keep the expected-return objective, and row E is that objective on the same archive (39.7%).
- Compute: the statement in Appendix C concerns wall-clock time under different stopping rules. The rollout budget is matched for all methods.
W3 / Q3: Alignment with task success
What the paper shows. The success rate in Table 2 is single-attempt task success on 512 held-out instances, and TROPIC is highest in all eight settings. The paper claims no guarantee beyond this: Section 4.2 states that the bound of Eq. 10 "does not by itself force pass@1 up."
What we measured in addition. Across consecutive training checkpoints on Sokoban, we tracked three quantities on a fixed reference archive, so that newly added paths cannot inflate the numbers:
- the best-path probability;
- the summed probability of all archived verified paths;
- the success rate, estimated by repeated sampling on the same problems.
Table R8. Tropical value and success (Sokoban, Qwen2.5-3B-Instruct).
| Quantity | Value |
|---|---|
| Intervals with rising best-path log-probability in which sampled success did not fall (%) | 91.7 |
| Intervals with rising best-path log-probability in which summed archived-path probability rose (%) | 88.9 |
| Non-best verified paths losing at least half their probability (%) | 24.8 |
| Spearman correlation between best-path log-probability and sampled success across problems | 0.76 |
- Q3, first part: yes. In 8.3% of the intervals where the best-path probability rises, sampled success falls. In the other 91.7% it does not.
- The sum follows the maximum. Task success depends on the summed probability of verified paths, as you note. This sum rises in 88.9% of the intervals where the best-path probability rises.
- Q3, second part: other verified paths. 24.8% of non-best verified paths lose at least half their probability. This is expected, since the objective concentrates probability on the best path. For reference, under GRPO, 30.2% of the best verified paths themselves lose half their probability, against 6.8% under TROPIC (Table R7, response to Reviewer 5kND).
The alignment is therefore strong but empirical, and we will say so in Section 4.2.
Theory. Both gaps are stated in the submission. The text below Theorem 4 says that the theorem is exact only for separate parameters per state. Remark 1 says that the coverage path lies outside Theorem 12 and is a deliberate trade. In practice, the trade pays off: coverage paths raise success from 55.6% to 58.6% (rows B and A) and reduce the share of deteriorated probe paths from 15.4% to 6.8% (Table R7).
Pt.3
Q4: Root-Only and First-Solve
You are right, and no such example exists. In Root-Only, every attempt starts at the initial state, so any successful suffix already belongs to a complete successful attempt. A join can therefore never be the first verified solution.
On auditing the counter, we found that it measured a different quantity: the share of solved training problems whose best verified path is a join that was never sampled in one piece. We will rename the statistic to Best-Join and correct its definition and the statements that describe 24.7% and 31.6% as first solutions. No success rate is affected.
Where first solutions come from. The first verified solution of a problem has one of three origins:
- Root-started rollout: sampled in one piece from the initial state.
- Frontier-started completion: a stored prefix from an earlier attempt, completed by a new attempt started at its end state.
- Graph join: a stored prefix joined with a stored suffix.
Table R9. Origin of the first verified solution (% of solved training problems; Sokoban, Qwen2.5-3B-Instruct, 3 seeds).
| Variant | Root-started rollout | Frontier-started completion | Graph join |
|---|---|---|---|
| No Composition | 63.8 | 36.2 | 0.0 |
| Root-Only | 100.0 | 0.0 | 0.0 |
| Successful-Only | 61.4 | 38.6 | 0.0 |
| Full TROPIC | 55.9 | 44.1 | 0.0 |
In Full TROPIC, 44.1% of first solutions are frontier-started completions. These combine fragments of two attempts and were also never sampled in one piece.
What joins contribute. A join matters because it can be more likely under the current model than any sampled solution, and it then becomes the path the model trains on. A typical Root-Only case has three steps:
- Attempt 1 succeeds and passes through a state .
- Attempt 2 reaches by a more likely prefix, then fails.
- Joining the prefix of attempt 2 with the suffix of attempt 1 gives a verified path that was never sampled and is more likely than attempt 1.
Table R10. Contribution of joins to training paths (Sokoban, Qwen2.5-3B-Instruct, 3 seeds).
| Variant | Best verified path is a join (%) | Mean log-probability gain over best sampled path (nats) | Best-path updates that select a join (%) |
|---|---|---|---|
| No Composition | 0.0 | – | 0.0 |
| Root-Only | 24.7 | +0.84 | 21.6 |
| Successful-Only | 16.8 | +0.61 | 13.4 |
| Full TROPIC | 31.6 | +1.18 | 28.5 |
The gain is measured under the same frozen model, on problems where a join is the best verified path.
- Root-Only: in 24.7% of solved problems, the best verified path is a join. The gain of 0.84 nats means it is about 2.3 times more likely than the best sampled solution. It is selected in 21.6% of best-path updates.
- Full TROPIC: the share is 31.6%, the gain is 1.18 nats (about 3.3 times more likely), and joins are selected in 28.5% of best-path updates.
Composition therefore provides better training targets, not first solutions. This matches the success rates: Root-Only reaches 51.8% against 40.8% without composition, and removing composed paths at fixed acquisition costs 9.9 points (Table R1).
Thank you for your thoughtful feedback. We would appreciate it if you could let us know whether our clarifications address your concerns. If the responses above are sufficient, we kindly ask that you consider raising your score.
Pt.1
Thank you for the review. We ran the fixed-archive experiment you proposed (Table R1). Please see the answers below.
Q1: What is the contribution?
The combination. Composition builds verified solutions from fragments of different attempts. The tropical (maximum-based) update decides which verified path the model is trained on. Table R1 tests each part with the training data held fixed:
Neither part alone reaches the combination. The end-to-end ablation agrees: Full TROPIC reaches 58.4% on Sokoban against 40.8% for No Composition. Across all four tasks and both models, the gain from composition is 4.9–17.6 points (Tables R5a and R5b, response to Reviewer 5kND).
The two parts are also linked in the method. Joining a prefix and a suffix requires a value that names concrete paths. A sum over paths does not provide this (Observation 1), while the maximum does (Eq. 9). The difference from related work is addressed under W2.
W1 / Q2: Comparison on a fixed archive
The Table 3 ablations are end-to-end by design: they show what each component contributes to the full system. For fixed data, Proposition 3 gives the comparison analytically, as the weight each objective places on the same set of paths. Table R1 tests it empirically.
Protocol. We saved the graph and archive of every problem at every iteration of the TROPIC runs and trained each rule on this identical stream. The matched quantities are:
Only the choice and weighting of training paths differ. The witness is the best (most likely) verified path of a problem. A composed path is a verified path that exists in the archive only through composition: it was assembled from parts of different attempts and not sampled in one piece. The third column is the share of update weight on such paths.
Table R1. Update rules trained on the same data (Sokoban, Qwen2.5-3B-Instruct, 3 seeds).
The 9.9 points and the 17.6-point end-to-end gain measure different things and do not add up. End-to-end runs also differ in which paths are acquired afterwards.
Cost against the baselines. At matched model-token cost on Sokoban, TROPIC at half of its budget (45.8%) already exceeds SNR-Aware at the full budget (40.7%). See Table R4 in our response to Reviewer sof8. We will add the compute accounting to Appendix C.