{"id":"e75d13d6-fd0b-4189-804a-af30136a9861","arxiv_id":"2507.09247","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The authors propose a CLuP-SK barrier-descent algorithm and report it achieves approximately 0.76 of the SK ground state free energy for n around 2000 to 8000, approaching the theoretical Parisi limit of about 0.763.","lead":"A new CLuP-SK algorithm, a simple barrier-based gradient descent, reportedly finds near-optimal spin configurations for the Sherrington-Kirkpatrick spin glass, achieving a ground state free energy near 0.76 for systems of a few thousand spins, close to the known Parisi value of about 0.763. If reliable, this would make a canonical hard optimization problem practically easy for typical random instances.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central claim hinges on the unproven surrogate-landscape assumption in Eq. (61): the no-local-optimima conclusion is established only for a one-dimensional replacement, not for the high-dimensional barrier objective on which gradient descent actually runs.","rationale":"The reader's weakest_assumption identifies the same load-bearing concern: Eq. (61) replaces the actual random objective by the deterministic ξ(rx) and then uses the one-dimensional surrogate f_b(rx) to conclude that the loss landscape is free of problematic local optima. I agree that this is the highest-risk premise. The paper's numerical agreement between simulated CLuP-SK dynamics and the surrogate-based theoretical curves in Figures 5-11 is genuine evidence that the surrogate works on the tested instances and dimensions, and the convergence trend in Figures 12-13 is encouraging. However, those simulations cover n up to a few thousand, report no error bars or across-instance variability, and do not prove that gradient descent from a generic initialization cannot be trapped in a spurious high-dimensional local minimum. The section's own caveats—'approximate landscape characterization' and the warning that numerical evaluations 'need to be taken with a bit of additional caution'—are limitation statements that should carry weight in the verdict. Since the central empirical claim is plausible and not demonstrably false, and the identified gap is addressable by running multistart experiments and comparing actual high-dimensional minima with the surrogate, the appropriate verdict remains CONDITIONAL as the reader concluded. My stress-test therefore does not change the reader's verdict.","tokens_in":25911,"tokens_out":14366,"duration_ms":174613,"concrete_test":"Fix n=2000 (and, if computationally feasible, n=8000) and generate 50 independent SK instances. For each instance, run the exact CLuP-SK procedure of Eq. (55) with κ=0.155, t0x(0)=0.0005, and c(t)=1.1 from 100 random feasible starting points x(0), recording the final ξ(1) achieved. If the across-initialization distribution is bimodal, or if the fifth percentile falls below approximately 0.75 while the median is near 0.76, then the surrogate landscape is not faithful and the 'typically easy' claim fails. Additionally, for a fixed t0x, compute the actual minimum of ar f_{b,x}(x;t0x) over a dense grid of rx values using randomized multistart descent and compare it with f_b(rx) from Eq. (61); any substantial mismatch at some rx would directly falsify the concentration/replacement step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.2.1 replaces the random quadratic inside the barrier objective with the deterministic asymptotic maximum ξ(rx) over X(rx), producing the one-dimensional profile f_b(rx) in Eq. (61). This replacement is load-bearing in two ways. First, it assumes that the random quadratic form concentrates uniformly over X(rx) to ξ(rx), although the minimization of -log(...) is governed by the maximum of that random quadratic and finite-n fluctuations are not analyzed. Second, even if Eq. (61) is accepted, it characterizes only the one-dimensional profile f_b(rx), not the high-dimensional objective ar f_{b,x}(x;t0x) that the CLuP-SK gradient descent actually minimizes. The log-barrier term -1/n Σ log(1 - n x_i^2) and the random quadratic can create stationary points that are invisible in the rx-projection, so a benign one-dimensional profile does not rule out spurious local minima in high dimension. The paper itself labels Section 4.2.1 an 'approximate landscape characterization,' cautions in Section 4.2.2 that numerical results 'need to be taken with a bit of additional caution,' and in Section 4.2.1 states that 'whether or not other intrinsic features beyond the loss landscape play much of an additional role remains to be seen.' The abstract's conclusion that computing SK near-ground-state free energy is 'typically easy' is therefore stronger than the evidence supplied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes CLuP-SK, a barrier-descent (\"Controlled Loosening-up\") algorithm for the Sherrington-Kirkpatrick ground-state problem, and reports that for n on the order of a few thousand it achieves ground-state free energy values around 0.75–0.76, close to the Parisi value 0.763. To analyze the algorithm, the author introduces a family of CLuP-SK random models and uses fully lifted random duality theory (fl RDT), from the author's earlier works, to compute the asymptotic ground-state energy ξ(r_x) as a function of the radius r_x. The paper then studies a one-dimensional barrier profile f_b(r_x), claims it has no non-global local optima, simulates the CLuP-SK dynamics for n = 200, 1000, 2000, 4000, 8000, and reports excellent agreement with the theoretical predictions. It also reports overlap distributions and an ultrametric Gram matrix for near-optimal configurations.","tokens_in":26224,"tokens_out":7649,"duration_ms":95396,"significance":"If the central claims were fully supported, this would be a practically significant result: a simple barrier method would approach the SK ground-state energy without requiring precomputed Parisi parameters, in contrast to IAMP-type methods. The reported numerical agreement between the simulated dynamics and the theoretical curves (Figures 5–13) is visually convincing, and the emergence of ultrametric structure in Figure 15 is striking. The paper also makes a useful conceptual connection between a CLuP-type algorithm and a random-model analysis. However, the significance is conditional: the theoretical machinery is imported from the author's own arXiv preprints without proofs, the landscape analysis is carried out for a one-dimensional surrogate rather than the true high-dimensional objective, and the manuscript contains no concentration result for the key replacement of a random quadratic form by its asymptotic maximum. These gaps are load-bearing for the claim that computing the SK near-ground-state free energy is \"typically easy.\"","major_comments":[{"comment":"The theoretical predictions rest on Theorem 1, which is quoted from the author's own preprint [98] with the proof deferred to \"line-by-line derivations\" in [94,97,98], and on Theorem 2, whose proof states that it \"follows automatically.\" The manuscript does not state or verify the \"complete sfl RDT frame\" assumptions needed for the exact equality in Eq. (21). Since Eqs. (35)–(36) and Table 1 all depend on this equality, the theory is not self-contained and cannot be independently checked from the manuscript. Moreover, because the same unproven framework is used both to predict and to interpret the simulations, the reported \"excellent agreement\" does not independently validate either the theory or the algorithm. I recommend either including a complete proof, or precisely stating the conditions under which Eq. (21) holds and pointing to accessible peer-reviewed versions of [94,97,98].","section":"Section 3, Theorems 1 and 2"},{"comment":"The replacement of the random quadratic form x^T G x by the deterministic quantity ξ(r_x) is not justified. The barrier objective in Eq. (59) depends, for a fixed instance G, on the maximum of the random quadratic form over X(r_x), whereas ξ(r_x) is defined in Eq. (14) as a thermodynamic-limit expectation of that maximum. The paper provides no concentration bound showing that sup_{x∈X(r_x)} x^T G x / √(2n) is close to ξ(r_x) with high probability, nor any finite-n fluctuation estimate. Because this substitution is the basis for the one-dimensional profile f_b(r_x) in Eq. (61) and for the no-local-optima conclusion, the absence of a concentration argument is a load-bearing gap.","section":"Section 4.2.1, Eq. (61)"},{"comment":"The no-local-optima claim is established only for the one-dimensional profile f_b(r_x), not for the high-dimensional objectives in Eqs. (56) and (64) on which gradient descent actually runs. A benign one-dimensional projection does not rule out spurious stationary points in directions orthogonal to r_x, and the paper itself acknowledges this by noting that \"whether or not other intrinsic features beyond the loss landscape play much of an additional role remains to be seen\" and that the numerical results in Section 4.2.2 \"need to be taken with a bit of additional caution.\" These caveats are in tension with the abstract's conclusion that computing the SK near-ground-state free energy is \"typically easy.\" Either the high-dimensional landscape needs to be characterized, or the strength of the concluding claim should be reduced to match the evidence.","section":"Section 4.2.1 and 4.2.2"},{"comment":"The algorithm as specified in Eq. (55)–(56) lacks a step-size rule, a stopping criterion, and any complexity estimate; the text says only that the parameters κ, t_0x, and c(t) are \"fairly flexible.\" For the central claim that the problem is \"typically easy,\" a statement about the number of iterations or total floating-point operations is needed, or at least a clear reformulation of the claim as a purely empirical finite-n observation. As written, the reader cannot tell whether the reported n ≤ 8000 runs are representative or whether the procedure is guaranteed to terminate in polynomial time.","section":"Section 4.1, Eq. (55)"}],"minor_comments":[{"comment":"There are typos such as \"agrement\" and inconsistent spacing in \"fl RDT\"; these should be corrected.","section":"Abstract and Conclusion"},{"comment":"The displayed formulas for f^{(1)}_{q,1} and f^{(1)}_{q,2} are difficult to parse, with ambiguous parentheses and expressions like \"2/2/γ\"; please rewrite them in a cleaner form and verify all prefactors.","section":"Section 3.2, Eq. (39)"},{"comment":"Figure 15 has no caption explaining what is plotted, and Table 3 intermixes \"partial\" and \"full\" rows without a clear ordering; a short caption and consistent row labels would improve readability.","section":"Figure 15 and Table 3"},{"comment":"Several core references, in particular [94], [97], and [98], are arXiv preprints with no publication status, and reference [101] is incomplete (\"2025. available online at arxiv.\"). Please supply DOIs or journal information where available.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's theoretical apparatus is almost entirely the author's own fl RDT framework, with key theorems deferred to arXiv preprints that are not accessible to a standard referee check. I would advise the editor to require either a self-contained proof of Theorems 1–3 or an explicit statement that the theoretical predictions are not needed for the empirical contribution. The absence of code or a data repository also limits the verifiability of the numerical claims. The empirical results are interesting, but the current framing overstates what has been established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a useful heuristic paper with a thin theory. The CLuP-SK algorithm is simple, parameter-light, and the reported numbers are plausible: 0.755/0.757/0.758 at n=2000/4000/8000, heading toward the known Parisi value around 0.763. What's new is that it gets there without precomputed Parisi parameters, which IAMP needs. The overlap/ultrametricity plots are a nice empirical bonus. The paper is honest about its caveats: it calls Section 4.2.1 an approximate landscape characterization and says other intrinsic features may matter. That honesty extends to a fair literature review, heavily self-referential but complete on the classical SK results.\n\nThe soft spots are exactly where you'd expect. Eq (61) replaces the random quadratic inside the barrier objective with its asymptotic maximum xi(rx) over X(rx). That kills the fluctuations that can create high-dimensional local minima, and it assumes the descent finds the maximizing x for each radius. The no-local-optima conclusion is about the one-dimensional profile, not the actual high-dimensional objective. The paper admits this, but the abstract's 'typically easy' claim is stronger than the evidence. Theorems 1 and 2 are imported from the author's own fl RDT papers without proof; a referee would need to verify those or the paper should mark the whole theoretical section heuristic. Numerical evidence needs work: no error bars, no code, no comparison against IAMP or other baselines, and Table 2 is three points. I don't think this is fatal; the core empirical claim is testable and likely correct in broad brush. But as written, the theory is a suggestion rather than a proof.\n\nWho is this for? People who want a practical near-optimal solver for the SK model and are willing to trust an empirical demonstration. It is not a rigorous complexity-theoretic statement. The fl RDT framework users may also find the application interesting. I would send it to a serious referee—the algorithm is simple enough and the numbers good enough that the community benefits from an independent check—but the referee should insist on code, more experiments, and a clear separation between proved and heuristic claims.","headline":"Useful heuristic with plausible numbers, but the theory is a heuristic too and the 'typically easy' claim overshoots the evidence.","tokens_in":26744,"tokens_out":4408,"would_cite":false,"duration_ms":48726,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["82D30","82B44","68Q25","90C26"],"pacs":["75.10.Nr"],"model":"deepseek-v4-flash","headline":"The paper shows that a simple barrier-descent routine reaches about 0.76 of the Sherrington–Kirkpatrick ground-state free energy at n≈2000–8000, approaching the 0.763 thermodynamic limit.","keywords":["Sherrington–Kirkpatrick model","ground state free energy","CLuP algorithm","spin glass","random duality theory","barrier descent","quadratic maximization","typical-case complexity"],"falsifier":"Take fresh Gaussian matrices of size n=$10^{5}$, run the published CLuP-SK dynamics with the stated parameters (one random start, no restarts), and record the best normalized objective. If the value stays below 0.75 or varies widely across starts, the surrogate-landscape assumption and the claimed typical easiness would be contradicted; movement toward 0.763 with increasing n would confirm them.","tokens_in":25667,"feed_emoji":"🧲","tokens_out":9190,"duration_ms":104647,"temperature":0.7,"pith_summary":"The paper tries to establish that the ground-state free energy of the Sherrington–Kirkpatrick (SK) spin glass, an indefinite Gaussian quadratic maximization over the binary cube, is typically easy to approximate in practice despite being NP-hard in the worst case. It introduces a Controlled Loosening-up (CLuP) algorithm, a barrier-descent routine that gradually relaxes a temperature-like parameter while descending, and shows numerically that it reaches about 0.76 for n in the low thousands, close to the exact thermodynamic limit of roughly 0.763. The same theory characterizes the landscape in terms of a one-dimensional radius variable, explaining why plain gradient descent does not get trapped. If the claims hold, the practical computational gap for the SK ground-state problem is effectively erased.","feed_headline":"One descent routine hits 0.76 spin-glass ground-state energy","feed_subtitle":"On instances with a few thousand spins it approaches the 0.763 thermodynamic limit — with no precomputed parameters.","key_machinery":"The load-bearing object is the one-dimensional surrogate landscape f_b(r_x)=-t_{0x}r_x-\\log(-0.$9r_x^{2}$+\\xi(r_x)+\\kappa), where ξ(r_x) is the asymptotic maximum of x^T G x over the sphere-and-box set X(r_x)=\\{x:\\|x\\|_2=r_x,\\ $x_i^{2}$\\le 1/n\\}. The paper computes ξ(r_x) through fully lifted random duality theory, a stationarized duality method for random processes, giving the sequence 0.7979 to 0.7653 to 0.7640 as the lifting level increases. The CLuP-SK iteration is gradient descent on the barrier objective \\bar{f}_{b,x}(x;t_{0x})=-t_{0x}\\|x\\|^2-\\log\\left(-\\left(x^T\\left(0.9I-\\frac{G^T+G}{2\\sqrt{2n}}\\right)x-\\kappa\\right)\\right)-\\frac{1}{n}\\sum_i\\log(1-$nx_i^{2}$), with t_{0x} multiplied by 1.1 after each pass. The surrogate has no non-global local minima for the tested t_{0x} values, which is what makes plain descent work.","core_discovery":"The central claim is that a simple iterative procedure can erase the residual constant-factor computational gap of the SK model in the typical case. Concretely, running CLuP-SK on Gaussian instances with n=2000, 4000, and 8000 gives normalized ground-state free energies of 0.755, 0.757, and 0.758, respectively, and the paper's fully lifted random duality theory yields the n→∞ limit 0.763, in agreement with established values of about 0.7632. The algorithm requires no precomputed order-parameter function, in contrast to earlier polynomial-time message-passing schemes that depend on Parisi parameters. The argument ties algorithmic success to a surrogate loss landscape along the radius r_x that exhibits no non-global local minima for the CLuP-SK model and its trimmed variant.","pith_inferences":["A testable consequence the paper leaves implicit is that if the surrogate landscape remains unimodal as t_{0x}→∞, the residual gap between simulated values (0.758 at n=8000) and the 0.763 limit should close uniformly as n grows.","The same CLuP-style loosening could plausibly transfer to other random quadratic maximization problems with sphere-and-box feasible sets, such as Hopfield-type or p-spin models, since the paper's construction is not tied to the specific SK interaction matrix beyond the Gaussian assumption.","If typical-case SK is genuinely easy for this procedure, worst-case NP-hardness results cease to be predictive for Gaussian instances, and similar barrier-descent methods may erode computational gaps in other random problems where uniform concentration holds.","The overlap and ultrametricity plots suggest CLuP-SK can serve as a practical sampler of near-optimal spin configurations, potentially replacing replica-based calculations in finite-size studies."],"forward_implications":["At n=2000, 4000, and 8000, single runs of plain gradient descent on the CLuP-SK barrier reach normalized ground-state free energies of approximately 0.755, 0.757, and 0.758, converging toward the theoretical 0.763 limit.","The associated CLuP-SK model's ground-state free energy ξ(r_x), viewed as a function of the radius r_x, is monotone increasing and has no non-global local optima at the lifting levels tested, which is why descent-based optimization succeeds.","Higher lifting levels refine the theoretical prediction from 0.7979 through 0.7653 and 0.7640 toward the known 0.7632 value, and the simulated overlap distribution matches the predicted RSB q(c/c_2) distribution on the fifth partial level.","No precomputed Parisi or order-parameter function is needed to run the algorithm, in contrast to earlier polynomial-time message-passing schemes.","Near-optimal configurations produced by CLuP-SK display an ultrametric overlap structure consistent with replica symmetry breaking predictions."],"supporting_citations":[{"why":"Introduces the Sherrington–Kirkpatrick model whose ground-state free energy is the optimization target.","marker":"[81]"},{"why":"Establishes worst-case NP-hardness of approximating indefinite quadratic maximization, motivating the typical-case analysis.","marker":"[12]"},{"why":"Provides the polynomial-time message-passing approach whose reliance on precomputed Parisi parameters the new algorithm avoids.","marker":"[62]"},{"why":"Introduces the Controlled Loosening-up mechanism that the CLuP-SK algorithm adapts to non-planted SK instances.","marker":"[92]"},{"why":"Supplies the stationarized fully lifted random-process machinery used to characterize the CLuP-SK model.","marker":"[94]"},{"why":"Supplies the fully lifted interpolation comparisons for bilinearly indexed random processes behind Theorem 1.","marker":"[97]"},{"why":"States the fully lifted random duality theorem that yields the closed-form expression for ξ(r_x).","marker":"[98]"},{"why":"Gives the high-precision thermodynamic-limit estimate 0.76321±0.00003 that the algorithm's outputs are compared against.","marker":"[30]"}],"fun_headline_variants":["CLuP erases computational gap for SK spin glasses","Practical CLuP hits 0.76 SK ground state free energy","SK ground state free energy via CLuP: ~0.76","Simple CLuP routine approaches SK model limit","CLuP algorithm nears SK ground state free energy limit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the random objective x^T G x inside the barrier can be replaced by its deterministic large-n maximum ξ(r_x) uniformly across every radius level X(r_x), so the one-dimensional surrogate faithfully represents the true high-dimensional landscape; if that concentration fails, plain gradient descent could stall in local minima even at large n.","fun_headline_variants_meta":{"raw":{"variants":["CLuP erases computational gap for SK spin glasses","Practical CLuP hits 0.76 SK ground state free energy","SK ground state free energy via CLuP: ~0.76","Simple CLuP routine approaches SK model limit","CLuP algorithm nears SK ground state free energy limit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000401,"raw_usage":{"total_tokens":2138,"prompt_tokens":1038,"completion_tokens":1100,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":1014}},"tokens_in":654,"tokens_out":1100,"duration_ms":9917,"temperature":1.0,"reasoning_tokens":1014,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:00:52.125467+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take fresh Gaussian matrices of size n=$10^{5}$, run the published CLuP-SK dynamics with the stated parameters (one random start, no restarts), and record the best normalized objective. If the value stays below 0.75 or varies widely across starts, the surrogate-landscape assumption and the claimed typical easiness would be contradicted; movement toward 0.763 with increasing n would confirm them.","supporting_citations":[{"cited_title":"Montanari","cited_arxiv_id":null,"evidence_quote":"Provides the polynomial-time message-passing approach whose reliance on precomputed Parisi parameters the new algorithm avoids."}],"review_version":1}