# ToTRL: Unlock LLM Tree-of-Thoughts Reasoning Potential through Puzzles Solving

arXiv: https://arxiv.org/abs/2505.12717 · HTML: https://mlsanity.com/paper/2505.12717/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 20 of its 32 references that are in the map.
- First posted on arXiv 19 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 20 of 20)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [From Crowdsourced Data to High-Quality Benchmarks: Arena-Hard and BenchBuilder Pipeline](https://mlsanity.com/paper/2406.11939/) (2024)
- [Demystifying Long Chain-of-Thought Reasoning in LLMs](https://mlsanity.com/paper/2502.03373/) (2025)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [SWE-RL: Advancing LLM Reasoning via Reinforcement Learning on Open Software Evolution](https://mlsanity.com/paper/2502.18449/) (2025)
- [Logic-RL: Unleashing LLM Reasoning with Rule-Based Reinforcement Learning](https://mlsanity.com/paper/2502.14768/) (2025)
- [REINFORCE++: Stabilizing Critic-Free Policy Optimization with Global Advantage Normalization](https://mlsanity.com/paper/2501.03262/) (2025)
- [Large Language Model Guided Tree-of-Thought](https://mlsanity.com/paper/2305.08291/) (2023)
- [Llama-Nemotron: Efficient Reasoning Models](https://mlsanity.com/paper/2505.00949/) (2025)
- [Phi-4-reasoning Technical Report](https://mlsanity.com/paper/2504.21318/) (2025)
- [On Memorization of Large Language Models in Logical Reasoning](https://mlsanity.com/paper/2410.23123/) (2024)
- [Back to Basics: Revisiting REINFORCE Style Optimization for Learning from Human Feedback in LLMs](https://mlsanity.com/paper/2402.14740/) (2024)
- [Z1: Efficient Test-time Scaling with Code](https://mlsanity.com/paper/2504.00810/) (2025)
- [Autonomous Tree-search Ability of Large Language Models](https://mlsanity.com/paper/2310.10686/) (2023)

## Built on by (most cited first, 8 of 8)

- [A Survey of Reinforcement Learning for Large Reasoning Models](https://mlsanity.com/paper/2509.08827/) (2025)
- [StreamingTOM: Streaming Token Compression for Efficient Video Understanding](https://mlsanity.com/paper/2510.18269/) (2025)
- [Reinforcement Learning Meets Large Language Models: A Survey of Advancements and Applications Across the LLM Lifecycle](https://mlsanity.com/paper/2509.16679/) (2025)
- [One-Token Rollout: Guiding Supervised Fine-Tuning of LLMs with Policy Gradient](https://mlsanity.com/paper/2509.26313/) (2025)
- [Structure Enables Effective Self-Localization of Errors in LLMs](https://mlsanity.com/paper/2602.02416/) (2026)
- [Hint-Guided Diversified Policy Optimization for LLM Reasoning](https://mlsanity.com/paper/2606.03021/) (2026)
- [TensorCast: The Missing Tensor Management Layer in Large Language Model Infrastructure](https://mlsanity.com/paper/2608.06007/) (2026)
- [Self-Play Search Distillation for Large Language Model Reasoning](https://mlsanity.com/paper/2609.30936/) (2026)

## Abstract (arXiv)

Large language models (LLMs) demonstrate significant reasoning capabilities, particularly through long chain-of-thought (CoT) processes, which can be elicited by reinforcement learning (RL). However, prolonged CoT reasoning presents limitations, primarily verbose outputs due to excessive introspection. The reasoning process in these LLMs often appears to follow a trial-and-error methodology rather than a systematic, logical deduction. In contrast, tree-of-thoughts (ToT) offers a conceptually more advanced approach by modeling reasoning as an exploration within a tree structure. This reasoning structure facilitates the parallel generation and evaluation of multiple reasoning branches, allowing for the active identification, assessment, and pruning of unproductive paths. This process can potentially lead to improved performance and reduced token costs. Building upon the long CoT capability of LLMs, we introduce tree-of-thoughts RL (ToTRL), a novel on-policy RL framework with a rule-based reward. ToTRL is designed to guide LLMs in developing the parallel ToT strategy based on the sequential CoT strategy. Furthermore, we employ LLMs as players in a puzzle game during the ToTRL training process. Solving puzzle games inherently necessitates exploring interdependent choices and managing multiple constraints, which requires the construction and exploration of a thought tree, providing challenging tasks for cultivating the ToT reasoning capability. Our empirical evaluations demonstrate that our ToTQwen3-8B model, trained with our ToTRL, achieves significant improvement in performance and reasoning efficiency on complex reasoning tasks.