When a language model solves a problem by tree search, it writes several candidate next steps, scores them, and expands the promising ones. The tree grows exponentially, and much of that growth is waste, because many branches are the same step in different words. The current fix, Chopping Trees (semantic similarity dynamic pruning, SSDP), embeds sibling steps with a frozen sentence encoder, merges those whose cosine similarity exceeds a fixed threshold, and keeps the highest-scoring member of each group. That cuts explored nodes by 85–90%. The criterion is surface meaning, though, and surface meaning is the wrong notion of sameness. Two steps that differ only in a sign or a single digit look almost identical to a sentence encoder but lead to entirely different futures. Two steps phrased very differently, such as "subtract 7 from both sides" and "so x equals 12 minus 7," can lead to the same place and still survive as separate branches.
Poker solvers met this problem a decade ago. Potential-Aware Imperfect-Recall Abstraction with Earth Mover's Distance showed that grouping card hands by their current strength is misleading. Hands should be grouped by the distribution of strengths they can reach in later rounds, compared with Earth Mover's Distance (EMD, the minimum cost of reshaping one histogram into another). The authors made this practical with a fast approximation that ran 1400x faster than exact EMD. We propose the same move for reasoning trees. Each candidate step gets a summary of what its continuations look like, namely a histogram of learned-value scores over a few cheap lookahead continuations. Siblings are merged when their histograms are close in EMD. A small learned head predicts that histogram from the model's hidden state, so the merge costs about as much as an embedding lookup.
Core Claim
If two reasoning steps have the same distribution of downstream values, expanding both mostly wastes compute. If two steps look alike but have different downstream distributions, merging them throws away the branch that might have been correct. Merging on future-value distributions should therefore give a better accuracy-per-compute curve than merging on text similarity. It should make fewer harmful merges (collapsing a correct step into an incorrect one) and more useful merges (collapsing true duplicates that are worded differently). The claim is testable because on one benchmark, Game24, the true intermediate state is exactly the multiset of remaining numbers. That gives a ground-truth abstraction to measure both methods against.
What Exists and How This Differs
Four lines of work set the context. Chopping Trees is the closest prior work and the one we modify. It uses a myopic, text-based, static-threshold merge rule, and it reports accuracy only "typically within 5% of the strongest baseline." That loss is exactly what a better merge criterion should recover. AlphaZero-Like Tree-Search (TS-LLM) supplies the method we reuse: a learned value function $v_\phi$ that scores partial solutions, which lets search reach depth 64. TS-LLM treats every generated branch as a distinct state and does no merging, so it motivates the gap. Incentivizing LLM Reasoning via Functional MCTS and STATe-of-Thoughts control branching from the generation side, with learned control tokens and hand-written action templates respectively. We act after generation and choose which generated branches to keep, so the approaches can be combined. Finally, Efficient Subgame Refinement (GS2) constrains the design. It shows that in huge game information sets, selecting a diverse subset with EMD over values works better than random subsampling. That supports using distributional distance rather than a point estimate when deciding which candidates are interchangeable.
The contrast with poker abstraction is that poker potentials are computed offline over a known deck. We have no enumerable future, so the potential must be estimated by sampling and then distilled into a predictor. The contrast with SSDP is that we never compare text at all.
Research Program
For a node $s$ in the search tree, we define its potential signature $h_s$. To build it, we sample $m$ short continuations of $k$ steps from a small draft model, score each endpoint with the value model $v_\phi$, and bin the scores into a histogram over $[0,1]$. Two siblings $s, s'$ are merged when
$$ \mathrm{EMD}(h_s, h_{s'}) < \tau_d, $$
where $\tau_d$ is a threshold that depends on depth. For one-dimensional histograms, EMD equals the area between the two cumulative distributions, so it is exact and computes in linear time. Within each merged group we keep the member with the highest $v_\phi$, and we free the KV-caches (the stored attention keys and values) of the others. Merged nodes forget their distinct wording, which is the analogue of imperfect recall in poker abstraction.
Sampling $m$ continuations per node would eat the savings, so we distill. From offline rollouts on the training splits, we train a small head on the policy's final-layer state to predict $h_s$ directly. This parallels the fast heuristic that made potential-aware poker abstraction affordable. We will report the prediction error of this head, measured as EMD to held-out rollout histograms.
We will also calibrate $\tau_d$ with a held-out target of at most $\epsilon$ harmful merges per depth, rather than tuning it by hand. The depth dependence matters because early steps have wider, less certain futures.
The analysis centers on abstraction quality, not only end accuracy. On Game24, where the true state is known, we count four outcomes for each method. False splits are nodes with identical true state that were kept apart. Harmful merges are nodes with different solvability that were merged. Duplicates caught and correct branches lost follow the same logic. On GSM8K and MATH-500, where the true state is unknown, we estimate each node's solve probability from 32 full rollouts. We then count a merge as harmful when the merged nodes' solve probabilities differ by more than 0.3.
Baselines
The naive reference points are greedy chain-of-thought and unpruned TS-LLM search. TS-LLM reports 12.7% on Game24 for greedy chain-of-thought against 71.3% for MCTS-Rollout. It also reports GSM8K MCTS accuracy of 56.5% after one improvement iteration. We will rerun both using the released LLaMA-2-7B policy and value models from LLM_Tree_Search, so every method shares one policy and one value function. Unpruned search defines the accuracy ceiling at unlimited compute.
The strongest existing method is SSDP, run from its public code on the same TS-LLM search loop. Chopping Trees reports a 2.3x speedup over Dynamic Parallel Tree Search and 85–90% fewer explored nodes. It reports accuracy only as within 5% of the strongest baseline, and the file gives no absolute SSDP accuracy on MATH-500, GSM8K or Game24. We therefore produce those numbers ourselves. For fairness, SSDP gets the same threshold-tuning budget we give $\tau_d$, a grid of equal size on the same held-out split. Compute is counted as total generated tokens plus forward passes, and this count includes our signature rollouts and head evaluations.
We beat SSDP if our accuracy-versus-tokens curve dominates at matched compute, with at least a 2-point accuracy gain at SSDP's operating point on MATH-500. We also need fewer harmful merges on Game24.
Three ablations isolate the key ingredient. The first replaces the histogram with its mean, which is plain value-similarity merging. It tests whether the distributional shape matters beyond the expected value. The second uses the full rollout-estimated signature with no distillation, which bounds what the head loses. The third merges on the continuation text embedding at lookahead $k$, which tests whether "looking ahead" or "comparing values" is doing the work.
Game24 also admits an oracle: exact deduplication on the multiset of remaining numbers. This is the upper bound any learned abstraction should approach.
Why not just…?
Why not just prune low-value branches with the value model, as in beam search? Value pruning removes weak branches but does nothing about several strong branches that are duplicates, so compute still goes to redundant expansions. The mean-only ablation tests exactly this. If mean-value merging matches the full histogram, the distributional part of our claim fails and we will say so. We expect it to fail most at early depths, where two steps with the same average value can lead toward different answers. Merging those steps loses the diversity that GS2's results on EMD-based selection suggest is worth keeping.
Why not just tune SSDP's threshold, or make it adaptive? This is a real threat, because much of SSDP's accuracy gap could come from one badly chosen threshold. We give SSDP an equal tuning budget, including a depth-dependent threshold. If tuned SSDP matches us, the lesson is that threshold selection mattered, not the merge signal. The Game24 audit still tells the two apart. A text encoder cannot tell "8 − 3" from "8 + 3" once the contexts are nearly identical, and the harmful-merge count shows whether that limitation actually costs accuracy.
Why not just canonicalize the intermediate state symbolically and deduplicate exactly? Where this works it is the better method, and on Game24 we use it as the oracle. The idea behind Code World Models, writing an explicit state parser, does not extend to free-form MATH derivations, where no canonical state exists. Our method is meant for that case. We measure how far it falls short of the oracle on Game24 to show what is lost when the state is not explicit.
Why not just spend the saved compute on more Best-of-N samples? We plot Best-of-N at matched tokens. SSDP already reports 5.2–7.7x speedups over Best-of-N on GSM8K, so this baseline is weaker, but it remains the natural sanity check.
Proposed Experiments
We run Game24, GSM8K and MATH-500 with the shared TS-LLM models. We sweep the compute budget and plot accuracy against total tokens for every method, with three seeds, and report the Game24 abstraction audit together with the harmful-merge rates estimated by rollouts on the math sets.
Three checks decide the outcome. The first is whether our method dominates tuned SSDP on the MATH-500 accuracy-per-token curve. The second is whether the harmful-merge rate on Game24 falls below SSDP's while coverage of the exact oracle's merges rises. The third is whether the distilled head keeps most of the gain of full rollout signatures at a fraction of the cost. If the first holds without the second, the gains come from somewhere other than better abstraction, and we will report that. If the second holds without the first, better merges exist but are not worth their price at this scale, and we will report that too.
References
- Chopping Trees: Semantic Similarity Based Dynamic Pruning for Tree-of-Thought Reasoning
- Potential-Aware Imperfect-Recall Abstraction with Earth Mover's Distance in Imperfect-Information Games
- AlphaZero-Like Tree-Search can Guide Large Language Model Decoding and Training
- Incentivizing LLM Reasoning via Reinforcement Learning with Functional Monte Carlo Tree Search
- STATe-of-Thoughts: Structured Action Templates for Tree-of-Thoughts
- Efficient Subgame Refinement for Extensive-form Games
- Code World Models for General Game Playing