LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers
Authors: Theo X. Olausson
Alex Gu
Ben Lipkin
Cedegao E. Zhang
Armando Solar-Lezama
Joshua B. Tenenbaum
Roger P. Levy
Venue: EMNLP 2023 Main (2023)
Keywords: large language models
logical reasoning
neuro-symbolic AI

Abstract: Logical reasoning, i.e., deductively inferring the truth value of a conclusion from a set of premises, is an important task for artificial intelligence with wide potential impacts on science, mathematics, and society. While many prompting-based strategies have been proposed to enable Large Language Models (LLMs) to do such reasoning more effectively, they still appear unsatisfactory, often failing in subtle and unpredictable ways. In this work, we investigate the validity of instead reformulating such tasks as modular neurosymbolic programming, which we call LINC: Logical Inference via Neurosymbolic Computation. In LINC, the LLM acts as a semantic parser, translating premises and conclusions from natural language to expressions in first-order logic. These expressions are then offloaded to an external theorem prover, which symbolically performs deductive inference. Leveraging this approach, we observe significant performance gains on FOLIO and a balanced subset of ProofWriter for three different models in nearly all experimental conditions we evaluate. On ProofWriter, augmenting the comparatively small open-source StarCoder+ (15.5B parameters) with LINC even outperforms GPT-3.5 and GPT-4 with Chain-of-Thought (CoT) prompting by an absolute 38% and 10%, respectively. When used with GPT-4, LINC scores 26% higher than CoT on ProofWriter while performing comparatively on FOLIO. Further analysis reveals that although both methods on average succeed roughly equally often on this dataset, they exhibit distinct and complementary failure modes. We thus provide promising evidence for how logical reasoning over natural language can be tackled through jointly leveraging LLMs alongside symbolic provers. All corresponding code is publicly available.

LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers
Theo X. Olausson* #1
Alex Gu Benjamin Lipkin* #2
Cedegao E. Zhang*
Armando Solar-Lezama'
Joshua B. Tenenbaum 1.2
Roger Levy?
{theoxo, gua, lipkinb, cedzhang) @@mit.
MIT CSAIL "MIT BCS
'Equal contribution.
Abstract
Introduction
Widespread adoption of large language models (LLMs) such as GPT-3 (Brown et al., 2020), GPT- (OpenAI, 2023), and PaLM (Chowdhery et al., 2022) have led to a series of remarkable successes in tasks ranging from text summarization to pro- gram synthesis. Some of these successes have en- couraged the hypothesis that such models are able to flexibly and systematically reason (Huang and Chang, 2022), especially when using prompting strategies that explicitly encourage verbalizing in- termediate reasoning steps before generating the final answer (Nye et al., 2021; Wei et al., 2022: Kojima et al., 2022; Wang et al., 2023b). However, this reasoning ability appears to be unreliable for tasks that require reasoning out of domain (Liang et al., 2022; Saparov et al., 2023), understanding negation (Anil et al., 2022), and following long reasoning chains (Dziri al., 2023). Furthermore, while the standard approach of "scaling up" seems to improve performance across some reasoning do- mains, other domains, e.g., reasoning involving use of Modus Tollens, show no such improvements (McKenzie et al., 2022). These findings suggest that such models may be relying on approximate heuristics based surface-level statistical patterns in reasoning tasks, rather than consistent, gener- alizable representations and strategies (Srivastava et al., 2023; Creswell et al., 2023).
Logical reasoning, i.e., deductively inferring the truth value of conclusion from set of premises, is an important task for artificial in- telligence with wide potential impacts on sci- ence, mathematics, and society. While many prompting boomptig--based strategies have been proposed enable Large Language Models (I..Ms) to do such reasoning more effectively, they still appear unsatisfactory, often failing in subtle and unpredictable ways. this work, we investigate the validity of instead reformulat- ing such tasks as modular neurosymbolic pro- gramming, which we call LINC: Logical In- ference via Neurosymbolic Computation. In LINC, the LLM acts as a semantic parser, trans- lating premises and conclusions from natural language to expressions in first-order logic. These expressions are then offloaded to an ex- ternal theorem prover, which symbolically per- forms deductive inference. Leveraging this ap- proach, we observe significant performance gains on FOLIO and a balanced subset of ProofWriter for three different models in nearly all experimental conditions we evaluate. On ProofWriter, augmenting the comparatively small open-source StarCoder+ (15.5B parame- ters) with LINC even outperforms GPT-3.5 and GPT-4 with mhain-of-Thoughe (CoT) prompt- ing by an absolute 38% and 10%, respec- tively. When used with GPT-4, LINC scores 26% higher than CoT on ProofWriter while performing comparatively on FOLIO. Further analysis reveals that although both methods on average succeed roughly equally often on this dataset, they exhibit distinct and complemen- tary failure modes. We thus provide promising evidence for how logical reasoning over natural language be tackled through jointly lever- aging LLLMs alongside symbolic provers. All corresponding code is publicly !vailable.'
At the same time, the ability to accurately and soundly perform logical reasoning is important for Al and NLP due to its impact on downstream tasks. For example: retrieval become more truthful if it can be verified that their answers logically follow from the retrieved facts; data-driven models capable of logical reasoning may speed up progress across mathematics and the sciences through automated theorem proving and knowledge discovery; and AI tutoring systems which ensure internal logical consistency might
retrieval-augmentte augmented chatbots may
Author order randomized; all reserve the right to list their name first.
https: thw.bb htw.eihh....o.beeeeeeeeeee htt.hbb..cmmbbnlliiiiiiinnc

---

Inpost
Step 1:
Premise:
All rectangles have four sides.
Output
Semantic Parser
Premise: All four-sided things are shapes.
True
Conclusion:
Are all rectangles shapes?
Sample 1
Sample 1
(essanglat)) (oseviaatt)) o/PEESTEE
oDNGLUITTи all Cwwrtagg (O) ( (etspeçc) 3730U88666
Step 2:
True
Step 3:
Logic
K-Maj
Sample 2
Theorem
Sample 2
expecte> all (sccanglats) (osesidaa()) OHBRR otNcUusiie all (metaaglittt) 9 (ssapecc) 4IGMUU8IO
Voting
Prover
Ezror
Sample
<PERATSES (mecanglata) (oorssacchings))) сиEatss 0H4R [twmsiellbigg solaeee)) CHRNESS (socanglats)
True
Sample N
Sampl N
<PAATTES> (recooggatt) (oursieesg)) CHAENTSES
Unknown
0OP9CLUSINM all (onsanglatt) > (ssppp00) GEMMURDD
Figure This figure showcases the essence of our approach. Starting from a problem in natural language, Step 1, the LLM semantic parser samples logic formulas expressing estimates of the semantics. It is possible that some of these might contain errors, e.g., the second example shows a syntax error involving an extra parenthesis. whereas the fourth example highlights semantic error caused by mismatched predicates. In Step these are then each offloaded to an automated theorem prover, filtering out syntax errors, and producing labels for the remaining samples. In Step the remaining candidate outputs are passed through a majority-vote sieve to arrive at the best estimate for single output label.
make for better educational platforms, teaching students to think more clearly and rigorously. The question of how to enable statc-of-the-art LLMs to become more reliable logical reasoners is thus one of great importance, with far-reaching implications.
the solver astray, leading to an incorrect conclusion. As it is not clear whether the task of formalization is more or less difficult than that of end-to-end nat- ural language reasoning, our core interest in this work is compare and contrast neurosym- bolic approach to existing reasoning strategies like Chain-of-Thoughh Our contributions are thus three-fold:
In this work, we analyze LINC: Logical Inference via Neurosymbolic Computation (Fig. 1). In LINC, logical reasoning is tackled through modular, two-step neurosymbolic process. First, the language model converts the natural language premises and desired conclusion into first-order logic (FOL) expressions (Enderton, 2001; Barker- Plummer et al., 201 1). Second, a symbolic FOL theorem prover algorithmically determines the truth value of the conclusion given the formalized premises. In practice, we also incorporate third majority voting step, which is shown to improve performance. LINC is natural extension of recent work augmenting lanugage models with symbolic tools such calculators or interpreters (Schick al., 2023).
First, we propose LINC, a two-stage neurosym- bolic approach for logical reasoning tasks (Sec. 2).
Second, we compare LINC to three baseline LLM strategies (Fig. 2), across three mod- els (StarCodert, GPT-3.5, GPT-4) and two datasets (FOLIO and ProofWriter) (Sec. 4). We find that LINC significantly improves per- formance over every baseline in all experimen- tal conditions except for GPT-4 on FOLIO.
Third, we provide a thorough enror analysis of both LINC and Chain-of-Thought identify- ing three high-level failure modes of cach. We discover that these failure modes are distinct, highlighting the potential for synergy of the two methods (Sec. 5).
LINC has a key advantage: the language model itself no longer needs to perform any deductive rea- soning, which is offloaded to the theorem prover. However, there also clear drawbacks: the for- malization from natural language to first-order logic must perfectly capture all relevant informa- tion contained in the premises, and any loss of in- formation in the formalization procedure may lead
Overall, we present strong evidence for the po- tential of future neurosymbolic logical reasoning systems based on integrating language models and theorem provers.

---

2 LINC: Logical Inference via Neurosymbolic Computation
3 Experiments
In this section, we present experimental setup, the models we use, and the three basclines to which we compare LINC.
Our neurosymbolic approach to end-to-end logical reasoning consists of two stages. In the first stage, the LLM acts semantic parser, translating NL statements into FOL expressions in our supported logic language. In the second stage, these expres- sions are parsed from the text generated by the LLM and then get passed to an automated theo- rem prover; we use Prover9, a nigh-performanee prover widely used in the logic community (Mc- Cune, 2005-2010). The external solver then ex- ecutes symbolic deduction algorithm, which ei- ther returns value from the set (True, False, Uncertain) raises exception due improper FOL syntax (e.g., if the model fails balance parantheses in the formulae).
Datasets: Our experiments use tasks from two existing datasets: FOLIO (Han et al., 2022) and ProofWriter (Tafjord et al., 2021), both of which have been shown to be challenging for off shelff LLMs (Han et al., 2022; Creswell et al., 2023). FO- LIO is an expert-written, open-domain, logically complex and diverse dataset for natural language reasoning with first-order logic. We use its val- idation set for our evaluation. However, of the 204 samples in the validation set, we discover that 22 have errors (details in Appendix C), leaving with 182 examples for evaluation. ProofWriter, meanwhile, is synthetically generated dataset for logical reasoning over natural language. For our evaluation, we use the OWA (Open-World World Assump- tion) portion of ProofWriter, since this setting best matches that of FOLIO. Since we are running a large number of experiments, we randomly select 360 data points to evaluate on in order to reduce costs. We sample these in such way that the sulting data set is balanced across both the number of reasoning steps in the shortest ground truth proof (depth 0-5; 50 samples each) and across the three labels (True/Fal al se/Uncertain, 120 samples each; 20 each per depth).
At its core, the strength of this approach lies in the reformulation of the problem space. End-to- end NL--based reasoning allows for operation over highly flexible expression space, but leaves the LLM with the difficult task of performing explicit deductive inference over expressions in this space. Using LINC, we instead trade off the flexible ex- pression space of NL for syntactically strict logic formulas, allowing us to leverage symbolic algo- rithms with provable guarantces that the deductive chains will be correct with respect to the semantics of the intermediate representation. Making effec- tive use of this reformulation thus requires the logic expressions generated by the LLM to be 1) syntac- tically valid, such that they are accepted by the prover, and 2) semantically valid, such that their evaluation results in the correct conclusion. In our experiments, we mitigate these risks by using a K- way majority voting procedure, which is discussed further in Sec. 3.
In-context learning examples: We hand-pick eight diverse samples from the FOLIO training to be used as few-shot in-context examples. Because ProofWriter does not come with ground truth FOL statements, we use these eight samples for both evaluations. Compared to FOLIO, ques- tions in ProofWriter generally have more premises per question (in our validation sets: an average of 5.3 in FOLIO vs. 18.8 in ProofWriter). Thus, our evaluation on FOLIO is an in-distribution task. whereas ProofWriter requires generalizing out-of- distribution reasoning over considerably larger sets of premises than are given in the prompt.
The significance of this problem space refor- mulation can can beyond the numerical increases in performance observed across our experiments- perhaps best be seen through an in-depth compari- son of how LINC and traditional end-to-end LLM reasoning approaches such as Chain-of-Thoupee (CoT) fail. To foreshadow our latter analysis, we find that compared to CoT, LINC has worse recall but better precision on True/False predictions. We discuss this further in Sec. 5 and highlight that this suggests that LINC, as well as neurosymbolic com- putation more generally, has the potential to reduce LLM overconfidence and ballucination.
Majority voting: K-way majority voting, in which K samples are taken i.i.d. from the model and the mode is used as the final prediction, has previously been shown to improve the performance of prompting-
strategies in logical reasoning tasks (Wang et al., 2023b). We implement such a strategy in our work, with reported accuracies reflecting K-10-way majority voting, unless oth- erwise stated. In the case of ties between two la-

---

rectangles have four sides. ALL siur-sided things shapes. Are all rectangles shapes?
Exarples
Navva
Nx: All pactorgies have toer 1031
Seeaicheed
Since rectangles have tour sides, foup-sided things shapes, rectang be True! AKSWER: Trus </EVALLRTE>
<EVALITTE>
Co2
LINC
Nv:
All lost sind shing aze shapes bodwosta]; toe all rectorgies stares?
P0.: (eocterpiiee (nssiddtts]
tour shings shupos
Rt. (houreseesç)) susre?
Ne5xt: Tex:
F0L: (sectorgie(s) Sentopa(<4)
All dogs mammals. Harry is a dog.
concatenstionn
Harry a mammal?
<EVALUATE>
Figure This figure outlines the string concatenation workflow for each of our conditions. We start with the original problem, provide ICL examples through intermediate markup language, and finally append the problem to evaluate. At this stage, we allow the model to autoregressively sample until producing a stop token.
bels, we arbitrarily select the first of the two to have been generated. We report the effect of K on performance across our conditions and briefly discuss trends in Appendix H.
In the Scratchpad baseline (Nye et al., 2021), the model is asked to first generate FOL expressions corresponding to the premises, and then generate the label. This baseline is thus an ablation of LINC, where we use the LLM instead Prover9 as the logic solver. Finally, in the CoT baseline, we use the standard technique of CoT prompting (Wei et al.. 2022; Kojima et al., 2022; Wang et al., 2023b), where the model is asked to generate step-by-step natural language reasoning to arrive the conclu- sion. The prompts be found in Appendix D.
Models: We use three models pre-trained on both natural language and code: GPT-3.5 (Ouyang et al., 2022), GPT-42 (OpenAI, 2023), and Star- 3oder+3 (Li al., 2023) with decoding temper- ature of T 0.8 for all experiments. We defer model, hyperparameter, and hardware details to Ap- pendix B. We opt for Star Coder+ for three reasons: firstly, unlike the other models we consider, it is a free, open-access model. Secondly, it has dataset search functionality", with which we verify that FOLIO and ProofWriter are not in StarCoder+3s training set, giving further assurance in the validity of our findings. Thirdly, with its 15.5B parameters is likely considerably smaller than GPT-3.5 and GPT-45, allowing us to compare performance at different model scales.
for all approaches
Results & Discussion
Our main results are shown in Figure 3. Each bar represents either LINC or one the three baselines, while each group of bars indicates the language model used (in (StarCoder+, GPT-3. GPT-4)).
We note first that in the FOLIO domain (Figure 3a), StarCoder+-hhe smallest model we experi- ment with benhftenefits the most from LINC, achiev- ing mean accuracy that is 14.2 points higher than the closest controlled baseline (56.0% vs. 41.8% with CoT). We find that Scratchpad, where the intermediate logical formulae are still generated but the call to the symbolic solver is ablated and replaced by the model's 's own prediction, does not appear to benefit performance; for StarCoder+, nei- ther Scr atcchpd nor the Naïve baseline perform better than simply deterministically predicting the most common label ("Uncertain"". For GPT-3.5, the trend is similar, although the gap between LINC and the closest baseline shrinks (62.6% vs. 54.9%
Controlled baselines: We compare LINC to three baselines, which call Naïve, Scratchpad, and Chain-of-Thought (CoT), illustrated in Fig. 2. In the Naïve baseline, the model is given the natural language premises and is asked to di- rectly generate the label (rrueFaalse/Uncertain))
We use gpt-3.5 3.5--355-tae S--trrto-6k---0-- and gpt-4-0613.
Phttps://huue htttp:://huggingface co/bi www/biccoe//taarreeeeceeeeeeeeee gcade//taaccoerppluu
*See https: httpp://hugginggfcee co/ spaces/bigcode in- the-stack and ht httpp::/hugginggf http:/acccccaceceeeeeeeeeeceeeee co/spaces/ bigcode/search.
"Although the exact size of these models has not boen made public, their common predecessor GPT-3 was known to have 175B parameters, see Brown et al. (2020).

---

100%
100%
Nave
Chuin afflhuski
Nave
Chais afbeogh
Senistped
LINIC leanno
Scntccpat
LINE (ourt)
80%
80%
60%
14.%
60%
$5.00
40%
3344
40%
20.5
20%
20%
StarCoder+
G.T-3.5
GPT-4
StarCoder+
GPT-3.5
GPT4
(a) FOLIO.
(b) ProofWriter.
Figure 3: Results of cach model on the FOLIO and ProofWriter datasets. Accuracies are for bootstrapped 10-way majority vote for all models. Error bars are 11 bootstrapped standard deviation. Dotted, black line is the accuracy obtained by always guessing the most common label in the dataset.
average accuracies). For GPT-4, the trend reverses: LINC underperforms COT. However, we perform a McNemar's test (McNemar, 1947) to get the value on this GPT-4 LINC vs. CoT comparison, and we find that the difference is not significant (p = 0.58). Meanwhile, for our balanced subset of ProofWriter,
tion of the necessary proof depth in Figure 4. We note first that StarCoder+'s performance remains flat and close to chance with all three baseline meth- ods (Figure 4a). Mcanwhile, with LINC the perfor- mance remains far above chance, although it drops somewhat as necessary proof depth increases; this performance drop suggests that StarCoder+ strug- gles somewhat with the NL-to-FOL translation task as the problem at hand gets larger. For GPT-3.5, all baselines perform above chance at proof depth (i.e., where the conclusion can immediately be reached from the premises), but then quickly drop back down (Figure 4b). While Shain-of-Thougeee prompting allows the model to complete some depth-1 tasks, even this strategy then performs equivalently chance (within I standard deviation) for higher depths. When augmented with LINC, however, GPT-3.5 able to achieve near-perfect performance across all proof depths, providing evi- dence for the scalability of this approach to longer deductive chains. Finally, for GPT-4 we observe much stronger performance from the baselines; in particular, CoT performs above chance for all proof depths, and all baselines perform well for shallow proofs (Figure 4c). However, even with GPT-4 the performance drops as the necessary proof depth increases with every configuration except for LINC, which performs near or at ceiling through the max- imum proof depth available in the dataset.
significant performance gains across the board (Figure 3b); particularly so for GPT-3.5 and GPT-4, which achieve mean accura- cics 96.4% and 98.3% when paired with LINC, In light of the high accuracies obtained with LINC on ProofWriter, we offer two plausible rea- sons why LINC is particularly favorable on this dataset. Firstly, ProofWriter in-ukiike FOLIO completely synthetically generated, with relatively short sentences, perhaps lending itself particularly well to being formalized in FOL. However, it is noteworthy that the Scratchpad mode does not seem to improve performance over the Naïve base- line, indicating that even if the NL-to-FOL task were particularly casy in this domain, this is not something that the model is itself capable of lever- aging improve its predictions. The second reason might be that the baseline strategies struggle in this distrriiiittittttoon setting, in which the model must generalize to a larger set of premises (with poten- tially longer deductive chains) than those found in the prompt. This distribution shift makes it harder for the model to ignore irrelevant premises in the question and carry out all deductive chains cor- rectly. Mcanwhile, with LINC, the symbolic solver robustly handles irrelevant premises and long de- ductive chains, since the LLM only needs trans- late each sentence into FOL.
Error Analysis
Having established that LINC can improve perfor- mance in many settings, we now move on to our final research question: How do the failure modes of LINC compare to those of in-context reasoning
To test this last explanation further, we plot each model's performance across ProofWriter as func-

---

1.0
1.0
0.8
0.8
0.8
Accuracy
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
Chile Thaggh
0.0
0
2
5
0
2
0
2
4
Proof Depth
Proof Depth
Proof Depth
(a) StarCoder+.
(b) GPT-3.5.
GPT4.
Figure 4: Accuracy per necessary proof depth in ProofWriter. Accuracies reported are for bootstrapped 10-way majority vote, and shaded areas cover #1 bootstrapped standard deviation. Black, dotted lines reflect the expected success rate of guessing random label, which is 1/3 in all subsets per our experiment design.
methods? We focus on comparing GPT-4+COT vs. GNT on FOLIO, since their overall perfor- mance is very similar (75.3% vs. 72.5% average accuracy). We leave an analysis of StarCodert's predictions on FOLIO to Appendix G.
one symbol NaziGermanPoli tiaan,, causing the information that he was independently Nazi, Ger- man, or a politician to be lost. As a result, LINC predicted Uncertain instead of the ground truth label True.
5.1 Qualitative Analysis
Premise: Heinrich Scmidt was politician.
Nazi
German
Qualitatively, we find that LINC and CoT have com- pletely different failure modes. We give a high- level overview and abbreviated examples of each failure mode here, leaving full detailed examples Appendix E.
FOL: NaziGermannoliticionn (HeinrichSchmidt)
Conclusion (Prover9: Uncertain): Heinrich Schmidt was Gernan.
FOL:
German (Heinr icchcchidtt
First, we detail the failure modes for LINC: L1: FOL fails to capture implicit informa- tion not mentioned in the premises. Often, there is obvious information not explicitly listed in the premises that is necessary to explicitly encode in FOL in order to successfully make desired deduc- tion. For example, in the snippet below must encode in FOL the implicit assumption that Harry is a person (Person (Harry)).
L3: FOL contains syntax errors. Across all generations, we find that the FOL expressions sometimes contain syntax errors: 38% for Star- CoderPlus, 24% for GPT-3.5, and 13% for GPT-4.
The most common error is that the same symbol is used with multiple arities. As example, if Summer (July4) and Loves (Alex, Summer) were both present FOL translation, Summer would have multiple arity violation.
Premise I: When a person reads a book, that person gains knowledge.
Next, we detail three failure modes for CoT: C1: CoT concludes something different than it suggests. One common mistake often with the CoT approach is that generates a chain of reasoning indicating uncertainty, but then asserts that the conclusion is false. An example of this is shown below, where GPT-4 suggests there is "no evidence" for the conclusion but then deduces it false.
FOL: x. all y. (Person(x) Reads(x, y) Book(y) Gains(x, Knowledge))
Premise 2: Harry read the book "Walden" by Henry Thoreau.
FOL.: (Harry, Walden)
Conclusion (Prover9: Uncertain): knowledge.
Harry
gains
FOL: CHanry,,rr,, Knowledge)
L2: FOL. fails to capture information explic- itly mentioned in the premises due to the choice of representation. Even when information is plicitly written in the premises, the choice of how the NL is represented in FOL. can lead to lost infor- mation. In the example below, the fact that Hein- rich was a Nazi German politician captured by
(GPT-4 Incorrect CoT); Let's think step by step. We want to evaluate platypus are reptiles. We know from the premises that platypus are mammals and that they have no teeth. The fact that some mammals have teeth does not contradict the fact that platypus, although mammals, do not have teeth. Moreover, the statement about humans having teeth is unrelated to the classification of platypus. There's 's no evidence in the premises that would suggest platypus are reptiles. Therefore, the statement is false.

---

True
True
100
39
1
0
50
1
80
Predictna Label
False
Predictad Label
False
Uncertain
31
0
0
60
Uncertain
3
38
9
60
62
10
10
15
10
Error
Error
20
20
0
True
False
Uncertain
Error
True
False
Uncertain
Error
Reference Label
Reference Label
(a) Confusion matrix for LINC.
(b) Confusion matrix for Chain-of-Thought
100
LINC
Correct
80
108
29
0.8
ma Mucoone Incorrect
CoT
Scratchpad
0.22
0.6
0.21
24
21
Naive
20
0.14
0.52
0.56
0.2
0
Correct
Incerrect
LINC
CoT
Scratebpad
Naive
LINC Outcome
Comparing Chain-of-Thouge
the
consistency of LINC
vs.
(d) Similarity between incorrect predictions of each method,
ie.. (A wrong wrong) (A wrong or wrong).
Figure 5: Analyzing and comparing the mistakes made by GPT-4 on the FOLIO dataset.
C2: CoT makes incorrect logical deductions. While there are many instances where CoT makes incorrect logical deductions, one common deduc- tion mistake is the structure "if is true and > B, then is true". the example shown below, we see this incorrect deduction where A is "Mike has an Fl visa" and B is "Mike needs ap- ply for CPT or OPT if he wants to work in the US" We note that making this type of logical mistake is often called the fallacy of the converse, and that humans are not immune to either.
(GPT-4 Incorrect CоT): Let's think step by step. We want evaluate Mike know Mike is an international student apply CPT if wants to work the US. We know that an international student the US student wants to work in
visa. From the premises, we
needs
visa needs
to apply for CPT or US. So, it clear that Mike has FI visa since fits the criteria. Therefore, the conclusion is true.
C3: CoT fails to find complex paths of reason- ing. We find that with all three models, CoT fails when the path reasoning necessary to make the deduction is complex. Sometimes, CoT has diffi- culty getting started, and other times, it gets stuck in the middle of reasoning chain.
Premise I: International students in US have either an Fl visa or J1 visa.
Premise An international student US with visa needs apply CPT or OPT the student wants work in the US.
5.2 Quantitative Analysis
1. Compared to CoT, LINC has worse recall but better precision on True/False predictions. To see this, we plotted the confusion matrices in Fig- ure 5b (CoT) and Figure/ 5a (LINC). Looking just at the distributions of predicted labels the two methods, we see that CoT predicts 32% True, 27%
Premise 3: Mike international student.
Premise 4: Mike needs to apply for CPT if he wants work in the US.
Conclusion (Ground Truth: Uncertain): Mike has an FI visa.

---

False, and 41% Uncertain, while LINC predicts 24% True, 17% False, and 57% Uncertain (with 2% of predictions throwing an error). Notably, we observe that LINC predicts Uncertain much more frequently than COT (57% vs. 41%). To under- stand why, note that the translation from natural language to FOL is a lossy process: recall that in LI and L2, we saw that the information conveyed through the FOL is sometimes a subset of the infor- mation in the original premises. Removing pieces of crucial information that were on the critical path to deducing True/False may then leave an uncer- tain conclusion. At the same time, while the FOL translations sometimes do not retain all of the infor- mation in the NL, they rarely contain false informa- tion that was not provided in the original premises. Therefore, LINC'S precision when predicting True Fals is very high (93%) compared that of CoT (81 11), but this comes at the cost of lower re- call on True/False predictions (60% for LINC vs. 75% for CoT).
vs. the number of instances where at least one of them is wrong.
Figure 5d shows the pairwise similarity between our four methods, highlighting that the similar- ity between LINC's mispredictions and the other methods' mispredictions (0.14, 0.21, 0.22) is much lower than the similarity between any pair of the in-context reasoning methods (0.52, 0.54, 0.56). These results suggest that for GPT-4 on FOLIO, LINC is the only method we evaluate which signifi- cantly alters the ways in which the model fails to reason.
Related Work
Our work contributes to the wider literature eliciting natural language reasoning capabilities in models. Although we have focused here on comparing neurosymbolic approach to Scratchpad (Nye al., 2021) and Chain-of-Thought prompting (Wei et al., 2022; Kojima et al., 2022; Wang et al., 2023b), many other similar or related techniques have been de- veloped in recent years; these include least-to-most prompting (Zhou et al., 2023), selection-inference (Creswell et al., 2023), backward chaining (Tafjord et al., 2022: Kazemi et al., 2023), and self-taught reasoning (Zelikman et al., 2022). Some of these techniques have been formalized under the lan- guage model cascades framework (Dohan et al.. 2022).
Reasoning in LLMs:
2. LINC and CoT mispredict on different ex- amples. Earlier in Sec. 5. we saw that LINC and CoT exhibit different failure modes, which suggests they should fail on different examples. Indeed, we find that this is the case in our experiments on FO- LIO: Figure 5c shows 2 x 2 confusion matrix which compares whether or not each method's pre- diction was correct. We observe that out of the 24 + 29 + 21 = 74 samples where at least one method makes an incorrect prediction, only 21 are shared. On closer examination of these 21 sam- ples, we find that 16 are ambiguous or incorrect in their specification (details in Appendix E.4), so the methods only agree on 5 well-formed samples. This suggests that LINC and CoT are complementary methods which fail under distinct circumstances. 3. Mispredictions of in-context reasoning baselines are more similar to each other than they are with mispredictions of LINC. As an ex- tension of the previous analysis, we next investigate the correlation between the mispredictions of each pair of methods. To do so, we define a similarity score between two methods A and B follows: Given a dataset D with N rows and ground truth labels { and (B from two methods A
Semantic parsing: The notion of a semantic parser rests long tradition of research (Kamath and Das, 2019) whose aim is to map fragments of natural language into useful, symbolic meaning rep- resentations (Zelle and Mooncy, 1996; Zettlemoyer and Collins, 2005; Berant et al., 2013; Liang et al., 2013; Wong et al., 2023). Unlike earlier works in this tradition, we use language model to generate the semantic parse, which is a method under active investigation in recent years (Shin and Van Durme, 2022; Drozdov et al., 2022; Lu et al., 2022; Wang et al., 2023a).
Neurosymbolic approaches for reasoning: Methods which combine neural networks with sym- bolic techniques have seen broad uptake in domains adjacent to logical reasoning, such as generating outputs consistent with a pre-existing symbolic knowledge base (Marra et al., 2019; Manhaeve et al., 2018; Zhang et al., 2023a) and performing algorithmic reasoning over symbolically grounded inputs (Ebrahimi et al., 2021; Ibarz et al., 2022;
and B, we define
14 B
(Am I R4 B Rd]
words, simp(A, (A, B) measures the number of in- stances where A and B are wrong in identical ways

---

Veličković al., 2022). As for logical reasoning with LLMs in particular, there have been a few dif- ferent proposals for when and how to best combine the LLM with a symbolic component. Zhang et al. (2022) finetune a language model to synthesize po- tential facts paired with likelihoods and then use a handwritten differentiable symbolic reasoner in order to deduce other facts. Weir and Van Durme (2022) relax the solver by instead training neural "entailment" models to decide if and how a given in- ference rule applies at each stage. Concurrently to this work, Logic-LM (Pan et al., 2023) and SATLM (Ye et al., 2023) propose neurosymbolic approaches which have much in common with LINC. However, other than the models and datasets considered, their contributions have a few key differences to ours. First, place particular emphasis establishing an in-depth understanding of the relative benefits and drawbacks of a neurosymbolic approach to reasoning when compared to traditional in-context reasoning strategies like Chain-of-Thougee Sec- ond, Logic-LM employs a self-refinement strat- egy, which has shown promise across code gen- eration and NLP tasks (Zhang et al., 2023b; Chen et al., 2023a; Peng et al., 2023; Madaan et al., 2023; Olausson et al., 2023) but which we do not consider here. Third, SATLM studies arithmetic reasoning in addition to logical reasoning, showcasing the versatility of the neurosymbolic approach. Fourth, and finally, we use an FOL representation that we believe is easier for humans to read and models to learn. We highly encourage interested readers to study these two contemporary works in detail.
the model does not need learn how or where invoke the tool: instead, the tool is predefined and is applied after the generation step finishes. For example, Gao et al. (2023) and Drori et al. (2022) solve mathematical reasoning tasks by generating Python programs and using the Python interpreter as the tool, Liu et al. (2023) approach physical reasoning tasks with physical simulator as the tool, and Wong al. (2023) tackle cognitively- inspired probabilistic reasoning tasks with Church (a probabilistic programming language) as the tool. In the second class, the model must learn to in- voke the tool by itself, meaning that the model must generate explicit API calls to the tool which are then executed when those calls are decoded (Schick et al., 2023; Thoppilan et al., 2022; Yao et al., 2022; Cheng et al., 2023). Our work belongs to the former class, with the task at hand being logical reasoning and the tool available for use be- ing a FOL solver (Prover9). We refer the reader to Mialon et al. (2023) for a more thorough survey of recent work in the tool-usage literature.
7 Conclusion
In this work, we present LINC: Logical Inference via Neurosymbolic Computation, a neurosymbolic approach for scalable logical reasoning with large language models. Our experiments show that LINC leads significant performance gains in nearly ev- ery setting we consider, and that it supports gener- alization to settings where the model has to reason about a much larger set of premises than it is shown in the in-context learning examples. Furthermore, carrying out a quantitative and qualitative analysis of the mistakes made by LINC, we find evidence that it may complement purely in-context reasoning prompting.
The idea of automatically translating natural language into structured sym- bolic representations that programs can reason about has gained popularity in the domain of formal mathematics, leading to autoformalization systems for several theorem provers including Mizar (Wang et al., 2018, 2020), Lean 3 (Azerbayev et al., 2023), and Isabelle (Wu et al., 2022). Outside formal math- ematics, autoformalization has also been applied to translating natural language into system specifica- tion languages such as temporal logic (Hahn et al.. 2022; Cosler et al., 2023; Chen al., 2023b).
Autoformalization:
strategies such Chain-of-Thouse since they differ greatly in the types and frequen- cies of mistakes made. This work thus supports the efficacy of neurosymbolic approaches to natural language reasoning, setting the stage for continued advances in combining large language models and symbolic reasoning engines; we discuss several promising future directions in Appendix A.
Limitations
Tool usage: Our work is heavily inspired by re- cent work on tool usage. The central idea in this augment language models with
Narrow scope of logical reasoning task consid- ered: In this work, we focus exclusively on one as- pect of logical reasoning: predicting the truth value of conclusion given a set of natural language premises. Here, we consider a setting where the
line of research external tools such as calculators, code interpreters and information retrieval systems. We further di- vide these works into two classes. In the first class,

---

premises and conclusion are expressed in relatively short statements, which makes the formalization task tractable. In particular, ProofWriter's natural language statements are synthetically generated, so they can be easily and accurately parsed into FOL. FOLIO reflects a more naturalistic dataset, so we see higher failure rate in LINC's semantic parsing step. However, the formalization task be- comes more difficult if the premises in longer paragraph form, such as question answering or contradiction detection from context passages. This is because the same piece of information can be formalized in a variety of ways, and there a lot of information that must be pragmatically inferred to arrive at the proper conclusion.
dle problems requiring higher-order logics (Miller and Nadathur, 1986; Higginbotham, 1998). Also, in many settings is desirable to work with non- classical logics (Priest, 2008; Burgess, 2009). Al- ternative theorem provers would be needed for such problems. A method like LINC can be naturally ex- tended to those settings, but exactly how well it works there requires further investigations.
Computational costs: Implementing our ap- proach with both GPT models and the StarCoder+ model requires non-trivial resources. The former requires reliance on costly API requests and the latter dedicated GPUs for inference. Especially as we use majority voting, many generations must be made for each query, increasing the computational requirements.
Generalizability of qualitative evaluation: While we find that LINC and CoT produce com- plementary mistakes for natural language rea- soning task, it is unelear if this result also holds true in similar scenarios, such as the ones considered in PAL (Gao et al., 2023), Logic-LM, and SATLM. This is due to the difference in intermediate lan- guage and overall logical reasoning task. However, we hypothesize that it will and encourage future investigation in this direction.
Acknowledgements
T.X. Olausson is supported by the Defense Ad- vanced Research Projects Agency (DARPA) under the ASKEM program, award HR001 12220042. A. Gu is supported by the National Science Founda- tion (NSF) Graduate Research Fellowship under Grant No. 2141064. B. Lipkin and C.E. Zhang are supported by MIT Presidential Fellowships. A. Solar- is supported by the National Science Foundation (NSF) and Intel Corporation through NSF Grant CCF:2217064 J.B. Tenenbaum is sup- ported by AFOSR Grant #EA9550-22-1-0388 and the MIT-IBM Watson AI Lab. R.P. Levy sup- ported by a grant from the Simons Foundation to the Simons Center for the Social Brain at MIT.
More sophisticated reasoning techniques: Re- cent work has proposed more sophisticated tech- niques beyond Slain-of-thought such tree of thoughts (Yao et al., 2023), program of thoughts, (Chen et al., 2022), or using retrieval in chain-of- thought prompting (Yasunaga et al., 2023). These have potential to improve and eliminate some of the failure modes of the traditional CoT method. In addition, ideas such as self-repair may also serve to improve these failure modes. It remains future work to do more thorough investigation of the efficacy of these techniques, though there is also preliminary evidence that they still lack reasoning capabilities (Huang et al., 2023).
We thank our anonymous reviewers for their in- sightful feedback and recommendations, We thank the members of the Computer Aided Programming. Computational Psycholinguisties, and Computa- tional Cognitive Science groups for constructive commentary at various stages of this project. We thank Yoon Kim for helpful suggestions and com- ments on pieces of the initial project proposal. In addition, we thank Zhaofeng Wu and Simeng Han for discussions regarding the FOLIO dataset.
Scalability: is unclear how well LINC will perform as the number of premises scales. First, one mistake formalization can lead to an incor- rect deduction, and more premises lead to higher probability of errors. Second, in the deduction stage, while many fast algorithms (e.g., forward- and backward-chaining) exist for logical deduction, the general problem is still hard. Therefore, the theorem prover may take a long time in practice.
References
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowyez, Vedant Misra. Vinay Ramasesh, Am- brose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. 2022. Exploring length generalization in large language models. In Advances in Newral Information P Processing Systems, volume 35, pages 18546-38556, (Cited on pg. 1)
Other logies beyond first-order logic: In this work, we exclusively focus on first-order logic. However, FOL is not expressive enough to han-

---

Zhangir Azerbayev, Bartosz Piotrowski, Hailey Schoelkopf, Edward W Ayers, Dragomir Radev, and Jeremy Avigad. 2023. ProofNet: Autoformalizing and formally proving undergraduate-levw mathemat- ics. arXiv preprint 4xXiv:2302.12453 (Cited on pg. 9)
language modeling with pathways. arXiv preprint arXiv:2204.02331. (Cited on pg. 1)
Matthias Coster. Christopher Hahn, Daniel Men- doza, Frederik Schmitt, and Caroline Trippel. 2023, n12spec: Interactively translating unstructured natu- ral language to temporal logics with large language models. In Computer Aided Verification, pages 383- 396, Cham. Springer Nature Switzerland. (Cited pg. 9)
David Barker-Plummee Jon Barwise, and John Etchemendy. 201 I. Language, proof, and logic, 2 edition. Center for the Study of Language and Infor- mation. (Cited on pg. 2)
Antonia Creswell, Murray Shanahan, and Irina Higgins. 2023. -nneereon-iifeeeeee:: Exploiting large language models for interpretable logical reasoning. In The Eleventh International Conference on Learning Rep- resentations. (Cited on pg. 1,3,8)
Mohammad Bavarian, Heewoo Jun, Nikolas Tezak, John Schulman, Christine McL.aavy,, Jerry Tworek, and Mark Chen. 2022. Efficient training lan- guage models to fill in the middle. arXiv preprint arXiv:2207. 14255. (Cited on pg. 15)
Jonathan Berant, Andrew Chou, Roy Frostig, and Perey Liang. 2013. Semantic parsing on Freebase from question-answer pairs. In Proceedings of the 2013 Conference on Empirical Methods in Natural Lan- guage Processing, pages 1533-1544, Seattle, Wash- ington, USA. Association for Computational Linguis- tics. (Cited pg. 8)
David Dohan, Winnie Xu, Aitor Lewkowycz, Ja- cob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif Saurous, Jascha Sohl-Dickstein. et al. 2022. Language model cascades. arXiv preprint arXii: on pg. 8)
(Cited
Iddo Drori, Sarah Zhang, Reece Shuttleworth, Leonard Tang, Albert Lu, Elizabeth Kc, Kevin Liu, Linda Chen, Sunny Tran, Newman Cheng, et al. 2022. A neural network solves, explains, and generates uni- versity math problems hy program synthesis and few- shot learning human level. Proceedings of the Na- tional Academy of Sciences, 119(32):e212343311 (Cited on pg. 9)
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. In Advances neural information process- ing systems, volume 33, pages 1877-1901. (Cited on pg. 1, 4)
John P Burgess. 2009, Philosophical logic. Princeton University Press. (Cited on pg. 10)
Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. 2022. Compositional semantic parsing with large language models. arXiv preprint arXiv: 15003. (Cited pg. 8)
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. 2022. Program of thoughts prompting: Disentangling computation from reason- ing for numerical reasoning tasks. arXiv preprint arXiv:22I1.12588 (Cited on pg. 10)
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin. Peter West, Chan- dra Bhagavatula, Ronan Le Bras, Jena D Hwang. et al. 2023. Faith and fate: Limits of transformers on compositionality. arXiv preprint arXiv: 230..8654. (Cited on pg. 1)
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2023a. Teaching large language mod- els selffdebug. arXiv preprint arX1v22304.05/28. (Cited on pg. 9)
Yongchao Chen, Rujul Gandhi, Yang Zhang, and Chuchu Fan. 2023b. NL2TL: Transforming natu- ral languages to temporal logics using large language models. arXiv preprint arXiv:2305.0776. (Cited on pg. 9)
Monireh Ebrahimi, Aaron Eberhart, Federico Bianchi, and Pascal Hitzler. 2021. Towards bridging the neuro- symbolic gap: Deep deductive reasoners. Applied Intelligence, 51 1632666338 (Cited on pg. 8)
Herbert Enderton. 2001. A mathematical introduction to logic. Elsevier. (Cited on pg. 2)
Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni. Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zeulemoyer, Noah A. Smith, and Tao Yu. 2023. Binding language models in symbolic languages. In The Eleventh In- ternational Conference on Learning Representations. (Cited on pg. 9)
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang. Jamie Callan, and Gra- ham Neubig. 2023. PAL:: Program-aided language models. In International Conference on Machine Learning, pages 10764-10799, PMLR. (Cited pg. 9, 10)
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gauray Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sebastian Gehrmann, et al. 2022. Palm: Scaling
Herbert P Grice. 1975. Logic and conversation. Speech acts, pages 41 41-58, Brill, (Cited on pg. 15)

---

Christopher Hahn, Frederik Schmitt, Julia Tillman, Niklas Metzger, Julian Siber, and Bernd Finkbeiner. 2022. Formal specifications from natural language. arXiv preprint arXiv:2206.01962 (Cited on pg. 9)
Perey Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Ku- mar, et al. 2022. Holistic evaluation of language models. arXiv preprint 22X1v:221..01110. (Cited on Pg. 1)
Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Eka- terina Zubova, Yujie Qiao, Matthew Burtell, et al. 2022. Folio: Natural language reasoning with first- order logic. arXiv preprint arXiv:2209 00840. (Cited on pg. 3)
Percy Liang, Michael I Jordan, and Dan Klein. 2013. Learning dependency-basee compositional seman- tics. Computational Linguistics, 39(2):389-446 (Cited on pg. 8)
Ruibo Liu, Jason Wei, Shixiang Shane Gu, Ye-Yen Wu, Soroush Vosoughi, Claire Cui, Denny Zhou, and An- drew M. Dai. 2023. Mind's eye: Grounded language model reasoning through simulation. In The Eleventh International Conference on Learning Representa- rions. (Cited on pg. 9)
James Higginbotham. 1998. On higher-order logic and natural language. In Proceedings of the British Academy, volume 95, pages 1-27. (Cited on pg. 10)
Jie Huang and Kevin Chen-Chuan Chang. 2022. To- wards reasoning in large language models: A survey. arXiv preprint arXiv:2212. 10403. (Cited on pg.
Xuantao Lu, Jingping Liu, Zhouhong Gu, Hanwen Tong, Chenhao Xie, Junyang Huang, Yanghua Xiao, and Wenguang Wang. 2022. Parsing natural language into propositional and first-order logic with dual re- inforcement learning. In Proceedings of the 29th International Conference Computational Linguis- tics, pages 5419-543) (Cited on pg. 8)
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xiny- ing Song, and Denny Zhou. 2023. Large language models cannot self-correct reasoning yet. arXiv preprint 2300023300 (Cited on pg. 10)
Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyr- iacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvit- skyi, Yulia Rubanova, et al. 2022. A generalist neural algorithmic learner. In Learning on Graphs Confer- ence, pages 2 1. PMLR. (Cited on pg. 8)
Aman Madaan. Niket Tandon. Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. 2023. Self-refine: Iterative refinement with self- feedback. arXiv preprint arXiv:2303.176. (Cited on pg. 9)
Robin Manhaeve, Sebastijan Dumancic, Angelika Kim- mig. Thomas Demeester, and Lue De Raedt. 2018. DeepProbL.og: Neural probabilistic logic program- ming. In Advances neural information processing systems, volume 31. (Cited on pg. 8)
Aishwarya Kamath and Rajarshi Das. 2019. A survey on semantic parsing. In Automated Knowledge Base Construction (AKBC). (Cited on pg. 8)
Mehran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, and Deepak Ramachandran. 2023. LAMBADA: Backward chaining for automated reasoning in nat- ural language. In Proceedings of the 61st Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 6547-6568, Toronto, Canada. Association for Computational Lin- guistics. (Cited on pg. 8)
Giuseppe Marra. Francesco Giannini, Michelangelo Diligenti, and Marco Gori. 2019. Integrating learn- ing and reasoning with deep logic models. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 517-532. Springer. (Cited on pg. 8)
W. McCune. 2005-2010. http://wwww.s.umm.ce. mccune/prover991 (Cited on 3g.
Prover9 and mace4,
Denis Kocetkov, Raymond Li, Loubna Ben Allal, Jia Li, Chenghao Mou, Carlos Muñoz Ferrandis, Yacine Jer- nite, Margaret Mitchell, Sean Hughes, Thomas Wolf. al. 2022. The Stack: 3 TB of permissively licensed source code. arXiv preprint arXiv:221 15533. (Cited on pg. 15)
lan McKenzie, Alexander Lyzhov, Alicia Parrish. Ameya Prabhu, Aaron Mueller, Najoung Kim, Sam Bowman, and Ethan Perez. 2022. The inverse scaling prize. (Cited on pg. 1)
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yu- taka Matsuo, and Yusuke Iwasawa. 2022. Large lan- guage models are zero-shot reasoners. In Advances in neural information processing systems, volume 35, pages 22 229912 (Cited on pg. 1, 4, 8)
Quinn McNemar. 1947. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika, 12(2):153 157. (Cited on pg. 5)
Grégoire Mialon, Roberto Dessi, Maria Lomeli, Christo- foros Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi- Yu, Asli Celikyilmaz, et al. 2023. Augmented language models: a survey. arXiv preprint 472.0:2302.07842. (Cited on pg. 9)
Raymond Li, Loubna Ben Allal, Yangtian Zi Niklas Muennighoff, Denis Kacetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, et al. 2023. Starcoder: may the source be with you! arXiv preprint 23055 06161. (Cited on pg. 4, 15)

---

Dale A. Miller and Gopalan Nadathur. 1986. Some uses of digher-order logic in computational linguistics. In Proceedings of the 24th Annual Meeting Associ- ation for Computational Linguisties, page 247-256, New York, USA. Association for Computational Lin- guistics. (Cited on pg. 10)
Abulhair Saparov, Richard Yuanzhe Pang, Vishakh Padmakumar, Nitish Joshi, Seyed Mehran Kazemi, Najoung Kim, and He He. 2023. Testing the general deductive reasoning capacity of large lan- guage models using ood examples. arXiv preprint 2rXiv:2305. 2.05.2230.152000 15269. (Cited on pg. 1)
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. 2021. Show your work: Scratch- pads for intermediate computation with language models. arXiv preprint 12X00:211..00114 (Cited on pg. 1, 4, 8)
Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023. Toolformer: Language models can teach themselves to use tools. arXiv preprint 2302.:::30004400 (Cited on pg. 2, 9)
Noam Shazeer. 2019. Fast transformer decoding: One write-head is all you need. arXiv preprint arXiv:1911.02150 (Cited on pg. 15)
Theo X Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar- Lezama. 2023. Is self-repair silver bullet for code genera- tion? arXiv preprint arXiv:2306.09896 (Cited on pg. 9)
Richard Shin and Benjamin Van Durme, 2022. Few- shot semantic parsing with language models trained on code. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistiex: Human Lunguage Tech- nologies, pages 5417-5425, Seattle, United States. Association for Computational Linguistics. (Cited on pg. 8)
OpenAL. 2023. GPT-4 technical report. (Cited on pg. 1, 4, 15)
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishknn. Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022. Training language models to follow instruc- tions with human feedback. In Advances in Nearal Information Processing Systems, volume 35, pages (Cited on pg. 4. 15)
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2023. Beyond the imitation game: Quantifying and extrapolating the capabili- ties of language models. Transactions on Machine Learning Research. (Cited on pg. 1)
Liangming Pan. Alon Albalak, Xinyi Wang. and William Yang Wang. 2023. Logic-Im: Empower- ing large language models with symbolic solvers for faithful logical reasoning. arXiv preprint ar05v:2305. 12295. (Cited on pg. 9)
Robert Stainaker. 2002. Common ground. Linguistics and philosophy, 2515/6) (Cited on pg. 15)
Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. 2021. ProofWriter: Generating implications, proof',, and abductive statements over natural language. In Find- ings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 3621-3634, Online. Asso- ciation for Computational Linguistics. (Cited on pg. 3)
Guilherme Penedo, Quentin Malartic, Daniel Hesslow, Ruxandra Cojocaru, Alessandro Cappelli, Hamza Alobeidli, Baptiste Pannier, lbbtesam Almazrouei, and Julien Launay. 2023. The Ref dataset for Falcon LLM: outperforming curated corpora with web data, and web data only. arXiv preprint vrXiv:2306.01116 (Cited on pg. 15)
Oyvind Tafjord, Bhavana Dalvi Mishra, and Peter Clark. 2022. Entailer: Answering questions with faithful and truthful chains of reasoning. In Proceedings of the 2022 Conference on Empirical Methods in Nat- urul Lunguage Processing, pages 2078-2093 Abu Dhabi, United Arab Emirates. Association for Com- putational Linguistics. (Cited on pg. 8)
Baolin Peng. Michel Galley, Pengcheng He, Hao Cheng, Yujia Xie, Yu Hu, Qiuyuan Huang, Lars Liden, Zhou Yu, Weizhu Chen, and Jianfeng Gao. 2023. Check your facts and try again: Improving large language models with external knowledge and automated feed- back. arXiv preprint (..ii:2302.228.... (Cited on pg.9. 9)
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Tzz Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, al. 2022. LaMDA: Language models for dialog applica- tions. arXiv preprint 2rXiv:2201.082.9. (Cited on pg. 9)
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gul- wani. 2022. Synchromesh: Reliable code generation from pre-trained language models. In International Conference Learning Representations. (Cited on pg. 15)
Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Da- shevskiy, Raia Hadsell, and Charles Blundell. 2022. The clrs algorithmic reasoning benchmark. In In- ternational Conference on Machine Learning, pages 22084-22102. PMLR. (Cited on pg. 9)
Graham Priest. 2008. An introduction to ron-classical logic: From if to is. Cambridge University Press. (Cited on pg. 10)

---

Bailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao, Rif Saurous, and Yoon Kim. 2023a. Grammar prompting for domain-specific language generation with large language models. arXiv preprint arXiv:2305. 19234. (Cited on pg. 8)
Michihiro Yasunaga, Xinyun Chen, Yujia Li, Panupong Pasupat, Jure Leskovec, Percy Liang, Ed H Chi, and Denny Zhou. 2023. Large language models as ana- logical reasoners. arXiv preprint arXi::2310.0714. (Cited on pg. 10)
Qingxiang Wang, Chad Brown, Cezary Kaliszyk, and Josef Urban. 2020. Exploration of neural machine translation in autofornalization of mathematics in mizar. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, pages 85-98. (Cited on pg. 9)
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. 2023. Satisfiability-addee language models using declara- tive prompting. arXiv preprint Xivv22305009656 (Cited on pg. 9)
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Good- man. 2022. STaR: Bootstrapping reasoning with reasoning. In Advances in Neural Information Pro- cessing Systems, volume 35, pages 15476-15488. (Cited on pg. 8)
Qingxiang Wang, Cezary Kaliszyk, and Josef Urban. 2018. First experiments with neural translation of informal to formal mathematics. In Intelligent Com- puter Mathematics: 17th International Conference, CICM 2018, Hagenberg. Austria, August 13-17, 2018, Proceedings 11. pages 255-270. Springer. (Cited on pg. 9)
John M Zelle and Raymond J Mooney. 1996. Learn- ing to parse database queries using inductive logic programming. In Proceedings of the National Con- ference on Artificial Intelligence, pages 1050-1055. (Cited on pg. 8)
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery. and Denny Zhou. 2023b. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations. (Cited on pg. 1, 4, 8, 23)
Luke Zettlemoyer and Michael Collins. 2005. Learn- ing to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, UAI'05, page 658 666, Arlington, Virginia, USA. AUAI Press. (Cited on pg. 8)
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. 2022. Chain-of-though prompting elicits rea- soning in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 24824-24837 (Cited on pg. 1, 4,8) 8)
Hanlin Zhang, Ziyang Li, Jiani Huang, Mayur Naik, and Eric Xing. 2022. Improved logical reasoning of language madels via differentiable symbolic pro- gramming. First Workshop on Pre-training: Per- spectives, Pitfalls, and Paths Forward at 1CML 2022. (Cited pg. 9)
Nathaniel Weir and Benjamin Van Durme. 2022. Dy- namic generation of interpretable inference rules in a neuro-symbolic expert system. arXiv preprint arXiv:2209.07662. (Cited on pg. 9)
Honghua Zhang, Meihua Dang. Nanyun Peng, and Guy Van den Broeck. 2023a. Tractable control for autore- gressive language generation. In International Con- ference on Machine Learning, pages 40932-40945. PMLR. (Cited on pg. 8)
Lionel Wong. Gabriel Grand, Alexander K Lew, Noah D Goodman, Vikash K Mansinghka, Jacob Andreas, and Joshua B Tenenbaum. 2023. From word mod- els to world models: Translating from natural lan- guage to the probabilistic language of thought. arXiv preprint 2r36. 12672. (Cited on pg. 8, 9)
Kechi Zhang, Zhuo Li, Jia Li, Ge Li, and Zhi Jin. 2023b. Self-edit: Fault-aware code editor for code generation. In Proceedings of the 61st Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pages 769-787, Toronto. Canada. Association for Computational Linguistics. (Cited on pg. 9)
Yuhuai Wu, Albert Qiaochu Jiang, Wenda Li. Markus Rabe, Charles Staats, Mateja Jamnik, and Christian Szegedy. 2022. Autoformalization with large lan- guage models. In Advances in Neural Information Processing Systems, volume 35, pages 32353-32368. (Cited on pg. 9)
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang. Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed H Chi. 2023. Least-to- most prompting enables com- plex reasoning in large language models. In The Eleventh International Conference on Learning Rep- resentations. (Cited on pg. 8)
Shunyu Yao. Dian Yu. Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao. and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305.1000 (Cited on pg. 10)
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.0302 (Cited on pg. 9)

---

A Future Directions
date for the previously mentioned larger number of premises involved in typical question). For the StarCoder+ model, we allow generation up until the 8192 context window length, since this model is run locally. In either case, decoding is halted early whenever the stop token < </EVALUATE> is pro- duced. All local experiments were executed on a cluster equipped with NVIDIA A100 GPUs. GPT Models: We use the gpt-3.5-turbo-I1 16k- 0613 and gpt-4-0613 checkpoints of the GPT-3.5 (Ouyang et al., 2022) and GPT-4 (OpenAI, 2023) models, respectively, invoking both models via the OpenAl API.
Of the error types we catalog in our analysis of LINC, the key opportunity for improvement is more clegant handling of naturalistic language use. While the errors observed with CoT result from faulty deductive inferences, in the case of LINC, all errors have been localized to the semantic pars- ing procedure. This process flows primarily unim- peded in the evaluation of the synthetic ProofWriter dataset, yet leaves room for improvement with the naturalistic FOLIO. In follow-up work, we hope to deeply explore naturalistic evaluation settings, when data get the most messy is also where im- provements become the most valuable. Here, propose three strategies for further improvement on naturalistic settings.
StarCoder+: StarCoder+ (15.5B) is a version of StarCoderBase (Li et al., 2023) which has been finetuned on 600B tokens from combination of (1) Falcon RefinedWeb (Penedo et al., 2023) (filtered version of CommonCrawl), (2) The Stack v1.2 (Ko- cetkov et al., 2022), and (3) Wikipedia dataset. Its base model, StarCoderBase, an open-access model with a GPT-2 architecture using query attention (Shazeer, 2019) and fil-ilethe-mmddle ob- jective (Bavarian et al., 2022). StarCoderBass has 8192 context window and is trained on 17 code tokens of permissively licensed text from GitHub across 80 programming languages (Li et al., 2023). We use StarCoder+ instead of StarCoderBase be- cause it finetuned on natural language, which should improve the performance on our task. We run StarCoder+ with 6616 precision to reduce its memory footprint.
First, in naturalistic communication, "obvious" information often left out of explicit productions, left to be inferred in the "common ground" of the communicative act (Grice, 1975; Stalnaker, 2002). Implicit premise rediscovery through controlled exploration on the logical neighborhood of the ex- isting explicit premises promises to be a powerful strategy for improving performance in underspeci- fied settings.
Second, while a number of samples are lost to syntax errors, recent work has proposed restricting the sampling space of an LLM to that which is consistent with term expansions in a context-free- grammar (CFG) (Poesia et al., 2022). Doing so in this setting would climinate all syntax errors.
Third, sometimes, the translation process to FOL is lossy, throwing away valuable information present in the original sentence. We propose im- proving the faithfulness of FOL translations by ask- ing the LLM to translate the FOL back to natural language and comparing with the original. Forward translations that rank highly when back-translate translated would be those which have effectively captured the intricacies of a particular sentence's 's semantics. Overall, believe that shifting to evalua- tions on more naturalistic datasets, and incorpo- rating strategies such as those presented here, will help pave the path forward for ncurosymbolic ap- proaches to formal reasoning.
C FOLIO Dataset Preprocessing
We use the publicly available FOLIO dataset on https://gi ttt.. com./all-LLLLLVVOOL... We choose representative samples from the training split of the dataset to be our few-shot examples and use the validation split of the dataset in our eval- uation. The testing split is not publicly available.
The original dataset has 204 validation examples. However, we discovered that there are errors in 22 of the samples. We remove these samples for our evaluation and use the remaining 182 examples. The errors as follows:
In 4 samples, one more of the ground truth FOL expressions have unbalanced parenthe- ses (samples 3, 109, 110, 111).
B Model Details and Parameters
We use a decoding temperature T 0.8 for all models. For GPT-3. and GPT-4, we limit the max- imum number of tokens to generate to 1024 for FOLIO and 4096 for ProofWriter (to accommo-
In 8 samples, the label obtained by executing the ground-truth FOL expressions does not

---

match the provided ground truth label. We double-checked this, first by executing the FOL expressions through Prover9 and second by checking it manually. (samples 6, 28, 30, 48, 113, 115, 139, 140).
main/data/vo, e/folio-train, jsonl. We do not optimize for the choice of few-shot examples, and this is the only set of examples we evaluated with, so it is likely that there exist better choices for few-shot examples that would lead to improved performance across the board.
In 10 samples, the number of premises does not match the number of FOL. expressions (samples 10, 11, 12, 88, 106, 107, 108, 174, 175, 176).
D.1 FOLIO, 1-shot (baseline)
The following is first-order logic (FOL)
+ problem.
The problem is determine whether the
The sample numbers above refer the line index in the validation file located https://ggithub..cm//llllltt httpa//.....mall-LLLooooLO//lll. main/data/vO. hat.aa/ta.....llloolllaaaatoonno
+ canclusion fallows from the premises.
The premises given in the form of set of
< first-order logic sentences.
The conclusion is given in the form of single
<> first-order logic sentence.
The task evaluate the conclusion as 'True',
( 'False', 'Uncertain' given the premises.
D FOLIO Few-Shot Prompts
The methodologies we investigate do not re- quire any finetuning on domain-specific data. In- stead, we use in-context learning (ICL) with pre- trained models. We prompt the model with set of instructions and 1-8 ICL examples, which adhere signed to scaffold generations and ease post- processing. In particular, we begin each ICL exam- ple with each of the NL premises wrapped in an HTML-style tag <PREMISES>... </PREMISES> followed by the NL conclusion wrapped in <CONCLUSION>. </CONCLUSION>. The requi- site evaluation steps for each evaluation paradigm are then outlined in subsequent section wrapped <EVALUATE>, </EVALUATE>, Following the in- clusion of ICL examples, test example is added, with the <PREMISES> and <CONCLUSION> sections.
<PREMISES>
dispensable things are environment-friemdly. woodware dispensable.
paper woodware.
No good things are bad.
enviromment-frienclly things are good. worksheet either paper or is environment- 4 friendly.
structured text format de-
</PREMISES>
<CONCLUSION>
A worksheet is not dispensable.
</CONCLUSION>
<EVALUATE>
Uncertain
</EVALUATE>
<PREMISES>
premises for sample here, one premise per + 1ine
</PREMISES>
<CONCLUSION>
c.ccolllsiion for sample here
Then, the <EVALUATE> tag is opened, and the LM is allowed to proceed with causal generation un- til the </EVALUATE> tag is generated. Upon gen- eration of this stop token, the <EVALUATE> block is segmented for post-processing according to the method being evaluated ((naīve, scratchpad, chain-of-thought, neuro-symbolic)).
</CONCLUSION>
<EVALUAT>>
Listing I: todo
D.2 FOLIO, 1-shot (scratchpad)
The following is first-order logic (FOL)
For the few-shot examples, we use samples from
<> problem.
The problem
determine whether the <> conclusion follows from the premises.
the publicly available FOLIO training set. We select a set of diverse samples that are balanced across labels. Since the FOLIO training set does not come with FOL. expressions for the conclusions manually add
The premises are given the form a set of
<> first-order logic sentences.
The conclusion is given in the form of single 4 first-order logic sentence. The task is to translate each of the premises 4 and conclusions into FOL expressions, and o then to evaluate the conclusion as 'True
chain of thought prompts, both for each sample. For the k-shot setting (k:4),, we use the first k samples from the following list of sample indices: 126, 24, 61, 276, 149, 262, 264, 684. Here, sample i refers to the ith line in https:/ //gi thub. http://c.../aa........oo/.//..1.
4 'False', or 'Uncertain' given the G premises.
<RRMISSSS>

---

All dispensable things are enviromment-friendly.
<EVALUATE>
All woodware is dispensable.
Let's think step by step. want evaluate
All paper is woodware.
a worksheet is not dispensable. From premise 6, we know
good things are bad.
worksheet either paper or is enviromment-frienly paper, then from premise 3, 4 worksheet is woodware, and from premise
All environimett-friendly things are good. worksheet is either paper or environment-
4 friendly.
</PREMISES>
7 2, a worksheet is dispensable. If it is environment friendly, we know it is good 4 from premise 5, but we know nothing about whether it is dispensable. Therefore, we don't 't know if a worksheet is dispensible or not, so the statement is uncertain. ANSWER: Uncertain
<CONCLUSIGN>
A worksheet is not dispensable.
</CONCLUSION>
<EVALUATE>
TEXT: All dispensable things are environment-
- friendly.
FOL: all x. (0ispensable(x) ->
</EVALUATE>
+ Envi EnvirromenntFreenllyyy
TEXT: All woodware is spensable
<PREMISES>
FOL: all x. (Noodware(x) -> Dispensable(x)
-premises for sample here, one premise per 4 line
TEXT: All paper is woodware.
FOL: all (Paper(x) -> Woodware(x))
</PREMISES>
TEXT: No good things are bad.
<CONCLUSION>
FOL: all (x) -> -x))
...cocllusion for sample here
TEXT: All enviromment-friendly things are good.
</CONCLUSION>
FOL: all (ENvirommentFriendllyy)) -> Good(x))
<EVALUATE>
TEXT: A warksheet is either paper is frinirollynt--iienlll... FOL: ((Paper (Horksheet) *EnvirommentFriendlyy Worksheet)) (-Paper (Workshet)))) & www.rrommntFriendl. (Worksheet))) TEXT: A worksheet is not dispensable.
D.4 FOLIO, 1-shot (neurosymbolic)
The following is first-order logic (FOL)
< problem.
FOL:
-Dispensable (Worksheet)
The problem is to determine whether the
ANSWER: Uncertain
+ canclusion follows from the premises.
</EVALUATE>
The premises are given in the form of a set of + -first-order logic sentences.
<PREMISES>
The conclusion is given in the form of single + firrtt-order logic sentence.
.premises sample here, premise se per line
The task is to translate each of the premises ( and conclusions into FOL expressions, so ( that the expressions can be evaluated by
</PREMISES>
<CONCLUSION>
... conclussion for sample here
S theorem solver to determine whether the
</CONCLUSION>
4 conclusion follows from the premises.
<EVALUATE>
Expressions should be adhere to the format of
+ the Python NLTK package logic module.
D.3 FOLIO, 1-shot (chain of thought)
<PREMISES>
The following first-order logic (FOL)
All dispensable things are enviromment-frieedlyy
problem.
All woodware is dispensable.
The problem is to determine whether the conclusion follows from the premises. The premises are given in the form of first-order logic sentences.
All paper woodware.
No good things bad.
All environment-friendlly things good.
worksheet either paper environment-
The
conclusion is given in the form a single first-order logic sentence. The task to translate each the premises conclusions into FOL expressions,
4 friendly.
</PREMISES>
<CONCLUSION>
worksheet not dispensable.
</CONCLUSION>
<EVALUATE>
<PREMISES>
TEXT: All dispensable things are environment-
All dispensable things are enviromment-friendly.
< friendly.
All woodware is dispensable.
FOL: all x. (Dispensable ->
All paper is woodware.
+ EnvirromeentFriendlyyyy
No good things are bad.
TEXT: All woodware is dispensable.
All environment-frientae
things are good.
FOL: all x. (Moodware -> Dispensable(x)
A worksheet is ther paper or is environment-
TEXT: All paper is woodware.
+ friendly.
FOL: all x. (Paper(x) -> Woodware(x))
</PREMISES>
TEXT: No good things are bad.
<CONCLUSION>
FOL: all x. (Good(x) >> -Bad(x))
A worksheet is not dispensable.
TEXT: All invironment-friende things are good,
</CONCLUSION>
FOL: all x. (EnvirommentFriendlyee -> Good(x))

---

TEXT: A worksheet is either paper or envi friendll
(Incorrect) Translation 2 (StarCoderPlus): 4 Rabbit(Animal) & -Aniaa)el(Animal) (-
FOL: ((Paper (Norksheet) =EnvirommentFrieendlyy Worksheet)) (-Paper (Worksheet) & EnvironmmetFFiemm y (Wookl((wrssheeet)) TEXT: A worksheet is not dispensable. -Dispensable (Workshee(
< Rabbit(Animal) & Squirre((Animal))
(Incorrect) Translation 3 (GPT-4): all x. ((
9 Animal(x) Rabbit(x)) I (Xnimal(x) Squirre((x)))
FOL:
</EVALUATE>
Premise: person either studys or teaches (Ground Truth) Translation: all x. (Study(x)
<PREMISES>
4 Teaches
premisss for sample here, one premise per
(Incorrect) Translation 1 (StarCoderPlus):
< line
4 Studys(Person) I Teaches(Person)
</PREMISES>
(Incorrect) Translation 2 (StarCoderPlus): ((
<CONCLUSION>
4 Study(Persan) & -Teach(Person)
(-Study
c.conllusion for sample here
4 (Person) & Teach(Person))
</CONCLUSION>
(Correct) Translation 3 (GPT-4): all x. (Studies
<EVALUATE>
4 (x) Teaches(x))
Premise: man is either kind or evil. (Ground Truth) Translation: all x. (Kind(x) &
E
FOLIO Error Analysis
+ Evil(x)) | (-Kind(x) & Evil(x))
E.1 Ambiguity of "Either" statements
(Incorrect) Translation 1 (GPT-3.5): (MMan(x) &
+ Kind(x)) | (-Man(x) & Evil(x)))
Depending the context, the phrase "either x or y" could mean XOR y, OR y, or be ambiguous. Throughout our experiments, found that models had many creatively incorrect ways of translating these statements. One reoccurring error was that statements that clearly intended x XOR (such as, "an animal is either rabbit or a squirrel") were translated into OR y. We tried to account for this into account by including multiple samples with this construct in the few shot examples (see Sec. D.4). However, the models still handle this construct inconsistently and incorrectly.
(Incorrect) Translation 2 (StarCoderPlus): Kind(
+ AMan) | (AMan)
(Incorrect) Translation 3 (StarCoderPlus): (Kind
4 (x) Evil(x))
Premise: Ben is either from The Simpsons + funny.
(Ground Truth) Translation: (Simpsons
Funny(Ben)) (-Simpsons(Ben) Funny (Ben
))
(Correct) Translation (StarCoderPlus): ((
Simpsons(Benn -Funny(Ben)) (-Simpsons
4 (Ben) & Funny(Ben))
(Incorrect) Translation 2 (GPT-3.5): Funny(Ben))
<> FromTheeSmmsons
(Incorrect) Translation 3 (GPT-4):
In addition, we find that throughout the FOLIO dataset, by matching the natural language premises to the FOL premises, we find no consistent or pre- dictable pattern as to how "either x or y" state- ments are translated. For example, "an animal is either a rabbi or squirrel" is translated as all fabbit(x)) Squirrel(x), (x), while believe this instance should clearly be XOR. Therefore, believe that some of these samples are inherently ambiguous or malformed.
FromTTheSimpsons(BBn Funny(Ben)
E.2 GPT-4 LINC Failure Modes
L1: FOL fails to capture implicit information not mentioned in the premises. Three examples of errors from the FOLIO validation set are shown below. The first two occurring in both GPT-3.5 and GPT-4, and the latter only occurs GPT-3.5 and interestingly. is correct in GPT-4. In Example 1, to make the correct conclusion, we must encode in FOL that Harry is a person (Person (Harry)) and that Walden is book (Book (ooo"ld""l"")) Harry being a person is implicit, but "Walden" being a book is explicitly mentioned in premise but fails to be explicitly encoded by the model. In Exam- ple 2, we must encode that KiKi an animal to make the correct deduction. One can argue that this example is ambiguous, but from the context, most would make this inference. In Example 3, we need clause that says LGA and LGA are the same airport (SameAirport (LGA, LGA)).
To highlight model behavior on these exam- ples, four representative examples from the FO- LIO validation set are shown below; examples have multiple translations because we used tem- perature T 0.8. Here, Correct/Incorrect indicate whether the translations match the ground truth (which doesn't necessarily match how we would translate it).
Premise: an animal is either a rabbit or a S squirrel
(Ground Truth) Translation: all x. (xabbit(x)
+ Squirrel(x))
(Correct) Translation 1 (GPT-3.5): all x.
+ (x) >> (Rabbit(x) | Squirrel
Example 1 (GPT-4)

---

Premises:
choice of representation. We show four illus- trative examples: the first two examples occur in both GPT-3.5 and GPT-4, while the last two examples only occur in GPT-3.5 and are correct when using GPT-4. The first example is described in the main text. In example 2, we know that Barutin Cove is a cove, but this lost information is not encoded in the FOL, so cannot conclude Cove (BarutinCove). although this is crucial in- formation for making the deduction. In Example 3, we must deduce that Tom's license plate is license plate (FromIs tanbul ( (TomPlate)), which obvi- ous but not encoded by the model. the final example, the idea that an object has four sides ex- pressed both as FourSided and FourSides(( (x), so the model is unable to make the correct deduc- tion.
Books contain tons knowledge.
when ser son reads a book, that person gains knowledge.
a person gains knowledge, they become smarter.
Harry read the book "Walden" by Henry Thoreau.
Conclusion (Ground Truth: True)
Harry is smarter than before.
FOLs:
all x. (Book(x) -> Contains(x, Knowledge))
all x. all y. (Person(x) & Reads(x, y) & Book(y)
9 -> Gains(x, Knowledge))
all x. (xains(x, Knowledge) Smarter(x))
Reads (Hlarry Walden)
Conclusion (Prover9 Deduction: Uncertain) Amarter(Hare
Example 2 (GPT-4)
Premises:
If animal barks, then Jane does not like it.
All dogs animals that bark.
Example (GPT-4)
If animal jumps, then Jane likes it.
Premises:
If animal has legs, then it jumps.
Heinrich Scmidt was Nazi German pol politician.
If animal is terricolous, then it has legs. If KiKi neither jumps nor has legs, then KiKi is terricolous has legs.
Heeinrich Scmidt was also a member the
9 Prussian State Parliament and the Nazi Reichstag.
Conclusion (Ground Truth: True)
Conclusion (Ground Truth: True): Heinrich Schmidt was either German or Russian.
KiKi neither barks nor is dog.
FOLs:
FOLs:
all (Animal(x) Barks(x) NJane x)
& Nazi
> HeinrichSchmidt)
all x. (Dog(x) -> Animal(x) & Barks(x))
uumberPrussianStateerrt iament (HeinrichSchmiitt) &
all x. (Animal(x) Jumps(x) -> Like(Jane, x))
all x. (Animal(x) HxsLegs(x) Jx))
all x. (Animal(x) Terricolousxx) HxsLegs(x)
Conclusion (Prover9 Deduction: Uncertain): (HerniniHiiicchhhhhiine Russian( + HeinrichSchmidte
(Kiii) & HasLegssKiKi)) >> (Terricolous(
KiKi) HasLegs(KiKi))
Example 2 (GPT-4)
Conclusion (Proverg Deduction: Uncertain) (KiK)) -Dog(KiKi)
Premises:
Barutin Cove named after the Bulgarian
< settlement of Barutin.
Example (GPT-3.5):
Barutin Cove
the southwest coast of Snow + Island.
Premises:
Susan flies to LGA airport.
The South Shetland Islands include Snow Island,
The departure and arrival can not be the same
4 Greenwich Island, Deception Island. The South Shetland Islands are considered part 4 Antarctica.
+ airport.
John flies from LGA airport.
If is located in and located in C, then
Conclusion (Ground Truth: False)
<) A located C.
Susan flies from LGA airport.
Conclusion (Ground Truth: True)
FOLs:
There is at least one cove in Antarctica named 4 after a place Bulgaria.
(Susa, LGA) all x. all y. (Departure(x) & Arrival(y) & + SameAi y))
FoLs:
Flies(John, LGA)
NamedAfter NamedkFtee (Barutinooee,,, Barutin) & In(Barutin, + Bulgaria)
Conclusion (Prover9 Deduction: Uncertain): Flies(Susan, LGA)
(BBauuttinoov,, SnowIsland)
In (nnowIIsland, SouthShetLandIslaane & In
+ Greemwichssland, SouthShetlanddIsaands) &
4 In(DeceptionIsland, SouthShetlandIsIlnds) (SSSuthhhhtlaaddIslane Antarctica)
L2: FOL fails to capture information ex- plicitly mentioned in the premises due to the
all x. all all z. ((In(x, y) & In(y, z)) ~>

---

In(x, 2))
Premises:
There are four seasons year: Spring, Summer,
Conclusion (Prover9 Deduction: Uncertain)
> Fall, Winter.
exists x, (X)ve(x) In(x, Antarctica) & exists
All students who want to have a long vacation
y. (In Bulgaria) NamedAfter(x, y)))
> love summer most.
Example 3G
FOLs:
Premises:
all x. (Year (x) -> (Spring(X) Summer Fall
All vehicle registration plates in Istanbul
4 (x) Winter(x)))
+ begin with the number 34.
all x. (Student & Wantssoog@Vacationns)) >>
Plates that do not begin with the number 34 are
4 Loves(x, Summer))
+ not from Istanbul.
Joe s vehicle registration plate is from
Prover9 Error:
+ Isttabul.
The following symbols are used with multiple
Tom's license plate begins with the number 35. If a license plate begins with the number 35,
4 arities: Summer/1, Summer/0.
- then it does not begin with the number
Example 2
- 34.
Premises:
Badults is British Sitcom series, starring ( members of Pappy's s. Badults piloted in July 2013 BBC Three.
Conclusion (Ground Truth: False):
Tom's s license plate is from Istanbul.
FOLs:
FOLs:
all Vehacllefgisstrationlllttxx Beg 34))
exists x. (Badults(x) & BritishSitcom(x) &
4 StarringMembersof( Pappys))
all (-BeginsWith(x, 34) -> -Fromistanbul (x))
Piloted(Badultss July2813, BBCThree)
35)
Prover9 Error:
all (LicensePlate(x) BeginsWith(x, BeginsWith(x, 34))
The following symbols used with mul tiple
- arities: Badults/1, Badults/0.
Conclusion (Prover9 Deduction: Uncertain):
While rarer, there are also syntax errors. For illustration, two examples from GPT-4 are shown
FromIstanbul (TommlatabuuTammlattt
Example (GPT-3.5)
below:
Premi
Premise: Ailton Silva foes not play for a - football club.
All squares have four sides.
All four-sided things are shapes.
FOL: -Exists (FootballClubxx) & PlaysFor(
<> AiltonSilva, x))
Conclusion (Ground Truth: True):
Error: Exists should not be capitalized
All squares are shapes.
Premise: The security deposit can be either + equal one month' 's rent more.
FOLs:
all x. (Square(x) -> (o))Sides(x))
FOL: all x. all (Rent y) <> (Deposit(x) + Deposit(x) > y))
all x. (FourSided(x) -> Shape(x))
Error: is not allowed in Prover9's FOL
Conclusion (Prover9 Deduction: Uncertain) all x. (Square(x) -> Shape(x))
L4: There are mistakes in the FOL trans- lation. For GPT-4, there are very few transla- tion mistakes, but we still find a couple instances where GPT-3.5 fails to capture the semantic mean- ing of the NL examples properly. Two examples shown here:
L3: FOL contains syntax errors. This one reason that we observe majority voting helps sig- nificantly for neurosymbolic methods, as multiple generations increase the likelihood that at one least one FOL representation successfully compiles. As stated in the main text, the most common сгтоr is that the same symbol is used with multiple ari- ties. Two examples of this are shown below: in the first example, the primitive Summer is both used as function representing that year has a summer (in the first premise) and as constant represent- ing that student loves summer. A similar phe- nomenon occurs in the second example with the symbol Badults.
Premise: Platypus have teeth Incorrect FOL: -NoTeeth(Platypus)
Premise: Imperium doesn't t have feud with ( professional wrestling stable that includes Ivy Nile.
Incorrect FOL: -all x. (Includes(x, IvyNile)
HasFeud (Imperium, x))
E.3 GPT-4 CoT Failure Modes
C1: CoT concludes something different than it suggests. We show two examples of this below
Example

---

attends and is very engaged with school student who attends the (both of which LINC solves correctly).
needs apply CPT wants to work in the US. We also know that
Example
international student the US with an F1 visa needs apply for CPT or OPT if
Premises:
Plungers suck.
9 the student wants to work in the US. So,
Vacuums suck.
9 clear that Mike has an F1 visa
Vampires suck.
4 since fits the criteria. Therefore,
Space is
7 the conclusion is true.
A duster is household appliance that doesn't suck.
Example 2
Premises:
Conclusion:
If people perform in school talent shows often,
Space vampire.
9 then they attend and are very engaged
4 with school events.
(GPT-4 rncorrect CoT): Let's think step by step. want to evaluate Space a vampire. We know that Space is vacuum
People either perform in school talent shows
+ often or are inactive and disinterested
+ members of their community.
and that vacuums suck. However, while it' s true that vampires also suck, this doesn't it mean that everything that sucks is vampire. Therefore, there is no reason believe that Space a vampire based on these premises, so the statement is false.
If people chaperone high school dances, then
7 they are not students who attend the school.
All people who are inactive and disinterested
members of their community chaperone high school dances.
All young children and teenagers who wish to
ANSWER: False
+ further their academic careers and students + educational aoportunities
Example 2
4 who attend the school.
Premises:
Bonnie either both attends and is very engaged with school events and is student who attends the school, she neither
Some manmals have teeth. Platypus have no teeth. Platypus are mammals.
Humans have teeth.
events
school.
Conclusion:
Platypus are reptiles.
Conclusion (Ground Truth: Uncertain):
Bonnie performs in school talent shows often.
(GPT-4 Incorrect CoT): Let's think step by step. We want to evaluate if platypus are reptiles. We know from the premises that platypus are mammals and that they have no teeth. The fact that some mammals have teeth does not contradict the fact that platypus, although mammals, do not have teeth. Moreover, the statement about humans having teeth is unrelated to the classification of platypus. There's 's
(GPT-4 Incorrect CoT): Let's think step by step. want evaluate if Bonnie performs 9 school talent shows often. Based on the last premise, if Bonnie a student who attends school engaged with school events, this only possible if she performs school talent shows often, as per the first premise.
is very
she doesn't 't attend and is not engaged with school events, she is an inactive and disinterested member of her communi ty
evidence in the premises that would
suggest platypus reptiles. Therefore, the statement is false.
S But the fourth premise states that
S these individuals chaperone high school
C2: CoT makes incorrect logical deductions.
dances, meaning they cannot be students,
which would contradict the last premise.
Example
Therefore, Bannie performs in school
Premises: ses:
9 talent shows often, so the statement is true.
International students in US have either an visa or a visa.
international student
with needs to apply for CPT or OPT + student wants to work in the US.
visa
C3: CoT fails to find complex paths of reason- ing. We highlight two examples below: in the first example, the ground truth is false. To make this deduction, one must reason that if Greyhound is Boeing 707, then it is plane, which means it is empty, which means it cannot transport multiple passengers, which means it is not airline, which means there are no Greyhound planes, which a contradiction. Looking at the CoT generations, the first CoT attempt gives up after failing to find any
Mike an international student.
Mike needs to apply for CPT
wants to work
4 in the US.
Conclusion (Ground Truth: Uncertain):
Mike has an F1 visa.
(GPT-4 Incorrect CoT): Let's think step by step. + We want to evaluate if Mike has an F1 + visa. From the premises, we know that
Mike is an international student and

---

link between Greyhound and Boeing 707. The sec- ond generation attempts make deductions from the premises. In this case, none of the 10 CoT rea- soning chains begin with the correct step of starting from the negation of the conclusion and deducing it false.
No young person teaches. Jerry nei ther teaches nor manager.
Rose is young or student.
Conclusion (Ground Truth: True)
Rose is a human or Jerry is manager.
(GPT-4 Incorrect CoT, 1): Let's think step by
In the second example, to make the correct de- duction, we need start from the fact that Rose is young or a student. Rose is young, then they do not teach, which means they study, which mcans they are a student, which means they are human. If Rose is a student, then they are humans. Neither of the CoT generation is able to make progress on the deduction from the information that Rose is young. In addition, the first CoT generation also has a logical error at the last step, where it asserts that "A or False" False when the truthness of is uncertain.
4 step. want to evaluate if Rase is
4 human or Jerry is a manager. Let's first
9 look at Rose. From premise 6, we know
9 that Rose is either young or a student.
9 If Rose is a student, then from premise 1
4 we know that Rose is a human. If Rose is
9 young, we don't t know from the premises
4 whether she is a human. Therefare, it is uncertain whether Rose is a human. Now
4 let's look at Jerry. From premise 5, we
9 know that Jerry is not a manager.
O Therefore, Jerry is not manager. So, it
9 is uncertain whether Rose is human,
9 but we know that Jerry is not manager,
9 the statement is false.
(GPT-4 Incorrect CoT, 2): Let's think step by step. We want evaluate if Rose is human Jerry is manager. First, we know that Jerry nei teaches nor is manager, , which
Example
Premises:
If something can transport multiple passengers,
+ then they are not empty.
Jerry is not manager. Therefore, the only way for the conclusion be true is if Rose is human. We know that Rase either young student. If she's 's student, since all students humans, then she human. However, if Rose is young, don' determine
All airlines can transport multiple passengers.
All planes are empty.
All Boeing 707s are planes.
If Greyhound is not an airline, then there are
- no Greyhound planes.
Conclusion (Ground Truth: False)
enough information whether she human. Therefore, it's uncertain whether Rose a human or Jerry a manager.
A Greyhound is Boeing 707.
(GPT-4 Incorrect CoT, 1): Let's think step by step. We want to evaluate if Greyhound is Boeing 707. Looking at our premises, we have no direct or indirect
E.4 Shared mistakes between GPT-4 CoT and LINC
information linking Greyhounds to Boeing
707s. Given the information available, we cannot make any certain conclusion about
As shown in Fig. 5c, there are 21 common errors between GPT-4 CoT and GPT-4 LINC. After an in- depth analysis of the examples, we see that 16 of these arise due to inherent errors in the dataset:
Greyhound being Boeing 707.
Therefore, it is uncertain whether
Greyhound Boeing 787.
(GPT-4 Incorrect CoT, 2): Let's think step by step. We want to evaluate if Greyhound is Boeing 707. The first three premises don't provide any information about
2 of these samples contain the sentence frag- ment "Either Zaha Hadid's design style or Kelly Wearstler's design style." as premise. This premise is likely intended to mean all design styles are one these two styles, but this is hard for the model to grasp from just the fragment (sample 41, 42).
Greyhound Boeing 787s. The fourth
premise tells us that Boeing 707s are planes but doesn't tell us anything about Greyhound,
fifth premise tells us that if Greyhound not an airline,
then there are no Greyhound planes, but this still doesn't imply that a Greyhound is Boeing 707. Therefore, we not have enough information to conclude
2 of these samples contain the sentence frag- ment "Either female tennis players Roland Garros 2022 or male tennis players Roland Garros 2022." as a premise (sample 43, 45).
whether a Greyhound is Boeing 707 or not. So, the statement is uncertain.
Example 2
Premises:
All students are humans.
2 of these samples have an ambiguous use "either": "Ben either from The Simpsons or
If someone studies, then they are a student.
A person either studies or teaches.

---

funny." which in this case ambiguously means XOR. We believe this sentence is an unnatural usage of "either" (sample 142, 143).
F Proofwriter StarCoder+ Errors
We also analyzed, qualitatively, the errors that Star- Coder+ makes on the ProofWriter dataset. Since premises from the ProofWriter dataset are relatively simple and direct, lossy translation is rarer. Most rors are due syntax improper representations. We show five representative errors below:
In 4 samples, there is name that is implicitly an animal, but this is clear (sample 126. 127, 128, 199). Also, in samples 126-122 128, there is statement "If Rock neither a fly nor bird, then Rock neither flies nor breathes." that should likely say "If Rock neither flies nor is a bird, With the original formulation, everything could be uncertain because nothing is known in the case that Rock is a fly (and this is reasonable interpretation).
Premise: All quiet people are round. StarCoder+ FOL: all x. Quiet(x) >> Rxund(x) Ground Truth FOL: all x. (Quiet(x) -> Round(x))
Premise: If someone is quiet and nice then they S are cold.
Starcoder+ FOL: all x. (Quiet(x) \& Nice(x)) >> 4 Cold(x)
Ground Truth FOL: all ((Quiet(x) A& Nice(x))
In 5 samples, the ground-trute truth FOL represen- tation of the natural language premise is incor- rect, causing the label to be incorrect (samples 29, 79, 85, 86, 87).
Cold(x))
Premise: If something is furry then it is quiet. Starcoder+ FOL: Furry(x) -> Quiet(x)
Ground Truth FOL: all x. (Furry(x) Quiet(x))
Premise: The
the dog.
There is a sample where the conclusion is likely mis-worded and should be "Barutin Cove is not located in Antarctica." instead of "Barutin is not located in Antarctica." This changes the ground truth label. (sample 121).
Starcoder+ FOL: Cow(Eats(Dog))
Ground Truth FOL: Eatw Dog)
Premise: The cow is blue. Starcoder+ FOL: Cow(x) \8 Blue(x)
Ground Truth FOL: Blue(Cow)
The remaining 5 samples are examples where both methods fail. In all cases, CoT fails to find the correct reasoning chain, as the premises/reasoning path convoluted and complex. Mcanwhile, LINC fails as follows:
G StarCoderPlus FOLIO Error Analysis
For StarCoder+, In Fig. 6a, we see the same pattern as for GPT-4, with a majority of uncertain predictions. In Fig. 6b, however, we see that CoT for StarCoder+ primarily predicts true. This likely because the model was trained on much more code than text, and may not have picked up sophisticated textual chain-of- thought reasoning capabilities. In Fig. 6c, we can that the mispredictions between CoT and LINC differ much more for StarCoder+ than GPT- Finally, in Fig. 6d, we see the same trends as we saw with GPT-4 but more pronounced, as the similarity between mispredictions LINC and those in the baseline methods is even lower than they were for GPT-4.
slightly different trend.
In sample 104, LINC generates separate sym- bols for NotLiveAtHome and -Li -LoveAtHome, which are semantically equivalent.
In sample 149, LINC generates FOLs that miss implicit information; i.c. that people with names Rose and Jerry humans.
In samples 172 and 173, LINC does not gener- ate a single valid set of FOL premises because all generated expressions have mismatched arity issue.
H The effect of K-way majority voting on LINC and CoT
In sample 193, LINC fails to express the con- clusion correctly: the conclusion is "If Yuri is not American basketball player, then Yuri is a basketball player." but the FOLs outputted are either -American (Yuri) -BasketballPlaeer (Yuri) (merrcaa(YYrr))
In all experiments, use 10-way majority voting, inspired by prior work which found that Chain-of-Though prompting benefited therefrom (Wang et al., 2023b). However, one might won- der how robust the performance gains seen with LINC are to the precise value of K. Figure thus
or BasketballPlayer (Yur)

---

True
True
100
31
7
6
0
61
38
55
80
Predicted Label
False
Predicted Label
False
Uncertain
16
0
0
60
Uncertain
12
60
29
55
10
4
10
Error
Error
20
20
0
True
False
Uncertain
Error
True
False
Uncertain
Error
Reference Label
Reference Label
(a) Confusion matrix for LINC.
(b) Confusion matrix for Chain-of-Thought
100
LINC
Correct
37
39
80
0.8
ma Aucoone Incorrect
CoT
Scratchpad
0.11
0.6
0.62
0.4
65
41
Naive
20
0.21
0.44
0.48
0
Correct
Incerrect
LINC
CoT
Scratcbpad
Naive
LINC Outcome
Comparing
the
consistency
LINC
vs
(d) Similarity between incorrect predictions of each method,
Chain-of-Thoughe
ie.. (A wrong wrong) (A wrong or wrong).
Figure 6: Analyzing and comparing the mistakes made by StarCoder+ on the FOLIO dataset.
shows, for each model equipped with either LINC Chain-of-Though how the accuracy on FO- LIO varies with E 21, 10). We note that, generally speaking, LINC makes good use of increased values of K. This is especially true for the weaker models; these are more prone to gener- ating syntactically invalid FOL expressions, which cause the solver to return an Error. Taking the ma- jority vote many samples thus lessens the risk
1.0
Accuracy on held-on -out tast set
Cloi Choslll G2rS3 LIMC touno
0.8
0.6
0.4
of predicting Error, which is of course always the wrong label. Notably, our results do indicate that CoT benefits from majority voting in this do- main. Future work is needed to establish how this relates to the findings in the previously mentioned prior work.
0.2
0.0
2
7 K-way majority vote
4
5 6
8
9
10
Figure 7: Accuracy FOLIO per value of K (Ap- pendix H). Shaded areas are + standard deviation over 1000 bootstrapped samples. Note that increasing benefits LINC (solid lines; shading in color) but not CoT (dashed lines; shading in gray) in our experiments on this dataset.


Reviews:
[{"review_id": "E8fYJSo1nQ", "reviewer": "Reviewer_1NfW", "summary": "", "questions": " A. Why not run experiments with GPT4 on ProofWriter? (Figure 2, right side)\n\n B. Did you perform experiments on the paraphrased portion of ProofWriter? If so, how do the results compare?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for the thoughtful comments and helpful questions. We are glad that the exploration in this work was determined to be in-depth, and that the presentation was found to be clear and easy to understand. We hope that this work can facilitate ongoing conversations and act as a reproducible marker. In addition to the use of an open source model, we will release the entirety of our code base for researchers to build upon. The link will be included in the updated manuscript.\n\n**Q1: Unclear how well our method would perform on more natural language**\n\nThis is an excellent question! We agree with the reviewer that extending to more natural language is one of the core limitations of our work as it currently stands, and we believe that it is one of the most impactful directions for future work. This is one of the main motivations of our error analysis, and we believe that identifying the bottlenecks of the LINC approach will pave the way for improvements on more natural language. We provide here a discussion on this and will integrate the core information into our updated version.\n\nIndeed, while LINC’s performance on ProofWriter was quite strong, this reflects a best case scenario. ProofWriter is a synthetically generated dataset, and as such is expected to be more easily parsed back into its underlying logical structure. FOLIO, on the other hand, reflects a more naturalistic dataset, as noted by the reviewer, and as such we see a gap in performance between these two evaluations.\n\nIn follow-up work, we hope to more deeply explore a more naturalistic setting and are actively looking for such benchmarks, as when things get the most messy is also where improvements become the most meaningful. Below, we propose potential solutions addressing each of the failure modes of LINC with GPT-4 on FOLIO from Appendix E.2.\n\n*L1 (lines 1365 - 1451): FOL fails to capture implicit information not present in the premises.*\n\n**Potential solution:** In naturalistic communication, “obvious” information is often left out of explicit productions, and left to be inferred by interlocutors in the “common ground”’ of the communicative act [1, 2]. We hope to directly model this phenomena as part of our approach using the following strategy. After generating the set of logic expressions explicitly presented by the problem, the model next explores the set of additional premises that might be generated to connect the sparsely connected terms thus far, filtered to those that would impact the conclusion (akin to a goal-directed strategy). The likelihood of each of these premises can then be evaluated under the LM parser conditioned on the original problem as well as new ICL examples showcasing this type of implicit premise recovery. Those with high probability of inclusion (above some to-be-determined threshold) can then be included in the premises passed to the logic prover.\n\n*L2 (lines 1452 - 1566): FOL fails to capture information explicitly mentioned in the premises due to the choice of representation.*\n\n**Potential solution:** This is a simpler case of L1 since it can be explicitly verified whether a proposed fact is explicitly stated in the premises, and all of the individual expressions in our FOL representation are relatively simple and checkable by an LM. \n\n*L3 (lines 1567 - 1629): FOL contains syntax errors.*\n\n**Potential solution:** Recent work [3, 4] has shown promise in the ability of models like GPT-4 to self-debug and correct itself from error messages, and [5] has already seen improvements from this idea in the domain of logical reasoning. Therefore, we believe that the idea of self-repair may be able to at least partially mitigate this class of errors.\n\n*L4 (lines 1630 - 1645): There are mistakes in the FOL translation.*\n\n**Potential solution:** These mistakes are rare with models like GPT-4, but can still occur from time to time. One potential method we propose for improving the faithfulness of FOL translations is to ask the LM to translate the FOL back to natural language and compare with the original. \n\nWe hope that this expanded discussion surrounding the additional complexity and challenge of naturalistic evaluation, combined with an initial proposal for how we view the next steps will help make this paper more valuable for the community.\n\n[1] Grice, H. P. (1975). Logic and conversation. In D. Davidson & G. Harman (eds.), The Logic of Grammar (pp. 64–75). Dickenson.\n\n[2] Stalnaker, R. (2002). Common ground. Linguistics and philosophy, 25, 701-721.\n\n[3] Chen, X., Lin, M., Schärli, N., & Zhou, D. (2023). Teaching large language models to self-debug. arXiv preprint arXiv:2304.05128.\n\n[4] Olausson, T. X., Inala, J. P., Wang, C., Gao, J., & Solar-Lezama, A. (2023). Demystifying GPT Self-Repair for Code Generation. arXiv preprint arXiv:2306.09896.\n\n[5] Pan, L., Albalak, A., Wang, X., & Wang, W. Y. (2023). Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning. arXiv preprint arXiv:2305.12295.\n\n**Q2 (Reviewer question A): Why not run experiments with GPT4 on ProofWriter? (Figure 2, right side)**\n\nThanks for the suggestion, we have run this experiment and included the results below. At a high-level, the insights are as follows:\n- GPT-4 performs better than GPT-3.5 for both CoT (72.2% vs. 43.6%) and LINC (98.3% vs. 96.4%).\n- LINC still performs better than CoT across the board, and even StarCoder+ with LINC outperforms GPT-4 with CoT. (LINC: GPT-4 98.3%, GPT-3.5 96.4%, StarCoder+ 82.5%; CoT: GPT-4 72.2%, GPT-3.5 43.6%, StarCoder+ 38.6%).\n- Just like we saw with GPT-3.5 in Figure 3b, GPT-4 CoT performance steadily drops as longer deductive chains are required (98%, 92%, 74%, 65%, 57%, 48% for depths 0, 1, 2, 3, 4, 5), while LINC remains near perfect accuracy (100%, 98%, 95%, 98%, 98%, 100%).\n- On CoT, compared to GPT-3.5, gains from GPT-4 are primarily from performance on samples with low proof depth. \n\n*GPT-4 ProofWriter results*\n| Condition | Accuracy | \n| --- | --- |\n| Baseline | 53.1% |\n| Scratchpad | 55.8% |\n| CoT | 72.2% |\n| LINC | 98.3% |\n\nSo, in sum, we think that these new results are consistent with the general conclusion we stated in our paper that LINC has strong advantages over the other approaches for ProofWriter, even when using GPT-4.\n\n**Q3 (Reviewer question B): Did you perform experiments on the paraphrased portion of ProofWriter? If so, how do the results compare?**\n\nWhile we did not perform such experiments, this is an excellent general suggestion for our follow-up work on extending LINC to more naturalistic settings, which we have looped into the discussion above. We thank the reviewer for raising this line of inquiry. Regarding specifically why we did not include the paraphrased portion of ProofWriter, it was because we found it to be less naturalistic than FOLIO, which we adopted for our initial semi-naturalistic option. See below an example from the paraphrased portion of ProofWriter, which reflects the indeed complex but still not quite natural style:\n\n```\nsent1\":\"Charlie is green, but often kind, even when he is blue and cold.\",\"sent2\":\"Fred rather resembles the rainbow, as he is green, red and blue; Fred is also said to be very kind.\",\"sent3\":\"Harry seems to be round.\",\"sent4\":\"Young people who are nice and look round are also going to be green.\n```\n\n**Q4: Missing citation for McNemar's test**\n\nThank you for catching this. We will add the following reference for McNemar's test:\n\nMcNemar, Q. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika 12, 153–157 (1947).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": " - They provide an in-depth exploration and comparison between their neurosymbolic approach and chain-of-thought prompting (and more broadly against methods that perform reasoning entirely in text).\n - They experiment with StarCoder+, a smaller open LLM, which facilitates reproducibility.\n - The paper is well-written and easy to understand.", "reasons_to_reject": " - The proposed method seems like it would perform well on tasks like ProofWriter, which was generated synthetically. But it's less clear how well it would perform on more natural language, which can be noisy. A comparison of the performance on a more realistic dataset would strenghten the paper. FOLIO is more realistic than ProofWriter, but it would be interesting to see this approach applied to a reasoning dataset without symbolic logical form labels.", "questions_to_authors": " A. Why not run experiments with GPT4 on ProofWriter? (Figure 2, right side)\n\n B. Did you perform experiments on the paraphrased portion of ProofWriter? If so, how do the results compare?", "paper_topic_and_main_contributions": "The authors present a framework for solving reasoning problems where an LLM converts natural language text into first-order logic. A classical theorem prover is then used to solve the reasoning problem symbolically. The authors compare their approach to chain-of-thought with GPT and StarCoder+.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "Minor: Missing citation for McNemar's test.", "Typos_Grammar_Style_and_Presentation_Improvements": "The paper is really well written."}, "extra_text": {}}, {"review_id": "5nF9YfeWl7", "reviewer": "Reviewer_iSNf", "summary": "", "questions": "A. Can you add discussions about non-LLM neuro-symbolic approaches in related work? I am not an expert in the field and list a few as examples. They adopt different settings as yours, but can also provide valuable perspectives for positioning your contributions. If you feel that this field is totally non-comparable, can you explain why?\n\nEbrahimi, Monireh, et al. \"Towards bridging the neuro-symbolic gap: Deep deductive reasoners.\" Applied Intelligence 51 (2021): 6326-6348.\nRocktäschel, Tim, and Sebastian Riedel. \"Learning knowledge base inference with neural theorem provers.\" Proceedings of the 5th workshop on automated knowledge base construction. 2016.\n\nB. In a place you feel appropriate, can you list the approximate cost for running these inferences? 360 still seems a tiny number compared with the original dataset size.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for your thoughtful comments and helpful questions. We are happy to see that you believe our contributions are novel and will be valuable to the community, in particular the qualitative analysis which—as you note—“provides valuable evidence on how [the] two paradigms work differently”. On the other hand, you have also contributed valuable critiques, in particular the lack of a thorough comparison between LINC and tool-augmented LLM methods more generally. We believe addressing this will help clarify to the reader where our contributions stand in comparison to contemporary work.\n\n**Q1: Conceptual/theoretical comparison with tool-using papers**\n\nWe thank the reviewer for pointing out the resemblance to tool-using papers! Our work was heavily inspired by these works, and we will add a section in our related work about LLM + tool use papers. Conceptually, as you mentioned, LINC follows a very similar framework as [1-4], which solves reasoning problems into an appropriate intermediate symbolic language which is then executed to obtain an answer. Tool-based methods are quite ideal for solving reasoning tasks, as there should be no room for error in the grounded tool-use step. We compare LINC to [1-4] below:\n\n| Work | Task | Intermediate language to be executed |\n| :---: | :----: | :---: |\n| [1] (PAL) | Mathematical reasoning (GSM8K) | Python |\n| [2] | Mathematical reasoning (MATH and university benchmark) | Python (with Numpy, Sympy, and Matplotlib) |\n| [3] (Mind's Eye) | Physical reasoning (Utopia) | MuJoCo |\n| [4]  | Probabilistic reasoning (cognitively inspired tasks) | Church (probabilistic programs) |\n| LINC (ours) | Logical Reasoning (FOLIO, ProofWriter) | FOL |\n\nAnother line of work [5-8], including Toolformer, proposes methods that teach themselves how and when to use tools like a calculator, an information retrieval system, a translator, etc. In these works, the model must learn when to use the tool itself, whereas in the reasoning tasks from [1-4] and LINC, it is known *a priori* which tool will be used. \n\nWhile the ideas from [5-8] have not yet been used in reasoning tasks, we believe there is promise in doing so. A key contribution we make is the observation that LINC and CoT make different errors (Fig. 4c), so there is high potential for future improvements by choosing whether to apply CoT or LINC on a given sample. For example, on FOLIO with GPT-4, CoT and LINC get 75% and 73% accuracies, respectively. If we could perfectly decide when to apply each technique, we would get an accuracy of 88%. We hypothesize that similar ideas of choosing when to use a direct LLM vs. when to use a tool-based approach also apply to [1-4], but they unfortunately do not contain any analysis indicating that the methods show different errors.\n\nWe hope that this comparison helps with your excitement about our work! Let us know if you would like us to clarify anything else in terms of conceptual/theoretical comparison with the tool use literature.\n\n[1] Gao, L., Madaan, A., Zhou, S., Alon, U., Liu, P., Yang, Y., ... & Neubig, G. (2023). PAL: Program-aided language models. In International Conference on Machine Learning (pp. 10764-10799). PMLR.\n\n[2] Drori, I., Zhang, S., Shuttleworth, R., Tang, L., Lu, A., Ke, E., ... & Strang, G. (2022). A neural network solves, explains, and generates university math problems by program synthesis and few-shot learning at human level. Proceedings of the National Academy of Sciences, 119(32).\n\n[3] Liu, R., Wei, J., Gu, S. S., Wu, T. Y., Vosoughi, S., Cui, C., ... & Dai, A. M. (2022). Mind's Eye: Grounded Language Model Reasoning through Simulation. arXiv preprint arXiv:2210.05359.\n\n[4] Wong, L., Grand, G., Lew, A. K., Goodman, N. D., Mansinghka, V. K., Andreas, J., & Tenenbaum, J. B. (2023). From Word Models to World Models: Translating from Natural Language to the Probabilistic Language of Thought. arXiv preprint arXiv:2306.12672.\n\n[5] Schick, T., Dwivedi-Yu, J., Dessì, R., Raileanu, R., Lomeli, M., Zettlemoyer, L., ... & Scialom, T. (2023). Toolformer: Language models can teach themselves to use tools. arXiv preprint arXiv:2302.04761.\n\n[6] Thoppilan, R., De Freitas, D., Hall, J., Shazeer, N., Kulshreshtha, A., Cheng, H. T., ... & Le, Q. (2022). Lamda: Language models for dialog applications. arXiv preprint arXiv:2201.08239.\n\n[7] Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., & Cao, Y. (2022). React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629.\n\n[8] Cheng, Z., Xie, T., Shi, P., Li, C., Nadkarni, R., Hu, Y., ... & Yu, T. (2022). Binding language models in symbolic languages. arXiv preprint arXiv:2210.02875.\n\n**Q2 (Reviewer question A): Non-LLM neuro-symbolic approaches**\n\nThank you for bringing this oversight to our attention! The rich literature on pre-LLM neuro-symbolic work on logical reasoning was also key inspiration for this project; for the updated version, we will amend the Related Work section accordingly.\n\nRoughly speaking, pre-LLM neuro-symbolic work on logical reasoning fell into one of two buckets, both of which are quite distinct from the setting we consider:\n(1) *Neural logical reasoning*. Here one trains a neural network to perform reasoning over a chosen logic [1]. This form of neuro-symbolic reasoning integration can be seen as an instance of what is more broadly called neural algorithmic reasoning [2, 3], where the algorithm to be learned is to perform deductive reasoning. This line of work assumes that the inputs are already symbolically grounded, which is quite a different setting than in LINC and other recent work in the LLM era that has focused on reasoning over natural language inputs.\n(2) *Inference modulo logical constraints*. Here one constructs or constrains a probabilistic model, e.g., a DNN or even a simpler graphical model, so that its outputs are guaranteed to satisfy some logical constraints (e.g. matching some FOL knowledge base) [4, 5, 6]. While this allows for flexible input formats such as natural language, efficiently combining a large output space with a symbolically grounded set of constraints in a way that scales beyond toy datasets is challenging, although recent work is making some headway in this space [7]. This is a closer setting to the one we consider in our work, but the methodology is quite different: in LINC the output space of the LLM is not actually constrained, and so it does not suffer from the same scalability concerns, although of course this comes at the cost of losing all hard guarantees about the logical consistency of the outputs.\n\nIn summary, the setting we study in LINC is more closely aligned to other recent work in which the LLM itself performs the symbolic grounding [8, 9, *inter alia*] than it is to most work in the older neuro-symbolic logical reasoning literature, which has traditionally focused on settings where you either have pre-existing symbolic constraints (e.g., a knowledge base) or symbolically grounded inputs (e.g., in a particular logic of your choice).\n\n[1] Ebrahimi, M., Eberhart, A., Bianchi, F., & Hitzler, P. (2021). Towards bridging the neuro-symbolic gap: Deep deductive reasoners. Applied Intelligence, 51, 6326-6348.\n\n[2] Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Bennani, M., Csordás, R., ... & Veličković, P. (2022). A generalist neural algorithmic learner. In Learning on Graphs Conference (pp. 2-1). PMLR.\n\n[3] Veličković, P., Badia, A. P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., ... & Blundell, C. (2022). The CLRS algorithmic reasoning benchmark. In International Conference on Machine Learning (pp. 22084-22102). PMLR.\n\n[4] Marra, G., Giannini, F., Diligenti, M., & Gori, M. (2019). Integrating learning and reasoning with deep logic models. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (pp. 517-532). Cham: Springer International Publishing.\n\n[5] Bach, S. H. (2015). Hinge-loss Markov random fields and probabilistic soft logic: A scalable approach to structured prediction (Doctoral dissertation, University of Maryland, College Park).\n\n[6] Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T., & De Raedt, L. (2018). Deepproblog: Neural probabilistic logic programming. Advances in neural information processing systems, 31.\n\n[7] Zhang, H., Dang, M., Peng, N., & Van den Broeck, G. (2023). Tractable control for autoregressive language generation. In International Conference on Machine Learning (pp. 40932-40945). PMLR.\n\n[8] Nye, M., Tessler, M., Tenenbaum, J., & Lake, B. M. (2021). Improving coherence and consistency in neural sequence models with dual-system, neuro-symbolic reasoning. Advances in Neural Information Processing Systems, 34, 25192-25204.\n\n[9] Gao, L., Madaan, A., Zhou, S., Alon, U., Liu, P., Yang, Y., ... & Neubig, G. (2023). Pal: Program-aided language models. In International Conference on Machine Learning (pp. 10764-10799). PMLR.\n\n**Q3 (Reviewer question B): Approximate cost for running experiments and concern about small dataset size**\n\nThis is a reasonable question. The approximate cost for running these experiments was ~$600. As we note in our response to Reviewer 1NfW, we have run additional experiments using GPT-4 on ProofWriter; we repeat those results in the table below.\n\nWe note that in order to carry out our extensive analysis, we required a dataset which was balanced across all combinations of depths and labels without repeating any task. This is not the case in the full ProofWriter dataset: for example, we found that there are very few depth-5 questions in ProofWriter that have the label “Uncertain”/”Unknown”. The dataset we use for our experiments has 20 questions per label (3) and proof depth (6); this results in a final dataset size of 20 * 3 * 6 = 360. We found that without cherry-picking the seed, we were unable to obtain a subset that had 30 questions per depth and label through simple rejection sampling, due to the aforementioned relative lack of “Uncertain”/”Unknown” questions. We also note that the dataset was, up to these constraints, randomly generated and would therefore likely generalize to a larger sample from the same balanced distribution.\n\nFrom these results, while the dataset size is small, we believe that it is sufficient to highlight our key insight on ProofWriter: while LINC achieves almost perfect accuracy across all proof depths, CoT's accuracy drops off as the proof depth increases.\n\nTogether with our source code release, we will also release the code generating this balanced subset from the full dataset. Future researchers are welcome and encouraged to explore a larger number of samples within particular subsets.\n\n*GPT-4 ProofWriter results*\n| Condition | Accuracy | \n| --- | --- |\n| Baseline | 53.1% |\n| Scratchpad | 55.8% |\n| CoT | 72.2% |\n| LINC | 98.3% |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The propose method is one of the first papers to combine large language models with logical solvers, so that the strong semantic understanding ability of LLMs and strict logical reasoning of FOL solvers can complement each other.\n\nThe empirical results confirm their conclusions that the proposed approach do reflect a benefit in reasoning scores.\n\nI also appreciate the qualitative analysis on the difference in error modes of LINC compared with pure LLM reasoning (Figure 3 and section 5.1). They are not surprising but provides valuable evidence on how two paradigms work differently.", "reasons_to_reject": "A minor reason to reject is that, although in the specific problem of FOL this approach is one of the first-of-its-kind, if we place the problem under a wider umbrella of \"connecting LLMs with tools\", the paradigm shows resemblance with other LLM + tool using papers. For example, if we compare with Toolformer, both approaches can be categorized in the following process:\n\n- Prompting LLMs to convert the problem in a tool/API compatible format\n- (Optional) using examples or let LLMs to correct answers\n- Applying the tool/API on the converted format\n- post-processing the answers.\n\nI do acknowledge that in an era when LLMs are so powerful that people had to give up fancy model designs and reluctantly welcome LLMs into every problem, it is hard to avoid it or derive too crazy methods on overwhelmingly large LLMs. The author also made an effort to focus the paper on comparing with LLM reasoning and CoT. But I still do like to see more conceptual / theoretical comparison with other tool using papers if the \"Excitement\" score is to be raised.", "questions_to_authors": "A. Can you add discussions about non-LLM neuro-symbolic approaches in related work? I am not an expert in the field and list a few as examples. They adopt different settings as yours, but can also provide valuable perspectives for positioning your contributions. If you feel that this field is totally non-comparable, can you explain why?\n\nEbrahimi, Monireh, et al. \"Towards bridging the neuro-symbolic gap: Deep deductive reasoners.\" Applied Intelligence 51 (2021): 6326-6348.\nRocktäschel, Tim, and Sebastian Riedel. \"Learning knowledge base inference with neural theorem provers.\" Proceedings of the 5th workshop on automated knowledge base construction. 2016.\n\nB. In a place you feel appropriate, can you list the approximate cost for running these inferences? 360 still seems a tiny number compared with the original dataset size.", "paper_topic_and_main_contributions": "This paper proposes novel neuro-symbolic approach for first-order logical reasoning on natural language tasks. They deploy a large language model for parsing the natural language inputs input first-order premises, and then let FOL solvers do the logical deduction. The authors also provide extensive qualitative and quantitative analysis for the error modes and model behaviors on both proposed method and baselines.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "See question A"}, "extra_text": {}}, {"review_id": "B2KB44zevr", "reviewer": "Reviewer_HxCp", "summary": "", "questions": "Question A: What is the pass rate of the parsed FOL expressions in the prover?\nQuestion B: How to deal with the error propagation from parsing the FOL expressions to getting the final answer?\n", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for the thoughtful comments and helpful questions. We are pleased that you find our analysis comprehensive and our error analysis useful. We too hope that the method and findings could be valuable to the community. We appreciate that you point out the connections between our method and autoformalization research, and we address your questions below.\n\n**Q1: Comparison to autoformalization in mathematical reasoning**\n\nThis is a great suggestion! We will certainly add a comparison to the autoformalization literature in our related work. There have been many prior works on translating NL to representations such as formal mathematical languages [1, 2, 3, 4], FOL [5, 6], temporal logic [5, 7, 8], regex [5], etc. The novelty in our LINC approach is in leveraging these autoformalization abilities to perform logical reasoning about commonsense scenarios rather than mathematical domains, and a key contribution in our paper is comparing and contrasting how LINC and CoT approach reasoning tasks. For example, one benefit of LINC is that it eliminates a class of reasoning errors introduced by CoT because it uses a theorem prover to do the logical reasoning step.\n\n[1] Wang, Q., Kaliszyk, C., & Urban, J. (2018). First experiments with neural translation of informal to formal mathematics. In Intelligent Computer Mathematics: 11th International Conference, CICM 2018, Hagenberg, Austria, August 13-17, 2018, Proceedings 11 (pp. 255-270). Springer International Publishing.\n\n[2] Wang, Q., Brown, C., Kaliszyk, C., & Urban, J. (2020). Exploration of neural machine translation in autoformalization of mathematics in Mizar. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (pp. 85-98).\n\n[3] Wu, Y., Jiang, A. Q., Li, W., Rabe, M., Staats, C., Jamnik, M., & Szegedy, C. (2022). Autoformalization with large language models. Advances in Neural Information Processing Systems, 35, 32353-32368.\n\n[4] Azerbayev, Z., Piotrowski, B., Schoelkopf, H., Ayers, E. W., Radev, D., & Avigad, J. (2023). Proofnet: Autoformalizing and formally proving undergraduate-level mathematics. arXiv preprint arXiv:2302.12433.\n\n[5] Hahn, C., Schmitt, F., Tillman, J. J., Metzger, N., Siber, J., & Finkbeiner, B. (2022). Formal specifications from natural language. arXiv preprint arXiv:2206.01962.\n\n[6] Lu, X., Liu, J., Gu, Z., Tong, H., Xie, C., Huang, J., ... & Wang, W. (2022). Parsing natural language into propositional and first-order logic with dual reinforcement learning. In Proceedings of the 29th International Conference on Computational Linguistics (pp. 5419-5431).\n\n[7] Cosler, M., Hahn, C., Mendoza, D., Schmitt, F., & Trippel, C. (2023). nl2spec: Interactively Translating Unstructured Natural Language to Temporal Logics with Large Language Models. arXiv preprint arXiv:2303.04864.\n\n[8] Chen, Y., Gandhi, R., Zhang, Y., & Fan, C. (2023). NL2TL: Transforming Natural Languages to Temporal Logics using Large Language Models. arXiv preprint arXiv:2305.07766.\n\n**Q2 (Reviewer question A): What is the pass rate of the parsed FOL expressions in the prover?**\n\nWhile strictly speaking Prover9 does not come with guarantees for soundness and completeness, we found in our analysis that the theorem-proving step had 100% accuracy (from FOL expressions to final answer). \n\nIf we interpret the pass rate as the proportion that does not contain syntax errors, then on FOLIO it is 62% for StarCoder+, 76% for GPT-3.5, and 87% for GPT-4, as reported in Sec. 5.1.\n\n**Q3 (Reviewer question B): How to deal with the error propagation from parsing the FOL expressions to getting the final answer?**\n\nSince all errors in our LINC experiments happen in the parsing/translation stage, there is no compounding of errors in the pipeline. If there is a syntax error in a parsed FOL expression such that it fails to compile, an “Error” label will be produced as the final answer. We encourage the reviewer to check out Appendix E.1 and E.2 in addition to Sec. 5.1 for a thorough analysis of the parsing mistakes, and we are actively looking for ways to mitigate these mistakes as part of future work.\n\n**Q4: Reproducibility concerns**\n\nWe strive to make our results as reproducible as possible, and we will open source all of our data (including filtered FOLIO and ProofWriter datasets) and implementations, including clearly marked scripts to reproduce each figure in the paper. Please let us know if there are any other clarifications we can include that you believe would help with reproducibility!\n\n**Q5: StarCoder+ citation**\n\nThanks for catching this! We will cite the model in the main text.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The performance of the proposed LINC is significant as the smaller model StarCoder+ outperforms GPT-3.5 with LINC. The analysis is comprehensive. I especially appreciate the error analysis in Section 5. The proposed method and the insightful findings are inspiring to the community. The paper is also well-written and easy to follow.", "reasons_to_reject": "The NL-to-FOL task might not be original considering the autoformalization task in mathematical reasoning of converting natural language questions into verifiable formal proofs. Please see “Missing References” for more details.", "questions_to_authors": "Question A: What is the pass rate of the parsed FOL expressions in the prover?\nQuestion B: How to deal with the error propagation from parsing the FOL expressions to getting the final answer?\n", "paper_topic_and_main_contributions": "This paper proposes a neurosymbolic approach of combining language models with first-order logic provers. In this framework, the LLMs first parse natural language questions into first-order logic expression, then it uses a logic prover to evaluate the expressions and obtain the final answer. The framework uses a smaller StarCoder+ and the GPT-3.5 as two backbone models and is evaluated on two datasets FOLIO and ProofWriter. The experiments show significance of the approach. ", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "The StarCoder+ model is not cited or attached hyperlink in the main text. "}, "extra_text": {"Missing_References": "The NL-to-FOL task is similar to the autoformalization task in mathematical reasoning, for instance:\n[1] Wu Y, Jiang A Q, Li W, et al. Autoformalization with large language models[J]. Advances in Neural Information Processing Systems, 2022, 35: 32353-32368.\n[2] Wang Q, Brown C, Kaliszyk C, et al. Exploration of neural machine translation in autoformalization of mathematics in Mizar[C]//Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs. 2020: 85-98.\n"}}]

Author rebuttal:

Meta-review: This paper proposed a semantic parser to parse natural language to first-order logic for commonsense problems. Applying this semantic parser to smaller models resolved much better results compared to LLMs (with or without CoT).

**Pros**: The paper is very well-written and easy to follow. It also provided in-depth analyses of their methods and LLM performance. The performance improvement from smaller models is also important compared to LLMs. All the reviewers appreciate these aspects of the paper.

**Cons**: It's unclear how to apply this method to more "natural language" tasks, as mentioned by 1NfW. Moreover, adding more discussion in the related work section about the comparison to Toolformer and other work in the mathematical domain of semantic parsers is going to be beneficial for the readers (HxCp, iSNf).

Overall, it's a very well-written, solid, and sound paper. The direction of combining neural models and traditional solvers is exciting to solve certain problems in commonsense domains.
Decision: Accept-Main