Testing the General Deductive Reasoning Capacity of Large Language Models Using OOD Examples
Authors: Abulhair Saparov
Richard Yuanzhe Pang
Vishakh Padmakumar
Nitish Joshi
Mehran Kazemi
Najoung Kim
He He
Venue: NeurIPS 2023 poster (2023)
Keywords: large language models
reasoning
out-of-distribution generalization
chain-of-thought
in-context learning

Abstract: Given the intractably large size of the space of proofs, any model that is capable of general deductive reasoning must generalize to proofs of greater complexity. Recent studies have shown that large language models (LLMs) possess some abstract deductive reasoning ability given chain-of-thought prompts. However, they have primarily been tested on proofs using modus ponens or of a specific size, and from the same distribution as the in-context examples. To measure the general deductive reasoning ability of LLMs, we test on a broad set of deduction rules and measure their ability to generalize to more complex proofs from simpler demonstrations from multiple angles: depth-, width-, and compositional generalization. To facilitate systematic exploration, we construct a new synthetic and programmable reasoning dataset that enables control over deduction rules and proof complexity. Our experiments on four LLMs of various sizes and training objectives show that they are able to generalize to compositional proofs. However, they have difficulty generalizing to longer proofs, and they require explicit demonstrations to produce hypothetical subproofs, specifically in proof by cases and proof by contradiction.

Testing the General Deductive Reasoning Capacity of Large Language Models Using OOD Examples
Abulhair Saparov
Richard Yuanzhe Pangl
Vishakh Padmakumar
Nitish Joshi
Seyed Mehran Kazemi
Najoung A,,
He He
New York University, Google, s Boston University as175820nyu. edu
Abstract
Given the intractably large size of the space proofs, any model that is capable of general deductive reasoning must generalize to proof' of greater complexity. Re- cent studies have shown that large language models (LLMs) possess some abstract deductive reasoning ability given chain-of-thoughh prompts. However, they have primarily been tested on proofs using modus ponens of specific size, and from the same distribution as the in-context examples. To measure the general deductive reasoning ability of LLMs, we test on a broad set of deduction rules and measure their ability generalize to more complex proof' from simpler demonstrations from multiple angles: depth-, width-, and compositional generalization. To fa- cilitate systematic exploration, reasoning dataset that enables control over deduction rules and proof complexity. Our experiments on four LLMs of various sizes and training objectives show that they are able to generalize to compositional proofs. However, they have difficulty generalizing to longer proofs, and they require explicit demonstrations produce hypothetical subproofs, specifically proof by cases and proof by contradiction.
construct
synthetic and programmable
Introduction
In many tasks that require deductive reasoning, such as thcorem proving or medical diagnosis, the complexity of proofs can grow without bound via the use of multiple deduction rules and the composition of subproofs. Given the large space proofs, it is infeasible to find data to cover proofs of all sizes. Therefore, general reasoning model must extrapolate to complex proofs from simpler ones. Recent work has shown that LLMs, combined with in-context learning (ICL) and chain-off of-thought (CoT) prompting, Chang, 2022, Han et al., 2022, Wei et al., 2022b, Kojima et al., 2022, Lewkowycz et al., 2022, Nye al., 2021, Gontier al., 2020]. However, much of the prior work focused deduction rules such as modus ponens [Zhang et al., 2022a, Saparov and He, 2023, Tafjord et al., 2021]. In addition, the evaluation is in-demonstration, where the test example comes from the same distribution as the in-context demonstrations, In this work, we evaluate whether LLMs are capable of general deductive reasoning by measuring how well they generalize to proof's that more complex
capable of deductive reasoning to an extent [Huang and
limited set of
"Equal contribution.
GPT and PaLM experiments in this paper were conducted independently. Authors affiliated with NYU were responsible for the GPT experiments, and authors affiliated with Google were responsible for the PaLM experiments.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Train
Test unseen deduction rules:
"Alex a dog. All dogs mammals. Alex is mammal."
"Alex is not a mamuall. All dogs mammals. Suppose Alex is dog. Alex is mammal. This contrudicts with Alex is not mammal. Alex is not dog."
Test deeper proofs:
a dog- dags mammals. Alex is mammal."
"Alex is a dog. All dogs are mammals. Alex is a mammal. All mammals vertebrates. Alex vertebrate."
Train on:
Test on wider proofs:
"Alex a dog. Alex is soft. Alex is dog and soft."
"Alex is a dog. Alex is soft. Alex is kind. Alex is dog and soft and kind."
Train
"Alex is dog- All dags mammals. Alex is mammal." "Fhe a cat. Fae is soft. Fac soft and
Test compositional proofs:
"Alex is dog. All dogs are mammals. Alex a mammal. Alex not mean. Alex mammal and mean."
An overview of the kinds of OOD generalization that test in experiments. Each training example a sample demonstration provided the LLM in the few-shot prompt, whereas each test example a sample proof that the model is expected to output.
FIGURE 1:
than their demonstrations."
We characterize the complexity of proofs from three angles: the deduction rules involved, the depth of the proof (i.e. length of a sequential chain of proof steps), and the width of the proof (i.e. the number premises of each proof step). Each of the three dimensions contributes to the overall size of the proof. To measure the general deductive reasoning ability of LLMs. we extend prior studies in two key ways. First, we determine whether LLMs have learned complete of deduction rules, beyond modus ponens. Second, we evaluate whether they can reason over longer proofs than those given as in-context examples (depth- and width- generalization); and whether they are able to use multiple different deduction rules in single proof (compositional generalization) Figure 1 shows an overview our study.
Our findings suggest that in-context learning is best applied to reasoning tasks by including examples that diverse of deduction rules, and keeping the examples simple. The in-context examples should especially contain examples of deduction rules that are less familiar to the model (i.e. proof by cases and proof by contradiction), and distractors should be provided for such examples as the model is more prone to overfitting.
We test four different LLMs of different scales and training objectives: GPT-3.5 175B [Ouyang et al., 2022], PaLM 540B (Chowdhery et al., 2022], LLaMA 65B ['Tuurron et al., 2023], and FLAN-T5 11B [Chung et al., 2022], and we find:
CoT is able elicit cit-of-ddmonstraation (OOD) reasoning in LLMs generalizing composi- tional proofs. This is somewhat surprising given the amount of previous work that claim that LLMS are not able to generalize compositionally [Hosseini al., 2022, An et al., 2023]. See Section 4.2.2 and Figure 6.
ICL. generalizes differently compared to supervised learning (i.e. gradient descent on in-context examples). We find numerous examples where it is strictly worse provide in-context examples from the same distribution as the test example. For instance, in some cases, we observe better generalization to compositional proofs when the in-context examples each contain individual deduction rules. See Sections 4.2.2 and 4.3, and Figures 6 and 8.
3. However, the LLMs cannot generalize to some deduction rules without explicit demonstrations, specifically, proof by cases and proof by contradiction, suggesting that pretraining is not sufficient teach the model to generate hypothetical subproofs. See Section 4.2.1 and Figure 4.
4. Model size does not strongly correlate with performance. Smaller (but not the smallest) models with instruction tuning and longer pretraining perform comparably to larger models.
All analysis code, data, data generation scripts, and model outputs are publicly available at github. www./oom/paa.ce httpa/ppproo//poooogaaaa

---

Automated evaluation proofs
Contains proofs with multiple deduction rules
Tests proof deplh generalization
Tests proof widlh generalization
Tests compositional generalization
Data generation code available
Dataset
CLUTAR
Sinha [2019]
x
LA
human- annotated
Liu et [2020]
x
ProofMriter
Tafjord et al. [2021]
FOLI0
human- annotated
x
Han et al. [2022]
PRONTOQA
Separov and He [2023]
X
PRÓNTOQA-OOD (this dataset)
TABLE 1: Comparison existing datasets to evaluate reasoning ability. Datasets marked with ~ contain examples of varying width, depth, and compositionality, hut these are not programmable (i.c. we cannot generate new examples controlling for these variables), and splitting the existing examples would produce highly imbalanced splits.
2 Related work
OOD generalization of LLMs. Previous work has measured the generalization ability of LLMs on tasks such bit parity and Boolean variable assignment [Anil et al., 2022], semantic parsing (Hosseini al., 2022, Qiu et al., 2022], deductive reasoning [Zhang et al., 2022a, Sanyal et al., 2022, Kazemi et al., 2023], and arithmetic reasoning [Kudo et al., 2023], where the length/complexit of the test example is greater than that the in-context examples. On the bit parity and variable assignment tasks, LLMs are able generalize to longer inputs with scratchpad prompting [Nye et al., 2021], but this generalization imperfect, and accuracy still degrades with increasing input length. Generally, larger models tend to be better at generalization than smaller ones. The studies on reasoning were limited to reasoning using modus ponens. Wu et al. [2021] tests the OOD generalization of transformers and graph neural networks symbolic mathematical reasoning. Our study more systematically examines OOD generalization of L.MSs to larger proofs as well as to other deduction rules.
Evaluating reasoning abilities of LLMs. A number of recent studies measured the reasoning ability of LLMs [Huang and Chang, 2022, Han et al., 2022]. Table 1 provides comparison of our proposed dataset to datasets from these studies. Many of these datasets are not amenable to automated evaluation of proofs, relying instead on measuring label accuracy. The datasets also do proof width generalization and compositional generalization. Some datasets focus on a limited set of deduction rules, namely modus ponens. Our work is closest PRONTOQA [Saparov and He, 2023] but extends it to complete set of deduction rules and to compositional proofs.
for
Understanding in-context learning. Recent work has shed some light on ICL, and the mechanism by which the model learns from in-context examples. Akyürek et al. [2023], Dai et al. [2023]. von learn in-context by performing gradient descent on in-context examples internally. Xie et al. [2022], Wang et al. [2023] show that LLMs exhibit behavior similar to that of topic models where their output dependent on a latent topic, and the in-context examples help to specify the topic. Ye et al. [2022] demonstrated that ICL is more effective when the in-context examples are both diverse and relevant to the test example. An al. [2023) and Levy et al. [2022] explored the effect of in-context demonstrations on compositional generalization, showing that it benefits from diverse and individually simple demonstrations. Our results contribute to this growing literature by showing that the generalization behavior in ICL is different from that of supervised learning, and so algorithms such as gradient descent are not the only mechanisms underlying ICL.
Oswald al. [2022] showed that transformers
3 Approach
A programmable dataset. Our main evaluation approach is to prompt the LLM with simpler proofs and test on proofs with greater depth and width, or with those using additional deduction rules. Therefore, require programmable approach to data generation, where the deduction rules
3

---

Deduction rule
Formal definition
Natural language example
Implication elimination
Ma) Ve([()) g(x))
"Alex is a cat. All cats are carnivores. Alex is a carnivore."
(i.e. modus ponens)
g(a)
Conjunction introduction
A B
"Alex is cat. Alex is orange. Alex is cat and orange."
A A
Conjunction
A
"Alex is a cat and orange. Alex is orange."
climination
A
Disjunction
A
"Alex is cat. Alex is cat orange."
introduction
AV
Disjunction climination (i.e. proof by cases)
AVB
AFC BHC
"Alex is cat dog. Suppose Alex is then Alex is warm-blooded. Suppose Alex a dog then Alex is warm-blooded. Alex warm-blooded."
C
"Alex cold-blooded, Alex a mammal, Alex not cold-blooded. Suppose Alex is mammal. Alex not cold-blooded. This contradicts with Alex is cold- blooded. Alex is not mammal."
A+ B -B
Proof by contradiction
-A
TABLE An overview of the deduction rules in PRONTOQA-OOD. The notation denotes entailment: that provable from A.
"Alex dog. All dogs are mammals. Alex is mammal. Alex is blue. All mean things are not blue. Suppose Alex is mean. Alex is not blue. This contradicts with Alex is blue. Therefore, Alex is not mean. Alex is mammal and not mean."
mean(alex)
(r(mean(>) bblue())
dog(alex)
Va -> mammal(2) (x))
blue(alex)
blue(alex)
manmal (alex) mammal (alex) A mean (alex)
mean alex)
FIGURE 2: An example of compositional proof containing modus ponens, proof by contradiction, and conjunction introduction, shown both natural language a formal tree representation.
used, as well as the depth and width of each proof, are controllable parameters. To this end, we propose PRONTOQA-OOD, generative process for synthetic reasoning questions. Each example in PRONTOQA-OOD contains a handful premises, query (the target fact to be proved/disproved), and gold CoT containing the proof of the query. See Figure 10 for an example from this dataset. Specifically, we extend the PRONTOQA dataset [Saparov and He, 2023] that contains proofs gen- erated from synthetic world models using modus ponens. (1) To evaluate reasoning using different deduction rules, we generate proofs with deduction rules for all connectives in propositional logic: conjunction disjunction V, implication ->, and negation -. (2) To study width/depth generalization, the proof depth and width are controllable parameters in proof generation, where they control the number of generated deduction rules, and the number of premises in each deduction rule, respectively. (3) To study compositional generalization, we generate compositional proofs using a simple recursive procedure, where each proof contains multiple subproofs with distinct deduction rules.
Generating proof's with a complete of deduction rules. We follow the deduction rules of natural deduction [Gentzen, 1935, Pfenning, 2004], a well-studied proof calculus with desirable completeness properties. Examples of each deduction rule are shown in Table 2. For each type of deduction rule, we randomly generate proof that applies that rule (see details in section A.4. An example of a compositional proof is shown in Figure 2. To prevent LLMs from exploiting knowledge from pretraining to solve the problems without reasoning, we use fictional names for all concepts (e.g. "wumpus" instead of "cat" etc.).
'Wit minor differences: Negation introdunttion/elimnnatio truth introduction, and falsity elimination are impossible express in natural text, and they omitted. We use proof by contradiction reason negation.

---

Varying proof width and depth. To characterize the size or complexity of each proof, we represent each proof as tree (Figure 2), where each proof step corresponds to node, and its premises correspond to the parent nodes. Then the size of the proof can be naturally described by the width and depth of this tree. When generating proofs, we control the depth by continuing to append proof steps until a proof of the desired depth is generated. The number of premises of deduction rules is set to the desired proof width.
Generating compositional proofs. To generate proofs combining many different types of deduction rules, we use simple recursive procedure: (1) select a deduction rule uniformly at random, (2) select the premises for the selected rule, (3) recursively generate subproof for each premise. See section A.5 for details and pseudocode.
Adding distractors. One key challenge to OOD generalization is shortcut solutions. For example, given the facts "Alex cat," "All cats are feline," since there no other fact of the form "All cats are...," the model can deterministically follow the only valid deduction and conclude "Alex is feline." " To make the heuristics uninformative, we add distractor sentences. In the above case, distractor sentence would be "All cats are graceful." Then the model is forced to choose the correct premise from two options for the next deduction step. See Section A.7 for details on distractors for all deduction rules.
Formal evaluation of chain-of-thought. Unlike previous datasets that evaluate on a binary true/false answer, PRONTOQA-OO -OOD requires LLMs to generate full proofs. Therefore, we need a way to evaluate the correctness of the output proofs directly. The sentences in PRONTOQA-OOD are syntactically simple and amenable to semantic parsing, which allows us to formally analyze each step in the CoT. To determine whether a predicted CoT correct, we: (1) semantically parse each CoT sentence into first-order logic, (2) determine whether each logical form follows from previous logical forms via a rule of deduction, and (3) compute whether there exists a path of correct steps from the premises to the goal. An example of this process is shown below:
"Alex is dog.
dog(alex),
(ar((g(()) + mammel(x)) dog(alex)
All dogs are mammals.
(z(()g(22) + mammal(x)).
Alex a mammal."
(alex)
manmal (alex)
Each proof step is considered correct if it is valid and if immediately follows of its premises."
For further details see section A.6.
Results
FLAN-T5
LLaMA
GPT-3.5
PaLM
In this section, we test existing LLMs on PRONTOQA-OON -OD and analyze whether they can produce longer and compositional proofs given simpler demonstrations. We experiment with variety of models, with different sizes and training objectives, as shown in Figure 3. In all experiments, 8-shot chain-of-tie to-thoof- prompting. We compare performance in two settings: (1) an in-demonstration (ID) setting where the 8 in-context demonstrations come from the same distribution as the test example, and (2) an (OOD) setting where the in-context demonstrations come from a distribution that is different from that of the test example. 95% confidence intervals are provided for all results.
Model Size
11B
658
175B*
540B
Instruction
X
RLHF
*
Open
Limited
Limited
Limited
An overview and properties of the LLMs in our experi- ments. We place an asterisk* for GPT-3.5 since to verify size.
FIGURE 3:
not able
TTreeffasse queries introduce an extra implicit negation step of the final conclusion. The negated conclusion may be tricky to represent in natural language given the extensive space of potential conclusions of the proofs that we generate.
'Note that if we only check for validity, the following proof would be considered correct: "Fae is a cat. All cats are carnivores. Fae is carnivore. All carnivores are mammals. Fae is a mammal, All mammals are not herbivorous. Fae is not herbivorous." Here, the goal is to prove "Fae is not herbivorous." Every step of the proof correct except "All mammals are not herbivorous." To avoid this, we require each step to immediately follow one its premises.
Following PRONTOQA, since adding further in-context examples did not improve performance.
5

---

ID: Rule generalization
1.00
proof accuracy
0.75
PaLM
0.50
LLaMA
FLAN-TS
0.25
0.00
implication
conjunction introduction
conjunction elimination
disjunction introduction
disjunction elimination
proof contradiction
elimination
OOD: Rule generalization
0.5
A proof accuracy
0.0
PaTM
1LMA
-0.5
FLAN-TS
implication elimination
conjunction introduction
conjunction elimination
disjunction introduction
disjunction elimination
proof by contradiction
FIGURE 4: (top) Proof accuracy across examples different deduction rules. The in-context examples and test examples come from the same distribution. (bottom) Change in proof accuracy, where the test example is out-of-demonstraile deduction rule, but the in-context examples uniformly distributed over all other deduction rules. See Figure 11 the Appendix for the equivalent plot with absolute proof accuracy the y-axis. See Figure for an incorrect example. Implication climination examples have proof width of and depth of 2. Conjunction introduction, conjunction climination, and disjunction introduction examples have proof width and depth 2. Disjunction elimination examples have proof width 3 and depth 1. Proof by contradiction examples have proof width 2 and depth 1.
with respect to the in-context examples. That is, the test example has the specified
Prove: Max is gorpus.
Predicted answer: Max is tumpus rompus lempus. Max tumpus.
Tumpuses are wumpuses. Max a wumpus. Rompuses are gorpuses. Max is gorpus. Max 18 a gorpus.
Expected answer: Asaume Max is a tumpus. Tumpuses are gorpuses. Assume Max is rompus. Rompuses are gorpuses. Max is a gorpus. Assume Max is lempus. Lempuses gorpuses. Max is gorpus.
Max is a gorpus.
tumpus rompus
lempus,
gorpus.
FIGURE 5: Example of incorrect proof generated by GPT-3.5 on out-o--demonstration disjunction elimination example. The premises (axioms) given in blue, and invalid steps given in red. For the full example, see Figure 14 the Appendix.
4.1 Can LLMs use deduction rules other than modus ponens?
We first evaluate whether LLMs "know" all deduction rules (Table 2) when provided with correspond- ing CoT prompts. For each deduction rule, we independently and identically generate in-context examples and one test example, and prompt the model to answer the test example. We run each experiment for 100 trials and measure the accuracy of the output proofs. The accuracies are shown in the top chart of Figure 4. We emphasize that the A proof accuracies in the bottom row of the figure should be interpreted comparison with the accuracies in the top row (e.g. for some rules, the zero A accuracy for FLAN-T5 is due zero absolute accuracy). For clarity, we provide the same plots using absolute accuracy rather than A accuracy Section A.2.
In general, most models are able to use each deduction rule reasonably well, with GPT-3.5 performing best. Similar prior studies [Liang et al., 2022], we do not observe a strong correlation between model size and performance. I.aMA performs comparably to PaLM, despite being smaller. FLAN- T5 is smaller and performs reasonably on implication and conjunction elimination, but is not able to leam the other deduction rules.

---

Prove:
Polly not lempus.
ID: Compositional examples
1,00
Predicted answer: Polly is wumpus, jompus, and tumpus. Everything that is a wumpus, a jompus, and a tumpus is not
proof accuracy
G27-35
PaLM
LLMA
FLAN-15
0.75
0.50
lempus. Polly is not lempus.
0.25
Expected answer: Polly is tumpus. Polly is a jompus. Polly is vumpua. Polly is wumpus and jompus and tumpus. Everything that wumpus, a jompus, and a tumpus is not a lorpus. Polly is not lorpus.
0.00
min depth:
min depth:
min depth:
min depth: rule types: 3
rule types:
rule types:
rule types:
OOD: Compositional examples
0.50
à proof accuracy
0.25
Asaume Polly is a lempus. Each lempus
0.00
impus and lorpus and rompus. Polly is an impus and a lorpus and a rompus. Polly is lorpus. This contradicts with Polly is not a lorpus. Polly is lempus.
-0.25
-0.50
min depth: min depth: min depth: min depth:
rule types:
rule types:
rule types:
rule typess
FIGURE (top-left) Proof accuracy compositional examples where the in-context examples are also compositional examples with the same min depth and number rule types. (bottom-left) Change in proof accuracy where the test examples are compositional but the in-context examples are those of individual deduction rules. See Figure 12 in the Appendix for the equivalent plot with absolute proof accuracy the y-axis. (right) Example of an incorrect proof generated by GPT-3.5 4 rule types. The premises (axioms) are given in blue, and invalid steps are given red. For the full example, see Figure 15 in the Appendix.
oetoos-demonsttattinn example with min depth 2 and
4.2 Out-offdemmonstration generalization
4.2.1 Can LLMs generalize to unseen deduction rules?
While the above results show that LLMs are able to reason with variety of deduction rules, it is unclear whether the ability is learned from in-context examples or elicited from pretraining. We test the LLM with examples where the test proof requires deduction rule that does not appear in the in-context examples (i.e. for each in-context example, we sample a deduction rule uniformly at random from the set of deduction rules excluding that of the test example). Our intuition was that LLMS would not be able to use deduction rules unless given explicit demonstrations thereof (aside from those like modus ponens which are well-represented in pretraining). The change in proof accuracy relative to the ID setting is shown in the bottom chart of Figure 4. Evidently, the models are able to use four deduction rules despite not being shown an in-context example with those rules: both conjunction rules, disjunction introduction, and (somewhat) implication elimination. GPT-3.5 was additionally able to proof by contradiction by relying on alternate deduction rule called modus tollens (i.e. given (c) and (g(() + f(c)), conclude -g(c)). This is in contrast with McKenzie et al. [2022] which showed that reasoning with modus tollens exhibited inverse scaling behavior, and yet GPT-3.5 is able to use it correctly without any demonstrations. However, Wei et al. [2022a] has shown that when trained with additional compute, models able to perform modus tollens. GPT-3.5 performed worse on disjunction elimination possibly due to the fact that there is no equivalent alternate rule (an example of an error is given in figure 5). However, model is able to use disjunction elimination and proof by contradiction without demonstrations.
4.2.2
Can LLMs generalize to compositional proofs?
Next, we test whether the model is able to generalize to compositional proofs that contain multiple different deduction rules. In the ID setting, the in-context examples and test examples are both generated from the same distribution of compositional proofs. the OOD setting, the in-context demonstrations contain non-compositional examples of each rule that appears in the test example. In Figure 6, in all but three experiments, we observe that the gap in proof accuracy between the ID) and OOD settings is close to zero, indicating that the models are able to generalize compositionally
7

---

GTT33
PaLM
LLaMA
FLAN-TS
Depth generalization: Implication elimination
Depth generalization: Conjunction introduction
1.00
1.00
proof accuracy
proof accuracy
0.75
0.75
0.50
0.50
0.25
0.25
0.00
0.00
proof depth of test example
proof depth of test example
Width generalization: Conjunction elimination
Width generalization: Conjunction introduction
1.00
1.00
proof accuracy
proof accuracy
0.75
0.75
0.50
0.50
0.25
0.25
0.00
0.00
3
2
3
proof width of test example
proof width test example
FIGURE (top row) Proof accuracy vs proof depth test examples, where in-context examples have fixed proof depth 2. (bottom row) Proof accuracy vs proof width of test examples, where in-context examples have fixed proof width 2. Dashed lines indicate in ni-distribution accuracy, where the depth and width of the in context examples are the same as that of the text-examples. In these experiments, there are 4 rather than 8 in-context examples.
to an extent. This is surprising since past studies show that LLMs struggle with compositional generalization, but this could be due to the fact that much of the previous work focused on semantic parsing rather than on reasoning. But there is prior work showing that models can generalize compositionally some settings, such as Hosseini et al. [2022] (see Figure 4) and in Press et al. [2022] (see Figure 6). In addition, our study is limited by the token limit of the LLMss, as we are not able to further increase the complexity of the proofs without reducing the number of in-context examples, which would render the results difficull to compare. GPT-3.5 and PALM have difficulty when the number rule types is 4, with an example of an incorrect output given in the right side of Figure 6. Interestingly, PALM, LLAMA, and FLAN-T5 sometimes perform better in the OOD setting than in the ID setting, showing that, in ICL, it not always best to provide demonstrations from the same distribution the test example.
4.2.3 Can LLMs generalize to bigger proofs?
To test whether LLMs can generalize to bigger proofs, we test the models on examples where the proof width depth is larger than those of the in-context examples. As is evident from Figure when shown demonstrations of proofs of depth 2, the models' performance decreases with increasing depth. But this due the increase in the inherent difficulty of the task. both ID and OOD accuracies decrease with increasing depth. Though the notable exception is GPT-3.5 on conjunction elimination, where ID accuracy remains high as OOD accuracy decreases. Models are able generalize better with increasing proof width on conjunction elimination, possibly because there are ample examples of long conjunctions in natural language, but only GPT-3.5 is able to generalize to greater proof widths on conjunction introduction.
4.3 Do distractors help OOD generalization?
In supervised learning, one challenge to OOD generalization spurious correlations [Zhang et al., 2022b]. Intuitively, if ICL were to behave like supervised learning on in-context examples [Akyürek al.. 2023, Dai et al., 2023, von Oswald al., 2022], we would expect that without distractors. the models would overfit to the in-context examples and perform poorly on OOD examples. An example where distractors hurt generalization is shown Figure where GPT-3.5 copies many of the distractor sentences into the output, likely due to the fact that it has learned to apply copying heuristic from the in-context demonstrations. seems only GPT-3.5 acquires these heuristies in implication and disjunction elimination. Surprisingly, this is not the case for all deduction rules, as is

---

ID: In-context examples with distractors
1.00
proof accuracy
0.75
GPI-35
0.50
LAAMA
0.25
0.00
implication
conjunction introduxction
conjunction elimination
disjunction introduction
disjunction elimination
proof by
climination
contradiction
OOD: In-context examples without distractors
0.5
& prouf accuracy
0.0
GP133
PaLM
-0.5
FLAN-IS
-1.0
implication
conjunction introduction
conjunction elimination
disjunction introduction
disjunction elimination
proof by contradiction
climination
OOD: In-context examples with irrelevant sentences
proof
GF133
LLaMA
implication conjunction elimination
conjunction elimination
disjunction introduction
disjunction elimination
proof by contradiction
introduction
FIGURE 8: (top) Proof accuracy examples where both the in-context examples and test examples have distractors. Sentences in all questions ordered randomly. (middle) Proof accuracy when distractors removed from the in-context examples, not from the test examples. The sentences the in-context questions have fixed order (corresponding to a postorder traversal of the ontology tree), whereas the sentences in the test question have random order. See Figure 13 in the Appendix for the equivalent plot with absolute proof accuracy the y-axis. (bottom) The same setting (middle) except the distractors in the in-context examples instead replaced with irrelevant sentenees. Implication climination examples have proof width of and depth Conjunction introduction, conjunction climination, and disjunction introduction examples have proof width and depth 2. Disjunction elimination examples have proof width 3 and depth 1. Proof by contradiction examples have proof width 2 and depth 1.
Prove: Sally is dull.
Sally is impus. Impuses are sterpuses. Every grimpus is zumpus. Every brimpus is grimpus. Lorpuses dumpuses. Brimpuses vumpuses. Every lorpus brimpus. Sally is brimpus.
Predicted unswer:
vumpus is opaque. is not broun. Every grimpus is dull. Sally is grinpus. Sally is dull.
dumpus
Expected answer: Sally is a brimpus. Every brimpus a grimpus. Sally is grimpus. Each grimpus is dull. Sally is dull.
FIGURE 9: Example of incorrect proof generated by GPT-3.5 OOD implication elimination example where the in-context demonstrations have no distractors, the test example does. The premises (axioms) are given in blue, and invalid steps are given red. For the full example, see Figure 16 in the Appendix.
visible in Figure 8. The models' performance is largely unaffected, with the exception of few rules for specific models. This is in stark contrast to supervised learning, where it is always best to train on examples from the same distribution the test example.
Conclusion and future work
In this study, we provide a systematic test of the general deductive reasoning capabilities of LLMs, specifically measuring their rule-, depth-, width-, and compositional generalization abilities. We found that L.LMs exhibit mixed generalization unseen deduction rules, but they exhibit more robust generalization to compositional proofs than previously suggested.

---

One important future direction is to better understand the mechanism of ICL and CoT prompting. We found that in many cases, for a given test example, the best in-context examples were drawn from distribution distinct from that of the test example. This is not explained by existing theories of Bayesian inference [Xie al., 2022] or gradient descent [Akyürek et al., 2023, Dai al., 2023, von Oswald et al., 2022]. Are simpler examples better even if the test example is fairly complex? Should we include examples with a diverse set of deduction rules [Levy et al., 2022]? Or should the in-context examples focus on rules for which the model's OOD generalization is poor? Further study needed to better characterize generalization from in-context examples.
Reproducibility statement
For the sake of reproducibility of the analysis, model outputs (except those of Pal.M, code for data generation, and analysis code are freely available with a permissive open-source license at gi github. com/ http//aarr//ppooooo.aaa The generated data for all experiments in this paper is avail- able in the file generated_ _oo__ooodaaaaaaeeeeeeeeeeeeeaaee zip. The command python pake_plots. py produces all figures used in this paper. GPT-3.5 experiments were run using the OpenAl API with the model on April 20th 22rdd 2023. Experiments for Figure 7 and the bottom row of Figure were August 3tt 2023.
Acknowledgements
We thank Tania Bedrax-Weit Xin Xu, and Deepak Ramachandran for their valuable feedback. This work supported by Open Philanthropy, AWS AI, Samsung Advanced Institute of Technology (under the project Next Generation Deep Learning: From Pattern Recognition to AI), and in part through the NYU IT High Performance Computing resources, services, and staff expertise. NJ is supported by an NSF Graduate Research Fellowship under grant number 1839302.
References
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? Investigations with linear models. In The Eleventh International Conference Learning Representations, 2023. URL WtRlhhttps///ppeeeeeee 0g0X4H8yN4I.
Shengnan An, Zeqi Lin, Qiang Fu, Bei Chen, Nanning Zheng, Jian-Guang Lou, and Dongmei Zhang, How do in-context examples affect compositional generalization? CoRR, hass/3005048835 2023, URL https://axxii... www.oorgg////aoeeeeoeeee abs/2305 04835.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay V. Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. CoRR, abs/2207.0400 04901, 2022. doi: 00448550/axxi.2200..4000 URL https: //doi /doi. org/10. 10. 48550/ arviv 2207 04901.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski. Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontack Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Sankaranaraaaaaaaaaaaaaa Pillai, Marie Pellat, Aitor Lewkowyez, Er- ica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language model- ing with pathways. CoRR, abs/2204.02311, 2022. doi: 10.48550laxx..220440311 URI https: / //ooi//ii//// org/10. /00 48550/ arxiv 2204. 02311.
10

---

Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y. Zhao, Yanping Huang, Andrew M. Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. Scaling instruction- finetuned language models. CoRR, abs/2210. 1416, 2022. doi: 10.48850/rrXiv2210000 11416. URL https://don org/10 10. 48550/ arxiv 2210.222222222222 11416.
Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Zhifang Sui, and Furu Wei. Why can gpt learn in- context? language models secretly perform gradient descent as meta optimizers. In Findings of the Association for Computational Linguistics: ACL 2023, Toronto, Canada, 2023. Association for Computational Linguistics.
G. Gentzen. Untersuchungen über das logische schließen i. Mathematische 2.itcchh 1935.
19:tchhriii,91776--22 39:176-210.
Nicolas Gontier, Koustuv Sinha, Siva Reddy, and Christopher Pal. Mcasuring systematic general- ization neural proof generation with transformers. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL https: / pppppeeeeeeengeeeee neurips. Abstract html.
cc/paper/200 2200 http:/22200hhahaaah
Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Ekaterina Zubova, Yujie Qiao. Matthew Burtell, David Peng, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, Ansong Ni, Linyong Nan, Jungo Kasai, Tao Yu, Rui Zhang, Shafiq R. Joty, Alexander R. Fabbri, Wojeiech Kryscinski, Xi Victoria Lin, Caiming Xiong, and Dragomir Radev. FOLIO: natural language reasoning with first-order logic. CoRR, abs/2209.0088 00840, 2022. doi: 10.485500ar2iv.2220..00 000400. URL https: /doii org/10 A8550/arXiv 2209. 00840..
Arian Hosseini, Ankit Vani, Dzmitry Bahdanau, Alessandro Sordoni, and Aaron C. Courville. On the compositional generalization gap of in-context learning. In Jasmijn Bastings, Yonatan Belinkov, Yanai Elazar, Dieuwke Hupkes, Naomi Saphra, and Sarah Wiegreffe, editors, Pro- ceedings of the Fifth BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP, BlackboxNLP EMMLP 2022, Abu Dhabi, United Arab Emirales (Hybrid), Decem- ber 8, 2022, pages 272-280. Association for Computational Linguisties, 2022. URL https: l/aclanthology . org/ 2222.222..22 blackboxmlp-1.22
Jie Huang and Kevin Chen-Chual Chang. Towards reasoning in large language models: A survey. CoRR, abs/2212. 2.s/2222.10403, 2022. doi: 10.488550arxx..222...00 10403. URL https://doi. org/10. 48550/ arxiv. 2212. 10403.
Seyed Mehran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, and Deepak Ramachandran. LAM- BADA: backward chaining for automated reasoning in natural language. In Proceedings of the sl Annual Meeting of the Association for Computational Linguistics, Toronto, Canada, July 2023. Association for Computational Linguistics.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Advances in Neural Information Pro- cessing Systems, 2022. URL http:: http::/ mips. cc/ fatplpaaalllee///l/lllllaaaaeeee pptpp//ppp2///aaaa////e h2s////h/22hhh/h////// .ttl..
Keito Kudo, Yoichi Aoki, Tatsuki Kuribayashi, Ana Brassard, Masashi Yoshikawa, Keisuke Sak- aguchi, and Kentaro Inui. Do deep neural networks capture compositionality in arithmetic reason- ing? In Andreas Vlachos and Isabelle Augenstein, editors, Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, FACI. 2023, Dubrovnik, Croatia, May 2-6, 2023, pages 1343-1354, Association for Computational Linguisties, 2023. URL https: fttep://accantholooe
org/ 2223/2223..022 eacl - main. 98.
Itay Levy, Ben Bogin, and Jonathan Berant. Diverse demonstrations improve in-context compositional generalization. CoRR, abs/2212.06800 2022. doi: 10.48550/arKv.22122066000 URI. https: //doi. //doi.org/10. org/10. 48550/ (15550/aXiiv 2212.22222222222 06800.
11

---

Aitor Lewkowyez, Anders Johan Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Venkatesh Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL /tttp::/oppnrevier. sett/forun?2d--1IXYEEB....
Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang. Deepak Narayanan, Yuhuai Wu, Ananya Kumar, Benjamin Newman, Binhang Yuan, Bobby Yan, Ce Zhang. Christian Cosgrove, Christopher
Manning, Christopher Ré, Diana Acosta-Navas, Drew A. Hudson, Eric Zelikman, Esin Durmus, Faisal Ladhak, Frieda Rong, Hongyu Ren, Huaxiu Yao, Jue Wang, Keshav Santhanam, Laurel Orr, Lucia Zheng, Mert Yüksekgönül, Mirac Suzgun, Nathan Kim, Neel Guha, Niladri S. Chatterji, Omar Khattab, Peter Henderson, Qian Huang, Ryan Chi, Sang Michael Xie, Shibani Santurkar, Surya Ganguli, Tatsunori Hashimoto, Thomas Icard, Tianyi Zhang, Vishrav Chaudhary, William Wang, Xuechen Li, Yifan Mai, Yuhui Zhang, and Yuta Koreeda. Holistic evaluation of language models. CoRR, abs/221 1.09110, 2022. doi: 10.48550/arXiv.22 111122111111111 100110. URL https: //t:::///do org/ 10. 48550/ ariiv 2211 09110.
Jian Liu, Leyang Cui, Hammeng Liu, Dandan Huang, Yile Wang, and Yue Zhang. Logiqa: A challenge dataset for machine reading comprehension with logical reasoning. In Christian Bessiere, editor, Proceedings of the Twenty-Nimt International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 3622-3628. ijcai.org, 2020. doi: 200966//ccai2222/50000 URL https: //doi.org// 10. 24963/ /iaa//ija....// 2020/501.
Ian McKenzie, Alexander Lyzhov, Alicia Parrish, Ameya Prabhu, Aaron Mueller, Najoung Kim, Sam Bowman, and Ethan Perez. Inverse scaling prize: Second round winners, 2022. URL attps://irmckenzh/ co. uk/round2.
Maxwell I. Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language models. CoRR, //bs/2112.00111 14, 2021. URL
wtwp://www....r//////..... 00114
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances Neural Information Processing Systems, 2022. URL https: http:/:///peeevvieeeeeeee eepeeneeviww..mm.. new/ font//form??? Tx=EGAA
Frank Pfenning. Natural deduction. Lecture notes in 15-815 Automated Theorem Proving, 2004. URL https: //wp://wwww.cc cs. cmu, wttpe///////ours///aaa///////p// http://apaaaaaoussc///h// www.eannnnnnnn.eaaaaeeeaa pdf.
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis. Measuring and narrowing the compositionality gap language models. CoRR, abs/2210.033500, 2022. doi:
10.48550/arxii.2210.333 URL https: /tttps://doi org/ 10. 48550/ arrivv.iivvv...v. 2210. 03350.
Linlu Qiu, Peter Shaw, Panupong Pasupat, Tianze Shi, Jonathan Herzig, Emily Pitler, Fei Sha, and Kristina Toutanova. Evaluating the impact of model scale for compositional generalization in semantic parsing. In Yoav Goldberg. Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pages 9157-9179. Association for Computational Linguistics, 2022. URL httph:tt//// http://llaaaathohoeoo/e org/ org/2022 2022. emnlp-man mminn..mmai..mmmm m2...
Soumya Sanyal, Zeyi Liao, and Xiang Ren. Robustir: A diagnostic benchmark for evaluating logical robustness of deductive reasoners. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirutes, December 7-11, 2022, pages 9614-9631. Association for Computational Linguistics, 2022. doi: 10. 00.18663/1122022eemmp- mainnppmmiin65.3. URI. https: //doi. org/10. 10. 18653/v1/2022. emnlp-maaa..a...e 653.
12

---

Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of- thain-of-thought. The Eleventh International Conference on Learning Representations, 2023.
URL http:/::///eerreeee..eee. http://///pppeeeeeee///oo/a//aa/ wwt.:e//oorrurt.teegea.a...a
Koustuv Sinha, Shagun Sodhani, Jin Dong. Joelle Pineau, and William L. Hamilton. CLUTRR:
A diagnostic benchmark for inductive reasoning from text. In Kentaro Inui, Jing Jiang, Vincent Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-
Ng. and Xiaojun Wan, editors, Proceedings of the 2019 Conference
2019, Hong Kong, China, November 3-7, 2019, pages 4505-4514. Association for Computational Linguistics, 2019. doi: 1..18653/11/11--11 //doi //doi.org/10 18653/663/12 vtt1///1/11/// 1458.
URL https:
Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. Proofwriter: Generating implications, proofs, and abductive statements over natural language. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, Findings of the Association for Computational Linguistics: ACI/IJCNLP 2021, Online Event, August 1-6, 2021, volume ACL/UJNLP 2021 of Findings of ACL,, pages 3621-3634 Association for Computational Linguistics, 2021. doi: 10. (0.18653/v1/2000 1/255/.//.. ac1.317. URL https://doi. org/ 10. 11w53/11120000 fwwdiigiinnniii 317.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anme Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. LLaMA: Open and efficient foundation language models. CoRR, abs/2302. 13971, 2023. doi: 10.48550ar2iv22302.155 13971. org/10. org/10.48550/ 4 arriv. 2302. 13971.
URL https: //doi.
Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. CoRR, abs/2212.07677 2022. doi: 10.48550/axXx..222..777777 URL https: org/10. 48550/ artov..iiv.... 2212.07677
Xinyi Wang, Wanrong Zhu, and William Yang Wang. Large language models are implicitly topic mod- els: Explaining and finding good demonstrations for in-context learning. CoRR, abs/2301.11916. 2023. doi: 10.48550/arXiv.230011 11916.
URL https://don org org/10/ 38550/arXiv... 2301.
Jason Wei, Yi Tay, and Quoe V. Le. Inverse scaling can become u-shaped. CoRR, abs/2211.02011 2022a. doi: 0.485500/rXxv..2211.0000 URL https://doo org/ 02011.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022b. URL -VJQLMeSB_J.
net/forum?ide
Yuhuai Wu, Albert Q. Jiang, Jimmy Ba, and Roger Baker Grosse. INT: inequality benchmark for evaluating generalization in theorem proving. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL nttps://openreviiss net/ forum?dd-DSLPudooiii
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://openreview wttp:ereeeieieeeeffoeeeeeeee net./Eorum/dddRdJJeEH..
Xi Ye, Srinivasan Iyer, Asli Celikyilmaz, Ves Stoyanov, Greg Durrett, and Ramakanth Pasunuru. Complementary explanations for effective in-context learning. CoRR, abs/2211. 2022. doi: 10.485550arXiw.2211..5
URL www.hhtps///ooo. org/ 10. 10.400..//..1111. 2289.1189.....211111
Hanlin Zhang, Yi-Fan Zhang, Li Erran Li, and Eric P. Xing. The impact of symbolic representations on in-context learning for few-shot reasoning. CoRR, abs/2212.08668 2022a. doi: 10.48550/arXiv. 2212.08686 URL https: //wii//////// org/10. 48550.8855/4480 /arisv//r//vv./.. 2212. 08686.
13

---

Honghua Zhang. Liunian Harold Li, Tao Meng, Kai-Wei Chang, and Guy Van den Broeck, On the paradox of learning to reason from data, CoRR, 115022 2022b. doi: 10.48550/arXiv. 2205.1 1502. URL. http:::t//////.. / //d////..w./ org/10. 48550/ 2205. 11502.
14

---

A Appendix
A.1 Example from PRONTOQA-0OD
Q: Everything that is lorpus, brimpus, or a jompus is shumpus. Every wumpus is a vumpus and a sterpus and a brimpus. Everything that is a vumpus, grimpus, or brimpus is lempus. Everything that is a lempus or jompus or a lorpus is a dumpus. Vumpuses are rompuses. Every sterpus is gorpus. Everything that is a vumpus, a grimpus, or brimpus dumpus. Wumpuses are shumpuses. Polly is a rompus. Polly is a wumpus. Prove: Polly is a lempus or an impus or a yumpus.
A: Polly is wumpus. Every wumpus is vumpus and sterpus and brimpus. Polly is vumpus and a sterpus and a brimpus. Polly is a brimpus. Polly is vumpus, grimpus,
brimpus. Everything that is vumpus, grimpus, or a brimpus is a lempus. Polly is a lempus. Polly is a lempus, an impus, or yumpus.
FIGURE 10: An example from PRONTOQA-OOD, is compositional example with min depth and 3 rule types. The given answer is the expected chain-of-thought. The question is shown in blue, the query in red, and the thain-of-though/ansswee in green.
A.2 Results with absolute accuracy
ID: Rule generalization
1.00
proof proof accuracy
GPT-355
PaLM
0.50
FLAN-TS
0.25
0.00
implication
conjunction introduction
conjunction elimination
disjunction introduction
disjunction elimination
proof by contradiction
elimination
OOD: Rule generalization
proof accuracy
0.75
GPT-33
0.50
LLMMA
FLAN-T5
0.25
0.00
implication elimination
conjunction introduction
conjunction elimination
disjunction introduction
disjunction elimination
proof contradiction
FIGURE 11: (top) Proof accuracy across examples with different deduction rules. The in-context examples and test examples come from the same distribution. (bottom) Proof accuracy where the test example is out-of- demonstration with respect to the in-context examples (for comparison, the in-demonstration proof accuracy is shown as the dotted black bars). That is, the example has the specified deduction rule, the in-context examples are uniformly distributed over other deduction rules. See Figure Implication elimination examples have proof width of and depth of 2. Conjunction introduction, conjunction elimination, and disjunction introduction examples have proof width 3 and depth 2. Disjunction elimination examples have proof width 3 and depth 1. Proof contradiction examples have proof width 2 and depth 1.
an incorrect example.
15

---

ID: Compositional examples
1.00
proof accuracy
GFE35
PaLM
LLaMA
FLAN-T5
0.75
0.50
min depth: 2
min depth: 2
min depth: 2 rule types:
min depth: 4 rule types:
rule types:
rule types:
OOD: Compositional examples
1.00
proof accuracy
0.75
0.00
min depth: 2
min depth: 2
min depth: 2
min depth: 4 rule types:
rule types:
nule types:
rule types:
FIGURE 12: (top) Proof accuracy on compositional examples where the in-context examples are also composi- tional examples with the same min depth and number of rule types. (bottom) Proof accuracy where the test examples compositional but the in-context examples are those of individual deduction rules (for comparison, the in-demonstration proof accuracy is shown the dotted black bars).
ID: In-context examples with distractors
proof accuracy
0.75
Cy135
0.50
LLaMA
0.25
implication
conjunction introduction
conjunction elimination
disjunction introduction
disjunction elimination
proof by contradiction
elimination
OOD: In-context examples without distraciors
1,00
proof accuracy
0.75
PaLM
0.50
proff
FLAN-T5
0.25
0.00
implication
conjunction introduction
conjunction climination
disjunction introduction
disjunction elimination
proof by contradiction
climination
OOD: In-context examples with irrelevant sentences
1.00
proof accuracy
0.75
CPT35
0.50
LLMA
0.00
implication
conjunction introduction
conjunction
disjunction introduction
disjunction elimination
proof by contradiction
FIGURE 13: (top) Proof accuracy examples where both the in-context examples and test examples have distractors. Sentences all questions are ordered randomly. (middle) Proof accuracy in-demonstration removed from in-context examples, but not from test examples (for comparison, the proof accuracy is shown as the dotted black bars). The sentences of the in-context questions have fixed order (corresponding to postorder traversal of the ontology tree), whereas the sentences in the test question have random order. (bottom) The same setting as (middle) except the distractors the in-context examples instead replaced with irrelevant sentences. Implication elimination examples have proof width of and depth of 2. Conjunction introduction, conjunction climination, and disjunction introduction examples have proof width 2 and depth 2. Disjunction elimination examples have proof width 3 and depth 1. Proof by contradiction examples have proof width and depth I.
distractors
16

---

A.3 Full examples of incorrect predicted proofs
Question:
Lempuses are gorpuses. Rampuses are sumpuses. Tumpuses are vumpuses.
Dumpuses gorpuses. Every zumpus is vumpus. Every brimpus is gorpus. Yumpuses gorpuses. Lempuses sumpuses. Rompuses gozpusea. Tumpusea are gorpuses. Max a tumpus or rompus or a lempua. Max is zumpus, tumpua, or a rompus.
Prove: Max 1a a gorpus.
Max is a tumpus or rompus or a lempus. Max is tumpue. Tumpuses wumpuses. Max is wumpus. Rompuses are gorpuses. Nax is gorpus. Max is gorpus.
Predicted answer:
Expected answer: Assume Max tumpua. Tumpuses are gorpuses. Assune Max & rompus. Rompusee are gorpusea. Max is gorpus.
Max is gorpus.
Assume Max is a lempus. Lempuses are gorpuses. Max is gorpus.
Since Nax is tumpus
rompus or lempus, Max is gorpus.
Example of incorrect proof generated by GPT-3.5 on an out-of-demoostration disjunction elimination example. The premises (axioms) are given in blue, and invalid steps given in red.
FIGURE 14:
Question: Polly is wumpus. Every rompus is dumpus. Lempuses are vumpuses. Everything that is a wumpus, jompus, and a tumpus is a dumpus. Polly is gorpus. Every impus is brimpus. Everything that is wumpus, gorpus, and shumpus is vumpus. Each lempus tumpus not lorpus. Zumpuses are lorpuses. Polly a shumpus. Polly is zumpus. Polly is a zumpue. Polly is vuspus. Polly is jompus. Polly is tumpus.
impus and lorpus and rompus. Everything that
a sumpus, jompus,
Prove: Polly is not lempus.
Predicted unswer: Polly is wumpus, jompus, and tumpus. Everything that is vumpus, jompus, and tumpus is lempua. Polly
lempus.
Supected answer: Pally tumpus. Polly
jompus. Polly sumpus. Polly tumpus. Everything that is wumpus, jompus, and
a wumpus and a jompus tumpus is not a lorpus. Polly is not a lorpus.
Assume Polly is lempus. Each lempus is an impus and lorpus and rompus. Polly impus and lorpus and rompus. Polly Polly
lorpus. This contradicts with
lorpus. Polly not lempus.
Example of an incorrect proof generated by GPT-3.5 on an out-of-demmosstration example with min depth and rule types. The premises (axioms) are given in blue, and invalid steps are given in red.
FIGURE 15:
Question: Every grimpus zumpus. vumpus opaque. dumpus brown. Each grimpus is dull. Lorpusee are moderate. Every brimpus is rainy. Impuaea are temperate. Lorpuses are dumpuses. Brinpuses are vumpuses. Every lorpus is brimpus. Zumpuses angry. Grimpuses yumpuses. Every brimpus grinpus. Impuses sterpuses. Sally is impus. Sally brimpus.
Prove: Sally is dull.
Predicted answer: Sally is an impus. Impuses are sterpuses. Every grimpus zumpus. Every brimpus is gr grimpus. Lorpuses are dumpuses. Brimpuses are vuspuses. Every lorpus is a brimpus. Sally is brimpus. Each vumpus is opaque. Each dumpus is not broun. Every grimpus is dull. Sally is grimpus. Sally is dull.
Sxpected answer: Sally is brimpus. Every brimpus is grimpus. Sally is a grimpus. Each grimpus is dull. Sally is dull.
FIGURE 16: Example of an incorrect proof generated by GPT-3.5 on an OOD implication elimination example where the in-context demonstrations have no distractors, but the test example does. The premises (axioms) are given in blue, and invalid steps given in red.
17

---

A.4 Generative process details
In this section, we describe the process to generate examples of each deduction rule.
Implication elimination (i.e. modus ponens) Given f(c) and Vx(f(z) - g(x)), prove g(c). These are the examples in the original PRONTOQA. We follow the same process here:
1. Generate an ontology. For simplicity, we generate linear ontologies, consisting of a collection of concepts, well subtype-supertype relations between those concepts (i.e. concept I is subtype of the supertype if every instance of f is an instance of g). For simplicity, we limit each type to have at most one supertype.
2. Perform a random walk of length from a randomly selected start vertex, where k is the desired proof depth.
3. Traverse the edges of the ontology and convert each into a sentence of the question.
4. Convert each step of the random walk into a sentence of the gold chain-of- of-thhught.
Note that this process allows us to generate proofs of any depth, but the width is fixed to 1.
Conjunction introduction Given A and B, prove A A B. The generative process is a modified version of that for implication elimination. Instead of generating rules of the form (x(((z) - g(2)), we generate rules of the form Vo(Si (ar) A... (x) (c), and Sn [c),), the model must first prove fi (c) A...A A fa (c) before applying implication elimination to prove g(c). To increase the depth of the proof, g(c) itself can be part of conjunct in the antecedent of another rule.
g(x)), where is the proof width. Given,
Conjunction elimination Given A B, prove A. These examples identical to those in conjunc- tion introduction, except the conjunction appears in the consequent of each rule, rather than in the antecedent: Vx((f()) > 9 (x) A... (x)) where is the proof width.
Disjunction introduction Given A, prove V B. These examples are identical to those in conjunc- tion introduction, except the conjunction is replaced with disjunction: (z)V.. (z.)) gx))) where n is the proof width. But note that grounded axioms are not necessary for every disjunct: To apply the rule vxrSf( (x) V... V (n()) - g(x)), knowing (n(e) is sufficient, and do not need to generate grounded axioms for the other disjuncts f((c) for < n.
Disjunction elimination (i.e. proof by cases) Given A V... V An, and A, + C' for all i, prove C. Here, n is the proof width. While it is possible to construct proof's containing multiple nested applications of disjunction elimination, such proofs are quite complex, even for humans understand, and so we fix the depth of these examples to 1. To generate an example, we first generate the disjunction: fi()) ... (c). Next, generate the rules for each case: (x(f((x) + g(x)) for all i. The goal is to prove g(c).
Proof by contradiction Given A and BB, prove -A. Note that this is a rule composed of two natural deduction rules: negation elimination and introduction. But since those individual rules do not lend themselves natural text representation, we choose to study their composition. Similar to disjunction elimination, it is possible to construct proofs containing multiple nested applications of proof by contradiction, but such proofs are unnaturally complex. So we fix the depth to 1. To generate an example, we first generate axiom -g(e). Next, for each subproof, we generate a rule (a V... V (xr) > g(x)). where n is the proof width. The goal to prove -fi(c) A... ... A (c). Note that in addition to proof by contradiction, this proof requires disjunction introduction, implication elimination, and conjunction introduction.
Note that the above list constitutes complete set of deduction rules from propositional natural deduction, save for one rule: implication introduction. However, it is unclear how to construct an example with this deduction rule where its difficulty can be controlled by increasing the width or depth of the proof (e.g. how can a statement of the form A, - A 7 A, be expressed in natural language?).
18

---

Algorithm 1: Pseudocode for generating examples of compositional proofs in PRONTOQA-OOD. In this algorithm, 52 denotes the set of all logical forms. The function generate, cttpreeooooocitieeeeeeee initially called with parameters ft Ø0 d, and false, where d is the requested depth and is randomly selected entity
watpssiiionnllpppa .proof is
(e-g. alex, fae, etc). sample is helper function that, given an input set of logical forms S and an entity e, returns sample_unisi uniform( (set logical forms with minimal depth where all atoms are of the form l(e) where is predicate)).
function cnmeratee_cmpoaitiinn proof (set of possible conclusions (logical forms) C, disallowed deduction rules R. requested depth d,
ground entity proof hypothetical h))
initialize A as the of all deduction nules excluding those in /* filter deduction rules such that: (1) an element of C can be conclusion of the rule, (2) for which we have sufficient depth, and (3) we don't create overly complex logical forms */ if C does contain conjunction
set
if does not contain a disjunction
set A = A (disjunction,
if h true or d
C does not contain negation
set A (proof_bre __ _ contradiction)
h = true or d or contains only conjunctions or only disjunctions
10
set = A {diejunction itteejunntioooelmmnatiiiooo
11
if C' contains only conjunctions only disjunctions
set A {conjunction elimination)
13
if contains only conjunctions only disjunctions and any operand negated set
14
\ (implication, wwwcccatneemmiinnaa.. eliminationn
15
if d = 0 or C' contains singleton logical form or A = Ø
return azi step with conclusion given by samp eCC,e)
sample uniform(A)
18
if r imp immlication ion_ elimnaaion
do 19
20
for any E C, and share operands or negations of operands annerate_compsittiee Sariaallproo(SSS (S2, Ø, e)
while do
22
23
and s do not share any operands or negations of operands
24
while 8 = sample(C,,
25
return implication_ elimination inmplcaattin.eeelmmaaatttooooon with premises and Va(afe - x] ale x))
26
else if = conjunctionn introduction
27
initialize as an empty list, and == 0
28
|C| if C contains only conjunctions, else T,
do
let C: = th operand of C' if C contains only conjunctions, else C; = Q generate_ compositions terittiinnn_pooottt .proof (C., (conjunction) el elimination). d 1, h)
30
31
if a atomic and is not any other operand C
33
append a to P i i=i+1 while L
34
38
return conjunction introduction with premises P
37
else if r = conjunction son son_ elimination
let C" be the set of conjunctions of length 3, aumple_uiiform(11222
C' C C" the tth operand of c' is in C) 39
do
= generate_compositionne wwwpocoiiiooallloooo..ooo. _roolllprooo(ee (C', (conjunction, ("onjuuttt iit.ooocnnittrotttinnnn...... d 1,e, h) while has no duplicate operands, and each operand of a is not itself a conjunction or disjunction
41
42
return conjunct ton, el immmmaaiio ion with premise a and conclusion given by the 1th operand of a
43
19

---

Algorithm 1: (continued from previous page)
44
else if duscttttionn introduction
45
C Ω let be the set disjunctions of length
46
i = sample_unis st__uniffrr form( number of disjuncts in C?)
47
do
let C. = :th operand of C
48
49
generate_composit compositional paool_proofcC. (disjunction, )imiimatiioi d e, h)
50
while is atomic and not any other operand of C
replace 1th operand of C with do
52
53
x - s=mpleee
54
while 4th disjunct of is distinct from all other disjuncts
return disjunctioo, introduct with premise given by the 8th operand of x and conclusion else if r = disjunction connntioon.. elimination
55
56
initialize P as empty list
58
while [P|
do if p is not a conjunction or disjunction and p has an axiom that is not an axiom of any q E
59
=
[disjunction. introduction). d 1, e, true)
60
61
L append to P
62
A.
set axioms P. that are not axioms of Pj for $
83
let a; = =sample_unifore
for all
let a' a disjunciii with disjuncts a, ctt.:/tttscoooossssooooopppppee return disjunction, introduction with premises a and P:
85
http://ntonnttooduueeeeooeoeeeee d 1, h)
87
else if = proof_ by_ contradiction
let . be the set of all negated logical forms
69
catprratteccooosieeeeeee wtrttlilloaolooMMM by bycoottradiction d 1,
70
do
71
a =8
generate, generate__ompositionn cowpositional. (rrof((ss) (proof_by_contrrreeee contraddiitii d e, true)
73
while has an atomic non-negated axiom that is not an axiom of
s' sample_ uniform( (atomic non-negated axioms of b that axioms of a})
75
return proof_ by. con contradiction with premises and b and conclusion me'
A.5
Generating compositional proofs
We use a simple recursive procedure to generate compositional proofs: (1) select deduction rule uniformly random, (2) select the premises for the selected rule, (3) recursively generate subproof for each premise. A consistency checking step is required to make sure we avoid generating contradictory axioms. In addition, introduction rule (or vice versa). See Algorithm in the appendix for pscudocode of this procedure. To test compositional proofs of various sizes, we implement a parameter that controls the minimum depth of the proof tree, and another parameter that controls the number of distinct rule types in each proof.
avoid generating elimination rule directly following an
A.6 Further details evaluation of CoT
We aim to test whether L.MMs are able to use deduction rules OOD, where the rules do not appear in the in-context examples, and take not be overly striet. For example, wish to avoid penalizing the model for formatting differences, so long as the reasoning is correct. To this end, in determining whether logical form follows from previous logical forms, we consider any deduction rule listed in Table 2. We also allow for two additional rules: (1) given Vz(f(z) + g(x)) and
An example is: Suppose select conjunction introduction as the first rule: next, recursively generate the proof of each conjunct; suppose for each of these, choose generate the axioms cat(alex) and -cat(alex).
In the following example, conjunction introduction step immediately follows a conjunction elimination step: "Jay is cat and orange. Jay is cat. Jay orange. Jay cat and orange."
20

---

vr(g(a) + h(z)) conclude (x(f(=) - h(z)), and (2) given vx(f(x) - g(x)) and -g(c) conclude -f(c) (i.e. modus tollens). 8 Additionally, we are flexible with respect the ordering of conjuncts and disjuncts. For example, given the previous steps (g()) and (r(((=))A(z))) - u(x) Vo(a)).
we consider v(a) u(a) to be valid.
A.7 Generating distractors
Implication elimination For any rule (x(f(z) + g(z)) in the gold proof, we generate a distractor distractor and is not helpful completing the proof. In addition, for any ground logical form in the gold proof fc), we generate distractor logical form h(c) well rule vz(h(z)) + (z)) Note that the original PRONTOQA only adds a single distractor, whereas we add multiple, one for each hop in the proof.
rule (x(((=) - h(z)) where the concept
Conjunction introduction Similar to those implication elimination. For any rule (z( (x) A...A (x()) + g(x)), we generate rule of the form (rr(h) (z: A... A h (a)) fn (x) - g(x)) where h; are distractor concepts. Grounded distractor conjuncts are also generated as axioms hi(c)). so that, given (c), both the gold rule and distractor rule are valid proof steps.
Conjunction elimination Distractors are generated similarly to the conjunction introduction case. Disjunction introduction Distractors are generated similarly to the conjunction introduction case. Disjunction elimination Since this deduction step has many premises, multiple distractors are neces- sary to ensure the model doesn't 't resort to heuristics. For every rule of the form (x((((x)) - g(x)), two distractor rules are generated: Vx(fi(x) - l((x)) and (x(),(()) - g())). A distractor disjunction is also generated: h² (c) V hy (c) V...V..-l1l
Proof by contradiction As with disjunction elimination, multiple distractors are necessary here. We generate two distractor rules (x( V... + h(x)) and (2)).. V.VV h, (x) g())).
We also generate the distractor axiom (c'(c) so that the model forced to choose between two axioms for the first step of the proof.
To avoid creating inconsistencies when generating a distractor rule, we avoid using existing predicates in the consequent of each rule.
Analogous to the valld steps in PRONTOQA.
21

---

Algorithm 2: Pscudocode for evaluating the output chain of ofouhhhtht Here, the comparison operations hetween logical forms ignore the order of conjuncts if both operands are conjunctions; and similarly for disjunctions. In addition, when iterating over previous steps in the proof, consider them in reverse order, that more
steps prioritized. The helper function negate defined, in order of precedence: negate( (44) A, negate B) negate (A) negate (B), negate(A B) negate(A) negate B), or ( AA
function evaluate_ (context sentences Q1..... Qm.
predicted thain-of-thought sentences goal sentence g)
L = semantic semantic_parsee parpccc_pp______ (g)
/* parse the goal */
for i E I..... do
/* parse the context
1 bemantic_parase (Q,)
for E 1..... do
/* parse the predicted thain-of-thought */
T = semantic_ppaaee
initialize an empty set, and H empty map reconstruct the proof from the chain-of- tthougt */
for E I,...,n do if L indicates 'this contradiction' megate(T. E (((.{_1)
10
(P, D. k) [ (T,+1)), (negatee)) (hegate(T[41))
else continue
13
else
(P, = is is.poovable (L..... ........ (,),..,,,,,,, S,), H)
14
set H(..) UpEP [p)) D
16
if 2 0
17
add L, S
18
/+ the proof is correct the final conclusion is provable +/ function is_provable (Logical form y. set axioms A.
return e
19
previous conclusions hypothesis map H)
20
if E A
21
return ([)),1)
/* this is axiom */
else if o conjunction disjunction initialize p' as an empty list, and for yi operand in do
23
24
25
(P, k) = provarlvlleeeeee A, if so is conjunction
27
if 2 and the step immediately preceding yp in the proof is in P append P to set k k else break
28
30
31
else if l: > and o is disjunction return (P, 2, k 1)
32
provable by disjunction introduction
33
if P' has the same size as ip has operands return (U,', 22,
34
provable by conjunction introduction */
35
a Ao if a is conjunction and ş = a, for some i
36
37
return (fa), Ø, + 1ia A})
/+ provable by conjunction elimination */
else if has form Vz + where 7/2
39
(P. k)) iis_provalleee (wlx c), H)
40
& 2 and the step immediately preceding yp in the proof is PU {a}
41
return (PU
{a A))
/* provable by conjunction elimination */
42
for s S where is a disjunction do
if for all disjuncts si, there is sj S such that s; 1p and E H(s;) return (183), (8i):
/* provable by disjunction elimination
22

---

Algorithm 2: (continued from previous page)
46
for a SUAde do
46
has form Var(1) + 7) where 7|2 + =
47
(P, k) = is _.s_provable (ifz + c A,
if ls 2 0 and the step immediately preceding & in the proof is in (U
return (PU (a) 1 A})
/* provable by implication elimination +/
else if has form Vz + 7) where negate (1) [2 (c)=
(P. _s__provable (negate (y(z c] A.
52
& 2 and the step immediately preceding y the proof (a)
/* provable with additional deduction rules (modus tollens) */ return (PU Ø, &o 1fa E A})
83
54
if y E 5
return (()).
/* proved by previous step
56
else if yp form Va((/ - 7)
/+ note: we precompute this graph */
57
let G be the graph where for axiom in A with form vz(aa - 9). and B are vertices and there is a directed edge from to 3
if there a path G from d ty
/* provable with additional deduction rules */ return (axioms corresponding to path edges, Ø, length of path)
59
60
return (0,00-1) -1)
/* this step is not provable (i.e., invalid) +/
23


Reviews:
[{"review_id": "NrfND1Hjyu", "reviewer": "Reviewer_w9uz", "summary": "The authors propose a new dataset ProntoQA-OOD, to evaluate LLMs' reasoning abilities across more complex proofs across multiple aspects such as depth, compositionality, etc. The authors find that LLMs are able to generalize to longer and compositional proofs but usually require demonstrations to get these good accuracies.", "questions": "See weakness section for suggestions.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The analysis done in the paper is pretty comprehensive and contains some interesting findings that can help future LLM research.\n* The dataset is an interesting resource for future reasoning-based evaluation of LLMs", "weaknesses": "* The main weakness is the lack of meaningful insights from the results, which are mostly contradictory to previous findings. Since the majority of the observations contradict previous works (section 4.2.1, 4.2.2, 4.3), its not sufficient to just state the observation and note its in stark contrast to previous findings. It'd help to take few of these scenarios and deep dive on why the observations are so different. Likely reasons could be the kind of datasets, number of ICL examples, etc. Please add a case study comparing these models across previous datasets and this dataset to make the analysis more interesting.\n* Another issue with so many surprising results where the authors claim that LLMs are good at a task (which previous papers found to be hard to solve), leads to the question about the specific data distribution being used to test these models. Maybe the data is very basic and in-distribution (i.e., the models already have strong knowledge about these instances). Comparisons with a synthetic dataset such as ProofWriter can help alleviate this issue.\n* Observations made by the authors in Section 4.2.2 (lines 192-193) that its not always best to provide demonstrations from the same distribution is in contrast to the general claim that LLMs do require in-demonstration examples (contribution 3). More discussion on this point needs to be done to explain when some examples are helpful and when they are harmful.\n* The work on expanding compostionality is very similar to a prior work [1] that explores OOD compositonality. Consider discussing that in the related works.\n\n[1] RobustLR: A Diagnostic Benchmark for Evaluating Logical Robustness of Deductive Reasoners, EMNLP 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and helpful comments! We would greatly appreciate any additional comments.\n\n1. “The main weakness is the lack of meaningful insights from the results, which are mostly contradictory to previous findings…”\n\nIn addition to the summary of contributions in the common rebuttal, we ran a handful of new experiments to perform a more in-depth investigation into some of the observations.\n\n  For the experiments probing the generalization capacity of LMs on proofs with greater depth and width, we were previously limited by the context limit of the LMs and were unable to test for higher proof depth and width values. Thus, we performed new experiments where we reduced the number of in-context (IC) examples from 8 to 4 and tested for greater proof depths and widths. We replace Fig 7 and 8 with Fig 12 in the supplementary PDF and rephrase Sec 4.2.3:\n\n  “As is evident from [New Fig], when shown demonstrations of proofs of depth 2, the models’ performance decreases with increasing depth. But this is due to the increase in the inherent difficulty of the task, as both ID and OOD accuracies decrease with increasing depth. Though the notable exception is GPT-3.5 on conjunction elimination, where ID accuracy remains high as OOD accuracy decreases. Models are able to generalize better with increasing proof width on conjunction elimination, but only GPT-3.5 is able to generalize to greater proof widths on conjunction introduction.”\n\n  Having probed higher depths, these results are more consistent with previous findings, and helps to disentangle the effects of proof width, depth, and rule composition.\n\nTaking a closer look at Fig 9, we observe for some deduction rules, removing distractors from the IC examples improved performance on test examples with distractors. We ran a new experiment, shown in Fig 13 of the supplementary PDF, where we replaced each distractor in the IC examples with an irrelevant sentence, unrelated to the ground truth proof. This tests whether the increased length of each IC example could cause poorer ID performance than OOD. We replace Fig 9 with 13 and add the following to Sec 4.3:\n\n  “The bottom row of [New Fig] shows the result where each distractor sentence in the IC examples is replaced with an irrelevant sentence. Irrelevant sentences are unrelated to the ground truth proof, containing entirely distinct entities and concepts. We observe that replacing the distractors with irrelevant sentences either does not change or decreases the accuracy, suggesting that, for conjunction introduction, the improved accuracy in the OOD setting is likely due to the fact that each IC example is not as long as in the ID setting. Thus, at least for some deduction rules, the model may be better primed for the task by simpler demonstrations than by those that are ID.”\n\n  To address the concern with Sec 4.2.1, we replace the sentence on line 172: “This is in contrast with McKenzie et al. [2023] which showed that reasoning with modus tollens exhibited inverse scaling behavior... More recently, [1] has shown that when trained with additional compute, models are able to perform modus tollens.”\n\n  We also note that the modus tollens task in the Inverse Scaling Prize is distinct from our task, and the results are not directly comparable.\n\nWe emphasize that much of the prior work showing models are unable to generalize compositionally was done on semantic parsing and not on reasoning, and so our findings complement but do not directly contradict with that body of work.  \n\n  We add the following to Sec 4.2.2 on line 186: “But there is prior work showing that models can generalize compositionally in some settings, such as in [2] (see Fig 4) and in [3] (see Fig 6).”\n  \n[1] Wei et al. 2022. Inverse scaling can become U-shaped.\n\n[2] Hosseini et al. 2022. On the compositional generalization gap of in-context learning.\n\n[3] Press et al. 2022. Measuring and narrowing the compositionality gap in language models.\n\n\n2. The data distribution used to test the models may be too simple.\n\nOur dataset is synthetic and specifically uses fictional names for concepts to avoid any confounding effects from the model’s knowledge acquired during pretraining. Compared with ProofWriter, our dataset tests for many more rules of deduction (covering all logical connectives in propositional logic), whereas ProofWriter tests only for modus ponens and conjunction rules. [1] demonstrate that the previous version of PrOntoQA is comparable with ProofWriter in terms of difficulty (compare Fig 2b and c in [1]), and the set of generated questions of PrOntoQA-OOD is a strict superset of that of PrOntoQA.\n\nFig 12 of the supplementary PDF shows a new experiment that probes the model’s ability to find proofs of depth much greater than that shown in Fig 7. The models do indeed struggle with proofs of such depth, indicating that the data distribution is likely not in the training distribution of the models.\n\n[1] Kazemi et al. 2023. LAMBADA: Backward chaining for automated reasoning in natural language.\n\n\n3. “More discussion on this point needs to be done to explain when some [IC] examples are helpful and when they are harmful.”\n\nWe agree and have added discussion as described in the common rebuttal. Specifically, we make a distinction between deduction rules with which the model is more vs less familiar. Our results show that in-demonstration examples are required for proof by cases and proof by contradiction, but not for other deduction rules.\n\n\n4. “The work on expanding compositionality is very similar to a prior work [1] that explores OOD compositionality. Consider discussing in related work”\n\nWe thank the reviewer for bringing this work to our attention. They similarly use synthetic examples to test the OOD reasoning capacity of models after fine-tuning. We will add it to the paragraph beginning on line 65.\n\n[1] Sanyal et al. 2022. RobustLR: A diagnostic benchmark for evaluating logical robustness of deductive reasoners."}, {"review_id": "YMu6AKUx4w", "reviewer": "Reviewer_ReKG", "summary": "In this paper, the authors explore the general deductive reasoning ability of LLMs. They test LLMs on a broad set of deduction rules and measure the ability to generalize to more complex proofs from simpler demonstrations from multiple angles. They construct a programmable dataset that enables control over deduction rules and proof complexity. The experiments are conducted on four LLMs with different sizes and training objectives.", "questions": "1. In line 183, \"we observe that the gap in proof accuracy between the ID and OOD settings is quite small\". However, in figure 6, it seems like you observe an accuracy drop of 20% in some experiments.\n\n2. Different from previous works, this paper claims that LLMs can generalize compositionally. Can you further compare your work with them, and analyze why different conclusions are made?\n\n3. I cannot understand the subtitle of section 4.1. Many a more concise and academic title would be better.", "limitations": "Not applicable.\n\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I think the paper is addressing an important research direction that helps better understand the general deductive reasoning ability of LLMs. Several strengths I particularly admire are:\n\n1. The category of rules and studies of models under various settings are systematic and comprehensive. Many takeaways are provided (although I believe some of them can be made clearer). \n2. The creation of a new synthetic and programmable reasoning dataset is a valuable contribution. This dataset allows for control over deduction rules and proof complexity, which can be beneficial for future research in this area.", "weaknesses": "While the paper presents comprehensive experiments to assess the reasoning capabilities of LLMs, there are aspects that require clarification:\n\n1. The main issue with the writing is that the outcomes of the experiments are not clearly communicated, likely due to a lack of correlation between figures and claims. For example, the paper asserts that \"LLMs can generalize to more complex proofs but require explicit demonstrations to produce hypothetical subproofs\". It would be beneficial if the authors could explicitly highlight which experiments (and comparisons) substantiate this claim. \n\n2. A critical concern, albeit not too severe, is the absence of a discussion about the underlying mechanisms and the implications or applications of the observations. Various claims are made, but the *reasons* behind these phenomena and *how* we can improve the models aren't elaborated on. For instance, ICL exhibits variable performance under different deduction rules, which complicates the decision of its usage. If the authors could provide explanations, identify the factors causing ICL's performance degradation, and propose potential solutions, it would significantly enhance the paper's value.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and helpful comments! We would greatly appreciate any additional comments or questions during the discussion period.\n\n1. “The main issue with the writing is that the outcomes of the experiments are not clearly communicated, likely due to a lack of correlation between figures and claims. For example, the paper asserts that \"LLMs can generalize to more complex proofs but require explicit demonstrations to produce hypothetical subproofs\". It would be beneficial if the authors could explicitly highlight which experiments (and comparisons) substantiate this claim.”\n\nWe thank the reviewer for the suggestion to make clearer the connections between claims and experiments. At the end of Section 1, in the bulleted list of main claims, we will add references to the subsections containing the experiments that substantiate the claim. More specifically:\n - On line 41, we will add explicit references to Subsection 4.2.2 and Figure 6.\n - On line 45, we will add explicit references to Subsections 4.2.2, 4.3, and Figures 6 and 9.\n - On line 49, we will add explicit references to Subsection 4.2.1 and Figure 4.\n\nIn addition, after each experiment described in the Results section, we will reiterate the main claims supported by that experiment.\n\n2. “...the reasons behind these phenomena and how we can improve the models aren't elaborated on. For instance, ICL exhibits variable performance under different deduction rules, which complicates the decision of its usage.”\n\nWe agree that the paper would benefit from additional elaboration and discussion on these points. We added further discussion as described in the common rebuttal. Specifically, we make a distinction between deduction rules with which the model is more vs less familiar. Our results show that in-demonstration examples are required for proof by cases and proof by contradiction, but not for other deduction rules, highlighting weaknesses where the models may benefit from explicit demonstrations, additional pretraining, and/or finetuning.\n\n\n3. “In line 183, `we observe that the gap in proof accuracy between the ID and OOD settings is quite small’. However, in figure 6, it seems like you observe an accuracy drop of 20% in some experiments.”  \n\nWe agree this characterization could be more nuanced. We will rephrase the sentence on 183 to: “Figure 6, in all but three experiments, we observe that the gap in proof accuracy between the ID and OOD settings is close to zero…”\n\n  It is also important to interpret the OOD \\Delta proof accuracies in comparison to the absolute proof accuracies shown in the ID charts. To underline this for the reader, we will add the following sentence to line 168: “We emphasize that the \\Delta proof accuracies in the bottom row of the figure should be interpreted in comparison with the accuracies in the top row (e.g. for some rules, the zero \\Delta accuracy for FLAN-T5 is due to zero absolute accuracy).”\n\n  Additionally, we will provide OOD charts with absolute proof accuracies in the Appendix.\n\n\n4. “Different from previous works, this paper claims that LLMs can generalize compositionally. Can you further compare your work with them, and analyze why different conclusions are made?”\n\nWe will add the following sentence to Section 4.2.2 on line 186: “But there is prior work showing that models can generalize compositionally in some settings, such as in [1] (see Figure 4) and in [2] (see Figure 6).”\n\n  We emphasize that much of the prior work showing models are unable to generalize compositionally was done on semantic parsing and not on reasoning, and so our findings do not directly contradict with that body of work. We are also careful to disentangle composition with respect to rules vs proof depth, which are often conflated. We find in new experiments that LMs are not able to find proofs with very large depth. The experiments are described in greater detail in (1) in the response to Reviewer w9uz, with results shown in the new figures in the 1-page supplementary PDF.\n\n[1] Arian Hosseini, Ankit Vani, Dzmitry Bahdanau, Alessandro Sordoni, and Aaron C. Courville. On the compositional generalization gap of in-context learning. BlackboxNLP@EMNLP 2022. URL https://aclanthology.org/2022.blackboxnlp-1.22.\n\n[2] Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, & Mike Lewis (2022). Measuring and Narrowing the Compositionality Gap in Language Models. CoRR, abs/2210.03350. URL https://arxiv.org/abs/2210.03350.\n\n5. “I cannot understand the subtitle of section 4.1. [Maybe] a more concise and academic title would be better.”\n\nWe thank the reviewer for the suggestion. We will rename the section to be clearer.\n"}, {"review_id": "1rnGlHJPDH", "reviewer": "Reviewer_CjCV", "summary": "This submission proposes a new dataset PRONTOQA-OOD to systematically study the general deductive reasoning capabilities of large language models (LLMs). Some findings are obtained, e.g., LLMs exhibit mixed generalization to unseen deduction rules and more robust generalization to longer, wider, and compositional proofs than previously suggested.", "questions": "How is the same distribution defined? That is, how do we determine whether two examples are obtained from the same distribution?", "limitations": "I do not find limitations that the authors do not address in their methodology or mention in future work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Summary:\n(1) A new dataset for evaluating the deductive reasoning capabilities of LLMs is proposed.\n(2) Some new findings on the deductive reasoning capabilities of LLMs are presented.\n(3) The submission is well written and easy to follow.\n\nSoundness:\nThe construction method for the proposed dataset PRONTOQA-OOD is sound, using natural language templates from deduction rules and fictional names for all concepts, where fictional names rather than real names are exploited to prevent LLMs from reusing knowledge from pretraining. The findings are drawn from careful experimental designs and adequately supported with empirical evidence.\n\nPresentation:\nThe submission is well written and organized, with sufficient technical details, easy to follow.\n\nContribution:\nEvaluating the deductive reasoning capabilities of LLMs is important in the field of artificial general intelligence. The submission pushes forward this study by considering more natural deduction rules and drawing some new findings. The findings are valuable to share with the broader NuerIPS community.\n", "weaknesses": "Similar to existing datasets for evaluating the deductive reasoning capabilities of LLMs, the proposed dataset is built on simple and short templates mimicking deduction rules. The sentences used to evaluate LLMs are different from general natural language sentences. It may not reflect the deductive reasoning capabilities of LLMs over natural language sentences.\n\nThere are two minor issues on presentation. One issue is on the definition of the same distribution, which has been referred to in several places including Abstract. It is unknown how to determine whether two examples are obtained from the same distribution or from different distributions. The other issue is on the mentions of abbreviations. An abbreviation should be given its full name when it is mentioned for the first time, however, some abbreviations such as OOD do not come with their full names when they appear for the first time.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and helpful comments! We would greatly appreciate any additional comments or questions during the discussion period.\n\n1. “Similar to existing datasets for evaluating the deductive reasoning capabilities of LLMs, the proposed dataset is built on simple and short templates mimicking deduction rules. The sentences used to evaluate LLMs are different from general natural language sentences. It may not reflect the deductive reasoning capabilities of LLMs over natural language sentences.”\n\nThe synthetic aspect of our dataset and the original PrOntoQA facilitated a much greater degree of programmability and control over many variables that can have a large effect on the model’s reasoning performance. For example, using real-world sentences would confound the model’s ability to memorize and recall information from its pretraining with its ability to reason [1]. This was shown in [2] where the model’s reasoning accuracy was significantly lower when real concept names were replaced with fictional ones. We also note that recent LMs are quite good at understanding realistic examples, as evidenced by recent work on QA and math word problems, and we don’t believe that using examples with more naturalistic language will affect our main observations.\n\n[1] Zhaofeng Wu, Linlu Qiu, Alexis Ross, Ekin Akyürek, Boyuan Chen, Bailin Wang, Najoung Kim, Jacob Andreas, & Yoon Kim (2023). Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Tasks. CoRR, abs/2307.02477. URL https://arxiv.org/abs/2307.02477.\n\n[2] Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. ICLR 2023. URL https://arxiv.org/abs/2210.01240.\n\n\n2. “How is the same distribution defined? That is, how do we determine whether two examples are obtained from the same distribution?” “One issue is on the definition of the same distribution, which has been referred to in several places including Abstract. It is unknown how to determine whether two examples are obtained from the same distribution or from different distributions.”\n\nAn advantage of a synthetic and programmable dataset such as PrOntoQA and PrOntoQA-OOD is that we define the generative process with which we generate the examples, and so we control the ground-truth distribution each example is sampled from, and thus are able to make claims such as whether two examples come from the same or different distributions.\n\n\n3. “An abbreviation should be given its full name when it is mentioned for the first time, however, some abbreviations such as OOD do not come with their full names when they appear for the first time.”\n\nWe thank the reviewer for the suggestion. We will rephrase “OOD” on line 41 to “out-of-demonstration (OOD).” We performed a search for other undefined acronyms and found no others.\n"}, {"review_id": "Pv6lAdPTMn", "reviewer": "Reviewer_bcxG", "summary": "The paper presents a programmable natural language reasoning dataset, PrOntoQA-OOD, specifically designed for testing the out-of-distribution generalization abilities of machine learning models. 4 LLMs, FLAN-T5, LLaMA, GPT-3.5, and PaLM, are tested on this dataset for their ability to generalize to different deduction rules, proof width/depth, and rule compositions.", "questions": "More contextualization with prior work should be good.", "limitations": "More discussion on limitation of this paper's approach for evaluating LLMs reasoning would certainly improve the paper.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The dataset construction is solid and takes into consideration various deduction rules.\n- The experimentation is thorough and insightful.\n- The paper is well written.", "weaknesses": "- (Major) [1] presents a benchmark for theorem proving that is programmable and tests generalization across six dimensions. These dimensions include different deduction rules and proof width/depth, which this paper also discusses. It's a very relevant paper and the failure to discuss it as related work in context seems like a major oversight in scholarship. But this is quite easy to fix.\n- (Minor) Footnote 2 says the deduction rules used in this paper have minor differences with Gentzen's natural deduction, yet there are 3 rules omitted from it. This seems more than minor and I fail to see how natural deduction's completeness or soundness claims can translate to this paper's, without substantiation.\n- (Minor) Figure 3 notes GPT 3.5 as 175B* with an asterisk indicating low confidence in its size. I feel like it's best to omit the 175B size claim altogether if the authors are unsure, to avoid misleading.\n- (Major) For the figures, OOD generalization performances are shown in $\\Delta$ proof accuracies w.r.t. the ID ones. This is hard for me to get an intuitive understanding of the different models used, particularly for FLAN-T5: FLAN-T5 often has trivial (close to 0) proof accuracies for ID and its OOD performance $\\Delta$ being 0 is an indication of triviality instead of good generalization. Showing the absolute OOD proof accuracies will solve this problem.\n- (Minor) For Figure 5 and several others, there's an example of (predicted answer, expected answer), without the question. I had to use my inductive reasoning to figure out exactly what the question was. Please fix this.\n- (Minor) Line 17 seems to cast theorem proving and medical diagnosis as purely deductive reasoning problems. Both tasks require inductive reasoning among other modes. So this claim is not rigorous.\n\nOverall, there are problems but all seem fixable. I'm happy to change my rating if the authors can amend the paper to be more satisfactory.\n\n\n[1] Wu, Y., Jiang, A.Q., Ba, J. and Grosse, R., 2020. Int: An inequality benchmark for evaluating generalization in theorem proving. arXiv preprint arXiv:2007.02924.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and helpful comments! We would greatly appreciate any additional comments or questions during the discussion period.\n\n1. “[1] presents a benchmark for theorem proving that is programmable and tests generalization across six dimensions. These dimensions include different deduction rules and proof width/depth, which this paper also discusses.”\n\nWe thank the reviewer for bringing this work to our attention. The referenced work focuses on symbolic theorem proving but otherwise shares many aspects of the exploration with our work. We will add it to the paragraph beginning on line 65.\n\n[1] Wu, Y., Jiang, A.Q., Ba, J. and Grosse, R., 2020. Int: An inequality benchmark for evaluating generalization in theorem proving. arXiv preprint arXiv:2007.02924.\n\n\n2. “For the figures, OOD generalization performances are shown in proof accuracies w.r.t. the ID ones. This is hard for me to get an intuitive understanding of the different models used, particularly for FLAN-T5: FLAN-T5 often has trivial (close to 0) proof accuracies for ID and its OOD performance being 0 is an indication of triviality instead of good generalization. Showing the absolute OOD proof accuracies will solve this problem.”\n\nThis is a good point. To help readers better interpret the OOD charts in relation to the ID charts, we will add the following sentence to line 168: “We emphasize that the \\Delta proof accuracies in the bottom row of the figure should be interpreted in comparison with the accuracies in the top row (e.g. for some rules, the zero \\Delta accuracy for FLAN-T5 is due to zero absolute accuracy).”\n\n  We tried different ways to plot the OOD accuracy on an absolute scale, showing the change in accuracy vs ID as well as 95% confidence intervals, but we found the resulting charts to be difficult to read. But we will provide OOD charts with absolute proof accuracies in the Appendix.\n\n\n3. “Footnote 2 says the deduction rules used in this paper have minor differences with Gentzen's natural deduction, yet there are 3 rules omitted from it. This seems more than minor and I fail to see how natural deduction's completeness or soundness claims can translate to this paper's, without substantiation.”\n\nThis is a fair point. We clarify that we do not make claims about the soundness and completeness of our modified proof calculus. Rather, we use the soundness and completeness of natural deduction (ND) to motivate its use in our experiments.\n\nBut it is interesting to think about the soundness and completeness of the modified proof calculus. Since the proof by contradiction rule can be proved using negation elimination followed by negation introduction, any proof in our system can be translated into one in ND, which is sound. Therefore, our system is also sound. Our system is not complete, however, since it is missing rules governing truth and falsity. We chose to remove these rules since it is very non-obvious how to express the logical forms “T” or “F => cat(bob)” in natural language. The removed deduction rules also seem very unlikely to appear outside the context of mathematical proofs (and similar contexts). For logical forms without “T” or “F,” our system would be complete with respect to minimal logic, since minimal logic excludes the principle of explosion (i.e. falsity elimination).\n\nWe would be happy to include this discussion in an appendix section if the reviewer finds it helpful.\n\n\n4. “For Figure 5 and several others, there's an example of (predicted answer, expected answer), without the question. I had to use my inductive reasoning to figure out exactly what the question was. Please fix this.”\n\nWe thank the reviewer for this suggestion. We chose not to include the full question due to space constraints: Each question not only includes the query, but all the axioms required to answer the question, as well as all distractors. However, we will modify the figures to include the query (e.g. “Prove: Polly is not a lempus.”) and we will add the full questions to the appendix, with references from each figure.\n\n\n5. “Line 17 seems to cast theorem proving and medical diagnosis as purely deductive reasoning problems. Both tasks require inductive reasoning among other modes. So this claim is not rigorous.”\n\nWe will rephrase the sentence on line 17 as: “In many tasks that require deductive reasoning, such as theorem proving or medical diagnosis, the complexity of proofs can grow without bound via the use of multiple deduction rules and the composition of subproofs.”\n"}]

Author rebuttal:
Thank you to all reviewers for the very helpful feedback and comments! We will address common concerns below and also respond to each reviewer individually.

1. Some reviewers have raised the concern that there is a lack of meaningful insights from the results, especially those that are contradictory with previous findings.

The following is brief summary of the main contributions and insights in our paper:
 - We believe ours is the first comprehensive exploration of LMs’ reasoning ability on a complete set of deduction rules (covering all logical connectives of propositional logic). Our proposed testbed provides a way to evaluate reasoning ability on deduction rules that are not covered by existing natural language benchmarks, and we believe this is valuable to the field.
 - We disentangle “composition” into three types–rule composition, depth, and width–and test LMs’ generalization ability with respect to each type. Previous work often conflated depth generalization with generalization via rule composition [1,2], and we find that LMs are able to generalize compositionally in reasoning in terms of rule composition, while proofs of larger depth are still challenging.
 - LMs are less familiar with proof by cases and proof by contradiction than with other deduction rules. Thus any task that requires reasoning over disjunction and negation would benefit from explicit demonstrations of those deduction rules, as in our experiments. In addition, it provides an explanation for why LMs struggle on tasks involving negation [3,4]. This finding can inform future pretraining or finetuning of models to improve their knowledge of these rules.
 - In some settings, we find LMs perform better on tasks when the in-context examples are not from the same distribution as the test example. We observe via new experiments that longer demonstrations can be harmful. This raises new questions to pursue, to further characterize better distributions for in-context demonstrations and to understand the mechanism of learning from in-context examples.

Some of these points are supported by new experiments which we describe in detail in (1) in the response to Reviewer w9uz. The results of these experiments are shown in new figures in the 1-page supplementary PDF.

[1] Hanlin Zhang, Yi-Fan Zhang, Li Erran Li, & Eric P. Xing (2022). The Impact of Symbolic Representations on In-context Learning for Few-shot Reasoning. CoRR, abs/2212.08686. URL https://arxiv.org/pdf/2212.08686.pdf.

[2] Nicolas Gontier, Siva Reddy, & Christopher Pal (2022). Does Entity Abstraction Help Generative Transformers Reason?. Trans. Mach. Learn. Res., 2022. URL https://arxiv.org/pdf/2201.01787.pdf.

[3] RobustLR: A Diagnostic Benchmark for Evaluating Logical Robustness of Deductive Reasoners, EMNLP 2022. URL https://aclanthology.org/2022.emnlp-main.653.pdf.

[4] Thinh Hung Truong, Timothy Baldwin, Karin Verspoor, & Trevor Cohn (2023). Language Models are not Naysayers: An Analysis of Language Models on Negation Benchmarks. *SEM@ACL 2023. URL https://arxiv.org/abs/2306.08189.


2. Lack of insights/recommendations on how to best use in-context learning for reasoning, given our findings.

We address this concern by adding the following sentences to the Introduction (and the Conclusion, space permitting):

  “Our findings suggest that in-context learning is best applied to reasoning tasks by including examples that cover a diverse set of deduction rules, and keeping the examples simple. The in-context examples should especially contain examples of deduction rules that are less familiar to the model (i.e. proof by cases and proof by contradiction), and distractors should be provided for such examples as the model is more prone to overfitting.”

Meta-review: This paper studies the deductive inference capabilities of LLMs in a way that is more thorough than prior work. Many interesting insights are extracted from the experiments, around compositionality vs. reasoning depth, etc.
Decision: Accept (poster)