The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizes

Information Retrieval using dense low-dimensional representations recently\nbecame popular and showed out-performance to traditional sparse-representations\nlike BM25. However, no previous work investigated how dense representations\nperform with large index sizes. We show theoretically and empirically that the\nperformance for dense representations decreases quicker than sparse\nrepresentations for increasing index sizes. In extreme cases, this can even\nlead to a tipping point where at a certain index size sparse representations\noutperform dense representations. We show that this behavior is tightly\nconnected to the number of dimensions of the representations: The lower the\ndimension, the higher the chance for false positives, i.e. returning irrelevant\ndocuments.\n