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.
A dead end, and ranked last, so here the ranking was right.
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.
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.