Break the Chain, Gain a Margin: A Theory of Multi-Step Reasoning in LLMs

Despite advances in retrieval-augmented reasoning through reinforcement learning (RL), it remains unclear when and why language models struggle with multi-step reasoning. We study this issue using a graph-based mathematical framework, in which a language model (LM) identifies valid reasoning steps by using statements as nodes and correct links as edges. We present a key theoretical result suggesting that such LMs are capable of internally identifying long reasoning chains. However, without multi-step reasoning, their confidence (margin) in distinguishing true from false links decreases as chains grow longer, making long-range dependencies increasingly error-prone. Motivated by this analysis, we develop theoretical principles for multi-step reasoning that break long chains into shorter segments with larger training margins. We instantiate these principles in PHyRR (Plan-Conditioned Hypergraph Retrieval-Reasoning), a reinforcement learning framework for question answering (QA). PHyRR first decomposes queries into smaller sub-goals during planning, then performs hypergraph retrieval and reasoning adaptively based on the resulting plan. Its RL rewards further encourage reasoning steps that are theoretically predicted to be more effective. Experiments confirm the predicted margin behavior and show that PHyRR outperforms baselines across four QA benchmarks, with the largest improvements on multi-hop reasoning tasks.