Coherent Belief Revision Under Inconsistent Evidence

16 concepts15 papers2 proposals

In classical logic, encountering a contradiction is catastrophic. If a system accepts both $A$ and $\neg A$, the principle of explosion dictates that any arbitrary statement can be proven true. This makes the knowledge base instantly useless.

Yet, real-world artificial intelligence agents must constantly operate in environments where information is messy, conflicting, and dynamic. An agent might receive contradictory sensor readings, conflicting witness testimonies, or updates that invalidate past assumptions. The challenge of belief revision is to design mechanisms that allow an agent to ingest new, potentially contradictory information, resolve internal conflicts, and maintain a consistent, usable representation of the world without collapsing into logical triviality.

Minimal Change and Maximal Coherence

When new information arrives and contradicts what an agent previously believed, how should the agent decide what to keep and what to discard? Foundational work in knowledge base revision established two core guiding principles: minimal change and maximal coherence.

As explored in Minimal Change and Maximal Coherence: A Basis for Belief Revision and, when an agent accommodates a new fact, it should alter its existing web of beliefs as little as possible. In Investigations into a Theory of Knowledge Base Revision: Preliminary Report, the authors formalize this using a model-theoretic approach: the incoming information is given strict priority, and the system judiciously prunes only the specific historical beliefs that directly cause a contradiction.

This process ensures that updates preserve classical inference while avoiding total knowledge collapse. This problem framing is deeply intertwined with non-monotonic reasoning paradigms like circumscription, which similarly attempt to minimize abnormalities when reasoning about changing worlds, as shown by the authors of Relating.

However, agents do not always have to be purely conservative. Adrian Haret et al. demonstrate in Belief Revision Operators with Varying Attitudes Towards Initial Beliefs that by varying an agent's underlying "attitude" toward its initial beliefs, one can model a rich spectrum of rational update behaviors—ranging from stubborn entrenchment to radical openness to new data.

Tracking Evidence Without Explosion

Before an agent can decide which conflicting belief to retain, it must be able to hold contradictory evidence in memory without its reasoning engine breaking down. If the system immediately computes the logical closure of all incoming data, it will explode before it can even begin to resolve the conflict.

To solve this, Eric Pacuit et al. developed "evidence logic" using neighborhood semantics (Evidence Logic: A New Look at Neighborhood Structures; Evidence and plausibility in neighborhood structures).

Instead of forcing all inputs into a single, interconnected logical space, neighborhood structures allow an agent to isolate individual pieces of evidence into separate "neighborhoods." An agent can simultaneously record evidence for $A$ and evidence for $\neg A$ in distinct compartments. The system remains stable because these neighborhoods are not automatically intersected. Only when the agent steps back to compute high-level cognitive attitudes—such as what is actually plausible or what should be believed—does it attempt to find a coherent combination of these isolated neighborhoods.

Mechanisms for Conflict Resolution

Once conflicting evidence is safely tracked, how does the system negotiate a resolution? Researchers have proposed several distinct mechanisms to model this internal negotiation:

Overcoming the Drowning Problem

A subtle failure mode in traditional belief revision is the "drowning problem." Imagine an agent receives a package of new information containing two facts: "The library is open" and "The moon is made of cheese." If the second fact conflicts with the agent's existing knowledge base, a naive revision operator might reject the entire package, or cause a cascade of deletions that accidentally "drowns" the completely valid, unrelated information about the library.

To fix this, James P. Delgrande et al. proposed a framework called Parallel Belief Revision. Instead of treating an incoming update as a single, massive conjunction of facts, the framework processes updates as a set of distinct formulas evaluated in parallel.

By isolating the inputs, the system can pinpoint and reject the specific formula causing the contradiction while safely integrating the surrounding, non-conflicting knowledge.

Making Revision Computationally Tractable

While these logical frameworks provide elegant solutions to inconsistency, executing them in practice is computationally demanding. The authors of The Complexity of Model Checking for Belief Revision and Update demonstrate that checking whether a given world state is consistent with an updated knowledge base is often significantly harder than standard logical inference.

To bridge the gap between theory and real-world deployment, research has shifted toward optimization and tractability:

  • Qualitative Probabilities: Moisés Goldszmidt et al. introduced System-Z+ in Reasoning with Qualitative Probabilities Can Be Tractable. By using ranked "if-then" rules to handle varying degrees of certainty, System-Z+ bypasses heavy probabilistic machinery, making common-sense belief revision computationally feasible.
  • Local Optimization: Rather than computing global consistency across a massive network of beliefs, Oliver Ethan Richardson developed The Local Inconsistency Resolution Algorithm (LIR). LIR maps beliefs to probabilistic dependency graphs and resolves conflicts locally within subgraphs, offering a highly scalable approximation method for complex systems.
  • High-Performance Solvers: For exact logical revision, Aaron Hunter 0001 et al. created GenC (GenC: A Fast Tool for Applications Involving Belief Revision). GenC leverages parallel processing and advanced AllSAT solvers to drastically accelerate the underlying calculations, proving that rigorous, non-explosive belief revision can be applied to real-time AI applications.

Key Foundational Work

Minimal Change and Maximal Coherence: A Basis for Belief Revision and Reasoning about Actions (1989) — contributed 1 concept elements to this direction.
Investigations into a Theory of Knowledge Base Revision: Preliminary Report (1988) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_knowledge_base_revision_ed53a70f,
  title = {knowledge base revision},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/knowledge-base-revision/rdr_ed53a70fd17242cc918612c8bbe2530b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_knowledge_base_revision_ed53a70f_v1,
  title = {knowledge base revision},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/knowledge-base-revision/rdr_ed53a70fd17242cc918612c8bbe2530b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake