SAGE uses symbolic closure analysis (SCA) to explain exploration bias and cumulative bias in long reasoning, then turns this diagnosis into structural guidance during training. SCA first defines what counts as a path that "can still continue": starting from the origin, as long as every step conforms to the task-specified local operations, it belongs to the locally feasible region F, which has the prefix-closed property—once a step is illegal, subsequent continuations cannot turn this prefix back into a legal path. But feasibility is only a local condition; F may also contain routes that cannot reach the answer, and the set of truly successful trajectories is smaller, and is not known during training.
The first difficulty is exploration bias. The geometric intuition given in the paper is that the proportion of feasible prefixes at depth T is roughly constrained by the product of the ratios of feasible branches to total branches at each layer. If many layers have only a small number of feasible branches, this proportion shrinks rapidly with depth; when terminal rewards are limited, randomly sampling useful trajectories becomes harder. The paper further decomposes the fluctuation of policy gradients into three parts: variance within the feasible region, variance within the infeasible region, and variance caused by the different average signals of the two types of trajectories. If sampling truly concentrates on F, the latter two terms vanish. This decomposition explains why "which branches to spend budget on" affects the quality of the learning signal; it does not mean that local legality guarantees solving the problem.
The second difficulty is cumulative bias. When reward is given only at the endpoint, early decisions lack direct correction. The paper considers optimization with KL regularization: if the reference policy's probability of finding a successful trajectory is p, the upper bound of the terminal reward is Rmax, and the KL penalty strength is λ, then the total variation distance between the optimal policy and the reference policy has an upper bound. When successful trajectories are extremely rare and the reward is not strong relative to the KL constraint, this upper bound is very small; training struggles to move far away from the reference model's original early choices, so small deviations may persist along the long chain.
SCA therefore gives two clear design goals: first, concentrate sampling probability on more promising locally feasible branches; second, let prefixes receive feedback related to the target structure before reaching the endpoint. Symbolic tasks like AC can precisely define local legality; natural language tasks require estimating residuals and target anchors, and the theoretical guarantees cannot be carried over as-is.