{"id":"92e5deba-a08b-4025-ba85-b55625bf58f9","arxiv_id":"2507.18727","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":7,"one_line_summary":"The paper proposes a three-phase TSP heuristic for RIS codebook index assignment, but the stated equivalence between single-bit-error robustness and a Hamiltonian path is flawed.","lead":"This paper assigns binary labels to RIS phase configurations so that a single bit error in the feedback link causes minimal signal loss. It treats the reordering task as a traveling salesman problem and offers a fast three-phase heuristic, with simulations claiming near-optimal robustness.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The TSP reduction is invalid: a Hamiltonian path plus Gray-code labeling controls only two of log2(K) Hamming neighbors per index, so Eq. (8) is not equivalent to Eq. (9), and the paper's optimality claim is unsupported.","rationale":"The reader's weakest assumption identifies the same load-bearing flaw that I find: the paper equates a Hamiltonian path objective with the true single-bit-error objective, but a path has only K-1 edges while the Hamming graph has K log2(K)/2 edges. This is not a peripheral gap; it is the foundation of the claimed TSP formulation and of the optimality interpretation of the simulations. The proposed heuristic may still produce practical codebooks, and the simulation pipeline is internally consistent in measuring Eq. (8), but the solver optimizes Eq. (9), so the results do not support the central claim. I agree with the reader's REJECT verdict. My concrete test would settle the matter by direct computation on a small instance and by re-evaluating the paper's own K=16 example against the true objective.","tokens_in":25615,"tokens_out":3490,"duration_ms":42096,"concrete_test":"Use the paper's K=16 setup or the actual SNR-loss matrix from Section IV and perform four steps: (a) compute the exact shortest Hamiltonian path pi*; (b) assign Gray-code labels g_k sequentially along pi*; (c) evaluate the true objective (8) by summing d(c_i,c_j) over all Hamming-distance-1 index pairs; (d) compare this value against random and natural labelings, and against the best labeling found by exhaustive search over the true objective. If pi* does not minimize (8), the reduction fails. A decisive analytical micro-test: take K=4 with distances d(0,1)=d(1,3)=d(3,2)=0 and d(0,2)=1; the shortest Hamiltonian path 0-1-3-2 has cost 0, but under Gray labels 00,01,11,10 the true objective (8) includes the missing Hamming edge 00-10 and equals 1. Exhaustive indexing shows the true objective can instead be minimized by a different assignment, directly disproving the claimed equivalence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction from the true single-bit-error objective to a shortest Hamiltonian path is mathematically incorrect. With K codewords and log2(K)-bit indices, each index has log2(K) Hamming neighbors, so the true objective (8) contains K log2(K)/2 terms. A Hamiltonian path has only K-1 edges, and a sequential Gray-code labeling makes only the two path-neighbor labels differ by one bit (except at endpoints). Thus the path objective (9) controls at most 2/log2(K) of the single-bit-error events; for K=256 this is only 25%. The paper's claim that 'any single-bit index error leads to jumping to an adjacent codeword on this path' is false for every K>4: for example, in the K=16 example, codeword 0000 has Hamming neighbors 0001 (path-adjacent) and also 0010, 0100, and 1000, none of which are path-adjacent in the listed Gray sequence. Consequently, the simulations report average loss over all Hamming-neighbor pairs (Eq. 8), while the solver minimizes only the path cost (Eq. 9); the reported gains over natural or random indexing do not validate the advertised TSP equivalence. Appendix B repeats the same unsupported assertion. The three-phase heuristic may remain useful as an engineering heuristic, but the paper's foundational equivalence and near-optimality guarantee are unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies index assignment for RIS codebooks under imperfect feedback links. The authors propose to assign binary indices to RIS codewords so that single-bit index errors cause minimal SNR degradation. They formulate the problem as a shortest Hamiltonian path (TSP) over codewords, with edge weights given by relative SNR loss, and then label the codewords sequentially along the path using a Gray code. A three-phase heuristic (provision, shotgun, fuzzy concatenation) is proposed to solve the resulting TSP, and simulations compare the achieved average SNR loss against natural indexing, random indexing, and several TSP solvers.","tokens_in":25964,"tokens_out":3961,"duration_ms":49827,"significance":"The practical problem is relevant: feedback errors on RIS control links are rarely modeled, and a principled index assignment could improve robustness. The paper also contains a substantial amount of benchmarking against standard TSP solvers (LKH3, Concorde, GLOP, POMO, ELG, 2-opt, etc.), with runtime and scaling results. However, the central theoretical contribution—the equivalence between the single-bit-error objective and a shortest Hamiltonian path—is mathematically incorrect. Because this equivalence is the foundation for the problem formulation, the proposed optimality claim, and the interpretation of all simulation results, the paper's main advertised result is not supported. The heuristic may still be useful as an engineering heuristic, but the manuscript does not provide a valid basis for claiming near-optimal robustness under single-bit errors.","major_comments":[{"comment":"The reduction from the true single-bit-error objective to a shortest Hamiltonian path is invalid. In Eq. (8), the objective sums over all index pairs with Hamming distance 1; with log2(K)-bit indices, each index has log2(K) Hamming neighbors, so the sum contains K log2(K) directed terms. In contrast, the Hamiltonian path objective Eq. (9) sums only K-1 path edges. Under a sequential Gray-code labeling, only the two path-adjacent labels (one at each endpoint) differ by one bit from a given interior label. For K=256, Eq. (9) controls at most 2/log2(256)=25% of the single-bit-error events, and for K=16 it controls at most 2/4=50%. The paper's claim that 'any single-bit index error leads to jumping to an adjacent codeword on this path' is therefore false.","section":"Section II.B, Eqs. (8)-(9)"},{"comment":"The K=16 example in Table II concretely demonstrates the failure of the claimed equivalence. In the listed Gray sequence, the codeword labeled 0000 (position 0) has Hamming neighbors 0001 (position 1), 0010 (position 3), 0100 (position 7), and 1000 (position 15). Only position 1 is adjacent on the TSP path; the other three Hamming-neighbor pairs are not constrained by the path cost in Eq. (9). Thus the path objective does not control the majority of single-bit confusions even in the paper's own illustrative example.","section":"Section II.B, Table II example"},{"comment":"The simulations do not close the gap between the optimized objective and the evaluated metric. Step 5 of the simulation procedure evaluates average SNR loss over all codeword pairs whose indices differ by one bit, i.e., the objective in Eq. (8). The proposed solver, however, minimizes only the path cost in Eq. (9). Consequently, Figs. 4-10 and Tables VI-VII report the heuristic's performance on a metric that the algorithm does not directly optimize, and the comparisons against other TSP solvers compare solutions to an objective that is not equivalent to the stated problem. The reported 'near-optimal' behavior therefore does not validate the advertised TSP equivalence.","section":"Section IV, simulation methodology"},{"comment":"Appendix B repeats the unsupported assertion that 'Hamming-distance-1 neighbors correspond exactly to adjacent nodes on the TSP path.' This is the same incorrect statement as in Section II.B. A Gray-code sequence of length K has many non-adjacent pairs at Hamming distance 1; only the path-neighbor relation is controlled by Eq. (9). Since this appendix is used to justify the entire simulation model, the invalid assertion is load-bearing and not a minor presentation issue.","section":"Appendix B"}],"minor_comments":[{"comment":"The title contains a typo: 'Control Link s' should read 'Control Links'.","section":"Title"},{"comment":"The text says the codewords can be 'labeled sequentially or via Gray code.' Sequential binary labeling does not guarantee that adjacent path positions differ by one bit; only a Gray-code labeling does. This ambiguity should be clarified.","section":"Section II.B"},{"comment":"There are two experiments labeled 'Experiment III' (the ablation study and the comparison with other TSP solvers). The second should be renumbered.","section":"Section IV"},{"comment":"The sentence 'fix the number of codebooks at K = 256' should read 'fix the number of codewords at K = 256'.","section":"Section IV.D"},{"comment":"The loss d(ci,cj) defined in Eq. (6) is not symmetric, yet the algorithm accumulates unordered pair counts (Algorithm 1, step 22) and treats the path as undirected. The manuscript should state explicitly whether the edge weights are symmetrized for the TSP formulation.","section":"Section II.A / Eq. (6)"},{"comment":"The many heuristic parameters (l1, l2, l3, nshot, kshot, ncate, kcate, µ0, σ, µmin, z, kmin, T) are given without derivation or sensitivity analysis. This does not affect the central mathematical error, but it limits reproducibility and makes the claimed scalability results less informative.","section":"Table III"}],"recommendation":"reject","confidential_remarks":"The central reduction in Section II.B is not a minor flaw; it invalidates the paper's main claim that the SNR-loss minimization problem under single-bit feedback errors is equivalent to a shortest Hamiltonian path. The simulation results are therefore not evidence for the advertised equivalence, and the proposed method is reduced to an unvalidated heuristic for a different objective. This cannot be fixed within the current manuscript's scope without fundamentally reworking the problem formulation and the supporting claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core equivalence does not hold, but there is a real engineering artifact here. The three-phase heuristic is new and the simulation study is wide and careful. The problem is that the claimed reduction of the single-bit-error objective to a Hamiltonian path is incorrect.\n\nEquation (8) sums over every pair of indices at Hamming distance 1, which is K log2(K)/2 terms. Equation (9) sums over K-1 path edges. With a Gray-code labeling, only the two adjacent positions on the path differ from a given index in one bit; every other Hamming neighbor (and there are log2(K)-2 of them) is not constrained by the path. For K=256 only 25% of the single-bit-error events are controlled by the path objective. So a path can be optimal while many high-loss Hamming-neighbor pairs are completely ignored. The claim in Section II.B that any single-bit error jumps to an adjacent codeword on the path is simply false for K>4. Appendix B repeats the same assertion.\n\nThat is a load-bearing flaw, not a detail. The simulations measure SNR loss over all Hamming-neighbor pairs (Eq. 8) while the solver minimizes only path cost (Eq. 9). So the reported gains over natural or random indexing do not validate the advertised TSP equivalence. The authors would need to either solve the true QAP formulation or prove a bound relating path cost to the true objective.\n\nWhat the paper does well: the three-phase heuristic is clearly described, the complexity analysis is honest, and the benchmark against LKH3, Concorde, GLOP, POMO and others is thorough. The ablation study gives real information about which components matter. The authors also cite the earlier TSP-based index assignment work (Spira et al. [27]), so the novelty is appropriately limited to the heuristic itself, even if the text elsewhere overstates the conceptual contribution.\n\nThe heuristic might still be useful in practice, and the problem it targets is real. But as a contribution to the theory of index assignment, the central claim is unsupported. I would recommend sending it to peer review, because the flaw is substantive and needs careful articulation, but the right outcome after review is rejection unless the objective is corrected or a formal connection is established.","headline":"The TSP-reduction claim is mathematically wrong, but the three-phase heuristic and benchmark study are real and the paper as an engineering artifact could be salvaged with a corrected objective.","tokens_in":26535,"tokens_out":1850,"would_cite":false,"duration_ms":24567,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","05C45"],"pacs":[],"model":"deepseek-v4-flash","headline":"The shortest Hamiltonian path through a RIS codebook, labeled with Gray codes, is the ordering that minimizes average SNR loss under single-bit feedback errors.","keywords":["reconfigurable intelligent surface","codebook index assignment","traveling salesman problem","feedback error resilience","Gray code","SNR loss minimization","combinatorial optimization","binary symmetric channel"],"falsifier":"On a fixed RIS codebook and channel realization (e.g., $K=256$, $N=256$, $b=8$), compute the expected SNR loss in eq. (7) under the TSP-path Gray-code assignment and under an assignment that directly minimizes the all-Hamming-neighbor sum in eq. (8); if the direct minimizer achieves lower loss, the claim that the Hamiltonian path is the optimal single-bit-error index assignment is falsified.","tokens_in":25353,"feed_emoji":"📡","tokens_out":10921,"duration_ms":108739,"temperature":0.7,"pith_summary":"Reconfigurable intelligent surfaces (RIS) are tuned by sending a short binary index over a wireless control link, and a single flipped bit can make the surface apply the wrong phase pattern and degrade the received signal. This paper claims that the damage from such one-bit feedback errors can be minimized by reordering the codebook: treat each codeword as a city, use the relative SNR loss caused by swapping two codewords as the distance, and find the shortest Hamiltonian path through all codewords. Assigning Gray-code labels along that path makes the most probable error land on a neighboring, minimally damaging configuration. The paper also contributes a three-phase heuristic that finds near-optimal orderings in polynomial time, scaling to codebooks of 1024 codewords, so the protection is achievable without changing the RIS hardware.","feed_headline":"Traveling-salesman path ordering cuts RIS bit-flip SNR loss","feed_subtitle":"If a bit flips, the RIS switches to the next codeword on the path, not a random one.","key_machinery":"The carrying object is a complete graph on the $K$ RIS codewords, with edge weight $d(c_i,c_j)=|1-\\mathrm{SNR}_j/\\mathrm{SNR}_i|$ measuring the relative SNR loss from applying $c_j$ in place of $c_i$. The optimization target is the Hamiltonian path $\\pi^*$ minimizing $L(\\pi)$, and a Gray code — a binary labeling in which consecutive labels differ in exactly one bit — is the indexing rule that turns path adjacency into one-bit index adjacency. The solver that makes the approach practical has three phases: provision (builds layered nearest-neighbor candidate sets from the loss distribution), shotgun (samples $3K^2$ random routes with selection probability $1/(1+(d/(\\mu\\bar d))^2)$ and keeps the best $3K$), and fuzzy concatenation (reinforces frequently used edges while adaptively decaying greediness). The worst-case complexity is $O(K^4)$.","core_discovery":"The central claim is that RIS codebook index assignment under a binary symmetric feedback channel reduces to a Traveling Salesman Problem: with equal priors and single-bit errors dominating, the expected SNR loss is proportional to $\\sum_i \\sum_{j:\\mathrm{Ham}(i,j)=1} d(c_i,c_j)$, and the paper argues that minimizing the Hamiltonian path cost $L(\\pi)=\\sum_{k=0}^{K-2} d(c_{\\pi(k)}, c_{\\pi(k+1)})$ and labeling the path with consecutive Gray codes achieves this robustness. The optimal permutation $\\pi^*$ is the one minimizing $L(\\pi)$, found by a three-phase solver whose worst-case complexity is $O(K^4)$. In simulations the solver matches the SNR loss of strong exact and heuristic TSP solvers while running substantially faster on large codebooks, and it retains its advantage on clustered and exploded edge-weight distributions.","pith_inferences":["The path objective in eq. (9) controls only the two path neighbors of each index, while the true single-bit objective in eq. (8) sums over all $\\log_2 K$ Hamming neighbors; an ordering that directly minimizes eq. (8) would be a strictly stronger defense and is a natural follow-up the paper leaves open.","The same TSP-plus-Gray-code machinery should transfer to other finite codebooks whose entries have a quantifiable confusion cost, such as beamforming or quantization codebooks, not just RIS phase configurations.","Under non-uniform codeword priors, the equal-prior simplification in eq. (7) breaks, and the optimal ordering would need to weight pair losses by the prior probabilities of the intended codeword.","A direct comparison between the proposed solver and generic TSP solvers on 'exploded' edge-weight distributions suggests that neural solvers trained on uniform Euclidean TSP instances may be systematically worse on quantized RIS codebooks, a hypothesis testable with the paper's published setup."],"forward_implications":["Existing RIS codebooks can be reordered in place, with no new phase hardware or feedback-channel changes, to reduce SNR loss from the dominant single-bit error events.","The $O(K^4)$ heuristic completes a 1024-codeword reordering in about two minutes, making large-codebook robustness practical.","The solver keeps its advantage on clustered and exploded edge-weight distributions, where generic fast heuristics lose 20% or more in SNR compared with the best orderings.","If feedback error rates are not tiny, multi-bit errors become non-negligible and the paper's own limitation note says the TSP simplification should give way to the full quadratic assignment formulation."],"supporting_citations":[{"why":"Supplies the pseudo-Gray coding and binary switching algorithm that define the index-assignment problem this paper specializes to RIS.","marker":"[24]"},{"why":"Introduces vector quantization index assignment for noisy channels, the source of the expected-distortion objective in eq. (7).","marker":"[25]"},{"why":"Provides the Hadamard-transform index assignment algorithm used as a classical baseline.","marker":"[26]"},{"why":"Already approximates codebook index assignment by a traveling salesman problem, the formulation this paper adopts and extends.","marker":"[27]"},{"why":"LKH3 is the high-quality TSP solver against which the proposed heuristic's near-optimal SNR loss is benchmarked.","marker":"[28]"},{"why":"Concorde is the exact TSP solver used as the optimal reference for feasible codebook sizes.","marker":"[29]"}],"fun_headline_variants":["TSP solver minimizes RIS SNR loss from one-bit errors","Reorder RIS codebook with a traveling-salesman path for robustness","TSP-inspired indexing slashes RIS bit-flip SNR degradation","Make RIS resilient to feedback errors with a TSP order","RIS codebook ordered by TSP to cut single-bit error loss"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a Gray-code labeling of a Hamiltonian path makes every single-bit index error fall on a path-adjacent codeword, even though each binary index has several one-bit neighbors and only two of them sit next to it on the path.","fun_headline_variants_meta":{"raw":{"variants":["TSP solver minimizes RIS SNR loss from one-bit errors","Reorder RIS codebook with a traveling-salesman path for robustness","TSP-inspired indexing slashes RIS bit-flip SNR degradation","Make RIS resilient to feedback errors with a TSP order","RIS codebook ordered by TSP to cut single-bit error loss"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00034,"raw_usage":{"total_tokens":1865,"prompt_tokens":922,"completion_tokens":943,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":538,"completion_tokens_details":{"reasoning_tokens":857}},"tokens_in":538,"tokens_out":943,"duration_ms":7942,"temperature":1.0,"reasoning_tokens":857,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:32:03.242160+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a fixed RIS codebook and channel realization (e.g., $K=256$, $N=256$, $b=8$), compute the expected SNR loss in eq. (7) under the TSP-path Gray-code assignment and under an assignment that directly minimizes the all-Hamming-neighbor sum in eq. (8); if the direct minimizer achieves lower loss, the claim that the Hamiltonian path is the optimal single-bit-error index assignment is falsified.","supporting_citations":[{"cited_title":"Pseudo-gray coding,","cited_arxiv_id":null,"evidence_quote":"Supplies the pseudo-Gray coding and binary switching algorithm that define the index-assignment problem this paper specializes to RIS."},{"cited_title":"A study of vector quantization for noisy channels,","cited_arxiv_id":null,"evidence_quote":"Introduces vector quantization index assignment for noisy channels, the source of the expected-distortion objective in eq. (7)."},{"cited_title":"The hadamard transform- a tool for index assignment,","cited_arxiv_id":null,"evidence_quote":"Provides the Hadamard-transform index assignment algorithm used as a classical baseline."},{"cited_title":"Codebook index ass ignment by an approximate solution of the traveling salesman problem,","cited_arxiv_id":null,"evidence_quote":"Already approximates codebook index assignment by a traveling salesman problem, the formulation this paper adopts and extends."},{"cited_title":"An extension of the lin-kernighan-helsg aun tsp solver for constrained traveling salesman and vehicle routing proble ms,","cited_arxiv_id":null,"evidence_quote":"LKH3 is the high-quality TSP solver against which the proposed heuristic's near-optimal SNR loss is benchmarked."},{"cited_title":"Concor de tsp solver,","cited_arxiv_id":null,"evidence_quote":"Concorde is the exact TSP solver used as the optimal reference for feasible codebook sizes."}],"review_version":1}