Unverified 2026

Berrut-Coded Neural Evaluation

Implementation & benchmark of arXiv:2607.22427 — Robust Berrut-Approximated Coded Computing via Discrete Cosine Transforms

Usefulness6/10

Difficulty6/10

Novelty7/10

Architecture Speedup Stability Scalability Mlp Training Inference speedup Approximation theory Numerical analysis Linear algebra

Source paper: Robust Berrut-Approximated Coded Computing via Discrete Cosine Transforms arXiv:2607.22427 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Encode K input vectors at Chebyshev nodes with a Berrut rational interpolant, send different evaluations of that interpolant to N workers, and let every worker run the same neural function on its encoded input. The master reconstructs the desired outputs at the original data nodes from worker responses, allowing stragglers to be omitted and enabling robust rejection of inconsistent responses.

Formulas

$$\alpha_j=\cos\left(\frac{(2j+1)\pi}{2K}\right),\qquad j=0,\ldots,K-1,$$

$$u(z)=\frac{\displaystyle\sum_{j=0}^{K-1}\frac{(-1)^j}{z-\alpha_j}\mathbf{X}_j}{\displaystyle\sum_{k=0}^{K-1}\frac{(-1)^k}{z-\alpha_k}},\qquad u(\alpha_j)=\mathbf{X}_j,$$

$$\widehat{\mathbf Y}_j=\frac{\displaystyle\sum_{i\in S}\frac{(-1)^{r_i}}{\alpha_j-z_i}\mathbf Y_i}{\displaystyle\sum_{i\in S}\frac{(-1)^{r_i}}{\alpha_j-z_i}},\qquad \mathbf Y_i=F(u(z_i)),$$

$$R_i=\frac{1}{K}\sum_{j=0}^{K-1}\left\|\mathbf Y_i-\widetilde{\mathbf Y}^{(-i)}(z_i)\right\|_2^2,\qquad S_{\mathrm{clean}}=\{i:R_i\leq\operatorname{median}(R)+\tau\operatorname{MAD}(R)\},$$

Mathematical statement

The paper defines data nodes $\alpha_j=\cos((2j+1)\pi/(2K))$, for $j=0,\ldots,K-1$, and stores vectors or matrices $\mathbf X_j$ at those nodes. Its Berrut encoding is $u(z)=\frac{\sum_{j=0}^{K-1}(-1)^j\mathbf X_j/(z-\alpha_j)}{\sum_{k=0}^{K-1}(-1)^k/(z-\alpha_k)}$, where $z$ is a scalar coding coordinate and the denominator is nonzero away from interpolation nodes. By construction, $u(\alpha_j)=\mathbf X_j$. Let $F$ be a neural computation, such as an MLP block, activation map, loss-gradient map, or complete inference network. Worker $i$ receives $u(z_i)$ at a distinct evaluation point $z_i$, returns $\mathbf Y_i=F(u(z_i))$, and the master treats these responses as samples of $v(z)=F(u(z))$. For a responding subset $S$, the reconstructed output at node $\alpha_j$ is $\widehat{\mathbf Y}_j=\frac{\sum_{i\in S}(-1)^{r_i}\mathbf Y_i/(\alpha_j-z_i)}{\sum_{i\in S}(-1)^{r_i}/(\alpha_j-z_i)}$, where $r_i$ is the fixed rank of worker node $z_i$ in the decoder subset. The interpolation is exact when $F\circ u$ belongs to the represented rational-interpolation class and approximate for general nonlinear networks. Byzantine responses can be screened by leave-one-out reconstruction residuals before final interpolation.

Implementation notes

Integrate this at the distributed-worker boundary around one complete smooth neural computation, starting with an MLP inference block rather than an entire deep transformer. Partition a batch into K vectors X[j] with identical shape. Choose K Chebyshev first-kind nodes alpha[j], choose N distinct worker nodes z[i] in [-1,1] away from all alpha[j], and precompute encoding weights w_encode[i,j]=((-1)^j/(z[i]-alpha[j])) / sum_k((-1)^k/(z[i]-alpha[k])). Each worker receives U[i]=sum_j w_encode[i,j]*X[j], computes Y[i]=F(U[i]), and returns Y[i]. The master waits for the fastest responding subset, forms decoder weights w_decode[j,i]=((-1)^rank(i)/(alpha[j]-z[i])) / sum_l((-1)^rank(l)/(alpha[j]-z[l])), and computes Yhat[j]=sum_i w_decode[j,i]*Y[i]. For robustness, calculate each worker's leave-one-out prediction by decoding without worker i, evaluating the resulting rational function at z[i], and computing residual R[i]. Reject workers with R[i] above median(R)+tau*MAD(R), then decode with the remaining workers; sweep tau over 3, 5, and 8. The paper supplies the Chebyshev/Berrut construction, while interpolation error should be estimated empirically by comparing Yhat[j] against uncoded F(X[j]). Do not claim a formal Byzantine guarantee from the extracted material. Start with a 4-layer MLP on MNIST or CIFAR-10, K=8 shards, and N=12 simulated workers. Test 0%, 10%, and 20% stragglers plus 10% and 20% workers returning corrupted outputs. Compare with uncoded execution using replication and with polynomial/Lagrange coded computation at equal worker FLOPs. Measure wall-clock completion time, output MSE, classification accuracy, and Byzantine detection precision. Success means lower time-to-completion at matched MSE under stragglers, graceful nonlinear interpolation error, and reliable rejection of corrupted responses.

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.