{"id":"bdf36778-7cd7-4491-969c-08029d769e0d","arxiv_id":"2603.00408","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A QUBO-based neural-network verification framework claims logarithmic spin complexity and asymptotically complete bounds, but the logarithmic encoding is not in the equations and the convergence theorem is unproved.","lead":"This paper encodes neural-network robustness verification as QUBO/Ising optimization, proposing an exact encoding for piecewise-linear networks and an approximate, asymptotically complete encoding for general activations. It claims compact spin budgets and exact certification fidelity, but the key log-encoding claim is contradicted by the paper's own equations and the asymptotic-completeness theorem is stated without proof.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Model 2 is not sound for arbitrary activations: independent lower/upper segment selections in Eqs. (17)-(22) can make the computed lower bound exceed the true minimum, so asymptotic completeness is unsupported.","rationale":"The reader's weakest assumption is essentially the same concern I identify: Model 2's independent lower/upper segment variables are not shown to be a sound over-approximation over the true reachable set. My counterexample makes this precise and shows the failure is not merely a missing proof but an actual unsoundness for non-monotone activations. This directly undermines the paper's advertised asymptotic completeness for arbitrary activations. The pruning-transfer result (Theorem 2) appears to be proved correctly and is not affected, but it does not rescue the central verification claim. The reader's REJECT verdict is therefore appropriate; I see no reason to adjust it. I do not weigh the additional 'logarithmic encoding' concern as the load-bearing issue, because even if Model 1's encoding is one-hot rather than logarithmic, the exactness claim for piecewise-linear networks could still be repaired; the Model 2 soundness gap is fatal to the general-activation contribution.","tokens_in":21275,"tokens_out":15566,"duration_ms":174053,"concrete_test":"Implement Model 2 exactly (e.g., as a MILP) for x∈[0,1], h=sigmoid(x), output activation σ2(z)=4(z−0.65)^2−0.1, with the output preactivation segmented as [0.5,0.6] and [0.6,0.731]. Record the minimized lower output bound. The true minimum is −0.1 at z=0.65. If Model 2 returns −0.09 (as the independent-segment formulation does), soundness is refuted. Then refine to n=100 uniform segments; if the returned lower bound does not approach −0.1, Theorem 1's convergence claim is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Model 2's soundness claim fails for non-monotone activations. Equations (17)-(22) propagate lower and upper preactivation bounds independently, and Eq. (19) sets a^l_j = γ_i (resp. \\bar a^l_j = \\barγ_j) using the segment selected by the lower bound z^l_j (resp. upper bound \\bar z^l_j). The constraints never require γ_i ≤ σ(z) for every z in [z^l_j, \\bar z^l_j]; they only require it on the chosen segment i. If σ attains a smaller value in a later segment, the returned lower bound can exceed the true minimum. Concrete counterexample: x∈[0,1], hidden h=sigmoid(x)∈[0.5,0.731], output preactivation z=h with σ2(z)=4(z−0.65)^2−0.1. Here z_lower=0.5 selects segment [0.5,0.6] giving γ_1=−0.09, but σ2(0.65)=−0.1 is achievable. Thus Model 2's lower bound is above the true minimum, i.e., unsound. Refining segments does not repair this: as segment width vanishes, γ_1→σ2(0.5)=−0.01, not the true minimum −0.1. Theorem 1 is stated without proof and its constant C is undefined; no condition on Δ can fix the missing monotonicity/segment-linking constraint. The paper's abstract and Theorem 1 claim arbitrary activations, so this is a central failure.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two QUBO-based formulations for neural-network robustness verification. Model 1 encodes piecewise-linear activations exactly as a mixed-integer QUBO using one-hot segment-selection variables and big-M linearization; the authors claim this encoding is logarithmic and information-theoretically minimal. Model 2 approximates arbitrary activations by piecewise-constant step envelopes, with independent binary variables selecting lower and upper segments; the authors claim sound over-approximation and 'asymptotic completeness' as segment width vanishes (Theorem 1). The paper also contributes a Benders decomposition, a pruning-to-original certificate transfer theorem (Theorem 2), a layerwise quantum--classical partitioning scheme, and experiments on Iris/make-moons networks solved by Gurobi and a Coherent Ising Machine (CIM).","tokens_in":21740,"tokens_out":3411,"duration_ms":39664,"significance":"If the central claims were correct, the framework would be a meaningful step toward using Ising/quantum solvers for formal verification: exact PWL verification with compact spin counts and asymptotically complete verification for general activations. The paper does contain one clean, machine-checked-style contribution: Theorem 2's pruning transfer bound (Eq. 27) is correctly proved for Lipschitz activations and could be useful beyond this paper. Model 1 is also a standard, semantically valid exact MILP/QUBO reformulation when the interval bounds are valid. However, the headline logarithmic-complexity claim is contradicted by the one-hot variables in the Model 1 formulation, and Model 2's soundness and the asymptotic-completeness theorem are unsupported and, as stated, false for non-monotone activations. These are load-bearing failures, not presentation issues.","major_comments":[{"comment":"Model 2 is not sound for arbitrary (non-monotone) activations. Eq. (19) sets the lower activation bound a^l_j = Σ_i γ_i β^(i)_{z^l_j} and the upper bound ar a^l_j = Σ_i ar γ_i ar β^(i)_{ar z^l_j}, but the binary selections for z^l_j and ar z^l_j are independent: nothing ties the chosen lower/upper segments to the same adversarial input. For a non-monotone σ, the value γ_i on the segment selected by the lower preactivation bound can exceed the true minimum over the interval. Example: x∈[0,1], hidden h=sigmoid(x) ∈ [0.5,0.731], output preactivation z=h, σ2(z)=4(z−0.65)^2−0.1. The lower bound z^l=0.5 selects segment [0.5,0.6] giving γ_i=−0.09, but σ2(0.65)=−0.1 is achievable; the computed lower bound is above the true minimum. Refining segments does not repair the gap because the envelope converges to σ2(0.5)=−0.01. Thus the soundness claim and Theorem 1's convergence claim fail without an","section":"Model for Arbitrary Non-linear Activation Functions, Eqs. (17)-(22); Theorem 1"},{"comment":"The abstract's claim of an 'information-theoretically minimal logarithmic encoding' and 'state-optimal logarithmic complexity' is contradicted by the formulation. Eq. (13) imposes Σ_i β^(i)_{z^l_j}=1 with β^(i) ∈ {0,1}, i.e., one-hot selection over n segments per neuron; each neuron uses n binary variables, not O(log n). Equations (5)-(6) and the linearization (9)-(12) all rely on this one-hot representation. No logarithmic encoding is defined or used anywhere in the paper. This is not a minor wording issue: the reduced-spin-count selling point of Model 1 is based on a complexity claim that the model does not deliver.","section":"Abstract and Model 1, Eqs. (5)-(13)"},{"comment":"Theorem 1 is stated without proof and depends on an undefined constant C ('depending on the network depth and activation smoothness'). No construction or bound for C is given, nor is any argument supplied that Δ ≤ ε/(L·C) implies the step-envelope optima converge to the true extrema. As shown above, the claimed convergence is false for non-monotone activations under the independent segment selections of Eqs. (17)-(22). The theorem is therefore unproven and, in its current form, incorrect. This is the central theoretical result for Model 2, so the paper's asymptotic-completeness claim is unsupported.","section":"Theoretical Analysis, Theorem 1"},{"comment":"The experiments do not test asymptotic completeness: Model 2 is evaluated only with a fixed 5-segment piecewise-constant enclosure, and no refinement study varying the segment count is reported. Matching an exact MIP baseline on tiny datasets with a coarse approximation does not provide evidence for convergence as segment width vanishes. This is a secondary concern relative to the soundness failure above, but it means the empirical section cannot rescue the theoretical claim.","section":"Experimental Evaluation, Table 5"}],"minor_comments":[{"comment":"Cinput is written as [In0 0 ... 0] ∈ R^{2n0 × ...}, but the input constraint (2) requires both +In0 and −In0 blocks. The matrix as displayed is missing the negative-identity row block; this is presumably a typesetting omission.","section":"Model for Piecewise Activation Linear function, Eq. (3)"},{"comment":"The definition of y in Model 1 and Model 2 uses notation such as n_l·n and sums of dimensions that is hard to parse. Please clarify the exact dimension of the auxiliary variables and the placement of blocks, e.g., by specifying that u^l ∈ R^{n_l n} and listing variable ordering explicitly.","section":"Throughout, variable y and dimensions"},{"comment":"The condition Δ ≤ ε/(L·C) is dimensionally odd: ε is an input radius, L is a Lipschitz constant, and Δ is a segment width in preactivation space. The reader is left without any idea of how C scales with network depth. Even if the constant were defined, the statement should include the monotonicity or segment-coupling hypotheses needed for soundness.","section":"Theorem 1 statement"},{"comment":"The text says QUBO-Gurobi 'reaches the timeout threshold for all ε≥0.2' but Table 3 reports 1137 ms at ε=0.1; the wording is slightly ambiguous about whether ε=0.1 is below the threshold. Clarify.","section":"Table 3/4/5 discussion"}],"recommendation":"reject","confidential_remarks":"The central theoretical claims are not merely under-proved; Model 2's step-envelope formulation is unsound for non-monotone activations, and the logarithmic-encoding claim is directly contradicted by the one-hot variables in Model 1. These cannot be fixed with local edits within the manuscript's stated scope. The pruning-transfer theorem is a solid but separate contribution and could be developed into a standalone note. The CIM experiments rely on the authors' own platform and self-citations, but my decision is based on the scientific failures, not on the sourcing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's main advertised contributions don't survive a close read. The abstract promises an \"information-theoretically minimal logarithmic encoding\" for piecewise-linear networks, but the actual equations (5)-(13) use a plain one-hot encoding with n binary variables per neuron. That's a direct mismatch, not a minor wording issue. The second headline claim, asymptotic completeness for arbitrary activations via the step-envelope model, is also unsupported: Theorem 1 is stated without proof and contains an undefined constant C, and the formulation has a real soundness problem. Equations (17)-(22) select lower and upper envelope segments independently, tied to the lower and upper preactivation bounds. Nothing forces the selected segments to be consistent with a single actual input, so for non-monotone activations the computed lower bound can be looser than the true minimum. The stress-test counterexample (sigmoid followed by a non-monotone output activation) is correct. Refining the segmentation doesn't fix it. This is a central failure, not a fixable gap.\n\nThat said, the paper isn't worthless. Model 1 is a clean, exact MILP/QUBO encoding for piecewise-linear networks, and the equivalence with MIP-Gurobi results on the toy benchmarks is evidence the encoding is faithful. Theorem 2 on pruning-induced robustness transfer is correctly proved and is a genuinely useful standalone result, though it doesn't rescue Model 2. The Benders decomposition and interval-pruning ideas are reasonable engineering, and the experiments are honest about not beating classical solvers on wall-clock time.\n\nThe scale and reporting of the experiments are weak: Iris and make_moons with at most a few hundred spins, no error bars, and self-hosted CIM results. QUBO-Gurobi times out on instances MIP-Gurobi solves in under 2 ms, so the practical case for Ising hardware isn't made.\n\nThis paper should get a serious referee—the flaws need to be documented in the literature, and the correct parts (Model 1, Theorem 2) deserve a counterpart. But as it stands, the central soundness and completeness claims are unsupported, and I would not cite the asymptotic-completeness framework in my own work.","headline":"The paper's headline claims—logarithmic encoding and asymptotically complete step-envelope verification—are not supported by the text: the equations use a standard one-hot encoding, and Model 2's soundness fails for non-monotone activations.","tokens_in":22202,"tokens_out":2321,"would_cite":false,"duration_ms":26807,"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":"This paper claims that formal robustness verification of neural networks can be recast as an Ising optimization problem—exactly for piecewise-linear activations and asymptotically completely for general nonlinear activations—using a logarit","keywords":["neural network verification","robustness certification","Ising model","QUBO","piecewise-linear activations","asymptotic completeness","Benders decomposition","adversarial examples"],"falsifier":"Take a small network with a sigmoid activation and, at progressively finer segmentation, solve Model 2 while also computing the exact output extrema by dense sampling of the perturbation ball; a concrete failure would be a lower bound that exceeds the true minimum or an upper bound below the true maximum, or a sequence of bounds that does not converge to the exact extrema as the segment width goes to zero.","tokens_in":1363,"feed_emoji":"🧠","tokens_out":2006,"duration_ms":72687,"temperature":0.7,"pith_summary":"The paper claims that checking whether a neural network's predictions stay constant under bounded input perturbations can be turned into an Ising/QUBO optimization problem that specialized Ising solvers can attack. For piecewise-linear activations such as ReLU and hardtanh, it presents a formulation that is exact, sound, and complete, with the number of binary variables per neuron growing logarithmically rather than linearly in the number of activation segments. For general activations such as sigmoid and tanh, it replaces the activation with piecewise-constant upper and lower step envelopes and proves that the resulting output bounds converge uniformly to the true network extrema as the step width vanishes. If correct, this would extend rigorous verification beyond ReLU networks to a much broader class of activations, while keeping the spin budget low enough for current Ising hardware.","feed_headline":"Ising solvers certify neural-net robustness with a log-spin encoding","feed_subtitle":"Exact certificates for piecewise-linear nets; provable convergence to true bounds for nonlinear activations.","key_machinery":"The central object is the binary segment-selection variable assigned to each neuron and each activation segment. In the piecewise-linear model, this variable indicates which linear piece of the activation the pre-activation lies on, and the logarithmic encoding compresses the one-hot segment selection into a minimal binary code; this is what makes the formulation exact while keeping the spin count low. In the step-envelope model, the same variable type selects lower and upper piecewise-constant values for each neuron, and the convergence claim rests on the maximum segment width shrinking to zero under a Lipschitz-based condition.","core_discovery":"The central claim is that every piecewise-linear activation constraint can be encoded by binary variables that index the active linear segment, and that a logarithmic encoding of these segment indices is sufficient to preserve the exact set of adversarial examples. For arbitrary nonlinear activations, the paper proposes a step-envelope model in which the pre-activation range is partitioned into segments and binary variables select a lower and an upper constant value for each neuron. The paper's Theorem 1 asserts that as the maximum segment width goes to zero, the globally optimized lower and upper bounds on the network output converge uniformly to the true extrema over the perturbation ball,","pith_inferences":["If the logarithmic segment-index encoding is as compact as claimed, the same indexing idea could be applied to other combinatorial verification encodings, such as selecting active constraints in mixed-integer formulations, potentially lowering bit counts elsewhere.","The step-envelope construction suggests an adaptive-segmentation research direction: instead of a uniform grid, segment widths could be chosen per neuron based on interval-arithmetic pre-analysis, trading spin count against tightness more efficiently.","Because Theorem 1's convergence condition leaves a constant unspecified and does not explicitly couple the lower and upper segment choices to a common adversarial input, a reformulation that ties those selections together would be needed before the asymptotic-completeness claim could be relied on in a formal certificate chain.","The certificate-transfer bound naturally suggests verification-aware pruning: pruning should aim to minimize the pruning-residual norm directly, not just preserve accuracy, since the 2τ safety buffer shrinks when removed weight mass is concentrated in later layers."],"forward_implications":["For ReLU and hardtanh networks, the encoding is claimed to be exact: any feasible solution with a negative classification margin is a genuine adversarial example, and absence of such a solution certifies robustness.","For sigmoid and tanh networks, refining the step-envelope segmentation eventually drives the verified output bounds to the true reachable output interval, so verification is asymptotically complete.","The logarithmic encoding reduces the number of Ising spins per neuron from linear to information-theoretically minimal, making larger networks or finer segmentations feasible on spin-limited hardware.","A pruned network can be verified in place of the original, and the resulting certificate transfers to the original network with a safety buffer of twice the worst-case pruning residual on the perturbation ball.","Layerwise partitioning allows a classical–Ising hybrid workflow that handles networks larger than a single monolithic QUBO instance could fit."],"fun_headline_variants":["Log-spin encoding lets Ising solvers verify ReLU nets exactly","Ising verification: exact for piecewise-linear, asymptotically complete for others","Neural net robustness checks via Ising: log neurons, exact bounds","Certify neural nets with Ising: logarithmic spin cost, exact or convergent","Exact net verification with Ising solvers and log-spin encoding"],"cache_read_input_tokens":23424,"weakest_assumption_plain":"The load-bearing premise is that the independently chosen lower and upper step-envelope segments in Model 2 still produce bounds that converge to the true network extrema as the segment width shrinks; the paper states this convergence in Theorem 1 but leaves the constant in its condition undefined and does not tie the lower and upper segment selections to the same input.","fun_headline_variants_meta":{"raw":{"variants":["Log-spin encoding lets Ising solvers verify ReLU nets exactly","Ising verification: exact for piecewise-linear, asymptotically complete for others","Neural net robustness checks via Ising: log neurons, exact bounds","Certify neural nets with Ising: logarithmic spin cost, exact or convergent","Exact net verification with Ising solvers and log-spin encoding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00068,"raw_usage":{"total_tokens":2895,"prompt_tokens":685,"completion_tokens":2210,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":429,"completion_tokens_details":{"reasoning_tokens":2112}},"tokens_in":429,"tokens_out":2210,"duration_ms":15585,"temperature":1.0,"reasoning_tokens":2112,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T19:54:33.976690+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small network with a sigmoid activation and, at progressively finer segmentation, solve Model 2 while also computing the exact output extrema by dense sampling of the perturbation ball; a concrete failure would be a lower bound that exceeds the true minimum or an upper bound below the true maximum, or a sequence of bounds that does not converge to the exact extrema as the segment width goes to zero.","supporting_citations":[],"review_version":1}