Escaping Redundant Reasoning: Structure-Aware Search for Inference-Time LLMs

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 textitreasoning basin collapse. We introduce textscBASIN, 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, textscBASIN improves over Tree of Thoughts (ToT) by up to +22pp on Game of 24 and +6.7pp on MuSR. Because indiscriminate diversification can over-explore once search has found a promising basin, we further introduce textscQA-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 redundancy gap Delta, which measures the difference in search concentration between correct and incorrect predictions: standard ToT often operates near Delta ≈ 0, whereas textscBASIN 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