EDIT: haha I am downvoted for speaking the truth. The parent and I have both read lots of papers like these, there is only a modest contribution of this paper. It basically says we fudged the inference and the end results look similar so its a good optimization. However, there will be probably lots of specific models that "need" the mixing freedom the approximation removes, and hence the algorithm will only work for a specific subspace of MCMC problems. MCMC is basically impossible to debug, so we dunno how well it works overall. THIS IS THE SAME CONCLUSION OF EVERY OTHER MCMC APPROXIMATION PAPER. The only reason this is on HN, is because of its heritage. I do not think this paper is revolutionary (unlike some other papers coming out of Google).
EDIT 2: evidence Modern: "Fully Parallel Inference in Markov Logic Networks" - Max-Planck "Hybrid Parallel Inference for Hierarchical Dirichlet Process" "A split-merge mcmc algorithm for the hierarchical dirichlet process" Old: "Parallel Implementations of Probabilistic Inference" a 1996 review paper!
You might say these papers are not exactly the same, ok, but the final justification for the given paper is:
"Depending on the model, the resulting draws can be nearly indistinguishable"
NOTE kewords: "depending" and "nearly"