Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs

Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs

Speakers: Jie Hu, Yi-Ting Ma, Do-Young Eun

Conference: ICML 2025

YouTube: https://slideslive.com/39044073

Overview

At ICML 2025, Jie Hu from NC State University, alongside colleagues Yi-Ting Ma and Professor Do-Young Eun, presented a significant advancement in the realm of Markov Chain Monte Carlo (MCMC) sampling with their work titled "Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs." This presentation introduced History-Driven Target MCMC (HDT-MCMC), a novel framework designed to dramatically enhance the efficiency and scalability of MCMC samplers, particularly when dealing with complex networks and systems. MCMC methods are indispensable tools for drawing samples from intricate, high-dimensional probability distributions, providing critical insights into systems ranging from social networks to physical phenomena where exhaustive analysis is computationally intractable.

The talk addressed critical limitations inherent in previous state-of-the-art history-aware MCMC approaches, most notably their computational cost, restrictive reversibility requirements, and prohibitive memory footprints. HDT-MCMC directly confronts these challenges by fundamentally re-envisioning how historical information is integrated into the sampling process. Instead of modifying the MCMC transition kernel—a method that proved costly and inflexible—HDT-MCMC embeds the history into the target distribution itself. This paradigm shift allows for the preservation of lightweight sampling operations, broad compatibility with diverse MCMC algorithms (including fast non-reversible ones), and robust theoretical guarantees for unbiased and low-variance sampling, all while introducing a practical memory-saving heuristic.

The significance of HDT-MCMC lies in its ability to transform history-aware MCMC from a theoretically promising but practically constrained concept into a powerful, scalable, and deployable tool. By achieving O(1) computational cost per sample and demonstrating superior performance over prior methods, especially on dense graphs, HDT-MCMC paves the way for more accurate and efficient analysis of increasingly large and complex real-world systems. Its practical implications are far-reaching, offering a substantial boost to practitioners, infrastructure teams, and model builders who rely on MCMC for complex inference tasks, making sophisticated sampling techniques accessible for a wider range of applications.

Background

▶ Watch: Introduction to MCMC and key design criteria (0:00)

The analysis of complex networks and systems, such as social graphs, biological pathways, and physical models like the Ising model, frequently demands an understanding of underlying probability distributions that are too intricate to be directly computed or enumerated. In these scenarios, Markov Chain Monte Carlo (MCMC) methods emerge as a cornerstone technique. MCMC allows researchers to draw samples from these complex distributions, providing statistical approximations and insights into the system's overall behavior without needing to analyze every single state. The design of an effective MCMC sampler hinges on three critical criteria: scale-invariance, meaning it operates without requiring global information like the normalizing constant Z; robust theoretical convergence, ensuring the sampler reliably converges to the correct target distribution; and paramount efficiency, delivering the highest possible accuracy with the fewest samples.

Historically, traditional MCMC methods like Metropolis-Hastings (MH), while theoretically sound and widely used, often suffer from slow mixing times, particularly in complex or rugged energy landscapes. This can lead to high sampling variance and a need for an extremely large number of samples to achieve acceptable accuracy. To address these limitations, researchers have explored various enhancements, including incorporating "memory" or "history-awareness" into the random walk process.

A notable prior contribution from Jie Hu's group was the Self-Repellent Random Walk (SRW), which garnered an Outstanding Paper Award at ICML 2023. SRW introduced a groundbreaking concept: making the random walk history-aware. Unlike traditional memoryless random walks, SRW dynamically modifies its transition kernel. The walker becomes "repelled" by nodes it has visited frequently, effectively forcing it to explore the graph more thoroughly and avoid getting trapped in local minima. This direct modification of the transition kernel rendered SRW a nonlinear MCMC method. The results were compelling: SRW achieved near-zero sampling variance, significantly outperforming traditional methods. It boasted scale-invariance, robust convergence to the correct target distribution mu, and exceptional efficiency, even surpassing independent and identically distributed (i.i.d.) sampling under certain topological constraints. At the time, SRW appeared to be a near-perfect solution for history-aware MCMC.

However, despite its theoretical elegance and performance prowess, SRW harbored several practical limitations that hindered its widespread applicability, particularly in large-scale or high-dimensional problems. These issues became the primary motivation for the development of HDT-MCMC:

1. Computational Cost: SRW's core mechanism—directly modifying the transition kernel based on visit history—destroyed the elegant "propose-and-reject" structure characteristic of lightweight MCMC algorithms like Metropolis-Hastings. A standard MH step involves proposing a single neighbor and making a quick O(1) decision to accept or reject it. In contrast, SRW, at every step, had to calculate the transition probability to every neighbor before making a move. This meant the computational cost to obtain a single sample scaled with the node's degree, making it an O(degree) operation. For dense graphs, where nodes can have many neighbors, this cost became prohibitively slow, negating much of its efficiency gains.

1. Reversibility Constraint: The theoretical guarantees underpinning SRW required the underlying Markov chain to be time-reversible. While many MCMC samplers are reversible, this constraint excluded a whole class of advanced, often faster, non-reversible samplers. Non-reversible MCMC methods can exhibit superior mixing properties and efficiency in certain problem domains, and SRW's inability to leverage them was a significant limitation.

1. Memory Problem: Storing the visit count for every single node in a graph or state space is a substantial memory burden. For large-scale graphs with millions or billions of nodes, or for configuration spaces like the Ising model which can have an astronomical number of states, this requirement was simply impossible to meet. The memory footprint of SRW made it impractical for real-world large-scale applications.

These three practical issues—computational cost, reversibility, and memory—formed the crucible from which HDT-MCMC emerged, aiming to retain the powerful benefits of history-awareness while overcoming the critical hurdles that limited SRW's real-world utility.

Key Findings

▶ Watch: Identifying SRW's practical limitations: cost, reversibility, memory (2:05)

The central contribution of this work is the introduction of History-Driven Target MCMC (HDT-MCMC), a novel framework that fundamentally redefines how history-awareness is incorporated into MCMC sampling. HDT-MCMC successfully addresses the critical practical limitations of previous methods like SRW, making history-aware MCMC both efficient and scalable.

The core insight behind HDT-MCMC is a simple yet profound paradigm shift: instead of integrating historical information directly into the MCMC transition kernel (as SRW did), the history is embedded into the target distribution itself. This shift from kernel modification to an adaptive target distribution is the cornerstone of the HDT framework. The new adaptive target, denoted pi_x, is formulated as the original target distribution mu penalized by a term that accounts for the sampler's visit history. This implicitly integrates the "self-repellence" effect, guiding the sampler towards less-visited regions of the state space.

This innovative approach yields several key findings and advantages:

1. Resolved Computational Cost: By modifying only the target distribution, HDT-MCMC retains the elegant propose-and-reject scheme characteristic of lightweight algorithms like Metropolis-Hastings. This means that, unlike SRW, HDT-MCMC achieves an O(1) computational cost per sample, regardless of the node's degree. This is a crucial breakthrough, eliminating the prohibitive slowness of SRW in dense graphs.

1. Universal MCMC Compatibility: HDT-MCMC acts as a simple, uniform wrapper that can enhance any underlying MCMC sampler. Crucially, because it modifies the target rather than the kernel, it is no longer constrained by the time-reversibility requirement. This allows HDT to be seamlessly applied to fast non-reversible samplers, significantly expanding the range of MCMC algorithms that can benefit from history-awareness.

1. Strong Theoretical Guarantees: The framework is backed by robust theoretical proofs. HDT-MCMC is proven to provide unbiased sampling, guaranteeing convergence to the correct target distribution. Furthermore, it achieves a powerful O(1/alpha) variance reduction, ultimately leading to near-zero sampling variance, mirroring SRW's success in this regard. Most importantly, through the application of random change of time theory and Slutsky theorem, the theory rigorously demonstrates that for the same computational budget, HDT-MCMC is provably more cost-efficient than SRW. This theoretical superiority translates directly to faster real-world computation.

1. Practical Memory Solution: To overcome the memory burden of storing visit counts for every node, the authors propose a heuristic Least Recently Used (LRU) cache scheme. This intuitive approach tracks the history only for the most recently visited nodes within a limited cache. For nodes not in the cache, their visit counts are extrapolated based on the average historical behavior of their neighbors that are in the cache, leveraging the inherent locality of random walks.

1. Empirical Validation: Extensive experiments confirm the theoretical predictions. HDT-MCMC consistently provides a significant performance boost across various MCMC samplers, both reversible and non-reversible, when measured by metrics like total variance distance or normalized root mean squared error (RMSE). When performance is plotted against actual computational cost, HDT-MCMC drastically outperforms SRW, with this performance gap widening considerably on denser graphs, unequivocally demonstrating that SRW's high per-sample cost was indeed a major bottleneck. The LRU cache scheme also proved highly effective, showing that even with a 90% reduction in memory usage (using only 10% of full memory), HDT-MCMC still significantly outperforms original baseline MCMC methods, proving its robustness, practicality, and scalability for large graphs.

In essence, HDT-MCMC captures the spirit of self-repellence and near-zero variance sampling introduced by SRW but resolves its critical practical shortcomings, making history-aware MCMC a truly practical and powerful tool for a broad spectrum of real-world applications.

Technical Deep Dive

▶ Watch: HDT's core idea: adaptive target distribution and lightweight integration (4:30)

The technical ingenuity of HDT-MCMC stems from its fundamental re-architecture of history-aware MCMC, moving away from modifying the transition kernel to adapting the target distribution. To appreciate this shift, it's essential to understand the mechanics of MCMC and the challenges posed by prior approaches.

Traditional MCMC methods aim to sample from a target probability distribution mu(x) over a state space X. The core idea is to construct a Markov chain whose stationary distribution is mu(x). A common and widely used algorithm is Metropolis-Hastings (MH). In MH, at each step, a new state x' is proposed from the current state x using a proposal distribution q(x'|x). This proposal is then accepted or rejected with a probability given by the acceptance ratio:

alpha(x', x) = min(1, (mu(x') q(x|x')) / (mu(x) q(x'|x)))

If accepted, the chain moves to x'; otherwise, it remains at x. The beauty of MH (and similar algorithms) is its on-demand O(1) operation: it only needs to evaluate mu at x and x', and q for the proposed transition, making it computationally lightweight per sample.

The Self-Repellent Random Walk (SRW), while innovative, deviated from this O(1) efficiency. SRW directly modified the transition kernel P(x'|x) based on the historical visit counts N(v) for each node v. The kernel was designed such that the probability of moving to a frequently visited node v from x was reduced. This made the MCMC nonlinear and history-aware. However, the direct modification of P(x'|x) meant that to determine the next state, the sampler had to re-calculate the modified transition probabilities to all potential neighbors. If a node x had degree d, this meant O(d) computations for each step. In dense graphs where d can be very large, this quickly became a computational bottleneck, destroying the O(1) per-sample efficiency crucial for large-scale applications. Furthermore, SRW's theoretical guarantees relied on the underlying chain being time-reversible, which restricted its applicability to a subset of MCMC samplers.

HDT-MCMC's paradigm shift directly addresses these issues. Instead of altering the mechanism of how the sampler moves (the kernel), HDT-MCMC modifies where the sampler wants to go (the target distribution). The core idea is to introduce an adaptive target distribution pi_x that incorporates the history H_t (the set of visit counts up to time t). The formulation is elegantly simple:

pi_x(H_t) = mu(x) * f(N(x))

where mu(x) is the original desired target distribution, and f(N(x)) is a penalty term that decreases as the visit count N(x) of state x increases. This function f implicitly integrates the self-repellence: states that have been visited more frequently receive a lower "effective" probability mass in pi_x, making them less attractive to the sampler. The specific form of f(N(x)) can vary, but the general principle is to "push" the sampler away from over-explored regions.

The beauty of this approach is that an MCMC sampler (e.g., Metropolis-Hastings) can then be run using pi_x(H_t) as its target distribution. The acceptance ratio for an MH-like algorithm would then become:

alpha(x', x) = min(1, (pi_x(x', H_t) q(x|x')) / (pi_x(x, H_t) q(x'|x)))

Since pi_x(x, H_t) only depends on the current state x and the proposed state x', and their respective visit counts N(x) and N(x'), the computation of the acceptance ratio remains an O(1) operation. The sampler only needs to query the history for x and x', not all neighbors. This restores the lightweight nature of MCMC, making it efficient even on dense graphs.

Furthermore, because HDT-MCMC is a wrapper around the target, it doesn't impose restrictions on the underlying sampler's reversibility. This allows it to accelerate non-reversible MCMC samplers, which are known for their potentially faster mixing properties in certain contexts.

The theoretical underpinnings of HDT-MCMC are robust. The paper proves unbiased sampling, ensuring that despite the dynamic target, the long-run distribution of samples correctly reflects mu(x). It also demonstrates O(1/alpha) variance reduction, indicating that HDT-MCMC achieves the same high accuracy (near-zero variance) as SRW. Critically, the theoretical work employs random change of time theory and Slutsky theorem to formally prove that HDT-MCMC is provably more cost-efficient than SRW for a given computational budget. This means that for the same amount of real-world CPU/GPU time, HDT-MCMC will generate more effective samples than SRW.

Finally, the memory challenge is addressed with a heuristic Least Recently Used (LRU) cache scheme. For large graphs, storing N(v) for every v is infeasible. The LRU cache maintains visit counts only for a fixed number of most recently visited nodes. When a node v is visited, its count is updated. If v is not in the cache, it's added, potentially evicting the least recently used node. For nodes not in the cache, their visit counts are not stored directly. Instead, the scheme extrapolates their counts by averaging the visit histories of their neighbors that are present in the cache. This strategy leverages the locality property of random walks: a node's recent visit history is often correlated with that of its immediate neighbors. This heuristic allows for significant memory reduction while still effectively informing the adaptive target, making HDT-MCMC scalable to massive graph structures.

Experimental Setup & Results

▶ Watch: HDT's strong theoretical guarantees and provable cost-efficiency (5:30)

The experimental validation of HDT-MCMC meticulously confirmed its theoretical advantages, demonstrating significant performance improvements over both traditional MCMC baselines and the prior state-of-the-art SRW, particularly when considering actual computational cost.

The researchers applied HDT-MCMC to several different MCMC samplers, encompassing both reversible and non-reversible algorithms. While specific sampler names were not explicitly detailed in the transcript, the broad categorization underscores HDT's versatility. The experiments aimed to evaluate the quality of samples generated and the efficiency of the sampling process.

Two primary metrics were used to quantify the accuracy and convergence of the MCMC samplers:

1. Total Variance Distance: A measure of the distance between the empirical distribution of samples and the true target distribution. Lower values indicate better accuracy.
2. Normalized Root Mean Squared Error (RMSE): Used for specific MCMC tasks, providing another robust measure of approximation error.

The results were consistently positive:

• Performance Boost Over Baselines: Plots presented in the talk visually demonstrated this improvement. Dashed lines represented the performance of the baseline MCMC samplers, while solid lines depicted the performance of the HDT-enhanced versions. Across all tested scenarios and for both reversible and non-reversible samplers, HDT-MCMC consistently provided a significant performance boost, yielding lower error (either total variance distance or normalized RMSE) for a given number of samples or computational budget.

A crucial aspect of the experimental design was the nuanced comparison with SRW, the prior history-aware method. The researchers highlighted a critical distinction:

• Performance by Number of Steps vs. Computational Cost: Initially, if performance was measured solely by the "number of steps" taken by the MCMC chain, SRW sometimes appeared competitive (shown in red curves in some plots). However, this metric is misleading for SRW because, as previously discussed, "not every sample costs the same for SRW" due to its O(degree) complexity.
• Actual Computational Cost: The most compelling results emerged when performance was plotted against actual computational cost (e.g., CPU time or FLOPs). Here, HDT-MCMC (represented by solid blue and orange lines) drastically outperformed SRW. This performance gap was observed to be even wider on denser graphs, providing strong empirical evidence that SRW's high per-sample cost was indeed a major bottleneck that HDT-MCMC successfully resolves by maintaining its O(1) cost.

Finally, the efficacy of the heuristic Least Recently Used (LRU) cache scheme for memory management was rigorously tested:

• Memory Reduction Impact: The experiments showed that even when using a significantly reduced memory footprint—specifically, using just 10% of the full memory required to store all visit counts (equivalent to a 90% memory reduction)—HDT-MCMC still managed to significantly outperform the original baseline MCMC methods. This outcome conclusively demonstrated the robustness, practicality, and scalability of the HDT-MCMC approach, affirming that the LRU cache, combined with the extrapolation strategy, effectively mitigates the memory burden without sacrificing performance.

In summary, the experimental results provided strong empirical validation for all the theoretical claims: HDT-MCMC offers superior accuracy, is significantly more cost-efficient than SRW, works universally with various MCMC types, and is scalable to large systems through its intelligent memory management.

Practical Implications

▶ Watch: Practical solution for memory: LRU cache and its effectiveness (7:00)

The introduction of HDT-MCMC carries profound practical implications for a wide array of stakeholders involved in machine learning, scientific computing, and systems analysis. By addressing the critical limitations of prior history-aware MCMC methods, HDT-MCMC transforms a theoretically powerful concept into a truly deployable and impactful tool.

For Practitioners and Model Builders:

• Enhanced Efficiency and Accuracy: HDT-MCMC offers a direct pathway to achieving near-zero sampling variance with significantly improved efficiency. This means practitioners can obtain more accurate samples from complex distributions in less time, leading to more reliable inferences and predictions in fields like Bayesian inference, statistical physics, and network analysis.
• "Bring Your Own MCMC" Flexibility: One of HDT's most compelling features is its role as a universal wrapper. Model builders are not forced to abandon their existing, well-understood MCMC samplers (e.g., various Metropolis-Hastings variants, Gibbs samplers, etc.). Instead, they can integrate HDT-MCMC on top of their preferred sampler, immediately boosting its performance without requiring a complete overhaul of their sampling methodology.
• Access to Non-Reversible Samplers: The removal of the time-reversibility constraint is a game-changer. Practitioners can now leverage the often faster mixing properties of non-reversible MCMC samplers while simultaneously benefiting from history-awareness. This expands the toolkit available for tackling particularly challenging or high-dimensional problems.

For Infrastructure Teams and Deployers:

• Scalability for Large Graphs: The O(1) computational cost per sample is paramount for deploying MCMC on large-scale systems, especially those involving dense graphs (e.g., social networks, knowledge graphs). This guarantees that the sampling cost does not explode with increasing node degrees, making it feasible to run history-aware MCMC on real-world datasets with millions or billions of connections.
• Memory Efficiency for Massive State Spaces: The heuristic LRU cache scheme, which allows for a 90% memory reduction while maintaining high performance, is critical for tackling problems with vast state spaces. This includes not only large graphs but also complex configuration spaces (like those in statistical physics or deep learning model parameter spaces) where storing full historical visit counts is simply impossible. Infra teams can deploy HDT-MCMC with confidence, knowing it can operate within practical memory constraints.
• Robustness and Reliability: The strong theoretical guarantees for unbiased sampling and O(1/alpha) variance reduction provide assurance that HDT-MCMC will converge correctly and produce high-quality samples, which is essential for mission-critical applications.

Tradeoffs and Limitations:

While HDT-MCMC represents a significant leap forward, it's important to acknowledge potential nuances.

• Heuristic Nature of LRU Cache: The LRU cache scheme is described as a "heuristic." While experiments show it works "well," there might be specific graph structures or sampling patterns where the extrapolation of visit counts from neighbors might be less accurate, potentially leading to minor performance degradations compared to a full memory solution (if one were feasible). The effectiveness of the extrapolation relies on the assumption of local correlation in random walk behavior.
• Overhead of History Management: Although the per-sample cost is O(1), there is still an inherent overhead associated with managing the history (updating the LRU cache, calculating f(N(x))). While this overhead is minimal compared to SRW's O(degree) cost, it's a factor to consider for extremely high-frequency sampling scenarios.
• Optimal f(N(x)) Design: The specific functional form of the penalty term f(N(x)) and its parameters can influence performance. While the general principle is clear, finding the optimal f for a given problem or graph type might require some tuning, though the talk implies a robust general formulation.

In conclusion, HDT-MCMC makes history-aware MCMC a genuinely practical, powerful, and scalable tool. Its ability to accelerate existing samplers, work with diverse MCMC types, and handle large-scale data with efficient memory usage opens up new avenues for tackling complex inference problems across science and engineering.

Key Takeaways

• MCMC is crucial for analyzing complex systems but faces challenges in efficiency and scalability. Traditional methods can be slow to mix, and prior history-aware approaches, while powerful, had significant practical limitations.
• Self-Repellent Random Walk (SRW) introduced history-awareness for near-zero variance but suffered from high computational cost (O(degree)), reversibility constraints, and prohibitive memory requirements.
• History-Driven Target MCMC (HDT-MCMC) resolves SRW's issues by shifting history integration from the transition kernel to an adaptive target distribution. This is the core paradigm shift.
• HDT-MCMC achieves O(1) computational cost per sample, making it drastically more efficient than SRW, especially on dense graphs. It also works as a universal wrapper, accelerating any MCMC sampler, including fast non-reversible ones.
• Backed by strong theoretical guarantees, HDT-MCMC provides unbiased sampling, O(1/alpha) variance reduction, and is provably more cost-efficient than SRW for the same computational budget.
• A heuristic Least Recently Used (LRU) cache scheme makes HDT-MCMC memory-scalable, enabling significant memory reduction (e.g., 90%) while maintaining high performance on large graphs. HDT-MCMC transforms history-aware MCMC into a practical, powerful, and scalable tool for real-world applications.

About the Speaker(s)

The talk was presented by Jie Hu from NC State University. This research is a collaborative effort, undertaken as a joint work with colleagues Yi-Ting Ma and Professor Do-Young Eun. The presentation highlights their collective expertise in developing advanced MCMC methodologies for complex systems.