Demand Driven Inference in Reasoning Systems

49 concepts35 papers1 proposal

When building systems to reason about the world—whether through formal logic, probabilistic models, or neural networks—we constantly battle the curse of dimensionality. If a system attempts to pre-compute every possible logical consequence, sample every random variable, or evaluate every rule upfront, it quickly drowns in a combinatorial explosion.

Demand-driven inference (often called lazy evaluation) solves this by flipping the direction of computation. Instead of computing everything from the bottom up, a demand-driven system starts with a specific query and works backward, executing only the precise computations required to answer that query. By deferring expensive operations until they are strictly necessary, these systems can operate over massive, or even infinite, state spaces in finite time.


Taming Combinatorial Explosion in Logical Systems

Early automated theorem provers and expert systems frequently bottlenecked because they performed heavy mathematical work on rules and variables that ultimately had no bearing on the final conclusion. To make these engines practical, researchers began introducing structural checks that postponed expensive operations.

For example, in automated theorem proving, Norbert Eisinger demonstrated in [1] that integrating redundancy tests directly into connection graphs allows systems to postpone the computationally heavy process of variable unification. By waiting until lightweight structural checks flag a potential redundancy, the engine ensures that heavy mathematical work is reserved only for high-probability candidates.

[Traditional Forward Inference]
Facts & Rules ---> Exhaustive Unification ---> Massive State Space ---> Query Evaluation

[Demand-Driven Inference]
Query ---> Backward Chain ---> Lightweight Structural Filter ---> Targeted Unification

This philosophy of "waiting until forced" appears across several classical reasoning domains:

  • Expert Systems: Sauers et al. showed in [2] that delaying the evaluation of rule preconditions until after conflict resolution filters have been applied prevents unnecessary computational expenditure, ensuring the system only tests rules that are statistically likely to execute.
  • Qualitative Arithmetic: In large-scale physical simulations, Reid G. Simmons demonstrated in [3] that performing arithmetic inferences on-demand rather than pre-calculating all possible qualitative relationships saves massive amounts of computation, as only a small fraction of relationships are typically needed to resolve a specific query.
  • Knowledge Representation: In instance-heavy applications, MacGregor et al. argued in [4] that shifting from a full abstraction-based recognition strategy to a query-based backward-chaining approach avoids the overhead of managing redundant logical structures. Robert M. MacGregor extended this to first-order predicate calculus in [5], showing that triggering logical elaboration only when a specific query fails focuses resources strictly on query-relevant facts.
  • Truth Maintenance: Collins et al. tackled the notorious "label explosion" problem in [6] by introducing lazy context expansion, which defers the calculation of logical closures and consistency checks until a specific query or critical propagation step demands it.
  • Hybrid Reasoning: Even when combining logic with heavy numerical subroutines, Guan et al. showed in [7] that executing numerical calculations via a backward-chaining mechanism ensures that complex mathematical models are only triggered when a specific value is required to satisfy a logical rule.
  • Language Extensions: The authors of [8] introduced functional notation to Prolog by evaluating constraints associated with terms only when their values are needed for unification, naturally supporting the manipulation of infinite data structures.

Scaling Probabilistic Programming to Infinite Worlds

The demand-driven approach becomes even more critical in Probabilistic Programming Languages (PPLs), which often model "open-universe" scenarios where the number of objects or variables is unknown or theoretically infinite. Pre-sampling an infinite background is impossible.

Milch et al. solved this dilemma in [9] by introducing a stack-based sampling procedure for infinite contingent Bayesian networks. Instead of instantiating the entire model, the algorithm follows only "active" edges—dependencies that are strictly necessary to resolve the current query and evidence. By ignoring the infinite background of inactive variables, the algorithm guarantees computation completes in finite time.

To make this strategy performant, modern PPL compilers embed laziness directly into execution. Li et al. introduced the Swift compiler in [10], which bakes lazy evaluation into compiled inference code so that random variables are only sampled when their values are required to compute a specific query, closing the performance gap between generic PPLs and hand-optimized code. Similarly, Kiselyov et al. utilized delimited continuations in [11] to reify programs into search trees, automatically identifying and skipping the calculation of stochastic choices that do not influence the final query result.

When moving to relational and causal models, demand-driven evaluation prevents over-computation across shared structures:

  • Lazy Aggregation: In Probabilistic Relational Models, Kaelin et al. demonstrated in [12] that computing and caching the results of aggregation functions only when required by a query avoids redundant calculations when multiple child nodes share the same aggregated parents.
  • Evidence Path Restriction: Taghipour et al. showed in [13] that restricting the exploration of evidence paths to those capable of influencing a query prevents the computational waste of proving irrelevant facts that ultimately have no impact on the query's result.
  • Tabling and Memoization: Kersting et al. combined lazy sampling with memoization in [14], ensuring that probabilistic facts are evaluated exactly once per sample path, maintaining consistency across different branches of a proof without pre-sampling the entire state space.

Beyond Logic: Optimization, Streams, and Neural Circuits

The core intuition of demand-driven inference—deferring work until a query or threshold forces action—extends far beyond classical logic engines into modern optimization, data streaming, and deep learning.

SAT and XOR Solving

In modern constraint satisfaction, Gocht et al. demonstrated in [15] that generating reasons for variable assignments lazily—only when they are required for conflict analysis—saves significant overhead and avoids unnecessary computations for reasons that are never actually used during solving.

Streaming and Decision Problems

When processing high-speed data streams or large-scale recommendation pools, updating every parameter in real time is prohibitively expensive.

  • Duffield et al. showed in [16] that deferring the recalculation of sampling probabilities and estimated values until a specific key is revisited or a query is made avoids the overhead of performing complex mathematical operations for every incoming packet.
  • For large-scale decision problems, Yang et al. demonstrated in [17] that partitioning candidates based on uncertainty and managing them via a min-heap allows for lazy candidate elimination. Instead of exhaustively scanning millions of items at every step, the system only re-evaluates candidates when specific reward thresholds are crossed.
  • In distributed environments, Eiter et al. showed in [18] that implementing lazy evaluation across distributed reasoning nodes ensures downstream components only process data when upstream nodes signal an explicit change in state, eliminating redundant time-point re-evaluations.
  • In model validation, Isychev et al. optimized machine learning test suites in [19] by adopting a lazy approach where expensive model invocations are only performed when their output is strictly necessary to determine the final test outcome.

Demand-Driven Circuits in LLMs

Perhaps the most surprising discovery is that large language models naturally implement demand-driven reasoning internally.

[Input Tokens] ---> "If A implies B, and B implies C..." ---> [Latent Storage]
                                                                   |
                                                      (No heavy inference yet)
                                                                   |
[Query Token] ---> "Does A imply C?" -----------------------------> [Circuit Activation]
                                                                   |
                                                      (Specialized attention heads 
                                                       compute logical conclusion)

Hong et al. performed circuit analysis on transformers in [20] and discovered that models do not pre-calculate all possible logical inferences while encoding facts and rules. Instead, they exhibit a demand-driven behavior: the core logical processing circuits remain dormant until the model encounters a specific query token. Only when the final question triggers the need for a conclusion do specialized attention heads activate to locate rules, move information, and resolve the step-by-step logic.

Conclusion

Whether bypassing variable unification in a 1980s theorem prover, isolating active dependencies in an infinite Bayesian network, or activating attention heads in a modern transformer, demand-driven inference works for the same fundamental reason: it bounds computational cost by the complexity of the answer, not the complexity of the universe.


References

[1] Subsumption And Connection Graphs
[2] On the Requirements of Future Expert Systems
[3] Commonsense Arithmetic Reasoning
[4] Recognition Algorithms for the Loom Classifier
[5] A Description Classifier for the Predicate Calculus
[6] CATMS: An ATMS Which Avoids Label Explosions
[7] Model Expert System MES
[8] Term
[9] Approximate Inference for Infinite Contingent Bayesian Networks
[10] Swift: Compiled Inference for Probabilistic Programming Languages
[11] Monolingual Probabilistic Programming Using Generalized Coroutines
[12] A Study of Approximate Inference in Probabilistic Relational Models
[13] First-Order Bayes-Ball for CP-Logic
[14] Trading Memory for Answers: Towards Tabling ProbLog
[15] Tinted, Detached, and Lazy CNF-XOR Solving and Its Applications to Counting and Sampling
[16] Stream Aggregation Through Order Sampling
[17] Linear Bandit Algorithms with Sublinear Time Complexity
[18] A Distributed Approach to LARS Stream Reasoning (System paper)
[19] Lazy Testing of Machine-Learning Models
[20] A Implies B: Circuit Analysis in LLMs for Propositional Logical Reasoning

Key Foundational Work

E-Resolution: Extension of Resolution to Include the Equality Relation (1969) — contributed 1 concept elements to this direction.
Subsumption And Connection Graphs (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_demand_driven_inference_91ae632d,
  title = {demand-driven inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/demand-driven-inference/rdr_91ae632d3d0c4c889e07cb9600a58793},
  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_demand_driven_inference_91ae632d_v1,
  title = {demand-driven inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/demand-driven-inference/rdr_91ae632d3d0c4c889e07cb9600a58793/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