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

Authors: Andreas Opedal, Haruki Shirakami, Bernhard Schölkopf, Abulhair Saparov, Mrinmaya Sachan
Primary area: foundation or frontier models, including LLMs
Keywords: Arithmetic reasoning, evaluation, proofs, large language models

Abstract:
Large language models (LLMs) can solve arithmetic word problems with high accuracy, but little is known about how well they generalize to more complex problems. This is difficult to study, as (i) much of the available evaluation data has already been seen by the most capable models during training, and (ii) existing benchmarks do not capture how problem proofs may be arbitrarily complex in various ways. In this paper, we present a data-generation framework for evaluating LLMs on problems with arbitrarily complex arithmetic proofs, called MathGAP. MathGAP generates problem statements and chain-of-thought reasoning traces according to specifications about their arithmetic proof structure, enabling systematic studies on easy-to-hard generalization with respect to complexity of proof trees. Using MathGAP, we find that LLMs 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 the most capable models. The models are also sensitive to simple changes in sentence ordering. However, they remain capable of solving some complex problems, suggesting that reasoning generalization is noisy.

Decision: accept (poster)
Reviewer scores: 8, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1730077398468

thread_type:
official_review

<thread_object>
creator: reviewer_ipba

<content>
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.

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.

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.

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.?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730504440582

thread_type:
official_review

<thread_object>
creator: reviewer_d9we

<content>
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.

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

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

questions:
See weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730588291397

thread_type:
official_review

<thread_object>
creator: reviewer_tygu

<content>
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.

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).

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).

questions:
See the questions from my comments above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731372699580

thread_type:
official_review

<thread_object>
creator: reviewer_w9zb

<content>
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.

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.

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).

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732309750065

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We would like to thank all reviewers for their valuable feedback which has helped improve the paper. We have updated our draft to incorporate many of the points made by the reviewers; please see our responses below and the updated draft for details. Perhaps most notably, we have added experiments on OpenAI o1 as suggested by reviewer iPba.
</content>
</thread_object>

</thread>


Metareview:
metareview:
(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.