Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index

• URL: http://arxiv.org/abs/2506.12229v2
• Date: Tue, 08 Jul 2025 00:58:37 GMT
• Title: Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index
• Authors: Hao Xu, Jiacheng Liu, Yejin Choi, Noah A. Smith, Hannaneh Hajishirzi,
• Abstract summary: We present Infini-gram mini, a scalable system that can make petabyte-level text corpora searchable.<n>We index 46TB of Internet text in 50 days with a single 128-core CPU node.<n>We show one important use case of Infini-gram mini in a large-scale analysis of benchmark contamination.
• Score: 124.68209298883296
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Language models are trained mainly on massive text data from the Internet, and it becomes increasingly important to understand this data source. Exact-match search engines enable searching in large text corpora -- counting string appearances and retrieving the enclosing documents -- yet the high storage overhead hinders their application on Internet-scale data. We present Infini-gram mini, an efficient and scalable system that can make petabyte-level text corpora searchable. Based on the FM-index data structure (Ferragina and Manzini, 2000), which simultaneously indexes and compresses text, our system creates indexes with size only 44% of the corpus. Infini-gram mini greatly improves upon the best existing implementation of FM-index in terms of indexing speed (18$\times$) and memory use during both indexing (3.2$\times$ reduction) and querying (down to a negligible amount). We index 46TB of Internet text in 50 days with a single 128-core CPU node (or 19 hours if using 75 such nodes). We show one important use case of Infini-gram mini in a large-scale analysis of benchmark contamination. We find several core LM evaluation benchmarks to be heavily contaminated in Internet crawls (up to 40% in SQuAD), which could lead to overestimating the capabilities of language models if trained on such data. We host a benchmark contamination bulletin to share the contamination rate of many core and community-contributed benchmarks. We also release a web interface and an API endpoint to serve general search queries on Infini-gram mini indexes.

Related papers

• The Curious Case of High-Dimensional Indexing as a File Structure: A Case Study of eCP-FS [0.8998543739618077]
  eCP-FS is a file-based implementation of eCP, a well-known disk-based ANN index.<n>This paper presents eCP-FS, a file-based implementation of eCP, a well-known disk-based ANN index.<n>In a memory-constrained scenario, eCP-FS offers a minimal memory footprint, making it ideal for resource-constrained or multi-index environments.
  arXiv  Detail & Related papers  (2025-07-29T15:51:44Z)
• LEANN: A Low-Storage Vector Index [70.13770593890655]
  LEANN is a storage-efficient approximate nearest neighbor search index optimized for resource-constrained personal devices.<n>Our evaluation shows that LEANN reduces index size to under 5% of the original raw data, achieving up to 50 times smaller storage than standard indexes.
  arXiv  Detail & Related papers  (2025-06-09T22:43:30Z)
• HAKES: Scalable Vector Database for Embedding Search Service [16.034584281180006]
  We build a vector database that achieves high throughput and high recall under concurrent read-write workloads.<n>Our index outperforms index baselines in the high recall region and under concurrent read-write workloads.<n>namesys is scalable and achieves up to $16times$ higher throughputs than the baselines.
  arXiv  Detail & Related papers  (2025-05-18T19:26:29Z)
• MIRACL-VISION: A Large, multilingual, visual document retrieval benchmark [1.8448587047759064]
  We introduce MIRACL-VISION, a multilingual visual document retrieval evaluation benchmark.<n> MIRACL-VISION covers 18 languages, and is an extension of the MIRACL dataset.<n>We observe a gap in state-of-the-art VLM-based embedding models on multilingual capabilities.
  arXiv  Detail & Related papers  (2025-05-16T19:22:19Z)
• InfiMM-WebMath-40B: Advancing Multimodal Pre-Training for Enhanced Mathematical Reasoning [58.7966588457529]
  InfiMM-WebMath-40B is a high-quality dataset of interleaved image-text documents. It comprises 24 million web pages, 85 million associated image URLs, and 40 billion text tokens, all meticulously extracted and filtered from CommonCrawl. Our evaluations on text-only benchmarks show that, despite utilizing only 40 billion tokens, our dataset significantly enhances the performance of our 1.3B model. Our models set a new state-of-the-art among open-source models on multi-modal math benchmarks such as MathVerse and We-Math.
  arXiv  Detail & Related papers  (2024-09-19T08:41:21Z)
• Semi-Parametric Retrieval via Binary Bag-of-Tokens Index [71.78109794895065]
  SemI-parametric Disentangled Retrieval (SiDR) is a bi-encoder retrieval framework that decouples retrieval index from neural parameters.<n>SiDR supports a non-parametric tokenization index for search, achieving BM25-like indexing complexity with significantly better effectiveness.
  arXiv  Detail & Related papers  (2024-05-03T08:34:13Z)
• What's In My Big Data? [67.04525616289949]
  We propose What's In My Big Data? (WIMBD), a platform and a set of sixteen analyses that allow us to reveal and compare the contents of large text corpora. WIMBD builds on two basic capabilities -- count and search -- at scale, which allows us to analyze more than 35 terabytes on a standard compute node. Our analysis uncovers several surprising and previously undocumented findings about these corpora, including the high prevalence of duplicate, synthetic, and low-quality content.
  arXiv  Detail & Related papers  (2023-10-31T17:59:38Z)
• LexLIP: Lexicon-Bottlenecked Language-Image Pre-Training for Large-Scale Image-Text Retrieval [71.01982683581572]
  The conventional dense retrieval paradigm relies on encoding images and texts into dense representations using dual-stream encoders. We propose the lexicon-weighting paradigm, where sparse representations in vocabulary space are learned for images and texts. We introduce a novel pre-training framework, that learns importance-aware lexicon representations. Our framework achieves a 5.5 221.3X faster retrieval speed and 13.2 48.8X less index storage memory.
  arXiv  Detail & Related papers  (2023-02-06T16:24:41Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.