Abstract
Deep learning has shown tremendous success on a variety of problems. However, unlike traditional computational paradigm, most neural networks do not have access to a memory, which might be hampering its ability to scale to large data structures such as graphs, lookup-tables, databases. We propose a neural architecture where sketch based memory is integrated into a neural network in a uniform manner at every layer. This architecture supplements a neural layer by information accessed from the memory before feeding it to the next layer, thereby significantly expanding the capacity of the network to solve larger problem instances. We show theoretically that problems involving key-value lookup that are traditionally stored in standard databases can now be solved using neural networks augmented by our memory architecture. We also show that our memory layer can be viewed as a kernel function. We show benefits on diverse problems such as long tail image classification, language model, large graph multi hop traversal, etc. arguing that they are all build upon the classical key-value lookup problem (or the variant where the keys may be fuzzy).
Introduction
Modern neural networks face a fundamental scaling bottleneck. While they excel at pattern recognition, they struggle with "memorization"—the ability to store and retrieve specific facts or handle massive, sparse data structures like knowledge graphs. In the standard paradigm, a network's memory is implicitly stored in its weights. To increase capacity, one must typically increase the number of parameters, which leads to a proportional surge in computational cost.
Researchers from Google Research address this in their paper, "Sketch based Memory for Neural Networks," by introducing SketchMem. This architecture equips neural networks with an external, scalable episodic memory, effectively giving them a "hard drive" that operates independently of the processing core.
Methodology: The SketchMem Module
SketchMem is a trainable external memory layer that can be integrated into any standard neural network layer. It utilizes Locality Sensitive Hashing (LSH) and sketching to manage information efficiently.
As detailed in the architecture above, the process follows four primary steps:
- Hashing (LSH): For an input activation vector $x$, the module uses $k$ independent LSH functions to map $x$ to specific buckets in a large memory table $Z$. LSH ensures that similar inputs are likely to map to the same buckets, enabling "fuzzy" retrieval.
- Retrieval: The module retrieves learnable vectors $z_{h_i(x)}$ from the identified buckets.
- Sketching: These vectors are combined into a single "sketch" vector $y$ using random subspace embedding matrices $R_i$. This compresses the retrieved information into a format compatible with the network's internal representations.
- Integration: The resulting sketch $y$ is added back to the original activation $x$ before proceeding to the next layer.
Crucially, the contents of the memory table are fully differentiable and updated via standard backpropagation, allowing the model to learn what specific metadata it needs to store to solve a given task.
Experimental Evaluation
The authors evaluated SketchMem across synthetic tasks, language modeling (PTB), long-tail image classification (ImageNet-LT), and NLP benchmarks (GLUE, SQuAD).
Key Results
- Scaling and Accuracy: As shown in the synthetic benchmarks, SketchMem maintains high accuracy and exact match rates even as the data size $N$ scales to $10^5$, whereas simple baselines collapse.
- NLP Performance: Adding SketchMem to a BERT-tiny model resulted in a massive jump in F1 score on SQuAD 1.1 from 12.99 to 42.31—a 225% improvement.
- Efficiency: A BERT-small model with SketchMem outperformed a standard BERT-medium on MNLI while requiring significantly fewer floating-point operations (FLOPs).
- Long-Tail Classification: On ImageNet-LT, SketchMem achieved 37.2% top-1 accuracy, outperforming specialized state-of-the-art models designed for rare-class distributions.
Key Insights
- Memory as a Kernel: Theoretically, a SketchMem layer approximates a kernel function that measures similarity between current inputs and historical data.
- Decoupling Capacity from Computation: SketchMem allows a model to increase its capacity (by expanding the memory table) without a corresponding increase in the number of FLOPs per forward pass.
- Fuzzy Lookups: Unlike traditional databases, SketchMem handles noisy or "fuzzy" keys, allowing the network to retrieve relevant information even when the input is not an exact match to previously seen data.
Conclusion and Future Work
SketchMem provides a theoretically grounded and empirically effective way to augment neural networks with external memory. While it excels as a persistent episodic memory, future work may explore its use as a "working memory" for short-term reasoning. Additionally, while the LSH-based approach is efficient, optimizing its implementation within dense-matrix-oriented deep learning frameworks remains an engineering priority.
Summary updated