  A Monte-Carlo algorithm for discrete statistical models that combines the
full power of the Belief Propagation algorithm with the advantages of a
detailed-balanced heat bath approach is presented. A sub-tree inside the factor
graph is first extracted randomly; Belief Propagation is then used as a perfect
sampler to generate a configuration on the tree given the boundary conditions
and the procedure is iterated. This appoach is best adapted for locally tree
like graphs, it is therefore tested on the hard cases of spin-glass models for
random graphs demonstrating its state-of-the art status in those cases.
