Boosting Deductive Reasoning with Step Signals In RLHF

## Abstract

Abstract Logical reasoning is a crucial task for Large Language Models (LLMs), enabling them to tackle complex problems. Among reasoning tasks, multi-step reasoning poses a particular challenge. Grounded in the theory of formal logic, we have developed an automated method, Multi-step Deduction (MuseD), for deductive reasoning data. MuseD has allowed us to create training and testing datasets for multi-step reasoning. Our generation method enables control over the complexity of the generated instructions, facilitating training and evaluation of models across different difficulty levels. Through RLHF training, our training data has demonstrated significant improvements in logical capabilities for both in-domain of out-of-domain reasoning tasks. Additionally, we have conducted tests to assess the multi-step reasoning abilities of various models.

## 1 Introduction

Recent advancements in large language models (LLMs) (Ouyang et al., ; Bai et al., ) have yielded remarkable outcomes. Among the various capabilities of LLMs, reasoning stands out as one of crucial skills, serving as a foundational ability required for solving complex tasks. Numerous efforts (Sun et al., ) have been made to explore and enhance the reasoning capabilities of LLMs.

In this work, we focus on multi-step deductive reasoning tasks (Sun et al., ) within the realm of reasoning. Many previous works (Han et al., ; Saparov & He, ; Saparov et al., ) have been done of deductive reasoning data generation. However, most works concentrate on supervised fine-tuning (Sanh et al., ) or evaluation. Our work mainly concentrates on generation data for Reinforcement Learning from Human Feedback (RLHF) (Ouyang et al., ). Deductive reasoning tasks concentrate on deriving correct conclusions from given premises through rigorous and effective reasoning. Our attention is directed towards constructing high-quality data to improve the deductive reasoning abilities of models during the alignment phase. The inherent rigor of deductive reasoning tasks dictates that the corresponding prompts should not contain contradictory information or be incapable of leading to the correct answer. This presents our first challenge: how to obtain prompts with correct answers and no contradictions. Based on the proper conditions in prompts, we expect LLMs to employ multi-step reasoning to deduce the correct answer. Assessing the correctness of such a multi-step reasoning process constitutes our second issue, since we need accurate scores of responses to construct training data. Lastly, how to efficiently acquire a substantial amount of data for training is the third problem we need to consider.

To address these issues, we propose a generation scheme for multi-step deductive reasoning data, named Multi-step Deduction (MuseD). MuseD is a scalable approach from prompt creation to final evaluation. To sum up, we base our method MuseD on the syllogistic reasoning of deductive inference (Copi et al., ), employing a backward generation approach to obtain the conditions required for the prompt. This ensures that the conditions in the prompt can lead to the correct conclusion without any contradictory conditions. Moreover, by controlling the number of generated conditions, we regulate the number of inference steps required for the prompt. Based on prompts generated by this method, we score the responses of LLMs step by step. That is, we provide an evaluation method that can assess whether an answer was correctly obtained through multi-step reasoning rather than merely being the correct answer. The data generation process is shown in Fig. 1.

Using MuseD, we synthesize partially ordered data for multi-step deductive reasoning and use this data for Reinforcement Learning from Human Feedback (RLHF) training. We achieve significant performance enhancements on both in-domain and out-of-domain reasoning datasets, validating the effectiveness of our synthesized data. Further experiments demonstrate that step scoring is crucial for improving the model’s performance in RLHF and that positive rewards for correct answers are the primary motivator for model learning.

Additionally, we utilize our method to create a multi-step deductive reasoning evaluation set, also named MuseD(^1^11The code for MuseD evaluation is given in: https://github.com/zhangyipin/mused/tree/main.). Compared to previous evaluation sets, it can provide insights into the model’s performance changes under tasks with different numbers of reasoning steps and offer more granular process evaluations. In summary, our main contributions include: (1) proposing a data synthesis method MuseD based on multi-step deductive reasoning, (2) achieving improvements in deductive reasoning performance on RLHF with this method, and (3) presenting a multi-step deductive reasoning evaluation set that allows for multi-dimensional automatic scoring.

We will briefly introduce the logical concepts involved in our method in Sec. 3 and describe our data generation approach in Sec. 4. In Sec. 5, we will present the experimental results, and in Sec. 6, we will show the performances of some LLMs on our evaluation set.

Figure: Figure 1: The logic training data pipline.
Refer to caption: extracted/5951151/figures/instruction.png

## 2 Related Work

Many recent works concentrate on the reasoning ability of LLM. Sun et al. () give a survey on LLM reasoning, where different kinds of reasoning are considered. Traditionally, reasoning are divided into deductive reasoning (Saparov & He, ), inductive reasoning (Wang et al., ) and abductive reasoning ().

Our work concentrates on deductive reasoning, where valid reasoning process are focused. Many efforts have been done on this tasks to provide high-quality datasets. Tafjord et al. () give a pipline to generate a synthetic data based on rules. Liu et al. () extend human logical testing to LLM dataset. Han et al. () concentrate on natural logical data that are created by experts. Saparov & He () and Saparov et al. () use deduction rules to generate synthetic data and provide datasets. Our work takes inspirations from all these previous works and we combine syllogism rules to develop synthetic data. Specially, we provide not only a dataset, but also a pipline that can give scores on LLM responses. Therefore, our method is suitable for on-policy training such as reward model and PPO training.

Many works improve reasoning ability from algorithmic aspect. Wei et al. () use Chain-of-Thought (CoT) method to improve reasoning ability, while Wang & Zhou () try some decoding method. and Pang et al. () explore improving reasoning ability of LLM through RLHF and iterative DPO respectively. Kumar et al. () attempt to incentive the self-correction ability of LLM. Our method mainly concentrates on RLHF method with our generated dataset. We show that data generation process has large performance effect on RLHF method.

## 3 Preliminary

### 3.1 Proposition

The proposition provides an object that we can judge to be true or false. Logical reasoning focuses on the process of deriving a conclusion from one or more premises. These premises and conclusions often appear in the form of propositions. In natural language, the expression of a proposition may be complex and diverse and it is hard to deal with such flexible data. In this article, we mainly focus on the syllogistic deduction in formal logic, which has relatively simple structure. Therefore, we mainly pay attention to the categorical propositions that judge the relationship between the subject and predicate. In categorical propositions, we judge the relationship between members of one category (the subject of the proposition) and another category (the object of the proposition). Aristotle has established four standard forms of categorical propositions, which we generally write as A, E, I, O (Aristotle, ; Copi et al., ). Below we use S as the subject and P as the predicate, and we give the formats of the four forms of propositions: (1) form A: All S are P; (2) form E: No S are P; (3) Form I: There is one S that is P; (4) form O: There is one S that is not P.

The four propositional structures presented here provide fundamental statements for judging the relationship between two entity categories. Such structures are independent of the actual semantics of the entities, allowing us to focus more easily on the formal relationships. For large-scale model data production, based on such formal structures, we can effectively carry out data production.

### 3.2 Syllogism

Herein, we briefly introduce the categorical syllogism in formal logic (Copi et al., ). The data generation process in our subsequent work is predicated on these effective deductive reasoning rules.

The categorical syllogism is an ancient method of logical argumentation that employs deductive reasoning to study the inferential process of deriving a conclusion from two premises. In the syllogism, we refer to the subject of the conclusion as the minor term, and the predicate as the major term. The two premises of the syllogism each contain the major and minor terms, along with a term that connects the two premises, which we call the middle term. The premise containing the major term is referred to as the major premise, while the premise containing the minor term is called the minor premise. For instance, we may cite a classic example of a syllogism:

> “All men are mortal. Socrates is a man. Therefore, Socrates is mortal.”

Here, the major term is ’mortal’, the minor term is ’Socrates’, and the middle term is ’men’. Hence, ”All men are mortal” is the major premise, and ”Socrates is a man” is the minor premise.

The inference process of a categorical syllogism involves establishing a relationship between the major and minor terms using the middle term. In a valid categorical syllogism, if both the major and minor premises are true, then the conclusion must be true. Formal logic has provided several valid syllogistic forms. In our work, we utilize the 15 valid syllogistic forms(^2^22These valid syllogistic forms can be found in the table of all syllogisms in the wiki website: https://en.wikipedia.org/wiki/Syllogism. We only use results in solid line boxes.) found in modern formal logic (Copi et al., ) to generate our logical data.

## 4 MuseD Method

Given our knowledge of valid syllogistic forms, we can in turn generate two premises from a conclusion by introducing a middle term. Conversely, in the actual deductive process, the relationship between the major and minor terms is established by eliminating the middle term.
Therefore we can generate prompts in different complexity using the premises generation method. Moreover, we can score the responses based on the rules of deductive reasoning, thereby obtaining densely rewarded data. Additionally, our dataset can also serve as an evaluation set, allowing for the assessment of a model’s deductive reasoning capabilities at various levels of complexity.

In the following, we will introduce the entire data generation process in four parts: prompt generation, response generation, response scoring and preference-pair composition.

### 4.1 Prompt Generation

The prompt for logical problems should be rigorous and reasonable. We need to ensure that the prompts we generate can lead to correct conclusions through multi-step reasoning. Therefore, we must guarantee correctness during the prompt generation process. Our approach to constructing prompts is backward-generated, starting from the conclusion to be proven and progressively increasing the complexity of the prompt based on valid formal rules of inference.

Our generation process consists of three steps. The first step is to create a deductive reasoning logic tree where each node on this tree is a proposition. The root node is the conclusion and the leaf nodes are the conditions in prompts. The generated tree only gives a logical structure where all terms are not filled. In the second step, we fill in the content for the missing entities in this tree. Finally, we combine conditions and conclusions to get prompts.

Specifically, we initially employ the syllogistic method of formal logic to generate a multi-step logic tree from the ultimate target conclusion. At the beginning of the tree generation process, we create a root node, which takes the form of one of the four propositions randomly sampled from the previous context. This root node is the final conclusion of this prompt. Throughout the process, we maintain a set of leaf nodes, which initially contains only the root node. As we progress, we iteratively pop a node from the set of leaf nodes, use it as a conclusion, sample a valid categorical syllogism pattern, and transform this conclusion node into two premise propositions by introducing a middle term. These two premise propositions are then added to the set of leaf nodes. Each such sampling process increases the number of leaf nodes by 1 and also necessitates an additional step in the multi-step reasoning from the leaf nodes back to the root node. Thus, by setting the number of times we expand the leaf nodes, we can control the complexity of the generated prompt. When we ultimately have $N+1$ leaf nodes, we turn them to $N+1$ propositions to construct the prompt. From these propositions, the final conclusion can be inferred through $N$ steps of reasoning. Note that during the generation process, we use placeholders rather than specific entities as terms to generate a logical framework.

Based on the aforementioned logical conditions, we can also randomly introduce some interfering conditions. We introduce extra conditions that are related to the existing terms but do not conflict with current propositions, serving as noisy conditions in the reasoning process.

After establishing the logical trees, we then filling placeholders with entities. The most straightforward yet challenging approach is to populate it with noun concepts that conform to the logical conditions. However, this method can easily lead models to take shortcuts (Zhang et al., ; Saparov & He, ) in concluding judgments rather than genuinely engaging in logical reasoning. For instance, given the premises that cats are mammals and mammals are animals, the model can easily arrive at this conclusion that cats are animals with common sense judgment rather than using deductive reasoning. This is what we aim to avoid.

In our work, we focus on the formal structure of logical reasoning itself. Therefore, we have chosen two forms of virtual entities: Greek letter names and virtual nouns. Greek letter names are directly sampled, such as “ALPHA” or “BETA”, to substitute for entities. Virtual nouns consist of 4-14 English letters and are added to our virtual noun database after confirming they are not actual words. We then sample the required quantity from this database to fill the prompts.

Finally, we transform the conditions and conclusion with added entities into a prompt. For the conditions, we concatenate them directly as the given premises. Regarding the conclusion, we have two questioning formats: proof and judgment. For proof questions, we directly ask the model to prove the conclusion. For judgment questions, we reverse the conclusion to its negation with a probability of 0.5 and ask the model to judge whether the given proposition is correct. The templates for proof and judgement are given in Appendix F.

### 4.2 Response Generation

Based on the generated prompts, we can directly access the model to obtain responses. We refer to this method as “natural” response generation. This approach yields the model’s reasoning process expressed in natural language; however, such responses are not easily evaluated. We also incorporate instructions to generate responses in a specified JSON format within the prompt, allowing for structured answers that can be conveniently scored. We term this approach as “formatted” response generation.

The natural method applies solely to the prompt itself, without additional requirements for the format and style of the response. We believe this is more consistent with the model’s output during user interaction and aligns with the distribution of natural language. However, such natural language is relatively challenging to handle during scoring, necessitating additional operations in the evaluation phase to achieve better scoring outcomes.

The formatted generation method, on the other hand, introduces a fixed format for responses, resulting in outputs that are easier to score. Nevertheless, the significant difference between such structured expressions and natural language may impact the learning process during model alignment. The added format is provided in a few-shot manner, with details outlined in Appendix G.

We sample responses to the generated prompts using both methods. In our experiments, we utilize the Llama3 8b model and evaluate the model’s responses under these two approaches.

### 4.3 Response Evaluation

The construction of formal logic problems are generated from the root node to the leaf node with the syllogism approach. Consequently, the procedure of proof or judgement constitutes the process of initiating from the leaf nodse and to arrive at the proposition of the root node.

We assess the responses of LLMs on formal logic reasoning problems in multiple aspects:

- •
Step score: Calculate the how much correct step the response reaches. We mainly calculate this score by counting the eliminated middle terms, details given in Sec. 4.3.1.
- •
Result score: Evaluate whether the response reaches the correct conclusion. A score of 0/1 is assigned. For proof-type questions, if the proposition to be proved emerges in the reasoning process, a score of 1 point is awarded. For judgment-type questions, the score is directly allocated based on the correctness of the judgment.
- •
Intent score: Evaluate whether the generated formatted response is valid JSON string. If valid, a score of 1 is given; otherwise, a score of 0 is assigned.
- •
Wrong step: Count the number of wrong reason steps. The scores equals the number of wrong steps in the propositions within the responses.
- •
Noise step: There might be propositions in the responses that we cannot check its correctness or irrelevant to the reasoning process. We count the numbers of these steps as the noise step score.
- •
Extra step: For correct steps in the responses, we count the number of repeated steps.

Step score, Result score, and Intent score are positive indicators. The higher the value, the better the effect of the LLM. Wrong step score, Noise step score, and Extra step score are negative indicators. The lower the value, the better the effect of the model.

#### 4.3.1 Step Score Calculation

For multi-step reasoning processes, we aim to obtain accurate process scores to evaluate the quality of different answers. It should be noted that the reason process from premises to the final conclusion is not unique. For example, consider conditions: (1) A is B, (2) B is C, and (3) C is D, and we want to conclude that (6) A is D. Using syllogistic reasoning, we can first derive (4) A is C from (1) and (2), and then combine condition (3) to reach (6). Alternatively, we can derive (5) B is D from (2) and (3), and then combine condition (1) to reach the conclusion (6). Both methods are correct and should receive equally high step scores.

Recall that the process of expanding logic tree is to add middle terms to get conditions. Hence reasoning process towards the final conclusion is essentially the process of eliminating these middle terms. In the above example, there are two paths to conduct inference. The first path eliminating B first and then C, while the second path eliminating C first and then B.

Based on observation above, we can enumerate valid middle terms in the logical tree, i.e. term B and C in the above example. We can check the reasoning process of each response and count the number of middle terms that are eliminated. Repeated elimination would not be counted. We calculate the rate of the eliminated middle terms and the number of all middle terms to get the step score.

### 4.4 Preference-pair Composition

We need to construct preference data to train the reward model (RM), based on the scored data above. Different from Outcome Reward Model (ORM) (), we have multiple scoring dimensions to construct pairs. Therefore our RM can learn to provide dense reward signals to help PPO training. On the other hand, we don’t train RM in the Process Reward Model (PRM) pattern ; Wang et al. (), where rewards are assigned to each step, thus we can train RM with other datasets to ensure the general ability of RM.

Since each data point has multiple scoring dimensions, we can construct dataset with different composition methods, ultimately affecting the learning outcome of the model. Here, we experiment with three methods for generating data pairs:

- •
P: uses only positive scores (i.e., the step score and the result score) to construct pairs. For each pair, the chosen response must have a higher step score than the rejected one, while the result score of the chosen cannot be lower than that of the rejected one.
- •
PN: uses both positive and negative scores to construct pairs. We use all the scores above. For wrong, noise and extra scores, we use the opposite number to turn the negative signal into positive. For each pair, each score of the chosen response cannot be lower that that of the rejected one and the chosen should has at least one score that is higher.
- •
R: uses only result score as the pair standard. That is, the chosen response should has result score 1 while the rejected one has result score 0.

One important concern is that whether negative signals should be used. Intuitively, since it should be easier not to do wrong than to do right, negative signals may be easier to learn than positive ones. We compare method P and PN to see whether the choice of signals matters much. We also conduct method R to show the importance of step scores, since R only provides sparse final result signal, as usually used on ORM training.

## 5 Experiments

### 5.1 Evaluation Sets

We use three kinds of evaluation sets to test the performance of models. The in-domain (ID) set MuseD is generated and evaluated by our proposed method. The out-of-domain (OOD) sets are open source logical sets to show whether our model indeed improve its deductive logical ability on prompts out of distribution. We finally choose some general open source datasets to test whether the general abilities are influenced. We set the sampling temperature to be 0.3 for MuseD, 0.001 for OOD datasets.

- •
ID set: MuseD dataset with 2000 prompts, which is introduced in Sec. 6.
- •
OOD sets: For the open source logical verification set, we choose PrOntoQA (Saparov & He, ), ProofWriter (Tafjord et al., ), LogicalDeduction (Pan et al., ), FOLIO (Han et al., ), AR-LSAT (Zhong et al., ).
We use the CoT (Chain of Thought) (Wei et al., ) method, and CoT prompt of each dataset from  (Xu et al., ). The evaluation metric is accuracy, which measures the correctness of multiple-choice questions.
- •
General ability sets
We follow the default implementation setting of LM Eval Harness (Gao et al., ) and set the temperature hyperparameter as 0.
For general ability evaluation, we select the task evaluation in Sec. • ‣ D and follow the default implementation setting of LM Eval Harness with temperature hyperparameter as 0 and report 0-shot accuracy.

### 5.2 Reward Model

The reward models (RM) are trained following the standard process of InstructGPT (Ouyang et al., ). We choose the Llama3 (Dubey et al., ) 8B pretrain model as our base model. If not specified, we keep the hyper-parameters of RMs fixed. More specifically, we set the batchsize to be 384 and the maximum learning rate to be 5e-6.

We train RMs with different preference datasets. We mainly to evaluate the performance of our constructed logic dataset. We choose UltraFeedback (UF) (Cui et al., ) as our base dataset to avoid ability decline in other fields, we use the fine-grained scores to get around UF 27w pairs. For our logic dataset, we compare the performances of the natural and formatted response generation methods. We also test the P, PN and R pair construction methods. All our RMs are listed below. For convenience, we use Na to denote natural responses and Fo to denote formatted responses.

- •
RM-UF: uses only 27w UF data.
- •
RM-Na-P: uses 15k natural P-pair logic data. UF data is used.
- •
RM-Fo-P: uses 15k formatted P-pair logic data. UF data is used.
- •
RM-Mix-P: uses 16k logic data, half from the logic data in RM-Na-P and half from the data in RM-Fo-P. UF data is used.
- •
RM-Na-PN: uses 11k natural PN-pair logic data. UF data is used.
- •
RM-Na-R: uses 8k natural R-pair logic data. UF data is used.
- •
RM-NaO-P: uses only 15k natural P-pair logic data. We turn the batchsize of this RM to be 96 to get more steps.

Notice that we use the same natural responses to construct P, PN and R pairs and different rules result in different size of dataset. For Fo-P data, we downsample them to the same size of Na-P data. We put the validation accuracy and RewardBench (Lambert et al., ) scores of these RMs in the Appendix C. Roughly speaking, each RM gains high validation accuracy on its trained datasets, and the reasoning scores in RewardBench are not directly consistent with our experimental results in Sec. 5, possibly due to the distribution mismatch.

### 5.3 PPO Training

#### 5.3.1 Settings

We train PPO models using above RMs. The base model for PPO training is Llama3 8B Instruct model. The prompts used for training are the same prompts used for the corresponding RM. That is, the prompts used for one RM would be used for the PPO model that uses this RM. The hyperparameters for training PPO are fixed for all experiments. The experience batch size is 160 and the micro batch size is 20. The sampling temperature for training is 1.0. We train for only one epoch. For convenience, we denote each PPO model with its corresponding RM as its subscript. We remove the $\mathrm{RM-}$ in the subscript for briefly. That is, we use $\mathrm{PPO}_{\mathrm{A}}$ to denote the PPO trained with RM-A.

Further, we compare the performance difference if we change the training prompts of PPO. We choose RM-Na-P as our baseline RM and use $\mathrm{PPO}_{\mathrm{Na-P}}$ as our baseline PPO model. We test the impact of using extra in-domain prompts. For $\mathrm{PPO}_{\mathrm{Na-P}}$, we use 6587 prompts trained for RM-Na-P. Then construct more prompts with our pipline MuseD to increase the logical prompts to reach 20000. We combine all these prompts with UF prompts to train one epoch over PPO training, and we get $\mathrm{PPO}_{\mathrm{Na-P-All}}$. We also sample 6587 prompts from the 20000 prompts to train PPO and we get $\mathrm{PPO}_{\mathrm{Na-P-Replace}}$. Finally, we test the effect of curriculum learning during PPO training. That is, we sort the logical prompts used in $\mathrm{PPO}_{\mathrm{Na-P}}$ with their levels. We train them from easy to hard and we get $\mathrm{PPO}_{\mathrm{Na-P-Cur}}$.

#### 5.3.2 Performances

We compare the performances of all PPO models on the three kinds of evaluation sets mentioned in Sec. 5.1. The performances of all models on our MuseD dataset, i.e. the ID dataset, are shown in Table 1. Table 2 gives comparison of models on the OOD datasets. The results for general ability of models are shown in Appendix A. Compared with $\mathrm{PPO}_{\mathrm{UF}}$, the involvement of our data do not seem to cause degradation on other abilities.

Compared to $\mathrm{PPO}_{\mathrm{Na-P}}$, $\mathrm{PPO}_{\mathrm{NaO-P}}$ shows bad performance on all scores, indicating the necessity of using a general dataset. Compared to Llama3 8B Instruct, the UF dataset only don’t increase the step and result scores much, while on out-of-domain datasets, $\mathrm{PPO}_{\mathrm{UF}}$ has a obvious improvement. We check the cases and find that the bad performance on instruction following leads to the low scores of Llama3-8b-Instruct. It can be seen from the results on AR-LSAT, which is a 5-choice dataset. A random strategy would leads to a score around 0.2 while Llama3-8b-Instruct gets a score near 0.

To show the effect of training with our dataset, we compare $\mathrm{PPO}_{\mathrm{UF}}$ and $\mathrm{PPO}_{\mathrm{Na-P}}$. The logical data yields a significant gain in logical effects. Compared to $\mathrm{PPO}_{\mathrm{UF}}$, $\mathrm{PPO}_{\mathrm{Na-P}}$ increases the step and result scores of MuseD both by 12 percentage points, and reduces the average wrong step significantly. The noise step and extra step indicators are basically the same. More results on level-wise comparison are given in Appendix B. On the public evaluation datasets, there is significant growth on ProntoQA, ProofWriter, and LogicalDeduction. Specifically, there are 14-16% improvements on ProntoQA and LogicalDeduction, which have quite similar deductive tasks as MuseD dataset. There is a slightly decrease on AR-LAST, a five-choice task dataset (refer to Appendix E.1). Although both PPO models get a reward similar to a random strategy, $\mathrm{PPO}_{\mathrm{Na-P}}$ sometimes refused to pick any answer when it thinks all options are wrong.

Table: Table 1: Performances of Lamma3 8B models trained with different RMs on MuseD dataset.

Table: Table 2: Performances of Lamma3 8B models trained with different RMs on out-domain logical evaluation sets.

#### 5.3.3 Preference Pair Composition

We compare the performance of models trained with PPO across different preference pair generation methods which are presented in Section  • ‣ 4.4. We compare the performances of $\mathrm{PPO}_{\mathrm{Na-P}}$, $\mathrm{PPO}_{\mathrm{Na-PN}}$ and $\mathrm{PPO}_{\mathrm{Na-R}}$.

Process signals can significantly improve the effect. RM-Na-P uses preference data incorporating process signals while RM-Na-R uses data constructed with result score only. The step score exhibits significant growth on the MuseD evaluation set. On the public datasets, $\mathrm{PPO}_{\mathrm{Na-P}}$ is notably superior to $\mathrm{PPO}_{\mathrm{Na-R}}$. There are about 10-point improvement LogicalDeduction, 7-point imporvement on ProntoQA , and 5-point improvements on both ProofWriter and FOLIO .

Negative signals will cause degradation in effectiveness. Introducing negative signals for the construction of preference data in the reward model will notably diminish the effectiveness of the PPO model. $\mathrm{PPO}_{\mathrm{Na-PN}}$ further incorporates negative indicators on the foundation of $\mathrm{PPO}_{\mathrm{Na-P}}$. There is indeed a reduction in the three dimensions of negative indicators (wrong step count, noise step count, and extra step count) in MuseD. However, it significantly deteriorates in the positive indicator step score. Concurrently, on the public logical verification set, ProntoQA, LogicalDeduction, and FOLIO exhibit a significant decline.

#### 5.3.4 Natural response VS. Formatted response

We also investigate the influence of data format of prompts. We choose Na (natural responses) and Fo (formatted responses). We train three PPO models with distinct data formats: $\mathrm{PPO}_{\mathrm{Na-P}}$ (utilizing Na), $\mathrm{PPO}_{\mathrm{Fo-P}}$ (employing Fo), and $\mathrm{PPO}_{\mathrm{Mix-P}}$ (mixing Na and Fo in a 1:1 ratio).

Natural format performs better. $\mathrm{PPO}_{\mathrm{Na-P}}$ is notably superior to $\mathrm{PPO}_{\mathrm{Fo-P}}$ and $\mathrm{PPO}_{\mathrm{Mix-P}}$. On MuseD dataset, $\mathrm{PPO}_{\mathrm{Na-P}}$ exhibits significant superiority over $\mathrm{PPO}_{\mathrm{Fo-P}}$, boasting a 6-7 point advantage in step score and result score. In comparison to $\mathrm{PPO}_{\mathrm{Mix-P}}$ version, $\mathrm{PPO}_{\mathrm{Na-P}}$ version is generally on an equal footing in positive indicators. However, regarding negative indicators such as incorrect step count, noise step count, and extra step count, $\mathrm{PPO}_{\mathrm{Na-P}}$ version is markedly better than $\mathrm{PPO}_{\mathrm{Mix-P}}$ version. On the public test logic test collection, $\mathrm{PPO}_{\mathrm{Na-P}}$ version surpasses $\mathrm{PPO}_{\mathrm{Fo-P}}$ and $\mathrm{PPO}_{\mathrm{Mix-P}}$ version in the ProntoQA, ProofWriter, LogicalDeduction, and FOLIO datasets. The result shows that natural format, which is more closely to the natural language, is more effective for RLHF training.

#### 5.3.5 Variants of logical prompts in PPO training

We also experiment on the impact of using additional prompts on top of the prompts covered by RM training. We compare the performances among $\mathrm{PPO}_{\mathrm{Na-P}}$, $\mathrm{PPO}_{\mathrm{Na-P-All}}$ and $\mathrm{PPO}_{\mathrm{Na-P-Replace}}$.

Compare $\mathrm{PPO}_{\mathrm{Na-P-All}}$ with $\mathrm{PPO}_{\mathrm{Na-P}}$. It can be observed that by adding in-domain prompts, the effect on the MuseD set is significantly increased, while there is a significant drop on the out-of-domain data set. It seems that RM-Na-P has the ability to get relatively correct scores for these in-domain prompts, which helps PPO model to improve. However, a too high data proportion will cause overfittin on MuseD data and reduce the effect on non-identically distributed datasets.

Compare the two experiments of $\mathrm{PPO}_{\mathrm{Na-P-Replace}}$ and $\mathrm{PPO}_{\mathrm{Na-P}}$. In the MuseD set, $\mathrm{PPO}_{\mathrm{Na-P}}$ exhibits superiority in all indicators to $\mathrm{PPO}_{\mathrm{Na-P-Replace}}$. On the publicly available logic test set, $\mathrm{PPO}_{\mathrm{Na-P-Replace}}$ shows worse performance on ProntoQA and LogicalDeduction but better performance on FOLIO and ProofWriter. On average, it decreased by approximately 1 point. Generally, using prompts trained with the reward model to train PPO yields better effects both on in-distribution prompts and on open-source data outside the distribution. The possible reason is that on the trained prompts, the reward model scores more accurately, thereby better guiding the training process of PPO. As for the better performance on FOLIO and ProofWriter, it might be caused by a bit overfitting on the MuseD deductive format, which hurts the reasoning ability on tasks like FOLIO or ProofWriter a bit, since ProntoQA and LogicalDeduction have more similar formats to MuseD.

#### 5.3.6 curriculum learning

We also conducte an experiment on curriculum learning as $\mathrm{PPO}_{\mathrm{Na-P-cur}}$ to study its impact on the effect. We uniformly incorporate data of varying levels, ranging from low to high, into the prompt of PPO training. Ensure that with PPO steps training, the traversed logical data progresses from simple to complex.

It can be observed that in comparison to shuffling data, employing the mechanism of curriculum learning: on the MuseD set, the overall result is comparable. However, on the open-source test set, the performance drops. On ProntoQA and LogicalDeduction, it declines by 8 to 10 percentage points.

## 6 Evaluations on LLMs

Our constructed data can also be used as an evaluation dataset to test the performance of LLMs on multi-step deductive reasoning. We generate 2000 prompts to compose this evaluation sets, which we called MuseD. MuseD includes questions that multi-step deductive reasoning is needed. The reason steps range from 1 to 10.

We test the effects of some models on MuseD and the results are shown in Table 3. Obviously, GPT-4-o1-Preview shows best performance. Qwen2.5-72B-Instruct also reaches high scores on step and result scores.

Table: Table 3: Performances of Different Models on MuseD.

Using our MuseD evaluation set, we can see the detailed performances of LLMs. Besides the positive and negative scores above, we show the performance of LLMs over different levels and noise counts, as shown in Appendix H.

## 7 Conclusion

In this work, we propose a multi-step deductive data generation pipline, MuseD, including prompt generation, response scoring and pair composition. MuseD can construct prompts with controllable complexity and check the step scores of responses. We validate the effect of our generated logical data on Lamma3 8B instruct model with RLHF method. The result shows that our data can lead to significant improvement on in-domain of out-of-domain deductive reasoning tasks. Further, we show that natural format and positive step signals are important for RLHF. Finally, we use our pipline to generate an evaluation dataset, also named MuseD, to evaluate the performance of current LLMs.

## Appendix A General ability sets Evaluation

Here, we present the evaluation results of various models on general datasets. We mainly compare PPO models using our dataset with $\mathrm{PPO}_{\mathrm{UF}}$. For most datasets, there is little difference in performance among the models. On the gsm8k dataset, there is a significant variation in model performance, with some models showing improvement while others experiencing a slight decline.

Table: Table 4: Performences of PPO Trained Model with different reward model on general ability evaluate sets.

## Appendix B Detail Comparison

We give some detailed comparison between $\mathrm{PPO}_{\mathrm{UF}}$ and $\mathrm{PPO}_{\mathrm{Na-P}}$. We plot the performances of the two models over different levels, ranging from 1 to 10. Here the level is the necessary steps needed to solve the deductive task. The result is shown in Fig. 2. It can be see that on step and result scores, $\mathrm{PPO}_{\mathrm{Na-P}}$ outperforms $\mathrm{PPO}_{\mathrm{UF}}$ on all levels. $\mathrm{PPO}_{\mathrm{Na-P}}$ also has a lower wrong step count, even through we do not use negative signals when constructing preference data. It can also be see that as the level be larger, performances of models become worse.

Figure: (a)
Refer to caption: x1.png

## Appendix C Validation Set Accuracy and RewardBench Scores of RMs

For each training dataset, we split a small set as validation set to test the accuracy of RMs. For logic and UF datasets, we split some prompts so that all RMs haven’t been trained on these prompts. We use UF-2667 to denote the validation set of UF dataset with 2667 pairs. For each logic dataset with A responses and B pair method, we denote its validation set with c pairs as “Logic-A-B-c”. The results are given below.

Table: Table 5: Accuracy of RMs over all validation sets

It can be see that most models has high accuracy on validation sets corresponding to their own training data. RM-UF has low accuracy on our logical data. However, we gain higher accuracy if we add UF dataset to our logical set, as shown by RM-Na-P and RM-NaO-P.

For each dataset, we test these RMs on RewardBench.

Table: Table 6: Accuracy of RMs over all validation sets

We can check the reasoning score of RewardBench on all the RMs with the final performances of PPOs. We find that this reasoning scores can not be a proper standard for RM chosen. This might be caused by the mismatch of both prompts and responses.

## Appendix D Evaluation Sets Details

We list all evaluation sets we used below.

- •
lambada_openai: Tasks designed to predict the endings of text passages, testing language prediction skills.Paperno et al. ()
- •
mmlu: Massive Multitask Language Understanding benchmark for broad domain language evaluation. Several variants are supported.Hendrycks et al. ()
- •
gsm8k: A benchmark of grade school math problems aimed at evaluating reasoning capabilities.Cobbe et al. ()
- •
openbookqa: Open-book question answering tasks that require external knowledge and reasoning.Mihaylov et al. ()
- •
triviaqa: A large-scale dataset for trivia question answering to test general knowledge.Joshi et al. ()
- •
arc_easy: Tasks involving complex reasoning over a diverse set of questions.Clark et al. ()
- •
arc_challenge: Tasks involving complex reasoning over a diverse set of questions.Clark et al. ()
- •
truthfulqa: A QA task aimed at evaluating the truthfulness and factual accuracy of model responses.Lin et al. ()
- •
logicqa: Logical reasoning tasks requiring advanced inference and deduction.Liu et al. (),

## Appendix E Evaluate Set Template

### E.1 AR-LSAT

## Appendix F Templates for proof and judgement prompts

We use below templates to construct our prompts.

The proof template is

The judgement template is

## Appendix G Templates for formatted response generation

To generate response with JSON format, we use few-shot learning to instruct model to generate. The template is given below. The template for proof problem is.

The template for judgement problem is given below. The template for proof problem is quite similar.

## Appendix H Detailed Evaluation Results

Here we give detailed evaluation results form LLMs on our MuseD dataset. We show the step scores, which we think is the most import score, over the deductive steps and the noise conditions.

Table: Table 7: Performances of Different Models on MuseD over prompt levels.

Table: Table 8: Performances of Different Models on MuseD over noise counts.

As the result shows, LLMs become worse as the the level becomes larger. That is, the more complex the prompt is, the lower the step score is. GPT-4-o1-preview still keeps a 0.7 step score for level 10. Similarly, the more noise conditions are involved, the worse performances LLMs have.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 1
questions: * Why did the authors particularly focus on PPO for reasoning? For post-training, SFT and DPO [1] are often much simpler alternatives that often achieve comparable or better results. Did the authors consider these?
* Are there concrete examples in the paper of problems that MuseD is able to generate?
* What are all the rules of inference that MuseD uses?
* How much compute did the experiments in Table 1 use?
soundness: 2
strengths: * The paper starts with a good premise, of generating synthetic reasoning data for training LLMs. Methods to generate high-quality synthetic data at scale are generally becoming more popular in the field, and I predict their importance to keep rising.
* The paper explores post-training, which is less explored in the reasoning space than fine-tuning approaches
* Results with Llama 8B seem to be mostly positive, and the authors compared to running RLHF on Ultrafeedback alone
summary: This paper introduces MuseD, a method for generating synthetic data of multi-step logical deductive reasoning for training LLMs. The authors focus on generating data for post-training (RLHF). MuseD can also serve as an evaluation benchmark, with finer-grained metrics on the quality of each step. Experiments show that RLHF on MuseD improves performance on OOD datasets, like PrOntoQA, ProofWriter, FOLIO, LogicalDeduction (a BigBench task), and AR-LSAT.
weaknesses: * The paper doesn't show a single example of the data the method is able to generate (not even in the appendix). The explanation (Section 4) is a bit hard to follow, with details all only given in text. It would perhaps be more productive to discuss concrete examples, even if the details of the algorithm are discussed at a higher level (these can likely be inferred from seeing a few representative prompts). If I missed this, I'd appreciate if the authors point me to where such examples are.
* From the description, it seems like the problems in MuseD will look rather templated. It's unclear how the models generalize to much messier data like the problems in FOLIO, which are human-written and involve nuance in language and common sense (which the authors explicitly want to avoid; e.g L204 -- to avoid shortcuts).
* The authors should show that PPO is really necessary here, by trying an Supervised Fine-Tuning baseline on the same data. PPO is generally very unstable, and there's no a priori reason why it makes sense to focus on it.
* The many ways to train the reward model seem a bit ad hoc - I'm not sure I get the intuition behind many of the variations (Sec 5.2). Perhaps it would make sense to try something like DPO, with an implicit reward model, and thus less design choices to be made.
* Post-training experiments only done on Llama 8B

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: In addition to the points above, I have a few further questions:

1. How does the system verify that a step is both correct and relevant to the problem, particularly for responses in natural language? In Section 4.2, the authors mention that "natural language is relatively challenging to handle during scoring," but no details are provided on how this challenge is addressed.

2. In the judgment setting, conclusions are either correct or reversals of correct conclusions. However, does the dataset lack conclusions that cannot be determined (i.e., cases where neither the conclusion nor its reversal can be logically derived from the premises)?

3. The website referenced in the footnote is unavailable. Please check its accessibility. Additionally, it would be helpful to list the 15 formats in the appendix for reference.
soundness: 4
strengths: 1. Deductive reasoning, especially syllogistic reasoning, is foundational for tackling more complex tasks. Fine-tuning on the proposed dataset meaningfully improves the model's ability to apply correct syllogistic reasoning.

2. Using a step-based signal for reinforcement learning is a reasonable approach. For tasks where sequential steps are crucial, step-level feedback can help the model learn accurate reasoning pathways more effectively during the RL process.

3. The experiments are thorough, including a detailed ablation study on various output formats (e.g., natural language, JSON) and different scoring compositions (step score, negative score, or result-only score).
summary: This paper explores logical reasoning of LLMs, specifically focusing on syllogism. The authors propose an automated approach for generating questions at various difficulty levels, along with step-by-step responses and a step-based scoring system. They use this score to fine-tune models with PPO, achieving better performance than baselines (untrained models and finetuned on a general dataset) and PPO models with only results reward. This scoring approach also offers a framework to evaluate current LLMs.
weaknesses: 1. While the use of step-level feedback or process-based rewards is intuitive, it is not novel and has been previously introduced by works such as [1] with subsequent advancements in [2, 3]. Automating label generation is crucial for training a reward model; however, since syllogistic reasoning is formal and symbolic, the potential step formats are highly constrained. Consequently, the step-level feedback here may be trivial, as identifying correct and relevant steps is straightforward.
2. The proposed automated labeling method is tailored specifically to the structured nature of syllogistic reasoning, limiting its applicability to other tasks. Additionally, models fine-tuned on this dataset appear sensitive to data shifts; in the OOD (out-of-distribution) experiments, PPO fine-tuning degrades performance on AR-LSAT, which involves a different logical paradigm. Also notice that the authors should add citation and introduction to these OOD datasets.
3. The OOD datasets ProntoQA, ProofWriter, and LogicalDeduction are quite similar to the in-domain syllogistic samples in the MuseD fine-tuning dataset. These datasets largely comprise syllogisms or syllogism combinations, and FOLIO also includes a subset of syllogisms. It would be insightful to test the fine-tuned models on a broader range of reasoning tasks to assess their generalization capabilities.
4. The hangling of those "incorrect steps" feels somewhat crude. Although these noise and irrelevant steps may not contribute to the correct answer, are they always a negative effect on the overall reasoning of the model? Are they necessary attempts at a reasonable reasoning process? Could they represent necessary exploratory attempts? It's worth questioning if a reasoning process that "goes straight to the correct answer" is indeed better --- or more aligned with human preference --- than one that includes reasonable yet unfruitful attempts. The experimental results suggest that penalizing incorrect steps can degrade performance, so a more nuanced discussion of these steps and their role in the reasoning process would add depth.

[1] Let's Verify Step by Step, Lightman et. al., 2023

[2] Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations, Wang et. al., 2024

[3] Let's reward step by step: Step-Level reward model as the Navigators for Reasoning, Ma et. al., 2023

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: (1) Can you provide more PPO results on other baseline LLMs and comparisons with other baselines introduced in the original paper of the evaluation tasks (ProntoQA, ProofWriter, LogicalDeduction, FOLIO, AR-LSAT). I believe that a relatively comprehensive presentation of the current state of AI in formal logical reasoning would help in understanding the value of this work.

(2) Why do you choose the RLHF strategies to train your model. The processes and results of logical reasoning themselves can provide the necessary knowledge for formal logical reasoning, without needing human experience as a supplement. Actually, many fine-tuning models can also perform formal reasoning without pre-training.

(3) What are the characteristics of the MuseD test set? From Table 3, LLMs seem to perform well on this dataset already.
soundness: 2
strengths: This work proposes a simple but effective method to enhance the logical reasoning ability of LLMs. The performance of LLM (Llama3-8B) improves significantly on several logical reasoning tasks.
summary: This work proposes an automatic method, MuseD, to generate multi-step reasoning training/test datasets based on formal logic. After RLHF on the synthetic data, LLM achieves significant improvements in logical capabilities for logical reasoning tasks. Besides, the test dataset of MuseD can be used as a benchmark for LLMs.
weaknesses: The contributions and experiments of this work do not seem solid.

Firstly, the methods and forms of the generated logical reasoning datasets seem overly simple, only reflecting multi-step features, and do not appear to be significantly different from previous works, like ProofWriter. 

Secondly, the PPO-based model are only compared with the original baseline LLM (LLaMA3) and do not include comparisons with other baseline models. In fact, many fine-tuned smaller models have also achieved good performance on formal logical reasoning, such as ProofWriter. 

Thirdly, the performance of the LLaMA model after secondary training seems to be inferior to that of the GPT models, this raises a question: is the data augmentation method provided in this paper equally effective on the GPT models or other LLMs?

Finally, from the results in Table 3, the statement "Among reasoning tasks, multi-step reasoning poses a particular challenge" doesn't seem to be true.

In conclusion, constructing formal logical reasoning datasets does not seem to be an innovative endeavor. Moreover, the formal reasoning capabilities of LLMs do not appear to be the primary challenge.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: - Why do you need to train a reward model for this?  You could use an open-source one and use the gold truth reward function since the dataset is synthetic (as long as it produces text in a parseable format).

- What are the average sizes of the trees? I think I see a few trees at level 7 in the appendix from the supplementary material pdf, but average stats on the dataset would be nice.

- Did you explore performance across question types somewhere? You introduce the A, E, I, O questions from Aristotle, but I think I only saw "All X are Y" type of questions (or maybe they are all mixed together in your results)?
soundness: 3
strengths: 1. Incorporating reward signals from other domains outside of math, I think, is exciting. 
2. Including dense rewards for following specific steps does seem to have a positive impact on the language model after alignment
summary: This paper introduces a new synthetic dataset, MuseD, consisting of multi-step deduction questions that are constructed from a novel tree generation algorithm that can be configured for varying levels of complexity. Because the questions are synthetic and based on syllogisms (and formal logic), the intermediate outputs can be evaluated from language models, which can then be given a score acting as a reward.  The authors use the intermediate scores from language models on the MuseD dataset to train reward models, followed by language models using PPO.  They show that by incorporating their dataset with dense positive rewards, LMs perform better on other deduction/reasoning tasks such as ProntoQA, FOLIO, and AR-LSAT.
weaknesses: 1. As of now, the paper is difficult to read and understand.  The mistakes in the grammar make many of the sentences and paragraphs difficult to understand what model/results/etc. are being discussed. Additionally, this paper would benefit greatly from figures explaining how the trees are constructed and another showing the types of questions with the reward structure broken down. Finally, I think there are so many models reported in Table 1, that using the subscript naming scheme is difficult to follow.  I would separate the ablated models like PPO_Fo-p and PPO_Na-R into their own sections, introduce them there and talk about them there rather than introduce all the models at once.  A figure for these or a table clearly showing how they differ from each other may also ease the burden on the reader.

2. There is no discussion on why models get questions from MuseD wrong.  This is especially important for this paper, I think, because it's a very toy setting.  I don't think "toy" is bad here, but I do find it surprising that o1 only gets 89% of these correct when they are questions like "all As are B. All Bs are C. Are all As C?" - from personal experience, I think it would take a very large set of premises for o1 / GPT-4 to start to fail, so I am curious why it's failing so often already.  I also think that general error analysis is always nice for papers like this (ones targeting behaviors in LLMs) so that researchers know where models fail on your dataset.

In short, the paper severely lacks clarity. I think fixing this, along with some error analysis, would greatly increase my score.

---

Less serious weakness: Section 3 takes up a page, and I think is mostly redundant.  The "middle term" is introduced here, but I think it'd be far more impactful to replace this section with an image and actually show the "middle term"s in an image to drive home the meaning.  I also do not think you should introduce notation like the A, E, I, O questions if they are not referenced again (didn't see it mentioned else where).  This is just another clarity thing.

Meta-review: While the reviewers felt there were some merits in the paper (the premise of using logical reasoning inside LLMs), there were several areas of improvement as listed in the proposal. On reading the paper and reviews, I tend to agree with the reviewers that more work is needed but this paper does have potential after fixing the writing as clearly explained in the reviews.

Decision: Reject