Probabilistic Delta Debugging

DDMin follows a fixed script: partition into n chunks, test each chunk and its complement, double n, and repeat. Test outcomes are only used to guide the scripted steps—the oracle’s signal is otherwise ignored.

ProbDD maintains a probability model over units, estimating how likely each unit is to be essential (i.e., to survive into the minimized result). It updates that model after every test and, instead of following a preset schedule, chooses at each step the removal expected to produce the largest reduction. Failed removals then inform the model to avoid similar attempts.

A Probability Model

Give every unit a probability that it is essential—that it survives into the minimized result. Everything starts at a small prior p0.

The model only learns from failed removals; a success just shrinks the configuration behind its back. sync realigns them each round: forget removed units—or we would propose them forever—and seed new ones at p0 (that’s the first round, where the model starts empty).

struct ProbDD<U: AtomicUnit> {
    /// `unit2prob[u]`: the belief that `u` is *essential*.
    unit2prob: HashMap<U, f64>,
    /// The prior for unseen units.
    p0: f64,
}

impl<U: AtomicUnit> ProbDD<U> {
    /// Realign the model with `config`.
    fn sync(&mut self, config: &Configuration<U>) {
        self.unit2prob.retain(|u, _| config.contains(u));
        for &u in config {
            self.unit2prob.entry(u).or_insert(self.p0);
        }
    }
}

Choosing What To Remove

Removing a set of units only succeeds if every unit in it is non-essential. Suppose we remove $k$ units with probabilities $p_1,\dots ,p_k$. The probability of success is ${\prod }_{i=1}^k(1-p_i)$, so the expected number of units a removal will delete is $k\cdot {\prod }_{i=1}^k(1-p_i)$.

ProbDD sorts units by probability and removes the prefix that maximizes that gain.

/// Choose the removal set with the highest *expected gain*.
fn best_prefix<U: AtomicUnit>(
    unit2prob: &HashMap<U, f64>,
) -> Vec<U> {
    let mut units: Vec<U> =
        unit2prob.keys().copied().collect();
    // ascending by probability; ties by id for a reproducible demo.
    units.sort_by(|a, b| {
        unit2prob[a]
            .partial_cmp(&unit2prob[b])
            .unwrap()
            .then(a.cmp(b))
    });

    let mut survive = 1.0; // ∏ (1 - p) over the current prefix
    let (mut best_k, mut best_gain) = (0, 0.0);
    for (i, u) in units.iter().enumerate() {
        survive *= 1.0 - unit2prob[u];
        // gain = k · ∏(1 - p)
        let gain = (i + 1) as f64 * survive;
        if gain > best_gain {
            (best_k, best_gain) = (i + 1, gain);
        }
    }

    units.truncate(best_k);
    units
}

Learning From Failure

When a removal fails, at least one of those units was essential after all, so every unit in it becomes more suspect. Bayes’ rule says exactly how much. The evidence is “this removal failed”, which the model expected with probability $1-{\prod }_i(1-p_i)$ (the removal succeeds only if every unit in it is non-essential). And if a given unit is essential, the failure was certain—the likelihood is $1$. Prior times likelihood over evidence:

$$p\leftarrow \frac{p\cdot 1}{1-{\prod }_i(1-p_i)}$$

A removal of a single unit that fails is conclusive: the denominator reduces to $p$ itself, so that unit’s probability jumps straight to 1.

Tip

Press play to watch three units start at the prior 0.1, rise after a failed bulk removal, then watch unit 2 get pinned to 1.000 the moment removing it alone fails.

use std::collections::HashMap;
trait AtomicUnit: Copy + Eq + std::hash::Hash + Ord {}
impl<T: Copy + Eq + std::hash::Hash + Ord> AtomicUnit for T {}
/// A removal of `pre` just failed: raise the belief of every unit in it.
fn bayes_update<U: AtomicUnit>(
    unit2prob: &mut HashMap<U, f64>,
    pre: &[U],
) {
    let survive: f64 =
        pre.iter().map(|u| 1.0 - unit2prob[u]).product();
    let denom = 1.0 - survive;
    if denom <= 0.0 {
        return;
    }
    for u in pre {
        let p = unit2prob[u];
        unit2prob.insert(*u, (p / denom).min(1.0));
    }
}

fn show(probs: &HashMap<u32, f64>) -> Vec<String> {
    let mut v: Vec<(u32, f64)> =
        probs.iter().map(|(&u, &p)| (u, p)).collect();
    v.sort_by_key(|&(u, _)| u);
    v.iter().map(|(u, p)| format!("{u}:{p:.3}")).collect()
}

fn main() {
    let mut probs: HashMap<u32, f64> =
        [(1, 0.1), (2, 0.1), (3, 0.1)].into_iter().collect();
    println!("prior:                 {:?}", show(&probs));
    bayes_update(&mut probs, &[1, 2, 3]);
    println!("after {{1,2,3}} fails:   {:?}", show(&probs));
    bayes_update(&mut probs, &[2, 3]);
    println!("after {{2,3}} fails:     {:?}", show(&probs));
    bayes_update(&mut probs, &[2]);
    println!("after {{2}} alone fails: {:?}", show(&probs));
}

ProbDD Policy

Let’s look back at the delta debugging loop:

/// A candidate removal set
type Delta<U> = HashSet<U>;

/// The main loop of delta debugging
fn reduce<U: AtomicUnit, P: Policy<U>>(
    units: Configuration<U>,
    oracle: &Oracle<U>,
    mut policy: P,
) -> Configuration<U> {
    let mut config = units;
    loop {
        let mut reduced = None;

        for delta in policy.propose(&config) {
            // an empty delta would be a no-op
            // that could never make progress.
            assert!(!delta.is_empty());

            let candidate = &config - &delta;
            if oracle(&candidate) == Verdict::Interesting {
                reduced = Some(candidate);
                break;
            }
        }

        // the policy decides when to stop
        let keep_going =
            policy.on_reduced(reduced.as_ref());

        if let Some(candidate) = reduced {
            config = candidate; // update the current configuration
        }

        if !keep_going {
            break;
        }
    }

    config
}

If the current candidate removal fails, the loop iterates the next candidate and tries again; otherwise, it breaks and calls propose again with the new configuration. Therefore, the act of iterating to the next candidate is the “that removal failed” signal that ProbDD needs to update its model.

Now, let’s implement the new policy for ProbDD:

impl<U: AtomicUnit> Policy<U> for ProbDD<U> {
    fn propose(
        &mut self,
        config: &Configuration<U>,
    ) -> impl Iterator<Item = Delta<U>> {
        self.sync(config);
        let unit2prob = &mut self.unit2prob;

        // pulling the next delta means the previous one failed
        let mut last: Option<Vec<U>> = None;
        std::iter::from_fn(move || {
            if let Some(pre) = &last {
                bayes_update(unit2prob, pre);
            }
            // Done once every survivor is believed essential (p = 1).
            if unit2prob.values().all(|&p| p >= 1.0) {
                return None;
            }
            let pre = best_prefix(unit2prob);
            if pre.is_empty() {
                return None;
            }
            last = Some(pre.clone());
            Some(pre.into_iter().collect())
        })
    }
}

Note

Unlike DDMin, ProbDD does not march down to singleton chunks on a schedule, so it guarantees only conditional 1-minimality (1-minimal when the units are independent). However, our loop above guarantees that a fixpoint is reached, so the result is 1-minimal.

Run It

Now, let’s see how ProbDD works on the same example as DDMin.

Tip

Press play to minimize the same {1, ..., 8} problem as the DDMin page (“interesting iff it keeps 2 and 7”).

// Probabilistic delta debugging: same loop, an adaptive policy. The framework
// below (`reduce`, `Policy`, and the core types) is byte-for-byte identical to
// `ddmin.rs`; only the policy is swapped. Compiles and runs on its own:
//
//     rustc --edition 2024 probdd.rs && ./probdd

use std::collections::HashMap;
use std::collections::HashSet;

/// An indivisible piece of the input: a char, token, line, etc.
trait AtomicUnit: Copy + Eq + std::hash::Hash + Ord {}
impl<T: Copy + Eq + std::hash::Hash + Ord> AtomicUnit for T {}

/// The units we keep.
type Configuration<U> = HashSet<U>;

#[derive(PartialEq)]
enum Verdict {
    Interesting,    // still triggers the bug
    NotInteresting, // does not trigger the bug or is invalid
}

type Oracle<U> = dyn Fn(&Configuration<U>) -> Verdict;

/// A candidate removal set
type Delta<U> = HashSet<U>;

/// The main loop of delta debugging
fn reduce<U: AtomicUnit, P: Policy<U>>(
    units: Configuration<U>,
    oracle: &Oracle<U>,
    mut policy: P,
) -> Configuration<U> {
    let mut config = units;
    loop {
        let mut reduced = None;

        for delta in policy.propose(&config) {
            // an empty delta would be a no-op
            // that could never make progress.
            assert!(!delta.is_empty());

            let candidate = &config - &delta;
            if oracle(&candidate) == Verdict::Interesting {
                reduced = Some(candidate);
                break;
            }
        }

        // the policy decides when to stop
        let keep_going =
            policy.on_reduced(reduced.as_ref());

        if let Some(candidate) = reduced {
            config = candidate; // update the current configuration
        }

        if !keep_going {
            break;
        }
    }

    config
}

trait Policy<U: AtomicUnit> {
    /// Generate candidate removal sets *lazily*.
    fn propose(
        &mut self,
        config: &Configuration<U>,
    ) -> impl Iterator<Item = Delta<U>>;

    /// React to a reduction pass.
    /// `reduced` is `Some` if the pass removed anything,
    /// `None` if it made no progress.
    /// Return `true` to keep going, `false` to stop.
    /// The default stops at the fixpoint.
    fn on_reduced(
        &mut self,
        reduced: Option<&Configuration<U>>,
    ) -> bool {
        reduced.is_some()
    }
}

struct ProbDD<U: AtomicUnit> {
    /// `unit2prob[u]`: the belief that `u` is *essential*.
    unit2prob: HashMap<U, f64>,
    /// The prior for unseen units.
    p0: f64,
}

impl<U: AtomicUnit> ProbDD<U> {
    /// Realign the model with `config`.
    fn sync(&mut self, config: &Configuration<U>) {
        self.unit2prob.retain(|u, _| config.contains(u));
        for &u in config {
            self.unit2prob.entry(u).or_insert(self.p0);
        }
    }
}

/// Choose the removal set with the highest *expected gain*.
fn best_prefix<U: AtomicUnit>(
    unit2prob: &HashMap<U, f64>,
) -> Vec<U> {
    let mut units: Vec<U> =
        unit2prob.keys().copied().collect();
    // ascending by probability; ties by id for a reproducible demo.
    units.sort_by(|a, b| {
        unit2prob[a]
            .partial_cmp(&unit2prob[b])
            .unwrap()
            .then(a.cmp(b))
    });

    let mut survive = 1.0; // ∏ (1 - p) over the current prefix
    let (mut best_k, mut best_gain) = (0, 0.0);
    for (i, u) in units.iter().enumerate() {
        survive *= 1.0 - unit2prob[u];
        // gain = k · ∏(1 - p)
        let gain = (i + 1) as f64 * survive;
        if gain > best_gain {
            (best_k, best_gain) = (i + 1, gain);
        }
    }

    units.truncate(best_k);
    units
}

/// A removal of `pre` just failed: raise the belief of every unit in it.
fn bayes_update<U: AtomicUnit>(
    unit2prob: &mut HashMap<U, f64>,
    pre: &[U],
) {
    let survive: f64 =
        pre.iter().map(|u| 1.0 - unit2prob[u]).product();
    let denom = 1.0 - survive;
    if denom <= 0.0 {
        return;
    }
    for u in pre {
        let p = unit2prob[u];
        unit2prob.insert(*u, (p / denom).min(1.0));
    }
}

impl<U: AtomicUnit> Policy<U> for ProbDD<U> {
    fn propose(
        &mut self,
        config: &Configuration<U>,
    ) -> impl Iterator<Item = Delta<U>> {
        self.sync(config);
        let unit2prob = &mut self.unit2prob;

        // pulling the next delta means the previous one failed
        let mut last: Option<Vec<U>> = None;
        std::iter::from_fn(move || {
            if let Some(pre) = &last {
                bayes_update(unit2prob, pre);
            }
            // Done once every survivor is believed essential (p = 1).
            if unit2prob.values().all(|&p| p >= 1.0) {
                return None;
            }
            let pre = best_prefix(unit2prob);
            if pre.is_empty() {
                return None;
            }
            last = Some(pre.clone());
            Some(pre.into_iter().collect())
        })
    }
}

fn main() {
    println!("minimizing the set 1..=8; interesting iff it keeps 2 and 7");

    let input: Configuration<u32> = (1..=8).collect();

    let oracle_calls =
        std::rc::Rc::new(std::cell::Cell::new(0u32));
    let counter = oracle_calls.clone();
    let keeps_2_and_7 = move |c: &Configuration<u32>| {
        counter.set(counter.get() + 1);
        let mut probe: Vec<u32> =
            c.iter().copied().collect();
        probe.sort_unstable();
        let verdict = if c.contains(&2) && c.contains(&7) {
            Verdict::Interesting
        } else {
            Verdict::NotInteresting
        };
        let mark = if verdict == Verdict::Interesting {
            "interesting (reduce to this)"
        } else {
            "not interesting"
        };
        println!("  test {probe:?} -> {mark}");
        verdict
    };

    let model = ProbDD {
        unit2prob: HashMap::new(),
        p0: 0.1,
    };
    let mut result: Vec<_> =
        reduce(input, &keeps_2_and_7, model)
            .into_iter()
            .collect();
    result.sort_unstable();
    println!(
        "=> minimized to {result:?} in {} oracle calls",
        oracle_calls.get()
    );
    assert_eq!(result, [2, 7]);
    assert_eq!(oracle_calls.get(), 12);
}

Tip

Watch the first probe try to delete everything, then watch the removals shrink as failures push probabilities up.

Note

How many oracle calls did DDMin and ProbDD make respectively?

33 v.s. 12.