Abstract
Knowledge compilation uses Horn approximations to enable fast reasoning, but these structures are traditionally static and difficult to update. This paper introduces "incremental recompilation," a method to update Horn envelopes and cores directly. While general theory update is intractable, the authors demonstrate that updating a Horn formula with a single clause can be achieved in linear time for several standard revision formalisms. This approach offers a path toward efficient, dynamic AI reasoning systems that maintain their performance advantages even as new information is integrated.
Introduction
Reasoning in propositional logic is a cornerstone of artificial intelligence, yet it is computationally expensive (NP-hard). To mitigate this, researchers proposed knowledge compilation: approximating a complex knowledge base by "sandwiching" it between two simpler Horn formulas—a Horn envelope (a relaxed upper bound) and a Horn core (a strict lower bound). Because Horn formulas consist of simple "if-then" rules, reasoning with them is lightning-fast (linear time).
However, real-world AI agents operate in dynamic environments. When new information arrives, the knowledge base must be updated. Traditional methods face a dual challenge: standard belief revision typically destroys the Horn structure, and recompiling the approximations from scratch is computationally prohibitive (often NP-complete or TRANSVERSAL-hard). This paper addresses the challenge of maintaining these efficient approximations dynamically.
The Challenge of Dynamic Knowledge
Existing frameworks for theory update and revision are plagued by complexity-theoretic impediments. Even in the Horn case, updates can lead to an exponential explosion in formula size or a loss of the very structural properties that made the knowledge base efficient to begin with. Furthermore, these schemes are not "inductive"; a single update can strip away the positive properties of the represented sets.
The authors identify two primary bottlenecks:
- Structural Decay: Applying standard revision to a Horn formula often results in a complex, non-Horn formula.
- Recompilation Cost: Re-computing the envelope or core after every update is too slow for real-time applications.
Incremental Recompilation
To bypass these issues, the authors propose incremental recompilation. In this scheme, the system does not attempt to maintain the original complex formula. Instead, it maintains only the upper and lower Horn approximations. When a new piece of information ($\phi$) arrives, the system directly updates the approximations:
- The new upper bound becomes the Horn envelope of the updated old upper bound.
- The new lower bound becomes the Horn core of the updated old lower bound.
While finding Horn envelopes and cores is generally hard, the authors identify a crucial computational loophole: if the formula being approximated is already Horn, and the update is a single Horn clause, the complexity collapses.
Key Results and Complexity
The standout result of the paper (Theorem 3) proves that the Horn envelope and core of the update of a Horn formula by a single Horn clause can be computed in linear time for several major update formalisms, including those by Borgida, Forbus, Dalal, and Satoh. This bridges the gap between rapid approximate reasoning and dynamic belief revision.
The Additivity Dilemma
For the approximations to remain logically sound, the lower bound must always imply the upper bound (a property called additivity). The authors evaluated five model-based update formalisms and found a significant trade-off:
- Borgida, Forbus, Dalal, and Satoh: These allow for the efficient linear-time updates discovered by the authors but are not additive. Over multiple updates, the "sandwich" structure may break.
- Winslett’s Formalism: This is the only formalism that guarantees additivity, ensuring the bounds remain logically sound. However, it is also the only one where the authors could not prove that single-clause updates are efficient.
The Hitting Set Bottleneck
The authors also demonstrated the limits of this efficiency. If an update is even slightly more complex—such as a conjunction of several negative clauses—the problem immediately becomes NP-hard, as it maps directly to the classic minimum hitting set problem.
Conclusion and Future Work
Incremental recompilation provides a theoretical foundation for maintaining efficient reasoning structures in dynamic systems. By identifying specific conditions where belief revision and knowledge compilation become tractable, the paper offers a compromise between logical rigor and computational necessity.
Future research is required to address the "Winslett Bottleneck" and to perform empirical evaluations. Such studies would determine how quickly "semantic drift" occurs—the process by which approximations grow increasingly loose over a long sequence of updates—and whether this approach remains viable for large-scale, real-world AI applications.
Summary updated