Can RL Teach Long-Horizon Reasoning to LLMs? Expres... | AI Research

Can RL Teach Long-Horizon Reasoning to LLMs? Expressiveness Is Key
Researchers are investigating why large language models (LLMs) often struggle with complex, multi-step reasoning. While reinforcement learning (RL) has improved model performance in areas like math and coding, these gains often disappear when tasks require long sequences of logical steps. This paper introduces "ScaleLogic," a synthetic framework designed to systematically measure how training difficulty—specifically the depth of reasoning and the complexity of the logic involved—affects an LLM's ability to learn. By controlling these variables, the authors provide a clearer picture of how to scale RL training effectively.

A Controlled Environment for Reasoning

Current methods for training LLMs often lack the ability to precisely control the difficulty of reasoning tasks. ScaleLogic addresses this by generating synthetic problems that require the model to identify a correct conclusion from a set of facts. The framework allows researchers to independently adjust two key factors: the "horizon" (the depth of the proof tree required to reach a conclusion) and the "logical expressiveness" (the complexity of the rules, such as adding "and," "or," "not," or "for all" statements). Because these problems are automatically generated and verifiable, they provide a scalable and low-cost way to test how models handle increasingly difficult logical chains.

The Power Law of Training Compute

The study reveals a consistent relationship between the effort required to train a model and the difficulty of the tasks it must solve. The authors found that the amount of training compute needed to reach a specific accuracy threshold follows a "power law" relative to the depth of the reasoning required. Crucially, the "scaling exponent"—a measure of how much harder the training becomes as tasks get deeper—increases significantly as the logic becomes more expressive. For simple "if-then" logic, the exponent is 1.04, but it rises to 2.60 for more complex first-order logic. This demonstrates that as logical complexity increases, the training effort required to master deeper reasoning grows disproportionately.

Impact on Real-World Performance

Beyond synthetic tasks, the researchers tested whether this training translates to real-world benchmarks in mathematics and general reasoning. They discovered that training on highly expressive synthetic data leads to better performance on these external benchmarks, with improvements of up to 10.66 percentage points. The results suggest that the "quality" of the training data—specifically its logical expressiveness—is just as important as the quantity. Models trained on more expressive logic showed more efficient and robust transfer to real-world problems, whereas models trained on simpler logic tended to plateau early, failing to gain the same level of reasoning capability.

Key Takeaways for Future Training

The findings suggest that the way we structure training data fundamentally shapes how well an LLM learns to reason. The authors also noted that using a "curriculum"—a structured approach to training that introduces difficulty gradually—can significantly improve the efficiency and stability of the learning process. By providing a framework that isolates these variables, the paper offers a roadmap for developers to move beyond simple data scaling and toward more targeted, compute-efficient strategies for teaching LLMs how to handle long-horizon, complex reasoning.