CodedNN: Coding-Theoretic Redundancy for Robust Neural Classification

Neural classifiers can degrade substantially under input corruptions and perturbations to learned features. We investigate a simple way to improve reliability: encode labels into redundant binary outputs and train a shared-backbone network to predict the resulting codeword. Coded Neural Networks (CodedNN) preserve the original label coordinates in multilabel classification (MLC), while redundant parity coordinates provide additional supervision and can optionally be exploited by belief-propagation (BP) decoding; in single-label classification (SLC), classes are represented by redundant binary codewords and prediction is performed by soft codeword matching. A central difficulty is that learned output errors are strongly dependent, so the independent-channel abstraction underlying classical error-correcting codes does not accurately describe neural predictions. We therefore develop a dependence-aware analysis of aggregate codeword errors, including a distribution-free correction-radius bound and a Gaussian-margin reference model. Empirically, redundant outputs provide gains in both clean and corrupted regimes. Across 13 clean MLC benchmarks, raw CodedNN improves micro-F1 over a matched binary-cross-entropy predictor by 1.5 percentage points on average, while explicit decoding provides additional robustness in some corrupted regimes. On CIFAR-10-C, redundant 8-bit output representations improve mean corruption accuracy by up to 1.67 percentage points over softmax with essentially unchanged clean accuracy, and on ImageNet the coded model exceeds softmax by 12.2 points under the strongest tested feature perturbation. These results show that structured output redundancy can improve neural reliability even when classical coding assumptions fail, providing a framework for exploiting redundancy through both representation learning and decoding.