Composed labels beat whole-problem guesses: compositional self-improvement pushes reliable prediction past a model's starting range

Compositional self-improvement lets a model keep improving beyond its initial reliable range by building training labels for harder problems from predictions on simpler subproblems. Under the same expansion schedule, direct self-improvement uses the model's prediction on the full harder instance as its pseudo-label and yields little or no such extension on addition and grid navigation. Composed supervision extended reliable prediction in all three controlled algorithmic tasks (grid navigation, addition, max run length), and composed labels were more accurate than direct self-labels on program generation and multi-hop reasoning.

The reliability of composed labels depends on component predictions, the composition rule and coverage, not on average label accuracy alone. Earlier work using compositional structure to build training data usually targeted generalization to novel compositions without separating these three error sources. In grid navigation, models with lower initial one-room accuracy plateaued earlier; in addition, carries across block boundaries made unfiltered composed labels wrong, and filtering restored self-improvement; in max run length, runs crossing the concatenation boundary exceed what composed labels can express, and accuracy fell sharply as the excess grew.

Even imperfect composed supervision can give reinforcement learning a useful starting point. Direct reinforcement learning samples inefficiently when correct samples are rare, and can receive no reward at all. On five-operation string chains, direct RL never sampled a correct composition even with twice the generation budget, whereas RL after a short compositional SFT warmup improved steadily; on typed Python, RL after the warmup reached with half the generation budget what direct RL needed the full budget to reach.

The scope is tasks with supplied decomposition plans and composition rules: three controlled algorithmic tasks, Bash pipeline generation, MuSiQue multi-hop question answering, and RL warm-start experiments on string transformations and typed Python. The intended reader is someone working on self-training, pseudo-labels or reinforcement-learning data construction.

The authors state that the study focuses on tasks with supplied decomposition plans and composition rules, leaving open how to discover and validate such structures in less controlled settings; expanding supervision coverage without introducing additional composition errors is another direction. In multi-hop reasoning, composed-label accuracy rises with model size (first-round accuracy from 45% for 2B to 65% for 9B), and component reliability still limits the gains.