{"id":"5e147a47-6295-4875-96d1-7831186f191b","arxiv_id":"2507.17893","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Reinforcement learning with action-list (beam) search decodes short LDPC codes over the binary symmetric channel with performance close to bounded-distance decoding.","lead":"This paper trains reinforcement learning agents to correct errors by flipping bits in received codewords, and it keeps a list of the most promising flip paths to avoid getting stuck. The method is shown to approach ideal bounded-distance decoding on a standard LDPC code and can also be bolted onto existing decoders to improve them.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'approaches BDD(10)' claim rests on all-zero-codeword FER, but the paper's own anisotropy argument (Sec. IX) breaks the decoder-symmetry condition (Sec. V) needed to equate that with average FER.","rationale":"Good-faith reading: the paper proposes a plausible beam-search-style list decoder built on DQN Q-values, plus a feedback wrapper, and reports large FER gains on the Tanner (155,64,20) code. The load-bearing question is not whether the algorithm works in some configuration, but whether the headline comparison to BDD(10) is a fair average-performance statement. The paper's Section V explicitly relies on decoder symmetry to justify all-zero-codeword simulation; Section IX undercuts that reliance by attributing the benefit of automorphisms to RL-induced anisotropy. These two statements cannot both hold in the strong form needed: if the policy is position-dependent, then the all-zero-word FER is not the code-average FER. Since no code, seeds, or confidence intervals are released, this cannot be checked post hoc. The reader flagged exactly this as the weakest assumption; I agree. The Theorem 3 issue is real but less load-bearing for the headline: it concerns state-space counting for QC-LDPC reduction, not the FER comparison. The recommendation is therefore to keep the CONDITIONAL verdict, with the added condition that the authors demonstrate codeword-averaged performance or explicitly qualify the claim.","tokens_in":19332,"tokens_out":4183,"duration_ms":45005,"concrete_test":"Recompute the Fig. 8 list-size-5 automorphism curve with test transmissions drawn uniformly from all codewords (or, equivalently, apply a uniformly random automorphism before decoding and its inverse after decoding, for each received word), at the same BSC crossover probabilities. Compare the resulting average FER against the BDD(10) curve. If the average lies above BDD(10) by more than the Monte Carlo standard error, the headline claim must be rephrased as conditional on the all-zero codeword; if it matches, the symmetry concern is empirically resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central performance claim — action-list list-size-5 plus automorphisms approaches BDD(10) on the Tanner code — is evaluated under the Section V assumption that transmitting the all-zero codeword suffices, citing Richardson–Urbanke Lemma 1. That lemma requires decoder symmetry. The paper then states in Section IX that 'the sequential nature of reinforcement learning introduces anisotropy, position-dependent bit-flipping rules,' which is precisely a violation of decoder symmetry. The automorphism trick is a partial mitigation: applying (p-1) cyclic shifts averages the policy over some positions, but the reported Monte Carlo FER curves are still conditional on the all-zero transmitted word unless the test set includes random codewords. BDD(10) FER from Eq. (1) is an average over all error positions; for an asymmetric decoder the all-zero conditional FER can differ from the codeword-averaged FER, potentially making the comparison optimistic. The paper provides no error bars and no code, so the size of this effect is unquantified. No internal contradiction in the action-list algorithm itself is identified; the issue is whether the benchmark answers the question asked.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a reinforcement-learning framework for syndrome-based bit-flipping decoding of binary linear block codes. It introduces a truncated MDP that restricts the state space to syndromes inside a Hamming ball of radius w, an action-list decoder that uses DQN Q-values to maintain a beam of k candidate flip sequences, a feedback decoder that attaches an RL block to an existing decoder, and an automorphism-group reduction for QC-LDPC codes based on Burnside counting and lexicographic canonical representatives. Numerical results are reported for the Tanner (155,64,20) code and a random (24,6,10) code. The main claim is that action-list decoding with list size 5 combined with cyclic automorphisms closely approaches BDD(10), and that the DQN generalizes to error patterns beyond its training radius.","tokens_in":19576,"tokens_out":30852,"duration_ms":357477,"significance":"If the central claims held, the action-list mechanism would be a useful way to convert imperfect DQN policies into low-FER decoders for short and moderate-length codes, and the automorphism-based state reduction could be valuable for QC-LDPC training. The paper's strengths are its explicit pseudocode, the use of concrete BDD baselines, and the error-floor estimation methodology. However, the key experimental evidence is not auditable from the preprint: there is no code, no trial counts, no seeds, and no error bars. In addition, the BDD(10) baseline is not a well-defined bounded-distance decoding curve for a code of minimum distance 20, and the lower bound in Theorem 3 is not proved. The paper is therefore promising but not yet ready for publication.","major_comments":[{"comment":"The lower bound in Theorem 3 is not established by the proof. The Burnside calculation in Appendix D counts orbits of all binary colorings of the jp check-node coordinates, giving Nfull, but the valid syndrome space is the rank(H)-dimensional subspace im(H), not the full coloring set. The step that divides by 2^{m-rank(H)} is asserted in one sentence (the coloring of redundant rows can be identified through independent row colorings) and is not a derivation. The upper bound Ns ≤ Nfull follows from the subset relation, but the lower bound does not follow from Burnside's lemma. The theorem should either be proved or restated as an upper bound; as written, the state-space reduction claim in Section IX is unsupported.","section":"Section IX-B, Theorem 3 (Eq. (43)) and Appendix D"},{"comment":"The baseline labeled BDD(w=10) is not the frame error rate of a valid bounded-distance decoder for the Tanner code. Since dmin=20, t=9, and there exist pairs of codewords at distance 20, a weight-10 error pattern can be equidistant from two codewords; such patterns are not uniquely correctable by any decoder. Equation (1) counts all weight-i patterns for i≤10 as corrected, so for w=10 it is a genie-aided bound, not a BDD curve. The headline claim that the action-list decoder closely approaches BDD(10) is therefore ambiguous. Please define the baseline explicitly as a genie-aided bound, or compute the true BDD(10) performance with ties taken into account.","section":"Section II-A (Eq. (1)), Figs. 7-8"},{"comment":"The empirical claims cannot be audited from the manuscript. There is no code, no dataset, no random seed, no number of Monte Carlo trials, and no confidence intervals. Several FER curves extend below 10^-8 (Figs. 7 and 8), which would require at least 10^10 trials per point; the paper does not state how these curves were obtained. The claims that DQN generalizes to untrained states and that list-size-5 plus automorphisms approaches BDD(10) rest entirely on these curves. Please provide the simulation protocol and either release the code and data or include statistical error bars.","section":"Section X (Figs. 5-9)"}],"minor_comments":[{"comment":"The all-zero-codeword evaluation is actually justified for these syndrome-based decoders: for any transmitted codeword c, the syndrome of y=c+e equals the syndrome of e, so the same bit-flip sequence is applied and the frame error decision is identical. The anisotropy discussed in Section IX concerns dependence on the error-pattern position, not dependence on the transmitted codeword. The paper should state this explicitly, since the current wording invites confusion.","section":"Section V and Section IX"},{"comment":"Several reward definitions contain is s instead of if s; please correct these typos.","section":"Eqs. (13), (21), (29), (31)"},{"comment":"The displayed product is ambiguous (it should presumably be i^{binom(n,i)}), and the proof text describes i*binom(n,i) possible optimal actions and then multiplies over i. The notion of distinct optimal policy is never defined. Please clarify the statement and proof.","section":"Theorem 1 and Appendix A"},{"comment":"Equation (12) counts error patterns, not necessarily distinct syndromes. Equality holds when all error patterns of weight at most w have distinct syndromes (true for the Tanner code for w≤9 because t=9), but the condition should be stated for general codes.","section":"Section V, Eq. (12)"},{"comment":"The captions of Figs. 7 and 8 use beam sizes while the text uses list sizes; please unify the terminology and add the number of trials to each figure caption.","section":"Figure captions and Section X"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within scope and the action-list idea is worth pursuing, but I would not accept it in its current form. The main obstacles are the unproved lower bound in Theorem 3, the ambiguous BDD(10) baseline, and the lack of reproducible experimental evidence. I would ask the authors to fix these before resubmission; if the experiments cannot be made reproducible, I would lean toward rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version. The action-list decoding idea is real: expanding the beam according to Q-value improvement and pruning to top-k is a sensible way to stabilize a learned bit-flipping policy, and the feedback wrapper that trains RL only on the failure set of an existing decoder is a practical touch. The reported gains on the Tanner code, with list size 5 plus cyclic automorphisms getting close to BDD radius 10, would be a useful result for short-block LDPC if it holds up.\n\nWhat's solid: the tabular Q-learning matches BDD for w=1,2,3, which is a good sanity check; the paper is up front about the anisotropy that RL introduces and tries to mitigate it with automorphisms; and the action-list algorithm is specified precisely enough to reimplement.\n\nThe soft spots are serious, though. Theorem 3 as written is false. For the length-3 single parity-check code with j=1,p=3, Nfull=4 but the syndrome space has exactly two orbits (0 and 1), so the lower bound Ns >= 4 is impossible. The proof counts orbits of colorings, not orbits of syndromes; dividing by 2^{m-rank(H)} doesn't fix that, as the counterexample shows. This theorem isn't load-bearing for the main simulations (the automorphism trick is used at inference, not for state-space reduction), but it can't stay as stated.\n\nTheorem 2's proof also doesn't match its reward. Equation (21) gives the same reward for reaching any syndrome outside the failure set, so the agent has no incentive to avoid miscorrection, yet the proof assumes the decision boundary between the correctable and miscorrectable regions is respected. The bound may hold for the modified reward (23), but as written the argument is incomplete.\n\nThe bigger problem is the evaluation. No code, no data, no error bars. FER curves down to 1e-10 need many samples, and without confidence intervals the 'approaches BDD(10)' claim can't be audited. The all-zero-codeword issue is real: Section V invokes the Richardson-Urbanke symmetry lemma, but Section IX explicitly says RL policies are position-dependent. The automorphism-averaging helps, but the Tanner code's automorphism group is not transitive on all 155 positions, so averaging over cyclic shifts doesn't fully symmetrize the decoder. Unless the Monte Carlo runs used random codewords, the reported FER is conditional on the zero word and may be optimistic.\n\nNet: this deserves a serious referee. The action-list idea is new enough and the empirical direction is useful enough to justify review. But the authors need to fix or qualify Theorem 3, align Theorem 2 with its reward, and either release code/data or provide confidence intervals plus a random-codeword evaluation. I'd send it out, expecting major revision.","headline":"New RL decoding recipe with a real action-list idea, but a false theorem and unaudited FER curves make the headline BDD(10) claim conditional.","tokens_in":20119,"tokens_out":5156,"would_cite":false,"duration_ms":55451,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a reinforcement-learning decoder guided by Deep Q-Network values and run as a short action list can bring the Tanner (155,64,20) code close to bounded-distance decoding with radius 10, correcting most error patterns…","keywords":["reinforcement learning","action-list decoding","beam decoding","automorphism group","bit-flipping decoding","linear block codes","QC-LDPC codes","bounded distance decoding"],"falsifier":"Run the trained list-size-5-plus-permutations decoder on a large set of random transmitted codewords of the Tanner code, not just the all-zero word, and compare the measured frame error rate; if it rises materially, the claimed approach to bounded-distance radius-10 decoding is conditional on the all-zero test. A second check is to enumerate all error patterns of weight exactly 10 and confirm every one is corrected, since bounded-distance decoding with radius 10 corrects all of them.","tokens_in":19106,"feed_emoji":"📡","tokens_out":10140,"duration_ms":111240,"temperature":0.7,"pith_summary":"The paper proposes a general recipe for turning binary linear block-code decoding into a reinforcement-learning task: the state is the syndrome of the received word, an action is flipping one bit, and a learned Q-function guides the decoder to the all-zero syndrome. To keep the state space tractable, it truncates the MDP to a Hamming ball of radius $w$ around codewords and shows that a Deep Q-Network trained on this smaller space corrects errors outside the ball. It then adds action-list decoding, a beam-search-like scheme over the Q-values, and uses the code's automorphism group to permute received words, because RL bit-flipping rules are position-dependent even on a symmetric channel. On the Tanner $(155,64,20)$ code, list size 5 plus these permutations approaches bounded-distance decoding with radius 10, correcting most error patterns of weight up to 10 although the code's guaranteed correction radius is nine; a feedback variant wraps an existing bit-flipping decoder and trains RL only on that decoder's failures.","feed_headline":"Five candidate flips near the bounded-distance limit","feed_subtitle":"Reinforcement learning plus code symmetries corrects most weight-10 errors, beyond the code's guaranteed radius.","key_machinery":"The machinery has four moving parts. The truncated MDP replaces the full syndrome space by the set of syndromes reachable from a Hamming ball $B(w)$ of radius $w$ around codewords, so the agent trains only on the most probable error patterns and the state count shrinks from $2^{n-k}$ to roughly the number of words within the ball. A Deep Q-Network approximates the action-value function $Q(s,a)$ for flipping bit $a$ in syndrome state $s$; the reward is a small penalty per flip plus a terminal bonus for reaching the all-zero syndrome, so good paths are short bit-flip sequences. Action-list decoding is beam search over these Q-values: at each state it keeps the top $k$ actions, extends only paths whose next Q-value exceeds the parent's score, and prunes back to the top $k$ until a zero syndrome appears, which suppresses the oscillation that greedy use of approximate Q-values causes. The automorphism group of the quasi-cyclic code supplies cyclic permutations of bit positions that are applied to the received word and inverted on the output; because RL bit-flipping rules are position-dependent, permuting the word lets the same learned rules handle many error patterns. A feedback decoder wraps an existing bit-flipping decoder and trains the RL block only on the failure region, so the state space stays small while the correctable region expands.","core_discovery":"The central claim is that approximate Q-values can be turned into a reliable decoder by keeping a short list of candidate flipping paths instead of one greedy action. For the Tanner $(155,64,20)$ code, the action-list decoder with list size 5, combined with cyclic permutations from the automorphism group, closely approaches bounded-distance decoding with radius 10: it corrects most error patterns of weight up to 10, beyond the code's guaranteed correction radius of $t=9$. The same truncated-MDP and action-list construction is claimed to apply to any binary linear block code, and the feedback decoder is claimed to lift any existing decoder by training RL only on the error patterns that decoder fails to correct.","pith_inferences":["If the position dependence that motivates the automorphism trick is real, then the all-zero-codeword evaluation is not automatically representative of average frame error rate; averaging over random transmitted codewords or over the automorphism orbit would tell whether part of the reported gain is an artifact of the test condition.","The monotone pruning rule (extend only when the next Q-value exceeds the parent's score) is an extra assumption about approximate Q-values; a natural variant is to keep the top $k$ successor Q-values regardless of monotonicity and compare robustness.","The same truncated-MDP and action-list pattern should transfer to soft-decision channels and to other learned decoders, since the feedback wrapper only needs the base decoder's failure syndromes rather than its internals."],"forward_implications":["A Deep Q-Network trained inside a small Hamming ball generalizes to error patterns of higher weight that it never saw, so the RL state space does not need to cover the full syndrome space.","The action-list decoder with list size 5 plus cyclic automorphisms brings the Tanner $(155,64,20)$ code close to bounded-distance decoding with radius 10, so most weight-10-or-less error patterns are corrected despite a guaranteed radius of $t=9$.","The feedback decoder gives a direct route to improving an existing iterative decoder: train the RL block on the failure syndromes only, and its correctable region expands while training complexity stays low.","Because the scheme is formulated for arbitrary binary linear codes and any base decoder, the same pieces transfer to other short-block codes and other decoders."],"supporting_citations":[{"why":"Supplies the bit-flipping MDP formulation and the reward function that the paper adapts and extends.","marker":"[14]"},{"why":"Defines bounded-distance decoding and the Hamming-ball viewpoint used as the performance baseline and the truncation principle.","marker":"[17]"},{"why":"Provides the Q-learning and Deep Q-learning background, convergence conditions, and epsilon-greedy machinery the algorithms build on.","marker":"[18]"},{"why":"Provides the symmetry lemma that justifies restricting evaluation to the all-zero codeword.","marker":"[19]"},{"why":"Introduces beam search, the conceptual basis of the action-list expansion and pruning rules.","marker":"[20]"},{"why":"Defines the group-structured QC-LDPC code family and the automorphism structure exploited for permutation decoding.","marker":"[21]"},{"why":"Supplies the linear-time lexicographically minimal rotation algorithm used to canonicalize states under the automorphism group.","marker":"[22]"}],"fun_headline_variants":["RL decoder with action-list pushes past bounded-distance limit","Short action list boosts RL syndrome decoding beyond radius","Action-list RL decoding exceeds guaranteed radius for LDPC","List of 5 flips makes RL decoder approach bounded-distance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported error rates assume the decoder is symmetric enough that transmitting the all-zero codeword represents every codeword; the paper's own account of position-dependent RL rules makes that symmetry assumption doubtful.","fun_headline_variants_meta":{"raw":{"variants":["RL decoder with action-list pushes past bounded-distance limit","Short action list boosts RL syndrome decoding beyond radius","Action-list RL decoding exceeds guaranteed radius for LDPC","List of 5 flips makes RL decoder approach bounded-distance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000617,"raw_usage":{"total_tokens":2841,"prompt_tokens":896,"completion_tokens":1945,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":512,"completion_tokens_details":{"reasoning_tokens":1880}},"tokens_in":512,"tokens_out":1945,"duration_ms":12855,"temperature":1.0,"reasoning_tokens":1880,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:39:37.509119+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the trained list-size-5-plus-permutations decoder on a large set of random transmitted codewords of the Tanner code, not just the all-zero word, and compare the measured frame error rate; if it rises materially, the claimed approach to bounded-distance radius-10 decoding is conditional on the all-zero test. A second check is to enumerate all error patterns of weight exactly 10 and confirm every one is corrected, since bounded-distance decoding with radius 10 corrects all of them.","supporting_citations":[{"cited_title":"Reinforce- ment Learning for Channel Coding: Learned Bit-Flipping Decoding,","cited_arxiv_id":null,"evidence_quote":"Supplies the bit-flipping MDP formulation and the reward function that the paper adapts and extends."},{"cited_title":"Lin and D","cited_arxiv_id":null,"evidence_quote":"Defines bounded-distance decoding and the Hamming-ball viewpoint used as the performance baseline and the truncation principle."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Q-learning and Deep Q-learning background, convergence conditions, and epsilon-greedy machinery the algorithms build on."},{"cited_title":"The Capacity of Low-Density Parity-Check Codes under Message-Passing Decoding,","cited_arxiv_id":null,"evidence_quote":"Provides the symmetry lemma that justifies restricting evaluation to the all-zero codeword."},{"cited_title":"Simulation-Guided Beam Search for Neural Combinatorial Optimization,","cited_arxiv_id":null,"evidence_quote":"Introduces beam search, the conceptual basis of the action-list expansion and pruning rules."},{"cited_title":"A Class of Group-Structured LDPC Codes,","cited_arxiv_id":null,"evidence_quote":"Defines the group-structured QC-LDPC code family and the automorphism structure exploited for permutation decoding."},{"cited_title":"Lexicographically Least Circular Substrings,","cited_arxiv_id":null,"evidence_quote":"Supplies the linear-time lexicographically minimal rotation algorithm used to canonicalize states under the automorphism group."}],"review_version":1}