🔗9.3.4 MCT Self-Refine

Research Background:

• Large language models face accuracy and reliability issues in strategy and logical reasoning, especially in mathematical reasoning tasks, where they are prone to generate hallucinations or erroneous outputs. These outputs may appear reasonable but incorrect, and finally harmful for the reasoning process.

• Self-refine method can alleviate these issues, but it tends to produce misleading or incorrect results when dealing with complex real-world mathematical problems.

MCTS and Self-refine Recall

⭐

Recall: Upper Confidence Bound (UCT) applied in MCTS

For MCTS, the Selection stage is crucial. UCT selects the action that maximizes the following formula to balance exploration and exploitation:

• : the average reward (or value) of node . When the decision process has clear win/loss outcomes (e.g., in Go game), it can be expressed as:
where is the number of wins along the path through node , and is the total number of visits to node . These statistics are updated during the Backpropagation stage (since win/loss can be treated as 0–1 reward, this is also the average reward).

• : the total number of visits to the parent node of the current node.

• : a constant to balance exploration and exploitation.

Interpretation of the formula:

• The first term () is exploitation: The larger the node’s average value, the more the algorithm tends to exploit (choose) this node.

• The second term () is exploration: The smaller the node’s visit count, the larger this term becomes, encouraging exploration of less-visited nodes.

⭐

Self-refine

Given an input to an LLM, it first produces an initial output. Then, this output is fed back into the LLM itself, prompting it to generate its own revision suggestions or feedback. Next, based on the output and the feedback, the model generates a refined plan and a revised output.

This iterative process continues until either the maximum number of iterations is reached or no further improvements are made. Finally, the result is the output obtained after multiple rounds of refinement.

Example of Self-refine

Method of MCTSr

• Some notations:
• Problem
• Answer node set
• Action set available at each node (each action represents a possible self-refinement)
• Reward sampling function (based on the quality and validity of refinements)
• Reward set sampled by node
• Terminal state function
• Value function of node ,
• UCT value

Experiment

1. GSM Benchmark Test: On GSM8K and GSM-Hard, results show that as the number of MCTSr refinement iterations increases, the success rate improves significantly. Moreover, on GSM-Hard, no performance ceiling was observed even at higher iteration counts.

2. MATH Benchmark Test: On the MATH dataset (five difficulty levels), 8-rollouts of MCTSr improved success rates across all levels, with an overall accuracy of 58.24%. This indicates the algorithm’s effectiveness and scalability for problems of varying difficulty.

3. Olympiad-level Benchmark Test: On AIME, Math Odyssey, and OlympiadBench datasets, results showed significant improvements with more refinement iterations. For example, AIME accuracy increased from 2.26% to 11.79%, demonstrating the algorithm’s potential and adaptability in tackling Olympiad-level math problems.

 

Conclusion

• Developed and validated a reasoning algorithm that integrates LLMs with MCTS, demonstrating its effectiveness on Olympiad-level math problems.

• Experiments revealed that the synergistic potential of LLMs and MCTS shows performance improvements on complex reasoning tasks.

• Although the MCTSr algorithm shows advantages in mathematical tasks, the research is still in its early stages.

• As a general decision-making framework, its broader applicability (e.g., in black-box optimization problems or large language model–driven dialogue and strategy tasks) remains to be further explored.