Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams
Yuan Feng, Yukun Cao, Hairu Wang, Xike Xie, S. Kevin Zhou · 2025
Read Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams by Yuan Feng, Yukun Cao, Hairu Wang, Xike Xie, S. Kevin Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-19561.txt.
Introduction
Yuan Feng and co-authors build a learning sketch for endless data streams in this 2025 paper. Sketches guess item counts in a stream while using tiny memory. Learned sketches beat hand-made ones on space, but past designs fit poorly across data types and space caps.
Their sketch stacks memory blocks like toy bricks, adding or shedding blocks as space allows. That flex lets one design serve many streams. The team proves the first error bound for a learned sketch of this kind. Wide tests show better space-accuracy trade-offs than both hand-made and learned rivals. Code is shared in public.
Catalog record
| CREATOR | Yuan Feng, Yukun Cao, Hairu Wang, Xike Xie, S. Kevin Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-19561
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams Yuan Feng, Yukun Cao, Hairu Wang, Xike Xie, S. Kevin Zhou Abstract Sketches, probabilistic structures for estimating item frequencies in infinite data streams with limited space, are widely used across various domains. Recent studies have shifted the focus from handcrafted sketches to neural sketches, leveraging memory-augmented neural networks (MANNs) to enhance the streaming compression capabilities and achieve better space-accuracy trade-offs. However, existing neural sketches struggle to scale across different data domains and space budgets due to inflexible MANN configurations. In this paper, we introduce a scalable MANN architecture that brings to life the Lego sketch , a novel sketch with superior scalability and accuracy. Much like assembling creations with modular Lego bricks, the Lego sketch dynamically coordinates multiple memory bricks to adapt to various space budgets and diverse data domains. Our theoretical analysis guarantees its high scalability and provides the first error bound for neural sketch. Furthermore, extensive experimental evaluations demonstrate that the Lego sketch exhibits superior space-accuracy trade-offs, outperforming existing handcrafted and neural sketches. Our code is available at https://github.com/FFY0/LegoSketch_ICML . † † affiliationnotice: Equal contribution 1 Introduction The estimation of item frequency in a continuous and never-ending data stream stands as a pivotal task in supporting a broad spectrum of applications in machine learning ( Goyal et al., 2012 ; Aghazadeh et al., 2018 ; Talukdar & Cohen, 2014 ) , network measurements ( Yu et al., 2013 ; Yang et al., 2018 ) , and big data analytics ( Cormode et al., 2012 ; Zaharia et al., 2016 ) . Sketches, a typical probabilistic structure, have become essential for representing data streams with sub-linear space and linear time while maintaining accurate item frequency estimates. Two major research direction in sketching techniques have emerged: handcrafted sketches ( Cormode & Muthukrishnan, 2005 ; Charikar et al., 2002 ; Estan & Varghese, 2002 ; Deng & Rafiei, 2007 ) and neural sketches ( Rae et al., 2019 ; Feng et al., 2024 ; Cao et al., 2023 ; Cao et al., 2024 ) . Derivatives ( 2018 ; 2016 ; 2018 ; 2019 ; 2024 ) , … Core Structure Handcrafted vs. Neural Sketches CM-sketch ( 2005 ) Meta-sketch ( 2023 ; 2024 ) C-sketch ( 2002 ) Lego sketch (2025) Figure 1: Sketch Literatures Figure 2: Space-accuracy Trade-off (Aol Dataset) Handcrafted sketches rely on core structures, such as the CM-sketch ( Cormode & Muthukrishnan, 2005 ) and C-sketch ( Charikar et al., 2002 ) , which are comprised of compact 2D arrays, hash functions, and predefined strategies. These handcrafted core structures have since formed the foundation for numerous variants or derivatives ( Estan & Varghese, 2002 ; Deng & Rafiei, 2007 ) , designed to better adapt to the skewed distributions in data streams 4 . In contrast to the decade-old core structures of handcrafted sketches, recent advancements in neural sketches ( Cao et al., 2023 ; Cao et al., 2024 ; Feng et al., 2024 ; Rae et al., 2019 ) have introduced memory-augmented neural networks (MANNs) as a new class of core structures. The MANN-based cores improve sketching performance by leveraging their capability of memory compression and adaptability to distributional patterns of data streams. Figure 2 provides an overview of the literatures on sketches. Despite recent advancements, existing neural sketches face practical challenges when deployed in real-world settings, particularly in scaling effectively to data streams across diverse domains and varying space budgets. A major scalability issue is that they require retraining when there is a shift in data domains or changes in space budgets. This requirement stems from their reliance on a sample MLP-based embedding module and a fixed-size memory module within the traditional MANN architecture. Also, as demonstrated in Figure 2 , the accuracy advantage of existing neural sketches, i.e., meta-sketches, in terms of estimation error over handcrafted sketches, tends to decrease as the space budget increases. Figure 3: Lego Sketch Overview: The Lego sketch enables a scalable and unified framework capable of adapting to different domains and space budgets, mirroring the modular design seen in dedicate creations built from multiple Lego bricks. In this paper, we propose a novel neural sketch, called the Lego sketch , designed to significantly enhance scalability and improve the space-accuracy trade-offs of existing neural sketches, thereby setting new benchmarks in performance 1 1 1 This paper focuses on the core structure of sketches. Derivatives of a core structure typically incorporates external enhancements, such as filters (discussed in Section 2 ). Section 3.3 explores derivatives of the Lego sketch, which use it as the core structure, providing a comprehensive analysis. As depicted in 3 , the Lego sketch is initially trained on a single memory brick to acquire basic sketching capabilities across data domains. When dealing with a large-scale data stream, it divides the stream into manageable sub-streams, each controlled by an independent memory brick. The Lego framework is achieved by devising a new MANN architecture from two aspects. For scalability , the Lego sketch overcomes the shortcomings of existing neural sketches under conventional MANN architecture, particularly when used across different data domains and space budgets. First, we propose a novel normalized multi-hash embedding technique to enable theoretically provable domain-agnostic scalability (Section 4.1 ), without necessitating retraining for different data domains. Second, with theoretical foundations (Section 4.2 ), our approach leverages a scalable memory strategy to coordinate multiple memory bricks, avoiding the need for retraining when adapting memory sizes to fit different space budgets. For accuracy , the Lego sketch not only addresses the issue of diminished advantage of existing neural sketches in high budgets but also offers enhancement in accuracy. Specifically, we propose a novel self-guided weighting loss (Section 3.2 ) for dynamically weighting different meta-tasks during self-supervised meta-learning, effectively addressing issues of diminished advantage. Moreover, a pioneering module termed memory scanning (Section 3.1 ), which autonomously reconstructs stream features from the compressed memory, along with other optimization techniques, significantly aids in the estimation, thereby achieving superior space-accuracy trade-offs, as shown in Figure 2 . Contributions. 1) We introduce the Lego sketch, a novel neural sketch equipped with a scalable MANN architecture designed for sketching data streams. 2) The Lego sketch resolves scalability limitations and achieves a superior space-accuracy trade-off through key technical innovations, including normalized multi-hash embedding , scalable memory , memory scanning , and self-guided weighting loss . 3) We also provide theoretical support for the scalability and estimation error analysis, areas previously unexplored in existing neural sketches. 4) Extensive empirical studies on both real-world and synthetic datasets confirm that the Lego sketch significantly outperforms state-of-the-art methods. 2 Related Works Sketch techniques fall into two categories: core sketches and their derivatives, as shown in Figure 2 . Core sketches ( Cormode & Muthukrishnan, 2005 ; Charikar et al., 2002 ; Estan & Varghese, 2002 ; Deng & Rafiei, 2007 ; Liu & Xie, 2021 ; Cao et al., 2023 ; Cao et al., 2024 ) , also referred to as core structures, provide the fundamental structure for stream processing, where ( Estan & Varghese, 2002 ; Deng & Rafiei, 2007 ) are variants of ( Cormode & Muthukrishnan, 2005 ; Charikar et al., 2002 ) under specific