Thank you for your valuable and constructive review. Below, we respond to each of your comments in detail and hope that our responses could properly address your concerns. If you find them satisfactory, we would be grateful if you could consider updating your score (Rating: 2: reject). Otherwise, please feel free to let us know any remaining questions or concerns, and we will be happy to continue the discussion.

Motivation and Core Contributions of Our Work

We sincerely apologize for any lack of clarity in our manuscript that may have caused confusion. To provide a clearer understanding of our work, we would like to begin by outlining the motivation and core contributions of this paper.

1. Motivation: The Scarcity of High-Quality, Multi-Step Logical Reasoning Data for LLM Training

Our research is motivated by a critical challenge: LLMs still exhibit significant weaknesses in complex, multi-step logical reasoning. This limitaion underscore a significant scarcity of high-quality training data that embodies multi-step logical reasoning chains in natural language form.

Prior work on synthesizing logical data suffers from key limitations: 1) Limited Reasoning Complexity, with limited combinations of logical rules.2) Inadequate Real-World Instantiation, lacking contextual coherence and fail to reflect realistic scenarios.

2. Our Main Contribution: The LogicTree Framework for Synthesizing Logical Reasoning Datasets for LLM Training

We introduce LogicTree, a novel framework for synthesizing multi-step logical reasoning datasets for LLM training, offering advantages in terms of complexity and instantiation. The pipeline consists of two main stages. First, we construct symbolic and diverse formal logic trees from scratch. Then, we design a two-stage LLM-based method to instantiate these symbolic logic trees into context-rich natural language narratives with diverse real-world scenarios.

Our experiments show that fine-tuning LLMs on the LogicTree-generated dataset yields significant and consistent improvements across multiple challenging natural language logical reasoning benchmarks.

Weakness 1

...any backward chaining symbolic system is likely to give you the same sort of tree? Why re-invent what is well known and well implemented?

We appreciate the reviewer‘s observation regarding a crucial point that we wish to clarify: the fundamental difference in purpose between LogicTree and backward-chaining symbolic systems. Our work is not an attempt to reinvent backward chaining for proof verification, but rather to design a novel framework for data synthesis to train LLMs. To address your question in detail, we organize our response along the following two aspects:

1. Key Difference in Core Objective: Synthesis, Not Verification

1.1 Backward chaining symbolic system for Verification

Our understanding of these systems [1,2] are used for verification. Given a target conclusion or hypothesis, they employ a backward-chaining mechanism to search a knowledge base for relevant facts and rules. If a valid reasoning path is found, the system outputs a grounded proof tree that supports the target conclusion. For example:

        Conclusion: is(charlie, cold)?  
                        |
Rule 1. IF is(X, young) And is(X, round), THEN is(charlie, cold).   
                /                 \
Fact 1: is(Bob, young)         Fact 2: is(bob, round).

Backward-chaining symbolic systems are not well-suited for generating training data aimed at teaching LLMs logical reasoning.

1. The process of searching for a reasoning path is deterministic and does not allow control over the number of reasoning steps, tree structure, or types of rules used.
2. The resulting proof tree is already instantiated — the validity of intermediate rules relies on specific factual knowledge. As a result, it lacks structural abstraction, making it unsuitable for synthesizing multiple diverse instantiations from the same underlying logic tree.

1.2 LogicTree for Data Synthesis

In contrast, LogicTree is a synthesis framework that starts from an arbitrary fully symbolic logical formula. Guided by controllable specifications—such as the number of reasoning steps, rule types, and tree structure—it employs a backward-chaining strategy to select applicable logical rules from a formal logic system.

        Logic formula: P -> Q 
                | Rule: ((p → q)) ∧ (q → r)) ⊢ (p → r)
             /      \
 Premise1: P->T     Premise2: T->Q

By instantiating abstract logic trees into diverse real-world scenarios, we aim to synthesize data that helps LLMs acquire fundamental logical reasoning skills.

1.3 Key Differences

2. Motivation for Structural Pattern Matching in Logical Formulas

Under the synthesis objective, existing methods[3,4,5] for generating formal logic trees face a key limitation: they require strict structural identity between formulas, which severely limits the diversity of rule combinations.

To overcome this, we introduce Structural Pattern Matching—a more flexible backward deduction method that compares the structural skeletons of Abstract Syntax Trees (ASTs, line 113). For example, consider the abstract rule of Hypothetical Syllogism, HS: ((p→q)∧(q→r)) ⊢ (p→r). A traditional method requiring unification could only apply this to a simple X→Y conclusion and would fail with a more complex formula like (A∨B)→(¬C). Our method enables us to apply the HS rule to decompose (A∨B)→(¬C) into two new sub-goals: (A∨B)→G and G→(¬C).

Weakness 2

Thank you for your valuable comments. We will respond to your questions point by point.

Question 2.1

a. How were the initial problems specified? Were they chosen from some existing logical benchmarks?

We generate the entire logical reasoning tree from scratch based solely on fundamental logical rules, without the need for any initial problems as input. As discussed in more detail in Weakness 1.2 above, our reasoning tree generation starts from an arbitrary, fully symbolic logical expression — it is not derived from any real-world problem.

Question 2.2

b. How many such problems were there, c. What is the size/complexity of the problems.

We generated 5k symbolic logic trees with depths from 2 to 15, and instantiated each into 3 semantically diverse scenarios, yielding 1.5k reasoning problems. After applying an automatic verification process that discarded 8.73% of invalid samples, the final dataset for LLM training contains 1.38k high-quality, multi-step reasoning instances.

Due to space limitations, the table below presents statistical information for logic trees with 5 to 8 reasoning steps.

Questino 2.3

d. How did you assure that you had similar complexity problems to benchmarks from FOL theorem provers? How do you ... the NL statements make sense at a semantic level?

Since LLMs still face significant challenges in multi-step logical reasoning [6] — for example, their performance on 4-step and 5-step problems remains weak in Multi-LogiEval — we focus on synthesizing problems that are currently difficult for LLMs to solve, in order to better support their learning.

We emphasize that our work is not intended as a benchmark for first-order logic provers, nor does it require alignment with their difficulty levels. Rather, our objective is to generate logically valid, diverse, and controllable training samples that are suitable for improving LLM reasoning capabilities.

In our synthesis pipeline, we design a two-stage LLM-based approach to instantiate logic trees into realistic and coherent scenarios. The goal is not to have LLMs memorize fixed natural language statements, but rather to help them learn how fundamental logical reasoning rules are applied across diverse contexts. Extensive evaluations on multiple benchmarks demonstrate the effectiveness of our method.

Weakness 3

If the core contribution is ...

As we stated at the beginning of our reply, our work aims to address the scarcity of high-quality, multi-step logical reasoning data for LLM training. We propose LogicTree, a framework that synthesizes instantiated and structurally complex logical reasoning data. Such data is essential for teaching LLMs to develop robust, generalizable logical reasoning capabilities.

Reference：

[1] Lambada: Backward chaining for automated reasoning in natural language. ACL, 2023.

[2] SymBa: Symbolic Backward Chaining for Structured Natural Language Reasoning. ACL, 2025.

[3] Enhancing reasoning capabilities of llms via principled synthetic logic corpus. NIPS, 2024.

[4] Learning deductive reasoning from synthetic corpus based on formal logic. ICML, 2023.

[5] LogicAsker: Evaluating and improving the logical reasoning ability of large language models. EMNLP, 2024.

[6] Multi-logieval: Towards evaluating multi-step logical reasoning ability of large language models. EMNLP, 2024.

Thank you for your valuable and constructive review. We sincerely appreciate your feedback. Below, we respond to each of your comments in detail and hope that our responses could properly address your concerns. If you find them satisfactory, we would be grateful if you could consider updating your score. Otherwise, please feel free to let us know any remaining questions or concerns, and we will be happy to continue the discussion.

Weakness 1

Weakness 1.1

it lacks a formal analysis of algorithmic complexity (e.g., runtime or space complexity) for logic tree generation or instantiation.

We appreciate your attention to the computational complexity of our data synthesis process, which is indeed crucial for the practical applicability of our method. Below, we provide a detailed analysis of the algorithmic complexity for both logic tree generation and LLM-based instantiation:

• Logic tree generation: As illustrated in Algorithm 1, the process of generating a symbolic reasoning tree has a time complexity of $O(NM)$, where N is the number of reasoning steps and M is the number of available logical rules. Since both N(<20) and M(<200) are relatively small in practice, the computational cost of this step is negligible.
• LLM-based instantiation: The computational cost of calling LLMs is typically measured by the number of output tokens they generate, which serves as a practical indicator of runtime and resource usage. Specifically: 1) The first call to LLM populates the abstract logical symbols with concrete natural language entities. We denote the number of output tokens consumed in this step as $c$. 2) The second call translates the sequence of reasoning steps into natural language. We assume that translating each individual reasoning step requires an average of $T$ output tokens. The computational cost of generating a data instance with reasoning steps $m$ is: $Cost_{inst}=m⋅T+c$ For a more detailed analysis of the complexity of invoking LLMs, please refer to Appendix B.5.

Our framework guarantees correctness by design, thereby eliminating the need for multiple LLM calls. As a result, the generation cost remains acceptable compared to other approaches.

Weakness 1.2

There is no statistical breakdown of the structural complexity of the generated logic trees (e.g., average depth, node count, rule variety),

We sincerely thank you for your insightful comment and apologize for the lack of this information in the previous version. We provide the relevant details below. The table below presents statistical information for logic trees with 5 to 8 reasoning steps, including (1) the average maximum depth of the trees, (2) the average number of nodes per tree, (3) the average number of distinct rules applied, as well as (4) the proportion of first-order logic rules and propositional logic rules used in each tree.

Weakness 1.3

The paper includes Qwen2.5-7B results only in Multi-LogiEval, and omits it from the main result table (Table 1) and other benchmark evaluations, limiting the completeness of cross-model comparison.

Thank you for your valuable comments. We apologize for omitting this part of the evaluation due to space limitations in the main text. We have now added the experimental results of the Qwen2.5-7B model as follows.

As shown in the table, LogicTree demonstrates consistent and comprehensive performance improvements on Qwen2.5-7B, in line with our main experimental results. On average, it achieves a 4.6% increase in accuracy across multiple benchmarks. Notably, it achieves gains of 6.1% on LogicBench and 9.5% on FOLIO, both of which require more advanced logical reasoning capabilities.

Weakness 2

Some table captions do not totally match with the content or the context around.

Thank you for your careful review and valuable comments. We will thoroughly check the formatting and content throughout the paper and make the necessary corrections in the final version.

Weakness 3

The paper devotes substantial space to analyzing the weakest model, but lacks a discussion on why stronger models benefit less...

Thank you for your valuable comments. First, we would like to clarify that the average improvement for LLaMA3.1-70B is relatively modest (2.3%). This is primarily because LLaMA3.1-70B already achieves high scores on several relatively simple benchmarks, leaving limited room for further improvement. It is worth noting that the LLaMA3.1-70B model still achieves substantial improvements on several challenging benchmarks, such as a 12.1% gain on MultiLogic-Eval(Appendix Table 5) and a 5.6% gain on FOLIO.

To further address your concerns, we conducted additional experiments using the well-known DeepSeek series of distilled models.

As shown in the table, LogicTree consistently improves the performance of DeepSeek-R1-Distill-Llama-8B and DeepSeek-R1-Distill-Qwen-7B across multiple benchmarks, with average gains of 6.5% and 4.9%, respectively.

Question 1

The paper emphasizes the effectiveness of the method on smaller models, but then why are 1B or 3B-scale models not evaluated?

Thank you for your valuable comments. We have conducted additional experiments using Qwen2.5-1.5B and Qwen2.5-3B to further evaluate the effectiveness of LogicTree on smaller language models.

As shown in the table, LogicTree effectively enhances the logical reasoning capabilities of smaller models such as Qwen2.5-1.5B and Qwen2.5-3B, achieving consistent and substantial improvements across multiple benchmarks. Specifically, Qwen2.5-1.5B achieves an average accuracy gain of 7.7%, and Qwen2.5-3B improves by 9.3%, demonstrating that our synthesized data remains effective even for smaller-scale models.

Question 2

Given that recent advances in long-chain Chain-of-Thought (CoT) prompting ..., have you conducted any experiments or comparisons related to this line of work?

We appreciate you pointing out this critical issue—it indeed relates to one of our core contributions. In fact, we provide a detailed discussion of this aspect in Appendix A.1. We apologize for not highlighting it more clearly in the main text, which may have caused confusion. To address this, we will add an appropriate reference in Section 5.

For your convenience, we summarize the key differences below:

Many efforts focus on designing more effective prompting strategies to help LLMs complete complex logical reasoning tasks, such as Symbolic Chain-of-Thought (SymbCoT)[1] and Logic-of-Thought[2]. Although prompt-based methods can effectively leverage the potential of large language models(LLMs), their performance remains fundamentally constrained by the models’ inherent reasoning capabilities.

These works aim to elicit the existing reasoning capabilities of LLMs through carefully designed prompts, rather than enhancing their intrinsic reasoning abilities. In contrast, our approach focuses on synthesizing a large volume of high-quality logical reasoning data from a training perspective, which helps to strengthen the inherent reasoning skills of LLMs. Moreover, our method is not in conflict with these prompt-based approaches — rather, they are complementary. We believe that developing a unified framework that bridges training-based and prompt-based methods is a promising direction for future research.

We humbly hope our response has addressed your concerns. If you have any additional concerns or comments that we may have missed in our responses, we would be most grateful for any further feedback from you to help us further enhance our work.

Reference:

[1] Faithful logical reasoning via symbolic chain-of-thought. ACL, 2024.

[2] Logic-of-thought: Injecting logic into contexts for full reasoning in large language models. NAACL,2024

Thank you for your valuable and constructive review. We sincerely appreciate your feedback. Below, we respond to each of your comments in detail and hope that our responses could properly address your concerns. If you find them satisfactory, we would be grateful if you could consider updating your score. Otherwise, please feel free to let us know any remaining questions or concerns, and we will be happy to continue the discussion.

Weakness 1 & Question 1

Lack of details statistics on the generated datasets, such as the number of questions, unique reasoning patterns, complexity levels, and distribution of question types.

Thank you for your valuable comments. We generated 5,000 symbolic logic trees with depths from 2 to 15, and instantiated each into 3 semantically diverse scenarios, yielding 15,000 reasoning problems. After applying an automatic filtering process that discarded 8.73% of noisy or invalid samples, the final dataset for LLM training contains 1.38k high-quality, multi-step reasoning instances.

An analysis of our synthetic data's properties and a comparison with other methods are presented in Appendix C.3. For the reviewer's convenience, we reproduce the key information below.

In addition, the following table presents supplementary statistical information to further characterize our dataset. The table below presents statistical information for logic trees with 5 to 8 reasoning steps, including (1) the average maximum depth of the trees, (2) the average number of nodes per tree, (3) the average number of distinct rules applied, as well as (4) the proportion of first-order logic rules and propositional logic rules used in each tree.

Weakness 2 & Question 2

How does the LLM-based instantiation process handle the hallucination issues of LLMs to ensure the correctness of the generated statements?

Thank you for this insightful question. Ensuring the correctness of the generated statements is a critical component of our methodology. We address this concern from two key perspectives: (1) our proactive methodological design and (2) a systematic error verification process.

• Two-stage LLM-based instantiation: Due to the inherent limitations of LLMs in handling complex logical reasoning, directly prompting them to generate realistic logical reasoning problems from symbolic logic trees may introduce errors and hallucinations. Therefore, to address this challenge, we designed a two-stage prompting strategy to reduce the task's difficulty for the LLM. The first stage prompts the model to assign factually and logically coherent entities to the symbolic variables in the leaf nodes. Subsequently, the second stage instructs the LLM to translate the symbolic reasoning process into natural language on a step-by-step basis. This decomposition ensures that when generating the natural language statements, the LLM only needs to focus on the translation of individual logical expressions, rather than grappling with the complex dependencies of the entire logic tree. This targeted approach effectively minimizes hallucinations and improves the fidelity of the generated natural language statements.
• Error verification process：Furthermore, to minimize errors in the instantiated data, we implemented a systematic verification process. For each generated instance, we employed an LLM-based verifier to check for logical fallacies and implausible natural language statements by comparing them against their corresponding logical expressions. This process successfully filtered out 8.73% of erroneous data, thereby significantly enhancing the overall quality of the dataset.

To further address the reviewer's concern, we manually evaluated 500 randomly selected samples and found an error rate of only 4.6% (23/500). These minor errors were primarily caused by the model using incorrect entities or misunderstanding certain logical relations within a single reasoning step.

Moreover, we would like to emphasize that the purpose of our synthetic data is not to teach the LLM to memorize specific instantiations of natural language statements, but rather to help it learn to apply underlying logical rules across diverse instantiation scenarios. Given this objective, we contend that this small proportion of noise is acceptable.

Weakness 3 & Question 3

Can you consider using more advanced large reasoning models as DeepSeek-R1-distill-8B, to further validate the effectiveness of the LogicTree framework in improving the reasoning abilities of LLMs?

We appreciate your suggestion to supplement our work with experiments involving more advanced reasoning models, as this would provide important evidence to further validate the effectiveness of our dataset. We further include experiments using advanced reasoning models such as DeepSeek-R1-Distill-Llama-8B and DeepSeek-R1-Distill-Qwen-7B to strengthen our evaluation.

As shown in the table, LogicTree consistently improves the performance of DeepSeek-R1-Distill-Llama-8B and DeepSeek-R1-Distill-Qwen-7B across multiple benchmarks, with average gains of 6.5% and 4.9%, respectively. Notably, on logic-intensive benchmarks such as the ML series, the improvements reach up to 13.3% and 10.9%. These results further confirm the effectiveness of LogicTree in enhancing the logical reasoning capabilities of LLMs.

We humbly hope our response has addressed your concerns. If you have any additional concerns or comments that we may have missed in our responses, we would be most grateful for any further feedback from you to help us further enhance our work.

We thank the reviewer for the insightful and valuable comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score (Rating: 4: Borderline accept). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Weakness 1

LLM-based verification: ...This may introduces a potential failure mode where systematic instantiation errors might go undetected.

Thank you for your valuable comment. We acknowledge that using LLMs for verification inevitably introduces some detection errors. However, our framework mitigates this by simplifying the verification task. Instead of tasking the LLM with the complex evaluation of global logical consistency, we decompose the problem into a series of localized verification steps. In each step, the LLM simply verifies the translation between a logical expression and its natural language counterpart, a task at which state-of-the-art models excel [1,2]. Once each step is correctly translated, the symbolic nature of the LogicTree inherently ensures the overall logical consistency.

To further address the reviewer's concern, we manually evaluated 500 randomly selected samples and found an error rate of only 4.6% (23/500). These minor errors were primarily caused by the model using incorrect entities or misunderstanding certain logical relations within a single reasoning step.

Moreover, we would like to emphasize that the purpose of our synthetic data is not to teach the LLM to memorize specific instantiations of natural language statements, but rather to help it learn to apply underlying logical rules across diverse instantiation scenarios. Given this objective, we contend that this small proportion of noise is acceptable.

Weakness 2

Depth in real-world evaluation: ...More interpretive or failure-case analyses would strengthen the argument that such improvements stem from generalization rather than mere memorization.

We sincerely appreciate your insightful observation that more in-depth qualitative analysis is necessary to substantiate our quantitative findings. We will include more examples of real test cases in the appendix of the final version. Here, we present a representative examples, obtained by comparing the performance of Llama-3.1-8B-Vanilla and our LogicTree-trained model on the MultiLogic-Eval benchmark.

Case 1

Premise 1 : If a biological sample is labeled "High-Risk" (P), then the handler must wear a Level-A protective suit (Q). (P → Q )

Premise 2 : A review of today's lab footage shows that a researcher, Dr. Li, was not wearing a Level-A protective suit while handling sample S-007.(¬Q)

Conclusion to Evaluate: an it be determined that sample S-007 was labeled "High-Risk"? (¬P)

Vanilla Model's Response: No

LogicTree-trained Model's Response: Yes

The LogicTree-trained model correctly identifies and applies Modus Tollens (a core idea underlying the well-known method of proof by contradiction). It adheres closely to the given logical structure, avoiding distractions from irrelevant speculations. This indicates that the training process has effectively internalized fundamental deductive principles, allowing the model to reason reliably from premises rather than relying on superficial pattern matching.earning this rule is instrumental in enabling the model to apply proof by contradiction—an essential technique in mathematical reasoning.

Question 1

What are the practical, computational costs of large-scale synthetic data generation and verification using LLMs

We appreciate the reviewer's insightful comment regarding the importance of computational cost associated with synthetic data generation. Indeed, a detailed analysis of the generation cost is provided in Appendix.B.5. For the reviewer's convenience, we summarize the key findings below. To clarify our computational cost, we analyzed the number of LLM output tokens consumed when generating each data instance.

• Instantiation Cost: 1) The first call to LLM populates the abstract logical symbols with concrete natural language entities. We denote the number of output tokens consumed in this step as $c$. 2) The second call translates the sequence of reasoning steps into natural language. We assume that translating each individual reasoning step requires an average of $T$ output tokens. The computational cost of generating a data instance with reasoning steps $m$ is: $Cost_{inst}=m⋅T+c$
• Verification Cost: We assume that the complexity of verifying a single step is comparable to that of translating it during instantiation. Consequently, the computational cost for verifying a data instance with m reasoning steps is: $Cost_{ver}=m⋅T$

As shown in the table, the ratio of synthesized tokens to consumed tokens for our method is $\frac{mT}{2mT+c}$ (close to 1/2,in our data $T = 79_{\pm14}$, $c = 114_{\pm44}$),which is significantly lower than the cost of other methods. Our framework's guarantee of correctness eliminates the need for multiple LLM calls. Consequently, its generation cost is entirely acceptable in comparison with other approaches.

Question 2

How sensitive are the results to the number of scenario instantiations per logic tree? Is there an upper bound after which gains saturate or reverse?

We sincerely thank the reviewer for the insightful comment. We would like to clarify that an initial analysis on this topic was provided in our ablation study in Section 4.4 of the manuscript.

In that section, we instantiated each logical tree into a varying number of reasoning scenarios (from 1 to 3), with our main results using three scenarios. As presented in Table 2, we observed that increasing the number of scenarios led to a consistent performance improvement across most benchmarks (e.g., from 51.6% to 55.3%). This finding supports our conclusion that greater diversity in reasoning scenarios is beneficial for the model to learn genuinely generalizable logical reasoning skills.

We apologize for the omission and agree that exploring the upper bounds of this effect is valuable. To address this, we have conducted additional experiments for 4 and 5 instantiated scenarios. The complete set of results, including these new data points, is summarized below:

As the results in the table indicate, the performance of Llama-3.1-8B peaks when using 3 or 4 instantiations. However, upon further increasing the number to 5, we observe a slight decline in performance. Therefore, taking into account both the computational overhead and the performance curve, using 3 instantiations offers the best cost-benefit trade-off and was chosen for our main experiments.

We humbly hope our response has addressed your concerns. If you have any additional concerns or comments that we may have missed in our responses, we would be most grateful for any further feedback from you to help us further enhance our work.

Reference:

[1] Faithful Logical Reasoning via Symbolic Chain-of-Thought. ACL, 2024

[2] Divide and Translate: Compositional First-Order Logic Translation and Verification for Complex Logical Reasoning. ICLR, 2025