Composition-RL: Compose Your Verifiable Prompts for Reinforcement Learning of Large Language Models

The gist The authors propose Composition-RL, an approach that automatically composes multiple problems into a new verifiable question and uses these compositional prompts for RL training, which consistently improves reasoning capability over RL trained on the original dataset.

Composition-RL Overview

Composition-RL is a simple yet useful approach for better utilizing limited verifiable prompts targeting pass-rate-1 prompts by automatically composing multiple problems into a new verifiable question and using these compositional prompts for RL training The authors introduce a procedure for composing K existing prompts into new prompts (Section 3.1) and empirically show that prompt composition can, to some extent, mitigate the growing number of “too-easy” prompts (Section 3.2) They then formalize Composition-RL as RL training on compositional prompts (Section 3.3) As shown in Figure 1, CompositionRL outperforms RL training on the original prompts

Sequential Prompt Composition (SPC)

Sequential Prompt Composition (SPC) is defined as a procedure where one prompt is modified using the ground-truth answer of another prompt, and this process is generalized to composing K prompts into one prompt Composing two prompts involves three steps: Modify q1 with gt1, which involves extracting a numeric value v1 from gt1 and introducing a natural-language definition d1 that names this value in terms of (q1, gt1), and forming q¯1 = q1 ⊕ d1. Modify q2 by replacing its numeric values with new variables, yielding q¯2 = q2(v2), for example, replacing the constant 1 with a variable name Y Connect q1 and q2 by computing v1 − v2 and expressing the resulting relation between the two variables as a naturallanguage statement r, such as “Y is 6 less than X” The composed prompt is then q1:2 = ¯q1 ⊕ r ⊕ q¯2, and its ground-truth answer is gt1:2 = gt2 More generally, SPC applies Compose recursively for K − 1 steps to compose K prompts into one prompt, where K is the Compositional Depth

Effect on Training Data Quality

Meta-experiments show that the increasing prevalence of solve all prompts is another major impediment to effective RL training SPC can make easy prompts harder and reduce the ratio of solve all prompts Switching to compositional prompts reduces avg@8 by 19.7% for OpenMath-Reasoning-1.5B and by 15.4% for JustRL-1.5B, and the solve all rate also drops substantially This suggests that SPC can effectively reduce solve all prompts, potentially turn part of the original uninformative prompts useful again Furthermore, even SPC with K = 2 can almost double the training set size in principle (from D to D · (D − 1))

Curriculum RL for Higher Compositional Depth

A curriculum variant of Composition-RL gradually increases compositional depth over training, starting by training on MATH12K and then switching to Composition-RL with Depth 2 once performance saturates This transition causes the solve all ratio to drop sharply and enables further performance gains Continuing RL with Depth 3 data after Depth 1 (i.e., the original MATH12K) yields substantial gains over the Depth 1 checkpoint, improving by +9.7% on AIME24 and +5.9% on MMLU-Pro

Cross-Domain Composition

Composition-RL enables more effective cross-domain RL by composing prompts drawn from different domains When sampling q1 from the physics subset and q2 from MATH12K, yielding a cross-domain compositional dataset, Physics-MATH-Composition-141K, RL training on Physics-MATH-Composition-141K consistently delivers the best results on both in-domain subjects (math and physics) and OOD subjects (law, engineering, and chemistry) This highlights the great potential of Composition-RL for RL of multiple topics

Analysis of Success Factors

Composition-RL works through two main mechanisms: Compositional Generalization, where training on composed prompts can elicit new reasoning skills, and Implicit Process Supervision, where the structured dependency nudges the model toward a correct intermediate step The error analysis shows that after applying Composition-RL, all three error types—linkage error, q1 error, and q2 error—are reduced Specifically, linkage errors are the dominant failure mode for the original model but are reduced substantially by Composition-RL

Conclusion and Future Work

Composition-RL consistently outperforms RL on the original prompts across various model sizes and benchmarks The authors plan to release two compositional datasets, MATH-Composition-199K and Physics-MATH-Composition-141K, which they expect to be useful resources for future work on RL for LLMs Promising future directions include extending beyond MATH12K by composing more challenging math training set like Polaris-53K and expanding composition to cover more domains

Ablation Results

The ablation study on candidate sets Dk shows that Configuration B, where D1 is the full set D and D2 is a small randomly sampled subset, achieves the best performance, improving overall accuracy by +3.4% over variant A and by +2.2% over variant B This suggests that increasing the diversity of D2 is beneficial because it exposes the model to verification over the full set D2 = D, yielding a substantially more diverse set of answers to be verified

Evaluation Details

Evaluation benchmarks include in-domain math reasoning tasks like AIME24 and IMOBench, as well as out-of-domain multi-task reasoning benchmarks such as GPQA-Diamond and MMLU-Pro The authors report pass@1 accuracy using 32 samples per problem for AIME24 and AIME25, avg@8 for BeyondAIME, avg@4 for IMOBench, and pass@1 using 8 samples per problem for GPQA-Diamond The evaluation scripts are adapted from the DeepscaleR codebase

Error Analysis Summary

Table 5 shows that linkage error is the dominant failure mode for the original model, accounting for 22 out of 40 cases, compared with 7 q1 errors and 11 q2 errors After applying Composition-RL, all three error types are reduced, with the largest reduction observed in linkage errors (from 22 to 7) Linkage errors often arise from incorrect intermediate computation, unproductive self-verification loops, or selecting an incorrect linkage value despite otherwise correct reasoning

Response Length

Table 7 shows that Composition-RL does not significantly increase response length across all model scales The average response length for Composition-RL is similar to the baseline, indicating that the method does not substantially increase output length

Final Conclusion

Composition-RL consistently outperforms RL on the original prompts and demonstrates the potential of composing prompts from different topics The authors believe that compositional prompts can provide implicit process supervision by encouraging correct intermediate steps They will release their codes, compositional datasets, and trained models to support future RL research

References

Albalak et al.

1. Bold header: Composition-RL for better utilization of limited verifiable prompts

This system can automatically composes multiple problems into a new verifiable question and uses these compositional prompts for RL training, which is proposed to mitigate the growing number of “too-easy” prompts.

2. Bold header: Curriculum variant for progressive difficulty scaling

The system can implement a curriculum variant of Composition-RL that gradually increases compositional depth over training, allowing the model to continue RL training with Depth 2 data after Depth 1 to achieve substantial performance gains.

3. Bold header: Cross-domain RL through prompt composition

The system enables more effective cross-domain RL by composing prompts drawn from different domains, such as composing prompts from physics and math, which can induce broad improvements across the corresponding topics.