Research map / Large language models / Agents, code and math
MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces MathGAP, a synthetic generator of arithmetic word problems with controllable proof-tree depth, width, shape and sentence ordering, used to test OOD easy-to-hard generalization of LLMs with in-context CoT demonstrations.
Problem
Existing math word problem benchmarks are likely contaminated and do not systematically vary proof complexity, so it is unclear whether LLMs generalize to problems with deeper, wider, or nonlinear arithmetic proofs.
Approach
Formalize math word problems as world models of logical forms and inference rules, generate problems and CoT traces top-down from sampled proof trees with controlled depth, width, shape and leaf ordering, and use the generator to build OOD test sets of increasing complexity.
Key results
- Accuracy decreases as proof depth and width increase; nonlinear problems are hardest, and even GPT-4o fails on the most complex nonlinear problems.
- Llama3-70B performs near perfectly on linear depth problems but drops on linear width (partwhole) problems, showing width generalization is harder than depth.
- o1-preview and DeepSeek-R1 reach only 5.0% and 11.0% accuracy on a depth-7 randomly ordered nonlinear test subset with 25k output tokens.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the output-token limit from 4,096 to 10,000 | o1-preview · MathGAP nonlinear depth 7 | answer accuracy: 0.25% -> 76.5% | Helped |
| Increase the output-token limit to 10,000 | DeepSeek-R1 · MathGAP nonlinear depth 6 | answer accuracy: 77.5% | Helped |
| Randomly order the problem sentences | o1 · MathGAP nonlinear depth 7 (100 problems) | answer accuracy: 5.0% | Hurt |
| Randomly order the problem sentences | DeepSeek-R1 · MathGAP nonlinear depth 7 (100 problems) | answer accuracy: 11.0% | Hurt |
| Increase proof depth and/or width | LLMs evaluated with MathGAP · MathGAP arithmetic problems | answer accuracy | Hurt |
| Increase proof width rather than proof depth | LLMs evaluated with MathGAP · MathGAP linear problems | answer accuracy | Hurt |
| Use nonlinear rather than linear proof structures | LLMs evaluated with MathGAP · MathGAP arithmetic problems | answer accuracy | Hurt |
| Move a sentence from canonical ordering to the front | LLMs evaluated with MathGAP · MathGAP linear depth 5 order generalization | answer accuracy | Hurt |
| Use a range of OOD examples with varying complexity instead of only primitive examples | LLMs evaluated with MathGAP · MathGAP linear depth generalization | answer accuracy | Helped |
| Provide in-context examples rather than zero-shot prompting | LLMs evaluated with MathGAP · MathGAP easy-to-hard generalization | answer accuracy | Mixed |
| Provide in-distribution examples rather than zero-shot prompting | LLMs evaluated with MathGAP · MathGAP nonlinear depth generalization | answer accuracy | Mixed |
Surprising findings
- Moving one sentence to the front of the problem hurts performance non-monotonically: problems are easiest when the moved sentence comes from near the beginning or end rather than the middle.
- In-distribution in-context examples do not consistently beat zero-shot prompting, and GPT-3.5-Turbo is the only model that consistently benefits from added in-context examples.
Limitations
- Limited linguistic diversity in generated problems; templates are not paraphrased.
- Direct difficulty comparison between linear and nonlinear problems is confounded since they use different inference rules.
- Only English problems are considered.
Experimental setup
Benchmarks: MathGAP
Metrics: answer accuracy 95% bootstrap confidence intervals
Baselines: zero-shot prompting in-distribution in-context examples primitive in-context examples
Builds on: chain-of-thought prompting GSM8K Dynabench
Closest papers by meaning
- Not All Proofs Are Equal: Evaluating LLM Proof Quality Beyond Correctness (NeurIPS 2026 · similarity 0.90)
- Llemma: An Open Language Model for Mathematics (ICLR 2024 · similarity 0.89)
- OMEGA: Can LLMs Reason Outside the Box in Math? Evaluating Exploratory, Compositional, and Transformative Generalization (NeurIPS 2025 · similarity 0.88)
- RealMath: A Continuous Benchmark for Evaluating Language Models on Research-Level Mathematics (NeurIPS 2025 · similarity 0.88)
- FaithSieve: Fine-Grained Evaluation of Math Proofs with Faithful Formal Evidence (NeurIPS 2026 · similarity 0.88)
- MathConstruct: Challenging LLM Reasoning with Constructive Proofs (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.