{"id":"a67e6b1d-cca7-4883-80f0-ae8dc1438a29","arxiv_id":"2412.08532","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"An L-BFGS-accelerated alternating projections method on the NPA dual gives quick, slightly loose upper bounds for large Bell inequalities.","lead":"The paper introduces a fast, low-memory algorithm for computing approximate upper bounds on the maximum quantum violation of large Bell inequalities. It combines the NPA hierarchy dual with alternating projections accelerated by L-BFGS, reporting bounds within about 2% of the optimum, often 100x faster than standard SDP solvers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No feasibility certificate: the returned dual points are only valid upper bounds if the final slack matrix is PSD, which the paper never verifies or reports.","rationale":"The reader's verdict identifies the same gap I would: the method's validity claim rests on feasibility of the returned dual point, and the paper provides no certificate. I agree with that assessment. The paper has real strengths: the code is open source, the benchmarks are averaged over 100 seeds with visible error bars in the relative-error plot, and the limitations section explicitly concedes that the method never beats a true SDP solver at equal cost, so there is no overclaiming of tightness or generality. The speed comparison is at unequal accuracy, but that is secondary: if the returned points are feasible, a 2%-loose bound at 100x speed is a useful contribution; if they are not, the contribution collapses. The absence of min-eigenvalue reporting is thus the single load-bearing concern. It is eminently fixable and does not require rejecting the method; a conditional acceptance with the feasibility certificate as a condition is appropriate, matching the reader's verdict. I do not see an internal inconsistency in the algorithm's description, and I would not elevate the heuristic nature of L-BFGS to a fatal flaw: many numerical methods are heuristic and still useful once validated empirically. The missing empirical validation of feasibility, not the lack of a convergence proof, is the issue.","tokens_in":10549,"tokens_out":6467,"duration_ms":71791,"concrete_test":"Run the released code with instrumented output for every benchmark in Tables I and II and for representative Rxx22 sizes (matrix sizes 61, 131, 261, 401), computing for the final returned y the dual slack S = C − Σ_i A_i y_i, its minimum eigenvalue via Eigen's SelfAdjointEigenSolver, and the affine residual ‖A y − b‖/‖b‖. Accept the point as feasible only if λ_min(S) ≥ −1e−8 and the residual is below 1e−6; if any reported bound fails this test, recompute the objective and determine whether it still lies within the claimed 2% of the MOSEK/SCS value. Also rerun the 100-seed average at matrix size 261 and report the worst λ_min over all seeds; a single negative eigenvalue among the runs invalidates the corresponding 'valid upper bound' claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the method produces a valid upper bound on the quantum violation. For a dual NPA point y, validity requires C − Σ_i A_i y_i ⪰ 0 and satisfaction of the affine constraints; if either fails, the objective b·y is not a certified upper bound. Algorithm 1's inner loop (lines 5–10) ends with an affine projection after a PSD projection. Alternating projections onto two convex sets only converge to their intersection in the limit; after any finite number of iterations, and especially in the 'Ours (1)' single-shot cases in Tables I and II, the final matrix can fail PSD because the last affine projection can reintroduce negative eigenvalues. The L-BFGS acceleration is a heuristic that changes the iterate non-projectively, so it cannot by itself certify feasibility. The paper never reports the minimum eigenvalue or affine residual of the returned matrices, nor any tolerance-based feasibility test, and 'linear error less than 10^-10' (Section IV.A) is not defined as a feasibility certificate. The open-source code may well produce feasible points, but the evidence as written does not establish it. Since the advertised use case is a 'quick-and-dirty' bound for problems other solvers cannot handle, an unchecked PSD failure would void exactly the claimed deliverable. This is a missing verification rather than an observed failure; the fix is straightforward.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a heuristic method for obtaining upper bounds on the quantum violation of Bell inequalities at a fixed level of the NPA hierarchy. The method works in the dual SDP: it starts from a point far outside the feasible set along the objective direction, then uses alternating projections onto the affine and PSD cones, accelerated by L-BFGS, to reach a point near the feasible boundary. A refinement loop repeats this with shrinking step sizes to improve the bound. The paper benchmarks the method on the I3322 inequality at levels 1 and 3 of the NPA hierarchy and on randomized Rxx22 inequalities with up to 130 inputs per party, reporting time and memory advantages over MOSEK and SCS and bounds typically within about 2% of the SDP optimum.","tokens_in":10784,"tokens_out":6039,"duration_ms":68964,"significance":"If the returned points are certified feasible for the dual NPA SDP, the method would be a practically useful tool for obtaining quick upper bounds on large Bell inequalities that are beyond the reach of standard solvers. The paper is self-contained, the open-source code is a concrete asset, and the benchmark against external solvers is appropriate. The main advertised deliverable, however, is a certified upper bound, and the manuscript currently does not provide the feasibility certificate that this claim requires. The method is clearly presented as a heuristic approximation, and the author is candid about its limitations, but the missing verification step is load-bearing for the central claim.","major_comments":[{"comment":"The paper's central claim is that every returned point is a valid upper bound, but this holds only if the final dual point y satisfies both the affine constraints and C - sum_i A_i y_i ⪰ 0. No such feasibility certificate is reported anywhere: the manuscript does not give the minimum eigenvalue of the dual slack matrix, does not give the affine residual, and Algorithm 1 does not end with a verification step. Because the final affine projection can reintroduce negative eigenvalues and the L-BFGS update can move the iterate away from the feasible set, the matrices underlying Tables I, II, and Figures 5-7 are not certified as feasible unless a check is performed after the fact. I ask the author to add an explicit feasibility test to the algorithm, report the minimum eigenvalue and affine residual for every reported instance, and state the tolerances used; without this, the advertised 'valid upper bound' is not supported by the text.","section":"Algorithm 1 and Section III.C"},{"comment":"The claimed super-linear convergence of the L-BFGS-accelerated alternating projections is not established. The standard L-BFGS convergence theory applies to smooth objectives with true gradients, whereas here the 'gradient' is the difference between two affine projections and the line-search 'objective' is the squared error of an unspecified quantity; the paper provides no convergence proof and no convergence traces beyond a comment that Aitken acceleration reduced 300 iterations to 250. Since the central speed advantage rests on this acceleration, the paper should either present empirical convergence data for representative Rxx22 instances, including iteration counts, stopping criteria, and final feasibility residuals, or explicitly label the acceleration as a heuristic whose observed performance is the only evidence for the speed claim.","section":"Section III.B and Section IV.A"},{"comment":"The benchmarking methodology is under-specified in a way that affects the headline speedup. The text does not state the tolerances used by MOSEK and SCS, the solver versions, or whether the timings in Figure 5 include model parsing and setup; the statement that error bars are 'barely visible' in Figure 5 would be more convincing if the per-run variance were reported, as is done for Figure 6. These details are needed to assess whether the reported speed comparison is robust rather than an artifact of default settings.","section":"Section IV.B"}],"minor_comments":[{"comment":"SCS is not an interior-point solver; it is a first-order operator-splitting method. The sentence listing 'first-order interior point solvers include SCS and SDPA' should be corrected.","section":"Section II"},{"comment":"The phrase 'linear error less than 10^-10' is not defined and does not obviously measure feasibility; it should be replaced by a precise metric such as the objective gap, the primal/dual residual, or the minimum eigenvalue of the dual slack.","section":"Section IV.A"},{"comment":"The pseudocode is underspecified: 'enough iterations', 'if better solution desired', and the meaning of the iteration counts in Tables I and II are not defined, making it difficult to reproduce the exact procedure from the text alone.","section":"Algorithm 1"},{"comment":"The comment that the diagram 'may somewhat resemble a whale' is informal and should be removed from a journal article.","section":"Figure 4 caption"},{"comment":"There are several minor textual issues: 'Einstein-Podolsky-Rosenparadox' is missing a space, and the closing statement that the method is 'an approximation algorithm for an NP-hard problem' should be qualified, since a fixed-level NPA SDP is a convex optimization problem that is polynomial-time solvable in principle.","section":"Section I and Section V"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this is a useful engineering paper, not a breakthrough. The genuinely new piece is the specific combination—NPA dual, alternating projections, L-BFGS acceleration—as a fast way to get candidate upper bounds on Bell violations, and the empirical demonstration on randomized Rxx22 inequalities. The open-source code is a real asset, and the speed advantage at 261×261 matrices is plausible from the figures.\n\nWhat it does well: the method is simple to state, the benchmarks cover both a known hard case (I3322) and a scalable random family, and the paper is honest that the bounds are not tight. The observed ~2% looseness at scale is presented as a property, not hidden. The conclusion that the method is best for “quick-and-dirty” bounds when standard SDP solvers can’t run is appropriately scoped.\n\nThe soft spot is the load-bearing one: the paper never verifies that the returned point is actually feasible for the dual SDP. Every claimed upper bound depends on C − Σ A_i y_i being positive semidefinite. Algorithm 1 ends with an affine projection after the last PSD projection; after a finite number of alternating projections, especially the single-shot cases in Tables I and II, that final matrix can have negative eigenvalues. The L-BFGS step is a heuristic and cannot certify feasibility. The text mentions “linear error less than 10−10” but doesn’t define it as a feasibility certificate, and no minimum eigenvalue or affine residual is reported. This is a missing check rather than an observed failure, and the fix is straightforward: report the min eigenvalue and affine residual for every returned point, or explicitly construct a dual certificate.\n\nA second, smaller issue: the timing comparison is at unequal accuracy levels. MOSEK and SCS solve to high precision; the method stops after a fixed number of iterations and is allowed to be ~2% loose. That explains part of the speed gap. A fairer comparison would stop the other solvers at the same 2% tolerance. The paper’s own extensive search admits the method never beats a true SDP solver at equal cost, which is an honest limitation and worth keeping.\n\nThe citation pattern is fine. Reference [10] is self-citation but unrelated to the method; the relevant NPA and alternating-projection literature is cited.\n\nBottom line: this deserves a serious referee. I’d send it out with a request to add the feasibility check and a same-tolerance timing comparison. If the verification comes back clean, it’s publishable as a useful tool. If not, the main advertised deliverable—a valid upper bound—is void.","headline":"A genuinely faster way to get approximate NPA upper bounds, but the paper never verifies that its returned points are actually dual-feasible.","tokens_in":11323,"tokens_out":2567,"would_cite":true,"duration_ms":26221,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P40","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"A projection-based method computes valid upper bounds on large-scale Bell-inequality quantum violations orders of magnitude faster than standard SDP solvers, trading a few percent of tightness for a ~100x speedup and minimal memory.","keywords":["Bell inequalities","NPA hierarchy","semidefinite programming","alternating projections","L-BFGS","quantum nonlocality","upper bounds","dual SDP"],"falsifier":"Run the published code on one of the randomized Rxx22 benchmark instances and compute the minimum eigenvalue of the returned dual slack matrix $C - \\sum_i A_i y_i$; if any eigenvalue is negative beyond numerical tolerance, the reported bound is not a certified upper bound. Alternatively, search for any instance in which the method's reported upper bound lies below a known lower bound for the same inequality — for example, a seesaw bound for a fixed state dimension — which would likewise expose invalidity.","tokens_in":10282,"feed_emoji":"⚛","tokens_out":13117,"duration_ms":114438,"temperature":0.7,"pith_summary":"Bell inequalities certify quantum non-locality, but computing the maximal quantum violation of a large one is a semidefinite program — the NPA hierarchy — that quickly outgrows standard solvers. This paper claims that a far cheaper route exists: work in the dual of the NPA program, where every feasible point is already a valid upper bound, and find such a point by 'exile and projection' — moving far from the feasible set along the objective direction, then projecting back with alternating projections accelerated by the low-memory L-BFGS optimization algorithm. On randomized two-outcome inequalities with 130 inputs per party (a first-level moment matrix of size 261×261), the method returns a bound roughly 2% above the optimum in about one-hundredth of the time taken by MOSEK or SCS, with minimal memory. The trade-off is that the bounds are not the tightest possible, and the method is a heuristic, so its purpose is to supply valid quick-and-dirty bounds for problems that would otherwise be intractable.","feed_headline":"100x faster way to bound Bell inequality violations","feed_subtitle":"Valid upper bounds come ~100x faster than standard solvers, within ~2% of optimal, at minimal memory cost.","key_machinery":"The central object is the dual of the NPA-hierarchy SDP, whose feasible set is the intersection of an affine subspace (the linear relations among moment-matrix entries) with the positive-semidefinite cone, and in which every feasible point is a valid upper bound on the quantum value. The method, summarised in Algorithm 1, takes a starting point (usually zero), travels far from the feasible set in the direction of the objective, and then alternates two projections: onto the affine space, by solving the linear constraints with a warm-started linear solver, and onto the positive-semidefinite cone, by zeroing negative eigenvalues. L-BFGS provides the acceleration: the displacement between one affine projection and the next is used as an approximate gradient and the squared error as the line-search objective, giving super-linear convergence while storing only a handful of previous gradients. A refinement loop then moves the projected point a geometrically decreasing fraction of the way back toward the far-away point and re-projects, tightening the bound toward the optimum as the user is willing to spend more time.","core_discovery":"The paper's central claim is that a feasible point of the dual NPA semidefinite program — and therefore a certified upper bound on the maximum quantum violation of a Bell inequality — can be found orders of magnitude faster than solving the SDP, by starting far outside the feasible set in the direction of the objective and projecting back onto it. The projections alternate between the affine subspace of linear moment-matrix constraints and the positive-semidefinite cone; L-BFGS accelerates the process by treating the displacement between successive affine projections as an approximate gradient, yielding convergence in a few iterations instead of hundreds. Benchmark results: for the I3322 inequality, a single shot at level 1 returns the loose bound 6.34423 in 1 ms and twelve refinement iterations recover the exact bound 5.5; at level 3 a single shot gives 5.41829 in 217 ms. On randomized Rxx22 inequalities with 130 inputs per side, the method is roughly 100x faster than MOSEK and SCS while staying within about 2% of the optimal bound. The author states the main drawback explicitly: at equal computational cost the method never beats a true SDP solver in tightness, so its value lies in very large systems where the level-1 SDP cannot even be run.","pith_inferences":["A certification step that computes the minimum eigenvalue of the returned dual slack matrix would cost roughly one extra projection and would convert the heuristic bound into a verifiable upper bound without changing the algorithm.","The stable ~2% overshoot across randomized instances hints that the projection path escapes the dual feasible set in a regular way; identifying when that regularity breaks would predict which inequalities the method can be trusted on.","The method could serve as a triage or warm-start tool in larger pipelines — for example, deciding which large Bell inequalities deserve an exact solve, or seeding an interior-point solver with a feasible dual point."],"forward_implications":["Large Bell inequalities whose first-level NPA SDP is too big for standard solvers can still receive valid upper bounds.","For 130 inputs per side, bounds arrive roughly 100x faster than MOSEK or SCS, within about 2% of the optimum, using memory comparable to a first-order solver.","The same exile-and-projection recipe applies to other SDP relaxations and to the commuting-variable problems that give classical bounds, since only the affine and semidefinite-cone projections are required.","The user controls the speed-versus-tightness trade-off: a single shot gives a fast loose bound, while repeated refinement moves toward the optimum at increasing computational cost."],"supporting_citations":[{"why":"Supplies the NPA hierarchy, the semidefinite-programming relaxation whose dual feasible set the method projects onto.","marker":"[11]"},{"why":"SCS is the first-order baseline solver that the method's time and memory claims are benchmarked against.","marker":"[17]"},{"why":"MOSEK is the second-order baseline solver that the method claims to beat by roughly 100x at 261×261 matrices.","marker":"[19]"},{"why":"Provides the duality theory and the projection formulas (pseudo-inverse and PSD-cone) on which the method is built.","marker":"[21]"},{"why":"Dykstra's projection algorithm is the closest-point alternative the paper tests and sets aside as too slow from far away, motivating plain alternating projections.","marker":"[26]"},{"why":"The limited-memory BFGS algorithm is the acceleration step that converts linear alternating-projection convergence into super-linear convergence.","marker":"[30]"},{"why":"Introduces the I3322 inequality, the proof-of-principle benchmark for the method.","marker":"[35]"},{"why":"Supplies the reference NPA-level values of I3322 against which the method's bounds are compared.","marker":"[36]"}],"fun_headline_variants":["Bell bounds 100x faster, 2% off optimal","Fast Bell bound: 130 inputs, ~100x speedup","Near-optimal Bell bounds at 100x speed","Projection method: Bell bounds 100x faster"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The results are valid upper bounds only if the point the method returns actually lies in the dual feasible set — meaning the final moment matrix is positive semidefinite to numerical tolerance — and the paper reports no direct feasibility check, such as the minimum eigenvalue of the returned matrix, and the L-BFGS acceleration is a heuristic with no convergence proof.","fun_headline_variants_meta":{"raw":{"variants":["Bell bounds 100x faster, 2% off optimal","Fast Bell bound: 130 inputs, ~100x speedup","Near-optimal Bell bounds at 100x speed","Projection method: Bell bounds 100x faster"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000449,"raw_usage":{"total_tokens":2271,"prompt_tokens":957,"completion_tokens":1314,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":1246}},"tokens_in":573,"tokens_out":1314,"duration_ms":9871,"temperature":1.0,"reasoning_tokens":1246,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:43:47.564741+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the published code on one of the randomized Rxx22 benchmark instances and compute the minimum eigenvalue of the returned dual slack matrix $C - \\sum_i A_i y_i$; if any eigenvalue is negative beyond numerical tolerance, the reported bound is not a certified upper bound. Alternatively, search for any instance in which the method's reported upper bound lies below a known lower bound for the same inequality — for example, a seesaw bound for a fixed state dimension — which would likewise expose invalidity.","supporting_citations":[{"cited_title":"The mosek interior point optimizer for linear programming: an im- plementation of the homogeneous algorithm","cited_arxiv_id":null,"evidence_quote":"MOSEK is the second-order baseline solver that the method claims to beat by roughly 100x at 261×261 matrices."},{"cited_title":"Extended aitken acceleration","cited_arxiv_id":null,"evidence_quote":"The limited-memory BFGS algorithm is the acceleration step that converts linear alternating-projection convergence into super-linear convergence."},{"cited_title":"A relevant two qubit bell inequality inequivalent to the chsh inequality.Jour- nal of Physics A: Mathematical and General, 37(5):1775, 2004","cited_arxiv_id":null,"evidence_quote":"Introduces the I3322 inequality, the proof-of-principle benchmark for the method."},{"cited_title":"Maximal violation of the I3322 inequality using infinite dimensional quantum systems","cited_arxiv_id":"1006.3032","evidence_quote":"Supplies the reference NPA-level values of I3322 against which the method's bounds are compared."}],"review_version":1}