Pith. sign in

REVIEW 2 major objections 4 minor 15 references

Efficient implementation of Cluster Expansion models in surface Kinetic Monte Carlo simulations with lateral interactions: Subtraction Schemes, Supersites and the Supercluster Contraction

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Combining three algorithmic modifications brings kinetic Monte Carlo simulations with lateral interactions to near-constant per-step cost.

desk verdict A genuinely new exact energy-contraction method, but the headline factor-3 overhead is based on a biased no-update baseline; the method is worth a look, the abstract overclaims. read the letter →

arxiv 1908.03526 v1 pith:OR54HVOQ submitted 2019-08-09 physics.comp-ph cond-mat.stat-mechphysics.chem-ph

Franziska Hess This is my paper · ORCID
classification physics.comp-phcond-mat.stat-mechphysics.chem-ph
keywords kineticMonteCarloclusterexpansionlateralinteractionssuperclustercontractionsubtractionschemesupersitesearchvariablestepsizemethodsurfacereactions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that the well-known performance penalty of kinetic Monte Carlo (KMC) simulations with lateral interactions can be almost entirely removed by a combination of three algorithmic changes. It traces the slowdown to three sources: expensive cluster-expansion energy evaluations, extensive rate recomputation after each event, and the impracticality of rate-catalog schemes when the number of distinct rate constants becomes astronomically large. The proposed SSS-VSSM method replaces the literal cluster expansion with a contracted "supercluster" Hamiltonian, updates only local changes of the total rate through a subtraction scheme, and uses a two-level "supersite" search. The paper claims this brings the per-step cost to a practical constant with respect to lattice size, scaling only with the square of the interaction range, and that including a complex lateral-interaction model adds less than a factor of 3 to the runtime. If this holds, realistic first-principles-based KMC simulations of catalytic surface reactions with explicit lateral interactions become feasible in serial on a workstation.

What carries the argument

The central object is the combined SSS-VSSM algorithm, but the load-bearing piece is the Supercluster Contraction: a pre-computed lookup representation of the cluster-expansion Hamiltonian in which individual interaction terms are merged into a small number of larger "supercluster" energy tables. Each supercluster contains several 2-, 3-, and 4-body interaction figures, and the contraction is constructed so that every interaction cluster is contained in at least one supercluster while overlap weighting avoids double counting, making the contracted Hamiltonian exactly equivalent to the original at zero accuracy loss. The Subtraction Scheme (updating Gamma via Gamma_new = Gamma_old - gamma_old + gamma_new over the interaction range) and the Supersite Search (two-level, first over chunks then within a chunk) are the other two mechanisms; their role is to remove the O(N) accounting and search scalings so that the Supercluster-accelerated O(1) update step governs runtime for lattices below roughly $10^{5}$ sites.

What would settle it

Run the SSS-VSSM algorithms in a production KMC code on a realistic cluster-expansion model with bimolecular surface reactions, several intermediates, and pattern matching, then measure wall-clock time per accepted step against a matched simulation with no lateral interactions; if the overhead exceeds a factor of 3 or the per-step time grows noticeably with lattice size beyond the O($\sqrt$(N)) search term, the central claim is refuted. A complementary check is to run the subtractive Gamma update for $10^{7}$ steps in a stiff system where rate constants span more than 10 orders of magnitude and verify that the numerical drift in Gamma stays below a tolerance consistent with unbiased kinetics.

Watch

Extended reading notes

Core claim

The central claim is that the site-based Variable Step Size Method can be modified so that KMC simulations with cluster-expansion lateral interactions run at essentially fixed cost per step for practical lattice sizes (up to about $10^{5}$ sites), with an overall added cost of less than a factor of 3 compared with an interaction-free simulation. This is achieved by three components that act on the three cost-driving steps: the Supercluster Contraction reduces the number of terms in the energy evaluation from 25 to as few as 4 by pre-computing energies of larger composite clusters that exactly reproduce the original cluster expansion; the Subtraction Scheme updates the total rate Gamma by subtracting the old local rate sum around the reaction event and adding the new one, making accounting O(1); and the Supersite Search, based on Maksym's 2-Level method, divides the lattice into chunks to make the search step O($\sqrt$(N)). The combined algorithm, SSS-VSSM, changes the overall scaling from O(N) to O($\sqrt$(N)), with the O($\sqrt$(N)) term asymptotically negligible for practical lattice sizes because the update step dominates runtime.

Load-bearing premise

The performance claims rest on toy benchmarks that use only one energy evaluation per step and per updated site, include no real reaction mechanism, pattern matching, or rate computation, and model the interaction-free baseline by deactivating the update step entirely, which the paper itself notes biases the comparison in favor of simulations without lateral interactions.

Editorial extensions

If this is right

  • KMC simulations with cluster-expansion lateral interactions can be run serially on a workstation with wall-clock times comparable to interaction-free simulations, making microkinetic models with coverage-dependent kinetics practical for broader screening.
  • For lattices up to about 10^5 sites, runtime per step is dominated by the update step rather than by the search step, so further performance gains should come from optimizing energy evaluation (e.g., better supercluster contractions) rather than from more sophisticated search trees.
  • The Subtraction Scheme for updating Gamma is beneficial even in KMC simulations without lateral interactions, since it removes the O(N) accounting step entirely.
  • The optimal supercluster contraction depends on computer architecture, memory access speed, and compiler, so testing several contractions before production runs is advisable to achieve the best speedup.
  • Because the Supercluster Contraction is an exact post-processing of an existing cluster expansion, it can be applied to any fitted CE model without changing parameters or requiring new first-principles calculations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same triad of contraction, local-difference updates, and hierarchical search should transfer to other site-based stochastic simulators (e.g., continuous-time random walk or lattice-gas models outside surface catalysis) whenever local energy evaluation is expensive and configurations change only locally.
  • The paper's data imply that on modern architectures, memory access time, not the number of arithmetic operations, often limits energy evaluation; a portable implementation could auto-tune the supercluster contraction at runtime to the specific hardware, which the paper does not explore.
  • The near-constant per-step cost opens the door to long-ranged lateral interactions if the supporting-information sketch of a modified energy updating scheme is developed further, since the supercluster memory footprint currently grows with the interaction range squared.
  • A testable extension would be to apply SSS-VSSM to a production KMC model with bimolecular reactions and pattern matching; the paper predicts the update step will dominate even more strongly, making the Supercluster Contraction more impactful than in the toy benchmark.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper addresses the computational cost of kinetic Monte Carlo (KMC) simulations of surface reactions when lateral interactions are included through a Cluster Expansion (CE). The authors identify three bottlenecks in site-based Variable Step Size Method (VSSM) implementations: evaluation of the CE Hamiltonian, updating the total rate sum after each event, and searching for the next event. They propose three corresponding algorithmic improvements: (1) the Supercluster Contraction, which precomputes and stores energies of larger composite clusters so that the CE Hamiltonian is evaluated from fewer terms without changing the underlying model; (2) a Subtraction Scheme that updates the total rate Γ locally rather than recomputing it from scratch; and (3) the Supersite Search, an adoption of Maksym's two-level method to reduce event selection to O(√N). Benchmarks with toy programs show that the supercluster contraction speeds up energy evaluation by factors between 3 and 13.5 depending on architecture, the subtraction scheme removes the O(N) accounting cost, and the combined SSS-VSSM algorithm exhibits approximately constant runtime per step for lattices up to about 10^5 sites. The paper claims an overall added cost of less than a factor 3 for including a complex lateral interaction model.

Significance. If the reported scalings are reliable, the work is a valuable practical contribution: it shows that CE-based KMC with many interaction terms can be run serially on workstations, avoiding the exponential rate-catalog problem and the linear-in-N cost of naive site-based algorithms. The Supercluster Contraction is exact by construction when overlaps are handled as described, the memory overhead is modest (≤ 175 kB for the tested models), and the sample programs are provided on GitHub. The Subtraction Scheme and Supersite Search are standard ideas in other settings, but their combination with the supercluster contraction is new and the paper gives a clear derivation of the resulting O(√N) scaling. The central quantitative claim, however, is weaker than the abstract suggests because the factor-3 overhead is measured against a deliberately deactivated update baseline in a toy workload, as the author acknowledges in Section 3.4.

major comments (2)
  1. [Abstract and Section 3.4] The abstract's claim that 'the overall added cost of including a complex lateral interaction model amounts to less than a factor 3' is not established for production KMC simulations. In the benchmark behind this claim (Figure 6), the interaction-free baseline is obtained by deactivating the update step entirely, which the author states is 'biasing this comparison in favor of simulations without lateral interaction.' The test also uses only one energy evaluation per step and per updated site, and includes no real reaction mechanism, pattern matching, or rate computation, as stated in Section 3.4. The factor of 3 therefore measures the cost of the interaction update relative to a zero-cost update, not the added cost in a working simulation with a finite O(1) update constant. The conclusion should be reworded to state the factor-3 result as a bound for the toy workload, or the benchmark should be extended to a more representative KMC event loop.
  2. [Section 3.1.2, Eq. (5)] The relative speedup formula in Eq. (5), rel. speedup = (t_SC - t0)/(t_lit - t0), is inverted: for a supercluster contraction that is faster than the literal evaluation, t_SC < t_lit, so the quotient is less than 1, whereas Table 1 reports speedups between 3.01 and 13.51. The intended definition is presumably (t_lit - t0)/(t_SC - t0), or the numerator and denominator should be swapped. Please correct the equation and check that the table values and the accompanying text are consistent with the corrected formula.
minor comments (4)
  1. [Section 3.3.1] The text contains a dangling reference to '( Section 0)' in the paragraph after Eq. (11); this should be replaced with the actual section number describing the supersite search.
  2. [Abstract vs. Section 3.4] The abstract says the algorithm is 'fixed-cost with respect to the number of lattice sites for practical lattice sizes,' while Section 3.4 states the asymptotic scaling is O(√N) and that runtime is 'practically constant' for medium to large lattices. Consider using 'nearly fixed-cost' or 'approximately constant' in the abstract to avoid implying strict O(1) scaling.
  3. [Section 3.1.2] The sentence 'The number of terms in Eq. 1 is 25' could be made clearer by explicitly noting the breakdown: 13 terms for the one-site and pairwise interactions plus 12 terms for the three-body interactions.
  4. [Supporting Information] The sample programs are announced as being available on GitHub, but the supporting information sections on error handling (S1.1) and the long-range interaction approach (S1.2) are not included in the arXiv text; please ensure the final published version contains these sections or clearly points to them.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithmic claims are either exact algebraic rearrangements or measured benchmarks, not predictions derived from their own conclusions.

full rationale

The paper's central contributions are algorithmic and are validated by direct measurement rather than by folding the conclusion back into an input. The Supercluster Contraction is an exact recombination of the existing Cluster Expansion Hamiltonian: the paper states that 'the supercluster contraction must exactly reproduce the energy of every configuration as given by Eq. 1,' and it precomputes supercluster energies from the original CE parameters, which is a legitimate algebraic transformation rather than a self-definitional prediction. The Subtraction Scheme is an identity for updating the total rate under local changes: Eq. 9, Gamma_new = Gamma_old - gamma_old + gamma_new, is exact by construction given that only sites within the interaction range change, and the paper does not present this identity as an empirical discovery. The Supersite Search is explicitly attributed to prior work by Maksym and Blue et al., with only 'minor alterations' proposed, so there is no borrowed uniqueness theorem or ansatz smuggled in via self-citation. The factor-3 overhead claim in the abstract is a benchmark measurement, and while the comparison is acknowledged to be favorable to the no-interaction baseline ('biasing this comparison in favor of simulations without lateral interaction'), that is a limitation on the generality of the quantitative claim, not circularity: the number is measured, not derived from the claim itself. The test Cluster Expansion is taken from the author's own HCl and CO oxidation models, but it is an input test model rather than a fitted parameter that reappears as the output. The possible typo in Eq. 5 (the printed ratio would be smaller than 1 for a speedup) is a correctness or notation issue, not a circular step. Overall, the derivation chain is self-contained: the algorithms are exact transformations or cited external methods, and the performance statements are experimental measurements with stated caveats.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters were fitted, and the paper introduces no new physical entities. The main assumptions are the local, site-centered form of the CE Hamiltonian and the representativeness of the simplified benchmark tests.

assumptions (4)
  • domain assumption The Cluster Expansion Hamiltonian is site-centered, so all changed rates after a reaction event lie within a local region of radius R.
    This is implicit in Eq. 1 and in the local update and Subtraction Scheme (Section 3.2). If the CE had non-local or delocalized contributions, the O(1) accounting claim would fail.
  • standard math The cumulative-sum search with exponential waiting times (VSSM/direct method) produces unbiased KMC trajectories.
    Standard result from Bortz et al. and Gillespie, invoked in Section 2 as the basis of the algorithm.
  • standard math Grouping sites into supersites and selecting by supersite-level rate sums does not bias event selection.
    This is the established 2-level method of Maksym, invoked in Section 3.3.
  • ad hoc to paper The toy benchmark is representative enough to support the factor-3 overhead claim.
    Section 3.4 acknowledges the test has no real reaction mechanism, pattern matching, or rate computation, and models the interaction-free baseline by deactivating the update step. The abstract nevertheless states the factor-3 conclusion without those caveats.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient implementation of Cluster Expansion models in surface Kinetic Monte Carlo simulations with lateral interactions: Subtraction Schemes, Supersites and the Supercluster Contraction." pith.science (2026). https://pith.science/paper/OR54HVOQ

@misc{pith2026190803526,
  author       = {Pith},
  title        = {Pith review of: Efficient implementation of Cluster Expansion models in surface Kinetic Monte Carlo simulations with lateral interactions: Subtraction Schemes, Supersites and the Supercluster Contraction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OR54HVOQ}},
  note         = {Machine review of arXiv:1908.03526}
}
read the original abstract

While lateral interaction models for reactions at surfaces have steadily gained popularity and grown in terms of complexity, their use in chemical kinetics has been impeded by the low performance of current KMC algorithms. The origins of the additional computational cost in KMC simulations with lateral interactions are traced back to the more elaborate Cluster Expansion Hamiltonian, the more extensive rate updating, and to the impracticality of rate-catalog-based algorithms for interacting adsorbate systems. Favoring instead site-based algorithms, we propose three ways to reduce the cost of KMC simulations: 1. Represent the lattice energy by a smaller Supercluster Hamiltonian without loss of accuracy, 2. employing Subtraction Schemes for updating key quantities in the simulation that undergo only small, local changes during a reaction event, and 3. applying efficient search algorithms from a set of established methods (Supersite Approach). The resulting algorithm is fixed-cost with respect to the number of lattice sites for practical lattice sizes and scales with the square of the range of lateral interactions. The overall added cost of including a complex lateral interaction model amounts to less than a factor 3. Practical issues in implementation due to finite numerical accuracy are discussed in detail, and further suggestions for treating long-range lateral interactions are made. We conclude that, while KMC simulations with complex lateral interaction models are challenging, these challenges can be overcome by modifying the established Variable Step Size Method by employing the Supercluster, Subtraction and Supersite algorithms (SSS-VSSM).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    (1) Hess, F.; Over, H. Catal. Sci. Technol. 2014, 4, 583–598. (2) Andersen, M.; Panosetti, C.; Reuter, K. Front. Chem. 2019, 7, 202–. (3) Stamatakis, M. J. Phys.: Condens. Matter 2015, 27, 013001. (4) Zuo, Z.-J.; Gao, X.-Y.; Han, P.-D.; Liu, S.-Z.; Huang, W. The Journal of Physical Chemistry C 2016, 120, 27500–27508. (5) Moskaleva, L.; Chiu, C.-c.; Genest...

    work page 2014

  2. [5]

    (11) Lian, Z.; Ali, S.; Liu, T.; Si, C.; Li, B.; Su, D. S. ACS Catalysis 2018, 8, 4694–4704. (12) Tetlow, H.; Posthuma de Boe r, J.; Ford, I. J.; Vvedensky, D. D.; Curcio, D.; Omiciuolo, L.; Lizzit, S.; Baraldi, A.; Kantorovich, L. Phys. Chem. Chem. Phys. 2016, 18, 27897–27909. (13) Stamatakis, M.; Vlachos, D. G. The Journal of Chemical Physics 2011, 134,...

    work page 2018

  3. [18]

    (35) Schulze, T. P. Journal of Computational Physics 2008, 227, 2455 –

    work page 2008

  4. [23]

    (24) Blel, S.; Hamouda, A. B. Vacuum 2018, 151, 133 –

    work page 2018

  5. [83]

    I.; Hong, S.; Rahman, T

    (8) Shah, S. I.; Hong, S.; Rahman, T. S. The Journal of Physical Chemistry C 2014, 118, 5226–5238. (9) Aleksandrov, H. A.; Moskaleva, L. V.; Zhao, Z.-J.; Basaran, D.; Chen, Z.-X.; Mei, D.; Rösch, N. Journal of Catalysis 2012, 285, 187 –

    work page 2014

  6. [94]

    M.; Schneider, W

    (16) Bajpai, A.; Mehta, P.; Frey, K.; Lehmer, A. M.; Schneider, W. F. ACS Catalysis 2018, 8, 1945–1954. (17) Hess, F.; Over, H. ACS Catalysis 2017, 7, 128–138. (18) Hess, F.; Sack, C.; Langsdorf, D.; Over, H. ACS Catalysis 2017, 7, 8420–8428. (19) Bajpai, A.; Frey, K.; Schneider, W. F. The Journal of Physical Chemistry C 2017, 121, 7344–7354. (20) Bray, J...

    work page 2018

  7. [139]

    The Journal of Physical Chemistry C 2012, 116, 581–591

    (25) Farkas, A.; Hess, F.; Over, H. The Journal of Physical Chemistry C 2012, 116, 581–591. (26) Sutton, J. E.; Lorenzi, J. M.; Krogel, J. T.; Xiong, Q.; Pannala, S.; Matera, S.; Savara, A. ACS Catalysis 2018, 8, 5002–5016. (27) Vignola, E.; Steinmann, S. N.; Le Mapihan, K.; Vandegehuchte, B. D.; Curulla, D.; Sautet, P. The Journal of Physical Chemistry C...

    work page 2012

  8. [195]

    (10) Mei, D.; Neurock, M.; Smith, C. M. Journal of Catalysis 2009, 268, 181 –

    work page 2009

Show all 15 references
  1. [594]

    (42) Bortz, A.; Kalos, M.; Lebowitz, J. J. Comp. Phys. 1975, 17, 10–18. (43) Gillespie, D. J. Phys. Chem. 1977, 81, 2340–2361

    1975

  2. [1299]

    Journal of Catalysis 2012, 286, 88 –

    (15) Wu, C.; Schmidt, D.; Wolverton, C.; Schneider, W. Journal of Catalysis 2012, 286, 88 –

    2012

  3. [1480]

    Surface Science 2019, 681, 18 –

    (23) Chen, X.; Li, Y. Surface Science 2019, 681, 18 –

    2019

  4. [2150]

    (38) Leetmaa, M.; Skorodumova, N. V. Computer Physics Communications 2014, 185, 2340 –

    2014

  5. [2349]

    The Journal of Chemical Physics 2018, 149, 114101

    (39) Jørgensen, M.; Grönbeck, H. The Journal of Chemical Physics 2018, 149, 114101. (40) Blue, J. L.; Beichl, I.; Sullivan, F. Phys. Rev. E 1995, 51, R867–R868. (41) Maksym, P. Semicond. Sci. Technol. 1988, 3,

    2018

  6. [2404]

    Journal of the American Chemical Society 2019, 10.1021/jacs.9b02132

    (6) Jørgensen, M.; Grönbeck, H. Journal of the American Chemical Society 2019, 10.1021/jacs.9b02132. (7) Prats, H.; Gamallo, P.; Illas, F.; Sayós, R. Journal of Catalysis 2016, 342, 75 –

    2019 doi

  7. [2462]

    J.; Segers, J

    (36) Lukkien, J. J.; Segers, J. P. L.; Hilbers, P. A. J.; Gelten, R. J.; Jansen, A. P. J. Phys. Rev. E 1998, 58, 2598–2610. (37) Hoffmann, M. J.; Matera, S.; Reuter, K. Computer Physics Communications 2014, 185, 2138 –

    1998

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.