TL;DR
Large language models (LLMs) often contradict themselves when answering a series of related questions, even if individual answers are correct. This paper introduces a new benchmark and a solver-augmented method to ensure logical consistency across multiple queries, significantly reducing these contradictions while maintaining accuracy.
What Problem Does This Paper Address?
Imagine asking an LLM a series of questions about a complex scenario, like a legal case or a medical diagnosis. While the LLM might answer each question correctly in isolation, its answers to related questions can sometimes contradict each other, leading to an unreliable overall understanding. This phenomenon, known as "cross-query contradictions," is a significant hurdle for deploying LLMs in real-world applications where global logical coherence is crucial. Existing benchmarks often focus on evaluating answers to single questions, failing to capture this multi-query inconsistency. This paper aims to bridge this gap by formalizing "case-file logical consistency" – the ability of an LLM to maintain a globally satisfiable belief state across a bundle of interdependent queries.
Methods
The authors propose a novel approach that combines LLMs with symbolic solvers to enforce logical consistency. Here's a breakdown:
- Commitment Extraction: After an LLM answers a query, its answer is translated into a formal logical commitment. This is done using a structured extractor that maps the LLM's output (e.g., "ENTAILED," "CONTRADICTED," "UNKNOWN") into logical propositions.
- Incremental Satisfiability Checking: The system maintains a "belief state" which is the conjunction of all extracted commitments so far. After each new query's commitment is added, a symbolic solver (SAT or SMT) checks if this belief state is still logically satisfiable.
- Unsat-Core Localization: If a contradiction is detected (the belief state becomes unsatisfiable), the solver identifies a minimal subset of conflicting commitments (the "unsat core"). This helps pinpoint the source of the inconsistency.
- Counterexample-Guided Repair: Based on the unsat core, the system attempts to repair the contradiction. This involves prompting the LLM to revise its answer, prioritizing minimal changes like flipping the label (e.g., from "ENTAILED" to "UNKNOWN") or softening the commitment. If these fail, it may retract prior commitments.
This approach is contrasted with simpler baselines like direct decoding (no context), chain-of-thought (CoT), and self-consistency (sampling multiple answers per query).
Datasets
The authors introduce a new benchmark called Cross-Query Reasoning Benchmark. It comprises:
- 390 case files: Each case file contains a set of natural language premises.
- 2,450 interdependent query bundles: Each bundle consists of 5-8 queries related to a case file, designed to cover various reasoning patterns like forward-chaining, counterfactuals, and missing information.
- Four domains: Relational/SAT, Temporal/SMT, Policy/Rules, and Underspecified/Abductive.
- Machine-verified labels: Entailment, contradiction, and unknown labels for each query, validated by three annotators and further checked by solvers.
This benchmark is designed to specifically test cross-query consistency, unlike existing benchmarks that focus on single-query accuracy.
Key Insights and Ideas
- Global coherence is key: The most striking insight is that LLMs struggle with maintaining logical consistency across related queries, even when individual answers are accurate. This "global coherence" is a distinct challenge from per-query correctness.
- Solver-augmented reasoning is powerful: Explicitly tracking and verifying logical commitments with a solver dramatically improves consistency, even with lightweight repair mechanisms.
- Repairing contradictions is feasible: The proposed counterexample-guided repair loop effectively resolves contradictions with minimal changes, demonstrating that LLMs can be guided to produce globally consistent outputs.
- Contradictions are not just over-abstention: The gains in consistency are not achieved by simply making the LLM output "UNKNOWN" more often. Instead, the method corrects actual contradictions and entailments.
Key Results
- Substantial SetCons improvement: The proposed "Ours (Check+Repair)" method significantly boosts the SetConsRate (Case Satisfiability Rate) from a baseline of 0.56 to an average of 0.94 across four reasoning domains.
- Preserved per-query accuracy: While improving global consistency, the method generally maintains or slightly improves per-query accuracy (e.g., Acc↑ from 0.80 to 0.85 for DeepSeek-R1).
- Reduced Revision Cost: The RevisionCost (average number of commitments to change for repair) is substantially reduced by the repair mechanism, indicating more stable and coherent outputs.
- Efficiency: The solver-augmented approach is computationally efficient, with overheads significantly lower than self-consistency sampling, especially for the repair version.
- Domain-specific gains: Consistency improvements are most pronounced in constraint-heavy domains like temporal/capacity reasoning, where a single error can cascade into global infeasibility.
Limitations and Future Work
- Extraction Noise: The LLM's ability to accurately extract logical commitments can be a source of errors. While the authors report high extraction accuracy (92.75% overall), failures can lead to spurious outcomes or trigger conservative "UNKNOWN" fallbacks.
- Solver Sensitivity and Timeouts: The performance and reliability of symbolic solvers can be sensitive to the problem formulation and theory fragment. Complex SMT instances can also lead to solver timeouts, forcing a fallback to "UNKNOWN."
- Repair Insufficiency: In rare cases, even the full repair loop might not restore satisfiability without retracting a large number of prior commitments.
- Future Directions: The authors suggest extending the framework to richer logics (e.g., probabilistic, modal), scaling to longer query bundles, and integrating commitment tracking directly into LLM training objectives.
Summary updated