Stress-Testing the Reasoning Competence of Language Models With Formal Proofs

Konstantine Arkoudas, Serafim BatzoglouEMNLP 2025

TL;DR

This paper introduces PROOFGRID, a novel benchmark designed to rigorously evaluate the logical reasoning capabilities of Large Language Models (LLMs) and Large Reasoning Models (LRMs) by focusing on formal proof construction and verification, rather than just final answer correctness. The results show that while top models perform impressively on simpler tasks, they still struggle with complex, structurally rich reasoning challenges, highlighting the need for more robust evaluation methods.

What Problem Does This Paper Address?

Current benchmarks for evaluating LLMs and LRMs on reasoning tasks often focus solely on the correctness of the final answer. This approach can be misleading, as models might arrive at correct answers through superficial pattern matching or memorization rather than genuine logical deduction. This is particularly problematic for mathematics, where the proof itself is fundamental. The authors argue that to truly assess a model's reasoning competence, we need to evaluate its ability to construct, check, and reason about formal proofs. Existing benchmarks often fall short by being too tied to specific proof systems or by not posing sufficiently challenging reasoning problems.

Methods

The core contribution of this paper is the PROOFGRID benchmark. It consists of a battery of challenging but tractable logical inference tasks that are domain-independent and focus on constraint-based reasoning. The tasks involve:

  • Proof Checking: Verifying the correctness of a given formal proof.
  • Proof Writing: Generating a formal proof for a given problem.
  • Proof Infilling: Filling in masked parts of a formal proof.
  • Proof Gap-Filling: Completing missing subproofs within a formal proof.

PROOFGRID utilizes a minimalist natural-deduction language (NDL) for propositional and equational logic. This formalism is designed to be simple, rigorous, and aligned with human inferential practices, making it accessible without requiring deep knowledge of complex theorem-proving systems. The dataset includes over 10,000 formal deduction problems and their corresponding proofs, with a focus on problems that require complex reasoning, hierarchical subproofs, and maintaining coherence across nested assumptions.

Datasets

The paper introduces PROOFGRID, a new dataset comprising:

  • Propositional Logic (PL):
    • PL1: ~1.4K problems and proofs, focusing on simpler proofs.
  • PL2: 300 problems with more structurally rich reasoning challenges (e.g., DAG pebbling, graph coloring, pigeonhole principle, De Bruijn formulas, Tseitin formulas, subset cardinality).
  • Equational Logic (EQ):
    • EQ1: 1K purely equational proofs involving term rewriting.

PROOFGRID is designed to be a continuously expanding resource. The authors also release benchmarks based on specific "task slices" of the dataset, typically containing 200-500 instances.

Key Insights and Ideas

  • Proof-based evaluation is crucial: Focusing solely on final answers inflates performance metrics and doesn't capture true reasoning ability. Evaluating proofs directly is a more accurate and insightful approach.
  • Abstract reasoning matters: Using formal logic tasks, devoid of natural language ambiguity, tests "fluid intelligence" – the ability to reason abstractly and solve novel problems, rather than relying on memorized knowledge.
  • Current LLMs/LRMs struggle with complex structure: While models excel at simpler proof tasks, they falter when faced with problems requiring deep structural understanding, hierarchical reasoning, and managing complex dependencies.
  • Reasoning about reasoning is emerging: The novel tasks of proof infilling and gap-filling, which require models to understand and reconstruct proof structures, show promising, albeit still limited, capabilities in leading LRMs.
  • Formal proofs as a path to reliable AI software: The authors envision a future where AI can reliably generate formal proofs alongside code, significantly boosting software reliability and trustworthiness.

Key Results

The paper benchmarks 15 prominent LLMs and LRMs on PROOFGRID.

  • Proof Checking (PL1): Top models like GPT-5 achieved accuracies around 0.86, indicating strong performance on simpler proof verification.
  • Proof Writing (PL1): Accuracies were lower, with Grok-4 reaching 0.63, suggesting that generating proofs is more challenging than checking them.
  • Proof Infilling & Gap Filling (PL1): Performance dropped significantly, with accuracies for infilling around 0.70 for Grok-4 and gap filling around 0.58. This highlights the difficulty of reconstructing missing parts of proofs.
  • PL2 (Complex Reasoning): Performance was considerably lower across the board, with Grok-4 achieving only 0.51 accuracy on proof writing. This underscores the limitations of current models on more structurally complex problems.
  • Equational Logic (EQ1): Models showed varied performance, with GPT-5 achieving 0.67 on proof checking but much lower scores on tasks like gap filling.

Qualitatively, the results reveal that models often make elementary errors and can be easily fooled by decoy problems. Slight changes in problem presentation can also significantly degrade performance.

Limitations and Future Work

  • Formal vs. Natural Language Reasoning: PROOFGRID primarily tests reasoning in formal languages. Its results may not fully generalize to models' abilities in natural language contexts.
  • Efficiency Not Measured: The benchmark focuses on accuracy, not efficiency (e.g., compute time). Different models might achieve similar accuracy with vastly different resource requirements.
  • Rapid Advancement: The benchmark's findings apply to models evaluated during the study period. The rapid pace of AI development means these relative performances may change quickly.

Future work could involve expanding the benchmark to include more complex logical formalisms, incorporating efficiency metrics, and exploring the translation of formal proofs to natural language explanations. The authors also suggest that the ability of LLMs to propose proof strategies, combined with symbolic solvers for execution, points towards a promising neurosymbolic paradigm for AI-driven theorem proving.

Summary updated

BibTeX
@inproceedings{arkoudas2025stress,
  author = {Konstantine Arkoudas and Serafim Batzoglou},
  title = {{Stress-Testing the Reasoning Competence of Language Models With Formal Proofs}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure