Source-linked AI summary
Verifiable Environments Are LEGO Bricks: Recursive Composition for Reasoning Generalization
Hao Xiang, Qiaoyu Tang, Le Yu, Yaojie Lu, Xianpei Han, Ben He, Le Sun, Bowen Yu, Peng Wang, Hongyu Lin, Dayiheng Liu
TL;DR
Existing individual environment construction scales linearly, limiting diversity for reasoning generalization. RACES recursively composes verifiable environments when output and input types match, consistently improving generalization while using fewer base environments.
Problem
Individual environment synthesis scales linearly with construction cost, limiting environment diversity within a fixed budget for reasoning generalization.
Method
RACES recursively composes verifiable environments whose codomain matches another’s domain, producing new verifiable environments that remain composable.
Results
RACES consistently improves generalization across model backbones and benchmarks, raising DeepSeek-R1-Distill-Qwen-14B’s average score from 48.2 to 51.3.
Takeaways & Limitations
Using 50 base environments, RACES outperforms direct reinforcement learning on 300 initial environments and offers controllable task difficulty through composition depth.
Takeaways & Limitations
RACES explores only four composition operators, while conditional branching and bounded loops remain unexplored; composite tasks also require capable models and sufficiently large context windows.
Abstract
from arXiv · showhide
Reinforcement Learning (RL) with verifiable environments has emerged as a powerful approach for enhancing the reasoning capabilities of Large Language Models (LLMs). While prior research demonstrates that scaling environment quantity improves RL performance, existing manual or individual construction methods suffer from linear scaling limits, thereby hindering scalable reasoning generalization. This paper introduces RACES (\textbf{R}ecursive \textbf{A}utomated \textbf{C}omposition for \textbf{E}nvironment \textbf{S}caling), a framework that conceptualizes verifiable environments as composable building blocks that can be recursively assembled. The key insight is that when the codomain (output type) of one environment matches the domain (input type) of another, they can be automatically fused into a new verifiable environment, enabling recursive composition. RACES is implemented with 300 individual environments and defines a set of composition operators (\textsc{SEQUENTIAL}, \textsc{PARALLEL}, \textsc{SORT}, and \textsc{SELECT}) that induce diverse reasoning patterns. Extensive experiments show that RL training on these composite environments consistently enhances reasoning generalization. Specifically, RACES improves DeepSeek-R1-Distill-Qwen-14B by an average of 3.1 points (from 48.2 to 51.3) and boosts Qwen3-14B performance from 58.8 to 61.1 on six benchmarks, which are unseen during the construction of training environments. Moreover, RACES achieves performance comparable to training on 300 individual environments using only 50 base environments, demonstrating significant efficiency in environment utilization.
1 Introduction
RACES addresses the linear scaling limits of individually synthesized verifiable environments by recursively composing existing environments whose output and input types align. Experiments show that this approach expands training diversity and consistently improves reasoning generalization across model configurations.
- Motivation: Increasing environment quantity improves performance, but individually synthesizing environments expands the pool only linearly with construction cost.This linear scaling limits diversity under a fixed budget and remains inadequate for optimal reasoning generalization.
- Approach: RACES expands the environment space by leveraging existing environments rather than generating entirely new ones from scratch.The framework draws on transformation composition and prior work on problem composition.
- Approach: RACES recursively fuses environments when one environment’s output type matches another’s input type, creating increasingly complex verifiable reasoning tasks.The framework treats environments as composable building blocks that can be assembled into new training problems.
- Experiments: 300 environments and four composition operators support tens of thousands of composite environments for reinforcement learning on Qwen3 and DeepSeek-R1-Distill-Qwen.The experiments evaluate RACES across both model families.
- Results: 3.1 points is the average improvement for DeepSeek-R1-Distill-Qwen-14B, reaching 51.3 compared to 48.2 with RACES.RACES consistently enhances generalization across all model configurations.
2 Related Work
Prior work establishes RLVR and verifiable environments as scalable sources of reasoning-training signals, while composition research explores constructing more complex problems from limited data. RACES builds on these directions by composing deterministic environments into structurally diverse composites whose variety scales with composition size.
- RLVR: RLVR improves LLM reasoning but requires substantial verifiable data, while increasingly larger curated datasets struggle to meet demand for high-quality training signals.The passage identifies RLVR as a leading approach and highlights its data-scaling challenge.
- Verifiable Environments: Verifiable environments provide an automatic data-synthesis approach, with RLVE demonstrating effectiveness through hundreds of algorithmically verifiable environments and adaptive difficulty.RLVE is described as surpassing much larger static datasets.
- Environment Composition: Deterministic verifiable environments can be composed when one environment’s output feeds another’s input, preserving verifiability through intermediate results.For environments f(x) and g(x), the composition is g(f(x)).
- Environment Composition: Finite environment sets can generate structurally diverse composites, inducing deeper and more varied reasoning patterns while scaling combinatorially with composition size.This motivates recursive composition as a way to expand training-environment variety.
- Problem Composition: Problem-composition research constructs complex problems from simpler ones to generate diverse training signals from limited data, emphasizing the importance of composition-method design.Examples include pairwise mathematical composition and extended dependency chains formed from GSM8K problems.
3 Method
RACES represents verifiable environments through typed, executable interfaces and recursively composes environments when one output type matches another input type. It scales construction through frontier-based search, executable quality filtering, and operators that convert composites into diverse model-facing reasoning problems.
- Environment representation: Each verifiable environment is a four-tuple whose input sampler generates valid instances and whose deterministic output mapper defines the domain signature (X_e, Y_e).The sampler provides an unlimited stream of training data, while the mapper’s domain and codomain determine composability.
- Recursive composition: Two environments compose when the first codomain equals the second domain, producing a deterministic mapper that preserves an interface suitable for further recursive composition.A compatible sequence induces a composite with signature (X_e1, Y_et), enabling expansion from a finite pool into a larger environment space.
- Construction pipeline: RACES constructs composites through frontier-based search comprising composition path discovery, quality assurance, and operator instantiation.Search uses randomized breadth-first traversal with depth, time, and extension limits, while usage-budget weighting promotes balanced pool utilization.
- Quality assurance: Online executable filtering retains only compatible extensions that run successfully and produce well-formed intermediate states, excluding runtime failures, step-limit violations, timeouts, and invalid outputs.Domain compatibility is necessary but insufficient because executable compositions can fail on specific intermediate states.
- Composition operators: RACES implements four operators—SEQUENTIAL, PARALLEL, SORT, and SELECT—that transform executable composites into model-facing problems with distinct reasoning patterns.SEQUENTIAL predicts chained intermediate outputs, PARALLEL solves independent threads jointly, SORT recovers a valid execution order, and SELECT identifies and orders the correct subset amid executable distractors.
4 Experiments
Across two 14B backbones, RACES consistently outperforms individual-environment RL on six unseen benchmarks. Its advantage comes from training on composed environments that require chaining transformations, maintaining intermediate states, and inferring valid operation orders or subsets.
- Main results: RACES consistently outperforms individual-environment RL across both model families using the same environment pool and identical RL data scales.The evaluation uses six benchmarks spanning code generation, mathematical and logic reasoning, instruction following, and long-context understanding; none are used in RACES.
- Main results: 51.3: RACES raises DeepSeek-R1-Distill-Qwen-14B’s average score from 48.2, versus 48.8 with RLindividual, outperforming RLindividual by 2.5 points.Both methods are initialized from the same environment pool and use identical RL data scales.
- Mechanism: RACES trains on composed environments requiring chained transformations, intermediate-state maintenance, and inference of valid operation orders or subsets.This training signal is more effective than exposing models to isolated environments, producing stronger transfer on unseen reasoning benchmarks.
5 Analysis
Analysis shows that RACES can outperform individual-environment RL despite slower reward gains, using fewer base environments and composition-induced reasoning behaviors. Performance improves with composition depth up to a moderate range, but excessively deep compositions reduce trainability and final scores.
- Training dynamics: RLRACES reaches 51.9 at step 200 versus 50.4 for RLindividual, despite RLindividual improving faster and maintaining higher training rewards.This separates rapid reward optimization from downstream generalization: individual environments favor easy, short transformations, whereas composites require intermediate-state maintenance and multi-step transformations.
- Environment efficiency: RLRACES(50) achieves 50.8, outperforming RLindividual(300) at 50.4 with one-sixth of the base environment pool; RLRACES(300) reaches 51.9.Composition expands a fixed pool into a more diverse training distribution by varying positions, neighbors, and operators.
- Composition size: Average scores rise from 50.8 to 51.2 as composition size increases from 2 to 5, then fall to 50.7 at size 6.Deeper compositions increase reasoning burden and optimization difficulty, producing a non-monotonic trade-off between generalization and trainability.
- Qualitative behavior: RLRACES responses use explicit representations, hypothesis testing, constraint preservation, and final verification to avoid local errors and falsified rules.In AIME, it applies a uniform function and cross-checks totals; in Enigmata, it tests candidates across demonstrations and verifies all 16 clues.
6 Conclusion
RACES enables modular, recursive assembly of verifiable environments when one environment’s output type matches another’s input type. Experiments show that composing 50 base environments improves generalization and can outperform direct reinforcement learning on 300 initial environments, while composition size controls task difficulty.
- 6 Conclusion: RACES recursively composes verifiable environments when one environment’s codomain aligns with another’s domain.The resulting environment remains verifiable and composable.
- 6 Conclusion: 50 base environments composed with RACES outperform direct reinforcement learning applied to 300 initial environments.This demonstrates more efficient use of available environments.
- 6 Conclusion: RACES consistently enhances generalization across diverse model backbones and evaluation benchmarks.The conclusion attributes this improvement to experiments across varied models and benchmarks.
- 6 Conclusion: Composition size provides a principled control for task difficulty, with moderate depths producing optimal transfer performance.Thus, composition depth affects the difficulty and transfer behavior of generated tasks.
A Limitations … D Initial environments construction.
The paper identifies limitations in composition coverage and model capability, documents LLM-assisted environment construction and writing, discusses positive and negative impacts, and specifies the initial pool and filtering procedures.
- A Limitations: RACES covers representative composition patterns but leaves conditional branching and bounded loops unexplored, while weaker models may produce sparse rewards on composite tasks.The framework’s effectiveness depends on adequate reasoning competence.
- B Declaration of LLM Usage: Claude-Sonnet-4.5 generates candidate verifiable environments that undergo static code self-consistency and multi-sample output consistency filtering.Filtered candidates enter the initial environment pool.
- B Declaration of LLM Usage: LLMs were used for limited writing assistance, specifically grammar checking and minor sentence-level refinement.
- C Broader Impacts: RACES reduces reliance on human annotation by transforming a small environment pool into a structurally diverse and effectively unbounded space of composite tasks.This may improve accessibility of verifiable RL for groups without industrial-scale annotation resources.
- C Broader Impacts: RACES could be misused to synthesize malicious verifiable training data, while large-scale RL training may contribute to environmental impact.Model checkpoints are not released, removing the most direct misuse vector in this work.
- D Initial environments construction.: 300 environments form the initial pool, combining standardized algorithmic datasets, Claude-Sonnet-4.5-generated environments, and manually authored environments.Each environment undergoes quality assurance review.
- D Initial environments construction.: Candidate extensions are rejected for execution failures, 2-second timeouts, no output, more than 400 atomic steps, degenerate outputs, or paths shorter than two steps.Non-degenerate outputs cannot repeat states or siblings, equal 0 or 1, exceed integer 500, exceed length 100, or consist of one repeated character.
- D Initial environments construction.: 45 of the 300 environments are derived from algorithms.
E Case Studies for Pattern Analysis
This appendix presents prompts and key response excerpts for three cases from Section 5.4, emphasizing decision points where Base, RLindividual, and RLRACES diverge.
- E Case Studies for Pattern Analysis: Three Section 5.4 cases are documented through their prompts and key response excerpts.Complete responses are released in the supplementary materials.
- E Case Studies for Pattern Analysis: The excerpts focus on decision points where the three models diverge.
- E Case Studies for Pattern Analysis: The models are consistently labeled Base, RLindividual, and RLRACES.
E.1 AIME: 2 × 2 Grid-Coloring
For the AIME 2025 2 × 2 grid-coloring problem, RACES replaces error-prone ad-hoc counting with a reusable function abstraction and verifies the correct total of 82 in two independent ways.
- Problem: The task asks for the number of red-blue colorings of a 2 × 2 grid in which every square has exactly 2 red and 2 blue sides.The stated ground truth is 82.
- RACES solution: RACES defines f(x,y) based on whether two bits have equal or unequal values, then expresses each square’s count as a function of its internal-edge pair.The total is the sum over all a,b,c,d of f(a,c) · f(b,c) · f(a,d) · f(b,d).
- Verification: 82 is obtained by evaluating all 16 internal-edge assignments correctly and grouping their products into 48, 32, and 2.The groups are 12 rows × 4, 2 rows × 16, and 2 rows × 1.
- Verification: 82 is independently confirmed by summing the complete sequence of 16 row products.The sequential verification also ends at 82.
E.2 Enigmata: List-Transformation Rule Induction
RACES solves Enigmata list-transformation tasks by verifying candidate rules against every demonstration while explicitly tracking indices and preserving consistent rules. Unlike Base and RLindividual, it systematically rejects hypotheses contradicted by earlier examples.
- RACES: RACES tests hypotheses against all examples before accepting a rule, combining exhaustive verification with explicit index–value tracking.This procedure preserves rules that remain consistent across demonstrations rather than relying on a single matching example.
- Base: Base explores broad hypotheses without verification and ultimately guesses after numerous rules fail to explain the demonstrations.Its exploration includes dozens of candidate rules, such as local-maxima removal and suffix extraction.
- RLindividual: RLindividual notes contradictions but continues using a falsified rule, unlike RACES’s systematic rejection of rules that fail earlier examples.RLindividual explicitly observes a contradiction in the demonstrations yet proceeds with the rejected hypothesis.
- RACES: RACES identifies outputs as values appearing multiple times in the input and retains all occurrences of each repeated value.For the test input, 66 appears at indices 2, 4, and 5, so all three occurrences are included.
E.3 Enigmata: Sum Skyscraper Logic Puzzle
The Enigmata puzzle requires filling a 4 × 4 grid with heights 1–4 so every row and column is a permutation of {1, 2, 3, 4} while satisfying visibility-sum clues. RACES solves it through column-wise decomposition and constraint propagation, whereas Base and RLindividual incorrectly conclude that no solution exists.
- RACES solution strategy: RACES switches from row-wise to column-wise decomposition, exhausting the smaller search space first and propagating fixed values to constrain remaining cells.Column clues force values such as N=4 for bottom=4 and C=4 for top=4, narrowing subsequent options.
- Baseline failures: Base and RLindividual commit to incomplete row-wise searches and incorrectly conclude that the puzzle has no solution.Base overlooks the valid row [3,2,4,1] after finding it, while RLindividual tests many Row 1 permutations without completing the necessary search.
- Problem setup: The task fills a 4 × 4 grid with heights 1–4, requiring row and column permutations of {1, 2, 3, 4} and satisfaction of visibility-sum clues on all sides.The clues are top, left, right, bottom: 7 9 4 5 7 9 4 5 5 4 7 9 5 4 7 9.
- RACES solution strategy: Constraint propagation fixes Row 1 as A=3, B=2, C=4, forcing D=1 and determining compatible column options through later row constraints.Further propagation sets G=1 and F=3, fixing Column 3 Option A and Column 2 Option 2.
- Result: All 16 clues pass under the RACES assignment, confirming a valid solution.The final verification reports that every clue is satisfied.