Discriminative graphical models such as conditional random fields and Markov logic net- works have achieved state of the art results in a variety of NLP and IE tasks including coreference and relation extraction. Increasingly, automated knowledge extraction is demanding models with more complex structure— higher tree-width, larger fan-out, more features, more data—rendering even approximate inference methods such as MCMC inefficient. In this paper we propose a new MCMC sampling scheme where transition probabilities are approximated. We demonstrate that our method converges more quickly than a traditional MCMC sampler for both marginal and MAP inference. For a task of author coreference over 5 million mentions, we achieve a speedup of 13 over regular MCMC inference.