ORBGRAND Is Exactly Capacity-achieving via Rank Companding

Wenyi Zhang; Zhuang Li

arxiv: 2512.00347 · v5 · pith:O5TKVVUDnew · submitted 2025-11-29 · 💻 cs.IT · math.IT

ORBGRAND Is Exactly Capacity-achieving via Rank Companding

Zhuang Li , Wenyi Zhang This is my paper

Pith reviewed 2026-05-17 03:53 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords ORBGRANDCDF-ORBGRANDrank compandingsymmetric capacitymutual informationbinary-input memoryless channelsBICM capacityguessing-based decoding

0 comments

The pith

By companding ranks in ORBGRAND with the inverse CDF of channel reliability, CDF-ORBGRAND exactly achieves the symmetric capacity for binary-input memoryless channels under symmetric inputs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that a simple transformation of the rank ordering in ORBGRAND produces an algorithm that reaches the exact mutual information of the channel. For any binary-input memoryless channel with symmetric input distribution, mapping the reliability ranks through the inverse cumulative distribution function converts the guessing sequence into one whose success probability matches the information-theoretic limit. The same construction is then applied to bit-interleaved coded modulation, where it is shown to attain the BICM capacity even after accounting for the mismatch introduced by treating the bits as independent parallel channels. A reader cares because the result supplies a concrete, implementable decoder that provably saturates the symmetric capacity rather than merely approaching it.

Core claim

Via suitably companding the ranks in ORBGRAND according to the inverse cumulative distribution function (CDF) of channel reliability, the resulting CDF-ORBGRAND algorithm exactly achieves the mutual information, i.e., the symmetric capacity. This result is then applied to bit-interleaved coded modulation (BICM) systems to handle high-order input constellations, showing that CDF-ORBGRAND achieves the BICM capacity after considering mismatched decoding effects.

What carries the argument

Rank companding by the inverse CDF of channel reliability, which reorders the guessing list in ORBGRAND so that the probability of each guess aligns with the channel's reliability distribution.

If this is right

CDF-ORBGRAND reaches the symmetric capacity exactly rather than only approximately for any binary-input memoryless channel under symmetric signaling.
In BICM systems the same construction achieves the BICM capacity after mismatch from independent bit decoding is included.
Guessing-based decoders can be turned into capacity-achieving schemes by a single monotonic transformation of the reliability ranks.
The approach separates the ordering of guesses from the underlying channel statistics in a way that preserves the mutual-information limit.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar inverse-CDF mappings may convert other ordered-reliability decoders into exact capacity achievers for the same channel class.
Hardware implementations could exploit the fact that the companding step is a fixed lookup table once the channel is known.
The construction invites direct comparison with polar or LDPC constructions on the same channels to test whether the guessing overhead remains competitive at finite length.

Load-bearing premise

The exact capacity achievement requires a general binary-input memoryless channel and a symmetric input distribution; deviation from either condition removes the guarantee.

What would settle it

Compute the mutual information for a concrete binary-input memoryless channel with symmetric inputs, run CDF-ORBGRAND at that rate, and check whether the block error rate tends to zero as block length grows; any persistent gap would falsify the exact-achievement claim.

Figures

Figures reproduced from arXiv: 2512.00347 by Wenyi Zhang, Zhuang Li.

**Figure 1.** Figure 1: Comparison between IORB and ICDF-ORB under AWGN, AWLN, and Rayleigh fading channels. Since Rayleigh fading channels are described in complex baseband, the SNR is defined as the effective per-dimension SNR, corresponding to the in-phase component of the received signal. error probability of decoding, which, for the i.i.d. random coding ensemble in our system model, is equivalent to the error probability of … view at source ↗

**Figure 2.** Figure 2: Parallel channel model of BICM with ideal interleaving. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: Gray (left) and SP (right) labelings for 16QAM. Here [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

**Figure 4.** Figure 4: Achievable rates of ORBGRAND, CDF-ORBGRAND, and BICM capacity for QPSK, 8PSK, and 16QAM over Rayleigh fading channel with perfect [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗

read the original abstract

Within the family of guessing-based decoding algorithms, ordered reliability bits GRAND (ORBGRAND) has attracted considerable attention due to its efficient use of soft information and suitability for hardware implementation. It has also been shown that ORBGRAND achieves a rate very close to the capacity of an additive white Gaussian noise channel under antipodal signaling. In this work, it is further established that, for general binary-input memoryless channels under symmetric input distribution, via suitably companding the ranks in ORBGRAND according to the inverse cumulative distribution function (CDF) of channel reliability, the resulting CDF-ORBGRAND algorithm exactly achieves the mutual information, i.e., the symmetric capacity. This result is then applied to bit-interleaved coded modulation (BICM) systems to handle high-order input constellations. Via considering the effects of mismatched decoding due to both BICM and ORBGRAND, it is shown that CDF-ORBGRAND is capable of achieving the BICM capacity, which was initially derived in the literature by treating BICM as a set of independent parallel channels.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

CDF-ORBGRAND exactly achieves symmetric capacity on binary memoryless channels by inverse-CDF rank companding, and the BICM extension follows from the same argument.

read the letter

The main point is that the authors take ORBGRAND, which already gets close to capacity on AWGN, and show that companding the integer ranks with the inverse CDF of the per-bit reliability distribution turns the guessing order into one that exactly matches the mutual information bound for symmetric binary-input memoryless channels. They then carry the same construction over to BICM and argue it reaches the BICM capacity despite the usual mismatches from both the bit interleaving and the decoder itself.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces CDF-ORBGRAND, a variant of ordered reliability bits GRAND (ORBGRAND) in which integer ranks are companded by the inverse CDF of the per-symbol channel reliability distribution. For general binary-input memoryless channels with symmetric input distribution, the authors claim that this procedure yields a guessing order whose cumulative probability mass exactly equals the symmetric capacity (mutual information). The result is then extended to bit-interleaved coded modulation (BICM), where CDF-ORBGRAND is shown to achieve the BICM capacity despite the mismatch introduced by both the BICM demapper and the GRAND-style decoder.

Significance. If the central claim is correct, the work supplies a rare example of a practical, list-based soft decoder that is provably capacity-achieving rather than merely capacity-approaching. The explicit construction via rank companding also furnishes a concrete link between the order statistics of reliability and the information-theoretic bound, which could guide the design of other guessing decoders. The BICM extension further demonstrates that the same technique recovers the BICM capacity under the standard mismatched-decoding analysis.

major comments (2)

[§3] §3 (or the section containing the main theorem): the argument that marginal inverse-CDF companding of per-bit ranks produces a global ordering whose cumulative mass equals the symmetric capacity appears to rely on the companded ranks being equivalent to sorting by the joint likelihood of the noise vector. The manuscript does not explicitly address whether the joint distribution of the companded ranks coincides with the joint likelihood ordering when the underlying reliability random variables are dependent across positions (as they are under a fixed codeword length). A concrete counter-example or a proof step showing that the marginal transform preserves the required order statistics would strengthen the claim.
[Theorem 1] Theorem 1 (or the statement of exact capacity achievement): the derivation assumes a symmetric input distribution and memoryless channel. It is not immediately clear how the same companding rule extends when the input distribution is asymmetric or when the channel has memory; the manuscript should state whether the exact equality continues to hold or whether only an approximation is obtained.

minor comments (2)

[§2] The notation for the companded rank variable (e.g., R' versus R_cdf) is introduced without a dedicated definition paragraph; adding an explicit equation would improve readability.
[Figure 2] Figure 2 (BICM capacity curves) lacks error bars or confidence intervals on the simulated points; including them would make the closeness to the theoretical BICM capacity easier to assess.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major points below and will incorporate clarifications into the revised manuscript.

read point-by-point responses

Referee: [§3] the argument that marginal inverse-CDF companding of per-bit ranks produces a global ordering whose cumulative mass equals the symmetric capacity appears to rely on the companded ranks being equivalent to sorting by the joint likelihood of the noise vector. The manuscript does not explicitly address whether the joint distribution of the companded ranks coincides with the joint likelihood ordering when the underlying reliability random variables are dependent across positions (as they are under a fixed codeword length).

Authors: We appreciate this observation. Because the channel is memoryless, the per-position reliability random variables are conditionally independent given any fixed codeword; the fixed block length does not introduce statistical dependence among the channel outputs. Consequently the joint likelihood factors into the product of marginals, and the marginal inverse-CDF companding applied to each rank preserves equivalence to the joint-likelihood ordering. We will add an explicit paragraph in Section 3 stating this independence and the resulting preservation of order statistics. revision: yes
Referee: [Theorem 1] the derivation assumes a symmetric input distribution and memoryless channel. It is not immediately clear how the same companding rule extends when the input distribution is asymmetric or when the channel has memory; the manuscript should state whether the exact equality continues to hold or whether only an approximation is obtained.

Authors: Theorem 1 is proved under the stated assumptions of symmetric inputs and memoryless channels, which define the symmetric capacity. For asymmetric input distributions or channels with memory the exact equality to capacity does not hold in general; the CDF-ORBGRAND ordering then yields only an approximation to the optimal guessing sequence. We will revise the statement of Theorem 1 and the surrounding discussion to make this scope explicit and to note that extensions beyond these conditions are not claimed to be exact. revision: yes

Circularity Check

0 steps flagged

Derivation self-contained; no reduction to inputs by construction

full rationale

The paper derives that CDF-ORBGRAND achieves symmetric capacity exactly by companding ORBGRAND ranks with the inverse CDF of marginal channel reliability for binary-input memoryless channels under symmetric inputs, then extends the result to BICM capacity. No quoted equation or step in the abstract or context reduces a claimed prediction to a fitted parameter, self-citation chain, or definitional equivalence. The central claim rests on information-theoretic definitions and channel statistics rather than renaming known results or smuggling ansatzes via prior self-work. The derivation is therefore treated as independent and externally falsifiable against mutual information bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard definitions of mutual information and CDF for memoryless channels plus the assumption of symmetric inputs; no free parameters or new invented entities are introduced in the abstract.

axioms (2)

domain assumption Channel is binary-input memoryless with symmetric input distribution
Explicitly required for the exact capacity result to hold, as stated in the abstract.
standard math Mutual information equals symmetric capacity under the given conditions
Standard information theory identity invoked to equate the achieved rate with capacity.

pith-pipeline@v0.9.0 · 5480 in / 1260 out tokens · 54357 ms · 2026-05-17T03:53:30.601518+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the decoding metric of CDF-ORBGRAND is given by D(w) = 1/N ∑ Ψ^{-1}(R_i/(N+1)) · 1(sgn(T_i)·X_i(w)<0)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Performance Analysis and Optimal Design of ORB-Type GRAND Algorithms
cs.IT 2026-06 conditional novelty 6.0

Develops unified AGP framework for ORB-type GRAND, derives exact BLER and stopping-time expressions for random ensembles plus code-dependent bounds, and shows RS-ORBGRAND within 0.1 dB of ML benchmark at 10^{-6} BLER ...