I Spent $0.48 to Find Out When MCTS Actually Works for LLM Reasoning

Does tree search help LLM reasoning? The literature can’t decide.

ReST-MCTS* says yes. AB-MCTS got a NeurIPS spotlight. “Limits of PRM-Guided Tree Search” says no: MCTS with a process reward model used 11x more tokens than best-of-N for zero accuracy gain. Snell et al. found beam search degrades performance on easy problems.

I built mcts-reasoning and ran controlled experiments to find where the boundary is. Total API cost: $0.48.

Setup

Four methods, same budget. Eight solution attempts per problem:

• Pass@1: One shot.
• Best-of-N: 8 independent solutions, verifier scores each, pick the best.
• Self-consistency: 8 solutions, majority vote.
• MCTS: 5 initial solutions scored by verifier, then 3 more guided by UCB1, informed by what worked and what failed.

Model: Claude Haiku 4.5. Problems: constraint satisfaction. Find integer values for variables satisfying simultaneous constraints. Example:

Find A, B, C, D, E, F satisfying ALL constraints:
  1. A * D = 21
  2. C = A + F
  3. B * F = 20
  4. E = A + 2
  5. D + B = A
  6. E - F = B
  7. A mod 7 = 0
  8. C mod 4 = 0
  9. B * D = 12
  10. C > E > A > F > B > D
  11. A + B + C + D + E + F = 40
  12. E * D = 27

The verifier is a Python function. Checks each constraint, returns the fraction satisfied. No LLM in the loop. Deterministic.

Calibration

Easy problems first (3-5 variables, 5-9 constraints). Haiku solved them in one pass. All methods tied at 100%.

5-variable problems with 9 constraints: Pass@1 dropped to 65%. Self-consistency failed one problem. But BestOfN still tied MCTS, because with 8 independent samples at least one is usually correct. BestOfN just picks it.

I needed problems where blind sampling hits a ceiling.

Results

Ten harder problems: 6-8 variables, 12-15 constraints. Products, modular arithmetic, ordering chains, cascading dependencies. Pass@1 dropped to 29%.

MCTS solved all 10. Every other method failed on one problem (v6_3).

v6_3 is a 6-variable, 12-constraint problem where none of 8 independent samples found the correct solution. Pass@8 oracle: 0/8. Self-consistency picks the most popular wrong answer. BestOfN picks the best wrong answer. Both fail.

MCTS sees that initial attempts satisfied 10/12 constraints but violated specific ones. UCB1 selects the most promising partial solution. The next attempt, informed by the failure pattern, satisfies all 12.

Total: $0.48. 180 API calls, about 190K tokens.

When MCTS Helps

The pattern across three rounds of experiments:

1. Easy problems (Pass@1 > 80%): No advantage. The model solves them.

2. Medium (Pass@1 40-70%): MCTS ties BestOfN. Blind sampling usually contains a correct solution. The verifier selects it.

3. Hard (Pass@1 < 30%): MCTS pulls ahead. When Pass@8 oracle is low, blind sampling can’t find the answer. MCTS’s informed exploration does.

The condition: MCTS adds value when independent sampling hits a ceiling and the verifier provides a gradient.

The gradient part matters. A binary pass/fail verifier says “wrong” but not how wrong. Partial credit (constraints satisfied / total) gives MCTS something to work with. The exploration phase sees what’s close and adjusts.

Why Self-Consistency Can’t Help

Self-consistency and UCB1 have a structural conflict.

Self-consistency rewards consensus. UCB1 rewards diversity: it explores undervisited branches precisely because they’re undervisited. Using self-consistency as a reward signal inside MCTS tells the tree to explore and converge at the same time. The exploration term pushes toward novel solutions. The consistency reward penalizes them.

On v6_3, all 8 samples failed. SC selected the most common failure mode. A per-path verifier doesn’t have this problem. Each solution is scored against the constraints independently. Good solutions propagate through the tree regardless of what other branches found.

I haven’t seen this conflict discussed in the literature. Most prior MCTS-for-LLM work uses per-path evaluation without explaining why self-consistency is absent.

What the Literature Says

These results fit a pattern.

Snell et al. (2024): compute-optimal test-time scaling needs difficulty-adaptive allocation. Easy problems need no search. Hard problems need search plus good verifiers.

“Limits of PRM-Guided Tree Search” (2025): PRM-guided MCTS fails to beat best-of-N because PRM quality degrades with depth. Noisy reward, no benefit from search.

“Don’t Get Lost in the Trees” (ACL 2025): verifier variance causes search pathologies. Deterministic verifiers avoid this.

Chen et al. (2024): 90% discriminator accuracy threshold for tree search to beat reranking. Deterministic constraint checkers hit 100%.

MCTS was built for games with perfect information. Chess and Go have deterministic reward signals. When the reward is noisy, the search can’t exploit it.

The Verification Asymmetry

The problems where MCTS helps share a structure: easy to verify, hard to solve.

A constraint satisfaction problem with 8 variables and 15 constraints is hard to solve. The LLM has to coordinate assignments across all variables simultaneously. Checking a proposed solution is trivial: evaluate each constraint, count violations.

This is the asymmetry that makes NP problems interesting. Checking a certificate is polynomial. Finding one is (presumably) not. It’s why search works for code generation (run the tests) and proof checking (verify the steps) but not for open-ended essay writing (no verifier).

The same asymmetry shows up at other levels. Reverse-Process Synthetic Data Generation exploits it for training data: run the easy direction (differentiation) to get solved examples of the hard direction (integration). Science as Verifiable Search is the same observation about scientific method: science is search through hypothesis space, and the bottleneck is the cost of testing. Cheap verification enables fast iteration.

At training time, verifiable rewards let you RL a model into producing better reasoning (DeepSeek-R1, GRPO). At inference time, verifiable rewards let you search over candidate solutions (MCTS, best-of-N). At the level of scientific discovery, verifiable predictions let you prune hypothesis space. Sutton’s “Reward is Enough” is the abstract version of this.

The practical question for LLM reasoning: can you write a verifier? If yes, search is worth trying. If not, best-of-N with an LLM judge is probably the ceiling.

Code

Open source: mcts-reasoning.

pip install -e ".[anthropic]"
export ANTHROPIC_API_KEY=your-key
python experiments/run_csp.py --hard --budget 1.00

The provider tracks token usage and enforces budget caps.

Limitations

The problems are hand-crafted. A generator calibrated by Pass@1 rate would be more convincing. Ten problems shows the pattern but isn’t enough for statistical significance.

I tested one model. A weaker model might show MCTS advantage on simpler problems. A stronger one would need harder problems.

The MCTS exploration context shows which solutions scored well and poorly, but not which specific constraints were violated. Adding evaluator feedback to the exploration prompt is an obvious improvement I haven’t tried yet.

Summary

Three conditions for MCTS to help LLM reasoning:

1. A deterministic verifier. Not a learned reward model, not an LLM judge.
2. Partial credit from the verifier. A gradient, not just pass/fail.
3. A problem hard enough that blind sampling can’t reliably solve it.

When all three hold, MCTS outperforms best-of-N, self-consistency, and single-pass. When any one fails, it doesn’t.