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

The evolution of large-scale pretraining models like GPT-3 and BERT has underscored the importance of prompt engineering in enhancing reasoning capabilities. Reinforcement learning with verifiable rewards (RLVR) has been instrumental in guiding models to improve complex reasoning, exemplified by Chain of Thought prompting and RLHF techniques. However, the high cost of curating high-quality prompts and the increasing prevalence of overly simple prompts (pass@1=1) during training limit further progress. Researchers have explored methods such as advantage shaping and hard prompt prioritization, but these approaches do not fully address the challenge of prompt diversity and complexity. Recent efforts focus on prompt augmentation and composition, aiming to generate richer training signals from existing datasets, which is crucial for scaling reasoning abilities in large models.

The core issue lies in the diminishing effective training data as models become stronger, with the proportion of 'solve all' prompts rising sharply, reducing the informativeness of training signals. Collecting new high-quality prompts is expensive, and the existing data often contains many uninformative or overly easy examples. This bottleneck hampers the model’s ability to learn deeper reasoning patterns and generalize across tasks and domains. Additionally, current methods lack systematic mechanisms to generate complex prompts that can challenge models without incurring prohibitive costs, limiting the scalability of reasoning improvements.

The paper introduces three main innovations: 1) the Compose operator, which automatically combines multiple prompts into a single, more complex prompt by extracting key values and relations; 2) recursive multi-layer prompt construction (Depth K), enabling the gradual increase of reasoning complexity; 3) a curriculum training strategy that progressively raises the composition depth, fostering better learning of complex reasoning patterns. These innovations differ from prior approaches by systematically expanding prompt complexity through automation and recursion, rather than relying solely on manual prompt design or hard examples. The framework supports cross-task and cross-domain composition, broadening its applicability.

• �� Develop the Compose operator to merge two prompts by extracting answer values and defining relations, creating a new, more challenging prompt.
• �� Extend Compose recursively to build multi-layer prompts (Depth K), increasing reasoning complexity.
• �� Use RL algorithms like GRPO to optimize policy on these compositional prompts, maximizing verifiable rewards.
• �� Implement a curriculum strategy, starting training with simple prompts (Depth 1) and gradually increasing to Depth 3, allowing models to adapt progressively.
• �� Incorporate cross-domain prompts (e.g., physics and math) to enhance multi-task generalization.
• �� Sample prompts from datasets such as MATH12K and other benchmarks, ensuring diversity and relevance.
• �� Evaluate performance using pass@1 accuracy across multiple benchmarks, including AIME24, IMOBench, and MMLU-Pro.

The experimental setup involves training models of sizes 4B, 8B, 14B, and 30B on datasets like MATH12K, with comparison between original RL and Composition-RL. The key metrics include pass@1 accuracy, evaluated on in-domain and out-of-domain benchmarks. The experiments test various composition depths, curriculum strategies, and cross-domain prompts. Hyperparameters such as batch size, learning rate, and rollout settings are kept consistent. Ablation studies analyze the impact of composition depth and prompt diversity. Results confirm that Composition-RL outperforms baseline methods, with significant gains in challenging mathematical and reasoning tasks.

Composition-RL consistently improves performance across models, with the largest gains (up to 21.4%) on difficult benchmarks like AIME24. Increasing composition depth from 1 to 3 yields further performance boosts, validating the curriculum approach. Cross-domain experiments combining physics and math prompts show an average accuracy increase of 0.8%, demonstrating versatility. The method effectively reduces the prevalence of overly easy prompts, leading to richer training signals and better reasoning depth. Larger models benefit more, with improvements scaling with model size, indicating strong potential for scaling reasoning capabilities.

This approach is applicable in educational AI, scientific research, and industrial automation where complex reasoning is required. It enables automatic generation of challenging prompts from existing datasets, reducing manual effort and costs. The method can be integrated into multi-task learning pipelines, enhancing model robustness and transferability across domains. Future deployment could include intelligent tutoring systems, scientific problem solvers, and AI assistants capable of handling multi-step reasoning tasks efficiently.

The approach depends on the quality of existing datasets; in highly complex or novel domains, prompt composition may not fully capture necessary reasoning patterns. Increasing composition depth raises computational costs and may lead to diminishing returns. Cross-domain relevance remains a challenge, requiring further refinement of composition strategies. Additionally, the method’s effectiveness in real-world, noisy data scenarios needs further validation, and scalability to extremely large models may encounter resource constraints.