{"id":"5de8fe3a-5a62-4822-8f19-798204d248bf","arxiv_id":"2412.09285","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Free-Energy Machine, a mean-field annealing method powered by automatic differentiation and parallel replicas, matches or beats specialized solvers on MaxCut, balanced MinCut, and Max k-SAT benchmarks.","lead":"This paper introduces a general algorithm, the Free-Energy Machine, that minimizes a statistical-mechanics free energy with gradient-based machine-learning tools to solve combinatorial optimization problems. It reports strong speed and solution quality on maximum cut, balanced graph partitioning, and maximum satisfiability benchmarks, including graphs with over a million nodes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central 'general method surpasses specialized solvers' claim depends on per-instance hyperparameter tuning (Tables S2, S3, S5); a fixed-configuration held-out benchmark is needed to confirm that FEM is a general solver rather than an instance-tuned heuristic.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: the empirical superiority claim requires that FEM's reported performance reflects a fixed, general method rather than per-instance tuning. I agree with that assessment. The paper presents a coherent extension of mean-field annealing with automatic differentiation and parallel replicas, the free-energy derivations are straightforward, and the public code is a genuine asset. However, the headline claim of markedly surpassing specialized solvers is not separable from the extensive per-instance hyperparameter selection documented in Tables S2, S3, and S5. For example, in the G-set comparison, FEM uses different optimizer families and widely different temperature ranges per instance, while the dSBM baseline is cited from a fixed published protocol; this asymmetry makes the TTS comparison difficult to interpret as a property of FEM as a general method. In the bMinCut and MaxSAT benchmarks, the per-instance choices are also extensive, and the chip-verification result selects different coarsening levels for different q. None of this invalidates the method as a tunable heuristic, but it does invalidate the unqualified generality claim as currently supported. The proposed fixed-configuration held-out test would settle whether FEM retains its advantage when the tuning advantage is removed. Since this is exactly the condition that would need to hold for the strongest claim, the reader's CONDITIONAL verdict is appropriate and should not be changed.","tokens_in":69004,"tokens_out":3817,"duration_ms":43233,"concrete_test":"Freeze a single hyperparameter configuration (for example, the RMSprop defaults from the Methods code with the inverse-proportional beta schedule of Fig. 3a) by tuning only on a small development subset, say G1, G48, one 3elt q=4 instance, and one HG4 instance. Then run FEM with that exact fixed configuration on all 54 G-set instances, all four Walshaw graphs at q=2 through 32, and all 454 MaxSAT instances, reporting aggregate best-cut counts, TTS, and the number of best-known solutions achieved, and compare against the same dSBM, METIS, and KaFFPaE baselines. If per-instance tuning is essential to the current results, performance will drop measurably; if the drop is small, the generality claim is supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's strongest claim is that FEM is a unified, general solver that markedly surpasses algorithms tailored to each problem. What would have to be true is that a single FEM configuration, or at most a protocol with minor per-problem adjustments, achieves the reported performance without per-instance selection. The supplementary tables show the opposite: Table S2 assigns different optimizers (RMSprop vs SGD), learning rates, temperature ranges, gradient scales, Nstep, and batch sizes to individual G-set instances; Table S3 varies beta ranges, lambda_max, and Adam hyperparameters for every graph and q; Table S5 lists instance-specific Nstep, Nreplica, Tmax, gamma_grad, lr, alpha, weight decay, and momentum for many MaxSAT instances. The chip-verification experiment additionally chooses Louvain coarsening level 3 for q=4,8 and level 2 for q=16. Because the same instances were used to select these settings, the reported cuts and TTS values can reflect overfitting to the benchmark rather than the robustness of the mean-field annealing idea. The authors even state in Methods that hyperparameters were carefully tuned and suggest tuning on small replica counts before increasing R, which is legitimate as an engineering recipe, but it means the published numbers are not evidence for a parameter-free general solver. This is a correctness-risk issue in the empirical claim: if a fixed configuration is run on new instances, the advantage over METIS, KaFFPaE, dSBM, and MaxSAT solvers may shrink or disappear. The core derivations and code appear sound, so the concern is about benchmark methodology, not the mathematics.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Free-Energy Machine (FEM), a variational mean-field annealing method for combinatorial optimization. The authors represent discrete variables by softmax-parameterized marginal probabilities, minimize a temperature-annealed variational free energy for several replicas in parallel using automatic differentiation and standard machine-learning optimizers, and read out solutions by argmax. The method is applied to MaxCut (Ising-type binary variables), q-way balanced minimum cut (Potts-type multi-state variables), and Max k-SAT (higher-order interactions), with additional chip-verification and random-graph scalability experiments. The paper claims that FEM solves these problems in a unified framework, without Ising conversion, and markedly surpasses state-of-the-art specialized solvers in both solution quality and speed.","tokens_in":69380,"tokens_out":3724,"duration_ms":42288,"significance":"If the empirical claims survive scrutiny, FEM would be a valuable contribution: a single GPU-friendly mean-field annealing framework covering binary, multi-state, and higher-order cost functions, with explicit gradient formulas (Eqs. S21-S28) that are derived correctly and reduce computation time. The variational free-energy expressions in Eqs. (9)-(11) are sound, and the paper provides reproducible code and detailed supplementary tables. The core physics idea is not entirely new - references to earlier mean-field annealing are included - but the combination with massive replica parallelism, automatic differentiation, and modern optimizers is a useful engineering advance. The main weakness is that the headline claim of being a general solver that surpasses specialized algorithms is not established by the reported protocol, because per-instance hyperparameter selection is used throughout the benchmarks. The mathematical framework itself is not circular: the free energies and gradients follow from the problem definitions with no fitted constants. The empirical general-solver claim, however, requires a fixed-configuration or properly separated tuning protocol.","major_comments":[{"comment":"The central claim that FEM is a general method that markedly surpasses specialized solvers is weakened by the benchmark protocol. Tables S2, S3, and S5 assign different optimizers, learning rates, temperature ranges, gradient scales, replica counts, and penalty schedules to individual instances, and the chip-verification experiment chooses the Louvain coarsening level separately for q=4,8 versus q=16. Because the same benchmark instances were used to select these settings, the reported cuts, TTS values, and solution times do not demonstrate that a single FEM configuration, or even a fixed per-problem protocol, generalizes to unseen instances. Please report held-out results with a fixed configuration, or explicitly reposition FEM as requiring per-instance tuning and report the tuning cost as part of the time-to-solution.","section":"Methods, 'Hyperparameter tunning'; Tables S2, S3, S5"},{"comment":"The MaxCut TTS comparison supports a more qualified claim than the text states. FEM achieves shorter TTS than dSBM on 33 of 54 G-set instances, but dSBM remains faster on many random, toroidal, and planar instances, including G6-G13, G22-G34, and G43-G47; for some instances FEM TTS is orders of magnitude larger (e.g., G33: 659,607 ms versus 57,766 ms, and G51-G54 are all slower). This is consistent with FEM being competitive rather than uniformly superior, and the Discussion should be revised to quantify the comparison and describe where FEM is and is not faster.","section":"Fig. 3(c) and Table S1"},{"comment":"The bMinCut results do not uniformly support the statement that FEM 'significantly outperforms KaFFPaE with a large q value.' In Table I, FEM is sometimes worse than KaFFPaE (add20 q=16: 2057 versus 2054; data q=8: 669 versus 668; bcsstk33 q=8: 34440 versus 34437) and sometimes better. FEM is consistently better than METIS, which is a solid result, but the KaFFPaE comparison should be reported with run-to-run variability and the claim should be restricted to the instances and settings where the advantage actually holds.","section":"Table I and accompanying text"},{"comment":"The MaxSAT speed comparison measures 'RC time' (replica computation time) and reports an average of 0.074 seconds per instance, but Table S5 shows per-instance hyperparameter tuning was performed in advance. The time spent selecting Nstep, Nreplica, Tmax, gamma_grad, learning rate, and momentum is not included in the comparison, while the incomplete-solver times from the competition represent full end-to-end runs. For a fair speed claim, the paper should either report end-to-end time including hyperparameter selection or state explicitly that the quoted time excludes tuning; as written, the speed advantage is overstated.","section":"Fig. 6 and Table S4"}],"minor_comments":[{"comment":"The sentence 'The expression of FMF can be explicitly formulated' appears in several places; for the MaxCut free energy in Eq. (9), the summation over σ_i and σ_j and the factor 1/2 conventions should be stated clearly, since the code in the Methods divides the cut by 2 during inference but the free energy does not.","section":"Methods, Eq. (9)"},{"comment":"The phrase 'a slight modification on the constraint term in the formula of mean-field free energy should be made' has a grammatical issue and should be rewritten as 'we modify the constraint term in the mean-field free energy as follows.'","section":"Supplementary, Eq. (S33)"},{"comment":"The caption states 'the inverse-proportional scheduling is used for the annealing,' but Table S5 lists Tmin and Tmax rather than βmin and βmax; please define the relationship to the β schedule used in the main text to avoid confusion.","section":"Supplementary, Table S5"},{"comment":"The claim that FEM 'markedly surpasses contemporary algorithms tailored specifically for each problem' should be tempered to reflect the mixed TTS results on G-set, the mixed KaFFPaE comparison, and the per-instance tuning used in the benchmarks.","section":"Discussion, paragraph 3"}],"recommendation":"major_revision","confidential_remarks":"The paper presents a clean variational mean-field framework with correct derivations and a useful open-source implementation. The main issue for the editor is that the empirical headline depends on per-instance hyperparameter tuning that is documented in the supplementary tables; this should have been disclosed as a limitation in the main text. I would be willing to reconsider after the authors provide a fixed-configuration or properly separated tuning experiment, or after they substantially reframe the claims as those of an instance-tuned heuristic. The fit with the journal is acceptable for a methods paper, but the current version overstates the evidence for generality."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is older than the paper lets on—annealed variational mean-field goes back to Bilbro et al.—but the combination of automatic differentiation, parallel replicas, and application to Potts and higher-order problems is genuinely new, and the benchmarks are extensive. The free-energy expressions and explicit gradients are derived correctly, the code is public, and the authors are honest about the lineage. That is real work.\n\nThe soft spot is the headline claim. The paper says FEM 'markedly surpasses' specialized solvers and presents it as a general method. But the supplementary tables show per-instance hyperparameter tuning: different optimizers, learning rates, temperature ranges, replica counts, and penalty schedules for individual G-set instances (Table S2), for each graph and q in bMinCut (Table S3), and for many MaxSAT instances (Table S5). The chip-verification experiment also chooses different Louvain coarsening levels for different q. When the same instances used to select settings are the ones reported, the numbers can reflect tuning rather than the robustness of the underlying method. This is not a fatal flaw—tuning is standard in heuristic solver papers—but it means the published cuts and TTS values are not evidence for a single fixed-configuration general solver. The abstract's 'surpasses the performance of state-of-the-art algorithms' is also stronger than the G-set TTS results, where FEM wins on only 33 of 54 instances. The bMinCut and MaxSAT results are more convincing, but they too use per-instance choices.\n\nThe mathematics is not circular: the free energies are derived from the problem definitions, no fitted constants are hidden in the objective, and the benchmarks use external best-known results. The authors even note that hyperparameter tuning can be done on the mean cut with small replica counts, which is a legitimate recipe. What is missing is a held-out evaluation: a fixed FEM configuration, or at most one small grid per problem class, run on instances not used for tuning. That would be the clean test of generality.\n\nWho gets value from this: researchers working on GPU-based heuristics, physics-inspired optimization, and anyone who wants a practical general framework for MaxCut, balanced partition, and MaxSAT. The paper deserves a serious referee: the method is sound, the code is public, and the empirical claims are important enough to verify properly. I would recommend accepting for review, but the referee should insist on a fixed-configuration benchmark with error bars and a head-to-head against general-purpose solvers. Without that, the strongest claims should be softened.","headline":"A solid, honest extension of mean-field annealing to Potts and higher-order problems, with correct math and public code, but the 'surpasses specialized solvers' claim rests on per-instance tuning that a reviewer should push on.","tokens_in":69954,"tokens_out":1542,"would_cite":true,"duration_ms":21619,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","82B20","68T20"],"pacs":["05.10.-a","89.20.Ff","75.10.Nr"],"model":"deepseek-v4-flash","headline":"The Free-Energy Machine claims a single annealed mean-field solver outperforms problem-specific solvers on MaxCut, balanced MinCut, and Max k-SAT without Ising formulations.","keywords":["combinatorial optimization","free-energy minimization","mean-field annealing","automatic differentiation","maximum cut","balanced minimum cut","Max k-SAT","GPU parallelization"],"falsifier":"Run FEM on a held-out set of new and previously published instances using a single fixed default hyperparameter configuration (for example, the most common settings in the supplementary tables) and compare the resulting cuts and MaxSAT gaps with the per-instance-tuned numbers reported in the paper; if the fixed configuration systematically misses best-known values, the general-unified-solver claim would not survive.","tokens_in":68759,"feed_emoji":"⚡","tokens_out":10537,"duration_ms":97322,"temperature":0.7,"pith_summary":"This paper sets out to establish that one algorithm, the Free-Energy Machine (FEM), can serve as a general and fast heuristic for combinatorial optimization by replacing the original discrete search with the minimization of an annealed variational mean-field free energy. The cost function of a problem is treated as the energy of a spin system, and the ground state is recovered from the zero-temperature limit of the Boltzmann distribution, approximated by softmax-parameterized per-variable marginals and updated with gradient optimizers such as Adam. Because the gradients come from automatic differentiation, the same framework applies to binary, multi-state, and higher-order interacting variables without converting the problem into an Ising formulation. The paper reports best-known cuts on most G-set MaxCut instances, lower cut values than METIS on large balanced minimum cut problems, a roughly 22-27% reduction in communication volume in a chip-verification task, and optimal answers on 448 of 454 MaxSAT 2016 instances in about 0.07 seconds on a GPU.","feed_headline":"Free-energy annealing tops tailored solvers on three NP-hard problems","feed_subtitle":"Best-known MaxCut cuts, lower cuts than METIS, and 448 of 454 MaxSAT optima in about 0.07 seconds.","key_machinery":"The load-bearing object is the variational mean-field free energy $F_{\\rm MF}(\\{P_i(\\sigma_i)\\},\\beta)=U_{\\rm MF}-S_{\\rm MF}/\\beta$, where $U_{\\rm MF}$ is the mean-field expectation of the problem's cost and $S_{\\rm MF}$ is the entropy of the product distribution over marginals. Each marginal $P_i(\\sigma_i)$ is the softmax of a local field $h_i(\\sigma_i)$, so the discrete search becomes a smooth optimization with exact gradients. Annealing $\\beta$ from small to large values first lets the entropy dominate, then drives the marginals toward one-hot states; reading out the argmax of the marginals and selecting the lowest-energy replica yields the proposed solution. The machinery is general because the only problem-specific ingredient is the energy expectation, which can be fed to automatic differentiation or to explicit gradient formulas.","core_discovery":"The central claim is that minimizing replicas of the variational mean-field free energy $F_{\\rm MF}=\\sum_\\sigma P_{\\rm MF}(\\sigma)E(\\sigma)+(1/\\beta)\\sum_\\sigma P_{\\rm MF}(\\sigma)\\ln P_{\\rm MF}(\\sigma)$, annealed from high to low temperature, is a unified and competitive way to solve NP-hard combinatorial optimization. The marginals $P_i(\\sigma_i)$ are parameterized by local fields through a softmax, the gradients are computed by automatic differentiation or explicit formulas, and many replicas are minimized in parallel on GPUs. The paper argues that this single recipe, without Ising formulations, produces the best-known cut on the 2000-node complete graph K2000, reaches the best-known value on most G-set instances with shorter time-to-solution than the discrete simulated bifurcation machine on 33 of 54 instances, beats METIS on q-way balanced minimum cut across real-world and million-node random graphs, and finds the best-known answer on 448 of 454 random MaxSAT 2016 instances, with an average GPU time of 0.074 seconds.","pith_inferences":["The generality claim could be tested directly by freezing one hyperparameter configuration and running FEM across all G-set, Walshaw, and MaxSAT 2016 instances without per-instance tuning; the supplementary tables currently vary those settings, so that experiment would separate the method from its tuning.","Because the paper writes energy expectations for graph coloring, community detection, and quantum error correction in the supplement, the same annealing scheme is immediately testable on those problems without further methodological work.","The mean-field product ansatz is the least expressive part of the loop; upgrading it to TAP or Bethe free energies, as the paper itself mentions for future work, could improve accuracy on hard glassy instances while keeping the optimization machinery intact.","The converged marginals could serve as a warm start for exact or local-search solvers, a hybrid use the paper does not explore."],"forward_implications":["If the benchmarks hold, a single FEM implementation, differing by one line between MaxCut and balanced MinCut, could replace several problem-specific solvers for QUBO, Potts, and higher-order problems.","For a new combinatorial problem, a user only needs to write down the mean-field expectation of its cost; automatic differentiation then supplies the gradients, removing the need for Ising conversion.","The parallel-replica design means runtimes can shrink almost linearly with GPU or FPGA resources, making million-variable instances solvable in seconds or less.","In balanced graph partitioning, FEM's reported lower edge cuts on million-node graphs would translate directly into reduced communication overhead in parallel computing and chip verification.","On MaxSAT-style problems, sub-second average solution times would give practitioners a fast alternative to dedicated incomplete MaxSAT solvers on competition-size instances."],"supporting_citations":[{"why":"supplies the discrete simulated bifurcation machine baseline and the time-to-solution metric used for MaxCut comparisons.","marker":"[11]"},{"why":"Adam optimizer, the gradient-based update rule that FEM uses to minimize the mean-field free energies.","marker":"[29]"},{"why":"G-set MaxCut benchmark instances with best-known cut values that define the TTS comparisons.","marker":"[46]"},{"why":"METIS, the multilevel graph partitioner that is the main baseline for q-way balanced minimum cut.","marker":"[52]"},{"why":"KaHIP/KaFFPaE, the balanced partitioning solver that FEM compares against on real-world graphs.","marker":"[53]"},{"why":"Max-CTDS, the continuous-time MaxSAT solver whose energy gaps and runtimes are used as the MaxSAT baseline.","marker":"[60]"},{"why":"MaxSAT 2016 competition instances and the incomplete-solver results that define the benchmark.","marker":"[61]"},{"why":"Louvain community detection, used to coarsen the large chip-verification graph before FEM partitioning.","marker":"[58]"}],"fun_headline_variants":["Free-energy machine beats tailored solvers on MaxCut, MinCut, MaxSAT","0.07s per optimum: free-energy annealer tops MaxSAT, MaxCut, MinCut","Best-known K2000 cut, beats METIS, 448/454 MaxSAT in 0.07s","Single free-energy algorithm outperforms dedicated solvers on three NP-hard problems","Unified free-energy annealing tops problem-specific solvers on three NP-hard tasks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported superiority assumes the results come from one fixed general method, whereas the supplementary tables give different optimizers, learning rates, temperature ranges, gradient scales, replica counts, and penalty schedules to individual instances, so the published numbers may not be reproducible with a single configuration on new instances.","fun_headline_variants_meta":{"raw":{"variants":["Free-energy machine beats tailored solvers on MaxCut, MinCut, MaxSAT","0.07s per optimum: free-energy annealer tops MaxSAT, MaxCut, MinCut","Best-known K2000 cut, beats METIS, 448/454 MaxSAT in 0.07s","Single free-energy algorithm outperforms dedicated solvers on three NP-hard problems","Unified free-energy annealing tops problem-specific solvers on three NP-hard tasks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001764,"raw_usage":{"total_tokens":6996,"prompt_tokens":1013,"completion_tokens":5983,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":629,"completion_tokens_details":{"reasoning_tokens":5869}},"tokens_in":629,"tokens_out":5983,"duration_ms":41941,"temperature":1.0,"reasoning_tokens":5869,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:06:10.905271+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run FEM on a held-out set of new and previously published instances using a single fixed default hyperparameter configuration (for example, the most common settings in the supplementary tables) and compare the resulting cuts and MaxSAT gaps with the per-instance-tuned numbers reported in the paper; if the fixed configuration systematically misses best-known values, the general-unified-solver claim would not survive.","supporting_citations":[{"cited_title":"Ye ,\\ @noop title G-set test problems ,\\ howpublished https://web.stanford.edu/ yyye/yyye/Gset/ NoStop","cited_arxiv_id":null,"evidence_quote":"G-set MaxCut benchmark instances with best-known cut values that define the TTS comparisons."},{"cited_title":"Moln \\'a r , author F","cited_arxiv_id":null,"evidence_quote":"Max-CTDS, the continuous-time MaxSAT solver whose energy gaps and runtimes are used as the MaxSAT baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"MaxSAT 2016 competition instances and the incomplete-solver results that define the benchmark."}],"review_version":1}