PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Lu Cheng

arXiv:2609.00738v1cs.AI

TL;DR

Inference-time LLM search can concentrate on redundant reasoning strategies, leaving alternatives underexplored. This paper introduces BASIN, which groups states into reasoning basins and penalizes repeated visits, plus QA-BASIN for quality-aware exploration. Across tasks and models, basin-aware selection improves matched-budget search, while the redundancy gap helps characterize harmful redundancy but is insufficient alone for adaptive decisions.

  • Problem

    Inference-time search may generate many trajectories without exploring distinct reasoning strategies, because standard procedures can repeatedly revisit equivalent paths.

  • Method

    BASIN is a training-free, structure-aware selection method that groups reasoning states into strategy-level basins and penalizes repeated visits; QA-BASIN weakens penalties for high-quality basins.

  • Results

    Basin-aware selection improves search across symbolic, natural-language, mathematical, and code tasks under matched inference budgets, with QA-BASIN yielding more robust gains.

  • Takeaways & Limitations

    The findings support structure-aware search as a broader principle, while adaptive policies should jointly consider redundancy and search quality.

  • Takeaways & Limitations

    Basin definitions are task-dependent, semantic grouping adds extraction and NLI cost, and the redundancy gap alone cannot determine when exploration will help.

Abstract

from arXiv · show

Inference-time search with large language models (LLMs) often concentrates on a small set of structurally or semantically similar trajectories, leaving alternatives underexplored---a failure mode we call \textit{reasoning basin collapse}. We introduce BASIN, a training-free, structure-aware selection method that groups reasoning states into basins and penalizes repeated visits to the same strategy, thereby reallocating search across genuinely distinct reasoning paths under a fixed compute budget. Under matched inference budgets, BASIN improves over Tree of Thoughts (ToT) by up to $+22$pp on Game of 24 and $+6.7$pp on MuSR. A quality-aware variant, QA-BASIN, further improves robustness by preserving high-quality basins when unconditional diversification over-explores. To explain when basin-aware selection helps, we introduce the redundancy gap $Δ$, which measures how differently search concentrates for correct versus incorrect predictions: standard ToT often operates near $Δ\approx 0$, while BASIN consistently shifts $Δ$ positive. More broadly, BASIN suggests structure-aware selection as a simple and general approach to improving inference-time reasoning. Code can be found at https://github.com/GitHubLuCheng/basin.

1 Introduction

Inference-time search can repeatedly explore equivalent reasoning strategies, producing reasoning basin collapse rather than meaningful diversity. BASIN and QA-BASIN address this through structure-aware selection, improving search across tasks while diagnosing when redundancy is harmful.

  • Motivation: Reasoning basin collapse occurs when inference-time search revisits equivalent reasoning paths instead of exploring genuinely different strategies.Standard search can spend substantial inference budget on structurally or semantically similar trajectories.
  • Motivation: 38% of the search budget reaches genuinely new reasoning strategies under standard Tree of Thoughts on MuSR.Incorrect searches can concentrate on wrong basins just as correct searches concentrate on right ones.
  • Basin representation: A reasoning basin groups states pursuing the same underlying strategy, using deterministic structural features or semantic equivalence depending on the task.Semantic grouping can use a central hypothesis and natural language inference, separating strategy diversity from surface variation.
  • BASIN: BASIN applies a logarithmic penalty to candidates from over-visited basins, reallocating selection toward underexplored strategies without training.Strong candidates from previously visited basins can remain competitive.
  • QA-BASIN: QA-BASIN weakens revisit penalties for high-quality basins, addressing cases where unconditional exploration diverts fixed compute toward weaker alternatives.Both methods operate only during candidate selection and require no changes to the underlying generator.
  • Empirical findings: Across multiple reasoning domains, basin-aware selection improves matched-budget search, while QA-BASIN provides more robust gains across models, tasks, and search frameworks.The redundancy gap Δ is near zero for standard ToT and shifts positive with BASIN, but remains insufficient as a standalone predictor.
  • Contributions: The paper formalizes reasoning basins, introduces BASIN and QA-BASIN, and proposes the redundancy gap Δ as a diagnostic for harmful search redundancy.These contributions target inference-time search under fixed budgets across multiple domains, models, and search frameworks.

2 Related Work

Related work develops reasoning through intermediate steps, search, reflection, verification, adaptive effort allocation, and diversity-promoting decoding. These approaches provide context for BASIN’s focus on reducing redundant reasoning at the strategy level.

  • Reasoning with intermediate steps: Chain-of-thought prompting elicits step-by-step reasoning, while later methods improve intermediate rationales through decomposition, exemplar selection, and complexity-based sampling.The supplied passage also references Zero-shot-CoT as a way to elicit reasoning without demonstrations.
  • Search-based reasoning: Tree of Thoughts frames LLM reasoning as search over intermediate states, with extensions to graph-structured reasoning, planning, and agentic tree search.Recent work also studies search-efficiency improvements and learned controllers for expansion, branching, and backtracking.
  • Reflection, refinement, and verification: Reflection, refinement, verification, and adaptive allocation methods improve outputs or guide future attempts through feedback, revision, evaluators, or effort scheduling.The passage names Self-Refine, Reflexion, verifier-based approaches, and recent test-time allocation methods.
  • Diversity-promoting search and decoding: Diversity-promoting methods discourage near-duplicate candidates or elicit distinct solution approaches to broaden exploration.The passage situates BASIN closest in spirit to diversity-promoting search, though its objective is truncated here.

3 Method

BASIN makes redundancy explicit by grouping reasoning states into strategy-level basins and penalizing repeated selection, using structural or semantic equivalence according to task structure. QA-BASIN moderates this penalty with basin quality, while the selection mechanism remains applicable beyond ToT.

  • Reasoning basins: BASIN groups states that pursue the same underlying reasoning strategy, distinguishing strategic redundancy from surface-level textual variation.States may share a core hypothesis or relevant continuation structure even when their textual realizations differ.
  • Reasoning basins: The basin assignment function maps each state to a discrete basin identifier and treats states sharing an identifier as repeated exploration.Explicitly structured tasks use deterministic definitions, whereas open-ended tasks use semantic approximations.
  • Structural basins: For structured arithmetic tasks, basin membership uses the ordered operation sequence and sorted remaining values, preserving distinctions between different operation orders.This representation captures task-relevant redundancy with lightweight deterministic parsing.
  • Semantic basins: For open-ended tasks, BASIN extracts a central hypothesis and uses answer agreement plus NLI compatibility to group semantically equivalent reasoning states.NLI is preferred over embedding similarity because shared narrative context can mask different hypotheses; clustering granularity is controlled by τe and τc.
  • Basin-aware selection: BASIN replaces the underlying candidate score with a history-dependent logarithmic penalty based on how often the candidate’s basin was previously selected.The shared visit count penalizes redundant trajectories collectively, with increasing but sublinear pressure that does not forbid revisits.
  • Quality-aware BASIN: QA-BASIN weakens revisit penalties for high-quality basins while retaining stronger penalties for weaker ones, addressing the exploration–exploitation trade-off.Its effectiveness depends on the verifier providing a meaningful quality signal.
  • General applicability: Basin-aware selection changes only candidate selection within ToT and can also be used with other repeated-selection search procedures, including Graph of Thoughts and UCT-based MCTS.The principle is agnostic to whether basin membership is structural or semantic, although deterministic task-specific keys are preferred when available.

4 Experiments

Across symbolic, natural-language, and other reasoning tasks, basin-aware selection improves inference-time search under matched budgets, but its benefits depend on avoiding both redundant and excessive exploration. QA-BASIN is generally more robust because it preserves promising basins while discouraging repeated visits to weaker ones.

  • Main Results: Game of 24 accuracy rises from 66.0% to 72.0% with gpt-4o-mini and from 43.0% to 65.0% with Qwen3-27B under the same budget.The Qwen3-27B improvement is +22pp (p<0.01), and BASIN also increases Neff.
  • Main Results: BASIN improves accuracy on BBH logical deduction by +13pp and produces task-dependent MuSR gains despite noisier semantic basin construction.On MuSR, BASIN improves both accuracy and Pass@k for gpt-oss-120b, while gpt-4o-mini gains accuracy despite a slight Pass@k decrease.
  • Generalization: QA-BASIN is more robust than flat BASIN when exploration can displace promising regions, improving standard MCTS by +18, +15, +6, and +11 percentage points across four models.Flat BASIN helps two MCTS models and hurts two, whereas quality-aware modulation preserves high-quality basins.
  • Collapse-Stratified Analysis: On Game of 24, BASIN gains +0.21 accuracy in high-collapse problems with gpt-4o-mini, versus +0.05 mid-collapse and −0.10 low-collapse.MuSR is less monotonic: its largest gains occur in the mid-collapse group, so collapse severity alone is insufficient.
  • Redundancy Gap: The redundancy gap shifts positive under BASIN, indicating different concentration patterns for successful and unsuccessful searches rather than diversity increases alone.Across six model–task settings, the gap alone selects the better fixed policy in only 2/6 cases, increasing to 5/6 when combined with search effort.
  • Ablations: Accuracy peaks at λ=3.0 and is non-monotonic with penalty strength, while informative quality signals help QA-BASIN and poorly calibrated signals can reduce accuracy to 33.7%.On MuSR with gpt-4, QA-BASIN reaches 58.7% with an LLM-based quality signal, versus 58.3% for flat BASIN and 52.0% for ToT.
  • Ablations: Diverse Beam Search reaches 64.0% and higher-temperature ToT reaches 68.0% on Game of 24, below BASIN’s 72.0%, showing that generic diversity does not reproduce basin-level selection.The comparison supports penalizing repeated reasoning strategies rather than merely increasing token- or candidate-level variation.

5 Discussion

BASIN treats reasoning redundancy at the strategy level rather than maximizing surface diversity, while QA-BASIN balances exploration with preserving promising regions. The redundancy gap is informative as a diagnostic but insufficient alone for routing, and basin representations remain task-dependent.

  • BASIN reallocates search across distinct strategies by penalizing repeated visits to the same reasoning basin, reducing shared error modes.
  • Generic candidate- or token-level diversity does not reproduce strategy-aware gains, so increasing Neff is not itself the objective.
  • The redundancy gap shifts positive under BASIN, but it selects the better fixed policy in only 2/6 settings alone versus 5/6 with search-effort signals.
  • Flat BASIN helps when baseline search repeatedly commits compute to an unproductive basin but can hurt when concentration reflects useful exploitation.
  • QA-BASIN weakens revisit penalties for high-quality basins and is more robust across tasks, models, and search frameworks than unconditional penalties.
  • Basin effectiveness depends on meaningful representations: exact structural keys are preferable, while semantic clustering approximates equivalence for open-ended tasks.

A MuSR Per-Subtask Results

MuSR subtask results show that BASIN’s benefits depend on whether concentration reflects harmful underexploration or useful agreement. Across related transfer evaluations, strategy-level reallocation improves some settings but unconditional exploration can also reduce accuracy.

  • Murder mysteries: Murder mysteries show small, statistically insignificant gains, while high baseline Pass@k values indicate limited room for improving candidate coverage.
  • Object placement: +0.082 accuracy for gpt-oss-120b on Object placement accompanies Neff = 4.18 and Pass@k = 0.755 under standard ToT.
  • Object placement: -0.036 final accuracy for gpt-4o-mini on Object placement shows that low Neff alone does not establish harmful collapse.
  • Team allocation: +0.062 accuracy for gpt-4o-mini on Team allocation contrasts with no change for gpt-oss-120b, whose baseline Neff is 8.76.
  • Summary: Across six task–model combinations, significant positive results occur where exploration recovers or preserves alternatives, while unconditional penalties can over-explore useful consensus.
  • Transfer evaluation: 13pp accuracy improvement over standard ToT on BBH Logical Deduction coincides with Neff increasing from 4.50 to 5.60.

D Graph-of-Thought Backbone

BASIN transfers to a Graph-of-Thought backbone without changing its aggregation mechanism. QA-BASIN achieves the strongest result by preserving useful reasoning regions even without maximizing basin coverage.

  • 3pp accuracy improvement from 57% to 60% occurs when flat BASIN is applied to GoT on MuSR.
  • QA-BASIN reaches 64%, a 7pp gain over standard GoT, despite reducing Neff to 5.12 and escape rate to 45.8%.
  • GoT aggregation changes beam answers on 16–18% of problems and selects the correct answer in 64–69% of changed cases.
  • Basin-aware selection determines which strategies survive search, while GoT aggregation combines resulting trajectories afterward.

E Sensitivity to the Quality Signal

QA-BASIN’s effectiveness depends on the quality signal used to modulate revisit penalties. NLI-based semantic clustering provides more useful strategy-level structure than embedding similarity, but approximate representations add cost and uncertainty.

  • Quality signal: Heuristic score AUC is near chance at 0.510 for GoT and 0.516 for GoT+BASIN, indicating little direct information about trajectory correctness.
  • Quality signal: 33.7% accuracy with the search heuristic shows that poorly calibrated quality signals can make QA-BASIN actively harmful.
  • Quality signal: Flat BASIN requires no basin-quality estimate, whereas QA-BASIN is preferred when an informative verifier or quality estimate is available.
  • Basin representation: Semantic basin definitions require approximate representations with extraction and NLI cost, and their effectiveness depends on capturing meaningful redundancy.

G Semantic Basin Sensitivity

BASIN’s MuSR accuracy gains remain robust across tested semantic basin constructions, although the representation changes detailed search behavior and remains a modeling sensitivity.

  • Experimental design: The sensitivity analysis reruns the full search while varying the entailment threshold, NLI model, and hypothesis extractor.This varies the semantic construction during search rather than merely reclustering fixed trajectories afterward.
  • Sensitivity results: Accuracy remains between 0.620 and 0.640 and exceeds standard ToT under every tested semantic basin definition.Pass@k is more sensitive to the hypothesis extractor than accuracy.
  • Sensitivity results: The contradiction ceiling has no observable effect over τc ∈{0.20, 0.30, 0.40} in these experiments.The entailment criterion already removes most incompatible pairs.
  • Interpretation: Semantic basin construction is a genuine source of modeling sensitivity despite robust accuracy improvements across the tested configurations.The representation affects detailed search trajectories and basin counts.

H Redundancy Gap as a Routing Signal

The redundancy gap is informative about search structure but insufficient alone for routing; combining it with inexpensive problem-level search signals improves adaptive selection.

  • Routing rules: The aggregate rule selects BASIN whenever Δρ ≤ 0, while the combined rule adds per-problem routing in the Ambiguous regime.The combined rule keeps higher-node problems under standard ToT.
  • Routing results: Using Δρ alone selects the empirically better fixed policy in only 2/6 settings (33.3%).Its main failure mode is the Ambiguous regime, where BASIN improves accuracy in all three experiments despite Δρ > 0.
  • Routing results: Adding the already-available n_nodes signal raises routing decision accuracy to 5/6 settings (83.3%).Problems at or below the experiment-specific median are routed to BASIN in the Ambiguous regime.
  • Routing results: On Game24/gpt-4o-mini, routed accuracy reaches 0.760 versus 0.660 for standard ToT and 0.720 for BASIN.On Game24/Qwen3-27B, routing reaches 0.700 versus 0.430 and 0.650, respectively.
  • Interpretation: The redundancy gap is a useful diagnostic of search structure but insufficient as a standalone criterion for increasing exploration.Combining redundancy information with inexpensive problem-level search-state signals is a more promising basis for adaptive search.

I Case Study: MuSR Murder Mystery: murder_mysteries_185

The MuSR case study shows standard ToT repeatedly selecting lexically varied explanations that share one strategy, while BASIN preserves a distinct alternative that yields the correct answer.

  • Case Study: MuSR Murder Mystery: murder_mysteries_185: Nicole is the correct answer because she owns an authentic medieval crossbow, remained at the crime scene, and is linked to suspicious deaths among acquaintances.Preserving this alternative changes the final candidate set and allows the correct answer to be selected.
  • Case Study: MuSR Murder Mystery: murder_mysteries_185: Under standard ToT, most terminal hypotheses reuse Isabelle’s crossbow skill and presence at the crime scene, leading the search to predict Isabelle.The explanations differ in surface form but share the same core strategy.
  • Case Study: MuSR Murder Mystery: murder_mysteries_185: Lexically different trajectories are assigned to one semantic basin when they share the same answer and central hypothesis.Repeated selection then elaborates the same explanation instead of testing materially different alternatives.
  • Case Study: MuSR Murder Mystery: murder_mysteries_185: BASIN reduces the relative score of revisits to the Isabelle-centered basin, retaining a distinct Nicole-centered explanation.The alternative combines weapon ownership, crime-scene ownership, and suspicious deaths.
  • Case Study: MuSR Murder Mystery: murder_mysteries_185: The example illustrates a cross-domain mechanism in which search repeatedly selects states instantiating the same underlying strategy.BASIN uses this structure to discourage redundant revisits and reallocate budget toward underexplored alternatives.
  • Case Study: MuSR Murder Mystery: murder_mysteries_185: The compared search methods use identical generation prompts, while MuSR shares the same hypothesis-extraction and semantic-clustering pipeline across conditions.BASIN and standard search therefore differ in candidate selection rather than generation prompts or semantic preprocessing.

K Compute Resources

The experiments use external model APIs and CPU-based semantic clustering, with no local GPU required, but open-ended semantic basin construction adds substantial computation and API usage.

  • Compute Resources: LLM inference uses external model APIs and multithreaded calls across problems, rather than local GPU inference.The reported experiments include gpt-4o-mini, gpt-4, gpt-oss-120b, and Qwen3-27B.
  • Compute Resources: MuSR uses 18 reasoning-generation calls and 18 hypothesis-extraction calls per problem, totaling 36 LLM calls.Hypothesis extraction adds 100% identical across compared MuSR search conditions.
  • Compute Resources: NLI-based clustering runs on CPU, taking approximately 4–11 s per problem for roughly 18 states, plus 2.6 s model loading per worker.The implementation recomputes same-answer pairwise scores rather than updating clusters incrementally.
  • Compute Resources: Deterministic structural basin definitions require only basin-key construction, visit-statistic maintenance, and candidate-score modification.These tasks do not require hypothesis extraction or NLI computation.
  • Compute Resources: Semantic basin construction is not computationally negligible because it substantially increases API inference and doubles MuSR LLM calls relative to generation alone.This cost is identified as a limitation of the current open-ended implementation.
Loading 2609.00738v1…