FLASH: Fast Generative Retrieval via Autoregressive Semantic Hashing with Provably Distance Bounds

Abstract

Retrieval-Augmented Generation (RAG) relies critically on the effectiveness of its retrieval component. Dense retrieval with Approximate Nearest Neighbor (ANN) search is efficient but relies on symmetric similarity metrics that can limit the modeling of directional relevance. Generative retrieval addresses this limitation by ranking documents through conditional generation, but existing approaches assign documents unstructured identifiers that lack geometric grounding, leading to error codes and poorly controlled ranking behavior. We propose Flash (Fast Generative Retrieval via Autoregressive Semantic Hashing), a framework that integrates random orthogonal projection hashing (ROPH) with autoregressive hash code generation. Documents are encoded into D-bit binary codes that provide two key properties: (i) a structured Hamming space in which imperfectly generated codes can still retrieve semantically related candidates, and (ii) an unbiased inner-product estimator with O(1/√D) error, enabling binary codes to support accurate similarity estimation. We introduce a dual-head autoregressive decoder that jointly predicts hash tokens and a quantization scalar, allowing the estimator to be applied directly to generated candidates while modeling asymmetric relevance through conditional generation. At inference time, candidate scoring and index storage reduce to bitwise operations, substantially improving efficiency compared to dense retrieval.