{"id":"4e5cb6f7-f811-4600-ba65-1e5a6df998d7","arxiv_id":"2411.09803","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For binary linear codes with a full-message parity bit, the new SA-GCD decoder cuts GCD guesswork by up to half without changing block error rate.","lead":"This paper shows that adding a single parity-check bit to the message section of a binary linear code can halve the number of guesses a Guessing Codeword Decoder needs, with the same error rate. The trick is to use the parity bit as an outer code and a list version of ORBGRAND to order the guesses more cleverly.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SA-GCD's no-BLER-degradation claim relies on an unverified order-preservation property of list-ORBGRAND; a single delayed low-total-cost codeword would break the equality.","rationale":"The paper is a coherent applied contribution: the SA-GCD construction is clearly explained, the use of the SPC bit to reorder outer-code guesswork is sensible, and the empirical results for three code families support a guesswork reduction of up to roughly 2x with no observed BLER change. The factor-of-2 intuition is plausible because the SPC bit splits the guesswork into two parity classes. I did not find an internal inconsistency in the algorithm as described. The load-bearing gap is the one the reader identified: the no-degradation claim is not an invariant but a property of ORBGRAND's approximate ordering, and the paper gives no analytic condition under which the reordered list is guaranteed not to delay a codeword with total cost below the GCD stopping threshold. ORBGRAND's approximation is cited as having 'little impact on BLER' in its original setting, but that does not transfer automatically to the different task of feeding an order-sensitive stopping rule in GCD. The proposed exhaustive small-code check would directly test whether the required order-preservation property holds universally or only for the simulated parameter points. Since the concern is about missing proof rather than demonstrated error, the conditional verdict with moderate confidence remains appropriate; no change to the reader's verdict is needed.","tokens_in":9783,"tokens_out":10879,"duration_ms":110220,"concrete_test":"For the (7,3) simplex code of Figure 2, exhaustively search over all 2^7 hard-decision patterns and a fine grid of LLR magnitude vectors (or all distinct reliability orderings plus magnitude sampling) using the exact landslide generator. For each input, compare the decoded codeword of ORB-GCD and SA-GCD. If any input yields different outputs, the 'identical BLER' claim is false as a universal statement; if none does, record the smallest margin by which the stopping threshold separates the two orders and state the empirical scope of the claim. A complementary check is to replace list-ORBGRAND with the exact ML-ordered list of all 2^{k+1} outer SPC patterns; if SA-GCD with exact ordering still matches ORB-GCD, any observed discrepancy is attributable to ORBGRAND's approximation, which would pinpoint the missing invariant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim is that SA-GCD halves GCD guesswork 'without impacting decoding precision' relative to ORB-GCD. That claim is order-sensitive: GCD stops when cost(z^k) exceeds the best total codeword cost found so far, so the decoder must not skip or delay any z^k whose total cost (including the SPC bit) is below the stopping threshold. Section III asserts that list-ORBGRAND produces 'approximately the correct order' and that the only guesses pushed later have high cost(z^n), but this is not proven. ORBGRAND's landslide generator is an integer-partition approximation to the true LLR-ordered list; it is known to be inexact for arbitrary LLR vectors. If the approximation ever delays a low-total-cost z^k — for example, a genuine ML codeword with z_{k+1}=1 but very low cost(z^k) — past the GCD stopping point, SA-GCD would output a different codeword than ORB-GCD and the BLER curves would differ. The empirical BLER equality in Figures 3, 6, and 9 covers only three code families and no error bars or code are provided, so rare LLR configurations that violate the required order property are not ruled out. The paper's own acknowledgement that ORBGRAND is approximate is precisely the place where the universal no-degradation claim lacks support.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes single-parity-check-aided guessing codeword decoding (SA-GCD), a modification of GCD in which the code is viewed as a concatenation of an SPC outer code and an arbitrary inner code. Noise guesses are generated by list-ORBGRAND on the outer SPC code, so they are ordered by the cost of the first k+1 bits rather than by the cost of the first k bits alone. This reordering pushes guesses whose implied SPC bit is one later in the order, reducing the number of re-encodings needed to reach the GCD stopping condition, by up to a factor of two in the experiments. The authors also show that codes without a full-message SPC bit can be modified by adding one, with small measured performance loss for BCH and CRC codes.","tokens_in":10023,"tokens_out":13159,"duration_ms":124726,"significance":"If the claims hold, SA-GCD is a simple, parameter-free complexity reduction for a universal soft-input decoder, applicable to any binary linear code with the required SPC structure. The conceptual mechanism is clear and the paper correctly identifies the need for a fixed-Hamming-weight-capable pattern generator. The empirical validation covers three distinct code families and the reduction in guesswork is consistently positive and substantial at low-to-mid SNR. The principal weakness is that the central 'without impacting decoding precision' claim is not proven for the approximate ORBGRAND ordering and is stated more strongly than the evidence supports.","major_comments":[{"comment":"The no-BLER-degradation claim is load-bearing but is justified only heuristically. The text states that list-ORBGRAND produces 'an appropriate list with approximately the correct order' and that the only guesses pushed later have high cost(z_{k+1}) and thus high cost(z^n). Since ORBGRAND's ordering is an integer-partition approximation (as the paper itself notes in the Introduction), a single delayed pattern with low total codeword cost could, in principle, cross the stopping threshold and change the decoder output. Please either prove that under the exact ordering by cost(z^{k+1}) the SA-GCD stopping rule is exactly ML and state the approximation error condition under which ORBGRAND preserves this, or qualify the abstract's 'without impacting decoding precision' to 'no measurable degradation in the simulated cases.' The empirical equality in Figures 3, 6, and 9 alone does not support the universal claim.","section":"Section III"},{"comment":"The stopping rule is stated as 'cost(z^k) > min_q cost(z^{n,(q)})', but SA-GCD's list is ordered by cost(z^{k+1}) = cost(z^k) + cost(z_{k+1}). These two costs are not the same, and the reordering can place a later guess with strictly smaller cost(z^k) after an earlier one with larger cost(z^k). The paper should specify explicitly that the SA-GCD comparator uses cost(z^{k+1}) (or the generated list order) and prove that this is a valid lower bound on all future codeword costs; currently the text is ambiguous and Figure 2 is the only place where the intended comparator is visible.","section":"Section III"},{"comment":"Figures 3, 6, and 9 report that SA-GCD and ORB-GCD have 'identical' BLER, but no confidence intervals, error bars, or trial counts are provided. Since the abstract's central promise is an exact equality of decoding precision, the statistical evidence should be quantified. Please report the number of independent channel uses per SNR point and the observed maximum difference in BLER, or add error bars.","section":"Section IV"}],"minor_comments":[{"comment":"The notation z^{k+1} and z_{k+1} is used interchangeably in prose (e.g., 'cost(z_{k+1})' vs. 'cost(z^{k+1})'), which is confusing. Define both and use them consistently.","section":"Section III"},{"comment":"In the RLC experiments, the statement that a new code is generated for each channel use 'mimicking Shannon's original proof' is unusual for BLER evaluation; please clarify whether the reported BLER is averaged over code instances and how many were used.","section":"Section IV"},{"comment":"The y-axis label 'Average Guesswork Saved per Message Bit' is not defined. Specify the unit (number of re-encoded sequences per message bit) and how 'saved' is computed.","section":"Figures 4, 7, 10"},{"comment":"References [19] and [23] refer to the same ORBGRAND paper; please consolidate or cross-reference.","section":"References"},{"comment":"The claim that codes can be modified to include an SPC bit 'often' without losing decoding precision is stronger than the results show: the BCH example has 0.15 dB distortion and the CRC example has 0.1 dB. Replace 'without losing decoding precision' with 'with negligible or small, quantified loss.'","section":"Abstract and Section V"}],"recommendation":"major_revision","confidential_remarks":"The paper is a competent incremental contribution. The main gap is the unproven order-preservation assumption, which the authors can likely fix in revision by adding a formal lemma for the exact-ordering case and softening the universal claims. I would not recommend rejection; the mechanism is sound and the empirical results are useful. If the authors are unwilling to qualify the 'without impacting decoding precision' claim, the abstract should be revised."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a clean, honest engineering result. SA-GCD is a straightforward but new combination of two known techniques—even-code ORBGRAND and GCD—with a reordering argument that shifts high-total-cost guesses later. The empirical BLER and guesswork results for three code families support the claims. The main soft spot is that the \"no impact on decoding precision\" statement is not proven; it depends on ORBGRAND's approximate ordering. The paper says the order is \"approximately correct,\" and that is exactly where a universal claim needs more support. A single low-total-cost codeword delayed past the stopping point would change the BLER. The empirical equality is reassuring but limited to three code families, with no error bars or released code. That said, the concern is not fatal: ORBGRAND is known to be near-ML in practice, and the mechanism is coherent. The factor-2 bound is also heuristic—an upper limit that requires the SPC bit's reliability to dominate—but the paper is honest about that and the savings figures are plausible. The writing is clear, the figures are informative, and the citation pattern is appropriate. This is a useful contribution for people working on GRAND/GCD implementations; it deserves a serious referee. My recommendation: send it to review, ask for error bars or confidence intervals, the simulation code, and either a tighter analytical statement about the ordering condition or an explicit search for counterexamples.","headline":"Useful, honest complexity reduction for GCD via SPC-aided reordering; the no-degradation claim is plausible but lacks a proof and reproducible data.","tokens_in":10567,"tokens_out":2559,"would_cite":true,"duration_ms":26505,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","94B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adding one parity bit to a binary linear code can halve the guesswork of Guessing Codeword Decoding without changing its block error rate.","keywords":["guessing codeword decoding","single parity-check","ORBGRAND","guesswork reduction","even code","binary linear code","soft-input decoding","GRAND"],"falsifier":"Run SA-GCD and ORB-GCD on the same (128,104) random linear code realizations and LLR vectors at a symbol SNR around 2 dB and compare the decoded codewords: if any received vector yields different decoder outputs, the no-loss claim is false. More directly, one can search for a single LLR realization where the true maximum-likelihood codeword's message noise effect has parity opposite to the hard-decision SPC bit and appears after SA-GCD's stopping point; if such a case exists, SA-GCD is not equivalent to ORB-GCD on that instance.","tokens_in":9578,"feed_emoji":"⚡","tokens_out":5709,"duration_ms":51558,"temperature":0.7,"pith_summary":"The paper proposes single parity-check aided GCD (SA-GCD), a way to speed up Guessing Codeword Decoding (GCD) for any binary linear code whose generator matrix contains a full-message single parity-check (SPC) bit. It shows that by running list-ORBGRAND on the SPC outer code and feeding its guesses into GCD on the inner code, the decoder reaches its stopping condition with up to half the query count, with the largest savings at low signal-to-noise ratios. The key is that noise-effect patterns violating the SPC constraint cost more and are pushed later in the guess order, while likely codewords surface earlier. The paper also gives a column-operation recipe for modifying codes without an SPC bit to gain this advantage, and demonstrates on random linear codes, a modified BCH code, and a 5G CRC code that block error rate is not measurably changed. The practical payoff is that GCD is a universal soft-input decoder, and halving its dominant cost—guesswork—lowers decoding latency and energy for a broad class of codes.","feed_headline":"Adding one parity bit halves decoding guesswork","feed_subtitle":"A single parity bit can cut Guessing Codeword Decoding's queries by up to half at low SNR, with no loss in block error rate.","key_machinery":"The central object is the concatenated generator structure G = G_Out G_Inn, with G_Out = T[I_k 1] an SPC (even) outer code and G_Inn = [I_{k+1} P_Inn] an arbitrary inner code; the SPC bit is column k+1. The mechanism is a joint decoder in which list-ORBGRAND, using the landslide error-pattern generator (which can emit sequences of given Hamming weight and skip parity-invalid patterns), generates candidate message noise effects $z^{{k+1}}$ for the inner code in approximately decreasing likelihood order. This ordering is then used as the noise-effect guesswork for GCD on the full code. The machinery works because GCD's stopping condition depends only on the cost of the current message noise effect versus the best codeword cost already found, so pushing high-cost, parity-mismatching guesses later in the order shortens the guesswork without delaying the maximum-likelihood codeword. The paper's applicability rule is that a set of k columns of G must span F_2^k and their mod-2 sum must equal a (k+1)th column, which in systematic form means the generator has an all-ones column.","core_discovery":"On the paper's own terms, the central discovery is that the parity constraint of an outer SPC code is usable as a free source of ordering information for GCD. When the code C is decomposed as an SPC outer code concatenated with an arbitrary inner code, list-ORBGRAND on the outer code produces, for every query, a valid outer codeword rather than a raw message noise effect. Guesses whose message part has parity mismatching the hard-decision SPC bit carry an extra z_{k+1}=1 term, hence larger reliability cost, so they appear later in the guess sequence; guesses consistent with the parity constraint appear earlier. Because GCD's stopping rule compares the cost of the current message noise effect with the best codeword cost already found, reordering in this way lets the codewords that matter for the maximum-likelihood decision be examined first, and the decoder stops sooner. The paper claims this reduces the number of queries by up to a factor of 2, with the largest proportional savings at low SNR, and that the block error rate of SA-GCD matches that of ORB-GCD on the tested code families.","pith_inferences":["The same reordering idea could be generalized to outer codes richer than a single parity check, such as any even code or any code with a small trellis, where list decoding produces only valid outer codewords; the gain would then depend on how much extra likelihood information the outer constraint provides.","The guesswork savings being largest at low SNR suggests SA-GCD is a natural fit for rateless or incremental-redundancy schemes, where decoding begins before the SNR is high enough for the zero-noise guess to dominate.","If ORBGRAND's ordering approximation is later improved or replaced by an exact soft maximum-likelihood pattern generator, the SA-GCD mechanism should still work and would likely make the no-block-error-rate-loss property provable rather than empirical."],"forward_implications":["For any binary linear code that admits the SPC decomposition, SA-GCD can halve the number of re-encoding queries in the low-SNR regime while matching ORB-GCD's block error rate.","Codes without a full-message SPC bit can be modified by replacing one generator-matrix column with an all-ones column; for the BCH and CRC codes tested, this costs at most about 0.15 dB and enables the guesswork reduction.","The scheme inherits the code-agnostic property of GCD and GRAND, so it applies to arbitrary inner codes once the SPC outer structure is present.","Because the guesswork reduction comes from a single parity computation on the received hard-decision bits, no extra online computation is needed to decide which guesses to skip, which is favorable for circuit implementations."],"supporting_citations":[{"why":"Defines GCD and its stopping rule based on comparing message noise-effect cost with the best codeword cost already found; SA-GCD builds directly on this decoder.","marker":"[5]"},{"why":"Shows that even codes permit skipping parity-invalid noise patterns, the observation SA-GCD exploits through the SPC outer code.","marker":"[9]"},{"why":"Introduces ORBGRAND and the landslide error-pattern generator that can emit sequences of given Hamming weight, the practical enabler of SA-GCD.","marker":"[14]"},{"why":"Establishes that list-GRAND outputs codewords in decreasing likelihood order, which justifies using list-ORBGRAND as an approximately ordered guesswork source.","marker":"[7]"},{"why":"Provides the soft-information LLR framework for generating noise-effect sequences in decreasing likelihood order, on which GCD and SA-GCD rely.","marker":"[13]"},{"why":"Introduces GRAND and the principle of querying noise effects in decreasing likelihood order, the foundation of the guesswork framework.","marker":"[1]"}],"fun_headline_variants":["Single parity bit halves GCD guesswork at low SNR","Parity check cuts GCD queries by up to half","One parity bit: up to 2x fewer queries for GCD","Adding one parity bit reduces decoding guesswork"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that ORBGRAND's approximate likelihood ordering is accurate enough that reordering the same guesses by the SPC bit never pushes the true most-likely codeword past the point where decoding stops; the paper shows this empirically for three code families but does not prove it analytically.","fun_headline_variants_meta":{"raw":{"variants":["Single parity bit halves GCD guesswork at low SNR","Parity check cuts GCD queries by up to half","One parity bit: up to 2x fewer queries for GCD","Adding one parity bit reduces decoding guesswork"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000712,"raw_usage":{"total_tokens":3211,"prompt_tokens":957,"completion_tokens":2254,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":2190}},"tokens_in":573,"tokens_out":2254,"duration_ms":15645,"temperature":1.0,"reasoning_tokens":2190,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:18:01.797369+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SA-GCD and ORB-GCD on the same (128,104) random linear code realizations and LLR vectors at a symbol SNR around 2 dB and compare the decoded codewords: if any received vector yields different decoder outputs, the no-loss claim is false. More directly, one can search for a single LLR realization where the true maximum-likelihood codeword's message noise effect has parity opposite to the hard-decision SPC bit and appears after SA-GCD's stopping point; if such a case exists, SA-GCD is not equivalent to ORB-GCD on that instance.","supporting_citations":[{"cited_title":"Constrained error pattern gener ation for grand,","cited_arxiv_id":null,"evidence_quote":"Shows that even codes permit skipping parity-invalid noise patterns, the observation SA-GCD exploits through the SPC outer code."},{"cited_title":"List-GRAND : A practical way to achieve maximum likelihood decoding,","cited_arxiv_id":null,"evidence_quote":"Establishes that list-GRAND outputs codewords in decreasing likelihood order, which justifies using list-ORBGRAND as an approximately ordered guesswork source."},{"cited_title":"Soft maximum li kelihood decoding using GRAND,","cited_arxiv_id":null,"evidence_quote":"Provides the soft-information LLR framework for generating noise-effect sequences in decreasing likelihood order, on which GCD and SA-GCD rely."},{"cited_title":"Capacity-achieving g uessing random additive noise decoding (GRAND),","cited_arxiv_id":null,"evidence_quote":"Introduces GRAND and the principle of querying noise effects in decreasing likelihood order, the foundation of the guesswork framework."}],"review_version":1}