Resampled Thought Trees
When an AI solves a problem step by step, some steps are essential and some are wasted effort. Nobody could tell which was which. We built a way to measure it.
- 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 over 22,350 re-runs on two puzzle types. The AI's top-ranked move reaches a solution 16% of the time; moves it ranked lower reach one about 40% of the time. Deleting branches rarely changed whether a puzzle was solved but removed most of the routes to the solution, a loss that 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.
The catch: nobody knew whether “looks promising” and “actually 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 really worth. We ran it 22,350 times across two kinds of puzzle.
A dead end, and ranked last, so here the ranking was right.
Main finding
The AI's own confidence is a weak guide. Across 200 Game24 puzzles, the move it ranked first reached a solution 16% of the time. The moves it ranked second, third and fourth each reached one about 40% of the time. Part of that gap is tree depth rather than rank, since top-ranked moves are followed deeper where every state is harder, and the paper says so; within the first move alone the difference is small.
That matters practically: these systems decide what to explore using exactly 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.
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.
But counting how many different routes to the answer survived told another story: some branches quietly removed most of the solutions while leaving one behind. The puzzle 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. The honest framing of the results: 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 numbers above are from the temperature 0.2 run. 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.