We propose a hierarchy of two-level kinetic Monte Carlo methods for sampling high-dimensional, stochastic lattice particle dynamics with complex interactions. The method is based on the efficient coupling of different spatial resolution levels, taking advantage of the low sampling cost in a coarse space and developing local reconstruction strategies from coarse-grained dynamics. Furthermore, a natural extension to a multilevel kinetic coarse-grained Monte Carlo is presented. Microscopic reconstruction corrects possibly significant errors introduced through coarse-graining, leading to the controlled-error approximation of the sampled stochastic process. In this manner, the proposed algorithm overcomes known shortcomings of coarse-graining of particle systems with complex interactions such as combined long- and short-range particle interactions and/or complex lattice geometries. Specifically, we provide error analysis for the approximation of long-time stationary dynamics in terms of relative entropy, measuring the information loss of the path measures per unit time. We show that this observable either can be estimated a priori, or it can be tracked computationally a posteriori in the course of a simulation. The stationary regime is of critical importance to molecular simulations as it is relevant to long-time sampling, obtaining phase diagrams, and in studying metastability properties of high-dimensional complex systems. Finally, the multilevel nature of the method provides flexibility in combining rejection-free and null-event implementations, generating a hierarchy of algorithms with an adjustable number of rejections that includes well-known rejection-free and null-event algorithms. Read More: http://epubs.siam.org/doi/abs/10.1137/120887060