Escaping Reasoning Basin Collapse with History-Biased Search

Abstract

Inference-time search with large language models (LLMs) often concentrates on a small set of structurally or semantically similar trajectories, leaving alternative reasoning strategies underexplored---a failure mode we call \textit{reasoning basin collapse}. We introduce \textsc{BASIN}, a training-free, history-biased search method that groups reasoning states into basins and accumulates a revisit penalty on repeatedly selected basins, reallocating a fixed inference budget toward underexplored reasoning strategies. Under matched inference budgets, \textsc{BASIN} improves over Tree of Thoughts (ToT) by up to $+22$pp on Game of 24 and $+6.7$pp on MuSR. Because indiscriminate diversification can over-explore once search has found a promising basin, we further introduce \textsc{QA-BASIN}, a quality-aware variant that weakens the revisit penalty for high-quality basins and yields more robust gains. To characterize when basin-aware search helps, we introduce the \emph{redundancy gap} $\Delta$, which measures the difference in search concentration between correct and incorrect predictions: standard ToT often operates near $\Delta \approx 0$, whereas \textsc{BASIN} consistently shifts $\Delta$ positive. Together, these results identify reasoning basin collapse as a failure mode of inference-time search and show that history-dependent bias provides a simple, training-free mechanism for escaping redundant reasoning under fixed compute. Code is available at https://github.com/GitHubLuCheng/basin

arXiv commentAccepted to NeurIPS'26