Pith. sign in

REVIEW 3 major objections 5 minor 19 references

Generalized Multivariate Polynomial Codes for Distributed Matrix-Matrix Multiplication

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A tri-variate polynomial code removes the upload-overhead penalties that univariate codes pay in distributed matrix multiplication, at the cost of more computation per block.

desk verdict Solid incremental coded-computing paper with a real flaw in the numerical evaluation: the upload-overhead formulas are used outside their Rth≫N regime, so the reported latency gains may be overstated. read the letter →

arxiv 2411.14980 v1 pith:25TSOPU6 submitted 2024-11-22 cs.IT math.IT

Jesús Gómez-Vilardebó , Burak Has{i}rc{i}oğlu , Deniz Gündüz This is my paper · ORCID
classification cs.ITmath.IT
keywords distributedmatrix-matrixmultiplicationcodedcomputingpolynomialcodesmultivariateinterpolationstragglermitigationcommunicationoverheaduploadcostrecoverythreshold
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper extends bivariate polynomial codes for distributed matrix-matrix multiplication to support arbitrary matrix partitions $(p_0,p_1,p_2)$, going beyond the restricted partition that earlier multivariate schemes required. It proposes two families of coded computing schemes, one bivariate (Bi0 with its dual Bi2) and one tri-variate (Tri), and analyzes their computation-complexity and upload/download communication overheads relative to a single uncoded server. The central claim is that the Tri scheme brings both upload overheads down to $\delta_{u,0}=\delta_{u,1}=(p_1-1)/p_1$, eliminating the $p_0-1$ and $p_2-1$ penalties that univariate entangled polynomial codes incur, while the Bi0/Bi2 schemes remove the penalty on one of the two matrices. This matters because upload cost, not just computation, is a bottleneck in communication-constrained distributed systems, and the paper's latency simulations show Tri beating the univariate baseline under fixed overhead limits.

What carries the argument

The central object is the multivariate product polynomial built from the two encoded matrices, e.g. $\tilde{M}^{\mathrm{Tri}}(x,y,z)=\tilde{M}_0^{\mathrm{Tri}}(x,y)\tilde{M}_1^{\mathrm{Tri}}(y,z)$. The master chooses evaluation points on a Cartesian product $\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$ rather than on a one-dimensional curve; this structured set guarantees decodability by multivariate polynomial interpolation and is what lets the paper count exactly how many coded blocks must be uploaded. The shared variable $y$ is the reuse mechanism: one evaluation of $\tilde{M}_0(x,y)$ can be multiplied against up to $p_2$ evaluations of $\tilde{M}_1(y,z)$ with the same $y$-coordinate, and one evaluation of $\tilde{M}_1(y,z)$ against up to $p_0$ evaluations of $\tilde{M}_0(x,y)$ with the same $y$-coordinate, reducing the number of distinct uploaded blocks. Bi0 and Bi2 use the same machinery with only one matrix encoded bivariately, giving an asymmetric upload saving.

What would settle it

Repeat the Section V latency comparison after replacing formulas (4)-(5) with exact upload counts for each $(p_0,p_1,p_2)$ configuration, e.g. simulating worker assignments until $R_{\mathrm{th}}$ completed products arrive for $p_1=1$, $p_0=p_2=10$, $N=300$; if the exact univariate upload overhead is not $p_2-1$ (and $p_0-1$) times the single-server cost, the reported penalty and the latency gap between Tri and the univariate scheme are artifacts of the $R_{\mathrm{th}}\gg N$ approximation.

Watch

Extended reading notes

Core claim

The paper claims that multivariate polynomial coding can be combined with arbitrary matrix partitions $(p_0,p_1,p_2)$ without paying the upload penalties that univariate entangled polynomial codes incur. In the bivariate scheme Bi0, the blocks of $M_0$ are encoded by $\tilde{M}_0^{\mathrm{Bi0}}(x,y)=\sum_{b_0,b_1} M_0^{(b_0,b_1)} x^{b_0} y^{p_1-1-b_1}$ and those of $M_1$ by a univariate polynomial; because each evaluation $\tilde{M}_1(y)$ is reused across $p_0$ values of $x$, the upload overhead on $M_1$ drops to $\delta^{\mathrm{Bi0}}=(p_1-1)/(p_1 p_2)$, while the overhead on $M_0$ remains $p_2-1+p_2\delta^{\mathrm{Bi0}}$. Bi2 is the dual scheme obtained by swapping $p_0$ and $p_2$. In the tri-variate scheme Tri, $\tilde{M}_0^{\mathrm{Tri}}(x,y)=\sum_{b_0,b_1}M_0^{(b_0,b_1)}x^{b_0}y^{b_1}$ and $\tilde{M}_1^{\mathrm{Tri}}(y,z)=\sum_{b_1,b_2}M_1^{(p_1-1-b_1,b_2)}y^{b_1}z^{b_2}$, so the target block $M^{n_0,n_2}$ is the coefficient of $x^{n_0}y^{p_1-1}z^{n_2}$ in the product polynomial. With the Cartesian product evaluation set $\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$, $|\mathcal{X}|=p_0$, $|\mathcal{Y}|=2p_1-1$, $|\mathcal{Z}|=p_2$, recovery needs $R_{\mathrm{th}}=p_0p_2(2p_1-1)$ evaluations, and the upload overheads for both matrices become $\delta_{u,0}=\delta_{u,1}=(p_1-1)/p_1$. Simulations with 300 workers and shifted-exponential task times show Tri with the lowest average latency under equal upload/download constraints, while the univariate scheme is, in the paper's words, "heavily penalized" at low communication overheads.

Load-bearing premise

The load-bearing premise is that upload cost can be counted by the number of distinct coded blocks sent to the workers over the whole computation, which requires the recovery threshold to be much larger than the number of workers ($R_{\mathrm{th}}\gg N$); the paper's own Section V search includes low-overhead cases with $p_1=1$ and $R_{\mathrm{th}}=p_0p_2\le 100$ while $N=300$, a regime where that premise is violated.

Editorial extensions

If this is right

  • If Tri works as described, choosing finer partitions in the $p_0$ and $p_2$ dimensions no longer increases either upload overhead; both stay at $\delta_{u,0}=\delta_{u,1}=(p_1-1)/p_1$.
  • Bi0 and Bi2 give asymmetric intermediate trade-offs: Bi0 multiplies the computation-complexity overhead by $p_0$ relative to the univariate scheme and removes the upload penalty on $M_1$, while Bi2 multiplies it by $p_2$ and removes the upload penalty on $M_0$.
  • Under the paper's shifted-exponential model with 300 workers, Tri achieves the lowest average latency among the schemes considered for the tested communication-overhead constraints.
  • The three schemes have recovery thresholds that remain linear in the partition level $K=p_0p_1p_2$: $p_0(p_2p_1+p_1-1)$ for Bi0, $p_2(p_0p_1+p_1-1)$ for Bi2, and $p_0p_2(2p_1-1)$ for Tri.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same shared-$y$ reuse mechanism should carry over to matrix-chain products and to secure distributed matrix multiplication, where upload and storage costs are also limiting; the paper does not analyze those settings.
  • The paper assumes a broadcast uplink, where uploading one coded block reaches all workers; in a unicast or star network the reuse of evaluations would not reduce total traffic by the same factor, so the ranking of schemes could change.
  • A boundary test worth running is the regime where $R_{\mathrm{th}}$ approaches $N$; the paper's upload-overhead formulas are derived for $R_{\mathrm{th}}\gg N$, so exact counting at, say, $p_1=1$, $p_0=p_2=10$, $N=300$ would show whether the reported low-overhead advantage of Tri is robust.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. This paper studies distributed matrix-matrix multiplication (MMM) under coded computing, extending the authors' previous bivariate polynomial codes to arbitrary matrix partitions (p0, p1, p2). The master partitions M0 into p0 x p1 blocks and M1 into p1 x p2 blocks, and assigns coded evaluations to N workers that compute multiple subtasks. The paper defines computation, upload, and download overheads relative to a single-server baseline, derives recovery thresholds and overhead expressions for a univariate entangled polynomial code (epc) and for two bivariate schemes (Bi0, Bi2) and one trivariate scheme (Tri) with Cartesian-product evaluation sets, and presents a Monte Carlo study of the latency-communication trade-off. The central claim is that the multivariate schemes achieve lower upload overhead than univariate codes, yielding new points in the latency-overhead trade-off.

Significance. If the claims are substantiated, the paper makes a useful incremental contribution to multivariate coded computing: it generalizes bivariate codes to p1 ≥ 1, introduces symmetric upload-overhead reduction in the Tri scheme, and correctly identifies that the penalty factors p0 - 1 and p2 - 1 in the univariate upload overhead can be removed at the cost of extra computation complexity. The algebraic derivations of Rth and the overhead expressions in Table I check out, and the tensor-product evaluation sets are unisolvent for the stated degree bounds, so the schemes are mathematically sound in the asymptotic regime Rth >> N. The paper is honest about the provenance of the tri-variate encoding polynomials from [6]. However, the numerical evaluation in Section V is not currently reliable, and the unsupported optimality claim should be corrected.

major comments (3)
  1. [Section II, Section V, Eqs. (4)-(5)] The upload overhead formulas (4)-(5) are derived under the explicit assumption Rth >> N, stated in Section II just before these equations. The numerical optimization in Section V, however, uses N = 300, p0, p2 ≤ 10, and at low overhead constraints the feasible regimes force p1 = 1, so Rth = p0 p2 ≤ 100 ≤ N. In this regime the neglected N - 1 unfinished subtasks are of the same order as or larger than Rth, so (4)-(5) underestimate the true upload cost. Because the univariate scheme carries additional p0 - 1 and p2 - 1 penalties, the reported ordering in Figure 2 at low overhead constraints may be an artifact of this under-counting. The authors should either restrict the search to partitions with Rth >> N, derive and use finite-N overhead expressions, or report the scheduling protocol and show that the conclusions are unchanged under exact accounting.
  2. [Section IV (before IV-A)] The sentence 'The Cartesian product set guarantees decodability and provides the lowest possible upload communication overheads' asserts an optimality result without proof. Decodability is standard for tensor-product grids, but the 'lowest possible' part is a lower-bound claim over all evaluation sets and is not established. Since the paper's contribution is framed as new points in the trade-off, this unsupported claim should either be proved (e.g., via a cutset or rank argument on R0 and R1 for a given Rth) or replaced by a comparison with the univariate baseline. The current wording overstates what is shown.
  3. [Section V, Eq. (6)] The Monte Carlo evaluation of the latency T(p0, p1, p2) in (6) does not describe the subtask scheduling/assignment policy, the number of simulation runs, or the confidence intervals, and no code is released. Since Figure 2 is the primary quantitative evidence for the claimed trade-off improvement, these omissions prevent reproducibility and make it impossible to assess whether the scheme ordering is robust to finite-N effects. Please provide the simulation protocol and, preferably, code.
minor comments (5)
  1. [Section II (computation complexity)] In the paragraph defining δ, the text 'each partial computation ... involves r0/p0 r1/p1 r2/p1' should have the last denominator p2, not p1, to be consistent with the block dimensions and with (2).
  2. [Section IV-A] In the expressions for RBi0_0 and RBi0_1, 'RTri_th' appears to be a typo for 'RBi0_th'; as written, it equates two different recovery thresholds.
  3. [Section IV-B] Minor language issues: 'This encoding polynomials' should be 'These encoding polynomials', and 'witch' should be 'which'.
  4. [Section V (Figure 2)] Figure 2 lacks a clear statement of the range of δ̂u,d values and the number of Monte Carlo trials; consider adding error bars or stating that the reported curves are means over a fixed number of runs.
  5. [Section II] The phrase 'For simplicity, we assume the number of partitions is large' could be made precise by stating a concrete inequality such as Rth ≥ cN for some constant c, and checking it for all simulated partitions.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: overhead expressions follow by direct calculation from definitions, and the latency comparison is an independent Monte Carlo search; the Rth≫N regime mismatch is a correctness concern, not circularity.

full rationale

The paper's quantitative claims are derived, not fitted. Section II defines the computation overhead by δ = R_th/K − 1 (Eq. (2)) and the download overhead by δ_d = R_th/(p0p2) − 1 (Eq. (3)); the upload overhead expressions (4)–(5) then follow algebraically from the counts R0 and R1 of uploaded coded blocks. Section IV computes R0 and R1 for the Cartesian-product evaluation sets of the Bi0, Bi2, and Tri schemes, and substituting those counts into (4)–(5) produces exactly the Table I entries, e.g., δTri_u,0 = δTri because R0 = Rth/p2. No parameter is fitted to the reported latency curves; the numerical section is a Monte Carlo search over partition schemes under stated constraints, using the shifted-exponential worker model from the external literature. The self-citations [15] and [16] provide the earlier bivariate framework, and the tri-variate polynomial form is attributed to [6], but the extension to generalized partitions and the multivariate Cartesian evaluation sets is the paper's own contribution; no uniqueness theorem from the authors is invoked to forbid alternatives, and the multivariate interpolation guarantee rests on standard polynomial interpolation over Cartesian products. One non-circularity concern must be flagged: Section II derives the upload overhead formulas under the explicit assumption Rth ≫ N, while Section V explores the low-overhead regime with N = 300 and p1 = 1, where Rth = p0p2 ≤ 100, so the asymptotic upload count may undercount the inputs needed to keep all workers busy and could bias the reported comparison in Figure 2. This is a validity risk in the numerical evaluation rather than a circular reduction of the claimed derivation to its inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No parameters are fitted to data; the simulation constants (1/λ=10, T0=1/(10λ), N=300, p̂0=p̂2=10) are illustrative choices, not fitted to the claimed result. The axioms listed are the load-bearing modeling and mathematical assumptions the analysis rests on. No new physical or mathematical entities are introduced; the coding schemes are polynomial encodings of existing matrix blocks.

assumptions (4)
  • standard math Cartesian product evaluation sets are unisolvent for polynomial spaces of the stated multidegree, so the claimed recovery thresholds are sufficient for interpolation.
    Invoked in Section IV for Bi0, Bi2, and Tri; not proved, but standard for multivariate polynomial interpolation over Cartesian product grids.
  • domain assumption Task completion times follow a shifted exponential distribution with parameters scaled by the number of subtasks (Fi(t)=1-exp(-λK(t-T0/K))).
    Adopted in Section V to model stragglers; standard in the distributed computing literature, but it is a modeling choice that drives the reported latency numbers.
  • domain assumption Upload communication overhead can be approximated by counting coded blocks R0 and R1 required for Rth computations, valid when Rth ≫ N.
    Stated in Section II before equations (4)-(5); violated in the Section V low-overhead regime where Rth can be much smaller than N.
  • domain assumption Uplink uses a broadcast model where one subtask input can be sent to all workers at the cost of one transmission.
    Stated in Section II; this makes the upload cost equal to the number of distinct coded blocks, which the overhead formulas rely on.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Generalized Multivariate Polynomial Codes for Distributed Matrix-Matrix Multiplication." pith.science (2026). https://pith.science/paper/25TSOPU6

@misc{pith2026241114980,
  author       = {Pith},
  title        = {Pith review of: Generalized Multivariate Polynomial Codes for Distributed Matrix-Matrix Multiplication},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/25TSOPU6}},
  note         = {Machine review of arXiv:2411.14980}
}
read the original abstract

Supporting multiple partial computations efficiently at each of the workers is a keystone in distributed coded computing in order to speed up computations and to fully exploit the resources of heterogeneous workers in terms of communication, storage, or computation capabilities. Multivariate polynomial coding schemes have recently been shown to deliver faster results for distributed matrix-matrix multiplication compared to conventional univariate polynomial coding schemes by supporting multiple partial coded computations at each worker at reduced communication costs. In this work, we extend multivariate coding schemes to also support arbitrary matrix partitions. Generalized matrix partitions have been proved useful to trade-off between computation speed and communication costs in distributed (univariate) coded computing. We first formulate the computation latency-communication trade-off in terms of the computation complexity and communication overheads required by coded computing approaches as compared to a single server uncoded computing system. Then, we propose two novel multivariate coded computing schemes supporting arbitrary matrix partitions. The proposed schemes are shown to improve the studied trade-off as compared to univariate schemes.

Figures

Figures reproduced from arXiv: 2411.14980 by the authors.

Figure 1
Figure 1. Distributed computational system. Section II, the problem formulation is presented. Section III characterizes the univariate polynomial coding scheme. Next, Section IV introduces the proposed multivariate polynomial codes. Numerical results are provided in Section V. Finally, conclusions are drawn in Section VI. II. SYSTEM MODEL AND PROBLEM FORMULATION We consider the problem of outsourcing the task of multiply￾ing … view at source ↗
Figure 2
Figure 2. Average computation latency as a function of the communication [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 18 canonical work pages

  1. [16]

    Bivariate polyno- mial coding for efficient distributed matrix multiplication,

    B. Hasırcıo ˘glu, J. Gómez-Vilardebó, and D. Gündüz, “Bivariate polyno- mial coding for efficient distributed matrix multiplication,” IEEE Journal on Selected Areas in Information Theory , vol. 2, no. 3, pp. 814–829, 2021

    work page 2021

  2. [6]

    On the optimal recovery threshold of coded matrix multiplication,

    S. Dutta, M. Fahim, F. Haddadpour, H. Jeong, V . Cadambe, and P. Grover, “On the optimal recovery threshold of coded matrix multiplication,” IEEE Transactions on Information Theory , vol. 66, no. 1, pp. 278–301, 2019

    work page 2019

  3. [1]

    The tail at scale,

    J. Dean and L. A. Barroso, “The tail at scale,” Communications of the ACM , vol. 56, pp. 74–80, 2013. [Online]. Available: http://cacm.acm.org/magazines/2013/2/160173-the-tail-at-scale/fulltext

    work page 2013

  4. [2]

    Speeding up distributed machine learning using codes,

    K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” IEEE Transac- tions on Information Theory , vol. 64, no. 3, pp. 1514–1529, 2017

    work page 2017

  5. [3]

    High-dimensional coded matrix multiplication,

    K. Lee, C. Suh, and K. Ramchandran, “High-dimensional coded matrix multiplication,” in 2017 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2017, pp. 2418–2422

    work page 2017

  6. [4]

    Polynomial codes: An optimal design for high-dimensional coded matrix multiplication,

    Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Polynomial codes: An optimal design for high-dimensional coded matrix multiplication,” in Proc. Int’l Conf. on Neural Information Processing Systems , 2017, pp. 4406–4416

    work page 2017

  7. [5]

    Straggler mitigation in distributed matrix multiplication: Funda- mental limits and optimal coding,

    ——, “Straggler mitigation in distributed matrix multiplication: Funda- mental limits and optimal coding,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1920–1933, 2020

    work page 1920

  8. [7]

    On the capacity of secure distributed matrix multiplication,

    W.-T. Chang and R. Tandon, “On the capacity of secure distributed matrix multiplication,” in 2018 IEEE Global Communications Conference (GLOBECOM), 2018, pp. 1–6

    work page 2018

Show all 19 references
  1. [8]

    Gasp codes for secure distributed matrix multiplication,

    R. G. L. D’Oliveira, S. El Rouayheb, and D. Karpuk, “Gasp codes for secure distributed matrix multiplication,” IEEE Transactions on Information Theory , vol. 66, no. 7, pp. 4038–4050, 2020

    2020

  2. [9]

    Coded matrix chain multiplica- tion,

    X. Fan, A. Saldivia, P. Soto, and J. Li, “Coded matrix chain multiplica- tion,” in 2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS) , 2021, pp. 1–6

    2021

  3. [10]

    Computation scheduling for distributed machine learning with straggling workers,

    M. M. Amiri and D. Gündüz, “Computation scheduling for distributed machine learning with straggling workers,” IEEE Transactions on Signal Processing, vol. 67, no. 24, pp. 6270–6284, 2019

    2019

  4. [11]

    An optimal coded matrix multiplication scheme for leveraging partial stragglers,

    L. Song, L. Tang, and Y . Wu, “An optimal coded matrix multiplication scheme for leveraging partial stragglers,” in 2023 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2023, pp. 1741–1744

    2023

  5. [12]

    Exploitation of stragglers in coded computation,

    S. Kiani, N. Ferdinand, and S. C. Draper, “Exploitation of stragglers in coded computation,” in 2018 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2018, pp. 1988–1992

    2018

  6. [13]

    Straggler-aware dis- tributed learning: Communication–computation latency trade-off,

    E. Ozfatura, S. Ulukus, and D. Gündüz, “Straggler-aware dis- tributed learning: Communication–computation latency trade-off,” En- tropy, vol. 22, no. 5, p. 544, 2020

    2020

  7. [14]

    Coded computation over heterogeneous clusters,

    A. Reisizadeh, S. Prakash, R. Pedarsani, and A. S. Avestimehr, “Coded computation over heterogeneous clusters,” IEEE Transactions on Infor- mation Theory , vol. 65, no. 7, pp. 4227–4242, 2019

    2019

  8. [15]

    Bivariate polyno- mial codes for secure distributed matrix multiplication,

    B. Hasırcıo ˇglu, J. Gómez-Vilardebó, and D. Gündüz, “Bivariate polyno- mial codes for secure distributed matrix multiplication,” IEEE Journal on Selected Areas in Communications , vol. 40, no. 3, pp. 955–967, 2022

    2022

  9. [17]

    A unified coded deep neural network training strategy based on generalized polydot codes for matrix multiplication,

    S. Dutta, Z. Bai, H. Jeong, T. M. Low, and P. Grover, “A unified coded deep neural network training strategy based on generalized polydot codes for matrix multiplication,” arXiv preprint arXiv:1811.10751 , 2019

    2019 arXiv

  10. [18]

    R. A. Lorentz, Multivariate Birkhoff Interpolation . Springer, 2006

    2006

  11. [19]

    Tofec: Achieving optimal throughput-delay trade-off of cloud storage using erasure codes,

    G. Liang and U. C. Kozat, “Tofec: Achieving optimal throughput-delay trade-off of cloud storage using erasure codes,” inIEEE INFOCOM 2014- IEEE Conference on Computer Communications . IEEE, 2014, pp. 826– 834

    2014

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.