We present a new sampling scheme for approximating hard to compute queries over graphical models, such as computing the partition function. The scheme builds upon exact algorithms that traverse a weighted directed state-space graph representing a global function over a graphical model. With the aid of an abstraction function and randomization, the state space can be compacted to facilitate tractable computation, yielding a Monte Carlo Estimate that is unbiased.