Does a survey enumerate every solution cluster?

No. The algorithm estimates messages associated with the clustered picture rather than explicitly listing all clusters.

Is a failed decimation run an unsatisfiability proof?

No. It can reflect an unsuitable heuristic choice or other algorithmic failure.

How can a successful result be checked?

Substitute the final Boolean assignment into every original clause and verify that all are satisfied.

AI Glossary / Graphs and symbolic AI / Advanced

Survey propagation

Definition

Survey propagation is a message-passing method developed for difficult constraint-satisfaction problems, especially certain random satisfiability instances. Instead of summarizing only one distribution over individual variable assignments, its messages describe how local constraint warnings vary across groups of solutions. These surveys can guide decisions about which variables to fix, after which the problem is simplified and the process repeated.

What it means

In Boolean satisfiability, or SAT, each variable is true or false and every clause must have at least one satisfied literal. Some large random formulas have many solutions organized into separated groups, making a single local view of the solution space less informative.

Survey propagation was motivated by this clustered picture. Its name does not refer to collecting questionnaires from people. A survey is a distribution over local messages associated with possible solution groups. In common SAT explanations, a variable may be forced true, forced false, or remain unfixed within a group. Those descriptions should not be mistaken for an exact count of all satisfying assignments.

How it works

Represent the formula as a factor graph connecting variable nodes to the clauses in which they occur. Pass and update survey messages along directed connections using the chosen survey-propagation equations. Messages to a neighbor are computed from the appropriate other incoming messages, avoiding simply feeding the same interaction back to itself.

When the messages converge sufficiently, use their estimated biases to select strongly polarized variables and assign preferred values. This simplification step is called decimation. Remove satisfied clauses, remove false literals from remaining clauses, and propagate any logically forced assignments. Recompute messages on the reduced problem as required.

If the remaining problem is suitable, another solver can finish it. Convergence, the usefulness of biases, and success are not guaranteed for every input. A found complete assignment can be checked directly against all original clauses. Failure of the heuristic or a contradiction after a speculative assignment does not by itself prove the original formula unsatisfiable.

Three practical examples

SAT research: investigate random formulas near difficult parameter regimes and compare how message-based guidance affects the search for satisfying assignments.
Constraint-solver education: demonstrate the distinction between local logical warnings, probability-like survey summaries, and irreversible-looking heuristic variable choices.
Hybrid experiments: use survey-guided simplification before handing a residual formula to another method, measuring overall success and checking every proposed assignment independently.

Think of it this way

Think of hearing summaries from several separated groups of feasible plans rather than averaging all plans into one undifferentiated picture. A choice can be fixed within one group and flexible in another. The analogy is limited because the algorithm does not ordinarily enumerate these groups or interview them; it estimates local survey messages using mathematical update rules.

Worked example

Start with an original decision illustration, not a computed survey-propagation run. Suppose an approximate survey summary for variable x assigns masses 0.75 to forced true, 0.05 to forced false, and 0.20 to unfixed. The masses sum to one. A summary for y is (0.40,0.30,0.30). If the selection rule uses the absolute difference between true-forced and false-forced mass, x has bias 0.70 and y has bias 0.10. That rule would choose x first and favor true.

These stipulated masses are not claims about the following small formula; the next calculation separately illustrates decimation mechanics. Let F=(x OR y) AND (NOT x OR z) AND (NOT z OR w). Assume a heuristic chooses x=true.

The first clause is satisfied and removed. The second reduces to the unit clause z, forcing z=true. The third then reduces to w, forcing w=true. The remaining variable y can take either value. Choosing y=false gives assignment (x,y,z,w)=(true,false,true,true).

Check the original clauses: x OR y is true; NOT x OR z is true because z is true; NOT z OR w is true because w is true. Thus the assignment satisfies F. This verification proves satisfaction of this toy formula, but it does not validate any survey probabilities or demonstrate the behavior of the full message-passing algorithm.

Illustrative case study

Fictional case: a research group adds survey-guided variable selection to a SAT benchmark harness. It initially labels every failed run unsatisfiable. A reviewer points out that a timeout or an unfortunate decimation choice is not a proof about the original formula.

The group separates verified assignments, certified unsatisfiability from a suitable complete solver, and unresolved heuristic runs. It reports convergence failures separately. This fictional case illustrates outcome interpretation without claiming performance improvements.

Common misconceptions and mistakes

Survey propagation is not ordinary opinion aggregation, nor is it simply belief propagation under another name. Its historical motivation concerns distributions of messages across solution groups, though alternative formal interpretations exist.

A high bias is guidance, not a deductive guarantee that a variable must have that value in every solution. Free within a group does not mean irrelevant to the original formula. Success on selected random benchmarks does not establish a polynomial-time algorithm for all SAT instances or resolve the worst-case complexity of satisfiability.

Business use

For business-oriented constraint systems, the practical lesson is to distinguish heuristic guidance from verifiable conclusions. Survey propagation can be a research option, but the match between benchmark structure and operational constraints must be demonstrated. Real configuration or scheduling formulas may have very different structure from random SAT instances.

Compare complete workflows: preprocessing, message updates, decimation, fallback solving, and solution checking. Record random seeds, stopping conditions, and failure categories. A method that finds good assignments quickly in some cases may still need a reliable fallback and clear unresolved-result handling.

Check your understanding

A heuristic survey strongly favors x=true, but fixing it leads to a contradiction. What follows about the original formula?

Answer: That heuristic branch failed. Without further sound reasoning, the original formula may still have a solution with x=false.

Related terms

Learn next

Practice unit propagation and assignment checking on a small SAT formula first. Then study the original survey-message equations and compare a heuristic decision with a logically forced one. Keep the message-passing stage and the decimation stage distinct in experimental logs.

Sources

Braunstein, Mézard, and Zecchina, Survey Propagation: An Algorithm for Satisfiability, original algorithm paper: https://arxiv.org/pdf/cs/0212002 Scope: introductory SAT survey propagation. The survey masses are stipulated illustrations, and the separate clause example checks simplification and satisfaction only; no full SP execution is claimed.

Previous: Survey errors Next: Survival analysis