{"id":"cc015141-538f-4fbc-a5a9-e2221839c055","arxiv_id":"2502.12012","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"The authors evolve max-cut graph instances in a graph autoencoder's latent space that are easy or hard for RQAOA relative to the Goemans-Williamson algorithm, then analyze their features.","lead":"This paper uses an evolutionary search algorithm inside a graph-generating neural network to create max-cut problem instances where the quantum algorithm RQAOA performs much better or much worse than the classical algorithm GW. The result is a method and a benchmark set for exposing where quantum and classical optimization algorithms diverge.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central claim lacks a baseline: without comparing evolved RQAOA/GW ratio distributions to random graphs or random latent points, it is unclear whether CMA-ES found genuinely hard instances or merely selected noise.","rationale":"The reader's own rationale lists 'no baseline comparison to random graphs is given' as one of several issues, so we are aligned on the existence of the problem. However, the reader's stated weakest assumption is the fidelity of the PIGVAE latent space, with the low link-prediction ROC-AUC as evidence. I regard the missing baseline as more load-bearing: even with a perfect latent space and decoder, the central claim of 'effectively pinpoints' would still be unsubstantiated because an optimizer will always find extreme ratios in a noisy objective. The latent-space fidelity issue is relevant to whether decoded graphs are representative, but the baseline issue is necessary to establish that the evolved instances are genuinely challenging or tractable relative to typical instances. I therefore partially agree with the reader. The verdict remains CONDITIONAL, since the missing baseline is addressable: adding a control comparison and reporting effect sizes and significance tests could either support or refute the central claim. No change to the reader's conditional verdict is needed, but the condition should be made explicit: the claimed hard-instance generation should be validated against random graphs and random latent points before the benchmark instances are adopted.","tokens_in":18062,"tokens_out":4843,"duration_ms":52129,"concrete_test":"Construct two control sets: (i) 1000 random latent points sampled from the same per-dimension bounds used for CMA-ES, decoded to graphs; and (ii) 1000 graphs drawn from the six generators used for GAE training, with 20 and 100 nodes. Run RQAOA and GW on every control graph with the same 100 trials per graph, and compute the same fitness ratios pGW/pRQAOA and pRQAOA/pGW. Compare the empirical distributions of the ratios for the evolved instances against the control distributions, using a two-sided nonparametric test (e.g., Mann-Whitney U) on the maxima or upper quantiles. If the evolved instances are not significantly beyond the control tail, the claim of effectively pinpointing hard instances is not supported; if they are, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that CMA-ES in the PIGVAE latent space 'effectively pinpoints' max-cut instances for which RQAOA and GW differ (Section 1, Section 4). The supporting evidence is the distribution of the fitness ratio pGW/pRQAOA (or its inverse) on decoded instances (Section 5.2). Nowhere is this distribution compared with a baseline: random latent points from the same bounded search region, random graphs from the six generators used for GAE training, or simple random graphs matched by size and density. Such a baseline is essential because CMA-ES is specifically optimizing this ratio; even with a perfect decoder and completely ordinary graphs, the optimizer will return instances with unusually high ratios merely by selecting the tail of a noisy objective. The reported 20-node ratios are close to 1 (0.952-0.979 for the RQAOA-dominant set), and the 100-node differences are similarly small, with no statistical test against chance. Without a control, the observed 'hard instances' cannot be distinguished from the upper tail of stochastic variation, and the benchmark claim is unsupported. This is the most load-bearing concern because it directly targets whether the method delivers its promised contribution.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a pipeline for evolving maximum cut instances that are intended to be respectively hard or easy for the recursive quantum approximate optimization algorithm (RQAOA) relative to the Goemans and Williamson (GW) classical algorithm. A permutation-invariant graph variational autoencoder (PIGVAE) is trained on graphs from six random graph models, and CMA-ES is then run in the latent space to maximize the ratio p_GW(I)/p_RQAOA(I) or its inverse, where the p-values are medians over 100 stochastic trials. The authors evaluate the approach on 20-node and 100-node graphs, report feature analyses using parallel coordinate plots and TPOT classifiers, and claim that the generated instances serve as benchmarks that expose RQAOA's strengths and weaknesses. The manuscript concludes that RQAOA can offer substantial benefits over GW and that the method opens new directions for graph generation research.","tokens_in":18332,"tokens_out":5576,"duration_ms":54896,"significance":"If the central claim is established, the paper would provide a practical instance-generation method and a benchmark set for quantum versus classical max-cut heuristics, which is a useful contribution to both evolutionary computation and quantum optimization. The core idea of using CMA-ES over a learned graph latent space is not inherently circular, and the availability of a Zenodo repository with code and supplementary material is a strength. However, the current evidence is not sufficient to support the benchmark claim: the absence of a random-instance baseline means the observed performance ratios could be the upper tail of a noisy objective, the 100-node decoder is reported to have link-prediction ROC-AUC of only 0.611, and the feature analysis is partly circular because its top feature is derived from GW's internal relaxation performance. These issues are addressable with additional experiments and reframing, but they are load-bearing.","major_comments":[{"comment":"The claim that CMA-ES 'effectively pinpoints' instances that are hard or easy for RQAOA relative to GW is not supported without a baseline. The fitness function p_GW(I)/p_RQAOA(I) is being maximized, so even with perfectly ordinary graphs, CMA-ES will return instances with unusually high ratios simply by selecting the tail of a noisy objective. The reported 20-node RQAOA-dominant ratios are close to 1 (0.952–0.979), and the 100-node ratios are described only qualitatively. Please report the same ratio distribution for (i) random latent points drawn from the same bounded search region, (ii) random graphs from the six generators used for GAE training, matched by node count and, where feasible, edge density, and (iii) simple Erdős–Rényi graphs with the same node count. A nonparametric test such as Mann-Whitney U with effect sizes should be used to show that the evolved instances are not merely the upper tail of the background noise. Without such a control, the central benchmark contribution is an assertion rather than a demonstrated result.","section":"§4 (Eq. 1) and §5.2"},{"comment":"The 100-node results rest on a decoder that the paper itself reports as barely above chance at link prediction (macro ROC-AUC 0.611±0.001, versus 0.5 for random guessing). Because every CMA-ES search point is decoded through this GAE, low reconstruction fidelity means the evolved 100-node instances may be unrepresentative of any meaningful graph distribution. The smoothness evidence in Fig. 3 concerns latent-space clustering of training embeddings, not the fidelity of decoded graphs. Please add a direct validation of decoded graphs, for example by comparing feature distributions of decoded graphs against training graphs, or by reporting full-graph reconstruction metrics. If the decoder fidelity cannot be improved, the 100-node claims should be restricted or substantially softened.","section":"§5.2, GAE evaluation"},{"comment":"The machine-learning feature analysis is partly circular. The label is defined by the ratio p_GW(I)/p_RQAOA(I) in Eq. (1), while the top predictive feature EXPECTED_COSTGW_OVER_SDP_COST is computed from GW's own average cost divided by the SDP optimum. A classifier can therefore predict the favored algorithm using GW's internal performance measure as a near-oracle, which does not establish that the discovered graphs differ in structurally meaningful ways. The permutation results are consistent with this concern: excluding the top two features leaves the 100-node accuracy unchanged (1.0000±0.0000). I recommend either removing GW-derived features from the explanatory analysis, or explicitly reframing the analysis as instance classification with algorithm-performance features and adding a structural-features-only ablation to support any claim about graph structure.","section":"§5.2, Feature analysis; §B (Table A1/A2)"},{"comment":"The hardness criterion is not statistically robust as reported. The manuscript states that on a representative RQAOA-favored 20-node instance, RQAOA outperforms GW in only 4 of 100 stochastic trials, with identical results in the rest. A median-based fitness can therefore label an instance as 'considerably more manageable' when the actual per-trial win probability is only 4%. Please report per-instance confidence intervals or paired tests across the 100 trials, and define 'hard' and 'easy' in terms of a statistically meaningful separation rather than a point-wise median. Without this, the benchmark instances cannot support comparative claims about algorithm behavior.","section":"§5.2, representative case and §4, fitness evaluation"}],"minor_comments":[{"comment":"The threshold of 0.96 is selected after reporting that 0.95 and 0.98 were discarded and 0.97 gives results comparable or better in some settings. This post-hoc threshold selection should be explicitly disclosed, and the reported balanced accuracies should be framed as exploratory rather than as a confirmatory evaluation.","section":"§5.2, 'RQAOA as a high-performing heuristic'"},{"comment":"The caption states that lower values indicate cases where one algorithm significantly outperforms the other, but the color bar is not defined. Please specify exactly which ratio is plotted (p_GW/p_RQAOA or p_RQAOA/p_GW) and the direction of the color scale.","section":"Fig. 4 caption"},{"comment":"The statement that the visualization offers 'an intuitive look at the way RQAOA navigates the solution space' is presented without quantitative support; consider citing the corresponding iteration costs or expectation values, or moving the interpretative sentence to the discussion.","section":"§2, Fig. 1 description"},{"comment":"Several importance scores have negative values (e.g., EXPECTED_COSTGW_OVER_SDP_COST in Table A3). A brief explanation of what negative permutation importance means in this context would help readers interpret the tables.","section":"Appendix D/E tables"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a conference-style application paper whose central claims are plausible but currently under-supported. The missing random-graph/random-latent baseline is the most serious issue, but it is addressable with additional experiments using the existing code. I do not see a need to reject the paper outright, but the revision should either strengthen the evaluation or substantially reword the claims about benchmark quality and feature-based insights."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real contribution—the first time anyone has used CMA-ES in a graph autoencoder's latent space to evolve max-cut instances that separate RQAOA from GW—and the authors have shipped code and data on Zenodo, which is more than many papers in this area do. The method is clearly described and the feature analysis, while not the core, is thoughtful. But the paper's central claim is currently under-supported: there is no baseline comparison. The authors optimize pGW/pRQAOA (or its inverse) with CMA-ES, and any optimizer will return the tail of whatever distribution the decoder produces. Without comparing the evolved ratio distribution to random latent points or to random graphs from the same generators, we cannot tell whether the instances are genuinely hard or just the upper tail of a noisy objective. The reported 20-node RQAOA-dominant ratios are 0.952–0.979, which are close to 1, and the one worked example where RQAOA beats GW in only 4 of 100 trials makes the effect size look small. This is the load-bearing soft spot.\n\nSecondary issues: the most important ML feature, EXPECTED_COSTGW_OVER_SDP_COST, is essentially a component of the label, so the classifier analysis is partly circular. The authors acknowledge the permuted importance is small, but the point stands. The threshold of 0.96 was chosen after looking at 0.95, 0.97, and 0.98, so that part is post hoc. And for 100-node graphs, the GAE's link-prediction ROC-AUC is 0.611, barely above chance, which makes the decoded instances less trustworthy at that scale.\n\nNone of these problems is fatal. The pipeline is reproducible, the authors are transparent about limitations, and a baseline plus a few statistical tests would substantially strengthen the benchmark claim. I would send this to peer review with a request for major revision rather than desk-reject it. It is useful for researchers working on quantum optimization benchmarking and evolutionary instance generation.","headline":"A genuine new instance-generation pipeline for quantum algorithm benchmarking, but the central 'hard instances' claim needs a baseline before it can be believed.","tokens_in":18862,"tokens_out":2625,"would_cite":false,"duration_ms":25702,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Searched by a classical evolutionary optimizer, the latent space of a graph autoencoder yields maximum cut instances on which the quantum RQAOA and the classical GW algorithm diverge sharply.","keywords":["maximum cut","RQAOA","Goemans-Williamson algorithm","graph autoencoder","CMA-ES","latent space search","quantum approximate optimization","benchmark instance generation"],"falsifier":"Decode a random sample of CMA-ES final search points, solve the decoded 20-node graphs exactly by brute force, and check that the RQAOA-vs-GW performance ratios persist against the true optimum and that the decoded graphs remain connected and structurally close to the six training graph families; if the ratios collapse or the graphs are degenerate (for example, dominated by isolated nodes), the evolved hard instances are artifacts of the autoencoder's decoder rather than genuine benchmarks.","tokens_in":2059,"feed_emoji":"🧬","tokens_out":2792,"duration_ms":166168,"temperature":0.7,"pith_summary":"Searched by the classical optimizer CMA-ES, the latent space of a graph autoencoder yields maximum cut instances that split the recursive quantum approximate optimization algorithm (RQAOA) from the classical Goemans-Williamson (GW) algorithm. The authors found thousands of 20-node and 100-node graphs on which one algorithm clearly beats the other, and their point is that hard instances for this quantum-classical comparison can be constructed on demand by evolutionary search, not merely described by theoretical guarantees. A machine-learning analysis over 18 graph features separates RQAOA-dominant from GW-dominant instances almost perfectly, with the GW algorithm's own semidefinite-relaxation cost ratio as the single most predictive feature. The result matters because concrete hard-instance families are exactly what the literature has lacked as benchmarks for deciding when near-term quantum optimization heuristics pay off.","feed_headline":"Evolved Max-Cut graphs split quantum RQAOA from classical GW","feed_subtitle":"CMA-ES inside a graph autoencoder's latent space produces benchmark instances where the two solvers diverge sharply.","key_machinery":"Three components carry the argument. PIGVAE maps graphs into a continuous latent space invariant to node relabeling, which is what makes a continuous search over graphs possible. CMA-ES searches that space to maximize the fitness ratio $p_{\\mathrm{GW}}(I)/p_{\\mathrm{RQAOA}}(I)$ or its reciprocal, with each evaluation decoding a latent point to a graph and running both algorithms 100 times; decoded graphs that are disconnected are handled component-wise, and components below the threshold $n_c$ are solved by brute force. An evaluation block then computes 18 graph-level features ranging from density, girth, assortativity, and Laplacian eigenvalues to statistics of GW's semidefinite relaxation, and an AutoML pipeline turns those features into classifiers and partial-dependence models that show which structures drive the divergence.","core_discovery":"The central claim is a constructive method that pinpoints maximum cut instances which pose significant challenges or are notably more tractable for RQAOA relative to the GW algorithm. The pipeline trains a PIGVAE (permutation-invariant variational graph autoencoder) on graphs from six standard random-graph models, then runs CMA-ES in the 64-dimensional latent space with fitness $p_{\\mathrm{GW}}(I)/p_{\\mathrm{RQAOA}}(I)$ to evolve hard-for-RQAOA instances and the reciprocal to evolve easy-for-RQAOA instances. Each fitness evaluation decodes a latent point into a graph and runs both algorithms 100 times, taking the median cut value. The method produced 1,519 RQAOA-favored and 1,231 GW-favored instances at 20 nodes, and 850 of each at 100 nodes; a classifier built on 18 features separates the two families with balanced accuracy $0.9988 \\pm 0.0012$ at 20 nodes and perfect accuracy at 100 nodes. The dominant predictor is the expected cut value of GW's randomized rounding normalized by its semidefinite bound, followed by spectral properties of the normalized Laplacian. A secondary analysis, labeling instances where RQAOA beats GW by at least 4 percent, yields balanced accuracies of 0.9826 at 20 nodes and 0.8343 at 100 nodes, with density emerging as a key feature.","pith_inferences":["If the 100-node autoencoder's link-prediction score (macro ROC-AUC 0.611, barely above chance) reflects a weak decoder, the 100-node benchmark instances may be partly decoder artifacts; a natural check is to compare the performance-ratio distribution of CMA-ES's final population against randomly sampled latent points decoded by the same model.","The same latent-space-plus-evolution recipe should transfer to other solver pairs, such as QAOA at depth $p \\ge 2$ versus GW or RQAOA versus simulated annealing, yielding a general tool for constructing contrasting benchmarks rather than a RQAOA-specific one.","Because only depth-1 RQAOA (classically simulable in $O(n^4)$) is evaluated, the evolved hard instances may not stay hard for deeper RQAOA; re-running the same graphs at depth $p \\ge 2$ would show whether the separation survives outside the classically simulable regime.","The authors note in their conclusion that PIGVAE suffers severe memory bottlenecks for 400-node graphs, so the benchmark's scope is tied to the autoencoder's capacity until lighter architectures, sparse attention, or diffusion models replace it."],"forward_implications":["The generated 20-node and 100-node graph sets can serve directly as benchmarks for any future comparison of RQAOA against classical max-cut heuristics, filling the gap the paper identifies: existing theory named hard graph families but gave no concrete construction.","Once trained, the 18-feature classifiers can predict which algorithm dominates on a new graph from graph and SDP-relaxation statistics alone, without a fresh RQAOA evaluation.","Because RQAOA-dominant instances cluster in a narrow performance-ratio band (0.952-0.979 at 20 nodes) while GW-dominant instances span a wider band (0.720-0.990), the two algorithms fail in detectably different regimes rather than by random fluctuations.","The near-perfect classifier separation implies the divergence between the two algorithms is systematic and feature-detectable, so the evolved instances expose structural differences between quantum-informed recursion and classical SDP rounding, not merely stochastic noise."],"supporting_citations":[{"why":"Introduces RQAOA, the quantum recursion algorithm whose behavior the paper targets, and describes an infinite family of d-regular bipartite graphs where QAOA lags behind GW at depth O(log n), the gap this paper turns into constructible instances.","marker":"[12]"},{"why":"Defines the Goemans-Williamson semidefinite-programming approximation with its 0.878 guarantee, the classical baseline whose performance the evolved instances contrast against RQAOA.","marker":"[24]"},{"why":"Provides PIGVAE, the permutation-invariant variational graph autoencoder whose 64-dimensional latent space is the search domain for CMA-ES.","marker":"[58]"},{"why":"Supplies CMA-ES, the evolutionary optimizer that searches the latent space for the fitness ratios that yield hard instances.","marker":"[28, 30]"},{"why":"The systematic library of max-cut and QUBO heuristic instances and the prior feature conventions that the generated benchmarks and graph-difficulty features extend.","marker":"[17]"},{"why":"Source of the feature-analysis paradigm and the GW semidefinite-relaxation features that dominate the trained classifiers.","marker":"[43]"},{"why":"Establishes that depth-1 RQAOA is classically simulable in O(n^4) time, which is what makes evaluating RQAOA on thousands of generated graphs feasible.","marker":"[49]"},{"why":"The paper's supplementary repository, which carries the implementation and the generated benchmark instances, making the pipeline's output reproducible.","marker":"[47]"}],"fun_headline_variants":["Evolved Max-Cut graphs expose RQAOA vs GW split","Latent-space CMA-ES creates hard Max-Cut cases for quantum","Graph autoencoder evolves instances that trip up RQAOA","Quantum optimization stress-test from evolved Max-Cut graphs"],"cache_read_input_tokens":20992,"weakest_assumption_plain":"The whole search rests on the premise that points in the PIGVAE latent space decode into valid, representative graphs, and the load-bearing evidence for that premise is the paper's own link-prediction result of macro ROC-AUC 0.611 on 100-node graphs, barely above chance.","fun_headline_variants_meta":{"raw":{"variants":["Evolved Max-Cut graphs expose RQAOA vs GW split","Latent-space CMA-ES creates hard Max-Cut cases for quantum","Graph autoencoder evolves instances that trip up RQAOA","Quantum optimization stress-test from evolved Max-Cut graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000209,"raw_usage":{"total_tokens":1434,"prompt_tokens":1002,"completion_tokens":432,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":618,"completion_tokens_details":{"reasoning_tokens":361}},"tokens_in":618,"tokens_out":432,"duration_ms":4407,"temperature":1.0,"reasoning_tokens":361,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T23:42:12.912765+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Decode a random sample of CMA-ES final search points, solve the decoded 20-node graphs exactly by brute force, and check that the RQAOA-vs-GW performance ratios persist against the true optimum and that the decoded graphs remain connected and structurally close to the six training graph families; if the ratios collapse or the graphs are degenerate (for example, dominated by isolated nodes), the evolved hard instances are artifacts of the autoencoder's decoder rather than genuine benchmarks.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces RQAOA, the quantum recursion algorithm whose behavior the paper targets, and describes an infinite family of d-regular bipartite graphs where QAOA lags behind GW at depth O(log n), the gap this paper turns into constructible instances."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides PIGVAE, the permutation-invariant variational graph autoencoder whose 64-dimensional latent space is the search domain for CMA-ES."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the feature-analysis paradigm and the GW semidefinite-relaxation features that dominate the trained classifiers."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that depth-1 RQAOA is classically simulable in O(n^4) time, which is what makes evaluating RQAOA on thousands of generated graphs feasible."},{"cited_title":"Patel, Aneta Neumann, Frank Neumann, Thomas Bäck, and Hao Wang","cited_arxiv_id":null,"evidence_quote":"The paper's supplementary repository, which carries the implementation and the generated benchmark instances, making the pipeline's output reproducible."}],"review_version":1}