acceptodds
Under review as a conference paper at ICLR 2027

Understanding Top- Sparsification in Distributed Deep Learning with LaplaceK

Abstract

Top- sparsification reduces the communication cost of distributed stochastic gradient descent, but existing convergence analyses often characterize its error using the looser Random- contraction. We analyze error-compensated gradients and show that their coordinate magnitudes exhibit a Laplace-like structure, which leads to a tighter characterization of the error introduced by Top- selection. Based on this observation, we introduce LaplaceK, a GPU-oriented selector that uses a Laplace-tail prior to localize a small candidate pool, performs exact Top- selection within that pool, and falls back to global selection when the candidate pool is invalid. This design preserves the exact selected coordinates and transmitted values while reducing selection overhead. Experiments across six non-Transformer image-model configurations show that LaplaceK maintains convergence and final accuracy comparable to magnitude-based sparsification while reducing wall-clock training time. Across the reported experiments, LaplaceK achieves up to speedup over standard TopK-SGD.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Distributed training, Training efficiency

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_KUW8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the selection overhead of gradient sparsification in distributed SGD and proposes LaplaceK. The method initializes a threshold using a Laplace-tail model, constructs a reduced candidate set, performs exact Top-k selection within that set, and falls back to global selection when necessary. Its primary contribution is to reduce the implementation cost of Top-k while preserving its selected output, rather than introducing a new SGD update rule. The paper provides compression-error and error-feedback convergence analyses, and evaluates accuracy, training time, sparsity, and distributed scaling across six image-model configurations, reporting up to approximately 1.70× training speedup over standard TopK-SGD.

Critical strengths
  1. Exact selection within the candidate set and global fallback separate threshold-estimation efficiency from output correctness. Under the stated comparison and tie-breaking conditions, the method preserves the exact Top-k output and transmitted cardinality even when the distributional prior is inaccurate. This makes it a potentially useful replacement for the selector in an existing Top-k compression pipeline, without introducing additional selection approximation error.
  2. The evaluation considers both accuracy versus epochs and wall-clock training time, together with sparsity, candidate-pool size, search-budget, and worker-count analyses. These dimensions are relevant to the practical trade-offs involved in gradient compression. The reported timing improvements suggest potentially useful systems benefits under the evaluated conditions.
Critical weaknesses

The paper demonstrates end-to-end efficiency gains and compares training quality, but the evaluation primarily focuses on relatively small, non-Transformer models. The gains at matched training quality, and their applicability to larger models and different distributed training environments, are not yet sufficiently characterized. This limits my assessment of the method’s practical scope and scalability.

Questions for authors
  1. Could the authors clarify whether the reported speedups hold when methods are compared at the same training-quality target, and whether there are meaningful speed–accuracy trade-offs?
  2. Which model and system conditions are most important for obtaining these benefits? To what extent do the existing results support extending the method to larger models and larger-scale distributed training?
Reviewer_VteaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies error-compensated Top-k gradient sparsification for data-parallel SGD from statistical and systems angles. It observes that error-compensated gradient coordinates have a sharp peak at zero with symmetric tails, and models them as i.i.d. Laplace. Under this model it derives the threshold retaining a fraction α of coordinates and the asymptotic discarded-energy ratio of Top-k. It then proposes LaplaceK, a CUDA selector: the mean absolute value initializes a Laplace-derived threshold, a multiplicative search adjusts it until the candidate count lies in [K, RK], exact Top-K runs inside the pool, and global exact Top-K is the fallback, so the output equals exact Top-k. Experiments on six image models compare Dense, TopK, RandomK, RadiK, AirTopK, Dragonn and LaplaceK SGD by accuracy versus epochs and wall-clock time. LaplaceK is reported fastest on all six models, 3.5%–41.0% below the best baseline and up to 1.70× over TopK-SGD.

Critical strengths

S1. Good theoretical results.

S2. Good experimental setup and results (athough the models are a bit outdated).

Critical weaknesses

W1. The two closest works are uncited: ["Understanding Top-k Sparsification in Distributed Deep Learning", arXiv:1911.08772, 2019] observed the same peaked distribution of error-compensated gradients, explained Top-k versus Random-k with it, proved similar bound to Theorem 4.2, and proposed a fitted-threshold selector with iterative refinement. ["An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems", MLSys 2021], fits a Laplace model similar to this paper.

Questions for authors

Q1. Address W1

Q2. State the GPU, interconnect, communication library, worker count and density behind Table 1, and report isolated per-step selection times of torch.topk, RadiK, AirTopK and LaplaceK. Why is every sparsified baseline, TopK-SGD included, slower than Dense-SGD on LeNet, MNISTNet and ResNet-20?

Reviewer_oVBtOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper identifies a Laplace-like structure in the distribution of error compensated gradients and proposes a method (LaplaceK) that exploits this structure to reduce the computational overhead of Top-K sparsification. Specifically, LaplaceK uses a Laplace-based threshold to identify a smaller set of candidate coordinates, performs exact Top-K selection within this set, and falls back to the global selection procedure when necessary.

The paper also provides a theoretical analysis of Top-K under different assumptions on the distribution of gradients and presents convergence guarantees for the proposed method. The paper evaluate LaplaceK on image classification tasks, reporting comparable accuracy to existing sparsification methods and improvements in wall-clock training time.

Critical strengths

The paper identifies a Laplace-like structure exhibited by the gradients of models in certain tasks, and uses this observation to devise a method that exploits it to alleviate some of the computational overhead of Top-K.

I think the idea of using the gradient distribution to reduce the cost of exact Top-K selection is interesting and potentially useful, particularly since the proposed method aims to preserve the exact Top-K operator rather than introducing an additional approximation.

Critical weaknesses

Major

Presentation and clarity

In general, the paper as a whole is very poorly written in my opinion. I found it difficult to understand even rereading parts of it a few times. The explanations are often unnecessarily complicated, the notation is very inconsistent, and the connection between the different parts of the paper is not always clear (I elaborate on all of this below in the "Minor" section).

Very limited theoretical novelty

I think the paper has very limited theoretical novelty. Most of the theoretical analysis, which is presented as one of the main contributions of the paper, consists of results that are either well-known, taken directly from prior work, or so straightforward that it would be better to explain them directly rather than present them as separate theorems. More specifically:

  1. Theorem 4.1: I'm not sure why this is presented as a theorem. This is a very well-known result that follows directly from the definition of Top-K. It should not be presented as a theoretical contribution of this work.

  2. Theorem 4.2: I also don't know why this is presented as a theorem. The proof is essentially one step, and the conclusion follows immediately from the assumption itself. More importantly, it's a bit unclear under what conditions the assumed inequality (Eq. 19) actually holds for the gradients considered in this paper. Without a proper justification of this assumption, the result provides very limited insight.

  3. Theorem 4.4: This theorem is presented as a convergence guarantee for LaplaceK, but the proof is simply the result from Karimireddy et al. (2019), which is cited in only the appendix and not in the theorem itself. Since Laplace-K implements the exact Top-K operator, the existing convergence guarantee applies directly and trivially. It is misleading to present this as a separate theoretical contribution, and especially without making it much clearer that the result is directly taken from prior work.

  4. Theorem 4.5: I also don't understand why this is presented as a separate theorem. This is essentially identical to Theorem 4.4, with only a different contraction coefficient. Both theorems follow directly from the same existing result (Karimireddy 2019) and could easily be combined with 4.4 (if presented at all).

  5. Lemma 4.7: This can be summarized in one line of math as it follows directly from the survival function of the Laplace distribution. I don't think it warrants a separate lemma and proof.

  6. A similar argument applies to several other lemmas and theorems in this section. Many of these are straightforward consequences of standard identities, assumptions, or previously established results. While some of the distribution-dependent characterizations may be useful, their novelty and significance are not sufficiently explained.

I think the entire theoretical section needs a major revision. There are too many separate theorems and lemmas with very limited novelty, and it is unclear what the authors are trying to establish beyond applying known results to their setting. The paper should clearly distinguish between established results and its own contributions, consolidate the redundant statements, and focus on results that actually provide new insights into the proposed method.

Potential inconsistency between the exact Top-K guarantee and the experiments

The authors repeatedly emphasize that LaplaceK preserves the exact Top-K operator. Specifically, the threshold and candidate-selection procedure only affect the computational path, but the final selected coordinates and their values remain identical to those of standard Top-K.

However, in Appendix C.3 the authors compare Laplace and Gaussian priors and report that the Laplace prior consistently achieves faster convergence and higher final accuracy. I find this very difficult to reconcile with the claimed exactness of the method. If both priors are used only to identify candidate sets, and both implementations ultimately perform exact Top-K selection (using a fallback when necessary), shouldn't they produce exactly the same compressed updates? Under otherwise identical training conditions, the optimization trajectories should also be (nearly) identical. The authors even argue that the Laplace prior preserves important coordinates more reliably than the Gaussian prior. But this seems to directly contradict the claim that both implementations preserve exact Top-K selection.

I think this requires a clear explanation. Either there are important implementation details that are missing, or the proposed method does not always preserve the exact Top-K operator as claimed.

Insufficient justification of the Laplace structure

The Laplace-like distribution of the error-compensated gradients is the central observation motivating the entire paper, yet I don't think it is sufficiently demonstrated or justified. The authors mainly rely on gradient histograms that visually resemble a Laplace distribution. However, a sharp peak around zero and symmetric tails do not necessarily establish that the gradients follow a Laplace distribution, particularly in the tails, which are precisely the part that matters for Top-K selection.

I would have expected a more thorough and quantitative characterization of this structure, including goodness-of-fit measures, comparisons with alternative distributions, and an analysis of how accurately the proposed Laplace model predicts the actual Top-K threshold. Also, it is unclear how consistent this structure is across training iterations, model architectures, layers, and different sparsity levels. Given that this observation is the main motivation for the proposed algorithm, I think a much stronger empirical justification is necessary.

Limited experimental evaluation and statistical reporting.

In general, I think the experimental section is quite limited given the motivation and claims of the paper.

Table 1 presents "the average wall-clock time across repeated runs", yet the main text does not specify how many runs were used and does not present any measure of uncertainty (like SEM or CI). The same applies to Figure 2, the results are presented without error bars / shaded confidence regions, and there is no mention of the number of runs used and it's also unclear whether the runs used different random seeds. There are some variability measurements are in the appendix, but I think the main results should include sufficient information to assess the reliability of the reported results.

Additionally, I would have expected a more detailed breakdown of the computational savings. Since the main contribution of the paper is reducing the overhead of Top-K selection, a direct comparison of the selection time itself, rather than only the overall training time, would be particularly informative. It would also be useful to report the fraction of iterations in which the proposed selection procedure succeeds, how often the global fallback is required, and how these quantities affect the overall performance.

Unclear scaling behavior.

In Table 1, I would have expected the gains of the proposed method to increase with the size of the model, or at least for the authors to investigate how model size affects the improvements. However, in the ResNet models the relative improvement in wall-clock time compared to TopK actually decreases as the models become larger. I understand that the computational savings do not necessarily have to increase monotonically with model size. But given that computational efficiency is the main contribution of the paper, I think this behavior deserves some discussion/explanation.

Minor

  • In the introduction, the sentence "Quantization introduces approximation noise, whereas sparsification may bias updates when important coordinates are omitted" is not entirely accurate. Both quantization and sparsification can be biased or unbiased, depending on the compressor. I suggest revising this.

  • The sentence "The standard analysis treats Top-k through the same generic contraction used for Random-k" could be clearer. While the unscaled Random-k operator considered in the paper does satisfy this contraction bound, this is not generally true for the commonly used unbiased (scaled) Random-k compressor. Moreover, Top-K and Random-k are not necessarily treated identically in existing analyses. I think it wouldbe better if the authors should clarify precisely which formulations they are referring to.

  • I found the notation somewhat unusual and very inconsistent. For example, Top-K already has an explicit parameter KK that is commonly used in the literature, so I'm not sure why the authors primarily define it through a density parameter. This is not incorrect, but I think it makes the presentation less intuitive.

  • There are numerous notation inconsistencies throughout the paper, including:

  1. Using ϵ\epsilon in Section 2 and ee in Section 3 for the error-feedback residual.
  2. Using T0T_0 and τt\tau_t for the threshold, rather than consistent notation, e.g., τ0\tau_0 and τt\tau_t.
  3. Using PτP_\tau and CtC_t for closely related candidate sets.
  4. Using both ρ\rho and dd for the retained density, while dd is also used to denote the dimension of the model.
  5. Using bold notation for vectors in Section 2 but not consistently throughout the rest of the paper.

I think these inconsistencies are unnecessary and make an already difficult-to-follow paper even harder to read.

  • The parameter TT is widely used in the optimization literature to denote the number of iterations (which is also the case in the Theorems you present). I would suggest using a different symbol for the integer threshold-search budget.

  • Section 3 uses CtC_t to denote the cardinality of the set of coordinates satisfying the threshold, while Algorithm 1 uses CC for the set itself and cc for its cardinality. Although these are technically different symbols, I think the notation could be made much more consistent.

  • In Appendix B, it would be more natural to present the proof of Theorem 4.2 before the proof of Theorem 4.4, following the order of the results in the main text.

  • Figure 2 is poorly organized in my opinion. It would be much easier to follow if the accuracy and wall-clock plots for each model were presented side by side, rather than splitting some models across rows. I also think the figure is unnecessarily large for the main paper and could be moved to the appendix, espeically since much of this info is already summarized in Table 1. The discussion of the figure in the main text is also limited.

Questions for authors

Can the authors address the concerns I raised in the weaknesses (Major) section?

1 comment

Dear authors,

I apologize if my initial review is too long. I gave an extreme score, so I needed to justify it thoroughly.

That said, I understand these rebuttals require significant effort and time. Therefore, if it would help alleviate the load, you can focus on addressing the following points, which can affect my decision the most:

  1. Potential inconsistency between the exact Top-K guarantee and the experiments
  2. Insufficient justification of the Laplace structure
  3. Limited experimental evaluation and statistical reporting.
  4. Unclear scaling behavior.

Regarding the part "Very limited theoretical novelty", I'm not sure much can be done here, but if you have further general thoughts on this, I would like to hear them (there is no need, however, to address each and every one of the things I listed there directly).

There is also no need to address the "Minor" section.

Looking forward to your response (although I don't mean to pressure you further with this comment, quite the opposite).

Reviewer_VovXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper explores an interesting perspective on accelerating exact Top-k gradient sparsification by exploiting the distribution of error-compensated gradients. Under an i.i.d. Laplace assumption on their coordinates, the paper derives a tighter asymptotic characterization of the compression error introduced by Top-k sparsification in SGD. LaplaceK uses a Laplace prior to identify a small candidate pool, followed by exact selection and a global fallback. I find the idea of exploiting distributional structure to accelerate Top-k without changing its output appealing.

Critical strengths

The paper offers an interesting perspective on accelerating exact Top-k selection by exploiting the distribution of error-compensated gradients. LaplaceK uses a Laplace prior to reduce the candidate pool while preserving the exact output through candidate selection and a global fallback. Under an i.i.d. Laplace assumption, the paper also derives a tighter asymptotic characterization of Top-k compression error.

Critical weaknesses
  • Limited theoretical novelty. In my view, the main intuition—that concentrating more squared energy in the largest coordinates reduces Top-k compression error—is relatively straightforward. Although the explicit Laplace formula is useful, the sharper finite-dimensional result in Theorem 4.2 essentially assumes the desired energy inequality rather than deriving it from an independently justified structural condition.

  • Missing expected-cost analysis. The paper does not provide a theoretical bound on the expected number of threshold-search iterations, fallback probability, or expected computational savings, even under the idealized Laplace assumption. The empirical search statistics are helpful, but they do not establish when and by how much the method should outperform global exact Top-k.

  • Limited experimental scope. The main acceleration experiments focus on relatively small, conventional image models. It remains unclear whether the observed gradient structure and practical speedups extend to larger language models, including both dense and MoE architectures.

Questions for authors
  • Can the analysis be extended to a standard Gaussian distribution, even if the resulting speedup is smaller? Beyond the empirical comparison in Appendix C.3, can the authors characterize the expected search cost under both Gaussian and Laplace assumptions?

  • Does the Laplace-like structure persist in error-compensated gradients of larger language models, such as 7B and 27B models, including dense and MoE architectures? Quantitative measurements across layers and training stages, together with selection-time benchmarks, would strengthen the paper.

  • Can the proposed Top-k acceleration be applied to the attention indexers in sparse-attention models such as Qwen3.8-Flash-Next or GLM-5.3-Flash, where Top-k selects the tokens or blocks to attend to? In particular, do the indexer scores exhibit a distributional structure that enables faster selection while preserving the exact selected indices? Demonstrating benefits in this setting would substantially strengthen the practical significance of the work

I would be willing to raise my score if the authors convincingly address some of these questions, particularly whether the approach can be extended beyond the Laplace assumption to a standard Gaussian distribution while still accelerating exact Top-k selection, even if the speedup is smaller, or evidence of practical relevance to modern large-scale models. Even detailed evidence establishing whether their error-compensated gradients or attention-indexer scores exhibit the claimed Laplace-like distribution would be valuable; full training experiments would be welcome but are not necessary to address this question.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.