{"id":"cd279c8b-f1e2-44d4-afc8-d2342fe624cc","arxiv_id":"2412.06072","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"Proves that PAC codes with rate profiles below polarized cutoff rates have Pareto-bounded sequential decoding complexity, and demonstrates a code built on this rule that gains over 0.75 dB at FER 1e-5.","lead":"This paper proves that PAC codes whose rate profile obeys polarized cutoff-rate constraints have sequential decoding effort bounded by a Pareto tail, and uses this rule to design a high-rate code. The designed code is reported to beat 5G polar and LDPC codes by more than 0.75 dB at a frame error rate of 1e-5.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5 is proved only for a genie-assisted decoder; the abstract's unassisted-Fano Pareto claim is not established, because an earlier-chunk error can send the search into subtrees not covered by the stated bounds.","rationale":"The first-half derivation (Lemmas 1–5, Theorems 1–3) appears internally consistent; the Hölder applications and threshold-spacing optimizations check out. The problem is the leap from the one-step genie-assisted bound to the abstract's global unassisted claim. If the genie can be removed by a standard sum over incorrect subtrees, the paper only needs a revised exposition; if not, the sufficient condition is not sufficient for the actual Fano decoder. The missing proof of Theorem 5 for k>1 reinforces this. I therefore keep the reader's CONDITIONAL verdict, and I do not elevate the independence assertion to the central concern.","tokens_in":18711,"tokens_out":20507,"duration_ms":214705,"concrete_test":"Carry out the induction that removes the genie: for each chunk, sum Theorem 4/5's incorrect-subtree bound over all correct nodes at the chunk boundary, and verify that the resulting total-work bound for the unassisted Fano decoder contains no probability factor for 'the decoder is at the correct node' that is not already controlled by the rate-profile conditions. If such a factor appears, the central claim is not proved; if the sum is O(N) with no extra probability term, the genie concern is resolved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's sufficient condition for Pareto-bounded sequential decoding is Theorem 5, but its statement and proof are explicitly conditional on a genie that supplies the correct earlier chunks ('Assume that, with the help of a genie, the previous chunks... have been decoded'). The abstract and Section V claim the conclusion for 'its sequential decoding' without that qualifier. For the unassisted Fano decoder, an error in an earlier chunk places the search in an incorrect subtree whose branch metrics are not those of the genie-assisted polarized channel used in the proof; nothing in the paper bounds how long the decoder may stay in such a subtree. The standard way to remove the genie is to sum the per-chunk incorrect-subtree bounds over all correct nodes of the full tree; that argument is absent, and it is not immediate because the rate-profile condition is stated only at chunk level and the proof of Theorem 5 for k>1 is omitted ('Similarly, we can prove'). Thus the central claim is stronger than the proved statement. The independence assertion (γ^-(S_i) ⊥ γ^-(S_j)) is also unproved but is likely valid in the random-coding ensemble under conditioning on the transmitted path; I do not treat it as the main issue.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the computational complexity of Fano sequential decoding of PAC codes. The authors derive upper bounds on the moments of the number of decoder computations per bit for one-step and multi-step polarized channels, under a rate-profile condition that each chunk's polarized rate lies below the corresponding polarized cutoff rate minus a slack epsilon. The main result, Theorem 5, states that under these conditions the complementary CDF of the number of computations for the nth bit of a chunk is bounded by a Pareto tail of the form (4/(L(1-2^{-epsilon/beta})^2))^beta. The authors then propose a rate-profile design based on freezing bits of an RM code to satisfy the cutoff-rate constraints, and present simulations for (1024,899), (512,460), and (128,85) PAC codes showing FER improvements over 5G polar, LDPC, and FDPC codes.","tokens_in":18992,"tokens_out":11968,"duration_ms":94724,"significance":"If fully established, the result would provide a converse to the necessary-condition result of [18] and a principled rate-profile design rule for PAC codes with bounded-complexity sequential decoding. The paper re-derives the key MGF bounds in a largely self-contained manner, states explicit Pareto bounds, and demonstrates nontrivial coding gains in simulation. However, the central claim as stated is stronger than what is proved: the theorem on which the recursive design relies is explicitly genie-assisted and its proof for general k is omitted. The independence assumption underlying Wald's identity is asserted without proof, and there are mismatches between the statements and proofs of the main theorems. These gaps need to be addressed before the result can be accepted as stated.","major_comments":[{"comment":"The theorem is stated for a genie-assisted decoder: 'Assume that, with the help of a genie, the previous chunks of the decoding tree ... have been decoded.' The abstract and Section V state the result for 'its sequential decoding' without this qualifier. For an actual Fano decoder, an error in an earlier chunk can send the search into incorrect subtrees of later chunks, and the branch-metric statistics in those subtrees are not those used in the genie-assisted proof. The paper does not provide the standard removal of the genie by summing per-chunk bounds over all correct nodes of the full tree, which would require a rate-profile condition at every node rather than only at chunk level. Please either prove the unassisted statement or revise the claims to state the genie-assisted version explicitly.","section":"Section III, Theorem 5 (Eq. (69)-(70)) and abstract/conclusion"},{"comment":"The proof for the multi-step polarization case (and even for the second half, Theorem 4) is omitted: before Theorem 4 the text says 'Similarly, we can prove,' and Theorem 5 is stated without proof. The extension to k>1 is not immediate, because the branch metrics of deeper polarized channels condition on the earlier decoded bits, and the dependence structure across chunks must be handled. Since Theorem 5 is the basis for the rate-profile design rule used in Section IV (k=7 for N=1024 and k=6 for N=512), the proof needs to be provided.","section":"Section III, Theorem 5 proof"},{"comment":"The assertion 'gamma^-(S_i) independent of gamma^-(S_j)' is stated without proof. Wald's identity in Lemma 4 and the factorization in Lemma 5 require independence (or at least uncorrelatedness for the MGF product). While this is likely true in the random-coding ensemble under conditioning on the transmitted path, it should be proven or clearly referenced. Without it, the bound on P(Gamma^-_min <= mu) and the subsequent moment bounds are not supported.","section":"Section III, after Eq. (7), and Lemmas 4-5"},{"comment":"There is a mismatch between the stated sufficient condition and the bound proved. The condition R^-_l <= (r/beta)(E0((1-r)/r,W^-)+b^-) - epsilon leads, in the proof (Eq. (60)), to a factor (1-2^{-epsilon})^{-2} in the moment bound, so the final Pareto bound should be (4/(L(1-2^{-epsilon})^2))^beta. The theorem instead states (4/(L(1-2^{-epsilon/beta})^2))^beta. Either the condition should be R^-_l <= (r/beta)(E0+b) - epsilon/beta, or the bound should use epsilon. The same issue appears in Theorem 5.","section":"Theorems 3 and 5, Eq. (56)-(57) and Eq. (69)-(70)"},{"comment":"The condition b^- <= E0(delta,W^-)/delta for 0<delta<1 is inconsistent with the stated ranges r in (0,1) and r0 in (-1,0). In Lemma 3's proof, delta = r/(1-r) lies in (0,infinity) for r in (0,1); the equivalence with delta<1 only holds for r<1/2. Similarly, in Lemma 4, delta = -r0/(1+r0) is <1 only for r0>-1/2. The special cases r=1/2 and r0=-1/2 used in the paper give delta=1, which is outside the stated range. Please correct the parameter ranges or extend the proofs to cover the claimed ranges.","section":"Lemmas 3-4, bias condition"}],"minor_comments":[{"comment":"Equation (30) contains typographical artifacts (the crossed-out 'P' terms) that should be removed in revision.","section":"Eq. (30)"},{"comment":"The phrase 'the first inequality is an application of Wald's identity' is misleading; the referenced inequality P(inf Gamma <= mu) <= 2^{-r0 mu} is Lemma 4, not Wald's identity directly.","section":"Lemma 6 proof"},{"comment":"The design choice to freeze the last weight-8 rows is presented as a guess ('We guess that freezing the bits corresponding to the last rows enhances the upper bound...'). This is acceptable as a heuristic, but it would be clearer to label it explicitly as an empirical design choice that requires further investigation.","section":"Section IV, rate-profile design"}],"recommendation":"major_revision","confidential_remarks":"The paper relies substantially on the authors' own prior work [7], [8], [18], [27] for metric polarization and the necessary-condition result. Those works are not independently reproduced in this manuscript. The main new contribution is the sufficient-condition theorem and the rate-profile algorithm; the genie issue and the unproved Theorem 5 are the key technical obstacles. If the authors can provide a complete proof of the unassisted version or explicitly restrict the claims, the paper may be suitable for publication after the remaining technical mismatches are corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is the short version: the paper does prove something real and useful—a sufficient condition, converse to their earlier necessary condition, under which the per-bit computation count for sequential decoding of a PAC code has a Pareto tail bound. The first-half derivation (Lemmas 1–3, then the Wald/Chernoff/Minkowski chain) is self-contained and credible. The extension of classical sequential-decoding bounds to vector-output polarized channels is a genuine generalization, and the numerical PAC(1024,899) design is a legitimate engineering result: more than 0.75 dB over 5G polar and LDPC at FER 10^-5, with ANV near 1 at high SNR.\n\nI agree with the stress-test note that the central gap is the genie. Theorem 5 is stated and proved only with a genie that supplies previously decoded chunks. The abstract and conclusion claim bounded complexity for the Fano decoder itself, without that qualifier. For an unassisted decoder, an error in an earlier chunk can push the search into incorrect subtrees whose branch metrics are not the ones the theorem's MGF bounds cover. The paper does not give the standard argument that sums per-chunk incorrect-subtree bounds over all correct nodes to remove the genie, and such an argument is not immediate here because the rate condition is chunk-level and the k>1 proof is omitted (\"Similarly, we can prove\"). That is the main soft spot, and it is load-bearing for the advertised claim.\n\nSecondary issues: the independence assertion (γ^-(S_i) ⊥ γ^-(S_j)) is asserted, not proved; probably fine in the random-coding ensemble under conditioning on the transmitted path, and I would not hang the review on it. Numerical curves come with no code or data and no confidence intervals; the rate-profile heuristic, including freezing the last weight-8 rows, is explicitly a guess. Self-citation is heavy but the main lemmas are re-derived, so I do not count that against them.\n\nBottom line: this deserves a serious referee and, with the abstract fixed or the genie removed by a real argument, likely acceptance. I would send it out, and ask the authors to either prove the unassisted bound or scope the claims to the genie-assisted setting. The k>1 theorem needs a proof, not a \"similarly.\" The numerics should be made reproducible.","headline":"A real sufficient condition for Pareto-bounded sequential decoding of PAC codes, but the paper's unassisted-Fano claim is stronger than the genie-assisted theorem actually proves.","tokens_in":19519,"tokens_out":2813,"would_cite":true,"duration_ms":29120,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","94A15","94A24"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a sufficient condition for bounded-complexity sequential decoding of PAC codes—per-chunk rates below the polarized cutoff rate give a Pareto-bound computation distribution—and turns it into a rate-profile design that…","keywords":["PAC codes","sequential decoding","Fano algorithm","polar codes","channel polarization","cutoff rate","Pareto distribution","rate profile design"],"falsifier":"Run a real Fano decoder without a genie on a PAC(1024,899) code designed by this paper's rate-profile rule at an $E_b/N_0$ where the first-chunk frame error rate is around $10^{-2}$; if the measured tail $P(C_n \\geq L)$ decays slower than the Pareto bound or the average visits start growing with block length, the genie assumption is doing essential work.","tokens_in":18502,"feed_emoji":"📡","tokens_out":7564,"duration_ms":61356,"temperature":0.7,"pith_summary":"This paper addresses the converse of an earlier necessary condition: it proves that when each chunk of a PAC code has a polarized rate below the corresponding polarized cutoff rate, the number of computations per decoded bit under sequential decoding has a Pareto upper tail. The proof works through the polarized branch metrics and bounds their moment-generating functions, then applies Wald's identity and a Minkowski-norm argument to control the Fano search. The result is a rate-profile design rule: place data bits only where the polarized rate sits below the polarized cutoff rate. Following that rule, the authors construct a PAC(1024,899) code whose Fano decoder outperforms 5G polar and LDPC codes by more than 0.75 dB at a frame error rate of $10^{-5}$, with per-bit visits near one at high SNR.","feed_headline":"Below the polarized cutoff rate, PAC decoding stays Pareto-bounded","feed_subtitle":"A sufficient condition for cheap Fano decoding, with a 0.75 dB gain over 5G polar and LDPC codes.","key_machinery":"The carrying objects are the polarized branch metric functions $\\phi^{\\{-,+\\}^k}(\\cdot)$ from metric polarization, which turn each polarized channel into a branch metric for the Fano decoder, together with a bias term $b$. Three lemmas bound the semi-invariant moment-generating functions of these metrics on correct paths, wrong paths, and their differences in terms of Gallager's $E_0$ function, the channel's error-exponent function; these feed a Wald's-identity argument that controls the minimum correct-path metric and a Chernoff-bound argument that controls how far wrong paths can get. A Minkowski-norm argument lifts the expected-computation bound to a bound on the $\\beta$-th moment, and the generalized Chebyshev inequality turns that into the Pareto tail. The free threshold spacing $\\Delta$ is set to $\\beta/r$ to optimize the constant, matching the conventional $\\Delta=2$ for $r=1/2$, $\\beta=1$.","core_discovery":"The central claim is Theorem 5: for any chunk of the decoding tree after $k$ polarization steps, if the chunk's rate satisfies $R^{\\{-,+\\}^k}_l \\leq \\frac{r}{\\beta}\\left(E_0\\left(\\frac{1-r}{r}, W^{\\{-,+\\}^k}\\right) + b^{\\{-,+\\}^k}\\right) - \\epsilon$ and the bias satisfies $b^{\\{-,+\\}^k} \\leq E_0(\\delta, W^{\\{-,+\\}^k})/\\delta$ for some $0<\\delta<1$, then $P(C^{\\{-,+\\}^k}_n \\geq L) \\leq \\left(\\frac{4}{L(1-2^{-\\epsilon/\\beta})^2}\\right)^\\beta$. With $r=1/2$ and $\\beta=1$, this becomes the polarized cutoff-rate condition $R \\leq E_0(1,W) - \\epsilon = R_0 - \\epsilon$. So staying below the polarized cutoff rate is not just necessary (as earlier work showed exponential growth above it) but sufficient for a Pareto-bounded computation distribution. The same argument recurses over the polarization transform, and the authors use it as a constructive rate-profile guideline.","pith_inferences":["The genie assumption means the theorem proves a conditional per-chunk guarantee; extending it to an unassisted Fano decoder likely requires controlling the probability that an earlier chunk is wrong, perhaps with a union bound over chunk error events.","The Pareto exponent $\\beta$ is tied to the slack $\\epsilon$ through $(1-2^{-\\epsilon/\\beta})^{-2\\beta}$; measuring the actual tail exponent per chunk in simulation could show whether deeper polarization produces heavier or lighter tails than this bound.","The design choice to freeze the last weight-8 rows is analogous to zero-padding termination in convolutional codes; the paper notes it improves FER but leaves it for further study, so a direct comparison of freezing different weight-8 rows would test whether the position effect is real.","Because polarized cutoff rates polarize to capacity, the same sufficient condition suggests that capacity-approaching PAC rate profiles could still be decoded sequentially with Pareto-bounded complexity for large block lengths."],"forward_implications":["The polarized cutoff rate becomes the design threshold: rate profiles that allocate data bits to positions whose polarized rate is below $R_0^{\\{-,+\\}^k}$ are guaranteed a Pareto-bounded computation distribution per bit.","The construction algorithm starts from an RM(1024,968) code, freezes data bits until the polarized cutoff-rate constraints hold at a target $E_b/N_0$, and then freezes last weight-8 rows; the resulting PAC(1024,899) code gains more than 0.75 dB over 5G polar and LDPC codes at FER $10^{-5}$.","At high SNR the average number of node visits per decoded bit approaches 1, so the Fano decoder's complexity stays within about a factor of two of plain successive cancellation decoding.","With more polarization steps the average polarized cutoff rate moves toward capacity, so the same Pareto bound allows Fano decoding to operate closer to capacity while retaining bounded complexity."],"supporting_citations":[{"why":"Supplies the polarized metric functions $\\phi^-$ and $\\phi^+$ that define the branch metrics analyzed throughout.","marker":"[8]"},{"why":"Establishes the necessary condition (exponential complexity above polarized cutoff rates) that this paper's sufficiency result inverts.","marker":"[18]"},{"why":"Provides the random-linear-code ensemble and Gallager's $E_0$ function used in the moment-generating-function bounds.","marker":"[24]"},{"why":"Gives the classic Pareto bound on sequential-decoding computations for convolutional codes below cutoff rate, the template generalized here.","marker":"[23]"},{"why":"Provides the proof approach for the semi-invariant MGF bounds used in Lemmas 1 and 3.","marker":"[27]"},{"why":"Supplies Wald's identity, used to bound the probability that the correct-path minimum metric falls below a barrier.","marker":"[28]"},{"why":"Introduces PAC codes and the rate-profile problem this paper addresses.","marker":"[1]"},{"why":"Defines the Fano metric with bias for PAC codes, setting up the bias conditions in the theorems.","marker":"[7]"}],"fun_headline_variants":["Pareto-bounded PAC decoding when rate respects cutoff constraints","Polarized cutoff rate rule makes PAC decoder complexity bounded","PAC codes: obey cutoff rate to get Pareto-distributed decoding cost","Sufficient cutoff-rate condition yields Pareto-bounded PAC decoding"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof for the second half and deeper chunks assumes a genie has already decoded the earlier chunks correctly, so an unassisted Fano decoder's errors in one chunk could propagate into later chunks in ways this argument does not bound.","fun_headline_variants_meta":{"raw":{"variants":["Pareto-bounded PAC decoding when rate respects cutoff constraints","Polarized cutoff rate rule makes PAC decoder complexity bounded","PAC codes: obey cutoff rate to get Pareto-distributed decoding cost","Sufficient cutoff-rate condition yields Pareto-bounded PAC decoding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00025,"raw_usage":{"total_tokens":1590,"prompt_tokens":1015,"completion_tokens":575,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":631,"completion_tokens_details":{"reasoning_tokens":505}},"tokens_in":631,"tokens_out":575,"duration_ms":5699,"temperature":1.0,"reasoning_tokens":505,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:03:20.345250+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a real Fano decoder without a genie on a PAC(1024,899) code designed by this paper's rate-profile rule at an $E_b/N_0$ where the first-chunk frame error rate is around $10^{-2}$; if the measured tail $P(C_n \\geq L)$ decays slower than the Pareto bound or the average visits start growing with block length, the genie assumption is doing essential work.","supporting_citations":[{"cited_title":"A New Metric Function for SC-based Polar Decoders: Polarization, Pruning, and Fast Decoders","cited_arxiv_id":"2408.03840","evidence_quote":"Supplies the polarized metric functions $\\phi^-$ and $\\phi^+$ that define the branch metrics analyzed throughout."},{"cited_title":"Application of guessing to sequential decoding of polarization-adjusted convolutional (PAC) codes,","cited_arxiv_id":null,"evidence_quote":"Establishes the necessary condition (exponential complexity above polarized cutoff rates) that this paper's sufficiency result inverts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the random-linear-code ensemble and Gallager's $E_0$ function used in the moment-generating-function bounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the classic Pareto bound on sequential-decoding computations for convolutional codes below cutoff rate, the template generalized here."},{"cited_title":"A tree pruning technique for decoding complexity reduction of polar codes and PAC codes,","cited_arxiv_id":null,"evidence_quote":"Provides the proof approach for the semi-invariant MGF bounds used in Lemmas 1 and 3."},{"cited_title":"On sequential decoding metric function of polarization- adjusted convolutional (PAC) codes,","cited_arxiv_id":null,"evidence_quote":"Defines the Fano metric with bias for PAC codes, setting up the bias conditions in the theorems."}],"review_version":1}