acceptodds
Under review as a conference paper at ICLR 2027

How Deep Can LLMs Learn to Reason? Expressiveness Is Key

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. 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 formal system. 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 follows a power law with respect to reasoning depth (, ), and the scaling exponent increases monotonically with expressiveness, from to . On downstream mathematics and general reasoning benchmarks, more expressive training settings yield both larger performance gains (up to 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 suggest that LLM shortcomings in long-horizon reasoning are not fundamental to the underlying architecture, and could be addressed by improved training methodology and data.

Primary area:
reinforcement learning
Keywords:
Large Language Models, Reinforcement Learning, Reasoning, Long-Horizon Reasoning, Synthetic Data

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_jxUNOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces SCALELOGIC, a synthetic RL environment that varies proof depth and the set of available logical operators. On Qwen3-4B, the authors find that the number of RL steps needed to reach 90% validation accuracy is well fit by a power law in proof depth, with a larger exponent for richer logical settings. They also report that training on the richer settings transfers better to eight math and science benchmarks, and that curriculum training improves scaling efficiency. The paper includes partial replications across RL algorithms and model families, as well as several controls for prompt length, surface form, alternative rewards, and logical validity.

Critical strengths
  1. SCALELOGIC is a useful experimental framework. It provides cheap generation, exact verification, explicit depth control, and more interpretable task variation than standard math or coding datasets. The Z3 audit and randomized predicates, axiom order, and answer order make obvious shortcut explanations less likely.

  2. The experimental coverage is unusually strong. The paper studies multiple logical settings, RL algorithms, curricula, model sizes, OOD depths, downstream tasks, proof faithfulness, and several potential confounders. The operator-swap and surface-form controls are particularly helpful.

  3. The downstream gains are meaningful rather than confined to the synthetic task. The strongest 4B model improves the eight-benchmark average from 49.39 to 60.05, with gains across most benchmarks. The SATURN comparison also uses the same base model and RL recipe, which is much fairer than copying numbers from the original paper.

Critical weaknesses
  1. The evidence supports a power-law fit over the observed range, but not yet a general scaling law. Most points in the central experiment come from one run per configuration, the depth ranges are short and selected after excluding saturated settings, and only power-law and exponential alternatives are compared. The three-seed check covers only the conjunction setting. High R^2 over five or six nearby points is therefore weaker evidence than the abstract suggests. This could be addressed with held-out-depth prediction and uncertainty estimates for the main five exponents.

  2. “Expressiveness” is not fully isolated from structural complexity. The hierarchy cumulatively changes rule arity and proof branching; the quantification condition additionally introduces two entities, predicate reuse, and rule reuse. The multi-entity ablation disables quantification and reuse, so it does not separate the effect of universal quantification from reuse. The operator-swap experiment helps for negation and disjunction but does not resolve this final step. A matched-graph ablation that toggles quantification and reuse separately is needed before attributing the exponent increase specifically to logical expressiveness.

  3. The claim of more compute-efficient downstream transfer is not established by Figure 3b. That comparison matches approximately 100 optimizer steps, while prompt and response lengths differ substantially across settings. Table 6 itself shows that changing from steps to tokens or FLOPs changes the fitted exponents. The downstream comparison should therefore be repeated at matched generated tokens or FLOPs. The “matched depth” control is also approximate because implication-only uses D = 16 while the other settings use D = 12.

  4. The downstream baseline coverage is narrow. The paper cites Logic-RL, SynLogic, Enigmata, Reasoning Gym, and G1, all of which already demonstrate transfer from synthetic verifiable reasoning after RL, but compares experimentally only with SATURN. SCALELOGIC’s controlled scaling analysis remains novel, but the stronger claim that its expressiveness design is responsible for superior transfer would benefit from at least one diverse synthetic-logic baseline, such as SynLogic or Enigmata, retrained with the same model, RL algorithm, and token budget.

  5. The architectural conclusion is overstated. Figure 5 shows that performance still approaches random near D_test / D_train = 3. Moreover, SCALELOGIC uses unique derivations, arity two, at most two entities, and a restricted logical fragment. The results show that RL can extend the reasoning horizon within this environment; they do not establish that long-horizon limitations are not architectural.

Questions for authors
  1. Do the five power-law models predict convergence cost at held-out depths that were excluded from fitting?

  2. What happens when universal quantification and rule reuse are toggled independently while matching rule count, proof size, and prompt length?

  3. Does the monotonic downstream ordering remain under matched generated-token or FLOP budgets rather than matched optimizer steps?

  4. Can the authors compare against SynLogic, Enigmata, or Logic-RL under the same Qwen3-4B and DAPO setup?

5 comments
AuthorsOpenReview ↗

Response to Reviewer jxUN (1/4)

We sincerely thank the reviewer for the detailed review. We address each point below and highlight the corresponding revisions in the manuscript in blue. We would welcome any follow-up in case there are any remaining concerns, so that we may have the opportunity to address them during the discussion period.

W1/Q1 Robustness of the power-law fit.

We appreciate the reviewer's concern and agree that additional robustness analyses of the power-law fit would strengthen our conclusion.

First, we have expanded Appendix G.1 to include a linear model (T=a+cDT=a+cD) alongside the original power-law and exponential models. All three models have two free parameters and are fitted by least squares. The corresponding results are summarized in the table below.

Table: Power-law (T=a⋅DγT = a \cdot D^{\gamma}), exponential (T=a⋅ebDT = a \cdot e^{bD}) and linear (T=a+cDT = a + cD) fits across expressiveness levels. All models have two free parameters and are fitted by least squares. ΔAICexp=AICexp−AICpow\Delta\text{AIC} _ {\text{exp}} = \text{AIC} _ {\text{exp}} - \text{AIC} _ {\text{pow}} and ΔAIClin=AIClin−AICpow\Delta\text{AIC} _ {\text{lin}} = \text{AIC} _ {\text{lin}} - \text{AIC} _ {\text{pow}}; positive values favor the power law.

SettingPower lawPower lawExponentialExponentialLinearLinearΔAICexp\Delta\text{AIC} _ {\text{exp}}ΔAIClin\Delta\text{AIC} _ {\text{lin}}
γ±SE\gamma \pm \text{SE}R2R^2b±SEb \pm \text{SE}R2R^2c±SEc \pm \text{SE}R2R^2
Implication-only1.05±0.031.05 \pm 0.030.9950.9950.023±0.0030.023 \pm 0.0030.9160.9160.87±0.030.87 \pm 0.030.9970.997+23.4+23.4−2.7-2.7
+ Conjunction1.67±0.051.67 \pm 0.050.9930.9930.113±0.0080.113 \pm 0.0080.9670.9673.70±0.343.70 \pm 0.340.9610.961+13.9+13.9+15.4+15.4
+ Negation1.77±0.041.77 \pm 0.040.9960.9960.120±0.0080.120 \pm 0.0080.9720.9725.03±0.505.03 \pm 0.500.9550.955+17.5+17.5+21.7+21.7
+ Disjunction2.11±0.092.11 \pm 0.090.9930.9930.174±0.0240.174 \pm 0.0240.9280.92814.08±1.2814.08 \pm 1.280.9780.978+14.1+14.1+6.9+6.9
+ Quantification2.60±0.062.60 \pm 0.060.9980.9980.318±0.0310.318 \pm 0.0310.9640.96428.55±4.7428.55 \pm 4.740.9430.943+17.6+17.6+20.4+20.4

We report the following findings in Appendix G.1 of the revised manuscript:

The power-law model outperforms the exponential model across all five expressiveness settings (ΔAICexp≥+13.9\Delta\mathrm{AIC} _ {\mathrm{exp}}\geq+13.9) and the linear model in four of five settings (ΔAIClin≥+6.9\Delta\mathrm{AIC} _ {\mathrm{lin}}\geq+6.9). The only exception is Implication-only, where the linear model achieves a slightly better fit (ΔAIClin=−2.7\Delta\mathrm{AIC} _ {\mathrm{lin}}=-2.7), consistent with its near-linear power-law exponent (γ=1.05\gamma=1.05). However, the linear model cannot capture the superlinear growth observed in the more expressive settings. Overall, the power-law model is the only one that achieves R2>0.99R^2 > 0.99 across all five settings.

Second, we conducted an additional held-out-depth prediction experiment. For each expressiveness setting, we fit the power-law, exponential, and linear models using only the shallower depths, reserving the two deepest depths for evaluation. The results are summarized in the table below and visualized in Figure 7 of the revised manuscript (Appendix G.1).

Table: Held-out-depth prediction. Mean absolute percentage error (MAPE, %) is computed over the two deepest held-out depths for each setting.

SettingPower lawExponentialLinear
Implication-only10.0136.76.6
+ Conjunction14.350.931.0
+ Negation9.268.131.0
+ Disjunction14.8135.222.7
+ Quantification7.287.941.7
Average11.195.826.6

We discuss these findings in Appendix G.1 as follows:

The power-law predictions closely follow the observed training costs at held-out depths across all five expressiveness settings, achieving an average mean absolute percentage error (MAPE) of 11.1%, substantially lower than 26.6% for the linear model and 95.8% for the exponential model. These results provide additional evidence that the power-law relationship captures the observed scaling behavior beyond the depths used for fitting.

AuthorsOpenReview ↗

Response to Reviewer jxUN (2/4)

Continuation of W1/Q1.

We have also updated Section 4.2 of the main text to highlight these additional analyses:

The power-law model generally outperforms exponential and linear fits in fitting accuracy (Appendix G.1). To further validate the scaling behavior, we fit each model on all but the two deepest data points and predict the held-out depths. The power-law model achieves substantially lower prediction error (11.1% average MAPE, compared to 26.6% for linear and 95.8% for exponential), further supporting the observed power-law scaling behavior.

For uncertainty estimation, we report the standard errors of the fitted exponents in Table 4 of Appendix G.1, with the corresponding error bars shown in Figure 2b of the main paper. We have also updated the caption of Figure 2 to reference these numerical values explicitly:

Error bars denote ±1\pm 1 standard error of the fitted exponent, with the corresponding numerical values reported in Table 4 (Appendix G.1).

Finally, we agree that additional multi-seed experiments across different expressiveness settings would further strengthen the robustness of our scaling results. However, due to computational constraints, a full multi-seed replication across all settings and depths is difficult to complete in the limited time available in the discussion period. In particular, some of the deeper configurations require several days of training on 8 GPUs, making experiments very expensive. We are currently running additional experiments where resources allow, and we will update our response with new results once they become available.

W2/Q2 Ablation on Reuse in Quantification.

We appreciate the reviewer's suggestion and agree that additional ablations would help clarify the effects of quantification and predicate/rule reuse on scaling behavior. To address this, we introduce an additional variant, + Quantification w/o reuse, which preserves universal quantification but disables predicate and rule reuse during problem generation. We compare this variant with the original + Quantification setting and the multi-entity + Disjunction setting as a reference. We have added this ablation study to Appendix G.5 of the revised manuscript, with the results summarized in the table below.

Table: Training steps to reach 90% validation accuracy under different quantification and reuse settings. All three settings use two entities. The + Disjunction results are from the multi-entity control in Appendix G.5.

DD+ Disjunction+ Quantification w/o reuse+ Quantification
6212349
8404498
106673186

We discuss the key findings in Appendix G.5 of the revised manuscript as follows:

Removing predicate/rule reuse from + Quantification substantially reduces training cost, bringing it close to that of the multi-entity + Disjunction setting. For example, at D=10D=10, + Disjunction with two entities, + Quantification without reuse, and the original + Quantification setting require 66, 73, and 186 training steps, respectively. This is consistent with our construction: without reuse, universally quantified rules effectively behave like entity-specific rules expressed using different natural-language templates, making their reasoning structures similar to those in + Disjunction.

AuthorsOpenReview ↗

Response to Reviewer jxUN (3/4)

W3/Q3 Downstream transfer under matched compute budgets.

We appreciate the reviewer's suggestion and agree that evaluating downstream performance using generated tokens and training FLOPs would further strengthen our downstream transfer findings. To address this, we added Figure 14 and the following analysis to Appendix H.2 of the revised manuscript:

As shown in Figure 14, the trends are consistent with those based on training steps (Figure 3). In particular, more expressive settings generally achieve larger and more sustained downstream gains as training compute increases. These results suggest that the advantage of more expressive training persists across different measures of training compute.

Furthermore, we repeat the matched-budget comparison in Figure 3b using a fixed training budget of 6×10196\times10^{19} FLOPs. As shown in the table below, downstream performance increases monotonically from 51.71% accuracy for Implication-only to 55.72% for + Quantification, preserving the same trend observed in our original comparison.

Table: Downstream performance (Avg@8) under matched FLOPs.

Training budgetImplication-only+ Conjunction+ Negation+ Disjunction+ Quantification
FLOPs (6×1019)(6\times10^{19})51.7151.9653.9254.2955.72

We have also updated Figure 3b and Section 4.3 of the main text to highlight these findings:

However, the observed downstream trends could be confounded by differences in training compute or inference-time response length. To control for these factors, we further analyze downstream performance as a function of total generated training tokens and training FLOPs, as well as under matched inference-time token budgets (Appendix H.2). The advantages of more expressive settings remain consistent across these comparisons.

For the matched-depth comparison, as noted in the footnote of Section 4.3, the Implication-only setting is relatively easy, so the base model already reaches the 90% validation accuracy threshold at D=12D=12 without training. Thus, the base model could have been used for this setting. However, we instead use the RL-trained checkpoint at D=16D=16, which achieves better downstream performance than the base model. This provides a stronger reference point for Implication-only, making the comparison more conservative with respect to the downstream advantages of more expressive settings.

Reviewer_oZXBOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates how reinforcement learning (RL) scales with reasoning complexity in large language models. The authors introduce SCALELOGIC, a synthetic logical reasoning framework that enables controlled variation along two dimensions: reasoning depth and logical expressiveness. Using this framework, the authors find that the number of RL training steps required to reach a target accuracy follows a power-law relationship with reasoning depth, with the scaling exponent increasing as logical expressiveness grows. The paper further demonstrates that training on more expressive logical reasoning tasks leads to stronger downstream generalization on mathematical and general reasoning benchmarks. Additional experiments examine the effects of curriculum learning, different RL algorithms, and out-of-distribution generalization.

Critical strengths
  • The paper investigates an interesting and fundamental question regarding the scalability of RL for long-horizon reasoning. Although the conclusions are established under controlled experimental settings, the research questions are well defined, and the experimental findings are clearly presented.

  • The authors make substantial efforts to control relevant variables and examine potential confounding factors. In particular, the controlled comparisons across reasoning depth, logical expressiveness, and training budgets, together with additional ablation studies, help strengthen the reliability of the empirical findings.

  • The paper provides an extensive set of experiments, including scaling-law analysis, downstream transfer evaluation, comparisons across RL algorithms, curriculum learning, and out-of-distribution generalization. Overall, the work is well organized, technically solid, and supported by a substantial experimental effort.

Critical weaknesses
  • Although the paper cites several relevant studies, the discussion in the Related Work section remains relatively superficial. In particular, existing works on controllable synthetic reasoning environments and long-horizon RL, such as h1, R-Horizon, SATURN, SynLogic, and Enigmata, share important similarities with the proposed framework in terms of task construction, difficulty control, and reasoning enhancement through RL. However, the paper provides limited analysis of these connections and does not sufficiently clarify how the proposed approach differs from or extends these studies.
  • reasoning depth as a primary measure of task difficulty and investigates how RL training scales with this variable. but with the same proof depth may differ substantially in their actual reasoning complexity, particularly when different logical operators are involved. i hope authors can provide more discussion on this point.
  • moreover, the paper primarily measures training cost using the number of RL training steps required to reach a target accuracy. However, the actual computational cost of a training step may vary considerably across different task configurations, particularly as reasoning depth and logical expressiveness increase. do the authors have more deep consideration of this design?
Questions for authors

please refer to the weakness, I would be open to raising my score if the authors could adequately address these concerns.

5 comments
AuthorsOpenReview ↗

Response to Reviewer oZXB (1/3)

We sincerely thank the reviewer for the detailed review. We address each point below and highlight the corresponding revisions in the manuscript in blue. We would welcome any follow-up in case there are any remaining concerns, so that we may have the opportunity to address them during the discussion period.

W1 Discussion of the related work.

We appreciate the reviewer's suggestion and agree that a more detailed comparison with related work would help to clarify our contributions. In our latest revision, we have expanded Related Work (Section 2) to better distinguish ScaleLogic from previous studies. Specifically, we added the following discussion:

In "Long-horizon Reasoning Limitations" (Line 143-148), we make the following revision to provide a detailed comparison with h1 and R-Horizon.

While these studies primarily aim to improve long-horizon reasoning through training on compositions of existing problems, our goal is to systematically characterize how RL training cost scales with reasoning depth. Moreover, the difficulty of individual subproblems in R-Horizon and h1 is difficult to control, since they come from existing math problems, whereas ScaleLogic provides fine-grained control over logical expressiveness, enabling a more systematic scaling analysis.

In "Synthetic Data for Post-training" (Line 171-178), we make the following revision to provide a detailed comparison with SATURN, SynLogic, Enigmata, etc.

While these studies demonstrate the potential of synthetic data for post-training, they often rely on diverse puzzle suites with heterogeneous task-specific difficulty controls, or NP-complete problems (e.g., SAT and Hamiltonian path), where difficulty can increase sharply and nonuniformly with problem size. These characteristics make it difficult to systematically study how RL training cost scales with a well-defined and well-behaved measure of reasoning complexity. In contrast, ScaleLogic provides independent control over proof depth and expressiveness within a unified framework, with each generated instance being solvable in linear time (Appendix B.4).

AuthorsOpenReview ↗

Response to Reviewer oZXB (2/3)

W2 Reasoning depth and alternative measures of structural complexity.

We appreciate the reviewer's suggestion and agree that further discussion of proof depth and reasoning complexity would help to clarify our experimental design. As shown in Figure 2a (Section 4.2), even when the reasoning depth is controlled, more expressive settings generally require more training steps to reach the same validation accuracy threshold. This observation is consistent with the reviewer's point that problems at the same depth can differ substantially in reasoning complexity across expressiveness settings.

We would like to clarify that our main goal is to investigate whether RL can extend an LLM’s reasoning horizon and how the cost of training scales as the horizon increases. We therefore chose proof depth as a natural and interpretable measure of the reasoning horizon. At the same time, we agree with the reviewer that proof depth alone may not fully characterize differences in problem complexity across expressiveness settings, as problems at the same depth may have different structural properties.

To investigate this potential confounding factor, we further examine whether our scaling results remain consistent under alternative measures of structural complexity. In Appendix G.6, we consider prompt length as an alternative measure of complexity, since more complex proof structures generally require longer prompts. In the revised manuscript, we further extend this analysis to three additional measures of proof complexity: (1) the number of axioms (NN), including both rules and grounded literals; (2) the total number of literals in the axioms, including those within rules (KK); and (3) a measure of rule complexity (AA), defined as A=∑r∣Pr∣⋅∣Cr∣A = \sum _ {r} |P_r| \cdot |C_r|, where PrP_r and CrC_r denote the premises and conclusions of rule rr, respectively. The results are summarized in the table below.

Table: Power-law exponents of training cost under different complexity measures. Each entry reports the fitted exponent ±\pm standard error. All fits achieve R2≥0.988R^2 \geq 0.988.

SettingDepth DDPrompt length LLAxioms NNLiterals KKRule complexity AA
Implication-only1.05±0.031.05 \pm 0.031.33±0.041.33 \pm 0.041.08±0.031.08 \pm 0.031.06±0.031.06 \pm 0.031.05±0.031.05 \pm 0.03
+ Conjunction1.67±0.051.67 \pm 0.052.09±0.062.09 \pm 0.061.72±0.051.72 \pm 0.051.67±0.051.67 \pm 0.051.62±0.051.62 \pm 0.05
+ Negation1.77±0.041.77 \pm 0.042.23±0.032.23 \pm 0.031.82±0.041.82 \pm 0.041.77±0.041.77 \pm 0.041.72±0.041.72 \pm 0.04
+ Disjunction2.11±0.092.11 \pm 0.092.50±0.142.50 \pm 0.142.06±0.092.06 \pm 0.092.01±0.082.01 \pm 0.081.91±0.071.91 \pm 0.07
+ Quantification2.60±0.062.60 \pm 0.063.27±0.103.27 \pm 0.102.61±0.062.61 \pm 0.062.48±0.052.48 \pm 0.052.26±0.052.26 \pm 0.05

We have added Figure 11, Table 8, and the following analysis to Appendix G.6 of the revised manuscript:

As shown in Figure 11 and Table 8, the power-law relationship remains robust across all four measures, with R2≥0.988R^2 \geq 0.988 in every case. More importantly, the fitted exponents increase monotonically with logical expressiveness across complexity measures, preserving the ordering observed under proof depth. These results demonstrate that the observed scaling trends are robust to alternative measures of problem size and structural complexity.

AuthorsOpenReview ↗

Response to Reviewer oZXB (3/3)

W3 Alternate measures of the training cost.

We thank the reviewer for raising this point. We agree that the computational cost per RL step is not constant across all settings, as prompts become longer with increasing depth and expressiveness, and responses also grow during training. We use training steps as our primary measure of training cost because they allow us to examine convergence speed (i.e., the number of gradient updates) independently of differences in sequence length.

To ensure that our findings are not specific to this choice of metric, we have also examined the scaling results under alternative measures of training cost in Appendix G.3 (Table 6 and Figure 9). Specifically, we report results under four alternative measures: the number of generated tokens, the total number of training tokens, training FLOPs, and GPU-hours. Across all four metrics, the power-law relationship remains robust (R2≥0.98R^2 \geq 0.98), and the overall ordering of scaling exponents is preserved: Implication-only has the lowest exponent, followed by + Conjunction / + Negation, + Disjunction, and + Quantification. For example, under training FLOPs, the exponents are 1.44, 2.26, 2.26, 2.62, and 3.12, respectively.

Furthermore, in our latest revision, we have also added Figure 14 and the following analysis to Appendix H.2, examining downstream performance with respect to generated tokens and FLOPs during training:

As shown in Figure 14, the trends are consistent with those based on training steps (Figure 3). In particular, more expressive settings generally achieve larger and more sustained downstream gains as training compute increases. These results suggest that the advantage of more expressive training persists across different measures of training compute.

Together, these findings demonstrate that our main conclusions do not depend on the choice of training steps as the measure of training cost.

Reviewer_PUKoOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how the expressiveness of a formal system influences the RL-based reasoning ability, and the authors introduce SCALELOGIC, a synthetic logical reasoning framework with a controlled, scalable environment. This framework enables independent control over proof depth and expressiveness, raising the suggestion that the RL training steps follow a power law of proof depth, and more expressive training settings yield larger gains on downstream mathematics and general reasoning benchmarks. The authors make three main contributions:

  1. They develop SCALELOGIC that supports exact answer verification, low-cost auto-generation, and independent control over proof depth and logical expressiveness.
  2. The authors identify a power-law relationship between the training effort and reasoning depth, with the scaling exponent increasing with logical expressiveness.
  3. They show that training on more expressive synthetic reasoning tasks yields larger gains on downstream mathematics and general reasoning benchmarks.
Critical strengths
  1. The authors provide a useful insight into the design of synthetic reasoning data: training on more expressive logical tasks leads to larger and more sustained downstream gains. The level of logical expressiveness should be considered during RL training.
  2. The authors provide an operational measure of learning difficulty based on the RL training effort required to reach a target accuracy.
Critical weaknesses
  1. The inference efficiency of the downstream gains from more expressive training settings is not fully established. The authors report that RL with correctness-based rewards substantially increases response length on synthetic tasks, but do not establish how downstream gains relate to test-time compute usage. Although all models use the same maximum output length, this does not guarantee that they generate the same number of tokens. To assess the inference efficiency of these gains, the authors should report downstream accuracy alongside actual generated token counts and compare performance at similar token costs.
  2. The robustness of the scaling results under different random seeds has not been fully verified. Appendix G.4 indicates that each configuration of the main scaling experiment used only one random seed. The authors report a check with multiple seeds in the +Conjunction setting, with similar fitted exponents. However, this does not establish that the exponents and their ordering across the other expressiveness levels are also stable. Since the increase in the scaling exponent with logical expressiveness is the core finding of this paper, supplementary repeated experiments, especially in more expressive settings, will help enhance the credibility of this conclusion.
Questions for authors

For the main questions, please see the weaknesses above. I have one additional clarification question:

  1. On page 4, the authors state that each instance is “oracle-solvable in time linear in the proof size.” Could the authors clarify what information the oracle receives and provide the corresponding algorithm and complexity argument? In particular, does it have access to the proof structure retained during generation, or only the final problem instance?
4 comments
AuthorsOpenReview ↗

Response to Reviewer PUKo (1/2)

We sincerely thank the reviewer for the detailed review. We address each point below and highlight the corresponding revisions in the manuscript in blue. We would welcome any follow-up in case there are any remaining concerns, so that we may have the opportunity to address them during the discussion period.

W1 Inference efficiency of the downstream gains.

We appreciate the reviewer's concern and agree that evaluating downstream performance under the same test-time token budgets would provide a clearer understanding of inference efficiency.

To address this, we conducted an additional experiment using the best-performing checkpoint from each expressiveness setting. Following the budget-forcing approach of s1 [1], we evaluate all models under the same test-time token budgets (2048, 4096, 6144, and 8192 tokens). If a model has not finished its response when reaching the budget, we append "Final Answer \boxed{" to its generated response and let the model complete the final answer using greedy decoding with at most 64 additional tokens. The results are summarized in the table below.

Table: Average downstream performance (Avg@8) and mean response length (tokens) across eight benchmarks under different test-time token budgets BB, using the same budget-forcing protocol for all models.

B=2048B=2048B=2048B=2048B=4096B=4096B=4096B=4096B=6144B=6144B=6144B=6144B=8192B=8192B=8192B=8192
ModelAvg@8LengthAvg@8LengthAvg@8LengthAvg@8Length
Base model48.11121949.62157349.63175349.651883
Impl. only (D=64)(D=64)49.50126651.63172952.00197852.092152
+ Conjunction (D=28)(D=28)48.35129450.83179651.74206651.842243
+ Negation (D=20)(D=20)49.44130452.04180952.58207052.742230
+ Disjunction (D=20)(D=20)50.54133354.51191555.80222456.372406
+ Quantification (D=14)(D=14)50.64141156.81211659.31251960.232738

We discuss these findings in Appendix H.2 of the revised manuscript as follows:

All RL-trained settings outperform the base model across all tested token budgets, and the relative ordering across expressiveness settings remains generally consistent. In particular, + Quantification consistently achieves the strongest downstream performance, with its improvement over the base model increasing from 2.53 percentage points at a budget of 2,048 tokens to 10.58 percentage points at 8,192 tokens. Moreover, even at a budget of 2,048 tokens, + Quantification achieves 50.64% accuracy with a mean response length of only 1,411 tokens, outperforming the base model at a budget of 8,192 tokens (49.65% accuracy with 1,883 tokens). This suggests that the downstream gains cannot be explained simply by longer responses.

We have also updated Section 4.3 of the main text to explicitly highlight these findings:

However, the observed downstream trends could be confounded by differences in training compute or inference-time response length. To control for these factors, we further analyze downstream performance as a function of total generated training tokens and training FLOPs, as well as under matched inference-time token budgets (Appendix H.2). The advantages of more expressive settings remain consistent across these comparisons.

[1] Muennighoff, Niklas, et al. "s1: Simple test-time scaling." Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

W2 Robustness under multi-seed.

We appreciate the reviewer's suggestion and agree that additional multi-seed experiments across different expressiveness settings would further strengthen the robustness of our scaling results. However, due to computational constraints, a full multi-seed replication across all settings and depths is difficult to complete in the limited time available in the discussion period. In particular, some of the deeper configurations require several days of training on 8 GPUs, making experiments very expensive. We are currently running additional experiments where resources allow, and we will update our response with new results once they become available.

AuthorsOpenReview ↗

Response to Reviewer PUKo (2/2)

Q1 Clarification of the oracle algorithm.

We sincerely thank the reviewer for raising this important question. It motivated us to conduct a more thorough analysis of the oracle algorithm and its computational complexity. We further clarify that the generated problems can be solved in linear time when given only the natural language rendering of each problem, without access to the underlying proof structures. We have added pseudocode, a detailed description of the oracle algorithm, and its complexity analysis to Appendix B.4.

We present a linear-time oracle that identifies the logically derivable candidate given only the natural language rendering of each question and candidate conclusions. Since all sentences follow predefined templates (Appendix B.3), they can be directly parsed into symbolic rules and literals.

For the first three expressiveness settings, the consequent of each rule is a literal, and so we apply standard forward chaining. Starting from the literals given as axioms, this procedure keeps track of the logical forms which have been derived so far and, at every iteration, applies rules whose premises have all been derived, adding the consequent to the set of derived literals. This procedure runs in time linear in the number of axioms [1]. Universal quantification can be handled by instantiating each rule over the entities in the problem. Since each instance contains at most two entities, this introduces only constant overhead and does not change the complexity of the underlying inference procedure.

Disjunction introduces a different challenge, as a rule P→a∨bP\rightarrow a\lor b does not establish the truth of either aa or bb individually. To handle this, we extend forward chaining so that its list of derived logical forms not only contains individual literals but also disjunctions that contain two literals. As described in Appendix C.4, our generation procedure restricts disjunctions to two cases:

  • Case 1 (Refutation): One alternative, say bb, is ruled out once ¬b\neg b is derived through the same forward-chaining procedure. Together with a∨ba\lor b, this allows the oracle to derive aa.
  • Case 2 (Merging): Both alternatives lead to the same conclusion through a single inference step. In this case, the generator has added matching rules for both alternatives, such as a→Ca \rightarrow C and b→Cb \rightarrow C. The oracle can recognize this pair of rules and directly derive CC from a∨ba \lor b.

Both forms of inference are logically sound. Since our construction restricts disjunctions to these two cases, the oracle can resolve each disjunction locally. The resulting conclusion may itself be a disjunction, which can be handled in the same way. Thus, the correct candidate can be derived through forward chaining without branching or backtracking.

Since each derived logical form is either the consequent of an original rule or a single literal in that consequent, and each consequent contains at most two literals, the number of logical forms derivable by the oracle is linear in the number of axioms. To perform inference efficiently, the oracle constructs a lookup table, implemented as a hash map, that maps each literal to the set of rules containing that literal in the antecedent. Whenever a new logical form is derived, the oracle uses this table to retrieve the relevant rules and check whether all of their premises are derived. We can prove an upper bound on the number of rules retrieved from each lookup table query by leveraging the properties of our procedure for generating proofs. As described in Appendix B.1, whenever a new node is generated in each proof tree, the logical form at the node is generated with "fresh" predicates. Thus, in the basic construction, each literal appears at most once as a premise and at most once as a conclusion of any rule.† Consequently, each logical form participates in only a constant number of relevant rules. Together with the linear-time construction of the lookup table, this yields an overall oracle complexity of O(n)O(n) for nn axioms.

† When both alternatives of a disjunction lead to the same conclusion (Case 2), the generator introduces a pair of rules that differ in exactly one literal. With universal quantification, each rule is instantiated for at most two entities. Either way, each literal still appears as a premise or conclusion in only a constant number of rules.

[1] William F Dowling and Jean H Gallier. Linear-time algorithms for testing the satisfiability of propositional horn formulae. The Journal of Logic Programming, 1(3):267–284, 1984.

We also revised the sentence on Line 177, Page 4 in Related work to reference this analysis explicitly:

In contrast, ScaleLogic provides independent control over proof depth and expressiveness within a unified framework, with each generated instance being solvable in linear time (Appendix B.4).

AuthorsOpenReview ↗

Supplementary Response to Reviewer PUKo

Supplementary result: Robustness under multi-seed.

We thank the reviewer for suggesting multi-seed experiments to further validate the robustness of our scaling results. Given the computational cost of replicating all depths across all experimental settings, we selected three depths in each setting for additional experiments. Following the multi-seed setup for + Conjunction in Section 4.3, we ran two additional seeds (Seeds 1 and 2) for each experimental setting that had only one seed in the original paper (Implication-only, + Negation, + Disjunction, and + Quantification). The results are summarized in the table below.

Table: Training steps TT to reach 90% validation accuracy under three random seeds. Seed 0 corresponds to the original run reported in the paper.

SettingDDSeed 0Seed 1Seed 2
Implication-only16121213
24201921
32272629
+ Negation8171617
12343535
16546156
+ Disjunction6212222
8404139
10666267
+ Quantification4171617
6495148
89810194

Table: Power-law exponents fitted using the single-seed runs versus all available runs, including additional seeds. Each entry reports the fitted exponent ±\pm standard error.

FitImplication-only+ Conjunction+ Negation+ Disjunction+ Quantification
Single-seed runs1.05±0.031.05 \pm 0.031.67±0.051.67 \pm 0.051.77±0.041.77 \pm 0.042.11±0.092.11 \pm 0.092.60±0.062.60 \pm 0.06
All runs1.05±0.031.05 \pm 0.031.68±0.031.68 \pm 0.031.78±0.031.78 \pm 0.032.11±0.052.11 \pm 0.052.61±0.042.61 \pm 0.04

We have added Figure 10 and the following analysis to Appendix G.4 of the revised manuscript:

The power-law exponents fitted using all available runs are highly consistent with those obtained from the original single-seed runs, with differences of at most 0.010.01, well within their standard errors. Importantly, the monotonic increase in the scaling exponent γ\gamma with logical expressiveness remains unchanged, further supporting the robustness of our main findings to random seed variation.

Dear Reviewer PUKo,

Thank you for your thoughtful review and constructive feedback. We have carefully considered your comments, addressed them in our rebuttal, and revised the manuscript accordingly.

As the discussion period is approaching its end, we would greatly appreciate it if you could take another look at our responses and let us know whether they have addressed your concerns. If anything remains unclear or requires further discussion, we would be happy to clarify.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.