FlyHash for LLM Agent Memory: An Empirical Validation and a New Application
Organizations: Independent Researcher.
Abstract
Large language model (LLM) agents increasingly rely on external memory stores to retain information across conversations, typically via dense vector embeddings searched with approximate nearest-neighbor methods. The fruit fly's olfactory circuit computes a locality-sensitive hash of sensory input using a strikingly different mechanism - sparse random projection followed by winner-take-all competition - and prior work (Dasgupta et al., 2017) showed this scheme, dubbed FlyHash, preserves neighbor structure better per bit than conventional random-hyperplane hashing (SimHash) on several benchmarks. We apply FlyHash, to our knowledge for the first time, to LLM agent memory retrieval, and ask three questions a practitioner actually needs answered: does the quality advantage hold under a correctly matched-bit protocol (it does, robustly, across 10 seeds and four datasets spanning two modalities, with one specific, previously undocumented comparison pitfall identified and corrected along the way); does that advantage translate into real memory and latency savings, including against the dense-vector indexing (HNSW) practitioners default to today (no: at equal bits FlyHash's codes are larger and slower to compare than SimHash's, and HNSW dominates both hash methods at ordinary scale; a sparse-set comparison we introduce recovers most but not all of a naive latency gap, leaving hashing's practical case narrower and more specific than the quality result alone implies); and does the advantage survive genuine, non-circular agent-memory relevance labels rather than the nearest-neighbor-by-embedding proxy this literature otherwise relies on (it does). We report all three answers precisely, including the two that narrow rather than flatter the headline result, and release our implementation, a working agent-memory demo, and a full account of the methodological pitfalls we found and corrected.
Figures & tables
| Dataset | Modality | Records | Dim. | Role |
|---|---|---|---|---|
| GloVe (glove-wiki-gigaword-100) [ 9 ] | Text (word vectors) | 5,000 | 100 | Primary dataset; discovery of the fair-comparison pitfall (Sec. 3.2 , App. A ); statistical (Sec. 3.4 ) and hyperparameter (Sec. 4.2 ) validation |
| MiniLM (all-MiniLM-L6-v2) [ 10 ] | Text (sentence embeddings) | 100 | 384 | Validates the exact embedding type used in the agent memory demonstration (Sec. 3.5 ) |
| scikit-learn digits [ 12 ] | Image | 1,797 | 64 (8 8) | Genuine, if small, image dataset used where full MNIST was not reachable during development |
| MNIST (via OpenML) [ 11 ] | Image | 5,000 (of 70,000) | 784 (28 28) | Full-scale image benchmark used in the original FlyHash paper |
| Dataset | (bits) | FlyHash | SimHash | Robust |
|---|---|---|---|---|
| GloVe, mAP@100 | 16 | 0.196 0.007 | 0.047 0.006 | Yes |
| 32 | 0.314 0.009 | 0.096 0.009 | Yes | |
| 64 | 0.449 0.008 | 0.185 0.008 | Yes | |
| 128 | 0.585 0.006 | 0.316 0.006 | Yes | |
| 256 | 0.705 0.006 | 0.469 0.007 | Yes | |
| MiniLM, mAP@20 | 16 | 0.310 0.013 | 0.214 0.026 | Yes |
| (bits) | Mean diff | 95% CI ( ) | 95% CI (bootstrap) | Cohen’s | Wilcoxon | Perm. |
|---|---|---|---|---|---|---|
| 16 | 0.1485 | [0.1421, 0.1549] | [0.1437, 0.1539] | 16.6 | 1.95e-03 | 2.30e-03 |
| 32 | 0.2179 | [0.2073, 0.2284] | [0.2095, 0.2267] | 14.8 | 1.95e-03 | 2.30e-03 |
| 64 | 0.2642 | [0.2550, 0.2734] | [0.2568, 0.2719] | 20.6 | 1.95e-03 | 2.30e-03 |
| 128 | 0.2691 | [0.2643, 0.2738] | [0.2654, 0.2732] | 40.8 | 1.95e-03 | 2.30e-03 |
| 256 | 0.2354 | [0.2284, 0.2424] | [0.2299, 0.2414] | 24.1 | 1.95e-03 | 2.30e-03 |
| (SimHash baseline: ) | ||||
| 0.05 | 0.169 0.009 | 0.169 0.003 | 0.178 0.006 | 0.186 0.002 |
| 0.10 | 0.200 0.001 | 0.199 0.006 | 0.193 0.010 | 0.189 0.008 |
| 0.20 | 0.198 0.003 | 0.205 0.003 | 0.200 0.005 | 0.204 0.001 |
| (SimHash baseline: ) | ||||
| (bits) | SimHash bytes/record | FlyHash (dense) ms/query | SimHash ms/query |
|---|---|---|---|
| 16 | 2 | 14.05 | 0.19 |
| 32 | 4 | 12.76 | 0.29 |
| 64 | 8 | 12.93 | 0.45 |
| 128 | 16 | 14.15 | 0.84 |
| 256 | 32 | 13.17 | 2.17 |
| (bits) | Sparse-idx | SimHash | Dense | Sparse | SimHash |
|---|---|---|---|---|---|
| bytes/rec | bytes/rec | ms/query | ms/query | ms/query | |
| 16 | 32 | 2 | 15.77 | 0.71 | 0.40 |
| 32 | 64 | 4 | 14.44 | 0.73 | 0.29 |
| 64 | 128 | 8 | 14.54 | 1.59 | 0.45 |
| 128 | 256 | 16 | 15.03 | 3.39 | 0.84 |
| 256 | 512 | 32 | 13.90 | 8.55 | 1.79 |
| Stage | ms/query | % of total |
|---|---|---|
| Sentence embedding (MiniLM) | 14.1 | 68.8% |
| FlyHash hash + sparse rank | 6.4 | 31.2% |
| Total end-to-end | 20.5 | 100% |
| efSearch | mAP@100 | ms/query | bytes/record |
|---|---|---|---|
| 16 | 0.7700 | 0.029 | 671.5 |
| 64 | 0.9862 | 0.060 | 671.5 |
| 128 | 0.9986 | 0.092 | 671.5 |
| (bits) | FlyHash mAP | FlyHash ms/q | FlyHash B/rec | SimHash mAP | SimHash ms/q |
|---|---|---|---|---|---|
| 16 | 0.198 | 0.66 | 32 | 0.048 | 0.19 |
| 32 | 0.312 | 1.04 | 64 | 0.095 | 0.22 |
| 64 | 0.440 | 1.62 | 128 | 0.185 | 0.26 |
| 128 | 0.582 | 4.46 | 256 | 0.325 | 0.50 |
| 256 | 0.697 | 10.13 | 512 | 0.476 | 0.70 |
| (bits) | FlyHash mAP (labeled) | SimHash mAP (labeled) | Robust |
|---|---|---|---|
| 16 | 0.195 0.014 | 0.038 0.010 | Yes |
| 32 | 0.271 0.017 | 0.105 0.011 | Yes |
| 64 | 0.324 0.012 | 0.212 0.016 | Yes |
| 128 | 0.365 0.009 | 0.298 0.011 | Yes |
| 256 | 0.392 0.009 | 0.345 0.011 | Yes |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| (bits) | Signed mAP | Binary mAP | diff | SimHash mAP (ref.) |
|---|---|---|---|---|
| 16 | 0.196 0.007 | 0.191 0.005 | 0.0042 | 0.047 0.006 |
| 32 | 0.314 0.009 | 0.298 0.007 | 0.0156 | 0.096 0.009 |
| 64 | 0.449 0.008 | 0.421 0.005 | 0.0277 | 0.185 0.008 |
| 128 | 0.585 0.006 | 0.540 0.005 | 0.0449 | 0.316 0.006 |
| 256 | 0.705 0.006 | 0.647 0.005 | 0.0577 | 0.469 0.007 |
LLM Agent Memory
Large language model agent memory lets agents retain, organize, retrieve, and update information across interactions and long-running tasks.
See all 399 papers