{"id":"246867a8-81d6-44fc-8b41-fd93bafbe88d","arxiv_id":"2501.07638","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":9,"one_line_summary":"Population annealing beats simulated annealing on diluted Ising models near an intermediate-connectivity hardness peak, and adaptive temperature schedules remove the need to tune the final temperature.","lead":"This paper benchmarks population annealing against simulated annealing on diluted Sherrington-Kirkpatrick Ising models. It finds an easy-hard-easy transition in problem hardness as graph connectivity varies, with population annealing winning near the hardness peak.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The easy-hard-easy transition is located using PA-internal metrics (ρ_t, R_eff) that are not independently validated as hardness proxies for diluted SK; a four-point TTS comparison is too coarse to confirm the peak, and the three-point extrapolation of Eq. (12) does not test the scaling law.","rationale":"The reader's weakest assumption—that ρ_t and R_eff faithfully track true problem hardness—is indeed the most load-bearing point in the paper. The entire easy-hard-easy transition and its mechanistic explanation via clusterization and connectivity rest on these PA-internal metrics. The two metrics are derived from the same PA family-size statistics, so their mutual agreement is not independent confirmation. The only direct efficiency comparison (Section IV A) covers four Np values for N=200 and uses heuristic success probabilities; it is too coarse to validate the precise peak location obtained from ρ_t. Furthermore, the asymptotic peak extrapolation via Eq. (12) fits three parameters to three data points, so the quoted 1.77±0.03 has no statistical degrees of freedom; a fourth size is needed to test the assumed power-law form. These issues do not by themselves invalidate the qualitative easy-hard-easy trend, and the N=200 TTS data do show increased difficulty near Np≈2, consistent with the proxy. I therefore keep the reader's CONDITIONAL verdict: the central claim is plausible but requires independent hardness validation. A fine-grained TTS/exact-solver scan across Np would settle whether the PA-metric peak coincides with true algorithmic difficulty. Since the conditional verdict already requests this validation, no change is needed.","tokens_in":12709,"tokens_out":8454,"duration_ms":82342,"concrete_test":"Perform a single systematic scan for N=200 (and, if feasible, N=300) over a fine grid of Np (e.g., 1.0 to 2.5 in steps of 0.1) with at least 1000 instances per point. For each point, measure (i) the mean SA time-to-solution with hyperparameters optimized per Np as in Section IV A, and (ii) the mean exact-solver time or branch-and-bound node count using Gurobi for smaller sizes (e.g., N=100–150) where exact solution is feasible. Compare the location of the TTS/exact-solver maximum with the location of the ρ_t and R_eff maxima from PA using the same N and instances. If the independently measured hardness peak differs by more than the quoted error bars (approximately 0.2 in Np) or no peak is found, then the PA-based easy-hard-easy transition is not a reliable proxy for intrinsic problem hardness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central easy-hard-easy transition is characterized exclusively through PA-internal quantities (ρ_t and R_eff, Section III), and both are computed from the same family-size statistics of a single PA run, so their co-peaking is not independent confirmation. The authors cite prior correlations of ρ_t with time-to-solution and autocorrelation (Refs. [23,24,35]), but no calibration is established for the diluted SK family studied here. The only direct efficiency check in the paper is the N=200 study of Section IV A, which samples just four Np values (1.3, 2, 5, 200) and uses heuristic success probabilities rather than an exact solver; it cannot localize the TTS maximum with the precision claimed for the ρ_t peak (extrapolated Np≈1.7–1.8). In addition, the finite-size extrapolation of the peak position uses Eq. (12) with three free parameters fitted to exactly three system sizes (N=300, 400, 500), so the quoted asymptotic value (1.77±0.03) is not a genuine test of the scaling law. If ρ_t and R_eff are not faithful hardness proxies in this model family—for example, if they saturate at intermediate connectivity for reasons specific to PA's resampling dynamics—then the easy-hard-easy transition and its clusterization/connectivity explanation would be artifacts of the algorithm rather than properties of the problem instances.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the diluted Sherrington-Kirkpatrick Ising model using population annealing (PA) and characterizes problem hardness through two PA-derived quantities, the mean square family size ρ_t and the effective population size R_eff. From these, the authors report an easy-hard-easy transition in hardness as the average degree Np varies, with the hardness peak extrapolating to Np≈1.77 (ρ_t) and Np≈1.68 (R_eff), and they associate this behavior with the clusterization and connectivity of the underlying Erdős-Rényi graphs. The paper then compares PA with simulated annealing (SA) on N=200 instances at Np=1.3, 2, 5, and 200, finding that PA outperforms SA near the claimed hardness peak. Finally, an adaptive inverse-temperature schedule for PA is shown to be more efficient and more robust to final-temperature miscalibration than a linear schedule.","tokens_in":13036,"tokens_out":5676,"duration_ms":59362,"significance":"If the central claim holds, the paper identifies a nonmonotonic hardness landscape in a physically and combinatorially relevant family of Ising models and provides practical guidance on when population annealing is preferable to simulated annealing. The computational study is carefully set up: it uses 6000 instances for the hardness data, optimizes SA hyperparameters to avoid straw-man comparisons, and uses multiple metrics (ρ_t, R_eff, success probability, approximation ratio). The adaptive-schedule comparison is a useful practical contribution. However, the central hardness transition is defined through PA-internal metrics rather than an external measure of optimization difficulty, and the direct efficiency benchmark is too sparse to confirm the precise location of the peak. These issues are fixable but currently leave the main claim only partially supported.","major_comments":[{"comment":"The easy-hard-easy transition is characterized exclusively by the PA-internal quantities ρ_t and R_eff, both computed from the family-size statistics of a single PA run, so their co-peaking is not an independent confirmation of a problem-hardness transition. The correlations with time-to-solution and autocorrelation cited in Refs. [23,24,35] were established for other model families, and no calibration is provided for the diluted SK model studied here. The central claim would be substantially strengthened by validating ρ_t (or R_eff) against an independent hardness measure, such as the SA time-to-solution or integrated autocorrelation time, on the same instances over a fine range of Np.","section":"Section III, Figs. 2-4"},{"comment":"The finite-size extrapolation of the peak position uses exactly three system sizes (N=300, 400, 500) for a three-parameter fit (asymptotic value, amplitude, and exponent), so the quoted power-law form is not tested and the bootstrap errors do not include the uncertainty in the functional form. The asymptotic peak values 1.77±0.03 and 1.68±0.01 should be presented as rough estimates, and the statement that the dependence could indicate critical behavior is premature without additional sizes.","section":"Section III, Eq. (12) and Fig. 4"},{"comment":"The direct efficiency comparison samples only four values of Np (1.3, 2, 5, 200), which is too coarse to locate the time-to-solution maximum or to verify that the efficiency peak coincides with the ρ_t peak near Np≈1.7-1.8. In addition, for Np=200 the reference ground states are obtained from PA itself rather than from an exact solver, which introduces a possible circularity in the benchmark. Additional Np values around the claimed peak and an independent verification of the reference energies are needed to support the conclusion that PA outperforms SA specifically near the hardness peak.","section":"Section IV A, Figs. 8-9"}],"minor_comments":[{"comment":"The clusterized regular-graph model shows a hardness peak at degree D=3, but no quantitative link is established between D and the mean degree Np of the Erdős-Rényi graphs; the diluted SK peak occurs near Np≈1.7-1.8, not at D=3. A mapping or a discussion of why D=3 corresponds to the ER peak would make the clusterization/connectivity association more convincing.","section":"Section III, Fig. 6"},{"comment":"The culling fraction is introduced as ε in the text but appears as ϵ in Eq. (7); the notation should be unified.","section":"Section II C, Eq. (7)"},{"comment":"The statement that SA and PA reach similar efficiencies in the SK limit depends on the PA sweep count: PA with NS=1 is similar to SA, but PA with NS=5 or 10 is noticeably worse, so the conclusion should be qualified as depending on PA hyperparameters.","section":"Section IV A, Fig. 9"},{"comment":"The quality of the log-inverse Gaussian fits is not quantified; the claim of perfect agreement would be supported by reporting goodness-of-fit statistics or confidence bands.","section":"Section III, Table I and Fig. 7"},{"comment":"The manuscript states that data are available upon request but does not provide a repository; for a computational study, releasing instance generation code and data would improve reproducibility.","section":"Overall"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the circularity between the PA-based hardness measure and PA's own success: the central transition is located with ρ_t and R_eff, while the only direct efficiency check uses too few Np values and PA-generated references at one point. I would not reject the paper, because the qualitative easy-hard-easy phenomenon is plausible and the adaptive-schedule results are useful, but the load-bearing claims need additional validation before publication. The paper is within scope for a statistical mechanics / computational physics journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper is a solid empirical benchmark, not a breakthrough. The easy-hard-easy transition in diluted SK was already in Perera et al. (Ref. [35]), and the authors say so. What they add is a PA-focused characterization via family-size metrics, a mechanistic story built from clusterized regular graphs, and a fair PA-vs-SA efficiency comparison with optimized SA hyperparameters. That last part is the strongest contribution: they use Gurobi for three of the four Np values, report both success probability and approximation ratio, and show PA clearly wins at Np=2, which is near their hardness peak.\n\nThe simulation design is careful: 6000 instances for each hardness data point, bootstrap errors on the peak fits, and explicit attention to thermalization via R>100ρt. The mechanism study with clusterized regular graphs in Fig. 6 is a nice controlled probe of the cluster-size and connectivity effects. The adaptive schedule robustness result is useful for practitioners.\n\nSoft spots, in proportion. The central hardness measure is ρ_t and R_eff, both computed from a single PA run. The paper argues these correlate with TTS via prior work, but there is no independent calibration for diluted SK. That matters because the transition peak is located with these metrics. The direct TTS check at N=200 uses only four Np values (1.3, 2, 5, 200), so it brackets the peak but does not localize it. This is a real limitation, though the paper does not overclaim precision there. The finite-size extrapolation of the peak via Eq. (12) fits three parameters to three sizes; that is not a test of the scaling law. The quoted asymptotic value Np≈1.77 is a rough estimate, and the authors essentially say so. Also, the Np=200 ground states come from PA rather than an exact solver; they checked no lower energy appeared, which is reasonable but not a proof. Finally, no code or data are released, only \"available upon request.\"\n\nNone of this sinks the paper. The existence of a hardness peak near Np≈2 is visible in the raw data, and the direct efficiency comparison gives independent support that something hard is happening there. The paper is honest, well-parameterized, and does not oversell its mechanistic explanation. It deserves a serious referee.\n\nMy recommendation: send it to peer review. Ask the authors to release code and data, and to either calibrate ρ_t against TTS for a few sizes or soften the claim that it faithfully tracks problem hardness. The three-point fit should be presented as an extrapolation, not a verification.","headline":"A careful empirical benchmark showing PA beats SA near a hardness peak in diluted SK, but the hardness metrics are PA-internal and the finite-size scaling is thinner than it looks.","tokens_in":13598,"tokens_out":2604,"would_cite":true,"duration_ms":27592,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Finding ground states of diluted Sherrington–Kirkpatrick Ising models is hardest when spins have about 1.8 interactions on average, and population annealing is the more efficient heuristic in that regime.","keywords":["population annealing","simulated annealing","diluted Sherrington-Kirkpatrick model","Erdős–Rényi graphs","spin glass ground states","easy-hard-easy transition","problem hardness","adaptive temperature schedule"],"falsifier":"Compute an exact time-to-solution for simulated annealing with optimized hyperparameters on the same class of diluted SK instances at larger sizes (e.g., $N=400$ or beyond), using an exact solver to certify ground states, and test whether the TTS peak occurs at $Np \\approx 1.7$–$1.8$ as the $N\\to\\infty$ extrapolation predicts; if the TTS peak is absent, displaced, or disappears when the PA diagnostics are replaced by direct success-probability measurements, the claimed transition is an artifact of the $\\rho_t$/$R_{\\text{eff}}$ proxies.","tokens_in":12461,"feed_emoji":"🧲","tokens_out":10021,"duration_ms":85032,"temperature":0.7,"pith_summary":"The paper studies the diluted Sherrington–Kirkpatrick Ising model, a spin glass whose spin couplings sit on random Erdős–Rényi graphs of tunable average degree $Np$, from sparse graphs up to the fully connected SK limit. It claims to find an easy-hard-easy transition in how hard it is to locate ground states: hardness rises as the graph becomes more dilute, peaks at an extrapolated $Np \\approx 1.8$, and then falls again. The peak is explained by the competition between clusterization and connectivity in the underlying graph: small isolated clusters are easy, a merging giant component is hardest, and higher connectivity inside that component makes the problem easy again. Near the peak, population annealing finds ground states with substantially less computational work than an optimally tuned simulated annealing, while both perform similarly in the easy limits. The paper further claims that an adaptive inverse-temperature schedule for population annealing is more robust against miscalibrated final temperatures and slightly more efficient near the peak than a linear schedule.","feed_headline":"Spin-glass hardness peaks at about 1.8 couplings per spin.","feed_subtitle":"Population annealing beats simulated annealing right at the peak, and its adaptive schedule removes a key tuning knob.","key_machinery":"The argument is carried by two diagnostics extracted from a single population-annealing run: the mean square family size $\\rho_t = \\lim_{R\\to\\infty} R \\sum_i n_i^2$ and the effective population size $R_{\\text{eff}} = \\sigma^2(E)/\\sigma^2_{\\bar{E}}(E)$, computed from jackknife variance estimates. Both measure how aggressively the resampling step prunes the population; large $\\rho_t$ and small $R_{\\text{eff}}$ indicate a rugged free-energy landscape and hence a hard instance. These quantities locate the hardness peak as a function of $Np$ and are compared against the giant-component size of the Erdős–Rényi graph. The mechanistic claim is then tested on clusterized regular graphs, in which clusters of size $S$ and degree $D$ are varied independently, isolating clusterization (size) from connectivity (degree) as the two competing controls of hardness.","core_discovery":"The central discovery is that problem hardness in the diluted Sherrington–Kirkpatrick Ising model, measured through the population-annealing diagnostics $\\rho_t$ (mean square family size) and $R_{\\text{eff}}$ (effective population size), is not monotone in the graph connectivity $p$. Instead, hardness follows an easy-hard-easy curve as a function of $Np$, with a maximum at $Np \\simeq 1.7$–$1.8$ in the infinite-size limit, extrapolated from sizes $N=300,400,500$. The authors attribute this transition to the structure of the underlying Erdős–Rényi graphs: at low $Np$ the graph breaks into small independent clusters that are individually easy to solve; as $Np$ grows past the percolation threshold these clusters merge into a giant component, producing weakly coupled clusters that trap single-spin-flip algorithms in local minima; at larger $Np$, the higher internal connectivity removes those traps and hardness drops. This mechanism is tested directly on clusterized regular graphs, where hardness increases with cluster size and peaks at degree $D=3$ before declining. In efficiency benchmarks on $N=200$ instances, population annealing outperforms an optimally calibrated simulated annealing near the hardness peak (e.g., at $Np=2$) for both success probability and approximation ratio, while achieving similar efficiency at the $p=1$ SK limit and at the dilute $Np=1.3$ side.","pith_inferences":["If the $\\rho_t$–TTS correlation holds beyond the sizes tested, a single short PA run could serve as a cheap hardness predictor, letting a practitioner allocate more compute to the hard tail of instances flagged by high $\\rho_t$.","The location of the hardness peak just above the Erdős–Rényi percolation threshold ($Np=1$) suggests that other NP-hard problems on sparse random graphs (e.g., Max-Cut or random $k$-SAT) may exhibit a similar easy-hard-easy pattern tuned by a percolation-like connectivity parameter; that is a testable extension.","The finite-size scaling $Np_{\\max}(N) = (Np)_{\\max,\\infty} + A/N^\\nu$ with $\\nu \\approx 0.8$ raises the question, not settled in the paper, of whether the hardness peak is a genuine critical phenomenon or a finite-size crossover; resolving this would require larger sizes and a scaling collapse."],"forward_implications":["Near the hardness peak at $Np\\approx 2$, population annealing requires less computational work than simulated annealing to reach ground states, so PA is the better heuristic for intermediate-connectivity spin-glass problems.","The extrapolated peak at $Np \\approx 1.7$–$1.8$ gives benchmark designers a target regime where random spin-glass instances are hardest, useful for stress-testing new optimization algorithms.","The log-inverse Gaussian fit to the $\\rho_t$ distribution means that near the peak the instance-to-instance difficulty spread widens, so budgets adequate for the average instance will fail on a non-negligible fraction of hard instances.","The adaptive temperature schedule removes the need to calibrate the final inverse temperature as long as it is high enough, making population annealing effectively hyperparameter-free in this respect.","PA's advantage over SA disappears at both easy limits ($p=1$ and very dilute $Np$), consistent with the resampling step mattering only when the free-energy landscape is rugged though not fully connected."],"supporting_citations":[{"why":"Defines the diluted SK model on Erdős–Rényi graphs whose hardness this paper maps.","marker":"[22]"},{"why":"Introduced population annealing as implemented here.","marker":"[13]"},{"why":"Earlier PA-versus-SA efficiency study on 3D spin glasses that this work extends to diluted SK.","marker":"[16]"},{"why":"Defined the mean square family size and the culling-fraction adaptive schedule used as the hardness metric and benchmark.","marker":"[24]"},{"why":"Observed easy-hard-easy behavior and connected PA metrics to time-to-solution, the prior result being extended.","marker":"[35]"},{"why":"Introduced the entropic family size and established its link to thermalization, supporting the use of $\\rho_t$ as a hardness proxy.","marker":"[23]"},{"why":"Supplied the definition of effective population size $R_{\\text{eff}}$ from the variance ratio.","marker":"[40]"}],"fun_headline_variants":["Easy-hard-easy transition: hardness peaks at Np~1.8","Population Annealing outperforms at spin-glass difficulty peak","Dilute Ising models: hardest at 1.8 couplings, PA wins","Adaptive schedule boosts PA near hardness peak","At Np~1.8, spin-glass hardness peaks; PA beats SA"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the population-annealing diagnostics $\\rho_t$ and $R_{\\text{eff}}$ faithfully measure the algorithmic difficulty of finding ground states for this model family; if they do not correlate with true time-to-solution, the easy-hard-easy transition and its peak position could be artifacts of the resampling dynamics rather than intrinsic problem hardness.","fun_headline_variants_meta":{"raw":{"variants":["Easy-hard-easy transition: hardness peaks at Np~1.8","Population Annealing outperforms at spin-glass difficulty peak","Dilute Ising models: hardest at 1.8 couplings, PA wins","Adaptive schedule boosts PA near hardness peak","At Np~1.8, spin-glass hardness peaks; PA beats SA"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000898,"raw_usage":{"total_tokens":3903,"prompt_tokens":1014,"completion_tokens":2889,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":630,"completion_tokens_details":{"reasoning_tokens":2797}},"tokens_in":630,"tokens_out":2889,"duration_ms":23595,"temperature":1.0,"reasoning_tokens":2797,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:38:17.510455+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute an exact time-to-solution for simulated annealing with optimized hyperparameters on the same class of diluted SK instances at larger sizes (e.g., $N=400$ or beyond), using an exact solver to certify ground states, and test whether the TTS peak occurs at $Np \\approx 1.7$–$1.8$ as the $N\\to\\infty$ extrapolation predicts; if the TTS peak is absent, displaced, or disappears when the PA diagnostics are replaced by direct success-probability measurements, the claimed transition is an artifact of the $\\rho_t$/$R_{\\text{eff}}$ proxies.","supporting_citations":[{"cited_title":"Machta, Physical Review E 82, 026704 (2010)","cited_arxiv_id":null,"evidence_quote":"Introduced population annealing as implemented here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier PA-versus-SA efficiency study on 3D spin glasses that this work extends to diluted SK."},{"cited_title":"Amey and J","cited_arxiv_id":null,"evidence_quote":"Defined the mean square family size and the culling-fraction adaptive schedule used as the hardness metric and benchmark."},{"cited_title":"Perera, F","cited_arxiv_id":null,"evidence_quote":"Observed easy-hard-easy behavior and connected PA metrics to time-to-solution, the prior result being extended."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced the entropic family size and established its link to thermalization, supporting the use of $\\rho_t$ as a hardness proxy."},{"cited_title":"Weigel, L","cited_arxiv_id":null,"evidence_quote":"Supplied the definition of effective population size $R_{\\text{eff}}$ from the variance ratio."}],"review_version":1}