Compositional Self-Improvement: Promises and Pitfalls
Organizations: Department of Computer Science, Princeton University, Princeton, NJ · Department of Electrical and Computer Engineering, University of Wisconsin–Madison, Madison, WI · Department of Psychology, Princeton University, Princeton, NJ · Department of Computer Sciences, University of Wisconsin–Madison, Madison, WI
Abstract
Although self-improvement is becoming increasingly important as tasks become more complex, models struggle to generate reliable supervision for harder, out-of-distribution instances. One way to address this challenge is to exploit compositional structure: models often solve simpler subproblems more reliably than full problems, so their subproblem predictions can be composed into supervision for harder ones. We systematically study when this kind of composed supervision supports self-improvement and when it fails. Our controlled experiments identify three failure modes: unreliable subproblem predictions, errors introduced by composition, and limited supervision coverage. Beyond controlled settings, these findings carry over to more realistic coding and reasoning tasks: composed labels are more accurate than direct self-generated labels and improve performance even on compositions longer than those seen during training, while the failure modes remain visible. Further, although these failure modes often keep compositional self-improvement from fully succeeding on its own, a short SFT warmup with compositional self-improvement can bootstrap reinforcement learning on tasks that require composing skills the model already has, particularly when direct exploration rarely succeeds. Together, these findings characterize when compositional self-improvement can provide sufficiently reliable supervision to expand model capabilities.
Figures & tables
| Task | Component 1 | Component 2 | Composed parent label | Filter |
|---|---|---|---|---|
| Grid navigation | ####### #.....# #...#.# #.....# #.#..G# #S...## ####### RRURR | ####### #....G# #S....# ###...# ##....# #.....# ####### URRRR | # ##### ### ##### # # ..... ### ....G # # ...#. #.. ..... # # ..... #.# ##... # # .#... ..# #.... # # S...# ### ..... # # ##### ### ##### # RRURR RRUURR URRRR | No filter |
| Addition | {\color[rgb]{0.1211,0.4336,0.5469}11}+{\color[rgb]{0.1211,0.4336,0.5469}22}={\color[rgb]{0.1211,0.4336,0.5469}33} | {\color[rgb]{0.4805,0.3086,0.6602}33}+{\color[rgb]{0.4805,0.3086,0.6602}44}={\color[rgb]{0.4805,0.3086,0.6602}77} | {\color[rgb]{0.1211,0.4336,0.5469}11}{\color[rgb]{0.4805,0.3086,0.6602}33}+{\color[rgb]{0.1211,0.4336,0.5469}22}{\color[rgb]{0.4805,0.3086,0.6602}44}={\color[rgb]{0.1211,0.4336,0.5469}33}{\color[rgb]{0.4805,0.3086,0.6602}77} | Accept |
| {\color[rgb]{0.1211,0.4336,0.5469}11}+{\color[rgb]{0.1211,0.4336,0.5469}22}={\color[rgb]{0.1211,0.4336,0.5469}33} | {\color[rgb]{0.4805,0.3086,0.6602}60}+{\color[rgb]{0.4805,0.3086,0.6602}45}={\color[rgb]{0.4805,0.3086,0.6602}105} | {\color[rgb]{0.1211,0.4336,0.5469}11}{\color[rgb]{0.4805,0.3086,0.6602}60}+{\color[rgb]{0.1211,0.4336,0.5469}22}{\color[rgb]{0.4805,0.3086,0.6602}45}={\color[rgb]{0.1211,0.4336,0.5469}33}{\color[rgb]{0.4805,0.3086,0.6602}105} | Reject | |
| Max run length | 3111 1|3 | 022227 2|4 | 3111 022227 2|4 | Accept |
| (symbol | length of the longest run) | 01111 1|4 | 11200 1|2 | 01111 11200 1|4 | Reject |
| Task | Component 1 | Component 2 | Composed parent label | Filter |
|---|---|---|---|---|
| Program generation | Output the first 5 lines head -5 | Sort in descending order sort -r | Step 1: output the first 5 lines. Step 2: sort in descending order. head -5 | sort -r | Parses as a pipeline |
| Multi-hop reasoning | Who issued the Royal Proclamation of 1763? King George III | What year did King George III die? 1820 | What year did the person who issued the Royal Proclamation of 1763 die? 1820 | Answer format; answer found in the passages |
| Task | Component 1 | Component 2 | Composed parent label | Filter |
|---|---|---|---|---|
| String transformations | func_20(kqz) k-q-z | func_11( k-q-z ) -q-zk | func_11(func_20(kqz)) func_20=k-q-z | func_11=-q-zk => -q-zk | Each step nonempty, length |
| Typed Python | Last digit {\color[rgb]{0.1211,0.4336,0.5469}p_{1}} : return x % 10 | Integer to binary string {\color[rgb]{0.4805,0.3086,0.6602}p_{2}} : return bin(x)[2:] | Step 1: last digit. Step 2: integer to binary string. return p2 ( p1 (x)) | Parses as one function |
Appendix figures & tables19 assets
Supplementary material from the paper’s appendix.
Appendix
| Component 1 output: | RRRDRDD |
|---|---|
| Component 2 output: | RUURRR |
| Composed target: | RRRDRDD RRDRR RUURRR (corridor actions in the middle) |
| Shared instruction block |
| Use only standard text utilities (such as sort, uniq, grep, cut, tr, head, tail, sed, awk, wc, rev, tac, nl, paste, fold, fmt, cat, column). The text arrives on standard input; do not name any file. Reply with the command on one line and nothing else. |
| Component 1: model input |
| Write one Bash command that reads standard input and does the following. Task: Output the first 5 lines of a file |
| Selected output: head -5 |
| Component 2: model input |
| Write one Bash command that reads standard input and does the following. Task: Sort a file in descending order |
| Model input | Saved output | |
|---|---|---|
| Component 1 | Q: func_2(bnqi) = ? | func_2=binq => binq |
| Component 2 | Q: func_15(binq) = ? | func_15=elqt => elqt |
| Component 3 | Q: func_15(elqt) = ? | func_15=hotw => hotw |
| Component 4 | Q: func_4(hotw) = ? | func_4=hOtW => hOtW |
| Component 5 | Q: func_13(hOtW) = ? | func_13=WhOt => WhOt |
| Grid navigation | Addition | Max run length | |
|---|---|---|---|
| Model | M-parameter character-level Transformer | ||
| Learning rate | |||
| Weight decay | |||
| Batch size | |||
| Initial training | one-room grids, updates | 3–7 digits, per length, updates | Lengths 6–10, per length, updates |
| Rounds | 12 | 8 | 8 |
| Program generation | Multi-hop reasoning | |
|---|---|---|
| Model | Qwen3.5-2B; LoRA rank , | Qwen3.5-2B, 4B, 9B; LoRA rank on attention and feed-forward projections |
| Initial training | All commands, updates, learning rate | single-hop questions, updates, batch size , learning rate |
| Rounds | (pipelines of , , commands) | ( -, -, -hop questions) |
| Parents per round | , , | |
| Training per round | AdamW updates, learning rate , batch size , gradient clipping | AdamW updates, learning rate , batch size |
| Rehearsal | of each batch | of examples per batch |
| Strings | Typed Python | |
| Initial model and compositional warmup | ||
| Initial model | M character Transformer | Qwen3.5-2B, LoRA rank , |
| Initial training | Chains of – functions | updates on single functions |
| Warmup SFT | updates, learning rate | updates, learning rate |
| Target tokens per update | ||
| GRPO | ||
| Task | Labels | Kept | Wrong labels ( ) | Summed component errors ( ) | Rule errors ( ) | Wrong with correct components | Correct with a wrong component |
|---|---|---|---|---|---|---|---|
| Grid navigation | 2 rooms | 100 | 0.9 | 0.9 | 0.0 | 0.0 | 0.0 |
| 2–13 rooms | 100 | 3.5 | 3.5 | 0.0 | 0.0 | 0.0 | |
| Bash | length 2 | 100 | 8.8 | 9.1 | 0.0 | 0.0 | 0.1 |
| length 4 | 100 | 30.3 | 32.3 | 0.0 | 0.0 | 0.3 | |
| Strings | depth 5 | 100 | 23.0 | 26.8 | 0.0 | 0.0 | 0.0 |
| Typed Python | depth 3 | 100 | 5.9 | 7.4 | 0.0 | 0.0 | 1.6 |
| Model | Quantity | Round 1 (2 hops) | Round 2 (3 hops) | Round 3 (4 hops) |
|---|---|---|---|---|
| 2B | Compositional labels correct | 44.8 | 42.3 | 49.9 |
| Direct labels correct | 28.9 | 21.6 | 24.3 | |
| Step error, step 1 to final | 12.9, 58.3 | 15.9, 27.2, 61.8 | 19.7, 32.6, 33.8, 55.9 | |
| Wrong labels, first error at final step | 83.4 | 60.7 | 39.4 | |
| Correct labels with a wrong step | 6.8 | 15.9 | 30.8 | |
| 4B | Compositional labels correct | 60.5 | 63.1 | 65.6 |
| Initial-training updates | One-room accuracy | Mean child error | , 2 rooms | , 13 rooms |
|---|---|---|---|---|
| 400 | 28.4 | 76.3 | 94.3 | 99.4 |
| 1,500 | 58.3 | 44.1 | 68.3 | 93.7 |
| 2,500 | 73.7 | 29.1 | 49.7 | 86.0 |
| 3,000 | 79.9 | 21.4 | 38.1 | 77.1 |
| 6,000 | 90.4 | 9.2 | 17.5 | 48.5 |
| 8,000 | 95.0 | 5.3 | 10.3 | 32.2 |
| Task | Test instances | Initial, direct | Initial, decomposed | Final round, direct |
|---|---|---|---|---|
| Grid navigation | 2–13 rooms | 0.0 | 88.6 | 80.9 |
| 13 rooms | 0.0 | 76.5 | 47.0 | |
| Addition | 8–23 digits | 0.0 | 23.2 | 93.7 |
| 23 digits | 0.0 | 4.0 | 80.0 | |
| Max run length | 11–83 symbols | 59.8 | 87.9 | 97.6 |
| 83 symbols | 37.0 | 81.0 | 94.0 |
| Task | Initial, direct | Initial, decomposed | After warmup | After warmup and RL |
|---|---|---|---|---|
| Strings, depth 5 | 0.0 | 77.3 | 11.5 | 19.2 |
| Strings, depth 4 | 0.2 | 85.4 | 38.7 | 50.1 |
| Length-preserving, depth 4 | 0.0 | 90.0 | 47.5 | 61.7 |
| Typed Python | 3.3 | 92.2 | 22.1 | 55.6 |
| Label source | Round 1 | Round 2 | Round 3 |
|---|---|---|---|
| Compositional | 90.6 | 83.6 | 80.6 |
| Direct | 7.9 | 2.0 | 0.5 |
Language Model Self-Improvement
Language model self-improvement studies how models use their own outputs, feedback, and experience to improve with less external supervision.
See all 195 papers