Long-horizon reasoning — the ability to chain together many logical steps to solve a complex problem — is one of the most difficult challenges for large language models. As the number of reasoning steps grows, even small errors accumulate, and models that perform well on short tasks frequently collapse when required to reason over many steps. Two researchers from Virginia Tech, along with collaborators from Dartmouth College and the University of Wisconsin-Madison, have identified the root causes of this brittleness as two distinct but interacting biases, and proposed a framework called SAGE that addresses both through structural guidance drawn from the geometry of the reasoning space itself.
Two Biases, One Problem
The team identifies two specific biases that cause long-horizon reasoning to fail under sparse-reward regimes — where the model receives feedback only at the end of a long chain of reasoning steps, not along the way.
The first is exploration bias. As the reasoning tree expands with depth, the number of possible trajectories grows exponentially, but successful trajectories occupy a vanishingly small fraction of the reachable space. Many intermediate steps are locally valid — each individual move is logically sound — but they lead into branches that cannot extend to success. A model trained with outcome-only feedback tends to favor trajectories that are easy to sample rather than trajectories that remain structurally extendable to the end.
The second is compounding bias. When rewards are sparse, with meaningful signal available only at the trajectory's end, small local deviations cannot be corrected early. Instead, they accumulate across depth, progressively steering the trajectory away from long-term feasibility. In KL-regularized post-training, when successful trajectories are rare under the reference policy, the reward signal is too weak to pull the learned policy meaningfully away from reference-model behavior. Locally plausible deviations persist rather than being corrected, and their failure surfaces only several steps later.
These two biases interact. Exploration bias sends the model into unproductive branches, and compounding bias prevents it from recovering once it has drifted. Together, they explain why LLMs can produce plausible intermediate steps while still failing at end-to-end long-horizon reasoning.
Symbolic Closure Analysis: A Theoretical Lens
Before designing a solution, the team developed a theoretical framework called Symbolic Closure Analysis (SCA) to characterize precisely how these biases arise. SCA models reasoning as a sequence of locally admissible transformations and studies how feasible support evolves as the reasoning space expands with depth.
The core insight is that local admissibility induces a prefix-closed feasible region: if any prefix of a trajectory violates the local structural requirements, all its continuations are infeasible. This means that the geometry of the feasible region — specifically, how much of the exponentially growing search space actually contains extendable trajectories — determines the severity of exploration bias. The analysis yields a quantitative bound: the fraction of the reachable space occupied by feasible trajectories scales as the product of ratios between locally admissible and total branching factors at each depth step. When the locally admissible branching factor is much smaller than the total branching factor at many depths, unconstrained rollouts concentrate almost entirely outside the feasible region.
For compounding bias, SCA provides a matching theoretical account. Under KL-regularized post-training with terminal-only rewards, the team proves a theorem showing that when successful trajectories are rare under the reference policy, the optimizer's distance from the reference policy is bounded by a term proportional to the success probability. If successful trajectories are vanishingly rare, the optimizer has limited leverage to move probability mass away from reference-likely prefixes — meaning locally inadmissible prefixes survive optimization and continue to accumulate errors.
How SAGE Works
SAGE, short for Structural Admissibility-Guided Exploration, translates the SCA diagnosis into two complementary trainable guidance signals.
Algebraic sparsification targets exploration bias by biasing the model's sampling toward operators that address the current unresolved symbolic residual. For each candidate operation, the method computes how much of the remaining problem structure that operation addresses. This produces a soft compatibility score — not a hard constraint that replaces local admissibility — that promotes feasible-support concentration without requiring the model to enumerate or filter the entire search space. The effect is to make the model prefer operations that structurally advance toward a solution rather than operations that merely look plausible.
Hyperbolic structural guidance targets compounding bias by embedding reasoning states into a negatively curved hyperbolic space, where hierarchical and tree-like structures are naturally represented. This provides dense depth-aware signals before terminal rewards arrive, giving the model information about whether its current trajectory is structurally on track. The hyperbolic embedding measures the distance between the current state (after applying a candidate operation) and the target structure, producing a signal that grows richer as the trajectory deepens. This addresses the core problem of compounding bias: without intermediate feedback, small deviations accumulate silently; with hyperbolic guidance, the model receives a depth-aware structural signal at every step.
The two potentials are combined into a unified guidance signal and injected during policy optimization. Crucially, the structural preferences are absorbed into the policy during training, so inference incurs no additional search or filtering overhead — the model simply reasons faster and more reliably.
Results Across 12 Benchmarks and 7 Models
SAGE was evaluated across 12 benchmarks spanning three families: closed-form mathematical reasoning (MATH, Minerva Math, AMC23, AIME 2024, OlympiadBench, GSM8K, Putnam), free-form natural reasoning (MMLU-Pro, GPQA, BBH-H, ARC-C), and a real-world long-horizon symbolic reasoning task (the Andrews-Curtis problem).
On mathematical reasoning, SAGE consistently improves outcome-level accuracy across all model scales. At the 9B parameter level, average accuracy across seven benchmarks rose from 29.01% for the base model to 47.95% with SAGE, surpassing the strongest baseline (EMPO) by 3.11 percentage points. At the 35B level, SAGE achieved 64.86% average accuracy, substantially exceeding the Llama-3.3-70B-Instruct flagship at 38.48% while using roughly half the parameters. Gains were particularly pronounced on the hardest competition-style benchmarks — Olympiad, AIME, and Putnam — where long-horizon reasoning is most demanding.
The benefits generalize beyond structured formal domains. On free-form natural reasoning, SAGE raised BBH-H accuracy from 44.04% to 45.31% at 9B, and from 60.71% to 69.07% at 35B, leading among question-only post-training methods across all scales.
The most striking results came on the Andrews-Curtis problem, an open mathematical challenge where the goal is to transform a group presentation into a trivial one through a long sequence of admissible symbolic moves. This task perfectly embodies the two biases: many legal moves are locally valid but structurally unstable, and small deviations accumulate over many steps. SAGE achieved up to an 8-fold improvement over baseline models on this task, with gains of +19.2 to +26.0 percentage points on AC validity (local step correctness) and over +13 percentage points on Lean-verified proofs (end-to-end rigor).
The Components Are Complementary, Not Redundant
An ablation study confirmed that both algebraic sparsification and hyperbolic structural guidance contribute independently. Removing either component degrades performance. Two additional controls ruled out the possibility that the gains came from generic dense shaping: replacing hyperbolic distance with Euclidean distance weakened performance, and shuffling the target anchors substantially reduced both accuracy and reward density. This confirms that the hyperbolic geometry — with its natural fit for hierarchical reasoning structures — provides a property that simple distance metrics cannot replicate.
The team also compared SAGE against a learned process reward model baseline. While a learned process reward model does improve over standard reinforcement learning from human feedback, SAGE still outperforms it. The key advantage is that SAGE's structural guidance is computable without gold reasoning traces or dense process labels — it relies solely on the task's algebraic structure, making it applicable to domains where expensive process supervision is unavailable.
Limitations and Open Questions
The paper acknowledges several limitations. The SCA framework was developed and validated primarily in symbolic domains where local admissibility is well-defined. Extending it to domains with softer or implicit structural constraints — such as open-ended creative reasoning or scientific discovery — remains an open challenge. The hyperbolic embedding requires careful tuning of its sharpness parameter, and the team notes that hyperparameter sensitivity is an area for further investigation. Additionally, while the Andrews-Curtis results are dramatic, they come from a specific problem family; broader validation across diverse long-horizon domains would strengthen confidence in the approach's generality.
The paper also notes that SAGE does not eliminate exploration or compounding biases entirely — it mitigates them. Even with SAGE, models still fail on some long-horizon tasks, and the gap between feasible and infeasible trajectories does not vanish. The structural guidance makes the model's search more efficient but does not make long-horizon reasoning trivial.
What This Means for Reasoning Systems
SAGE represents a shift in how we think about improving long-horizon reasoning. Rather than simply training on more examples or increasing model scale, it injects structural priors about the geometry of reasoning spaces directly into the learning process. The insight is that reasoning is not just about knowing facts or applying rules — it is about navigating a space where most paths lead nowhere, and where the structure of the space itself can guide the search.
For practitioners, the practical appeal is clear: the method requires no additional inference-time computation, no dense process supervision, and no architectural changes. It is a training-time intervention that makes existing models more reliable at long-horizon reasoning. The open-sourcing of the codebase further enables the research community to build on this work and extend the approach to new domains.
More broadly, the paper establishes that the two biases — exploration bias from structural complexity and compounding bias from sparse rewards — are not merely practical obstacles but mathematically characterizable phenomena. Understanding them through SCA provides a principled foundation for designing structural guidance that targets their specific mechanisms, rather than applying generic regularization.