Incremental Recompilation of Knowledge

Goran Gogic, Christos H. Papadimitriou, Martha Sideri

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:

  1. Structural Decay: Applying standard revision to a Horn formula often results in a complex, non-Horn formula.
  2. 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

Abstract

Approximating a general formula from above and below by Horn formulas (its Horn envelope and Horn core, respectively) was proposed by Selman and Kautz (1991, 1996) as a form of ``knowledge compilation,'' supporting rapid approximate reasoning; on the negative side, this scheme is static in that it supports no updates, and has certain complexity drawbacks pointed out by Kavvadias, Papadimitriou and Sideri (1993). On the other hand, the many frameworks and schemes proposed in the literature for theory update and revision are plagued by serious complexity-theoretic impediments, even in the Horn case, as was pointed out by Eiter and Gottlob (1992), and is further demonstrated in the present paper. More fundamentally, these schemes are not inductive, in that they may lose in a single update any positive properties of the represented sets of formulas (small size, Horn structure, etc.). In this paper we propose a new scheme, incremental recompilation, which combines Horn approximation and model-based updates; this scheme is inductive and very efficient, free of the problems facing its constituents. A set of formulas is represented by an upper and lower Horn approximation. To update, we replace the upper Horn formula by the Horn envelope of its minimum-change update, and similarly the lower one by the Horn core of its update; the key fact which enables this scheme is that Horn envelopes and cores are easy to compute when the underlying formula is the result of a minimum-change update of a Horn formula by a clause. We conjecture that efficient algorithms are possible for more complex updates.
BibTeX
@article{gogic1998incremental,
  author = {Goran Gogic and Christos H. Papadimitriou and Martha Sideri},
  title = {{Incremental Recompilation of Knowledge}},
  journal = {J. Artif. Intell. Res.},
  year = {1998},
  url = {https://openreview.net/forum?id=p_TFaEchHB6},
}

Loading related content...

Figure