{"id":"0fbaf5ac-73d6-468d-b7e9-ab17e5f8167d","arxiv_id":"2502.05959","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For constant-composition random codebooks, the optimal second-order region, error exponent, and strong converse exponent of guessing-based decoding with abandonment are exactly determined by a single bottleneck quantity: the minimum (or maximum) of a channel coding term and an abandonment term.","lead":"This paper analyzes guessing-based decoders that check a ranked list of candidate codewords and stop after a set number of guesses, for general noisy channels. It finds the exact asymptotic trade-off between code rate, guessing budget, and error probability in three regimes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's achievability proof cites the wrong bound on Ψ; the strong converse exponent result needs a corrected derivation before it is established.","rationale":"The reader's weakest-assumption pick was the positive-dispersion condition V_epsilon(W)>0 in Theorem 2. That is a real scope restriction, but it is explicitly stated and does not invalidate the theorem as formulated, so I do not consider it the most load-bearing problem. The stronger concern is the strong converse exponent proof. The paper discloses that an earlier proof of Theorem 4 was erroneous and was corrected after Nakiboglu's comment. In the current version, the achievability part contains a step that, taken literally, uses a lower bound on Ψ to establish an event requiring an upper bound on Ψ. This is not a mere cosmetic issue: it is the exact step that produces the max{R,H(P_X)−r} rate in the exponent. If the intended bound is the upper bound from Lemma 1, the step is likely fixable and the theorem may stand, but the printed proof is not yet self-consistent. Since the reader already requested a clean statement of the corrected Theorem 4 proof, my finding supports the CONDITIONAL verdict rather than changing it. I would not reject the paper: the second-order and error-exponent arguments appear sound, the first-order result is standard, and the questionable step is localized and plausibly a typo. The concrete test above would settle whether the Theorem 4 proof is genuinely complete or needs further revision.","tokens_in":21284,"tokens_out":35595,"duration_ms":354696,"concrete_test":"Independently re-derive the step around Eq. (45) in Section VI-A using Lemma 1's upper bound on Ψ (not the lower bound) and verify whether the condition I(P_X,V) ≥ max{R, H(P_X)−r} + 2δ_n implies both G(x|y) ≤ e^{nr} and Ψ(x,y) ≤ 1/(M_n−1) for all sufficiently large n. If the implication holds, the proof is repaired by replacing the cited bound; if it fails, Theorem 4's ensemble-tight strong converse exponent is not supported by the current argument and requires a new achievability proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing concern is in the achievability proof of Theorem 4, specifically the step leading to Eq. (45). The text says (45) uses the upper bound on G(x|y) and the lower bound on Ψ(x,y) from Lemma 1. But the event being lower-bounded includes Ψ(X,Y) ≤ 1/(M_n − 1), and a lower bound on Ψ cannot imply an upper bound on Ψ. What is needed is the upper bound Ψ(x,y) ≤ (n+1)^{3|X||Y|} e^{-n I(x∧y)}; together with the rank-function upper bound, this is what would justify the sufficient condition I(P_X,V) ≥ max{R, H(P_X)−r} + O(δ_n). As printed, the proof of Theorem 4 therefore contains an invalid implication at exactly the point where the strong converse exponent Ksp(max{R,H(P_X)−r},P_X) is derived. This matters because the paper itself acknowledges that an earlier proof of Theorem 4 was wrong, and Theorem 4 is one of the three central contributions. The stated theorem may still be true, but the given argument does not yet establish it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper analyzes a fixed ensemble of constant-composition random codebooks for discrete memoryless channels, used with a universal guessing-based decoder that rank-orders input sequences by empirical conditional entropy and abandons after e^{n r_n} guesses. The central claims are exact ensemble asymptotics for this scheme: Theorem 1 characterizes the first-order region of code rate and abandonment rate; Theorem 2 gives the second-order region under a positive-dispersion assumption, with the asymptotic error probability governed by Q((s∧t)/√V_ε(W)); Theorem 3 characterizes the error exponent as min{E_r(R,P_X), E_a(r,P_X)}; and Theorem 4 characterizes the strong converse exponent as K_{sp}(max{R, H(P_X)−r}, P_X). The unifying structural conclusion is that either the code-rate backoff or the abandonment-rate backoff dominates, so the three asymptotic regimes are determined by a scalar minimum or maximum of the two rate penalties.","tokens_in":21439,"tokens_out":9545,"duration_ms":94434,"significance":"The results are significant if they hold: they extend GRAND-style guessing decoding beyond symmetric additive channels and provide ensemble-tight first-order, second-order, exponent, and strong-converse characterizations for the memoryless case. The paper is careful in several respects: the proofs are detailed and follow standard large-deviation and CLT techniques; Lemma 1 gives explicit two-sided bounds on the rank probability; the decomposition into the incorrect-decoding event E_1 and the abandonment event A_1 is transparent; and the authors explicitly acknowledge a previously flawed proof of Theorem 4, which invites extra scrutiny. There are no fitted constants or circular arguments. The main caveat is a wrong bound direction in the achievability proof of Theorem 4, which must be corrected before that theorem is established.","major_comments":[{"comment":"The step leading to (45) is invalid as stated. The event being lower-bounded contains {Ψ(X,Y) ≤ 1/(M_n−1)}, so to convert that indicator into a lower bound on the probability, one needs the upper bound Ψ(x,y) ≤ (n+1)^{3|X||Y|} e^{−n\\hat I(x∧y)} from Lemma 1. A lower bound on Ψ cannot imply Ψ ≤ 1/(M_n−1); it implies the opposite direction of control. With the correct upper bound, the sufficient condition becomes \\hat I(P_X,V) ≥ R + 3δ_n (up to subexponential factors), and the claimed exponent K_{sp}(max{R, H(P_X)−r}, P_X) is recovered after the usual δ_n→0 argument. The text at (45) should be revised accordingly; as printed, the proof of Theorem 4's achievability does not go through.","section":"VI-A, Eq. (45)"}],"minor_comments":[{"comment":"After defining the set H_n, the chain of inequalities writes P[(X,Y) ∈ S_r ∩ F_n]; F_n was defined in Section IV with a different threshold. This should read H_n.","section":"VI-A"},{"comment":"The converse lower bound on (♣) is only meaningful when s ≤ t; for s > t the displayed Gaussian difference Q(s/√V) − Q(t/√V) is negative. The desired converse in that case follows from the abandonment term (♠) alone, but the proof should state this explicitly rather than leaving it implicit.","section":"IV-B"},{"comment":"The achievability proof treats only the choices R = I(P_X,W) − δ and r = H_{P_X×W}(X|Y) + δ. The full region in Theorem 1 follows by monotonicity of the error probability in M_n and m_n, but this should be said so that the proof covers every stated rate pair.","section":"III-A"}],"recommendation":"major_revision","confidential_remarks":"The substantive issue is the bound-direction error in the achievability proof of Theorem 4, which is load-bearing. Because the acknowledgments note that an earlier proof of Theorem 4 was erroneous, I suggest that the editor request a corrected derivation and a careful re-check of all uses of Lemma 1 in the revised manuscript. The other theorems appear to be supported by their proofs modulo minor gaps."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a strong, carefully written paper that gives the first ensemble-tight second-order and exponent characterizations for guessing-based decoding with abandonment over general DMCs. Theorems 2 and 3 hold up under scrutiny, and the unified picture they produce—where the code-rate backoff and abandonment-rate backoff interact through a single min or max—is a real step beyond the symmetric additive-channel GRAND results. The proofs are mostly clean: Lemma 1 is explicit, the Fn/Gn decomposition is sensible, and the self-citations are standard background, not circular support.\n\nThe one place I would not let the current text stand is the achievability proof of Theorem 4. At equation (45), the text says it uses the lower bound on Ψ from Lemma 1, but the event being lower-bounded contains Ψ(X,Y) ≤ 1/(M_n−1). A lower bound on Ψ cannot imply an upper bound on Ψ, so the printed implication is backwards. The fix is straightforward: use the upper bound Ψ(x,y) ≤ (n+1)^{3|X||Y|} e^{-nI(x∧y)} together with the upper bound on G(x|y); then for I(P_X,V) ≥ max{R, H(P_X)−r} + 2δ_n both conditions hold. I believe the theorem is true, but the argument as written does not establish it. Since the paper itself acknowledges that an earlier proof of Theorem 4 was wrong, the referee should ask for a clean corrected derivation.\n\nOther soft spots are minor. Theorem 1's achievability is written for a single rate pair rather than the full region, and the sign-split case (s > t) in the Theorem 2 converse is compressed—though it follows from the abandonment-event lower bound. The positive-dispersion assumption in Theorem 2 is a stated scope restriction, not a hidden flaw.\n\nOverall: the central contributions are valuable, the mathematics is mostly sound, and the flaw in Theorem 4 looks repairable rather than load-bearing. This paper deserves a serious peer review, but the referee should require a fixed proof of Theorem 4 before publication.\n\nRecommendation: send it out, with the Theorem 4 proof as the main requested revision.","headline":"A genuinely useful paper on guessing-based decoding: Theorems 2 and 3 are solid, and Theorem 4 is likely true but its printed proof has a reversed bound that must be fixed.","tokens_in":22014,"tokens_out":3898,"would_cite":true,"duration_ms":38892,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A29","60F05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that for a guessing-based decoder with abandonment, the ensemble error probability in the second-order, error-exponent, and strong-converse regimes is governed by a single scalar: the minimum or maximum of the code-rate…","keywords":["guessing-based decoding","abandonment","second-order asymptotics","error exponents","strong converse exponents","discrete memoryless channels","constant-composition codes","epsilon-dispersion"],"falsifier":"Fix a binary asymmetric channel with positive $\\epsilon$-dispersion, choose $s>t>0$, and simulate random constant-composition codes with $M_n=e^{nC-s\\sqrt{n}}$ codewords and abandonment budget $m_n=e^{nH_{P_X\\times W}(X|Y)+t\\sqrt{n}}$. The theorem predicts the ensemble error tends to $Q(t/\\sqrt{V_{\\epsilon}(W)})$, independent of $s$; observing instead a dependence on $s$, or a limit different from $Q(t/\\sqrt{V_{\\epsilon}(W)})$, would falsify the second-order characterization.","tokens_in":21031,"feed_emoji":"📡","tokens_out":11086,"duration_ms":108080,"temperature":0.7,"pith_summary":"This paper derives exact asymptotic limits for a decoder that, given a channel output, guesses input sequences in order of decreasing closeness and stops after a fixed number of guesses. For discrete memoryless channels with positive $\\epsilon$-dispersion, it proves that the second-order region is a quadrant: $(s,t)$ is achievable exactly when $s \\wedge t \\ge \\sqrt{V_{\\epsilon}(W)} Q^{-1}(\\epsilon)$, and the limiting ensemble error probability is $Q((s \\wedge t)/\\sqrt{V_{\\epsilon}(W)})$. It also proves the error exponent is $\\min\\{E_r(R,P_X), E_a(r,P_X)\\}$ and the strong converse exponent is $K_{\\mathrm{sp}}(\\max\\{R, H(P_X)-r\\}, P_X)$. The unifying message is that one scalar---the bottleneck between the code-rate backoff and the abandonment-rate backoff---controls the ensemble error in all three regimes. These results make precise when a guessing decoder can query exponentially fewer sequences than the codebook size without losing near-capacity performance.","feed_headline":"The weaker backoff governs guessing-decoder error","feed_subtitle":"Exact formulas show guessing decoders can abandon early without sacrificing near-capacity performance.","key_machinery":"The argument is carried by the modified rank function $G(x|y)$, which counts all input sequences in the codebook's type class whose empirical conditional entropy is no larger than that of $x$; equation (5) pins this rank to $e^{n\\hat{H}(x|y)}$ up to polynomial factors. Lemma 1 similarly pins the probability $\\Psi(x,y)$ that an independent codeword outranks the transmitted pair to $e^{-n\\hat{I}(x\\wedge y)}$ up to polynomial factors. These two bounds turn both the incorrect-decoding event and the abandonment event into threshold crossings of the single scalar random variable $\\hat{I}(X\\wedge Y)$, so the central limit theorem and large-deviation estimates for empirical mutual information close the proofs in all three asymptotic regimes.","core_discovery":"For a discrete memoryless channel with positive $\\epsilon$-dispersion, the set of ensemble-tight second-order rates is exactly $L^*_{\\epsilon}(P_X,W) = \\{(s,t): s \\wedge t \\ge \\sqrt{V_{\\epsilon}(W)} Q^{-1}(\\epsilon)\\}$. Parametrized as $R_n \\approx C(W) - s/\\sqrt{n}$ and $r_n \\approx H_{P_X\\times W}(X|Y) + t/\\sqrt{n}$, the ensemble average error probability converges to $Q((s \\wedge t)/\\sqrt{V_{\\epsilon}(W)})$, with $V_{\\min}(W)$ when $s \\wedge t \\ge 0$ and $V_{\\max}(W)$ when $s \\wedge t < 0$. In the exponent regimes, the ensemble error exponent is $\\min\\{E_r(R,P_X), E_a(r,P_X)\\}$, which reduces to $E_r(\\max\\{R, H(P_X)-r\\}, P_X)$ above the critical rate, and the strong converse exponent is $K_{\\mathrm{sp}}(\\max\\{R, H(P_X)-r\\}, P_X)$. These characterizations are ensemble-tight in the sense that achievability and converse bounds on the average error over random constant-composition codebooks coincide for the fixed guessing rule.","pith_inferences":["If the paper is right, the rectangular second-order region implies an engineering tradeoff: even when the code rate is held at capacity, the entire second-order backoff can be moved into the abandonment budget without changing the asymptotic error probability, so the decoder's search complexity can be tuned independently of the code rate in the $\\sqrt{n}$ regime.","The paper's explicit restriction to positive $\\epsilon$-dispersion suggests a direct follow-up: for zero-dispersion channels, the Gaussian limits on $\\hat{I}(X\\wedge Y)$ fail, and the second-order region should instead be described by a non-$\\sqrt{n}$ speed or by large-deviation thresholds rather than the $Q$-function.","The paper leaves Gaussian channels and optimized ranking metrics open; a natural testable extension is that the min/max scalar structure survives whenever the ranking metric is a sufficient statistic for the channel, with the appropriate per-symbol variance replacing $V_{\\epsilon}(W)$."],"forward_implications":["At the optimal first-order pair $(R,r)=(C(W), H_{P_X\\times W}(X|Y))$, a guessing decoder achieves vanishing error with about $e^{nH_{P_X\\times W}(X|Y)}$ guesses, which is exponentially fewer than the $e^{nC(W)}$ codewords exactly when $C(W) > H(P_X)/2$.","The second-order region is rectangular: once $s \\wedge t$ is fixed, the larger of the two backoffs can be increased without changing the limiting ensemble error probability.","In the error-exponent regime, whenever both $R$ and $H(P_X)-r$ lie above the critical rate, lowering the abandonment rate $r$ and raising the code rate $R$ have exactly the same effect, since the exponent depends only on $\\max\\{R, H(P_X)-r\\}$.","In the strong-converse regime, the correct-decoding probability decays at exponential rate $K_{\\mathrm{sp}}(\\max\\{R, H(P_X)-r\\}, P_X)$ whenever $R > C(W)$ or $r < H_{P_X\\times W}(X|Y)$, making the guessing decoder's strong converse exponent a special case of the conditional almost-lossless source coding exponent.","The abandonment exponent $E_a(r,P_X)$ equals the sphere-packing exponent at rate $H(P_X)-r$, which means guessing-based decoding with abandonment inherits the error-exponent behavior of universal conditional source coding."],"supporting_citations":[{"why":"Supplies the type-class and conditional-type bounds, the constant-composition random coding exponent $E_r$, and the shell-size estimates used throughout the proofs.","marker":"[7]"},{"why":"Supplies the random coding union bound and the second-order channel coding rate that the no-abandonment limit of Theorem 2 reduces to.","marker":"[20]"},{"why":"Supplies the central limit theorem for empirical mutual information that gives the Gaussian limits in Theorem 2.","marker":"[19]"},{"why":"Supplies the definition of $\\epsilon$-dispersion $V_{\\epsilon}(W)$, which sets the variance in the second-order region.","marker":"[18]"},{"why":"Introduces guessing-based decoding with abandonment and its decomposition of the error event into decoding error plus abandonment, which this paper extends to general discrete memoryless channels.","marker":"[10]"},{"why":"Establishes the strong converse exponent for discrete memoryless channels, the classical result that Theorem 4 adapts to the guessing-based setting with abandonment.","marker":"[9]"},{"why":"Defines Haroutunian's sphere-packing exponent, which appears as $K_{\\mathrm{sp}}$ and also underlies the abandonment exponent $E_a$.","marker":"[29]"}],"fun_headline_variants":["Guessing decoders can quit early without rate loss","Exact error exponents for guessing with abandonment","Tight second-order rates for guessing decoders","When to abandon guessing: a precise threshold"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The second-order characterization assumes the channel's $\\epsilon$-dispersion is strictly positive; if it is zero, the Gaussian limits on which the $\\sqrt{n}$ backoff result rests fail and Theorem 2 does not apply.","fun_headline_variants_meta":{"raw":{"variants":["Guessing decoders can quit early without rate loss","Exact error exponents for guessing with abandonment","Tight second-order rates for guessing decoders","When to abandon guessing: a precise threshold"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000572,"raw_usage":{"total_tokens":2751,"prompt_tokens":1037,"completion_tokens":1714,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":653,"completion_tokens_details":{"reasoning_tokens":1656}},"tokens_in":653,"tokens_out":1714,"duration_ms":17574,"temperature":1.0,"reasoning_tokens":1656,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T17:13:54.851605+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a binary asymmetric channel with positive $\\epsilon$-dispersion, choose $s>t>0$, and simulate random constant-composition codes with $M_n=e^{nC-s\\sqrt{n}}$ codewords and abandonment budget $m_n=e^{nH_{P_X\\times W}(X|Y)+t\\sqrt{n}}$. The theorem predicts the ensemble error tends to $Q(t/\\sqrt{V_{\\epsilon}(W)})$, independent of $s$; observing instead a dependence on $s$, or a limit different from $Q(t/\\sqrt{V_{\\epsilon}(W)})$, would falsify the second-order characterization.","supporting_citations":[{"cited_title":"Channel coding rate in the finite blocklength regime,","cited_arxiv_id":null,"evidence_quote":"Supplies the random coding union bound and the second-order channel coding rate that the no-abandonment limit of Theorem 2 reduces to."},{"cited_title":"The dispersion of joint source- channel coding,","cited_arxiv_id":null,"evidence_quote":"Supplies the central limit theorem for empirical mutual information that gives the Gaussian limits in Theorem 2."},{"cited_title":"A tight upper bound for the third- order asymptotics for most discrete memoryless channels,","cited_arxiv_id":null,"evidence_quote":"Supplies the definition of $\\epsilon$-dispersion $V_{\\epsilon}(W)$, which sets the variance in the second-order region."},{"cited_title":"Capacity-achieving guessing random additive noise decoding,","cited_arxiv_id":null,"evidence_quote":"Introduces guessing-based decoding with abandonment and its decomposition of the error event into decoding error plus abandonment, which this paper extends to general discrete memoryless channels."},{"cited_title":"Reliability function of a discrete memoryless channel at rates above capacity (corresp.),","cited_arxiv_id":null,"evidence_quote":"Establishes the strong converse exponent for discrete memoryless channels, the classical result that Theorem 4 adapts to the guessing-based setting with abandonment."},{"cited_title":"Estimates of the error exponent for the semi- continuous memoryless channel (in Russian),","cited_arxiv_id":null,"evidence_quote":"Defines Haroutunian's sphere-packing exponent, which appears as $K_{\\mathrm{sp}}$ and also underlies the abandonment exponent $E_a$."}],"review_version":1}