acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
learning theory
Keywords:
reinforcement learning, physics, spin glass, algorithmic tasks

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_EMufOpenReview ↗
Rating
2
Confidence
1
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies tabular policies for iterative symbolic tasks through deterministic policy codes, a Gibbs distribution over those codes, and product-distribution variational approximations. It proves a non-reward-decreasing path to perfect reward for untied (0,0) quasigroup folds, derives exact counting/partition results for parity, and investigates Monte Carlo traps, coordinate-ascent variational inference, and entropy/curriculum effects in transformers. The strongest contribution is the tractable landscape analysis; the connection from spin-glass states to actual training traps is less firmly established.

Critical strengths
  1. Substantive constructive and counting results. The constructive escape path for untied (0,0) quasigroup folds and exact parity counting are substantive, problem-specific results; exhaustive enumeration at T=2,3,4 agrees with the latter. They are not immediate corollaries of standard fully observed policy-gradient convergence results.

  2. The policy-code perspective makes a useful restricted model accessible. It allows comparisons among exact tabular optimization, Monte Carlo and transformer experiments. Closest work already studies restricted-policy myopic optima and entropy-dependent optimization landscapes; the present paper's specific combinatorics and quasigroup construction remain distinct, rather than making the general existence of traps or benefits of entropy new.

Critical weaknesses
  1. The implications for practical RL training are insufficiently developed. The non-decreasing escape-path theorem gives an interesting structural result, but it remains unclear what diagnosis or training decision it supports in large-scale RL. The construction uses exact continuation values and independent edits to table cells; the paper does not explain how these operations translate to a shared-parameter model trained from sampled terminal rewards. Training stagnation may also reflect the dataset or the training infrastructure. The analysis should explain when the proposed mechanism is relevant, what observations could distinguish it from these alternatives, and what intervention would follow. The common-curriculum entropy experiment supports an improvement on the tested symbolic tasks, but does not establish this broader diagnostic or practical guidance.

  2. The pure-state connection in Section 3.3 is overstated. The argument moves from weakly correlated pure states to fully factorized distributions "by definition", then identifies them with relevant variational optima. Weak correlation, or even pairwise independence, does not imply joint factorization. Figure 2 supports empirical agreement between cell marginals and CAVI endpoints, rather than the stronger identification of joint distributions. This limits the proposed explanation of training traps; the independent escape-path theorem and parity counting remain valid contributions.

Questions for authors
  1. Practical implications: What concrete guidance do the results provide for diagnosing or addressing stagnation in large-scale RL training? Please discuss the conditions under which the analyzed mechanism could apply to shared-parameter models, and how it could be distinguished from limitations arising from the dataset or training infrastructure.

  2. Scope of the theoretical connection: Does Section 3.3 establish a correspondence of joint distributions, variational stationary points, or only empirical marginal agreement? Please clarify the supported claim and revise the inference from weak correlation to factorization accordingly.

3 comments
AuthorsOpenReview ↗

Response to reviewer EMuf

We thank the referee for their valuable insights, yet respectfully disagree with their following remark: "The strongest contribution is the tractable landscape analysis; the connection from spin-glass states to actual training traps is less firmly established." We prove a lower bound on the RLVR loss via an auxiliary spin-glass model. As spin-glass models have been studied extensively in physics, this is not only a rigorous result but also a potentially valuable bridge for cross-fertilization between physics and computer science. Furthermore, the revised manuscript provides further numerical and analytical evidence for the relation between pure states and RLVR (Sec. 3.3, Fig. 2 and App. G), as detailed in our response to Q2 below.

We thank the referee for highlighting the policy-code perspective as a strength of our work. We would, however, like to clarify how we see our contribution, since the referee's summary places its novelty mainly in the specific combinatorics and the quasigroup construction. We agree that the general existence of traps, and the fact that entropy can aid optimization, are not new, and we do not claim them; the quasigroup construction, in turn, serves as a test bed. Our main contribution is a framework: an exact mapping from entropy-regularized RLVR to a spin-glass model, which, as discussed above, lower-bounds the RLVR loss and makes the toolbox of spin-glass theory available for analyzing RLVR. This framework yields results that go beyond the works cited by the referee, which study the behavior of specific optimizers (DeWeese & Qu, myopic optima under restricted policies; Ahmed et al., entropy and the optimization landscape), and in one case point in the opposite direction. First, although our tabular policies are myopic in DeWeese & Qu's sense, we prove (Theorem 4.1) that for a broad class of untied models the reward has no suboptimal local maxima, so that failures there must come from the optimization rather than from the landscape. Second, the framework allows us to anticipate when entropy helps: for parity, the first-order transition we compute exactly is what led us to the strong regulators with which transformers learn the task.

Questions are addressed bellow.

(1) Practical implications: First, regarding parameter sharing, we would like to emphasize that our bound, which is exact for untied/unshared models, also holds approximately for tied models (shared) at low temperatures (since double visits to policies are uncorrelated at low temperature when policies are deterministic/codes). We further comment that, as part of future work, we developed ways to encourage tying/sharing parameters by augmenting the RLVR loss, such that the bound is exact with respect to the spin system with gtie>0g_{tie}>0 (Eq. (7)).

More generally, our results do exactly what the referee asks – they separate between difficulties of optimization coming from parametrization and noise, from those which are an inherent property of the landscape. As such, they allow us to understand when it is worthwhile to invest compute in solving the former issues, and when to accept traps as a reality of training, and think about how we change the task or the loss.

In practice, this is exactly the process that allowed us to train the transformer. The new version contains an ablation study of 334 different transformer RLVR runs that have failed (App. I.5, Table 7), prior to our understanding that extremely high regulators are useful. Following these disappointing results, we studied the tabular models to establish the existence of suboptimal local maxima or prohibitive diffusive barriers in the reward landscape. Having demonstrated that there are no such problems (parity has mild diffusive barriers, but the other tasks we studied do not, see revised manuscript App. I.5, Fig. 5), we deduced that this is mainly a problem of exact-gradient RLVR updates not finding the optimum from random initializations. The final clue was noting that at least for some tabular models, regulator values close to collapse were beneficial. Applying those insights to transformers, we managed to train them so that they solve the task.

A more general practical pipeline we can envision is the following. Given a pure RLVR problem that fails to optimize yet has a deterministic code-like solution, consider first our spin-glass model over different families of codes containing the desired code. Study this problem using Monte Carlo or analytical techniques to unravel potential pitfalls in the landscapes (e.g. ones coming from shortcut heuristics which are suboptimal local maxima of the reward, as in our correlated parity task). Once these are addressed, look for regulators or other "hacks" which can improve RLVR. We can envision this pipeline leading to various disciplined advancements in pure RLVR, some of which may carry over to RLVR on pre-trained models.

(2) Scope of the theoretical connection: We thank the referee for this question, as the text may have mixed good approximations with proof level results. The exact result of Sec. 3.2 is that the RLVR loss coincides with a mean-field approximation to the spin-glass model. In such spin-systems, mean-field approximations coincide with the best product distribution. In the theory of spin-glasses, such product/mean-field states are good approximations to the states reached in practice using local Monte Carlo updates. As in physics, by good approximation we do not mean that the actual distribution is exactly a product state. What we mean is that when compared with experiments, the mean-field/product-probability approximates relevant observables well. The relevant observable here is the reward. In the revised manuscript, we clarify this (Sec. 3.3), and provide further evidence that this is the case. To ground this comparison, the revised manuscript defines traps explicitly (App. G.1) and specifies how they are identified in the Monte Carlo runs behind Fig. 2 (App. I.2). Establishing this as a mathematical proof (in the thermodynamic limit) is beyond the scope of this work. Nonetheless, App. G of the revised submission gives an exact expression for the reward gap between a trap and the product of its marginals (Theorem G.1), which we find to be below 10−210^{-2} relative to the trap's reward. Moreover, CAVI started from this product policy barely changes its reward (Fig. 2), and ends within 1.4×10−31.4\times10^{-3} (parity) and 2×10−62\times10^{-6} (tied models) of the trap's own Monte Carlo reward (App. I.2), so that each trap we find corresponds to an RLVR fixed point with the same reward.

Thank you for the thoughtful response. Your clarification that the pure-state approximation concerns the reward addresses my second question. I also appreciate how the theoretical analysis motivated the experiments with strong entropy regularization. I remain uncertain, however, about how far the tabular results can explain the behavior of transformer-based language models during RL training. On balance, I will keep my rating at 2. I should emphasize that my familiarity with this area is limited.

Reviewer_pe9BOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies RLVR in an iterated group/quasigroup multiplication setting. They map entropy regularized RLVR to a Potts/spin-glass model. The authors give a number of results about this landscape and discuss the obstacles to finding solutions.

Critical strengths

One strength is that this is a clear testbed, and we can separate optimization effects from landscape ones. The main result for a restricted-memory policy seems like a strong contribution.

The paper demonstrates exactly which structural features, namely, using each table entry once, no dependence on the past, spare unused capacity, make the untied problem easy.

Critical weaknesses

The “benign” condition seems like it holds for a slightly different problem. First, Theorem 4.1 and Corollary 4.3 are about the unregularized J and discrete escape paths, that the gradient dynamics “can never make” (App 6.3). And for the fully random policy the tokens are independent of the state, so every multilinear term of J that leaves any step unperturbed vanishes. For T>=3 the Hessian of J vanishes, which means that for tau>0 this fully random policy is a strict local minimum of the regularized loss. So this means that the “no local mnimima that could trap RLVR training” doesn’t hold, it holds for J but is false for entropy-regularized RLVR, regularization will just bring policies closer to this trap.

The Gibbs-Bogoliubov inequality is never studied numerically, eg for parity at T=6T=6, the difference between CAVI loss and F_spin is 0.26–0.44 for tau in [0.005,0.02], where the spin model has J=1 but CAVI has J=0.5. So I am not sure how useful this is.

The transformer connections is not quantitatively established. The theorem only covers for the (0,0) window, and anything else is just coming from Monte Carlo. Also the interpolation experiment in Table 4 demonstrates that distilled networks can represent one of these escape paths, but it does not show that RLVR with the transformer actually finds one. The results from the transformer are pretty thin, only one architecture and 5-8 seeds, and on the parity task, we do not see better than chance. And the β−1=1\beta^{-1}=1 does help with Z_5 but breaks the quasi group setting.

Also, technically I don’t see any non-abelian group multiplication as mentioned in the abstract, Z_2 and Z_5 are abelian and a quasi group is not a group.

Finally 12 of the references in the supplementary material are broken and render as ??.

Questions for authors

Do you agree that for any T >= 3 and and tau>0 the fully random policy is a strict local min of Equation 3? How can this be reconciled with the abstract and the strong-regularized recommendation.

Does Theorem 4.1 extend to the other windows?

What is the value of the free energy bound?

I would be interested in seeing transformer experience on a real nonabelian group like S_3 or A_5 with more seeds. How come it fails on parity?

Is there evidence that the weight sharing avoids the traps of Table 6?

4 comments
AuthorsOpenReview ↗

Response to reviewer pe9B

We thank the referee for their careful reading and for suggesting several new analyses, which we have implemented in the revised manuscript and describe below.

Regarding the referee's remark that "the connection to transformers is thin", we agree with the referee that this connection should be further clarified, and have done so in the revised version. The following connections are currently established:

(1) We have numerical evidence (App. I.4, Tables 4 and 5) showing that transformers can easily realize tabular policies and adapt to nearby tabular policies (this appeared also in the previous version). We now also cite Cagnetta et al. (2026) in Sec. 5.1, showing that pretraining small transformers yields myopic, lookup-table-like policies. (2) The new version contains an extended proof covering wider windows (see App. F.3), showing the landscape remains benign. Combining these two suggests that a reward landscape which is benign from the perspective of myopic tabular policies would also be benign for a transformer. We now make this argument explicitly in Sec. 5.1. (3) The revised version now includes a description of 334 experiments (App. I.5, Tables 7–8) we carried out in various different settings and architectures, showing that without strong entropy regulators, transformers do not train on this task. What is currently unclear to us is why temperature appears helpful for some tabular models and not others. We now state this in the Discussion (Limitations, point (ii)): “only half the tabular models we study gained from entropy regularization as opposed to transformer models, and the reason for this difference is not yet understood.” Nonetheless, it is this dependence, together with the appearance of a phase transition, that encouraged us to try these high values of regulators for the transformer.

We also thank the referee for pointing out the rendering issues with the citations, which are fixed in the revised version.

We address the referees questions below.

Do you agree that for any T≥3T\ge3 and τ>0\tau>0 the fully random policy is a strict local min of Equation 3? How can this be reconciled with the abstract and the strong-regularized recommendation.

Yes, we agree with the referee's statement that uniform policies are a strict local minimum of Eq. 3. However, this does not contradict our claims regarding the benign nature of the reward landscape in Theorem 4.1, as it concerns the reward landscape. We acknowledge that our wording, including in the abstract, was ambiguous regarding this point. The claim that the landscape is benign refers to the reward landscape JJ, not to the entropy-regularized loss LL. We have revised the abstract, the introduction and Sec. 4.1 to say that the benign-landscape result concerns the reward landscape, which has no suboptimal local maxima, and that it does not extend to the regularized loss.

Regarding the strong-regulator recommendation, the regulator involves a trade-off between exploration and exploitation. On the one hand, a larger regulator enlarges the basin of the uniform policy, and above the transition the uniform policy becomes the global minimum of LL (for parity, this is the first-order transition computed in App. H.3; below it, the uniform policy persists as a metastable state, as expected for a first-order transition). On the other hand, gradient dynamics cannot make escape moves at cells that are not visited, where the reward gradient vanishes. The regulator keeps the policy stochastic, so that cells remain visited and escape moves remain available. The recommendation is therefore to use the largest regulator for which training still starts outside the basin of the uniform policy, which in practice means just below the collapse. We note, however, that this picture does not explain why a strong regulator helps some tabular classes and not others, and we now state this explicitly as a limitation in the Discussion (Limitations, point (ii)).

Does Theorem 4.1 extend to the other windows?

Yes. Theorem 4.1 in Sec. 4.1 is now stated for any untied window (np,nf)(n_p,n_f) with one-token memory, and for any product input measure with full support. The proof is given in App. F, with the extension to general windows in App. F.3.

What is the value of the free energy bound?

The value of the bound is that it separates the two possible sources of failure: the variational family and the optimization. Specifically, the inequality limits what RLVR under perfect optimization can achieve, at all regulator values, including zero regulator. It allows us to analyze a simpler model of deterministic policies (the spin-glass model), which also allows interesting mappings between physics and CS, and use that to bound what RLVR can achieve. In particular, the failure of the spin model on the correlated parity task carries over to RLVR on the corresponding tabular models.

We agree, though, that the previous version lacked a direct comparison between the bound and the loss reached by RLVR. For parity at T=6T=6, 8 and 10 we now compare the CAVI loss with the free energy bound FspinF_\mathrm{spin}, together with the greedy and stochastic rewards and the entropy (App. H.4, Fig. 4). The gap from the bound, of 0.26–0.44, noted by the referee is that of CAVI from random starts, which, at intermediate β−1\beta^{-1} below the transition, ends at the uniform policy (J=0.5J=0.5). CAVI seeded at a correct code reaches a loss within 0.050.05 of FspinF_\mathrm{spin} well below the transition, and within about 0.150.15 up to it, so the variational approximation itself is nearly tight there, and the large gap is an optimization effect.

I would be interested in seeing transformer experience on a real nonabelian group like S3S_3 or A5A_5 with more seeds. How come it fails on parity?

The revised version contains further results on the group S3S_3, on both RLVR with tabular policies (tied and untied) and a transformer trained using REINFORCE (Fig. 3). Both results follow the trends shown in our previous results: Transformers solve it for some initialization seeds, but only with strong, near-collapse regulators. Half of the S3S_3 tabular models we tested ((1,1) window, tied and untied) show qualitatively similar behavior, while the others ((0,0) window, tied and untied) do not need a regulator.

Regarding the difficulty of transformers in the parity task, we would like to point out that from the RL perspective, the fact that one can successfully train models on this problem with only sparse rewards is not obvious at all. We point the referee to our newly added ablation study of 334 runs, which failed (App. I.5, Tables 7–8). This study was done prior to our understanding, coming from the first phase transition observed in the theory, that extremely large values of regulators are worth exploring. While parity has succeeded for a few seeds, this, in our minds, still counts as partial success or at least shows it is not impossible. It is interesting to note that, also for the tabular codes (the spin model) optimized using Monte Carlo, uncorrelated parity's training time increases exponentially with TT, while this is not the case for the other tasks we studied, such as Z5\mathbb{Z}_5 (App. I.5, Fig. 5). We attribute this to the all-or-nothing behavior of parity's CoT and the associated quantization of the rewards.

Is there evidence that the weight sharing avoids the traps of Table 6?

Perhaps we misunderstood the referee, but if what is meant by weight sharing is tying the policies at different CoT steps, then this is the tied setting in which there are indeed unavoidable traps. Namely, the reward landscape stops being benign.

Thank you for the thorough response and the revised manuscript. Several points are resolved: the abstract now limits "benign" to the reward landscape, Theorem 4.1 covers general untied windows, the new comparison with the free-energy bound gives the bound a clear role, and the added S3 experiments make the non-commutative claim accurate.

A couple more things re the main text that seem to differ from your response

  • The response says the revision states that the benign result does not extend to the regularized loss. I couldn't find that statement in the main text. The introduction and Sec. 4.1 don't mention that the uniform policy is a strict local minimum of Eq. 3 for every \tau > 0, and Sec. 4.2 only says CAVI "often ends at the uniform policy." Since this is the mechanism behind the RLVR–spin gap, and behind the trade-off in the regulator recommendation, I feel that you should include an explicit sentence in Sec. 4.1, ideally with a pointer to the strict-saddle/plateau literature (Ge et al. 2015; Li et al. 2021).
  • Sec. 5.1 still argues that transformers "should inherit" the untied landscape. The contributions still say transformers "share some of their benign landscape features." Yet a transformer shares parameters across positions, so its updates are coupled across CoT steps, as in the tied class, where you confirm there are unavoidable traps. Being able to represent untied tables doesn't settle which landscape RLVR on a transformer actually sees. It feels like maybe the evidence points the other way, with the many failed runs without near-collapse regulators and 3/10 seeds on S3. As a result I think this link be framed as a hypothesis, and that tied-vs-untied be added to Limitation (ii). Similarly "successfully learns" in the abstract maybe should instead say something like "can learn, in a fraction of seeds."
Reviewer_q1YpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies terminal-reward learning of iterated group and quasigroup operations using tabular policies that read a bounded input window and the preceding output token. It connects this setting to a statistical-mechanical model over deterministic policies, called codes.

  • Mapping. With an equally weighted entropy over table cells, the RLVR loss equals a product-measure variational free energy whenever each cell is visited at most once per rollout. Untied tables satisfy this condition, yielding L(π) = F_var[π] ≥ F_spin (Eq. 8–9).
  • Landscape results. In untied models, every local maximum of the unregularized reward J connects to an equal-reward code (Statement 3.1). For untied (0,0) policies on a quasigroup fold with uniform independent inputs, Theorem 4.1 constructs a finite sequence of non-decreasing single-cell moves from every code to J = 1. Eq. (10) gives an exact finite-depth partition function for parity; its large-depth limit exhibits a first-order transition. Correlated inputs and time tying yield examples of traps under the paper's single-cell dynamics.
  • Experiments. Monte Carlo with exactly evaluated rewards solves every tested untied class and seed in SI Table 2. Damped CAVI, also using exactly computed quantities, often ends at a lower greedy reward. The authors attribute this difference to the treatment of neutral moves. Entropy regularization or cell resets improve some classes. A one-block transformer trained from scratch with REINFORCE, an occupancy-based entropy bonus and a length curriculum solves the Z₅ and quasigroup tasks in several seeds. Distillation and interpolation experiments examine how tabular policies and paths can be represented by this transformer.
Critical strengths
  1. The paper makes a useful distinction between a favorable landscape and an easy learning problem. The exact connection to variational free energy gives the tabular setting a firm mathematical foundation, while Theorem 4.1 constructs a path to a perfect code under explicit assumptions. The solvable parity example adds a concrete case in which the theory can be checked. What I find especially valuable is the comparison between dynamics that can traverse neutral directions and CAVI: a good solution may be accessible without the training procedure finding it. This is a substantive insight, even within the deliberately simplified setting.
Critical weaknesses
  1. The favorable result for reward does not carry over directly to the training objective.

    Theorem 4.1 concerns the unregularized reward J and allows neutral changes to deterministic cells. Together with multilinearity, it gives a non-decreasing reward path from any policy in its scope. This is a meaningful geometric result, consistent with the no-spurious-valleys perspective, but it does not guarantee that a particular optimizer will follow such a path. Some preparation moves in the proof change unvisited cells, where the reward gradient is zero.

    Entropy regularization introduces a further distinction. For i.i.d. parity with untied (0,0) policies and T ≥ 3, expanding the stochastic-policy version of SI Eq. (34) around the uniform policy, with p_c = 1/2 + δ_c, gives

J(π)=12+O(∥δ∥T),L(π)−L(πunif)=2τ∑cδc2+o(∥δ∥2).J(\pi)=\tfrac12+O(\|\delta\|^T),\qquad L(\pi)-L(\pi_{\rm unif}) =2\tau\sum_c\delta_c^2+o(\|\delta\|^2).

Thus the uniform policy is a strict local minimum of L = −J − τΣ_c H(π_c) for every τ > 0. At T = 10 and τ = 10⁻⁶, its loss is approximately −0.50002634, compared with −1 for a perfect deterministic code, so this minimum is suboptimal. This does not contradict the theorem about J, but it matters for the paper's description of a benign landscape and its motivation for entropy regularization.

The finite-temperature experiments report greedy reward, whereas L depends on stochastic-policy reward and entropy. Reporting these quantities together would make it possible to interpret the endpoints more clearly. In particular, the optimization error L(endpoint) − min L and the variational gap min L − F_spin are different sources of a gap from the spin-model bound. The current results do not separate them at finite temperature.

  1. The connection to policy-gradient and transformer learning needs stronger evidence.

    The tabular experiments use damped CAVI with exactly computed d(c)Q(c,a): each iteration selects 30% of cells and moves them 30% toward their target. These quantities are exact reward gradients, but the resulting updates differ from conventional policy-gradient steps. At positive temperature, their interior stationary-point equations coincide for independent tabular logits and the same entropy objective; their trajectories and attraction basins need not. Since the tabular experiments have no gradient sampling error, they also do not directly test the proposed explanation involving that error. A comparison with exact and then sampled policy gradients would help connect the landscape analysis to training.

    Several modeling differences also matter. The exact correspondence uses equally weighted cell entropies, while the transformer uses an occupancy-based bonus. Input independence is needed for the escape construction, though not for the untied variational identity. Time tying in a table is also a different restriction from parameter sharing in a position-sensitive transformer. These distinctions deserve a clearer account of which conclusions are expected to transfer.

    The transformer experiments offer encouraging, but limited, evidence. Distillation and interpolation show that selected tabular solutions and local paths can be represented by the network; they do not establish escape paths from arbitrary RL-trained checkpoints or show that RL finds those paths. All successful transformer RL runs use a gated length curriculum, leaving its contribution entangled with regularization. The weaker parity results—failure at coefficient 0.3 in Fig. 3b and 2/5 successes at coefficient 1 in the SI—also deserve discussion in light of the tabular findings.

    Finally, the pure-state argument in §3.3 is less secure than the exact variational mapping. A pure state need not be a fully factorized distribution over a finite interacting system, and agreement of single-cell marginals does not establish joint independence. The SI calls this correspondence a heuristic; carrying that qualification into the main text would help readers distinguish the exact results from the proposed explanation.

Questions for authors
  1. Scope of the landscape result. Could you comment on the uniform-policy calculation above, which gives a suboptimal strict local minimum of the regularized loss in the parity setting? It would help to state explicitly which benign-landscape claims concern J, which concern deterministic single-cell moves, and whether any extend to L at positive temperature.

  2. Interpreting the free-energy bound. For representative finite-temperature CAVI runs, could you report stochastic reward, entropy and L alongside greedy reward? In the tractable parity setting, an estimate or bound separating optimization error from the variational gap would help explain what the comparison with F_spin reveals about training and the role of entropy regularization.

  3. From CAVI to policy gradients. What evidence supports extending the observed CAVI behavior to policy-gradient training, given that matching stationary-point equations need not imply matching trajectories? A comparison with exact and then sampled policy gradients on the same objective, with matched initializations, would help distinguish effects of the update rule from those of gradient-estimation noise.

  4. Status of the pure-state approximation. Could you clarify the assumptions under which the trapped distributions are expected to be approximately factorized? Agreement of single-cell marginals is informative, but does not establish joint independence. Joint-dependence diagnostics, or a more explicit statement of the approximation's limits, would help assess the proposed correspondence between Monte Carlo traps and CAVI fixed points.

  5. What transfers to the transformer? How much of successful transformer learning can be attributed separately to the length curriculum and entropy regularization? A focused ablation, together with a discussion of the weaker parity results, would help. Could you also explain how the occupancy-based entropy bonus affects the connection to the tabular objective used in the theory?

3 comments
AuthorsOpenReview ↗

Response to reviewer q1Yp

We thank the referee for their detailed review of our work. We would like to point out that although our results are consistent with the no-spurious-valley perspective of Venturi et al., which we now cite and discuss in the related work (Sec. 1), our RL setting is qualitatively different from these known supervised learning results. First and foremost, our tabular policies are underparametrized, while overparametrization is the main cause of the lack of spurious minima in Venturi et al. Evidently, in more complex settings (tied policies or correlated inputs) they do show suboptimal local maxima of the reward. The source of this is the complex highly non-linear form of the RLVR reward.

We address the referee's questions below.

(1) Scope of the landscape result: We agree with the referee, and thank them for the calculation. Our wording, including in the abstract, was ambiguous: the claim that the landscape is benign refers to the reward landscape JJ, not to the entropy-regularized loss LL, and at positive temperature the uniform policy is indeed a suboptimal strict local minimum of LL. We now state this explicitly in the abstract, the introduction and Sec. 4.1, which refer to the reward landscape having no suboptimal local maxima. Notwithstanding, whereas regulators could be switched on and off, the structure of the landscape generated by the reward is, to our taste, the more fundamental quantity. For instance, the aforementioned result regarding overparametrized networks would also fail if one initializes near-zero weights or adds weight decay.

(2) Interpreting the free-energy bound: We thank the referee for this suggestion. For parity at T=6T=6, 8 and 10 we now report, at each temperature, the loss LL, the greedy and stochastic rewards and the entropy of the CAVI endpoints, together with FspinF_\mathrm{spin} (App. H.4, Fig. 4). CAVI started at a correct code reaches a loss within 0.050.05 of FspinF_\mathrm{spin} well below the transition, so the bound is nearly tight there. From random starts, CAVI at intermediate β−1\beta^{-1} ends at the uniform policy, and the remaining gap is therefore an optimization effect rather than a looseness of the bound.

(3) From CAVI to policy gradients: We agree with the referee that two optimizers sharing the same fixed points need not reach them with equal probability, and we do not claim that CAVI and policy-gradient trajectories coincide. However, our analysis is deliberately independent of the update rule: it characterizes the reward landscape and its stationary points, which are shared by every optimizer of the same objective. The comparison the referee proposes isolates precisely the effects of the update rule and of gradient-estimation noise, which our framework is designed to abstract away. We now state this scope explicitly in the Discussion (Limitations, point (i)): “Our analytical approach isolates static and meta-stable properties of RLVR landscapes. It does not account for optimization dynamics or sampling noise.”

More broadly, we believe that a static characterization of the landscape is a meaningful contribution in its own right, particularly in a setting where theoretical results on RLVR remain scarce. Requiring a theory of the landscape to also account for the trajectories of specific optimizers would, in our view, set a bar that little existing theory in this area meets.

(4) Status of the pure-state approximation: We thank the referee and agree that our wording might have been inaccurate. The correspondence between Monte Carlo traps and pure states is a heuristic, which we expect to hold in the thermodynamic limit (large TT and, for tied models, large qq and large TT). As is usual in physics, the relevant question concerns observables, here the reward. We do not expect the trapped distribution itself to be factorized. Rather, we expect that its expected reward corresponds to one originating from a factorized distribution. Reporting single-cell overlaps (Bhattacharyya coefficients) suggested the stronger claim of joint independence, and we have replaced Fig. 2 accordingly. The revised Sec. 3.3 states the heuristic explicitly as one about observables, and tests its direct consequence: that each Monte Carlo trap corresponds to an RLVR fixed point with the same reward. To ground this comparison, the revised manuscript defines traps explicitly (App. G.1) and specifies how they are identified in the Monte Carlo runs behind Fig. 2 (App. I.2). The new Fig. 2 (panel a: parity with correlated inputs; panel b: tied models) shows that CAVI started from the product of a trap's marginals barely changes its reward, and ends within 1.4×10−31.4\times10^{-3} for parity and 2×10−62\times10^{-6} for the tied models of the trap's own Monte Carlo reward, at all temperatures at which the trap persists (App. I.2, which also describes the protocol). In App. G we further give an exact expression for the reward gap Δ\Delta between a trap and the product of its marginals (Theorem G.1). The joint dependence the referee asks about enters this expression explicitly, through the total correlation KL(pB∥ΠB)\mathrm{KL}(p_B\|\Pi_B), and the theorem also bounds the RLVR loss of the product policy. Numerically, Δ/⟨J⟩\Delta/\langle J\rangle is below 10−210^{-2} across the traps we study, and vanishes to numerical precision well below the temperature at which the trap dissolves (App. G.4).

(5) What transfers to the transformer? We added two tables to test this, showing our many (334) failed attempts at optimizing a transformer to T≥8T\geq 8 without high entropy regulators. We comment that one of these 334 runs, with 0.4 epsilon-exploration (which shares similarities with entropy regularization), reached T=7T=7 but not beyond. In contrast, with strong entropy regulators the transformer becomes trainable up to T=20T=20. Although not every seed succeeds, this is a far more effective tool than any of the standard alternatives we tried, none of which reached T=8T=8. These tests can be found in App. I.5, Tables 7 and 8. Fig. 3 now also includes transformer runs on the non-Abelian group S3S_3. In addition, Sec. 5.1 now motivates why results for tabular policies should carry over to transformers, citing evidence that pretraining yields myopic, lookup-table-like transformers (Cagnetta et al., 2026), and noting that Theorem 4.1 holds for any untied window, so that this conclusion does not depend on the transformer realizing a particular one. We note, in passing, that when pre-training the model on a copy task, which shares the same attention pattern, we did manage to train successfully without high-entropy regularization. However, this amounts to some CoT guidance and is hence beyond the scope of this work.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the referees for their detailed comments. In response, the revised manuscript contains several new numerical and analytical results that strengthen our core arguments. Three of these address the main weaknesses and questions raised by the referees:

  1. We extended Theorem 4.1 to any untied window (np,nf)(n_p,n_f) with one-token memory and to any product input measure with full support, and rewrote the proof in App. F accordingly.
  2. We rewrote Sec. 3.3, which now states the pure-state picture as a heuristic about observables, here the reward, and tests it directly. The new Fig. 2 shows that CAVI started from the product of a Monte Carlo trap's marginals reproduces the trap's reward, both for parity with correlated inputs and for tied models. The new App. G complements this with an exact expression for the reward lost by replacing a trap with its product of marginals, and shows that this loss is small.
  3. We added experiments, including on the non-Abelian group S3S_3, for both tabular RLVR and the transformer, which now appear in Fig. 3. We also report the 334 transformer runs that failed without strong entropy regulators, spanning different training algorithms, architectures, curricula and exploration schemes, alongside the runs at high regulators (App. I.5, Tables 7–8). Together, they show that the strong regulators motivated by our analysis are what made transformer training succeed.

Smaller additions and calculations are described in the individual responses.

Based on the comments we received, we have further clarified the limitations of our work: (1) Our theory focuses on fixed points and meta-stable states of the loss/reward (static properties), not dynamical properties. (2) Our tabular toy models are easily representable by transformers and sometimes respond to the same remedies, yet we have not established a formal correspondence between their respective optimizations. Notwithstanding these positioning issues, the following items should be kept in mind:

(a) None of the referees questioned the novelty of our mapping and bound relating RLVR to spin-glass models. This is a new perspective on RLVR, which opens a route for transferring knowledge from the mature field of spin-glass theory to RLVR with chains of thought. It does not by itself solve RLVR optimization, but conceptual connections of this kind are, in our view, a central contribution of theoretical work.

(b) To the best of our knowledge, no quantitative theory currently exists for the optimization of transformers with either RLVR or chains of thought. We believe theoretical contributions should be assessed against this state of the art, rather than against an ideal, complete theory.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.