MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs

## Abstract

Abstract Large language models (LLMs) can solve arithmetic word problems with high accuracy, but little is known about how well they generalize to problems that are more complex than the ones on which they have been trained. Empirical investigations of such questions are impeded by two major flaws of current evaluations: (i) much of the evaluation data is contaminated, in the sense that it has already been seen during training, and (ii) benchmark datasets do not capture how problem proofs may be arbitrarily complex in various ways. As a step towards addressing these issues, we present a framework for evaluating LLMs on problems with arbitrarily complex arithmetic proofs, called MathGAP. MathGAP generates problems that follow fixed proof specifications—along with chain-of-thought reasoning annotations—enabling systematic studies on generalization with respect to arithmetic proof complexity. We apply MathGAP to analyze how in-context learning interacts with generalization to problems that have more complex proofs. We find that among the models tested, most show a significant decrease in performance as proofs get deeper and wider. This effect is more pronounced in complex, nonlinear proof structures, which are challenging even for GPT-4o. Surprisingly, providing in-context examples from the same distribution as the test set is not always beneficial for performance. In particular, zero-shot prompting as well as demonstrating a diverse range of examples that are less complex than the test data sometimes yield similar or higher accuracies.

## 1 Introduction

High performance on reasoning benchmarks is often taken as evidence that transformer-based large language models (LLMs) can “reason”.
However,
many current evaluations are unreliable since it is likely that the problems they contain are present in the model’s training data (Sainz et al., ; Deng et al., ; Zhang et al., ).
Moreover, most evaluations
fail to capture that reasoning problems can be arbitrarily complex, through composition of subproofs and use of multiple rules of inference.
High accuracy on a specific set of problems in a benchmark dataset is therefore not sufficient to conclude that LLMs can generalize to more complex, unseen problems.
To obtain a more appropriate empirical measure of reasoning ability, one must evaluate on data that is *not* present in any benchmark dataset, containing proofs that are more complex than those used in training and context window alike.

Math word problems (MWPs) are one of the most frequently used testbeds for LLM reasoning. Yet there exist few, if any, systematic analyses on out-of-distribution (OOD) generalization in regards to proof complexity that avoid contamination in this domain.
We suspect that this is in part due to a lack of formalism for characterizing proof complexity, which we argue is necessary for making precise claims about generalization behavior for reasoning problems.

Figure: Figure 1: We propose MathGAP, an evaluation framework for arithmetic reasoning in which LLMs are tested on problems with proofs of arbitrary complexity. This diagram shows how problems and CoT solution annotations are generated under our formalism. The complete list of logical forms and inference rules that we consider in our experiments are given in Tables 1 and 3.1, respectively.
Refer to caption: x1.png

In this paper, we present a framework for evaluating Mathematical Generalization on Arithmetic Proofs—MathGAP.
First, we discuss how to characterize solutions to MWPs in terms of proof trees, in which the nodes are labeled with logical statements about the problem under a world-model framework (Opedal et al., ), and the edges are induced by proof steps on such logical statements.
Doing so reveals several ways of characterizing a problem’s complexity based on its proof tree, e.g., (non)linearity, depth, width, and the ordering of nodes (all defined in § 3.2).
With this formalism, we develop a method to generate problems with specified proof tree characteristics.
Because this method is based on proof trees, it also enables rich annotations in the form of ground-truth reasoning traces. More specifically, traversing the proof trees in post order, we obtain chain-of-thought (CoT; Wei et al., ) reasoning traces in an automated manner.
Fig. 1 illustrates the generation method, showing a nonlinear proof tree with depth $2$ and width $5$, in which the ordering of the sentences is given by traversing the leaf nodes in left-to-right order.
This generation method forms the backbone of MathGAP, our framework for studying OOD generalization gaps on arithmetic proofs. MathGAP avoids data contamination since the distribution of generated test problems can always be different from those in training or in context—by design.
When the performance on problems at one level of complexity hits saturation, we can flexibly generate a new set of problems that are even more complex. This is in spirit similar to Dynabench (Kiela et al., ) but, importantly, does not require human annotators.

MathGAP opens up the possibility for several new empirical investigations.(^1^11Code to generate problems with MathGAP will be publicly released with the final version.)
In the present study, we perform a systematic analysis on whether LLMs can use simple examples in context to solve more complex ones at inference.
To this end, we consider two different distributions of in-context CoT demonstrations: examples with only the simplest possible proof trees, and
a range of examples with varying complexity, akin to curriculum learning (Bengio et al., ).
We then evaluate on test sets containing problems that are increasingly more complex than the in-context examples.
The performance is compared to two baselines of in-context demonstrations, a prompt that has in-distribution examples with respect to the test set, and a zero-shot prompt.
Our study includes
Mixtral-8x7B (Jiang et al., ), Llama3-8B, Llama3-70B (Llama Team, ), GPT-3.5-Turbo, GPT-4o (OpenAI, ), and a few additional evaluations on o1-preview. We present several findings:

- •
As expected, there is a consistent decrease in performance as proof depth and width increase. The decrease is particularly notable for nonlinear problems, for which we observe a general inability of the evaluated LLMs to solve complex problems, even for GPT-4o.
- •
Generalization across orderings appears to be different, however. We conduct experiments where we move sentences to the front of the problem and find that the problem is easiest for LLMs if the sentence is moved from near the beginning or end, rather than from the middle of the problem. This is surprising since one would expect a monotonically decreasing relationship between accuracy and the distance of the movement.
- •
We see no clear relationship between in-context distribution and performance. Contrary to our expectations, in-distribution examples are not always beneficial for performance, as compared to zero-shot. Demonstrating a range of examples with varying complexity is usually preferable to demonstrating simple examples, suggesting that LLMs benefit from a diverse prompt.
- •
The o1-preview model outperforms the other models on nonlinear problems.
Yet, we are able to create a test set of which it solves only 5%—demonstrating that MathGAP can be future-proof.

## 2 Related Work

##### Data contamination.

Machine learning, broadly, is the study of algorithms that can learn from data, and generalize to *unseen* data.
Machine learning models must therefore be evaluated on unseen test sets. As it turns out, modern-day LLMs are not being properly evaluated in this regard: Much of the data they are evaluated on has already been used during model training, both labeled (Dodge et al., ; Deng et al., ) and unlabeled (Elazar et al., ). Researchers have raised serious concerns about these issues (Jacovi et al., ; Sainz et al., ). For arithmetic reasoning specifically, Zhang et al. () recently found evidence that the widely used GSM8k benchmark (Cobbe et al., ) is contaminated, and presented evaluations on a new dataset which is not publicly released. MathGAP mitigates data contamination by creating new, more complex synthetic test sets.

##### Generalization on reasoning tasks.

Generalization to data from a *different* distribution (i.e., OOD data) is a core problem in machine learning and has been studied extensively also in the context of LLM reasoning
(Schwarzschild et al., ; Razeghi et al., ; An et al., ; Kudo et al., ; Liu et al., ; Saparov & He, ; Zhang et al., ; Thomm et al., ).
While LLMs’ performance on OOD data can be improved by various techniques (Anil et al., ; Hu et al., ), generalization to problems of arbitrary complexity under a set of known inference rules is still an open problem.
For instance, Dziri et al. () demonstrate that the accuracy of transformer-based LLMs on compositional generalization rapidly approaches zero as the complexity of the problem increases—regardless of in-context guidance.
Saparov et al. () focus on theorem proving for logical reasoning, presenting a systematic analysis on generalization ability of LLMs with respect to proof size and diversity of inference rules.
Our paper contributes to this literature by providing an evaluation framework to systematically study OOD generalization in regards to arithmetic proof complexity.

##### Evaluation on MWP benchmarks.

It is common to treat MWPs as a testbed for studying reasoning abilities of LLMs
(Cobbe et al., ; Patel et al., ; Fu et al., ; Shakarian et al., ; Stolfo et al., ; Zong & Krishnamachari, ); such problems are useful because solving them requires several distinct skills, yet, they remain conceptually simple (Stern, ).
However, we are not aware of many studies that investigate generalization in regards to problem complexity in this domain.
Our study presented in § 5 relates to Hase et al. (), who fine-tune LLMs on easy problems and evaluate them on harder ones at inference.
Their complexity metrics focus on problem length, but do not capture
*how* a longer reasoning problem gets more complex (i.e., the shape of the proof tree).
Moreover, they evaluate on GSM8k, which is contaminated. Mishra et al. () proposed a method that uses GPT-4 to generate new synthetic problems from symbolic specifications. Their approach is scalable, but using an LLM to generate problems may (i) introduce bias (Boguraev et al., ; Opedal et al., ) and (ii) produce problems that are unfaithful to their specifications. Mirzadeh et al. () recently performed evaluations on a version of GSM8k in which the variable names and numbers have been altered, and found that LLMs are surprisingly sensitive to such substitutions. MathGAP is more general; while it allows for such substitutions, our main goal is to vary the proof structures.

**Table 1: Examples of logical forms. A logical form consists of a predicate and a set of properties which is specific to that predicate, given here in separate columns. Each logical form induces a set of natural language sentences which preserve its semantics.**
| Logical Form | Example Templates | Example Sentences |  |
| --- | --- | --- | --- |
| Predicate (abbr.) | Properties |  |  |
| container | (agent=a, | [a] has [q] [u]s of [k] [e]s. | Alice has 5 kilograms of red apples. |
| (cont) | quantity=q, |  |  |
|  | entity=e, | [a] owns [q] [u]s of [k] [e]s. | Alice owns 5 kilograms of red apples. |
|  | attribute=k, |  |  |
|  | unit=u) |  |  |
| comparison | (agentA=a, | [b] has [q] fewer [e]s than [a]. | Bob has 3 fewer apples than Alice. |
| (comp) | agentB=b, |  |  |
|  | quantity=q, | [a] has [q] more [e]s than [b]. | Alice has 3 more apples than Bob. |
|  | entity=e) |  |  |
| transfer | (receiver_agent=b, | [a] gave [b] [q] [e]s. | Alice gave Bob 3 apples. |
|  | sender_agent=a, |  |  |
|  | quantity=q, | [b] got [q] more [e]s from [a]. | Bob got 3 more apples from Alice. |
|  | entity=e) |  |  |
| partwhole | (whole_agent=$\hskip 1.00006pt\land\hskip 1.00006pt_{i=1}^{n}\texttt{a}_{i}$, | [$\texttt{a}_{1}$], …, and [$\texttt{a}_{n}$] combine the [f]s that they have. | Alice and Bob combine the fruits that they have. |
|  | part_agent1=a1, |  |  |
|  | … |  |  |
|  | part_agentn=an, |  |  |
|  | whole_entity=f, |  |  |
|  | part_entity=e) |  |  |
| comp-eq | (agentA=a, | The number of [e]s that [c] has more than [d] is equal to the difference between the number of [e]s that [a] and [b] have. | The number of apples that Charlie has more than David is equal to the difference between the number of apples that Alice and Bob have. |
|  | agentB=b, |  |  |
|  | agentC=c, |  |  |
|  | agentD=d, |  |  |
|  | entity=e) |  |  |

## 3 A Formal Treatment of Math Word Problems

We aim to generate new problems of arbitrary complexity, so we require a formalism for characterizing complexity in a precise manner.
First, we explain how the semantics expressed in math word problems can be written as sequences of logical forms (§ 3.1).
We then show how to apply inference rules on these logical forms to deduce new ones (§ 3.2).
This leads to a view of problem solutions as proof trees, the structure of which can be used to characterize the reasoning required to solve the problem.

### 3.1 Math word problems as logical forms

Each math word problem is represented as a sequence of logical forms under the formalism from Opedal et al. (; ).
A logical form is a statement about a truth in the world that is being described by the problem, representing some arithmetic relationship between the number of entities possessed by one or several agents. Such statements can refer to the number of entities an agent has, how many more entities an agent has relative to another, the action of an agent giving their entities to another agent, etc. Formally, a logical form represents the semantics of a single sentence and consists of a predicate that takes a set of properties as arguments.
Every logical form has an agent property, an entity property, and a quantity property. Other, optional, properties include unit and attribute.
We define a world model as a sequence of logical forms that align with the sentences of a problem text, thus, representing the semantics of the entire problem. See Fig. 5 for the world model representation of the problem from Fig. 1.

For a given predicate and set of properties, we write predicate(property1=x, property2=y, ...) to express a logical form. Property names are, however, often omitted for brevity, as in predicate(x, y, ...).
There are two types of predicates: (i) those that represent ownership over some entity by an agent, called container (abbreviated cont), and (ii) those that represent arithmetic relationships between two sets of properties. The relationship predicates correspond to arithmetic concepts and are based on a taxonomy from the learning sciences (Riley et al., ); we use transfer , comparison (abbreviated comp), partwhole and comp-eq.(^2^22The transfer and part-whole concepts are usually called *change* and *combine*, respectively, in learning science literature (Nesher et al., ). The comp-eq predicate was introduced in this paper in order to construct nonlinear problems of arbitrary length.)
Table 1 gives concrete example sentences for logical forms with each of these predicates.
In words, a cont logical form expresses the fact that an agent owns a particular entity in some quantity (e.g., *“Alice has 5 apples”*). A comp logical form expresses how much more some agent owns of a particular entity than some other agent (e.g., *“Bob has 3 fewer apples than Alice”*). A transfer logical form expresses the transfer of a certain quantity of an entity from one agent to another (e.g., *“Alice gave Bob 3 apples”*). A partwhole logical form expresses a superset relation between the combined entities of several agents (e.g., *Alice and Bob combine their fruits*).
Finally, a comp-eq logical form expresses that the quantity of a particular comp between two agents is equal to that of a comp between two other agents (e.g., *“The difference between the number of apples that Alice and Bob have is the same as the difference between the number of apples that Charlie and David have”*).

The logical forms in the world model of a math problem are separated into the body and question. The question is a single logical form that appears at the end of the world model. It is characterized by having a placeholder variable instead of an explicit quantity, which corresponds to the correct answer to the problem.
For example, the interrogative sentence “How many apples does Alice have?” is represented by the question cont(Alice, q, apples), where q is a placeholder variable.
The body consists of all logical forms in the world model which are not questions. The answer to a problem is the logical form declared by the question with the correct numerical quantity substituted into its placeholder variable, although we will sometimes refer to only the correct numerical quantity as the answer as well.

**Table 2: Inference rule templates (left) with corresponding examples of rule applications in natural language (right). The variables a, b, c, d refer to agents, q, q1, q2 refer to quantities, and e, f refer to entities. Attribute and unit properties are excluded here, but analogous rules exist in which they are present. All inference rules are commutative except the transfer rule; see footnote 3. Rule applications of an inference rule with premises $L_{1},L_{2},\dots,L_{N}$ and consequent $L$ are written as $L^{\prime}_{1}.L^{\prime}_{2}.\,\dots\,.L^{\prime}_{N}.\vdash L^{\prime}.$, where $L^{\prime}$ is a natural language expression for the logical form $L$. Axioms are formed from the facts stated in the problem, as illustrated in Fig. 1.**
| Inference Rules | Example Sentences |
| --- | --- |
| \proofSkipAmount\AxiomC<br>cont(a, q1, e) \AxiomCcomp(b, a, q2, e)<br>\BinaryInfCcont(b, q1 + q2, e)<br>\DisplayProof | Alice has 3 apples. Bob has 2 more apples than Alice. $\vdash$ Bob has 5 apples. |
| \proofSkipAmount\AxiomC<br>cont(a, q1, e) \AxiomCtransfer(a, b, q2, e)<br>\BinaryInfCcont(a, q1 + q2, e)<br>\DisplayProof | Alice has 3 apples. Bob gave 2 apples to Alice. $\vdash$ Alice has 5 apples. |
| \proofSkipAmount\AxiomC<br>cont(a, q1, e) \AxiomCcont(b, q2, e)<br>\BinaryInfCcomp(b, a, q2 - q1, e)<br>\DisplayProof | Alice has 3 apples. Bob has 5 apples. $\vdash$ Bob has 2 more apples than Alice. |
| \proofSkipAmount\AxiomC<br>cont(a1, q1, e) $\dots$ cont(an, qn, e)  partwhole($\hskip 1.00006pt\land\hskip 1.00006pt_{i=1}^{n}\texttt{a}_{i}$, a1, $\dots$, an, f, e)<br>\UnaryInfCcont($\hskip 1.00006pt\land\hskip 1.00006pt_{i=1}^{n}\texttt{a}_{i}$, $\sum_{i=1}^{n}\texttt{q}_{i}$, f)<br>\DisplayProof | Alice has 3 apples. Bob has 5 apples. Alice and Bob combine their fruits. $\vdash$ Alice and Bob have 8 fruits. |
| \proofSkipAmount\AxiomC<br>cont(a, q1, e) \AxiomCcomp(d, c, q2, e) \AxiomCcomp-eq(b, a, d, c)<br>\TrinaryInfCcont(b, q1 + q2, e)<br>\DisplayProof<br>\proofSkipAmount | Alice has 7 apples. David has 2 more apples than Charlie. The number of apples that Bob has more than Alice is the same as the difference between the number of apples that David and Charlie have. $\vdash$ Bob has 9 apples. |

### 3.2 Chain-of-thought solutions as proof trees

Solving math word problems is a form of deductive reasoning, where the correct answer follows necessarily from what is stated in the text through a combination of rules of arithmetic and world knowledge.
We use such derivations, called proofs, to characterize the structure of problems.
The proofs in our setup are analogous to those found in other deductive systems, e.g., of first-order logic.

We want to formally reason over the logical forms introduced in § 3.1. To that end we introduce inference rules,
which are used to prove new logical forms from previously-known ones.
A proof step, written as{prooftree}
\AxiomC$L_{1}$
\AxiomC$L_{2}$
\AxiomC$\cdots$
\AxiomC$L_{N}$
\RightLabel,
\QuaternaryInfC$L$
is an instance of an inference rule where the conclusion logical form $L$ is deduced from premises $L_{1},L_{2},\dots,L_{N}$. An axiom is a proof step without premises. The axioms of a math word problem are the logical forms in the body of its world model; that is, all logical forms excluding the question.
§ 3.1 lists the inference rules that we use, along with examples of how they may be expressed in natural language.(^3^33The list is not exhaustive as additional variations on the rules exist. In particular, the logical forms may contain attributes and units (such as the cont examples in Table 1), and the premises can be given in any order for all inference rules (i.e., they are commutative) except the one using transfer . The transfer rule is non-commutative since it involves a notion of time. For instance, “Alice (now) has 5 apples. Alice ate 2 apples.” does not imply the same conclusion as “Alice ate 2 apples. Alice (now) has 5 apples.” Moreover, note that the third inference rule listed in § 3.1 is commutative, since swapping the two premises yields the conclusion comp(a, b, q${}_{1}-\texttt{q}_{2}$, e), which is equivalent to comp(b, a, q${}_{2}-\texttt{q}_{1}$, e).)
For instance, consider the two logical forms cont(Isabella, 17, apple) and comp(Lucy, Isabella, 10, apple) from Fig. 1, representing the facts that Isabella has 17 apples and Lucy has 10 more apples than Isabella, respectively. The proof step
{prooftree}
\AxiomCcont(Isabella, 17, apple)
\AxiomCcomp(Lucy, Isabella, 10, apple)
\RightLabel,
\BinaryInfCcont(Lucy, 17 + 10, apple)
lets us deduce the logical form cont(Lucy, 27, apple), i.e., that Lucy has 27 apples.

A math word problem can be solved by applying inference rules until the answer to the problem has been proved.
Formally, a proof tree is a rooted ordered tree where each node is labeled with a logical form $L$, which is the conclusion of a proof step with premises $L_{1},\dots,L_{N}$, matching the labels of the child nodes in the same order. Leaf nodes are thus labeled with axioms.
A proof of a *particular* problem is a proof tree where the labels on the leaf nodes are logical forms in the body of the problem, and the label at the root is the answer to the problem.
The tree shown in Fig. 1 illustrates a proof of the problem given in the same figure.

##### Proof complexity.

We seek a systematic way to analyze whether LLMs can generalize from simple to more complex proofs. The definition of proof given above gives rise to several ways of characterizing reasoning, out of which we consider four: linearity, depth, width, and ordering.
These are defined below.

We say that a proof tree is linear if every one of its inference rules takes at most one premise that is not an axiom, and nonlinear otherwise. In other words, every step in the solution to a linear problem only uses at most one fact not directly present in the problem.
The proof tree given in Fig. 1 is nonlinear because the proof step that deduces the answer uses two premises that are not themselves axioms.
The depth of a proof tree is defined as its height, i.e., the maximum path length from the root node to any leaf node.
Next, the width of a proof tree is the number of leaf nodes, or axioms, that it contains. The proof tree in Fig. 1 thus has depth 2 and width 5. In words, this means that the answer is two proof steps “away” from any of the axioms and that the problem has five (declarative) sentences.(^4^44In this paper, the width of the proof tree matches the number of declarative sentences (i.e., all sentences except the question) in the corresponding problem since we restrict the logical forms and sentences to be one-to-one. In general, that need not be the case since a single sentence could be written as a conjunction of several logical forms. One could also imagine problems that have irrelevant sentences, which do not represent any logical form at all.)
Lastly, we define the canonical ordering to be the ordering of leaf nodes as visited left-to-right.
Note that the sentences in the natural language annotation from Fig. 1 follow the canonical ordering of the proof tree. Informally, this is the easy way of ordering the sentences in the problem since it matches the ordering of the proof steps. However, there exist multiple alternative orderings in general. In particular, given a proof tree that only contains commutative inference rules (see footnote 3), all orderings of the leaf nodes are valid.
For instance, swapping the ordering of the first two leaf nodes in the tree in Fig. 1 yields a problem with the same proof.

## 4 Evaluation Framework

Equipped with the formalism explained in § 3, we propose an evaluation framework that tests LLMs on MWPs of arbitrary proof complexity, called MathGAP. In § 4.1, we explain the generation method behind MathGAP. We then outline how this method can be used for OOD evaluation in § 4.2.

### 4.1 Generation Method

We propose a method for synthetic generation of problems and their CoT solution explanations.
It consists of three high-level steps: (i) sample a proof tree, (ii) map the logical forms at the leaf nodes into a natural language problem, and (iii) map the proof steps into a CoT solution.(^5^55Jin et al. () presents a related method for generating causal reasoning problems.) Fig. 1 gives an illustration of these steps; note that the agent properties are abbreviated for brevity.

In detail, the procedure is as follows: We first sample a logical form at the root of the proof tree.
We then sample a specific inference rule as well as its premises. We recursively repeat this procedure for each premise until a predetermined stopping criterion has been reached, resulting in a proof tree. The stopping criterion is user-specified; it could be, e.g., when the tree has reached a certain depth or width. The categorical properties for the logical forms (i.e., agent, entity, attribute, and unit) are sampled uniformly at random from handwritten vocabularies. The quantities are sampled uniformly at random from a user-specified range; in our study presented in § 5 we use $2{-}20$.

We then traverse the leaves of the proof tree in some order and convert each into a sentence via a natural language template, forming the text corresponding to the body of the problem. The default order follows the proof tree’s canonical ordering, but other orders are possible as well.
The sentences are sampled uniformly at random from a predefined set of templates; some example templates are given in Table 1.
The question is converted from the logical form at the root of the proof tree and is sampled from a set of interrogative sentences.

In the final step, we generate the CoT annotation for the problem. We first obtain a sequential ordering of the CoT proof steps by visiting the nodes in the proof tree with a post-order traversal.(^6^66Note that the choice of traversing the nodes in post order corresponds to applying each inference rule as soon as all of its premises are available. In addition, post-order traversal visits the axioms in the canonical ordering. Alternative orders of tree traversal would violate at least one of these constraints.)
We then convert each proof step into a sentence via a natural language template. The templates used for the axioms are identical to those used in the body of the problem text. In other words, the proof steps corresponding to axioms simply repeat the relevant part of the problem text. For the other proof steps, we have templates that are designed to explain the computation step that is performed.
Fig. 1 illustrates the mapping between nodes in the proof tree and sentences in the CoT annotation. For instance, the third sentence in Fig. 1 explains the conclusion cont(Lucy, 27, apple), which is deduced from the two leftmost nodes in the tree: “So Lucy has $17+10=27$ apples”.

Our pipeline is similar to the one proposed by Opedal et al. (), except that we use a recursive procedure to generate each proof step starting at the root, instead of a sequential one. This is a more general approach that also enables generation of nonlinear proofs.(^7^77The comp-eq rule enables the generation of nonlinear proof trees with arbitrary depth and is not included in the list of relations from Opedal et al. ().)

### 4.2 MathGAP: Mathematical Generalization on Arithmetic Proofs

With the generation method just described, we can generate new synthetic problems where we control for the structure of the proof and its complexity.
MathGAP can be used for various forms of systematic studies on arithmetic reasoning; here, we focus on OOD generalization. Specifically, we can select a family of problems of interest (e.g., linear problems under comp inference rules) and generate a train-test split of problems for which the problems in the test set are more complex than those in the training set (e.g., containing problems with deeper proofs).

The generation method can be flexibly adapted to fit specific studies. One can add new logical forms and inference rules, restrict the choice of existing ones during sampling, or create logical forms for irrelevant sentences (Shi et al., ). One can also vary the text templates for the logical forms and inference rules, the vocabularies for agents, entities, attributes, and units, and the range of numbers from which the quantities are sampled. In addition, one may increase linguistic diversity
by incorporating a last step in which a language model paraphrases the templated texts, or, alternatively, use a procedure like the one proposed by Mishra et al. (). In our study, we do not perform such paraphrasing, since we want to guarantee that the sentences are faithful to the proof trees from which they are generated. However, future studies using MathGAP may choose to prioritize differently.

## 5 Experiments

We apply MathGAP to study how LLMs generalize from proof demonstrations of simple problems in context to solve problems of higher complexity at inference. We test OOD generalization through several sets of experiments: depth generalization for linear problems (§ 5.1), width generalization for linear problems (§ 5.2), depth generalization for nonlinear problems (§ 5.3), and generalization to permutations (§ 5.4). We are also interested in how the choice of the distribution of problems provided in context affects performance, which is often not obvious (Min et al., ; Turpin et al., ).

##### Experimental setup.

For each set of experiments, the general experimental setup is as follows: We generate five test sets of different degrees of complexity with 400 problems in each. We then generate model predictions for the problems in these test sets under four different prompts: (i) A *zero-shot* baseline prompt, which contains only the test problem;
(ii) A prompt of *primitive* examples, in which all problems contain only one proof step of the same inference rule that is used in the test problem; (iii) A prompt of examples within a *range* of complexities, all of which are simpler than the test problem; (iv) An *in-distribution* baseline prompt, containing examples that are of the same complexity as the test problem.

Note that prompts (i) through (iii) evaluate in-context OOD generalization, since the test examples are from a distribution that is different from that of the in-context examples.
For prompts (ii) through (iv) we generate a new set of in-context examples for every test problem. This is done in order to avoid bias in the results towards any particular set of examples. We set the number of examples to 12, except for the experiments on nonlinear problems for which we use 5.(^8^88We use fewer in-context examples for nonlinear problems since the number of sentences in a nonlinear problem increases exponentially with depth. The number 12 was deemed large enough so that additional examples would have a negligible positive impact on performance; see, e.g., Agarwal et al. (, Fig. 7).)
Importantly, the in-context problems are provided together with their CoT solution annotations, as generated through the MathGAP pipeline. They are written out using the pattern “*Q:* {problem}\n*A:* {CoT solution}\n”. For prompt (iii), we make sure that there is at least one problem of every complexity in the range. This prompt can be viewed as a form of in-context curriculum learning (Bengio et al., ),(^9^99Related approaches have been explored in previous work (Li et al., ; Liu et al., ).) except that we randomize the ordering of the examples rather than arranging them in increasing order of complexity. This is done since in-context orderings can have a large effect on performance (Lu et al., ), and we do not want our results to overfit to any particular ordering.

Responses are generated using greedy decoding and a maximum length of 4,096 tokens. Model predictions are obtained by extracting the last number occurring in the model’s generated output.
We report answer accuracies and compute 95% confidence intervals using bootstrap sampling (Efron, ).
We evaluate the following models on all test sets: Mixtral-8x7B (Jiang et al., ), Llama3 with 8B and 70B parameters (Llama Team, ), GPT-3.5 Turbo and GPT-4o (OpenAI, ).(^10^1010The maximum context windows for these models are 65k, 8k, 8k, 16k, 128k, respectively. Combined with a maximum number of output tokens of 4,096, the models have a theoretically sufficient context size to solve all test problems. The largest test problems (nonlinear depth 6) have around 2.5k tokens, including CoT annotation. For the OpenAI models, we used “gpt-3.5-turbo-0125” and “gpt-4o-2024-05-13” as the model ids for all experiments.)

Figure: Figure 2: Answer accuracies for generalization to increasing depth and width for linear problems, across models and in-context distributions. Depth is increased using inference rules involving comp and transfer . Width is increased using partwhole.
Refer to caption: x2.png

### 5.1 Linear Depth Generalization

##### Problem sets.

We consider linear problems using both comp and transfer .
The five test sets consist of problems with depths between $6{-}10$. As such, the examples provided in the range of setting (iii) described above have depths between $1{-}5$. We give an example of a problem with depth $6$ in § B.1.

##### Results.

We illustrate the results in the top and middle rows of Fig. 2. As expected, we observe a decreasing trend in performance as depth increases, for all in-context distributions.
Curiously, GPT-3.5-Turbo is the only model for which adding in-context examples consistently leads to improvements.
For the majority of cases, performance tends to be larger when providing a range of examples of varying complexity as compared to only primitive examples.
The ranged OOD cases often show comparable performance to that of the in-distribution context, suggesting that these models benefit from demonstrations of how problems of varying complexity are solved.
Llama3-8B is an outlier in that its solving accuracy for in-distribution context is (substantially) lower as compared to other prompts. When inspecting the model outputs, we see that the model often fails to answer the inference question, recognizing instead that it has been provided a sequence of in-context examples. This could potentially be a consequence of how Llama3 is trained, using smaller context windows for the initial stages of pretraining (Llama Team, ).
Finally, we note that GPT-4o and the larger Llama3 model show close to perfect performance across all test sets.

### 5.2 Linear Width Generalization

##### Problem sets.

To test generalization to greater proof width, we use partwhole problems with a fixed depth of $1$. The five test sets have widths between $6{-}10$ and the width of the problems in setting (iii) described above have widths between $1{-}5$.

##### Results.

The results are shown in the bottom row of Fig. 2.
For GPT-3.5 and Mixtral-8x7B, we observe that providing in-context examples improves accuracy over zero-shot in most cases. As for linear depth generalization, it seems that having a range of OOD examples of varying complexity is superior to only including primitive examples. Llama3-8B exhibits worse performance with in-distribution context here as well. In general, for the Llama models, adding OOD in-context examples usually leads to lower performance over zero-shot.
Apart from GPT-3.5-Turbo, the performance is generally lower as compared to a deep problem with the same number of sentences (§ 5.1), often with a sharper decreasing trend. Such is the case even for Llama3 70B, which performed almost perfectly in the linear depth setting. This would suggest that it is more difficult to generalize in terms of width than in terms of depth. Again, GPT-4o demonstrates near perfect performance across all test sets.

Figure: Figure 3: Answer accuracies for generalization to increasing depth and width for nonlinear problems, across models and in-context distributions. Depth is increased using inference rules involving comp and comp-eq . The in-distribution contexts were too large to fit in the prompts for the Llama3 models and GPT-3.5 Turbo at some of the higher depths. App. C shows additional results on o1-preview.
Refer to caption: x5.png

### 5.3 Nonlinear Depth Generalization

##### Problem sets.

We generate test datasets containing nonlinear problems with comp and comp-eq , having the same form as the problem in Fig. 1. Another example is shown in § B.2. We generate a test set for each depth between $3{-}6$. Thus, the ranged OOD context setting contains examples of depths between $1{-}2$.

##### Results.

The results are shown in Fig. 3. All models exhibit a performance trend that tends to zero as depth increases, albeit at different rates.
For Mixtral-8x7B, Llama3-8B, and GPT-3.5 Turbo, the performance decreases rapidly across all context modes. These models benefit from in-distribution contexts for low depths, and in some cases, from a range of OOD examples.
Llama3-70B and GPT-4o are more robust to this type of OOD distribution shift,(^11^1111Note that GPT-4o performs better on depth 6 problems than depth 5 problems under the in-distribution prompt. Although we provided the same model id as in the other cases—which according to the documentation points to the original “gpt-4o-2024-05-13” snapshot—this particular test was performed at a later point in time.) but for the deepest problems, their performance tends to zero as well.
Moreover, it is worth noting that, for many cases, providing in-context examples does not significantly improve performance over zero-shot. On the other hand, for lower depths, it is usually beneficial to provide in-distribution contexts.
We perform an additional analysis on o1-preview in App. C.

### 5.4 Order Generalization

##### Problem sets.

LLMs are known to be sensitive to changes in the order of axioms in logical and mathematical reasoning problems (Chen et al., ; Eisape et al., ). Here, we present a systematic analysis of their sensitivity to a particular form of order permutation. We consider linear, left-leaning proof trees using comp that have depth 5, and generate problems that deviate from the canonical, left-to-right order of the leaf nodes. In particular, we pick one of the leaf nodes to visit first, and then visit the remaining leaf nodes in left-to-right order. This has the effect of moving one of the sentences in the canonically-ordered problem text to the beginning of the problem. We characterize complexity as the distance of the movement, with the hypothesis that a greater movement from a canonical ordering constitutes a more difficult problem.
We create five test sets with movement distances between $1{-}5$. We do not include a primitive OOD in-context distribution, the notion of a primitive problem is ill-defined in this case. The range prompt includes movements of all distances between $1{-}5$ except the one present in the test set.

Figure: Figure 4: Answer accuracies for generalization to permutations, across models and in-context distributions. We measure complexity as the distance of the movement of a sentence to the beginning of the problem, as compared to its position in the canonical ordering of the problem.
Refer to caption: x6.png

##### Results.

The results are shown in Fig. 4. First, note that all models show lower performance on perturbed problems as compared to non-perturbed ones (compare to Fig. 2). Second, there is a nonlinear relationship between accuracy and distance of the movement, in contrast to the monotonically decreasing relation we expected. More specifically, the performance is the highest for the problems where the sentence is moved from near the beginning or the end of the problem.(^12^1212This is consistent with findings on retrieval-augmented generation, for which models are better at using information that occurs near the beginning or end of the prompt (Liu et al., ).) In addition, including in-context examples gives a larger boost in performance for short and long movements, as compared to medium-length ones.

## 6 Conclusion

In this paper, we introduced MathGAP, a framework for evaluating LLMs on math word problems of arbitrary arithmetic proof complexity. MathGAP can flexibly generate synthetic arithmetic word problems with controllable proof tree characteristics. Importantly, this enables studies of OOD generalization that avoid issues of data contamination, since a train-test split where the distributions are different can be created programmatically. In particular, the test set can be made arbitrarily more complex than the training set.
We apply MathGAP to study whether LLMs can learn from simple examples in context to solve more complex problems in a test set. All LLMs tested show a decrease in performance as proof complexity increases through depth and/or width. We also find that LLMs are sensitive to the order in which sentences are presented in a particular manner: A problem is harder if a sentence is moved from the middle of the problem, as compared to the beginning or end. We find no clear relationship between the distribution of in-context examples and performance; zero-shot or OOD contexts sometimes yield performance higher than or comparable to in-distribution contexts.
Finally, we demonstrate that we can use MathGAP to construct problems that are challenging even for state-of-the-art reasoning models like OpenAI o1—see App. C.

### Limitations

Although we make sure to sample from a wide range of agent names, entities, attributes, and units, and include multiple templates for the predicates, future work may investigate how our findings generalize to distributions of problems with higher linguistic diversity.
It is also beyond the scope of the present study to consider problem texts in languages other than English; however, it is straightforward to extend MathGAP to other languages.
In addition, we cannot guarantee that the distributions of our generated problems are different from those of any potential internal data-generating mechanisms from Meta or OpenAI. However, we deem it to be unlikely that they use a similar formalism as we do here, and it gets increasingly unlikely that problems are similar as complexity increases.

While the more complex nonlinear problems are indeed challenging even for the most capable models, we note that the main purpose of our study was not to create a challenging evaluation set for state-of-the-art LLMs. If that is the goal, one could create harder problems by combining several inference rules (e.g., including the rate concept; Opedal et al., ), designing a wider variety of proof tree topologies, and presenting the axioms in arbitrary orderings. It is also possible to create more syntactically complex templates and use numbers on which it is more challenging for models to perform arithmetic (Razeghi et al., ).

Finally, it is hard to make a direct comparison between the difficulty of linear and nonlinear problems, since they use different inference rules. In particular, nonlinear proofs contain comp-eq predicates, which are not present in linear proofs.

#### Acknowledgments

We thank Alessandro Stolfo, Shehzaad Dhuliawala, Yanick Zengaffinen, and Yilmazcan Ozyurt for useful feedback and discussion. Andreas Opedal acknowledges funding from the Max Planck ETH Center for Learning Systems.

## Appendix A Example of a World Model

Fig. 5 gives an example problem text along with its world model.

Figure: Figure 5: World model (right) of a math word problem (left). Each sentence in the problem text is represented by a logical form which consists of a predicate with property arguments. The logical forms in the body are used as axioms in the proof of the problem, as shown in Fig. 1. The sentences and logical forms labeled (1) through (5) are the body of the problem, (6) is the question and (7) is the answer.
Refer to caption: x7.png

## Appendix B Example Problems

In this section we provide example problems for each set of experiments (§§ 5.1, 5.2, 5.3 and 5.4).

### B.1 Example linear comparison problem (depth 6)

Jackson has 16 red bottles of soap. Jackson has 10 more red bottles of soap than Abigail. Joseph has 18 more red bottles of soap than Abigail. Joseph has 14 fewer red bottles of soap than James. Michael has 2 more red bottles of soap than James. Ryan has 16 fewer red bottles of soap than Michael. Mia has 10 more red bottles of soap than Ryan. What is the number of red bottles of soap that Mia has?

### B.2 Example nonlinear comparison problem (depth 3)

Ella has 11 yellow plates. Ella has 19 fewer yellow plates than Jacob. Evelyn has 16 yellow plates. Daniel has 10 yellow plates. The number of yellow plates that Emma has more than Jacob is the same as the difference between the number of yellow plates that Evelyn has compared to Daniel. Lucy has 2 yellow plates. Amelia has 6 more yellow plates than Lucy. Layla has 17 yellow plates. Layla has 13 fewer yellow plates than Sophia. The number of yellow plates that Emma has more than Henry is the same as the difference between the number of yellow plates that Amelia has compared to Sophia. What is the number of yellow plates that Henry has?

### B.3 Example partwhole width problem (width 7)

Emily has 5 apples. Lily has 8 bananas. Abigail has 9 bananas. Benjamin has 11 grapes. Christopher has 20 apples. Mila has 16 grapes. Sophia has 11 watermelons. If everyone sums up the fruits that they have, how many fruits does everybody have in total?

### B.4 Permuted problems

#### Canonically ordered problem text

Nicholas has 19 computers. Lucy has 6 fewer computers than Nicholas. Harper has 6 fewer computers than Lucy. John has 10 more computers than Harper. Abigail has 15 fewer computers than John. Abigail has 12 fewer computers than Logan. How many computers does Logan have in their collection?

#### Permuted problem text (distance 1)

Lucy has 6 fewer computers than Nicholas. Nicholas has 19 computers. [Original Position] Harper has 6 fewer computers than Lucy. John has 10 more computers than Harper. Abigail has 15 fewer computers than John. Abigail has 12 fewer computers than Logan. How many computers does Logan have in their collection?

#### Permuted problem text (distance 3)

John has 10 more computers than Harper. Nicholas has 19 computers. Lucy has 6 fewer computers than Nicholas. Harper has 6 fewer computers than Lucy. [Original Position] Abigail has 15 fewer computers than John. Abigail has 12 fewer computers than Logan. How many computers does Logan have in their collection?

#### Permuted problem text (distance 5)

Abigail has 12 fewer computers than Logan. Nicholas has 19 computers. Lucy has 6 fewer computers than Nicholas. Harper has 6 fewer computers than Lucy. John has 10 more computers than Harper. Abigail has 15 fewer computers than John. [Original Position] How many computers does Logan have in their collection?

## Appendix C Additional Analysis on OpenAI o1

Fig. 6 shows additional results on the OpenAI o1-preview model, “o1-preview-2024-09-12”, evaluated on the nonlinear test sets. We only used zero-shot prompting due to the high costs of performing inference with o1-preview. Using a simple, straightforward prompt is also consistent with OpenAI’s current recommendations. We see that the o1 model shows superior performance to all models from the main text. However, as with the other models, the performance decreases as complexity increases.

Importantly, we note that performance can be improved by increasing the limit on the number of output tokens. The results presented in Fig. 6 used a token limit of 4,096, like the experiments in the main paper. We compared the effect of the token limit on an additional test set of 400 nonlinear problems with depth 7. With a token limit of 4,096, the model could only answer $0.25\%$ of the problems correctly. However, with a token limit of 10,000, it answered $76.5\%$ of the problems correctly. These results are noteworthy and suggests that the new inference technique used by the o1 model is highly effective in decomposing complex problems into smaller steps.

To test the model’s limits, we performed a final evaluation on a subset of 100 of the depth 7 problems where the sentences in each problem were *randomly ordered*. Recall from § 3.2 that permuting the sentences in random order is valid since all the inference rules used in these problems are commutative. In this experiment, we allowed 25,000 output tokens, which is the current recommendation by OpenAI. On this set, the answer accuracy was only $5\%$. Thus, we conclude that MathGAP is future-proof in the sense that it can generate problems on which current state-of-the-art models fail. We stress, however, that the aim of this paper is not to construct a challenging test set for state-of-the-art models; there are several other ways that MathGAP can be used to create problems that might be even more difficult.

Figure: Figure 6: Answer accuracies for generalization to increasing depth and width for nonlinear problems for OpenAI o1-preview under zero-shot prompting.
Refer to caption: x8.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Have you considered incorporating paraphrasing techniques or using LLMs to generate more diverse linguistic expressions to increase variety and challenge the models? Incorporating more arithmetic relations, irrelevant information, larger numbers, or units to enrich tasks could help increase the diversity as well. 

How do you ensure that the proof tree structures accurately reflect LLMs' reasoning processes? Is there a risk that models might not utilize the intended inference paths?

Can you provide more detailed analyses to determine whether performance drops are due to arithmetic computation errors, logical reasoning mistakes, or other factors?
soundness: 3
strengths: Addresses a Critical Gap: Tackles the underexplored area of evaluating LLMs on problems with arbitrary proof complexity. Directly addresses issues of data contamination and limited complexity in existing benchmarks.

Formalism and Clarity: Utilizes proof trees and logical forms to precisely characterize problem complexity. Well-structured and clearly written, with helpful figures enhancing understanding.

Comprehensive Experiments: Conducts extensive experiments across multiple dimensions of proof complexity (depth, width, linearity, ordering). Evaluates various state-of-the-art LLMs, providing valuable insights into model behaviors and limitations.

Insights into LLM Limitations and In-Context Learning: Reveals that model performance degrades with increasing complexity. Provides meaningful insights into the impact of different in-context learning strategies. Highlights the models' sensitivity to problem structure and ordering.
summary: This paper introduces MathGAP, a framework designed to evaluate large language models (LLMs) on mathematical word problems requiring proofs of arbitrary complexity. The authors address two critical issues in current evaluations: data contamination due to overlapping training and test sets, and benchmarks not reflecting the arbitrary complexity of problem proofs.

MathGAP uses proof trees characterized by properties such as depth, width, linearity, and ordering, enabling the generation of synthetic problems with controlled complexity and corresponding chain-of-thought (CoT) reasoning annotations. By systematically varying these properties, the framework assesses how well various LLMs generalize to problems more complex than those encountered during training or provided in-context.

The authors conduct comprehensive experiments that reveal model performance significantly declines as proof complexity increases, particularly for nonlinear proofs. Interestingly, providing in-context examples from the same distribution as the test set does not always enhance performance. The study sheds light on the limitations of current LLMs in handling complex reasoning tasks and offers insights into their generalization capabilities.
weaknesses: Synthetic Data Limitations and Linguistic Diversity: Synthetic problems may not capture the full linguistic and conceptual diversity of real-world problems. Reliance on templates could lead to repetitive linguistic patterns. 

Assumption of Reasoning Alignment: Assumes LLMs reason in ways closely aligned with the proposed proof trees. Models might use heuristics or patterns not captured by the formalism, affecting evaluation accuracy.

Limited Error Analysis: Lacks a deep analysis of error types made by the models. More detailed error categorization could provide insights into reasoning limitations (e.g., arithmetic vs. logical errors).

---

confidence: 5
contribution: 3
initial_rating: 5
presentation: 4
questions: See the questions from my comments above.
soundness: 3
strengths: 1- Given the unfortunate hype over LLMs, I believe it is crucial to have objective and solid evaluation metrics for LLMs and separate science from hype. This is exactly what this work is aiming to do.  
2- The paper is extremely well written and the authors present the results very well.  
3- Overall, the experiments are well-designed. However, they could have been extended to provide more insights (see below).
summary: The paper introduces MathGAP, a framework for evaluating LLMs' mathematical abilities. The paper notes two main motivations for creating MathGAP: 1) data leakage/contamination and 2) lack of comprehensive and systematic evaluation signals (e.g., OOD generalization, different complexity levels, etc.). The authors show that the performance of almost all LLMs drops as the difficulty (measured by depth/width of proof tree) increases. Moreover, the paper shows that LLMs are sensitive to the order in which input assumptions/axioms are presented, suggesting limitations in the perceived reasoning capabilities of LLMs.
weaknesses: 1- It is not clear how much "new insight" this work provides as many of the results have already been reported in other similar contexts. For instance, Dziri et al. also has a similar notion of graph depth/width, and shows that by increasing depth and width for both ID/OOD setups the performance drops significantly (see Fig. 5 of [1] for example). However, some open questions have not been addressed yet. For instance, from the results, it is not clear why the Llama3-70B model has a near-perfect score on "linear depth" scenarios: is it because of its training data, scale, or something else? Moreover, why is the performance gap between linear/non-linear benchmarks so significant? Do we know why the LLMs struggle so much in the nonlinear problems (e.g., Figure 3 of the paper) even when depth is small?

2- I believe given the nature of MathGAP, the paper could have explored more fine-grained evaluation scenarios beyond the final accuracy with in-context prompts. For instance, according to the note in section 5, the number of shots is fixed to 12 and the footnote mentions that this is large enough according to another work. However, the impact of context on model performance on MathGAP is unclear: Does the number of shots have a similar impact on linear/non-linear setups? Why?

3- The paper does not mention how large the overall set of proper names and values were. For instance, we know that LLMs have token bias and this can have an impact on results [2]. In addition, it is not clear what range of numbers was used and how many of the mistakes were arithmetic mistakes versus logical mistakes.

4- The logical forms and inference rules used are relatively simple and may not capture more complex mathematical relationships. However, this is not a critical issue compared to other issues as we know that models still struggle in these simple cases as well.

Overall, I think the work is borderline in its current form. I believe this work has potential to have a significant contribution if it can provide more insights and explanations that lead to better understanding of LLMs.

[1] Dziri, Nouha, et al. "Faith and fate: Limits of transformers on compositionality." Advances in Neural Information Processing Systems 36 (2024).
[2] Jiang, Bowen, et al. "A Peek into Token Bias: Large Language Models Are Not Yet Genuine Reasoners." arXiv preprint arXiv:2406.11050 (2024).

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See weaknesses
soundness: 3
strengths: Originality
- Current LLM reasoning benchmarks are mostly comprised of fixed datasets, which might be susceptible to data leakage and do not offer a way change different characteristics of the datasets such as difficulty
- MathGAP offers a way to systematically change the different aspects of the problem, size as depth, width and (non)linearity of problem tree, and constructs new problems every time, allowing for more controlled experiments on OOD generalization

Quality/Clarity
- Paper is well written and easy to understand

Significance
- in addition to providing a new benchmark to study generalization, paper also conducts analysis of current LLMs behavior using the proposed benchmark
- Presents interesting findings such as some models performing better when given OOD in-context examples rather than IID in-context examples
summary: Paper presents a framework for systematically studying the OOD reasoning capabilities of LLMs by programmatically generating training and test examples. Paper also presents analysis of how existing models behave for MathGAP problems under different settings.
weaknesses: MathGAP examples seem to mostly involve a certain type of arithmetic problem, it would be interesting to expand to scope to include other types of reasoning problems

It would also be interesting to also study the finetuning generalization behavior of LLMs

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 4
questions: I would appreciate if the authors could investigate the research questions raised in the 'weaknesses' section. In addition -

Why were different predicates used in different parts of the analysis, i.e. comp and transfer for depth analysis, part-whole for width analysis, etc.?
soundness: 3
strengths: 1. The authors did a good job elaborating the method. Section 3 provides a good background for readers to understand the method.
2. Constructing out-of-domain math problems using the logical form is a good way to evaluate the math capabilities of LLMs.
summary: This paper proposes a math proof benchmark, called MATHGap, by constructing proof trees with predefined predicates and inference rules. Evaluation on a number of LLMs shows that LLM's performance decreases as the proof complexity increases. Many LLMs do not do well in these problems.
weaknesses: 1. Despite the many LLMs being tested, the paper seems to miss the latest state-of-the-art LLMs, including Llama 3.1, Llama 3.2 (since Llama 3.2 is only recently released, I understand that the authors did not have time to include it), and GPT-O1. This is rather important, because the linear problems were pretty well-resolved by GPT-4O, and Llama 3 is also already very competitive. Including the more recent models might change the conclusions. Therefore, the current conclusion seems a bit outdated.

2. The authors seem to relate the failure of LLM's performance on the more complicated proofs to the OOD generalization failures. However, this is not necessarily the case because it may as well just be the performance degradation due to the problems being more challenging. In many cases, the in-distribution examples do not improve the performance over OOD examples, which is evidence that the performance drop is due to increased difficulty, not the generalization gap.

3. The analysis in the paper looks a bit shallow. It does not show much insight into why and how the LLMs fail. For example, is the performance degradation as complexity increases simply due to the more proof steps? Namely, it may as well be the case that the error rate of each step is constant; it is just the increased number of steps that drive down the overall success rate. In this case, the model scales fine and it is just the success criterion that becomes more stringent. Also, what are the typical failure modes? Are the errors simple arithmetic errors, reasoning errors, or errors in parsing the final results? Why does the in-context example fail to improve the performance? Why is there a nonlinear relationship between the distance of the ordering and the performance? It would make the paper stronger if the authors could perform more experiments to answer these research questions.

4. The MATHGap dataset looks too constrained for me. It only contains 5 predicates and 5 inference rules. As a result, the linear problems seem too easy for the latest state-of-the-art models. It would be nice to study how the performance scales with the number of predicates and inference rules, and whether the LLMs can retrieve the correct inference rules where there are many.

Meta-review: (a) Scientific Claims and Findings:
The paper introduces MathGAP, a framework for evaluating LLMs on arithmetic word problems with arbitrarily complex proofs. Key findings include:
- Most tested LLMs show significant performance degradation as proof complexity increases, particularly with deeper and wider proof structures
- Nonlinear proof structures are especially challenging, even for advanced models like GPT-4o
- Counter-intuitively, providing in-context examples from the same distribution as test data isn't always beneficial for performance
- Zero-shot prompting and demonstrating diverse but less complex examples sometimes perform similarly or better than IID examples
- Models show sensitivity to the ordering of problem premises, suggesting limitations in their reasoning capabilities

(b) Strengths:
- Addresses Critical Evaluation Gaps: The work tackles two major issues in current LLM evaluation - data contamination and limited complexity benchmarking.
- Rigorous Framework: MathGAP provides a systematic way to generate problems with controlled complexity and corresponding chain-of-thought reasoning annotations. The proof trees are well-characterized by properties like depth, width, linearity, and ordering.
- Comprehensive Experimentation: The study includes extensive testing across multiple dimensions of proof complexity and various state-of-the-art LLMs, providing valuable insights into model behaviors and limitations.
- Well-Presented: The paper is clearly written with helpful visualizations and thorough explanation of the methodology.

(c) Weaknesses:
- Limited Diversity: The synthetic nature of the problems may not capture the full linguistic and conceptual diversity of real-world mathematical problems.
- Scope of Analysis: The framework currently uses a relatively constrained set of predicates and inference rules, though these follow established taxonomies.
- Depth of Error Analysis: While some initial observations are made about logical vs arithmetic errors, a more detailed categorization and analysis of error types could provide deeper insights into model limitations.
- Reasoning Alignment Assumptions: The framework assumes LLMs reason in ways aligned with the proposed proof trees, though models might use different heuristics.

(d) Reasons for Accept:
- The paper makes a significant contribution by providing a systematic framework for evaluating LLM reasoning capabilities, addressing important gaps in current evaluation methods.
- The findings provide valuable insights into the limitations of current LLMs in handling complex reasoning tasks.
- The framework is well-designed and enables future research on model behavior and improvement.
- The work has been improved through the review process, including additional experiments with newer models like o1 that strengthen the conclusions.

Decision: Accept (Poster)