Exact probabilistic inference in complex graphical models and probabilistic logic programs is notoriously difficult. Whether computing marginal probabilities, solving Stochastic Boolean Satisfiability (SSAT), or finding a Marginal Maximum a Posteriori (MMAP) assignment, exact algorithms often exhibit an "all-or-nothing" behavior. As noted by Lee et al. (From Exact to Anytime Solutions for Marginal MAP), if an exact solver runs out of time or memory before completion, it returns absolutely nothing. This limitation is impractical for real-time, interactive, or time-sensitive applications where a usable, suboptimal answer delivered quickly is far better than a perfect answer delivered too late (Gorz et al. (Anytime Algorithms for Speech Parsing?)).
Anytime probabilistic inference solves this by transforming inference from a static calculation into a dynamic, resource-aware process. Instead of waiting for a single exact number, anytime algorithms provide immediate, valid lower and upper bounds on the target probability. As computation continues, these bounds monotonically tighten, converging toward the exact solution.
Prioritizing the State Space via Search
How do we bound a probability without looking at the entire system? The core intuition relies on the fact that in many real-world networks, a tiny fraction of variable assignments or states contains the vast majority of the probability mass.
By framing inference as a heuristic search problem, algorithms can explore the state space using a priority queue that prioritizes the most probable assignments first. For instance, Henrion (Search-Based Methods to Bound Diagnostic Probabilities in Very Large Belief Nets) demonstrated in diagnostic belief networks that bounding the relative probabilities of a subset of highly likely hypotheses yields strict absolute probability bounds.
Similarly, the authors of an early search approach (Average-case analysis of a search algorithm for) showed that when probabilities are extreme (close to 0 or 1), searching a tree of variable assignments in order of likelihood provides rapid estimates with guaranteed error bounds. For complex tasks like Marginal MAP, Lee et al. (From Exact to Anytime Solutions for Marginal MAP) applied weighted heuristic search to exact AND/OR search spaces, enabling rapid generation of high-quality solutions with guaranteed bounds instead of failing under resource limits.
Incremental Explanation and Logic Compilation
In probabilistic logic programming (PLP) and Weighted Model Counting (WMC), a query's probability is determined by the sum of the weights of all "possible worlds" or logical proofs (explanations) that make the query true. Finding all proofs is often computationally intractable.
Anytime algorithms bypass this by discovering explanations incrementally. Every time the engine finds a new independent proof or explanation, it establishes a strict lower bound on the true probability. As shown by Renkens et al. (Explanation-Based Approximate Weighted Model Counting for Probabilistic Logics), this explanation-based approach allows for a direct trade-off between computation time and the precision of the bounds. This strategy is also highly effective in probabilistic ontologies, where computing exact probabilities is often intractable, making lower-bound approximations from a subset of discovered explanations essential (Riguzzi et al. (Reasoning with Probabilistic Ontologies)).
To make this process efficient, frameworks like ProbLog use iterative deepening to expand the search space systematically, tracking both confirmed proofs (lower bounds) and potential unexplored paths (upper bounds) until the gap falls below a desired threshold (De Raedt et al. (ProbLog: A Probabilistic Prolog and Its Application in Link Discovery)).
Rather than separating logic generation from probabilistic calculation, Vlasselaer et al. (Anytime Inference in Probabilistic Logic Programs with Tp-Compilation) introduced $T_P$-compilation, which performs WMC on partially compiled logical formulas. This yields a guaranteed lower bound that improves continuously with each iteration. Even when dealing with massive knowledge graphs, limiting the forward-chaining iterations provides a reliable way to sidestep the grounding bottleneck and maintain anytime lower bounds (Tsamoura et al. (Beyond the Grounding Bottleneck: Datalog Techniques for Inference in Probabilistic Logic Programs)). This concept extends naturally to related domains like Stochastic Boolean Satisfiability (SSAT), where enforcing runtime limits allows solvers to derive tight upper and lower bounds on satisfying probabilities (Lee et al. (Solving Stochastic Boolean Satisfiability under Random-Exist Quantification)).
Dynamic Model Construction and Relaxation
Another powerful intuition for anytime inference is that we do not need to evaluate or even construct the entire probabilistic model to answer a specific query.
Instead of building a massive network upfront, Goldman et al. (Integrating Model Construction and Evaluation) proposed integrating model construction directly with evaluation. By evaluating the model as it is being built, the system can be interrupted at any stage to provide an approximate answer based on the partially constructed graph. For infinite or recursive models, the authors of a relational framework (Semantics and Inference for Recursive Probability Models) demonstrated that constructing increasingly larger network fragments captures the relevant dependencies for a query incrementally, converging steadily to the exact solution.
Alternatively, one can start with a simplified or relaxed version of the full problem and iteratively tighten it. Darwiche et al. (Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference) introduced this concept via "Lifted RCR." By relaxing complex constraints to allow fast, approximate first-order inference and then incrementally reintroducing those constraints over time, they created a tunable spectrum that smoothly transitions from rapid approximations to exact results.
Alternative Anytime Paradigms: Sampling and Clustering
While deterministic bounding via search or compilation is highly effective, anytime behavior can also be achieved through stochastic or structural approximations:
- Sampling: Wick et al. (Scalable Probabilistic Databases with Factor Graphs and MCMC.) utilized Markov Chain Monte Carlo (MCMC) sampling over factor graphs in probabilistic databases, where the accuracy of the query response improves continuously as more samples are drawn. In domains where subproblems are completely intractable due to high induced width, Marinescu et al. (Stochastic Anytime Search for Bounding Marginal MAP) combined search with importance sampling, using high-confidence stochastic estimates to establish lower bounds for otherwise untouchable problems.
- Structural Clustering: Structurally, the authors of a tree-approximation scheme (Tree Approximation for Belief Updating) extended mini-bucket techniques to tree decompositions, allowing users to tune accuracy parameters or halt execution early to obtain approximate beliefs for all variables simultaneously.
- Graceful Degradation: Early foundations like the Quickscore algorithm by Heckerman (A Tractable Inference Algorithm for Diagnosing Multiple Diseases) showed that algorithms designed to produce intermediate results can gracefully degrade performance under tight time constraints, providing valuable approximate answers when exact computation is too slow.
Key Foundational Work
A Tractable Inference Algorithm for Diagnosing Multiple Diseases (1989) — contributed 2 concept elements to this direction.
Search-Based Methods to Bound Diagnostic Probabilities in Very Large Belief Nets (1991) — contributed 1 concept elements to this direction.
Reflection and Action Under Scarce Resources: Theoretical Principles and Empirical Study (1989) — contributed 1 concept elements to this direction.