On the Interpretation of Survey Propagation

In this paper, we unify survey propagation (SP) for constraint-satisfaction problems as "probabilistic token passing" algorithms. We show that the reduction of SP from belief propagation (BP) for general problems requires a modification of the BP message-passing rule, namely, introducing what we call a state-decoupling operation on the BP messages. This raises a question mark on the recent "folk belief" that SP is BP.