{"id":"a199fa00-12fc-4d5e-88be-3fdf32247d2c","arxiv_id":"2505.20250","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A binary vector encoding with truth-table spin interactions gives probabilistic Ising machines competitive graph-coloring accuracy and a 1024-neuron FPGA implementation with large speedups.","lead":"This paper maps multi-state optimization problems such as graph coloring onto binary vector states instead of one-hot encoded states, shrinking the search space and improving solution quality on probabilistic Ising hardware. It also presents a 1024-neuron FPGA accelerator for the new mapping and reports large speedups over GPU-based heuristics.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"For non-power-of-two color counts, the binary vectorized encoding retains invalid color codes and Algorithm 1 penalizes them softly, so the claim that it 'eliminates invalid state space' is false and reported success rates may count invalid colorings.","rationale":"The reader's weakest_assumption identified the same central issue: for non-power-of-two color counts, the binary encoding does not eliminate invalid states, and Algorithm 1's F=1 for out-of-range colors is a soft penalty. My stress-test pass agrees with that reading and sharpens it. The load-bearing nature of the concern is that the paper's stated mechanism for accuracy improvement is the removal of invalid state space, and this mechanism is false for most of the benchmark instances. The paper never reports whether invalid color codes appear in solutions that are counted as successful, so the empirical central claim is underdetermined. This is not an external-consensus objection; it is a checkable correctness risk internal to the paper's own algorithm and metric definitions. The concrete test is straightforward and should be a condition for full acceptance. Because the reader already arrived at a CONDITIONAL verdict and my concern is essentially the same, the verdict does not need to change; the condition should explicitly include an audit of invalid color assignments and a re-evaluation of the affected tables.","tokens_in":15440,"tokens_out":6332,"duration_ms":71958,"concrete_test":"Using the authors' GPU or FPGA implementation, rerun the central benchmark instances queen13_13 (q=13, n=4), queen6_6 (q=7, n=3), and david/huck (q=11, n=4) for the same 200 runs and 1000 iterations. Decode each final bit vector to integer color values and count how many of the runs that meet the paper's success criterion (error less than 2%, i.e., mostly same-color-edge-free) contain at least one color value in the invalid range [q, 2^n - 1]. Then recompute success probability, Table 1 accuracy entries, and parallel-tempering error reduction after excluding all runs with invalid color assignments. Additionally, modify the implementation to add a large one-hot-style penalty or to project invalid codes to valid colors before evaluation, and compare the resulting accuracy and time-to-solution.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central mechanism is that binary vector encoding 'completely discards the exploration of infeasible/invalid solution space' and thereby makes probabilistic Ising machines competitive with Tabucol and GNN solvers. This is exactly true only when the number of colors q is a power of two. For the benchmark instances with q = 11, 12, 13, 7, or 5, there are 2^n possible codes for q valid color values, so the codes q through 2^n - 1 are invalid but remain in the state space. Algorithm 1 handles them by setting F=1, i.e., adding a weight penalty to the Hamiltonian in Eq. 3; it does not remove them from the sampler. The accompanying prose states that F becomes one when nodes take a color value greater than q, confirming this is a soft penalty, not a hard elimination. The problem is compounded by the error metric: 'error' is defined as the number of incorrectly colored edges divided by total edges, and in graph coloring an edge is typically considered incorrect only when both endpoints share a color. If a final solution contains an out-of-range color code, that node may not create any same-color edge, so the solution can be counted as successful even though it is not a valid q-coloring. The accuracy tables and success-probability results for non-power-of-two instances therefore depend on an unverified assumption that invalid color codes are either never sampled or never survive to the reported solutions. If invalid codes appear in a substantial fraction of runs counted as successful, the claimed competitiveness with Tabucol and GNN, and the 'up to 50% error reduction' from parallel tempering, are inflated. This is a load-bearing correctness risk rather than a wording issue, because the comparison baselines must produce legal colorings.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a 'vectorized mapping' for multi-state Ising problems, in which each node's color is encoded in a binary vector of length ceil(log2 Q) rather than a one-hot vector of length Q, and the pairwise interaction is defined by a truth-table operator F. The method is applied to graph coloring on COLOR benchmarks and to a small TSP example. The authors report that the vectorized mapping on GPU achieves errors comparable to Tabucol and PI-SAGE and substantially lower than one-hot probabilistic Ising and simulated bifurcation, and that adding parallel tempering reduces errors on hard instances. They also implement a 1024-neuron all-to-all FPGA accelerator supporting up to 256 nodes and 16 colors and report roughly 10,000x time-to-solution speedup over GPU-based Tabucol and about 5x power improvement over GPU-based vectorized mapping.","tokens_in":15806,"tokens_out":7864,"duration_ms":79949,"significance":"The core encoding idea is attractive and potentially useful: it reduces the physical neuron count from NQ to N ceil(log2 Q), a factor of about 1.5-4 for the color counts tested, and the truth-table formulation maps directly to multiplexer-based hardware. The FPGA demonstration is a concrete, measured result rather than a fitted prediction, and the state-space reduction from 2^{QN} to 2^{ceil(log2 Q) N} is a combinatorial fact. The per-instance distributions in the supplement and the explicit Algorithm 1 are helpful for reproducibility. However, the central claim that the mapping 'eliminates all invalid state space' is exact only when Q is a power of two; the benchmark claims for non-power-of-two Q rest on an unverified assumption about out-of-range binary codes. With that issue corrected or scoped, the contribution remains significant.","major_comments":[{"comment":"The statement that the vectorized mapping 'eliminates all invalid state space' is not correct for color counts that are not powers of two. For Q colors, the binary encoding uses n = ceil(log2 Q) bits, so the per-node code space has 2^n elements, of which 2^n - Q are invalid. Algorithm 1 handles out-of-range codes by setting F=1 and adding W_ij to the Hamiltonian; this is a soft penalty in the Gibbs sampler of Eq. (4), not a removal of those states from the explored space. The state space is therefore reduced from 2^{QN} to 2^{nN}, but not to Q^N as the text implies. Since Tables 1 and 2 report results for Q = 5, 7, 11, 12, and 13, this discrepancy affects the core accuracy claims.","section":"§2, Eq. (3), Algorithm 1"},{"comment":"The success metric counts only incorrectly colored edges, i.e., edges whose two endpoints share the same color value. A final assignment that contains out-of-range binary codes but has no two nodes sharing the same invalid code will have zero incorrectly colored edges and will be counted as successful even though it is not a valid Q-coloring. The manuscript does not report how often final solutions contain out-of-range codes for non-power-of-two instances. Please (i) report the fraction of runs with invalid codes, (ii) recompute success probability and time-to-solution treating any out-of-range code as a failure, and (iii) either restrict the 'eliminates invalid state space' claim to Q=2^n or explicitly describe the penalty as an approximation. This verification is necessary to support the competitive accuracy claims for hard instances such as queen11_11 and queen13_13.","section":"§4, Fig. 4(b)-(c)"},{"comment":"The FPGA accelerator is described as supporting up to 16 colors, which is a power of two, so the exact state-space elimination holds for the full-capacity hardware configuration. However, the FPGA column in Table 1 also reports results for non-power-of-two instances (Q = 5, 7, 11, 12, 13), and the text states that the FPGA achieves the same accuracy as the GPU vectorized mapping. The same invalid-code ambiguity therefore propagates to the hardware results. Please clarify whether the FPGA runs for such instances verify that the final colors are in [0, Q-1], or otherwise explain how out-of-range codes are treated in the reported accuracy.","section":"§5, Table 1"}],"minor_comments":[{"comment":"Equation (4) defines the sigmoid as sigma(x) = 1/(1 + e^x), while Algorithm 2 defines sigmoid(x) = 1/(1 + e^{-x}). With the minus sign in the argument of Eq. (4), these two conventions give opposite flip probabilities. Please unify the notation and verify the sign convention against the standard Gibbs update.","section":"Eq. (4)"},{"comment":"The speedup numbers are stated inconsistently: the abstract reports '~10000x' versus GPU Tabucol, the introduction reports '100000x speed improvement' compared to its GPU-based implementation, and the Discussion reports '~10000x' versus Tabucol and '~100000x' versus vectorized mapping on GPU. Please clarify the baseline in each location.","section":"Abstract and Discussion"},{"comment":"The condition 'S_i, S_j /∈ [0, Q-1]' is ambiguous: it should state clearly whether the penalty is triggered when either node is out of range or only when both are out of range. The surrounding prose suggests 'either', but the pseudocode should be explicit.","section":"Algorithm 1"},{"comment":"The truth-table portion of Fig. 2b appears garbled in the manuscript text (e.g., the strings '00123467' and the F column). Please ensure the final figure renders the truth table legibly and that the table entries match Algorithm 1.","section":"Fig. 2b"}],"recommendation":"major_revision","confidential_remarks":"The central overclaim about eliminating invalid states is the main obstacle. If the authors supply validation that out-of-range codes are absent or rare in the reported solutions, or if they narrow the claim to Q=2^n, the technical contribution and hardware results would justify publication after revision. I do not see grounds for rejection, as the encoding reduction and measured FPGA speedups are substantive."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid hardware-oriented mapping paper with one overstated claim that needs fixing. The vectorized binary encoding with a truth-table F operator is a genuinely useful idea, and the FPGA implementation shows real engineering. But the paper's central justification — that the encoding \"eliminates all invalid state space\" — is exactly true only when q is a power of two. For q = 5, 7, 11, 12, 13, the binary codes include out-of-range values, and Algorithm 1 handles them by adding a penalty, not by removing them. That is a soft constraint, and the text should say so.\n\nThe paper does well: it reduces physical neurons from Nq to N⌈log2 q⌉, a real win; it implements the F operator as higher-order multiplexers on an FPGA; and it reports per-instance error distributions, success probabilities, TTS, and power. The accuracy numbers against Tabucol and PI-SAGE are impressive. The comparison of a custom FPGA against GPU software is apples-to-oranges, but the authors acknowledge that and show Tabucol doesn't parallelize well.\n\nThe soft spots: first, the invalid-state issue. If a final solution contains an out-of-range code, that node doesn't share a color with anything, so it may not create an incorrectly colored edge. The error metric would count it as correct. The success probabilities in Figure 4b and Table 1 could therefore include illegal q-colorings. This is mechanically checkable — the authors should validate that all successful runs produce codes in [0, q-1], or exclude invalid ones. Second, the TSP extension uses a per-instance tuned wt and has the same out-of-range issue; that part is weaker but secondary. Third, code is not released, only data.\n\nNone of this sinks the paper. The mapping idea deserves serious attention, and the FPGA results are measured, not predicted. But the overclaim should be corrected, and the validity check is essential for the reported success rates to be meaningful. I'd send it to peer review and ask for those revisions.","headline":"Vectorized binary encoding with truth-table F is a real improvement for Ising solvers, but the 'eliminates invalid states' claim only holds for powers of two — for other q it's a soft penalty, and success counts may include illegal colorings.","tokens_in":16360,"tokens_out":4231,"would_cite":true,"duration_ms":42258,"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":"Binary-vector encoding of node colors makes probabilistic Ising machines competitive with Tabucol and GNN solvers on graph coloring, and a 1024-neuron FPGA version runs roughly 10000x faster than GPU Tabucol.","keywords":["graph coloring","Ising machines","probabilistic computing","combinatorial optimization","vectorized mapping","QUBO","FPGA accelerator","parallel tempering"],"falsifier":"Run the vectorized mapping on a non-power-of-two instance, for example a 3-color queen problem, collect every final color assignment across many runs, and count how many use out-of-range codes, i.e. binary values $\\ge q$. If such invalid-code solutions appear with nontrivial frequency or account for most incorrect edges, the central claim is falsified: the gains come from the penalty term, not from eliminating invalid state space.","tokens_in":15239,"feed_emoji":"🎨","tokens_out":10671,"duration_ms":121872,"temperature":0.7,"pith_summary":"This paper argues that the usual way of mapping multi-state optimization problems onto Ising machines---one-hot encoding plus a penalty term---is what makes those machines perform poorly on graph coloring. It proposes instead to encode each node's color as a $\\lceil \\log_2 q \\rceil$-bit binary vector, so the search space shrinks from $2^{qN}$ to $2^{\\lceil \\log_2 q \\rceil N}$ and the one-hot constraint term disappears from the energy function. With this vectorized mapping, probabilistic Ising solvers achieve accuracy competitive with Tabucol and physics-inspired graph neural networks on standard benchmark graphs, and they clearly beat one-hot QUBO-based Ising solvers and simulated bifurcation. Adding parallel tempering reduces the error by up to 50% on the hardest instances. The same mapping, expressed as a truth table and realized with higher-order multiplexers, supports a 1024-neuron all-to-all FPGA accelerator that reaches roughly 10000x time-to-solution speedup over GPU Tabucol while using 1.5-4x fewer physical neurons than one-hot Ising hardware.","feed_headline":"Binary-vector trick speeds Ising graph coloring by 10000x","feed_subtitle":"Encoding each color as a short binary vector removes invalid states and lets a 1024-neuron FPGA beat GPU Tabucol.","key_machinery":"The central object is the vectorized mapping: replace each $q$-state variable by $n = \\lceil \\log_2 q \\rceil$ binary spins and encode the interaction between two variables as a truth-table operator $F$, defined in Algorithm 1. In hardware, $F$ is implemented by higher-order multiplexers, so each spin's $\\Delta H$ is computed as the difference between the multiplexer outputs for $s_{ik}=1$ and $s_{ik}=0$. This removes the one-hot penalty term $B \\sum_i (1 - \\sum_k s_{ik})^2$ and shrinks the explored state space from $2^{qN}$ to $2^{nN}$, which is what makes the mapping the load-bearing element of the claimed accuracy and speedup gains.","core_discovery":"The paper's central claim is that mapping each multi-state variable to a binary vector, rather than to a one-hot vector, changes the energy landscape enough to make stochastic Ising machines competitive on graph coloring. For $q$ colors, node $S_i$ is represented by $\\{s_{i0}, \\dots, s_{i,n-1}\\}$ with $n = \\lceil \\log_2 q \\rceil$, and edge penalties are computed by a truth-table operator $F$ that returns 1 when two endpoints have equal color or an out-of-range code, and 0 otherwise. The resulting Hamiltonian is higher-order rather than quadratic, but each spin update needs only $\\Delta H = H_{s_{ik}=1} - H_{s_{ik}=0}$, which hardware can evaluate directly with multiplexers. The paper reports that this encoding eliminates all invalid state space, that parallel tempering adds a further accuracy gain of up to 50% error reduction on hard instances, and that a 1024-neuron FPGA implementation reaches about 10000x time-to-solution speedup over GPU Tabucol while using 1.5-4x fewer physical neurons than one-hot Ising mappings.","pith_inferences":["Editorial inference: the state-space reduction claim is exact only when $q$ is a power of two; for other color counts the method keeps a soft penalty for out-of-range codes, so an extension that truly excludes those patterns, or measures their frequency in the output, would settle how much of the gain is due to encoding versus penalty tuning.","Editorial inference: the ~10000x speedup over Tabucol is not purely algorithmic, because it compares a bit-parallel custom accelerator against a sequential heuristic on GPU; a fair algorithmic comparison would run both on the same hardware or count node-update operations.","Editorial inference: the higher-order truth-table interaction is a deliberate departure from standard QUBO hardware, so applying the same mapping to conventional Ising annealers would require expanding $F$ into quadratic terms, possibly reintroducing constraints or auxiliary variables; the paper does not explore that trade-off."],"forward_implications":["Graph coloring benchmarks previously dominated by Tabucol and GNN solvers can now be solved to comparable accuracy by a probabilistic Ising machine, because the vectorized encoding removes the one-hot constraint from the energy function.","One-hot QUBO-based Ising solvers, including simulated bifurcation, are less accurate on these instances; the paper attributes that gap to exploration of invalid states, which the binary-vector encoding largely avoids.","A 1024-neuron all-to-all FPGA accelerator built from truth-table multiplexers supports graph coloring instances up to 256 nodes and 16 colors, delivering roughly 10000x time-to-solution speedup and about 5x power improvement over the GPU implementations.","Because the truth-table operator $F$ is problem-specific rather than quadratic-specific, the same construction can be written down for other multi-state problems; the paper demonstrates it on traveling salesman problems in the supplement."],"supporting_citations":[{"why":"Defines the one-hot QUBO graph-coloring Hamiltonian that the paper identifies as the source of invalid-state exploration.","marker":"[27]"},{"why":"Supplies the Tabucol heuristic used as the main classical solver against which accuracy and time-to-solution are measured.","marker":"[32]"},{"why":"Provides the PI-SAGE GNN baseline and the hard/medium/easy instance labels used in the accuracy comparison.","marker":"[33]"},{"why":"Provides the GNN baseline for graph coloring compared in the accuracy tables.","marker":"[34]"},{"why":"Supplies the parallel tempering scheme the paper couples with vectorized mapping to improve solution quality.","marker":"[39]"},{"why":"Is the COLOR benchmark dataset on which all graph-coloring results are reported.","marker":"[40]"},{"why":"Provides the all-to-all reconfigurable probabilistic Ising machine baseline for accuracy and hardware comparison.","marker":"[42]"},{"why":"Supplies the simulated bifurcation algorithm used as a state-of-the-art QUBO Ising solver baseline.","marker":"[43]"},{"why":"Establishes the probabilistic Ising machine architecture and its use for optimization, which the FPGA design builds on.","marker":"[9]"}],"fun_headline_variants":["Binary-vector encoding lifts Ising graph coloring to 10000x speed","FPGA Ising solver hits 10000x speedup for graph coloring","Compact encoding shrinks Ising state space, accelerates coloring","Multistate Ising gets log-sized vectors, 10000x faster coloring"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central load-bearing premise is that penalizing out-of-range binary codes is as good as forbidding them. For color counts that are not powers of two, the $\\lceil \\log_2 q \\rceil$-bit encoding still contains invalid bit patterns; Algorithm 1 marks those with a penalty in the Hamiltonian, so the claimed elimination of invalid state space is a soft constraint, not a hard one, and the accuracy and speedup numbers depend on that approximation.","fun_headline_variants_meta":{"raw":{"variants":["Binary-vector encoding lifts Ising graph coloring to 10000x speed","FPGA Ising solver hits 10000x speedup for graph coloring","Compact encoding shrinks Ising state space, accelerates coloring","Multistate Ising gets log-sized vectors, 10000x faster coloring"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00063,"raw_usage":{"total_tokens":2929,"prompt_tokens":980,"completion_tokens":1949,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":596,"completion_tokens_details":{"reasoning_tokens":1881}},"tokens_in":596,"tokens_out":1949,"duration_ms":14239,"temperature":1.0,"reasoning_tokens":1881,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:56:35.485554+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the vectorized mapping on a non-power-of-two instance, for example a 3-color queen problem, collect every final color assignment across many runs, and count how many use out-of-range codes, i.e. binary values $\\ge q$. If such invalid-code solutions appear with nontrivial frequency or account for most incorrect edges, the central claim is falsified: the gains come from the penalty term, not from eliminating invalid state space.","supporting_citations":[{"cited_title":"Ising formulations of many np problems.Frontiers in Physics2(2014)","cited_arxiv_id":null,"evidence_quote":"Defines the one-hot QUBO graph-coloring Hamiltonian that the paper identifies as the source of invalid-state exploration."},{"cited_title":"& de Werra, D","cited_arxiv_id":null,"evidence_quote":"Supplies the Tabucol heuristic used as the main classical solver against which accuracy and time-to-solution are measured."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the PI-SAGE GNN baseline and the hard/medium/easy instance labels used in the accuracy comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the parallel tempering scheme the paper couples with vectorized mapping to improve solution quality."},{"cited_title":"COLOR Dataset (2002)","cited_arxiv_id":null,"evidence_quote":"Is the COLOR benchmark dataset on which all graph-coloring results are reported."},{"cited_title":"A., Chowdhury, S","cited_arxiv_id":null,"evidence_quote":"Provides the all-to-all reconfigurable probabilistic Ising machine baseline for accuracy and hardware comparison."},{"cited_title":"& Salahuddin, S","cited_arxiv_id":null,"evidence_quote":"Establishes the probabilistic Ising machine architecture and its use for optimization, which the FPGA design builds on."}],"review_version":1}