Backtracking with Linear-in-Depth Search-Space Growth: Width-Limited Tree Search for Large Language Models

Inference-time search offers a principled way to improve the reliability of large language models (LLMs) by exploring and scoring intermediate trajectories. However, widely used search paradigms exhibit complementary failure modes: sequence search scales linearly but commits early and cannot recover from mistaken prefixes, whereas tree search can backtrack but often becomes impractical for deep search due to the exponential growth of the search space with depth. These limitations become increasingly pronounced in long-chain-of-thought responses. We propose Width-Limited Tree Search (WLTS), which reconciles these strengths by preserving the tree-search structure that enables backtracking while using a dynamic expandability criterion to enforce a strict per-layer width constraint. This design keeps generated search-tree growth linear in depth and sustains verifier supervision across the full reasoning process. WLTS further supports two optional deployment components: prefix deletion for diversity and agreement-based early stopping to reduce computation on tasks with canonicalizable outputs. Across mathematical, coding, and logical reasoning benchmarks, and under both classifier and generative verifier settings, WLTS achieves higher accuracy and better inference-budget efficiency than well-established sequence- and tree-search baselines.