When a language model is trained with reinforcement learning on math problems, it typically writes several full solutions to the same problem and is rewarded only for the final answer. Every step of a wrong solution is then penalized, including steps that were correct. Many of those good steps also appear, in different words, inside other solutions that did reach the right answer. We propose to discover that hidden overlap. A learned matcher decides when two partial solutions from different attempts have reached the same intermediate state of the problem, even when they are worded differently. Merging those states turns a bundle of independent attempts into a single graph. Each node in the graph gets a value estimated from every attempt that passed through it, and each step is credited by how much it raised that value.
The opportunity is that this graph is free supervision. It needs no learned value network and no external judge. It also tells us where extra test-time samples are worth spending: at nodes whose outcome is still uncertain. The bet is specific. Inferring which reasoning states are equivalent, and training the matcher on whether two states lead to the same outcomes, rescues step-level credit in open-ended math reasoning. Exact state matching fails there, and fixed branching points spend compute in the wrong places.
Core Claim
Group Relative Policy Optimization (GRPO) is a critic-free reinforcement learning method that scores each sampled answer against the mean and standard deviation of rewards in its group of $G$ attempts. Its weakness is credit at the level of whole trajectories. GraphGPO showed that this weakness is real and fixable. It merges identical environment states across a batch of agent trajectories, credits each step by how much it reduces distance to the goal, and reports that 22% of steps in failed early-training trajectories were valid progress. It also reports an average success-rate gain of 14.85% over GRPO on ALFWorld for 1.5B models. GraphGPO, however, relies on exact state equality. Its authors' own analysis predicts that in noisy or open-ended state spaces the graph breaks into disjoint chains and the method collapses back into plain GRPO. Chain-of-thought math is exactly such a space: two solutions that have both established "the triangle is isosceles with base 6" will almost never share a string.
Our claim is that the merge relation should be inferred, which is the task of latent topology inference: learning the connectivity of data that comes without an explicit graph. We further claim the merge relation should be judged by the property that matters for credit. Two prefixes are equivalent if their continuations succeed at the same rate.
This follows the governing principle of graph structure learning, that the downstream task decides which edges are real. It borrows the most from Graph Agreement Models, which train an auxiliary model to predict whether two data points share a label and use that prediction as an edge weight. Here the "label" is the success probability of a prefix.
The resulting graph may contain cycles, for example when a solution backtracks to an earlier state. Node values are therefore plain visit-based Monte Carlo averages rather than Bellman backups, so cycles cause no difficulty. This partly resolves the tension the file identifies between the tree-shaped branching favored by variance analysis and the cyclic structure observed in strong reasoners.
Research Program
The model writes $G$ solutions per prompt, segmented at step boundaries (newlines or explicit step markers). For each step-end we take a hidden state from a late layer of the model. Roughly 90% depth is the layer at which Topology of Reasoning found clustered states to give meaningful reasoning graphs, though that work only used the clusters for after-the-fact analysis.
A small matcher network $m_\phi(h, h')$ scores whether two step-end states $h$ and $h'$ from different rollouts of the same prompt are equivalent. It is trained on pairs whose labels come from cheap branching. On a fraction of prefixes we sample a few continuations, as GRPO-MA does at its single </think> boundary. Two prefixes are labeled equivalent when their empirical success rates agree within a confidence interval. Merges are made sparse by allowing each state at most one partner per other rollout. This borrows the sparse edge selection used in the Differentiable Cell Complex Module to avoid dense, oversmoothed graphs.
Given the merged graph, let $\mathcal{R}(v)$ be the set of rollouts passing through node $v$, $r_j$ the final reward of rollout $j$, and $\hat V(v)$ their mean reward. A step that moves rollout $i$ from node $u$ to node $v$ receives a group-relative advantage. It is normalized among all steps leaving $u$, which plays the role of GraphGPO's grouping of actions taken from the same state:
$$A_{i,u\to v} = \frac{\hat V(v) - \overline{\hat V}(\mathrm{out}(u))}{\mathrm{std}\big(\hat V(\mathrm{out}(u))\big) + \epsilon}.$$
Here $\mathrm{out}(u)$ is the set of successor nodes reached from $u$ across rollouts, $\overline{\hat V}$ is their mean value, and $\epsilon$ is a small constant. Where no merges occur, $\mathrm{out}(u)$ contains a single node and we fall back to the ordinary trajectory-level GRPO advantage. The method is therefore never worse-defined than its parent.
The core analysis is a bias–variance tradeoff. Merging adds samples to a node and so cuts the variance of $\hat V(v)$ roughly as $1/|\mathcal{R}(v)|$, since it is a sample mean. Merging states whose true success rates differ adds bias. We will measure both directly against held-out branch rollouts and sweep the matcher threshold to locate the optimum.
The test-time side uses the same structure. During training, and optionally at inference, the remaining sampling budget goes to nodes with high $\hat V$ uncertainty and many incoming rollouts. GRPO-MA's delta-method result implies these are the places where extra continuations reduce advantage variance fastest. At inference, answers can be aggregated by node rather than by raw string vote.
Baselines
The naive reference is outcome-only GRPO with the same number of total generated tokens per prompt, with the group size increased until compute matches. This tells us whether any structure beats simply sampling more.
The strongest existing method on this exact question is GRPO-MA (Why Tree-Style Branching Matters for Thought Advantage Estimation in GRPO). It gets lower-variance credit by branching several answer continuations from a shared thought prefix. The file reports a Pass@1 of 70.58 for GRPO-MA versus 65.13 for GRPO's best "on Math"; the file attributes this to AIME2024/GSM8K evaluation without disambiguating. We will reimplement GRPO-MA on our models with the same prompts, the same total generated tokens per update, and the same hyperparameter search budget. We will not compare to the reported number directly. Beating it means higher Pass@1 on MATH-500 and AIME 2024 at equal training tokens, or equal accuracy with at least 25% fewer training tokens.
The second structural baseline is GraphGPO-style exact matching (GraphGPO), applied to normalized step strings. We expect it to fragment.
A third baseline is a hand-built key: extracted intermediate numeric values and normalized equations. This is the cheap version of our idea and a serious competitor on GSM8K.
The process-supervision baseline is LSRL (LSRL), which grades intermediate states with an external small LLM. It reports +4.27 points on GSM8K and +1.33 on MATH over a supervised depth-8 recurrent baseline. Those numbers are on a recurrent-depth model, so we will rerun the judge-based variant on our standard transformer with matched compute, charging judge calls to the budget.
Two ablations isolate the key ingredient. The first replaces the learned outcome-trained matcher with unsupervised k-means clustering of the same hidden states, as in Topology of Reasoning. This tests whether supervising merges by outcome agreement matters. The second keeps the graph but allocates branching uniformly instead of by uncertainty.
Why not just…?
Why not just use GRPO-MA's fixed tree branching? GRPO-MA does deliver lower-variance credit, and it is the main threat. Its branching, however, happens at one fixed point and shares nothing across independent rollouts. A correct step buried in a failed solution gets credit only if that solution happened to be branched exactly there. Our method harvests overlap that already exists among the $G$ rollouts, and spends branching only to train the matcher and probe uncertain nodes. If compute-matched GRPO-MA equals our method, the inferred graph adds nothing and we will say so. The per-budget learning curves are designed to settle this.
Why not just match intermediate results as text, which is trivial for arithmetic? On GSM8K this may work about as well as our method, because states there are mostly numbers. We expect it to fail on MATH-500 and AIME, where states are case splits, substitutions, and partial geometric facts that have no canonical string. The fragmentation measurements below test exactly this. If text keys reach comparable node coverage and value calibration on MATH, we would drop the learned matcher in favor of them.
Why not just train a process reward model or use an LLM judge? LSRL tried the judge route and reports modest gains (+1.33 on MATH), along with judge errors such as unit confusion. Verifying Chain-of-Thought Reasoning via Its Computational Graph shows that rich step verification from internal structure is possible, but it is an offline instrument too heavy for training rollouts. Our step signal comes only from verifiable final answers, aggregated across rollouts. The compute-matched LSRL-style comparison will show whether the judge's extra information outweighs its cost and bias.
Why not just use PPO with a learned value function? A critic duplicates the policy's memory footprint and drifts on long reasoning traces, which is the reason GRPO exists. Our node values act as a nonparametric critic restricted to states the batch actually visited. We include PPO only as a secondary reference on the 1.5B model, where memory permits.
Proposed Experiments
We train on DeepMath-103K, the training set used by S-GRPO. We start from Qwen-2.5-7B-Instruct, whose greedy MATH-500 accuracy of 71.2% is reported in ∇-Reasoner, and from a 1.5B model for ablations. We evaluate Pass@1 and accuracy-versus-training-tokens on GSM8K, MATH-500, and AIME 2024. ALFWorld serves as a sanity check: there exact matching works, and our method should recover GraphGPO's behavior rather than degrade it.
The first decisive check is fragmentation. We measure the fraction of step-ends that land in a node visited by at least two rollouts, under exact, text-key, k-means, and learned matching, on each benchmark. If the learned matcher does not raise coverage substantially over text keys on MATH and AIME, the premise fails.
The second check is value calibration. We compare node values $\hat V(v)$ to success rates from fresh held-out continuations, reporting error split into variance and merge-induced bias across matcher thresholds.
The third check is credit rescue. Following GraphGPO's analysis, we measure the fraction of steps in failed rollouts that receive positive advantage, and verify against held-out branching that those steps truly raise success probability.
The final test compares accuracy at fixed training tokens against compute-matched GRPO, GRPO-MA, text-key merging, and the judge baseline. A secondary test-time study compares node-level voting with uncertainty-directed branching against majority voting at equal inference tokens.
A clear win on MATH-500 and AIME combined with no win on GSM8K would be the most informative outcome. It would show that inferred topology matters exactly where states lack a canonical form.
References
- Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning
- Graph Agreement Models for Semi-Supervised Learning
- Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Properties
- Why Tree-Style Branching Matters for Thought Advantage Estimation in GRPO
- From Latent Graph to Latent Topology Inference: Differentiable Cell Complex Module
- LSRL: Process-Supervised GRPO on Latent Recurrent States Improves Mathematical Reasoning
- Verifying Chain-of-Thought Reasoning via Its Computational Graph
- S-GRPO: Early Exit via Reinforcement Learning in Reasoning Models
- $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space