{"id":"82037dd8-3c93-488d-97c0-e8a2a5be644c","arxiv_id":"2505.22631","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A CUDA implementation of a simulated coupled-oscillator Ising/Potts machine solves max-cut and graph-coloring benchmarks up to 20,000 nodes with reported 94-99% accuracy and large GPU speedups.","lead":"This paper presents a GPU-based simulator for oscillator Ising and Potts machines, which are physics-inspired solvers for hard optimization problems. On max-cut and graph-coloring benchmarks, it reports speedups of up to 11,295x over a CPU version of the same algorithm with 94-99% accuracy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 11,295x speedup is computed against an under-specified CPU baseline; Section IV never states whether the C code uses 1 or 32 EPYC cores, so the headline may be inflated.","rationale":"The empirical claim has two parts: solution quality and speed. The quality part is already qualified in the paper (e.g., NA best-known for G81/G77; undefined coloring accuracy), but the speedup is the headline and is presented without an auditable baseline. The implied serial rate for G81 is far below what a 32-core C implementation should achieve, so the concern is concrete rather than stylistic. The reader's weakest_assumption identified the same baseline fairness issue; I agree. Since the paper could be made acceptable by adding CPU runtimes and thread counts and recomputing speedups, the correct verdict remains the reader's CONDITIONAL; no change.","tokens_in":8947,"tokens_out":14520,"duration_ms":179661,"concrete_test":"Obtain the CPU source and rerun the same C implementation on the same EPYC 7513 for G81 and G77 with one thread and with all 32 threads (e.g., OpenMP), recording GPU_time/CPU_time for each. If the all-core speedup falls materially below 11,295x, the abstract should be rephrased as 'speedup over a single CPU thread' and the comparison should be reported with CPU runtimes and thread counts.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV says the CPU baseline is the same C algorithm on a 32-core AMD EPYC 7513 but does not disclose thread count. For G81, 23.37s GPU time times the 11,295x speedup implies about 73h of CPU time for a 20,000-node, O(n^2) simulation, which is roughly 1.5e6 pair updates per second. That is the signature of a single-threaded, scalar loop, not a 32-core CPU implementation. If the baseline uses one core, a fair 32-thread run would reduce the speedup by up to about 32x, leaving a much less dramatic per-core gain. Because the central advertised result is 'up to 11295x speed-up over CPUs,' the fairness of this baseline is load-bearing and is currently under-specified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript presents a CUDA-based digital simulator for oscillator-based Ising and Potts machines (OIM/OPM), using a modified Kuramoto model with injection locking and Gaussian noise (Eq. 5). The authors evaluate the solver on 32 GSET max-cut instances with 800-20,000 nodes and on SATLIB 3-coloring instances plus four custom 3-colorable graphs with up to 8,000 nodes. They report GPU runtimes of 0.45-23.37 s, speedups of 795x-11,295x over a C CPU implementation, and accuracies up to 99.27% for max-cut and 95.2%-99.5% for coloring. The paper also describes several CUDA optimizations, a triangular Ks annealing schedule, and a comparison with a prior GPU Ising solver.","tokens_in":9132,"tokens_out":6337,"duration_ms":79303,"significance":"If the results are reproducible, the paper is a useful engineering contribution: it demonstrates that a digital GPU emulation of OIM/OPM can handle large graphs (up to 20k nodes) with near-best-known solution quality on standard benchmarks, and that careful CUDA optimizations can yield very large speedups over a CPU implementation. The use of public GSET and SATLIB benchmarks is a strength, and Algorithm 1 provides enough pseudocode to reproduce the integration scheme. The main caveats are that the CPU baseline is under-specified, the accuracy metric for graph coloring is undefined, and the stochastic solver is reported without repeated runs; these issues currently make the headline speedup and accuracy claims difficult to assess.","major_comments":[{"comment":"The CPU baseline is described only as the same algorithm implemented in C and run on a 32-core AMD EPYC 7513, without stating whether the code is single-threaded or multithreaded, nor the compiler flags or optimization level. For G81, a 23.37 s GPU time and 11,295x speedup imply roughly 73 hours of CPU time for a 20,000-node simulation, which is consistent with a single-threaded scalar loop rather than a 32-core implementation. A fair 32-thread CPU run could reduce the speedup by up to about 32x. Because the abstract's headline is the speedup, this under-specification is load-bearing; please report the thread count, compiler, and optimization flags, and provide speedup against both single-threaded and multithreaded CPU baselines.","section":"Section IV"},{"comment":"The accuracy metric is not defined for the graph-coloring results in Table II. For max-cut, 'Acc(%)' is evidently GPU-cut divided by best-known cut, but no analogous definition is given for coloring. A proper 3-coloring is a binary property, so a value such as 99.5% for custom-8000 leaves unclear whether a valid coloring was found or whether the reported number is, for example, the fraction of constraint-satisfying edges. Define the metric precisely and, if the reported values are not the fraction of valid colorings, also state how many of the SATLIB and custom instances were solved to a fully proper 3-coloring.","section":"Tables I and II"},{"comment":"The solver is stochastic: initial phases are random and Eq. (5) includes Gaussian white noise, with Algorithm 1 drawing random numbers via CURAND. All reported runtimes and accuracies in Tables I and II appear to be single runs, with no number of trials, standard deviations, or best-of-N reporting. For a stochastic optimizer this makes it impossible to distinguish a typical solution from a lucky seed. Please report mean and standard deviation (or at least best-of-5/best-of-10) over multiple runs for a representative subset of instances in each table.","section":"Section IV-A / Tables I-II"},{"comment":"The best-known values for G81 (20,000 nodes) and G77 (14,000 nodes) are listed as '<NA>', yet these are the two largest instances and produce the two largest speedups. Without a best-known reference, the accuracy of the reported GPU-cut values cannot be established, and these rows should not be included in the statement in Section IV-A that the framework 'consistently achieves over 94% accuracy'. Provide best-known values or clearly mark these rows as speed-only results and exclude them from accuracy summaries.","section":"Table I"},{"comment":"The text states that 'these parameters are optimized' and lists K, Ks_max, Kn, h, and t_stop as tunable quantities. If the same benchmark instances are used for both parameter selection and the reported results, the accuracy numbers may be optimistic for unseen instances. Please report the exact parameter values used for each table, and, if possible, demonstrate robustness by evaluating on a held-out set or by presenting results across the parameter sweep rather than only at the tuned point.","section":"Section IV-B"}],"minor_comments":[{"comment":"The noise term is described inconsistently: Eq. (5) states that eta_i(t) has standard deviation sqrt(Kn * dt), but Algorithm 1 line 14 uses noise <- Kn * N(0,1) * sqrt(h). Unless Kn is redefined between these two places, the noise scaling should be clarified.","section":"Eq. (5) and Algorithm 1"},{"comment":"The runtime comparison with [18] is made on different GPUs; specify the GPU used in [18] or explicitly state that the wall-clock times are not directly comparable across implementations.","section":"Table III"},{"comment":"The parameter sweep panel in Fig. 3(b) would be easier to interpret if the axes were labeled with the parameter names and the accuracy color scale were identified in a legend.","section":"Fig. 3(b)"},{"comment":"There are minor formatting inconsistencies, such as '11295x' in the abstract versus '11,295x' in Section IV-A, and 'G-set' versus 'Gset'; please standardize the notation.","section":"Throughout"},{"comment":"The statement that 'the accuracy of the GPU and CPU implementations are the same' should be qualified: if the CPU and GPU use different summation orders or random seeds, the results may differ; state whether the implementations are bit-for-bit identical or use the same seed.","section":"Section IV-A"}],"recommendation":"major_revision","confidential_remarks":"The paper is a reasonable engineering contribution for GLSVLSI, and the central speedup/accuracy claims are plausible once the missing experimental details are supplied. I am recommending major revision rather than rejection because the problems are fixable with additional reporting: clarifying the CPU baseline's thread count, defining the coloring accuracy metric, adding repeated runs with error bars, providing best-known values for G81 and G77, and reporting the tuned parameters. I would also encourage the editor to request that the source code be made available, since the reproducibility concerns largely stem from the lack of implementation details."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Gonul et al. describe a CUDA simulator for the modified Kuramoto oscillator Ising/Potts machine, reporting up to 11,295x speedups over a C CPU baseline and 94-99% accuracy on GSET max-cut and SATLIB/custom 3-coloring instances. The novelty is modest but real: prior work includes GPU Ising solvers and digital OIM emulation, but this is the first GPU implementation of the Wang-Roychowdhury OIM/OPM dynamics with triangular Ks annealing that I know of, and the optimization details (float32, batched interactions, shared memory) are concrete and likely transferable. The paper is clearly written and the central engineering claim—a fast, programmable, large-scale digital OIM/OPM testbed—is plausible.\n\nThe main soft spot is the CPU baseline. Section IV says the C code runs on a 32-core AMD EPYC 7513 but never states whether it uses one thread or all 32. The implied CPU time for G81 (23.37s GPU times 11,295) is about 73 hours for a 20,000-node O(n^2) simulation, or roughly 1.5 million pair updates per second. That is the signature of a single-threaded scalar loop. If the baseline is single-threaded, the headline speedup is per-core, not against a 32-thread CPU, and a fair multi-threaded comparison would shrink it by up to ~32x. The contribution would survive—a per-core speedup of hundreds to thousands is still useful—but the advertised number is misleading as written.\n\nOther issues are smaller. The accuracy metric for graph coloring is never defined: for 3-coloring, does 99% mean the fraction of vertices with no conflict, or the fraction of satisfied edges? The numbers are not checkable without that definition. The solver is stochastic, yet no repeated runs or error bars are reported. Hyperparameters (K, Ks_max, Kn, h, t_stop) are tuned on the benchmark set, and the sweep in Figure 3(b) covers only two of them; the paper should disclose the values used for each instance. The two largest max-cut graphs (G77, G81) have no best-known reference, so the 99% accuracy claim rests on the smaller instances. None of this is fatal, but it makes the paper less verifiable than it should be.\n\nI'd send this to a referee. The right outcome is probably acceptance after a revision that discloses the CPU thread count, provides a multi-threaded baseline, defines the coloring accuracy metric, and reports repeated-run statistics. The audience is people building or validating analog OIM/OPM hardware, and researchers who want a fast emulator for studying oscillator dynamics. I wouldn't cite it myself, but it deserves a fair, serious review.","headline":"The headline 'up to 11295x speed-up' is real only if the CPU baseline is single-threaded; the paper never says, and that is the main thing a referee should chase.","tokens_in":9680,"tokens_out":3457,"would_cite":false,"duration_ms":36038,"reading_group":"yes","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 argues that a digital, GPU-parallelized simulation of coupled-oscillator Ising and Potts machines can solve large NP-hard combinatorial optimization problems quickly and accurately, using a modified Kuramoto model with…","keywords":["oscillator-based Ising machine","Potts machine","Kuramoto model","sub-harmonic injection locking","GPU acceleration","CUDA","max-cut","graph coloring"],"falsifier":"Re-run the identical algorithm with an optimized, fully multithreaded CPU implementation on the same 32-core processor and measure the wall-clock speedup on the 20,000-node G81 instance; if the gap falls far below the reported 11,295x, the speedup is inflated by the baseline rather than reflecting the GPU method.","tokens_in":8761,"feed_emoji":"⚡","tokens_out":4552,"duration_ms":48337,"temperature":0.7,"pith_summary":"This paper argues that a digital, GPU-parallelized simulation of coupled-oscillator Ising and Potts machines can serve as a practical heuristic solver for large NP-hard combinatorial optimization problems. Using a modified Kuramoto model with sub-harmonic injection locking and noise, the authors solve max-cut instances from the GSET suite with up to 20,000 nodes and 3-coloring instances up to 8,000 nodes. On an NVIDIA A100 GPU, their CUDA implementation runs up to 11,295 times faster than a C implementation of the same algorithm on a 32-core AMD EPYC CPU, while matching the CPU's solution quality. The practical payoff is that a commodity accelerator can bring oscillator-based optimization to graph sizes that are otherwise slow to handle.","feed_headline":"GPU oscillator solver hits 11,295x speedup on 20,000-node graphs","feed_subtitle":"Simulating coupled-oscillator Ising and Potts machines on CUDA solves max-cut and 3-coloring with up to 99% accuracy.","key_machinery":"The load-bearing object is the modified Kuramoto differential equation (Eq. 5): $$\\frac{d\\phi_i}{dt} = K \\sum_{j} J_{ij} \\sin(2\\pi(\\phi_i - \\phi_j)) + K_s \\sin(2\\pi N \\phi_i) + \\eta_i(t).$$ The sub-harmonic injection locking term $K_s \\sin(2\\pi N \\phi_i)$ pins oscillators to $N$ discrete phase states, with $N=2$ for Ising problems and $N \\ge 3$ for Potts problems; the coupling term encodes the problem Hamiltonian; and the Gaussian noise $\\eta_i(t)$ lets the system escape local minima. The speed comes from a dual-kernel CUDA layout, where one kernel integrates all phase derivatives in parallel and another thresholds phases, with the coupling matrix flattened and processed in batches across thread blocks to balance memory traffic.","core_discovery":"The central claim is that the dynamics of an oscillator Ising/Potts machine can be faithfully and quickly reproduced in floating-point arithmetic on a GPU, and that this digital realization keeps the solution quality of the physical model. The framework integrates Eq. (5), the modified Kuramoto equation with normalized phases, a sub-harmonic injection locking drive, and Gaussian noise, using Forward Euler integration, and assigns oscillator interactions to GPU threads in batches. Across 32 GSET max-cut instances, the computed cuts reach 94.08% to 99.27% of best-known values, and the 3-coloring results reach 95.2% to 99.5% accuracy on the tested instances. Because the same code runs on CPU and GPU, the paper reports identical accuracy for both and attributes the speedup to parallelization.","pith_inferences":["The paper does not explore automated tuning of K, Ks_max, and noise parameters, so an automatic parameter search could make the framework a drop-in solver for unseen instances.","The same batching and dual-kernel strategy should transfer to multi-GPU or distributed settings, which would let the method attack graphs well beyond 20,000 nodes.","Because the paper's convergence-time argument is sublinear in oscillator count, the GPU's relative advantage may widen further on larger graphs as long as memory bandwidth keeps up.","The comparison against a GPU simulated-annealing solver suggests a cheap hybrid strategy: run both solvers and keep the better solution, since the oscillator machine trades some speed for several percentage points of accuracy."],"forward_implications":["On the 32 GSET instances, the GPU solver consistently lands within 94% to 99% of best-known cuts, suggesting the approach can serve as a fast heuristic for max-cut on graphs up to 20,000 nodes.","Speedups grow with graph size, from 795x at 800 nodes to 11,295x at 20,000 nodes, so the parallelization is most valuable on large instances where exact solvers become impractical.","The 3-coloring results on custom graphs with 1,000 to 8,000 nodes show that Potts-state problems can be handled natively, without binary encoding overhead.","With runtimes from under half a second to about 23 seconds, the framework is fast enough for iterative use in design-space exploration or other workflows that need many solver calls."],"supporting_citations":[{"why":"Supplies the modified Kuramoto model with SHIL and noise, the core dynamics the GPU framework simulates, and the convergence-time scaling argument.","marker":"[6]"},{"why":"Provides the oscillator-based Potts machine formulation for multivalued spins, used for the 3-coloring problems.","marker":"[7]"},{"why":"Provides the Ising/Potts reformulations of max-cut and graph coloring that map directly onto oscillator phase states.","marker":"[13]"},{"why":"Supplies the digital Forward Euler emulation approach that the CUDA implementation follows.","marker":"[14]"},{"why":"Provides the CURAND library used for parallel Gaussian noise generation in the integration kernel.","marker":"[15]"},{"why":"Supplies the GSET benchmark instances used to measure max-cut accuracy against best-known solutions.","marker":"[16]"},{"why":"Supplies the SATLIB flat graph-coloring instances used to evaluate the Potts machine on 3-coloring.","marker":"[17]"},{"why":"Provides the GPU simulated-annealing Ising solver used as the related-work baseline in Table 3.","marker":"[18]"}],"fun_headline_variants":["GPU oscillator Ising/Potts sim hits 11,295x speedup","Simulated oscillator machines on GPU solve max-cut at 99%","GPU sim of coupled oscillators: 11k speedup, high accuracy","Oscillator-based optimizers get GPU boost: up to 11,295x","GPU digital OIM/OPM: 99% accuracy, 11,295x faster than CPU"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The headline speedup assumes the C CPU baseline is a fair reference implementation of the same algorithm, but the paper does not state whether that CPU code uses one core or all 32 cores of the EPYC 7513.","fun_headline_variants_meta":{"raw":{"variants":["GPU oscillator Ising/Potts sim hits 11,295x speedup","Simulated oscillator machines on GPU solve max-cut at 99%","GPU sim of coupled oscillators: 11k speedup, high accuracy","Oscillator-based optimizers get GPU boost: up to 11,295x","GPU digital OIM/OPM: 99% accuracy, 11,295x faster than CPU"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000197,"raw_usage":{"total_tokens":1346,"prompt_tokens":905,"completion_tokens":441,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":343}},"tokens_in":521,"tokens_out":441,"duration_ms":4612,"temperature":1.0,"reasoning_tokens":343,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:02:36.207217+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the identical algorithm with an optimized, fully multithreaded CPU implementation on the same 32-core processor and measure the wall-clock speedup on the 20,000-node G81 instance; if the gap falls far below the reported 11,295x, the speedup is inflated by the baseline rather than reflecting the GPU method.","supporting_citations":[{"cited_title":"Oim: Oscillator-based ising ma- chines for solving combinatorial optimisation problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the modified Kuramoto model with SHIL and noise, the core dynamics the GPU framework simulates, and the convergence-time scaling argument."},{"cited_title":"Oscillator-based potts machine (opm) for the implementation of the vector potts model,","cited_arxiv_id":null,"evidence_quote":"Provides the oscillator-based Potts machine formulation for multivalued spins, used for the 3-coloring problems."},{"cited_title":"Ising formulations of many np problems,","cited_arxiv_id":null,"evidence_quote":"Provides the Ising/Potts reformulations of max-cut and graph coloring that map directly onto oscillator phase states."},{"cited_title":"Digital emulation of oscillator ising machines,","cited_arxiv_id":null,"evidence_quote":"Supplies the digital Forward Euler emulation approach that the CUDA implementation follows."},{"cited_title":"CURAND Library","cited_arxiv_id":null,"evidence_quote":"Provides the CURAND library used for parallel Gaussian noise generation in the integration kernel."},{"cited_title":"G-set benchmarks, https://web.stanford.edu/ ∼yyye/yyye/gset/, Ac- cessed: 2025-03-01","cited_arxiv_id":null,"evidence_quote":"Supplies the GSET benchmark instances used to measure max-cut accuracy against best-known solutions."},{"cited_title":"Hoos and T","cited_arxiv_id":null,"evidence_quote":"Supplies the SATLIB flat graph-coloring instances used to evaluate the Potts machine on 3-coloring."},{"cited_title":"GPU Based Parallel Ising Computing for Combinatorial Optimization Problems in VLSI Physical Design","cited_arxiv_id":"1807.10750","evidence_quote":"Provides the GPU simulated-annealing Ising solver used as the related-work baseline in Table 3."}],"review_version":1}