SATURN: SAT-based Reinforcement Learning to Unleash LLMs Reasoning
Authors: Huanyu Liu
Ge Li
Jia Li
Hao Zhu
Kechi Zhang
Yihong Dong
Venue: NeurIPS 2025 spotlight ()
Keywords: Large Language Models
LLMs Reasoning
Reinforcement Learning
Curriculum Learning
Primary area: deep_learning
TL;DR: SATURN enables scalable, verifiable, and curriculum-controlled reinforcement learning that enhances the reasoning capability of LLMs, and generalizes to math and programming tasks.

Abstract: How to design reinforcement learning (RL) tasks that effectively unleash the reasoning capability of large language models (LLMs) remains an open question. Existing RL tasks (e.g., math, programming, and constructing reasoning tasks) suffer from three key limitations: (1) Scalability. They rely heavily on human annotation or expensive LLM synthesis to generate sufficient training data. (2) Verifiability. LLMs' outputs are hard to verify automatically and reliably. (3) Controllable Difficulty. Most tasks lack fine-grained difficulty control, making it hard to train LLMs to develop reasoning ability from easy to hard.

To address these limitations, we propose Saturn, a SAT-based RL framework that uses Boolean Satisfiability (SAT) problems to train and evaluate LLMs reasoning. Saturn enables scalable task construction, rule-based verification, and precise difficulty control. Saturn designs a curriculum learning pipeline that continuously improves LLMs' reasoning capability by constructing SAT tasks of increasing difficulty and training LLMs from easy to hard. To ensure stable training, we design a principled mechanism to control difficulty transitions.

We introduce Saturn-2.6k, a dataset of 2,660 SAT problems with varying difficulty. It supports the evaluation of how LLM reasoning changes with problem difficulty. We apply Saturn to DeepSeek-R1-Distill-Qwen and obtain Saturn-1.5B and Saturn-7B. We achieve several notable results:
(1) On SAT problems, Saturn-1.5B and Saturn-7B achieve average pass@3 improvements of +14.0 and +28.1, respectively.
(2) On math and programming tasks, Saturn-1.5B and Saturn-7B improve average scores by +4.9 and +1.8 on benchmarks (e.g., AIME, LiveCodeBench).
(3) Compared to the state-of-the-art (SOTA) approach in constructing RL tasks, Saturn achieves further improvements of +8.8\%.
We release the source code, data, and models to support future research.

SATURN: SAT-based Reinforcement Learning to Unleash Language Model Reasoning
Huanyu Liu
Ge Li Peking University edu.pp ligešpku. edu. en
Jia Li Tsinghua University jia_li fi@mail tssinhuua edu. cn
Peking University
huanyuliu@stu. pku.
edu. pku.edu.co cn
Hao Zhu
Kechi Zhang
Yihong Dong
Peking University zhuhao@stu. pku. edu,
Peking University Shangkechi@pku edu
Peking University dongyh@stu, pku. edu.
Abstract
How to design reinforcement learning (RL) tasks that effectively unleash the reasoning capability of large language models (LLMs) remains an open question. Existing RL tasks (egg,, math, programming. and constructing reasoning tasks) face three key limitations: ! Scalability. They rely heavily on human annotation expensive LLM synthesis generate sufficient training data. @ Verifiability, LLMs' outputs are hard to verify automatically and reliably. @ Controllable Difficulty. Most tasks lack fine-grained difficulty control, making it challenging train LLMs from easy to hard and progressively develop reasoning capability.
To address these limitations,
propose SATURN, BAT-based RL framework that uses Boolean Satisfiability (SAT) problems to train and evaluate LLM rea- soning. SATURN enables scalable task construction, rule-based verification. and precise difficulty control. SATURN designs a curriculum learning pipeline that continuously improves LLMs' reasoning capability by constructing SAT tasks increasing difficulty and training LLMs from easy to hard. To ensure stable training, design principled mechanism control difficulty transitions.
We introduce SATURN-2.6K, difficulty. It supports the evaluation of how LLM reasoming changes with problem difficulty. We apply SATURN to DeepSeek-B R1 Qwen and obtain SATURN- 1.5B and SATURN-7B. We achieve several notable results: 1 On SAT problems, SATURN-1.5B and SATURN-7B achieve average pass@3 improvements of +14.0 and +28.1, respectively. @ On math and programming tasks, SATURN-1.5B and SATURN-78 improve average scores by +4.9 and +1.8 on benchmarks (e.g.. AIME, LincCodeBench), @ Compared to the state-of-the-art (SOTA) approach in constructing RL tasks, SATURN achieves further improvements +8.8%, We release the source code, data, and models to support future research at https: //github. com/ gtxygyzb/ Saturn-
dataset of 2,660 SAT problems with varying
Introduction
Recently, reinforcement learning (RL) has become promising paradigm for unleashing the reasoning capability of large language models (LLMs), particularly in math, programming, and logical reasoning (e.g., OpenAl-ol (1). DeepSeck-RR [[]] Kimi-k1.5 (37). During the RL training process, the
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

design of RL tasks plays critical role [1 A well-designed RL task should elicit LLMs' reasoning capability, fostering behaviors such as hesitation, reflection, backtracking, summarization, and verification 28 31
43
44 53
However, how design RL tasks that can continuously enhance LLMs' reasoning capability remains an open question. We think a well-designed RL task for reasoning should satisfy the following three criteria: O Scalability. RL training requires large-scale data. RL tasks should support scalable data without human annotation or expensive LLMs' synthesis. @ Verifiability. RL rewards must be unambiguously correct. The outputs of LLMs for the task should be easy verify. @ Controllable Difficulty. Reasoning capability emerges progressively [2].. RL tasks should support the difficulty control enable curriculum learning, allowing LLMs gradually develop more complex reasoning skills [[6].
Table 1: The comparison between existing RL tasks and SATURN.
Tasks
Scalability
Verifiability
Controllable Difficulty
ScaleQuest
12
x
GSM8K (Math)
9
LiveCodeBench
/
Game Werewolf
45
48
X
X
LMRL Gym
4
X
J
SPAG t
X
Knights& Knaves Knaves
46
/
SATURN (Ours)
Table shows the features of current mainstream RL tasks. None of them satisfy all three criteria. Existing RL tasks can be divided into two categories: (1) One category of RL tasks requires LLMs to solve math or programming problems, with rewards based on the correctness of the final answer or code 6 27.. However, these tasks rely on human annotation for ground-trun -trth solutions or test cases, suffer from a lack of high-quality problems, and offer only coarse control over reasoning
difficulty 23 26 (2) Another category focuses on manually designed reasoning tasks [2 45 46
For instance, Logic-RI. [7] leverages natural language logic K&K puzzles to improve LLMs' reasoning capability through RI. However, they also present limitations, such as hard to scale up due to reliance on sampling from LLMs 77] 12). hard to verify despite relying on LLMs for
cross-validatie [12 41 51], and hard to control difficulty [45 48).
In this paper, we aim to answer the following research question:
Key Question
Can design an RL task that supports scalability, verifiability, controllable difficulty, and enhances the reasoning capability of LLMs?
To this end, we propose Boolean Satistiability (SAT) problem as the task for RL. Figure I shows an illustration of SAT problems and corresponding features. SAT satisfies all three desiderata we outlined earlier: OScalability. SAT instances can be generated programmatically at scale without human annotation or LLM synthesis, allowing for virtually unlimited training data. Verifiability. SAT is well-established NP-complete problem in theoretical computer science [Q]. The correctness of a solution can be easily verified linear time. But solving SAT problems requires complex reasoning. @ Controllable Difficulty. The difficulty of SAT instances can be precisely adjusted (e.g., number of variables, clauses), making it suitable for curriculum learning. What's 's more, SAT serves as universal substrate for limited forms of logical reasoning, as many problems in propositional logic, finite-domain first-order logic, and modal logic can be systematically reduced to SAT [7 24 36).
Building on these advantages, we propose SAT-basel reinforcement learning to Unleash LLMs ReasoNing, or SATURN. SATURN a multi- stage curriculum learning- based RL framework that continuously improves the reasoning capability of LLMs. SATURN efficiently constructs SAT tasks with controllable difficulty and organizes them into progressive stages from easy to hard, allowing L.MSs to develop reasoning skills step by step. To ensure training stability and effective progression, we design principled mechanism to control difficulty transitions based on L.MMs performance. SATURN enables smooth curriculum advancement and steady enhancement of reasoning capability.

---

Scalability
Controllable Difficulty
easy
Verifiability
SAT SAL_constructormn.kk
X1 True
</>
3
30
- V
LLMs
False
</>
X True
X
- - vx A
Figure I: An illustration of SAT problems and its corresponding features.
We introduce the SATURN-2.6K dataset, consisting of 1,500 training instances, 160 test instances at the same difficulty the training set, and 1,000 test instances from 10 harder unseen difficulty levels. The test set serves as a benchmark for systematically evaluating how LLMs' reasoning capability varies with increasing SAT task difficulty. We release SAT construction scripts alongside the dataset, which enable the creation of virtually unlimited SAT instances.
We apply SATURN to DeepSeek-FR Bereekk-R--DAe Distill-Qwen- and 7B [1, obtaining SATURN-1 -15B and SATURN-7B. Experiments show that SATURN effectively enhances LLMSs reasoning capability in generalizable scenarios:
SATURN-1.5B and SATURN-78 7B achieve strong performance on SATURN-2.6k benchmarks. unseen harder test set, two models achieve passe3 improvements of +14.0 and +28.1 respectively.
The reasoning capability learned from SATURN transfers well to math and programming tasks, bringing average improvements of +4.9 and +1.8 popular benchmarks such AIME (2), AMC O. MATH-500 [9]. GPQA Diamond 35 and LiveCodehench (22) for two SATURN models.
Compared the prior SOTA approach (e.g., Logic-RL), SATURN achieve average improvements of +8.8% on math and programming tasks.
2 SATURN
Curriculum Estimation Loop
LLMs Training Loop
SAT
Sucura
PJP
No
SAT
LLM
SAT ao
<D>
</>
</>
Evaluate
LLLM
Validate
Sample
GRPO
L.M
SAT _eunstructor
Validator
SAT difficulty increases
Yes
Evaluate
Figure 2: The overall framework of SATURN. It alternates between two interconnected loops: (1) Curriculum Estimation Loop. (2) LLMs Training Loop. The two loops iterate until the maximum number of curriculum stages is reached.
2.1 SATURN Learning Loop Framework
We introduce SATURN, multi-stage RL framework that leverages SAT tasks unleash LLMS reasoning via curriculum learning. As illustrated in Figure SATURN alternates between two inter- connected loops:
Curriculum Estimation Loop dynamically constructs SAT instances of adjustable difficulty and evaluates LLMs' performance determine whether to advance the curriculum stage; LLMs Training Loop employs RL to optimize LLMs on current difficulty SAT tasks. The curriculum loop presented in Algorithm I proceeds follows:
Step Curriculum Estimation Loop. Given initial SAT difficulty, SAT_ Construction generates validation set of SAT instances. The LLM is evaluated on this set using the pass@1 metric. If harder
the performance exceeds a predefined threshold e, the curriculum controller advances configuration with an increased estimated difficulty. Otherwise, SATURN process enters Step 2 I.LMs training loop the current SAT difficulty. This adaptive loop ensures that the L.LM always trained at the fronticr of its reasoning capability, neither too easy too hard.

---

Step 2: LLMs Training Loop. For the current difficulty, CAT_Consttnttion generates set of training instances that different from the validation set. These samples are then used to train LLMs with GRPO. The reward function encourages outputs that are both logically correct and properly formatted. The training loop proceeds until passê1 on the validation set. After that, the process backs to Step to reassess and potentially advance the curriculum.
The two loops iterate jointly. SATURN process terminates when predefined total number of iterations is reached. Importantly, SATURN is not designed to replace math or programming tasks, but serve as a complementary strategy for enhancing LLMs' reasoning. practice, SATURN can be integrated with math and programming tasks to enable a stronger training framework.
SATURN learning loop raises three core challenges: Section 2.2
introduces how to construct presents how to estimate instance difficulty for curriculum learning. Section 2.4 explains how to train L.LMs on SAT tasks with RL.
scalable and controllable SAT' instances. @ Section 2.3
2.2 SAT Instances Construction
In this subsection, we formalize the construction of SAT instances. A SAT problem determines whether propositional formula can be satisfied by Boolean truth assignment. Formally, we define a (n, k. 1)-SAT instance in conjunctive normal form (CNF) as:
{ @- = (Ias, V Taia V V Toi..) A .... A (Nar. V V -Zai. where or E (1,...,k)) k), i e [1,4]., E [1,
where each clause contains exactly n variables (literals), each being either æ; or its negation -x;, is the total number of variables, and is the total number of clauses. Based on the definition, design wwrr_CCnssuciionn
a SAT instance constructor, stances from the space of (n,k: k. ()-SAT. By adjusting the parameters (n, I, m). SAT_ Construction enables the scalable and controllable construction of SAT instances. The design details of the con- structor algorithm are provided in Appendix B All generated SAT instances guaranteed to be satisfiable.
k. I, l,m) which uniformly samples m SAT in-
2.3 Estimation of Task Difficulty
In this subsection, present the estimation of SAT task difficulty for LLMs. This estimation also serves as the foundation for curriculum learning in LLMs.
As canonical NP-complete problem [10] SAT admits a polynomial-time reduction from any other NP problem (25]. SAT exhibits known phase transition phenomenon: when the clause-to-variable ratio a 1/k approaches critical threshold (typically near 4.26 for 3-SAT), the probability of satisfiability drops sharply, and problem difficulty peaks. This phenomenon probably stems from replica symmetry breaking (RSB) (54): near a., the solution space fractures into disconnected clusters separated by energy barriers. Beyond Qee the space collapses, reducing complexity.
However, RSB theory is designed for heuristic SAT solvers. For humans or LLMs solving SAT problems through logical steps such as trial, verification, and reasoning, such solver-like phase transitions are hardly observable in human-like thinking processes. While any n-SAT (n >> 3) can be reduced to 3-SAT 25,, they differ significantly for L.LMs in terms of solution space size and token length.
Prior work [8 on SAT tasks for LLMs typically categorized difficulty based on phase transition points. To systematically estimate task difficulty, we define an analytical estimator of the expected solution space size. Given a (n, k 1) SAT instance, its difficulty for LLMs can be approximately estimated by:
D(n, logg(k) + logg(()) (1) -
(2)
Eq. (2) provides more controllable, fine-grained estimation of SAT task difficulty. The detailed
derivation is provided in Appendix [ To further validate Eq. (2), we evaluate L.MMs performance on SAT instances with varying difficulty levels. As shown in Figure each point represents LLM's

---

average passo3 on the same estimated difficulty instances. Pass@3 generally decreases as [(n, k, increases, suggesting that our estimation aligns with the solvability trends observed in practical LLMs.. Stronger LLMs maintain higher pass@3, while weaker L.Mss exhibit lower scores overall. The validity of the estimation Eq. further confirmed by ablation experiments, as detailed in Appendix
SAT Prablem Salving: Difficulty Pass@
DeepSeek Disbili pass 0.06-D+0.71
DeepSeak Dist-iiill--eee Qwaiill--wee-BB..... passge 0..15
0.6
(3,6200)
B. 3,7,20
0.5
Passi@3 (%)
X (3.5225)
0.3
X6.7.40
0.2
4,7.200
T09,001
235
X.. ad
(,440
(0.740) X
(3:7401
x 3.55,5
X:4.7 301
(4.8.40
(33440)
0.0
10
12
Difficulty
Figure 3: Scatter plots of pass@3 versus estimated diffieulty D(n, k. 1) for different LLMs, with linear regression fits. The linear regression for two models achieve R² values of 0.707 and 0.724 respectively, suggesting reasonably strong linear relationship between difficulty and passE3.
2.4 Reinforcement Learning with GRPO
In this subsection, we introduce the single- RL training for given (n, k. I)-difficulty tasks. RL can further improve LLMs' generalization by directly optimizing policy gradients diverse reasoning trajectories [I]. Given the SAT tasks, we then train LLMs using the original sample-level GRPO to optimize the policy va with KL divergence penalty. The GRPO objective function is defined as:
CiRrO =Elg ~ ((Q). ~ Toai (0/4)
6
10:
min (1) clip
Aca] -8lx [TO || medl (3)
To (or. q. oL.C)) Å., ro mean(r)
where (()
To Tem for. o.,ce)
std(r)
where & denotes SAT instance, O; is the reasoning trajectory generated by the policy ne. and G groups SAT instances with identical (n, k parameters. A simple yet effective reward scheme [1]] is designed that combines a format reward and correctness reward. Specifically, r; - if an output for well-formatted but incorrect answers; and r; 1 only when both the format and the answer correct. Here, answer is considered correct if it passes a verifier and represents a full satisfying assignment. Training schedule and hyperparameter settings are detailed in Appendix D And the SAT prompt template is shown in Appendix F
invalid (i.e., missing the \boxed{(} wrapper); r;
3 Experiments
We apply SATURN to PeepSeck-RI-Dsstinee Bissill-Qwen-1.BB and 7B, obtaining SATURN-1.SB and SATURN-7B. To evaluate the effectiveness of SATURN, we conduct a large-scale study to evaluate both models. In this section, we introduce our research questions (RQs), benchmarks, baselines, and evaluation metries. For each RQ, we present the corresponding experimental design, results, and analysis in separate subsections.
5

---

3.1 Research Questions
Our study aims to answer the following research questions:
RQ1: How much improvement does SATURN achieve in solving SAT tasks? We evaluate SATURN-1.51 and SATURN-7B performance on SATURN-2.6K with different difficulty levels.
RQ2: How effectively does SATURN generalize to math and programming tasks? To evaluate the transferability of reasoning capabilities learned by SATURN, we evaluate the performance of LLMs on math and programming benchmarks and compare them with current SOTA LLMs.
RQ3: How does SATURN compare to prior RL tasks? To explore the relationship between SAT-
URN and existing RL tasks, RQ3 investigates whether SATURN can (1) serve as a complementary task to math and programming, and (2) outperform other constructing RL tasks.
RQ4: How does SATURN affect LLMs reasoning trajectory? RQ4 explores whether SATURN influences the reasoning patterns of LLMs, particularly in terms of response length and the capability of verification. We investigate whether the reasoning improvements observed in SAT tasks generalize to math and programming.
3.2 Experimental Setup
SATURN Hyperparameters For SATURN-1.5B and SATURN-7B, set the initial SAT instance parameters (n, k. to (3, 5) and (3, 5, 13), respectively. In Curriculum Estimation Loop, the threshold is set 0.5 for the 1.5B model and 0.75 for the 7B model. In L.LMs Training Loop, evaluate the pass@k with step size of 250 training samples. The total number of curriculum iterations set to 2. Detailed hyperparameters are provided in Appendix [A] Ablation studies in Appendix H demonstrate the necessity of curriculum learning and the effectiveness of hyperparameters on SAT difficulty, thresholds, step sizes, etc.
Benchmarks. Building upon SAT Construction tool and difficulty estimation, we release SA6URN-2.6,, a curated benchmark designed evaluate L.MMs' reasoning capability across varying complexity. SATURN-2.6k consists of 1,500 training instances and 160 test instances that share the same estimated difficulty level. To assess performance under increasing task complexity, SATURN- 2.6k further includes 1,000 test instances from 10 unseen harder difficulty levels, with 100 instances per level. These levels are selected based on our difficulty estimation D(n, k. I), enabling a systematic analysis of how LLM performance changes as problem difficulty increases. Additionally, custom datasets of desired difficulty can be constructed using our apen-sourced SAT_ Construction tool. @ For math and programming tasks, following DeepSeck-Al [T]] 22/23 I. MATH-500 [9], GPQA Diamond 35|. and LiveCodeBench v4_v5 v5 subset 22
AIME 24/25 (2) AMC
Baseline Model. We conduct evaluations against several 1.5B and 7B parameter reasoning models as the baselines, which include ReepSsee-Ri--Disiill--eee.
& 7B [II], 40) 11.1- & 7B [31] z1-7B (50). OpenThinker-7B [38]. and DeepScaleR- 1.5--BPrreeee (29). In addition, we include a supervised fine-tuning (SFT)-only baseline trained on the Math training dataset 119. which provides step-by-step problem reasoning trajectories. We randomly select the most difficult Level-5 1,000 problems from training set for one epoch of SFT, following the same training template as DeepSeek- RI- RR--Ditill-Qwer With the same dataset size, our setup enables fair comparison between SFT and RL on SAT tasks.
Evaluation Metrics. Following DeepSeek-AI 11. we use pass@k as the evaluation metric. Pass@k assesses the probability that at least one correct solution is generated within i attempts. For SAT problems, we evaluate passūk (1,3,5, 7, 10) and sample times per problem. For math and programming benchmarks, we use pass01, following context length of 32,768 and temperature 0.6. More evaluation hyperparameters are provided in Appendix E, All experiments are conducted on NVIDIA 8xA100 (40GB) GPUs. Specific prompts are detailed in Appendix
3.3 RQI: SATURN Substantially Improves Performance on SAT Tasks
We evaluate the performance of SATURN-I.SS and SATURN-7B on SAT tasks using SATURN-2.6k test set. Specifically, the evaluation involves unseen SAT instances that were not included in the

---

training data. The results, presented in Table 2 T0 14 and detailed in Appendix G demonstrate the performance of LLMs across different SAT difnculties.
Table 2:
Performance (pass in %) SATURN-2.6K test across different difficulty levels.
SAT-(3,5,5)
SAT-(3,5,8)
Model
@
@3
@5
@7
@
10
@
@3
@5
@7
10
DeepSeek-B Berekk-R---iiiie R-----tiD---------- D---isill--Qen--.... 1
36.7
71.7
85.4
91.7
96.2
20.3
47.6
63.6
73.4
81.9
SATURN-I.SH Iteration-1 -
59.7
90.4
97.1
99.1
99.8
41.0
74.0
85.6
91.1
95.6
SATURN-I.5B ---e-tttooioon2
70.3
95.9
99.0
99.7
99.9
47.0
82.6
93.9
98.0
99.8
SAT-33,5,13)
SAT-(3,5,15)
Model
@ 1
@
@7
@ 10
@
@ 3
@
@
10
DeepSeek-RR R1 L--ii-iill-Queee Distill-Qwen-7B
53.9
86.2
94.2
97.3
99.3
39.3
74,9
88.3
94.3
98.3
SATURN-7E 7B-Iteration
73.0
96.1
98.9
99.7
99.9
65.7
91.8
96.8
98.7
99.7
SATURN-7B-ltcaan -terattot
89.5
99.0
99.9
100.0
100.0
85.4
98.3
99.8
99.9
100.0
SATURN substantially improves LLM performance on SAT tasks across varying difficulty levels. On the difficulty SAT-(3,5,5), SATURN-1.5B improves pass@1 from 36.7 to 59.7 at Iteration- and further to 70.3 Iteration-2, achieving a total gain of +33.6. On the unseen harder test set (Table ITI. EATURN-1.5B improves average pass from 10.1 to 24.2, while SATURN-7B improves from 36.1 to 64.2. average, these models achieve pass improvements +14.0 and +28.1 respectively, confirming that SATURN effectively enhances LLM reasoning across both and unseen SAT difficulties.
3.4 RQ2: SATURN Demonstrates Strong Generalization to Math and Programming
We assess whether the reasoning capability learned by SATURN generalizes to math and program- ming tasks. We evaluate SATURN- 1.5B and SATURN-7B on range of reasoning benchmarks. The results shown in Table provide detailed comparison.
Table 3: Performance comparison on math and programming Benchmarks
Model
AIME 24/25
AMC 22/23
Math500
GPQA-D
LiveCodeBench
Avg.
GPT-4o (Aug'24)
11.7
79.5
$2.1
31.7
Claude 3.5 Sonnet (Oct '24)
15.7
77.1
59.9
38.1
s1.1-1.5B
1.7
25.3
42.2
2.2
20.1
Bill-3-1.5B-Previiew
23.3
84.6
17.1
46.9
BeaSSek-RR--Distill--eer
21.6
65.1
83.6
30.3
16.4
43.4
+ SFT
25.0
68.7
82.0
34.3
14.6
44.9
SATURN-I.5B
28.3
73.5
84.6
37.4
17.4
48.2
z1-7B
8.3
39.8
35.4
19.3
35.4
s1.1-7B
21.7
61.4
80.8
43.4
12.8
44.0
OpenThinker-7B
26.7
53.0
88.6
42.9
21.5
46.5
DeepSeek-RI MaASSeck--R--iaee Distill-Qwen---
50.0
80.7
93.2
49.0
35.4
61.7
SATURN-7B
48.3
85.5
95.0
50.5
37.7
63.4
0 SATURN shows strong generalization to math and programming tasks. On the AIME 24/25
benchmark, SATURN- outperforms z1-7B by 8.3 and s1.1-7B by 21.7. Similarly, SATURN- 7B achieves strong improvement on the Math500 dataset, increasing from 93.2 to 95.0. On LiveCodeBench, improves from 35.4 to 37.7. On average, SATURN-I.SB improves by +4.9, and SATURN-7B improves by +1.8 across these benchmarks. These results highlight that SAT- URN enhances the reasoning performance of LLMs across various math and programming tasks, demonstrating strong generalization of the learned reasoning capabilities from SAT.
SATURN outperforms SFT on broader benchmarks. Consistent with the observations in SFT Memorizes, RL Generalizes [8) SFT improves performance on math-focused benchmarks (AIME, AMC, and Math500) that are similar to its supervised training domain. However, on LiveCodeBench. SFT drops from 16.4 to 14.6, exhibiting an aligument lax (33, where specializing on narrow domain compromises performance on other tasks. In contrast, SATURN improves performance across all benchmarks, with SATURN- 1.5B reaching 17.4 LiveCodeBench. Averaging across all
7

---

benchmarks, SATURN-I.5B outperforms the SFT counterpart by 3.3, demonstrating that SATURN generalizes effectively.
3.5 RQ3: SATURN Serves as a Complement and Further Enhances LLM Reasoning
RQ3 studies the relationship between SATURN and existing RL tasks. Beyond the DeepSeek-R1- Dhstil--wee--BB we introduce two additional models: Qwen2.5-7B-hhe Inntt-tttttttt--MM [39 49 following Logic-RL [47] settings, and DeepScaleR-
and programming examples from 11e.1-.---P-eeeee [29], which is further RL trained on 40k math We compare SATURN against several prior constructing RL task approaches, including Logic-RL 477], SPGA 7. and ScalcQuest [12], which represent strong baselines. Each approach is applied to different models for comparison. Results are summarized in Table 4
Table 4: Comparison of SATURN and prior approaches across various LLMs.
Model
AIME 24/25
AMC 22/23
Math500
GPQA-D
LiveCodeBench
Avg.
SPGA-3 (82k)
0.0
3.6
7.2
24.7
0.0
7.1
ScaleQuest (25k)
6.7
45.8
74.6
31.3
7.9
33.3
Owen2.5-7B-Instrueee
74.4
32.3
32.5
+ Logic-RL (5k)
29.3
+ Saturn (1k)
10.0
37.9
36.2
50.0
80.7
93.2
49.0
35.4
61.7
+ Logic-RL (5k)
50.0
80.7
93.4
52.0
35.7
62.4
+ Saturn (Ik)
48.3
95.0
50.5
37.7
63.4
DeepScaleR- R-1.BB--BBBB.... --5--rrvvee
30.0
74.7
87.8
37.4
19.8
49.9
+ Logic-RL (5k)
28.3
77.1
86.4
35.9
20.7
49.7
+ Saturn (0.5k)
35.0
73.5
88.6
43.4
21.0
52.3
SATURN serves as strong complement to math and programming. On DeepSccleRR11.5B Preview-desppee being further RL trained with 40k math and programming
Sammples-SATRRY still brings additional improvements, raising the average score from 49.9 to 52.3. Notably, it improves AIME by +5.0 and GPQA-D by +6.0. @ SATURN outperforms prior constructing RL task approaches across multiple models. On examples but improves the average score from 32.5 to 36.2, achieving a relative improvement of +8.8% over Logic-RL RL trained with 5k examples. These results indicate that SATURN not only complements math and programming tasks, but also provides greater improvements compared to other constructing RI. task approaches.
SATURN uses only 1k training
3.6 RQ4: SATURN Enhances Self-verification in LLMs Reasoning Trajectories
RQ4 investigates whether SATURN affects LLMs' reasoning behavior. On D0wen2.5-7B-Insstne we observe a gradual increase in response length during training, as illustrated in Figure 4 replicating the lengthening phenomenon reported in the RI and Logic-RL. RL [1]
train/response, length
Qven2
1800
1600
1400
1200
1000
m
800
MMW
Step
Figure 4: Response length trend during SATURN training on 1reen.557B-Instrruee 1M.

---

Question:
Math 402: how mony waye can people be sented around squire table with people side? (Two configurations considered equivalent if is a rosation anotiac))
R1 Discill Owen. 7B
Saturn-7i 78 problem: to rind haw many ways 8 people can be seated around a square table with 2 people on each side.
<think> Okay, so
<think- Okay, so have this problem where I need to find out kow many ways 8 peuple can seated around a square table, with people on each side.
But wasi, that woeld imply that the nomber distinet arsegeements 71 5040, which is loss than 81 /4 (which is 100s0), So which approwch correetf I'm getting
So to get the number of unique arrangements under rotationn we divide (4,So, 5040 1260. So the would 1260.
stack here. Let think simpler Suppose we have 4 people around square table,
But the case of em4, maybe the number unique amungements :4-6/4-1.5 1.5, which is impossible, so that can't be right. So perhaps the formala only applicable when is multiple of 4, but that seemss restrictive.
Wait second, in the 4 4-person case, the number of distinct acrangements is 31 -6, which the sume 41 /4, But 81 40320/4-1009)) 10080, which is diffeerent from 71 -5040.
<hiink To determine number of ways 8 people can be seaeed around square thiee with people on each side, considering rotations equivalent configurstios, we use formala cirenlar
<ithink> The problem involves finding the number distinct ways to sair 8 people amound a square table with sears on each side. considering two configuration equivalent ane is rotation other. Since square has rotational symmetry of onder 4 (rotations by 90",
urrangoments divided by the number of rotational symmetries. The square
number circulur arunggments (8.1))= 5040, rocational symmelzies (V", 90', 180", 270"), we divide by 4, resullting in 4- 1260. Therefore, final answer is: Sibosod [1260]S
270"), ). each distinct arangement counted in the total count of (40320). Therofore, the number of distioct arrangemeuts is 8. divided by which equals 10000 x*A Awwerr "6 hoosed (1088)8
Figure 5: Comparison of reasoning trajectories on Math 500 Question No.402 between two models.
To examine whether such reasoning patterns generalize, we present case studies across SAT and math domains. Figure [2] shows that solving SAT variables requires rechecking all clauses, naturally encouraging self- seff-verficattio. In Figure [ SATURN-7B verifies intermediate conclusions within small scenario and successfully chooses the correct solution path. In contrast, the baseline model reaches wrong answer and skips verification, even when inconsistencies are detected.
Recent studies [0) identify core behaviors shared by expert human reasoners and LLMs, such as verification and backtracking. These behaviors are domain- agnostic and provide fundamental reasoning patterns applicable to a wide range of tasks. In line with these findings, SATURN reinforces similar behaviors during SAT solving, leading to more structured reasoning trajectories. More reasoning trajectories are provided in Appendix to illustrate how SATURN works. These results suggest that the self-verification patterns learned from SAT transfer well to math and programming tasks, improving reasoning robustness and reliability.
4 Discussion
4.1 Limitations of Reasoning Capability Learned from SATURN
During curriculum learning, we observed that as the number of training iterations increases, the improvements in math and programming tasks tend to plateau, which is consistent with the findings in Logic-RL. Detailed evaluation results are provided in Table This plateau may stem from several factors: 1 Knowledge limitations. SATURN improves formal Togical reasoning but does not provide domain-specifie knowledge supervision. This limits its effectiveness tasks requiring mathematical or algorithmic knowledge. @ Context window bottlenecks. SAT problems are NP-complete tasks, and the required reasoning length grows exponentially with increasing problem difficulty. This leads to bottlenecks in the model's capability to handle increasingly complex tasks. 2 Limited plasticity and forgetting. Model plasticity and catastrophic forgetting are known limitations that hinder further improvements with additional training stages
4.2 Potential of SATURN on Stronger Models
To explore the potential of SATURN to stronger models, we evaluate frontier LLMs on SAT tasks using the extended SAT instances. Results are shown Appendix [I] Although these LLMs exhibit stronger performance, they still make common errors such as hallucinating clauses, confidently committing to incorrect decisions, or failing to apply basic logical rules. Even more advanced LLMs still struggle to solve complex SAT problems. We believe SATURN remains promising approach for enhancing reasoning in stronger L.Mss. With sufficient computation, SATURN can offer a scalable, verifiable, and controllable path to further improve reasoning capabilities.

---

Table 5: Performance of multi-Stage SATURN iterations on math and programming benchmarks
Model
AIME 24/25
AMC 22/23
Math500
GPQA-D
LiveCodeBench
Avg.
DeepSeck-R1 ---ittti--i-------
DegpSeek-II-Disiii--qew-------
21.6
65.1
83.6
30.3
16.4
43.4
SATURN- B-
26.7
85.0
16.9
46.1
SATURN- 1.---tteation
28.3
73.5
84.6
37.4
17.4
48.2
SATURN-1.55 ---rrttttoo
28.3
66.3
85.8
36.9
16.7
46.9
DeepSeek-ER -isttill-BB
50.0
93.2
49.0
35.4
61.7
SATURN-78 7B-Iteraton-
48.3
83.1
94.6
50.5
36.6
62.6
48.3
85.5
95.0
50.5
37.7
63.4
SATURN-7B-Heraatonn
46.7
87.9
93.2
58.1
38.1
64.8
Related Work
5.1
Constructing Reasoning Tasks for Reinforcement Learning
Several works have explored constructing reasoning tasks to improve the reasoning capability of LLMs. Logic-RL [47 and LMRL Gym 4 train LLMs natural language logic puzzles but lack scalability due to their limited puzzle set. ScaleQuest [12], Entity-Deducing Game [52], and K&K [46] propose automatic generation of constructing questions, but rely LLM sampling or handcrafted templates, making large-scale generation costly and hard to verify. CodeDPO [51] and PuzzBench 41) employ LLM-based verification, which may fail silently and cannot ensure correctness. Wolf Game 455 48) focus on multi-step logic reasoning but offer no control over task difficulty, limiting their support for curriculum learning. Overall, these tasks fall short in scalability, verifiability, or controllable difficulty. See Appendix K for detailed comparisons.
5.2
SAT-Based Evaluation LLM Reasoning Capability
Recent studies have evaluated the reasoning capability of LLMs on SAT problems. Most of these works focus analyzing model behavior around the SAT phase transition [18] 30 34], where problem hardness peaks. However, the phase transition theory is originally designed for heuristic SAT solvers and does not align well with the reflective and verification-based reasoning processes of humans LLMss. These studies also lack fine-grained scalable difficulty framework and typically divide difficulty based on the phase transition threshold. They are further limited to supervised fine-tuning and do not consider large reasoning models with long-CoT reasoning capability trained via RL. Our work addresses these limitations by building progressive evaluation and curriculum learning pipeline, enabling precise difficulty control and the generalization LLMs.
Conclusion and Future Work
We present SATURN, a SAT-based RL framework for unleashing and evaluating the reasoning capability of LLMs. By leveraging SAT's scalability, verifiability, and controllable difficulty, SATURN addresses key limitations existing RL tasks. It constructs multi-stage curriculum to gradually enhance reasoning, and introduces the SATURN-2.6K benchmark for controlled evaluation. Applied to DeepSeek-B -aieeek--R----isee R1-DDstilll- -wen, SATURN produces SATURN- 1.5B and SATURN-7B, which show strong gains on unseen SAT tasks and generalize well to math and programming benchmarks.
In future work, we plan to: (1) apply SATURN to larger-scale LLMs, (2) break the existing paradigm's reliance on human-annotated data and explore new paths toward building LLMSs with continuous self-evolution capabilities.
Acknowledgements
This research supported by the National Key R&D Program under Grant No. 2023YFB4503801, the National Natural Science Foundation of China under Grant No. 62192733, 62192730, 62192731, the Major Program (JD) of Hubei Province (03,202334)024), and the Beijing Natural Science Foundation under Grant No. 4264107.
10

---

References
[1] 2022-2023. AMC Datasets.
http:://artooooooeeeeeol////caca phpp
AMC 12, Problemss and Solutions
[2]
2024 2025. AIME Datasets.
http:://aaaagpoooooooooo.//././a php/
AIME Problems and Solutions
[3] Zaheer Abbas, Rosie Zhao, Joseph Modayil, Adam White, and Marlos C. Machado. 2023. Loss of Plasticity in Continual Deep Reinforcement Learning. In CoLLAs (Proceedings of Machine Learning Research, Vol. 232). PMLR, 620-636.
[4] Marwa Abdulhai, Isadora White, Charlie Snell, Charles Sun, Joey Hong, Yuexiang Zhai, Kelvin Xu, and Sergey Levine. 2023. LMRL Gym: Benchmarks for Multi-Turn Reinforcement Learning with Language Models. CoRR abs/2311.18232 (2023).
[5] Jacob Austin, Augustus Odena, Maxwell I. Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie J. Cai, Michael Terry, Quoe Le, and Charles Sutton. 2021. Program Synthesis with Large Language Models. CoRR abs/2108.07732 (2021).
[6]
Mark Chen, Jerry Tworek. Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray. Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. 2021. Evaluating Large Language Models Trained on Code. CoRR 2as/2107.03374 (2021).
[7] Pengyu Cheng, Tianhao Hu, Han Xu, Zhisong Zhang, Yong Dai, Lei Han, Nan Du, and Xiaolong Li. 2024. Self-playing Adversarial Language Game Enhances LLM Reasoning, In Advances Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, UIrich Paquet, Jakub M. Tomczak, and Cheng Zhang (Eds.). http: http::/paperrs nips ct/ hash/ Baebb//4bb7e99867ft 63563f 4ate4 Abstract--btttttttt-e Confeettttoooffeeceeeee .html
httpppppprr__ffee www.ffillfpppeeee /2024/
[8] Tianzhe Chu, Yuexiang Zhai, Jihan Yang, Shengbang Tong, Saining Xie, Dale Schuurmans, Quoe V. Le, Sergey Levine, and Yi Ma. 2025. SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training. CoRR abs/2501.17166 (2025).
[9] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jenry Tworek, Jacob Hilton, Reicchir Nakano, Christopher Hesse, and John Schulman. 2021. Training Verifiers to Solve Math Word Problems. CoRR abs/2110.14168 (2021).
[10] Stephen A. Cook. 1971. The Complexity of theorem-Proving Procedures. In STOC. ACM, 151-158.
[11] DeepSeek-AI, Daya Guo. Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma. Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang. Bochao Wu, Bei Feng. Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingehang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang,
11

---

Lecong Zhang, Liang Zhao, Litong Wang, Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang. Minghui Tang. Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang, Peng Zhang. Qiancheng Wang, Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang. R. J. Chen, R. L. Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang. Shuiping Yu, Shunfeng Zhou, Shuting Pan, and S. S. Li. 2025. DeepScek-RR R.: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. CoRR abs/2501. 12948 (2025).
[12] Yuyang Ding, Xinyu Shi, Xiaobo Liang, Juntao Li, Qiaoming Zhu, and Min Zhang. 2024. Unleashing Reasoning Capability of LLMs via Scalable Question Synthesis from Scratch. CoRR abs/2410. 18693 (2024).
[13] Shibhansh Dohare, J. Fernando Hemnandez-Gariia, Qingfeng Lan, Parash Rahman, A. Rupam Mahmood, and Richard S. Sutton. 2024. Loss of plasticity in deep continual learning. Nat. 632,
8026 (2024), 768-774.
[14] Ahmed El-Kishky, Alexander Wei, Andre Saraiva, Borys Minaiev, Daniel Selsam, David Dohan, Francis Song, Hunter Lightman, Ignasi Clavera Gilaberte, Jakub Pachocki, Jerry Tworek, Lorenz Kuhn, Lukasz Kaiser, Mark Chen, Max Schwarzer, Mostafa Rohaninejad, Nat McAleese, 03 contributors, Oleg Mürk, Rhythm Garg, Rui Shu, Szymon Sidor, Vineet Kosaraju, and Wenda Zhou. 2025. Competitive Programming with Large Reasoning Models. CoRR abs/2502.06807 (2025).
[15] Kanishk Gandhi, Ayush Chakravarthy, Anikait Singh, Nathan Lile, and Noah D. Goodman. 2025. Cognitive Behaviors that Enable Self--mmroving Reasoners, or, Four Habits of Highly Effective STaRs. CoRR abs/2503.01307 (2025).
[16] Yifan Gao, Lidong Bing, Wang Chen, Michael R. Lyu, and Irwin King, 2019. Difficulty Controllable Generation of Reading Comprehension Questions. In IJCAI. ijcai.org, 4968-448 4974..
[17] Enrico Giunchiglia, Armando Tacchella, and Fausto Giunchiglia. 2002. SAT- Decision Procedures for Classical Modal Logics. J. Autom. Reason. 28, 2 (2002), 143-171. doi:10
[18]
Rishi Hazra, Gabriele Venturato, Pedro Zuidberg Dos Martires, and Luc De Raedt. 2024, Can Large Language Models Reason? A Characterization via 3-SAT. CoRR hbbs/2408.07215 (2024).
[19] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardr. 2021, Measuring Mathematical Problem Solving With the MATH Dataset. In NeurlPS Datasets and Benchmarks.
[20] Zhiyuan Hu, Yibo Wang, Hanze Dong, Yuhui Xu, Amrita Saha, Caiming Xiong, Bryan Hooi, and Junnan Li. 2025. Beyond 'Aha!" Toward Systematic Meta-Abilities Alignment in Large Reasoning Models. CoRR abs/2505. 10554 (2025).
[21] Aaron Jacch, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, Alex Iftimie, Alex Karpenko, Alex Tachard Passos, Alexander Neitz, Alexander Prokofiev, Alexander Wei, Allison Tam, Ally Bennett, Ananya Kumar, Andre Saraiva, Andrea Vallone, Andrew Duberstein, Andrew Kondrich, Andrey Mishchenko, Andy Applebaum, Angela Jiang, Ashvin Nair, Barret Zoph, Behrooz Ghorbani, Ben Rossen, Benjamin Sokolowsky, Boaz Barak, Bob McGrew, Borys Minaiev, Botao Hao, Bowen Baker, Brandon Houghton, Brandon McKinzie, Brydon Eastman, Camillo Lugaresi, Cary Bassin, Cary Hudson, Chak Ming Li, Charles de Bourcy, Chelsea Voss, Chen Shen, Chong Zhang, Chris Koch, Chris Orsinger, Christopher Hesse, Claudia Fischer. Clive Chan, Dan Roberts, Daniel Kappler, Daniel Levy, Daniel Selsam, David Dohan, David Farhi, David Mely, David Robinson, Dimitris Tsipras, Doug Li. Dragos Oprica, Eben Freeman, Eddie Zhang, Edmund Wong, Elizabeth Proehl, Enoch Cheung, Eric Mitchell, Eric Wallace, Erik Ritter, Evan Mays, Fan Wang, Felipe Petroski Such, Filippo Raso, Florencia Leoni, Foivos Tsimpourlas. Francis Song, Fred von Lohmann. Freddie Sulit, Geoff Salmon, Giambattista Parascandolo, Gildas Chabot, Grace Zhao, Greg Brockman, Guillaume Leclere, Hadi Salman, Haiming Bao, Hao Sheng, Hart Andrin, Hessam Bagherinezhad, Hongyu Ren, Hunter Lightman, Hyung Won Chung, Ian Kivlichan, Ian O' O'Coneell, Ian Osband, Ignasi Clavera Gilaberte, and Ilge Akkaya. 2024. OpenAl ol System Card. CoRR 2iss/2422.1622 (2024).
12

---

[22] Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and Ion Stoica. 2024. LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code. CoRR abs/2403.07974 (2024).
[23] Siyuan Jiang, Jia Li, He Zong, Huanyu Liu, Hao Zhu, Shukai Hu, Erlu Li, Jiazheng Ding, Yu Han, Wei Ning, Gen Wang, Yihong Dong, Kechi Zhang, and Ge Li. 2024. aiXcoder-7B: Lightweight and Effective Large Language Model for Code Completion. CoRR abs/2410.13187 (2024).
[24] Mark Kaminski and Tobias Tebbi. 2013. InKreSAT: Modal Reasoning via Incremental Reduction SAT. In Automated Deduction CADE-24 24th International Conference on Automated Deduction, Lake Placid, NY, USA, June 9-14, 2013. Proceedings (Lecture Notes in Computer Science, Vol. 7898), Maria Paola Bonacina (Ed.). Springer, 436-442.
doi:10.
011-388774-22
(25) Richard M. Karp- 1972. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations (The IBM Research Symposia Series). Plenum Press, New York, 85-103.
[26] Jia Li, Hao Zhu, Huanyu Liu, Xianjie Shi, He Zong, Yihong Dong. Kechi Zhang, Siyuan Jiang, Zhi Jin, and Ge Li. 2025. aiXcoder-7B-v2- Training LLMs to Fully Utilize the Long Context in Repository-leve Code Completion. CoRR abs/2503.15301 (2025).
[27] Yujia Li, David H. Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang. Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. 2022. Competition-Leeve Code Generation with AlphaCode. CoRR abs/2203.0782 (2022).
[28] Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. 2024. Let's Verify Step by Step. In ICLR. OvenReview.net.
[29] Michael Luo, Sijun Tan, Justin Wong, Xiaoxiang Shi, William Y. Tang, Manan Roongta, Colin Cai, Jeffrey Luo, Li Erran Li, Raluca Ada Popa, and Ion Stoica. 2025. DeepScaleR: Surpassing O1-Preview with 1.5B Model by Scaling RI.. htttt::://gtthtiie com/ hatm//aaaaaaaooeeett.. Notion Blog.
r11m
[30] Raffaele Marino. 2024. Fast Analysis of the OpenAl O1-Preview Model in Solving Random K-SAT Problem: Does the LLM Solve the Problem Itself or Call an External SAT Solver? CoRR abs/2409.1 1232 (2024).
[31] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel J. Candès, and Tatsunori Hashimoto. 2025. sl: Simple test-time scaling. CoRR abs/2501.19393 (2025).
[32]
OpenAl. 2024. OpenAl 03-mini.
[33] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. 2022. Training language models follow instructions with human feedback. In NewrIPS.
[34] Leyan Pan, Vijay Ganesh, Jacob D. Abernethy, Chris Esposo, and Wenke Lee. 2024. Can Transformers Reason Logically? Study in SAT Solving. CoRR abs/2410.07432 (2024).
[35] David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R. Bowman, 2023. GPQA: Graduate- Google-Proof Q&A Benchmark. CoRR abs/2311. (2023).
13

---

[36] Roberto Sebastiani and Adolfo Villafiorita. 1998. SAT-Based Decision Procedures for Normal Modal Logics: A Theoretical Framework. In Artificial Intelligence: Methodology, Systems, and Applications, 8th International Conference, AIMSA '98, Sozopol, Bulgaria, September 21-13, 1998, Proceedings (Lecture Notes Computer Science, Vol. 1480), Fausto Giunchiglia (Fd.). Springer, 377-388. doi:10. 1007 20000//FBOOG BBBB0057406
[37] Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, Chuning Tang. Congcong Wang, Dehao Zhang. Enming Yuan, Enzhe Lu, Fengxiang Tang. Flood Sung, Guangda Wei, Guokun Lai, Haiqing Guo, Han Zhu, Hao Ding, Hao Hu, Hao Yang, Hao Zhang. Haotian Yao, Haotian Zhao, Haoyu Lu, Haoze Li, Haozhen Yu, Hongcheng Gao, Huabin Zheng. Huan Yuan, Jía Chen, Jianhang Guo, Jianlin Su, Jianzhou Wang, Jie Zhao, Jin Zhang. Jingyuan Liu, Junjie Yan, Junyan Wu, Lidong Shi, Ling Ye, Longhui Yu, Mengnan Dong. Neo Zhang, Ningchen Ma, Qiwei Pan, Qucheng Gong, Shaowei Liu, Shengling Ma, Shupeng Wei, Sihan Cao, Siying Huang, Tao Jiang. Weihao Gao, Weimin Xiong, Weiran He, Weixiao Huang, Wenhao Wu, Wenyang He, Xianghui Wei, Xianqing Jia, Xingzhe Wu, Xinran Xu, Xinxing Zu, Xinyu Zhou, Xuehai Pan, Y. Charles, Yang Li, Yangyang Hu, Yangyang Liu, Yanru Chen, Yejie Wang. Yibo Liu, Yidao Qin, Yifeng Liu, Ying Yang, Yiping Bao, Yulun Du, Yuxin Wu, Yuzhi Wang, Zaida Zhou, Zhaoji Wang, Zhaowei Li, Zhen Zhu, Zheng Zhang. Zhexu Wang, Zhilin Yang, Zhiqi Huang, Zihao Huang, Ziyao Xu, and Zonghan Yang. 2025. Kimi k1.5: Scaling Reinforcement Learning with LLMs. CoRR abs/2501. 12599 (2025).
[38]
OpenThoughts Team. 2025. Open Thoughts. https:/opee--houuhttaai
[39] Qwen Team. 2025. Qwen2.5-1M: Deploy Your Own Qwen with Context Length up 1M Tokens.
[40] RUCAIBox STILL Team. 2025. STILL-3-1.5B-Previeee A 1.5B slow-thinking reasoning model continuously evolving through RL. https://github. COT/R/CAAAAAAAAO/SSL....... Twwnsoooooohiiinngoooo.o
with LLMs
[41] Yongqi Tong, Sizhe Wang, Dawei Li, Yifan Wang, Simeng Han, 7i Lin, Chengsong Huang, Jiaxin Huang, and Jingbo Shang. 2024. Optimizing Language Model's Reasoning Abilities with Weak Supervision. CoRR abs/2405.000SS (2024).
[42] Xin Wang, Yudong Chen, and Wenwu Zhu. 2022. A Survey on Curriculum Learning, IEEE Trans. Pattern Anal. Mach. Intell. 44, 9 (2022), 4555-4576.
[43] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoe V. Le, and Denny Zhou. 2022. Chain-of-Thoughh Prompting Elicits Reasoning in Large Language Models. In NewrIPS.
[44] Yixuan Weng, Minjun Zhu, Fei Xia, Bin Li, Shizhu He, Shengping Liu, Bin Sun, Kang Liu, and Jun Zhao. 2023. Large Language Models are Better Reasoners with Self- Verification. In EMNLP (Findings). Association for Computational Linguistics, 2550-2575.
[45] Shuang Wu, Liwen Zhu, Tao Yang, Shiwei Xu, Qiang Fu, Yang Wei. and Haobo Fu. 2024. Enhance Reasoning for Large Language Models in the Game Werewolf. CoRR abs/2402.02330 (2024).
[46] Chulin Xie, Yangsibo Huang, Chiyuan Zhang, Da Yu, Xinyun Chen, Bill Yuchen Lin, Bo Li, Badih Ghazi, and Ravi Kumar. 2024. On Memorization of Large Language Models in Logical Reasoning. CoRR abs/2410,23123 (2024).
[47] Tian Xie, Zitian Gao, Qingnan Ren, Haoming Luo, Yuqian Hong. Bryan Dai, Joey Zhou, Kai Qiu, Zhirong Wu, and Chong Luo. 2025. Logic-RL: Unleashing LLM Reasoning with Rule-Based Reinforcement Learning. CoRR abs/2502.14768 (2025). doi:10. 485500/8555/AAII
2502. 14768 1476
[48] Yuzhuang Xu, Shuo Wang, Peng Li, Fuwen Luo, Xiaolong Wang, Weidong Liu, and Yang Liu. 2023. Exploring Large Language Models for Communication Games: An Empirical Study on Werewolf. CoRR abs/2309. 20./2309.046688 (2023).
14

---

[49] An Yang, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoyan Huang, Jiandong Jiang, Jianhong Tu, Jianwei Zhang, Jingren Zhou, Junyang Lin, Kai Dang, Kexin Yang, Le Yu, Mei Li, Minmin Sun, Qin 7hu, Rui Men, Tao He, Weijia Xu, Wenbiao Yin, Wenyuan Yu, Xiafei Qiu, Xingzhang Ren, Xinlong Yang. Yong Li, Zhiying Xu, and Zipeng Zhang. 2025. Qwen2.5-1M Technical Report. arXiv preprint arXiv:2501. 15383 (2025).
[50] Zhaojian Yu. Yinghao Wu, Yilun Zhao, Arman Cohan, and Xiao-Ping Zhang. 2025. Z1: Efficient Test-time Scaling with Code. arXiv preprint arXiv:2504. 00810 (2025).
[51] Kechi Zhang, Ge Li, Yihong Dong, Jingjing Xu, Jun Zhang, Jing Su, Yongfei Liu, and Zhi Jin. 2024, CodeDPO: Aligning Code Models with Self Generated and Verified Source Code. CoRR abs/2410.05605 (2024).
[52] Yizhe Zhang, Jiarui Lu, and Navdeep Jaitly. 2024. Probing the Multi-turn Planning Capabilities of LLMs via 20 Question Games. In ACL (7). Association for Computational Linguistics, 1495-1516.
[53] Huaixiu Steven Zheng. Swaroop Mishra, Xinyun Chen, Heng- Tze Cheng, Ed H. Chi, Quoe V. Le, and Denny Zhou. 2024. Take a Step Back: Evoking Reasoning via Abstraction Large Language Models. In ICLR. OpenReview.net.
[54] Haijun Zhou. 2004. Long Range Frustrations in Spin Glass Model of the Vertex Cover Problem. CoRR 1077 (2004).
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the main contributions, including the curriculum learning framework SATURN and the SATURN-2.6K dataset. All supported by experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of SATURN in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
15

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Any informal proof provided in the core of the paper is complemented by formal proofs the appendix, including the rigorous derivation of SAT estimation.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We release all code, models, datasets, and experimental results ensure full reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same
16

---

dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-sonnee open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We release all code, models, datasets, and experimental results, along with detailed information on the execution environment to ensure full reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co public/guides/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/nniss /mipsscc/pptlee httpsccccccgbccueeeeeeeeeeeeeeee httpc//gguuieee/eoouuuubibiibiia ssioooolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
17

---

We provide all important parameters needed to understand the results in the appendix, and the code scripts include complete training and test details.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Following current evaluation practices in recent large model benchmarks, report the unbiased estimator of the passêk metric. This expectation-base based metric is designed to reflect statistical significance across multiple samples and inherently captures sampling variability. Although do not report explicit error bars, pass@k inherently reflects statistical reliability. Further details are provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2- 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide details on the GPU resources used for experiments well as information on all data storage.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
18

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://///eaaeppsscccccc///////a
Answer: [Yes]
Justification: We have reviewed and ensured that all research conducted in this paper fully conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper focuses on improving LLMs' reasoning capability through SAT- URN curriculum learning framework, without direct deployment or application, and thus does not raise societal impacts concerns.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This paper poses no foreseeable risks of misuse, it does not involve the release of high-risk models or datasets.
19

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We properly credit all used assets in the paper and appendix, including code, datasets, and models. Licenses and terms of explicitly stated and respected.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pwpprswi thooe.. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release new code, datasets, and models. All new assets are thoroughly documented, including usage instructions and data format specifications, which are provided alongside the release.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
20

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: subjects.
This paper does not involve any form of crowdsourcing or research with human
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects, so IRB approval is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the L.M is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This paper does not involve the use of LLMs as an important, original, or non-standard component of the methodology.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy for what should or should not be described.
21

---

Appendix
Table of Contents
Appendix
Pseudocode of SATURN Algorithm
Appendix
Procedure SAT Constructor
Appendix
Derivation and Validity of the SAT Difficulty Estimation
Appendix
Training Schedule for SATURN-L.SD and SATURN-7B
Appendix
Evaluation Hyperparameters
Appendix
Prompt Templates
Appendix Detailed Performances of SATURN Models on SATURN-2.6k
Appendix
Ablation Details for SATURN
Appendix
Behavior of Stronger LLMs SATURN Tasks
Appendix
Examples of LLMs Reasoning Trajectories
Appendix
Comparisons Existing Reasoning Tasks
Appendix
SATURN-7B Word Cloud on GPQA Diamond
A
Pseudocode of SATURN Algorithm and Hyperparameters
Algorithm presents the complete algorithmic workflow of SATURN.
Algorithm SATURN Searning_Loopli k, kg)
LLM represents Te
def Increase_difficutty. (n, k, 1, step-1):
uen Increments by D_step to increase SAT difficulty.
return n, k, + D_step
def SATURN__earning_Ln loop (n, k, 1, LLM): for t in range
Max total curriculum iterations
# Step 1: Curriculum Estimation Loop # Generate validation set
Val_set uAr_Construction(n. k, 1, Val_size) pass_at_1 evaluate (Val_set, LLM) Evaluate pass@1
if pass_at_1 1 >= epsilon:
n, k, 1 Increase_difficcule else:
k, 1)
# Step 2: LLM Training Loop (only if pass_at_1 < epsilon) for in (ange(10):
Max GRPO steps per level
# Generate training set D_train SAT_ Construction (n, k, 1, Train_size) GRLO D_train)
Re-generate validation set Val_set - SAT_Construtioon k, 1, Val_size)
pass_at_1 evaluate (Val_set, LLM) Evaluate passe1 if pass_at. at_1 >- epsilon: break
return LLM
Table shows all SATURN hyperparameters.
22

---

Table 6: SATURN Hyperparameters
Parameter
SATURN-1.5B
SATURN-7B
Initial (n, k,
(3
(3,5, 13)
passčk threshold e
0.5
0.75
Training set size per step (Train_ Validation set size per step (Val_size) Difficulty increment (D_step) Curriculum iterations
250
250
40
40
2
2
Max GRPO steps per level
10
10
B Construction Procedure of SAT Instances
This appendix describes the implementation details of the SAT Construction algorithm introduced in Section 2.1 The goal is to generate m satisfiable (n, k, 1)-SAT instances in conjunctive normal form (CNF), each constructed to be consistent with known Boolean solution. The algorithm ensures diversity and uniformity across sampled instances.
The construction procedure is outlined in Algorithm 2 and consists of the following steps:
1. A Boolean solution is randomly generated for the variables.
2. The constructor randomly selects variables from the variables form clause.
3. Under the constraint of satisfying the solution, the variables randomly negated, resulting in 2" satisfiable clauses per variable set. From these steps, we uniformly obtain a large number of single-clause samples from the total of 2 (2 - 1) valid (solution, clause) pairs, with an upper bound set to 100,000.
4. These (solution, clause) pairs are grouped into clusters based on the same solution.
5. Within each cluster, randomly select [ clauses and shuffle their order to construct full SAT instance that satisfies the corresponding solution.
6. Finally, we uniformly sample across clusters and remove duplicates to obtain a total m diverse SAT instances.
C Derivation and Validity of Difficulty Estimation for SAT Tasks on LLMs
As stated in Section 2.2 we propose composite difficulty function Eq. ( to estimate the reasoning difficulty of SAT problems for LLMs. This difficulty score combines a sparsity-based estimate of solution density with a structural complexity adjustment.
Step 1: Sparsity-Baseee Based Estimate (D₂)
We first estimate task difficulty by measuring the ratio between symbolic search cost and expected solution space size.
The symbolic search cost is approximately proportional to the number of variable-symbol combina- tions across decoding steps. For a problem with variables and decoding steps, we estimate:
Search Cost k-
For Boolean constraint problems like SAT, the number of satisfying assignments is sparse. Assuming random clauses, the expected number of valid solutions is:
Expected Solutions = 2" = 2"
(5)
where approximate 2" - by 2n for analytical simplicity.
Taking the ratio and applying a logarithmic transform yields:
Di(n, k, () logo logg (2") loga (k) log,
(6)
23

---

# solution >> list of clauses Algorithm 2 SAT_ (onstrructionn/,,kk...
def SAT "TT_Construccion (n, ,, 1, m)
V [x_1, x_2, x_k] # k Boolean variables
()
# pool of (solution, clause) pairs
Step 1-3: Generate (solution, clause) pairs
while (P) 100000: max number of single-clause samples vars = sample_ variaalevriables( n) # select vars from V e.g., [x_2, x_4, ...]
solution random_assign (vars)
# assign 0/1 vars # e.g., {x_2:1, x_4:0, ...
clause = generate (vars, solution)
# create clause e.g., {x_2 !x_4 ...
add ((solution, clause))
store pair
Step 4: Group by solution
clusters = group_by.solutione
Step 5-6: Construct m SAT instances
instances = set()
while len (instances) < m:
solution, clauses
(clusters) # select group selected_clausee = sample clauses
if len lenccluses) 1: continue
cacuusesccauueee (clauses, 1) # pick clauses
shuffle instances add (solution, selected, (catted__lausss)
return instances
Step 2: Structural Complexity Adjustment (D2)
In addition to solution sparsity, symbolic reasoning difficulty also depends on the structural properties of the input formula. We construct structure-aware term D2(n, k. based on two contributing factors.
First, consider the symbolic reuse density: when & variables are reused across clauses, each variable is, on average, involved in n/k constraints. This increases the interdependency between clauses. Since higher reuse leads to greater symbolic entanglement, making factorization more challenging for the model, define the inverse ratio & proxy for the structural cost:
Variable Interaction Cost
Second, the clause length determines the number of symbols that each clause contains. Longer clauses introduce more intra-clause dependencies, increasing local reasoning complexity. We approx- imate this with:
Clause Width Cost = (1)
These two components affect reasoning difficulty independently-one globally through variable sharing, and the other locally through clause complexity. We, therefore, combine them additively into:
k n
Dz(n,k,1)
logg(()
This additive form is justified as both terms grow monotonically with symbolic complexity and are approximately aligned in scale, enabling stable and interpretable difficulty estimation.

---

Step 3: Final Composite Metric
Combining both components yields:
D(,k,1) D1 Di k, + D2(n, k1,)
(10)
-log2 (k) + loga(1) (1) +
+ log2(1)
(11)
k
=log2 + logg(1) - +
(12)
This final composite metric provides a stable and interpretable approximation of symbolic difficulty for LLMs, taking into account both sparsity and structure.
Step 4: Ablation Study about estimation metric
To further validate the necessity and effectiveness of Eg. 12 composite metric, we conduct an ablation study comparing alternative formulations. Table 7 reports the 122 correlation of each metric with LLM performance (pass03) across multiple model scales.
Table 7: Metric comparison across models.
Metric Formula
RI- RI-Qwen-I..B Satum-1.55B RI R1-Qwen-7B Saturn-7B Avg.
Std. Dev.
k 1ogg
0.507
0.537
0.132
0.000
0.294
0.269
+ B (I), 2,
0.428
0.478
0.568
0.508
0.496
0.059
a- E 3 log,(1),
8=1
0.240
0.279
0.719
0.826
0.516
0.300
log2(k- - 1) 12g -1)
0.875
0.893
0.451
0.157
0.594
0.356
logg(k) + (l) n A
0.707
0.746
0.724
0.501
0.670
0.113
Simpler metrics that consider only sparsity or only structural complexity perform worse overall, confirming that both components essential for accurately capturing task difficulty. Our metric (kg + 2 loga
+ combines both solution sparsity and structural complexity, which achieves the best overall correlation. The ratio between the solution space and the LLM's search space is the most crucial aspect. On SATURN-7B, the It2 value is about 0.5 because the LLM already achieves over 90% accuracy on easy problems, which limits the observable linear correlation that range. The corresponding figures are shown in Figures and II
D Training Schedule for SATURN-1.B and SATURN-7B
This appendix provides additional details on the SATURN-1.SB and SATURN-7B training. We conduct all experiments on 8 NVIDIA A A100 40GB GPUs. We use the OpenRLHF framework for GRPO training. The framework designed to make RL training simple and user-friendly, which works well in our experiments. The hyperparameters used in training are summarized in Table All other parameters not listed above consistently follow the default settings of OpenRLHF.
Figure 6 and Figure illustrate the training curves of SATURN-I.55 and SATURN-7B. Both models show clear upward trend in the average reward during training, accompanied by early fluctuations that gradually stabilize. The maximum reward curves quickly reach high values and maintain them throughout most of the training process. These results indicate that both SATURN- 1.5B and SATURN-78 successfully learn to generate high-reward outputs, demonstrating effective SAT reward- guided optimization.
E
Evaluation Hyperparameters
This appendix provides additional details on the hyperparameters used in the evaluation. We use the Hugging Face lighteval library for math and programming evaluations. It offers efficient bench- marks, helping us assess LLMs' performance across various tasks while ensuring both computational
httpss//ggthabbb.om//gggggggggg/
25

---

Table 8: OpenRLHF Training Hyperparameters
Parameter
SATURN-1.5B
SATURN-7B
Actor learning rate
5
10-7
5 10-7
Initial KL coefficient
1 X 10-3
1 x 10
Batch size (train)
2
2
Batch size (rollout)
2
2
Samples per prompt
8
8
Prompt length (max)
1024
1024
Generation length (max)
10000
8192
Temperature
0.8
1.0
Zero redundancy stage
3
3
Use bfl6
Yes
Yes
KL estimator
k3
k3
Advantage estimator
GroupNorm Yes
GroupNorm Yes
Use reward normalization
train/mak_rewart
train/reward
Saturn-158
Satum-1158
0.6
0.2
-0.2
Step -0.4
Step
Figure 6: Training curves of various metrics for SATURN-1.5B.
efficiency and high-quality results. For the evaluation of the DeepSeck-RR series distillation models, we use lighteval with the Hugging Face-Open Oaee--0eRRR R1 framework This framework effectively reproduces the evaluation results of the R1 series models.
During the evaluation process, we follow the parameter settings from Hugging Face-Open-Ri. as shown in Table 9 Additionally, for LivchodeBench, we also select the default v4_vd v5 version of
train/max_rent reward Saturn-78
train/reward Saturn-7B
0.8
0.5
0.6
0
0.4
0.2
-0.5
Stop
50
100
150
200
50
100
150
200
Figure Training curves of various metries for SATURN-7B.
26

---

this framework. Due to the long inference budget required by LiveCodeBench. we set the maximum response length 16K and generate four samples per instance estimate pass 1. All other parameters not listed and mentioned above consistently follow the default settings of Hugging Pace-Open-R1.
For larger closed-source models, we report the benchmark results from a public benchmark website
Table 9; Evaluation Hyperparameters for Hugging Face-Open-Ri
Hyperparameter
Setting
Data type
bfloat16
Maximum model length
32,768
Maximum new tokens
32,768
Temperature
0.6
Top-p (nucleus sampling)
0.95
Prompt Templates
This appendix provides the prompt templates used for evaluation, ensuring consistency and repro- ducibility across tasks. Figure presents the format for SAT problem training and evaluation, while Figure shows the template used for math, programming, and GPQA Diamond tasks.
SAT:
You are now required to solve a SAT (Boolean Setistiabilitt) preblem.. The problem provided in JSON Format, containing the following fields:
"o. sac": The number variables each clause (n-SAT problem).
-k": The total number distinct variables the problom.
"clause": A string representation of the SAT formula, where clauses are separated by & (reprenenting logical AND). Within each clause, variables are combined using concatenation (represcnting logical OR). negation is indicated by "!" before a variable.
Your provide valid
answer string length representing
for true, for false). there multiple solutions, provide one of them.
Please reason step by step, and put your final answer within lboxed
"EExmmple**
("o sot": 3, "clause": "IBIC'D & AIBD ABID")
**Final Answer+*
(100)
Below the SAT problem you aced solve:
Figure 8: Prompt format used for SAT problem training and evaluation.
G Detailed Performances of SATURN models on SATURN-2.6K
This appendix provides additional details of SATURN- and 7B on SATURN-2.6K spanning 10 harder SAT difficulty levels. Experimental results are shown in Table 14 and Figures 11 We summarize two key observations:
The pass @3 accuracy correlates strongly with the estimated SAT difficulty D(n k, across models. Specifically, the linear regression R.2 scores are 0.746 for SATURN-1.5B and 0.707 for DeenSeek-RI--Disill--eee.
(Figure IO), and 0.5011 for SATURN-7B and 0.724 for DeepSeek- RI-Distill-Qwen-77 (Figure [T]. These results indicate that our difficulty function effectively captures problem hardness, supporting the design of curriculum learning schedule based on it. They also demonstrate that SAT is a reliable benchmark for evaluating reasoning capability.
http:://aartificcalaanysss aimodells
27

---

Math:
Solve the following math problem efficienlly and clowly. The line of your respouse should of following format: Therefore, the final nnewer is: Sthoxed JNSSWRRS. Is. hope correct (without quotes) where ANSWER is just the final number expression solves problem. Think by step before answering.
(question)
Peogramming:
You given question (problem specifieution) will genertte correct Python progrum that matehes the specification and passes all tests.
Question: (question)
You will use the following starter code to write the solutioe the problem and cuelose code within delimiters. ' "pythou (starter code)
Multiple Chotce Question (GPQA Diamondy:
Answer the following maltiple choice question. The last lire of your response should be the following format: "Answer: SLETTER (without quoces) where LETTER
Think step by step before
(question)
Figure 9: Prompt format used for math, programming, and GPQA Diamond problems evaluation.
@ Although our models trained only on relatively casier SAT problems, they show consistent improvements on harder levels. As shown in Table TO 14 both SATURN-1 --.5 and SATURN-7B generalize well more challenging problems, highlighting the effectiveness of our curriculum-driven training strategy.
Table 10: Full passã1 results SATURN-2.6K
Model
(3.7,40)
(3,5,25)
(3,5,20)
(3,6,20)
(3,7,20)
(4,7,40)
(488,0)
(4,7,20)
(6,7,40)
(5,8,40)
Avg.
R1-Distil--L.5B
1.3
3.3
3.3
1.6
7.2
10.6
3.6
SATURN-I.5B
0.3
6.2
7.8
7.3
8.9
3.3
4.2
22.5
29.0
12.9
10.2
RI-Distill-7P
12.3
19.2
23.3
21.5
4.5
30.1
24.4
12.3
15.4
SATURN 7B
44.7
66.4
64.5
64.6
9.2
10.3
57.3
36.4
19.2
38.1
Table 11: Full pass@3 results on SATURN-2.66
Model
(3,7,40)
(3,5,25)
(3,5,20)
(3,6,20)
(3,7,20)
(4,7,40)
(488,40)
(4,7,20)
(6,7,40)
(5,8,40)
Avg.
RI-Distill-1.5B
3.8
9.4
9.1
4.7
19.3
10.1
SATURN-I.5B
0.8
15.8
19.5
18.5
21.6
9.5
11.3
50.3
62.5
31.7
24.2
RI-Distll-7B
6.5
31.2
45.6
52.8
49.9
10.4
11.8
65.6
56.2
31.3
36.1
SATURN-7B
22.9
78.2
94.1
24.3
26.5
91.0
72.4
64.2
Table 12: Full pass@5 results on SATURN-2.6K
Model
(3,7,40)
(3,5,25)
(3,5,20)
(3,6,20)
(3,7,20)
(4,7,40)
(4,8,40)
(4,7,20)
(6,7,40)
(5,8,40)
Avg.
RI 1i-Disilll-.S.
1.7
6.1
14.9
14.2
7.6
29.2
43.7
19.6
15.7
SATURN-1.5B
1.3
23.5
27.9
26.7
30.6
14.9
17.2
67.0
79.0
44.1
33.2
R1-Distill-7B
10.5
44.7
62.3
69.2
66.9
16.0
17.5
82.9
74.0
45.4
48.9
SATURN-7E
34.4
89.5
98.5
98.6
98.2
35.9
38.6
97.5
86.4
62.4
74.0
Table 13: Full pass@7 results on SATURN-2.6K
Model
(3,7,40)
(3,5,25)
(3,5,20)
(3,6,20)
(3,7,20)
(4,7,40)
(4,8,40)
(4,7,20)
(6,7,40)
(5,8,40)
Avg.
RI RI-Distill-LL511
2.3
8.1
19.9
18.9
18.9
7.6
10.1
37.4
55.7
25,8
20.5
SATURN-1.5B
34.2
22.1
78.2
39.7
RI-Distill-BB
14.3
54.6
73.6
78.7
20.9
22.2
91.6
84.3
$7.4
SATURN 7B
43.7
94.2
99.6
99.7
99.5
45.0
47.6
99.2
92.2
73.5
79.4
28

---

Table 14:
Full pass@10 results on SATURN-2.6k
Model
(3,7.40)
(3,5,25)
(3,5,20)
(3,6,20)
(3,7,20)
(4,7,40)
(4,8,40)
(4.7.20)
(6.7,40)
(5,8,40)
Avg.
RI-Disull-I.5B
3.3
10.6
26.8
25.2
24.6
10.8
14.5
47.9
69.3
33.7
26.7
SATURN-1..
38.7
41.3
28.0
89.6
R1-Distil--BB
19.6
65.0
84.7
86.6
87.8
27.2
27.9
97.4
92.8
68.6
65.8
SATURN-7B
54,9
97.1
99.9
99.9
100.0
55.0
$7.3
99.8
95.3
84.7
84.4
SAT Problem Solving: Difficulty vs. Pass@3
0.6
x
(6.7,40)
Satum-12 1.50:
DeepSeek- Distill Owen 50: pass@3=-0 0.00- 06000+0.0
paso@3=0014-441.00
(4.7,20)
0.5
Pass@3 (%)
(5.8,40)
0.3
X167740)
(377200)
0.2
(4:7.20)
(36.00)
(3.5.25)
((5.8.40)
(4.740)
0.1
x3.5.2
X(3.6.20)
(5.7.20
((3.525)
x447740
12
Difficulty (D)
Figure 10: Scatter plots of pass@3 versus estimated difficulty D(n, k. for DeepSeck-RI-Disttee Qwen-1.5B and SATURN-1.5 1.5N- ..5B, with linear regression fits. The linear regression for two models achieve R² values of 0.707 and 0.746 respectively.
SAT Problem Solving: Difficulty vs. Pass@3
1.0
DeepSeek-RL Datill Qwen-78. pass@3=-0015 D+ pass$3--
(3,6200)
(37,20
(6.7.00)
0.8
(35.25)
(6.7.40)
x
(4.220)
Pass@3 (%)
0.6
x (6.7.00
x (36,20)
(37.200)
(5.8.40)
XX (3.5.25)
(488400)
(4.7,40)
x
0.2
(47440)
x (488400)
12
0.0
9
10
11
12
Difficulty (D)
Figure 11: Scatter plots of pass#3 versus estimated difficulty Dnn, k 1) for DeepSeek-R -Distill- Qwen-7B and SATURN-7B, with linear regression fits. The linear regression for two models achieve R2 values of 0.724 and 0.501 respectively.
29

---

H
Ablation Studies for SATURN
This appendix presents the ablation studies for SATURN, as shown Table 13 and Table T6 Each training setting is denoted (n, k. 1) Train_size, where (n, k, controls SAT construction and Train_size ssie is the number of training examples, Here, Train_size can also be written as Train_size size D num, where is the number of difficulty levels and num is the number of samples per level in SATURN-2.6K (Figure 11 and 1Op. These experiments validate the effectiveness of curriculum learning and the design various SAT training configurations.
Table 15: Ablation comparison on math and programming benchmarks
Truining Setting
AIME 24/25
AMC 22/23
Math500
GPQA-D
LiveCudeBench
Avg.
(3,5, 10) x 500
45.0
84.3
93.2
53.5
35.1
62.2
53,5, 500
50.0
83.1
94.6
50.0
36.1
62.8
(3,5, 15) x 500
35.0
68.7
86.6
46.0
31.3
53.5
(3,5, 13) x 1000
51.7
81.9
94.0
47.5
37.2
62.5
(13,5, 13) (3,5, 15)) 500 (one epoch)
43.3
86.7
49.5
35.8
(3,5, x 500 + (3, 500
48.3
85.5
95.0
50.5
37.7
63.4
Table 16: Ablation Study with Different Sampling Strategies and Training Budgets
Training Setting
AIME 24/25
AMC 22/23
Math500
GPQA-D LiveCodeBench
Avg.
(7, k;,0) 100 10 shuffle
38.3
66.3
90.6
44.9
35.2
55.1
(1, k,1) (6.1)) 100 10
46.7
85.5
93.2
50.5
36.9
62.3
(n, k) x 200
5 shuffle
48.3
81.9
93.0
52.0
35.8
62.2
k,,) 200
46.7
88.0
93.2
48.0
35.8
62.6
(3.5, 13) 500 + (3.5, 15) 500
48.3
95.0
50.5
37.7
63.4
In Table 15 evaluate the impact of SAT difficulty, training budgets, and curriculum structure. We draw two key conclusions:
SATs that are too easy or too hard hinder model learning. Training solely easy (3, 10) X 500 hard (3, 5, 15) x 500 instances results in lower average scores (62.2 and 53.5, respectively). In contrast, moderate-difiie
SATs (3, 5, 13) x 500 yield a higher score of 62.8, showing that balanced difficulty essential for effective reasoning development.
@ Multi-stage curriculum learning outperforms flat or mixed training. Curriculum learning with progressively increasing SAT difficulty (3, 5, 13) x 500 (3, 5, 15) 500 achieves the highest average score of 63.4. In contrast, one-epoch mixed training ((3, 5, 13) + (3, 5, 15)) x 500 only reaches 61.7, despite using the same total number of examples. Furthermore, simply scaling up single-stage setting (3, 5, 13) x 1000 yields 62.5, which is also inferior to the curriculum. These results indicate that progressive difficulty scheduling is more effective than either flat or mixed training with the same or larger data budget.
Table 16 further investigates the impact of training thresholds and step sizes under fixed total training budget.
@ Gradual difficulty progression outperforms random shuffling of difficulty levels. Both (n, k. l) x 100 x 10 and (n, 1) x 200 perform better when difficulty levels follow a gradual progression (62.3 and 62.6), compared to random shuffling of difficulty levels (55.1 and 62.2). This demonstrates that a curriculum learning approach with progressive difficulty scheduling more effective.
Excessively fine-grained difficulty levels hinder performance. Training with overly fine-graid grained difficulty levels, such as (n, k, () x 100 10, results in lower performance (55.1) 1) compared to coarser steps like (ri, k. 1) 200 x 5 (62.6). Both these configurations perform worse than the two-stage curriculum (3, 5, 13) x 500 + (3, 15) x 500, which achieves the highest performance with an average score of 63.4. This indicates that excessively fine-grained difficulty levels prevent the model from effectively mastering each level before moving to the next, hindering overall learning.
30

---

I Behavior of Stronger LLMs on Extended SATURN Tasks
This appendix demonstrates the performance of stronger LLMs on more challenging SAT tasks. The experimental results are shown in Table[T7] Even the strongest LLMs available today cannot solve complex SAT tasks effectively as humans using simple reflection and verification search. Due to the long CoT involved, the full LLMs' outputs are provided in the supplementary material.
Table 17: One-shot performance of stronger LLMs extended SATURN tasks. Models with V successfully solve the corresponding difficulty of SAT tasks. Kimi-1.5 solves the task but with significantly longer reasoning chains.
SAT Task (n, k, length)
GPT-4o
O1-mini
DeepSeek-V3
R1
Kimi-1.5
(3, 5, 30)
X
V
(4, 7, 80)
X
X
X
x
x
To provide baseline comparison, we also tested CDCL SAT solver 6 on the SATURN-2.6K test set. The results are follows:
Table 18: CDCL SAT solver performance on SATURN-2.6K test set.
Metric
Value
Total instances
1000
Satisfiable
1000
Unsatisfiable
0
Valid SAT Models
1000
Model Accuracy
100.00%
Total time taken (s)
0.14
Table 18lleT8Sheer shows that the CDCL SAT solver significantly outperforms current L.LMs like DeepSeek- both in terms of runtime and accuracy. SATURN applied to today's 's strongest LLMs still has great potential.
Examples of Different LLMs' Reasoning Trajectories
This appendix presents examples of different LLMs' reasoning trajectories, shown in Figures 5 The full LLMs' outputs are provided the supplementary material.
and [2]
In the case of Math500-41 (Table 13), SATURN improves its ability to avoid unnecessary calculations and dead-end reasoning paths. By leveraging the self-verification patterns learned from SAT tasks, such as "I made a mistake earlier," SATURN-7B can better navigate through the problem, discarding invalid paths earlier in the process.
In the case of Math500-402 (Table SATURN-7B demonstrates a stronger ability to self-verify intermediate conclusions
smaller scenario (with individuals). While DeepSeek-Re RI-Distill Qwen-7B also tries to identify smaller scenario, it fails to recheck the result when an inconsistency found, instead stating, "perhaps I'm overcomplicating this." In contrast, SATURN-78 can identify the error and re-verify the results within this small scenario, ultimately selecting the correct solution from two possible candidates.
In conclusion, SATURN-7B exhibits enhanced self-verification capabilities. LLMs sometimes confidently claim that wrong answer is correct. Solving SAT tasks inherently involves frequent and fine-graide line-granned clause verification, which trains LLMs to perform precise checking during reasoning. The celf-verificatio patterns learned from SAT tasks help LLMs solve math problems more effectively by selecting correct solutions from multiple options. These results suggest that the self-verification mechanisms developed during SAT learning (Table [2) generalize well math and programming tasks, improving the LLMss' reasoning robustness and reliability.
littps://en. www.pppeaa..r///llt//ooooootoeee wttp:ddvvvvveccueeeeeeeeeeee _eauning
31

---

Question:
Cluue:: LAURID TATHIR& JAISC & JAIRE JATCIE IAIDIE & TARIE IRID & IRCE IRIER TRCIE IRCE & IBDIE & ICIDE & ICDE& & A ABIIC & AICID& & AICIE & ACCD & ABIC & ABIE & ADE & BICID & BOTE & BOIE
Saturn-7B
<tinkk> Olay, so I have this SAT problem to solve. Lei me ity to understamd what it's usking. The problem is given in. ISON ussignment
satisfies all cluuses. If can't find onc. I guess it's unsatisfiable, but I think should he satisfable since the example worked Fars First, let me parse the input. he ISON object has three fields: "n sat", "K', and "clause". "n sat" is 3, so it's 3-SAT problem. That means each clause has exietly variables connected by ORs. "k" is 5, there are distinet variables. Let mo list them out. Looking at the clause string, the variables A, B, C, D, E, So the variables are A, B, C, D, E. The "clause" field is a string that represects the SAT formula. Clauses are separated by & ", and within each clause, variables
format, and need
variables
to say
combined with concatenation, which represents ORR Negation indicaled by "1" before a variable So the clause string is: "IA'BID & IAIB'E & TATBC& & TATBE & LAICIE & IAIDIE & 'ABBE IBCIE IBCE
AIBIC AICID & ALCIE AICD & ABIC ABIE & ADE & BICID& & BCIE& & BDIE That's lot of clauses. Let me to break it down inco individaal clauses.
IBICD IBICE
ICIDE
IFE is Galse, then:Frum clause ID musi true (since is faise). So false From clause 14: IC OR ID OR E. Since E false and D false, ID true, so clause 14 is sarisfied.From clause 15: IC OR D OR D is false, B is false, so IC must he trae. So C is faise.From clause 17: 3C OR C false, clause satisfied From clause 18: IC OR E. is false, clause 18 is satisfied From clause 24 B OR C OR IE, C is false, E is false, so must be true From clmuse 25: B OR D OR 1E. B is tme, so lalse,
(liven clause 6)C false (from clause L5M true (from clause 24)Now, let's check other clouses with these assignments 3: 1B OR C. B is true, so IB is false. is false, so clause is folse. hat's a problem. this assignment doesn't work.
clause is salisfied.So So lan, assumning
FalseD
So the final answer is 1 000 boonee (10000)
Figure 12: Case study of SATURN-7B reasoning trajectory on a SAT instance.
Question:
Mach500-No. No.4 What the smallest posilive multiple of 450 whose digits are all zeroes and ones?
RI Mi-DistillQwee----
Satern-7B
-ddinaloo First. Eremember that a sumber that factoes into primes. Let me in, and times 450
"think kinww that number webe dealing with, Lets break
Wait, uo, was 9 5, which 3 5, So 450 is 3t 5t. Thut's importaat becouse any atthigle of 450 most he devisble by all these prine foctons.
hroik drrwn. 450
dlom facturs into
Wait no. bacause the sumber must have at least y is and and with rwo US. So, the mininal number would be 111111 11000, but aned to check if this the minimal
So smcollest possible would be would 11111111100 100. Wall,
with 9 So minimaal snch
saulleat?? Iet check.
Walt, when lniel divialing 111,111,111 450, got semeinale mayhe
colentation.
Wait, mashe arnange the way namber smaller exampic. (000000000000 has one bur wttp:///ooooooooooooooeooooooeo.
So, the mumbr 11111111100 is indeed a mubtiple of 150, and it's smallest such sumber because say smaller mumber would have lower digios. but we carl have fower than 11 digin bocoss we need 9 and 2 the ond--think- The smallest prective multigle of 45050 with all digits Our is 11131113100 1113
TThe digir or arpears besed(1000) times in the protagoniets first state digils TTink--To deternine how times digit ayeears in the first 5000
digins the number 1900000000000000000000
Figure 13: Comparison of reasoning trajectories on Math 500 Question No.41 between two models.
K Detailed Comparison of Constructed Reasoning Tasks
This appendix provides a detailed comparison between K&K logic puzzle and SAT problem. Illus- trative examples of each type are shown in Figure 14] While both are designed to test reasoning capability, they differ in construction cost, output format complexity, and difficulty control.
Construction Cost. K&K puzzles require translating symbolic logic into natural language. This involves paraphrasing logical constraints into grammatically and semantically valid sentences, which increases construction cost. In contrast, SAT problems are purely symbolic and follow a standard format. As shown in [18) symbolic SAT and its natural language version yield similar reasoning performance for LLMs, suggesting the symbolic form is sufficient.
Output Format Complexity. K&K puzzles require answers that list each character's identity in order, such (1) A is knight, (2) B is knave. This format imposes strict requirements structure, making it harder for LLMs to follow instructions. In practice, we observe that models struggle to learn this format in early training stages. SAT problems only require fixed-length binary string wrapped in \boxed(), which simplifies output and improves consistency during training.
Difficulty Control. K&K puzzles use the number of characters to control difficulty, which is coarse- grained. SAT problems allow ene-grained control via clause structure and variable interactions. We further define estimation of SAT task difficulty for LLMs as D(n, k l) logz(k) + 2 log, (!)
32

---

Logic RL Knights and Knaves (K&K) logic puzzle
Boolean Sutisfiability Problem
Prompt: You are required to solve a SAT (Beolem Suinfabbiiit)
Promut: You helpfal arsistant. The assistant first thinkss about the reasening process in the mind and then provides the user with the answer. The reasuning <thinkk> answee "hnnwwrr ligs, respectively, ie, <think- retsoning proveas here =ainke=-mmser"" amswer here </mnswer: mer soks you solve a logical rassoinng problem. After thinking. when you finally rescl conclosion, eleady state the idcarity
prahlem. problam provided JSON format, containing following fields:
and answer enclused within <think-
"a sart: The number of variahles in each clause (o-SAT problem). sumber distinct variables the problem.
"kk":
"clause": A string representation the SAT formuls, where clauses sre separated by & inepeesenting logical AND) Witain clause, varisbles are combined using concaicmation (xpreseming logicnl OR). negation indicated by "!" hefore vanable.
each charncter within <answer> clunwwrr tags. ke., sanswer> (1)
Zoey is knight (2) <lanswerr.
string longth k representinn the truth values of the variahles order for true, for false). there multiple solutions, provide any one of them.
Your task to provide valid solution. Tee
very special island inhabited only by knights knaves. Knights
always tell the truth, and knaves always lie. You meet 7 inlabitnnt::
Matthew, Noah that Matthow is knight and Victoris is knight. "Lily is knove if and
Nooh, Victoria, Ava, Lily, Daniel, Alexander,
Please resson step by siep, and put your final answer within lboxed ().
by "Mathhww is knight or Victoria is knight". Lily was heard suging. "If Vietoria knove then Matthew knave". Daniel commented.
Malthew knight," Victoria mentioned.
"Example**
I't sat": 3, "K:44 "clause": "IBICID AIBID ABBD") *"Finsl "Fiwee Answer*
"Alexander is not a knight",Alesnnae Alexander stated. "Nosh a knight or Ava knave". "Ava is knave". Matthew, who is knight and who a knave?
(bosed/1101;
Below the SAT problem you need to solve:
IATBC & JACE & IBICIE & AIBIE & AICE & ACD & EDIE")
suat: 3. "kk": "clause":
JACID
Figure 14: Comparison of Knights and Knaves (K&K) logic puzzle and SAT problem.
+ h. Adding a clause to a SAT formula never decreases its difficulty, for both humans and LLMs. This makes SAT more suitable for curriculum learning.
n'
In summary, while K&K puzzles provide linguistic diversity, SAT problems more efficient in construction, output consistency, and difficulty regulation, making them preferable for training LLMs at scale.
L Word Cloud of SATURN-7B's Outputs on GPQA Diamond
Saturn-7B Word Cloud for GPOA Diamand
proton
total
reat
carbondi
ney
theee ne tal ewrrutuuurr
two OH
ketone
e
opt 1on
nymber
answer
second
text
step
time
W
syneer
acid
question
correct
sight
form m
another
m
methyl
right
possible
pOS 1 t oo
H
C2
ellaina
charge
sqrt
Let
mUst
maybe
Tour
case
Bestituu
ener gy
Alternative
ppm
cco
ring
acjacent
r
g
Oup
Single
think
gnena
carbony
CH
Spprinng
Srrething
conething
Problers
gleaging
Bgetting
Compouma
one
have
Hmm
benzene
ea on
aigha
S state
pap
Xdouble
X
adid
S
D
make
bitt
take
proo
Postesution
Poducc
Brenk
thyyy
tached
different
mole oleeculecamme
distance sholate
sure
bond
Figure 15: Word cloud of SATURN-7BB generated answers on GPQA Diamond. Frequently used tokens are shown in larger fonts.
Figure shows the word cloud of SATURN-7B's generated answers GPQA Diamond, highlight- ing its frequent use of self-verificatiion patterns in reasoning.
33


Reviews:
[{"review_id": "HqGPx4lh89", "reviewer": "Reviewer_SUsx", "summary": "The authors propose SATURN, a RL framework intended to improve the reasoning capabilities of LLMs with SAT problems. Towards this end, they construct SAT problems (SATURN 2.6k dataset) of increasing difficulty to create a curriculum of reasoning problems of increasing difficulty. This is then interleaved with a LLM RL training loop (using GRPO) to improve LLM reasoning ability. They apply the framework to DeepSeek-R1-Distill-Qwen-1.5B and 7B, and demonstrate that the application of SATURN can improve the performance of the base LLMs on SAT problems. They also demonstrate that it can generalize to Math and Programming questions as well as complement other approaches to improve reasoning in LLMs.", "questions": "1. Do the authors have an explanation as to why such a method, even though it is trained on SAT, should generalize to other settings? For instance, does it encourage the LLMs to consider more cases and/or negations that help it reason more effectively in math/coding domains?\n2. Have you tested SAT problems that are not given as 3-SAT problems? I wonder about data leakage as the models have likely picked up instances of 3-SAT problems during pre-training. However, I would imagine that moderate-size SAT problems would be less prevalent on the internet since they are too large to be instructive or solvable without being converted into 3-SAT.\n3. Why does Saturn-7B perform worse on AIME24/25 compared to DeepSeek-R1-Distill-Qwen-7B?\n4. What does the lengthening phenomenon look like for a curriculum approach vs. a mixed training approach? While I appreciate the difficulty of performing all these ablations, I am curious, since curriculum learning adds another layer of complexity to the post-training step. Does mixed-training result in shorter responses compared to a curriculum approach?", "limitations": "The authors correctly highlight limitations in Section 4.1.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper works on an important problem—new methods to improve reasoning capabilities in LLMs. The proposed approach of combining curriculum learning and RL is natural. The study also is ablated (e.g., testing the efficacy of mixed training vs. curriculum) and comprehensive (e.g., testing transferability of SAT training to math/programming). Lastly, I found it promising that training on SAT problems could improve reasoning in other domains.\n\nWhile I believe the methods and study are sound, I found myself wishing for more explanation as to why such a method should work and for a deeper analysis of the reasoning chains produced as a result of training with SATURN. For instance, is it because training on SAT problems causes the model to take smaller reasoning steps, enumerate more cases, or something else, that also enables it to generalize better to math/coding problems?", "was_revised": true, "final_justification": "The discussion with the reviewers has helped answer some concerns on why SATURN. The two case studies that highlight LLM reasoning: (1) verification, (2) backtracking, (3) subgoal setting, and (4) backward chaining, should be put in appendix somewhere in the paper to help the reader understand why SATURN can help the reasoning process, and hopefully, inform future systematic study. Additional results, such as how the response length differs between curriculum learning and mixed training, would also be interesting to be put in the paper.\n\nOverall, I found the method to be promising (at the scale it is tested on). Nevertheless, provided that the code is open source and helps other researchers build on improving and analyzing LLM reasoning, I am leaning towards accepting this paper and am maintain my rating.", "rebuttal": "Thank you very much for your helpful comments. We respond to your concerns point by point in the following.\n\n## Q1: Why does SATURN work?\n\nWe appreciate the reviewer’s professional question regarding why training on SAT problems helps generalization to other domains such as math and code. We agree that understanding the underlying mechanisms is important. To this end, we offer key supporting evidence.\n\nA recent study, _Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs_ [1], identifies four core habits shared by expert human reasoners and LLMs:  (1) **verification**, (2) **backtracking**, (3) **subgoal setting**, and (4) **backward chaining**. These behaviors are domain-agnostic and fundamental for solving general reasoning tasks. And [2] proposed the same concept of meta-ability. The meta-ability represent general reasoning patterns that can be generalized across SAT, math, and programming tasks. In the following, we present additional case studies to illustrate how SATURN works.\n\n**Case 1**\n\nTo better understand how SATURN promotes these behaviors, we provide a case study comparing SATURN and a baseline model on the same SAT instance:\n\n> ¬A∨¬B∨¬D ∧ ¬B∨¬C∨D ∧ A∨¬B∨¬C ∧ A∨C∨E ∧ B∨C∨D\n\nR1-Distill-1.5B fails on this instance. Its trace is shown below:\n\n```\nWait, in the solution, D=0, so clause 3: A ∨ ¬B ∨ ¬C → 0 ∨ 0 ∨ 1 → True.\n\nYes, that's correct.\n\nClause 4: A ∨ C ∨ E → 0 ∨ 0 ∨ 0 → True.\n\nClause 5: B ∨ C ∨ D → 0 ∨ 0 ∨ 0 → True.\n\nSo, I think that's a valid solution.\n```\n\nThe model skips verification of earlier clauses and fails to backtrack after contradictions. The reasoning is shallow and linear. It does not apply backward chaining from goal constraints.\n\nIn contrast, SATURN-1.5B produces the following trace:\n\n```\nHmm, that's a contradiction. So, my assumption that B=False leads to a problem with clause 1. Therefore, B cannot be false.\n\nSo, B must be true. Let me backtrack.\n\nEarlier, I assumed A=True, and then B=False led to a contradiction. So, B must be true.\n\nLet me restart with A=True and B=True.\n\nThen, let's look at clause 1: ¬A ∨ ¬B ∨ ¬D. Since A and B are true, ¬A and ¬B are false, so for the clause to be true, ¬D must be true. Therefore, D must be false.\n\nSo, D=False.\n````\n\nThis trace shows verification of clause satisfaction, backtracking after an invalid assumption, and backward chaining from clause structure to variable assignments. These capabilities help the model reason accurately across steps.\n\n**Case 2**\n\nWe observe the same behaviors in LiveCodeBench.\n\n> You are given an array of positive integers `nums`.  \n> An array is called product equivalent if the product of all elements equals `gcd(arr) * lcm(arr)`.  \n> Return the length of the longest product equivalent subarray.  \n> A subarray is a contiguous non-empty sequence of elements in the array.\n\nThe R1-Distill-7B gives the following incorrect CoT:\n\n```python\nInitialize current_gcd to 0 (or None)\\n    Initialize current_lcm to 1\\n    For each j from i to len(nums)-1:\\n        current_product *= nums[j]\\n        current_gcd = gcd(current_gcd, nums[j]) if current_gcd is not None else nums[j]\\n        current_lcm = lcm(current_gcd, nums[j]) if current_gcd is not None else nums[j]\\n\n...\nclass Solution:\n    def maxLength(self, nums: List[int]) -> int:\n        max_len = 0\n        n = len(nums)\n        for i in range(n):\n            current_product = 1\n            current_gcd = nums[i]\n            current_lcm = nums[i]\n            for j in range(i, n):\n                current_product *= nums[j]\n                current_gcd = math.gcd(current_gcd, nums[j])\n                # Incorrect: uses current_gcd instead of current_lcm\n                current_lcm = math.lcm(current_gcd, nums[j])\n                if current_product == current_gcd * current_lcm:\n                    current_length = j - i + 1\n                    if current_length > max_len:\n                        max_len = current_length\n        return max_len\n````\n\nThis model incorrectly updates `current_lcm` using `current_gcd`. It fails to verify whether the condition is preserved after each step. It also does not backtrack or revise when the invariant breaks.\n\nSATURN-7B corrects the error with a single key change:\n\n```python\ncurrent_lcm = (current_lcm * nums[j]) // math.gcd(current_lcm, nums[j])\n```\n\nThis update uses the previous LCM, maintaining the correct invariant. The change reflects step-by-step verification and inference from the problem condition. The model traces through the logic and only updates when valid.\n\nIn summary, SATURN shows consistent use of verification, backtracking, and backward chaining across general reasoning tasks. These reasoning strategies, learned from SAT, enable generalization to unfamiliar domains through principled logical behavior. Additional examples illustrating these reasoning behaviors are provided in Appendix K and the supplementary materials submitted with the paper.\n\n## Q2: Have you evaluated SATURN on SAT problems beyond 3‑SAT?\n\nWe sincerely thank the reviewer for this clear and important question. Yes, we have evaluated SATURN-2.6k (Test Set) on SAT problems beyond 3-SAT, including 4-SAT and 5-SAT. We selected 10 categories of problems with 100 instances each, totaling 1,000 problems.\n\n**📊 Selected SAT Problem Difficulty $(n, k, l)$**\n| $n$ | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 6 | 5 |\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n| **$k$** | **7** | **5** | **5** | **6** | **7** | **7** | **8** | **7** | **7** | **8** |\n| **$l$** | **40** | **25** | **20** | **20** | **20** | **40** | **40** | **20** | **40** | **40** |\n\nThe pass@3 results are shown below:\n\n**📊  Full pass@3 results on SATURN-2.6k (Test Set)**\n\n| Model / $(n, k, l)$ | (3,7,40) | (4,7,40) | (4,8,40) | (5,8,40) | (6,7,40) | (3,5,25) | (4,7,20) | (3,7,20) | (3,6,20) | (3,5,20) | Avg. |\n|-|-|-|-|-|-|-|-|-|-|-|-|\n| R1-Distill-1.5B | **1.0** | 3.3 | 4.7 | 12.5 | 28.9 | 3.8 | 19.3 | 9.3 | 9.1 | 9.4 | 10.1 |\n| **SATURN-1.5B** | 0.8 | **9.5** | **11.3** | **31.7** | **62.5** | **15.8** | **50.3** | **21.6** | **18.5** | **19.5** | **24.2** |\n| R1-Distill-7B | 6.5 | 10.4 | 11.8 | 31.3 | 56.2 | 31.2 | 65.6 | 49.9 | 52.8 | 45.6 | 36.1 |\n| **SATURN-7B** | **22.9** | **24.3** | **26.5** | **45.7** | **72.4** | **78.2** | **91.0** | **93.3** | **93.5** | **94.1** | **64.2** |\n\nMore detailed experimental results can be found in Appendix G of the paper.\n\n## Q3: Why does Saturn-7B perform worse on AIME24/25?\n\nThank you for the important question. We appreciate the reviewer for pointing out the performance gap on AIME24/25. We believe this drop is primarily due to the limitations discussed in **Section 5**, especially **Limitation ❶: Knowledge limitations ❸ Plasticity and Forgetting**.\n\nFor instance, SATURN-7B failed on the following AIME 2024 problem:\n\n> *Let \\( ABCDEF \\) be a convex equilateral hexagon in which all pairs of opposite sides are parallel. The triangle whose sides are extensions of segments \\( AB, CD, \\) and \\( EF \\) has side lengths 200, 240, and 300. Find the side length of the hexagon.*\n\nAfter manual checking, SATURN-7B generates a mostly correct reasoning chain, but makes a small mistake at the final step by incorrectly applying the harmonic mean formula: $$s = \\frac{3}{\\frac{1}{200} + \\frac{1}{240} + \\frac{1}{300}} = 240$$ The correct relation is based on geometric decomposition: $$s \\left( \\frac{1}{200} + \\frac{1}{240} + \\frac{1}{300} \\right) = 1 \\quad \\Rightarrow \\quad s = 80$$\n\nThis error shows that the model selects a plausible-looking formula. SAT enhances the reasoning ability. But due to the potential issue of catastrophic forgetting in RL, certain math knowledge may be weakened.  When the forgotten knowledge exceeds the improvement from enhanced reasoning, it appears as a drop in benchmark performance, especially on AIME, which is the hardest among these benchmarks.\n\nHowever, it can be addressed through mixed hybrid curriculum training with SAT and math data. Due to time constraints, we conducted a very simple experiment: We fine-tuned SATURN-1.5B using RL for 50 steps on the GSM8K dataset. The results are as follows:\n\n| Model  | AIME 24 | AIME 25 | Math500 | GPQA-D |\n|-|---:|--:|---:|--:|\n| SATURN-1.5B  |   30.0  |   26.7  |   84.6  |   37.4 |\n| SATURN-1.5B + GSM8K    |   **36.7**  |   **30.0**  |   **85.8**  |   **37.9** |\n\nIn future, we will focus on hybrid curriculum with other types of reasoning tasks.\n\n## Q4: How does response length differ between curriculum learning and mixed training?\n\nThank you for your question. Your question is very insightful and highly professional. We are glad to address the difference between the curriculum approach and the mixed training approach. We retained the logs from the mixed training ablation on Qwen2.5-7B-Instruct-1M. Since external links and images are not allowed, we present the response length at each step as a list:\n```\n[903.2, 1012.1, 1176.8, 1135.0, 1026.6, 842.7, 836.2, 852.7, 846.8, 852.6, 823.7, 777.5, 754.6, 769.4, 875.6, 943.7, 865.6, 803.7, 839.3, 793.5, 869.5, 926.2, 947.8, 961.4, 953.0]\n```\nSince the list is too long, for clarity we report the average of every 10 consecutive numbers. As shown, during the early stage of training, the response length increases slowly. After around 50 steps, it drops sharply and struggles to grow again. As a result, the final responses of the mixed training approach are noticeably shorter compared to the curriculum approach.\n\n## Weakness1: Why does SATURN work?\n\nPlease see the response to **Q1**.\n\nFinally, your feedback is highly valuable to us, and we appreciate your recognition of our contribution.\n\n------\n\n[1] Gandhi, Kanishk, et al. \"Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars.\" arXiv preprint arXiv:2503.01307 (2025).\n\n[2] Hu, Zhiyuan, et al. \"Beyond'Aha!': Toward Systematic Meta-Abilities Alignment in Large Reasoning Models.\" arXiv preprint arXiv:2505.10554 (2025)."}, {"review_id": "7HiJqOqs9V", "reviewer": "Reviewer_np9g", "summary": "This paper introduces SATURN, a novel method for improving the reasoning abilities of large language models (LLMs) by training them on a curriculum of Boolean satisfiability (SAT) problems. The core idea is to leverage the structured, symbolic nature of SAT problems to enhance the underlying reasoning skills of LLMs. The authors propose a reinforcement learning framework where the LLM is trained on a progressively more difficult sequence of SAT problems. The difficulty of these problems is determined by a novel metric that estimates the size of the search space. A key contribution is the demonstration that training on this curriculum of SAT problems improves not only the model's ability to solve SAT problems but also its performance on a range of other reasoning tasks, including mathematical reasoning, code generation, and logical puzzles. The authors show that SATURN-trained models outperform baseline models of similar size and even some much larger models on several benchmarks. The paper also provides an in-depth analysis of the model's behavior, showing that the training process enhances the LLM's ability to perform self-verification and to generate more structured and logical reasoning step", "questions": "1. Could you provide more intuition or empirical validation for the chosen difficulty metric? Have you explored other possible metrics, and if so, how did they compare? A more in-depth justification for the chosen metric would help to clarify why it is particularly well-suited for this task.\n\n2. The paper provides some excellent case studies showing how SATURN enhances the model's ability to perform self-verification. However, it would be helpful to have a more detailed analysis of the specific reasoning mechanisms that are being improved. For example, is the model learning to better understand logical connectives, or is it learning to perform a more systematic search? A more fine-grained analysis of the model's reasoning process would provide valuable insights into how SATURN works and helps.\n\n3. The paper notes that the performance of the model plateaus after a certain point in the curriculum. Have you investigated any strategies for overcoming this plateau? For example, would it be possible to create a hybrid curriculum that integrates SAT problems with other types of reasoning tasks? This could help to further improve the model's general reasoning abilities.", "limitations": "Controllable Difficulty seems to make sense. However, it should be discussed with different kinds of metrics that define the difficulty.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- Clarity: The paper is well-written and easy to follow. The problem statement is clear, the SATURN framework is explained in detail, and the research questions are well-defined. The authors have done an excellent job of presenting their work in a way that is accessible to a broad audience, even those who may not be experts in SAT solvers or reinforcement learning.\n\n- Originality: The paper presents a novel and significant contribution by using SAT problems as a training ground for improving the general reasoning abilities of LLMs. This is a departure from the more common approach of training on vast amounts of text data, and it opens up a new avenue for research into how to best instill abstract reasoning skills in LLMs. \n\n- Quality: The experimental design is sound, and the authors have conducted a thorough set of experiments to validate their claims. The inclusion of extensive ablation studies in the appendix strengthens the paper by showing the impact of different components of the SATURN framework. The authors have also released their code, data, and models, which is a significant contribution to the community and allows for the reproduction and extension of their work.\n\n##  Weaknesses\n\n- Transferability: A key weakness is the limited transferability of the reasoning skills learned from SAT problems to more knowledge-intensive domains. While the paper shows improvements on a range of reasoning tasks, the improvements are most significant on tasks that are structurally similar to SAT problems. This suggests that the model may be learning to solve a particular type of reasoning problem, rather than developing a more general reasoning ability.\n\n- Justification for Difficulty Metric: The paper proposes a novel metric for estimating the difficulty of SAT problems, but the justification for this particular metric is not entirely convincing. While the authors provide some intuition and empirical validation, it is not clear why this metric is superior to other possible metrics. A more thorough discussion of the design choices behind the difficulty metric would strengthen the paper.", "was_revised": true, "final_justification": "I think the authors have addressed more of my initial concerns, but given the concerns of other reviewers, I will keep my score of 4.", "rebuttal": "We are grateful for your detailed review and valuable suggestions. Each point you raised is addressed below.\n\n## Q1: Could you provide more intuition or empirical validation for the chosen difficulty metric?\n\nThank you for your insightful and professional question. In our early exploration, we conducted an ablation study of the SAT difficulty estimation metric on our SATURN‑2.6K test set. The dataset contains 10 categories of problems with 100 instances each, totaling 1,000 problems (Appendix G).\n\n**📊 Selected SAT Problem Difficulty $(n, k, l)$**\n| $n$ | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 6 | 5 |\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n| **$k$** | **7** | **5** | **5** | **6** | **7** | **7** | **8** | **7** | **7** | **8** |\n| **$l$** | **40** | **25** | **20** | **20** | **20** | **40** | **40** | **20** | **40** | **40** |\n\nThe pass@3 results are shown below:\n\n**📊  Full pass@3 results on SATURN-2.6k (Test Set)**\n\n| Model / $(n, k, l)$ | (3,7,40) | (4,7,40) | (4,8,40) | (5,8,40) | (6,7,40) | (3,5,25) | (4,7,20) | (3,7,20) | (3,6,20) | (3,5,20) | Avg. |\n|-|-|-|-|-|-|-|-|-|-|-|-|\n| R1-Distill-1.5B | **1.0** | 3.3 | 4.7 | 12.5 | 28.9 | 3.8 | 19.3 | 9.3 | 9.1 | 9.4 | 10.1 |\n| **SATURN-1.5B** | 0.8 | **9.5** | **11.3** | **31.7** | **62.5** | **15.8** | **50.3** | **21.6** | **18.5** | **19.5** | **24.2** |\n| R1-Distill-7B | 6.5 | 10.4 | 11.8 | 31.3 | 56.2 | 31.2 | 65.6 | 49.9 | 52.8 | 45.6 | 36.1 |\n| **SATURN-7B** | **22.9** | **24.3** | **26.5** | **45.7** | **72.4** | **78.2** | **91.0** | **93.3** | **93.5** | **94.1** | **64.2** |\n\nWe then performed linear regression between each difficulty metric and model pass@3 (averaged across four models, with variance reported). The metrics capture different aspects including sparsity and structural complexity of SAT, as derived in Appendix C. The results are as follows:\n\n**📊 Metric Comparison Table**\n\n| Metric Formula | R1-Qwen-1.5B | Saturn-1.5B | R1-Qwen-7B | Saturn-7B | Avg. | Std. Dev. |\n|:--------------:|:------------:|:-----------:|:----------:|:---------:|:----:|:---------:|\n|$-k - l \\cdot \\log_2(1 - \\frac{1}{2^n})$|0.507|0.537|0.132|0.000|0.294|0.269|\n|$\\alpha \\cdot \\frac{k}{n} + \\beta \\cdot \\log_2(l)$, $\\alpha{=}2$, $\\beta{=}1$|0.428|0.478|0.568|0.508|0.496|0.059|\n|$\\alpha \\cdot \\frac{k}{n} + \\beta \\cdot \\log_2(l)$, $\\alpha{=}1$, $\\beta{=}1$|0.240|0.279|0.719|0.826|0.516|0.300|\n|$\\log_2(k \\cdot l) - \\log_2(2^{n} - 1)$|0.875|0.893|0.451|0.157|0.594|0.356|\n|$\\log_2(k) + 2 \\cdot \\log_2(l) - n + \\frac{k}{n}$|0.707|0.746|0.724|0.501|**0.670**|0.113|\n\nOur metric $\\log_2(k) + 2 \\cdot \\log_2(l) - n + \\frac{k}{n}$ combines both solution sparsity and structural complexity, and achieves the best overall correlation. The ratio between the solution space and the LLM’s search space is the most crucial aspect. **On SATURN‑7B, the R² value is about 0.5 because pass@3 already achieves over 90% on easy problems**, which limits the observable linear correlation in that range. Due to rebuttal length constraints, the corresponding figures are shown in Appendix Figures 9 and 10.\n\nWe will include this ablation study in future revisions to strengthen the paper. Thank you again for your valuable suggestion.\n\n## Q2: How does SATURN work?\n\nWe appreciate the reviewer’s professional question regarding why training on SAT problems helps generalization to other domains such as math and code. We agree that understanding the underlying mechanisms is important. To this end, we offer key supporting evidence.\n\nA recent study, _Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs_ [1], identifies four core habits shared by expert human reasoners and LLMs:  (1) **verification**, (2) **backtracking**, (3) **subgoal setting**, and (4) **backward chaining**. These behaviors are domain-agnostic and fundamental for solving general reasoning tasks. And [2] proposed the same concept of meta-ability. The meta-ability represent general reasoning patterns that can be generalized across SAT, math, and programming tasks. In the following, we present additional case studies to illustrate how SATURN works.\n\n**Case 1**\n\nTo better understand how SATURN promotes these behaviors, we provide a case study comparing SATURN and a baseline model on the same SAT instance:\n\n> ¬A∨¬B∨¬D ∧ ¬B∨¬C∨D ∧ A∨¬B∨¬C ∧ A∨C∨E ∧ B∨C∨D\n\nR1-Distill-1.5B fails on this instance. Its trace is shown below:\n\n```\nWait, in the solution, D=0, so clause 3: A ∨ ¬B ∨ ¬C → 0 ∨ 0 ∨ 1 → True.\n\nYes, that's correct.\n\nClause 4: A ∨ C ∨ E → 0 ∨ 0 ∨ 0 → True.\n\nClause 5: B ∨ C ∨ D → 0 ∨ 0 ∨ 0 → True.\n\nSo, I think that's a valid solution.\n```\n\nThe model skips verification of earlier clauses and fails to backtrack after contradictions. The reasoning is shallow and linear. It does not apply backward chaining from goal constraints.\n\nIn contrast, SATURN-1.5B produces the following trace:\n\n```\nHmm, that's a contradiction. So, my assumption that B=False leads to a problem with clause 1. Therefore, B cannot be false.\n\nSo, B must be true. Let me backtrack.\n\nEarlier, I assumed A=True, and then B=False led to a contradiction. So, B must be true.\n\nLet me restart with A=True and B=True.\n\nThen, let's look at clause 1: ¬A ∨ ¬B ∨ ¬D. Since A and B are true, ¬A and ¬B are false, so for the clause to be true, ¬D must be true. Therefore, D must be false.\n\nSo, D=False.\n````\n\nThis trace shows verification of clause satisfaction, backtracking after an invalid assumption, and backward chaining from clause structure to variable assignments. These capabilities help the model reason accurately across steps.\n\n**Case 2**\n\nWe observe the same behaviors in LiveCodeBench.\n\n> You are given an array of positive integers `nums`.  \n> An array is called product equivalent if the product of all elements equals `gcd(arr) * lcm(arr)`.  \n> Return the length of the longest product equivalent subarray.  \n> A subarray is a contiguous non-empty sequence of elements in the array.\n\nThe R1-Distill-7B gives the following incorrect CoT:\n\n```python\nInitialize current_gcd to 0 (or None)\\n    Initialize current_lcm to 1\\n    For each j from i to len(nums)-1:\\n        current_product *= nums[j]\\n        current_gcd = gcd(current_gcd, nums[j]) if current_gcd is not None else nums[j]\\n        current_lcm = lcm(current_gcd, nums[j]) if current_gcd is not None else nums[j]\\n\n...\nclass Solution:\n    def maxLength(self, nums: List[int]) -> int:\n        max_len = 0\n        n = len(nums)\n        for i in range(n):\n            current_product = 1\n            current_gcd = nums[i]\n            current_lcm = nums[i]\n            for j in range(i, n):\n                current_product *= nums[j]\n                current_gcd = math.gcd(current_gcd, nums[j])\n                # Incorrect: uses current_gcd instead of current_lcm\n                current_lcm = math.lcm(current_gcd, nums[j])\n                if current_product == current_gcd * current_lcm:\n                    current_length = j - i + 1\n                    if current_length > max_len:\n                        max_len = current_length\n        return max_len\n````\n\nThis model incorrectly updates `current_lcm` using `current_gcd`. It fails to verify whether the condition is preserved after each step. It also does not backtrack or revise when the invariant breaks.\n\nSATURN-7B corrects the error with a single key change:\n\n```python\ncurrent_lcm = (current_lcm * nums[j]) // math.gcd(current_lcm, nums[j])\n```\n\nThis update uses the previous LCM, maintaining the correct invariant. The change reflects step-by-step verification and inference from the problem condition. The model traces through the logic and only updates when valid.\n\nIn summary, SATURN shows consistent use of verification, backtracking, and backward chaining across general reasoning tasks. These reasoning strategies, learned from SAT, enable generalization to unfamiliar domains through principled logical behavior. Additional examples illustrating these reasoning behaviors are provided in Appendix K and the supplementary materials submitted with the paper.\n\n## Q3: Have you investigated any strategies for overcoming the plateau? \n\nYour question is very professional and forward-looking. Thank you for raising it.\n\nFollowing the insights from the DeepScaleR [3], we explored extending the RL context length from 8k to 12k and then to 16k tokens to overcome the plateau. The effect was limited, and extremely long responses can trigger OOM under our compute constraints.\n\nOur experiments confirm that SAT problems serve as an effective complement to math and code tasks. The plateau may be addressed through mixed hybrid curriculum training with SAT and math data. Due to time constraints, we conducted a very simple experiment: We fine-tuned SATURN-1.5B using RL for 50 steps on the GSM8K dataset. The results are as follows:\n\n| Model                  | AIME 24 | AIME 25 | Math500 | GPQA-D |\n|--|---:|----:|----:|---:|\n| SATURN-1.5B            |   30.0  |   26.7  |   84.6  |   37.4 |\n| SATURN-1.5B + GSM8K    |   **36.7**  |   **30.0**  |   **85.8**  |   **37.9** |\n\nThe idea of a hybrid curriculum with other reasoning tasks is excellent, and we will focus on it carefully in our future work.\n\n## Weakness 1: Transferability\n\nPlease see the response to **Q2**.\n\n## Weakness 2: Justification for Difficulty Metric\n\nPlease see the response to **Q1**.\n\nFinally, we thank you for your thoughtful review and your recognition of our efforts.\n\n------\n\n[1] Gandhi, Kanishk, et al. \"Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars.\" arXiv preprint arXiv:2503.01307 (2025).\n\n[2] Hu, Zhiyuan, et al. \"Beyond'Aha!': Toward Systematic Meta-Abilities Alignment in Large Reasoning Models.\" arXiv preprint arXiv:2505.10554 (2025).\n\n[3] Luo, Michael, et al. DeepScaleR: Surpassing O1-Preview with a 1.5B Model by Scaling RL. 2025. Notion Blog."}, {"review_id": "78gfZDvGWy", "reviewer": "Reviewer_QZ5H", "summary": "This paper proposes SATURN, a curriculum-based reinforcement learning (RL) framework that uses SAT problems to train and evaluate large language models (LLMs) on reasoning tasks.  A dataset named SATURN-2.6k is introduced to benchmark performance over varying difficulty levels. The authors apply their approach to LLMs like DeepSeek-R1-Distill-Qwen and show improvements on SAT solving tasks and modest improvements on math and programming benchmarks.", "questions": "1. How do you ensure that the SAT tasks used in SATURN actually require multi-step logical reasoning rather than simple token pattern recognition or template-based decoding?\n\n2. Can you provide a comparative study of SATURN vs. supervised fine-tuning on the same SAT dataset to justify the use of reinforcement learning?\n\n3. Is there any evidence that training on richer formal logic problems (e.g., QBF, theorem proving) would provide stronger reasoning benefits than SAT? If so, why was SAT selected despite its limited expressiveness?\n\n4. How does the reasoning learned from SAT generalize to tasks involving semantic understanding or abstraction, which SAT does not cover?\n\n5. Have you tested model behavior on harder SAT instances near the phase transition (e.g., α ≈ 4.2 for 3-SAT) with much more variables where symbolic reasoning becomes nontrivial?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n1. The paper introduces SATURN, a curriculum-based reinforcement learning framework that leverages SAT problems to train and evaluate LLMs on complex reasoning tasks.\n2. The authors provide a benchmark dataset, SATURN-2.6k, which enables evaluation across varying difficulty levels.\n3. The models fine-tuned with SATURN show improvements on SAT tasks and some generalization to math and code domains.\n\n**Weaknesses**\n1. **Overly simple SAT datasets**:\n- The SAT problems used in training (e.g., 3-SAT with clause-to-variable ratios far from the phase transition) are syntactically and semantically simple. \n- Many tasks can likely be solved by pattern matching or shallow heuristics rather than logical reasoning, especially with SAT instances constructed to be trivially satisfiable. \n- Despite the theoretical hardness of SAT, the practical instances used here do not reflect the complexity needed to truly test or build reasoning capabilities.\n\n2. **Whether SAT is suitable for reasoning skills**:\n- The paper claims that solving SAT via RL builds general reasoning skills. However, SAT solving is fundamentally search-based and benefits from symbolic constraint satisfaction strategies — not the kind of causal reasoning or abstraction often required in math or programming.\n\n- The assumption that SAT instances naturally induce verification and self-reflection is speculative and lacks empirical justification or ablation analysis.\n\n3. **Lack of RL Analysis**:\nThe contribution is based on the use of RL, but the role of RL is under-analyzed. There is no comparison to standard supervised fine-tuning on the same tasks, and it remains unclear whether RL offers any unique benefit over direct optimization on pass@k.\n\n4. **Modest improvements** : Improvements on downstream tasks (math, code) are modest and possibly attributable to performance variance introduced by training or domain transfer from additional training data, not necessarily from enhanced reasoning from SAT tasks.", "was_revised": true, "final_justification": "The authors' response addressed my concerns regarding dataset simplicity, the suitability of SAT for reasoning, and the role of RL. They provided additional empirical evidence and clarified theoretical motivations. I now find the claims more substantiated and have raised my score to 4.", "rebuttal": "## Q1: How do you ensure that SAT tasks require multi-step reasoning?\n\nWe demonstrate the LLM’s multi-step logical reasoning in our **Weakness 2** analysis.\n\nDue to the rebuttal length limit, we cannot include the full SAT solving traces here. More reasoning examples are provided in **Appendix K** and in the supplementary materials.\n\n## Q2: How about SATURN vs. SFT?\n\nOur setting is RLVR, where no supervised data with intermediate CoT annotations are available; only a verifier checks whether the LLM’s final answer is correct. RL encourages the model to explore reasoning paths **on its own**, which SFT cannot achieve without costly CoT annotations, which are unavailable in our dataset.\n\nA detailed discussion is provided in **Weakness 3**.\n\n## Q3: Would training on richer formal logic problems (e.g., QBF, theorem proving) would better?\n\nThank you for this insightful question. We answer from two perspectives.\n\n1. There is some work on RL training for theorem-proving tasks [4]. However, the difficulty of these problems is hard to control, which makes curriculum design challenging. This is an advantage of SAT, as we can generate large-scale instances with adjustable complexity.\n\n2. Our work is an initial exploration of how SAT can enhance the reasoning capability of LLMs. QBF is a natural extension of SAT that incorporates quantifiers into propositional logic, and we plan to explore QBF in future work to provide richer logical problems.\n\n## Q4: How does SAT generalize to semantic understanding or abstraction tasks?\n\nThank you for raising this important point. We agree that semantic understanding is an important capability of the LLM. However, the RLVR community (e.g., Deepseek-R1 [5], OpenAI O-series model [6]) mainly focuses on evaluating the reasoning capability of LLMs, with benchmarks in domains such as math and code. Semantic understanding or other tasks are largely out of scope for current RLVR studies, though future work may explore it.\n\n## Q5: Have you tested model behavior on harder SAT instances? \n\nWe sincerely thank the reviewer for this clear and important question. Yes, we have evaluated SATURN-2.6k (Test Set) on SAT problems beyond 3-SAT, including 4-SAT and 5-SAT. We selected 10 categories of problems with 100 instances each, totaling 1,000 problems.\n\n**📊 Selected SAT Problem Difficulty $(n, k, l)$**\n| $n$ | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 6 | 5 |\n|:---:|:----:|:---:|:---:|:---:|:---:|:----:|:--:|:---:|:---:|:---:|\n| **$k$** | **7** | **5** | **5** | **6** | **7** | **7** | **8** | **7** | **7** | **8** |\n| **$l$** | **40** | **25** | **20** | **20** | **20** | **40** | **40** | **20** | **40** | **40** |\n\nThe pass@3 results are shown below:\n\n**📊  Full pass@3 results on SATURN-2.6k (Test Set)**\n\n| Model / $(n, k, l)$            | (3,7,40) | (4,7,40) | (4,8,40) | (5,8,40) | (6,7,40) | (3,5,25) | (4,7,20) | (3,7,20) | (3,6,20) | (3,5,20) | Avg.  |\n|----|------|-----|----|------|-----|------|-----|----|------|-----|-----|\n| R1-Distill-1.5B  | **1.0**  | 3.3      | 4.7      | 12.5     | 28.9     | 3.8      | 19.3     | 9.3      | 9.1      | 9.4      | 10.1  |\n| **SATURN-1.5B**  | 0.8      | **9.5**  | **11.3** | **31.7** | **62.5** | **15.8** | **50.3** | **21.6** | **18.5** | **19.5** | **24.2** |\n| R1-Distill-7B    | 6.5      | 10.4     | 11.8     | 31.3     | 56.2     | 31.2     | 65.6     | 49.9     | 52.8     | 45.6     | 36.1  |\n| **SATURN-7B**    | **22.9** | **24.3** | **26.5** | **45.7** | **72.4** | **78.2** | **91.0** | **93.3** | **93.5** | **94.1** | **64.2** |\n\nMore detailed experimental results can be found in Appendix G of the paper.\n\n## Weakness 1: Overly simple SAT datasets\nThank you for your comment. We address the concern as follows:\n\n1.**Difficulty should match LLM's capability.** As shown in our RQ1 experiments, even SAT instances far from the classical phase transition remain non‑trivial for LLMs. Simply increasing SAT hardness would not better build reasoning capabilities, if the LLM cannot yet solve easier cases.\n\n2.**LLMs are not simply doing pattern matching.** Appendix L, the supplementary materials, and CoT examples provided in **Weakness 2** demonstrate that the models perform strictly step‑by‑step, clause-by-clause reasoning, rather than pattern matching.\n\n3.**Curriculum learning ensures effective training.** Our framework strictly progresses from easy to hard, enabling both models from 1.5B to 7B parameters to gradually build reasoning capabilities.\n\n## Weakness 2: Whether SAT is suitable for reasoning skills\n\nWe appreciate the reviewer’s professional question regarding. We agree that understanding the underlying mechanisms is important. To this end, we offer key supporting evidence.\n\nA recent study, _Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs_ [1], identifies four core habits shared by expert human reasoners and LLMs:  (1) **verification**, (2) **backtracking**, (3) **subgoal setting**, and (4) **backward chaining**. These behaviors are domain-agnostic and fundamental for solving general reasoning tasks. And [2] proposed the same concept of meta-ability. The meta-ability represent general reasoning patterns that can be generalized across SAT, math, and programming tasks. In the following, we present additional case studies to illustrate how SATURN works.\n\n**Case 1**\n\nTo better understand how SATURN promotes these behaviors, we provide a case study comparing SATURN and a baseline model on the same SAT instance:\n\n> ¬A∨¬B∨¬D ∧ ¬B∨¬C∨D ∧ A∨¬B∨¬C ∧ A∨C∨E ∧ B∨C∨D\n\nR1-Distill-1.5B fails on this instance. Its trace is shown below:\n\n```\nWait, in the solution, D=0, so clause 3: A ∨ ¬B ∨ ¬C → 0 ∨ 0 ∨ 1 → True.\n\nYes, that's correct.\n\nClause 4: A ∨ C ∨ E → 0 ∨ 0 ∨ 0 → True.\n\nClause 5: B ∨ C ∨ D → 0 ∨ 0 ∨ 0 → True.\n\nSo, I think that's a valid solution.\n```\n\nThe model skips verification of earlier clauses and fails to backtrack after contradictions. The reasoning is shallow and linear. It does not apply backward chaining from goal constraints.\n\nIn contrast, SATURN-1.5B produces the following trace:\n\n```\nHmm, that's a contradiction. So, my assumption that B=False leads to a problem with clause 1. Therefore, B cannot be false.\n\nSo, B must be true. Let me backtrack.\n\nEarlier, I assumed A=True, and then B=False led to a contradiction. So, B must be true.\n\nLet me restart with A=True and B=True.\n\nThen, let's look at clause 1: ¬A ∨ ¬B ∨ ¬D. Since A and B are true, ¬A and ¬B are false, so for the clause to be true, ¬D must be true. Therefore, D must be false.\n\nSo, D=False.\n````\n\nThis trace shows verification of clause satisfaction, backtracking after an invalid assumption, and backward chaining from clause structure to variable assignments. These capabilities help the model reason accurately across steps. Additional examples illustrating these reasoning behaviors are provided in Appendix K, RQ4, and the supplementary materials submitted with the paper.\n\n## Weakness 3: Lack of RL Analysis\n\nThank you for the valuable comment. We address your concern from two perspectives:\n\n1. **RL improves reasoning and generalization.** Prior work (e.g., SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training) shows that SFT often overfits to training data. In contrast, RL helps the LLM self-explore and check its reasoning steps. This leads to better reasoning and generalization.\n\n2. **RL reduces the need for data.** SFT needs carefully prepared training data with CoT anotation, which is difficult collected. However, reinforcement learning with verifiable rewards (RLVR) makes it practical to improve reasoning without extensive supervised data.\n\n## Weakness 4: Modest improvements\n\nWe clarify that our model is **not trained on additional math or code tasks**. The observed improvements therefore come from enhanced reasoning learned from SAT tasks, rather than domain transfer or data variance. This is a reliable improvement in the model’s own reasoning capability, as also illustrated in Weakness 2 and  in Appendix.\n\nMoreover, these math and code benchmarks are relatively difficult among current benchmarks. The experimental results in paper's **RQ3** show that SATURN's performance improvement exceeds prior methods.\n\n---\n\n[1] Gandhi, Kanishk, et al. \"Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars.\" arXiv preprint arXiv:2503.01307 (2025).\n\n[2] Hu, Zhiyuan, et al. \"Beyond'Aha!': Toward Systematic Meta-Abilities Alignment in Large Reasoning Models.\" arXiv preprint arXiv:2505.10554 (2025).\n\n[3] Chu, Tianzhe, et al. \"SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training.\" arXiv preprint arXiv:2501.17161 (2025).\n\n[4] Dong, Kefan, and Tengyu Ma. \"Stp: Self-play llm theorem provers with iterative conjecturing and proving.\" arXiv preprint arXiv:2502.00212 (2025).\n\n[5] Guo, Daya, et al. \"Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning.\" arXiv preprint arXiv:2501.12948 (2025).\n\n[6] Jaech, Aaron, et al. \"Openai o1 system card.\" arXiv preprint arXiv:2412.16720 (2024)."}, {"review_id": "sx33xwtmcz", "reviewer": "Reviewer_1uh9", "summary": "The authors propose a reinforcement learning loop that trains large language models (LLMs) to solve SAT queries. The reward scheme is simple; the SAT query construction scheme, and especially the task difficulty estimation, is well-motivated and not obvious (in a good way). After training, DeepSeek-R1-Distill-Qwen-1.5B and 7B improve performance on SAT queries and, more surprisingly, on other tasks, like math and programming. The authors suggest that this generalization is due to improved self-verification capabilities of LLMs + SATURN.", "questions": "- Which aspects of the difficulty estimation metric are most crucial?\n- (Optional) Is the author's metric good at estimating difficulty for CDCL SAT solvers?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- The paper is clear, well-written, and well typeset.\n- The task difficulty estimation is well-motivated and works empirically. The task construction method follows nicely from the difficulty estimation metric.\n- The evaluation is solid.\n- SATURN's ability to generalize beyond SAT is interesting and significant.\n\n## Weaknesses\n- Logic-RL is quite similar, although, of course, there is value in SATURN's data generation methodology.\n- While the task difficulty estimation is well-motivated and empirically effective, the paper would benefit from an argument for why this metric is the best choice. Why does something simpler not work just as well? Are all parts of the estimation method necessary? A comparison to alternatives or an ablation study for the metric specifically may be appropriate, given that this is the paper's strongest contribution.\n- The syntax constraint (e.g., \"\\boxed{}\") is never really explained. It was not until the appendix that it became clear that the LLM must output a satisfying model and not just SAT/UNSAT.\n- It is not obvious outside of the appendix that all queries are constructed to be satisfiable. The LLM is acting as a model finder, not as a SAT solver. This makes sense—you can avoid calling a SAT solver on all your generated queries to get the ground truth—but it should be explicit.", "was_revised": true, "final_justification": "The paper should be accepted because (1) the task difficulty estimation is well-motivated and works empirically; (2) the task construction method follows nicely from the difficulty estimation metric; and (3) SATURN's ability to generalize beyond SAT is interesting and significant.\n\nI asked the authors how their metric compares to simpler alternatives and they provided interesting data in the rebuttal that improves the paper. I also asked them to clarify some details, like the \"\\boxed{}\" syntax and the satisfiability of the queries, and they obliged. I am satisfied with their responses.\n\nThe main weakness I see is the originality of the work. For example, Logic-RL is similar. The main differentiating factor is that they can control the difficulty and they perform better than Logic-RL. I accept this argument.", "rebuttal": "Thank you for your valuable comments. We will address your concerns point by point.\n\n## Q1: Which aspects of the difficulty estimation metric are most crucial?\n\nThank you for your insightful and professional question. In our early exploration, we conducted an ablation study of the SAT difficulty estimation metric on our SATURN‑2.6K test set. The dataset contains 10 categories of problems with 100 instances each, totaling 1,000 problems (Appendix G).\n\n**📊 Selected SAT Problem Difficulty $(n, k, l)$**\n| $n$ | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 6 | 5 |\n|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|\n| **$k$** | **7** | **5** | **5** | **6** | **7** | **7** | **8** | **7** | **7** | **8** |\n| **$l$** | **40** | **25** | **20** | **20** | **20** | **40** | **40** | **20** | **40** | **40** |\n\nThe pass@3 results are shown below:\n\n**📊  Full pass@3 results on SATURN-2.6k (Test Set)**\n\n| Model / $(n, k, l)$            | (3,7,40) | (4,7,40) | (4,8,40) | (5,8,40) | (6,7,40) | (3,5,25) | (4,7,20) | (3,7,20) | (3,6,20) | (3,5,20) | Avg.  |\n|------------------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|-------|\n| R1-Distill-1.5B  | **1.0**  | 3.3      | 4.7      | 12.5     | 28.9     | 3.8      | 19.3     | 9.3      | 9.1      | 9.4      | 10.1  |\n| **SATURN-1.5B**  | 0.8      | **9.5**  | **11.3** | **31.7** | **62.5** | **15.8** | **50.3** | **21.6** | **18.5** | **19.5** | **24.2** |\n| R1-Distill-7B    | 6.5      | 10.4     | 11.8     | 31.3     | 56.2     | 31.2     | 65.6     | 49.9     | 52.8     | 45.6     | 36.1  |\n| **SATURN-7B**    | **22.9** | **24.3** | **26.5** | **45.7** | **72.4** | **78.2** | **91.0** | **93.3** | **93.5** | **94.1** | **64.2** |\n\nWe then performed linear regression between each difficulty metric and model pass@3 (averaged across four models, with variance reported). The metrics capture different aspects including sparsity and structural complexity of SAT, as derived in Appendix C. The results are as follows:\n\n**📊 Metric Comparison Table**\n\n| Metric Formula                                                                       | R1-Qwen-1.5B | Saturn-1.5B | R1-Qwen-7B | Saturn-7B | Avg.   | Std. Dev. |\n| :----------------------------------------------------------------------------------: | :----------: | :---------: | :--------: | :-------: | :----: | :--------: |\n| $-k - l \\cdot \\log_2(1 - \\frac{1}{2^n})$                                             |    0.507     |    0.537    |   0.132    |   0.000   | 0.294  |   0.269    |\n| $\\alpha \\cdot \\frac{k}{n} + \\beta \\cdot \\log_2(l)$, $\\alpha{=}2$, $\\beta{=}1$       |    0.428     |    0.478    |   0.568    |   0.508   | 0.496  |   0.059    |\n| $\\alpha \\cdot \\frac{k}{n} + \\beta \\cdot \\log_2(l)$, $\\alpha{=}1$, $\\beta{=}1$       |    0.240     |    0.279    |   0.719    |   0.826   | 0.516  |   0.300    |\n| $\\log_2(k \\cdot l) - \\log_2(2^{n} - 1)$                                             |    0.875     |    0.893    |   0.451    |   0.157   | 0.594  |   0.356    |\n| $\\log_2(k) + 2 \\cdot \\log_2(l) - n + \\frac{k}{n}$                                    |    0.707     |    0.746    |   0.724    |   0.501   | **0.670** |   0.113    |\n\nOur metric $\\log_2(k) + 2 \\cdot \\log_2(l) - n + \\frac{k}{n}$ combines both solution sparsity and structural complexity, and achieves the best overall correlation. The ratio between the solution space and the LLM’s search space is the most crucial aspect. **On SATURN‑7B, the R² value is about 0.5 because pass@3 already achieves over 90% on easy problems**, which limits the observable linear correlation in that range. Due to rebuttal length constraints, the corresponding figures are shown in Appendix Figures 9 and 10.\n\nWe will include this ablation study in future revisions to strengthen the paper. Thank you again for your valuable suggestion.\n\n## Q2: (Optional) Is the author's metric good at estimating difficulty for CDCL SAT solvers?\n\nThis is an excellent question. To fairly compare with LLM results, we tested a CDCL SAT solver on the SATURN-2.6k test set (see Appendix G). The results are as follows:\n\n```python\n  Total instances:   1000\n  Satisfiable:       1000\n  Unsatisfiable:     0\n  Valid SAT Models:  1000\n  Model Accuracy:    100.00%\nTotal time taken: 0.14 seconds\n```\n\nIt show that the CDCL SAT solver significantly outperforms current LLMs, even DeepSeek-R1.\n\nNext, we focused on 3-SAT problems with 100 variables, varying the number of clauses $l$ from 200 to 800 in steps of 5. We recorded the solving time across SAT instances of increasing clause numbers. Due to rebuttal format limits that forbid image uploads, we provide the solving times as a list, where the values represent solver runtimes:\n\n```\n['3.30e-05', '4.01e-05', '7.00e-05', '3.02e-04', '2.46e-03', '1.48e-03', '1.26e-03', '8.68e-04', '5.51e-04', '4.76e-04', '4.25e-04', '3.95e-04', '2.98e-05']\n```\n\nSince the list is too long, for clarity we report the average of every 10 consecutive numbers. As a result, heuristic SAT solvers still rely on traditional phase transition theory as their difficulty metric. The difficulty estimation we present in the paper is specifically designed to simulate human-like and LLM-like search, verification, and backtracking processes in solving SAT. Our metric is based on the solution space and the search space of SAT problems.\n\nWe also discuss this distinction in Section 2.3 of the paper: However, RSB theory is designed for heuristic SAT solvers. For humans or LLMs solving SAT problems through logical steps like trial, verification, and reasoning, such solver-like phase transitions are hardly observable in human-like thinking processes.\n\n## Weakness 1: Logic-RL is quite similar, although, of course, there is value in SATURN's data generation methodology.\n\nThank you for your comment. We agree that SATURN and Logic-RL share the same perspective about LLM reasoning. However, SATURN offers three key advantages: (1) **Controllable difficulty.** SAT-based generation with our estimator allows stable, fine-grained curriculum control. (2) **Better format following.** LLMs trained with SATURN is easier to follow the required output format after RL, and (3) Stronger results. Our main experiments in RQ3 show that, SATURN consistently outperforms Logic-RL on math and programming tasks. Detailed results can be found in Appendix L.\n\n## Weakness 2: Why is this metric the best choice.\n\nPlease see the response to **Q1**.\n\n## Weakness 3: The syntax constraint (e.g., \"\\boxed{}\") is unclear until the appendix.\n\nWe apologize for the confusion. In the revised version, we have moved this key information from the appendix to the main text.\n\n## Weakness 4: It is not obvious outside of the appendix that all queries are constructed to be satisfiable.\n\nThank you for the thoughtful and professional suggestion. We will clarify in the main text that all generated SAT queries are satisfiable by construction. This design avoids calling a SAT solver for ground-truth. We appreciate the reviewer for pointing out the need to make this explicit.\n\nFinally, thank you very much for recognizing our work. Your suggestions are highly valuable to us. We sincerely appreciate your feedback!"}]

Author rebuttal:

Meta-review: The paper proposes SATURN, a SAT-based reinforcement learning framework to enhance LLMs' reasoning capabilities. It addresses limitations of existing RL tasks by enabling scalable SAT task construction, rule-based verification, and precise difficulty control via a curriculum learning pipeline. The authors introduce Saturn-2.6k dataset and apply SATURN to DeepSeek-R1-Distill-Qwen, achieving significant improvements on SAT problems, modest gains on math/programming tasks, and outperforming SOTA RL task construction approaches. The authors argue that SAT training fosters self-verification and structured reasoning, enabling generalization to other domains.  

Reviewers acknowledge the paper’s originality in leveraging SAT problems for LLM reasoning, calling it a novel and significant contribution. The curriculum design and difficulty metric are praised as well-motivated and empirically effective, while the comprehensive evaluation—including ablation studies and transferability tests—adds robustness. The code is open source and helps other researchers build on improving and analyzing LLM reasoning. Reviewers also find the generalization to math/coding tasks interesting and significant, suggesting SATURN may improve broader reasoning skills.  

On the other hand, reviewers raise concerns: (1) The SAT problems may be too simple, relying on "shallow heuristics" rather than deep reasoning; (2) Limited justification for the difficulty metric’s superiority over alternatives; (3) Under-analysis of RL’s role versus supervised fine-tuning. Some reviewers also note the "modest" downstream improvements and speculate about data leakage. The paper’s claims about general reasoning mechanisms lack empirical grounding.  

In general, the paper’s strengths outweigh its weaknesses. The innovative use of SAT problems, robust curriculum design, and demonstrated improvements on multiple benchmarks justify acceptance. While critiques about metric justification and task simplicity are valid, they do not undermine the core contribution. Addressing these in revision by clarifying the difficulty metric’s rationale and adding RL-vs.-supervised comparisons would further strengthen the work. Given its potential to inspire future research, I recommend acceptance.  

During the rebuttal, the authors have provided detailed explanations on reviewers' concerns, regarding dataset simplicity, the suitability of SAT for reasoning, and the role of RL. They have also provided additional empirical validation for the chosen difficulty metric and model behavior on harder SAT instances. The effective rebuttal leads to the increase of average rating.
Decision: Accept (spotlight)