IncrConsist: Efficient Incremental Consistency Maintenance for LLM-Maintained Knowledge Bases

Abstract

Background: LLM-based agents are increasingly deployed not only to answer queries but to maintain persistent, evolving knowledge bases—continuously ingesting sources, revising assertions, and reconciling contradictions. After every edit, the knowledge base must be verified for internal consistency. However, naive full re-verification requires O(n²) pairwise comparisons, exceeding 90 seconds per edit step at 500-page scale and rendering it impractical for continuous maintenance.

Methods: The authors present IncrConsist, an incremental consistency maintenance framework that limits verification to a compact affected set derived from the edit's provenance-graph neighborhood. The framework formalizes five atomic edit operations (Add, Delete, Modify, Merge, Split) and three layered consistency invariants: local schema (INV1), reference chain (INV2), and mutex-based global semantic consistency (INV3). Affected-set computation integrates strength-weighted provenance BFS, keyword-Jaccard semantic expansion, and word-boundary mutex detection, thereby addressing the graph-topology gap that prevents pure graph traversal from identifying globally inconsistent assertion pairs.

Results: On a synthetic 61-page AI-course knowledge base (1,220 assertions, 908 typed provenance edges), IncrConsist achieves a 1,660× speedup over full re-verification, reduces the checked assertion count by 99.3% (an average of 10.0 nodes per step), and attains a violation recall of 0.80, compared with 0.66 for a naive 1-hop baseline. Scalability experiments across 50–500 pages confirm sub-linear time growth (3.4× for a 10× scale increase).

Conclusions: IncrConsist is the only method evaluated that detects mutex-based global semantic contradictions, a class of inconsistencies that is entirely missed by graph-traversal methods. The results demonstrate that incremental affected-set computation—a classical technique in database materialization and ontology maintenance—can be adapted to LLM-maintained text knowledge bases, through extensions for typed provenance strength and lexical mutex conflict.