Pith. sign in

REVIEW 5 major objections 4 minor 1 cited by

Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems

T0 review · 5 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The symmetric binary perceptron hosts a delocalized cluster of connected solutions that is stable only above a threshold $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}(\alpha)$; below it the connecting paths shatter.

desk verdict Genuinely new connected-solutions ensemble with concrete predictions, but the central cluster-stability claim rests on an Ansatz the paper itself shows is never a saddle point. read the letter →

arxiv 2505.20954 v5 pith:JK7WNMMZ submitted 2025-05-27 cond-mat.dis-nn cond-mat.stat-mech

Damien Barbier This is my paper · ORCID
classification cond-mat.dis-nncond-mat.stat-mech
keywords symmetricbinaryperceptronconnectedsolutionsno-memoryAnsatzlocalentropyreplicamethodconstraintsatisfactionproblemstatisticalmechanicsofdisorderedsystemsMonte-Carloannealing
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

The paper sets out to show that local-entropy biases—which favor configurations surrounded by other low-energy configurations—are the first step toward a statistical-mechanics description of connected solution clusters, and that such clusters can be computed well enough to predict where algorithms stall. The testbed is the symmetric binary perceptron, where typical solutions are isolated yet local algorithms still find solutions in part of the $(\alpha,\kappa)$ plane. The author defines an ensemble over chains of solutions whose consecutive members overlap by $m$, takes the no-memory Ansatz in which each solution only correlates with its direct ancestor, and sends $m \to 1$ while the chain length diverges. The result is a star-shaped cluster of delocalized connected solutions that is locally stable only above a threshold $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}(\alpha)$; below it the paths composing the cluster shatter, a transition that conventional Franz-Parisi computations miss. A Monte-Carlo dynamics built on the derived effective loss decorrelates until roughly the same threshold, confirming the prediction.

What carries the argument

The central object is the no-memory Ansatz: an assumption on the replica overlap matrix of a chain of configurations in which $Q^{-1}_{P_k,P'_{k'}}$ and $\hat{Q}_{P_k,P'_{k'}}$ are nonzero only between each configuration and its direct ancestor, forcing overlaps $m^{|k-k'|}$ along a path and an ultrametric (Bethe-tree) geometry. Under this Ansatz the replica free energy reduces to an iterative energy kernel $G^{\rm energ}_{k}(w_k,m,\{y_l\})$, and for $y_k=1$ the iteration converges to its leading eigenvector, which generates the delocalized cluster. The load-bearing quantity is the local entropy $s_{\rm loc}(k)$, the number of configurations gained when the connected chain is extended from layer $k-1$ to layer $k$; its perturbation $\delta s_{\rm loc}(k,k')$, defined by changing an ancestor overlap from $m^{|k-k'|}$ to $m^{|k-k'|-2}$, is the stability criterion, and the line where its sign changes is the predicted transition $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}(\alpha)$.

What would settle it

Measure the typical overlap between a solution and its grandparent along connected chains just below the predicted threshold: if non-ancestor overlaps grow beyond the no-memory value $m^2$, the Ansatz and the predicted $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}$ are wrong. A second falsifier is to rerun the annealed Monte-Carlo at $\alpha=0.75$ with the exact $G^{\rm energ}_{\lambda_{\rm top}}$ kernel instead of the quadratic approximation and check whether decorrelation still stops at the predicted threshold.

Watch

Extended reading notes

Core claim

The central claim is that the symmetric binary perceptron contains a subdominant but algorithmically relevant manifold: a star-shaped cluster of delocalized connected solutions, each linked along a chain to its direct ancestor. In the construction, all Lagrange multipliers are set to one, the overlap between consecutive solutions goes to $m \to 1$, and the chain length is sent to infinity so that the endpoints become fully uncorrelated; the cluster then has an edge of less-robust minima and a core of more-robust minima whose margin distributions are both computed explicitly. The paper proves that this no-memory geometry is globally unstable as a saddle point of the connected free energy, so the cluster does not dominate the measure; what governs it instead is the local stability of the entropy $s_{\rm loc}(k)$, the number of solutions gained by extending a path, perturbed by re-correlating a solution with a distant ancestor. When the perturbation $\delta s_{\rm loc}(k,k')$ changes sign, the connecting paths destabilize at $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}(\alpha)$, and the paper argues and then verifies numerically that the same threshold marks where a Monte-Carlo algorithm sampling the edge with the effective loss stops decorrelating. The Franz-Parisi potential overestimates the clustering transition, and the discrepancy is traced to the divergence of the margin cost function as $|w|$ approaches $\kappa$.

Load-bearing premise

The construction rests on the assumption that the connected solutions of interest arrange into chains in which each configuration is correlated only with its direct ancestor, and that the particular perturbation size chosen is the right probe for when those chains destabilize.

Editorial extensions

If this is right

  • The annealed Monte-Carlo with the effective loss should decorrelate for $\kappa$ above $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}(\alpha)$ and fail below it; simulations for $\alpha = 0.3, 0.5, 0.75$ show the decorrelation time $t_{\rm dec}/N$ diverging near the predicted threshold.
  • The no-memory cluster is a subdominant manifold, so standard replica computations that select the dominant isolated minima cannot see the shattering transition; local-entropy stability is the quantity that detects it.
  • The Franz-Parisi potential overestimates the clustering transition for the symmetric binary perceptron, so the local-stability criterion is the sharper diagnostic whenever the margin cost diverges at the constraint edge.
  • The effective-loss construction gives a principled design rule for dynamics: target the edge of the connected cluster by compressing margins toward zero, rather than sampling typical isolated solutions.
  • Below $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}$ the edge solutions develop an overlap gap and behave like a frozen one-step replica-symmetry-broken phase, explaining why local algorithms get trapped even though solutions remain exponentially numerous.

Reading between the lines

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

  • Inference: the nested local-entropy construction should transfer to other constraint satisfaction problems with isolated typical solutions; if their margin kernels also diverge at $|w|=\kappa$, the local-stability criterion may generically precede the Franz-Parisi transition.
  • Inference: the quadratic approximation $(\kappa-w)(\kappa+w)/\kappa^2$ to $G^{\rm energ}_{\lambda_{\rm top}}$ degrades as $\alpha$ grows, so using the exact eigenvector kernel could shift the predicted threshold; a direct numerical evaluation would settle whether $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}$ is approximation-independent.
  • Inference: the divergence $\partial_w^2 \log G \approx (\kappa-|w|)^{-2}$ implies the landscape around connected minima becomes steeper with $N$, predicting an $N$-dependent algorithmic slowdown even above the threshold; the damped loss in Appendix E partially removes this effect and could be used to measure it quantitatively.
  • Inference: the paper leaves open whether clusters with memory (nonzero couplings beyond the direct ancestor) survive below $\kappa^{\rm no\text{-}mem}_{\rm loc\, stab.}$; perturbing around a two-step-memory Ansatz would test for a secondary transition and might explain what happens to solutions below the threshold.
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

5 major / 4 minor

Summary. The manuscript introduces a statistical-mechanics ensemble for connected solutions in constraint satisfaction problems, built from iterated local-entropy biases, and applies it to the symmetric binary perceptron (SBP). Under a no-memory overlap ansatz, with all Lagrange multipliers set to one, m→1, and an infinite chain length, the paper derives an effective edge loss, edge and core margin distributions, and edge and local entropies, and identifies a delocalized, star-shaped cluster of SBP solutions. It then proposes a local-stability criterion for the local entropy, defines a threshold κ_loc.stab., and presents Monte-Carlo simulations using an effective loss with a simplified kernel, reporting that the algorithm decorrelates down to κ≈κ_loc.stab..

Significance. If the central claim were established, the paper would provide a genuinely new statistical-mechanics tool for characterizing dynamically accessible connected solution clusters in rugged landscapes, going beyond standard Franz-Parisi computations. The manuscript is creative, technically ambitious, and unusually transparent about the main technical caveat, Eq. (57). It also makes falsifiable predictions about margin distributions and algorithmic decorrelation times and compares them with simulations at several system sizes. However, the load-bearing stability argument is not currently valid as a saddle-point or Hessian analysis, its sign convention is internally inconsistent in the text, and the numerical validation is largely in-sample because the algorithm is built from the same no-memory ansatz whose physical relevance is at issue. These concerns must be resolved before the paper's main conclusions can be accepted.

major comments (5)
  1. [Sec. 3.3, Eqs. (57)-(60)] The global instability result, Eq. (57), states that the no-memory ansatz is never a stationary point of the connected free energy: δϕ/δQ > 0 for all non-ancestor overlap pairs, for all α and κ. The paper correctly acknowledges the two logical possibilities, that the no-memory manifold is subdominant or non-physical, but the proposed local-stability calculation does not resolve this dichotomy. Equations (58)-(60) evaluate the response of the local entropy s_loc along one prescribed perturbation, Q_{Pk,P'k'} = m^{|k-k'|-2}, with the exponent −2 chosen for convenience in App. D.2, and then declare the sign of δs_loc to be the stability indicator. Because the unperturbed geometry is not stationary, first-order variations of the free energy dominate the measure; a sign change of δs_loc along a single arbitrary direction is not a Hessian criterion and does not establish that no-memory paths are the relevant connected configurations, nor that they shatter at κ_loc.stab. To support the central claim, the manuscript needs either to identify a true stationary point of the connected free energy whose Hessian is computed, or to explicitly reframe the claim as a property of the no-memory ansatz rather than of the physical solution manifold.
  2. [Sec. 3.3, after Eq. (59) and the paragraph containing δs_loc(k,k')<0] The sign convention for the local-stability criterion is internally inconsistent. The text states that negative δs_loc means the path geometry is stable and positive δs_loc means it is destabilized. A few paragraphs later, however, it says that in a range of parameters the core is 'locally unstable -δsloc(k,k')<0-', which contradicts the earlier convention. Figure 5's caption also equates stability with δs_loc negative for all distances. Since the threshold κ_loc.stab. is defined entirely by a change of sign of this quantity, the paper must correct this contradiction and state unambiguously which sign corresponds to destabilization.
  3. [Sec. 4, Eqs. (45), (61)-(62), Figs. 8, 10, 11] The numerical validation is partly in-sample. The Monte Carlo loss is L_eff from Eq. (45), which is derived from the same no-memory ansatz whose stability is the central claim, and the simplified kernel G̃ in Eq. (62) is chosen by comparison with the theoretical G_λtop. Agreement between the predicted and measured margin distributions and decorrelation profiles therefore confirms that the algorithm samples the designed biased measure; it does not independently establish that this measure corresponds to a physical, dominant cluster of SBP solutions. An independent test of the cluster geometry, for example measuring overlap distributions among solutions found by an unbiased or differently biased solver, is needed to break this circularity.
  4. [Sec. 4, Fig. 8 and the paragraph defining the stopping criterion] The claim that t_dec 'diverges' near κ_loc.stab. is not supported by the data as presented, because the protocol stops each annealing round when no full decorrelation is observed for t/N < 1500. The plotted t_dec is therefore capped at 1500N, and the apparent divergence may just reflect the finite observation window. The paper should distinguish a true divergence from a sharp increase beyond the cutoff, for instance by showing survival probabilities or longer runs near the predicted threshold.
  5. [Sec. 3.3, Fig. 5 and Fig. 6] The critical line κ_loc.stab. is obtained by fitting only four points (the black dots in Fig. 5, reproduced in Fig. 6), and the text does not report error bars, sensitivity to the value of m, or the dependence on the chosen perturbation amplitude. Since the entire phase diagram and the comparison with simulations hinge on this line, a more systematic determination is needed before the threshold can be considered quantitative.
minor comments (4)
  1. [Eq. (31)] The text says 'given the constraint equations (31, 31)' but should refer to Eqs. (31)-(32); this is likely a typo.
  2. [Captions of Figs. 8 and 9] The captions list N = {1250, 2500, 500, 10^4}, but the text and Fig. 10 use N = 5000; the captions should be corrected to 5000.
  3. [Sec. 4, Eq. (62)] The simplified kernel G̃_λtop is introduced with 'lim_{m→1} G ≈ G̃', but G̃ is independent of m and no convergence rate or quantitative accuracy measure is given; Fig. 11 shows the approximation deteriorates with increasing α, so a quantitative statement of its validity range would be useful.
  4. [Sec. 3.2.2, Eq. (54)] The sentence stating that the edge entropy s_x0 'effectively counts the total number of minima in the entire cluster' is not derived in the text and is somewhat counterintuitive given the edge distribution is used; a brief justification would improve clarity.

Circularity Check

2 steps flagged · score 6.0 of 10

Central cluster and threshold rest on a self-cited no-memory ansatz; the Monte-Carlo validation is built from the same effective loss, so the agreement is in-sample.

  1. ansatz smuggled in via citation [Section 3.1, Eqs. (29)-(30)]
    "The simplification we will take comes from [38] and is referred to as the no-memory Ansatz. It ascribes each solution to correlate only with its direct ancestor: Q^{-1}_{Pk,P' k'} ≠ 0 iff P'_{k'} ∈ {P_k, P*_k} (k'≤k), ..."

    This is the load-bearing premise: Eqs. (29)-(30) fix the overlap structure and lead to the Bethe-tree free energy, the delocalized star cluster, and κ_loc.stab. The premise is not derived here; it is imported from the author's own prior work [38], where it is itself an ansatz. The paper's own global-stability computation then shows the no-memory geometry is never a saddle point (Eq. 57: δφ/δQ>0 for all non-ancestor pairs), and the local-stability test (Eqs. 58-60) substitutes a prescribed perturbation Q=m^{|k-k'|-2} chosen for convenience (App. D.2). Thus the central stability threshold is forced by the self-cited ansatz plus an ad hoc perturbation, not by an independent mathematical fact.

  2. fitted input called prediction [Section 4, Eqs. (45), (61)-(62), (70); Figs. 8 and 11]
    "Instead of sampling solutions using the original loss L_SBP(·) -see Eq. (9)-, we will target minima in the delocalized cluster(s) using L_eff_SBP(·) from Eq. (45). ... We propose this function after numerically studying the shape G_λtop[·,·], for different values of κ, and observing good agreement between the two."

    The Monte-Carlo acceptance is based on the same effective loss L_eff (Eq. 45) that defines the edge distribution P_edge (Eq. 55), with G approximated by the theory-fitted G̃ (Eq. 62). Consequently the simulation's margin distribution matching P_edge (Fig. 11) and the failure to decorrelate near κ_loc.stab (Fig. 8) are checks that the dynamics equilibrates in its own target measure, not independent evidence for the no-memory cluster's existence. The 'prediction' of P_edge is in-sample by construction; the algorithm is not an external probe of the cluster.

full rationale

The algebraic derivation of the free energy and entropies is internally coherent, and the paper honestly reports Eq. (57)'s global instability. The circularity is in the validation logic and in the load-bearing self-citation for the ansatz. The no-memory geometry is taken from the author's own [38]; the paper does not derive it from the full free-energy optimization, and its own Eq. (57) shows it is never a stationary point. The later local-stability criterion imposes a specific perturbation Q=m^{|k-k'|-2}, chosen for convenience, so the threshold κ_loc.stab is a property of the ansatz-plus-perturbation construction rather than a first-principles result. The numerical section then uses a Monte-Carlo algorithm whose effective loss (Eq. 45) and its approximation (Eq. 62) are constructed from the same no-memory cluster, making the observed P_edge agreement and the decorrelation failure near κ_loc.stab internally consistent rather than externally falsifying. I am not claiming the computations are incorrect; I am flagging that the central prediction reduces, at least partially, to its own construction.

Assumptions & free parameters 6 free parameters · 6 assumptions · 1 invented entities

The central claim rests on a chain of modeling choices: the no-memory Ansatz (shown by the paper to be globally unstable), the y_k=1 chain limit, the Perron-Frobenius eigenvector selection, an ad hoc local-stability perturbation, and a simplified kernel used by the algorithm. The phase boundary itself is fitted through four numerical points. These choices are not independently benchmarked, which is why the ledger is dominated by ad hoc_to_paper assumptions.

free parameters (6)
  • Overlap m (taken to 1) = 1 (limit m→1)
    The overlap between consecutive solutions in the chain is a modeling parameter; the paper analyzes the limit m→1 to enforce strong connectivity. The limit is not fitted to data but controls the local-stability calculation.
  • Lagrange multipliers y_k = 1 for all k in [1,k_f]
    All local-entropy Lagrange multipliers are set to 1 to obtain a linear Perron-Frobenius problem (Sec. 3.2.1). This is a simplifying choice, not derived from data.
  • Perturbation exponent in local-stability check = m^{|k-k'|-2}
    Eq. 60 perturbs overlaps by reducing the exponent by 2; the authors state this 'facilitates correspondence with other physical objects' (App. D.2), but it is an ad hoc choice that determines where the sign change of δsloc is evaluated.
  • Approximate kernel G̃_λtop[w] = (κ²-w²)/κ²
    Eqs. 61-62 replace the expensive eigenfunction G_{λtop} by a quadratic approximation 'after numerically studying the shape... and observing good agreement'. This approximation is used in the Monte-Carlo loss.
  • Smoothing bandwidth z in App. E damped loss = 0.1
    Eq. 164 introduces H(κ,w,0.1) with z=0.1 to soften the loss edges; the value 0.1 is chosen by hand to suppress finite-size effects.
  • Phase-boundary fit in Fig. 6 = polynomial through four critical points
    The red transition line in Fig. 6 is 'obtained by fitting the four critical points highlighted Fig. 5'; the fitted curve defines κ_no-mem_loc.stab as a function of α.
assumptions (6)
  • domain assumption Validity of the replica method (including annealing over y0 and replica limit y0→0) for the quenched free energy of the connected-solutions ensemble.
    Sec. 3.1 and App. A use the replica method without rigorous justification; for SBP some replica results are proven (e.g., [30]), but the connected-chains construction is new.
  • ad hoc to paper No-memory Ansatz: each configuration x_{Pk} correlates only with its direct ancestor x_{P*_k} (Eqs. 29-30), yielding an ultrametric overlap structure.
    This is the central simplifying assumption. The paper proves it is globally unstable (Eq. 57: δφ/δQ > 0 for non-ancestor overlaps), so it is not a true saddle point of the free energy.
  • ad hoc to paper Chain arrangement with y_k=1 and convergence of the iteration to the Perron-Frobenius eigenvector λ_top (Eqs. 41-43).
    Sec. 3.2.1 sets all y_k=1 and requires k_f→∞ with k_f(1-m)→∞ to select the top eigenvector; this is a specific limit that defines the 'delocalized cluster'.
  • ad hoc to paper The sign of the perturbed local entropy δsloc(k,k') governs physical and algorithmic stability of no-memory paths (Eqs. 58-60).
    The paper postulates that δsloc<0 means stable and δsloc>0 means destabilized, and uses this to define κ_no-mem_loc.stab; this criterion is not derived from the free-energy saddle point and the text contains a sign-convention inconsistency.
  • ad hoc to paper The approximation G_{λtop}[w,m→1] ≈ (κ²-w²)/κ² is accurate enough for the Monte-Carlo loss (Eqs. 61-62).
    The approximation is justified by visual and numerical agreement, not by a bound; it is used in all simulations and degrades as α increases (Figs. 10-11).
  • standard math Perron-Frobenius theorem to justify non-degenerate top eigenvector of the linear operator (Eq. 41).
    Used in Sec. 3.2.1 to assert λ_top exists; this is standard mathematical background.
invented entities (1)
  • Delocalized no-memory connected cluster (star-shaped cluster) of SBP solutions independent evidence
    purpose: A manifold of non-isolated, mutually reachable solutions with a specific margin distribution P_edge(w); it is the object whose stability is claimed to control algorithmic accessibility in the SBP.
    The paper predicts the margin distribution P_edge(w) and the stability threshold κ_no-mem_loc.stab, and the modified Monte-Carlo simulations report solutions with the predicted margin distribution (Fig. 11) and decorrelation failure near the predicted threshold (Fig. 8). The evidence is partially in-sample because the algorithm uses the same effective loss, but the predicted margin shapes are non-trivial and not directly fitted.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems." pith.science (2026). https://pith.science/paper/JK7WNMMZ

@misc{pith2026250520954,
  author       = {Pith},
  title        = {Pith review of: Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JK7WNMMZ}},
  note         = {Machine review of arXiv:2505.20954}
}
abstract

We define and study a statistical mechanics ensemble that characterizes connected solutions in constraint satisfaction problems (CSPs). Built around a well-known local entropy bias, it allows us to better identify hardness transitions in problems where the energy landscape is dominated by isolated solutions. We apply this new device to the symmetric binary perceptron model (SBP), and study how its manifold of connected solutions behaves. We choose this particular problem because, while its typical solutions are isolated, it can be solved using local algorithms for a certain range of constraint density $\alpha$ and threshold $\kappa$. With this new ensemble, we unveil the presence of a cluster composed of delocalized connected solutions. In particular, we demonstrate its stability until a critical threshold $\kappa^{\rm no-mem}_{\rm loc.\, stab.}$ (dependent on $\alpha$). This transition appears as paths of solutions shatter, a phenomenon that more conventional statistical mechanics approaches fail to grasp. Finally, we compared our predictions to simulations. For this, we used a modified Monte-Carlo algorithm, designed specifically to target these delocalized solutions. We obtained, as predicted, that the algorithm finds solutions until $\kappa\approx\kappa^{\rm no-mem}_{\rm loc.\, stab.}$.

Figures

Figures reproduced from arXiv: 2505.20954 by the authors.

Figure 1
Figure 1. Drawing representing the local arrangement of solutions [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Drawing representing the connected structure introduced to evaluate [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Drawing representing a star-shaped cluster of the connected minima. To obtain this [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (13 more)
Figure 4
Figure 4. Figure 4: Representation of the perturbation in the no-memory cluster(s). While along a no [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: Plot indicating the sign of the perturbation [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]
Figure 6
Figure 6. Figure 6: Phase diagram compiling all the different transitions we showed in the SBP solutions [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: Plot representing the different transitions occurring when tuning [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 8
Figure 8. Figure 8: To determine the nature of the clustering below κ no−mem. loc. stab. , we plot in [PITH_FULL_IMAGE:figures/full_fig_p020_8.png]
Figure 8
Figure 8. Figure 8: Plot showing the decorrelation time tdec. as a function of κ. Each annealing setup (α = {0.3, 0.5, 0.75} and N = {1250, 2500, 500, 104}) is simulated five times. Each point in the plot indicates a decorrelation time obtained for a given simulation and a given round of …
Figure 9
Figure 9. Figure 9: Plot showing the ratio between the total number of rejected spin flips [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]
Figure 10
Figure 10. Figure 10: Plots of the correlation functions xt · x0/N (obtained for each round of annealing) as a function of the rescaled time γ(κ)t. Each color corresponds to different value for α, red is α = 0.3, blue is α = 0.5 and green is α = 0.75. The solid lines are averages over five…
Figure 11
Figure 11. Figure 11: Plots displaying the distribution of margins at the end of annealing procedures, for [PITH_FULL_IMAGE:figures/full_fig_p024_11.png]
Figure 12
Figure 12. Figure 12: Plots displaying the Franz-Parisi potential defined in Eq. (135) as a function of the [PITH_FULL_IMAGE:figures/full_fig_p037_12.png]
Figure 13
Figure 13. Figure 13: Schematic representation for the landscape of equilibrated systems ( [PITH_FULL_IMAGE:figures/full_fig_p038_13.png]
Figure 14
Figure 14. Figure 14: Plots displaying the behavior of the Franz-Parisi potential defined in Eq. (151) as a [PITH_FULL_IMAGE:figures/full_fig_p041_14.png]
Figure 15
Figure 15. Figure 15: Plot showing the decorrelation time tdec. as a function of κ for a single annealing procedure. We tested the annealing setups (α = {0.3, 0.5, 0.75} and N = {750, 1250, 2500, 5000}) with the new cost Gˆenerg λtop [·] -see Eq. (164)-. Each point in the plot indicates a …

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On the robustness of noisy solutions in non-convex neural networks

    cond-mat.dis-nn 2026-07 conditional novelty 6.0 of 10

    Finite training error extends the overlap-gap threshold in binary perceptrons so wide, algorithmically reachable basins persist and still generalize where zero-error solutions are hard.

Reference graph

Works this paper leans on

60 extracted references · 3 linked inside Pith · cited by 1 Pith paper

  1. [1]

    World Scientific Publishing Company, 1987

    Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro.Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987

    1987

  2. [2]

    L. F. Cugliandolo and J. Kurchan. Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model.Phys. Rev. Lett., 71:173–176, Jul 1993

    1993

  3. [3]

    Dynamical instantons and activated processes in mean-field glass models.SciPost Physics, 10:002, 1 2021

    Valentina Ros, Giulio Biroli, and Chiara Cammarota. Dynamical instantons and activated processes in mean-field glass models.SciPost Physics, 10:002, 1 2021

    2021

  4. [4]

    Gibbs states and the set of solutions of random constraint satisfaction problems.Proceedings of the National Academy of Sciences, 104(25):10318–10323, 2007

    Florent Krzakała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems.Proceedings of the National Academy of Sciences, 104(25):10318–10323, 2007

    2007

  5. [5]

    Fear and Trevor Price

    Karen K. Fear and Trevor Price. The adaptive surface in ecology.Oikos, 82:440, 9 1998

    1998

  6. [6]

    Hatton, Onofrio Mazzarisi, Ada Altieri, and Matteo Smerlak

    Ian A. Hatton, Onofrio Mazzarisi, Ada Altieri, and Matteo Smerlak. Diversity begets stability: Sublinear growth and competitive coexistence across ecosystems.Science, 383, 3 2024

    2024

  7. [7]

    Bärbel M. R. Stadler and Peter F. Stadler. Generalized topological spaces in evolutionary theory and combinatorial chemistry.Journal of Chemical Information and Computer Sciences, 42:577–585, 5 2002

    2002

  8. [8]

    Transition paths in potts-like energy landscapes: General properties and application to protein sequence models.Physical Review E, 108:024141, 8 2023

    Eugenio Mauri, Simona Cocco, and Rémi Monasson. Transition paths in potts-like energy landscapes: General properties and application to protein sequence models.Physical Review E, 108:024141, 8 2023

    2023

Show all 60 references
  1. [9]

    Adaptation in protein fitness landscapes is facilitated by indirect paths.eLife, 5:e16965, 7 2016

    Nicholas C Wu, Lei Dai, C Anders Olson, James O Lloyd-Smith, and Ren Sun. Adaptation in protein fitness landscapes is facilitated by indirect paths.eLife, 5:e16965, 7 2016

    2016

  2. [10]

    Disordered systems insights on computational hardness.Journal of Statistical Mechanics: Theory and Experiment, 2022:114015, 11 2022

    David Gamarnik, Cristopher Moore, and Lenka Zdeborová. Disordered systems insights on computational hardness.Journal of Statistical Mechanics: Theory and Experiment, 2022:114015, 11 2022

    2022

  3. [11]

    Analytic and algorithmic solution of random satisfiability problems.Science, 297(5582):812–815, 2002

    Marc Mézard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems.Science, 297(5582):812–815, 2002

    2002

  4. [12]

    Donoho, Arian Maleki, and Andrea Montanari

    David L. Donoho, Arian Maleki, and Andrea Montanari. Message Passing Algorithms for Compressed Sensing.Proceedings of the National Academy of Sciences, 106:18914–18919, 2009

    2009

  5. [13]

    The algorithmic hardness threshold for continuous random energy models.arXiv:1810.05129, 2018

    Louigi Addario-Berry and Pascal Maillard. The algorithmic hardness threshold for continuous random energy models.arXiv:1810.05129, 2018

    2018 arXiv

  6. [14]

    A rugged yet easily navigable fitness landscape of antibiotic resistance.bioRxiv, 2023

    Andrei Papkou, Lucia Garcia-Pastor, José Antonio Escudero, and Andreas Wagner. A rugged yet easily navigable fitness landscape of antibiotic resistance.bioRxiv, 2023

    2023

  7. [15]

    The structure of genotype-phenotype maps makes fitness landscapes navigable.Nature Ecology and Evolution, 6:1742–1752, 2022

    S F Greenbury, A A Louis, and S E Ahnert. The structure of genotype-phenotype maps makes fitness landscapes navigable.Nature Ecology and Evolution, 6:1742–1752, 2022

    2022

  8. [16]

    Macadangdang, Sara K

    Benjamin R. Macadangdang, Sara K. Makanani, and Jeff F. Miller. Accelerated evolution by diversity-generating retroelements.Annual Review of Microbiology, 76:389–411, 9 2022. 44

    2022

  9. [17]

    Infinite number of order parameters for spin-glasses.Physical Review Letters, 43(23):1754, 1979

    Giorgio Parisi. Infinite number of order parameters for spin-glasses.Physical Review Letters, 43(23):1754, 1979

    1979

  10. [18]

    Thouless, Philip W

    David J. Thouless, Philip W. Anderson, and Richard G. Palmer. Solution of’solvable model of a spin glass’.Philosophical Magazine, 35(3):593–601, 1977

    1977

  11. [19]

    S. Wright. The roles of mutation, inbreeding, crossbreeding and selection in evolution. Proceedings of the XI International Congress of Genetics, 8:209–222, 1932

    1932

  12. [20]

    Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 79:2554–2558, 4 1982

    J J Hopfield. Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 79:2554–2558, 4 1982

    1982

  13. [21]

    Optimal storage properties of neural network models

    Elizabeth Gardner and Bernard Derrida. Optimal storage properties of neural network models. Journal of Physics A: Mathematical and general, 21(1):271, 1988

    1988

  14. [22]

    The overlap gap property: A topological barrier to optimizing over random structures.Proceedings of the National Academy of Sciences, 118(41), 2021

    David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures.Proceedings of the National Academy of Sciences, 118(41), 2021

    2021

  15. [23]

    On the solution-space geometry of random constraint satisfaction problems.Random Structures & Algorithms, 38:251–268, 5 2011

    Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems.Random Structures & Algorithms, 38:251–268, 5 2011

    2011

  16. [24]

    Limits of local algorithms over sparse random graphs

    David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. InProceedings of the 5th conference on Innovations in theoretical computer science, pages 369–376. ACM, 2014

    2014

  17. [25]

    Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference.Journal of Molecular Evolution, 43:304–311, 9 1996

    Bruce Rannala and Ziheng Yang. Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference.Journal of Molecular Evolution, 43:304–311, 9 1996

    1996

  18. [26]

    Huelsenbeck, Fredrik Ronquist, Rasmus Nielsen, and Jonathan P

    John P. Huelsenbeck, Fredrik Ronquist, Rasmus Nielsen, and Jonathan P. Bollback. Bayesian inference of phylogeny and its impact on evolutionary biology.Science, 294:2310–2314, 12 2001

    2001

  19. [27]

    Malatesta, Gabriele Perugini, Fabrizio Pittorino, and Luca Saglietti

    Brandon Livio Annesi, Clarissa Lauditi, Carlo Lucibello, Enrico M. Malatesta, Gabriele Perugini, Fabrizio Pittorino, and Luca Saglietti. Star-shaped space of solutions of the spherical negative perceptron.Physical Review Letters, 131:227301, 11 2023

    2023

  20. [28]

    Storage capacity of memory networks with binary couplings

    Werner Krauth and Marc Mézard. Storage capacity of memory networks with binary couplings. Journal de Physique, 50(20):3057–3066, 1989

    1989

  21. [29]

    Clustering of solutions in the symmetric binary perceptron.Journal of Statistical Mechanics: Theory and Experiment, 2020(7):073303, 2020

    Carlo Baldassi, Riccardo Della Vecchia, Carlo Lucibello, and Riccardo Zecchina. Clustering of solutions in the symmetric binary perceptron.Journal of Statistical Mechanics: Theory and Experiment, 2020(7):073303, 2020

    2020

  22. [30]

    Storage capacity in symmetric binary perceptrons.Journal of Physics A: Mathematical and Theoretical, 52(29):294003, 2019

    Benjamin Aubin, Will Perkins, and Lenka Zdeborova. Storage capacity in symmetric binary perceptrons.Journal of Physics A: Mathematical and Theoretical, 52(29):294003, 2019

    2019

  23. [31]

    Learning by message passing in networks of discrete synapses.Physical review letters, 96(3):030201, 2006

    Alfredo Braunstein and Riccardo Zecchina. Learning by message passing in networks of discrete synapses.Physical review letters, 96(3):030201, 2006

    2006

  24. [32]

    On-line balancing of random inputs.Random Structures & Algorithms, 57(4):879–891, 2020

    Nikhil Bansal and Joel H Spencer. On-line balancing of random inputs.Random Structures & Algorithms, 57(4):879–891, 2020

    2020

  25. [33]

    On the atypical solutions of the symmetric binary perceptron.Journal of Physics A: Mathematical and Theoretical, 57(19):195202, 2024

    Damien Barbier, Ahmed El Alaoui, Florent Krzakala, and Lenka Zdeborová. On the atypical solutions of the symmetric binary perceptron.Journal of Physics A: Mathematical and Theoretical, 57(19):195202, 2024. 45

    2024

  26. [34]

    Capacity threshold for the ising perceptron

    Brice Huang. Capacity threshold for the ising perceptron. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1126–1136. IEEE, 10 2024

    2024

  27. [35]

    Recipes for metastable states in spin glasses.Journal de Physique I, 5(11):1401–1415, 1995

    Silvio Franz and Giorgio Parisi. Recipes for metastable states in spin glasses.Journal de Physique I, 5(11):1401–1415, 1995

    1995

  28. [36]

    Quasi-equilibrium in glassy dynamics: an algebraic view

    Silvio Franz and Giorgio Parisi. Quasi-equilibrium in glassy dynamics: an algebraic view. Journal of Statistical Mechanics: Theory and Experiment, 2013(02):P02003, feb 2013

    2013

  29. [37]

    Quasi equilibrium construction for the long time limit of glassy dynamics.Journal of Statistical Mechanics: Theory and Experiment, 2015(10):P10010, oct 2015

    Silvio Franz, Giorgio Parisi, Federico Ricci-Tersenghi, and Pierfrancesco Urbani. Quasi equilibrium construction for the long time limit of glassy dynamics.Journal of Statistical Mechanics: Theory and Experiment, 2015(10):P10010, oct 2015

    2015

  30. [38]

    How to escape atypical regions in the symmetric binary perceptron: A journey through connected-solutions states.SciPost Physics, 18:115, 3 2025

    Damien Barbier. How to escape atypical regions in the symmetric binary perceptron: A journey through connected-solutions states.SciPost Physics, 18:115, 3 2025

    2025

  31. [39]

    Krzakala, M

    F. Krzakala, M. Mézard, F. Sausset, Y. Sun, and L. Zdeborova. Statistical physics-based reconstruction in compressed sensing.arXiv:1109.4424, 2011

    2011 arXiv

  32. [40]

    Alain Barrat, Silvio Franz, and Giorgio Parisi. Temperature evolution and bifurcations of metastable states in mean-field spin glasses, with connections with structural glasses.Journal of Physics A: Mathematical and General, 30:5593–5612, 8 1997

    1997

  33. [41]

    Barbier, C

    D. Barbier, C. Lucibello, L. Saglietti, F. Krzakala, and L. Zdeborová. Compressed sensing with l0-norm: statistical physics analysis & algorithms for signal recovery. In2023 IEEE Information Theory Workshop (ITW), pages 323–328. IEEE, 4 2023

    2023

  34. [42]

    Marvels and pitfalls of the langevin algorithm in noisy high-dimensional inference.Physical Review X, 10:011057, 3 2020

    Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Marvels and pitfalls of the langevin algorithm in noisy high-dimensional inference.Physical Review X, 10:011057, 3 2020

    2020

  35. [43]

    Local entropy as a measure for sampling solutions in constraint satisfaction problems.Journal of Statistical Mechanics: Theory and Experiment, 2016(2):023301, 2016

    Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Local entropy as a measure for sampling solutions in constraint satisfaction problems.Journal of Statistical Mechanics: Theory and Experiment, 2016(2):023301, 2016

    2016

  36. [44]

    Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses.Physical review letters, 115(12):128101, 2015

    Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses.Physical review letters, 115(12):128101, 2015

    2015

  37. [45]

    Unveiling the structure of wide flat minima in neural networks.Physical Review Letters, 127(27):278301, 2021

    Carlo Baldassi, Clarissa Lauditi, Enrico M Malatesta, Gabriele Perugini, and Riccardo Zecchina. Unveiling the structure of wide flat minima in neural networks.Physical Review Letters, 127(27):278301, 2021

    2021

  38. [46]

    Wide flat minima and optimal generalization in classifying high-dimensional gaussian mixtures.Journal of Statistical Mechanics: Theory and Experiment, 2020:124012, 12 2020

    Carlo Baldassi, Enrico M Malatesta, Matteo Negri, and Riccardo Zecchina. Wide flat minima and optimal generalization in classifying high-dimensional gaussian mixtures.Journal of Statistical Mechanics: Theory and Experiment, 2020:124012, 12 2020

    2020

  39. [47]

    Clustering of solutions in the symmetric binary perceptron.Journal of Statistical Mechanics: Theory and Experiment, 2020:073303, 7 2020

    Carlo Baldassi, Riccardo Della Vecchia, Carlo Lucibello, and Riccardo Zecchina. Clustering of solutions in the symmetric binary perceptron.Journal of Statistical Mechanics: Theory and Experiment, 2020:073303, 7 2020

    2020

  40. [48]

    Shaping the learning landscape in neural networks around wide flat minima.Proceedings of the National Academy of Sciences, 117:161–170, 1 2020

    Carlo Baldassi, Fabrizio Pittorino, and Riccardo Zecchina. Shaping the learning landscape in neural networks around wide flat minima.Proceedings of the National Academy of Sciences, 117:161–170, 1 2020. 46

    2020

  41. [49]

    Carlo Baldassi, Christian Borgs, Jennifer T Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes.Proceedings of the ...

    2016

  42. [50]

    Efficiency of quantum vs

    Carlo Baldassi and Riccardo Zecchina. Efficiency of quantum vs. classical annealing in nonconvex learning problems.Proceedings of the National Academy of Sciences, 115:1457– 1462, 2 2018

    2018

  43. [51]

    Frozen glass phase in the multi-index matching problem.Physical review letters, 93(21):217205, 2004

    OC Martin and M Mézard. Frozen glass phase in the multi-index matching problem.Physical review letters, 93(21):217205, 2004

    2004

  44. [52]

    Locked constraint satisfaction problems.Physical review letters, 101(7):078702, 2008

    Lenka Zdeborová and Marc Mézard. Locked constraint satisfaction problems.Physical review letters, 101(7):078702, 2008

    2008

  45. [53]

    Entropy landscape of solutions in the binary perceptron problem.Journal of Physics A: Mathematical and Theoretical, 46(37):375002, 2013

    Haiping Huang, KY Michael Wong, and Yoshiyuki Kabashima. Entropy landscape of solutions in the binary perceptron problem.Journal of Physics A: Mathematical and Theoretical, 46(37):375002, 2013

    2013

  46. [54]

    Origin of the computational hardness for learning with binary synapses.Physical Review E, 90(5):052813, 2014

    Haiping Huang and Yoshiyuki Kabashima. Origin of the computational hardness for learning with binary synapses.Physical Review E, 90(5):052813, 2014

    2014

  47. [55]

    The asymptotics of the clustering transition for random constraint satisfaction problems.Journal of Statistical Physics, 181, 12 2020

    Louise Budzynski and Guilhem Semerjian. The asymptotics of the clustering transition for random constraint satisfaction problems.Journal of Statistical Physics, 181, 12 2020

    2020

  48. [56]

    J. M. Kosterlitz, D. J. Thouless, and Raymund C. Jones. Spherical model of a spin-glass. Physical Review Letters, 36:1217–1220, 5 1976

    1976

  49. [57]

    Diversity-generating retroelements.Current Opinion in Microbiology, 10:388–395, 8 2007

    Bob Medhekar and Jeff F Miller. Diversity-generating retroelements.Current Opinion in Microbiology, 10:388–395, 8 2007

    2007

  50. [58]

    Harnessing diversity generating retroelements for in vivo targeted hyper-mutagenesis

    Raphael Laurenceau, Paul Rochette, Elena Lopez-Rodriguez, Catherine Fan, Amandine Maire, Paul Vittot, Karol Melissa Cerdas-Mejias, Auguste Bouvier, Thea Chrysostomou, and David Bikard. Harnessing diversity generating retroelements for in vivo targeted hyper-mutagenesis. bioRxiv, 2025

    2025

  51. [59]

    Marc Potters and Jean-Philippe Bouchaud.A First Course in Random Matrix Theory: for Physicists, Engineers and Data Scientists. 11 2020

    2020

  52. [60]

    Algorithms and barriers in the symmetric binary perceptron model.arXiv preprint arXiv:2203.15667, 2022

    David Gamarnik, Eren C Kızıldağ, Will Perkins, and Changji Xu. Algorithms and barriers in the symmetric binary perceptron model.arXiv preprint arXiv:2203.15667, 2022. 47

    2022 arXiv

Pith tools

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