SAGE: Mitigating Long-Horizon Reasoning Biases via Topological Guidance

AI summary

Overview

Research area: Large language model reasoning, specifically reinforcement learning post-training for long-horizon reasoning under sparse rewards.

Technical level: Advanced. The paper combines MDP formalism, KL-regularized policy optimization analysis, total-variation bounds, and hyperbolic (Poincaré) embeddings with large-scale empirical evaluation.

Scope: The paper proposes a theoretical lens (Symbolic Closure Analysis) for why LLMs fail at long-horizon reasoning, and a training framework (SAGE) that injects two structural guidance signals to counter those failures across 12 benchmarks and 7 model families.

What This Paper Is About

Outcome-based post-training of LLMs becomes brittle when reasoning horizons are long and rewards arrive only at the end of a trajectory. The authors argue this brittleness comes from two coupled biases: an exploration bias, where models are pulled toward locally plausible but structurally unextendable branches, and a compounding bias, where small early deviations accumulate across depth because no intermediate signal corrects them. The goal is to characterize these biases formally and to build a post-training framework that mitigates both without dense process labels or ground-truth solution paths.

Key Contributions

1. Symbolic Closure Analysis (SCA): A theoretical framework that defines a prefix-closed feasible region induced by a local admissibility predicate, and uses it to show how structural complexity dilutes feasible support (exploration bias) and how sparse terminal rewards leave deviations uncorrected (compounding bias).

2. SAGE (Structural Admissibility-Guided Exploration): A unified post-training framework combining two structural potentials: algebraic sparsification, which projects locally admissible candidates onto operator-indexed algebraic subspaces to suppress spurious branching, and hyperbolic structural guidance, which embeds reasoning states into negatively curved space to supply dense depth-aware signals.

3. Theoretical guarantees: A variance decomposition over feasible versus inadmissible regions (Proposition 3.4), a reference-anchoring bound for terminal-only KL-regularized optimization (Theorem 3.5), a non-vanishing structural advantage result under uninformative terminal rewards (Proposition 4.1), and an exponential feasible-support concentration bound (Proposition 4.2).

4. Large-scale evaluation: Experiments across 12 benchmarks and 7 model families, including the open real-world Andrews-Curtis (AC) problem, where SAGE achieves up to an 8-fold improvement. (The paper's contribution list states "13 benchmarks and 8 models"; the abstract, introduction, experiment section, and conclusion state 12 benchmarks and 7 model families.)

Main Findings

• Consistent accuracy gains on mathematical reasoning (Table 1): Average accuracy rises from 27.24% to 42.11% at the 2B scale, from 29.01% to 47.95% at 9B, and from 45.21% to 64.86% at 35B. These surpass the strongest baseline by +1.83, +3.02, and +2.49 points respectively.

• Small models beat a much larger flagship: The 35B SAGE variant reaches 64.86% average, substantially exceeding Llama-3.3-70B-Instruct at 38.48% at roughly half the parameters, with consistent gains on OlympiadBench, AIME 2024, and Putnam.

• Generalization to free-form natural reasoning: On Qwen3.5-9B, the paper reports gains on MMLU-Pro (37.91% to 39.99%), BBH-H (44.04% to 45.31%), and ARC-C (39.73% to 42.04%); Table 2 lists 9B averages of 39.73% and 42.04% for EMPO and SAGE respectively. Similar scaling is reported at 27B (BBH-H 60.25%, ARC-C 58.11%) and 35B (BBH-H 69.07%, ARC-C 66.41%).

• Long-horizon stress test on the AC problem: SAGE improves AC Validity by +19.2% to +26.0% across architectures, and Lean-Verified Proofs by over +13% in every case, with Qwen3 reaching a nearly 8-fold increase over its base model.

• Both guidance components are necessary: On Qwen3.5-9B, removing either potential degrades performance. Full SAGE reaches 41.59% on OlympiadBench and 45.31% on BBH-H, versus 39.84%/39.06% without hyperbolic guidance and 39.12%/38.85% without algebraic sparsification.

• Generic dense shaping does not explain the gains: Replacing hyperbolic guidance with Euclidean distance yields 38.01% on OlympiadBench and 38.02% on BBH-H; shuffling target anchors yields 37.99% and 37.83%.

• SAGE outperforms a learned process reward model (Table 4a): On Qwen3.5-35B, GRPO-PRM improves over GRPO on Lean-verified proofs (14.64 to 17.36), but SAGE reaches 23.69, alongside 68.26 on OlympiadBench and 69.07 on BBH-H.

• Direct bias ablation on AC (Table 4b): Full SAGE achieves 59.83 AC Validity, 31.76 AC Path Solving, and 23.69 Lean-verified, versus 54.28/23.05/14.64 for GRPO and 53.18/21.52/13.78 for EMPO.

• Not reported: Compute budget, training wall-clock time, and a stated limitations section are not included in the provided content.

Methodology in Plain English

The authors first formalize long-horizon reasoning as a sequential decision process over symbolic manipulations, where each step must satisfy a task-local admissibility rule. They define a feasible region as the set of trajectories whose every step is locally admissible, and note this region is prefix-closed: once a prefix breaks admissibility, no continuation can recover.

From this, they argue two things. First, because the reachable search space grows exponentially with depth while the feasible region stays small, random rollouts concentrate outside the feasible region. Second, because rewards arrive only at the end, and because KL-regularization keeps the policy close to the reference model when rewards are rare, early mistakes persist uncorrected.

SAGE turns these diagnoses into two training signals. Algebraic sparsification scores each candidate operator by how much of the current unresolved symbolic residual it explains, biasing sampling toward structurally productive moves. Hyperbolic structural guidance embeds states and the target into a negatively curved Poincaré space and scores candidates by their distance to the target, providing a dense step-level signal before any terminal reward arrives. These two potentials are combined into a single score that modulates the rollout sampling distribution and augments the reward used to form group-relative advantages in a KL-regularized policy update. The resulting structural preferences are absorbed into the policy during post-training, so inference incurs no additional search or filtering.

Why This Matters

Impact on research: The paper reframes long-horizon reasoning failure not as a matter of insufficient scale or harder tasks, but as an identifiable structural pathology with formal signatures — a volume mismatch in the feasible region and a KL-anchoring effect under rare rewards. It also offers a route to process-like supervision without annotation cost, since both guidance potentials are computable without ground-truth trajectories or process labels.

Real-world applications:

• Automated theorem proving and formal verification, where correctness must hold across long chains of admissible inference steps.
• Symbolic mathematics and algebra systems, including group-presentation simplification such as the Andrews-Curtis problem studied here.
• Multi-step planning and tool-use agents, where one locally valid but unproductive action can derail a long execution.
• Domains with expensive or delayed feedback, such as scientific discovery workflows or complex code synthesis, where terminal-only evaluation is the norm.

Industry relevance: The results suggest that structural guidance during post-training can let smaller, cheaper models match or exceed much larger flagship models on reasoning-heavy tasks (a 35B model at 64.86% versus a 70B instruction-tuned model at 38.48% on the reported average), and that inference-time cost is unchanged, which matters for deployment economics.

Future Directions

• Extending SCA beyond symbolic domains: The paper acknowledges that in closed-form math and free-form natural reasoning, local admissibility must be approximated by structural proxies (residuals, equations, answer-schema constraints, semantic anchors). How reliably these proxies approximate the true feasible region is an open question.

• Choice of embedding geometry: The Euclidean-distance control underperformed, suggesting the hyperbolic embedding is doing real work, but the paper does not report a systematic study of curvature, dimension, or alternative hierarchical geometries.

• Scaling and compute reporting: Compute budget, wall-clock cost, and training-time overhead are not reported, so the efficiency of SAGE relative to baselines is unclear from the provided content.

• Resolving the reported benchmark/model counts: The contribution list states 13 benchmarks and 8 models while the rest of the paper states 12 benchmarks and 7 model families, and the experiment section mentions 3 baselines while 4 are listed; a reconciled accounting would help readers.

• Transfer to other sparse-reward long-horizon tasks: The AC problem is treated as the open real-world stress test; whether the same two potentials transfer to interactive or partially observable environments is not evaluated.

Target Audience

Researchers and practitioners in LLM post-training and reinforcement learning who work on reasoning, especially those dealing with sparse or delayed rewards. It is best suited to readers comfortable with policy-gradient methods, KL-regularized objectives, and formal reasoning about search spaces; the theoretical sections require some mathematical maturity. Applied teams building reasoning agents in mathematics, theorem proving, or multi-step planning will find the empirical results and the inference-time-cost argument directly relevant.

Authors’ abstract

Long-horizon reasoning remains a central challenge for large language models (LLMs) under sparse-reward regimes. We argue that this brittleness arises from two biases induced by complex reasoning spaces: an exploration bias, where models are drawn toward locally plausible but structurally unstable branches, and a compounding bias, where small local deviations accumulate across depth and suppress rare rewards. We introduce Symbolic Closure Analysis (SCA) as a theoretical lens characterizing how branching structures and sparse rewards induce these biases in long-horizon reasoning with local admissibility, and as a design principle for structural priors in less formal reasoning tasks. Motivated by this analysis, we propose SAGE (Structural Admissibility-Guided Exploration), a unified framework that injects structural guidance to alleviate exploration bias and compounding bias in long-horizon reasoning. SAGE combines two complementary structural guidance: algebraic sparsification, which projects locally admissible candidates onto operator-indexed algebraic subspaces to suppress spurious branching and mitigate exploration bias, and hyperbolic structural guidance, which embeds reasoning states into a negatively curved space to provide dense depth-wise signals and mitigate compounding bias. Across 12 benchmarks and 7 model families, SAGE outperforms competitive baselines. In particular, SAGE achieves up to an 8-fold improvement on the Andrews-Curtis problem, an open real-world long-horizon task. Code is available at: https://github.com/Susan571/SAGE-NeurIPS2026.