Long-horizon reasoning under sparse rewards remains a persistent difficulty for large language models, according to a new research paper. The authors argue that this brittleness stems from two distinct biases that arise in complex reasoning spaces: an exploration bias, in which models gravitate toward branches that appear locally plausible but are structurally unstable, and a compounding bias, where small local deviations accumulate with depth and suppress rare rewards.
To characterize these effects, the paper introduces Symbolic Closure Analysis (SCA), a theoretical lens describing how branching structures and sparse rewards induce the two biases in long-horizon reasoning with local admissibility. The authors also position SCA as a design principle for structural priors in less formal reasoning tasks.
Building on that analysis, the researchers propose SAGE (Structural Admissibility-Guided Exploration), a unified framework that injects structural guidance to address both biases. SAGE combines two complementary mechanisms: 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 is reported to outperform competitive baselines. The authors highlight a particularly large gain on the Andrews-Curtis problem, an open real-world long-horizon task, where SAGE achieves up to an 8-fold improvement. Code is available at the project's GitHub repository.