Can RL Teach Long-Horizon Reasoning to LLMs? Expressiveness Is Key

Tianle Wang; Zhaoyang Wang; Guangchen Lan; Xinpeng Wei; Sipeng Zhang; Guanwen Qiu; Abulhair Saparov

Source-linked AI summary

Can RL Teach Long-Horizon Reasoning to LLMs? Expressiveness Is Key

Tianle Wang, Zhaoyang Wang, Guangchen Lan, Xinpeng Wei, Sipeng Zhang, Guanwen Qiu, Abulhair Saparov

arXiv:2605.06638v3May 7, 2026cs.AIcs.CL

TL;DR

Long-horizon reasoning remains difficult to study systematically, and its limitations may reflect the autoregressive transformer architecture. ScaleLogic independently controls proof depth and logical expressiveness, showing that training compute scales with depth and richer training improves downstream transfer.

Problem
Existing RL reasoning domains lack clean, scalable control over horizon and difficulty, limiting systematic evidence about how training scales with long-horizon reasoning.
Method
ScaleLogic is a verifiable synthetic reasoning framework that independently controls proof-tree depth and logical expressiveness across increasingly rich logical operators.
Results
+10.66 percentage points is the largest reported downstream gain, while training compute follows a depth power law with exponents rising from 1.04 to 2.60 as expressiveness increases.
Takeaways & Limitations
Training-data expressiveness shapes both RL scaling and compute-efficient transfer, indicating long-horizon reasoning limitations are not fundamental to the underlying architecture.
Takeaways & Limitations
Deeper training extends the solvable range approximately linearly but does not eliminate the horizon limit, with performance approaching random at roughly three times training depth.

Abstract

from arXiv · show

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. Observed LLM shortcomings in long-horizon reasoning have raised the prospect that they are fundamental to the autoregressive transformer architecture. To address this, 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. More broadly, our results demonstrate that LLM shortcomings in long-horizon reasoning are not fundamental to the underlying architecture, and can be addressed by improved training methodology and data.

1 Introduction

SCALELOGIC provides a scalable, synthetic environment with explicit control over reasoning horizon and logical expressiveness, addressing limitations in existing RL reasoning data. Experiments show that training effort scales superlinearly with expressiveness and that expressive training improves downstream transfer.

Motivation: Existing mathematics and coding domains often provide verifiability but limited control over reasoning horizon and difficulty, while high-quality problems are expensive to curate.Scalable long-horizon training requires exact verifiability, fine-grained difficulty control, and data available at scale.
Scaling: RL training steps T required to reach 90% validation accuracy follow T ∝ D^γ with R^2 > 0.99, while γ rises from 1.04 to 2.60 as expressiveness increases.The relationship holds over the observed proof-tree depth range.
Downstream transfer: +10.66 percentage points is the largest reported improvement in mean accuracy across eight downstream mathematics and general reasoning benchmarks over the base model.The most expressive setting produces this improvement, while less expressive settings plateau early.
Framework: SCALELOGIC offers exact verifiability, low-cost automatic generation, and independent control over proof-planning horizon and logical expressiveness.Each problem provides facts and candidate conclusions, requiring the model to identify the logically derivable conclusion.
Scaling: The power-law relationship holds across multiple RL methods, and curriculum-based training substantially improves scaling efficiency.

2 Related Work

Prior work documents sharp degradation in LLM reasoning as horizons grow, while scaling-law and RLVR research studies compute allocation and post-training improvements. Existing RL reasoning datasets often lack fine-grained difficulty control and scalable data generation, motivating synthetic task families such as ScaleLogic.

Long-horizon Reasoning Limitations: LLMs often show sharp performance degradation as reasoning horizons increase, with several benchmarks reporting steep declines at sufficiently large horizons.Graph-based reasoning models can perform well within limited complexity regimes before performance drops abruptly.
Scaling in LLMs: Scaling-law research established power-law relationships involving model scale, data volume, and training compute, later extending computation-based scaling to decoding and RL post-training.Test-time scaling improves reasoning by allocating additional computation during decoding.
RL for LLM Reasoning: RL with verifiable rewards, supported by optimizers such as GRPO, has enabled large-scale RL post-training and long chain-of-thought reasoning.The cited work positions RLVR as a promising paradigm for reasoning-oriented post-training.
RL for LLM Reasoning: Most RL reasoning work focuses on mathematics and programming, where limited problems, human-curated solutions or tests, and coarse difficulty control constrain sustained scaling.These limitations make RL performance dependent on the collected training data.
Synthetic Data for Post-training: Synthetic data research has progressed from task-specific logical reasoning settings toward controllable task families including SAT and graph reasoning.Examples include Knights and Knaves, SAT, and G1 graph reasoning tasks.

3 Method

SCALELOGIC generates synthetic logical reasoning problems with independently controlled proof depth, candidate count, and logical expressiveness. Its proof-tree construction supports exact answer verification for reinforcement learning, while a hierarchy extends implication-only reasoning through conjunction, negation, disjunction, and universal quantification.

Problem construction: Each instance contains literals and rules organized into proof trees, with one intact proof identifying the derivable candidate conclusion.Remaining candidates are made non-derivable by removing or polarity-flipping one axiom, with distracting rules added without creating valid derivations.
Difficulty control: The structural variables B and D control candidate ambiguity and proof-chain length, respectively, while final answers remain exactly verifiable without supervising full proofs.This makes the environment suitable for reinforcement learning with verifiable rewards.
Logical expressiveness: Logical expressiveness increases through five strict-superset settings, beginning with implication-only rules and adding conjunction, negation, disjunction, and quantification.Conjunction requires multiple premises, negation introduces signed literals, disjunction creates alternative consequents, and quantification applies rules across entities.
Scaling analysis: γ rises monotonically from 1.04 in Implication-only to 2.60 with + Quantification as training steps scale with reasoning depth D.The figure reports the relationship T ∝ D^γ for reaching the 90% accuracy threshold.
Logical expressiveness: Quantified rules apply to any entity by instantiating universal variables with concrete entities and checking the instantiated antecedents before inference.For example, ∀X(cat(X) →mammal(X)) derives mammal for entities established as cats.

4 Experiments

Experiments show that RL training cost grows polynomially with reasoning depth, with steeper scaling for more expressive logic. Expressive synthetic training improves downstream transfer, curriculum improves scaling efficiency, power-law scaling generalizes across RL methods, and deeper training extends—but does not remove—the reasoning horizon.

Experimental setup: Training compute T is the number of RL steps needed to reach held-out Pass@1 threshold µ = 90%.Each configuration uses a separate model evaluated after every RL training step.
Scaling with complexity: T follows T = a · D^γ across all five expressiveness levels, with R^2 > 0.99, indicating polynomial rather than exponential growth with depth.The power-law fit outperforms an exponential fit by ∆AIC ≥+7.1 across settings.
Scaling with complexity; Downstream transfer: γ rises monotonically from 1.04 ± 0.03 for Implication-only to 2.60 ± 0.06 for + Quantification, while + Quantification reaches 60.05% downstream accuracy at 414 steps.This corresponds to roughly 2× versus about 6× higher cost when doubling depth, and a 10.66-point gain over the 49.39% base model.
Training distribution and RL algorithms: Curriculum training achieves γ = 1.33 versus γ = 1.70 for uniform and γ = 2.36 for difficult-only training, while all tested RL algorithms retain power-law scaling.In the + Quantification setting, curriculum lowers γ from 2.60 with uniform training to 2.30.
OOD generalization: Models trained at greater depths preserve higher accuracy on unseen harder depths, with the two deepest models collapsing near random performance at roughly 3D_train.Deeper training extends the solvable range approximately linearly but does not eliminate the horizon limit.

5 Conclusion · Appendix · L Qualitative Examples

SCALELOGIC provides a controlled framework for studying how RL post-training scales with proof depth and logical expressiveness. The conclusion emphasizes established scaling trends and identifies larger models, broader RL regimes, and richer logical fragments as directions for future work.

5 Conclusion: SCALELOGIC independently controls reasoning depth and logical expressiveness to study RL post-training under varying task complexity.The framework is presented as a synthetic logical reasoning environment for controlled empirical analysis.
5 Conclusion: T ∝ D^γ with R^2 > 0.99 across settings, while γ increases monotonically from 1.04 to 2.60 as logic becomes richer.These results characterize how training compute scales with proof depth and logical expressiveness.
5 Conclusion: Logical expressiveness governs both RL training dynamics and downstream transfer.The passage identifies expressiveness as affecting more than training compute scaling alone.
5 Conclusion: The study empirically characterizes RL scaling in long-horizon reasoning under controlled conditions.The conclusion frames the work as a controlled characterization rather than a complete account of all scaling regimes.
5 Conclusion: Future work should test whether the observed scaling trends persist for substantially larger models and broader RL training regimes.This is identified as the first major open direction.
5 Conclusion: The expressiveness hierarchy should be extended to richer fragments, including equality, higher-order reasoning, non-monotonic reasoning, and more realistic multi-entity relational settings.The passage presents these logical extensions as a second major direction for future work.

A Limitations · B Broader Impact

The study’s evidence is limited by model scale, architecture coverage, and the restricted depth range used to fit scaling laws. Its controlled synthetic setting avoids real-world sensitive data while informing compute-efficient post-training design.

A Limitations: All experiments use Qwen3-4B, with only a subset replicated on Qwen3-8B for cross-scale consistency.The passage identifies the replication in Appendix I.5.
A Limitations: It remains unclear whether the observed scaling laws generalize to substantially larger models or different architectures.
A Limitations: The fitted relationship T = a · D^γ uses limited depth values for each expressiveness level.
A Limitations: Computational constraints prevented extending the depth range used to evaluate the power-law relationship.
B Broader Impact: The framework studies RL scaling in a controlled synthetic setting with abstract logical literals and randomly sampled entities and predicates.
B Broader Impact: The study does not involve real-world sensitive data or content that could be directly misused.
B Broader Impact: Understanding how training complexity and data expressiveness govern RL scaling may help design more compute-efficient post-training pipelines.

C Task Generation Procedure … F Full Implementation Details

ScaleLogic generates logically controlled multiple-choice reasoning problems by constructing proof trees backward, corrupting non-target candidates, and rendering randomized symbolic instances as natural-language prompts. Its expressiveness levels progressively add conjunction, negation, disjunction, and quantification, while shortcut controls and Z3 audits support reliable evaluation.

C Task Generation Procedure: The pipeline constructs candidate proof trees backward to target depth D, using expressiveness flags Φ to restrict available logical operators and rule forms.Open leaves are processed depth-first; leaves at depth D become axioms, while conjunction and disjunction can create multi-premise or multi-conclusion rules.
C.2 Multi-Choice Instance Assembly: Each B-choice instance preserves one provable goal, corrupts one uniformly selected axiom in every other proof tree, and may add up to M=5 distractor rules under a BD rule-application cap.Negation-enabled corruptions either remove an axiom with probability premove=0.5 or flip one literal’s polarity; distractors use fresh predicates on at least one side.
C.3 Natural Language Conversion: Natural-language conversion independently randomizes entity names and predicate strings, shuffles facts and candidates, and labels the unique provable candidate as the answer.Entities draw from a fixed pool of 26 names, while predicates use independently resampled random 5-letter strings and predefined factual, grounded-rule, and quantified templates.
D.1 Implication-only: Implication-only reasoning reduces validity checking to repeated rule application and path-finding in simple directed graphs.Conjunction instead requires jointly tracking multiple supporting literals before applying a rule.
D.3 + Negation: Negation adds polarity tracking and enables non-target candidates by flipping an intermediate literal, while the construction excludes hypothetical derivations such as proofs by contradiction.Polarity flips preserve consistent surface randomization while breaking the corresponding derivation.
D.4 + Disjunction: Disjunction produces multiple candidate conclusions per rule, requiring proof-tree edges to generalize into hyperedges and alternatives to be resolved by contradiction or shared downstream conclusions.The generator supports disjunction through multi-conclusion rules with arity set to 2 in experiments.
D.5 + Quantification: Universal quantification permits rules applying to any entity, and experiments vary entity count from single-entity problems to multi-entity settings.Reusable quantified templates are instantiated with fresh entities and removed after covering all available entities; instances contain at most two entities.
E Validity of the Construction: Shortcut controls randomize predicates, entity mappings, corruption locations, polarity flips, and ordering, while Z3 audits sampled instances by testing entailment for every candidate.These procedures target lexical, world-knowledge, position, polarity, and ordering cues, and independently verify label correctness.

F.1 Experimental Details … H.2 Sensitivity to the Accuracy Threshold

The appendices specify the training, evaluation, curriculum, and prompting procedures, then test whether the reported scaling laws remain robust across model fits and accuracy thresholds. These checks support power-law scaling and preserve the monotonic relationship between logical expressiveness and the fitted exponent.

F.1 Experimental Details: RL post-training uses verl with non-thinking Qwen3-4B and Qwen3-8B on 8×B200 180G GPUs, following the Section 3.3 recipe unless specified otherwise.
F.1 Experimental Details: Downstream evaluation uses Qwen decoding settings of T = 0.7, top-p = 0.8, top-k = 20, an 8192-token limit, and Avg@8 as the primary aggregate metric.
F.1 Experimental Details: OOD evaluations use a 32,768-token response limit to prevent deeper problems from being truncated by generation-length constraints, while keeping other decoding settings unchanged.
F.2 Curriculum Implementation: The curriculum samples depths up to Dcur, filters deeper instances, and increases Dcur by Δ whenever rolling training accuracy reaches 70%, until Dmax.
G Prompt Templates: The logical-reasoning prompt shuffles axioms, rules, and candidate statements, asks for the uniquely derivable statement, and requires an <answer>...</answer> response.
H Scaling Robustness: Five complementary checks assess whether the main scaling claims depend on key design or analysis choices.
H.1 Power-Law vs. Exponential Fit Comparison: Across all five expressiveness settings, power-law fits have higher R2 and lower AIC than exponential fits, with ΔAIC ≥ +7.1; exponentials overshoot at large depths.
H.2 Sensitivity to the Accuracy Threshold: R2 > 0.99 holds under both 90% and 85% accuracy thresholds, while γ remains monotonically increasing in expressiveness and shifts to 1.07 → 2.73 at 85%.The relative ordering of all five fitted exponents is preserved exactly.

H.3 Different Metrics of Training Compute … I.3 Curriculum at the Most Expressive Setting

Across alternative compute measures, random seeds, expressiveness confounds, candidate counts, detailed downstream results, and curriculum training, the paper finds that its scaling conclusions remain robust while efficiency depends on training design. Candidate branching shows sub-quadratic compute scaling with diminishing transfer returns, and curriculum training reduces the exponent even at the most expressive setting.

H.3 Different Metrics of Training Compute: R^2 > 0.98 holds for all four alternative compute measures, preserving the expressiveness ranking while shifting exponents upward relative to training steps.The measures are generated tokens, kept-batch tokens, Kaplan-rule FLOPs, and wall-clock GPU-hours.
H.4 Variability across Random Seeds: γ = 1.72 with pooled multi-seed runs, closely matching the single-seed estimate and confirming reliable scaling measurements.The pooled fit reports R2 = 0.991, while the single-seed comparison is within 0.02.
H.5 Multi-Entity Reasoning as a Potential Confounder: At most 2 steps separate single-entity and two-entity variants across D ∈ {6, 8, 10}, with no systematic depth trend.The ablation disables universal quantification and rule reuse, isolating the multi-entity contribution under + Disjunction.
H.5 Multi-Entity Reasoning as a Potential Confounder: Multi-entity design contributes negligibly to training difficulty, so the elevated + Quantification exponent reflects universal quantification and rule reuse.This conclusion follows from the single- versus multi-entity ablation in the tested depth range.
I.1 Candidate Count Scaling: γB = 1.41 ± 0.10 with R2 = 0.984, and the power-law fit outperforms an exponential fit by ∆AIC = +7.0.This result concerns candidate count B at fixed D = 8 under + Quantification; its exponent is below the same-setting depth exponent γ = 2.60.
I.1 Candidate Count Scaling: 52.5% at B = 2 rises to 55.7% at B = 4 (+3.2 pp), followed by only +0.6 pp from B = 4 to B = 6.Mean downstream accuracy averages the eight benchmarks of Section 4.3, and Table 8 provides the full benchmark-by-setting results.
I.3 Curriculum at the Most Expressive Setting: γ = 2.30 under curriculum training versus γ = 2.60 under uniform training at + Quantification, with R2 = 0.998 in both cases.The reduction is ∆γ = −0.30, comparable to the + Conjunction reduction of ∆γ = −0.37 from 1.70 to 1.33.

I.4 Data Distribution Shapes Long-CoT Emergence · I.5 Cross-Scale Replication on Qwen3-8B

Curriculum training accelerates the emergence of long reasoning traces by reducing depth-dependent delays, while uniform and difficult-only distributions prolong short-response, high-entropy behavior. On Qwen3-8B, the expressiveness-dependent power-law scaling pattern replicates with smaller exponents and similar downstream transfer gains.

I.4 Data Distribution Shapes Long-CoT Emergence: Curriculum training substantially reduces delays in long-CoT emergence across target depths.Runs at different depths enter the long-CoT regime within a relatively narrow range of training steps.
I.4 Data Distribution Shapes Long-CoT Emergence: Curriculum training couples earlier length expansion with a sharper entropy drop and earlier validation-accuracy improvement.These trajectory changes distinguish curriculum training from uniform sampling across response length, entropy, and validation accuracy.
I.4 Data Distribution Shapes Long-CoT Emergence: Uniform and difficult-only training remain longer in a short-response, high-entropy regime before transitioning to long-CoT behavior.Curriculum instead provides a smoother path by learning useful patterns on shallower instances before extending them to deeper instances.
I.4 Data Distribution Shapes Long-CoT Emergence: Figure 11 compares response length, entropy, and validation accuracy across three data distributions and target depths.The figure presents training trajectories for the + Conjunction setting, with shared depth legends and row-specific axis ranges.
I.5 Cross-Scale Replication on Qwen3-8B: R^2 ≥0.98: all five expressiveness settings on Qwen3-8B follow clean power laws in proof depth.The fitted exponent γ increases monotonically from 0.99 for Implication-only to 2.53 for + Quantification.
I.5 Cross-Scale Replication on Qwen3-8B: γ = 1.52 vs. 1.72 under + Conjunction: Qwen3-8B has systematically smaller exponents than the 4B model.The relative ordering across expressiveness settings and their qualitative dependence on expressiveness remain unchanged.
I.5 Cross-Scale Replication on Qwen3-8B: +9.60 percentage points: Qwen3-8B trained at D = 14 with + Quantification raises the eight-benchmark average from 50.93% to 60.53%.This indicates a downstream transfer trend similar to that observed for Qwen3-4B.

J Full Training Dynamics of the Main Experiments

The full training trajectories track response length, actor entropy, and validation accuracy across five settings. Validation accuracy reaches 0.9 for all trained depths, while deeper problems require more training steps and response length generally grows during training, especially with greater depth and expressiveness.

Training trajectories: The trajectories track mean response length, actor entropy, and validation accuracy as functions of training step across five experimental settings.Validation accuracy is the same quantity used to define training compute T in the main paper.
Training dynamics: Validation accuracy eventually reaches 0.9 for all trained depths, but deeper problems systematically require more training steps to reach that threshold.These threshold-reaching points define the scaling curves reported in the main text.
Training dynamics: Response length tends to grow during training, particularly at larger depths and in more expressive settings.The passage reports this trend as part of the consistent dynamics observed across the five settings.

K Evaluation of Frontier LLMs on SCALELOGIC

Frontier LLM performance on SCALELOGIC declines as reasoning depth increases, including for reasoning models. Targeted RL enables a 4B model to match the strongest frontier baseline at D = 28, while the most expressive tasks remain challenging overall.

Evaluation setup: Six frontier LLMs were evaluated on + Quantification tasks with B = 4 across depths D ∈ {4, 6, . . . , 32}, using 30 sampled tasks per depth.The evaluation included both non-thinking LLMs and reasoning models.
Depth scaling: All evaluated models degrade as reasoning depth increases, with non-reasoning models reaching near-random accuracy by D = 8 or D = 20.GPT-4o reaches near-random accuracy by D = 8, while DeepSeek-V3.1 does so by D = 20.
Depth scaling: Qwen3.5-397B-A17B remains above random at D = 32, although reasoning models also show marked degradation beyond D = 12.Reasoning models are more robust than non-reasoning LLMs but still degrade substantially at larger depths.
Overall challenge: The most expressive SCALELOGIC tasks remain challenging even for frontier reasoning models.This conclusion follows from the observed performance degradation on the + Quantification setting as depth increases.
Targeted RL: 40% accuracy at D = 28 was achieved by the RL-trained 4B model, matching only Qwen3.5-397B-A17B among the evaluated frontier models.Targeted RL substantially closes the in-distribution gap between the 4B model and much larger frontier models evaluated zero-shot.

L Qualitative Examples

On MATH500 #80, RL post-training markedly improves success and changes the model’s reasoning behavior. The trained model searches for hidden cases, branches systematically, and verifies domain constraints, whereas the base model stops after the discriminant case.

Performance comparison: 7/8 rollouts solved MATH500 #80 by the RL-trained model, versus 0/8 by the base model.Figure 15 compares Qwen3-4B with RL on synthetic logic against Qwen3-4B without RL.
Reasoning behavior: The trained model finds the second-root case, splits by k > 0 and k < 0, and uses Vieta’s formulas and f(−2) to verify valid-domain solutions.This systematic analysis establishes that every negative integer k works, in addition to k = 8, yielding 501 values.
Reasoning behavior: The base model stops after considering only the zero-discriminant case and answers 2, missing solutions arising when only one of two real roots lies in the logarithm domain.The trained model instead enumerates alternatives and checks domain-specific configurations.