Reasoning with Incomplete Knowledge Bases

80 concepts78 papers1 proposal

When designing systems to reason about the world, we must decide how to interpret silence. If a database of flight connections does not list a direct flight from Wichita to Wellington, we safely assume no such flight exists. This is the Closed-World Assumption (CWA): any statement not explicitly known to be true is treated as false.

For structured, fully observed environments, the CWA is incredibly efficient. But as computer science moved toward web-scale data, distributed systems, and open-ended artificial intelligence, this assumption became a liability. If a medical knowledge base does not explicitly state that a patient is allergic to penicillin, assuming they are not allergic simply due to a lack of data could be fatal.

To handle the messy reality of the real world, researchers developed frameworks for the Open-World Assumption (OWA), where a lack of information implies that a fact is simply unknown.

Closed-World Assumption (CWA):  [Not Stored] ──> False
Open-World Assumption (OWA):    [Not Stored] ──> Unknown

Shifting from a closed world to an open world requires rethinking the foundations of logic, database queries, and modern language modeling.

The Tyranny of the Closed World

Traditional relational databases are built entirely on the CWA. As Kurt Konolige observed in A Metalanguage Representation of Relational Databases for Deductive Question-Answering Systems, treating missing information as definitively false is too restrictive for real-world applications where data is naturally incomplete.

When we apply the CWA to open environments, systems fail in predictable ways:

Formalizing the "Known Unknown"

To build systems that can safely navigate incomplete information, logicians had to elevate "unknown" to a first-class citizen.

Hector J. Levesque provided a foundational breakthrough in The Interaction with Incomplete Knowledge Bases: A Formal Treatment by introducing an explicit knowledge operator ($K$) into standard logic. Instead of just asking whether a proposition $\phi$ is true, a system could reason about its own state of ignorance. This allows a system to formally distinguish between $\neg \phi$ (knowing that something is false) and $\neg K \phi$ (not knowing whether it is true).

Standard Logic (CWA):       Is φ true?  ───> [No] ───> Conclude ¬φ
Epistemic Logic (OWA):      Do I know φ? ──> [No] ───> Conclude ¬Kφ (Ignorance)

This shift alters how negation is handled. In standard logic programming, "negation as failure" automatically treats a failure to prove a fact as proof of its negation. Michael Gelfond argued in Strong Introspection that this mechanism is fundamentally inadequate for incomplete domains, advocating instead for systems that can explicitly introspect and declare a state of being unknown.

This conceptual shift extends across various formalisms. In modal logic, Wesley H. Holliday replaced the traditional assumption of infinite "total worlds" with finite, partial "possibilities" in Partiality and Adjointness in Modal Logic, allowing propositions to remain indeterminate without breaking the underlying semantics.

Making Open-World Reasoning Tractable

If dropping the closed-world assumption makes systems safer and more realistic, why don't we use the open-world assumption everywhere? The answer is computational complexity.

Under the CWA, querying a database is simple look-up and evaluation. Under the OWA, querying an incomplete knowledge base becomes an exercise in theorem proving: you must verify if a query holds true across all possible worlds that are consistent with your incomplete data.

To bridge this gap, researchers looked for fragments of logic that allow for incomplete information without triggering an exponential explosion in processing time. Bill MacCartney et al. in Practical Partition-Based Theorem Proving for Large Knowledge Bases and Yongmei Liu 0001 et al. in A Tractability Result for Reasoning with Incomplete First-Order Knowledge Bases proved that a class of systems known as Proper Knowledge Bases can be evaluated in polynomial time. By adapting standard database query algorithms and leveraging the "k-guarded" fragment of first-order logic, they showed that systems can remain highly efficient while natively representing incomplete information.

Similarly, open-world reasoning has been successfully adapted to temporal and existential frameworks. For example, Matthias Lanzinger et al. developed methods in Temporal Datalog with Existential Quantification to reason about scenarios where the existence of an entity is logically implied over time, even if its specific identity remains unknown.

The Modern Re-Emergence in Language Models

The tension between closed-world assumptions and open-world realities has re-emerged in the era of Large Language Models (LLMs) and modern Knowledge Graph Question Answering (KGQA).

When an LLM or a QA system is asked a question whose answer is missing from the underlying reference text, it faces a choice: admit ignorance or force an answer. Historically, evaluation benchmarks forced a closed world. As noted by Aleksandra Piktus et al. in KILT: a Benchmark for Knowledge Intensive Language Tasks, many knowledge-intensive benchmarks assume that the required information is always present in the source corpus, leaving models unequipped to handle real-world unanswerability.

When models are trained on these closed-world datasets, they become overconfident and prone to hallucination. Elior Sulem et al. exposed this vulnerability in Yes, No or IDK: The Challenge of Unanswerable Yes/No Questions, showing that boolean QA performance plummets when models are forced to choose between a binary "Yes" or "No" for queries that lack sufficient evidence.

To fix this, modern frameworks explicitly evaluate and train models for open-world scenarios:

Closed-World Evaluation:    [Query] ──> [Incomplete Context] ──> Force Answer (Hallucination)
Open-World Evaluation:      [Query] ──> [Incomplete Context] ──> Flag "I Don't Know" (Conscious Incompetence)

Hybrid Approaches: The Best of Both Worlds

Pure open-world reasoning can sometimes be paralyzingly conservative; if you can never assume anything is false, you can rarely make definitive practical deductions. The frontier of this research direction lies in hybrid frameworks that combine the safety of the OWA with the practical efficiency of the CWA.

One prominent strategy is the partial completeness heuristic. As utilized by Hiba Arnaout in Wiki-Based Communities of Interest: Demographics and Outliers, this heuristic posits that if a knowledge base contains at least one recorded value for a specific property of an entity, that local list can be treated as exhaustive. This allows systems to safely infer a negative for that specific property without assuming the entire database is complete.

Another approach involves embedding closed-world reasoning locally within open-world description logics. By utilizing stable model semantics for terminologies, systems can apply default negation—assuming the absence of a condition unless recorded—while maintaining a predictable, computationally bounded complexity class.

By formalizing ignorance, bounding query scopes, and designing benchmarks that reward models for knowing what they don't know, researchers continue to transform AI from brittle, closed-world calculators into resilient, open-world reasoners.

Key Foundational Work

A Metalanguage Representation of Relational Databases for Deductive Question-Answering Systems (1981) — contributed 1 concept elements to this direction.
The Interaction with Incomplete Knowledge Bases: A Formal Treatment (1981) — contributed 1 concept elements to this direction.
A Metalanguage Representation of Relational Databases for Deductive Question-Answering Systems (1981) — 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_closed_world_assumption_closed_world_ass_809fce4f,
  title = {closed-world assumption (closed world assumption)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/closed-world-assumption-closed-world-assumption/rdr_809fce4f6cd2402b93924df953cc31e3},
  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_closed_world_assumption_closed_world_ass_809fce4f_v1,
  title = {closed-world assumption (closed world assumption)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/closed-world-assumption-closed-world-assumption/rdr_809fce4f6cd2402b93924df953cc31e3/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