We express our gratitude to the reviewer for their valuable comments and feedback. In the above, we have offered a general response to the reviewers, addressing some of their common concerns. Here, we provide additional responses to the remaining questions raised.

Major: The biggest thing that confused me when reading the paper was the use case for this kind of method. As far as I understand, this method is specifically designed for inference. Inference of computer vision models such as the ones used in the experiments of this paper (VGG, VIT) is actually very fast in practice. Even mobile phones can run inference on these models within a few tens or hundreds of milliseconds. What application would require to run many inferences for these models in parallel in a timely manner? I understand that the results are interesting from a theoretical point of view. It’s nice that encoding and decoding functions can be derived theoretically. But from a practical perspective, I cannot think of a scenario where one would need to make their inference straggler-resilient because it is typically already very low latency. (Furthermore, if an even lower latency is needed, then quantization is usually the direction to explore.) Please let me know if I’m missing something here. Perhaps, straggler resilient computing makes more sense for large-scale computing (e.g. large-model training) where you have a large-scale computation that is distributed onto a compute cluster.

Answer: We appreciate the reviewer’s valuable feedback. We would like to answer this as follows:

1. Machine Learning as a Service (MLaS) is a new paradigm where resource-constrained clients outsource their computationally expensive tasks to powerful clouds such as Amazon, Microsoft, and Google [1]. Consequently, prediction serving systems in these powerful clouds host complex machine learning models and respond to a vast number of inference queries worldwide with low latency [1]. However, the limited number of worker nodes, the large volume of inference queries, and the ever-increasing complexity of models make this task even more challenging. In this context, addressing the straggler issue and making the entire system straggler-resistant is crucial. As shown in [2], stragglers are inevitable even in simple tasks like matrix multiplication. Therefore, straggler resiliency is a vital feature of any prediction serving system.

2. Inference is just one example of the proposed framework's applications. As mentioned in the paper, the framework is designed for general computing functions. Notably, inference is a crucial task, as it has been used as a benchmark in other works, such as [1]. By utilizing the gradient of a model's loss with respect to its parameters as the computing function, $f(x) =\nabla L(x; \theta)$, where $L$ is the loss of a large pre-trained neural network like large language models, the proposed framework can be applied to fine-tuning large neural networks as well. We consider this case as a potential direction for our future work.

[1] Soleymani, M., et al. "ApproxIFER: A model-agnostic approach to resilient and robust prediction serving systems." AAAI 2022.

[2] Gupta, V., et al. "Oversketch: Approximate matrix multiplication for the cloud." Big Data 2018.

Minor: Some of the related work on coded computing has the property that if a given number of nodes return their solution, the exact output can be recovered and if not, an approximate solution can be generated. As far as I understand, the proposed method cannot recover the exact result even if all nodes return their result successfully. Please correct me if I’m wrong about this point. I wonder if this method could be modified to have the exact recovery property.

Answer: We appreciate the reviewer’s valuable feedback. To the best of our knowledge, for general computation, there is no solution that has the property of exact recovery for a small number of stragglers and approximate results for a larger straggler. On the other hand, for specific structured computations such as polynomial computation, Lagrange coded computing [1] can give us exact output if $(K-1)\cdot \operatorname{deg}(f) + S < N$. However, the decoding algorithm of Lagrange coded computing does not work for the cases where the above condition does not hold. If we use a heuristic solution in which we fit a lower degree polynomial to the existing solution, the approximation is not acceptable (see Figure 3 in the attachment).

Additionally, if the function that we want to compute belongs to the space of functions generated through smoothing spline basis (refer to Equation (5) in the paper), then exact recovery is also feasible in our proposed scheme with appropriate hyper-parameters and appropriate condition on the number of stragglers.

[1] Yu, Q., et al. "Lagrange coded computing: Optimal design for resiliency, security, and privacy." PMLR 2019.

Dear Reviewer a2Af,

As we approach the conclusion of the author-reviewer discussion phase, we wish to gently remind you that we remain available to address any additional questions or concerns you may have before finalizing your score.

Best regards, The Authors

Thank you for your valuable feedback.

The importance of stragglers in distributed computing was raised in a seminal paper by Google [1]. The proposed framework introduces a straggler-resistant scheme for general computing, which is not limited to inference. For numerical evaluation, we chose machine learning inference as a benchmark, as it has been used in related papers such as [2].

[1] Dean, J., et. al, "The tail at scale." Communications of the ACM 2013

[2] Soleymani, M., et al, "ApproxIFER: A model-agnostic approach to resilient and robust prediction serving systems." AAAI 2022.

We express our gratitude to the reviewer for their valuable comments and feedback. In the above, we have offered a general response to the reviewers, addressing some of their common concerns. Here, we provide additional responses to the remaining questions raised.

LeTCC is proven to have a reconstruction error that scales better than BACC in terms of the number of worker nodes, but its scaling in terms of the number of stragglers is not directly compared. Based on Theorem 9 in the BACC paper, it appears that the max error along a single dimensions scales as S^2 The mean-squared error (MSE) for LeTCC scales as S^4 but since the max norm is upper bounded by the Euclidean norm it is unclear how to compare these results. It would be nice to compare the theoretical dependence on the number of stragglers, especially since the experimental results are mixed (in two cases the difference in MSE shrinks as S increases, and in the other case the MSE grows as S increases).

Answer: We thank the reviewer for the detailed question. Note that our proposed solution achieves a factor of $S^4$ for the squared $\ell_2$ norm of the error, compared to the factor of $S^2$ for the $\ell_\infty$ norm of error (equivalently $S^4$ factor for squared $\ell_\infty$ norm) in the BACC paper. Thus, if we compare these two schemes since $\ell_2$ norm is upper bounded by $\ell_{\infty}$ norm, both of them have the factor of $S^4$ for the upper bound of the $\ell_2$ norm of the error. Therefore, we cannot conclude that BACC performs better than LeTCC in terms of the scale of the error as a function of $S$.

The authors should explicitly state how many trials were averaged over to produce the plots in figure 3 to help readers interpret and/or reproduce the results.

Answer: We have provided information on the statistical properties of our experiments, including confidence intervals, in the general rebuttal and Figures 1 and 2 of the attached PDF. For a comprehensive overview of our experimental results and statistics, please see the general rebuttal and the attached file.

I identified the following typos in the paper:

• Line 502: There is a “loc” subscript missing

• Line 49: The sentence starting on this line is grammatically incorrect, I presume that the second comma is supposed to be replaced with the word “is”

• Figure 3: The title of the top-left plot seems to have the values of N and K reversed

Answer: Thank you for pointing out the typos in our paper. We appreciate your attention to detail and have corrected them.

Without more details on the hyperparameter optimization process and the relative computational complexity of fitting the encoder and decoder functions as compared to those of BACC, it is hard to say whether LeTCC is more practically advantageous to use than BACC. It could be that the overhead introduced by hyperparameter tuning outweighs the benefit from reduced reconstruction error in some cases. It would have been helpful to see how tolerant LeTCC is to changes in the smoothing parameters, i.e. how much variation can be allowed while still outperforming BACC. One can also see from Figure 3 that a large difference in the mean-squared error does not consistently translate to a large difference in relative accuracy (at least when deep models are used), which makes it less likely that LeTCC’s performance benefits would be worth the additional overhead. As it currently stands, these issues reduce the practical value of the contribution made by this paper.

Answer: Please refer to the general rebuttal and attached PDF for comprehensive information on the experiments, including smoothing parameter sensitivity, experimental statistics, and a comparison of the computational complexity of the proposed model.

According to Theorem 4, the mean-square error of LeTCC has a much worse scaling in terms of the number of stragglers in the noiseless setting than in the noisy setting. Does this originate from a sacrifice made to improve the scaling with respect to the number of worker nodes, or is there some other cause?

Answer: Based on Theorem 4, the error convergence rates of noiseless and noisy settings are $\mathcal{O}(S\cdot(\frac{S}{N})^3)$ and $\mathcal{O}(S\cdot(\frac{S}{N})^\frac{3}{5})$, respectively. We note that, for $S<N$, $S\cdot(\frac{S}{N})^3 < S\cdot(\frac{S}{N})^\frac{3}{5}$ and thus, as we expect, the upper bound on the error of the noiseless cases scales better compare to that of noisy ones. It is important to note that considering the variation of these bounds as a function of $S$ without considering the effect of $N$ may lead to a misleading conclusion

Limitations: The authors are upfront about the limited scope of their work. However, as mentioned in the weaknesses section, the extra overhead introduced by the need for hyperparameter tuning is something that I would have liked to have seen addressed in the paper. As mentioned in the weaknesses section, the comparison of error convergence rates with BACC is also limited.

Answer: We thank the reviewer for pointing out the limitations of out work. We have already addressed some of them in the general rebuttal and we will include them as a separate section in the revised paper. Also we decided to add a full section to the revised version of the paper to discuss the limitations in a more structured way in the paper.

We express our gratitude to the reviewer for their valuable comments and feedback. In the above, we have offered a general response to the reviewers, addressing some of their common concerns. Here, we provide additional responses to the remaining questions raised.

The experimental section does not look comprehensive enough for the following reasons: (a) Only one baseline is considered. (b) Authors acknowledge in Section 3 that the computational efficiency of encoder and decoders is a crucial factor. Yet, this was not reported in the numerical section.

Could the authors provide comparison with additional baselines?

Could the authors report the computational resources needed for fitting and evaluating the encoder and decoder?

Answer: We thank the reviewer for their constructive comment. Although there is only one baseline for general computing approximation, we compared our proposed scheme with Lagrange Coded Computing for polynomial computation. Additionally, we have analyzed the computational complexity of our scheme and compared it with BACC and Lagrange. Please refer to our general response for a detailed discussion.

The computing functions (which are generally pre-trained neural networks) are evaluated on (probably) mixtures of input samples at the worker nodes. Those neural networks were trained on the data distribution. However, the mixture of input samples might not fall on the support of data distribution. Although for images, this does not seem to be an issue, there could be unexpected behavior in general.

Also, does this framework work (or can it be modified to work) for computing functions that take discrete inputs?

Answer: We appreciate the reviewer's thoughtful and detailed comment. Firstly, as established in Theorems 1-3, our results are predicated on the assumption of computing function smoothness, which is guaranteed by bounding the maximum norm of its first and second derivatives. Consequently, our framework ensures high recovery accuracy only when the computing function exhibits smoothness. If this smoothness assumption is not met, our framework cannot guarantee accurate recovery.

Secondly, based on the results of Theorems 1-3 and Corollary 2, we have shown that the optimal encoder is the smoothing spline. It is shown that the smoothing spline operator is asymptotically equivalent to a kernel regression estimator with a Silverman kernel, whose local bandwidth is $\lambda^{\frac{1}{4}}q(t)^{\frac{-1}{4}}$, where $\lambda$ is the smoothing parameter and $q(t)$ is the probability density function of the input data points [1]. This leads to the key observation:

• In the smoothing spline, the bandwidth (i.e., the number of data points effectively contributing to the input data of a worker node) and their corresponding weights depend on the input data distribution as well as the smoothing parameter. This property makes our approach more generalizable to various data distributions. If the data distribution is such that a linear combination of input data points may be inappropriate, we can control the number of points involved in the linear combination and their weights by choosing the right smoothing parameter. This ensures that the output of the linear combination remains reasonably close to the data distribution on which the model was trained.

In contrast, the Berrut approach has a fixed, bounded bandwidth due to the $\frac{1}{z-\alpha}$ factor in the numerator of the data points coefficient $u_{enc}(z)=\sum_{i=0}^{K-1} \frac{\frac{(-1)^i}{\left(z-\alpha_i\right)}}{\sum_{j=0}^{K-1} \frac{(-1)^j}{\left(z-\alpha_j\right)}} \mathbf{x}_i$ Therefore, the problem that the reviewer mentioned will affect BACC more. This observation suggests another perspective on why the proposed solution outperforms BACC.

Finally, in the case of discreet input, if the model exhibits "smoothness" (i.e., it accepts continuous input and has bounded first and second derivatives, ensuring that small changes in the input result in minimal output changes), our proposed scheme will be effective.

[1] Silverman, B.W. "Spline smoothing: the equivalent variable kernel method." The Annals of Statistics, 1984

Limitations: Yes, but it is spread out throughout the manuscript. A separate limitation section/paragraph would be helpful for the readers.

Answer: We thank reviewer for the helpful comment. We will add a dedicated section to the limitations of our work in next version.

We express our gratitude to the reviewer for their valuable comments and feedback. In the above, we have offered a general response to the reviewers, addressing some of their common concerns. Here, we provide additional responses to the remaining questions raised.

«We develop a new foundation for coded computing, based on the theory of learning rather than the theory of coding». I would not be so categorical. Coding is a method when you add and the utilize the redundancy to deal with errors and erasures. The main advantage of your approach is that you are not using standard finite field codes.

Answer: We appreciate the reviewer’s valuable feedback. We would like to clarify our first contribution. As we mentioned in the objective box (line 70):

The main objective of this paper is to develop a new foundation for coded computing, not solely based on coding theory, but also grounded in learning theory

as well as abstract (lines 8 and 9):

we propose a novel foundation for coded computing, integrating the principles of learning theory, and developing a new framework that seamlessly adapts with machine learning applications.

Therefore, what we mean by "based on the learning theory" is basically integrating a learning theoretic mindset, on top of coding theory, into the whole framework, including (i) considering the whole system as an end-to-end system, (ii) defining its corresponding loss function and (iii) deriving optimum encoder and decoder function using theories from kernel regression. It does not mean that we are not using coding and learning theoretical approaches instead. Conventional coded computing did not consider the whole system view and was solely based on algebraic coding theory, originally developed for communication theory, which makes them not well generalizable to machine learning applications.

We agree that this sentence in Line 86 could cause misunderstanding, and we will change it accordingly.

How the optimal (under some assumptions) encoder and decoder functions in section 4 are related to the functions utilized for numerical experiments (DNNs)? Is it possible to analyze the performance under optimal encoder and decoder and compare it to the results from Section 5?

Answer: In fact, we do use the optimal encoder and decoder functions in the numerical experiments. We proved in Corollary 4 (lines 236-240) that the optimal encoder function is the smoothing spline function, just like the decoder function. As a result, we use smoothing spline functions for our experiments in both encoder and decoder with smoothing parameters $\lambda_{enc}$ and $\lambda_{dec}$ respectively. For more clarification, we will mention this fact directly in our experimental setup section (Section 5).

You made the comparison to BACC, which is a framework for general computing. Could you please make a comparison for some particular (e.g. polynomial) problems? I just wonder if proposed general approach is competitive with e.g. Lagrange computing and what you should pay for universality. So my claim is that more scenarios and computing problems should be checked to understand the limitations and applicability of your method.

Answer: We have provided further comparisons with Lagrange Coded Computing in the general rebuttal, as well as in Figure 3 of the attached PDF.

How flexible is your approach if the system parameters change (the number of worker nodes or the number of stragglers).

Answer: We have included a discussion on the sensitivity of the framework's hyper-parameters ($\lambda_{enc}$ and $\lambda_{dec}$) to the number of stragglers in the general rebuttal.

Figure 3 seems to suffer from the lack of statistics (you need more experiments).

Answer: We have included a detailed description of our experiments and added confidence intervals to the plots. Please refer to the general rebuttal and Figures 1 and 2 in the attached PDF for a comprehensive discussion.

You mentioned the Byzantine case. It is known to be a problem for the codes over the real field (in the case of the finite field, the approaches are well-developed). It would be beneficial to briefly explain how you plan to deal with this problem.

Answer: We appreciate the reviewer's insightful comment. While analyzing the scheme in the presence of Byzantine faults is beyond the scope of this paper, which primarily focuses on straggler resiliency, we acknowledge the importance of this aspect. Similar to [1], which enhances Berrut coded computing with Byzantine robustness using the Berlekamp-Welch (BW) decoding algorithm for Reed-Solomon codes [2], we plan to explore the same approach to incorporate Byzantine robustness into our framework. Still, it needs significant work to design an effective error correction algorithm and develop a theoretical guarantee tailored to our framework.

[1] Soleymani, M., et al. "ApproxIFER: A model-agnostic approach to resilient and robust prediction serving systems." AAAI 2022. [2] Blahut, R.E., "Algebraic codes on lines, planes, and curves: an engineering approach." Cambridge University Press 2008.