  We introduce an efficient message passing scheme for solving Constraint
Satisfaction Problems (CSPs), which uses stochastic perturbation of Belief
Propagation (BP) and Survey Propagation (SP) messages to bypass decimation and
directly produce a single satisfying assignment. Our first CSP solver, called
Perturbed Blief Propagation, smoothly interpolates two well-known inference
procedures; it starts as BP and ends as a Gibbs sampler, which produces a
single sample from the set of solutions. Moreover we apply a similar
perturbation scheme to SP to produce another CSP solver, Perturbed Survey
Propagation. Experimental results on random and real-world CSPs show that
Perturbed BP is often more successful and at the same time tens to hundreds of
times more efficient than standard BP guided decimation. Perturbed BP also
compares favorably with state-of-the-art SP-guided decimation, which has a
computational complexity that generally scales exponentially worse than our
method (wrt the cardinality of variable domains and constraints). Furthermore,
our experiments with random satisfiability and coloring problems demonstrate
that Perturbed SP can outperform SP-guided decimation, making it the best
incomplete random CSP-solver in difficult regimes.
