Skip to content
Raunak Sood
 
← Back
AI research · USC · five authors

Resampled Thought Trees

When an AI solves a problem step by step, some steps are essential and some are wasted effort. Search usually judges a step only by the final answer. We measured each step directly.

What I proposed
Score each intermediate step of an AI's search by freezing the search at that step and re-running it ten times. The share of re-runs that still reach the answer is the step's real value, independent of how promising the AI said it looked.
What it produced
A per-step map from about 11,000 stochastic re-runs (22,350 counting deterministic repeats) on two puzzle types. Within the first move, the AI's ranking barely predicts which move works (41% vs 37–38% at temperature 0.2), so rank alone is not a reliable guide. Deleting branches rarely changed whether a puzzle was solved; deleting a redundant branch removed 38% of the remaining routes to the solution, a loss pass/fail scoring cannot see.
My part
A five-author course project at USC, built and run collaboratively by the five co-authors. The repository linked below mirrors the team's release and adds the paper.

The problem

Modern AI systems solve hard problems by exploring: trying one line of reasoning, then another, like a person working through a puzzle. At each step the model picks which idea to pursue next, based on how promising it looks.

Nobody knew whether “looks promising” and “leads somewhere” are the same thing. Everyone measured whether the final answer was right, which tells you nothing about which steps along the way were doing the work.

What we did

Freeze the AI at one specific thought. Restart it from exactly that point, ten times over. Count how often it still reaches the right answer.

Do that for every thought in the tree and you get a score for each one: how much that step was worth. We ran it 22,350 times across two kinds of puzzle.

Puzzle: make 24 from the numbers 1, 1, 13, 13
Restarting the puzzle 10 times from “13 − 13 = 0”:
✕
✕
✕
✕
✕
✕
✕
✕
✕
✕

A dead end, and ranked last, so here the ranking was right.

What to look at: The AI ranked these four opening moves from best to worst. Click each one to see how often ten re-runs from that move reached the right answer. Here its top choice never works and its second choice always does. One puzzle, real logged numbers; the pattern across all 100 puzzles is below.

Main finding

The AI's own ranking is a weak guide. Across 100 Game24 puzzles, each run at two temperatures, the first moves it ranked first through fourth reached a solution 41%, 38%, 38% and 37% of the time at temperature 0.2, and 37–41% in no consistent order at temperature 0. Pooled over all depths the top-ranked move looks far worse (16% vs about 40%), but that is depth, not rank: top-ranked moves are followed deeper, where every state is harder.

That matters in practice: these systems decide what to explore using that ranking. If the ranking is unreliable, they spend their budget in the wrong places.

Results differ by task

We expected a simple rule like “early steps matter most.” Instead the two tasks behaved in opposite ways, so there is no shortcut and you have to measure.

1 step in
18%
4 steps
72%
16 steps
76%
24 steps
87%
32 steps
100%
How often the AI reaches a correct answer from that point.
What to look at: In crosswords, the further in you get, the more reliable things become: wrong guesses die early, so anything still alive deep in the puzzle is probably right.

A second result

We also deleted branches from the tree to see what broke. Judged only on did it still solve the puzzle, deleting things looked harmless.

Counting how many different routes to the answer survived gave a different result: deleting some branches removed most of the solutions while leaving one behind. The puzzle was still solved, so a normal evaluation saw nothing, while the system had become far more fragile.

Scope and limitations

This was a five-author project at USC. We controlled the AI's options rather than letting it generate freely, which makes the measurement much cleaner but means the findings describe this setup rather than every AI system. Two more limits. At temperature zero the re-runs are deterministic, so those scores can only be 0 or 100%; the opening-move example is from the temperature 0.2 run and the crossword depth chart from temperature 0. And the idea of re-running from a partial state to value it is shared with Monte Carlo tree search rollouts and with process-reward labelling; the contribution here is the per-step taxonomy and the ablation check, not the resampling itself.