Score-Repellent Monte Carlo: Toward Efficient Non-Markovian Sampler with Constant Memory in General State Spaces

History-dependent sampling can reduce long-run Monte Carlo variance by discouraging redundant revisits, but existing schemes typically encode history through empirical measure on finite state spaces, which is infeasible in high-dimensional discrete configuration spaces or ill-posed in continuous domains. We propose *Score-Repellent Monte Carlo* (SRMC) framework that summarizes trajectory history by a running average of score evaluations in $\mathbb{R}^d$, where $d$ is the dimension of the score and state representation. This history is converted into a surrogate target through an exponential *score tilt*, indexed with $\alpha$ that represents the *strength of repellence* in controlling the magnitude of the history-based repulsion. The surrogate family is normalization-free in the standard MCMC sense, yielding a generic wrapper: at each iteration, any base kernel targeting $\pi$ can instead be run on the current surrogate $\pi_{\theta_n}$ while the history is updated online. We analyze the coupled evolution of the history recursion and Monte Carlo estimators using stochastic approximation with controlled Markovian noise, establishing almost sure convergence and a joint central limit theorem. We further identify regimes in which the asymptotic covariance decreases as $\alpha$ increases, with scaling $O(1/\alpha)$, extending the near-zero-variance effect of finite-state history-dependent samplers to general state spaces with constant memory. Experiments on continuous targets and discrete energy-based models demonstrate improved estimator variance and mode coverage, while retaining $O(d)$ memory usage and modest per-iteration overhead.

Many problems in science and machine learning, from understanding protein structures to training generative AI models, require drawing random samples from complicated probability distributions. The standard tool for this is a family of algorithms called Markov chain Monte Carlo (MCMC), which works by taking a long random walk through the space of possibilities. The trouble is that these walks often get stuck: they wander around the same neighborhood over and over, missing large regions that the algorithm should also be exploring. This produces unreliable answers. A natural idea is to let the algorithm remember where it has already been and gently push itself away from over-visited areas. This works well in small, simple settings, but it breaks down for the kinds of problems people actually care about today, i.e., high-dimensional images and large molecular configurations, because keeping track of every visited state would require an astronomical amount of memory. We propose a new method, Score-Repellent Monte Carlo (SRMC), that summarizes the entire history of the walk using a single compact running average. Instead of remembering individual locations, the algorithm remembers a brief, fixed-size sketch of which directions it has been drifting toward, and uses this sketch to nudge itself away from those directions in the future. This keeps the memory cost essentially flat regardless of the problem size, while preserving the benefits of history-aware exploration. We prove mathematically that this approach is correct in the long run: the algorithm still produces unbiased answers and actually reduces uncertainty in its estimates as the repellence strength increases. In experiments on both continuous problems and large discrete image models, our method finds many more distinct modes of the target distribution and produces more reliable estimates than standard MCMC baselines, while adding minimal computational overhead. The method works as a simple plug-in wrapper around existing samplers, so practitioners can adopt it without overhauling their pipelines.