Algorithms for approximate inference usually come without any guarantee for the quality of the approximation. Nevertheless, we often find cases where such algorithms perform extremely well on the comp