Goal Driven Pruning for Scalable Deductive Reasoning

This direction is split into other directions: logic program pruning, magic sets rewriting. Its last version stays readable and citable here.

Version 1 of 160 papers87 conceptsfrozen 2026-10-04

In the world of automated reasoning, there is a classic tension between two ways of thinking. Top-down reasoning starts with a goal (a query) and works backward to find facts that support it. It is naturally focused but prone to infinite loops. Bottom-up reasoning starts with facts and derives everything possible. It is stable and exhaustive but suffers from a "grounding bottleneck"—it wastes immense energy deriving millions of facts that have nothing to do with the user's question.

The research direction described here focuses on bridging this gap. By using techniques like Magic Sets, relevance analysis, and constant propagation, researchers have developed ways to prune the search space of logic programs so that they only process data strictly necessary for a specific query.

The Grounding Bottleneck

Traditional deductive systems, such as those using Datalog or Answer Set Programming (ASP), often perform a "full materialization." They take a set of rules and a database of facts and compute the "least fixed point"—every single conclusion that can be drawn.

As Rehan Aziz, Geoffrey Chu, and Peter J. Stuckey point out in Grounding Bound Founded Answer Set Programs, this creates a massive overhead. If you only want to know if "John is a descendant of Mary," the system shouldn't have to calculate the entire family tree of the human race. Without pruning, systems evaluate variables and constraints that do not influence the final answer, leading to memory exhaustion.

Magic Sets: Teaching Bottom-Up Engines the Goal

One of the most influential solutions to this problem is the Magic Sets transformation. Originally popularized in the database community by researchers like Raghu Ramakrishnan 0001 and Divesh Srivastava in Semantics and Optimization of Constraint Queries in Databases, this technique rewrites a logic program to include "guard" predicates.

The intuition is simple: if the query is about a specific constant (e.g., UserID=123), the system generates a "magic" rule that propagates this constant through the logic. These magic predicates act as filters, ensuring that the bottom-up engine only derives facts that are "reachable" from the query constants.

Recent work has pushed this even further. Shaoyu Wang and Kai Zhao demonstrated in Goal-Driven Reasoning in DatalogMTL with Magic Sets that applying these transformations to temporal logic can result in a one-million-fold speedup. By making the program goal-driven, they allow the engine to ignore millions of irrelevant temporal facts.

Relevance Analysis and Dependency Graphs

Before the reasoning even begins, we can often determine which parts of a knowledge base are "dead weight." This is known as relevance analysis.

In Finding Answers and Generating Explanations for Complex Biomedical Queries, Esra Erdem 0001 and colleagues use a predicate dependency graph. By mapping how rules rely on one another, they can isolate the specific subset of a massive biomedical database (sometimes as small as 14% of the total data) that could possibly influence the query.

A more advanced version of this is abstracted relevance analysis. Michael Benedikt, Boris Motik, and Efthymia Tsamoura describe a method in Goal-Driven Query Answering for Existential Rules with Equality where they test rules against a simplified, "abstracted" version of the database. If a rule can't produce a result on the abstraction, it is mathematically guaranteed to be useless for the real data and is discarded before the main computation starts.

Sideways Information Passing

How does a constant from a query actually "travel" through a complex web of rules? This is handled by Sideways Information Passing (SIP).

When a rule has multiple conditions, SIP determines how the bindings from one condition are passed to the next. In Goal-Driven Query Answering over First- and Second-Order Dependencies with Equality, Efthymia Tsamoura and Boris Motik show that by carefully propagating these bindings, systems can reduce the number of derived facts to less than 1% of what exhaustive methods would produce. This allows for efficient reasoning even in the presence of complex "equality" rules that usually cause systems to crash.

Applications: From Bio-Medicine to Neurosymbolic AI

The ability to prune irrelevant logic is what makes modern symbolic AI practical at scale:

By treating the query not just as a question, but as a pruning constraint, this research direction transforms logic from a "brute force" generation of facts into a surgical, goal-oriented search.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_goal_driven_pruning_for_scalable_deducti_c23e6e8a,
  title = {Goal Driven Pruning for Scalable Deductive Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/goal-driven-pruning-for-scalable-deductive-reasoning/rdr_c23e6e8aa8cc4dd2820d5a7a038ab767},
  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_goal_driven_pruning_for_scalable_deducti_c23e6e8a_v1,
  title = {Goal Driven Pruning for Scalable Deductive Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/goal-driven-pruning-for-scalable-deductive-reasoning/rdr_c23e6e8aa8cc4dd2820d5a7a038ab767/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}