Committed Choice as a Source of Disjointness: Exact Inference for Probabilistic Logic Programs with Cut and Structured Loops

Probabilistic logic programs attach probabilities to facts. The chance that a query holds is the total probability of all "possible worlds" (random choices of which facts are true) in which the query can be proved. Computing this is hard because different proofs share facts, so their probabilities cannot simply be added. This is the disjoint-sum problem. Systems such as ProbLog solve it by collecting every proof into one Boolean formula and compiling that formula into a binary decision diagram (BDD), a graph in which every root-to-leaf path is mutually exclusive, so probabilities can be summed exactly. The price of this approach is that it has no place for the control constructs logic programmers use to tame search: Prolog's cut, if-then-else, "take the first answer," and structured loops. Cutting a branch during proof search throws away worlds, and the compiled formula then gives the wrong probability.

This note argues that the tension points the wrong way. Committed choice ("use the first branch that works, and only then consider the next") is itself a way to produce disjoint cases: the worlds where branch 1 fires and the worlds where branch 1 fails and branch 2 fires cannot overlap. We propose to give cut, if-then-else, once, and Logal-style bounded loops an exact per-world meaning. Each world runs as an ordinary deterministic Prolog program, cut included. We then compute query probabilities by symbolically executing the search tree once across all worlds, labelling each node with a BDD of the worlds that reach it. Under a first-answer reading, success leaves are disjoint by construction, so the final probability is a plain sum. BDD work is needed only for the world sets attached to nodes, and the program's own control order supplies a natural BDD variable ordering.

Core Claim

A program with structured control has a clean distribution semantics that no system in this file provides. The probability of query $q$ is the measure of worlds $w$ in which standard Prolog execution of the program restricted to $w$ succeeds. We claim this quantity can be computed exactly by a world-set-labelled search. Every node $n$ of the search tree carries a Boolean function $W_n$ over the probabilistic facts. A subgoal that uses fact $f$ conjoins $f$ onto the label of its child. A cut executed at node $n$ removes the worlds $W_n$ from every later sibling alternative. For a first-answer query the success leaves $\ell$ then satisfy $W_\ell \wedge W_{\ell'} = \bot$, meaning the two leaves share no world, whenever $\ell \neq \ell'$. Therefore

$$P(q) = \sum_{\ell \in \text{Succ}} P(W_\ell),$$

where $P(W_\ell)$ is computed by a linear BDD traversal. The disjointness follows from the same property that makes Prolog execution deterministic within a world: at most one first success exists per world.

Two consequences make this more than bookkeeping. First, a non-ground cut such as p(X) :- q(X), !, r(X) has a world-dependent "first answer." Answer $a_i$ of q is committed in exactly the worlds where q(a_i) holds and no earlier answer $a_j$, $j<i$, holds. That is an ordered, disjoint case split that neither hand-written negation nor declarative ProbLog expresses directly. Second, the order in which the program consults facts is a candidate BDD variable order obtained for free. This addresses the missing ordering heuristics that Scaling exact inference for discrete probabilistic programs (Dice) explicitly leaves open, since Dice relies on syntactic ordering.

Relation to Prior Work

The control-flow literature motivates the constructs but gives no probabilistic account of them. Logal packages cut and repeat into structured loops with generators, pre-tests, do_one/do_any bodies, and post-tests. It remains syntactic sugar over procedural pruning, which is exactly what breaks ProbLog. We reuse its loop grammar as the source language. Applications of the Situation Calculus To Formalizing Control and Strategic gives cut a declarative semantics through an accessibility predicate, but it is unique only for stratified programs. That result constrains us. We deliberately choose an operational per-world semantics, which is defined whenever each world's execution terminates, and we give up a model-theoretic reading in exchange.

On the inference side, ProbLog and its implementation paper supply the proofs-then-BDD pipeline we depart from. They enumerate all proofs and pay for disjointness afterward. We produce disjoint cases during search. Trading Memory for Answers: Towards Tabling ProbLog is the closest mechanism. Its probnot tables a ground subgoal and negates its compiled proofs, which is essentially what our label update needs when an earlier branch fails. We reuse tabling to compute the complete world set of a condition. It differs from our work in that it covers only ground negation, not ordered answers, loops, or cut. Dice already compiles functional if-then-else into BDD if-then-else operations with modular reuse, and it handles observations. It lacks unification, nondeterministic proof search, and loops, which is precisely the relational setting here. Sum-Product Loop Programming supports loops over probabilistic circuits, but only in a functional language without resolution. Efficient Counterfactual Reasoning in ProbLog via Single-World Intervention Programs shows that program-level rewriting before compilation can shrink formulas, which supports our choice to transform at the level of control rather than at the circuit. An Algebraic Prolog for Reasoning about Possible Worlds matters for scope. For idempotent semirings, disjointness is unnecessary, so our gain should appear only under probability-style (non-idempotent) aggregation. We use this as a built-in control condition in the experiments.

Research Program

We will build a symbolic Prolog interpreter, on top of a tabled ProbLog-style engine, whose search states carry BDD world labels. The source language adds if-then-else, once, cut restricted to clause bodies, and Logal's generalized loop. Loops must have an explicit iteration bound or a post-test guaranteed to trigger within a bound, because exact BDD methods cannot handle unbounded recursion (a limitation Dice also states).

The theory component proves two things. The first is correctness: the computed $P(q)$ equals the per-world Monte Carlo limit for every program whose per-world executions all terminate. The second is the disjointness lemma above. We will also characterize when a cut is "green," meaning removing it leaves the per-world answer unchanged. For such programs our semantics coincides with plain ProbLog, which gives a free consistency test.

The engineering component covers three pieces. The first is ordered-answer labelling for non-ground cuts. The second is compilation of loop iterations as reusable sub-BDDs, following Dice's modular caching. The third is a control-order variable ordering, in which facts are numbered in the order the leftmost-first search first consults them. We will compare that ordering against the engine's default and against dynamic sifting.

Baselines

The naive reference point is to delete all cuts and control constructs and run standard ProbLog. On programs with non-green cuts this answers a different question. We report its absolute probability error against ground truth to show that the semantics matters, and its runtime to show what control-free enumeration costs.

The strongest exact competitor is a hand or automatic rewrite of each cut into negation-as-failure, compiled by tabled ProbLog with probnot as in Trading Memory for Answers: Towards Tabling ProbLog. An ordered answer set becomes clauses of the form q(a_i), \+ q(a_1), …, \+ q(a_{i-1}). This baseline is strong because it is semantically equivalent on ground conditions and uses mature machinery. For fairness, both systems share the same BDD package, the same tabling, the same timeout and memory cap, and the same variable-ordering options. We beat this baseline only if we are strictly faster or smaller in peak BDD nodes on a majority of instances, or solve instances it cannot solve within the cap. The closest reported reference for this engine is the tabling paper's bloodtype result: a tree-depth-3 task took 1740 s with standard resolution and 4.3 s with tabling. That result is for Monte Carlo, not for exact inference with cut. For exact inference with cut, no reported result was found on Lacuna.

For the functional fragment (reachability on Dice's diamond and ladder networks, and a loop-based Luhn checksum), Dice and Dice.jl are the exact baselines. Dice reports completing the Munin Bayesian network in 3500 ms versus 2.2×10^7 ms for Ace. Dice.jl reports handling 10+ Luhn digits in seconds where WebPPL and Psi fail beyond 4–5. We run their released encodings under identical caps and count matching their scaling curves as success. We do not expect to beat a compiler specialized for that fragment.

For approximate inference, per-world Monte Carlo runs the real Prolog program with real cut in each sampled world. It is trivially correct in the limit, so we compare wall-clock time to reach a given relative error. No reported accuracy-versus-time figure was found on Lacuna for ProbLog Monte Carlo on these tasks.

Two ablations isolate the ingredients. The first swaps the control-order variable ordering for the default ordering. The second flattens our disjoint leaf labels into a single DNF and compiles it the standard way, which tests whether disjointness produced during search, rather than the semantics alone, drives the gains.

Why not just…?

Why not just rewrite cuts as negation-as-failure and use existing ProbLog? This is the real threat. For ground if-then-else it yields the same probabilities, so our semantics adds nothing there. What it adds is automation for non-ground first-answer cuts and loops, whose rewrites grow quadratically in the number of answers. It may also compile faster because disjoint labels avoid re-deriving the negated condition. The negation-rewrite baseline and the flattening ablation settle this directly. If the rewrite matches us in time and BDD size everywhere, the contribution shrinks to a correctness proof plus a source-to-source compiler, and we will say so.

Why not just sample worlds and run ordinary Prolog? Sampling gets cut semantics for free, and for moderate probabilities it may be good enough. The file reports that Monte Carlo in ProbLog needs impractically many samples for low-probability queries (On the Implementation of the Probabilistic Logic Programming Language ProbLog), and that exact compilation handles hard constraints where sampling struggles (Scaling integer arithmetic in probabilistic programs). Our time-to-error curves, stratified by query probability, will show where exact inference wins. We expect that to be on rare-event Biomine queries and on conditioned checksum queries.

Why not just use answer set programming, which needs no procedural control? Stable-model probabilistic reasoning requires enumerating models, and smProbLog identifies that enumeration as its bottleneck. Grounding the full program is also infeasible for a 6-million-edge network when the query touches a local neighbourhood (What Is Answer Set Programming?). ASP also expresses "first answer in program order" only awkwardly. We do not run this as a main baseline.

Why not just use better generic BDD reordering? Dynamic sifting may recover most of the control-order benefit. The ordering ablation includes sifting explicitly. If sifting matches control order, we drop the ordering claim and keep the disjointness claim.

Proposed Experiments

We construct cut-bearing workloads on the benchmarks in the file. On Biomine subgraphs (the 79-node/144-edge and 5,220-node/11,532-edge networks from the ProbLog implementation paper), we write priority-routing queries that commit to the first reachable intermediate hub, which is a non-ground cut. On the genealogical bloodtype model we write inheritance rules as if-then-else over parental genotypes, varying tree depth from 0 to 3. On the diamond and ladder reachability programs, and on the Luhn checksum written as a Logal for-loop over digits, we sweep the digit count.

The metrics are exact-inference wall time, peak BDD node count, and absolute error against the Monte Carlo limit. Correctness comes first: our probabilities must agree with long Monte Carlo runs on every instance and with plain ProbLog on green-cut programs.

The decisive checks are threefold. First, the flattening ablation must lose to full disjoint labelling on non-ground-cut workloads. If it does not, disjointness produced during search is not the mechanism. Second, we must beat the negation-as-failure rewrite on at least the Biomine priority-routing workload as answer counts grow. Third, as a sanity check, the advantage should vanish when the same programs run under an idempotent semiring such as most-probable-explanation. The aProbLog analysis predicts that there, disjointness buys nothing, and seeing no gain would confirm that the gains come from resolving the disjoint-sum problem rather than from incidental engineering.