Interleaving Grounding and Search in Relational Solvers

33 concepts17 papers1 proposal

Relational languages—such as Answer Set Programming (ASP), First-Order Logic, and Markov Logic Networks (MLNs)—allow us to express complex domains using compact, abstract rules. For instance, we can define a transitivity rule for a network using variables: if $X$ is connected to $Y$, and $Y$ is connected to $Z$, then $X$ is connected to $Z$.

To solve these problems, traditional reasoning engines rely on a "ground-and-solve" paradigm. Before the search for a solution begins, the engine expands every abstract rule into all possible concrete combinations of objects in the domain—a process known as grounding or propositionalization. If a domain contains $N$ objects, a rule with three variables requires generating $N^3$ propositions. As Sandeep Chintabathina outlines in Towards Answer Set Prolog Based Architectures for Intelligent Agents, this upfront expansion creates a massive computational bottleneck, causing solvers to exhaust memory and crash long before the actual inference or search phase can begin.

The Reality of Relational Sparsity

The core insight that makes upfront grounding unnecessary is relational sparsity. In real-world datasets, the vast majority of potential relationships do not exist. In a medical database, most patients do not have most diseases; in a social network, most people are not connected to one another.

When a traditional solver grounds a theory completely, it treats every potential relationship as equally active. As Singla et al. explain in Memory-Efficient Inference in Relational Domains, this ignores the fact that most generated clauses are trivially satisfied by the absence of data. For example, if person $A$ and person $B$ are not friends, any rule predicated on their friendship is automatically satisfied and consumes memory without contributing to the search.

To exploit this, solvers can adopt a "default-false" representation. Poon et al. demonstrate in A General Method for Reducing the Complexity of Relational Inference and its Application to MCMC that by assuming a default state for the vast majority of potential groundings, an algorithm can focus its memory and computation exclusively on the sparse subset of active elements that deviate from the default. Similarly, Shavlik et al. show in Speeding Up Inference in Markov Logic Networks by Preprocessing to Reduce the Size of the Resulting Grounded Network that turning the closed-world assumption into a computational advantage allows for early pruning of the grounding space, maintaining a sparse representation of only the bindings that remain uncertain.

This sparsity operates powerfully at an instance level. Chechetka et al. point out in Evidence-Specific Structures for Rich Tractable CRFs that while a global dependency graph across an entire dataset may appear dense and intractable, the actual dependencies relevant to any single data instance are highly sparse. By evaluating only the non-zero tuples present in empirical data rather than constructing full joint probability tables, Dechter et al. demonstrate in Graph-based Complexity for Causal Effect by Empirical Plug-in that the computational cost can scale with the number of samples rather than the exponential size of the variable state space.

Grounding on Demand

Instead of separating grounding and solving into sequential steps, the modern alternative is to interleave them. This is known as lazy grounding or grounding-on-demand. The solver begins searching for a solution with a minimal, partially grounded theory, expanding rules only when the search trajectory makes them relevant.

De Cat et al. formalize this mechanism in Lazy Model Expansion by Incremental Grounding by maintaining a pool of "delayed sentences" that are materialized only when necessary. In their subsequent work, Lazy Model Expansion: Interleaving Grounding with Search, the authors introduce symbolic proxies to represent ungrounded parts of the problem space. This prevents memory exhaustion in massive domains by ensuring that constraints are instantiated incrementally only as they become relevant to the current search state.

Traditional Workflow:
[First-Order Theory] ---> (Full Grounding) ---> [Massive Propositional Theory] ---> (Solver)

Lazy Grounding Workflow:
[First-Order Theory] ---> (Partial Grounding) ---> [Minimal Propositional Theory] ---> (Solver)
                                                              ▲                     │
                                                              └─(Instantiate on)────┘
                                                                ( Demand during)
                                                                (    Search    )

This strategy has dramatically improved the scalability of diverse logic programming paradigms. For example, Eiter et al. apply lazy grounding to HEX-programs in Lazy-Grounding for Answer Set Programs with External Source Access, bypassing the memory constraints of external data sources by materializing propositional components on the fly. As highlighted by Russo et al. in Introduction to the 36th International Conference on Logic Programming Special Issue I and Introduction to the 36th International Conference on Logic Programming Special Issue II, deferring rule expansion until required during computation mitigates memory bottlenecks in large-scale combinatorial search problems. The technique can even handle complex logical aggregates: Bomanson et al. demonstrate in Enhancing Lazy Grounding with Lazy Normalization in Answer-Set Programming that converting aggregates into standard rules on-the-fly during search avoids the traditional grounding bottleneck for complex mathematical constraints.

Lazy Constraint Instantiation via Violations

A particularly powerful way to implement lazy grounding is to let the solver guess a solution first, and then use first-order rules as a "critic" that adds constraints only when they are violated.

In probabilistic relational models, this is exemplified by Cutting Plane Inference (CPI). As Riedel et al. demonstrate in Cutting Plane MAP Inference for Markov Logic, instead of pre-generating all possible logical interactions, the inference process scales with the complexity of the actual solution. The solver starts with a tiny subset of constraints, finds a candidate solution, and lazily instantiates only the specific formulas that the current candidate actively violates. This reduces the number of active formulas by several orders of magnitude without sacrificing exact accuracy.

The same principle applies to deterministic verification and optimization frameworks. Lal et al. combine relational learning with Satisfiability Modulo Theories (SMT) solvers in Combining Relational Learning with SMT Solvers Using CEGAR. By utilizing Counterexample-Guided Abstraction Refinement (CEGAR), the authors avoid full propositionalization by only adding hard logical constraints to the model when they are explicitly violated by a candidate solution, focusing computational resources strictly on the relevant rules.

Combining Abstraction with Propositional Speed

Ultimately, lazy grounding succeeds because it bridges a long-standing trade-off in artificial intelligence: the memory efficiency of abstract, first-order representations versus the raw execution speed of propositional solvers.

As Corrêa et al. note in Lifted Planning: Recent Advances in Planning Using First-Order Representations, modern planning architectures achieve performance parity with fully grounded systems by utilizing grounding-on-demand. By deferring the creation of propositional representations until specific variables are required to validate a search node, solvers can maintain a compact memory footprint while leveraging the rapid, specialized search capabilities of propositional engines. Instead of wasting resources building a massive, mostly irrelevant network upfront, the solver builds exactly the network it needs to prove the solution's validity.

Key Foundational Work

Memory-Efficient Inference in Relational Domains (2006) — contributed 4 concept elements to this direction.
A General Method for Reducing the Complexity of Relational Inference and its Application to MCMC (2008) — contributed 3 concept elements to this direction.
Towards Answer Set Prolog Based Architectures for Intelligent Agents (2008) — 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_lazy_grounding_0c4b6e20,
  title = {lazy grounding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lazy-grounding/rdr_0c4b6e20fc714bf1b96f2523a6fef191},
  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_lazy_grounding_0c4b6e20_v1,
  title = {lazy grounding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lazy-grounding/rdr_0c4b6e20fc714bf1b96f2523a6fef191/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