Compositional Reasoning in Language Models under Reinforcement Learning Post-Training

# Compositional Reasoning in Language Models under Reinforcement Learning Post-Training
Source: [https://arxiv.org/html/2609.19465](https://arxiv.org/html/2609.19465)
###### Abstract

Compositional reasoning is critical for real\-world problem solving: since training data is necessarily limited, models must generalize by composing learned skills in new ways\. While post\-training methods such as reinforcement learning \(RL\) have substantially improved the reasoning abilities of language models \(LMs\), their effects on compositional reasoning remain less well understood\. We propose a dependency\-graph framework to formalize compositional reasoning, yielding three levels of compositionality with increasing complexity\. Empirically, we instantiate this framework with data\-structure tasks, which provide deterministic reward computation and clear compositional structure\. We find a consistent decomposed\-to\-composed asymmetry: decomposed\-skill training does not reliably transfer to composed tasks, whereas composed\-task training transfers more readily back to decomposed tasks\. We provide theoretical explanation for this asymmetry, and further evaluate compositional generalization under length extrapolation, structural distribution shift, and transfer to tasks requiring unseen skills\. Finally, we present a pilot study on real\-world tool\-calling benchmarks, showing preliminary evidence that the decomposed\-to\-composed asymmetry can extend to practical settings\.

### 1Introduction

Compositional reasoning is a prerequisite for general intelligence\. A model cannot merely learn individual skills; it must reuse and combine them systematically to solve unseen, more complex problems\. This is necessary because real\-world reasoning is open\-ended, while training data is inherently limited\. A model cannot be trained on every possible math problem, program, or tool\-use trajectory it may encounter; instead, it must generalize by composing familiar skills in new ways\.

As language models \(LMs\) take on increasingly complex reasoning tasks, understanding their compositional reasoning ability has become critical\. However, existing studies of compositionality in LMs have largely focused on semantic composition in language understanding\[[26](https://arxiv.org/html/2609.19465#bib.bib3),[29](https://arxiv.org/html/2609.19465#bib.bib2)\]or instruction following\[[23](https://arxiv.org/html/2609.19465#bib.bib8)\]\. In contrast, compositionality in reasoning tasks is less understood\. Unlike linguistic composition, where primitives can cleanly correspond to words, phrases, or instructions, reasoning tasks often involve latent skills whose definitions and interactions are non\-trivial to formalize\. This makes it difficult to systematically evaluate whether models can compose reasoning skills\.

On the other hand, reinforcement learning \(RL\) post\-training has recently become a central approach for improving LM reasoning\[[4](https://arxiv.org/html/2609.19465#bib.bib19),[19](https://arxiv.org/html/2609.19465#bib.bib18),[13](https://arxiv.org/html/2609.19465#bib.bib28),[28](https://arxiv.org/html/2609.19465#bib.bib29)\]\. Yet, most work on compositional reasoning studies in\-context learning\[[1](https://arxiv.org/html/2609.19465#bib.bib9),[17](https://arxiv.org/html/2609.19465#bib.bib10),[2](https://arxiv.org/html/2609.19465#bib.bib7),[24](https://arxiv.org/html/2609.19465#bib.bib6)\]or supervised finetuning\[[29](https://arxiv.org/html/2609.19465#bib.bib2),[23](https://arxiv.org/html/2609.19465#bib.bib8),[25](https://arxiv.org/html/2609.19465#bib.bib27)\]\. Much less is known about the effects of RL on compositional reasoning\. For example, one natural approach is to train on individual skills, where the smaller tasks may make it easier to design RL rewards and verifiers\. However, it remains unclear whether LMs can compose the learned skills at test time\.

To address this gap, we formalize compositional reasoning using a dependency\-graph framework\. We define skills as reusable primitives required to solve reasoning tasks, and use dependency graphs to model the compositional structure among them\. This framework provides a formal basis for systematically evaluating compositional reasoning in language models\.

For empirical evaluation, we instantiate the framework using data\-structure tasks from DSR\-Bench\[[8](https://arxiv.org/html/2609.19465#bib.bib14)\], a benchmark for evaluating structural reasoning in LMs\. Data structures are well suited for this study because they provide deterministic, verifiable final outputs for RL reward computation\. Moreover, these algorithmic tasks can be decomposed into clear skills, and the way these skills compose is explicit and unambiguous\. For example, in binary\-search\-tree construction, insertion is the primitive skill, and construction requires applying this skill sequentially\. This controlled setting allows us to compare decomposed\-skill training with composed\-task training and analyze how RL post\-training affects the compositional reasoning ability of LMs\.

A summary of our contributions:

- •Our conceptual contribution is a framework formalizing compositional reasoning in LMs by representing tasks as dependency graphs over reusable primitive skills \(Figure[1](https://arxiv.org/html/2609.19465#S1.F1)\)\. This framework gives rise to three increasingly difficult levels of compositionality with distinct challenges: single\-skill chains, which isolate horizon generalization; multi\-skill chains, which add skill switching; and branch–merge graphs, which further add non\-local dependencies across branches \(Section[3](https://arxiv.org/html/2609.19465#S3)\)\.
- •Empirically, we conduct a controlled RL comparison between decomposed\-skill training and composed\-task training across three compositionality levels, and identify a consistent asymmetry: decomposed\-skill training transfers poorly to composed tasks, whereas composed\-task training transfers more readily back to decomposed tasks\. We further evaluate compositional generalization under three transfer settings: length generalization, distribution shift, and unseen skills \(Section[4](https://arxiv.org/html/2609.19465#S4)\)\.
- •We offer a theoretical explanation for the decomposed\-to\-composed asymmetry through error compounding and coverage shift, showing that composed reasoning requires sustained correctness over induced state distributions that decomposed supervision may not cover \(Section[5](https://arxiv.org/html/2609.19465#S5)\)\.
- •Finally, we conduct a pilot study on real\-world tool\-calling benchmarks, demonstrating preliminary evidence for the decomposed\-to\-composed asymmetry in practical settings \(Section[6](https://arxiv.org/html/2609.19465#S6)\)\.

Skillsk1k2k3k4k5Level I: Single\-Skill Chain\(linear composition\)k1k1k1k1Structure:One skill repeated along one path\.Level II: Multi\-Skill Chain\(linear composition\)k1k2k1k2Structure:Different skills mixed along one path\.Level III: Branch\-Merge Graph\(non\-linear composition\)k3k1k2k2k4k5branchmergeStructure:Multiple\-branched dependency graph\.IncreasingcomplexityChallenge 1:Horizon generalizationChallenge 2:Skill switchingChallenge 3:Non\-local dependency\+\+Decomposed\-to\-Composed AsymmetryTrain on decomposed skillsTest on composed taskshardTrain on composed tasksTest on decomposed skillseasier

Figure 1:Three levels of compositionality with increasing complexity, shown as dependency structures among skills\. Skills are defined as reusable primitives required to solve a reasoning task\.
### 2Related work

##### Compositional generalization and skill composition\.

Compositional generalization has been studied extensively in sequence\-to\-sequence learning, including SCAN\[[12](https://arxiv.org/html/2609.19465#bib.bib15)\], CFQ\[[9](https://arxiv.org/html/2609.19465#bib.bib16)\], and COGS\[[10](https://arxiv.org/html/2609.19465#bib.bib17)\], which evaluate whether models can recombine familiar primitives in novel semantic structures\. Recent work extends this question to language models: SKILL\-MIX\[[26](https://arxiv.org/html/2609.19465#bib.bib3)\]evaluates whether models can generate text combining multiple specified skills;[Zhao et al\. \[29\]](https://arxiv.org/html/2609.19465#bib.bib2)study whether smaller models can learn higher\-order skill combinations from lower\-order examples;[Yang et al\. \[23\]](https://arxiv.org/html/2609.19465#bib.bib8)study compositional generalization in instruction following; and[Yin et al\. \[25\]](https://arxiv.org/html/2609.19465#bib.bib27)study composable chain\-of\-thought supervision for transferring from atomic to compositional tasks\. These works study important forms of linguistic, instructional, or trace\-level composition\. In contrast, we focus on reasoning tasks, where the primitives and their interactions are often less explicit than surface\-level linguistics\.

##### RL post\-training for compositional reasoning\.

RL post\-training with verifiable rewards has recently become a central approach for improving language\-model reasoning\[[4](https://arxiv.org/html/2609.19465#bib.bib19),[19](https://arxiv.org/html/2609.19465#bib.bib18),[13](https://arxiv.org/html/2609.19465#bib.bib28),[28](https://arxiv.org/html/2609.19465#bib.bib29)\], but its role in compositional transfer remains less understood\. Closest to our work,[Yuan et al\. \[27\]](https://arxiv.org/html/2609.19465#bib.bib24)show that RL can teach nested composition of string\-transformation functions, while[Xu et al\. \[22\]](https://arxiv.org/html/2609.19465#bib.bib25)propose Composition\-RL, which constructs harder verifiable prompts by composing existing prompts for RL training\.[Li et al\. \[14\]](https://arxiv.org/html/2609.19465#bib.bib4)study compositional generalization in vision\-language reasoning under SFT and RL\. In contrast, we focus on text\-based reasoning and offer a controlled study of compositional structure from an algorithmic\-reasoning perspective\.

##### Structural and algorithmic reasoning\.

[Dziri et al\. \[5\]](https://arxiv.org/html/2609.19465#bib.bib26)use computation graphs to analyze fixed algorithm executions and show that transformer performance can degrade with compositional complexity\. DSR\-Bench\[[8](https://arxiv.org/html/2609.19465#bib.bib14)\]evaluates structural reasoning through deterministic data\-structure tasks, and recent graph\-reasoning work uses RL to improve LMs on graph\-theoretic tasks\[[7](https://arxiv.org/html/2609.19465#bib.bib21)\]\. We build on this line of work by using data structures as a controlled environment for RL post\-training, while introducing a dependency\-graph framework that characterizes how reusable skills compose and isolates distinct bottlenecks: horizon generalization, skill switching, and non\-local dependencies\.

### 3A dependency\-graph framework for compositionality

We present our conceptual contribution by formalizing compositional reasoning with a*dependency graph*over reusable skills \(Figure[1](https://arxiv.org/html/2609.19465#S1.F1)\), capturing compositional structures in reasoning tasks\. Our framework yields three hierarchical levels of compositionality that isolate distinct bottlenecks: horizon generalization, skill switching, and non\-local dependencies\. This structure also enables our analysis of decomposed\-skill versus composed\-task training\. More broadly, it provides a formal basis for future empirical and theoretical studies of compositional reasoning in language models\.

##### Dependency graph\.

For a task instanceτ∈𝒯\\tau\\in\\mathcal\{T\}, let the dependency graphGτ=\(Vτ,Eτ\)G\_\{\\tau\}=\(V\_\{\\tau\},E\_\{\\tau\}\)be a finite directed acyclic graph \(DAG\), where each node represents a skill invocation and each edge indicates that the output of one invocation is required as input to another\. Intuitively,GτG\_\{\\tau\}specifies*which*intermediate computations must be performed,*which*skill is invoked at each step, and*how*they depend on one another; therefore, it represents the compositional structure within a task\. We use a Binary Search Tree \(BST\) construction task over input\{1,2,3\}\\\{1,2,3\\\}as a running example\.

- •Skill\.We assume a set of reusable skill primitives𝒦\\mathcal\{K\}\. Each skill typek∈𝒦k\\in\\mathcal\{K\}is associated with a functionfk:𝒳k→𝒴kf\_\{k\}:\\mathcal\{X\}\_\{k\}\\rightarrow\\mathcal\{Y\}\_\{k\}, where𝒳k\\mathcal\{X\}\_\{k\}and𝒴k\\mathcal\{Y\}\_\{k\}denote the input and output spaces of that skill\. For example, BST construction is composed of a sequence ofinsertoperations, whereinsertacts as the reusable skill primitive\.
- •Node\.A nodev∈Vτv\\in V\_\{\\tau\}is labeled by a skill typeκ⁡\(v\)∈𝒦\\kappa\(v\)\\in\\mathcal\{K\}, indicating which skill is invoked at that node\. Letzvz\_\{v\}denote the intermediate output produced by nodevv\. For example, a concrete operation of\(insert, 1\)to the current BST is a skill invocation\.
- •Edge\.An edge\(u,v\)∈Eτ\(u,v\)\\in E\_\{\\tau\}indicates a dependency constraint that the intermediate outputzuz\_\{u\}is required to form the input to nodevv\. Letpred⁡\(v\)=\{u∈Vτ:\(u,v\)∈Eτ\}\\mathrm\{pred\}\(v\)=\\\{u\\in V\_\{\\tau\}:\(u,v\)\\in E\_\{\\tau\}\\\}denote the predecessors ofvv\. The inputxvx\_\{v\}and outputzvz\_\{v\}to nodevvare computed via xv=ψv​\(ℓv,\(zu\)u∈pred⁡\(v\)\)∈𝒳κ⁡\(v\),zv=fκ⁡\(v\)​\(xv\)\.x\_\{v\}=\\psi\_\{v\}\\\!\\left\(\\ell\_\{v\},\\left\(z\_\{u\}\\right\)\_\{u\\in\\mathrm\{pred\}\(v\)\}\\right\)\\in\\mathcal\{X\}\_\{\\kappa\(v\)\},\\qquad z\_\{v\}=f\_\{\\kappa\(v\)\}\(x\_\{v\}\)\.Here,ℓv\\ell\_\{v\}denotes local information specified by the task instance \(e\.g\., what value to insert to the tree\) andψv\\psi\_\{v\}is an input\-construction map\. For example, after\(insert, 1\), the next operation\(insert, 2\)takes as input the BST state produced by the previous operation\.
- •Output\.For simplicity, we assume thatGτG\_\{\\tau\}has a unique sink nodevsink∈Vτv\_\{\\mathrm\{sink\}\}\\in V\_\{\\tau\}\. The final output of the task is the intermediate outputzvsinkz\_\{v\_\{\\mathrm\{sink\}\}\}produced at this sink node\. For example, the final output of BST construction is given by the output of the skill invocation\(insert, 3\)\.

##### Three levels of compositionality\.

As illustrated in Figure[1](https://arxiv.org/html/2609.19465#S1.F1), we formalize three levels of compositionality under the dependency\-graph framework\.

- •Level I: Single\-skill chain \(linear composition\)\.Single\-skill chain is the simplest setting, where the same skill is repeated across a sequence of steps\. Formally,GτG\_\{\\tau\}is a path, all nodes share the same skill type, and\|\{κ⁡\(v\):v∈Vτ\}\|=1\|\\\{\\kappa\(v\):v\\in V\_\{\\tau\}\\\}\|=1\. This setting tests whether a model trained on smaller instances can extrapolate to larger ones that require more repetitions of the same reasoning pattern\.
- •Level II: Multi\-skill chain \(linear composition\)\.Multi\-skill chain also has a path\-structured dependency graph, but the skill labelκ⁡\(v\)\\kappa\(v\)may vary across nodes with\|\{κ⁡\(v\):v∈Vτ\}\|\>1\|\\\{\\kappa\(v\):v\\in V\_\{\\tau\}\\\}\|\>1\. This setting tests whether a model can maintain intermediate state while sequentially composing heterogeneous skills, including handling skill switching and interface mismatches across skills\.
- •Level III: Branch\-merge graph \(non\-linear composition\)\.Here,GτG\_\{\\tau\}is a general directed acyclic graph rather than a path\.*Branching*occurs when one intermediate output feeds multiple downstream nodes, while*merging*occurs when a node depends on multiple upstream outputs\.

\(a\) Linear compositionDependency order = execution orderk1k2k4k5Unique validreasoning tracek1k2k4k5\(b\) Non\-linear compositionA valid reasoning trace corresponds to any topological ordering\.k3k1k2ak2bk4k5After k3, any of k1, k2a, k2b can be next\.Multiple*serialized*reasoning traces:k3k1k2ak2bk4k5✓\\checkmarkk3k2ak1k2bk4k5✓\\checkmarkk3k2bk2ak4k1k5✗Non\-local dependency:The execution of k4 requires information from all previous three states \(k1, k2a, k2b\) in the reasoning trace, rather than only the immediately preceding state\.

Figure 2:Reasoning traces serialize dependency graphs\.An explicit step\-by\-step solution can be modeled as a topological ordering of the task dependency graph\.
##### Linear vs\. non\-linear compositions: non\-local dependency\.

We model an explicit step\-by\-step solution as a sequential*reasoning trace*that serializes the dependency graphGτG\_\{\\tau\}\. Under this abstraction, any valid trace must respect the dependencies inGτG\_\{\\tau\}, and thus corresponds to a topological ordering\. As shown in Figure[2](https://arxiv.org/html/2609.19465#S3.F2), linear compositions are chains, so the trace follows a unique order\. In contrast, branch\-merge graphs are non\-linear: branches may be executed in different valid orders before being merged\. At merge points, the model must retrieve and combine intermediate outputs from earlier branches, rather than only propagating the immediately preceding state, which therefore requires coordinating*non\-local*dependencies\.

### 4Controlled RL study of compositional reasoning

We present our empirical contribution by systematically evaluating compositional reasoning under RL fine\-tuning using the three\-level framework above\. We use data\-structure tasks from DSR\-Bench\[[8](https://arxiv.org/html/2609.19465#bib.bib14)\], which are well\-suited because they provide deterministic, exact verification for RL reward computation, along with clear skill decompositions and compositional structure\. We first present our main data\-design finding, the decomposed\-to\-composed asymmetry\. We then analyze the sources of compositional difficulty across the three levels and study generalization beyond length extrapolation\.

![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/final_plots/model_aggregate_2x3_table_no_sft.png)Figure 3:Evaluation on three compositionality types with Qwen3\-4B\-Instruct, averaged across three runs with the standard deviation shown as a shaded region\. Rows evaluate*atomic*\(decomposed skill\) and*compound*\(composed task\) tasks\. RL\-Atomic trains on atomic tasks, while RL\-Compound trains on compound tasks\. Models are trained on small problem lengths \(5\-10\) and evaluated on larger ones \(up to 30\)\. Results show a consistent decomposed\-to\-composed asymmetry\.#### 4\.1Decomposed\-skill vs\. composed\-task training

Our main experimental contrast compares RL post\-training on decomposed skills and on composed tasks\. We use five data\-structure domains of varying difficulty: Array, Binary Search Tree \(BST\), Bloom Filter, Hashmap, and Heap\. Task length denotes the initial input size for atomic tasks and the number of operations for compound tasks\. Details on task description, example prompt, and data preparation can be found in Appendix[C](https://arxiv.org/html/2609.19465#A3)\.

##### Atomic vs\. compound tasks\.

An*atomic*task corresponds to a decomposed skill: a single skill\-invocation applied to a given state\. For example, in an atomic array task of length 3, given\[1,2,3\]\[1,2,3\], the model may be asked to insert44at position22, yielding\[1,2,4,3\]\[1,2,4,3\]\. A*compound*task corresponds to a composed task: a sequence of skill invocations, where intermediate states must be carried forward\. For example, in a compound array task of length 3, given\[1,2,3\]\[1,2,3\], the model may execute “insert44at position22, delete position00, then insert55at position11,” and return the final array\.

##### Decomposed\-skill vs\. composed\-task training\.

We use Qwen3\-4B\-Instruct\[[21](https://arxiv.org/html/2609.19465#bib.bib11)\]as the mainBasemodel, and additionally evaluate two more models from different families and sizes: OLMo\-3\-7B\-Instruct\[[15](https://arxiv.org/html/2609.19465#bib.bib12)\]and Llama\-3\.1\-8B\-Instruct\[[6](https://arxiv.org/html/2609.19465#bib.bib1)\]on multi\-skill chains\. We use instruct models for their instruction\-following ability, while excluding models already heavily post\-trained for reasoning\. For each base model, we compareRL\-Atomic, trained only on atomic tasks, withRL\-Compound, trained only on compound tasks\. Both use Group Relative Policy Optimization\[[4](https://arxiv.org/html/2609.19465#bib.bib19)\]with binary final rewards, while keeping the number of training steps the same\. Each problem in DSR\-Bench has a uniquely verifiable final answer\[[8](https://arxiv.org/html/2609.19465#bib.bib14)\]\. Refer to Appendix[C](https://arxiv.org/html/2609.19465#A3)for details on reward computation, training setup, and hyperparameters\.

##### Main observation: Decomposed\-to\-composed asymmetry\.

As shown in Figures[3](https://arxiv.org/html/2609.19465#S4.F3)and[4](https://arxiv.org/html/2609.19465#S4.F4), we observe a consistent asymmetry across three levels of compositionality and model families\. Atomic training often improves atomic\-task performance, but does not reliably transfer to compound tasks\. In contrast, compound training largely preserves or improves atomic\-task performance while substantially improving compound\-task performance\. This suggests that learning decomposed skills in isolation is insufficient for learning how to compose them: composed\-task training exposes the model to both the skills and their interactions\. We provide theoretical support in Section[5](https://arxiv.org/html/2609.19465#S5)\. This shared observation motivates the remaining subsections, where we analyze sources of compositional challenges in a more fine\-grained manner using the three\-level framework introduced in Section[3](https://arxiv.org/html/2609.19465#S3)\.

#### 4\.2Level I \(Single\-skill chain\): Horizon generalization

Single\-skill chained composition tests whether a model can repeatedly apply one skill invocation over a long dependent rollout\. As shown in Figure[1](https://arxiv.org/html/2609.19465#S1.F1), the dependency graph is a path with the same skill type at every node, yielding a unique valid serialized reasoning trace\. This setting isolates horizon generalization, where horizon is the number of sequential skill invocations\. Note this is distinct from problem length, which denotes input size\. Empirically, we instantiate this setting by stacking insertion operations across the five data\-structure domains, treating insertion as a skill\.

##### Compositional challenge 1: horizon generalization\.

In Level I \(Single\-skill chain\) of Figure[3](https://arxiv.org/html/2609.19465#S4.F3), both RL\-Atomic and RL\-Compound consistently improve over the base model, indicating that RL post\-training improves the underlying skill\. However, the decomposed\-to\-composed asymmetry persists: RL\-Atomic gives only marginal gains on compound tasks, whereas RL\-Compound improves both atomic and compound performance\. Moreover, performance drops much more sharply on compound than atomic tasks across all models, showing that even repeated invocation of a simple skill poses a horizon\-generalization challenge: success requires staying correct across many intermediate states, where one early error can corrupt all later operations\.

#### 4\.3Level II \(Multi\-skill chain\): Level I \+ Skill switching

![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/final_plots/olmo_3_7b_instruct_aggregate_compact_1x4_olmo_llama.png)Figure 4:Multi\-skill chained composition with OLMo\-3\-7B\-Instruct and Llama\-3\.1\-8B\-Instruct\.Multi\-skill chained composition adds a second bottleneck beyond horizon generalization: skill switching\. Unlike single\-skill chain, where one skill is repeatedly invoked, multi\-skill chain requires composing heterogeneous skills in sequence and handling the interfaces between them, where the output produced by one skill must be converted into the appropriate input state for the next\. We instantiate this setting by adding deletion as an additional skill across the five data\-structure domains\. Thus, RL\-Atomic trains on single\-step insertion or deletion, while RL\-Compound trains on multi\-step tasks with randomly interleaved insertions and deletions\.

##### Compositional challenge 2: skill switching\.

The decomposed\-to\-composed asymmetry becomes more pronounced in Level II \(Multi\-skill chain\) of Figure[3](https://arxiv.org/html/2609.19465#S4.F3), and also appears for OLMo\-3\-7B\-Instruct and Llama\-3\.1\-8B\-Instruct in Figure[4](https://arxiv.org/html/2609.19465#S4.F4)\. With heterogeneous skill composition, RL\-Compound clearly improves compound\-task performance, whereas RL\-Atomic provides little or no gain over the base models\. On atomic tasks, RL\-Compound remains comparable to RL\-Atomic, indicating that compound training improves on both atomic and compound tasks\. Figure[6](https://arxiv.org/html/2609.19465#S4.F6)further shows that RL\-Atomic stays close to the base model as the number of skill switches increases, suggesting that atomic training does not teach transitions between heterogeneous skills\. Thus, decomposed\-skill training becomes insufficient beyond repeatedly stacking one skill: the model must learn to switch skills and propagate intermediate states across changing skill input and output requirements\.

![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/final_plots/multi_compound_accuracy_vs_switches.png)Figure 5:Accuracy as a function of the number of skill switches between insertion and deletion\.
![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/final_plots/model_aggregate_sft_multi_only_atomic.png)

![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/final_plots/model_aggregate_sft_multi_only_compound.png)

Figure 6:Comparison of post\-training methods: supervised fine\-tuning \(SFT\) vs\. reinforcement learning \(RL\) for multi\-skill chained composition\.

##### SFT vs\. RL post\-training\.

Both supervised fine\-tuning \(SFT\) and reinforcement learning \(RL\) are widely used post\-training methods\. We further compare RL with supervised fine\-tuning \(SFT\) using programmatically generated SFT training samples\. Data\-structure tasks make this feasible because their algorithmic structure allows chain\-of\-thought templates for each skill to be instantiated with task\-specific values\. In principle, these structured traces should make the training pattern easy for SFT to learn\. However, as shown in Figure[6](https://arxiv.org/html/2609.19465#S4.F6), SFT performs well in\-domain but degrades sharply on larger out\-of\-domain instances, whereas RL shows better length generalization\. This suggests that SFT mainly learns the in\-domain pattern, while RL better supports generalization beyond the training regime, consistent with prior findings\[[3](https://arxiv.org/html/2609.19465#bib.bib13)\]\. Details of SFT training are in Appendix[C](https://arxiv.org/html/2609.19465#A3)\.

#### 4\.4Level III \(Branch\-merge graph\): Level II \+ Non\-local dependency

Segment\-tree construction as a branch–merge graphExample input array:\[2,−1,3\]\[2,\-1,3\]SkillsSplit indexintervalSolve leafbranchesMergeSplit\[1,3\]\[1,3\]Split\[1,2\]\[1,2\]Leaf\[3,3\]\[3,3\]Leaf\[1,1\]\[1,1\]Leaf\[2,2\]\[2,2\]Merge\[1,2\]\[1,2\]Merge\[1,3\]\[1,3\]Finalsegment tree\[1,2\]\[1,2\]\[3,3\]\[3,3\]value=2\\text\{value\}=2value=−1\\text\{value\}=\-1value=3\\text\{value\}=3

Figure 7:A simplified example illustration\.As contrasted in Section[3](https://arxiv.org/html/2609.19465#S3), unlike the linear compositions above, branch–merge graphs represent non\-linear composition: computation branches into multiple intermediate chains and later merges their results\. A valid reasoning trace may correspond to any topological ordering of the dependency graph, introducing a third bottleneck beyond horizon generalization and skill switching: non\-local dependency coordination\. At merge points, the model must retrieve, align, and combine outputs from earlier branches, rather than simply propagate the immediately preceding state\. We use segment\-tree construction as the branch–merge task, illustrated in Figure[7](https://arxiv.org/html/2609.19465#S4.F7), with details deferred to Appendix[C](https://arxiv.org/html/2609.19465#A3)\.

##### Compositional challenge 3: non\-local dependency\.

The decomposed\-to\-composed asymmetry is most significant in Level III \(Branch–merge graph\) of Figure[3](https://arxiv.org/html/2609.19465#S4.F3)\. All methods remain near ceiling on atomic tasks, indicating that the underlying skills are not difficult\. However, a huge gap emerges on compound tasks: RL\-Atomic gives little improvement over the base model and quickly collapses to near\-zero accuracy, whereas RL\-Compound performs substantially better\. This suggests that decomposed\-skill training is insufficient when reasoning requires coordinating non\-local dependencies across branches\. We note RL\-Compound also degrades sharply as problem length increases, showing that non\-local coordination is a stronger bottleneck than long horizon or skill switching alone\.

#### 4\.5Beyond length: structural shift and unseen skills

Above, we primarily vary problem length or execution horizon\. We now test whether composed\-task training generalizes under two additional forms of shift\. First, Figure[8](https://arxiv.org/html/2609.19465#S4.F8)\(a,b\) tests robustness under structural distribution shift by varying BST skewness and the graph\-construction threshold \(which determines whether an edge is added between two nodes\); composed\-task training remains robust, though its gains depend on structural difficulty\. Second, Figure[8](https://arxiv.org/html/2609.19465#S4.F8)\(c\) tests transfer to tasks requiring unseen skills: multi\-dimensional computation in KD\-Tree and Geometric Graph construction, and mapping natural\-language scenarios to formal BST and graph tasks in Clinical Appointments and Galaxy Traveling\. Performance improves only modestly, suggesting that composed training alone is insufficient when new reasoning skills are required\. Experiment details can be found in Appendix[D](https://arxiv.org/html/2609.19465#A4)\.

![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/final_plots/aggregate_shift_transfer.png)Figure 8:\(a,b\) Distribution\-shift generalization on BST and graph construction\. \(c\) Transfer to multi\-dimensional and natural\-language tasks\. Error bars denote 95% confidence intervals\.

### 5Theoretical explanation of the asymmetry

We provide a theoretical explanation of the underlying mechanisms for the observed decomposed\-to\-composed asymmetry\. Full statements, proofs, and additional analysis are deferred to Appendix[B](https://arxiv.org/html/2609.19465#A2)\.

#### 5\.1Why transfer from decomposition to composition is hard

Following the compositionality framework in Section[3](https://arxiv.org/html/2609.19465#S3), a taskτ\\tauis represented by a dependency graphGτ=\(Vτ,Eτ\)G\_\{\\tau\}=\(V\_\{\\tau\},E\_\{\\tau\}\)\. Each nodev∈Vτv\\in V\_\{\\tau\}is a skill invocation with an inputxvx\_\{v\}and an outputzvz\_\{v\}\. Atomic tasks involve only one skill invocation;*compound*tasks require multiple dependent invocations before returning the sink\-node outputzvsinkz\_\{v\_\{\\text\{sink\}\}\}\.

We model an autoregressive solution as a serialized rollout ofGτG\_\{\\tau\}\(Figure[2](https://arxiv.org/html/2609.19465#S3.F2)\)\. For a*compound*task with horizon\|Vτ\|=T\|V\_\{\\tau\}\|=T, the step\-ttstatests\_\{t\}encodes the task, the executed\-node setP⁡\(st\)⊂VτP\(s\_\{t\}\)\\subset V\_\{\\tau\}, and all intermediate outputs so far\. The set of nodes that are ready to execute next isR⁡\(st\)=\{v∈Vτ∖P⁡\(st\):pred⁡\(v\)⊆P⁡\(st\)\}R\(s\_\{t\}\)=\\\{v\\in V\_\{\\tau\}\\setminus P\(s\_\{t\}\):\\mathrm\{pred\}\(v\)\\subseteq P\(s\_\{t\}\)\\\}\. Correctness is defined over a set of next invocation\-output pairs because branch–merge graphs may admit several valid topological orderings\. Define the*decision context*Q⁡\(st\)=\{\(κ⁡\(v\),xv​\(st\)\):v∈R⁡\(st\)\}Q\(s\_\{t\}\)=\\\{\(\\kappa\(v\),x\_\{v\}\(s\_\{t\}\)\):v\\in R\(s\_\{t\}\)\\\}, wherexv​\(st\)x\_\{v\}\(s\_\{t\}\)is the input to ready nodevv\. Identifying invocations by skill type and input rather than node name, the set of valid invocation\-output pairs is

ℐ∗​\(st\)=\{\(\(κ,x\),fκ​\(x\)\):\(κ,x\)∈Q⁡\(st\)\}\.\\mathcal\{I\}^\{\*\}\(s\_\{t\}\)=\\\{\(\(\\kappa,x\),f\_\{\\kappa\}\(x\)\):\(\\kappa,x\)\\in Q\(s\_\{t\}\)\\\}\.Therefore, a policyπ^\\hat\{\\pi\}makes a mistake whenπ^​\(s\)∉ℐ∗​\(s\)\\hat\{\\pi\}\(s\)\\notin\\mathcal\{I\}^\{\*\}\(s\)\. Each valid step completes one ready node, so a rollout with no mistakes inTTsteps produces the correct final output\. For stochastic policies, we assume the output distribution depends on the rollout history only through the current state; probabilities include policy randomness\.

Letqqbe the decision\-context distribution induced by the*atomic*task training data\. Define the atomic\-distribution error asϵatom​\(π^,q\)=𝔼c∼q​\[eπ^​\(c\)\]\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)=\\mathbb\{E\}\_\{c\\sim q\}\[e\_\{\\hat\{\\pi\}\}\(c\)\]\.

For compound tasksτ∼ρT\\tau\\sim\\rho\_\{T\}, letμt\\mu\_\{t\}be the distribution ofQ⁡\(st\)Q\(s\_\{t\}\)conditioned on there being no earlier mistakes\. Assuming every context in the support ofμt\\mu\_\{t\}has nonzero probability underqqfor everyt∈\[T\]t\\in\[T\], define the coverage factor

CT\(q\)=supc:q⁡\(c\)\>0∑t=1Tμt​\(c\)q⁡\(c\)<∞,C\_\{T\}\(q\)=\\sup\_\{c:q\(c\)\>0\}\\frac\{\\sum\_\{t=1\}^\{T\}\\mu\_\{t\}\(c\)\}\{q\(c\)\}<\\infty,which measures how well the training data covers contexts encountered across all steps of a compound rollout\. It is large when a correct rollout contains contexts that are rare under atomic supervision\.

###### Lemma 5\.1\(informal\)\.

Under the preceding assumptions, letF=1F=1denote the event that the model fails to produce the correct final outputzvsinkz\_\{v\_\{\\text\{sink\}\}\}on a compound task drawn fromρT\\rho\_\{T\}\. Then,

Pr\[F=1\]≤CT\(q\)ϵatom\(π^;q\)\.\\Pr\[F=1\]\\leq C\_\{T\}\(q\)\\,\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)\.\(1\)Moreover, this bound is tight in the worst case\.

The bound in Equation[1](https://arxiv.org/html/2609.19465#S5.E1)shows that decomposed\-to\-composed transfer requires more than low atomic error\. The bound accumulates step errors across allTTrollout steps, under decision\-context distributions that atomic training may not cover well\. Although the bound has no explicit multiplicative factorTT, it is not horizon\-free: whenever the policy can reach every rollout position with positive mistake\-free probability, the cumulative coverage factor must satisfyCT​\(q\)≥TC\_\{T\}\(q\)\\geq T\. Thus, matchingq⁡\(c\)q\(c\)toT−1​∑t=1Tμt​\(c\)T^\{\-1\}\\sum\_\{t=1\}^\{T\}\\mu\_\{t\}\(c\)recovers an upper bound ofT​ϵatom​\(π^,q\)T\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\), while a poorer coverage weakens this guarantee\. Proposition[B\.2](https://arxiv.org/html/2609.19465#A2.Thmtheorem2)in Appendix[B\.1](https://arxiv.org/html/2609.19465#A2.SS1)shows that this horizon dependence is unavoidable\.

Lemma[5\.1](https://arxiv.org/html/2609.19465#S5.Thmtheorem1)also helps interpret differences across the three levels of compositionality\. Level I increases the rollout horizon, so even repeatedly applying a single skill leads to aT​ϵatom​\(π^,q\)T\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)\-scaling in the worse case\. Level II introduces skill switches, so intermediate outputs must be carried across states around transitions between skill types\. These transitions can produce skill\-input pairs that are rare underqq, increasingCT​\(q\)C\_\{T\}\(q\), consistent with Figure[6](https://arxiv.org/html/2609.19465#S4.F6)\. Level III adds merge points whose correct execution depends on multiple predecessor outputs, and the resulting input tuples may be rare underqq\. Level III can also expose several distinct ready skill\-input pairs simultaneously, creating non\-singleton contexts that lie outside the support of any purely atomic training distribution\. When reached with positive probability before the first mistake, these contexts create a structural gap in coverage: atomic error places no constraint on the policy’s error at these decisions\. Thus, even perfect atomic accuracy cannot rule out compound failure without additional assumptions linking performance on singleton and multi\-invocation contexts\.

#### 5\.2Why transfer from composition to decomposition is easier

Performance generalization from compound to atomic tasks avoids accumulating errors across the rollout\. Assume each compound task has a unique source node, so its initial decision context is a singleton\. Therefore, under a non\-recoverability assumption, good compound performance directly constrains the model’s error on the first\-step context induced by the compound\-task distribution\.

Letϵcomp​\(π^,ρT\)\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\\rho\_\{T\}\)be the compound\-task error, and lets1s\_\{1\}be the initial state forτ∼ρT\\tau\\sim\\rho\_\{T\}\. The first\-step error induced by the compound task distributionρT\\rho\_\{T\}isϵatom\(1\)\(π^;ρT\)=Pr\[π^\(s1\)∉ℐ∗\(s1\)\]\\epsilon\_\{\\mathrm\{atom\}\}^\{\(1\)\}\(\\hat\{\\pi\};\\rho\_\{T\}\)=\\Pr\[\\hat\{\\pi\}\(s\_\{1\}\)\\notin\\mathcal\{I\}^\{\*\}\(s\_\{1\}\)\]\. If a mistake in the first step necessarily prevents successful completion, thenϵatom\(1\)​\(π^,ρT\)≤ϵcomp​\(π^,ρT\)\\epsilon\_\{\\mathrm\{atom\}\}^\{\(1\)\}\(\\hat\{\\pi\};\\rho\_\{T\}\)\\leq\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\\rho\_\{T\}\)because every first\-step error is a compound failure\.

For atomic test cases drawn from a target context distributionqqcovered by this first\-step marginal, the same argument holds up to a coverage factor under context invariance\. Letq1ρTq\_\{1\}^\{\\rho\_\{T\}\}be the distribution over first\-step decision contexts induced by compound tasks, i\.e\.,q1ρT\(c\)=Prτ∼ρT\[Q\(s1\)=c\]q\_\{1\}^\{\\rho\_\{T\}\}\(c\)=\\Pr\_\{\\tau\\sim\\rho\_\{T\}\}\[Q\(s\_\{1\}\)=c\]\. Assumingqqputs no mass on contexts outside the support ofq1ρTq\_\{1\}^\{\\rho\_\{T\}\}and the coverage factor below is finite, we have

ϵatom\(π^;q\)≤C1\(q,ρT\)ϵcomp\(π^;ρT\),whereC1\(q,ρT\)=supc:q1ρT​\(c\)\>0q⁡\(c\)q1ρT​\(c\)\.\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)\\leq C\_\{1\}\(q,\{\\rho\_\{T\}\}\)\\,\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\{\\rho\_\{T\}\}\),\\qquad\\text\{where \}C\_\{1\}\(q,\{\\rho\_\{T\}\}\)=\\sup\_\{c:q\_\{1\}^\{\\rho\_\{T\}\}\(c\)\>0\}\\frac\{q\(c\)\}\{q\_\{1\}^\{\\rho\_\{T\}\}\(c\)\}\.
Whenq=q1ρTq=q\_\{1\}^\{\\rho\_\{T\}\},C1​\(q,ρT\)=1C\_\{1\}\(q,\{\\rho\_\{T\}\}\)=1, and small compound error implies small atomic error on this context distribution\. Thus, under these assumptions, good compound performance controls error on covered atomic test cases, consistent with the RL\-Compound results in Figures[3](https://arxiv.org/html/2609.19465#S4.F3)and[4](https://arxiv.org/html/2609.19465#S4.F4)\.

### 6Pilot study: multi\-call tool use

![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/final_plots/bfcl_seeded_barplot_mean_std.png)Figure 9:Decomposed\-to\-composed asymmetry in a tool\-calling benchmark\.We show preliminary evidence of practical implications for RL post\-training data design as language models are increasingly applied to complex real\-world tasks\. We provide a pilot test using the Berkeley Function Calling Leaderboard \(BFCL\)\[[16](https://arxiv.org/html/2609.19465#bib.bib20)\], a benchmark that maps user requests to valid tool calls\. Here, a skill corresponds to a tool\-calling schema for a specific function\. We define atomic tasks using thesimple\_pythonsplit, where each example requires one function call, and compound tasks using theparallelandparallel\_multiplesplits, where each request requires multiple calls\. We use the same RL setup as main experiments with Qwen3\-4B\-Instruct\. Figure[9](https://arxiv.org/html/2609.19465#S6.F9)shows the same asymmetry: decomposed\-skill training does not generalize well to compound tasks, whereas composed\-task training performs well on both tasks\. The results further motivate composed\-task training as a necessary and beneficial data\-design principle for RL post\-training\. Dataset description and experiment details can be found in Appendix[C](https://arxiv.org/html/2609.19465#A3)\. We discuss potential implications of this design principle for proof writing, coding agents, and tool\-calling agents in Appendix[E](https://arxiv.org/html/2609.19465#A5)\.

### 7Conclusion

We study compositional reasoning in language models under RL post\-training, formalizing it as the execution of reusable skills over dependency graphs with three levels of compositional complexity\. Using controlled data\-structure tasks, we evaluate these levels and find a consistent decomposed\-to\-composed asymmetry: training on decomposed skills transfers poorly to composed tasks, whereas training on composed tasks transfers more readily to decomposed settings\. We explain this asymmetry through error compounding and coverage shift, and further evaluate generalization beyond length extrapolation under structural distribution shifts and transfer to tasks requiring unseen skills\. A pilot study in multi\-call tool use provides preliminary evidence that the same asymmetry can arise in a practical domain\. Overall, our results suggest that RL post\-training cannot rely on decomposed skill supervision alone: exposing models to structured interactions among skills is important for improving composed reasoning while preserving performance on decomposed skills\.

##### Limitations and future work\.

We primarily evaluate compound tasks using final\-output accuracy\. Although intermediate\-state accuracy could be informative, our preliminary studies found that requiring intermediate outputs reduced final accuracy, and potentially constrained models’ ability to reason freely\. Similarly, using Structured Outputs with JSON also reduced accuracy, likely due to added formatting burden\. These design choices are further discussed in Appendix[F](https://arxiv.org/html/2609.19465#A6)\. Future work could use LLM\-based judging to track intermediate reasoning traces and parse final outputs\. In addition, our empirical evaluation focuses on controlled data\-structure tasks and broader validation on real\-world benchmarks remains an important direction, with our BFCL pilot study as a first step\.

### Contribution statement

YH led the project and contributed to the conceptual development, empirical components, and writing of the manuscript\. YL contributed to the theoretical proofs on asymmetry\. YW contributed to the conceptual framing and research discussions\. EV advised the project\.

### Acknowledgments and Disclosure of Funding

YH is supported by a Cubist PhD Fellowship\. YL is supported by an Amazon AI Fellowship\. EV gratefully acknowledges support from the National Science Foundation under award CCF\-2338226 and the AI2050 program at Schmidt Sciences\. We thank Connor Lawless, Anders Wikum, and Nikil Selvam for their feedback on this manuscript\.

### References

- \[1\]K\. Ahuja and A\. Mansouri\(2025\)On provable length and compositional generalization\.External Links:2402\.04875,[Link](https://arxiv.org/abs/2402.04875)Cited by:[Appendix A](https://arxiv.org/html/2609.19465#A1.p1.1),[§1](https://arxiv.org/html/2609.19465#S1.p3.1)\.
- \[2\]H\. Chang, J\. Park, H\. Cho, S\. Yang, M\. Ko, H\. Hwang, S\. Won, D\. Lee, Y\. Ahn, and M\. Seo\(2026\)Characterizing pattern matching and its limits on compositional task structures\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=VCjlm003WL)Cited by:[Appendix A](https://arxiv.org/html/2609.19465#A1.p1.1),[§1](https://arxiv.org/html/2609.19465#S1.p3.1)\.
- \[3\]T\. Chu, Y\. Zhai, J\. Yang, S\. Tong, S\. Xie, D\. Schuurmans, Q\. V\. Le, S\. Levine, and Y\. Ma\(2025\)SFT memorizes, RL generalizes: a comparative study of foundation model post\-training\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=dYur3yabMj)Cited by:[§4\.3](https://arxiv.org/html/2609.19465#S4.SS3.SSS0.Px2.p1.1)\.
- \[4\]DeepSeek\-AI\(2025\)DeepSeek\-r1: incentivizing reasoning capability in llms via reinforcement learning\.External Links:2501\.12948,[Link](https://arxiv.org/abs/2501.12948)Cited by:[§1](https://arxiv.org/html/2609.19465#S1.p3.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px2.p1.1),[§4\.1](https://arxiv.org/html/2609.19465#S4.SS1.SSS0.Px2.p1.1)\.
- \[5\]N\. Dziri, X\. Lu, M\. Sclar, X\. L\. Li, L\. Jiang, B\. Y\. Lin, P\. West, C\. Bhagavatula, R\. Le Bras, J\. D\. Hwang,et al\.\(2023\)Faith and fate: limits of transformers on compositionality \(2023\)\.arXiv preprint arXiv:2305\.186543\.Cited by:[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px3.p1.1)\.
- \[6\]A\. G\. et al\.\(2024\)The llama 3 herd of models\.External Links:2407\.21783,[Link](https://arxiv.org/abs/2407.21783)Cited by:[§4\.1](https://arxiv.org/html/2609.19465#S4.SS1.SSS0.Px2.p1.1)\.
- \[7\]X\. Guo, A\. Li, Y\. Wang, S\. Jegelka, and Y\. Wang\(2026\)$\\texttt\{g1\}$: teaching LLMs to reason on graphs with reinforcement learning\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=Lq4nneD2xX)Cited by:[§C\.2](https://arxiv.org/html/2609.19465#A3.SS2.p3.1),[§C\.4](https://arxiv.org/html/2609.19465#A3.SS4.p1.1),[Appendix F](https://arxiv.org/html/2609.19465#A6.p1.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px3.p1.1)\.
- \[8\]Y\. He, Y\. Li, C\. White, and E\. Vitercik\(2026\)Can llms reason structurally? benchmarking via the lens of data structures\.External Links:2505\.24069,[Link](https://arxiv.org/abs/2505.24069)Cited by:[§C\.1](https://arxiv.org/html/2609.19465#A3.SS1.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.19465#S1.p5.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px3.p1.1),[§4\.1](https://arxiv.org/html/2609.19465#S4.SS1.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2609.19465#S4.p1.1)\.
- \[9\]D\. Keysers, N\. Schärli, N\. Scales, H\. Buisman, D\. Furrer, S\. Kashubin, N\. Momchev, D\. Sinopalnikov, L\. Stafiniak, T\. Tihon, D\. Tsarkov, X\. Wang, M\. van Zee, and O\. Bousquet\(2020\)Measuring compositional generalization: a comprehensive method on realistic data\.InInternational Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px1.p1.1)\.
- \[10\]N\. Kim and T\. Linzen\(2020\)COGS: a compositional generalization challenge based on semantic interpretation\.InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),B\. Webber, T\. Cohn, Y\. He, and Y\. Liu \(Eds\.\),Online,pp\. 9087–9105\.External Links:[Link](https://aclanthology.org/2020.emnlp-main.731/),[Document](https://dx.doi.org/10.18653/v1/2020.emnlp-main.731)Cited by:[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px1.p1.1)\.
- \[11\]W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. E\. Gonzalez, H\. Zhang, and I\. Stoica\(2023\)Efficient memory management for large language model serving with pagedattention\.InProceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles,Cited by:[§C\.5](https://arxiv.org/html/2609.19465#A3.SS5.SSS0.Px1.p1.1),[Appendix F](https://arxiv.org/html/2609.19465#A6.p2.1)\.
- \[12\]B\. Lake and M\. Baroni\(2018\)Generalization without systematicity: on the compositional skills of sequence\-to\-sequence recurrent networks\.InProceedings of the 35th International Conference on Machine Learning,J\. Dy and A\. Krause \(Eds\.\),Proceedings of Machine Learning Research, Vol\.80,pp\. 2873–2882\.Cited by:[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px1.p1.1)\.
- \[13\]N\. Lambert, J\. Morrison, V\. Pyatkin, S\. Huang, H\. Ivison, F\. Brahman, L\. J\. V\. Miranda, A\. Liu, N\. Dziri, X\. Lyu, Y\. Gu, S\. Malik, V\. Graf, J\. D\. Hwang, J\. Yang, R\. L\. Bras, O\. Tafjord, C\. Wilhelm, L\. Soldaini, N\. A\. Smith, Y\. Wang, P\. Dasigi, and H\. Hajishirzi\(2025\)Tulu 3: pushing frontiers in open language model post\-training\.InSecond Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=i1uGbfHHpH)Cited by:[§1](https://arxiv.org/html/2609.19465#S1.p3.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px2.p1.1)\.
- \[14\]T\. Li, J\. Zhang, Y\. Rao, and Y\. Cheng\(2025\)Unveiling the compositional ability gap in vision\-language reasoning model\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=J76cCYTJub)Cited by:[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px2.p1.1)\.
- \[15\]T\. Olmo and A\. E\. et al\.\(2025\)Olmo 3\.External Links:2512\.13961,[Link](https://arxiv.org/abs/2512.13961)Cited by:[§4\.1](https://arxiv.org/html/2609.19465#S4.SS1.SSS0.Px2.p1.1)\.
- \[16\]S\. G\. Patil, H\. Mao, F\. Yan, C\. C\. Ji, V\. Suresh, I\. Stoica, and J\. E\. Gonzalez\(2025\)The berkeley function calling leaderboard \(BFCL\): from tool use to agentic evaluation of large language models\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=2GmDdhBdDk)Cited by:[§C\.7](https://arxiv.org/html/2609.19465#A3.SS7.p1.1),[§6](https://arxiv.org/html/2609.19465#S6.p1.1)\.
- \[17\]R\. Ramesh, E\. S\. Lubana, M\. Khona, R\. P\. Dick, and H\. Tanaka\(2024\)Compositional capabilities of autoregressive transformers: a study on synthetic, interpretable tasks\.InForty\-first International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=L1eJ3NKPCd)Cited by:[Appendix A](https://arxiv.org/html/2609.19465#A1.p1.1),[§1](https://arxiv.org/html/2609.19465#S1.p3.1)\.
- \[18\]F\. Redhardt, Y\. Akram, and S\. Schug\(2025\)Scaling can lead to compositional generalization\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=hZt0daVIZi)Cited by:[Appendix A](https://arxiv.org/html/2609.19465#A1.p1.1)\.
- \[19\]Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. K\. Li, Y\. Wu, and D\. Guo\(2024\)DeepSeekMath: pushing the limits of mathematical reasoning in open language models\.External Links:2402\.03300,[Link](https://arxiv.org/abs/2402.03300)Cited by:[§C\.5](https://arxiv.org/html/2609.19465#A3.SS5.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.19465#S1.p3.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px2.p1.1)\.
- \[20\]G\. Sheng, C\. Zhang, Z\. Ye, X\. Wu, W\. Zhang, R\. Zhang, Y\. Peng, H\. Lin, and C\. Wu\(2024\)HybridFlow: a flexible and efficient rlhf framework\.arXiv preprint arXiv: 2409\.19256\.Cited by:[§C\.5](https://arxiv.org/html/2609.19465#A3.SS5.SSS0.Px1.p1.1)\.
- \[21\]Q\. Team\(2025\)Qwen3 technical report\.External Links:2505\.09388,[Link](https://arxiv.org/abs/2505.09388)Cited by:[§4\.1](https://arxiv.org/html/2609.19465#S4.SS1.SSS0.Px2.p1.1)\.
- \[22\]X\. Xu, C\. Bai, K\. Yang, T\. Chen, Y\. Chen, W\. Liu, H\. Chen, Y\. Wang, S\. Yang, and C\. Yang\(2026\)Composition\-rl: compose your verifiable prompts for reinforcement learning of large language models\.arXiv preprint arXiv:2602\.12036\.Cited by:[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px2.p1.1)\.
- \[23\]H\. Yang, H\. Lu, W\. Lam, and D\. Cai\(2024\)Exploring compositional generalization of large language models\.InProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 4: Student Research Workshop\),Y\. \(\. Cao, I\. Papadimitriou, A\. Ovalle, M\. Zampieri, F\. Ferraro, and S\. Swayamdipta \(Eds\.\),Mexico City, Mexico,pp\. 16–24\.External Links:[Link](https://aclanthology.org/2024.naacl-srw.3/),[Document](https://dx.doi.org/10.18653/v1/2024.naacl-srw.3)Cited by:[§1](https://arxiv.org/html/2609.19465#S1.p2.1),[§1](https://arxiv.org/html/2609.19465#S1.p3.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px1.p1.1)\.
- \[24\]J\. Ye, Z\. Yao, Z\. Huang, L\. Pan, J\. Liu, Y\. Bai, A\. Xin, L\. Weichuan, X\. Che, L\. Hou, and J\. Li\(2025\)How do transformers learn implicit reasoning?\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=19ygs48nOa)Cited by:[Appendix A](https://arxiv.org/html/2609.19465#A1.p1.1),[§1](https://arxiv.org/html/2609.19465#S1.p3.1)\.
- \[25\]F\. Yin, Z\. L\. Liu, L\. Leqi, X\. Ye, and G\. Durrett\(2025\)Learning composable chains\-of\-thought\.arXiv preprint arXiv:2505\.22635\.Cited by:[§1](https://arxiv.org/html/2609.19465#S1.p3.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px1.p1.1)\.
- \[26\]D\. Yu, S\. Kaur, A\. Gupta, J\. Brown\-Cohen, A\. Goyal, and S\. Arora\(2024\)SKILL\-MIX: a flexible and expandable family of evaluations for AI models\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=Jf5gplvglq)Cited by:[§1](https://arxiv.org/html/2609.19465#S1.p2.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px1.p1.1)\.
- \[27\]L\. Yuan, W\. Chen, Y\. Zhang, G\. Cui, H\. Wang, Z\. You, N\. Ding, Z\. Liu, M\. Sun, and H\. Peng\(2025\)Fromf⁡\(x\)f\(x\)andg⁡\(x\)g\(x\)tof⁡\(g⁡\(x\)\)f\(g\(x\)\): llms learn new skills in rl by composing old ones\.arXiv preprint arXiv:2509\.25123\.Cited by:[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px2.p1.1)\.
- \[28\]Y\. Yue, Z\. Chen, R\. Lu, A\. Zhao, Z\. Wang, Y\. Yue, S\. Song, and G\. Huang\(2026\)Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model?\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=4OsgYD7em5)Cited by:[§1](https://arxiv.org/html/2609.19465#S1.p3.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px2.p1.1)\.
- \[29\]H\. Zhao, S\. Kaur, D\. Yu, A\. Goyal, and S\. Arora\(2024\)Can models learn skill composition from examples?\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=1sLdprsbmk)Cited by:[§1](https://arxiv.org/html/2609.19465#S1.p2.1),[§1](https://arxiv.org/html/2609.19465#S1.p3.1),[§2](https://arxiv.org/html/2609.19465#S2.SS0.SSS0.Px1.p1.1)\.

## Appendix

### Table of Contents

### Appendix AAdditional related work

A line of work studies when and why compositional generalization emerges\.[Redhardt et al\. \[18\]](https://arxiv.org/html/2609.19465#bib.bib5)show that, with sufficient coverage, scaling data and model size can induce generalization to unseen task compositions, and provide theoretical results for modular task families\.[Ahuja and Mansouri \[1\]](https://arxiv.org/html/2609.19465#bib.bib9)give guarantees for length and compositional generalization under sufficient training diversity\. In controlled synthetic settings,[Ramesh et al\. \[17\]](https://arxiv.org/html/2609.19465#bib.bib10)show that autoregressive transformers can generalize to many unseen compositions, while[Chang et al\. \[2\]](https://arxiv.org/html/2609.19465#bib.bib7)characterize the limits of pattern matching on compositional task structures and show that coverage alone is not always sufficient\. In symbolic reasoning,[Ye et al\. \[24\]](https://arxiv.org/html/2609.19465#bib.bib6)study multi\-hop generalization and find that atomic supervision mainly accelerates learning rather than determining it\. However, these analyses are developed largely in supervised or tightly controlled settings, and do not directly address how post\-training changes compositional reasoning in modern language models\.

### Appendix BOmitted Proofs

In this section, we provide omitted proofs and details from Section[5](https://arxiv.org/html/2609.19465#S5)of the paper\.

#### B\.1Omitted Proofs from Section[5\.1](https://arxiv.org/html/2609.19465#S5.SS1)

The key challenge in transferring from decomposed skills to composed tasks is that solving a compound task requires the trained policy to remain correct over a serialized rollout of the task dependency graph\. Even if each individual skill invocation is easy under the atomic training distribution, errors can accumulate over the reasoning trace, and the compound rollout may visit intermediate states that are rare under atomic supervision\.

##### Formal rollout model\.

Fix a horizonTTand letρT\\rho\_\{T\}be a distribution over compound task instances whose dependency graphs have\|Vτ\|=T\|V\_\{\\tau\}\|=T\. A task instanceτ∼ρT\\tau\\sim\\rho\_\{T\}is random, whileTTis fixed throughout this subsection\. As in Section[3](https://arxiv.org/html/2609.19465#S3), write

Gτ=\(Vτ,Eτ\)G\_\{\\tau\}=\(V\_\{\\tau\},E\_\{\\tau\}\)for the dependency graph ofτ\\tau\. Each nodev∈Vτv\\in V\_\{\\tau\}is labeled by a skill typeκ⁡\(v\)\\kappa\(v\)and local informationℓv\\ell\_\{v\}\. Its input and correct output at a rollout state are defined below\.

We write

pred⁡\(v\)=\{u∈Vτ:\(u,v\)∈Eτ\}\\mathrm\{pred\}\(v\)=\\\{u\\in V\_\{\\tau\}:\(u,v\)\\in E\_\{\\tau\}\\\}for the predecessors ofvv, and assume a unique sink nodevsinkv\_\{\\mathrm\{sink\}\}whose output is the final task output\.

Let𝒮\\mathcal\{S\}be a countable rollout\-state space\. A states∈𝒮s\\in\\mathcal\{S\}contains the task instanceτ\\tau, the completed\-node set

P⁡\(s\)⊆Vτ,P\(s\)\\subseteq V\_\{\\tau\},and the intermediate outputs produced so far, written as\{zu​\(s\):u∈P⁡\(s\)\}\\\{z\_\{u\}\(s\):u\\in P\(s\)\\\}\. Thus the state contains all task\-relevant context needed to determine which skill invocations are available next and what their correct outputs are\. The nodes that are ready to execute at statessare

R⁡\(s\)=\{v∈Vτ∖P⁡\(s\):pred⁡\(v\)⊆P⁡\(s\)\}\.R\(s\)=\\\{v\\in V\_\{\\tau\}\\setminus P\(s\):\\mathrm\{pred\}\(v\)\\subseteq P\(s\)\\\}\.For each ready nodev∈R⁡\(s\)v\\in R\(s\), its input is formed from the task\-local information and predecessor outputs by

xv​\(s\)=ψv​\(ℓv,\(zu​\(s\)\)u∈pred⁡\(v\)\)∈𝒳κ⁡\(v\),x\_\{v\}\(s\)=\\psi\_\{v\}\\\!\\left\(\\ell\_\{v\},\\left\(z\_\{u\}\(s\)\\right\)\_\{u\\in\\mathrm\{pred\}\(v\)\}\\right\)\\in\\mathcal\{X\}\_\{\\kappa\(v\)\},and its correct output is

zv∗​\(s\)=fκ⁡\(v\)​\(xv​\(s\)\)\.z^\{\*\}\_\{v\}\(s\)=f\_\{\\kappa\(v\)\}\(x\_\{v\}\(s\)\)\.

##### Decision context\.

A correct next step need not be unique, since a branch–merge graph may admit multiple valid topological orderings\. Moreover, whether a step is correct does not depend on the name of the node being executed, but only on the skill type invoked and the input it receives\. Therefore, for each state, we can define a decision context

Q⁡\(s\)=\{\(κ⁡\(v\),xv​\(s\)\):v∈R⁡\(s\)\},\\displaystyle Q\(s\)=\\\{\(\\kappa\(v\),x\_\{v\}\(s\)\):v\\in R\(s\)\\\},which is the set of skill\-input pairs available at statess\. We then define the set of valid next invocation\-output pairs by

ℐ∗​\(s\)=\{\(\(κ,x\),fκ​\(x\)\):\(κ,x\)∈Q⁡\(s\)\}\.\\mathcal\{I\}^\{\*\}\(s\)=\\\{\(\(\\kappa,x\),f\_\{\\kappa\}\(x\)\):\(\\kappa,x\)\\in Q\(s\)\\\}\.By construction,ℐ∗​\(s\)\\mathcal\{I\}^\{\*\}\(s\)is determined byQ⁡\(s\)Q\(s\)only\. Therefore, we writeℐ∗​\(c\)\\mathcal\{I\}^\{\*\}\(c\)for a decision contextcc\. Since𝒮\\mathcal\{S\}is countable, the set of decision contexts\{Q⁡\(s\):s∈𝒮\}\\\{Q\(s\):s\\in\\mathcal\{S\}\\\}is also countable\.

A rollout policyπ^\\hat\{\\pi\}maps a statessto a parsed invocation\-output pair, consisting of the skill invocation it performs, identified by its skill type and input rather than by a node name, together with the output it produces\. Whenπ^​\(s\)=\(\(κ,x\),z\)∈ℐ∗​\(s\)\\hat\{\\pi\}\(s\)=\(\(\\kappa,x\),z\)\\in\\mathcal\{I\}^\{\*\}\(s\), the rollout completes a ready node whose skill type is isκ\\kappaand input isxx, and records the correct outputz=fκ​\(x\)z=f\_\{\\kappa\}\(x\)\. If several ready nodes have the same skill type and input, a fixed deterministic tie\-breaking rule determines which one is completed, in accordance with our empirical deterministic tie\-breaking rule in Appendix[C\.3](https://arxiv.org/html/2609.19465#A3.SS3)\. Note that when simultaneously ready nodes induce at least two distinct skill\-input pairs,Q⁡\(s\)Q\(s\)is non\-singleton\. For stochastic policies, all probabilities and expectations below are also over the policy randomness\. We assume that, conditioned on the current rollout statess, the policy’s current randomization is independent of the previous rollout history\. Equivalently, any policy\-internal memory or persistent random seed that can affect future outputs is included as part of the rollout state\. Under this assumption, the stepwise error probability,

eπ^\(s\)=Prπ^\[π^\(s\)∉ℐ∗\(s\)\],\\displaystyle e\_\{\\hat\{\\pi\}\}\(s\)=\\Pr\_\{\\hat\{\\pi\}\}\[\\hat\{\\pi\}\(s\)\\notin\\mathcal\{I\}^\{\*\}\(s\)\],is a well\-defined function of statess\. For a deterministic policy, the error probability is either 0 or 1, soeπ^\(s\)=𝟙\{π^\(s\)∉ℐ∗\(s\)\}e\_\{\\hat\{\\pi\}\}\(s\)=\\mathbbm\{1\}\\\{\\hat\{\\pi\}\(s\)\\notin\\mathcal\{I\}^\{\*\}\(s\)\\\}\.

##### Context Invariance\.

We assume that the stepwise error probability depends on the state only through the decision context, i\.e\.,

Q⁡\(s\)=Q⁡\(s′\)⇒eπ^​\(s\)=eπ^​\(s′\),\\displaystyle Q\(s\)=Q\(s^\{\\prime\}\)\\Rightarrow e\_\{\\hat\{\\pi\}\}\(s\)=e\_\{\\hat\{\\pi\}\}\(s^\{\\prime\}\),and we writeeπ^​\(c\)e\_\{\\hat\{\\pi\}\}\(c\)for the stepwise error probability of a decision contextcc\. This is because our transfer bound compares the policy on rollout distribution with the policy on atomic tasks, and this hypothesis is required to connect the two\. By construction, the valid next\-step set depends on the state only through its decision context:Q⁡\(s\)=Q⁡\(s′\)Q\(s\)=Q\(s^\{\\prime\}\)impliesℐ∗​\(s\)=ℐ∗​\(s′\)\\mathcal\{I\}^\{\*\}\(s\)=\\mathcal\{I\}^\{\*\}\(s^\{\\prime\}\)\. Thus, context invariance imposes no additional assumption on task correctness; it assumes only that the policy assigns the same total probability to invalid outputs at states with the same decision context\. This assumption removes possible additional errors caused by embedding an invocation in a compound prompt, so the resulting transfer guarantee is optimistic\.

##### Failure and mistake\.

Matching the main text, we writests\_\{t\}for the rollout state at timesteptt; althoughsts\_\{t\}is induced by the sampled taskτ\\tau, we do not attach an additionalτ\\tausuperscript\. The rollout starts from the initial states1s\_\{1\}, whereP⁡\(s1\)=∅P\(s\_\{1\}\)=\\emptyset, and then updates the completed\-node set and intermediate outputs according to the parsed pair emitted byπ^\\hat\{\\pi\}\. Whenπ^​\(st\)∈ℐ∗​\(st\)\\hat\{\\pi\}\(s\_\{t\}\)\\in\\mathcal\{I\}^\{\*\}\(s\_\{t\}\), the rollout completes one ready node with its correct output; otherwise, the next state may be arbitrary, but the step is counted as a mistake\.

LetFFdenote the final\-failure indicator:

F=𝟙​\{the rollout does not produce the correct sink\-node output​zvsink\}\.F=\\mathbbm\{1\}\\\{\\text\{the rollout does not produce the correct sink\-node output \}z\_\{v\_\{\\mathrm\{sink\}\}\}\\\}\.Equivalently, if the terminal rollout state stores the outputs produced by the serialized rollout, missing or incorrect sink\-node output is counted as failure\.

A mistake at stepttis the event

π^​\(st\)∉ℐ∗​\(st\)\.\\hat\{\\pi\}\(s\_\{t\}\)\\notin\\mathcal\{I\}^\{\*\}\(s\_\{t\}\)\.Define the indicator of the first mistake made at stepttby

Mt=\{π^\(si\)∈ℐ∗\(si\)for alli<t,π^\(st\)∉ℐ∗\(st\)\}\.M\_\{t\}=\\mathbbm\{1\}\\\!\\left\\\{\\hat\{\\pi\}\(s\_\{i\}\)\\in\\mathcal\{I\}^\{\*\}\(s\_\{i\}\)\\ \\text\{for all \}i<t,\\quad\\hat\{\\pi\}\(s\_\{t\}\)\\notin\\mathcal\{I\}^\{\*\}\(s\_\{t\}\)\\right\\\}\.If no mistake occurs fort=1,…,Tt=1,\\ldots,T, then the rollout completes all nodes in a valid topological order and every completed node has the correct output\. In particular, the sink\-node output iszvsinkz\_\{v\_\{\\mathrm\{sink\}\}\}, soF=0F=0\. HenceF=1F=1implies thatMt=1M\_\{t\}=1for at least onett\.

Letqqbe the distribution over decision contexts induced by atomic task training data\. Sample an atomic\-task statessand recordQ⁡\(s\)Q\(s\)\. Define

ϵatom​\(π^,q\)=𝔼c∼q​\[eπ^​\(c\)\]=∑cq⁡\(c\)​eπ^​\(c\)\.\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)=\\mathbb\{E\}\_\{c\\sim q\}\\left\[e\_\{\\hat\{\\pi\}\}\(c\)\\right\]=\\sum\_\{c\}q\(c\)e\_\{\\hat\{\\pi\}\}\(c\)\.
Whenqqis clear from context, we writeϵatom​\(π^\)\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\}\)\. An atomic task instance has a single\-node dependency graph, so its decision context is a singleton\{\(κ,x\)\}\\\{\(\\kappa,x\)\\\}, andqqis supported on singleton contexts\. A compound rollout context can therefore be covered byqqonly if it is the same singleton and has positiveqq\-mass\. This singleton condition holds structurally along Level I and Level II paths, but may fail in Level III when several distinct invocations are simultaneously available\. We compare atomic and compound behavior at the level of decision contexts because this captures their possible overlap; it does not assume that every compound decision context has an atomic analogue\.

We demonstrate the notation above with a concrete example\.

###### Example B\.1\(BST construction\)\.

Consider the following prompt:

> You are given an initially empty binary search tree\. Execute the following operations in order: 1\. insert 5 2\. insert 2 3\. insert 8 4\. delete 2 5\. insert 3 Use \[\] for an empty child and \[v,L,R\] for a nonempty node with value v, left subtree L, and right subtree R\. Return only the final tree\.

This prompt is a task instanceτ\\tauwith horizonT=5T=5\. Its dependency graph is a pathv1→v2→v3→v4→v5v\_\{1\}\\to v\_\{2\}\\to v\_\{3\}\\to v\_\{4\}\\to v\_\{5\}, where each node is one BST skill invocation\. The local informationℓvi\\ell\_\{v\_\{i\}\}specifies the instructed operation, such asinsert 5forv1v\_\{1\}anddelete 2forv4v\_\{4\}\. The sink node isvsink=v5v\_\{\\mathrm\{sink\}\}=v\_\{5\}, and the correct sink\-node output is

zvsink=\[5,\[3,\[\],\[\]\],\[8,\[\],\[\]\]\]\.z\_\{v\_\{\\mathrm\{sink\}\}\}=\[5,\[3,\[\],\[\]\],\[8,\[\],\[\]\]\]\.
LetBtB\_\{t\}denote the BST after the firstt−1t\-1invocations have been correctly executed\. Along the correct rollout,

B1=\[\],B2=\[5,\[\],\[\]\],B3=\[5,\[2,\[\],\[\]\],\[\]\],B4=\[5,\[2,\[\],\[\]\],\[8,\[\],\[\]\]\],B\_\{1\}=\[\],\\quad B\_\{2\}=\[5,\[\],\[\]\],\\quad B\_\{3\}=\[5,\[2,\[\],\[\]\],\[\]\],\\quad B\_\{4\}=\[5,\[2,\[\],\[\]\],\[8,\[\],\[\]\]\],B5=\[5,\[\],\[8,\[\],\[\]\]\],B6=\[5,\[3,\[\],\[\]\],\[8,\[\],\[\]\]\]\.B\_\{5\}=\[5,\[\],\[8,\[\],\[\]\]\],\\quad B\_\{6\}=\[5,\[3,\[\],\[\]\],\[8,\[\],\[\]\]\]\.At timesteptt, the rollout state can be represented as

st=\(τ,\{v1,…,vt−1\},\{zvi=Bi\+1:i<t\}\)\.s\_\{t\}=\\left\(\\tau,\\\{v\_\{1\},\\ldots,v\_\{t\-1\}\\\},\\\{z\_\{v\_\{i\}\}=B\_\{i\+1\}:i<t\\\}\\right\)\.Because the graph is a path, the ready\-node set is a singleton at every nonterminal correct state:R⁡\(st\)=\{vt\}R\(s\_\{t\}\)=\\\{v\_\{t\}\\\}\. For example, at step44,

P⁡\(s4\)=\{v1,v2,v3\},R⁡\(s4\)=\{v4\}\.P\(s\_\{4\}\)=\\\{v\_\{1\},v\_\{2\},v\_\{3\}\\\},\\qquad R\(s\_\{4\}\)=\\\{v\_\{4\}\\\}\.so the decision context and the valid next invocation\-output set are the singletons

Q⁡\(s4\)=\{\(delete,\(B4,2\)\)\},ℐ∗​\(s4\)=\{\(\(delete,\(B4,2\)\),B5\)\}\.Q\(s\_\{4\}\)=\\left\\\{\\left\(\\texttt\{delete\},\(B\_\{4\},2\)\\right\)\\right\\\},\\qquad\\mathcal\{I\}^\{\*\}\(s\_\{4\}\)=\\left\\\{\\left\(\\left\(\\texttt\{delete\},\(B\_\{4\},2\)\\right\),B\_\{5\}\\right\)\\right\\\}\.If the model invokes the available skill\-input pair but returns an incorrect intermediate BST, or proposes a skill\-input pair not inQ⁡\(s4\)Q\(s\_\{4\}\), such as insert 3 before delete 2 is performed, then its invocation\-output pair does not belong toℐ∗​\(s4\)\\mathcal\{I\}^\{\*\}\(s\_\{4\}\)\.

The atomic task instance “given the treeB4B\_\{4\}, delete22” has the same decision contextQ⁡\(s4\)Q\(s\_\{4\}\), even though its dependency graph has one node while that ofτ\\tauhas five\. Decision contexts are exactly the level of description at which an atomic training example and a step of a compound rollout can coincide\.

Lemma[5\.1](https://arxiv.org/html/2609.19465#S5.Thmtheorem1)shows that generalizing from atomic to compound tasks depends on both the atomic error onqqand the mismatch betweenqqand the decision contexts visited along mistake\-free compound rollouts\.

###### Lemma[5\.1](https://arxiv.org/html/2609.19465#S5.Thmtheorem1)\.

Assumeπ^\\hat\{\\pi\}is context\-invariant\. For each steptt, letμt\\mu\_\{t\}be the conditional distribution of the decision contextQ⁡\(st\)Q\(s\_\{t\}\)given no mistakes before steptt:

μt​\(A\)=Pr⁡\[Q⁡\(st\)∈A∣M1=⋯=Mt−1=0\]fora setAof decision contexts\.\\mu\_\{t\}\(A\)=\\Pr\[Q\(s\_\{t\}\)\\in A\\mid M\_\{1\}=\\cdots=M\_\{t\-1\}=0\]\\qquad\\text\{for \}\\text\{a set $A$ of decision contexts\}\.Assume thatq⁡\(c\)=0⇒μt​\(c\)=0q\(c\)=0\\Rightarrow\\mu\_\{t\}\(c\)=0for everyt∈\[T\]t\\in\[T\]and every decision contextcc, i\.e\., any decision context that can occur at timestepttof a correct compound rollout has nonzero probability under the atomic training\-state distributionqq\. Define the cumulative coverage factor

CT\(q\)=supc:q⁡\(c\)\>0∑t=1Tμt\(c\)q\(c\)\.C\_\{T\}\(q\)=\\sup\_\{c:q\(c\)\>0\}\\frac\{\\sum\_\{t=1\}^\{T\}\}\{\\mu\}\_\{t\}\(c\)\{q\(c\)\}\.AssumeCT​\(q\)<∞C\_\{T\}\(q\)<\\infty\. Then, forτ∼ρT\\tau\\sim\\rho\_\{T\}, the probability of final failure satisfies

Pr\[F=1\]≤CT\(q\)ϵatom\(π^;q\)\.\\Pr\[F=1\]\\leq C\_\{T\}\(q\)\\,\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)\.This bound is tight in the worst case, as shown by Proposition[B\.2](https://arxiv.org/html/2609.19465#A2.Thmtheorem2)\.

###### Proof\.

For eachtt, define the conditional step\-error probability

δt​\(π^\)=Pr⁡\[π^​\(st\)∉ℐ∗​\(st\)∣M1=⋯=Mt−1=0\]\.\\delta\_\{t\}\(\\hat\{\\pi\}\)=\\Pr\[\\hat\{\\pi\}\(s\_\{t\}\)\\notin\\mathcal\{I\}^\{\*\}\(s\_\{t\}\)\\mid M\_\{1\}=\\cdots=M\_\{t\-1\}=0\]\.As argued above, if the final output is incorrect, then at least one first mistake must have occurred\. Hence

Pr\[F=1\]≤∑t=1TPr\[Mt=1\]=∑t=1TPr\[M1=⋯=Mt−1=0\]δt\(π^\)≤∑t=1Tδt\(π^\)\.\\Pr\[F=1\]\\leq\\sum\_\{t=1\}^\{T\}\\Pr\[M\_\{t\}=1\]=\\sum\_\{t=1\}^\{T\}\\Pr\[M\_\{1\}=\\cdots=M\_\{t\-1\}=0\]\\,\\delta\_\{t\}\(\\hat\{\\pi\}\)\\leq\\sum\_\{t=1\}^\{T\}\\delta\_\{t\}\(\\hat\{\\pi\}\)\.
Fixtt\. Conditioned on the rollout statest=ss\_\{t\}=s, the policy makes a mistake with probabilityeπ^​\(s\)e\_\{\\hat\{\\pi\}\}\(s\), which by context invariance equalseπ^​\(Q​\(s\)\)e\_\{\\hat\{\\pi\}\}\(Q\(s\)\)\. Conditioning instead on the decision context and using that the set of decision contexts is countable,

δt​\(π^\)=∑cμt​\(c\)​eπ^​\(c\)\.\\delta\_\{t\}\(\\hat\{\\pi\}\)=\\sum\_\{c\}\\mu\_\{t\}\(c\)\\,e\_\{\\hat\{\\pi\}\}\(c\)\.Summing overttand using the coverage assumption, which allows us to restrict the sum to contexts withq⁡\(c\)\>0q\(c\)\>0,

∑t=1Tδt​\(π^\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\delta\_\{t\}\(\\hat\{\\pi\}\)=∑c\(∑t=1Tμt\(c\)\)eπ^\(c\)=∑c:q⁡\(c\)\>0∑t=1Tμt​\(c\)q⁡\(c\)q\(c\)eπ^\(c\)\\displaystyle=\\sum\_\{c\}\\left\(\\sum\_\{t=1\}^\{T\}\\mu\_\{t\}\(c\)\\right\)e\_\{\\hat\{\\pi\}\}\(c\)=\\sum\_\{c:q\(c\)\>0\}\\frac\{\\sum\_\{t=1\}^\{T\}\\mu\_\{t\}\(c\)\}\{q\(c\)\}\\,q\(c\)\\,e\_\{\\hat\{\\pi\}\}\(c\)≤CT​\(q\)​∑cq⁡\(c\)​eπ^​\(c\)=CT​\(q\)​ϵatom​\(π^,q\)\.\\displaystyle\\leq C\_\{T\}\(q\)\\sum\_\{c\}q\(c\)\\,e\_\{\\hat\{\\pi\}\}\(c\)=C\_\{T\}\(q\)\\,\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)\.Combining the preceding inequalities proves the claim\.

∎

Lemma[5\.1](https://arxiv.org/html/2609.19465#S5.Thmtheorem1)shows that transferring from atomic supervision to compound tasks depends on two quantities: the atomic errorϵatom​\(π^,q\)\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)and the coverage factorCT​\(q\)C\_\{T\}\(q\), which measure the mismatch between the atomic training\-state distribution and the rollout state distribution\. This guarantee is not horizon\-free: the horizon dependence is absorbed into the coverage factorsCT​\(q\)C\_\{T\}\(q\)\.

Indeed, supposePr\[M1=⋯=Mt−1=0\]\>0\\Pr\[M\_\{1\}=\\dots=M\_\{t\-1\}=0\]\>0for everyt∈\[T\]t\\in\[T\], so that eachμt\\mu\_\{t\}is a probability distribution and∑c∑t=1Tμt​\(c\)=T\\sum\_\{c\}\\sum\_\{t=1\}^\{T\}\\mu\_\{t\}\(c\)=T\. Restricting to contexts withq⁡\(c\)\>0q\(c\)\>0, which the coverage assumption permits,

T=∑c:q⁡\(c\)\>0∑t=1Tμt​\(c\)q⁡\(c\)q\(c\)≤CT\(q\)∑c:q⁡\(c\)\>0q\(c\)=CT\(q\)\.T=\\sum\_\{c:q\(c\)\>0\}\\frac\{\\sum\_\{t=1\}^\{T\}\\mu\_\{t\}\(c\)\}\{q\(c\)\}\\,q\(c\)\\leq C\_\{T\}\(q\)\\sum\_\{c:q\(c\)\>0\}q\(c\)=C\_\{T\}\(q\)\.SoCT​\(q\)≥TC\_\{T\}\(q\)\\geq Talways, with equality exactly when atomic supervision matches the visitation frequencies of the compound rollout, i\.e\.∑tμt=T​q\\sum\_\{t\}\\mu\_\{t\}=Tq\. In particular, even perfectly matched coverage still pays a factorTT, recovering theT​ϵatomT\\epsilon\_\{\\mathrm\{atom\}\}\-scaling; poorer coverage further amplifies failure risk\. Note that the coverage assumption assumes atomic supervision is capable of producing the contexts a compound rollout visits\. This holds for path\-structured graphs, where\|R⁡\(st\)\|=1\|R\(s\_\{t\}\)\|=1along a correct rollout so every visited context is a singleton, but not in general; we return to this point in the discussion of Level III below\.

The following proposition shows that this horizon dependence is unavoidable even in a path\-structured, unique\-valid\-invocation setting\.

###### Proposition B\.2\(No horizon\-free transfer bound\)\.

For everyT≥1T\\geq 1, there exist a compound task distributionρT\\rho\_\{T\}, a countable state space𝒮\\mathcal\{S\}, an atomic training distributionqqover decision contexts, and a context\-invariant policyπ^\\hat\{\\pi\}such that each non\-terminal state on the mistake\-free rollout has a singleton valid next invocation\-output set, yet

ϵatom\(π^;q\)=1T,Pr\[F=1\]=1\.\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)=\\frac\{1\}\{T\},\\qquad\\Pr\[F=1\]=1\.Consequently, no bound of the form

Pr\[F=1\]≤g\(ϵatom\(π^;q\)\)\\Pr\[F=1\]\\leq g\\\!\\left\(\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)\\right\)withg⁡\(ϵ\)→0g\(\\epsilon\)\\to 0asϵ→0\\epsilon\\to 0can hold uniformly over all horizonsTTand all compound task distributions\.

###### Proof\.

LetρT\\rho\_\{T\}be the point mass on the following single\-skill chain: starting from the empty list, insert the values1,2,…,T1,2,\\ldots,Tin this order\. Its dependency graph is a path of lengthTT, so the ready\-node set is a singleton at every nonterminal correct state, and the correct output of each invocation is unique\. Along the correct rollout, the decision context at stepttis the singleton

ct=\{\(insert,\(\[1,…,t−1\],t\)\)\},c\_\{t\}=\\left\\\{\\left\(\\texttt\{insert\},\\left\(\[1,\\ldots,t\-1\],t\\right\)\\right\)\\right\\\},andc1,…,cTc\_\{1\},\\ldots,c\_\{T\}are pairwise distinct because their inputs are\. Eachctc\_\{t\}is also the decision context of an atomic task instance, namely the single invocationinsertttapplied to the list\[1,…,t−1\]\[1,\\ldots,t\-1\], so the uniform distributionqqover\{c1,…,cT\}\\\{c\_\{1\},\\ldots,c\_\{T\}\\\}is realizable as an atomic training distribution\.

Letπ^\\hat\{\\pi\}be the deterministic policy, defined on decision contexts and hence context\-invariant, that returns the valid pair onc1,…,cT−1c\_\{1\},\\ldots,c\_\{T\-1\}and a pair outsideℐ∗​\(cT\)\\mathcal\{I\}^\{\*\}\(c\_\{T\}\)oncTc\_\{T\}\. As the rollout model permits, let a mistake send the rollout to a state from which the correct sink\-node output is never produced\. Thenπ^\\hat\{\\pi\}errs on exactly one of theTTcontexts in the support ofqq, so

ϵatom​\(π^,q\)=1T\.\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)=\\frac\{1\}\{T\}\.However, the compound rollout makes no mistake at steps1,…,T−11,\\ldots,T\-1and therefore visitsc1,c2,…,cTc\_\{1\},c\_\{2\},\\ldots,c\_\{T\}in order, necessarily making a mistake at stepTT\. Thus, the rollout fails to produce the correct sink\-node output, so

∎

In this construction,μt\\mu\_\{t\}is the point mass onctc\_\{t\}, so∑t=1Tμt​\(cj\)=1\\sum\_\{t=1\}^\{T\}\\mu\_\{t\}\(c\_\{j\}\)=1for anyj∈\[T\]j\\in\[T\], whileq⁡\(cj\)=1/Tq\(c\_\{j\}\)=1/T; henceCT​\(q\)=TC\_\{T\}\(q\)=Tand the bound of Lemma[5\.1](https://arxiv.org/html/2609.19465#S5.Thmtheorem1)evaluates toT⋅1T=1=Pr\[F=1\]T\\cdot\\frac\{1\}\{T\}=1=\\Pr\[F=1\]\. Thus Lemma[5\.1](https://arxiv.org/html/2609.19465#S5.Thmtheorem1)is tight in the worst case\.

##### Connection with the compositionality levels\.

Lemma[5\.1](https://arxiv.org/html/2609.19465#S5.Thmtheorem1)explains how the difficulty of composing atomic tasks changes across our three levels of compositionality\.

- •Level I \(Single\-skill chain\): In this case,GτG\_\{\\tau\}is a path, and all nodes share the same skill type, so the main challenge is the rollout horizonT=\|Vτ\|T=\|V\_\{\\tau\}\|\(depth generalization\)\. Even without skill switches or merges, a length\-TTrollout incursTTcontext visits\. The cumulative factor counts all of these visits, including repeated visits to the same context, and therefore satisfiesCT​\(q\)≥TC\_\{T\}\(q\)\\geq Tunder the stated conditions, with equality only under perfectly matched coverage\. For the natural uniform mixture over visited contexts, this recovers the familiarT​ϵatomT\\epsilon\_\{\\mathrm\{atom\}\}\-type scaling\.
- •Level II \(Multi\-skill chain\): In this case, the skill invoked at each nodev∈Vτv\\in V\_\{\\tau\}, namelyκ⁡\(v\)\\kappa\(v\), varies across nodes\. The model must therefore not only remain correct over a long horizon, but also execute different skills in sequence and propagate intermediate outputs across skill switches\. Even if each skill is well covered in isolation by atomic supervision, the compound rollout distribution near a skill switch may assign mass to contexts in which one skill is applied to an input produced by a different skill, and such cross\-skill contexts may receive little mass under the atomic training distributionqq, increasingCT​\(q\)C\_\{T\}\(q\)\. This matches our experimental results in Figure[6](https://arxiv.org/html/2609.19465#S4.F6): as the number of skill switches increases, the task becomes more difficult for the model\.
- •Level III \(Branch\-merge graph\): In this case,GτG\_\{\\tau\}is a branch–merge graph, and two effects arise that have no counterpart in Levels I and II\. First, whenever simultaneously ready branches induce at least two distinct skill\-input pairs,Q⁡\(st\)Q\(s\_\{t\}\)contains more than one invocation\. The model must also choose which of them to execute next, a decision with no atomic analogue\. Since an atomic task instance has a single\-node dependency graph, its decision context is a singleton, so every such multi\-invocation context lies outside the support of any atomic training distributionqq\. The coverage assumption of Lemma[5\.1](https://arxiv.org/html/2609.19465#S5.Thmtheorem1)then fails unless the training distribution is enlarged beyond single\-node atomic tasks to include multi\-invocation choice contexts\. Second, a merge invocation is a single skill applied to a tuple of outputs from different branches, and so is atomically realizable, but the contexts that matter are those in which the tuple was produced by two separately executed branches; if atomic supervision covers merge invocations only on tuples from short or isolated branches, those contexts receive little mass andCT​\(q\)C\_\{T\}\(q\)is large\. Both effects are consistent with the collapse of RL\-Atomic on Level III compound tasks\.

#### B\.2Omitted Proofs from Section[5\.2](https://arxiv.org/html/2609.19465#S5.SS2)

The previous subsection shows that atomic\-to\-compound transfer is difficult because errors can accumulate over a multi\-step rollout\. The reverse direction does not have the same horizon dependence: an error at the first step of a compound rollout is already an error on a single skill invocation\.

LetρT\\rho\_\{T\}denote a distribution over compound task instances with horizonTT\. Forτ∼ρT\\tau\\sim\\rho\_\{T\}, lets1s\_\{1\}be its initial rollout state\. Define the compound\-task error by

ϵcomp​\(π^,ρT\)=𝔼τ∼ρT,π^​\[F\],\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\\rho\_\{T\}\)=\\mathbb\{E\}\_\{\\tau\\sim\\rho\_\{T\},\\hat\{\\pi\}\}\[F\],and define the first\-step error induced byρT\\rho\_\{T\}as

ϵatom\(1\)\(π^;ρT\)=Prτ∼ρT,π^\[π^\(s1\)∉ℐ∗\(s1\)\]\.\\epsilon\_\{\\mathrm\{atom\}\}^\{\(1\)\}\(\\hat\{\\pi\};\\rho\_\{T\}\)=\\Pr\_\{\\tau\\sim\\rho\_\{T\},\\hat\{\\pi\}\}\\left\[\\hat\{\\pi\}\(s\_\{1\}\)\\notin\\mathcal\{I\}^\{\*\}\(s\_\{1\}\)\\right\]\.To interpret this first\-step error as an error with atomic context, we assume that every compound task in the support ofρT\\rho\_\{T\}has a unique source node\. Since the completed\-node setP⁡\(s1\)=∅P\(s\_\{1\}\)=\\emptyset, the ready node setR⁡\(s1\)R\(s\_\{1\}\)contains exactly one node, and the decision contextQ⁡\(s1\)Q\(s\_\{1\}\)is a singleton decision context\.

###### Proposition B\.3\(First\-step compound\-to\-atomic transfer\)\.

Assume that a first\-step mistake necessarily prevents successful completion of the compound task, i\.e\., for every task instanceτ\\tauand every realization of the policy randomness,

π^​\(s1\)∉ℐ∗​\(s1\)⟹F=1\.\\hat\{\\pi\}\(s\_\{1\}\)\\notin\\mathcal\{I\}^\{\*\}\(s\_\{1\}\)\\quad\\Longrightarrow\\quad F=1\.Then

ϵatom\(1\)​\(π^,ρT\)≤ϵcomp​\(π^,ρT\)\.\\epsilon\_\{\\mathrm\{atom\}\}^\{\(1\)\}\(\\hat\{\\pi\};\\rho\_\{T\}\)\\leq\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\\rho\_\{T\}\)\.

###### Proof\.

Recall thatM1=𝟙\{π^\(s1\)∉ℐ∗\(s1\)\}M\_\{1\}=\\mathbbm\{1\}\\left\\\{\\hat\{\\pi\}\(s\_\{1\}\)\\notin\\mathcal\{I\}^\{\*\}\(s\_\{1\}\)\\right\\\}is the indicator of whether the model makes mistake on the first step\. By the non\-recoverable mistake assumption,M1≤FM\_\{1\}\\leq Ffor every task instance and every realization of the policy randomness\. Taking the expectation gives𝔼⁡\[M1\]≤𝔼⁡\[F\]\\mathbb\{E\}\[M\_\{1\}\]\\leq\\mathbb\{E\}\[F\], and notice that the left\-hand side isϵatom\(1\)​\(π^,ρT\)\\epsilon\_\{\\mathrm\{atom\}\}^\{\(1\)\}\(\\hat\{\\pi\};\\rho\_\{T\}\)and the right\-hand side isϵcomp​\(π^,ρT\)\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\\rho\_\{T\}\)\. ∎

Proposition[B\.3](https://arxiv.org/html/2609.19465#A2.Thmtheorem3)compares two events within the same compound rollout, so no coverage assumption or context invariance assumption is required here\.

##### Transfer to a separate atomic distribution\.

Even when an atomic task and the first step of a compound task require the same skill on the same input, their full rollout states differ because each state records the entire task instance\. We therefore compare them through their decision contexts\.

Define the first\-step decision\-context distribution induced by compound tasks as

q1ρT\(c\)=Prτ∼ρT\[Q\(s1\)=c\]\.q\_\{1\}^\{\\rho\_\{T\}\}\(c\)=\\Pr\_\{\\tau\\sim\\rho\_\{T\}\}\\left\[Q\(s\_\{1\}\)=c\\right\]\.Because every task has a unique source node,q1ρTq\_\{1\}^\{\\rho\_\{T\}\}is supported on singleton decision context\.

Assume thatπ^\\hat\{\\pi\}is context invariant\. Then the first\-step error can be written as

ϵatom\(1\)​\(π^,ρT\)\\displaystyle\\epsilon\_\{\\mathrm\{atom\}\}^\{\(1\)\}\(\\hat\{\\pi\};\\rho\_\{T\}\)=𝔼τ∼ρT​\[eπ^​\(s1\)\]\\displaystyle=\\mathbb\{E\}\_\{\\tau\\sim\\rho\_\{T\}\}\\left\[e\_\{\\hat\{\\pi\}\}\(s\_\{1\}\)\\right\]=𝔼τ∼ρT​\[eπ^​\(Q⁡\(s1\)\)\]\\displaystyle=\\mathbb\{E\}\_\{\\tau\\sim\\rho\_\{T\}\}\\left\[e\_\{\\hat\{\\pi\}\}\(Q\(s\_\{1\}\)\)\\right\]=∑cq1ρT​\(c\)​eπ^​\(c\)\.\\displaystyle=\\sum\_\{c\}q\_\{1\}^\{\\rho\_\{T\}\}\(c\)e\_\{\\hat\{\\pi\}\}\(c\)\.
Now letqqbe a target atomic distribution over decision contexts\. Assume thatqqis covered by the compound first\-step distribution:

q1ρT​\(c\)=0⟹q⁡\(c\)=0\.q\_\{1\}^\{\\rho\_\{T\}\}\(c\)=0\\quad\\Longrightarrow\\quad q\(c\)=0\.
Define the first\-step coverage factor as

C1\(q,ρT\)=supc:q1ρT​\(c\)\>0q⁡\(c\)q1ρT​\(c\)\.C\_\{1\}\(q,\\rho\_\{T\}\)=\\sup\_\{c:q\_\{1\}^\{\\rho\_\{T\}\}\(c\)\>0\}\\frac\{q\(c\)\}\{q\_\{1\}^\{\\rho\_\{T\}\}\(c\)\}\.Then

ϵatom​\(π^,q\)≤C1​\(q,ρT\)​ϵcomp​\(π^,ρT\)\.\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)\\leq C\_\{1\}\(q,\\rho\_\{T\}\)\\,\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\\rho\_\{T\}\)\.Indeed, using the definition of atomic error,

ϵatom​\(π^,q\)\\displaystyle\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\)=∑cq⁡\(c\)​eπ^​\(c\)\\displaystyle=\\sum\_\{c\}q\(c\)e\_\{\\hat\{\\pi\}\}\(c\)=∑c:q1ρT​\(c\)\>0q⁡\(c\)q1ρT​\(c\)q1ρT\(c\)eπ^\(c\)\\displaystyle=\\sum\_\{c:q\_\{1\}^\{\\rho\_\{T\}\}\(c\)\>0\}\\frac\{q\(c\)\}\{q\_\{1\}^\{\\rho\_\{T\}\}\(c\)\}q\_\{1\}^\{\\rho\_\{T\}\}\(c\)e\_\{\\hat\{\\pi\}\}\(c\)≤C1​\(q,ρT\)​∑cq1ρT​\(c\)​eπ^​\(c\)\\displaystyle\\leq C\_\{1\}\(q,\\rho\_\{T\}\)\\sum\_\{c\}q\_\{1\}^\{\\rho\_\{T\}\}\(c\)e\_\{\\hat\{\\pi\}\}\(c\)=C1​\(q,ρT\)​ϵatom\(1\)​\(π^,ρT\)\\displaystyle=C\_\{1\}\(q,\\rho\_\{T\}\)\\,\\epsilon\_\{\\mathrm\{atom\}\}^\{\(1\)\}\(\\hat\{\\pi\};\\rho\_\{T\}\)≤C1​\(q,ρT\)​ϵcomp​\(π^,ρT\),\\displaystyle\\leq C\_\{1\}\(q,\\rho\_\{T\}\)\\,\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\\rho\_\{T\}\),where the final inequality follows from Proposition[B\.3](https://arxiv.org/html/2609.19465#A2.Thmtheorem3)\.

Whenq=q1ρTq=q\_\{1\}^\{\\rho\_\{T\}\}, we haveC1​\(q,ρT\)=1C\_\{1\}\(q,\\rho\_\{T\}\)=1, and therefore

ϵatom​\(π^,q1ρT\)≤ϵcomp​\(π^,ρT\)\.\\epsilon\_\{\\mathrm\{atom\}\}\(\\hat\{\\pi\};q\_\{1\}^\{\\rho\_\{T\}\}\)\\leq\\epsilon\_\{\\mathrm\{comp\}\}\(\\hat\{\\pi\};\\rho\_\{T\}\)\.Unlike atomic\-to\-compound transfer, this bound has no horizon factor: it compares atomic performance with only the first decision context of the compound rollout, rather than accumulating errors over allTTsteps\.

### Appendix CExperiment details

#### C\.1Dataset tasks

##### Five data structure domains\.

We chose five common data structure domains of varying difficulty, taken from DSR\-Bench\[[8](https://arxiv.org/html/2609.19465#bib.bib14)\]: array, binary search tree, bloom filter, hashmap, and heap\.

- •Array\.An array is an ordered list of values indexed from left to right\. The model inserts a value at an index or deletes an element, and outputs the final array as a list of integers\.
- •Binary Search Tree \(BST\)\.A BST is a binary tree where values in the left subtree are smaller than the node and values in the right subtree are larger\. The tree is described through node relationships, and the output is the pre\-order traversal of the final tree as a flattened list\.
- •Bloom Filter\.We use a counting Bloom filter, which represents a set with an array of counters and several hash functions\. Insert increments the counters at the hashed positions, while delete decrements them without going below zero\. The output is the final count array\.
- •Hashmap\.A hashmap stores key\-value pairs in buckets using a hash function\. Insert adds or updates a key\-value pair, and delete removes a key if it exists\. The output is a nested list of buckets, where each bucket contains its key\-value pairs\.
- •Heap\.We use an array\-based min\-heap, where each parent is less than or equal to its children\. Insert adds a value and restores the heap property by sifting up, while delete removes the root and restores the heap by sifting down\. The output is the final heap array\.

The atomic skills areinsertanddeletefor each domain, with deletion calledremovefor BSTs and hashmaps in the implementation\. The compound task combines these skills: each example gives a sequence of insert and delete operations, and the model must apply them in order and return the final data structure state\.

The problem length is defined as the initial size of the input data structure, such as the number of elements in an array, nodes in a tree, or entries in a hashmap\. For compound tasks, the problem length additionally also indicates the number of operations in the chain, since the model must update the data structure repeatedly before producing the final state\.

##### Segment tree construction\.

Segment\-tree construction\(example:\[2,−1,3\]\[2,\-1,3\]\)SkillsSplitIntervalSplitIntervalMakeLeafMakeLeafMakeLeafMergeSummariesAssembleNodeAssembleNodeMergeSummariesAssembleNode\[0,1\]\[0,1\]\[2,2\],x2=3\[2,2\],x\_\{2\}=3\[0,0\],x0=2\[0,0\],x\_\{0\}=2\[1,1\],x1=−1\[1,1\],x\_\{1\}=\-1s00s\_\{00\}s11s\_\{11\}s01s\_\{01\}s22s\_\{22\}n01n\_\{01\}n22n\_\{22\}s02s\_\{02\}n02n\_\{02\}\[0,1\]\[0,1\]\[2,2\]\[2,2\]\[0,2\]\[0,2\]si​js\_\{ij\}= summary for interval\[i,j\]\[i,j\]ni​jn\_\{ij\}= assembled node for interval\[i,j\]\[i,j\]SplitIntervalInput: interval\[l,r\]\[l,r\]withl<rl<r Output:\[l,m\]\[l,m\]and\[m\+1,r\]\[m\{\+\}1,r\]MakeLeafInput: singleton\[i,i\]\[i,i\]and valuexix\_\{i\} Output:si​i=\[xi,xi,xi,xi\]s\_\{ii\}=\[x\_\{i\},x\_\{i\},x\_\{i\},x\_\{i\}\], where summarysi​j=\(sum,max\-prefix,max\-suffix,max\-subarray\)s\_\{ij\}=\(\\text\{sum\},\\text\{max\-prefix\},\\text\{max\-suffix\},\\text\{max\-subarray\}\)MergeSummariesInput: child summariessL,sRs\_\{L\},s\_\{R\} Output: parent summaryssAssembleNodeInput: interval\[l,r\]\[l,r\], summaryss, node\(s\) Output: nodenl​rn\_\{lr\}

Figure 10:An example of segment\-tree construction as branch\-merge graph\.Given an integer array, the model must construct a segment tree over the full index range\[0,n−1\]\[0,n\-1\]\. A segment tree is a binary tree that recursively partitions an array interval into smaller intervals\. In our setting, every node corresponds to an inclusive interval\[l,r\]\[l,r\]and stores a four\-field summary

\[sum,best\_prefix,best\_suffix,best\_subarray\]\.\[\\texttt\{sum\},\\texttt\{best\\\_prefix\},\\texttt\{best\\\_suffix\},\\texttt\{best\\\_subarray\}\]\.Here,sumis the total sum of the interval,best\_prefixis the maximum sum of a non\-empty prefix subarray,best\_suffixis the maximum sum of a non\-empty suffix subarray, andbest\_subarrayis the maximum sum of any non\-empty contiguous subarray inside the interval\. Thus, the constructed tree represents both the recursive interval structure and the dynamic\-programming summaries needed for maximum\-subarray range queries\.

We decompose segment\-tree construction into four skills:

- •SplitInterval: Given an interval\[l,r\]\[l,r\]withl<rl<r, computem=⌊\(l\+r\)/2⌋m=\\lfloor\(l\+r\)/2\\rfloorand return the two child intervals\[l,m\]\[l,m\]and\[m\+1,r\]\[m\+1,r\]\.
- •MakeLeaf: Given a single array valuexx, construct the leaf summary\[x,x,x,x\]\[x,x,x,x\], since the sum, best prefix, best suffix, and best subarray are all equal to the only element\.
- •MergeSummaries: Given left summary\[Lsum,Lpref,Lsuff,Lbest\]\[L\_\{\\mathrm\{sum\}\},L\_\{\\mathrm\{pref\}\},L\_\{\\mathrm\{suff\}\},L\_\{\\mathrm\{best\}\}\]and right summary\[Rsum,Rpref,Rsuff,Rbest\]\[R\_\{\\mathrm\{sum\}\},R\_\{\\mathrm\{pref\}\},R\_\{\\mathrm\{suff\}\},R\_\{\\mathrm\{best\}\}\], compute the parent summary: sum\\displaystyle\\texttt\{sum\}=Lsum\+Rsum,\\displaystyle=L\_\{\\mathrm\{sum\}\}\+R\_\{\\mathrm\{sum\}\},best\_prefix\\displaystyle\\texttt\{best\\\_prefix\}=max⁡\(Lpref,Lsum\+Rpref\),\\displaystyle=\\max\(L\_\{\\mathrm\{pref\}\},L\_\{\\mathrm\{sum\}\}\+R\_\{\\mathrm\{pref\}\}\),best\_suffix\\displaystyle\\texttt\{best\\\_suffix\}=max⁡\(Rsuff,Rsum\+Lsuff\),\\displaystyle=\\max\(R\_\{\\mathrm\{suff\}\},R\_\{\\mathrm\{sum\}\}\+L\_\{\\mathrm\{suff\}\}\),best\_subarray\\displaystyle\\texttt\{best\\\_subarray\}=max⁡\(Lbest,Rbest,Lsuff\+Rpref\)\.\\displaystyle=\\max\(L\_\{\\mathrm\{best\}\},R\_\{\\mathrm\{best\}\},L\_\{\\mathrm\{suff\}\}\+R\_\{\\mathrm\{pref\}\}\)\.
- •AssembleNode: Package an interval, its summary, and its two children into the node representation\[interval,summary,left,right\]\[\\texttt\{interval\},\\texttt\{summary\},\\texttt\{left\},\\texttt\{right\}\]\. Leaf children are represented asNone\.

The compound construction task applies these skills recursively\. Starting from\[0,n−1\]\[0,n\-1\], ifl=rl=r, the model appliesMakeLeafand thenAssembleNode\. Ifl<rl<r, the model appliesSplitInterval, independently constructs the left and right subtrees, appliesMergeSummariesto combine their summaries, and finally appliesAssembleNodeto form the parent\. Branching occurs at each non\-leaf interval when it is split into two child intervals that are processed independently\. Merging occurs after both child subtrees are complete, when their summaries are combined into the parent summary\.

The final answer is a pre\-order traversal of the constructed tree\. Each visited node is represented as

\[\[l,r\],\[sum,best\_prefix,best\_suffix,best\_subarray\]\]\.\[\[l,r\],\[\\texttt\{sum\},\\texttt\{best\\\_prefix\},\\texttt\{best\\\_suffix\},\\texttt\{best\\\_subarray\}\]\]\.

#### C\.2Example prompt

Below is an example array\-compound task of length 6:

> ``` An array supports the following operations (using 0-based indexing): 1. (insert, index=i, value=v) inserts value v at position i, shifting elements at i and beyond to the right. 2. (delete, index=i) removes the element currently at position i. Start with the provided initial array and apply each operation in order. Initial array: [94, 89, 79, 60, 41, 48] Operations: (delete, index=4) (delete, index=4) (insert, index=1, value=33) (insert, index=4, value=26) (delete, index=3) (delete, index=0) Q: What is the final array after applying all operations? Your answer should be a list of integers, e.g. [1, 2, 3]. Approach the problem methodically. Ensure all conclusions are based on precise calculations and logical deductions. Feel free to explore various solution methods and cross-check results for consistency. Maintain dynamic thinking and always verify each step of your reasoning. The last line of your response should be of the following format: ‘Therefore, the final answer is: $\boxed{ANSWER}$.’ (without quotes), where ANSWER is just the final number or expression that solves the problem. Think carefully and break down the problem step by step. ```

We append the instruction “Approach the problem methodically…”\. This instruction follows[Guo et al\. \[7\]](https://arxiv.org/html/2609.19465#bib.bib21), which prompts the model to think carefully step by step before giving the final answer\.

#### C\.3Data generation

All examples are synthetically and programmatically generated\. This is possible because the behavior of each data structure can be implemented exactly in code, which lets us compute the ground\-truth answer without human annotation\. Each data structure has a prompt template describing its rules and output format \(an example see above\)\. We then populate the template with randomly generated values, using either integers \(in the range 0–100\) or strings over the English alphabet, depending on the task domain\.

For multi\-skill chain’s compound tasks, each example starts from an initial data structure state and applies a chain of operations\. Each operation is sampled as an insert with probability0\.70\.7and a delete with probability0\.30\.3\. We ensure that every deletion is valid: for example, array deletion chooses an existing index, BST and hashmap deletion choose existing keys or values, heap deletion is only applied to a non\-empty heap, and counting Bloom filter deletion chooses an item that has previously been inserted\. The answer is the final serialized state after applying all operations in order\.

We also make the outputs deterministic and unique by fixing implementation details that could otherwise be ambiguous\. For example, when a traversal has multiple possible next nodes, we visit neighbors in increasing value order; when heap deletion has equal children, we use a fixed tie\-breaking rule\. These constraints ensure that each prompt has a single well\-defined ground\-truth output\.

#### C\.4Output validation

We extract the model’s final answer from the final\\boxed\{\}answer and compare it against the ground truth, following[Guo et al\. \[7\]](https://arxiv.org/html/2609.19465#bib.bib21)\. We use instruction\-tuned models to reduce errors caused by poor instruction following rather than poor data\-structure reasoning\. To further reduce formatting sensitivity, our evaluator applies several formatting relaxations:

- •it extracts the last boxed answer, including boxed answers with nested braces;
- •it accepts\\boxedanswers written without braces;
- •it falls back to answers following phrases such as “the final answer is”;
- •it strips common wrappers such as code fences and simple LaTeX text wrappers;
- •it extracts the first balanced list, tuple, or dictionary from otherwise verbose text;
- •it accepts both Python\-style literals and JSON\-style literals;
- •it treats tuples and lists as equivalent for sequence outputs;
- •for hashmaps, it allows key\-value pairs within a bucket to appear in any order\.

Before comparison, we also normalize the extracted output:

- •remove extra whitespace, newlines, dollar signs, backslashes, and simple LaTeX spacing commands;
- •normalize\\tfracand\\dfracto\\frac;
- •remove\\left,\\right, and degree markers;
- •normalize decimal forms such as\.5to0\.5;
- •normalizenull/Noneand Boolean tokens;
- •parse numeric answers as numbers, with a small tolerance for floating\-point answers;
- •recursively normalize nested sequence structures before equality checking\.

An example is marked incorrect if the model produces a wrong final state, if no final answer can be extracted, or if the extracted answer cannot be parsed under these formatting relaxations\. In preliminary experiments, we also tried Structured Output to allow more flexible answer formats while requiring JSON output, but this lowered performance\. We therefore use flattened representations when possible, such as pre\-order traversal for BST outputs, since a flat list is easier for models to produce reliably than a deeply nested structure\. Future work could use an LLM judge to further reduce the effect of formatting constraints\.

#### C\.5Reinforcement learning \(RL\) post\-training

##### Training framework\.

We perform RL post\-training with a rule\-based outcome reward\. The policy is initialized from an instruction\-tuned model and trained with Group Relative Policy Optimization \(GRPO\)\[[19](https://arxiv.org/html/2609.19465#bib.bib18)\]\. We useverl\[[20](https://arxiv.org/html/2609.19465#bib.bib22)\]as the RL training framework, which manages distributed policy updates, reference\-policy log probabilities, advantage computation, and checkpointing\. For generation during training, we usevLLM\[[11](https://arxiv.org/html/2609.19465#bib.bib23)\]as the rollout engine, which efficiently samples multiple responses from the current policy for each prompt\.

For each prompt, the model samples multiple candidate responses\. We extract the final boxed answer from each response and score it with the same deterministic verifier used for evaluation\. A response receives reward11if the extracted answer matches the ground truth after normalization, and reward00otherwise\. The scalar outcome reward is assigned to the final response token\. We do not train a learned reward model; instead, the reward is computed directly from programmatic correctness\.

##### Reward function\.

The reward function is a binary correctness signal aligned with the evaluation metric\. Given a generated response, we first extract the final answer, prioritizing the final\\boxed\{\}expression\. We then apply the same formatting relaxations and normalization rules used in evaluation \(Section[C\.4](https://arxiv.org/html/2609.19465#A3.SS4)\), such as stripping simple LaTeX wrappers, accepting JSON\- or Python\-style list literals, normalizing tuples to lists, and comparing parsed data\-structure states rather than raw strings\. The normalized prediction is compared against the programmatically generated ground truth\. Correct outputs receive reward11and incorrect or unparsable outputs receive reward00\. This makes the RL signal deterministic and avoids using a learned reward model or an LLM judge during training\.

##### Hyperparameters\.

Training uses a batch size of 128 prompts, with 5 rollouts per prompt for GRPO\. The maximum prompt length is 2048 tokens\. The maximum response length is 4096, 8192, and 16384 tokens for problem length ranges 5–10, 11–20, and 21–30, respectively\. We train for 30 optimization steps with learning rate5×10−65\\times 10^\{\-6\}\. We use KL regularization against the reference policy with coefficient0\.0010\.001and an entropy coefficient of0\.0010\.001\. The PPO mini\-batch size is 128, and the per\-GPU micro\-batch size is 4\. Experiments were conducted on four NVIDIA H200 141GB GPUs\.

#### C\.6Supervised finetuning \(SFT\) post\-training

##### Data generation\.

We build SFT data from the same synthetic data\-structure examples used for RL\. For each generated problem, we construct a supervised prompt\-response pair where the prompt contains the original data\-structure question and the response contains a step\-by\-step solution trace followed by the final answer\. For each data structure and operation type, we manually write SFT reasoning templates for insert and delete behavior\. The data generator then fills these templates with the sampled values from each training example, producing a complete chain\-of\-thought reasoning trace that walks through the operation sequence and ends with the final serialized answer\.

##### Example SFT training data\.

Below is an example array compound SFT instance with both insert and delete operations\. After preprocessing, the text beforeA:is used as the user prompt, and the text afterA:is used as the supervised assistant response\.

> ``` [User prompt] An array supports the following operations (using 0-based indexing): 1. (insert, index=i, value=v) inserts value v at position i, shifting elements at i and beyond to the right. 2. (delete, index=i) removes the element currently at position i. Start with the provided initial array and apply each operation in order. Initial array: [52, 74, 58, 7, 63, 79, 31] Operations: (insert, index=1, value=52) (delete, index=3) ... Q: What is the final array after applying all operations? Your answer should be a list of integers, e.g. [1, 2, 3]. Approach the problem methodically. Ensure all conclusions are based on precise calculations and logical deductions. Feel free to explore various solution methods and cross-check results for consistency. Maintain dynamic thinking and always verify each step of your reasoning. The last line of your response should be of the following format: ’Therefore, the final answer is: $\boxed{{ANSWER}}$.’ (without quotes), where ANSWER is just the final number or expression that solves the problem. Think carefully and break down the problem step by step. [Assistant response] The original array is [52, 74, 58, 7, 63, 79, 31]. The first step is insert 52 at index 1. Inserting 52 at index 1 shifts the elements from index 1 onwards to the right. The updated array becomes [52, 52, 74, 58, 7, 63, 79, 31]. The next step is delete at index 3. Removing the value 58 at index 3 updates the array. The updated array becomes [52, 52, 74, 7, 63, 79, 31]. ... Therefore, the final answer is: $\boxed{[52, 52, 73, 77, 7, 72, 63, 79, 68, 31]}$. ```

##### Training\.

We train for 300 optimization steps with learning rate1×10−51\\times 10^\{\-5\}, cosine learning\-rate scheduling, batch size of 32, weight decay0\.010\.01, gradient clipping at1\.01\.0, and 10% warmup\.

#### C\.7The Berkeley Function Calling Leaderboard \(BFCL\) Benchmark

We use the Berkeley Function Calling Leaderboard \(BFCL\)\[[16](https://arxiv.org/html/2609.19465#bib.bib20)\]to evaluate whether a model produces the correct API call given a request\. We focus on three Python function\-calling categories:simple\_python,parallel, andparallel\_multiple\. In BFCL, each function schema specifies a reusable skill primitive\. Thesimple\_pythonsplit contains atomic examples, where the user request can be solved by invoking a single function once\. Theparallelsplit contains compound examples that require multiple invocations of the same function schema, such as calling a weather API for several cities\. Theparallel\_multiplesplit further increases compositionality by providing multiple function schemas and requiring the model to select and invoke several relevant functions\. Thus,simple\_pythontests isolated skill execution, whileparallelandparallel\_multipletest whether the model can coordinate multiple skill invocations within a single user request\.

##### Prompt\.

Each sample is converted into a chat\-style prompt\. The prompt gives the user request and the list of available Python functions, and asks the model to return the final function call or calls\. If multiple calls are needed, the model is instructed to put one call per line\. The gold answer is stored as a structured JSON payload containing the target calls and whether call order matters\.

##### Data\.

We build separate atomic and compound training and test sets\. The atomic training set contains 300simple\_pythonexamples\. The compound training set contains 150parallelexamples and 150parallel\_multipleexamples\. The test set contains 100 examples from each of the three categories, for 300 examples in total\.

##### Verification\.

BFCL answers are verified with a rule\-based exact\-match checker\. The checker parses model outputs from several accepted formats, including Python\-style function calls, JSON objects or lists,<answer\>tags, and the final\\boxed\{\}answer format\. Parsed calls are normalized before comparison: dictionary keys are sorted, numeric values are canonicalized, and unordered call sets are sorted when the BFCL example is not order\-sensitive\. A prediction receives reward 1 only if the normalized predicted function name, arguments, and call structure exactly match the normalized gold payload; otherwise it receives reward 0\.

### Appendix DGeneralization of compositional reasoning

In Section[4](https://arxiv.org/html/2609.19465#S4), we primarily study*length generalization*to evaluate whether models can extend compositional reasoning beyond the training regime\. To further probe the generalization induced by composed\-task training, we consider two additional transfer settings: robustness under structural distribution shift, and transfer from basic skills to more complex tasks that require unseen skills\.

#### D\.1Generalization under structural distribution shift

We test whether a model trained on one input distribution can generalize to others while the underlying skill remains unchanged\. If the model has learned the skill rather than distribution\-specific patterns, its performance should remain robust under such shifts\.

![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/dist/dist_shift_compact.png)Figure 11:Distribution\-shift generalization on BST and graph construction\. Accuracy across shifts inα\\alphaandτ\\tau\. Dotted lines mark the training distribution; error bars show 95% confidence intervals\.##### Distribution\-shift transfer\.

We study two tasks: binary search tree \(BST\) construction and graph construction\. For BSTs, we introduce a parameterα\\alphato control tree skewness\. Whenα\>0\\alpha\>0, the generator favors values near the edges of the range, producing more unbalanced insertion orders and hence more skewed trees\. Whenα<0\\alpha<0, it favors values near the center, yielding more balanced trees\. The caseα=0\\alpha=0corresponds to the training distribution\. For graph construction, the training distribution uses an edge threshold of 30: an edge is created when the absolute difference between two node values exceeds this threshold\. At test time, lowering the threshold to 10 produces denser graphs, while increasing it to 50 produces sparser graphs\.

We find that the model finetuned with composed training remains robust under distribution shift, consistently outperforming the base model across all tested distributions in both BST and graph construction\. However, the improvement is not uniform across distributions\. For BSTs, the gain is largest on more balanced trees and smaller on more skewed trees, suggesting that skewed trees increase execution difficulty, plausibly by requiring a longer implicit stack\. For graphs, the gain is also smaller in the sparse regime than in the denser or training\-like regimes\. Overall, composed training transfers robustly across structural distributions, but its benefit still depends on structural properties that affect execution difficulty\.

#### D\.2Generalization to unseen skills

We study whether training on a set of basic skills enables a model to solve a more complex target task that requires skills unseen during training\. We consider two settings\.

![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/hard/hard_transfer_kd_geom.png)\(a\)Transfer to structurally richer tasks requiring unseen skills\.
![Refer to caption](https://arxiv.org/html/2609.19465v1/plots/natural/natural_transfer_compact.png)\(b\)Transfer from formal tasks to natural\-language variants\.

Figure 12:Left: transfer to KD\-Tree and Geometric Graph construction from basic 1D skills, compared with direct fine\-tuning on the target task\. Right: transfer from formal tasks to natural\-language BST and graph variants\. Error bars show 95% confidence intervals over test examples\.Higher\-dimensional transfer\.Following the spatial probe in DSR\-Bench, we train on BST construction and evaluate on KD\-Tree construction\. Relative to BSTs, KD\-Trees require an additional unseen skill: node\-level splitting, where the model must partition a set of points along a specified dimension\. For graph construction, we train on the 1D setting and evaluate on Geometric Graphs, a higher\-dimensional variant in which edges are determined by Euclidean distance rather than absolute difference\. In both cases, we use dimensionK=2K=2\.

Natural\-language transfer\.Following the realistic probe in DSR\-Bench, we embed both tasks into more realistic natural\-language settings\. For BSTs, the task is framed as patients calling to book clinical appointments, where each node contains a patient name and appointment time\. For graphs, the task is framed as spaceship travel across a galaxy through tunnels, where tunnels are created when two planets are sufficiently close in a hyperplane\. These variants require the model to map from context\-rich language to the underlying formal data\-structure problem, and then execute the appropriate reasoning procedure\.

We find that training on basic skills does not transfer strongly to harder target tasks that require unseen skills\. On KD\-Tree and Geometric Graph construction, the gains from transfer are small, while direct fine\-tuning on the target task yields much larger improvements\. Transfer to natural\-language variants is also limited, with only modest gains over the base model\. This suggests that compositional transfer remains difficult when generalization requires not only recombining known skills, but also acquiring new operations or reasoning primitives\.

### Appendix EPractical implications

Our observed decomposed\-to\-composed asymmetry has important practical implications for data design in RL post\-training, especially as language models are increasingly trained to solve real\-world problems that require advanced skills\. Such problems usually require skills to be combined, not executed in isolation\. In reasoning applications such as*proof writing*, compositional reasoning is required explicitly: success does not come from applying a single theorem or algebraic manipulation, but from choosing relevant lemmas, sequencing them into a valid argument, and maintaining dependencies between intermediate claims\. Similar compositional reasoning also underlies real\-world agentic applications\. In*tool\-calling agents*, the challenge is not only to learn individual API calls, such as retrieving weather, searching a database, or updating a calendar entry\. The harder problem is to coordinate these calls into a valid workflow, where the output of one step determines what should happen next\. Likewise,*coding agents*rarely succeed by editing one line in isolation: they must locate the relevant code, reason about dependencies across functions, apply a patch, and verify that the change is consistent with the intended behavior\. Our findings suggest that although individual\-skill training can be easier to supervise, it may not be sufficient for tasks that require composition\. Training on composed tasks provides a more relevant signal for compositional generalization, while also transferring back to individual skills\. Thus, for RL post\-training on real\-world deployment, data should prioritize verifiable multi\-step trajectories rather than only isolated skill drills\.

### Appendix FStructured output and intermediate scoring

As described in Section[C](https://arxiv.org/html/2609.19465#A3), we extract the final answer using a boxed output format, following[Guo et al\. \[7\]](https://arxiv.org/html/2609.19465#bib.bib21)\. To reduce errors caused by formatting issues, we additionally implement normalization and relaxation procedures, and evaluate outputs with instruction\-tuned models\. These design choices are based on preliminary experiments aimed at identifying the most suitable setup for evaluating compositional reasoning\. Below, we discuss the rationale behind these choices\.

One alternative is to use JSON\-based Structured Output, a feature provided byvllm\[[11](https://arxiv.org/html/2609.19465#bib.bib23)\]that enforces outputs to follow a predefined JSON schema\. This approach enables more flexible verification and allows correctness to be checked dynamically from successful executions, instead of relying on manually specified constraints such as always visiting neighbors in ascending order to guarantee a unique output\. However, our preliminary experiments with Qwen3\-4B\-Instruct produces substantially fewer correct outputs when using Structured Output\. We hypothesize that the stricter and more complex JSON formatting requirements increase the generation difficulty\. Therefore, we do not use Structured Output in our final setup, and instead evaluate serialized outputs \(e\.g\., flattening a tree with preorder traversal\) for correctness checking\.

Another design choice is that we use only final\-output scoring for both RL reward computation and evaluation\. Since each step in the data structure computation is deterministic, intermediate states can in principle also be generated and verified\. However, doing so requires additional formatting constraints to programmatically extract intermediate outputs\. In our preliminary experiments, we found that adding such constraints consistently reduced overall performance\. One possible reason is that models may rely on dynamic reasoning processes with self\-correction \(e\.g\., “Aha” moments\), which are disrupted by enforcing structured intermediate outputs\. As a result, we evaluate only the final output correctness for our experiments, providing flexibility to the models’ reasoning process\.

Finally, future work could explore LLM\-based judging for answer extraction, removing the need for Structured Output or explicit intermediate\-state formatting altogether\. This may further reduce formatting\-related errors\. In addition, tracking intermediate reasoning trajectories and comparing them against ground\-truth states—including cases with later error correction—could provide deeper insights into the compositional reasoning abilities of language models\.