Sound but Incomplete Approximations for Tractable Reasoning

16 concepts12 papers1 proposal

In an ideal world, automated reasoning systems would be both sound and complete. A sound system never lies: every answer it returns is correct, and every plan it formulates is guaranteed to succeed. A complete system never omits: if a valid answer or plan exists, the system will find it.

However, when agents must reason under uncertainty, manage inconsistent databases, or navigate complex logical ontologies, maintaining both properties is a computational nightmare. The state space explodes exponentially, pushing problems into PSPACE-hard or even undecidable territory.

To make these problems practical, researchers often make a deliberate choice: sacrifice completeness to preserve soundness. By utilizing sound but incomplete approximations, algorithms can run in polynomial time. They guarantee that any solution found is absolutely correct, accepting the trade-off that they might occasionally say "I don't know" or miss a valid path.


The Intuition: Collapsing the Belief Space

To understand why this trade-off works, consider an agent planning with incomplete information. If there are $n$ uncertain boolean variables, a fully complete planner must track a "belief state" consisting of up to $2^n$ possible worlds. Evaluating actions across this explicit disjunctive representation causes severe scalability bottlenecks, a challenge explored by To et al. in A Conformant Planner with Explicit Disjunctive Representation of Belief States.

A sound but incomplete approximation bypasses this exponential explosion by simplifying the state representation. Instead of tracking every combination of possibilities, it tracks a single, conservative lower bound of certainty. For instance, it might only track fluents that are definitely true or definitely false, treating any interaction between variables as independent.

Exact Belief State (Exponential)       Approximate State (Polynomial)
     ┌───────────────┐                       ┌───────────────┐
     │ A ∧ B ∧ C     │                       │               │
     │ A ∧ ¬B ∧ C    │  ─────────────────►   │  A is TRUE    │
     │ A ∧ B ∧ ¬C    │     Approximate       │  C is UNKNOWN │
     └───────────────┘                       └───────────────┘

Because the approximate state only contains verified truths, any plan built upon it is guaranteed to be safe and correct (sound). However, because it discards the nuanced, disjunctive relationships between variables, the planner becomes blind to complex solutions that rely on those interactions, rendering it incomplete.


Taming Complexity in AI Planning

The computational benefits of this approach were rigorously mapped out by Baral et al. in Computational complexity of planning and approximate planning in the presence of incompleteness. The authors demonstrated that while exact planning with incomplete information is highly intractable, sound approximations that simplify state representations can dramatically lower the computational hurdles, making planning tasks viable in domains where state properties are relatively independent.

In subsequent work, Baral et al. applied this to temporal goals in Complexity and approximation studies of finding polynomially bounded length plans for temporal goals. They showed that using a sound "0-approximation" technique can reduce the complexity of finding plans from PSPACE-hard down to NP-complete. The cost of this efficiency is that the simplified logic can be overly restrictive, failing to find valid paths when the environment requires highly coupled reasoning.

This trade-off is highly effective in practice. For example, Son et al. developed conformant planners in Conformant Planning for Domains with Constraints-A New Approach that use deterministic approximations of belief states. By sacrificing completeness, their system successfully solved complex benchmarks containing thousands of constraints that caused exact, complete planners to crash.

The tension between safety and completeness also dictates how agents learn about their environments. As formalized by Juba et al. in Action Model Learning with Guarantees, learning algorithms can be tuned to output either sound or complete action models. Sound models prioritize safety by guaranteeing that an action's predicted effects are perfectly accurate, though they may be too conservative to find a plan. Complete models ensure a plan will be found if it exists, but they risk precision.


Querying Inconsistent and Complex Knowledge Bases

The utility of sound but incomplete approximations extends far beyond planning; it is equally vital for querying large, complex, or "dirty" datasets.

When a knowledge base contains contradictions or violates data constraints, computing exact answers under "consistent query semantics" requires evaluating every possible minimal repair of the data. To avoid this overhead, Greco et al. proposed an approximation algorithm in Computing Approximate Query Answers over Inconsistent Knowledge Bases. By leveraging a "universal repair" representation that modifies fact values rather than deleting data, their method computes approximate query answers in polynomial time. The answers are guaranteed to be sound (consistent), though they may omit some valid answers that an exhaustive, complete search would uncover.

Exact Consistent Query Answering        Universal Repair Approximation
┌────────────────────────────────┐      ┌────────────────────────────────┐
│ Evaluate all possible repairs  │      │ Compute a single consolidated  │
│ of the database (Exponential)  │      │ representation (Polynomial)    │
└───────────────┬────────────────┘      └───────────────┬────────────────┘
                │                                       │
                ▼                                       ▼
       All Valid Answers                       Guaranteed Sound Answers
       (Slow but Complete)                     (Fast but Incomplete)

This strategy of trading completeness for speed appears across several data management paradigms:


Broad Applications of the Trade-Off

The core philosophy—grouping complex elements into simpler representations to gain tractability—is a foundational paradigm in computer science. In an early paper on domain abstraction, 88) (ijcai 1987), it was established that grouping domain elements into equivalence classes simplifies logical unification. Depending on how the abstraction is constructed, it can yield a sound but incomplete framework that accelerates automated reasoning while quantifying the introduced error.

Even modern software engineering tools rely on this balance. In Bolt-on, Compact, and Rapid Program Slicing for Notebooks [Scalable Data Science], Shankar et al. designed a tool to isolate code dependencies in computational notebooks. They noted that static and dynamic analysis tools must navigate the soundness-completeness spectrum, forcing users to choose between absolute guarantees of correctness and ensuring that every potentially relevant line of code is included.

Ultimately, sound but incomplete approximations work because they align with practical priorities. In many real-world applications, receiving a partial list of perfectly accurate answers or finding a single safe plan quickly is far more valuable than waiting indefinitely for an exhaustive list of every possibility.

Key Foundational Work

Computational complexity of planning and approximate planning in the presence of incompleteness (2000) — contributed 2 concept elements to this direction.
Domain Abstraction and Limited Reasoning (1987) — 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_sound_but_incomplete_approximation_9642b863,
  title = {sound but incomplete approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sound-but-incomplete-approximation/rdr_9642b86317d5448e845c8890d5d38014},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sound_but_incomplete_approximation_9642b863_v1,
  title = {sound but incomplete approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sound-but-incomplete-approximation/rdr_9642b86317d5448e845c8890d5d38014/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake