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

Paper: 2602.21044 Authors: Yanrui Wu, Lingling Zhang, Xinyu Zhang, Jiayu Chang, Pengyu Li, Xu Jiang, Jingtao Hu, Jun Liu Categories: cs.AI

Abstract

Current evaluations of large language models focus predominantly on convergent logical reasoning—finding a single correct proof. This paper introduces LogicGraph, the first systematic benchmark for multi-path logical reasoning that requires models to explore diverse valid derivations rather than committing to one route. Built through a neuro-symbolic framework combining backward logic generation and semantic instantiation, LogicGraph produces solver-verified reasoning problems with high-depth multi-path structures and inherent logical distractions. Each problem instance includes an exhaustive set of minimal proofs. The authors propose a reference-free evaluation framework to assess both convergent and divergent reasoning capabilities. Experiments on state-of-the-art LLMs reveal a critical limitation: models prematurely commit to single reasoning paths and fail to explore alternatives, with performance degradation increasing substantially as reasoning depth grows.

Key Contributions

• First benchmark specifically designed to evaluate multi-path logical reasoning in LLMs, addressing the gap between convergent and divergent reasoning capabilities
• A neuro-symbolic generation pipeline that combines backward logic generation with semantic instantiation to create solver-verified reasoning problems
• Exhaustive enumeration of minimal proofs for each problem instance, enabling rigorous evaluation of path coverage
• Reference-free evaluation framework that measures both convergent accuracy and divergent coverage without requiring ground-truth solutions
• Empirical evidence showing that current LLMs exhibit significant coverage gaps that grow with reasoning depth

Methodology: Neuro-Symbolic Problem Generation

The LogicGraph benchmark construction employs a sophisticated three-stage pipeline. First, backward logic generation creates abstract reasoning structures by recursively applying logical rules in reverse, starting from a target conclusion and working backward to premises. This ensures that generated problems have guaranteed solutions while maintaining controllable complexity through depth parameters.

Second, semantic instantiation grounds these abstract logical structures into natural language problems. The framework uses LLMs to generate contextually coherent problem statements that preserve the underlying logical relationships. This step introduces realistic linguistic variation while maintaining formal correctness.

Third, solver-based verification employs automated theorem provers to validate problem correctness and enumerate all minimal proofs. This exhaustive enumeration is crucial—it provides the ground truth for evaluating whether models can discover multiple valid reasoning paths. The pipeline also introduces logical distractions: semantically plausible but logically irrelevant information that tests whether models can distinguish valid reasoning paths from spurious ones.

Experimental Findings: The Divergence Gap

Experiments on models including GPT-4, Claude, and open-source alternatives reveal a systematic failure mode. While models achieve reasonable accuracy on shallow reasoning problems (depth $\leq$ 3), performance degrades rapidly as depth increases. More critically, coverage metrics—measuring what fraction of valid proof paths models explore—show even steeper decline.

The divergence gap quantifies this phenomenon: the difference between convergent accuracy (finding any valid proof) and divergent coverage (exploring multiple valid proofs). For problems with depth 5 or greater, models typically discover less than 30% of valid reasoning paths, even when they successfully solve the problem. This indicates that models employ brittle reasoning strategies that commit early to specific paths rather than systematically exploring the logical space.

Ablation studies demonstrate that logical distractions significantly impact performance. When problems include semantically plausible but logically irrelevant premises, models frequently incorporate these into their reasoning chains, suggesting weak discrimination between valid and invalid logical dependencies. This vulnerability becomes more pronounced in multi-path scenarios where models must evaluate multiple candidate reasoning chains.

Implications for LLM Development

LogicGraph exposes fundamental limitations in how current LLMs approach logical reasoning. The early commitment problem—where models fixate on initial reasoning paths—suggests that standard training objectives may not adequately incentivize exploration of alternative solutions. This has practical implications: in domains like mathematical problem-solving, legal reasoning, or scientific hypothesis generation, the ability to consider multiple valid approaches is often more valuable than quickly finding a single solution.

The benchmark also highlights the need for better evaluation metrics. Traditional accuracy-based metrics mask important distinctions between models that barely solve problems and those that demonstrate robust understanding through exploring multiple valid derivations. The reference-free evaluation framework proposed here provides a template for more nuanced assessment that captures both correctness and reasoning breadth.

Future work might explore training techniques that explicitly encourage path diversity, such as contrastive learning objectives that reward models for generating distinct valid proofs, or reinforcement learning approaches that incentivize exploration before exploitation. The LogicGraph benchmark provides the infrastructure to rigorously evaluate such innovations.

Takeaways

1. Current LLMs exhibit a significant divergence gap: they can find single proofs but fail to explore multiple valid reasoning paths, with coverage dropping below 30% for deep reasoning problems.

2. The neuro-symbolic generation pipeline combining backward logic generation, semantic instantiation, and solver verification enables creation of challenging, verifiable multi-path reasoning benchmarks.

3. Models show premature commitment to initial reasoning paths and struggle to distinguish valid logical dependencies from plausible distractions, especially as problem complexity increases.

4. Reference-free evaluation frameworks that measure both convergent accuracy and divergent coverage provide more comprehensive assessment of reasoning capabilities than traditional metrics.

5. Addressing the multi-path reasoning gap requires new training objectives and architectural innovations that explicitly incentivize exploration of alternative valid solutions.