{"id":"145cc2fe-49f2-49b1-84a2-4566893b4701","arxiv_id":"2412.13489","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"IsingSim uses Walsh-Fourier expansion and convolution to efficiently evaluate and differentiate higher-order Ising Hamiltonians, and its experiments suggest Type I spins outperform Type II and III on parity learning with error.","lead":"A group of engineers built a software framework, IsingSim, that simulates higher-order Ising models, a compact way to encode hard optimization problems. The framework computes gradients efficiently and compares three relaxation schemes, offering hardware designers a fast way to explore design choices before building chips.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4's gradient formula is off by one: differentiating Eq. (5) requires coefficient \\hat f(i+1), not \\hat f(i); on f(x1,x2)=x1x2 it returns 0 instead of x2, so the claimed bidirectional acceleration is not yet established.","rationale":"The most load-bearing weakness is not the Type II relaxation issue identified by the reader, but the off-by-one coefficient indexing in Corollary 4, which directly undermines the headline acceleration claim. The reader's Type II concern is real but secondary: Eq. (3) states p>0, yet the intrinsic locking term a^4 - 2p a^2 has minimum -p^2 per coordinate, and H on [-\\sqrt p, \\sqrt p]^n is not H on [-1,1]^n for p\\neq 1, so Corollary 1 is false as written; only p=1 is plausible. The bidirectional/cumulative-convolution gradient speedup is the formal basis of the abstract's claim, and Corollary 4 does not follow from Eq. (5): differentiating the elementary-symmetric expansion shifts the coefficient index, while the printed formula uses the unshifted coefficient. The two-variable case f=x1x2 makes the error unambiguous. Because the paper releases no code or runtime baselines, the reader cannot check whether the implementation secretly uses the corrected indexing. The convolution idea itself may be salvageable with a one-line coefficient shift and an implementation check, so outright rejection is not warranted; however, the central claim requires a corrected corollary, a rerun of experiments, and released artifacts before it can be accepted. The reader's overall conditional verdict is therefore retained, but for a different reason than the Type II concern.","tokens_in":7877,"tokens_out":14576,"duration_ms":130836,"concrete_test":"Independently re-derive Eq. (6) from Eq. (5) using the generating function \\prod_{j\\in e}(1 + a_j z): the coefficient of e_r(a_{\\neq j}) in \\partial f / \\partial a_j is \\hat f(r+1), not \\hat f(r). As a numerical check, implement Eq. (6) verbatim for f(x1,x2)=x1x2 and compare with automatic differentiation; it should produce 0 instead of x2. If the authors' implementation uses the corrected shifted coefficients, the paper must state that indexing explicitly and rerun the gradient-based experiments; otherwise the acceleration claim fails.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central acceleration claim rests on Corollaries 3 and 4. Corollary 4 is internally inconsistent with Eq. (5). If f_e(a) = \\sum_{k=0}^{d} \\hat f_e(k) e_k(a_1,...,a_d), where e_k is the elementary symmetric polynomial of degree k, then differentiating gives \\partial f_e / \\partial a_j = \\sum_{k=1}^{d} \\hat f_e(k) e_{k-1}(a_{\\neq j}) = \\sum_{r=0}^{d-1} \\hat f_e(r+1) e_r(a_{\\neq j}). Eq. (6) instead uses \\hat f_e(r). Concretely, for the symmetric two-variable constraint f(x1,x2)=x1x2, the Fourier coefficients are \\hat f(0)=0, \\hat f(1)=0, \\hat f(2)=1; Eq. (6) for \\partial f / \\partial x_1 sums only r=0,1 and returns 0, while the true derivative is x2. Thus the cumulative-convolution gradient formula, the alleged speedup, is not computing gradients of the FE Hamiltonian as written. No code or runtime baselines are released, so the discrepancy cannot be attributed to an implementation detail. A corrected index shift may salvage the idea, but the formal claim as stated is unsupported.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a theoretical and experimental framework, IsingSim, for simulating higher-order Ising Hamiltonians. It defines a higher-order Ising model whose hyperedges encode Boolean constraints, uses Walsh-Fourier expansions to obtain multilinear polynomial relaxations, and presents three continuous relaxation schemes: Type I (hypercube relaxation), Type II (DOPO-like intrinsic locking), and Type III (oscillator-based injection locking). The authors derive a symmetric-FE evaluation scheme using convolution (Corollary 3), a cumulative-convolution gradient scheme (Corollary 4), and a Moreau-envelope gradient estimator. Experiments on parity-learning-with-error instances compare three spin types and three gradient types, reporting success rates and model-size reductions. The paper concludes that the framework can guide higher-order Ising machine design.","tokens_in":8169,"tokens_out":11075,"duration_ms":95806,"significance":"The paper formalizes higher-order Ising Hamiltonians and gives a clean algebraic treatment of symmetric constraints; Corollary 3's O(|e|^2) evaluation via convolution is correct and useful, and the PLE benchmark comparison of three relaxation geometries is a reasonable proof-of-concept. The central acceleration and relaxation-equivalence claims, however, rest on Corollaries 1 and 4, both of which contain mathematical errors as written; because these corollaries are load-bearing for the paper's main claims, the current version does not establish the framework's validity. The paper would be significantly strengthened by correcting these statements and by providing runtime comparisons rather than only success rates.","major_comments":[{"comment":"Eq. (3) is false for p ≠ 1. The locking term a_i^4 − 2p a_i^2 has minimum −p^2 at a_i = ±√p, so the left side of Eq. (3) is generally not −Σ w_e − n: for example, with H = x1 x2, n = 2, p = 4, the point (2, −2) gives x1 x2 + (16−32) + (16−32) = −36, while the claimed minimum is −3. The proof's assertion that \"a function retains the minima when it is a linear combination of the functions with the same minima\" is false in general (e.g., x^2 and 2x^2 have the same global minimum, but x^2 − 2x^2 = −x^2 does not). For p = 1 the claim can be proved by a separate argument, since the locking term is then a nonnegative potential vanishing exactly on {±1}^n and the Type I relaxation already places the continuous minimum at the vertices; that argument is not given. The Type II relaxation as stated is therefore not a valid continuous relaxation except for p = 1.","section":"II-C, Corollary 1"},{"comment":"Eq. (6) has an index-shift error. Differentiating f_e(a) = Σ_{i=0}^d \\hat f_e(i) e_i(a) gives ∂f_e/∂a_j = Σ_{r=0}^{d−1} \\hat f_e(r+1) e_r(a_{\\ne j}); Eq. (6) instead sums \\hat f_e(r) e_r(a_{\\ne j}). The same error appears in the cumulative-convolution formula in the following paragraph. Concretely, for f(x1, x2) = x1 x2, the only nonzero coefficient is \\hat f(2) = 1; Eq. (6) returns 0 for ∂f/∂x1, whereas the true derivative is x2. Thus the cumulative-convolution gradient formula does not compute gradients of the FE Hamiltonian as written, and the claimed bidirectional acceleration of gradient computation is not established. A corrected coefficient index may salvage the scheme, but the formal claim must be revised.","section":"II-E1, Corollary 4"},{"comment":"The abstract and conclusion state that IsingSim \"significantly accelerate[s] the simulation speed\", but no runtime measurements or baselines are reported. Table I reports model sizes and Fig. 3 reports success rates, but there is no wall-clock comparison of the convolution-based evaluation against the naive O(2^{|e|}) evaluation, nor against other higher-order Ising solvers. The complexity reduction in Corollary 3 is theoretical; an empirical runtime comparison is needed to support the speed claim. In addition, the experimental section does not state how success rates are defined or provide error bars over the 100 trials per instance, which limits the strength of the performance conclusions.","section":"III and Abstract"}],"minor_comments":[{"comment":"The proof says \"minima of H(cos(a))\" but the function in Eq. (4) is H(sin(a)); this typo should be corrected.","section":"II-C, Corollary 2"},{"comment":"The notation \\bigcirc_{j∈e}[a_j,1] and the sentence \"N denotes the convolution of |e| sequences\" are not formally defined; please define the convolution operator and the indexing of the result entries explicitly.","section":"II-D, Corollary 3"},{"comment":"The Boolean formula is written F = V_{c∈C} c; the conjunction symbol should be \\wedge, and the term \"hybrid constraint\" should be explicitly defined.","section":"Definition 1"},{"comment":"The text says \"type-II Ising spins at the same initial point will converge to a local minimum near (1, 1)\", but for p = 1 the locking potential minima are at ±1; clarify the convergence points shown in Fig. 2b.","section":"III-A"},{"comment":"The columns |V_2| and |E_2| contain non-integer values; indicate whether these are averages over the generated instances.","section":"Table I"},{"comment":"Reference [14] is cited with a URL only; provide the publication status or a stable DOI if available.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The manuscript draws heavily on the authors' prior FourierSAT and GPU local search papers for Theorem 2 and the FE framework; the incremental contribution is the Type II/III relaxations and the convolution speedup. The errors in Corollaries 1 and 4 are the main barrier; they are correctable, so I recommend major revision rather than rejection. If resubmitted, a runtime comparison and code release would substantially strengthen the empirical claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is worth reading for its convolution-based evaluation of symmetric higher-order Ising Hamiltonians. Corollary 3 correctly reduces evaluation from O(2^|e|) to O(|e|^2), and the empirical comparison of three spin relaxation types on parity learning with error is genuinely new and useful for hardware designers. The framework is clean, and decoupling spins from gradients is a sensible design.\n\nBut the central acceleration claim is not established. Corollary 4's gradient formula is off by one. If f_e(a) = Σ \\hat f(k) e_k(a), then ∂f_e/∂a_j = Σ \\hat f(k) e_{k-1}(a_{\\neq j}) = Σ_{r=0}^{d-1} \\hat f(r+1) e_r(a_{\\neq j}). The paper uses \\hat f(i) instead of \\hat f(i+1). For f(x1,x2)=x1x2 the formula returns 0 instead of x2. The cumulative-convolution scheme that follows inherits the same index problem, so the bidirectional speedup is unsupported as written. A corrected index shift may salvage the idea, but the paper doesn't provide it.\n\nThere is also a problem with Corollary 1. For p≠1 the global minima of H(a)+Σ(a_i^4-2p a_i^2) over [-√p,√p]^n sit at vertices with coordinates ±√p, not at Boolean ±1, so the claimed equivalence only holds for p=1. The proof's hand-wave about functions retaining minima doesn't address this.\n\nThe experiments have no runtime baselines, no comparison with existing solvers, and no code or data. Success rates are modest, and the Moreau-envelope estimator is only tested on the smallest instances.\n\nThat said, the paper is not sloppy in spirit. The convolution evaluation is correct, the empirical study is honest about difficulties, and the errors are fixable. It deserves a serious referee who will catch the index bug and the p≠1 overgeneralization, but I wouldn't cite it in its current form.\n\nRecommendation: send it to review, with a request for corrected gradient formulas, a proper benchmark, and released artifacts.","headline":"Useful convolution trick and an honest empirical comparison, but the central gradient formula has an off-by-one index error and the Type II relaxation theorem only holds for p=1.","tokens_in":8696,"tokens_out":9946,"would_cite":false,"duration_ms":81558,"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":"The paper establishes that symmetric higher-order Ising Hamiltonians can be evaluated in $O(|e|^2)$ time via convolution, and that two cumulative convolution passes make every exact partial derivative cost one additional convolution.","keywords":["higher-order Ising model","Ising machine","Walsh-Fourier expansion","symmetric Boolean functions","convolution","Hamiltonian relaxation","parity learning with error","gradient descent"],"falsifier":"Take a small symmetric constraint such as the four-variable cardinality constraint from the paper's Example 2, form the Type II relaxed Hamiltonian with $p = 1$, and numerically search for a point inside the box whose value is below $-\\sum_e w_e - n$; finding one would refute the Type II relaxation theorem, while finding none on many random restarts would support it.","tokens_in":7658,"feed_emoji":"🧲","tokens_out":9549,"duration_ms":81610,"temperature":0.7,"pith_summary":"IsingSim is a simulator for higher-order Ising Hamiltonians, energy functions whose terms couple arbitrarily many binary spins at once, and this paper supplies the theoretical core that makes such simulation scalable. The central claim is that for symmetric constraints, the Walsh-Fourier expansion of a hyperedge can be evaluated by convolutions of two-term sequences, lowering the cost from $O(2^{|e|})$ to $O(|e|^2)$, and that the same convolution machinery yields exact partial derivatives with only one additional convolution after two cumulative passes. The paper further claims that the standard continuous relaxations of the Hamiltonian agree with the original Boolean problem at their global minima, so gradient descent on the relaxed landscape should find satisfying assignments, and that in experiments on parity learning with error, the plain hypercube relaxation outperforms the two physics-inspired relaxations. A sympathetic reader would care because higher-order Ising models encode industrial constraints compactly but lack efficient hardware or algorithms; this framework gives a way to study their behavior and a blueprint for building faster higher-order Ising machines.","feed_headline":"Convolution cuts Ising simulation from exponential to quadratic time","feed_subtitle":"A two-pass cumulative convolution makes each exact gradient cost one extra convolution, so larger hyperedges become simulable.","key_machinery":"The carrying object is the Walsh-Fourier expansion of a Boolean hyperedge function, a unique multilinear polynomial that agrees with the function on all $\\{-1,1\\}$ assignments. For a symmetric constraint, the expansion's coefficients depend only on the size of the monomial, so the polynomial can be assembled as a weighted sum of elementary symmetric functions. The paper computes those elementary symmetric functions as a convolution of $|e|$ two-term sequences $[a_j, 1]$; retaining intermediate results in forward order, called $CC_{\\text{seq}}$, and reverse order, called $CC_{\\text{rev}}$, lets every partial derivative be read off as one more convolution. This two-pass cumulative convolution is the mechanism that makes $O(|e|^2)$ evaluation and near-free exact gradients possible.","core_discovery":"The central claim is that a higher-order Ising Hamiltonian built from symmetric Boolean constraints can be simulated without exponential cost. Using the Walsh-Fourier expansion, each hyperedge becomes a unique multilinear polynomial; when the constraint is symmetric, the coefficients depend only on monomial size, so the evaluation reduces to a convolution of $|e|$ two-term sequences $[a_j, 1]$ and costs $O(|e|^2)$ instead of $O(2^{|e|})$ (Corollary 3). By keeping the intermediate convolution results in forward and reverse order, the partial derivative with respect to any one spin is obtained with a single additional convolution (Corollary 4), so exact gradient descent becomes computationally feasible. The paper also claims that the standard continuous relaxations, the hypercube, intrinsic locking, and injection locking, have global minima that match the Boolean satisfying assignments according to Theorem 2 and Corollaries 1 and 2, and reports experiments on parity learning with error showing that the hypercube relaxation has the highest success rate, with a weak-convexity explanation for that ranking.","pith_inferences":["One testable extension is to group nearly symmetric constraints into symmetric blocks; if the convolution speedup survives grouping, the practical range of hyperedge sizes could grow well beyond the paper's benchmarks.","Because the Type II relaxation argument depends on a linear combination of minima-preserving functions retaining those minima, checking this property on small random formulas would clarify exactly which relaxation guarantees hold beyond the paper's examples.","The reported Type I advantage suggests that hardware with simple hypercube coupling may be preferable to designs that add locking terms, an implication the paper leaves for designers to test on other benchmarks.","The framework's decoupling of spins from gradients means the same Hamiltonian could be simulated with new hardware-inspired update rules, such as noise-injected or analog-gradient rules, without changing the evaluation machinery."],"forward_implications":["Corollary 3 implies that any higher-order Ising simulator for symmetric constraints can replace exponential hyperedge evaluation with quadratic evaluation, so hyperedges with dozens of spins become practical to simulate.","Corollary 4 gives hardware designers a direct recipe: two cumulative convolution passes for the whole hyperedge, then one convolution per spin for the gradient, a structure that can be mapped to digital accelerators or analog arrays.","The relaxation theorems say that whenever the continuous minimum equals the Boolean minimum, gradient descent on any of the three landscapes is in principle a legitimate solver, not just a heuristic.","The weak-convexity analysis suggests a ranking of relaxation difficulty, with Type I easiest and Type III hardest, which can guide which physical Ising machine design is worth building for a given class of constraints.","The behavior of the proximal-style gradient estimator shows that global-minimum-finding gradients work on small problems but become impractical at higher dimensions, pointing toward hybrid local-global strategies at scale."],"supporting_citations":[{"why":"Supplies the Walsh-Fourier expansion theorem that turns each hyperedge into a unique multilinear polynomial, the starting point for the convolution speedup.","marker":"[15]"},{"why":"Establishes the Type I relaxation equivalence and the absence of interior local optima for multilinear Hamiltonians, which the paper's Theorem 2 extends to higher-order constraints.","marker":"[1]"},{"why":"Provides the maximum principle used to locate optima of the relaxed multilinear Hamiltonian on the boundary of the hypercube.","marker":"[17]"},{"why":"Source of the intrinsic locking term that the paper formalizes as the Type II relaxation in Corollary 1.","marker":"[10]"},{"why":"Source of the injection locking term that the paper formalizes as the Type III relaxation in Corollary 2.","marker":"[11]"},{"why":"Supplies the proximal-type gradient estimator that IsingSim uses to approximate gradients toward global minima.","marker":"[18]"},{"why":"Provides a prior higher-order Ising machine designed for CNF constraints, used as a baseline for compactness comparisons.","marker":"[13]"},{"why":"Supplies standard quadratic Ising encodings used to measure how much smaller hybrid higher-order models are than second-order ones.","marker":"[5]"}],"fun_headline_variants":["Convolution makes higher-order Ising gradients quadratic time","Symmetric hyperedges: Ising simulation drops to polynomial cost","One extra convolution per gradient in higher-order Ising","Quadratic-time gradients for symmetric higher-order Ising","Walsh expansion: Ising hyperedge cost from exponential to n^2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The framework assumes that the continuous relaxations' global minima coincide exactly with the Boolean satisfying assignments; if a relaxed Hamiltonian has an interior minimum lower than the discrete minimum, gradient descent can land on a point that is not a solution.","fun_headline_variants_meta":{"raw":{"variants":["Convolution makes higher-order Ising gradients quadratic time","Symmetric hyperedges: Ising simulation drops to polynomial cost","One extra convolution per gradient in higher-order Ising","Quadratic-time gradients for symmetric higher-order Ising","Walsh expansion: Ising hyperedge cost from exponential to n^2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000951,"raw_usage":{"total_tokens":4020,"prompt_tokens":872,"completion_tokens":3148,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":488,"completion_tokens_details":{"reasoning_tokens":3064}},"tokens_in":488,"tokens_out":3148,"duration_ms":21210,"temperature":1.0,"reasoning_tokens":3064,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:05:15.484038+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small symmetric constraint such as the four-variable cardinality constraint from the paper's Example 2, form the Type II relaxed Hamiltonian with $p = 1$, and numerically search for a point inside the box whose value is below $-\\sum_e w_e - n$; finding one would refute the Type II relaxation theorem, while finding none on many random restarts would support it.","supporting_citations":[{"cited_title":"Fouriersat: A fourier expansion-based algebraic framework for solving hybrid boolean constraints,","cited_arxiv_id":null,"evidence_quote":"Establishes the Type I relaxation equivalence and the absence of interior local optima for multilinear Hamiltonians, which the paper's Theorem 2 extends to higher-order constraints."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the maximum principle used to locate optima of the relaxed multilinear Hamiltonian on the boundary of the hypercube."},{"cited_title":"Net- work of time-multiplexed optical parametric oscillators as a coherent ising machine,","cited_arxiv_id":null,"evidence_quote":"Source of the intrinsic locking term that the paper formalizes as the Type II relaxation in Corollary 1."},{"cited_title":"Solving combinatorial optimisation problems using oscillator based ising machines,","cited_arxiv_id":null,"evidence_quote":"Source of the injection locking term that the paper formalizes as the Type III relaxation in Corollary 2."},{"cited_title":"A hamilton–jacobi-based proximal operator,","cited_arxiv_id":null,"evidence_quote":"Supplies the proximal-type gradient estimator that IsingSim uses to approximate gradients toward global minima."},{"cited_title":"Efficient optimization with higher-order ising machines,","cited_arxiv_id":null,"evidence_quote":"Provides a prior higher-order Ising machine designed for CNF constraints, used as a baseline for compactness comparisons."}],"review_version":1}