acceptodds
Withdrawn from ICLR 2027

What Does RLVR Learn? Binding, Table Access, and Composition

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

When reinforcement learning with verifiable rewards (RLVR) raises accuracy, what has the model learned? The same accuracy gain can reflect different outcomes: binding a new name to a familiar operation, fitting an arbitrary table of input–output pairs, or composing operations into unseen programs. We introduce Alien DSLs, executable languages whose symbol assignments and operation tables are sampled after pretraining, allowing us to evaluate these outcomes separately. Under outcome-only GRPO, exhaustive input evaluation supports partial binding between new names and familiar operations. Within the tested training budget, random-table accuracy plateaus near 30%, revealing a fitting bottleneck before transfer is assessed. Dense supervision largely resolves fitting, yet accuracy on the same observed cells drops from 96.5% to 13.7% when the query form changes. High training accuracy therefore does not ensure access to an observed table entry. For composition of renamed familiar operations, continued execution-trace supervision outperforms trace-initialized GRPO on held-out programs in smaller models. In the larger model, both recipes exceed an oracle per-program constant baseline on unseen operation pairs, unseen templates, and deeper programs. These transfer gains recur across two sequentially preregistered waves totaling sixteen fresh languages under a frozen training protocol. Together, these results show why fitting and transfer must be evaluated separately before interpreting an RLVR accuracy gain as evidence of a newly acquired capability.

Primary area:
reinforcement learning
Keywords:
RLVR

Reviews

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

RL training strategies may improve the performance of models on the concerned tasks, but it is not clear exactly what the models have learned from such training. The paper aims to answer this by disentangling the contributions from learned:

  1. symbol bindings - familiar operations bound to unfamiliar names,
  2. new operations - random table of input-output pairs, and
  3. operator composition;

by introducing "Alien DSLs", which are small synthetic domain-specific languages made up of 8 operations, with each derived program containing exactly 1 input variable x and literals ranging over the first 16 integers. These design choices allow the space of inputs for programs to be finitely evaluable. The synthetic DSL also allows incorporating counterfactuals such as binding familiar operations to new names, termed the "nonsense" variant in the paper, and permuting the symbol-literal bindings (eg: 7 means 2) via the "conjugate" variant. The execution outcome rewards in all cases come from a standard interpreter. The paper reports limited ability of models to learn binding of new names to familiar operations and to learn new operations under the tested GRPO strategies (outcome-only and pre-trained to some capacity with execution-trace SFT before GRPO, i.e., trace-initialized GRPO). For learning operation composition, continued execution-trace SFT outperforms trace-initialized GRPO.

Critical strengths
  1. The paper's main objective of understanding where the RLVR performance gains are coming from is an important and highly relevant one. The paper's approach of dissecting it across fitting, access, and transfer is also appropriate and conducive for constructing synthetic workflows to inspect and analyze.

  2. The DSL design choices allowing for exhaustive input evaluation of programs are important because they reduce ambiguities stemming from preferentially sampled inputs.

Critical weaknesses
  1. Incremental novelty. Many recent works already investigate whether RLVR induces new reasoning capabilities by setting up experiments that clearly distinguish between atomic skill acquisition and compositional generalization. Some of these also include composition depth ablations. The paper cites some of these and states that, "We evaluate binding, random-table access, and compositional execution within one experimental framework", but it is unclear from the paper what new information we learn from this dissection that was not already known from prior work. For example:

    • Yuan et al. From f(x) and g(x) to f(g(x)): LLMs Learn New Skills in RL by Composing Old Ones (ICLR 2026, cited) - already obfuscates function names to avoid inferring semantics from names, separates atomic skill acquisition from compositional generalization, and uses a two-stage training protocol (similar to the paper) for identifying whether RL improves composition of previously acquired primitives. The paper only adds an outcome-only symbol-binding task, random-table fitting, and a continued oracle-trace SFT as an additional comparison candidate. But it is unclear whether these additions are namesake only or if they provide any new information beyond Yuan et al.
    • Wang et al. New Skills or Sharper Primitives? A Probabilistic Perspective on the Emergence of Reasoning in RLVR (COLM 2026, not cited) - already studies whether compositional reasoning can arise from just improving existing atomic skills by training only on atomic operations and evaluating on held-out compositions, which is identical to the paper's Section 5, COMPOSING RENAMED FAMILIAR OPERATIONS. In fact, Wang et al. go further and empirically relate atomic primitive execution accuracies with compositional reasoning accuracies to explain compositional performance gains. The paper's novelty appears to be the random-table fitting task and including continued execution-trace SFT in comparisons, but as stated earlier, it is unclear what new information is learned from these two distinctions.
    • Minor point, but the paper states in the introduction that, "Standard math and code benchmarks make these claims difficult to separate", referring to it being difficult to disentangle RLVR performance gains from learning symbol-bindings, new operations, and composing known operations. But Thimmaiah et al. LLMs Lean on Priors, Not Programming Language Semantics (ICML 2026, not cited) introduce PLSemanticsBench that evaluates LLMs on conditioning their reasoning on explicitly provided formal semantic rules in program execution tasks under standard and counterfactual semantics. In fact, the paper's familiar standard and nonsense counterfactual variants are exactly PLSemanticsBench's Standard and KeywordObf semantic variants.
  2. Evaluation may not support the paper's claims. While the paper's contribution of unifying several previously known directed tasks under one umbrella diagnostic framework may be useful, its key takeaways, such as models improving at binding familiar operations, limited capacity of learning new operations, and limited capacity in transferring compositions, may have alternative explanations than the ones the paper supplies, making the paper's claims largely heuristic. For example:

    • The paper states in Section 2, "The nonsense-to-conjugated comparison changes both novelty and sample complexity." Does this not conflate novelty and complexity, making it hard to interpret which one is the primary reason behind poorer conjugated performance?
    • Once again in Section 2, "All composition experiments use the nonsense condition: new symbol assignments for familiar operations, with no conjugated or random tables." This makes the paper's evaluation materially weaker than its predecessors, which evaluate composition of not just obfuscated familiar operations, but entirely new operations as well (Yuan et al.). So we learn nothing about models' abilities to compose unfamiliar operations from the composition evaluations, which is a step back from prior work.
  3. Presentation. I also found this paper very hard to read, and page limitations are not an excuse, as this paper had an entire page to be less vague. Some examples are listed below:

    • Terms introduced without being defined clearly:
      • Comparison arms, namely, outcome-only GRPO, trace-initialized GRPO, continued execution-trace SFT, etc., are introduced in the introduction section without clearly explaining what each is and the motivation behind including it in the comparison.
      • The term phase-2 is used under Supervision controls in the Experimental Setup section, yet again without any prior discussion on how the training is structured and what happens in each phase, or even how many phases there are.
    • Key details missing in figures and offloaded to appendix:
      • Figure 2(B) is missing a Conjugated data point for scale 1.5B and there is no explanation in the caption or the relevant Section 4 explaining the reason. The paper instead states in Appendix G.1, "Conjugated tables were not run at 1.5B; this was a compute-allocation choice made before that wave." Why not include this in the caption?
      • Why does Figure 1(A) mention, "New programs and inputs"? Is the semantics of the operation kofo changing between training and testing for the symbol-binding task?
Questions for authors
  1. Although Appendix H explains the paper's position relative to related prior work, it is still unclear exactly what is novel beyond the same-cell random table fitting task and the inclusion of continued execution-trace SFT in comparison. Could the authors elaborate on what new information the evaluation results show that has not already been covered by prior work, especially the missing but highly relevant Wang et al. New Skills or Sharper Primitives? A Probabilistic Perspective on the Emergence of Reasoning in RLVR (COLM 2026)?

  2. Although the authors acknowledge that nonsense-to-conjugated changes novelty and sample complexity, how should the evaluation results be interpreted? What distinguishes learning unfamiliar operations from increased difficulty arising from conjugation counterfactuals?

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

This paper uses a synthetic programming languages to distinguish learning new names for familiar operations, fitting new operation tables, or composing seen operations into unseen ones. For instance, the authors find that RLVR learns partial symbol-operation bindings but struggles to fit random tables, while SFT does fit those tables but does not transfer well when the entries are queried under different names.

Critical strengths

The paper’s overall approach is interesting and potentially valuable to the community. Although the small synthetic language is a limited setting, it provides a useful way to probe specific questions about the nature of generalization in RLVR.

Critical weaknesses
  • The papers findings are somewhat inconclusive, and it is not clear what the key interpretations of the results are. Several individual observations could be interesting on their own, but their implications for the broader question of what RLVR learns remain uncertain and it is unclear what the take-aways are.
  • The drop in accuracy when changing the query form is an interesting result, since both forms refer to the same observed table entries. However, this is demonstrated on newly sampled operation tables. It would be useful to determine whether familiar arithmetic or mathematical problems exhibit similar failures under equivalent expressions or reformulated questions.
  • The paper appears to be largely AI-written, making the content difficult to follow at parts and does not meet the standards for high-quality scientific writing. I would strongly encourage the authors to rewrite the text and explicitly state each experimental question, the comparison used or experiment ran to answer it, and the conclusion supported by that experiment. At the moment it is very difficult to judge whether there is real scientific merit to the underlying findings.
  • The related work is lacking and should engage with several previous studies:

[1] Zhang et al., "When Scaling Meets LLM Finetuning: The Effect of Data, Model, and Finetuning Method", ICLR 24

[2] Jin et al., "RL Is Neither a Panacea Nor a Mirage: Understanding Supervised vs. Reinforcement Learning Fine-Tuning for LLMs", ArXiv 25

[3] Cai et al., "Extrapolation by Association: Length Generalization Transfer In Transformers", NeurIPS 25

[4] Ma et al., "Irreducible Supervision Enables Compositional Generalization in Post-Training", CompLearn 26

The latter paper seems particularly relevant, since it ties with the authors' claims regarding compositional generalization.

Questions for authors

N/A

Reviewer_MzrQOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces Alien DSLs, a synthetic benchmark designed to investigate what reinforcement learning with verifiable rewards (RLVR) enables language models to learn.

Critical strengths

Understanding whether RLVR improves existing capabilities or supports new forms of generalization is an important question for the community.

Critical weaknesses

The paper reads strongly AI generated and is really hard to follow.

Questions for authors

See weakness

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

Related papers

Discussion (0)

Sign in to comment.