mlsanityData to 14 Oct 2026

When Is Compositional Reasoning Learnable from Verifiable Rewards?

arXiv 2602.07992 ↗First posted 8 Feb 2026cs.LG stat.MLcited by 1

On the map: LLM reasoning → Reinforcement learning for reasoning

Abstract (arXiv)

The emergence of compositional reasoning in large language models through reinforcement learning with verifiable rewards (RLVR) has been a key driver of recent empirical successes. Despite this progress, it remains unclear which compositional problems are learnable in this setting using outcome-level feedback alone. In this work, we theoretically study the learnability of compositional problems in autoregressive models under RLVR training. We identify a quantity that we call the task-advantage ratio, a joint property of the compositional problem and the base model, that characterizes which tasks and compositions are learnable from outcome-level feedback. On the positive side, using this characterization, we show that compositional problems where correct intermediate steps provide a clear advantage are efficiently learnable with RLVR. We also analyze how such an advantage naturally arises in different problems. On the negative side, when the structural advantage is not present, RLVR may converge to suboptimal compositions. We prove that, in some cases, the quality of the base model determines if such an advantage exists and whether RLVR will converge to a suboptimal solution. We hope our analysis can provide a principled theoretical understanding of when and why RLVR succeeds and when it does not.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 21 of its 38 references that are in the map. First posted on arXiv 8 Feb 2026.

Builds on

21 of 38 references.

Closest ancestors · 5

Same direction, newest first

  1. 2025Reinforcement Learning for Reasoning in Large Language Models with One Training Example29 Apr
  2. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?18 Apr
  3. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective14 Feb
  4. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning22 Jan
  5. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMs22 Jan

Other references · 16

  1. 2024OpenAI o1 System Cardcited by 1,244
  2. 2025The Invisible Leash: Why RLVR May or May Not Escape Its Origincited by 97
  3. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 67
  4. 2024Transformers Provably Solve Parity Efficiently with Chain of Thoughtcited by 50
  5. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  6. 2025FormalMATH: Benchmarking Formal Mathematical Reasoning of Large Language Modelscited by 48
  7. 2025From f(x) and g(x) to f(g(x)): LLMs Learn New Skills in RL by Composing Old Onescited by 42
  8. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  9. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 36
  10. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 29
  11. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 23
  12. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 13
4 more
  1. 2025Task Generalization With AutoRegressive Compositional Structure: Can Learning From D Tasks Generalize to DT Tasks?cited by 11
  2. 2025From Reasoning to Super-Intelligence: A Search-Theoretic Perspectivecited by 9
  3. 2025Hardness of Learning Fixed Parities with Neural Networkscited by 7
  4. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Verification with Transfer: Exact Information Frontiers and Their Price in Callscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Composition-RL: Compose Your Verifiable Prompts for Reinforcement Learning of Large Language Models
  2. 2026Compositional Reasoning in Language Models under Reinforcement Learning Post-Training
  3. 2025The Reasoning Boundary Paradox: How Reinforcement Learning Constrains Language Models
  4. 2025Extending RLVR to Open-Ended Tasks via Verifiable Multiple-Choice Reformulation
  5. 2025Reinforcement Learning with Verifiable Rewards Implicitly Incentivizes Correct Reasoning in Base LLMs
  6. 2025ConfClip: Confidence-Weighted and Clipped Reward for Reinforcement Learning in LLMs
  7. 2025Reinforcement Learning vs. Distillation: Understanding Accuracy and Capability in LLM Reasoning
  8. 2026On the Emergence of Implicit Curriculum in RLVR Learning Dynamics