TLDR: A new research paper introduces the ‘Gödel Test’ to assess large language models’ ability to solve simple, previously unsolved mathematical conjectures. The study tasked GPT-5 with five problems in combinatorial optimization. GPT-5 produced nearly correct solutions for three easier problems, even refuting one conjecture with a valid alternative. However, it failed on two harder problems requiring the synthesis of insights from multiple sources, and its proofs often contained ‘lazy’ adaptations or significant errors. The findings indicate meaningful progress in routine reasoning and occasional originality, but highlight clear limitations in complex, integrative mathematical tasks, emphasizing the need for human verification.
A new research paper introduces the “Gödel Test,” a novel method for evaluating the mathematical reasoning capabilities of large language models (LLMs). The test challenges AI systems to prove simple, previously unsolved conjectures in advanced mathematical domains, moving beyond standard math competitions to assess true mathematical maturity and background knowledge.
Authored by Moran Feldman from the University of Haifa and Amin Karbasi from Cisco Foundation AI, the paper, titled G¨ odel Test: Can Large Language Models Solve Easy Conjectures?, details an experiment where GPT-5 was tasked with solving five conjectures in combinatorial optimization. This field was chosen because its problems are concrete, well-motivated, and designed to be within reach of a system aiming to display mathematical reasoning.
The Gödel Test: A New Benchmark for AI Reasoning
While frontier AI models have shown impressive results in high-school and undergraduate math competitions, it has remained unclear whether they can tackle new, simple conjectures in more advanced mathematics. The Gödel Test aims to fill this gap by presenting problems that are easy for humans with appropriate training but novel enough not to be directly available from existing sources. Unlike previous evaluations that involved extensive hints, this study provided only a minimal problem description and one or two source papers, allowing the LLM to interpret and attempt solutions independently.
GPT-5’s Performance Across Five Conjectures
The researchers presented GPT-5 with five conjectures, each designed to be solvable by a strong undergraduate or graduate student within a day. Here’s a breakdown of its performance:
Problem 1: Maximizing Monotone Plus Non-monotone Submodular Functions over a Convex Set Constraint
This problem involved maximizing a function composed of a monotone DR-submodular function and a non-monotone DR-submodular function. GPT-5 produced a nearly correct solution, adapting an existing proof with some “laziness” – skipping unchanged parts and sticking closely to the original structure. While generally accurate, it had minor inaccuracies, such as an unstated condition for an inequality and an incorrect justification for a lower bound.
Problem 2: Bicriteria Maximization of a Monotone Submodular Function subject to a p-System Constraint
GPT-5 was asked to find a bicriteria algorithm for maximizing a monotone submodular function under a p-system constraint. The model proposed a multi-pass greedy algorithm and derived an approximation guarantee for the β parameter that, upon checking, made more sense than the researchers’ initial conjecture. The proof was largely correct, with only a few minor issues, including a slightly lossy inequality and a missed connection to a known result for the p=1 (matroid) case.
Problem 3: Maximizing a Weakly-DR-Submodular Function over a Convex Set Constraint
This conjecture focused on maximizing a continuous monotone function with a relaxed DR-submodularity property. GPT-5 provided a generally correct projection-free Frank-Wolfe-style algorithm and its analysis. Initially, the response was concise, omitting many intermediate steps. When prompted for a full proof, GPT-5 delivered a much more detailed, self-contained version. However, it unnecessarily restricted the feasible set to down-closed sets and exhibited some inconsistent phrasing and minor inaccuracies in its justifications.
Problem 4: Maximizing a Partially Monotone Weakly-Submodular Function over a Cardinality Constraint
This problem combined two relaxations: weak-submodularity and m-monotonicity. GPT-5 initially failed to provide a new result, instead stating known results for special cases (ignoring m-monotonicity, or setting m=1 or γ=1). When prompted for an algorithm whose guarantees improved smoothly with both m and γ, GPT-5 provided a detailed proof for the Randomized Greedy with dummies algorithm. However, this response contained multiple significant errors, including incorrect inequalities, misapplication of mathematical concepts, and flawed justifications, rendering the answer largely useless.
Problem 5: Maximizing a Monotone Weakly-Submodular Function over a Matroid Intersection Constraint
The final conjecture involved maximizing a monotone weakly-submodular function subject to two matroid constraints. GPT-5 proposed the same algorithm the researchers had in mind but failed to analyze it correctly. The most significant errors stemmed from its inability to correctly account for the removal of two elements in each iteration, leading to incorrect set sizes and flawed proofs for key lemmas. Other issues included confusing notation, an algorithm that could crash, and incorrect mathematical justifications.
Also Read:
- Understanding LLM Verification: How Problem Difficulty, Generators, and Verifiers Interact
- Language Models Tackle Complex Optimization Challenges End-to-End
Key Takeaways and Future Outlook
The study, though based on a small sample, offers several insights into GPT-5’s capabilities:
- GPT-5 performed well when a single, straightforward line of reasoning was sufficient, producing nearly correct proofs in three out of five cases.
- It often adapted existing proofs in a “lazy” but broadly correct manner, similar to how a human might avoid redundant steps.
- The model struggled significantly with problems requiring the synthesis of insights from multiple papers (Problems 4 and 5), highlighting a major limitation in cross-paper reasoning.
- For Problem 5, GPT-5 identified the correct algorithm but failed in its analysis, suggesting the proof was more challenging than initially anticipated by the researchers themselves.
- Compared to earlier models, GPT-5 shows clear gains in mathematical competence and occasional flashes of originality, offering cautious optimism for future models.
- The researchers also noted that prompting can significantly affect performance, suggesting that improved prompt design could lead to better results.
- A critical observation was that incorrect proofs could appear plausible and convincing on the surface, underscoring a potential danger in relying solely on AI outputs for mathematical reasoning without rigorous human verification.
The Gödel Test represents an early step toward evaluating whether frontier models can eventually achieve a level of mathematical reasoning comparable to a “competent graduate student,” as envisioned by Terence Tao. The findings suggest meaningful progress in routine reasoning but also clear limitations in complex, integrative tasks.
