The Reasoning Depth vs. Width Dilemma: A Formal Model and Adaptive Inference Algorithm

We investigate the trade-off between reasoning \emph{depth} (sequential inference length) and \emph{width} (parallel exploration) in large reasoning models (LRMs). While depth enables multi-hop deduction, width supports uncertainty resolution and robustness. Existing inference schemes rely on heuristics balancing these two factors, often resulting in inefficient compute allocation. We develop a formal framework modeling reasoning as a directed acyclic graph (DAG) search problem with compute-aware cost functions. We derive theoretical lower bounds on the \emph{Reasoning Complexity} of problem classes, proving that both purely depth-first and width-first strategies are suboptimal under bounded compute. Building on this, we propose the \emph{Adaptive Depth–Width Search (ADWS)} algorithm—an inference-time adaptive policy that dynamically allocates computation based on learned halting and branching policies. Experiments on LLM reasoning benchmarks (GSM8K, StrategyQA, ProofWriter, and LastLetter) demonstrate statistically significant gains in accuracy (p $<$ 0.01) and compute efficiency compared to fixed-structure baselines. The proposed framework advances understanding of the depth–width reasoning trade-off, offering a unified theoretical and empirical lens on adaptive inference.