Escaping Reasoning Basin Collapse with History-Biased Search

A reasoning basin is an equivalence class of states that share the same underlying reasoning strategy. Basin membership captures redundancy relevant to search rather than surface similarity: states belong to the same basin when they pursue the same core hypothesis or induce the same relevant continuation structure, even if their textual realizations differ.

We define a basin assignment function $\mathcal{B}:\mathcal{S}\rightarrow\mathcal{Z}$ mapping each reasoning state $s$ to a discrete basin identifier. States satisfying $\mathcal{B}(s)=\mathcal{B}(s^{\prime})$ are treated as repeated exploration of the same strategy. The basin representation is task-dependent: when explicit structure is available, we use deterministic structural definitions; for open-ended reasoning, we approximate strategy equivalence semantically.

Structural basins. For arithmetic tasks such as Game of 24, we define basin membership using the ordered sequence of operations applied so far and the sorted remaining values:

Here $\mathrm{ops}(s)$ is the ordered operator sequence (e.g., $(\mathtt{mul},\mathtt{sub})$), so states applying the same operations in a different order remain distinct. For example, the partial step 11,-,1,=,10 on input ${1,11,11,13}$ yields basin sub,|,10,11,13. This representation captures task-relevant structural redundancy with lightweight deterministic parsing.

Semantic basins. For open-ended tasks such as MuSR, exact structural keys are unavailable and string matching is too brittle. We therefore extract from each reasoning trace a main_hypothesis, a one-sentence summary of its central claim, and group states that predict the same answer and express compatible hypotheses under an NLI model. Concretely, states $s$ and $s^{\prime}$ are grouped when

where $h_{s}$ denotes the extracted hypothesis and $\tau_{e},\tau_{c}$ control clustering granularity. We use NLI rather than embedding similarity because reasoning traces often share substantial narrative context despite supporting different hypotheses; NLI more directly captures propositional compatibility. We analyze sensitivity to the extractor, NLI model, and thresholds in Appendix G.

Let $\mathrm{visits}[z]$ denote the number of times basin $z=\mathcal{B}(s)$ has previously been selected into the active search set, and let $f(s)$ be the base score assigned by the underlying search procedure (e.g., model likelihood, a value estimate, or a heuristic score). Inspired by metadynamics (Laio and Parrinello, 2002) in molecular dynamics, which uses a history-dependent bias to discourage repeated visits to previously explored regions, BASIN replaces $f(s)$ with

where $\lambda\geq 0$ controls the strength of the history bias. Visit counts are updated after each selection step. Because all states in the same basin share a visit count, the penalty accumulates at the strategy level rather than independently for individual trajectories. Unvisited basins incur no penalty, while repeated visits receive an increasing but sublinear penalty. The resulting search is therefore biased by its own history: as a basin is revisited, candidates from that basin become progressively less competitive, shifting selection toward underexplored strategies. Importantly, revisits are not forbidden; a previously explored basin remains selectable whenever its base-score advantage exceeds the accumulated penalty.

The selection rule is agnostic to how basin membership is constructed: deterministic structural keys are preferable when available, while semantic clustering provides a fallback when no exact task-specific equivalence relation exists.

History-biased exploration introduces an exploration–exploitation trade-off. Penalizing revisits is useful when search is trapped in a repeatedly explored weak basin, but can also redirect compute away from a promising basin simply because it has been visited frequently. When a meaningful quality signal is available, we therefore introduce QA-BASIN:

where $q_{z}\in[0,1]$ is the running mean quality score for basin $z$. The quality term modulates the accumulated history bias: high-quality basins receive a weaker revisit penalty, whereas low-quality basins approach the original BASIN penalty. QA-BASIN therefore preserves promising strategies while continuing to discourage redundant exploration of weaker ones. Its effectiveness depends on the verifier providing a meaningful quality signal.

We instantiate history-biased basin selection within ToT, although the principle applies to any inference-time search procedure that maintains candidate states and repeatedly selects among them. We also evaluate the same mechanism with Graph of Thoughts (Appendix D) and UCT-based MCTS (Sec. 4.3). Standard ToT maintains a beam $\mathcal{A}_{t}$ of $k$ active states. At each round, it expands the active states into candidate continuations, scores them using $f$, and retains the top $k$. BASIN changes only this selection step: each candidate is assigned a basin through $\mathcal{B}$, rescored using Eq. (3) (or Eq. (4) for QA-BASIN), and ranked by the resulting history-biased score. Visit counts are then updated for the selected states. All other components of the search remain unchanged. Thus, BASIN changes not how candidate reasoning states are generated, but where search allocates inference compute as a function of its exploration history.

Datasets. Our primary experiments use two complementary benchmarks spanning symbolic and natural-language reasoning. Game of 24 requires combining four integers using basic arithmetic ($+,-,\times,\div$) to obtain 24; we use the standard 100-problem set from (Yao et al., 2023). Solutions are verified exactly by evaluating the expression and checking number usage. MuSR (Sprague et al., 2024) is a multi-step reasoning benchmark covering murder mystery, object placement, and team allocation; we use 300 problems sampled uniformly across subtasks.

To test broader generalization, we additionally evaluate HumanEval (Chen et al., 2021), GSM-Hard (Gao et al., 2022), and the Logical Deduction subtask of BIG-Bench Hard (Srivastava et al., 2022). HumanEval tests program synthesis and admits deterministic structural basin definitions, while GSM-Hard tests challenging mathematical reasoning. Together, these benchmarks span symbolic search, natural-language reasoning, mathematics, and code generation.

Models. Our primary Game of 24 experiments use gpt-4o-mini (OpenAI, 2024) and Qwen3-27B (Yang et al., 2025); MuSR uses gpt-4o-mini and gpt-oss-120b (OpenAI et al., 2025). For broader evaluation, we additionally test Qwen2.5-7B-Instruct (Team, 2024) and Llama-3.3-70B-Instruct (Dubey et al., 2024), covering multiple model families and scales.

Search and Basins. We use ToT as the primary controlled search framework. BASIN changes only candidate selection through Eq. (3); QA-BASIN uses Eq. (4). Generation, search budget, and final-answer selection are otherwise held fixed. Game of 24 and HumanEval use deterministic structural basin definitions. For MuSR, we extract a main_hypothesis from each reasoning trace and construct semantic basins as described in §3.1. The same extraction procedure is applied when computing basin statistics for baseline and basin-aware searches. Under our nine-round MuSR setup, both conditions use 18 generation and 18 hypothesis extraction calls per problem. The Appendices F-G study the sensitivity to the extractor and NLI clustering choices.

Hyperparameters. For Game of 24, we use beam size $k{=}5$, branching factor $b{=}5$, and depth $T{=}3$. For MuSR, we use beam size $k{=}2$ and nine reasoning rounds. Semantic clustering uses entailment threshold $\tau_{e}{=}0.45$ and contradiction ceiling $\tau_{c}{=}0.3$, chosen to require moderate positive support between hypotheses while excluding pairs with substantial contradictory evidence. Appendix G shows that the results are robust to alternative entailment thresholds and semantic basin constructions. Unless otherwise stated, $\lambda{=}3.0$. Sampling temperatures are $0.7$ for Game of 24 and $0.8$ for MuSR and are held fixed across methods. Appendix K provides compute and implementation details. Appendix J shows prompt templates.

Evaluation metrics. We report accuracy as the primary performance metric and Pass@k when the final beam can contain multiple candidate answers. To characterize search structure, we report the number of visited basins and the effective basin count $N_{\mathrm{eff}}=\exp(-\sum_{z}p_{z}\log p_{z})$, where $p_{z}$ is the fraction of selected states assigned to basin $z$. $N_{\mathrm{eff}}$ equals the number of basins under uniform visitation and decreases as search concentrates on a subset of them, thereby capturing both basin coverage and the evenness of search allocation. We define redundancy as $\rho=\#\mathrm{Basins}-N_{\mathrm{eff}}$ and the redundancy gap as

Thus, $\Delta>0$ indicates that correct searches are more concentrated than incorrect ones. We use these quantities as diagnostics of search structure rather than optimization objectives, since greater basin diversity does not necessarily imply higher accuracy.

Game of 24. Table 1 shows that BASIN improves accuracy from 66.0% to 72.0% with gpt-4o-mini, and from 43.0% to 65.0% with Qwen3-27B ($+22$pp, $p{<}0.01$). The gains occur under the same search budget and exact symbolic verifier. BASIN also increases $N_{\mathrm{eff}}$, particularly for Qwen3-27B, suggesting that ToT spends substantial compute revisiting structurally redundant arithmetic states. We observe similar findings for the BBH logical deduction task (Appendix C) with +13pp in accuracy.

MuSR. Table 3 reports results on 300 MuSR problems. The NLI-based semantic construction is inherently noisier than the exact structural basin definition used for Game of 24, which may limit how precisely the revisit penalty distinguishes genuinely different reasoning strategies. Unlike Game of 24, global diversity changes on MuSR are small. For gpt-oss-120b, BASIN improves both accuracy and Pass@k; for gpt-4o-mini, Pass@k decreases slightly while accuracy increases. We define selection efficiency as $\mathrm{Acc.}/\mathrm{Pass@}k$; BASIN achieves the highest selection efficiency for both models. This suggests that BASIN performance depends not only on exploration but also on the quality of the semantic basin representation. Appendix G shows that accuracy remains stable across alternative semantic constructions. Overall, the gains arise from reallocating search across strategies rather than simply maximizing basin coverage.

Quality-aware selection. We further investigate the exploration–exploitation trade-off in BASIN. Table 2 compares standard ToT, BASIN, and QA-BASIN using gpt-4 (Achiam et al., 2023). On Game of 24, standard ToT obtains 67.0% accuracy, flat BASIN falls to 61.0%, and QA-BASIN reaches 70.0%. On MuSR, the corresponding accuracies are 52.0%, 58.3%, and 58.7%. Notably, on Game of 24 the three methods achieve nearly identical effective basin counts despite substantially different accuracies. This reinforces that the objective is not to maximize basin diversity itself, but to avoid redundant exploration without suppressing promising reasoning regions. QA-BASIN directly addresses this trade-off by weakening the revisit penalty for basins with stronger quality signals.

We next test whether basin-aware selection generalizes beyond the primary Game of 24 and MuSR settings. Table 4 reports accuracy under matched inference budgets on HumanEval and GSM-Hard across four models. Across these settings, QA-BASIN is generally the most robust formulation: it matches or improves upon standard ToT for all four models on HumanEval and achieves the best or tied-best accuracy in three of four GSM-Hard settings. In contrast, flat BASIN sometimes increases exploration without improving accuracy, consistent with an exploration–exploitation trade-off rather than a simple benefit from greater basin coverage. This pattern also extends to additional Game of 24 models: both basin-aware variants improve over ToT on Qwen2.5-7B-Instruct, while QA-BASIN improves Llama-3.3-70B-Instruct from $70\%$ to $75\%$ (Appendix B).

Generalization beyond ToT. Because BASIN modifies candidate selection rather than the topology of a particular search algorithm, we also evaluate it with UCT-based Monte Carlo Tree Search (MCTS) on Game of 24 under matched search budgets. We use 50 simulations per problem and add the basin term only to UCT child selection (Table 5).

QA-BASIN improves over standard MCTS for all four models, by $+18$, $+15$, $+6$, and $+11$ pp, respectively. Flat BASIN, however, helps two models and hurts two. Since MCTS already contains an explicit exploration term, an additional unconditional revisit penalty can over-explore and displace promising regions. The quality-aware variant instead preserves high-quality basins while discouraging repeated visits to weaker ones. We observe the same transfer beyond tree search with Graph of Thoughts (GoT) on MuSR: BASIN improves accuracy from $57\%$ to $60\%$, while QA-BASIN further improves it to $64\%$. Notably, QA-BASIN achieves this gain with lower effective basin coverage than flat BASIN, again illustrating that effective basin-aware search requires balancing exploration with preservation of promising reasoning regions. Full results are reported in Appendix D.

Taken together, these results show that basin-aware selection transfers across tasks, model families, and search algorithms. They also motivate QA-BASIN as the preferred formulation when a reliable quality signal is available: it retains the benefit of escaping repeatedly explored low-quality basins while reducing the over-exploration that can arise from flat BASIN.

If reasoning basin collapse is an important failure mode, BASIN should help most when standard ToT repeatedly concentrates on a small set of strategies. We test this by splitting problems into tertiles according to standard-ToT $N_{\mathrm{eff}}$: high-, mid-, and low-collapse. We then report paired accuracy differences $\Delta\mathrm{acc}=\mathrm{acc}_{\textsc{BASIN}}-\mathrm{acc}_{\mathrm{ToT}}$ in Figure 2. For MuSR, we use the murder-mystery subset to avoid mixing heterogeneous subtasks; Appendix A reports the remaining subsets.

The expected pattern is clearest on Game of 24. With gpt-4o-mini, BASIN gains $+0.21$ accuracy in the high-collapse group, compared with $+0.05$ in the mid-collapse group and $-0.10$ in the low-collapse group. Qwen3-27B shows the same qualitative trend, with most of the improvement concentrated among high-collapse problems.

MuSR is less monotonic: the largest gains occur in the mid-collapse group. Semantic $N_{\mathrm{eff}}$ captures the amount of concentration but not whether the dominant reasoning basin is useful or misleading. This weaker alignment between collapse severity and the need for exploration may partly explain the smaller gains on MuSR relative to Game of 24. Overall, collapse severity is informative but insufficient by itself to determine when additional exploration will help.

The flat BASIN penalty is quality-agnostic: it depends on basin visitation rather than correctness. We use the redundancy gap $\Delta$ from Eq. (5) to analyze how the resulting concentration differs between successful and unsuccessful searches.

Figure 3 shows that standard ToT typically operates near $\Delta\approx 0$ or slightly below: correct and incorrect searches exhibit similar concentration patterns. BASIN consistently shifts $\Delta$ positive, concentrating successful searches around strong regions while dispersing repeated exploration among unsuccessful ones. This separation helps explain why a quality-agnostic revisit penalty can improve accuracy: its effect depends not simply on increasing diversity, but on restructuring where redundancy occurs.

The relationship is useful but not universal. For Qwen3-27b on Game of 24, ToT already has $\Delta=+0.11$, yet BASIN improves accuracy by +22pp. Since ToT solves only 43% of problems in this setting, substantial per-problem collapse onto incorrect arithmetic basins can remain even when the dataset-level gap appears favorable. Thus, $\Delta$ summarizes average search behavior but can obscure substantial per-problem heterogeneity.

The redundancy gap therefore provides a useful summary of how search concentration differs between successful and unsuccessful trajectories, but it does not by itself determine when additional exploration will improve accuracy. We therefore evaluate whether $\Delta$ can be used as a routing signal for choosing between standard search and BASIN. Across six model–task settings spanning Game of 24 and BBH, $\Delta$ alone selects the empirically better fixed policy in only $2/6$ cases. Combining it with a per-problem search-effort signal—the number of tree nodes explored before termination—increases this to $5/6$; Appendix H provides the full routing analysis. Thus, we treat the redundancy gap primarily as a diagnostic of search structure, while adaptive policies should combine it with additional search-state or quality signals.

Effect of compute budget. Figure 4 varies the number of reasoning rounds on 100 randomly selected MuSR problems with gpt-oss-120b, holding beam size fixed. Accuracy generally improves with additional reasoning depth, while $N_{\mathrm{eff}}$ also increases. Basin-aware exploration is therefore most useful when the search budget is large for alternative strategies to develop into complete solutions.

Effect of penalty strength. Figure 5 varies $\lambda\in\{0.5,1.0,1.5,2.0,3.0,4.0,5.0\}$ in the same MuSR setting. Accuracy peaks at $\lambda{=}3.0$ and is relatively stable over moderate values. $N_{\mathrm{eff}}$ increases with $\lambda$, but accuracy is non-monotonic: weak penalties have little effect, whereas overly strong penalties can override useful base-score differences. This again shows that the goal is not maximal diversity, but an effective exploration–exploitation balance.

How important is the quality signal? Because QA-BASIN uses basin quality to modulate the revisit penalty, its performance depends on the informativeness of that signal. On MuSR with gpt-4, using an LLM-based quality signal yields 58.7% accuracy, compared with 58.3% for flat BASIN and 52.0% for standard ToT. Replacing this signal with the search heuristic reduces accuracy to 33.7%. Thus, quality-aware modulation is beneficial when the quality estimate is informative, but can be actively harmful when it is poorly calibrated to correctness. We therefore recommend QA-BASIN when a meaningful quality signal is available and flat BASIN otherwise. Appendix E provides the full results and analyzes the discriminative quality of the heuristic score.

Is BASIN Just Promoting Diversity? The improvement from BASIN is not explained by generic diversity promotion. On Game of 24 with gpt-4o-mini, a Diverse Beam Search (DBS)-style baseline (Vijayakumar et al., 2016) achieves 64.0% accuracy, compared with 66.0% for standard ToT and 72.0% for BASIN. Thus, encouraging diverse candidates alone does not reproduce the gain from explicitly modeling strategy-level redundancy. We further vary the sampling temperature as an alternative way to increase token-level diversity (Fig. 6). Across $T\in\{0.7,1.0,1.2,1.5\}$, the best higher-temperature ToT configuration reaches 68.0% accuracy, still below BASIN’s 72.0% at $T=0.7$. Increasing temperature within BASIN also does not improve performance. These results show that token-level or candidate-level diversity is not interchangeable with history-biased, basin-level selection: BASIN benefits from identifying and penalizing repeated reasoning strategies rather than simply making individual candidates more different.

We illustrate how BASIN reallocates search effort on Game of 24; a MuSR example appears in Appendix I.

Game of 24: ${1,11,11,13}$. Under standard ToT, the first-step beam contains the same symbolic state twice:

11 - 1 = 10, 13 - 11 = 2, 11 * 1 = 11, 11 + 11 = 22, 11 - 1 = 10.

The first and final candidates both map to basin sub|10,11,13, so one beam slot is spent revisiting the same arithmetic state. After its first visit, BASIN lowers the score of this basin, allowing the alternative $1+11=12$ to survive. This new basin leads to

No new generator, operation, or verifier is introduced; the search simply allocates its existing beam budget across distinct symbolic strategies.