Correcting Errors, Correctly: Certified Robustness for Error-Correcting Output Codes

Error-Correcting Output Codes (ECOC) leverage redundancy from coding theory to map classes into structured codewords rather than standard one-hot encodings. While this paradigm enhances empirical robustness in machine learning tasks, it remains a heuristic defense susceptible to adaptive adversaries, and to date no certified robustness guarantee exists. We bridge this gap by presenting the first certification framework for ECOC-based models. Leveraging per-bit certification and decoding-aware analysis, we derive closed-form robustness bounds for both hard and soft decoding schemes, enabling efficient and scalable certification for structured multi-class outputs. Extensive experiments show that our approach consistently certifies a larger certified radius and a higher proportion of inputs than naive certification of the same ECOC model, while also increasing resistance to practical adversarial attacks. These results demonstrate that integrating error-correcting structure into certification yields stronger and more reliable robustness guarantees for multi-class prediction.