Skip to content

global consistency repair for natural language claim sets

content_hash: a3bc44540c7379a5 ---# Global Consistency Repair for Natural-Language Claim Sets

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/Hepaul7/QXR
Area: NLP Understanding
Keywords: factuality repair, global consistency, minimal unsatisfiable subsets, hitting set repair, retrieval-augmented generation

TL;DR

This paper formalizes global consistency repair for natural-language claim sets and introduces QXR, an adaptive diagnosis-and-repair framework that combines black-box LLM consistency judgments with recursive minimal unsatisfiable subset localization and greedy hitting-set deletion, substantially mitigating over-pruning while preserving maximum coherent information.

Background & Motivation

Modern natural-language systems—such as multi-document summarization, automated fact-checking, knowledge base construction, and retrieval-augmented generation (RAG)—increasingly assemble large collections of claims aggregated from multiple retrieved passages and multi-step reasoning outputs. However, conventional factuality verification pipelines almost exclusively focus on validating individual claims against isolated evidence or detecting pairwise contradictions between two statements. Such local verification mechanisms suffer from an intrinsic blind spot: a collection of claims can easily pass all local checks and remain entirely pairwise compatible while still being globally inconsistent as a whole set (e.g., temporal cyclic orderings, parity constraints, or multi-entity transitive contradictions). When facing an inconsistent collection of retrieved facts, discarding all information leads to unacceptable coverage loss, whereas keeping every locally supported claim inevitably produces self-contradictory system outputs.

Direct all-at-once judging using large language models (LLMs) represents the most direct black-box alternative, but it suffers from severe over-pruning. Empirical observations demonstrate that when models are prompted holistically over dozens of claims to return a consistent subset, they exhibit a persistent conservative bias: once an inconsistency is detected anywhere, the model aggressively eliminates large numbers of valid claims, causing recall to collapse dramatically. Meanwhile, exhaustive subset checking is computationally intractable, and pairwise natural language inference (NLI) scales quadratically while remaining fundamentally blind to multi-claim interactions. The central challenge in claim aggregation is therefore preservation-oriented: how to restore global consistency across claim sets while retaining the maximum amount of valid, non-conflicting information.

This paper addresses this challenge by framing claim set coherence as a constrained optimization problem over constraint scopes and drawing inspiration from inconsistency diagnosis in over-constrained systems. Core idea: formulate global consistency repair as the dual optimization of localizing minimal unsatisfiable subsets (MUSes) and removing a minimal hitting set of claims, using an LLM as a black-box subset-consistency oracle within an adaptive logarithmic-depth decomposition to pinpoint compact conflict sources and preserve maximum valid information.

Method

Overall Architecture

QXR (Query-eXplain-and-Repair) decouples global consistency repair into two alternating, iterative stages: adaptive conflict diagnosis and hitting-set-based targeted repair. Given a finite claim set \(F\) and a collection of constraint scopes \(\mathcal{C}=\{C_1, \dots, C_m\}\), the system first invokes the LLM consistency oracle to identify all currently inconsistent scopes. For each inconsistent scope, a recursive conditional divide-and-conquer procedure (QuickXplain) isolates a subset-minimal unsatisfiable subset (MUS). Next, a greedy hitting-set solver determines a minimal deletion set \(H\) that intersects every discovered MUS. Removing \(H\) from the retained claim set breaks all identified conflicts, and the scopes are restricted accordingly. This diagnosis-and-repair cycle repeats until no scope remains inconsistent.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input claim set F and scope family C"] --> B["Scope Consistency Screening<br/>Identify inconsistent scopes Tincons"]
    B -->|Inconsistent scopes exist| C["Adaptive Conflict Diagnosis<br/>QuickXplain recurses to localize MUS"]
    C --> D["Minimal Hitting-Set Repair<br/>Greedy algorithm finds deletion set H"]
    D --> E["Claim Set Update and Scope Shrinking<br/>F' ← F' \ H, Cj ← Cj \ H"]
    E --> B
    B -->|All scopes consistent| F["Output repaired maximal coherent subset F'"]

Key Designs

1. Adaptive Conflict Diagnosis: Logarithmic-Depth Localization of Minimal Unsatisfiable Subsets

Prompting an LLM directly over a large claim set to highlight contradictions often leads to hallucinations or incomplete diagnoses, while naïve independent divide-and-conquer partitions fail when contradictions cross partition boundaries (i.e., claims from both halves are required to manifest the conflict). QXR addresses this through conditional QuickXplain. Given a candidate set \(S\) and an established consistent background context \(B\), the algorithm bisects \(S\) into \(S_1\) and \(S_2\). When testing \(S_1\), it conditions explicitly on \(B \cup S_2\) as background. This conditional recursion correctly isolates cross-partition conflicts. Under a reliable consistency oracle, localizing a MUS of size \(k\) within a candidate set \(S\) requires only \(\mathcal{O}(k \log |S|)\) oracle queries, confining the diagnostic overhead to the conflict size rather than the combinatorial power set.

2. Minimal Hitting-Set Repair: Decoupling Conflict Explanation from Global Deletion

Once MUSes \(\mathcal{U} = \{U_1, U_2, \dots\}\) are localized across inconsistent scopes, restoring consistency strictly requires breaking every detected conflict. Formally, any valid deletion set \(H \subseteq F\) must be a hitting set of \(\mathcal{U}\), satisfying \(\forall U \in \mathcal{U}, H \cap U \neq \emptyset\). To maximize claim preservation, QXR computes a minimum-cardinality hitting set using a greedy approximation algorithm that iteratively selects the claim covering the largest number of unhit MUSes. This provides a theoretical \((1 + \ln |\mathcal{U}|)\) approximation factor and naturally extends to weighted claim preservation \(\min \sum_{f \in H} w(f)\) when claims carry differential provenance or confidence scores. By removing only what is strictly required to break the identified cores, QXR prevents the catastrophic over-pruning typical of end-to-end models.

3. Query Complexity Control and Conflict-Graph Treewidth Tractability

Because black-box LLM queries dominate computational expenditure, QXR provides formal upper bounds on query complexity: Algorithm 1 executes at most \(\mathcal{O}(I \cdot m \cdot (1 + k \log N))\) oracle calls, where \(N=|F|\), \(m=|\mathcal{C}|\), \(k\) is the maximum localized MUS size, and \(I\) denotes outer iterations. In the fully global setting with a single scope (\(m=1\)) and sparse conflicts (\(k \ll N\)), the dependency on total claim set size is purely logarithmic, \(\mathcal{O}(I \cdot k \log N)\), in sharp contrast to the \(\mathcal{O}(N^2)\) scaling of pairwise checking. Furthermore, structural analysis proves that if the conflict graph induced by \(\mathcal{A}_{\text{incons}}\) has bounded treewidth \(t\), exact minimum-deletion repair can be computed via dynamic programming over a tree decomposition in \(2^{t+1} \cdot \text{poly}(|F| + |\mathcal{A}_{\text{incons}}|)\) time, establishing when structured claim interaction guarantees combinatorial tractability.

A Worked Example

Consider a claim set with 5 statements extracted from conference schedules: \(f_1\) (Keynote starts before Panel), \(f_2\) (Panel starts before Networking), \(f_3\) (Networking starts before Keynote), \(f_4\) (Keynote is held in Hall A), and \(f_5\) (Poster demos occur during Networking). Here, \(\{f_1, f_2, f_3\}\) forms a size-3 cyclic MUS, while all claim pairs appear mutually plausible in isolation. Direct all-at-once LLM judging typically senses the global temporal contradiction and over-prunes indiscriminately, eliminating \(f_1, f_2, f_3\) and often extraneous fact \(f_5\). In QXR, QuickXplain recursively isolates the exact conflict core \(\{f_1, f_2, f_3\}\). The greedy hitting-set solver removes only 1 claim (e.g., \(f_3\)), successfully retaining 4 valid claims (\(f_1, f_2, f_4, f_5\)) and preserving complete event locations and non-conflicting schedules.

Key Experimental Results

Main Results

Experiments were conducted on global-consistency testbeds constructed from standard factuality benchmarks: VitaminC (24–32 claims per cluster, containing 2–6 size-2 injected contradictions derived from REFUTES edits) and FEVER (0–8 REFUTES claims combined with 14–18 SUPPORTS claims, forming dense multi-claim interaction networks). Evaluated metrics comprise Precision (P), Recall (R), and F1 over the retained claim set \(F'\) relative to gold coherent subsets.

LLM Judge Model Dataset Direct P Direct R Direct F1 QXR P (Ours) QXR R (Ours) QXR F1 (Ours)
Claude Sonnet 3.7 VitaminC 0.979 0.854 0.912 0.956 0.975 0.965
Claude Sonnet 4 VitaminC 0.956 0.877 0.915 0.938 0.983 0.960
Claude Sonnet 4.5 VitaminC 0.997 0.617 0.762 0.975 0.957 0.966
Claude Opus 4.6 VitaminC 0.654 0.574 0.611 0.985 0.968 0.976
DeepSeek-R1 VitaminC 0.980 0.730 0.837 0.973 0.990 0.981
GPT-OSS-120B VitaminC 0.984 0.926 0.954 0.956 0.995 0.975
Mistral Large 2 VitaminC 0.955 0.603 0.739 0.968 0.978 0.972
Claude Sonnet 3.7 FEVER 0.992 0.805 0.889 0.983 0.977 0.980
Claude Sonnet 4 FEVER 0.995 0.833 0.907 0.981 0.977 0.978
Claude Sonnet 4.5 FEVER 0.990 0.901 0.944 0.978 0.947 0.962
DeepSeek-R1 FEVER 0.989 0.821 0.897 0.988 0.980 0.983
GPT-OSS-120B FEVER 0.976 0.975 0.976 0.992 0.980 0.985
Mistral Large 2 FEVER 0.970 0.780 0.865 0.964 0.990 0.976

Ablation Study & Prompt Sensitivity Analysis

Ablations and sensitivity benchmarks evaluate performance on RAMDocs (realistic RAG setting with conflicting retrieved evidence snippets, \(N=30\)) and VitaminC under diverse prompting paradigms:

Benchmark / Model Evaluation Setting / Prompting Style Direct P Direct R Direct F1 QXR P QXR R QXR F1
RAMDocs / Qwen2.5 7B Realistic RAG Snippet Repair 0.883 0.639 0.741 0.902 0.743 0.815
RAMDocs / Qwen2.5 32B Realistic RAG Snippet Repair 0.852 0.839 0.845 0.854 0.998 0.920
RAMDocs / Claude Haiku 4.5 Realistic RAG Snippet Repair 0.979 0.575 0.724 0.925 0.810 0.863
RAMDocs / Claude Sonnet 4.5 Realistic RAG Snippet Repair 0.962 0.814 0.882 0.887 0.854 0.870
RAMDocs / DS-v4-Pro Realistic RAG Snippet Repair 0.905 0.822 0.861 0.860 0.952 0.904
VitaminC / Claude Sonnet 3.7 Chain-of-Thought Prompting 0.973 0.684 0.803 0.956 0.975 0.965
VitaminC / Claude Sonnet 3.7 Decomposition Prompting 0.987 0.626 0.766 0.956 0.975 0.965
VitaminC / Claude Sonnet 3.7 Few-shot Prompting 0.975 0.658 0.786 0.956 0.975 0.965
VitaminC / Claude Sonnet 3.7 Self-consistency Prompting 0.986 0.547 0.704 0.956 0.975 0.965

Key Findings

  • Direct judging fails due to over-pruning rather than low precision: Across frontier models, direct baseline precision remains high (0.95–0.99), but recall drops severely (e.g., Claude Sonnet 4.5 achieves only R = 0.617 on VitaminC, and Claude Opus 4.6 drops to R = 0.574). Direct all-at-once judging detects inconsistency accurately but cannot localize it cleanly, resulting in excessive deletion.
  • Structured diagnosis substantially empowers smaller models: On RAMDocs, open-weight models like Qwen2.5 7B and 32B improve from R = 0.639 and 0.839 to R = 0.743 and 0.998 with QXR, demonstrating that structured conflict diagnosis compensates for limited long-range reasoning in smaller LLMs.
  • Prompt engineering cannot substitute for algorithmic localization: Advanced prompting strategies (CoT, few-shot, decomposition, self-consistency) fail to alleviate over-pruning, with self-consistency dropping Sonnet 3.7 recall to 0.547. Explicit subset-level diagnosis is strictly required.

Highlights & Insights

  • Reframing factuality verification as a global preservation-oriented repair task: Moving beyond binary claim classification or pairwise NLI, this work formalizes the retention of coherent claim sets as a constrained optimization problem.
  • Bridging formal automated diagnosis with neural LLM oracles: Coupling the QuickXplain algorithm with an LLM black-box consistency judge establishes an effective paradigm where symbolic search structures noisy neural outputs without requiring formal predicate translation.
  • Broad transferability across NLP pipelines: The "localize minimal conflicts + delete via hitting set" pipeline directly transfers to multi-document RAG deduplication, long-context narrative consistency checks, and multi-agent debate reconciliation.

Limitations & Future Work

  • Reliance on oracle monotonicity: Theoretical guarantees presume monotonicity (subsets of consistent sets are consistent, supersets of inconsistent sets are inconsistent), but real LLM evaluations exhibit stochasticity and prompt sensitivity.
  • Worst-case query complexity on dense conflicts: Highly entangled overlapping conflicts can trigger numerous outer iterations and oracle calls, suggesting the need for approximate or early-stopping relaxations in latency-sensitive settings.
  • Consistency does not guarantee factual truth: A mutually coherent claim set may still consist of plausible hallucinations or suppress valid minority viewpoints in subjective or evolving domains.
  • vs Pairwise NLI / Contradiction Graphs: Pairwise approaches scale at \(\mathcal{O}(N^2)\) and cannot detect multi-premise contradictions that emerge only across \(\ge 3\) statements; QXR uses set-level queries to uncover true global inconsistencies.
  • vs Direct All-at-Once LLM Judging: Direct prompting induces severe over-pruning due to holistic attention dilution; QXR cleanly isolates conflict cores and applies minimal hitting-set deletions.
  • vs Symbolic Solvers (SAT/SMT): Symbolic tools require translating open-ended text into rigid formal logic; QXR operates directly on raw natural-language statements using an LLM oracle.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ First formulation of global consistency repair for natural language claim sets with hitting-set duality.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive coverage across frontier closed models, open-weight LLMs, synthetic benchmarks, and realistic RAG datasets.
  • Writing Quality: ⭐⭐⭐⭐⭐ Rigorous mathematical formalization, clear theoretical proofs, and intuitive pipeline illustrations.
  • Value: ⭐⭐⭐⭐⭐ Highly practical framework for mitigating knowledge corruption and hallucination in large-scale RAG and document aggregation systems.