The More The Merrier: Numerically Accurate Coded Computing for Machine Learning Inference

Coded distributed computing mitigates stragglers in machine learning inference, but modern neural network architectures consist of both polynomial and non-polynomial computations. For polynomial components, exact recovery is possible at a recovery threshold $D$, but the resulting decoding matrix can be ill-conditioned, leading to numerical instability under finite-precision arithmetic. Existing frameworks address this issue either by directly optimizing the decoding matrix or by carefully selecting the evaluation points to reduce its condition number. Despite these efforts, the condition number of the decoding matrix can remain large at the recovery threshold $D$. For general non-polynomial functions, approximation-based coded computing avoids the difficulty of exact reconstruction but suffers from approximation error. Classical exact-recovery schemes typically discard worker responses beyond the recovery threshold, leaving available computational redundancy underutilized. In this work, we improve recovery accuracy in both regimes by exploiting $N>D$ available worker responses. For polynomial subnetworks, we introduce ChebyLS, an overdetermined Chebyshev least-squares decoder that utilizes all $N>D$ responses to lower the condition number. We derive a probabilistic condition-number bound that sharpens a general coherence-based row-sampling result by exploiting the deterministic structure of the full Chebyshev-Vandermonde matrix and concentration of the missing workers. For non-polynomial subnetworks, we propose RepApprox, a hybrid Repetition-Approximation strategy that combines replicated exact evaluations with approximation-based coded computing. With $K$ tasks replicated $c$ times across $M$ servers, we show that the probability of exact recovery with $N$ responses is at least $1-K(1-N/M{)}^c$, where a larger $N$ increases the probability of achieving exact inference, with bounded-error approximation as a fallback when a repetition group is lost. We integrate ChebyLS and RepApprox into the heterogeneous Deep & Cross Network v2 architecture, applying them to its polynomial Cross and non-polynomial Deep branches, respectively. Experiments under finite-precision worker computation demonstrate improved end-to-end inference accuracy by exploiting responses beyond the recovery threshold.