Noise-Aware Soft ECOC Decoding
Implementation & benchmark of arXiv:2607.19334 — Fundamental limits of distributed multiclass classification from simple binary decisions
Source paper: Fundamental limits of distributed multiclass classification from simple binary decisions arXiv:2607.19334 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Treat the binary outputs of the hyperplane head as a noisy channel and decode with reliability-weighted likelihood rather than unweighted Hamming distance. Estimate each bit's flip probability on validation data and give unreliable hyperplanes less influence, while retaining the logarithmic code-length scaling.
Formulas
Mathematical statement
The paper's noisy model uses class centers $x_k\overset{iid}{\sim}\mathcal{N}(0,\tau^2I_d)$, an observation $y=x_a+z$ with $z\sim\mathcal{N}(0,\sigma^2I_d)$, and orthonormal hyperplanes $u_1,\ldots,u_N$. For one projection, the clean and noisy scalar coordinates have correlation $\rho=\tau/\sqrt{\tau^2+\sigma^2}$, so the sign-flip probability is $q=\arccos(\rho)/\pi$. Here $\tau$ is the signal scale, $\sigma$ is additive noise scale, and $q$ is the binary channel crossover probability. If bit $n$ has estimated crossover probability $q_n$, the negative log-likelihood decoder is $\arg\min_k\sum_n[-\mathbf{1}\{b_n=c_{k,n}\}\log(1-q_n)-\mathbf{1}\{b_n\neq c_{k,n}\}\log q_n]$. For equal $q$, a Chernoff pairwise bound for two random codewords has the characteristic factor $(1/2+\sqrt{q(1-q)})^N$; a union bound gives $P_e\lesssim(K-1)(1/2+\sqrt{q(1-q)})^N$. This motivates increasing $N$ when bits are noisy and weighting bits by measured reliability.
Implementation notes
Use the same $N$-bit projection head, but retain real-valued logits $s_n$ rather than immediately taking signs. On a held-out calibration set, estimate each bit's conditional error rate $q_n$ by comparing the predicted sign with the target code bit: $\hat q_n=(\sum_i\mathbf{1}[\operatorname{sign}(s_{i,n})\neq c_{y_i,n}]+\alpha)/(M+2\alpha)$, with small Laplace smoothing $\alpha$. At inference, decode with weighted Hamming cost $\sum_n w_n\mathbf{1}[b_n\neq c_{k,n}]$, where $w_n=\log((1-\hat q_n)/\hat q_n)$, or use the soft log-likelihood expression in the formula and replace hard bits with Bernoulli probabilities $p_n=\sigma(s_n)$. During training, use binary cross-entropy but optionally apply dropout to bits according to a simulated crossover probability $q_n$, making the embedding robust to distributed packet loss or noisy quantization. The paper-derived quantities are the Gaussian correlation relation $q=\arccos(\rho)/\pi$ and the exponential pairwise-error factor; actual $q_n$ must be estimated empirically because neural bit errors are not identically distributed. First experiment on CIFAR-100 or ImageNet-100 with a ResNet-18, injecting independent bit flips at inference for rates $q\in\{0,0.01,0.05,0.1,0.2\}$. Compare unweighted Hamming, weighted Hamming, and soft likelihood decoding at the same $N$. Success is a flatter accuracy-versus-noise curve and recovery of baseline accuracy with fewer bits than unweighted decoding; also report calibration cost and decoder latency.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.