Research map / Architectures and efficiency / RNNs and normalization
Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Lego sketch, a scalable memory-augmented neural sketch that uses normalized multi-hash embeddings, scalable memory bricks, memory scanning, and a self-guided weighting loss to improve space-accuracy trade-offs for frequency estimation over data streams.
Problem
Existing neural sketches (meta-sketches based on MANNs) require retraining when data domains or space budgets change, and their accuracy advantage over handcrafted sketches vanishes at large space budgets.
Approach
Replace domain-specific MLP/CNN embeddings with a normalized multi-hash embedding over a learnable vector, scale memory by stacking independent memory bricks routed by hashing, add a Deep Sets memory-scanning module that reconstructs global stream statistics (n, alpha), and train with a self-guided weighting loss that uses a rule-based min-estimate as guide.
Key results
- At 0.6 MB, Lego sketch ARE is 0.93, about 85% of meta-sketch's error and 21% and 26% of CMS and CS errors.
- At 3.6 MB, Lego sketch ARE is 0.074, about 21%, 46%, and 16% of meta-sketch, CMS, and CS errors respectively.
- Lego sketch store throughput is up to 6.90x and query throughput up to 12.47x that of meta-sketch on CPU (Wiki).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Lego sketch instead of MS | Lkml · Lkml, 0.6 MB | ARE: 85% of the error | Helped |
| Use Lego sketch instead of CMS | Lkml · Lkml, 0.6 MB | ARE: 21% of the errors | Helped |
| Use Lego sketch instead of CS | Lkml · Lkml, 0.6 MB | ARE: 26% of the errors | Helped |
| Use Lego sketch instead of MS | Lkml · Lkml, 3.6 MB | ARE: 21% of the errors | Helped |
| Use Lego sketch instead of CMS | Lkml · Lkml, 3.6 MB | ARE: 46% of the errors | Helped |
| Use Lego sketch instead of CS | Lkml · Lkml, 3.6 MB | ARE: 16% of the errors | Helped |
| Use Lego sketch instead of MS | Lkml · Lkml, 0.6 MB and 3.6 MB | AAE: 97% and 13% of that of MS | Helped |
| Add a learnable embedding vector instead of using a fixed vector (ablation) | Lego sketch · Two datasets, higher space budgets | estimation error | Helped |
| Add L1 normalization to the embedding (ablation) | Lego sketch · Two datasets, all space budgets | estimation error | Helped |
| Add the memory scanning module (ablation) | Lego sketch · Two datasets, small space budgets | estimation error | Helped |
| Use self-guided weighting loss instead of conventional loss L_o (ablation) | Lego sketch · Two datasets, larger space budgets | estimation error | Helped |
| Use Lego sketch instead of MS | Wiki, CPU Store · Wiki | throughput: 6.90 times higher | Helped |
Surprising findings
- Removing the normalization in the embedding consistently increases error across budgets, and the paper notes its error bound is looser than handcrafted sketches.
- Meta-sketch falls behind handcrafted sketches at larger budgets (e.g., 3.2 MB on Lkml).
Limitations
- Error bound is looser than those of handcrafted sketches due to dependence introduced by normalization.
- Interpretability of MANN limits error analysis.
- Aol dataset results were excluded due to anonymization concerns.
Experimental setup
Datasets: Aol Lkml Kosarak Wiki Webdocs
Benchmarks: Lkml Kosarak Wiki Webdocs synthetic Zipf streams
Metrics: AAE ARE throughput
Baselines: CM-sketch C-sketch Learned augmented C-sketch Meta-sketch D-CMS
Builds on: Meta-sketch Hash Embeddings Deep Sets Elastic sketch
Closest papers by meaning
- Meta-Sketch: A Neural Data Structure for Estimating Item Frequencies of Data Streams (AAAI 2023 · similarity 0.88)
- SketchINR: A First Look into Sketches as Implicit Neural Representations (CVPR 2024 · similarity 0.88)
- Sketch Down the FLOPs: Towards Efficient Networks for Human Sketch (CVPR 2025 · similarity 0.86)
- Efficient Sketches for Training Data Attribution and Studying the Loss Landscape (NeurIPS 2024 · similarity 0.85)
- It's All About Your Sketch: Democratising Sketch Control in Diffusion Models (CVPR 2024 · similarity 0.84)
- SketchDNN: Joint Continuous-Discrete Diffusion for CAD Sketch Generation (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.