FlyHash for LLM Agent Memory: An Empirical Validation and a New Application

FlyHash for LLM Agent Memory. An Empirical Validation and a New Application. By Mohan Bheemadolu and one other, working independently. Published on the fourth of November.

Agents built on large language models increasingly keep information across conversations in external memory stores. The usual way to search such a store is with dense vector embeddings and approximate nearest-neighbor methods. The fruit fly's olfactory circuit does something quite different. It computes a locality-sensitive hash of its sensory input through sparse random projection followed by winner-take-all competition. Earlier work by Dasgupta and colleagues showed that this scheme, called FlyHash, preserves neighbor structure better per bit than conventional random-hyperplane hashing, known as SimHash, on several benchmarks.

The authors apply FlyHash to agent memory retrieval, to their knowledge for the first time. They frame the work around three questions a practitioner actually needs answered, and they report all three answers precisely, including the two that narrow the headline result rather than flatter it. The claim, stated plainly, is that the quality advantage is real and survives careful testing, but the practical advantage is narrower than quality alone would suggest.

The first question is whether the quality advantage holds under a correctly matched-bit protocol. It does, robustly, across ten seeds and four datasets spanning two modalities. Along the way the authors identify and correct one specific comparison pitfall that had not been documented before.

The second question is whether that advantage translates into real savings in memory and latency, including against HNSW, the dense-vector indexing that practitioners default to today. Here the answer is no. At equal bits, FlyHash's codes are larger than SimHash's and slower to compare. At ordinary scale, HNSW dominates both hash methods. The authors introduce a sparse-set comparison that recovers most of a naive latency gap, though not all of it.

The third question is whether the advantage survives genuine relevance labels for agent memory. The literature otherwise relies on a proxy, treating the nearest neighbor by embedding as the relevant item, which is circular. With non-circular labels in its place, the advantage does survive.

The positive results concern retrieval quality per bit: neighbor structure under matched bits, and relevance under genuine labels. They do not extend to efficiency. On memory and latency the comparison goes against FlyHash at equal bits, and HNSW leads both hashing methods at ordinary scale. The practical case for hashing that remains is described as narrower and more specific than the quality result implies on its own. The evaluation covers four datasets and two modalities, with ten seeds. Alongside the results, the authors release their implementation, a working demo of agent memory, and a full account of the methodological pitfalls they found and corrected.

Three questions, two of them answered in a way that cuts against the attractive story, and both of those reported with the same care as the one that supports it. A borrowed piece of biology does hold its edge on quality, even with honest labels. Whether that edge pays for itself is a separate matter, and on the evidence here, at ordinary scale and equal bits, it mostly does not.