Probabilistic Inference for Predicate Constraint Satisfaction

Yuki Satake, Hiroshi Unno, Hinata YanagiAAAI 2020 · DOI

Introduction

Formal verification often relies on translating programs into logic constraints to prove safety properties. For years, Constrained Horn Clauses (CHCs) have served as the standard for linear-time safety verification—proving that a "bad" state is never reached. However, CHCs struggle with branching-time properties, such as proving that a program has at least one non-terminating execution. These properties require existential quantification and disjunctions in the head of implications, leading to the more general Predicate Constraint Satisfaction Problem (pCSP).

The search space for pCSP solutions is massive and non-smooth. This paper introduces a novel framework that integrates probabilistic inference into a synthesis loop to efficiently navigate this space.

The pCSP Framework and Predicate Abstraction

To solve pCSPs, the authors employ a Counterexample Guided Inductive Synthesis (CEGIS) loop. The process begins with predicate abstraction, which maps the infinite search space of mathematical invariants to a finite Boolean Constraint Satisfaction Problem (bCSP). This abstraction allows the solver to search for true/false assignments over a set of base predicates rather than synthesizing complex formulas from scratch.

Probabilistic Inference via Survey Propagation

The core innovation of this work is the use of Survey Propagation (SP), a probabilistic inference algorithm derived from statistical physics. Instead of using a standard SAT solver to find any valid assignment, the authors utilize Survey Inspired Decimation (SID).

Figure 1: Factor graph representation of a Boolean Constraint Satisfaction Problem (bCSP), where circles represent variables and squares represent constraints (factors).

SP identifies "clusters" of solutions within a factor graph (see Figure 1). By sampling from these clusters, the solver can select candidate solutions that are both "simple" (adhering to Occam’s Razor) and "diverse." This diversity prevents the CEGIS loop from getting stuck in local minima and ensures that each iteration provides maximum information gain.

Experimental Evaluation

The proposed solver, PCSAT, was evaluated against standard benchmarks (SyGuS-Comp and CHC-COMP) and a new suite of pCSP problems involving non-termination.

Figure 3: Performance comparison of SID and SAT solvers on SyGuS benchmarks. The plot shows time vs. benchmarks passed, while the table summarizes the total solved instances.

As shown in Figure 3, the SID-based approach significantly outperforms standard SAT solvers. Specifically, using SID with 8 candidate solutions (#cand=8) allowed the solver to pass 100 out of 127 SyGuS instances. Furthermore, PCSAT successfully solved new pCSP benchmarks (e.g., nt-rec) in under 2 seconds—problems that existing CHC solvers are fundamentally unable to express.

Conclusion and Future Work

By combining predicate abstraction with probabilistic inference, this work provides a powerful tool for verifying branching-time properties. While PCSAT is already competitive with state-of-the-art CHC solvers, future work aims to improve engineering maturity and extend the framework to handle infinitely branching systems. A promising direction involves modeling pCSPs directly as factor graphs to bypass the Boolean abstraction step entirely.

Summary updated

BibTeX
@inproceedings{satake2020probabilistic,
  author = {Yuki Satake and Hiroshi Unno and Hinata Yanagi},
  title = {{Probabilistic Inference for Predicate Constraint Satisfaction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5526},
}
Figure