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

arXiv: https://arxiv.org/abs/2506.12229 · HTML: https://mlsanity.com/paper/2506.12229/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 50 references that are in the map.
- First posted on arXiv 13 Jun 2025.

## Builds on (most cited first, 30 of 34)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering](https://mlsanity.com/paper/1809.02789/) (2018)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [AGIEval: A Human-Centric Benchmark for Evaluating Foundation Models](https://mlsanity.com/paper/2304.06364/) (2023)
- [Deduplicating Training Data Makes Language Models Better](https://mlsanity.com/paper/2107.06499/) (2021)
- [CoQA: A Conversational Question Answering Challenge](https://mlsanity.com/paper/1808.07042/) (2018)
- [Language Models are Multilingual Chain-of-Thought Reasoners](https://mlsanity.com/paper/2210.03057/) (2022)
- [Dolma: an Open Corpus of Three Trillion Tokens for Language Model Pretraining Research](https://mlsanity.com/paper/2402.00159/) (2024)
- [Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens](https://mlsanity.com/paper/2401.17377/) (2024)
- [What's In My Big Data?](https://mlsanity.com/paper/2310.20707/) (2023)
- [Autoregressive Search Engines: Generating Substrings as Document Identifiers](https://mlsanity.com/paper/2204.10628/) (2022)
- [AI as Humanity's Salieri: Quantifying Linguistic Creativity of Language Models via Systematic Attribution of Machine Text against Web Text](https://mlsanity.com/paper/2410.04265/) (2024)
- [ORCA: Interpreting Prompted Language Models via Locating Supporting Data Evidence in the Ocean of Pretraining Data](https://mlsanity.com/paper/2205.12600/) (2022)
- [OLMoTrace: Tracing Language Model Outputs Back to Trillions of Training Tokens](https://mlsanity.com/paper/2504.07096/) (2025)

## Built on by (most cited first, 14 of 14)

- [Speculative Speculative Decoding](https://mlsanity.com/paper/2603.03251/) (2026)
- [QuCo-RAG: Quantifying Uncertainty from the Pre-training Corpus for Dynamic Retrieval-Augmented Generation](https://mlsanity.com/paper/2512.19134/) (2025)
- [From Data to Behavior: Predicting Unintended Model Behaviors Before Training](https://mlsanity.com/paper/2602.04735/) (2026)
- [DatedGPT: Preventing Lookahead Bias in Large Language Models with Time-Aware Pretraining](https://mlsanity.com/paper/2603.11838/) (2026)
- [Death of the Novel(ty): Beyond n-Gram Novelty as a Metric for Textual Creativity](https://mlsanity.com/paper/2509.22641/) (2025)
- [BenchMarker: An Education-Inspired Toolkit for Highlighting Flaws in Multiple-Choice Benchmarks](https://mlsanity.com/paper/2602.06221/) (2026)
- [The Role of Mixed-Language Documents for Multilingual Large Language Model Pretraining](https://mlsanity.com/paper/2601.00364/) (2026)
- [Understanding the Interplay between LLMs' Utilisation of Parametric and Contextual Knowledge: A keynote at ECIR 2025](https://mlsanity.com/paper/2603.09654/) (2026)
- [Formula-One Prompting: A Composable Equation-First Prefix for Applied Mathematics](https://mlsanity.com/paper/2601.19302/) (2026)
- [SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora](https://mlsanity.com/paper/2602.10908/) (2026)
- [On the scaling relationship between cloze probabilities and language model next-token prediction](https://mlsanity.com/paper/2602.17848/) (2026)
- [Auditing Chinese Web-scale Corpora via Sampled BPE Token Statistics](https://mlsanity.com/paper/2608.10678/) (2026)
- [What to Forget in Unlearning? Forget Set Curation for Language Models](https://mlsanity.com/paper/2608.14855/) (2026)
- [Evaluating LLM Creativity through Long-Tail Performance](https://mlsanity.com/paper/2610.12998/) (2026)

## Abstract (arXiv)

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×) and memory use during both indexing (3.2× reduction) and querying (down to a negligible amount). We index 83TB of Internet text in 99 days with a single CPU node with 128 vCPUs (or 19 hours if using 137 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 74.2% in GSM8K), 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.