SCALELOGIC: Is Expressiveness the Secret to Unlocking Long-Horizon Reasoning?

TL;DR

Common wisdom suggests that Transformers are fundamentally "bad" at long-chain reasoning due to their autoregressive nature. This paper challenges that notion by introducing SCALELOGIC, a framework showing that RL can indeed teach long-horizon planning. The catch? The logical expressiveness of your training data dictates how efficiently the model learns. By scaling from simple "if-then" rules to complex first-order logic, the authors discovered a strict Power Law ($T\propto D^{\gamma }$) governing training compute, where more complex logic significantly boosts downstream transfer to real-world math and science problems.

The "Wall" of Long-Horizon Reasoning

We have all seen it: a model solves a 3-step logic puzzle effortlessly but trips over its own feet when the same puzzle is extended to 10 steps. This "horizon limit" has led many researchers to believe that Transformers lack the iterative "search" capability required for deep proofs.

The authors of this paper argue that we haven't been able to diagnose this properly because our training data (like MATH or Code) is messy. We can't easily turn a "difficulty knob" to see exactly why RL fails. SCALELOGIC provides those knobs:

1. Depth (D): The number of steps in a proof.
2. Expressiveness ($\Phi$): The operators used (AND, OR, NOT, FOR ALL).

Methodology: Controlling the Reasoning Frontier

The core of SCALELOGIC is a Backward Construction algorithm. Instead of starting with facts and seeing what happens, the generator starts with a conclusion and builds the necessary premises "downward" until the target depth $D$ is reached.

The Expressiveness Hierarchy

The researchers tested five distinct levels of logic:

• Implication-only: Simple $AoB$ chains.
• + Conjunction: $A\wedge BoC$ (Coordinating multiple premises).
• + Negation: Handling $egA$.
• + Disjunction: $AoB\vee C$ (Handling uncertainty/branching).
• + Quantification: $\forall X(P(X)oQ(X))$ (Abstract, first-order rules).

Figure 1: Comparison between simple implication-only reasoning (left) and the highly expressive +Quantification setting (right).

Key Insight: The Power Law of Effort

The most striking discovery is that RL training compute ($T$) is a polynomial function of depth ($D$). However, the cost of depth is not constant.

In the simplest logic (Implication-only), the exponent $\gamma$ is 1.04—almost linear. But as soon as you add complexity like universal quantification, $\gamma$ jumps to 2.60. This means doubling the proof depth in a complex environment doesn't just double the training time; it increases it by over 6x.

Figure 2: The scaling exponent $\gamma$ increases monotonically with the expressiveness of the logic.

Why Should We Care? Downstream Transfer

You might ask: "Who cares about synthetic 'Alice is a cat' puzzles?"

The authors demonstrate that this synthetic training is a powerful "gym" for real-world reasoning. Models trained on the +Quantification setting didn't just get better at the synthetic tasks; they saw a massive +10.66% boost across 8 major benchmarks including AIME and GPQA.

Crucially, models trained on "easier" logic (like Implication-only) plateaued early. The complexity of the logic, rather than just the number of steps, is what forces the model to learn transferable "thinking" patterns.

Figure 3: Downstream performance continues to rise for expressive data while plateauing for simpler logic.

Critical Analysis & Future Outlook

The Curriculum Advantage

The paper also proves that Curriculum Learning is highly effective here. By starting with shallow proofs and gradually increasing depth, the scaling exponent $\gamma$ was reduced (e.g., from 1.70 to 1.33). This suggests that "learning to crawl before you run" is essential for RL-based reasoning.

Limitations

While the results are robust for Qwen3-4B and 8B, the "asymptotic" nature of these power laws for 70B+ models remains to be seen. Furthermore, the environment is still symbolic; it doesn't yet capture the "soft" reasoning or nuance of natural language argumentation.

Conclusion

SCALELOGIC proves that the "Transformer reasoning wall" is movable. By providing LLMs with a high-expressivity "logic gym" and using RL to encourage long-chain verification, we can push the boundaries of what these models can solve, moving them closer to human-level proof-planning capabilities.