Query Driven Pruning for Large Scale Logical Inference

28 concepts20 papers1 proposal

In the ideal world of symbolic AI, a knowledge base contains everything a system knows, and an inference engine simply deduces the truth. In practice, however, large-scale reasoning faces a "combinatorial explosion." When a database contains millions of facts and rules, a naive search for an answer is like looking for a needle in a haystack—except the haystack grows exponentially with every step of the search.

The solution to this bottleneck is query-driven pruning. Instead of evaluating the entire knowledge base, these techniques isolate the specific subset of rules and facts that are logically capable of influencing a particular query. By throwing away the "irrelevant" parts of the program before the heavy lifting begins, systems can turn queries that would otherwise crash from memory exhaustion into results delivered in seconds.

The Principle of Relevance

The core intuition behind pruning is that most knowledge is irrelevant to any specific question. If you ask a medical database about "insulin," rules regarding "orbital mechanics" should never be touched. While this seems obvious, formalizing "relevance" in logic is complex.

Early work by Jared L. Darlington established that search spaces could be mitigated by restricting the inference engine to a "logical lineage"—only deriving new clauses that descend directly from the initial query. Eliezer L. Lozinskii refined this by focusing on how constants (like specific drug names) propagate through variables. By mapping these connections, the APEX algorithm ensures the system only explores data paths that share constants with the query, guaranteeing a finite search even in recursive databases.

Dependency Graphs and Axiom Pruning

To prune effectively, a system must understand the "shape" of its knowledge. Erdem et al. demonstrate this using a predicate dependency graph. By treating rules as nodes and logical dependencies as edges, the system can perform a reachability analysis. If a rule cannot reach the query node in the graph, it is pruned. In complex biomedical datasets, Erdem et al. found that the necessary ruleset for a query might be as small as 14% of the total database.

This "relevant-only" approach allows general-purpose tools to compete with specialized ones. Tsarkov et al. showed that general First-Order Logic provers, which usually struggle with large ontologies, can achieve performance comparable to specialized reasoners simply by pruning unnecessary axioms before processing begins. Similarly, Luu et al. and the authors of the study use axiom-based pruning to resolve contradictions between high-level rules and massive datasets, focusing diagnostic resources only on the specific formulas responsible for a clash.

Magic Sets and Constraint Propagation

One of the most powerful mechanisms for pruning is the Magic Sets algorithm. The goal of Magic Sets is to give a bottom-up inference engine (which is stable and fast) the "focus" of a top-down search.

As Ramakrishnan et al. explain, this involves propagating constraints from the query back into the program rules. If a query asks for the ancestors of "John," the system rewrites the rules so that it only generates "ancestors of John," rather than generating every ancestor-descendant pair in the entire database. Benedikt et al. applied this to existential rules, showing that relevance analysis can prevent systems from wandering into infinite search spaces. For data integration, Faber et al. and the authors utilized query-driven filtering to handle inconsistent data, reducing the search space by orders of magnitude.

Pruning for Probabilistic and Neurosymbolic AI

Modern AI often combines logic with probability or neural networks, but these hybrid systems are even more sensitive to scale. In Probabilistic Logic Programming (PLP), the system must often "ground" the program—turning abstract rules into every possible concrete instance.

Fierens et al. and the authors address this by using SLD-resolution to identify a "minimal subset" of the program. By pruning inactive rules and irrelevant branches, they can reduce the size of the logical representation by up to 90%, making probabilistic inference computationally tractable. This is echoed in newer neurosymbolic frameworks; Geh et al. and the authors note that without automated relevance-based pruning, these systems waste significant resources on logical branches that do not contribute to the final differentiable output.

Finally, pruning can be guided by historical success. Sharma et al. introduced retrograde analysis, which pre-calculates successful inference paths from the bottom up. This creates a "map" of productive search directions. By prioritizing paths that match known successful proofs, the system can speed up complex queries by over 20x, effectively pruning "doomed" branches before they are even explored.

Whether through dependency graphs, constraint propagation, or path prioritization, the goal remains the same: ensuring that the engine's effort is proportional to the query's complexity, not the size of the entire universe of known facts.

Key Foundational Work

Theorem Provers as Question Answerers (1969) — contributed 2 concept elements to this direction.
Evaluating Queries in Deductive Databases by Generating (1985) — 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_logic_program_pruning_a41231c6,
  title = {logic program pruning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logic-program-pruning/rdr_a41231c6ebc44fad8b220d739790f3f4},
  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_logic_program_pruning_a41231c6_v1,
  title = {logic program pruning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logic-program-pruning/rdr_a41231c6ebc44fad8b220d739790f3f4/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