잡음이 있는 LLM 오라클을 이용한 전역 일관성 검증의 기초

Foundations of Global Consistency Checking with Noisy LLM Oracles

사실 검증, 요약 및 지식 베이스 구축과 같은 작업에서 자연어 사실들의 집합이 전역적으로 일관성을 유지하는 것은 필수적입니다. 대규모 언어 모델(LLM)은 작은 사실 집합의 일관성을 평가할 수 있지만, LLM의 판단은 노이즈가 많으며, 쌍별 검사만으로는 전역적인 일관성을 보장하기에 충분하지 않습니다. 본 논문에서는 이 문제를 공식화하고, 전역 일관성을 검증하는 데 최악의 경우 지수적으로 많은 오라클 쿼리가 필요함을 보여줍니다. 이 문제를 실용적으로 해결하기 위해, 우리는 최소 불일치 부분집합(MUS)을 식별하고, 선택적으로 히팅-셋을 통해 최소 수정을 계산하는 적응형 분할 정복 알고리즘을 제안합니다. 우리의 접근 방식은 낮은 차수의 다항 시간 복잡도를 가집니다. 합성 데이터와 실제 LLM 오라클을 사용한 실험 결과, 우리의 방법은 불일치를 효율적으로 감지하고 위치를 파악하며, LLM 기반 평가기를 사용한 언어적 일관성 검증을 위한 확장 가능한 프레임워크를 제공합니다.

Ensuring that collections of natural-language facts are globally consistent is essential for tasks such as fact-checking, summarization, and knowledge base construction. While Large Language Models (LLMs) can assess the consistency of small subsets of facts, their judgments are noisy, and pairwise checks are insufficient to guarantee global coherence. We formalize this problem and show that verifying global consistency requires exponentially many oracle queries in the worst case. To make the task practical, we propose an adaptive divide-and-conquer algorithm that identifies minimal inconsistent subsets (MUSes) of facts and optionally computes minimal repairs through hitting-sets. Our approach has low-degree polynomial query complexity. Experiments with both synthetic and real LLM oracles show that our method efficiently detects and localizes inconsistencies, offering a scalable framework for linguistic consistency verification with LLM-based evaluators.