cs.AIFeb 24, 2026

LogicGraph : Benchmarking Multi-Path Logical Reasoning via Neuro-Symbolic Generation and Verification

Authors: Yanrui Wu, Lingling Zhang, Xinyu Zhang, Jiayu Chang, Pengyu Li, Xu Jiang, Jingtao Hu, Jun Liu

Organizations: School of Computer Science and Technology, Xi’an Jiaotong University · Ministry of Education Key Laboratory of Intelligent Networks and Network Security, China · Department of Electrical Engineering, Stanford University · School of Computer Science and Technology, Tiangong University · Shaanxi Province Key Laboratory of Big Data Knowledge Engineering, China

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Evaluations of large language models (LLMs) primarily emphasize convergent logical reasoning, where success is defined by producing a single correct proof. However, many real-world reasoning problems admit multiple valid derivations, requiring models to explore diverse logical paths rather than committing to one route. To address this limitation, we introduce LogicGraph, the first benchmark aimed to systematically evaluate multi-path logical reasoning, constructed via a neuro-symbolic framework that leverages backward logic generation and semantic instantiation. This pipeline yields solver-verified reasoning problems formalized by high-depth multi-path reasoning and inherent logical distractions, where each instance is associated with an exhaustive set of minimal proofs. We further propose a reference-free evaluation framework to rigorously assess model performance in both convergent and divergent regimes. Experiments on state-of-the-art language models reveal a common limitation: models tend to commit early to a single route and fail to explore alternatives, and the coverage gap grows substantially with reasoning depth. LogicGraph exposes this divergence gap and provides actionable insights to motivate future improvements. Our code and data will be released at https://github.com/kkkkarry/LogicGraph.

Figures & tables

Figure 1: Illustration of the multi-path reasoning challenge. In the real world, the same conclusion may be entailed via multiple derivation paths.
Figure 2: LogicGraph generation pipeline. (a) Logic DAG generation (Section 4.1 ) builds a goal-to-premise directed acyclic graph by sampling argument forms, yielding multiple valid reasoning paths; paths that share intermediate inference nodes are grouped into families . (b) Semantic instantiation (Section 4.2 ) translates the DAG into Prover9 formulas and renders the corresponding steps into natural language by instantiating abstract entities and scenario context with LLMs. (c) Solver-based Filtering (Section 4.3 ) uses Prover9 to validate each instance.
Figure 3: Three-stage evaluation pipeline for LLM-generated multi-path proofs: (1) pre-processing and auto-formalization extract candidate solutions, resolve references, and translate natural-language steps into a symbolic representation (Prover9-style); (2) a solver is then used to validate local (stepwise) and global validity; (3) failures are annotated along two independent, non-exclusive error axes: semantic comprehension and logical execution.
Figure 4: Performance dynamics of LLMs across varying reasoning depths. Solid lines represent Reasoning-oriented LLMs; dashed lines represent General-purpose LLMs.
Figure 5: Comparative Analysis of Error Type: Semantic Comprehension vs. Logical Execution.
Figure 6: Model performance on case (Figure 8 ). GT represents the ground truth paths.
Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Distribution of the benchmark dataset by average steps and number of solutions. The bubble size indicates the frequency of samples.
Domain CategorySpecific Fields (Examples)# SamplesPercentage
Business & FinanceQuality Control, Insurance, Industrial Engineering, etc.20723.0%
Environment & ScienceScientific Method, Biodiversity, Forestry, etc.18720.8%
Medical & HealthClinical Trials, Pharmacology, Emergency Medicine, etc.16718.6%
Law & GovernanceRegulatory Compliance, Legal Procedure, Litigation, etc.11312.6%
Engineering & TechIoT, Software Development, Telecommunications, etc.9410.4%
Humanities & SocietySports, Visual Arts, Culinary Arts, etc.849.3%
Appendix
Table 6: Domain Distribution of the LogicGraph Benchmark. The dataset covers a wide spectrum of real-world scenarios, categorized into 7 major domains and over 90 specific fields. This diversity ensures a comprehensive evaluation of reasoning capabilities across various professional and practical contexts.
Figure 8: A Small type example in LogicGraph.
Figure 9: A Medium type example in LogicGraph.
Figure 10: A Large type example in LogicGraph.
Error TypeDetailed DescriptionConcrete Example
A. Semantic Comprehension (Information Processing Layer)
Semantic MisinterpretationThe model fails to correctly parse the linguistic meaning of a specific fact or rule. This often involves confusing the direction of causality or ignoring negations.Context: “If A, then B.” Model interpretation: “If B, then A.” (Conditional inversion) Context: “John is not eligible.” Model interpretation: “John is eligible.” (Negation neglect)
Information OmissionThe model completely ignores a critical piece of evidence or a constraint provided in the input context during the reasoning chain.Context: “John has no medical insurance.” Error: The model concludes John proceeds with a procedure requiring insurance, failing to retrieve the negation fact.
Fact HallucinationThe model fabricates premises or assumes external knowledge that contradicts or is absent from the provided context.Context: “John visits the hospital.” Error: The model adds “John has cancer” as a premise for deduction, despite no such mention in the text.
B. Logical Execution (Reasoning Layer)
Invalid DeductionThe derivation step is logically fundamentally flawed. Even if the premises are correct, the conclusion cannot be derived using standard logic (e.g., formal fallacies).Premises: “Rule: If it rains, the ground is wet.” + “Fact: The ground is wet.” Conclusion: “Therefore, it is raining.” Reason: Fallacy of affirming the consequent.
Appendix
Table 7: Detailed definitions and examples of the error taxonomy. We provide concrete scenarios to illustrate the distinction between comprehension failures and execution failures.
Figure 11: Error distribution across models, grouped by semantic comprehension and logical execution.
Figure 12: A specific example of our model’s error analysis.
Figure 13: A valid complex reasoning step correctly verified by our formal method but incorrectly accepted by an LLM-based judge (using Deepseek-V3.2-Exp directly as an LLM judge).
Figure 14: Comparison of evaluation robustness. (a) A fully valid solution. (b) An invalid solution with missing premises (Rule 5), correctly rejected by our method but incorrectly accepted by LLM judges.
Figure 15: Prompt we use during the generation process.
Figure 16: Prompt we use during the test process.
Figure 17: Prompt template we use during the performance evaluation process.

Explore similar work

CardsList

  1. SymbolLKG: Towards Verifiable Logical Reasoning via Logical Knowledge Graph and Symbolic Solvers

    Aug 27, 2026Haizhao Fan, Yuchi Xiong, Jize Wang +2LLM ReasoningNeuro-Symbolic Reasoning

    Shanghai JiaoTong University

  2. Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models

    Aug 2, 2026Fali Wang, Ali Al-Lawati, Iliyas Bektas +5LLM EvaluationLLM Reasoning with Graphs

    The Pennsylvania State University, University Park, PA, USA · Rensselaer Polytechnic Institute, Troy, NY, US

  3. LGMT: Logic-Grounded Metamorphic Testing for Evaluating the Reasoning Reliability of LLMs

    May 12, 2026Zenghui Zhou, Man Li, Xiaoke Fang +3LLM EvaluationAutomated Software Testing

    School of Automation Science and Electrical Engineering, Beihang University, Xueyuan Road, Haidian District, Beijing, 100191, China