Irreducible Supervision Enables Compositional Generalization in Post-Training

Reinforcement learning (RL) with verifiable rewards has driven recent gains in large language model (LLM) reasoning, but whether it creates new capabilities or merely sharpens existing ones remains debated, especially for compositional generalization, where models must combine learned primitives into novel multi-step functions. Using a controlled program synthesis domain over a typed domain-specific language (DSL) of 119 primitives with verifiable compositional depth and irreducibility, where the base model has zero capability prior to fine-tuning, we show on Qwen3-8B (and replicate within-family at 4B and 32B, and cross-family on Llama-3.1-8B) that compositional capability is established during supervised fine-tuning (SFT) and depends on irreducibility at two levels of SFT data: structural irreducibility of compositional exemplars and observational irreducibility, where prompt input-output pairs are chosen adversarially to rule out shallower programs. Neither alone is sufficient; even moderate contamination with structurally reducible exemplars substantially degrades performance, and full contamination yields zero pass@64. Given this SFT foundation, standard outcome-reward RL (GRPO, PPO) maintains but does not extend compositional performance, contrasting with prior results in settings with simpler nested function execution. Compositional capability is bottlenecked by structural properties of SFT data, before RL begins. Code release pending institutional IP review.