acceptodds
Under review as a conference paper at ICLR 2027

Mixture of Sketches: Learning-Augmented Distributed Sketch Aggregation with NetSketch

Abstract

Estimating frequencies of elements in a distributed data stream is a key task in machine learning, databases, and network measurement. It utilizes popular sketches such as count-min sketch (CMS) to collect data with worst-case error guarantees in the single-node setting, while a global frequency view is obtained by maintaining per-node sketches and aggregating them counter-wise. State-of-the-art sketches attach learned neural corrections to sketches to mitigate single-node errors, but per-node correction easily ignores cross-node statistics after aggregation. To address this problem, we propose NetSketch, an implementation of mixture of sketches (MoS) with a local correction module (LCM) at each node and a merge-aware correction module (MACM) at the aggregator. Each node runs the LCM and transfers its corrected sketch and compact summary while the aggregator counter-wise merges the corrected sketches and runs the MACM with cross-node statistics to produce global estimates. Extensive experiments on eight real-world workloads show that NetSketch achieves 1.6-17.2 AAE reduction over six state-of-the-art baselines. Our analysis further characterizes why the two-level design helps, i.e., it improves the aggregation-error dependence from for single-level correction to for MoS, with a finite-sample refinement and a matching lower bound.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
sketches, distributed sketch aggregation, frequency estimation

Reviews

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

This paper proposes NetSketch for distributed frequency estimation. A local correction module (LCM) adjusts estimates at each node, while a merge-aware correction module (MACM) uses the merged sketch and cross-node summaries to refine global estimates. The paper claims an O(\sqrt K,\epsilon_{\mathrm{single}}) error bound. The two-level idea is promising, but the proposed method is not described clearly enough to assess how its key components are implemented.

Critical strengths
  1. Separating local collision correction from post-aggregation correction is a distinctive way to address errors that arise at different stages of distributed measurement.
  2. The paper reports improvements across accuracy and memory budgets with module ablations. These results make the approach worth investigating.
Critical weaknesses
  1. The paper does not measure whether A1 or the memory condition A2 holds in its main experiments.
  2. Section 3.3.1 defines the per-item estimate \hat f_i^{(k)}, but it did not explain how those item-specific corrections are encoded in \tilde M^{(k)}. This matters because multiple items share counters, and MACM relies on merging the resulting sketches.
  3. The paper does not sufficiently motivate the separate roles of f_{\mathrm{global}}, f_{\mathrm{local}}, f_{\mathrm{load}}, and f_{\mathrm{dec}}. It also does not clearly explain why the representations h^{(k)} is needed and what information \phi^{(k)} preserves for the merge-aware correction.
  4. Eqs. (12) trains the skip gate only through a nonnegative penalty on |g_i\Delta_i^{(a)}|, which favors g_i\to0 even when a large correction is needed.
  5. The values of \lambda_1 and \lambda_{\mathrm{skip}} are not reported in the experiments.
  6. The eight real workloads also come from two closely related traffic-trace groups, limiting evidence of broader transfer.
  7. The paper does not compare NetSketch’s training time with that of the baselines, leaving the training cost of its accuracy gains unclear.
Questions for authors

See Weaknesses.

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

The paper targets distributed frequency estimation where per-node sketches are merged by counter-wise addition. Its main observation is that existing learned sketch correctors are designed for single-node settings and degrade badly after aggregation, with error amplified by KK. The authors propose NetSketch, a two-level design: an LCM at each node corrects local collision error and sends a compact summary, and a MACM at the aggregator applies a residual correction using cross-node statistics. They show the error improves from Ω(Kϵsingle)\Omega(K\epsilon_{\mathrm{single}}) to O(Kϵsingle)O(\sqrt{K}\epsilon_{\mathrm{single}}), and evaluate on eight real traffic traces with up to 64 nodes against six baselines.

Critical strengths

S1. The authors' research on the distributed sketch aggregation problem is meaningful.

S2. The LCM+MACM two-level correction architecture is also reasonable and somewhat innovative.

S3. The experimental evaluation is extensive in its selected settings, and the results appear promising.

Critical weaknesses

W1. The authors do not explain why the "Min of Sums" approach was chosen over the more accurate "Sum of Mins" method used in SCREAM; furthermore, the theoretical derivation conflates these two operations. Additionally, under appropriate conditions, Count Sketch can also achieve an error growth of O(K)O(\sqrt K) through local summation-based estimation.

W2. LCM produces item-wise correction results, whereas MACM takes a corrected counter matrix as input. Since multiple items may map to the same counter, there is an unexplained, critical gap in the algorithmic pipeline between these two components.

W3. The training process for LCM does not adequately account for items with a local frequency of zero. In a distributed setting, an item might appear at only a few nodes, yet it can still cause collision errors at the remaining nodes.

W4. The theoretical analysis assumes that LCM residuals have a zero mean, are mutually independent, and have controlled variance—yet these properties are never proven. In particular, the use of an L1 loss does not guarantee unbiasedness, and the sharing of hash functions does not ensure the independence of residuals.

W5. The review of related work is incomplete; it fails to discuss other research on distributed sketch aggregation, such as SCREAM, Cluster-Reduce, and MimoSketch.

W6. The paper lacks experiments to justify the necessity of the proposed LCM design—for instance, by comparing it against an alternative setup that uses RatioSketch for local correction and MACM for global correction.

Questions for authors

I look forward to a clear and constructive response to the weaknesses above. I will carefully evaluate the rebuttal and consider adjusting my score accordingly.

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

This paper studies distributed frequency estimation with sketches. In its setting, each nodes maintain local sketches and merge them to estimate global item frequencies. The paper argues that local collision errors accumulate after merging, while existing learned sketch methods either lack cross-node information or lose useful local information. To address this issue, the paper proposes a two-level framework called Mixture of Sketches, implemented as NetSketch. Each node uses a Local Correction Module to correct local estimates and produce a compact feature summary. The aggregator merges the corrected sketches and applies a Merge-Aware Correction Module, which uses cross-node statistics to estimate the remaining error. Experiments on network traffic traces show that NetSketch improves frequency-estimation accuracy over CMS and several learned-sketch baselines.

Critical strengths

S1. The paper considers a practical distributed sketching setting. Its two-level design preserves local information before merging and uses cross-node statistics afterward, which is a reasonable approach for settings where raw traffic cannot be centralized.

S2. The evaluation includes several relevant baselines and ablations. The results suggest that both the local and merge-aware correction modules contribute to the reported improvements.

Critical weaknesses

W1. The distinction between centralized processing and distributed merging could be clearer. Under the paper’s setting, if all nodes use the same hash functions and standard CMS instances are merged by counter-wise addition, the merged sketch is equivalent to a centralized CMS of the same size over the union stream. This also applies to many linear, mergeable sketches. Therefore, the benefit of the proposed approach may come mainly from retaining node-level side information, such as the pooled ϕ(k)\phi^{(k)} features, rather than from the merging operation itself. A clearer discussion of these two factors would help explain the motivation.

W2. The realism of the distributed setting is not fully established. The WAN and MAWI traces appear to be complete traffic traces that are later partitioned into KK nodes using uniform, hash-based, and Zipf-weighted splitting. These controlled splits are useful for evaluation, but it is unclear how well they represent real multi-vantage-point, multi-switch, or multi-datacenter deployments, where node traffic can have stronger correlations, overlap, and different load patterns.

W3. The dataset coverage is relatively narrow. The evaluation uses only WAN and MAWI network traffic traces. According to Appendix F, Figure 7, their fitted Zipf parameters also appear relatively similar. Evaluating the method on more diverse network traces, online service logs, web request streams, or workloads with more different skew levels would provide stronger evidence of general applicability.

W4. The comparison and discussion of related sketches could be broader. The evaluation does not include several widely used network measurement sketches, such as ElasticSketch [1], MV-Sketch [2], and UnivMon [3]. It would also be useful to discuss or compare distributed or network-wide sketching systems such as Distributed Sketch [4], DUNE [5], and Eagle [6], which study collaborative measurement or network-wide sketch deployment from different perspectives.

W5. Some reported numbers would benefit from additional clarification. The beginning of Section 4 reports a 12.2×12.2\times–17.2×17.2\times improvement over Merged CMS, while the MAWI 2026 example in Section 4.2 reports a 4.83×4.83\times AAE improvement. Similarly, the reported throughput advantages are 1.8×1.8\times and 22×22\times in one place, but 1.7×1.7\times and 19×19\times later. These differences are somewhat confusing.

[1] Yang et al. Elastic Sketch: Adaptive and Fast NetworkWide Measurements. SIGCOMM 2018. [2] Tang et al. MV-Sketch: A Fast and Compact Invertible Sketch for Heavy Flow Detection in Network Data Streams. INFOCOM 2019. [3] Liu et al. One Sketch to Rule Them All: Rethinking Network Flow Monitoring with UnivMon. SIGCOMM 2016. [4] Gu, et al. Per-flow Network Measurement with Distributed Sketch. IEEE/ACM Transactions on Networking 2023 . [5] Wei et al. DUNE: Improving Accuracy for Sketch-INT Network Measurement Systems. INFOCOM 2023. [6] Chen et al. Eagle: Toward Scalable and Near-optimal Network-wide Sketch Deployment in Network Measurement. SIGCOMM 2024.

Questions for authors
  1. Please address the motivation concern in W1. It would be helpful to clarify which gains come from the two-level correction itself and which come from retaining node-level summaries.

  2. Please address the experimental-setting concerns in W2 and W3. More details on how the synthetic splitting strategies relate to realistic distributed traffic would be useful. Additional experiments on naturally distributed traces, or on workloads with more diverse skewness and data characteristics, would further strengthen the evidence for general applicability.

  3. Please address the baseline and related-work concern in W4. It would be helpful to explain how the evaluated sketches were selected and whether the conclusions are expected to extend to other network measurement sketches. Additional comparisons would better position the paper.

  4. Please address the reporting concern in W5 by clarifying the datasets, memory settings, and metrics associated with the different reported accuracy and throughput ratios.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.