Can RL Teach Long-Horizon Reasoning to LLMs? Expressiveness Is Key
:::info Stub — Full Engineering Breakdown Coming This paper was featured on Hugging Face Daily Papers on 2026-05-07 with 11 upvotes. A full breakdown with production viability rating, implementation notes, and honest limitations is being written. Subscribe to AI Letters → :::
| Authors | Tianle Wang et al. |
| Year | 2026 |
| HF Upvotes | 11 |
| arXiv | 2605.06638 |
| Download | |
| HF Page | View on Hugging Face |
Abstract
Reinforcement learning (RL) has been applied to improve large language model (LLM) reasoning, yet the systematic study of how training scales with task difficulty has been hampered by the lack of controlled, scalable environments. We introduce ScaleLogic, a synthetic logical reasoning framework that offers independent control over two axes of difficulty: the depth of the required proof planning (i.e., the horizon) and the expressiveness of the underlying logic. Our proposed framework supports a wide range of logics: from simple implication-only logic ("if-then") towards more expressive first-order reasoning with conjunction ("and"), disjunction ("or"), negation ("not"), and universal quantification ("for all"). Using this framework, we show that the RL training compute T follows a power law with respect to reasoning depth D (T propto D^γ, R^{2} > 0.99), and that the scaling exponent γ increases monotonically with logical expressiveness, from 1.04 to 2.60. On downstream mathematics and general reasoning benchmarks, more expressive training settings yield both larger performance gains (up to +10.66 points) and more compute-efficient transfer compared to less expressive settings, demonstrating that what a model is trained on, not just how much it is trained, shapes downstream transfer. We further show that the power-law relationship holds across multiple RL methods, and curriculum-based training substantially improves scaling efficiency.
Engineering Breakdown
Plain English
This paper introduces ScaleLogic, a controlled synthetic environment for studying how reinforcement learning teaches LLMs to reason over long horizons. The key finding is that RL training compute follows a power law relationship with task difficulty, and critically, the expressiveness of the logic (whether the system can handle conditionals, conjunctions, quantifiers, etc.) is a major factor determining how well LLMs learn—more expressive logics require significantly more compute to train effectively.
Key Engineering Insight
Expressiveness of the reasoning domain is not just a feature of the task; it's a fundamental scaling axis that determines training efficiency. A system trained on simple if-then logic won't smoothly generalize to first-order logic with quantifiers—you need to budget substantially more compute when targeting more expressive reasoning capabilities.
Why It Matters for Engineers
If you're building LLM-based reasoning systems for real applications (planning, code synthesis, theorem proving), this tells you that task complexity isn't one-dimensional. You can't just measure difficulty by horizon depth; you need to understand the logical expressiveness required and budget training accordingly. This prevents wasting compute on models that'll fail when facing slightly more complex logical constructs in production.
Research Context
Prior work applied RL to LLM reasoning but lacked systematic ways to isolate what makes tasks harder. This paper fills that gap by decoupling horizon (proof depth) from expressiveness (what logical operators exist), creating a controlled scaling study. It advances our understanding of LLM scaling laws beyond raw model size into task-structure space, enabling more principled decisions about when RL fine-tuning is worth the compute investment.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::