Verifiable Environments Are LEGO Bricks: Recursive Composition for Reasoning Generalization

The fundamental unit of RACES is the verifiable environment. Each verifiable environment $e$ is formally defined as a four-tuple:

where the components are defined as follows: (1) Input sampler $G_{e}$ programmatically yields valid input instances from $\mathcal{X}_{e}$, providing an unlimited stream of training data for each environment. (2) Output mapper $f_{e}:\mathcal{X}_{e}\to\mathcal{Y}_{e}$ produces a unique output for any valid input. $f_{e}$ is implemented as code and encodes the core semantics of the verifiable environment. Its domain $\mathcal{X}_{e}$ and codomain $\mathcal{Y}_{e}$ jointly define the domain signature $\tau_{e}=(\mathcal{X}_{e},\mathcal{Y}_{e})$, which is the primary criterion for determining whether two environments can be composed. (3) Problem descriptor $D_{e}:\mathcal{X}_{e}\to\Sigma^{*}$^†† $\Sigma^{*}$ denotes the natural language space. utilizes a sampled input $x\in\mathcal{X}_{e}$ to render the environment to a solvable problem. (4) Programmatic verifier $V_{e}:\mathcal{Y}_{e}\times\mathcal{Y}_{e}\to\{0,1\}$ evaluates whether a model’s output matches the reference answer $f_{e}(x)$.

This four-tuple characterizes a family of verifiable environments capable of generating an unlimited supply of RL training data and forms the foundation of RACES. Details regarding the construction of initial environments are provided in Appendix D.

RACES leverages the compositional closure property of verifiable environments. Two environments $e_{i}$ and $e_{j}$ with domain signatures $\tau_{e_{i}}=(\mathcal{X}_{e_{i}},\mathcal{Y}_{e_{i}})$ and $\tau_{e_{j}}=(\mathcal{X}_{e_{j}},\mathcal{Y}_{e_{j}})$ are composable if the codomain of the first matches the domain of the second, that is, $\mathcal{Y}_{e_{i}}=\mathcal{X}_{e_{j}}$. Their composition is defined as:

Because both mappers are deterministic, the composite $f_{e_{j}}\circ f_{e_{i}}$ is also deterministic, mapping $\mathcal{X}_{e_{i}}$ to $\mathcal{Y}_{e_{j}}$. Consequently, the composite maintains the same domain-codomain interface as the initial environment and can be further composed with additional environments. More generally, a domain-compatible sequence $(e_{1},\ldots,e_{t})$ induces a composite mapper

with domain signature $(\mathcal{X}_{e_{1}},\mathcal{Y}_{e_{t}})$. If another environment $e^{\prime}$ satisfies $\mathcal{X}_{e^{\prime}}=\mathcal{Y}_{e_{t}}$, the composite can be recursively extended by $f_{e^{\prime}}\circ F_{\pi_{t}}$. This compositional closure enables RACES to expand a finite set of environments into a substantially larger space. In practice, domain matching serves as a proposal mechanism rather than a guarantee of validity. The quality filtering process is detailed in Section 3.3.

To operationalize compositional closure, RACES recursively constructs composite environments through a frontier-based search strategy. Given an environment pool, RACES automatically assembles executable composite environments at scale and renders these as model-facing RL instances. The construction process comprises three stages: composition path discovery, quality assurance, and operator instantiation.

As shown in Figure 1, RACES implements four representative operators: SEQUENTIAL, PARALLEL, SORT, and SELECT.

Table 1 presents a comparison between RL on RACES ($RL_{RACES}$) and RL on individual environments ($RL_{individual}$). $RL_{RACES}$ and $RL_{individual}$ are initialized from the same environment pool and utilize identical RL data scales. Across both model families, RACES consistently demonstrates superior performance. For DeepSeek-R1-Distill-Qwen-14B, $RL_{individual}$ increases the average score marginally, from 48.2 to 48.8. In contrast, RACES improves the average score to 51.3, outperforming $RL_{individual}$ by 2.5 points. For Qwen3-14B, RACES also surpasses $RL_{individual}$, increasing the average score from 60.1 to 61.1. Performance gains are consistent across all benchmarks for both backbones.

$RL_{individual}$ exposes the model to isolated environments, whereas $RL_{RACES}$ trains the model on composed environments that require chaining transformations, maintaining intermediate states, and inferring valid operation orders or subsets. The consistent advantage of RACES indicates that environmental composition offers a more effective training signal than sampling instances from the original environment pool, resulting in stronger transfer on unseen reasoning benchmarks.

We first compare the training dynamics of $RL_{RACES}$ and $RL_{individual}$ on Qwen3-4B-Instruct-2507. A natural expectation is that a method that increases reward more rapidly during reinforcement learning will also achieve superior downstream generalization. However, the results indicate that this expectation does not hold. Figure 2(a) compares the training reward and average performance during RL training. $RL_{individual}$ improves more rapidly and maintains consistently higher rewards throughout training, suggesting that the model adapts more easily to environments. In contrast, $RL_{RACES}$ exhibits progressively slower reward growth, reflecting the increased complexity of composite environments.

However, the advantage of $RL_{individual}$ in training reward does not result in superior downstream performance. As shown in Figure 2(b), the average score of $RL_{individual}$ improves fast at the beginning, and then quickly peaks around 50.5. Conversely, $RL_{RACES}$ continues to improve throughout the training process. While initially comparable to $RL_{individual}$, it gradually surpasses $RL_{individual}$ after the early stages, reaching 51.9 at step 200 compared to 50.4.

These findings differentiate between overfitting to training environments and acquiring transferable reasoning behaviors. Individual environments are shorter and structurally simpler, making them easier to optimize and leading to rapid reward gains. However, this improvement remains largely restricted to the training distribution. Composite environments in RACES require the model to maintain intermediate states, execute multi-step transformations, and, in some cases, infer the latent order of operations. Although these tasks are more challenging and result in slower reward improvement, they offer a richer training signal and produce more sustained gains on downstream benchmarks. This suggests that the primary advantage of RACES is the induction of reasoning patterns that generalize more effectively beyond the training environments.

The results in Figure 2(b) indicate that $RL_{RACES}$ significantly outperforms $RL_{individual}$ when both are provided with the same 300 initial environments. Further analysis examines whether RACES maintains this advantage across varying numbers of environments.

Table 2 compares the performance of Qwen3-4B-Instruct-2507 on 50 and 300 initial environments, denoted as $RL_{setting}(50)$ and $RL_{setting}(300)$ $RL_{individual}$ improves the average score from 49.2 to 50.2 and rises to 50.4 when utilizing all 300 environments. In contrast, $RL_{RACES}(50)$ achieves 50.8, outperforming $RL_{individual}(300)$ with only one-sixth of the base environment pool. $RL_{RACES}(300)$ further increases to 51.9. The same trend appears on DeepSeek-R1-Distill-Qwen-14B. $RL_{RACES}(50)$ reaches 50.2, clearly above $RL_{individual}(300)$ at 48.8.

This substantial difference demonstrates that RACES enhances the efficiency of environment utilization. An individual environment can provide only instances of a single transformation family. However, once composed, the same environment can appear at different positions, with different neighboring environments, under different operators. Thus, composition converts a fixed environment pool into a much larger and structurally more diverse training distribution. This represents the principal advantage of RACES over linear environment scaling, as it increases the utility of each existing environment rather than relying exclusively on synthesizing additional independent environments.

The effect of composition size on training effectiveness is subsequently examined. Composition size is a central control variable in RACES, increasing it does not merely change the amount of generated data but directly changes the structure and difficulty of the resulting composite environments. Larger compositions require the model to maintain more intermediate states, handle longer dependency chains, and tolerate stronger error propagation, thereby increasing the overall reasoning burden.

To isolate this effect, the environment pool is fixed at $|\mathcal{E}|=300$, and variants with different composition sizes are trained on Qwen3-4B-Instruct-2507. The analysis focuses on the SEQUENTIAL operator, for which composition size has the most direct interpretation, and varies the size from 2 to 6. Figure 3 summarizes both the training dynamics and the final performance under different composition sizes.

The training curves reveal a clear increase in optimization difficulty as composition size grows. As shown in Figure 3(a), the rewards are consistently higher for smaller composition sizes and decrease as the size increases, indicating that deeper compositions are harder for the policy to optimize. A similar trend is observed in Figure 3(b). The average reward variance (affecting advantage directly) tends to be lower for larger composition sizes, suggesting that deeper compositions leave a less informative learning signal for RL.

The effect on downstream performance is shown in Table 3. As the composition size increases from 2 to 5, the average score improves steadily from 50.8 to 51.2. However, when the size is increased further to 6, performance decreases to 50.7. This produces a clear non-monotonic trend. Increasing composition size is beneficial up to a moderate-to-large range, but excessively deep compositions become less effective. Taken together, these results reveal a trade-off between reasoning generalization and trainability. Small composition sizes are easier to optimize, but they provide only limited expansion beyond environments. Increasing the composition size introduces richer multi-step reasoning patterns and improves reasoning generalization. However, once the composition becomes too deep, the difficulty of optimization begins to dominate: rewards decrease, reward variance becomes less informative, and final performance deteriorates. In practice, these results suggest that composition size should be regarded as a controllable curriculum variable rather than a parameter to maximize indiscriminately.

To complement the aggregate results, qualitative comparisons are made between responses from the base model, $RL_{individual}$, and $RL_{RACES}$ on identical AIME and Enigmata prompts. Three representative cases are presented in Appendix E.

For AIME. In the $2{\times}2$ grid-coloring problem (Appendix E.1), the base model sets up a valid enumeration but confuses variables when filling the case table and $RL_{individual}$ makes a single inconsistent update on an internal edge color. Both errors are local yet propagate to the final count. The $RL_{RACES}$ model instead introduces a compact function $f(x,y)$ that maps each pair of internal-edge colors to its boundary-assignment count, applies it uniformly, and cross-checks the total via an independent grouping calculation—replacing error-prone table-filling with representation-mediated counting and self-consistency verification.

For Enigmata. In a list-transformation task (Appendix E.2), the base model and $RL_{individual}$ both cycle through surface rules (suffix extraction, duplicate-run selection) without rejecting hypotheses that fail earlier examples and $RL_{individual}$ even notes a contradiction yet continues with the falsified rule. The $RL_{RACES}$ model maintains explicit index–value tracking, tests each candidate against all demonstrations, and identifies the correct rule. A related pattern appears on Sum Skyscraper (Appendix E.3), non-RACES models commit to an incomplete row-wise search and reach a spurious “no valid solution.” $RL_{RACES}$ reframes the search column-by-column, exhausts a smaller space, propagates fixed values through row-uniqueness, and verifies all 16 clues.

These behaviors reflect the RACES training signal. SEQUENTIAL compositions train state carry-over, Parallel compositions train subproblem separation, Sort compositions train order inference, and Select introduces distractor discrimination. The transferable routines, including stable intermediate representations, constraint preservation, hypothesis revision, and final-answer verification, account for the observed performance gains without requiring surface similarity to the training environments.