Compositional Reasoning in Language Models After Reinforcement Learning Post-Training

Summary

Compositional reasoning allows language models to combine learned skills in unfamiliar ways, but how reinforcement-learning post-training affects this ability is not well understood. The authors propose a dependency-graph framework that defines three levels of compositionality with increasing complexity. They instantiate it with data-structure tasks, whose rewards can be computed deterministically and whose composition is explicit. Across these tasks, decomposed-skill training does not reliably transfer to composed tasks, while training on composed tasks transfers more readily back to decomposed tasks. The paper provides a theoretical explanation for this decomposed-to-composed asymmetry. It also tests generalization under length extrapolation, structural distribution shift, and transfer to tasks requiring previously unseen skills. A pilot study on real-world tool-calling benchmarks provides preliminary evidence that the same asymmetry can occur in practical settings.