Locality-Sensitive Hashing (LSH) is a fundamental tool in computer science used to find "nearest neighbors" in massive datasets by mapping similar inputs to similar binary codes. A few years ago, researchers introduced FlyLSH, an algorithm inspired by the fruit fly’s mushroom body—a brain region used for olfactory learning. FlyLSH is highly efficient because it uses sparse, binary connections to project data into a higher-dimensional space.
However, traditional FlyLSH relies on random connections. While mathematically convenient, biological evidence suggests that neural connections in the fly are not purely random; they develop over time and are influenced by experience. Existing methods to "train" these connections often require seeing the entire dataset multiple times or are computationally expensive.
In the NeurIPS 2022 paper "DevFly: Bio-inspired Development of Binary Connections for Locality Preserving Sparse Codes," researchers ask a compelling question: Can we "grow" these connections one by one based on data samples to create a better hash without losing the speed of the original fly-inspired model?
The Problem: Randomness in FlyLSH
Random connections might create "detectors" for combinations of features that never actually occur in the real world. By wiring based on actual samples, a network can ensure every coding neuron is a detector for a feature pattern that actually exists in the dataset.
To address the inefficiencies of random wiring, DevFly replaces the random connections in the FlyLSH algorithm with a bio-inspired developmental process that wires neurons based on the strongest features of experienced data.
The DevFly Solution: "Wire-and-Fix"
The authors propose moving away from static random matrices toward a developmental wiring process, introducing three specific methods:
- Method 1 (Random Samples): Instead of random wiring, the algorithm picks a random data sample, identifies its $n$ strongest dimensions (highest values), and wires a new coding neuron specifically to those dimensions.
- Method 2 (Unfamiliarity-based): A new neuron is only wired when the network encounters an "unfamiliar" sample—one that doesn't strongly activate any existing neurons. This ensures the network covers the input space efficiently.
- Method 3 (Noisy Unfamiliarity): Similar to Method 2, but it adds a layer of stochasticity (noise) to the wiring process to improve generalization, mimicking the inherent "messiness" of biological systems.
Crucially, once a connection is formed in DevFly, it is fixed. It never changes, which provides a stable signal for any "downstream" parts of a neural network that might be trying to learn from these codes. In deep learning, changing early-layer weights often forces later layers to "re-learn" everything. DevFly’s "wire-and-fix" approach allows the network to expand its representational capacity as it sees new data without disrupting what it has already learned.
Key Results and Performance
The researchers evaluated DevFly on four standard benchmarks: MNIST (handwritten digits), CIFAR-10 (color images), SIFT10M (image descriptors), and GloVe (word embeddings).
- Superior Accuracy: On the MNIST dataset, DevFly outperformed the standard FlyLSH across the board. For very sparse codes ($k=2$), it improved accuracy by a staggering 106%.
- Massive Speedup: Compared to "BioHash" (another data-dependent version of FlyLSH), DevFly reached peak performance in just 320 iterations, whereas BioHash required 10,000 iterations.
- Efficiency: Because DevFly produces sparse codes, query times are significantly faster than "dense" hashing methods because the system only needs to compare the small number of activated dimensions.
- Hardware Friendliness: Because the weights are binary and only update once (from 0 to 1), DevFly is exceptionally well-suited for low-power edge computing and specialized hardware like Write-Once-Read-Many (WORM) memory.
Limitations and Future Directions
A key insight from the paper is the realization that DevFly works best when the strongest signals in the data (highest intensity) are also the most informative signals.
This highlights the main limitation of the approach: dataset sensitivity. DevFly struggled to improve performance on CIFAR-10. The authors explain that in CIFAR-10, the brightest pixels (high intensity) are often just background (like the sky) and aren't the most useful features for distinguishing objects. In contrast, for MNIST digits, the brightest pixels are the digit.
To overcome this, future work could explore variance-based wiring, modifying the algorithm to wire connections based on dimensions with the highest variance or correlation rather than just the highest intensity. Additionally, the authors propose using DevFly for "state counting" in Reinforcement Learning (RL), where stable, locality-preserving hashes can help agents track which parts of an environment they have already explored.
Summary updated