Reliable Reasoning Beyond Natural Language

The Math Word Problems category (21 problems) is inspired by grade-school math problems in datasets such as GSM8k but introduces an additional dimension of variable interdependence.

“This category (21 problems) is inspired by the grade-school math problems in datasets such as GSM8k (Cobbe et al., 2021), but introduces an additional dimension of variable interdependence (i.e., higher relational complexity between the variables).”

• cites Cobbe et al., 2021 sourceSupported

Unlike synthetically templated logic datasets, NLR problems have explicit statements along with implicit information that must be inferred from common sense and context.

“Unlike synthetically templated logic datasets (Han et al., 2022;Clark et al., 2020) in which all premises are stated as short clauses, NLR problems have explicit statements along with implicit information that must be inferred from common sense and context.”

• cites Han et al., 2022 sourcePartly supported

  The Introduction describes RuleTaker and LogicNLI as limited in natural-language variety and not written by humans using real-world knowledge; the paper’s comparison table labels them synthetic. This supports the contrast with synthetic logic datasets, but our copy does not establish that all their premises are short clauses or that NLR problems require implicit information inferred from commonsense and context. (LLM, conf=0.83)

  Experimental — accuracy not yet measured
• cites Clark et al., 2020 sourceSupported

The statistical nature of LLM training means they often fail to generalize appropriately to problems outside their training distribution.

“Moreover, the statistical nature of LLM training means they often fail to generalize appropriately to problems outside their training distribution (Zhang et al., 2022).”

• cites Zhang et al., 2022 sourcePartly supported

  The Discussion and Section 4 report that models trained on one distribution of logical-reasoning problems fail on another because they rely on statistical features rather than the correct reasoning function. The study chiefly tests BERT in a confined problem space, with an extension to T5; it does not establish that LLMs generally or often fail on out-of-distribution problems. (LLM, conf=0.85)

  Experimental — accuracy not yet measured

Math Word Problems in NLR test reasoning on math problems similar to GSM8k but with varying levels of relational complexity, particularly degree of variable interdependence.

“(i) Math Word Problems test reasoning on math problems similar to GSM8k (Cobbe et al., 2021) but with varying levels of relational complexity, particularly in their degree of variable interdependence, which we define as the number of other variables on which a single variable's value depends.”

• cites Cobbe et al., 2021 sourceSupported

LLMs often struggle to reason reliably and flexibly despite their linguistic competence.

“Despite their linguistic competence, Large Language Models (LLMs) often struggle to reason reliably and flexibly.”

• Also stated in: § 1 Introduction · boosted

  “However, despite their linguistic competence, LLMs often demonstrate limitations in their capacity to reason reliably and flexibly (Mahowald et al., 2023;Dziri et al., 2024;Wu et al., 2023).”

• cites Mahowald et al., 2023 sourceSupported
• cites Dziri et al., 2024Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Wu et al., 2023Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

PaLM 540B and PaLM 62B's performance on the Navigate task were significantly below the best human performance score.

“We selected Navigate for our experiments among other BIG-bench tasks due to the fact that PaLM 540B and PaLM 62B's performance on the task were significantly below the best human performance score(Chowdhery et al., 2022).”

• cites Chowdhery et al., 2022 sourceSupported

LINC has a limitation in capturing implicit information not explicitly stated in the premises, as it primarily uses LLMs as a semantic parser.

“However, it has a limitation in capturing implicit information not explicitly stated in the premises, as it primarily uses LLMs as a semantic parser, translating each natural language premise directly into a logical statement (Olausson et al., 2023).”

• cites Olausson et al., 2023 sourceSupported

The degree of variable interdependence has a significant effect on the performance of text-only LLMs.

“As we show in Section 5, the degree of variable interdependence has a significant effect on the performance of text-only LLMs.”

In contrast to Navigate, each problem in the NLR dataset defines a new task with unique rules, world models, and update logic, thus testing for generalizable reasoning.

“However, in contrast to Navigate, which features systematically generated instances of a single task (navigation), each problem in the NLR dataset defines a new task with unique rules, world models, and update logic, thus testing for generalizable reasoning.”

Similar to the Navigate task, the algorithmic games provide deterministic instructions for updating an initial state.

“Similar to the Navigate task (Srivastava et al., 2023), these problems provide deterministic instructions for updating an initial state.”

• cites Srivastava et al., 2023Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The NLR dataset is composed of 55 unique problems across three categories: math word problems, constraint satisfaction problems, and algorithmic games.

“The NLR dataset acts as a diagnostic tool, composed of 55 unique problems across three categories.”

• Also stated in: § Algorithmic Game Problem: · plain

  “(i) NLR, a 55-problem benchmark (21 math word problems, 17 constraint satisfaction, 17 algorithmic games) targeting tasks that require iterative reasoning with high variable interdependence”

On NLR, GPT-4's performance increases significantly from as low as 8.3% to 100% on two of the three categories.

“On NLR, GPT-4's performance increases significantly from as low as 8.3% to 100% on two of the three categories (Figure 3), and remains stable even as the degree of variable interdependence increases from 1 to 4-where text-only GPT-4's performance falls from 100% to 0% (Figure 4).”

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

The proposed method yields large and robust performance gains across GSM8k and BIG-bench Navigate.

“Our method yields large and robust performance gains across the GSM8k and BIG-bench Navigate benchmarks and achieves near-perfect accuracy on NLR problems, maintaining robustness even as variable interdependence-the number of other variables on which the value of a single variable depends-increases.”

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

The proposed method achieves near-perfect accuracy on NLR problems.

“Our method yields large and robust performance gains across the GSM8k and BIG-bench Navigate benchmarks and achieves near-perfect accuracy on NLR problems, maintaining robustness even as variable interdependence-the number of other variables on which the value of a single variable depends-increases.”

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

The NLR dataset is a collection of 55 unique, hand-designed problems that target reasoning bottlenecks arising from the sequential prediction paradigm of LLMs and the inherently linear nature of natural language.

“To identify these shortcomings, we introduce the Non-Linear Reasoning (NLR) dataset, a collection of 55 unique, hand-designed problems that target reasoning bottlenecks arising from the sequential prediction paradigm of LLMs and the inherently linear nature of natural language.”

• Also stated in: § 1 Introduction · plain

  “The NLR dataset acts as a diagnostic tool, composed of 55 unique problems across three categories.”

On NLR, GPT-4's performance remains stable even as the degree of variable interdependence increases from 1 to 4.

“On NLR, GPT-4's performance increases significantly from as low as 8.3% to 100% on two of the three categories (Figure 3), and remains stable even as the degree of variable interdependence increases from 1 to 4-where text-only GPT-4's performance falls from 100% to 0% (Figure 4).”

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

The proposed method maintains robustness as variable interdependence increases.

“Our method yields large and robust performance gains across the GSM8k and BIG-bench Navigate benchmarks and achieves near-perfect accuracy on NLR problems, maintaining robustness even as variable interdependence-the number of other variables on which the value of a single variable depends-increases.”

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

Across GSM8k, BIG-bench Navigate, and the NLR benchmark, delegating deduction to Prolog yields large, reliable gains.

“Across GSM8k, BIG-bench Navigate (Srivastava et al., 2023), and our NLR benchmark, delegating deduction to Prolog yields large, reliable gains.”

• cites Srivastava et al., 2023Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

The Non-Linear Reasoning dataset (NLR) is a collection of 55 problems hand-designed by the authors to probe the generality of LLMs on out-of-distribution tasks requiring iterative, non-linear reasoning while requiring only basic arithmetic calculations.

“We introduce the Non-Linear Reasoning dataset (NLR), a collection of 55 problems hand-designed by the authors to probe the generality of LLMs on out-of-distribution tasks requiring iterative, non-linear reasoning while requiring only basic arithmetic calculations.”

Text-only GPT-4's performance on NLR falls from 100% to 0% as the degree of variable interdependence increases from 1 to 4.

“On NLR, GPT-4's performance increases significantly from as low as 8.3% to 100% on two of the three categories (Figure 3), and remains stable even as the degree of variable interdependence increases from 1 to 4-where text-only GPT-4's performance falls from 100% to 0% (Figure 4).”

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

The design of controlled relational complexity significantly impacts the model's ability to solve the problems end-to-end.

“Our experimental results show this design significantly impacts the model's ability to solve the problems end-to-end (see Section 5).”

On Navigate, all evaluated models exceed 98% with Prolog, versus substantially lower with text-only CoT.

“On Navigate, all evaluated models exceed 98% with Prolog (vs.substantially lower with text-only CoT; see Figure 2).”

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

This performance is a significant improvement compared to the performance of models prompted with CoT in text.

“As shown in Figure 2, performance exceeds 98% for all three models integrated with Prolog on the Navigate task, a significant improvement compared to the performance of models prompted with CoT in text.”

Defining variables in relation to other variables significantly impacts the end-to-end performance of LLMs in solving math word problems.

“As shown in Figure 3, the simple modification of defining variables in relation to other variables significantly impacts the end-to-end performance of LLMs in solving math word problems.”

• AssumptionRests on an assumption: The four new instances share the same setting, variables, and reasoning patterns as the original problems.

The neurosymbolic model solved nearly all math problems in all 25 attempts with very few inference retries.

“Our robustness experiments (Figure 5) confirm this: the neurosymbolic model solved nearly all math problems in all 25 attempts with very few inference retries.”

• AssumptionRests on an assumption: The four new instances share the same setting, variables, and reasoning patterns as the original problems.

Prompting GPT-4 to formulate the information encoded in the problems as Prolog predicates effectively addresses these issues.

“However, as demonstrated by Figure 3, prompting GPT-4 to formulate the information encoded in the problems as Prolog predicates, where the model's task is to encode the constraints as logical code statements rather than attempting to iteratively check the possible states against the constraints, effectively addresses these issues.”

The neurosymbolic approach (GPT-4 + Prolog) maintains consistently high performance as variable interdependence increases.

“In contrast, our neurosymbolic approach (GPT-4 + Prolog) maintains consistently high performance, demonstrating its robustness to this complexity.”

• AssumptionRests on an assumption: The four new instances share the same setting, variables, and reasoning patterns as the original problems.

text-davinci-003 and GPT-3.5 models, which have a more restricted working memory relative to GPT-4, showed the most significant improvements.

“Notably, the text-davinci-003 and GPT-3.5 models, which have a more restricted working memory relative to GPT-4, showed the most significant improvements.”

LLMs mostly fail to solve the NLR constraint satisfaction problems when prompted with chain-of-thought in text.

“Figure 3 demonstrates that LLMs mostly fail to solve the NLR constraint satisfaction problems when prompted with CoT in text.”

Integrating Prolog with text-davinci-003 and GPT-3.5 significantly improved their performance on GSM8k.

“As shown in Figure 2, integrating Prolog with text-davinci-003 and GPT-3.5 significantly improved their performance on GSM8k, highlighting the benefit of incorporating a reliable reasoning module in the inference pipeline of LLMs.”

The performance of GPT-4 also showed considerable improvement with the integration of Prolog.

“The performance of GPT-4 also showed considerable improvement with the integration of Prolog.”

GPT-4 text-only chain-of-thought performance decreases drastically as variable interdependence increases, falling from 100% to 0% on problems with four interdependent variables.

“As shown in Figure 4, the text-only CoT performance of GPT-4 decreases drastically as interdependence increases, falling from 100% to 0% on problems with four interdependent variables.”

• AssumptionRests on an assumption: The four new instances share the same setting, variables, and reasoning patterns as the original problems.

Performance exceeds 98% for all three models integrated with Prolog on the Navigate task.

“As shown in Figure 2, performance exceeds 98% for all three models integrated with Prolog on the Navigate task, a significant improvement compared to the performance of models prompted with CoT in text.”

This approach resulted in a 100% success rate in solving the problems.

“This approach resulted in a 100% success rate in solving the problems.”

For the constraint satisfaction problem in Table 1, LLMs only consider the possibility where Bob is in the ith position and Alex in the (i+5)th position, which is one of the two possible orders of Bob and Alex.

“The LLMs only consider the possibility where Bob is standing in the ith position and Alex in the (i + 5)th position of the line, which is one of the two possible orders of Bob and Alex.”

The proposed neurosymbolic approach shifts the LLM's task from deductive reasoning to mapping information in problem statements into Prolog code, offloading iterative computations to a reliable symbolic engine.

“This division of labor shifts the LLM's task from iterative computations to inferring all information-explicit or implied through common sense-and encoding it as logical code.”

• Also stated in: § 1 Introduction · plain

  “Second, we introduce a neurosymbolic approach that shifts the LLM's task from deductive reasoning to mapping information in problem statements into Prolog code, effectively offloading the iterative computations involved in navigating the solution space to a reliable symbolic engine.”

• AssumptionRests on an assumption: LLMs are proficient at understanding and extracting explicit and implicit information from problem statements.
• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

These reasoning limitations likely stem from the autoregressive architecture of transformers, which enforces sequential problem solving and constrains backtracking and error recovery.

“These limitations likely stem from the autoregressive architecture of transformers, which enforces solving problems sequentially, constraining their ability to backtrack and recover from errors (Dziri et al., 2024).”

• cites Dziri et al., 2024Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The reasoning failures diagnosed with the NLR dataset can be alleviated by the neurosymbolic method.

“We show that the reasoning failures diagnosed with the NLR dataset can be alleviated by our neurosymbolic method (Figure 1).”

Even the most advanced LLMs, including GPT-4, have a short working memory.

“Furthermore, even the most advanced LLMs, including GPT-4, have a short working memory (Bubeck et al., 2023), while reliable reasoning requires accurate and robust retrieval and integration of all relevant information.”

• cites Bubeck et al., 2023 sourceNot checked yet

  Checked before — its earlier verdict is held back until a new check runs.

Symbolic tools support reasoning about much richer types of logical and causal relationships than could be easily conveyed in natural language.

“These tools support reasoning about much richer types of logical and causal relationships than could be easily conveyed in natural language.”

Confining required operations to basic arithmetic/algebra separates evaluation of computational skill acquisition from reasoning, allowing attribution of errors to models' shortcomings in tracing multiple paths, backtracking, or limited working memory rather than missing higher-math knowledge.

“This separates evaluation of computational skill acquisition from reasoning, allowing us to attribute errors to models' shortcomings in tracing multiple paths to the solution, backtracking, or limited working memory rather than to missing higher-math knowledge.”

• AssumptionRests on an assumption: LLMs have shortcomings in tracing multiple paths to the solution, backtracking, or limited working memory.

The neurosymbolic pipeline integrates LLMs with Prolog for reliable reasoning.

“(ii) a neurosymbolic pipeline that integrates LLMs with Prolog for reliable reasoning”

• AssumptionRests on an assumption: Prolog can reliably solve systems of equations with interdependent variables, trace all possible states, and update world models.

The first design choice-prompting the LLM to perform chain-of-thought reasoning in text and logical code-helps the approach work well.

“Two specific design choices help this approach work well.First, we prompt the LLM to perform chainof-thought (CoT) (Wei et al., 2022) reasoning in text and logical code.”

Complex relational structures can be represented accurately in symbolic form.

“In this approach, complex relational structures can be represented accurately in symbolic form, and the LLM's task changes to understanding and extracting explicit and implicit information, a task it is proficient in.”

• AssumptionRests on an assumption: LLMs are proficient at understanding and extracting explicit and implicit information from problem statements.

When LLMs are prompted to generate logical code, Prolog's declarative nature reduces the load on the LLM to define variables or constraints in the correct order or generate all intermediate steps correctly, allowing a more direct mapping from natural language statements to logical code.

“When LLMs are prompted to generate logical code to solve a problem, this declarative nature reduces the load on the LLM to define the variables or constraints encoded in the problem in the correct order or generate all intermediate steps of the computation correctly, allowing for a more direct mapping of the information encoded in natural language statements to logical code.”

• AssumptionRests on an assumption: In contrast to procedural or functional programming, the declarative programming paradigm of Prolog focuses on defining what to execute and the program logic rather than specifying the detailed control flow.

Using Multiple-Try inference to rerun the model with slightly increased temperature if the Prolog code fails to execute and returning the first executable code generation helps mitigate the brittleness of symbolic programming code.

“Second, we use the Multiple-Try inference algorithm to obtain the model's logical code generation for the problems.Using this inference method, if the Prolog code generated by the LLM fails to executefoot_1 , we rerun the model with a slightly increased temperature (with a preset maximum number of attempts) and return the numerical answer from the model's first executable code generation”

• Also stated in: § 3 Our Neurosymbolic Approach · plain

  “This approach helps to mitigate the brittleness of symbolic programming code.”

LLMs struggle with the non-linear computations of solving a system of linear equations when the number of simplification and variable replacement iterations required increases, even though the mathematical scope of operations is limited to simple algebra.

“This suggests that while LLMs are adept at understanding the semantic meaning of problem statements, they struggle with the non-linear computations of solving a system of linear equations when the number of simplification and variable replacement iterations required increases, even though the mathematical scope of operations is limited to simple algebra.”

• AssumptionRests on an assumption: The four new instances share the same setting, variables, and reasoning patterns as the original problems.

Faithfully translating the game's rules into a valid program placed a higher load on the LLM's code-generation and implicit reasoning abilities.

“Thus, faithfully translating the game's rules into a valid program placed a higher load on the LLM's code-generation and implicit reasoning abilities.”

Constraints that encode multiple possibilities make these problems particularly difficult for LLMs due to the extensive non-linear reasoning required to trace and revisit all potential solutions.

“The existence of constraints that encode multiple possibilities makes these problems particularly difficult for LLMs due to the extensive non-linear reasoning required to trace and revisit all potential solutions.”

This allows the comments to encode different reasoning from the code statements, extracting necessary but unstated information to generate the correct logical code.

“This allows the comments to encode different reasoning from the code statements, extracting necessary but unstated information to generate the correct logical code (see Table 2 for examples of implicit reasoning performed by GPT-4 in the comments).”

The main limitation of the NLR dataset is scalability.

“The main limitation of the NLR dataset is scalability.”

The lower robustness in algorithmic games is anticipated because these tasks require the LLM to correctly implement the data structure for initializing and updating a world model, a complex code-generation task.

“This is anticipated, as these tasks require the LLM to correctly implement the data structure for initializing and updating a world model, a complex code-generation task.”

The paper introduces a hand-designed benchmark that targets iterative computation with controlled degrees of variable interdependence.

“We (i) introduce a hand-designed benchmark that targets iterative computation with controlled degrees of variable interdependence;”

Originally, the Navigate task required determining whether the agent returns to its starting location, inherently introducing a 50% chance of correctness due to the binary nature of the answer.

“Originally, the Navigate task required determining whether the agent returns to its starting location, inherently introducing a 50% chance of correctness due to the binary nature of the answer.”

Textual tokens embedded within the logical code enable the model to do implicit reasoning, extracting information that is not explicitly stated but must be inferred from context or common sense.

“Textual tokens embedded within the logical code enable the model to do implicit reasoning, extracting information that is not explicitly stated but must be inferred from context or common sense.”