pith. sign in

arxiv: 2606.15414 · v2 · pith:WU5HVR6Lnew · submitted 2026-06-13 · ❄️ cond-mat.dis-nn · cond-mat.stat-mech· stat.CO

Cluster-based Message-Passing (CluMP) Optimization for Complex QUBO Problems

Paolo Rissone , Stefan Boettcher , Alfonso Amendola , Simone Sala , Federico Ricci-Tersenghi This is my paper

Pith reviewed 2026-06-27 03:54 UTC · model grok-4.3

classification ❄️ cond-mat.dis-nn cond-mat.stat-mechstat.CO
keywords QUBO optimizationcluster updatesbelief propagationspin glassescombinatorial optimizationIsing modelsmessage passingfrustration
0
0 comments X

The pith

CluMP uses belief-propagation-guided cluster updates to reach lower energies in frustrated QUBO problems than single-spin dynamics.

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

The paper introduces CluMP, an algorithm that selects connected clusters of spins and updates them collectively after running belief propagation on each cluster. By keeping frustration low inside the chosen clusters, the method makes belief propagation converge on subgraphs that can contain hundreds of variables. Benchmarks on spin-glass instances defined on random regular graphs and on two- and three-dimensional lattices show that these collective moves escape the metastable states that trap conventional single-spin flips. The approach therefore finds lower final energies after fewer total spin operations. Because many industrial and scientific QUBO instances are sparse and frustrated, a reliable way to perform medium-range rearrangements matters for practical solvers.

Core claim

CluMP performs collective updates on connected clusters of spins using information from Belief Propagation. By controlling the amount of frustration within clusters, CluMP enables BP convergence on large subgraphs and proposes nonlocal rearrangements involving up to hundreds of spins in a single move. Benchmarks against state-of-the-art local-update heuristics on spin-glass models defined on random regular graphs and lattice regular graphs in two and three dimensions show that cluster moves consistently bypass local trapping and reach lower energies with fewer effective operations than single-spin dynamics.

What carries the argument

Cluster-based Message-Passing (CluMP) that selects frustration-controlled clusters and runs belief propagation to generate collective spin rearrangements on sparse graphs.

If this is right

  • Cluster moves bypass local trapping in spin-glass models on random regular graphs and on 2D and 3D lattices.
  • The method reaches lower energies with fewer effective operations than single-spin dynamics.
  • Frustration-tolerant cluster updates can be implemented efficiently on sparse graphs.
  • The CluMP framework supplies a scalable strategy for large-scale combinatorial optimization and inference problems where medium- and long-range correlations dominate.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same cluster-selection logic might be combined with other message-passing or sampling schemes to handle even denser or time-varying graphs.
  • Because the method works on both random regular and lattice topologies, it could transfer to grid-structured problems such as image denoising or lattice protein folding.
  • If the cluster-construction heuristic can be made fully local and parallel, CluMP becomes a candidate for distributed or hardware-accelerated solvers.
  • The performance gain on three-dimensional lattices suggests the approach may help with optimization tasks whose correlation length exceeds a few lattice spacings.

Load-bearing premise

That keeping frustration low inside selected clusters lets belief propagation converge reliably on large subgraphs without creating new trapping mechanisms.

What would settle it

On a fixed large spin-glass instance with known ground-state energy, run CluMP and a tuned single-spin heuristic to the same computational budget and check whether CluMP ever returns a higher energy or requires more total spin flips.

Figures

Figures reproduced from arXiv: 2606.15414 by Alfonso Amendola, Federico Ricci-Tersenghi, Paolo Rissone, Simone Sala, Stefan Boettcher.

Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
read the original abstract

Quadratic Unconstrained Boolean Optimization (QUBO) problems are widespread in both industrial applications and scientific studies. A QUBO problem corresponds to the optimization of a system of Ising spins defined on a generally sparse and heterogeneous graph. When the QUBO problem contains conflicting requests, the corresponding Ising system is frustrated, generating a complex energy landscape, which is hard to explore and optimize. Despite extensive algorithmic and hardware developments, finding low-energy configurations in these systems remains challenging (e.g., local-update heuristics typically become trapped in metastable states), especially when the (possibly frustrated) interactions generate extended correlated domains. We introduce CluMP (Cluster-based Message-Passing), an algorithm that performs collective updates on connected clusters of spins using information from Belief Propagation (BP). By controlling the amount of frustration within clusters, CluMP enables BP convergence on large subgraphs and proposes nonlocal rearrangements involving up to hundreds of spins in a single move. We benchmark CluMP against state-of-the-art local-update heuristics on spin-glass models defined on several graph topologies, including random regular graphs and lattice regular graphs in two and three dimensions. Cluster moves consistently bypass local trapping and reach lower energies with fewer effective operations than single-spin dynamics. These results demonstrate that frustration-tolerant cluster updates can be implemented efficiently on sparse graphs. The CluMP framework provides a scalable strategy for large-scale combinatorial optimization and inference problems, where exploiting medium- and long-range correlations is key to navigating complex energy landscapes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces CluMP, a cluster-based message-passing algorithm for QUBO optimization on sparse, heterogeneous graphs. It selects connected clusters of spins, controls frustration within them to enable Belief Propagation convergence on large subgraphs, and performs nonlocal collective updates. Benchmarks on spin-glass models defined on random regular graphs and 2D/3D lattice graphs claim that these cluster moves consistently reach lower energies with fewer effective operations than single-spin local-update heuristics by bypassing metastable traps.

Significance. If the performance claims hold under detailed scrutiny, the work offers a practical advance for navigating complex energy landscapes in frustrated systems by exploiting medium-range correlations via controlled clusters. This is relevant to both combinatorial optimization and inference tasks on sparse graphs. The empirical focus on standard spin-glass instances across multiple topologies is a positive aspect, though the absence of parameter-free derivations or machine-checked elements limits the strength of the contribution relative to purely theoretical advances.

major comments (2)
  1. [Numerical Experiments] Numerical Experiments section: the central claim that cluster moves reach lower energies with fewer operations lacks reported error bars, number of independent runs per instance, graph-size distribution, and explicit definition of 'effective operations'; without these, the statistical significance of the reported gap versus local heuristics cannot be assessed and the cross-topology consistency claim is unsupported.
  2. [CluMP Algorithm] CluMP Algorithm section (cluster construction and frustration control): the key assumption that controlling frustration within clusters enables reliable BP convergence on large subgraphs without introducing new trapping mechanisms is stated at a high level but is not accompanied by quantitative convergence diagnostics, failure-rate analysis, or ablation on frustration thresholds; this is load-bearing for the performance advantage.
minor comments (2)
  1. [Abstract] Abstract: the term 'effective operations' is used in the performance claim but is only defined later; moving a brief definition to the abstract would improve readability.
  2. [Numerical Experiments] Figure captions in the benchmark section: several panels comparing energy vs. operations do not label the different heuristics or include legend entries for CluMP variants, reducing clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address the two major comments point by point below. Where the comments identify missing details that strengthen the presentation, we agree to incorporate revisions.

read point-by-point responses

  1. Referee: [Numerical Experiments] Numerical Experiments section: the central claim that cluster moves reach lower energies with fewer operations lacks reported error bars, number of independent runs per instance, graph-size distribution, and explicit definition of 'effective operations'; without these, the statistical significance of the reported gap versus local heuristics cannot be assessed and the cross-topology consistency claim is unsupported.

    Authors: We agree that the Numerical Experiments section requires additional statistical information to support the performance claims. In the revised manuscript we will add error bars on all reported metrics (computed over independent runs), explicitly state the number of independent runs performed per instance, provide the distribution of graph sizes tested, and give a precise definition of 'effective operations' (total BP message updates normalized by graph size). These additions will allow readers to assess statistical significance and cross-topology consistency. revision: yes

  2. Referee: [CluMP Algorithm] CluMP Algorithm section (cluster construction and frustration control): the key assumption that controlling frustration within clusters enables reliable BP convergence on large subgraphs without introducing new trapping mechanisms is stated at a high level but is not accompanied by quantitative convergence diagnostics, failure-rate analysis, or ablation on frustration thresholds; this is load-bearing for the performance advantage.

    Authors: We acknowledge that quantitative diagnostics would better substantiate the role of frustration control. In the revised CluMP Algorithm section we will add convergence diagnostics (e.g., BP residual norms and iteration counts per cluster), report failure rates as a function of cluster size and frustration threshold, and include an ablation study varying the frustration threshold to show its effect on both convergence reliability and final energies. These results will be presented alongside the existing algorithmic description. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The manuscript introduces the CluMP algorithm as a heuristic combining Belief Propagation with cluster updates for QUBO/spin-glass optimization. All load-bearing claims are empirical performance comparisons on random-regular and lattice graphs; no first-principles derivations, parameter fits renamed as predictions, or self-citation chains that reduce the central result to its own inputs appear in the abstract or surrounding context. The method is presented as a practical construction whose validity is tested externally via benchmarks rather than by algebraic identity with its assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; all technical details are absent.

pith-pipeline@v0.9.1-grok · 5819 in / 1017 out tokens · 48375 ms · 2026-06-27T03:54:56.839967+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 1 canonical work pages

  1. [1]

    National Center for HPC, Big Data and Quantum Computing

    partially addresses the problem by constructing frustration-free clusters whose GS can be computed ex- actly, while freezing the remainder of the system. Ex- tensions based on Belief Propagation (BP) [24] en- able finite-temperature sampling, but remain confined to frustration-free clusters. Introducing frustration typi- cally causes BP to lose convergenc...

    Pith/arXiv arXiv 2026

  2. [2]

    Lucas, Ising formulations of many np problems, Front

    A. Lucas, Ising formulations of many np problems, Front. Phys.2, 74887 (2014)

    2014

  3. [3]

    Barahona, On the computational complexity of ising spin glass models, J

    F. Barahona, On the computational complexity of ising spin glass models, J. Phys. A: Math. Gen.15, 3241 (1982)

    1982

  4. [4]

    Metropolis, A

    N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, Equation of state calcula- tions by fast computing machines, J. Chem. Phys.21, 1087 (1953)

    1953

  5. [5]

    W. K. Hastings, Monte carlo sampling methods using markov chains and their applications, Biometrika57, 97 (1970)

    1970

  6. [6]

    Kirkpatrick, C

    S. Kirkpatrick, C. Gelatt, and M. Vecchi, Optimization by simulated annealing, Science220, 671 (1983)

    1983

  7. [7]

    Boettcher, Extremal optimization: heuristics via co- evolutionary avalanches, Comput

    S. Boettcher, Extremal optimization: heuristics via co- evolutionary avalanches, Comput. Sci. Eng.2, 75 (2000)

    2000

  8. [8]

    Boettcher,New optimization algorithms in physics (Wiley Online Library, 2004) Chap

    S. Boettcher,New optimization algorithms in physics (Wiley Online Library, 2004) Chap. 11

    2004

  9. [9]

    M. C. Angelini and F. Ricci-Tersenghi, Monte carlo al- gorithms are very effective in finding the largest inde- pendent set in sparse random graphs, Physical Review E 100, 013302 (2019)

    2019

  10. [10]

    Caracciolo, A

    S. Caracciolo, A. Hartmann, S. Kirkpatrick, and M. Weigel, Simulated annealing, optimization, searching for ground states, inSpin Glass Theory and Far Beyond: Replica Symmetry Breaking After 40 Years(World Sci- entific, 2023) pp. 1–20

    2023

  11. [11]

    M. C. Angelini and F. Ricci-Tersenghi, Limits and per- formances of algorithms based on simulated annealing in solving sparse hard inference problems, Physical Review X13, 021011 (2023)

    2023

  12. [12]

    M. C. Angelini, M. Avila-Gonz´ alez, F. D’Amico, D. Machado, R. Mulet, and F. Ricci-Tersenghi, Algorith- mic thresholds in combinatorial optimization depend on the time scaling, Phys. Rev. X16, 011045 (2026)

    2026

  13. [13]

    R. H. Swendsen and J.-S. Wang, Nonuniversal critical dynamics in monte carlo simulations, Phys. Rev. Lett. 58, 86 (1987)

    1987

  14. [14]

    Wolff, Collective monte carlo updating for spin sys- tems, Phys

    U. Wolff, Collective monte carlo updating for spin sys- tems, Phys. Rev. Lett.62, 361 (1989)

    1989

  15. [15]

    Wang and R

    J.-S. Wang and R. H. Swendsen, Cluster monte carlo al- gorithms, Physica A Stat. Mech. Appl.167, 565 (1990)

    1990

  16. [16]

    C. M. Fortuin and P. W. Kasteleyn, On the random- cluster model: I. introduction and relation to other mod- els, Physica57, 536 (1972)

    1972

  17. [17]

    Coniglio and W

    A. Coniglio and W. Klein, Clusters and ising critical droplets: a renormalisation group approach, J. Phys. A Math. Gen.13, 2775 (1980)

    1980

  18. [18]

    Kandel and E

    D. Kandel and E. Domany, General cluster monte carlo dynamics, Phys. Rev. B43, 8539 (1991)

    1991

  19. [19]

    Cataudella, A

    V. Cataudella, A. Coniglio, L. De Arcangelis, and F. di Liberto, Cluster formulation for frustrated spin models, Physica A Stat. Mech. Appl.192, 167 (1993)

    1993

  20. [20]

    M¨ unster and M

    L. M¨ unster and M. Weigel, Cluster percolation in the two-dimensional ising spin glass, Physical Review E107, 054103 (2023)

    2023

  21. [21]

    Houdayer, A cluster monte carlo algorithm for 2- dimensional spin glasses, Eur

    J. Houdayer, A cluster monte carlo algorithm for 2- dimensional spin glasses, Eur. Phys. J. B22, 479 (2001)

    2001

  22. [22]

    Houdayer and A

    J. Houdayer and A. K. Hartmann, Low-temperature be- havior of two-dimensional gaussian ising spin glasses, Phys. Rev. B70, 014418 (2004)

    2004

  23. [23]

    Bernaschi, L

    M. Bernaschi, L. A. Fern´ andez, I. G.-A. Pemart´ ın, V. Mart´ ın-Mayor, G. Parisi, and F. Ricci-Tersenghi, Low energy excitations in a long prism geometry: computing the lower critical dimension of the ising spin glass (2026), arXiv:2601.07926

    arXiv 2026

  24. [24]

    A. K. Hartmann, Cluster-exact approximation of spin glass groundstates, Phys. A: Stat. Mech. Appl.224, 480 (1996)

    1996

  25. [25]

    Decelle and F

    A. Decelle and F. Krzakala, Belief-propagation-guided monte-carlo sampling, Phys. Rev. B89, 214421 (2014)

    2014

  26. [26]

    Lage-Castellanos, R

    A. Lage-Castellanos, R. Mulet, F. Ricci-Tersenghi, and T. Rizzo, Inference algorithm for finite-dimensional spin glasses: Belief propagation on the dual lattice, Phy. Rev. E84, 046706 (2011)

    2011

  27. [27]

    J. R. Finˇ zgar, A. Kerschbaumer, M. J. Schuetz, C. B. Mendl, and H. G. Katzgraber, Quantum-informed recur- sive optimization algorithms, PRX Quantum5, 020327 (2024)

    2024

  28. [28]

    P. J. Eder, A. Kerschbaumer, J. R. Finˇ zgar, R. A. Med- ina, M. J. Schuetz, H. G. Katzgraber, S. Braun, and C. B. Mendl, Quantum-guided cluster algorithms for combina- torial optimization, in2025 IEEE QCE, Vol. 1 (IEEE,

  29. [29]

    Castellani and A

    T. Castellani and A. Cavagna, Spin-glass theory for pedestrians, J. Stat. Mech.: Theory Exp.2005(05), P05012

    2005

  30. [30]

    Parisi, Spin glasses and fragile glasses: Statics, dy- namics, and complexity, Proc

    G. Parisi, Spin glasses and fragile glasses: Statics, dy- namics, and complexity, Proc. Natl. Acad. Sci. U.S.A. 103, 7948 (2006)

    2006

  31. [31]

    See the End Matter for a brief description of the belief propagation update equations at zero temperature and the algorithm initialization

  32. [32]

    Lucibello, F

    C. Lucibello, F. Morone, G. Parisi, F. Ricci-Tersenghi, and T. Rizzo, Finite-size corrections to disordered ising models on random regular graphs, Phys. Rev. E90, 012146 (2014)

    2014

  33. [34]

    Liang and W

    F. Liang and W. H. Wong, Evolutionary monte carlo: ap- plications to c p model sampling and change point prob- lem, Stat. Sin. , 317 (2000)

    2000

  34. [35]

    For other values ofVthe optimalϕis unchanged for LRGs and should be scaled byVfor RRGs

  35. [36]

    Boettcher and A

    S. Boettcher and A. Percus, Nature’s way of optimizing, Artif. Intell.119, 275 (2000)

    2000

  36. [37]

    Boettcher and A

    S. Boettcher and A. G. Percus, Optimization with ex- tremal dynamics, complexity8, 57 (2002)

    2002

  37. [38]

    Rissone, Cluster-based message-passing (clump) optimization in rugged energy landscapes - code, https://github.com/PaoloRiss1/CluMP-optimization (2026)

    P. Rissone, Cluster-based message-passing (clump) optimization in rugged energy landscapes - code, https://github.com/PaoloRiss1/CluMP-optimization (2026)

    2026

  38. [39]

    See Supplemental Material at [URL will be inserted by publisher] for additional information about the CluMP performance on RRGs with low connectivity and integer couplings

  39. [40]

    While completing this work, a new proposal to use the Houdayer cluster move has been shown effective ind= 3 [43]

  40. [41]

    Dominguez, A

    E. Dominguez, A. Lage-Castellanos, R. Mulet, F. Ricci- Tersenghi, and T. Rizzo, Characterizing and improv- ing generalized belief propagation algorithms on the 2d edwards–anderson model, Journal of Statistical Mechan- ics: Theory and Experiment2011, P12007 (2011)

    2011

  41. [42]

    Lage-Castellanos, R

    A. Lage-Castellanos, R. Mulet, and F. Ricci-Tersenghi, Message passing and monte carlo algorithms: Connecting fixed points with metastable states, Europhysics Letters 107, 57011 (2014)

    2014

  42. [43]

    Rissone, Cluster-based message-passing (clump) optimization in rugged energy landscapes - data, https://doi.org/10.5281/zenodo.19048237 (2026)

    P. Rissone, Cluster-based message-passing (clump) optimization in rugged energy landscapes - data, https://doi.org/10.5281/zenodo.19048237 (2026)

    work page doi:10.5281/zenodo.19048237 2026

  43. [44]

    Chilin, E

    C. Chilin, E. Marinari, V. Mart´ ın-Mayor, G. Parisi, J. J. Ruiz-Lorenzo, and D. Yllanes, Cluster moves with an entropic reservoir accelerate low-temperature simu- lations of three-dimensional spin glasses, arXiv preprint arXiv:2605.25872 (2026)

    Pith/arXiv arXiv 2026

  44. [45]

    M´ ezard and G

    M. M´ ezard and G. Parisi, The cavity method at zero temperature, J. Stat. Phys.111, 1 (2003)

    2003

  45. [46]

    Perugini and F

    G. Perugini and F. Ricci-Tersenghi, Improved belief prop- agation algorithm finds many bethe states in the random- field ising model on random graphs, Phys. Rev. E97, 012152 (2018). END MATTER Belief Propagation: Update Equations at Zero Temperature Belief Propagation (BP) is an iterative message-passing algorithm that aims at solving the self-consistency...

    2018

  46. [47]

    Machta, Population annealing with weighted averages: A monte carlo method for rough free-energy landscapes, Phys

    J. Machta, Population annealing with weighted averages: A monte carlo method for rough free-energy landscapes, Phys. Rev. E82, 026704 (2010)

    2010

  47. [48]

    M´ ezard, G

    M. M´ ezard, G. Parisi, and M. A. Virasoro,Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, Vol. 9 (World Scientific Publishing Company, 1987)

    1987

  48. [49]

    A. K. Hartmann, Ground-state landscape of j ising spin glasses, The European Physical Journal B-Condensed Matter and Complex Systems8, 619 (1999)

    1999