When Is Compositional Reasoning Learnable from Verifiable Rewards?

• URL: http://arxiv.org/abs/2602.07992v1
• Date: Sun, 08 Feb 2026 14:31:54 GMT
• Title: When Is Compositional Reasoning Learnable from Verifiable Rewards?
• Authors: Daniel Barzilai, Yotam Wolf, Ronen Basri,
• Abstract summary: We study the learnability of compositional problems in autoregressive models under RLVR training.<n>We show that compositional problems where correct intermediate steps provide a clear advantage are efficiently learnable with RLVR.<n>On the negative side, when the structural advantage is not present, RLVR may converge to suboptimal compositions.
• Score: 10.475998113861896
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• LongRLVR: Long-Context Reinforcement Learning Requires Verifiable Context Rewards [51.45138356629732]
  We introduce LongRLVR to augment the sparse answer reward with a dense and verifiable context reward.<n>This auxiliary signal directly incentivizes the model for selecting the correct grounding information.<n>LongRLVR consistently and significantly outperforms the standard RLVR across all models and benchmarks.
  arXiv  Detail & Related papers  (2026-03-02T18:07:53Z)
• On the Learning Dynamics of RLVR at the Edge of Competence [86.52481827737097]
  Reinforcement learning with verifiable rewards (RLVR) has been a main driver of recent breakthroughs in large reasoning models.<n>We develop a theory of the training dynamics of RL for transformers on compositional reasoning tasks.
  arXiv  Detail & Related papers  (2026-02-16T16:03:08Z)
• Adaptive Ability Decomposing for Unlocking Large Reasoning Model Effective Reinforcement Learning [82.91265691530351]
  A$2$D is an Adaptive Ability Decomposing method for enhancing the effectiveness ofReinforcement Learning with verifiable rewards.<n>We first train a decomposer via RLVR without distillation, enabling it to decompose complex questions into a set of simpler sub-questions.<n>Next, we use this decomposer to annotate sub-questions for each question in the training dataset, and then train the reasoner under RLVR with sub-question guidance.
  arXiv  Detail & Related papers  (2026-01-31T14:48:23Z)
• Generalization of RLVR Using Causal Reasoning as a Testbed [20.97376329817835]
  Reinforcement learning with verifiable rewards (RLVR) has emerged as a promising paradigm for post-training large language models.<n>This paper provides an empirical study of RLVR generalization in the setting of probabilistic inference over causal models.
  arXiv  Detail & Related papers  (2025-12-23T20:45:31Z)
• Efficient Reinforcement Learning for Large Language Models with Intrinsic Exploration [33.02780998281276]
  Reinforcement learning with verifiable rewards (RLVR) has improved the reasoning ability of large language models.<n>This study investigates how simply leveraging intrinsic data properties, almost free benefit during training, can improve data efficiency for RLVR.
  arXiv  Detail & Related papers  (2025-11-02T04:16:47Z)
• Making Mathematical Reasoning Adaptive [61.45161826629692]
  We propose the AdaR framework to enable adaptive reasoning in large language models (LLMs)<n>AdaR synthesizes logically equivalent queries by varying variable values, and trains models with RLVR on these data to penalize spurious logic.<n> Experimental results demonstrate that AdaR improves robustness and generalization, achieving substantial improvement in mathematical reasoning.
  arXiv  Detail & Related papers  (2025-10-06T09:30:05Z)
• SwS: Self-aware Weakness-driven Problem Synthesis in Reinforcement Learning for LLM Reasoning [95.28059121743831]
  Reinforcement Learning with Verifiable Rewards (RLVR) has proven effective for training large language models (LLMs) on complex reasoning tasks.<n>We introduce a Self-aware Weakness-driven problem Synthesis framework (SwS) that systematically identifies model deficiencies and leverages them for problem augmentation.<n>SwS enables robust generalization byempowering the model to self-identify and address its weaknesses in RL, yielding average performance gains of 10.0% and 7.7% on 7B and 32B models.
  arXiv  Detail & Related papers  (2025-06-10T17:02:00Z)
• Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model? [66.61292196146016]
  Reinforcement Learning with Verifiable Rewards (RLVR) has recently demonstrated notable success in enhancing the reasoning performance of large language models (LLMs)<n>This study critically examines the current state of RLVR.<n>We find that the current training setup does not elicit fundamentally new reasoning patterns.
  arXiv  Detail & Related papers  (2025-04-18T17:59:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.