Training Recursive Language Models for Hierarchical Compositional Generalization

Recursive language-model inference distributes reasoning across independent calls, but it is unclear whether the structure itself improves compositional generalization or simply adds inference compute. We study hierarchical compositional generalization through Countdown expression trees, with controlled splits of seen patterns and held-out compositions. With the search policy and training budget fixed, the Recursive Language Model attains higher seen-pattern and compositional accuracy than Linearized, generates fewer tokens, and loses less accuracy as pattern size grows. We compare two ways to scale inference compute: lengthening one linearized trajectory and widening recursive search. Wider recursive search gives larger gains in our experiments. By splitting a trajectory across calls, Recursive can learn from searches whose total length exceeds one context without increasing the training-token budget. A checkpoint trained on narrow search does not reliably use wider inference-time search, and a large compositional gap remains. On this task, recursive execution yields more accuracy per generated token, but its scaling depends on the search policy used in training.