PaperlayerView exact revision on arXiv

Source-linked AI summary

RLVR landscapes for iterated multiplications can be benign: Insights from spin-glass theory

Noa Rubin, Zohar Ringel

arXiv:2609.28625v1cs.LGcond-mat.dis-nnstat.ML

TL;DR

Whether RLVR learns genuinely new reasoning remains debated, and its optimization landscape is not well characterized. The paper maps entropy-regularized tabular RLVR to a spin-glass model and finds benign landscapes for simple untied settings, while showing that regulation can help address optimization gaps.

  • Problem

    Whether RLVR produces genuinely new reasoning or mainly reweights pretrained behavior remains debated, alongside open questions about its optimization landscape.

    Source: §1 · p. 1

  • Method

    The paper maps entropy-regularized RLVR over tabular policies to a spin-glass energy model over deterministic policies, whose free energy lower-bounds the RLVR loss.

    Source: §1 · p. 2, §2.2 · p. 4

  • Results

    For simple untied models, reward has no suboptimal local maxima; with weight tying and input correlations, local maxima are found.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Local resets to random deterministic policies or strong regulators can close the gap between RLVR updates and spin-model Monte Carlo optimization.

    Source: §1 · p. 2

    Pure tabular models provide only a qualitative link to transformers, and extending the analysis from untrained to real pretrained models remains complex.

    Source: §6 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper uses spin-glass theory to analyze RLVR landscapes on iterated group and quasigroup multiplication tasks. It finds benign landscapes in simple untied settings, while identifying optimization obstacles and settings where local maxima occur.

1 INTRODUCTION

  • The algorithmic task models reasoning as composing finite-group or quasigroup elements in sequence, with reward only for the correct final product.The study uses myopic tabular policies as a tractable approximation that isolates aspects of the RLVR loss from policy parameterization.Source: §1 · p. 2

A mapping between RLVR and spin models

  • The spin-glass mapping makes deterministic policies configurations and lower-bounds the RLVR loss with free energy under entropy regulation.It also links steady states of local dynamics on trapped configurations to approximate RLVR fixed points.Source: §1 · p. 2

Spin-glass model for parity task is solvable

  • At large T, the parity spin-glass model has a first-order phase transition between strictly random and correct codes.The model's free energy is derived in closed form at any temperature and depth T.Source: §1 · p. 2

Reward landscapes can be benign

  • For simple untied models, the reward has no suboptimal local maxima, and a simple Monte Carlo sampler solves the tasks without a curriculum.With weight tying and input correlations, the proof breaks down and local maxima are found.Source: §1 · p. 2

The RLVR–spin-glass gap and regulator choices

  • Exact local policy updates fail to optimize untied models, while spin-model Monte Carlo succeeds; local resets or strong regulators can close this gap.The gap is attributed to RLVR's inability to diffuse across equal-reward code landscapes.Source: §1 · p. 2

Strongly regulated transformers solve the task

  • Transformers trained from scratch often reach J = 1 on the task when strongly regulated and given a curriculum to address signal-to-noise issues.Weakly or moderately regulated transformers fail in the described experiments.Source: §1 · p. 2

2 SETTING: TASK AND MODELS

The section defines iterated multiplication tasks and two policy-modeling approaches: entropy-regularized tabular RLVR and an energy model over deterministic policies. The setup also specifies how bounded context windows and tying restrictions shape the policy classes.

2 SETTING: TASK AND MODELS

  • Inputs are uniformly drawn sequences, and the target is their left-fold product under a quasigroup operation; groups are associative quasigroups.The task's model emits a token at each step but is optimal when its final token equals the product.Source: §2 · p. 3

2.1 RLVR OPTIMIZED TABULAR POLICIES

  • Each tabular policy maps a bounded input-and-output context window and timestep to a token distribution, with reward only for a correct final output.Intermediate tokens are unsupervised; policies are tied when they ignore the token index.Source: §2.1 · p. 3
  • Tabular policies minimize negative expected reward plus an entropy regularizer; the coefficient τ = β^-1 is the temperature.The loss is optimized by coordinate-ascent variational inference, updating one cell while holding the others fixed.Source: §2.1 · p. 3

2.2 STATISTICAL SPIN-GLASS MODELS OF DETERMINISTIC POLICIES

  • The energy model assigns each deterministic policy, or code, a Gibbs probability using energy E(σ) = −J(σ), where J is expected reward.Its policy-cell interactions are non-local and complex, but differ from canonical spin glasses because they are quasirandom and have gauge symmetry.Source: §2.2 · p. 4
  • Window and tying restrictions can be represented as penalties, with zero penalties recovering the complete parameterization and infinite penalties yielding restricted classes.The paper notes that transformer implicit bias or pretraining could also be represented by a penalty term.Source: §2.2 · p. 4

3 MAPPING THE SPIN-GLASS MODEL TO RLVR

Section 3 links entropy-regularized tabular RLVR to a spin-glass model over deterministic codes. It uses this correspondence to relate reward maxima, RLVR loss bounds, and training traps.

3.1 SPIN-GLASS CODES AS REWARD MAXIMIZERS

  • Every untied policy with locally maximal reward can reach a deterministic code of equal reward along a constant-reward path.At a consulted non-deterministic cell, local maximality requires equal action values, leaving the reward unchanged as the action probabilities vary.Source: §3.1 · pp. 4–5

3.2 FREE ENERGY AS AN RLVR LOSS BOUND

  • For untied models, independently sampled-cell and rollout rewards coincide, so variational free energy lower-bounds tabular RLVR loss; tightness depends on mean-field fit.The reward correspondence holds exactly for untied tabular models; it holds approximately for tied models when revisits are rare or cells are largely deterministic.Source: §3.2 · p. 5

3.3 SPIN-GLASS PURE STATES AS TRAINING TRAPS

  • Monte Carlo steady states approximately match RLVR fixed points when trapped spin configurations have weakly correlated cells, as observed for the studied traps.The figure compares Monte Carlo stationary distributions with CAVI endpoints for correlated-input parity traps and tied quasigroup traps as the regulator varies.Source: §3.3 · p. 6, Figure 2 · p. 6

4 SOME EXACT RESULTS ON UNTIED MODELS

For untied models with uncorrelated inputs, the reward landscape has no defended suboptimal maxima, and monotone escape paths can reach optimal reward. The parity case admits a closed-form spin-model partition function that predicts a first-order phase transition.

4.1 UNTIED CLASSES HOLD NO DEFENDED MINIMA

  • Untied (0, 0), (2, 1), (1, 1), and (3, 0) window models with uncorrelated inputs have no local minima, and Monte Carlo consistently samples optimal-reward codes.The evidence cited is for the listed class of models and tasks; tied models and correlated inputs are outside this result.Source: §4.1 · p. 6
  • For the untied (0, 0) quasigroup fold with uniformly drawn inputs, every code has a finite sequence of single-cell changes that never lowers reward and ends at J = 1.The proof first removes collisions without decreasing reward, then handles the resulting collision-free code.Source: §4.1 · pp. 6–7
  • A non-decreasing reward escape path also exists from every policy, by connecting local maxima to codes or following an improving path otherwise.For code-to-code changes, the reward varies linearly along policy interpolation, yielding piecewise linear paths.Source: §4.1 · p. 7

4.2 EXACT SOLUTION FOR PARITY

  • For parity, the analysis classifies codes by dead steps and half-resets; a dead step forces chance reward, while one half-reset yields code rewards of 3/4 or 1/4.The closed-form partition function accounts for half-resets and dead steps.Source: §4.2 · p. 7
  • At large T, the parity spin model has a first-order transition at τc = 1/(6T log(2)), where average reward shifts from 1 to chance, 1/2.The entropy of dead codes overtakes the reward scale at the transition.Source: §4.2 · p. 7

5 FURTHER EXPERIMENTAL RESULTS

Experiments find an RLVR–spin-model gap on many untied tasks, while resets and strong entropy regulation can improve RLVR training. Transformers can express tabular policies, traverse many sampled code transitions with little reward loss, and often solve tasks with strong regulation and curriculum.

5 FURTHER EXPERIMENTAL RESULTS

  • For many untied tasks at negligible temperature, RLVR achieves much lower reward than the spin model, whose Monte Carlo sampling consistently reaches near-perfect reward.The spin model's sampling suggests its diffusive barriers are mild.Source: §5 · p. 8
  • In Figure 3’s left panel, about half the models respond well to high entropy regulator levels, and periodic resets work even better for this class.Source: §5 · p. 8
  • Tied tables have microscopic but common reward barriers, whereas correlated inputs have macroscopic barriers found in about 12% of initialization seeds.The correlated-input barriers involve a finite fraction of input combinations; tied-model barriers involve a few specific combinations.Source: §5 · p. 8

5.1 TRANSFORMERS ON THE SAME TASK

  • A 791k-parameter transformer can express random untied tabular policies, though wider windows take longer to train.This suggests an implicit bias toward narrow tables.Source: §5.1 · p. 9
  • At T = 6, all 189 transformer fine-tuning runs exactly reproduce their codes on 15,625 inputs; 159 of 180 sequential-code interpolations show no reward drop, and the rest drop by at most 2 × 10^-3.The measurements test expressing sampled codes and traversing the sampled escape path.Source: §5.1 · p. 9
  • At β^-1 = 0.3, five of eight Z5 seeds and three of eight quasigroup seeds exceed 0.95 accuracy at length 8, with curriculum runs reaching T = 18 and T = 20, respectively.Without a regulator or at coefficients up to β^-1 = 0.1, no task seed exceeds T = 2, and all are at chance at length 8.Source: §5.1 · p. 9

6 DISCUSSION

The discussion presents a spin-glass mapping for tabular RLVR and notes that strong regulators can facilitate training from scratch in tabular models and transformers. The appendices define the rollout quantities and policy setting used to analyze the objective, its multilinearity, and local maxima.

6 DISCUSSION

  • The spin-model free energy lower-bounds RLVR loss, and strong regulators can facilitate training from scratch in tabular models and transformers.The paper also describes scenarios in which both the spin model and RLVR become trapped in loss valleys.Source: §6 · p. 9
  • The tabular analysis is only a qualitative link to transformers; it focuses on untrained models, and the strong regulators that help here are likely damaging for pretrained models.The relation of prior terms, including KL penalties, to network RLVR training remains to be studied.Source: §6 · p. 9

A DEFINITIONS OF VARIOUS RL QUANTITIES

  • For rollouts, d(c) is the expected number of visits to cell c and Q(c, a) is expected reward after taking action a there; the reward gradient is d(c)Q(c, a).For untied policies, that gradient is independent of the policy at the cell; tied-policy gradients are not.Source: A DEFINITIONS OF VARIOUS RL QUANTITIES · p. 13

B.1 SETTING

  • The setting defines cells as policy table rows, policies as action distributions over cells, and codes as deterministic policies assigning one action to each cell.The task reward is arbitrary, and the objective is expected reward over inputs and generated trajectories.Source: §B.1 · p. 14

B.2 MULTILINEARITY

  • The reward objective is multilinear in cell-policy blocks because each rollout visits distinct cells at distinct steps.The appendix also defines local maxima and establishes two-sided feasibility for tangent directions within a policy's support.Source: §B.2 · p. 14, §B.3 · pp. 14–15

B.4 THE THEOREM

The theorem shows that a local maximum lies on a constant-reward set connected to compatible deterministic codes. The spin-model correspondence relates that structure to the RLVR objective, while a relabelling symmetry makes computed functions more informative than cell-by-cell policy overlap.

B.4 THE THEOREM

  • A local maximum’s reward stays constant along the compatible-policy set, which is convex and contains a compatible deterministic code.Cells can be collapsed one at a time onto compatible actions without changing reward.Source: §B.4 · p. 15

C THE CODE SPIN MODEL AND ITS RELATION TO THE RLVR OBJECTIVE

  • The spin-model construction separates a deterministic-policy model, a product-measure variational bound, and an identity with the stochastic RLVR objective under a single-visit condition.The only approximation in the correspondence is restricting trial measures to products; the passage describes this as a structural property of stochastic tabular policies.Source: C THE CODE SPIN MODEL AND ITS RELATION… · p. 16, §C.1 · p. 16, §C.2 · p. 17

C.1 NOTATION

  • The single-visit condition requires each trajectory to visit distinct cells, and the router assigns exactly one cell at each step.It holds trivially for untied policies.Source: §C.1 · p. 16

C.2 THE VARIATIONAL BOUND OVER PRODUCT MEASURES

  • The product-measure variational objective is the negative Gibbs–Bogoliubov free energy, with temperature τ.The bound is exact apart from the restriction to product trial measures.Source: §C.2 · pp. 16–17

D GAUGE STRUCTURE, INVARIANT OBSERVABLES, AND ABELIAN TARGETS

  • Relabelling can make policies disagree cell by cell while computing the same function, so comparisons should use relabelling-invariant quantities such as function agreement.The spin model has a local relabelling symmetry on a one-dimensional chain.Source: D GAUGE STRUCTURE, INVARIANT… · p. 18

E.1 SETUP AND NOTATION.

For untied policies with independent inputs, the proof constructs a non-decreasing path from any code to optimal reward by resolving collisions. The argument relies on structural assumptions that fail under weight tying or correlated inputs.

E.1 SETUP AND NOTATION.

  • A collision-free code below optimal reward has a strictly improving move, and repeated corrections reach J = 1 after at most q^2 final-step moves.The bound follows because at most q^2 final-step cells may need correction.Source: §E.1 · p. 19

E.2 ALGORITHMIC CONSTRUCTION OF A PATH TO OPTIMAL REWARD

  • At the first colliding step, the construction makes actions depend on true state, assigns unused tokens to continuations, and advances the first collision until none remain.These edits do not lower reward; after at most T rounds, the final-step correction completes the path.Source: §E.2 · pp. 19–20

E.3 REMARKS, VERIFICATION, AND SCOPE

  • The argument requires bijectivity and independent inputs; extension to wider untied windows is expected but currently supported only by measurements.Gradient-based dynamics cannot make the first escape move at an unvisited cell because its gradient is zero.Source: §E.3 · p. 20

E.4 WHAT BREAKS UNDER WEIGHT TYING AND CORRELATED INPUTS

  • Weight tying removes the guarantee of free preparation and isolated repairs, while correlated inputs break the equal-continuation condition used to consolidate cells.With tied entries, an unused token at one step may be in use elsewhere; with correlated inputs, cells sharing an outgoing state can have different continuation values.Source: §E.4 · p. 20

F DERIVATION OF THE PARITY PARTITION FUNCTION, AND THE FIRST-ORDER

The parity spin model has a closed-form partition function whose thermodynamics imply two phases separated by a first-order transition. Its derivation transforms the reward into a product-form expression and counts code configurations by their step types.

F DERIVATION OF THE PARITY PARTITION FUNCTION, AND THE FIRST-ORDER

  • The parity model has two phases—random codes at chance reward and a solution-orbit condensed phase—separated by a first-order transition at βc = 6T ln 2.The derivation checks the partition function against exhaustive enumeration for T = 3–5 and thermodynamic statements against exact evaluations through T = 200.Source: F DERIVATION OF THE PARITY PARTITION… · p. 20

F.1 A PRODUCT FORMULA ON THE FULL CODE SPACE

  • A Hadamard-conjugated link-matrix recursion expresses the final output sign through stepwise terms, with later nonzero reset terms removing dependence on earlier states.Independence of input tokens lets the remaining expectation factorize over steps.Source: §F.1 · p. 21

F.2 DENSITY OF STATES AND THE PARTITION FUNCTION

  • The code count is organized by the number of half-reset steps and the configurations of live steps, yielding the density of states and partition function.The passages distinguish live-code contributions from dead codes at J = 1/2.Source: §F.2 · p. 21

F.3 TWO PHASES AND A FIRST-ORDER CONDENSATION

Monte Carlo reaches optimal reward on every tested untied class, whereas plain RLVR often ends below it; the paper attributes this gap to how the dynamics handle reward-neutral moves. The parity model also exhibits a temperature-driven first-order transition, and tests find close correspondence between sampled stationary distributions and RLVR fixed points.

F.3 TWO PHASES AND A FIRST-ORDER CONDENSATION

  • τc = 1/(6 log(2)T) separates the random-code chance-reward phase from the condensed solution phase in the parity model.The free energy has a kink at τc, identifying a first-order transition.Source: §F.3 · pp. 21–22

G.1 EQUILIBRATION OF THE CHAIN COMPARISON

  • In the parity block, three quarters of replicas reached the optimum by sweep 20 and all did by sweep 100; at T = 7, untied runs reached the optimum while tied runs remained below it.In the middle block, both kernels agree on stationary values but differ in how quickly they reach them.Source: Table 1 · p. 23

G.2 STATIONARY DISTRIBUTIONS OF MC ARE APPROXIMATELY CAVI FIXED POINTS

  • CAVI converged to machine precision on all tested correlated traps and nine of twelve tied traps; the other endpoints stayed within 2 × 10^-5 of trap reward.These tests compare CAVI endpoints with sampled Monte Carlo seed distributions.Source: §G.2 · p. 24, §G.3 · p. 24

G.3 THE RLVR MONTE-CARLO GAP

  • 268 of 268 Monte Carlo runs reached J = 1 on untied classes, versus 40 of 168 plain RLVR runs outside parity; parity RLVR reached J = 1 in 100 of 100 runs.The authors attribute the gap to Monte Carlo moving between codes along reward-neutral paths while RLVR spreads probability over tied actions.Source: §G.3 · p. 24, Table 2 · p. 25

G.4 MEASURING TRANSFORMER BIAS TOWARD TABULAR POLICIES

Transformers can express random tabular policies, with an implicit bias toward narrower windows. Along tabular escape paths, embedding policies in transformer weights adds few reward barriers, and none on the final stretch to the optimum.

G.4 MEASURING TRANSFORMER BIAS TOWARD TABULAR POLICIES

  • Agreement measures the fraction of emitted tokens matching the teacher on held-out inputs, with training targeting 0.999 agreement.Wider windows took one to two orders of magnitude longer to reach that threshold.Source: §G.4 · p. 25
  • 159 of 180 steps add no transformer barrier, and all 60 steps in the final stretches to the optimum are barrier-free across three classes.Any barriers are early and small, at most 35 reward quanta, corresponding to a reward drop of 2 × 10−3.Source: §G.4 · p. 25, Table 4 · p. 26
  • Transformers express random narrow-window policies better and train faster than wider-window policies.The eight tabular classes were used as teachers for dense transformer training with three seeds each.Source: §G.4 · p. 25, Table 3 · p. 26

G.5 REGULATOR EFFECTS

The effects of regulators differ across tabular and transformer training. Tabular resets often reach the optimum, while transformer results vary by task and regulator setting; token relabelling provides a modest improvement but does not solve the task.

G.5 REGULATOR EFFECTS

  • For multi-length tabular classes trained on random T values, peak rewards occur at τ between 1.8 × 10−5 and 5.6 × 10−5, with gains lost by 10−4.The runs used uniform entropy regulators, random starting policies, and exact greedy-reward evaluation.Source: §G.5 · p. 26
  • Random resets take six of seven tabular classes to the optimum in all or all but one seed; for (0, 3), reward rises from 0.764 to 0.940 without reaching 1.The protocol redraws 2% of reachable cells every 10 sweeps for 100 cycles before undisturbed training resumes.Source: §G.5 · p. 26
  • At β = 1, Z5 reaches 0.992 in five of five seeds and parity has its only successes (2/5), while the quasigroup reaches 0.216.The same transformer training setup uses REINFORCE, a gated curriculum, and an entropy bonus β; β = 1 corresponds to β−1 = 1.Source: §G.5 · pp. 26–27
  • At T = 2, full-permutation relabelling gives 0.542 ± 0.081 versus 0.417 ± 0.101 without perturbation, but none of eight seeds solves the task.For training on T = {1, 2, 3}, the observed positive signal is within seed-noise levels.Source: §G.5 · p. 27

G.6 CORRELATIONS AND TYING INDUCE LOCAL REWARD MAXIMA

Correlated inputs and tied policies can introduce traps into otherwise benign landscapes. Correlation-generated traps are rare but can be reached by Monte Carlo, while tied-policy runs stop at suboptimal endpoints, some certified against reward-neutral escape paths.

G.6 CORRELATIONS AND TYING INDUCE LOCAL REWARD MAXIMA

  • A trap has no improving single-cell change and no reward-neutral single-cell path to a policy from which one exists; correlations and tying invalidate elements of the no-trap proof.Correlated inputs are drawn from a Markov chain with persistence k, while tied policies share a table across positions.Source: §G.6 · p. 27
  • With correlated inputs, over 99.99% of local maxima have a cost-free exit, yet Monte Carlo reaches a trap about once in eight runs, consistent with traps having large basins.Every identified trap is a shortcut policy discarding one or two input positions; at k = 0.9 these score 0.90 and 0.82, respectively.Source: §G.6 · p. 27
  • For tied policies, the search explores each endpoint’s connected component of reward-neutral single-cell changes and tests neighbors for improvement.Exhausting the component certifies that no non-losing single-cell path leads to an improving move; hitting the 10^5-node cap yields only a bounded result.Source: §G.6 · pp. 27–28
  • None of 12 tied-policy Monte Carlo runs reaches the optimum; their endpoints score between 0.830 and 0.976, with mean 0.897 ± 0.044.Ten endpoints are certified after shelf exhaustion; two hit the search cap and are reported as bounded.Source: §G.6 · p. 28

Related papers

Loading 2609.28625v1…