Principles of Minimal Change in Belief Revision

48 concepts34 papers1 proposal

Imagine an autonomous agent operating with a simple knowledge base: it believes a room is empty and the light is off. Suddenly, its sensors detect light shining from under the door. To maintain an accurate model of the world, the agent must update its beliefs.

Logically, there are infinitely many ways to resolve this contradiction. The agent could conclude that the light is on and that someone has secretly redecorated the room, changed the carpet to red, and left a pizza on the table. All of these additions are perfectly consistent with the new observation. However, a rational agent should not invent arbitrary details. It should alter its existing beliefs just enough to accommodate the new evidence, and no more.

This foundational concept is known as the minimal change principle. Across decades of research in knowledge representation, logic programming, and database management, this principle serves as the bedrock for how systems rationally evolve when faced with new, conflicting information.

The Geometry of Minimal Change: Symmetric Difference

To operationalize minimal change, we need a way to measure the "distance" between an agent's old knowledge state and its potential new state. The most intuitive and widely used metric is the symmetric difference—the set of elements that change their truth value or existence during the update.

In early foundational work, Jon Doyle formalized this concept within Reason Maintenance Systems in The Ins and Outs of Reason Maintenance. Doyle demonstrated that a rational system should seek a new state of justified beliefs that minimizes the symmetric difference from the previous state, ensuring maximum continuity. Shortly after, Marianne Winslett proved in Is Belief Revision Harder Than You Thought? that enforcing a strict minimal change constraint—where the truth values of atomic propositions change only if they are directly impacted by new information—is computationally challenging but necessary to prevent the catastrophic loss of unrelated knowledge.

Old State: {Empty, LightOff, CarpetGray}
New Info:  {LightOn}

Minimal Change Update:     {Empty, LightOn, CarpetGray}  (Symmetric Difference = 2)
Over-Inferred Update:      {Occupied, LightOn, CarpetRed} (Symmetric Difference = 4)

This semantic approach of minimizing the symmetric difference of facts has been successfully applied across diverse domains:

Shifting Plausibility and Epistemic Rankings

Beliefs are rarely a flat, unweighted collection of facts. Instead, agents maintain an internal hierarchy of how firmly they hold certain beliefs. When new information arrives, minimal change must operate not just on the surface facts, but on these underlying epistemic rankings.

When an agent learns a new conditional rule (e.g., "If it rains, the ground is wet"), it shouldn't completely scramble its worldview. As shown by Craig Boutilier et al. in Revision by Conditional Beliefs, the agent should perform a minimal plausibility shift. This mechanism reorders only the specific possible worlds necessary to make the new rule true, preserving the relative ordering of all other worlds.

Similarly, Mary‐Anne Williams developed a computational model for iterated changes in Iterated Theory Base Change: A Computational Model, demonstrating how explicit knowledge bases can adjust belief rankings to the absolute minimum extent necessary to maintain logical consistency. By treating belief revision as a conservative transmutation of rankings, as explored by Maurice Pagnucco et al. in Determining Explanations using Transmutations, the agent's internal preference structure remains as stable as possible across successive updates.

The Tension Between Minimal Change and Over-Inference

While minimizing change to past beliefs is intuitive, pure minimal change operators suffer from a subtle vulnerability: over-inference.

Suppose an agent's most plausible world where "the light is on" happens to be a world where "a thief is in the room." If you tell the agent "the light is on," a standard minimal change operator might select that specific world as the closest match, leading the agent to suddenly believe a thief is present. The agent has over-inferred details that were never explicitly communicated.

To resolve this, James P. Delgrande et al. introduced Conservative Belief Revision (C-revision) in foundational papers like Conservative Belief Revision and Prolegomenon to a Theory of Conservative Belief Revision.

Standard Minimal Change: Minimizes distance to the PRIOR state.
                         (Can accidentally pull in unmentioned properties)

Conservative Revision:   Minimizes information gain relative to the NEW evidence.
                         (Enforces an "only-knowing" constraint)

Conservative revision operates orthogonally to standard minimal change. Instead of focusing exclusively on minimizing change relative to the prior state, it minimizes the information gained relative to the new evidence. It treats the incoming data as an "only-knowing" constraint, ensuring that the updated belief state is a conservative extension of the input. This prevents the agent from favoring one specific model of the evidence over others based on pre-existing biases, mirroring the Principle of Minimal Commitment articulated by Frank Klawonn et al. in The Dynamic of Belief in the Transferable Belief Model and Specialization-Generalization Matrices.

Preserving Intent in Rules and Causal Structures

The principle of minimal change extends far beyond simple factual updates; it is vital when modifying underlying rules, causal laws, and system specifications.

When updating an agent's understanding of how actions affect the world, Thomas Eiter et al. showed in Updating Action Domain Descriptions that simply overwriting rules destroys valid domain knowledge. Instead, systems must isolate and remove the minimal subset of existing causal laws that directly conflict with the new information.

This preservation of structure is equally critical in machine learning and inductive logic programming. When a system refines an expert theory to account for new empirical data, systems like those proposed by Dirk Ourston et al. in Changing the Rules: A Comprehensive Approach to Theory Refinement employ greedy algorithms to find the smallest number of rule modifications. As Alessandra Russo et al. argued in Normative design using inductive learning, applying a minimal revision bias during automated updates ensures that the system preserves the original human designer's intent and conceptual model, avoiding radical, uninterpretable restructurings.

Ultimately, whether an agent is updating its immediate factual beliefs, reordering its epistemic preferences, or refining its causal laws, the principle of minimal change ensures that transitions between states remain focused, justifiable, and clean. By changing only what is strictly necessary, intelligent systems maintain continuity in an ever-changing environment.

Key Foundational Work

Is Belief Revision Harder Than You Thought? (1986) — contributed 1 concept elements to this direction.
The Ins and Outs of Reason Maintenance (1983) — 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_minimal_change_principle_dcca5ec6,
  title = {minimal change principle},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimal-change-principle/rdr_dcca5ec6789648f583761c42fa0b8499},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_minimal_change_principle_dcca5ec6_v1,
  title = {minimal change principle},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimal-change-principle/rdr_dcca5ec6789648f583761c42fa0b8499/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake