{"id":"33abc8c8-3856-401c-a528-4f2e9cb20347","arxiv_id":"2501.12834","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A finite-computation achievability bound for sequential decoding of random tree codes, optimized by a greedy bit-placement rule, approaches the random-coding union and Gallager benchmarks for pure random codes.","lead":"Random tree codes are optimized here for a decoder that must stop after a fixed number of checks. The paper derives an analytical error bound for this setting, then greedily chooses where message bits enter the code, and reports that the optimized bound nearly matches the bound for fully random maximum-likelihood decoding.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The numerical CLE bound treats the common prefix of the true and competing paths as independent, which can make D^G_CLE smaller than the exact term and invalidate the tabulated upper bounds.","rationale":"The reader's weakest-assumption concern about stack memory does not appear to bite: after any number of expansions, the live stack size equals Nc minus the number of popped nonterminal nodes, so it is never larger than Nc; a stack of capacity L suffices to execute the algorithm until the Nc > L exit. The genuine problem is the independent-prefix relaxation in the CLE bound used for all numerical tables. The paper's central existence theorem (Theorem 1) and the RCU/CFE connections are not affected by this issue, so the appropriate outcome is a conditional accept once the common-prefix factors are corrected and the tables are recomputed. If the correction shows that the bounds were materially understated, the claim that CORT codes approach the ML performance of pure random codes would need to be weakened or substantiated with corrected numbers. This concern is precise, checkable, and independent of any disagreement with the community consensus.","tokens_in":15044,"tokens_out":64788,"duration_ms":614948,"concrete_test":"Take the SBP-optimized s for one table entry, e.g., p=0.02, L=10^11, gamma=0.9992 in Table IV. For each h with a gap b_{h+1} > b_h+1, recompute the h'=h term with the exact factor 1 on t=b_h+1,...,b_{h+1}-1 instead of the independent product in (53), leaving all other terms as in the paper. If the corrected D^G_CLE increases by more than the slack in D^G_E - (D^G_CLE + D^G_CFE), or makes D^G_E exceed the claimed 7.5e-6, the numerical central claim fails. A second check: re-derive equation (53) directly by computing E[2^{\\vartheta(d_t(x,y)-d_t(\\bar x,y))}] under \\bar x_t = x_t; it equals 1, not (55) times (56).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing numerical claim rests on Theorem 6's upper bound D^G_CLE, but the Chernoff relaxation in (48)/(53) mishandles the common-prefix segment. In (34)-(40), for the event tau_h = b_{h'}, the messages m and \\bar m agree through stage h'; the first differing bit does not arrive until time b_{h'+1}. For every t in [b_{h'}+1, b_{h'+1}-1], the codeword bits satisfy \\bar x_t = x_t, so the cost difference d_t(x,y) - d_t(\\bar x,y) is identically 0 and its Chernoff factor is 1. Equation (53) instead factors E[2^{-\\vartheta d_t(\\bar x,y)}] E[2^{\\vartheta d_t(x,y)}], treating these equal bits as independent. For BSC p=0.02, gamma near 1, and \\vartheta near 1/2, this product is about 0.67 via (55)-(56), not 1. The h'=h term should enter D^M_CLE with probability 1, but the relaxed formula multiplies it by products of 0.67 for every gap symbol, so D^G_CLE can be strictly smaller than the exact computation-limit term. Hence the inequality D^M_CLE <= D^C_CLE in Theorem 6 is not guaranteed, and the Table I-IV values are not established as upper bounds.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies random tree codes under a stack-based sequential decoder (SSDGU) with a hard computational limit L. The main result, Theorem 1, decomposes the frame error probability into a computation-limit-error (CLE) term and a computation-free-error (CFE) term. The authors derive relaxations of these terms, connect the CFE term to the random coding union and Gallager bounds, and propose a successive bit placement (SBP) heuristic to optimize the tree branching profile and a discounted decoding cost measure. Numerical evaluations for a (128,64) code over the BSC suggest that the optimized bound approaches the ML decoding performance of pure random codes at moderate L.","tokens_in":15348,"tokens_out":7365,"duration_ms":67303,"significance":"If the bounds are valid, the paper offers a principled design methodology for tree codes under hard computational limits, connecting sequential decoding with finite-blocklength random-coding bounds. Theorem 4's reduction of the CFE term to the RCU bound is elegant, and the SBP optimization framework is a useful contribution. However, the numerical claims rest on the correctness of the CLE bound and on the assumptions of the decoding algorithm's memory model, both of which have serious issues in the current manuscript.","major_comments":[{"comment":"The stack memory assumption is not consistent with the algorithm description. The stack S is initialized with c0 nodes, and each iteration pops one node and adds its ch children, so after N checks the live stack contains c0 + sum_{i=1}^{N}(c_i - 1) entries. For a binary tree with ch=2, this is c0 + N, which exceeds L well before N reaches L. If the stack is truly limited to L entries, the algorithm must either overflow or terminate early, so the event {the algorithm gives up} can occur even when the count in inequality (12) is below L. Consequently, the bound Pr(mhat = epsilon) <= D_CLE[s,d] in Theorem 1 is not established for the described algorithm with stack capacity L. The statement 'the memory capacity of the stack is assumed to be as large this computational limit' does not resolve this, because the number of live nodes is not bounded by the number of checks.","section":"Section II-B, Algorithm 1 and Theorem 1"},{"comment":"The Chernoff relaxation in Eq. (53) is not valid for the common-prefix segment. In the event tau_h = b_{h'}, the message prefixes agree through stage h', so for every t in [b_{h'}+1, b_{h'+1}-1] the coded bits satisfy bar x_t = x_t and hence d_t(bar x_t, y_t) - d_t(x_t, y_t) = 0. The correct factor for these positions is 1. Equation (53) instead factors E[2^{-vartheta d_t(bar x_t,y_t)}] E[2^{vartheta d_t(x_t,y_t)}], treating bar x_t and x_t as independent. For BSC p=0.02, gamma near 1, and vartheta near 1/2, each such factor is about 0.64, not 1, so D^G_CLE can be strictly smaller than the exact CLE term. Therefore the inequality D^M_CLE <= D^C_CLE in Theorem 6 is not guaranteed for the BSC evaluation, and the numerical upper bounds in Tables I-IV are not established.","section":"Section III, Theorem 6, Eqs. (48) and (53)"},{"comment":"Table II shows D^G_CFE = 2.1e-3 for L=10^9, 1.5e-5 for L=10^10, and 1.4e-3 for L=10^11, with the same p=0.03 and gamma=0.9992. Since D^G_CFE is independent of L after SBP optimization but the optimized s(t) can vary with L, a non-monotonic change of two orders of magnitude is surprising and needs explanation. As written, this appears to be an internal inconsistency (possibly a typo) and undermines confidence in the numerical tables.","section":"Table II"}],"minor_comments":[{"comment":"There are numerous typos and grammatical errors, e.g., 'optimizated' (Abstract), 'memorlyless' (after Eq. (33)), 'lenght' (Section II-A), 'paramater' (Section II-B), 'inequlity' (Eq. (47) proof), 'abondons' (Introduction). A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The second product in Eq. (48) runs from t=b_{h+1} to n, but the exponent only contains d_{b_{h'}+1:n}(x,y) minus d_{b_{h'}+1:r[h]}(bar x,y), so the second product should start at t=r[h]+1, not b_h+1. Please correct the index.","section":"Section III, Eq. (48)"},{"comment":"The definition of r[h] appears before Eq. (34) as r[h] = r_{s(b_h)}, but it is not explicitly defined in the text; please state it clearly.","section":"Section III, Eq. (40) and surrounding text"},{"comment":"The caption for Table I says 'CONSIDEREING' and the table entries use inconsistent formatting (e.g., '3 .6' with a space); please format consistently.","section":"Section IV, Table I caption"}],"recommendation":"major_revision","confidential_remarks":"The paper's central numerical claim depends on the correctness of the CLE bound; the flaw in Eq. (53) directly invalidates the tabulated upper bounds, and the stack memory issue affects Theorem 1's applicability. Both are fixable in principle, but the numerical results will need to be recomputed and the algorithm's memory model re-examined. The paper should also clarify whether the stack can really be bounded by L or whether the computational limit should be redefined to include stack capacity."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The CLE/CFE decomposition is real and useful. Splitting the SSDGU error into computation-limit and computation-free parts, then reducing the CFE term to RCU/Gallager bounds, is a clean idea that short-blocklength people will want. Theorems 1-4 are solid; the SBP optimizer is a sensible way to search irregular profiles. That part of the paper deserves attention.\n\nThe load-bearing numerical results do not hold up. In (53), the Chernoff relaxation factors E[2^{ϑ(d_t(x,y)-d_t(\\bar x,y))}] into E[2^{-ϑ d_t(\\bar x,y)}]E[2^{ϑ d_t(x,y)}]. For the common-prefix segment between b_{h'} and b_{h'+1}, the true exponent is identically 0, so the factor is 1. The factored expression is about 0.67 for BSC p=0.02 with gamma near 1 and theta near 1/2, so D^G_CLE can be strictly below the exact CLE term. That invalidates Theorem 6 as stated and means Tables I-IV are not established upper bounds. This is not a cosmetic issue; it is the main numerical claim.\n\nAlso, Algorithm 1's memory model is inconsistent. If the stack capacity is L, the stack overflows before L checks because each pop adds ch-1 net entries. Equation (12) and Theorem 1 assume no overflow. The author notes the stack memory drawback in the conclusion but doesn't fix the analysis. Table II has a typo (CFE cannot vary with L), and no code or optimized s(t) profiles are given, so the tables can't be reproduced.\n\nCredit where due: The Theorem 4 reduction to RCU is nice, and the paper is self-contained about what is and isn't proven. The problems are addressable: replace the invalid factorization with a correct treatment of the common prefix (or use a valid upper bound), fix the memory model, correct the tables, ship code. The CFE-minimization claim for pure random codes also needs proof or softening.\n\nWho this is for: coding theorists working on sequential decoding, PAC codes, short-blocklength bounds. Worth a serious referee, but the reviewer should be asked to verify the numerics rather than just read them. My recommendation: send to peer review with major revision; do not accept the numerical bounds until the (53) issue is resolved.","headline":"A genuinely useful CLE/CFE decomposition, but the numerical claims rest on a Chernoff-factorization error and a violated memory assumption; worth reviewing, not worth trusting the tables as-is.","tokens_in":15895,"tokens_out":10481,"would_cite":false,"duration_ms":95742,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94B35","94B70"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves an achievability bound for irregular random tree codes decoded by a stack-based sequential decoder with a hard node budget, and shows that optimizing branching structure and a discounted cost measure brings the bound…","keywords":["random tree codes","sequential decoding","stack algorithm","computational limit","achievable error bound","successive bit placement","discounted decoding cost","random coding union bound"],"falsifier":"Run SSDGU with a stack that physically cannot hold more than $L$ entries on a $(128,64)$ optimized CORT ensemble over the BSC at $p=0.02$ with $L=10^{9}$, and record how often the decoder returns $\\varepsilon$ because of stack overflow before $L$ node checks; if that frequency exceeds $D_{\\mathrm{CLE}}$, the achievability bound does not describe the memory-capped decoder.","tokens_in":14797,"feed_emoji":"🌳","tokens_out":13151,"duration_ms":120243,"temperature":0.7,"pith_summary":"This paper attempts to establish a computable guarantee for tree codes when the decoder is allowed only a fixed number of node checks. It proves an achievability bound that splits the frame error probability into a computation-limit term and a computation-free term, then shows how to optimize the code's branching structure and a discounted decoding cost so that the bound approaches the ML error of pure random codes. The practical upshot would be a design procedure for error-correcting codes tuned against a bound rather than by simulation, with a decoder that has a hard, explicit stopping point. Numerically, for a $(128,64)$ code on a binary symmetric channel, the optimized bound drops to about $7.5\\times10^{-6}$ with a budget of $10^{11}$ node checks, close to the pure-random-code ML benchmark.","feed_headline":"Tree-code tuning nears ML error under a fixed decoding budget","feed_subtitle":"Stack decoding with give-up can reach the random-code union bound by shaping tree branching and cost discounting.","key_machinery":"The central objects are irregular random tree codes, whose generator matrix places message bit $j$ at an arrival time $a_j$ so that $s(t)=|\\{j:a_j\\le t\\}|$ defines a branching profile, and the stack-based sequential decoding with give-up (SSDGU) algorithm, which repeatedly expands the lowest-cost stack node and returns $\\varepsilon$ if $L$ node checks are exhausted. The argument rides on the separation in Theorem 1 between $D_{\\mathrm{CLE}}$ (the probability that the node-count inequality fails) and $D_{\\mathrm{CFE}}$ (the probability that a wrong terminal node has cost no higher than the true message's cost). The AEC condition $d(x_{1:t},y_{1:t})\\le d(x_{1:t'},y_{1:t'})$ for $t<t'$ is what makes the stack's current minimum a global lower bound, so a non-$\\varepsilon$ return is truly a minimum-cost message. The optimization machinery is the successive bit placement (SBP) heuristic, which greedily places each message bit at the position minimizing the relaxed bound $D_E^{(G)}[s,d]$, together with the discounted cost measure whose parameter $\\gamma$ tunes how quickly older mismatches are devalued.","core_discovery":"The paper's central claim is that for any irregular random tree code with branching structure $s(t)$, any accumulating error-cost (AEC) measure $d$, and any computational limit $L$, the frame error probability of the SSDGU decoder is bounded by $\\Pr(\\hat{m}\\neq m)\\le D_{\\mathrm{CLE}}[s,d]+D_{\\mathrm{CFE}}[s,d]$, where $D_{\\mathrm{CLE}}$ is the computation-limit error term that decays with $L$ and $D_{\\mathrm{CFE}}$ is the computation-free error term that does not depend on $L$. For the special case of pure random codes, $s(1)=k$, and a causal channel, the relaxed CFE term becomes the random coding union bound, so the computational constraint and the classical random-coding error floor separate cleanly. The paper then defines CORT codes as ensembles optimized over $s$ and a discounted cost measure $d_t=\\gamma^{t-1}d_1$ via a successive bit placement (SBP) heuristic, and reports numerical evaluations for $(128,64)$ codes on the BSC. With $\\gamma\\approx0.9992$ and $L=10^{11}$, the bound reaches $7.5\\times10^{-6}$ at $p=0.02$ and $1.5\\times10^{-3}$ at $p=0.03$, close to the ML error of pure random codes.","pith_inferences":["If the paper is right, the split between $D_{\\mathrm{CLE}}$ and $D_{\\mathrm{CFE}}$ implies a design floor: no increase in $L$ can push error below the computation-free term, so for a fixed ensemble the only route to a lower floor is to change the branching profile or the measure.","The success of $\\gamma\\approx0.9992$ suggests a general principle for bounded-budget decoding: devaluing older cost terms prioritizes early agreement with the channel output. This is an editorial extension; the paper optimizes over a one-parameter discount but does not optimize the full discount schedule.","If the stack memory is truly capped at $L$ rather than assumed as large as $L$, the node-count inequality in the proof would need revision; designing a low-memory variant and re-deriving the bound is a testable extension the paper lists as future work.","The SBP heuristic greedily places one bit at a time; comparing it with dynamic programming or continuous relaxation over branching profiles would test whether the greedy placements are near-optimal. This is an editorial inference, not a claim of the paper."],"forward_implications":["The achievability bound guarantees that for any $L$, an $(n,k)$ tree code in the optimized ensemble has SSDGU frame error probability at most $D_E[s,d]$, so the bound is a design target for practical codes that does not require Monte Carlo simulation.","As $L$ grows, the SBP-optimized branching profile converges to $s(1)=k$, i.e., all message bits at the root, and the computation-free term coincides with the random coding union bound for pure random codes; the scheme therefore inherits the classical random-coding benchmark in the large-budget limit.","A discount factor just below one, e.g., $\\gamma=0.9992$, lowers the computation-limit term at finite $L$ and yields smaller total error bounds than $\\gamma=1$ when the budget is modest, while $\\gamma=1$ catches up as $L$ grows.","Because the expected number of node checks is at most $D_{\\mathrm{CLE}}[s,d]\\cdot L$, the same bound also estimates the average decoding runtime, not just the probability of giving up."],"supporting_citations":[{"why":"Supplies the random-coding achievability method that the ensemble bounds are built on.","marker":"[1]"},{"why":"Introduces sequential decoding of tree codes, the setting SSDGU operates in.","marker":"[2]"},{"why":"Defines tree codes and the cutoff-rate perspective that motivates limiting node checks.","marker":"[3]"},{"why":"Provides the stack decoding procedure that SSDGU modifies into a give-up variant.","marker":"[8]"},{"why":"Supplies the fast stack-based decoding mechanism with ordered stack entries.","marker":"[9]"},{"why":"Gives the random coding union bound that the CFE term reduces to for pure random codes.","marker":"[10]"},{"why":"Offers an approximate-ML decoder with a fixed query budget, a related bounded-computation benchmark.","marker":"[11]"},{"why":"Defines random staircase generator matrix codes, a special case of these tree codes, and a comparable approximate-ML construction.","marker":"[12]"}],"fun_headline_variants":["Tree codes tuned to hit ML error within compute limits","Optimized tree codes approach ML performance under compute cap","Shaping tree codes hits ML error with a fixed decoding budget","Branch shaping lets tree codes mimic ML within compute limit","Tree-code optimization approaches ML under compute limits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the decoder's stack can hold as many node entries as the computational limit $L$, so the proof may count every sufficiently low-cost node as checkable; if the stack is hard-capped at $L$, the SSDGU decoder can be forced to give up before the bound's node count is reached.","fun_headline_variants_meta":{"raw":{"variants":["Tree codes tuned to hit ML error within compute limits","Optimized tree codes approach ML performance under compute cap","Shaping tree codes hits ML error with a fixed decoding budget","Branch shaping lets tree codes mimic ML within compute limit","Tree-code optimization approaches ML under compute limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000765,"raw_usage":{"total_tokens":3368,"prompt_tokens":894,"completion_tokens":2474,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":510,"completion_tokens_details":{"reasoning_tokens":2398}},"tokens_in":510,"tokens_out":2474,"duration_ms":16060,"temperature":1.0,"reasoning_tokens":2398,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:47:45.726917+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SSDGU with a stack that physically cannot hold more than $L$ entries on a $(128,64)$ optimized CORT ensemble over the BSC at $p=0.02$ with $L=10^{9}$, and record how often the decoder returns $\\varepsilon$ because of stack overflow before $L$ node checks; if that frequency exceeds $D_{\\mathrm{CLE}}$, the achievability bound does not describe the memory-capped decoder.","supporting_citations":[{"cited_title":"A mathematical theory of communication,","cited_arxiv_id":null,"evidence_quote":"Supplies the random-coding achievability method that the ensemble bounds are built on."},{"cited_title":"Sequential decoding for reliable com munication,","cited_arxiv_id":null,"evidence_quote":"Introduces sequential decoding of tree codes, the setting SSDGU operates in."},{"cited_title":"Information theory and reliable commun ication,","cited_arxiv_id":null,"evidence_quote":"Defines tree codes and the cutoff-rate perspective that motivates limiting node checks."},{"cited_title":"Procedures of sequential decoding,","cited_arxiv_id":null,"evidence_quote":"Provides the stack decoding procedure that SSDGU modifies into a give-up variant."},{"cited_title":"Fast sequential decoding algorithm using a stack,","cited_arxiv_id":null,"evidence_quote":"Supplies the fast stack-based decoding mechanism with ordered stack entries."},{"cited_title":"Capacity-achieving guessing random additive noise decoding,","cited_arxiv_id":null,"evidence_quote":"Offers an approximate-ML decoder with a fixed query budget, a related bounded-computation benchmark."},{"cited_title":"Random sta ircase generator matrix codes,","cited_arxiv_id":null,"evidence_quote":"Defines random staircase generator matrix codes, a special case of these tree codes, and a comparable approximate-ML construction."}],"review_version":1}