Abstract
Belief revision—the process of updating knowledge when new, potentially contradictory information arrives—is notoriously slow because it is computationally intractable (NP-hard). This paper introduces the Attention-Shifting Belief Revision System (ABRS), which mimics human cognition by focusing revision efforts on a small "Working Memory" of relevant beliefs. By sacrificing global consistency for local coherence, the system allows for near-instant updates even in massive knowledge bases.
The Challenge of Global Consistency
In artificial intelligence, maintaining a consistent world model is a fundamental challenge. When an agent learns a new fact that contradicts its existing database, it must decide which old beliefs to discard to restore consistency.
Most traditional systems attempt to maintain global consistency. However, if a database contains millions of beliefs, adding a single new fact can trigger a chain reaction of consistency checks across the entire repository. This process is mathematically intractable, making it unsuitable for real-world, interactive applications like intelligent tutoring systems or online monitors. The authors argue that a perfectly consistent "brain" is not always necessary; rather, the system only needs the subset of information currently under consideration to be coherent.
The ABRS Architecture
The authors propose a dual-memory architecture inspired by human psychology, separating the vast knowledge base from the active reasoning space.
Core Components:
- Working Memory (WM): A small subset of beliefs currently "under attention." Revision (detecting and fixing contradictions) only happens within this limited space.
- Long-Term Memory (LTM): The vast repository of all beliefs, organized into "Frames." Frames are clusters of related beliefs, such as all facts related to a specific physics problem or a particular context.
The Engines Under the Hood:
- EBRS (Evolutionary Belief Revision System): This is the core revision engine. It uses a modified Assumption-based Truth Maintenance System (ATMS) to track justifications for every belief. When a contradiction is found, it employs a "minimal hitting set" algorithm (Reiter’s HS-tree) to ensure the system discards the absolute minimum number of beliefs necessary to restore consistency.
- Attention Shifting: The system manages the flow of information via two main operations:
RETRIEVE(pulling a specific frame from LTM into WM) andACCEPT(pushing revised beliefs from WM back into LTM and propagating changes).
Local Revision and the "Lazy" Reviser
The ABRS is "lazy" by design. It does not attempt to fix contradictions in the LTM until the relevant beliefs are actually pulled into the Working Memory. This defers the computational cost until the information is actually needed.
As shown in the figure above, the system can focus on specific frames (like F1 or F2) to resolve local contradictions without needing to process the entire belief network at once. By restricting the revision engine to a WM of a fixed size (e.g., 50 nodes), the exponential growth typically associated with revision algorithms is effectively capped. The computation time becomes a function of the "attention span" rather than the total knowledge base size.
Key Results and Scalability
The authors evaluated the system using custom-built belief bases of varying sizes to test scaling. The most significant findings include:
- Size Independence: The time required for belief revision in the ABRS is independent of the size of the total belief base (LTM).
- Real-Time Performance: In experiments with a WM limited to 50 nodes, the system typically resolved contradictions in less than two seconds.
- Linear Scaling: While standard revision systems see processing time explode exponentially as the belief base grows, the ABRS remained stable. The only operations that slowed down were
RETRIEVEandACCEPT, which grew linearly—a much more manageable trade-off for large-scale systems.
Limitations and Future Work
While powerful, the ABRS approach involves trade-offs. It is not suitable for applications where a perfectly consistent global state is mandatory, such as safety-critical hardware verification. Additionally, the current implementation relies on static, pre-assigned frames. Future work could explore dynamic frame assignment, where the system learns to cluster related beliefs on the fly, and background "sweep" processes to clean up LTM inconsistencies during idle periods.
Summary updated