Mining Statistically Likely k-Reachable States in Probabilistic Programs

Arnab Ray; Nitesh Trivedi; Ansuman Banerjee; Sourav Chakraborty; Arijit Ghosh; Subhajit Roy

IJCAI 20260 citations

Mining Statistically Likely k-Reachable States in Probabilistic Programs

Arnab Ray, Nitesh Trivedi, Ansuman Banerjee, Sourav Chakraborty, Arijit Ghosh, Subhajit Roy

Abstract

We propose the notion of statistically likely k-step reachable set in probabilistic programs, a statistically robust notion for high-probability k-step reachable program states. We design an inductive algorithm to capture this set as a symbolic representation in propositional logic for Boolean probabilistic programs. Our methodology iteratively learns a symbolic formula for the statistically likely k-step reachable set that involves (a) learning an initial symbolic candidate via decision tree learning, (b) collecting positive and negative counterexamples via forward and backward verification checks, and (c) refining the current candidate via a sequence of prune and split moves on the decision tree. We demonstrate that the statistically likely k-step reachable set can reveal interesting properties about programs by studying probabilistic programs from the literature.

Uncertainty in AI: Probabilistic programming

BibTeX

@inproceedings{ijcai2026_miningstatistica,
  title = {Mining Statistically Likely k-Reachable States in Probabilistic Programs},
  author = {Arnab Ray and Nitesh Trivedi and Ansuman Banerjee and Sourav Chakraborty and Arijit Ghosh and Subhajit Roy},
  booktitle = {IJCAI 2026},
  year = {2026}
}