MCTS Reasoning Search

MCTS (Monte Carlo Tree Search) organizes generation as tree search: nodes are reasoning states (partial reasoning produced so far), edges are next actions. It loops over four steps — selection (pick nodes by the UCT formula $UCT = \bar{v} + c\sqrt{\frac{\ln N}{n}}$, balancing exploration and exploitation), expansion, simulation (rollout), and backpropagation of the leaf value. With LLMs, node values $v$ come from process reward model (PRM) step scores, forming Test-Time Search — the AlphaGo idea transplanted to LLM reasoning.

reasoning enhancement on verifiable tasks (math, games), searching high-quality trajectories during reasoning-model training (as RL data), and test-time tree search combined with PRMs.

autoregressive generation goes down one path — a single wrong step is unrecoverable and errors propagate; MCTS explores multiple paths with value-guided pruning, finding better routes at test time and raising solution rates on hard problems.

What do MCTS's four steps (selection/expansion/simulation/backpropagation) each do?

Write the UCT formula, explain each symbol, and how it balances exploration vs exploitation?

How is MCTS combined with an LLM? How are nodes, actions, and values defined?

The role of PRMs in MCTS? Why are step-level rewards better than outcome rewards?

MCTS vs plain sampling (best-of-N): compute complexity vs gains?