Reliable Proof Generation with LLMs via Analogical Retrieval and Symbolic Verification: A Case Study in Euclidean Geometry

arXiv:2505.14479 · cs.AI, cs.CL · Submitted 2025-05-20 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Reliable Proof Generation with LLMs via Analogical Retrieval and Symbolic Verification: A Case Study in Euclidean Geometry".

Jane: The paper was written by Oren Sultan, Eitan Stern and Dafna Shahaf from The Hebrew University of Jerusalem, Department of Computer Science and Engineering at the Hebrew University of Jerusalem, Israel (implied by context).

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: We're talking about "Reliable Proof Generation with LLMs via Analogical Retrieval and Symbolic Verification: A Case Study in Euclidean Geometry," and it’s clear from the start that the authors see a major need to build reliability into AI systems. They aren't just asking the Large Language Model to guess the answer; they are setting up a framework for rigorous, step-by-step deduction.

Jane: Exactly, Tom. It’s about moving beyond relying on language patterns and shifting toward achieving formally valid inferences that actually hold up under scrutiny. That reliance on statistical probability alone doesn' absolute truth is what researchers have been struggling with in formal domains like mathematics.

Lu: The authors chose Euclidean geometry as their starting point because it's inherently symbolic and structured enough for this kind of verification. It gives us a perfect testing ground to see if we can apply complex, verifiable logic to something that has been represented in a clear way.

Meng: And by focusing on geometry, they’ have defined measurable criteria for success or failure. We can definitively prove whether the LLM solved the problem correctly based on the theorem dictionary, which makes the results far more practical and meaningful than general-purpose tasks.

Lalam: The deeper implication here is that we are actively moving away from just accepting what LLMs spit out; we are building a robust system that verifies its consistency. This will have huge effects on any high-stakes fields like scientific discovery or complex engineering design.

Tom: It’s impressive how they set up the problem to challenge the probabilistic nature of the LLM using that specific domain, forcing a need for structure over chance.

Jane: That' is exactly why this paper is such an important read right now, because it shows a path toward achieving genuine logical coherence in a system that has been trained primarily on language.

Summary: Tom: So, the core question is how does this "neuro-symbolic" approach actually work in practice? The paper suggests a sophisticated two-fold method to guide the LLM when solving a geometry problem.

Jane: It starts by guiding the LLM using analogous problems and then checking every step of the resulting proof with a dedicated symbolic verifier. Think of it like providing an expert student with examples from their own textbook to help them solve new, similar homework problems.

Meng: The first part, which is the analogy retrieval, involves taking the target problem and abstracting it—replacing specific names or numerical values with placeholders—to find structurally similar problems in vast datasets. This is how we intelligently narrow down the search space for potential solutions.

Lu: When you combine that structural similarity finding with the actual proof examples, it provides a powerful form of few-shot learning. It helps the LLM understand complex problem patterns and logic without having to solve every single problem from scratch.

Lalam: The system essentially learns from its own historical successes and failures in analogous problems, which makes the generated solution feel grounded in established mathematical principles rather than just being a random guess based on training data patterns.

Tom: It’s fascinating that this isn't just feeding the LLM more information; it’s feeding it highly relevant structural context derived from previous work.

Jane: And after the guidance, the verifier acts as a rigorous quality control check, ensuring that every single step follows logically from what came before it.

Improvements: Tom: Let’s talk about the actual results, because they are incredibly dramatic and directly address whether this method actually works at all. The authors found that with their full pipeline, accuracy jumped significantly across all tested models.

Jane: It's astounding to see those gains; for example, OpenAI's o1 improved from a mere ten percent accuracy to an impressive eighty percent, and GPT-five went from forty-four percent up to a remarkable ninety-six percent.

Meng: They also showed that substantial improvement happens even when using just the analogy component or the verifier alone, proving that each piece contributes critically important value to making a reliable proof.

Lu: This is where the theory meets practical application; we saw that while the full pipeline is best, any system relying on these structured inputs provides a massive advantage in overcoming purely probabilistic reasoning. It forces logic onto chance.

Lalam: This suggests that for critical tasks, we shouldn't just want an answer; we need a verifiable path to the answer. The ability catching errors via the verifier means the AI is showing signs of genuine logical coherence and safety.

Tom: It’s a massive leap in reliability, moving from a guessing model to a system that enforces logical rigor at every step of computation.

Jane: And since they isolated these contributions, we know which part of the system is doing the heavy lifting when trying to fix those initial weak attempts by correcting them iteratively.

Conclusion: Tom: We've seen how "Reliable Proof Generation with LLMs via Analogical Retrieval and Symbolic Verification: A Case Study in Euclidean Geometry" provides a roadmap for achieving logical consistency in AI reasoning.

Jane: It’s really quite something, Tom; the authors have shown that combining the flexibility of a Large Language Model with the precision of symbolic tools gives us confidence that complex derivations can perform reliably.

Lu: I think what's truly exciting is that this moves us away from just hoping the AI gets lucky with its probabilistic training. It demonstrates a clear path toward genuine symbolic reasoning, which is a huge theoretical leap for any generative model.

Meng: For practical implementation, this means we can finally start designing systems where verification isn't an afterthought; we can build trust into the core to make these complex solvers useful in mission-critical applications.

Lalam: I feel like this work has the potential to profoundly change how we approach knowledge itself. It allows us to see complex problems solved not just as plausible text, but as verifiable truths that will elevate human understanding of science and mathematics.

Tom: That is a massive shift in trust, Meng; it's reassuring to know we aren't just relying on statistical correlation anymore when the stakes are high.

Jane: And Lu is right, it’s not just a clever prompt trick; the structure provides actual logical constraints that makes the difference for those who are trying to understand.

Meng: The fact that this approach is scalable and reduces the theorem dictionary size suggests practical deployment isn't a real-world cost nightmare either, which is great news.

Lu: It makes me think about what other domains—like physics or even legal reasoning—could benefit from applying this same robust architectural philosophy to find solutions.

Lalam: We are moving toward a world where the certainty of our conclusions is just as important as the findings themselves, ensuring that our collective pursuit of knowledge remains reliable.

Tom: It really does, and it's something we can't wait to explore further with all that data and those impressive results today.

Oren Sultan, Eitan Stern, Dafna Shahaf

The Hebrew University of Jerusalem, Department of Computer Science and Engineering at the Hebrew University of Jerusalem, Israel (implied by context)

cs.AI, cs.CL

Submitted: 2025-05-20

Updated: 2026-08-31

Importance score: 87/100

The gist: The paper proposes a neuro-symbolic approach designed to overcome the limitations of Large Language Models (LLMs) in formal domains requiring rigorous logical deduction, such as mathematical proof

Key concepts

Analogical Retrieval
This method guides the LLM by taking a target problem and abstracting it (replacing specific values with placeholders) to find structurally similar problems in large datasets. This narrows the search space and provides relevant context for solving new problems.
Symbolic Verification
This acts as a rigorous quality control check on the LLM's output. It ensures that every single step of the generated proof follows logically from what came before it, enforcing logical coherence and accuracy.
Euclidean Geometry
The authors used this domain because it is inherently symbolic and structured enough for verification. It serves as a clear testing ground to apply complex, verifiable logic, allowing for measurable criteria of success or failure.
Neuro-Symbolic Approach
This describes the system's architecture, which combines the flexibility of a Large Language Model (LLM) with the precision and logical constraints of symbolic tools. This combination aims to achieve genuine logical coherence in AI reasoning.

Terminology

Summary

The paper proposes a neuro-symbolic approach designed to overcome the limitations of Large Language Models (LLMs) in formal domains requiring rigorous logical deduction, such as mathematical proof generation. The fundamental challenge identified is that LLMs are trained on probabilistic sequence generation, which struggles with the requirement for absolute truth and sustained logical coherence inherent in mathematical reasoning.

The proposed solution combines LLM generative strengths with two complementary structured components: (1) Analogical Guidance and (2) Symbolic Verification.

Methodology: Analogical Guidance

The first component leverages structural similarity to guide the LLM. The process involves abstracting both the target problem and all problems in a dataset to identify analogous structures, where entity names and numerical values are replaced by placeholders (e.g, Equal(MeasureOfAngle(word, 40) ). The pipeline then retrieves structurally similar problems from the dataset using Jaccard similarity over key formal components: construction, conditions, and goal. These retrieved problems and their corresponding proofs are presented to the LLM as in-context examples (few-shot learning), along with a reduced Geometry Theorem Dictionary (GDL). This approach serves two purposes: providing a better starting point for constructing a new proof and substantially reducing computational costs by narrowing the theorem dictionary, which shrinks from 18K to an average of 2.5K tokens.

Methodology: Symbolic Verification

The second component employs an external symbolic verifier that checks the generated proofs and provides structured feedback, driving an iterative loop. The verifier is a symbolic reasoning system that encodes proof steps and geometric constraints as logical formulas and algebraic expressions, evaluating them using satisfiability modulo theories (SMT) via the Z3 Theorem Prover. Crucially, the verifier does not know the solution; it assesses whether the numerical answer is logically entailed by the constraints imposed by the proof. The verifier identifies three distinct error tiers:

  1. Theorem call syntax violation: Errors in syntax or undefined theorems.

  2. Premise violation: Theorems relying on premises that have not been derived from the problem description or preceding proof steps, identifying missing premises and listing available ones.

  3. Goal not reached: The proof does not uniquely determine the value, indicating either an underconstrained proof or a solution differing from the LLM’s answer.

Experimental Setup

The approach was tested on Euclidean geometry problems from the FormalGeo-7k dataset (6,981 SAT-level problems. The experiments involved evaluating four primary base models: OpenAI o1, GPT-5, Gemini-Flash-2.5, and Claude Sonnet 4.6. For each model, two variants were tested: the analogy-based method (providing k analogous problems and their proofs) and a baseline variant (providing k random problems). The evaluation included three inference settings: single pass, verifier-guided feedback iterations (up to five retries), and multiple independent runs (up to three restarts).

Results

The results demonstrate substantial performance gains across all evaluated models. The accuracy of the base models ranged from 10%–44%. With the proposed neuro-symbolic approach, this accuracy significantly increased to 68%–96%.

Ablation studies confirmed that both analogical guidance and verifier feedback contribute meaningfully to these improvements. Specifically:

  • Analogy Retrieval: Consistently improved performance across all settings (e.g., o1 increased from 10% to 48% in a single run without retries).

  • Verifier Feedback: Allowed for consistent improvement, increasing accuracy from 10% to 38% for the base model o1 when using only verifier feedback.

  • Multiple Runs: Further enhanced performance, with gains of 8%-20% observed in both the full pipeline and the base model.

The results were found to be stable; when increasing the sample size from 50 to 100 problems, overall accuracy varied by only an average of 3% per level. Furthermore, while the base model often found correct numerical answers (90%), it frequently failed to produce a valid proof (57.7%). The full pipeline achieved both a 100% rate of finding correct numerical answers and an 80% proof correctness rate, demonstrating that the method helps bridge this gap by improving both proof validity and overall answer accuracy.

Improvements for AI systems

Improvements and Capabilities of a Neuro-Symbolic AI System based on this Research:

The fundamental weakness addressed by this research—the inability of large language models (LLMs) to guarantee logical consistency in formal domains—is overcome by implementing a robust, neuro-symbolic architecture. This system transcends simple chain-of-thought prompting and enables verifiable, iterative reasoning across diverse applications.

A. Automated Structural Guidance via Analogical Retrieval:

  • Mechanism: Instead of relying solely on the LLM's internal knowledge, a dedicated Structural Regressor is used to identify analogous problems from a vast database (like FormalGeo-7k). This regressor computes Jaccard similarity across abstracted features: problem construction, conditions, and goal.

  • Improvement: The system retrieves the entire verified proof for the top k most structurally similar problems. This is delivered to the LLM as highly targeted few-shot examples. The LLM is also provided with a reduced Theorem Dictionary, pruned specifically to include only those theorems used in analogous proofs.

  • Efficiency Gain: By narrowing the theorem set, computational cost and token usage are drastically reduced, making complex reasoning scalable.

B. Iterative Correctness through Symbolic Verification:

  • Mechanism: An external, dedicated Symbolic Verifier (leveraging an SMT solver like Z3) acts as a rigorous gatekeeper for the LLM’s output.

  • Improvement: The system operates in a closed feedback loop:

  1. The LLM generates a proof attempt.

  2. The Verifier checks the proof against logical and algebraic constraints derived from the problem's premises and goal.

  3. If incorrect, the Verifier provides highly specific, structured feedback categorized into three tiers: Tier 1 (Syntax/Format violation), Tier 2 (Premise violation—missing or unproven assumptions), or Tier 3 (Goal not reached/Under-constrained).

4 The LLM integrates this precise feedback and attempts to revise the proof. This process repeats up to a defined retry limit (m).

This integrated neuro-symbolic system enables capabilities that are currently impossible for base LLMs:

A. Guaranteed Formal Validity:

  • The system ensures that any generated conclusion is logically entailed by the premises, moving beyond probabilistic plausibility to verifiable truth. The output is not just a likely answer, but a formally sound derivation.

B. Robust Problem Solving in Complex Domains:

  • The system can solve problems requiring multi-step logical deduction and symbolic manipulation (e.g, advanced mathematics, formal logic, or complex engineering constraints) without the need for explicit fine-tuning or specialized training models. It effectively learn through guided induction (analogies) and rigorous self-correction (verifier feedback).

C. Accelerated Convergence and Reliability:

  • The system achieves significantly higher proof accuracy across all tested model families (e.g., increasing reliability from 10%–44% to 68%–96%). It is inherently more reliable for safety-critical applications where errors are unacceptable.

D. Targeted Error Analysis and Debugging: Provides precise diagnostic capabilities, allowing developers to pinpoint exactly why a model failed (e.g., The model used Theorem X without establishing Premise Y) rather than just reporting a failure rate, enabling rapid iterative improvement of the system components themselves.

Sources

Related papers