cs.LGSep 23, 2026
SaveRLVR landscapes for iterated multiplications can be benign: Insights from spin-glass theory
Organizations: Racah Institute of Physics The Hebrew University of Jerusalem
Abstract
Despite the importance of reinforcement learning with verifiable rewards (RLVR), the extent to which it can learn new reasoning capabilities remains debated. Here we study the optimization landscape of RLVR on algorithmic tasks, such as iterated group and quasigroup multiplication. To this end, we map entropy-regularized RLVR over myopic tabular policies onto an energy-based (spin-glass) model over deterministic policies. This mapping upper-bounds what RLVR can achieve, and lets us rigorously characterize the landscape in this tabular setting. We show, both theoretically and experimentally, that for a wide class of models and tasks with uncorrelated inputs, this landscape is benign, containing no local minima that could trap RLVR training. Rather, the practical difficulty of these tasks appears to stem, at least in part, from issues such as diffusive barriers and gradient-estimation error in traversing the landscape. These are genuine obstacles that can prevent a solution from being found, but they are distinct from the landscape itself being rugged. We show that these obstacles can often be mitigated through the choice of entropy regulator. Consistent with this theory, we find that a transformer trained from scratch, using only last-token rewards, successfully learns an algorithmic chain of thought for iterated non-Abelian group multiplications.
Figures & tables
Figure 1: The RLVR and spin-glass mapping. ( I ) Relating concepts from reinforcement learning to spin-glass models. ( II ) Two codes on the window (i.e. ), for and . Each circle is a cell ; the arrow inside it is the code’s output at that cell, up for token 1 and down for token 0. Dashed gray edges trace the code’s action on all input sequences. Two inputs differing only in are highlighted: and .Both trajectories of the parity code (a) converge to the correct answer, whereas the copy code (b) succeeds on only one of the two, the same success rate as chance.
Figure 2: MC stationary distributions against the CAVI endpoints seeded at them, as a function of the regulator : (a) the 27 correlated-input parity traps, (b) the twelve tied quasigroup traps. Left axis: MC reward, averaged over all traps and replicas; Bhattacharyya coefficient between the CAVI endpoint and the MC histogram, mean standard deviation over the finite-temperature traps; and its null. Right axis: the entropy of , averaged over the same traps; dotted lines mark its value when every cell is uniform. Open markers: fewer than half of the traps enter the average at that ; missing points: none does.
Figure 3: The entropy regulator on the untied classes. (a) Tabular RLVR from a uniformly random policy at a constant regulator , scored by the greedy reward of the endpoint policy. Each point is a mean over independent runs: for parity (window ), for the two classes at using window ( , quasigroup), for the narrow-window classes using window (at and ) and window (at ), and for quasigroup using window at . The inset table summarises reset interventions of the same class ( of the cells redrawn uniformly every iterations for cycles): the reward attained and the of the run it summarises. (b) The one-block transformer under the gated curriculum, REINFORCE with an entropy bonus (occupancy convention), read as greedy accuracy on held-out inputs of length at the final step. One point is shown per seed, bar is the mean over seeds. The transformer has no direct counterpart of tabular cell resets.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Approach to equilibrium, parity , , replicas | ||||
|---|---|---|---|---|
| exact equilibrium reward | ||||
| sweeps | greedy reward | at the optimum | gap to equilibrium | |
Table 1: Stationarity of Monte-Carlo runs . Upper block: the parity class, where the equilibrium reward is known exactly and equals the optimum at every temperature used, so the last column is a true distance from equilibrium. The approach is fast but steep — three quarters of the replicas are at the optimum by sweep and all of them by sweep , while a budget of sweeps would report . Middle block: where the equilibrium value is not computable, the sweep at which each run’s greedy reward stopped changing for consecutive sweeps. Both kernels are shown; they agree on the stationary value and differ only in how fast they reach it, the Metropolis kernel being the slower because it can propose a cell’s current action and hold. Lower block: the classes at , which are slower by two orders of magnitude and are checkpointed rather than run to the criterion. The untied class does reach the optimum in every run, but the mean at the cap conceals one run still crossing a plateau of flat cells, which arrives at sweep ; the tied class is flat over a fourfold change of budget at a reward well below the optimum, and does not arrive.
| class | window, tying | chain | average RLVR reward | RLVR exactly |
|---|---|---|---|---|
| parity, , | untied | |||
| , | untied | |||
| quasigroup, | untied | |||
| quasigroup, | untied | |||
| quasigroup, | untied | |||
| quasigroup, | untied |
Table 2: MC solves all untied models at vanishing temperature and plain RLVR typically ends below that. Mean reward over 12–100 random seeds (equal number of seeds for MC and RLVR) per class at the end of each dynamics; for RLVR also the standard deviation over starts and the number of runs ending at exactly . The chain reaches in every run on every untied class. We attribute this gap to the different way the two dynamics treat reward-neutral moves: the chain moves between codes along them at no cost, whereas RLVR at zero temperature spreads a cell’s probability evenly over exactly tied actions, producing non-code-like (non-deterministic) policies.
| class | reachable cells | steps to agreement |
|---|---|---|
| untied | ||
| untied | ||
| untied | ||
| untied | ||
| untied | ||
| tied |
Table 3: Eight random untied tabular policies used as teachers for dense (cross-entropy reward on each CoT token) transformer training, three seeds each. Transformers express better and train quicker on narrower tabular models. Agreement is evaluated every steps, so the step counts are multiples of that and is a bound rather than a measurement.
| class | stretch | steps | barrier | largest barrier (in quanta= ) |
|---|---|---|---|---|
| untied | first | |||
| middle | ||||
| last | ||||
| untied | first | |||
| middle | ||||
| last |
Table 4: Steps of a tabular escape path along which the transformer’s reward does not fall. Each stretch is consecutive policies of one Monte-Carlo chain, distilled in a chain and joined by straight lines in weight space; a step counts as barrier-free when the reward along that line never falls below its lower endpoint, and the barrier is measured in reward quanta . The last stretch, where the chain climbs to the optimum, is barrier-free on every step of every class.
| best of the scan | J @ | ||||||||
| class | seeds | sweeps | range of | at | at | ||||
| parity , | none | — | — | ||||||
| , | none | — | — | ||||||
| quasigroup , | |||||||||
| quasigroup , | |||||||||
| quasigroup , | |||||||||
Table 5: The two regulators on the untied classes with i.i.d. inputs, per seed. All entries are greedy rewards of the endpoint code; at counts the seeds ending at reward exactly out of the seeds run, which is the informative statistic because these distributions are bimodal. Upper block, the temperature scan: is the coldest point of the scan and top its warmest, so the two outer columns bracket the range; none means no temperature in the scan beats the coldest point, and on the row the best mean ( at ) is within noise of the coldest and its seed count is lower ( ), so it is reported as no effect. Standard deviations are omitted for width and are on the narrow-window rows, on and – on the two rows at . The scan is refined to half and quarter decades near each peak; a grid of one point per decade puts the optimum at and rather than at and . Lower block, re-randomisation: of the reachable cells re-drawn every sweeps for cycles, then undisturbed to the stated budget; the plain column is the same protocol with the perturbation switched off, at the same temperature, seeds and budget, so the pair is one controlled comparison. The three narrow-window rows were run with the regulator off ( ) rather than at the cold end of the scan, and give the same plain values as the scan does to four decimals.
| Correlated inputs, : every policy visited, every local maximum classified | ||||||
| cells | policies | local maxima | traps | trap frac. | escape barriers | |
| , | ||||||
| , | ||||||
| , , | ||||||
Table 6: Two modifications that put traps into an otherwise featureless landscape. A trap is a policy with no improving single-cell change and no cost-free path to one. Top: with inputs from a Markov chain of persistence , every policy in the space is visited and every local maximum classified, so these counts are complete rather than sampled. Traps are rare, yet the chain lands in one about once in eight runs, because they carry the large basins. Removing the correlation removes them entirely. Bottom: with one table shared across positions the space cannot be enumerated, so each endpoint is certified individually by exhausting its shelf of reward-neutral changes and testing every neighbour of every shelf node for improvement.