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

🎯 Pitch

A single 128-vCPU node can now index 83TB of Internet text and search for any exact string in constant time, using an FM-index that compresses the corpus to just 44% of its original size. The system reveals that up to 74.2% of GSM8K benchmark examples already appear verbatim in a recent Common Crawl dump — a contamination rate that renders current LM evaluations dangerously unreliable.

1. Executive Summary

This paper introduces INFINI-GRAM MINI, a scalable system for exact-match search over petabyte-scale text corpora using the FM-index data structure, which simultaneously indexes and compresses text to only 44% of the original corpus size. The system achieves an 18× speedup in indexing and a 3.2× reduction in peak RAM compared to the prior best FM-index implementation, indexing 83TB of Internet text in 99 days on a single 128-vCPU node—or 19 hours if embarrassingly parallelized across 137 such nodes. Applying the system to benchmark contamination analysis, the authors find that several core LM evaluation benchmarks are heavily contaminated in Internet crawls—up to 74.2% of GSM8K entries are dirty in a recent Common Crawl snapshot—establishing that benchmark contamination is a worsening evaluation crisis as new crawls increasingly contain exact matches of both questions and answers, inflating model capability estimates.

2. Context and Motivation

The Core Problem: We Cannot Search Petabyte-Scale Text Efficiently

The fundamental problem this paper addresses is deceptively simple: how do we make Internet-scale text corpora searchable for exact string matches? By "Internet-scale," the authors mean petabyte-level datasets — the raw material from which modern language models are trained. These corpora are enormous (Common Crawl alone is approximately 1PB of text), yet understanding their contents is increasingly critical for responsible LM development. Without the ability to search these corpora efficiently, researchers and practitioners are essentially flying blind — unable to audit training data for contamination, unable to trace model outputs back to their sources, and unable to curate datasets with precision.

The term "searchable" here has a specific technical meaning that goes beyond what a standard search engine like Google or ElasticSearch provides. The paper focuses on exact-match full-text search — the ability to take an arbitrary string (from a single character to thousands of characters long) and find every occurrence of that exact string across the entire corpus, along with the documents containing it. This is fundamentally different from keyword search (which matches individual tokens), fuzzy search (which allows mismatches), or semantic search (which matches meaning, not surface form). Exact-match search is essential for tasks like benchmark contamination detection, where a question appearing verbatim in training data must be identified with certainty, or for tracing whether a specific generated sequence was memorized from pretraining data.

The challenge is not that exact-match search is conceptually difficult — one could always scan the entire corpus linearly for each query. The challenge is that doing so is impractically slow at scale: with $n \approx 10^{15}$ bytes of text, a linear scan for every query would take $O(n)$ per query, which is completely infeasible for interactive use or large-scale analysis. The paper thus needs a data structure that can answer queries in time independent of the corpus size — the standard solution being some form of full-text index.

But building a full-text index introduces its own problem: storage overhead. Traditional index structures multiply the size of the data they index, sometimes dramatically. If an index is 6× or 29× the size of the original text, then indexing a petabyte corpus would require 6–29 petabytes of storage — placing it firmly outside the budget of academic research and even most industrial deployments. The core tension this paper addresses is therefore: how can we build an index that answers queries efficiently while keeping storage requirements manageable at Internet scale?

Why This Problem Matters Now

The paper identifies several converging trends that make this problem urgent:

Language models are trained on data we don't understand. The largest and most capable LMs are trained primarily on massive text corpora downloaded from the Internet — Common Crawl snapshots, curated subsets like DCLM-baseline, and compilations like the Pile. These datasets are so large that no human can read even a tiny fraction of them. Yet the contents of this training data profoundly shape model behavior: what the model knows, what biases it inherits, what copyrighted or sensitive material it memorizes, and crucially, whether it has been exposed to evaluation benchmarks during training.

Benchmark contamination is an accelerating evaluation crisis. The paper's contamination analysis reveals a disturbing trend: benchmarks that were clean when created progressively become contaminated in newer Internet crawls. For example, GSM8K shows a dirty rate of approximately 0% on the Pile (knowledge cutoff 2020) and only 5% on early Common Crawl snapshots from early 2025, but jumps to 74.2% on a snapshot from late May 2025 (CC-2025-21). This is not because GSM8K was suddenly added to the Internet — rather, it is because the benchmark has become so widely used that its questions and answers appear in blog posts, derivative datasets hosted on platforms like Hugging Face, academic papers, and other online sources that eventually get crawled. The result is that an LM trained on recent data may "know" GSM8K answers from memorization rather than mathematical reasoning ability, artificially inflating its evaluation scores without any genuine improvement in capability.

Without tools to detect this contamination systematically, the entire evaluation framework for language models becomes unreliable. Every new model release reports accuracy on benchmarks like MMLU, ARC, and GSM8K, but those numbers are increasingly meaningless if we cannot verify which examples were seen during training.

The scale problem is worsening. The paper points out that prior contamination analyses are limited to smaller corpora (up to 12TB for open corpora like RedPajama-1T and Dolma), while actual LM training datasets are substantially larger and growing. The trend toward larger and more frequently updated training corpora means that contamination can occur faster than our ability to detect it using existing tools.

Exact-match search has broader applications beyond contamination. Beyond the crisis-driven motivation, the paper notes that exact-match search enables task-specific dataset construction (finding documents containing specific phenomena), pretraining data curation (identifying and removing duplicates, low-quality text, or sensitive content), and model attribution (tracing generated outputs back to training sources). These use cases all share the same requirement: efficiently finding exact string matches in massive text corpora.

Where Prior Approaches Fall Short

The paper surveys three prior approaches to exact-match search at scale, each with a fundamental limitation that makes them impractical for petabyte-level corpora:

Suffix Automata: Extreme Storage Overhead

Merrill et al. (2024) use a suffix automaton (specifically a DAWG — Directed Acyclic Word Graph) to index 1.3TB of text for evaluating n-gram novelty of language model outputs. A suffix automaton is a finite-state automaton that accepts all substrings of the indexed text, enabling $O(|Q|)$ query time (where $|Q|$ is the query length). However, the storage multiplier is 29× — meaning the index is 29 times larger than the original text. At this ratio, indexing the 83TB of text that INFINI-GRAM MINI handles would require approximately 2.4 petabytes of storage, which is economically prohibitive and would require sophisticated distributed storage systems. The method is elegant for small-to-medium corpora but does not scale.

Suffix Arrays: Moderate Storage Overhead with Practical Limits

Liu et al. (2024) (the original infini-gram system) use a suffix array to index 12TB of text for training trillion-token n-gram language models. A suffix array is an array of integers representing the starting positions of all suffixes of the text in lexicographic order. Querying involves binary search over this sorted suffix range, achieving $O(|Q| \log n)$ query time. The storage cost for a suffix array is approximately 6× the text size (the authors mention 5n bytes for corpora with length up to one trillion characters, where each suffix array entry requires $\log_2 n$ bits). While 6× is dramatically better than 29×, it still makes petabyte-scale indexing impractical: a 1PB corpus would require approximately 6PB of storage for the index alone. The authors of the current work explicitly acknowledge this as the motivation for seeking a more compact representation.

Proprietary Search Engines: Opaque and Still Large

Elazar et al. (2024) use ElasticSearch, a proprietary full-text search engine, to index and analyze 35TB of text. ElasticSearch builds an inverted index that maps terms (typically words or n-grams) to document locations, which is fundamentally different from the arbitrary-string matching that suffix-based structures provide. The storage multiplier is reported as approximately 2×. While 2× is substantially better than 6× or 29×, three problems remain:

Cost at scale: 2× of a petabyte is still 2PB of storage, which is expensive and requires distributed cluster management.
Proprietary dependency: ElasticSearch is not open-source infrastructure that can be freely modified, studied, or replicated by the research community. The paper positions open-source accessibility as important for reproducible research.
Limited functionality for exact-match search: Inverted indexes are designed for token-based search rather than arbitrary substring matching. While they can be configured for exact string matching, they are not purpose-built for the specific use case of finding exact occurrences of arbitrary-length strings (e.g., a 50-character substring extracted from a benchmark example). This mismatch in design goals may lead to performance issues or workaround complexity that the paper does not detail but that motivated the search for a more principled solution.

The Missing Approach: Compressed Full-Text Indexes

Notably absent from the prior work surveyed is the use of compressed full-text indexes — data structures that simultaneously build the index and compress the underlying text. The FM-index, which INFINI-GRAM MINI is built on, is the canonical example: it can represent the suffix array and the original text in space proportional to the entropy of the text rather than its raw size. For natural language text with its highly non-uniform character distribution, this means the index can be smaller than the original text (the paper reports a theoretical minimum of 0.26×, and a practical configuration of 0.44×).

Why hasn't this been done before at scale? The paper identifies two reasons:

1. FM-index is primarily used in bioinformatics, not NLP. The FM-index is a standard tool for indexing DNA sequences and genomes, where the alphabet size is small ( $\sigma = 4$ for DNA) and compression is critical because genomic datasets are enormous. The bioinformatics community has developed highly optimized implementations, but these are specialized for genomic data and not directly applicable to natural language text (different alphabet sizes, different compression characteristics, different query patterns). The NLP community, by contrast, has largely relied on suffix arrays or proprietary search engines without adopting compressed index structures from bioinformatics.

2. Existing FM-index implementations are not performant enough for Internet-scale text. The standard library for succinct data structures, SDSL (Gog et al., 2014), includes an FM-index implementation. However, the paper demonstrates that this implementation is far too slow and memory-intensive for petabyte-scale indexing. Specifically, the authors benchmark SDSL indexing an 8.7GB corpus: it takes 5,847 seconds and requires 74,807 MB of peak RAM. At this rate, indexing 83TB would take approximately 1.7 years on a single machine and require more RAM than any reasonable server configuration provides. The implementation is largely single-threaded and was designed for much smaller datasets. INFINI-GRAM MINI's primary engineering contribution is making FM-index construction fast and memory-efficient enough to be practical at Internet scale.

How This Paper Positions Itself

INFINI-GRAM MINI is positioned as bridging the gap between compressed index theory and Internet-scale practice. The paper's contribution is not a new data structure — the FM-index has existed since Ferragina and Manzini (2000) — but rather the first system that makes it feasible to build and query FM-indexes for petabyte-scale natural language corpora. This positioning has three dimensions:

Engineering contribution: making FM-index viable for big text. By parallelizing every step of index construction (suffix array building, wavelet tree construction, suffix array sampling, inverse suffix array creation) and optimizing the query engine to work with on-disk indexes using minimal RAM, the paper transforms FM-index from a theoretically elegant but practically limited data structure into a deployable system. The 18× speedup and 3.2× RAM reduction over SDSL is not an incremental improvement — it is the difference between practically impossible and practically achievable for datasets of this scale.

Scale contribution: indexing more text than any prior open-source system. The paper's claim of "the largest body of text ever in the open-source community" is specific and verifiable: 83TB of text, comprising two curated pretraining datasets (the Pile and DCLM-baseline) and seven Common Crawl snapshots spanning January to July 2025. For comparison, prior open-source systems top out at 35TB (Elazar et al., 2024 using ElasticSearch) and 12TB (Liu et al., 2024 using suffix arrays). The paper goes further by estimating that indexing the full 1PB Common Crawl would require 1,200 node-days, or 19 hours if parallelized across 1,500 nodes — establishing a clear path to petabyte-scale in the near term.

Application contribution: demonstrating impact through contamination analysis. The paper does not just build infrastructure; it uses it to produce actionable findings. The benchmark contamination analysis is the largest-scale such study conducted on open corpora, covering 24 benchmarks across three major corpora. The finding that GSM8K went from essentially clean to 74.2% dirty in a matter of months (within the 2025 Common Crawl snapshots) is a specific and alarming result that would have been much more expensive or impossible to obtain with prior methods. The paper positions INFINI-GRAM MINI as not just a tool but a monitoring infrastructure — a system that can continuously track contamination as new crawls are released, enabling the community to make informed decisions about which benchmarks remain valid for evaluation.

A philosophical position: open and accessible infrastructure. The paper explicitly releases source code, hosts a web interface, provides an API endpoint, and maintains a public contamination bulletin. This reflects a position that tools for understanding training data should be community resources, not proprietary assets. The contrast with ElasticSearch (used by Elazar et al., 2024 but not freely modifiable) is implicit but clear: building on open data structures ensures that the system can be studied, improved, and deployed by anyone without licensing constraints.

In summary, the paper's motivating insight is that the NLP community has been using the wrong tools for exact-match search at scale — suffix arrays and automata are too large, proprietary engines are too opaque and expensive — and that compressed indexes from bioinformatics, properly re-engineered for natural language and parallelized for modern hardware, can solve the problem with an order-of-magnitude improvement in storage efficiency. The subsequent sections of the paper validate this insight through careful engineering and large-scale empirical demonstration.

3. Technical Approach

3.1 Reader Orientation

What INFINI-GRAM MINI is: a system that builds a compressed, searchable index of raw text corpora at scales up to petabytes, then answers two types of queries — "how many times does this exact string appear?" and "show me the documents containing this string" — in seconds regardless of corpus size.

What problem it solves and the shape of the solution: the core tension is that exact-match search over Internet-scale text requires an index, but traditional indexes are prohibitively large (2–29× the corpus size). INFINI-GRAM MINI resolves this by adapting the FM-index data structure from bioinformatics — which simultaneously indexes and compresses text using the Burrows-Wheeler Transform and wavelet trees — and re-engineering it for natural language at scale. The result is an index only 44% the size of the original corpus, built 18× faster and with 3.2× less RAM than previous implementations, queryable with negligible memory by keeping the index on disk.

3.2 Big-Picture Architecture (Diagram in Words)

The system has five major components, organized into an offline indexing pipeline and an online query engine:

Text Preprocessor — takes a collection of documents (from corpora like the Pile, DCLM-baseline, or Common Crawl), encodes each document as UTF-8 bytes, concatenates them with \xff delimiter bytes marking document boundaries, and produces a single giant byte string along with a text offset file mapping each document to its starting byte position. This turns a multi-document corpus into the single-string input the FM-index requires.
FM-Index Builder — the core indexing engine with five parallelized stages: (a) suffix array and BWT construction using the parallel implementation from Liu et al. (2024), (b) alphabet ordering, (c) Huffman-shaped wavelet tree construction using the parallel implementation from Labeit et al. (2017), (d) suffix array sampling (storing every a = 32-th entry), and (e) inverse suffix array sampling (storing every b = 64-th entry). These stages compress the text so effectively that the original text string does not need to be stored — it can be reconstructed on-the-fly from the compressed representation.
Shard Manager — for corpora too large to index in one piece (constrained by the ~2TB RAM available per node), the preprocessed byte string is split into shards of up to 700GB. Each shard is indexed independently, producing a self-contained FM-index. Querying across shards produces identical results to querying a single unified index, enabling embarrassingly parallel construction across multiple nodes.
On-Disk Query Engine — at query time, all index files remain on disk as memory-mapped files, consuming only ~30MB of RAM regardless of corpus size. This design choice trades latency for memory efficiency: queries require random disk reads (since the BWT shuffles the text and the wavelet tree scatters access patterns), so query speed is bounded by disk I/O throughput rather than CPU or RAM.
Query Interface (Web UI + API) — exposes two operations to users: counting (returns the number of occurrences of a query string, parallelized across all shards) and document retrieval (locates each occurrence position, maps it to the enclosing document via the text offset file, reconstructs the document text character-by-character from the compressed index, and returns results).

Information flow for indexing: corpus documents → UTF-8 encoding → concatenation with delimiters → shard splitting → per-shard FM-index construction (SA+BWT → alphabet → wavelet tree → SA sampling → ISA sampling) → on-disk index files + text offset file.

Information flow for counting query: query string → shard-level find operation (backward search through BWT wavelet tree) → sum of occurrence counts across shards → result returned to user.

Information flow for document retrieval: query string → shard-level find operation → suffix array range of occurrence positions → per-position locate (maps to byte offset in original text) → binary search in text offset file for enclosing document boundaries → per-document reconstruct (walks backward through BWT to recover document text) → returned to user.

3.3 Roadmap for the Deep Dive

First, the FM-index data structure itself (§2 of the paper, covered here as foundational context): because the entire system is built around this data structure, I will explain how suffix arrays, the Burrows-Wheeler Transform, Huffman-shaped wavelet trees, and LF-mapping combine to enable compressed full-text search — this is essential background without which the engineering design decisions make no sense.
Second, the index construction pipeline (§3.1 of the paper): how INFINI-GRAM MINI parallelizes each FM-index building step to achieve 18× speedup and 3.2× RAM reduction over SDSL, including the critical design choices around alphabet size, document boundary encoding, and sampling rates.
Third, the sharding strategy and scaling analysis: how the system partitions massive corpora into independently indexable shards, what constrains shard size (RAM limits), and what the indexing times and costs look like for the actual 83TB indexed — with the extrapolation to full 1PB Common Crawl.
Fourth, the query engine and its performance characteristics (§3.2): how counting and document retrieval work at query time, why the system trades latency for memory efficiency by keeping indexes on disk, the time complexity analysis, and actual benchmarked latencies for different query lengths and retrieval sizes.
Fifth, the web interface and API deployment (§3.3): briefly, how users access the system, since this is part of the technical contribution (making Internet-scale search available to the community, not just building it).

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily an engineering systems paper whose core idea is that the FM-index data structure — properly parallelized and optimized for natural language — can achieve order-of-magnitude improvements in storage efficiency for exact-match search at Internet scale, and that this efficiency enables practical applications (like large-scale contamination detection) that were previously infeasible.

The FM-Index Data Structure: Foundational Context

Before diving into INFINI-GRAM MINI's engineering, I must explain the FM-index itself, since every design decision in the system follows from properties of this data structure. The FM-index (Ferragina and Manzini, 2000) combines three ideas: the suffix array (for locating pattern occurrences), the Burrows-Wheeler Transform (for compressing the text while preserving searchability), and wavelet trees (for compressing the BWT further while supporting fast rank queries). The result is a full-text index that is smaller than the original text for natural language while still supporting exact-match search in time independent of corpus size.

Suffix Array (SA). Given a string $T$ of length $n$ (terminated with a special symbol $ that is lexicographically smaller than all other characters), the suffix array $SA$ is an array of $n$ integers where $SA[i] = j$ means that the suffix $T[j \ldots n]$ is the $i$ -th smallest suffix in lexicographic order. All occurrences of any query pattern $Q$ in $T$ correspond to suffixes that start with $Q$ , and because $SA$ is sorted, these occurrences form a contiguous range $[l, r]$ in $SA$ . Finding this range enables counting occurrences ( $r - l + 1$ ) and locating them in $T$ (each $SA[i]$ for $i \in [l, r]$ gives a starting position).

The problem with storing $SA$ directly is size. Each entry is an integer in $[0, n-1]$ , requiring $\lceil \log_2 n \rceil$ bits. For $n$ up to one trillion (approximately $10^{12}$ ), this is 40 bits per entry, or 5 bytes per byte of text — a 5× storage multiplier. For a 1PB corpus, the suffix array alone would be approximately 5PB. This is the bottleneck that FM-index addresses: it avoids storing most SA entries, instead recovering them on-the-fly through the BWT.

Burrows-Wheeler Transform (BWT). The BWT (Burrows et al., 1994) is a reversible permutation of $T$ defined as:

$L[i] = \begin{cases} T[SA[i] - 1] & \text{if } SA[i] > 0 \\ \$ & \text{otherwise} \end{cases}$

where $L$ is the BWT string of length $n$ , $SA[i]$ is the $i$ -th suffix array entry, and $T[j]$ is the $j$ -th character of the original string.

What it computes: for each position $i$ in the sorted suffix order, $L[i]$ is the character that immediately precedes the suffix starting at $SA[i]$ in the original text. In other words, if you sort all suffixes of $T$ and write down the text character that comes right before each suffix, you get the BWT. Figure 2 in the paper illustrates this for the toy string "banana$": the suffixes sorted lexicographically are $, a$, ana$, anana$, banana$, na$, nana$, and the BWT $L$ is annb$aa (the characters preceding each suffix in order).

Why this form: two crucial properties make the BWT the foundation of compressed indexing:

The BWT clusters repeated characters. Characters that appear in similar contexts (preceding similar suffixes) tend to cluster together in $L$ , making it highly compressible. For natural language text with its skewed character distribution, the zeroth-order entropy $H_0$ of $L$ is approximately $0.26 \log_2 \sigma$ bits per character (where $\sigma = 256$ is the alphabet size), which is substantially less than the $\log_2 256 = 8$ bits per character needed for uncompressed UTF-8. Empirically, the paper reports $H_0 \approx 2.1$ for their corpora.
The Last-to-First (LF) mapping enables traversing $T$ backward without storing $T$ . The LF mapping takes a position $i$ in $L$ and returns the position $LF(i)$ in $L$ corresponding to the same character in the first column $F$ (where $F[i] = T[SA[i]]$ is the first character of each suffix, which is just $L$ sorted). Formally:

$LF(i) = C[L[i]] + \text{rank}(L[i], i)$

where:

$c$ is a character (one of 256 possible byte values),
$C[c]$ is the number of characters in $L$ lexicographically smaller than $c$ (a precomputed cumulative count),
$\text{rank}(c, i)$ counts how many times character $c$ appears in $L[0 \ldots i]$ (the prefix of $L$ up to position $i$ ).

What the LF mapping computes: given a position $i$ in $L$ representing some character that precedes suffix $T[SA[i] \ldots n]$ , $LF(i)$ gives the position in $L$ of that same character as it appears in $F$ , which corresponds to the suffix starting one character earlier in $T$ . By applying LF repeatedly, you can walk backward through $T$ one character at a time starting from any position, reconstructing the original text from the compressed BWT. This is why FM-index does not need to store $T$ — it can be reconstructed on-the-fly using LF mapping.

Why this matters: LF mapping is the computational engine behind all three FM-index operations (find, locate, reconstruct). Find uses it for backward search (starting from the end of the query and narrowing the SA range). Locate uses it to walk from an unsampled SA entry to the nearest sampled one. Reconstruct uses it to walk backward through $T$ recovering characters. The correctness and performance of the entire system depends on efficient rank queries over $L$ , which is where wavelet trees enter.

Huffman-Shaped Wavelet Tree. Storing $L$ as a raw string would require $n \log_2 256 = 8n$ bits — no compression at all. The wavelet tree (Mäkinen and Navarro, 2005) compresses $L$ by hierarchically partitioning the alphabet and storing bitvectors at each internal node. A Huffman-shaped wavelet tree optimizes this by grouping symbols based on their frequencies in $L$ .

The tree is a binary tree with $\sigma = 256$ leaf nodes, one per possible byte value. Leaf depths are determined by Huffman coding: more frequent characters (like spaces and lowercase letters) are closer to the root, less frequent characters (like special symbols or high byte values) are deeper. At each non-leaf node, a bitvector marks whether each position in $L$ belongs to the left subtree (0) or right subtree (1). The total storage for the Huffman-shaped wavelet tree is:

$n H_0 + 2 \sigma \log n \text{ bits}$

where $n H_0$ is the entropy of $L$ (approximately $0.26 n \log_2 256 = 2.08n$ bits for natural language), and $2 \sigma \log n = 2 \times 256 \times \log_2 n$ bits is the overhead for storing the tree structure (about 10,240 bits for $n = 10^{12}$ — negligible compared to $n H_0$ ).

What it computes: the wavelet tree supports two operations essential for LF mapping:

$\text{rank}(c, \ell)$ : count occurrences of character $c$ in $L[0 \ldots \ell-1]$ . Traverses the tree from root to leaf $c$ , at each step using the bitvector to count how many positions in the current range go to the relevant child. Time complexity: $O(H_0)$ — proportional to the entropy, not the alphabet size — because the tree depth is roughly $H_0$ bits.
$\text{select}(c, m)$ : find the position of the $m$ -th occurrence of $c$ in $L$ . Walks from leaf $c$ back to root, using the bitvector's select operation at each step. Time complexity: also $O(H_0)$ .

Why this form: the Huffman-shaped wavelet tree provides the optimal space-time tradeoff for this application. A balanced wavelet tree would have depth $\log_2 \sigma = 8$ , which is fine for a 256-character alphabet but would require $n \log_2 \sigma = 8n$ bits of storage — no compression. A fully compressed wavelet tree using RRR bitvectors could achieve near-entropy storage but would slow down rank/select operations. The Huffman shape achieves entropy-level compression ( $n H_0$ bits) while keeping rank/select at $O(H_0)$ time, which is fast because $H_0 \approx 2.1$ for natural text — a tree of average depth only about 2.1 bits. This means each rank or select operation requires only 2–3 bitvector queries on average, making the FM-index operations fast despite the compression.

Sampled Suffix Array. Storing the full $SA$ would defeat the compression goal, so FM-index stores only every $a$ -th entry of $SA$ , where $a$ is a configurable sampling rate. For unsampled positions, the locate operation recovers the SA value by applying LF mapping repeatedly (at most $a$ times) until reaching a sampled entry, then working backward. This creates a space-time tradeoff: higher $a$ means smaller index but slower locate (more LF steps per query). The paper chooses $a = 32$ empirically to balance storage and latency.

Sampled Inverse Suffix Array (ISA). $ISA$ is the inverse permutation of $SA$ : $ISA[j] = i$ if $SA[i] = j$ . It maps a position in the original text to its rank in the suffix array, which is needed for reconstruct (to find where to start the backward walk from). FM-index samples $ISA$ at a different rate $b$ , storing only every $b$ -th entry. The paper chooses $b = 64$ , twice as coarse as $SA$ sampling, because $ISA$ is used less frequently (only for reconstruct, not for locate).

Index size formula. The total FM-index size is approximately:

$\frac{n}{a} \lceil \log_2 n \rceil + \frac{n}{b} \lceil \log_2 n \rceil + n H_0 + 2 \sigma \log n \text{ bits}$

The first term is the sampled $SA$ (every $a$ -th entry, each requiring $\lceil \log_2 n \rceil$ bits). The second term is the sampled $ISA$ . The third and fourth terms are the wavelet tree. For the paper's configuration ( $a = 32$ , $b = 64$ , $n \approx 10^{12}$ — though actual corpora range from 1.3GB to 65TB), the sampled SA and ISA together contribute about $0.18n$ bytes (using 40-bit $\lceil \log_2 n \rceil$ ), and the wavelet tree contributes about $0.26n$ bytes (since $H_0 \approx 2.1$ bits per byte). The total is approximately $0.44n$ bytes — the $0.44\times$ storage multiplier reported in Table 1. If $a$ and $b$ were set to infinity (no SA or ISA sampling, relying entirely on LF mapping for recovery), the index would theoretically approach $0.26\times$ the corpus size — the entropy of the BWT — but query latency would become prohibitive.

The Three FM-Index Operations: Find, Locate, Reconstruct

Everything INFINI-GRAM MINI does at query time is built from three primitive operations on the FM-index. Understanding these operations in detail is essential because the query latency benchmarks (Table 4) are direct consequences of their time complexities.

Find (Backward Search). Given a query string $Q$ , find the SA range $[l, r]$ containing all suffixes that start with $Q$ .

The algorithm works backward through $Q$ , starting from the last character and moving to the first. Initially, the range is the entire SA: $[l, r] = [0, n-1]$ . For each character $c$ in $Q$ , processed from $|Q|-1$ down to $0$ , the range is updated:

$l_{\text{new}} = C[c] + \text{rank}(c, l_{\text{old}} - 1)$ $r_{\text{new}} = C[c] + \text{rank}(c, r_{\text{old}}) - 1$

where $C[c]$ is the cumulative count of characters in $L$ smaller than $c$ , and the rank operation is supported by the wavelet tree.

What it computes: each backward step narrows the SA range to suffixes that match one more character of the query. After processing all $|Q|$ characters of $Q$ , the range $[l, r]$ contains exactly the suffixes starting with $Q$ . The count of occurrences is $r - l + 1$ .

Time complexity: $O(|Q| H_0)$ , where $|Q|$ is the query length and $H_0$ is the time per rank operation (the average wavelet tree depth). This is independent of $n$ — the corpus size does not affect how long find takes, which is the key property that makes FM-index scalable. For the paper's corpora with $H_0 \approx 2.1$ , each step of backward search requires about 2.1 rank operations on average.

Locate. Given a position $i$ in the SA (i.e., the rank of a suffix), find the byte offset $SA[i]$ of that suffix in the original text $T$ .

If $i$ is a sampled SA entry (i.e., $i \bmod a = 0$ ), return the stored value directly. Otherwise, apply LF mapping repeatedly: start with position $i$ , apply $LF(i)$ to move to position $i_1$ , apply $LF(i_1)$ to move to $i_2$ , and so on, counting steps until reaching a position $i_k$ that is sampled. Then $SA[i] = SA[i_k] + k$ — the sampled value plus the number of backward steps taken.

Time complexity: $O(a H_0)$ worst case, since at most $a$ LF steps are needed before hitting a sampled entry, and each LF step costs $O(H_0)$ for the rank query. With $a = 32$ , each locate requires up to approximately 67 wavelet tree rank queries (32 LF steps × 2.1 average rank operations per step). This makes locate the most expensive operation per occurrence, which is why document retrieval latency grows with the number of occurrences retrieved (each occurrence needs its own locate).

Reconstruct. Given a starting byte offset $p$ in $T$ and a desired length $d$ , recover the substring $T[p \ldots p+d-1]$ .

First, use the sampled ISA to find the SA rank corresponding to position $p+d-1$ (the end of the desired substring). Since ISA is sampled at rate $b = 64$ , finding the exact SA rank may require up to $b$ LF steps, similar to how locate handles unsampled SA entries. Once the SA rank for the end position is known, apply LF mapping $d$ times, recovering one character at each step: start from the SA rank for the end position, extract $L[i]$ (the character at that position in the BWT), apply LF to move to the previous character's position, repeat $d$ times. The recovered characters, in reverse order, spell out $T[p \ldots p+d-1]$ .

Time complexity: $O((b + d) H_0)$ , where $b H_0$ accounts for locating the starting SA rank (potentially walking up to $b = 64$ LF steps from a sampled ISA entry), and $d H_0$ accounts for the $d$ reconstruction steps. For a document of length $d = 3000$ bytes, this is approximately $(64 + 3000) \times 2.1 \approx 6434$ wavelet tree operations — hence the latency of 1.8–4.5 seconds reported in Table 4.

Why these three operations compose as they do: the FM-index is fundamentally a backward-traversal data structure — it can efficiently move from any position to the position one character earlier, but not forward. This is a consequence of the BWT, which stores the character preceding each suffix, not following it. To find pattern occurrences, find starts at the end of the pattern and works backward because that matches the natural direction of LF traversal. To retrieve document text, reconstruct starts at the end of the desired substring and walks backward to the beginning, then reverses the recovered characters. The asymmetry between forward and backward access is the price paid for compression — a suffix array can jump forward in constant time (just follow the SA link), but an FM-index must walk backward through the BWT, one LF step per character.

Index Construction Pipeline: From Text Corpus to FM-Index

INFINI-GRAM MINI's index construction takes raw text documents and produces an FM-index through five stages, each of which the authors parallelized to achieve the 18× speedup over SDSL. I'll trace through each stage, explaining what it does, why the parallelization matters, and what the performance numbers are.

Preprocessing: UTF-8 encoding and document concatenation. The FM-index is designed to operate on a single string, but text corpora are collections of documents. The paper's solution is conceptually simple: encode every document as UTF-8 bytes, then concatenate all documents using the byte \xff as a delimiter. This byte is chosen specifically because it is not used in valid UTF-8 encoding (UTF-8 uses bytes in the range 0x00–0x7F for single-byte characters, and bytes 0xC0–0xFF only appear as leading or continuation bytes in multi-byte sequences; 0xFF never appears in any valid UTF-8 encoding). This choice avoids ambiguity — \xff unambiguously marks a document boundary rather than being part of any document's content. The paper notes that working with raw UTF-8 bytes rather than character-level indexing keeps the alphabet size fixed at $\sigma = 256$ (one per byte value), which bounds the wavelet tree's branching structure and avoids the unbounded alphabet size that character-level indexing would produce for Unicode text.

Alongside this giant concatenated byte string, the system stores a text offset file: an array mapping each document ID to its starting byte position in the concatenated string. This file is used at query time to map a byte offset (returned by locate) to the enclosing document (found by binary search in the offset file) and to retrieve document metadata corresponding to that position.

Why UTF-8 bytes rather than tokens: the original infini-gram system (Liu et al., 2024) tokenized the text before indexing, which reduces the string length (since one token covers multiple characters) but requires committing to a specific tokenizer and prevents searching for arbitrary byte sequences. Since the FM-index already compresses the text to below the original size, tokenization would provide no additional storage benefit while reducing flexibility — a user could not search for a substring that spans token boundaries or uses characters that the tokenizer handles differently. The raw byte approach also eliminates tokenization as a preprocessing step, simplifying the pipeline.

Partitioning into shards. Before indexing, large corpora are split into shards. The shard size is constrained by the available RAM on the indexing node: the paper uses nodes with 128 vCPUs and 2TB RAM, and under this constraint, each shard can be up to approximately 700GB of raw text. For the 17TB DCLM-baseline corpus, this means 25 shards; for the 65TB of Common Crawl across seven snapshots, this means 137 shards total (Table 1). Each shard is indexed completely independently, producing a self-contained FM-index. At query time, the counting operation sums results across shards, and the document retrieval operation searches each shard independently and merges results. This sharding is lossless with respect to search semantics: because each document is entirely contained within a single shard (documents are not split across shard boundaries), searching across all shards produces exactly the same results as searching a single unified index.

The crucial engineering advantage of sharding is embarrassing parallelism: all 137 shards of the Common Crawl could be indexed simultaneously on 137 separate nodes, reducing the total wall-clock time from 99 days (sequential on one node) to 19 hours (parallel). For the full Common Crawl at ~1PB, the paper estimates 1,500 shards requiring 1,200 node-days total, or 19 hours if parallelized across 1,500 nodes.

Stage 1: Suffix array and BWT construction. This is the most computationally intensive step and the one that scales super-linearly with text size due to the complexity of sorting suffixes. The paper adapts the parallel implementation from Liu et al. (2024), which itself builds on the divsufsort algorithm — a state-of-the-art suffix array construction algorithm. The output is the full (unsampled) suffix array and the BWT string $L$ .

The time for this stage dominates the total indexing cost. Table 3 shows that for a 654GB shard of CC-2025-05, SA+BWT construction takes 55,692 seconds (15.5 hours) out of 67,923 seconds (18.9 hours) total — about 82% of indexing time. For DCLM-baseline shards of similar size (~667GB), this stage takes 29,543 seconds (8.2 hours) out of 43,586 seconds (12.1 hours) — about 68%. The difference arises because the Pile contains over 60% duplicate documents (noted in Appendix B), and duplicate suffixes cause the suffix sorting algorithm to take longer. This super-linear scaling with respect to duplication is a known property of suffix array construction (Lee et al., 2022).

The RAM usage is substantial because the SA and BWT are both $O(n)$ structures: the unsampled SA requires $n \lceil \log_2 n \rceil$ bytes (about $5n$ for trillion-character corpora), and the BWT requires $n$ bytes (one byte per character). For a 700GB shard, this means the SA alone uses approximately 3.5TB if stored naively — which is why the sampling step (Stage 4) is essential before the index can be used for querying. During construction, the full SA exists only transiently in RAM or on disk, and only the sampled portion is retained in the final index.

Stage 2: Alphabet construction. This stage builds the cumulative count array $C$ used in the LF mapping. $C[c]$ stores the total number of characters in $L$ that are lexicographically smaller than $c$ . For $\sigma = 256$ , this array has 256 entries, each containing an integer up to $n$ — trivial in size ( $256 \times \lceil \log_2 n \rceil$ bits, or about 1,280 bytes for trillion-character corpora). Table 3 shows this stage takes 2,500–2,900 seconds for 650–700GB shards — about 3–5% of total indexing time. The time is linear in $n$ because building $C$ requires a single pass over $L$ to count character frequencies, followed by computing cumulative sums.

Stage 3: Huffman-shaped wavelet tree construction. This stage takes the BWT $L$ produced in Stage 1 and builds the wavelet tree representation that compresses it and supports rank/select queries. The paper uses the parallel implementation from Labeit et al. (2017) rather than SDSL's single-threaded construction.

Construction proceeds in two phases: first, character frequencies in $L$ are computed to build the Huffman tree (determining the depth of each of the 256 leaf nodes based on character frequency). Second, the bitvectors at each internal node are built by scanning $L$ and, for each position, determining whether the character at that position belongs to the left or right subtree, then appending a 0 or 1 to the corresponding bitvector. This second phase is parallelizable because the bitvectors for different nodes at the same depth are independent — the paper's parallel implementation divides $L$ into chunks and processes them concurrently.

Table 3 shows wavelet tree construction takes 5,325 seconds (1.5 hours) for a 654GB CC-2025-05 shard and 6,257 seconds (1.7 hours) for a 667GB DCLM-baseline shard — about 8–14% of total indexing time. The wavelet tree's final size is approximately $n H_0$ bits — for the 654GB CC-2025-05 shard with $H_0 \approx 2.1$ , this is about $654 \times 0.26 \approx 170$ GB.

Stage 4: Suffix array sampling. From the full SA built in Stage 1, this stage retains only every 32nd entry ( $a = 32$ ). The paper parallelized SDSL's single-threaded sampling: each thread processes a disjoint range of SA indices, writing sampled entries to a file and discarding unsampled ones. The sampled SA size is $\frac{n}{32} \times \lceil \log_2 n \rceil$ bits — for the 654GB CC-2025-05 shard, this is about $654 \text{ GB} / 32 \times 5 \text{ bytes} \approx 102$ GB (using 5 bytes per entry for trillion-character indexing). Table 3 shows sampling takes 2,013 seconds for CC-2025-05 and 2,232 seconds for DCLM-baseline — about 3–5% of total time.

The choice of $a = 32$ is empirical, not derived from first principles. The paper notes that higher $a$ would reduce the sampled SA size (e.g., $a = 64$ would halve it to ~51GB) but increase locate latency proportionally (each unsampled position would require up to 64 LF steps instead of 32). Lower $a$ would reduce latency but increase storage. The authors do not report the experiments that led to $a = 32$ , but the value is standard in FM-index implementations (commonly $a = 32$ or $a = 64$ in bioinformatics).

Stage 5: Inverse suffix array sampling. From the full ISA (which would be another $n \lceil \log_2 n \rceil$ bytes if stored completely), this stage retains only every 64th entry ( $b = 64$ ). The paper parallelized this from SDSL's single-threaded version similarly to Stage 4. The sampled ISA size is $\frac{n}{64} \times \lceil \log_2 n \rceil$ bits — about half the size of the sampled SA (since $b = 64$ vs. $a = 32$ ). Table 3 shows ISA sampling takes 2,313 seconds for CC-2025-05 and 2,659 seconds for DCLM-baseline — comparable to SA sampling.

The choice of $b = 64$ (twice as coarse as $a$ ) reflects that ISA is used less frequently: only during reconstruct to find the starting SA rank, whereas SA is used for every locate operation. Making $b$ larger reduces storage without affecting counting or locating latency.

Total index size after all stages. The final on-disk FM-index for each shard consists of the wavelet tree (approximately $0.26n$ bytes), the sampled SA (approximately $0.16n$ bytes), the sampled ISA (approximately $0.08n$ bytes), and the alphabet array $C$ (negligible). The sum is approximately $0.50n$ bytes. The paper reports $0.44n$ (Table 1) — the discrepancy likely arises because the wavelet tree's actual entropy $H_0$ is slightly lower than 2.1 bits for some corpora, or because the bitvectors in the wavelet tree are further compressed beyond the raw $n H_0$ estimate.

For the 83TB total indexed, the final index occupies 36.884TB (Table 1, "Index Size" column) — a $0.44\times$ multiplier. This is the central efficiency claim: where a suffix array would require approximately 415TB (5× multiplier) and a suffix automaton would require approximately 2,407TB (29× multiplier), INFINI-GRAM MINI requires only 37TB.

Comparison with SDSL. The paper benchmarks SDSL indexing an 8.7GB corpus (a single file from DCLM-baseline) as a direct comparison point. SDSL required 5,847 seconds and 74,807MB peak RAM. INFINI-GRAM MINI on the same corpus required 324 seconds (18× faster) and 23,742MB peak RAM (3.2× less). The speedup comes primarily from parallelizing the four stages that SDSL runs single-threaded (wavelet tree construction, SA construction, SA sampling, ISA sampling). The RAM reduction comes primarily from more efficient memory management during construction — the paper does not detail exactly how, but the likely explanation is that SDSL keeps multiple intermediate representations in memory simultaneously, while INFINI-GRAM MINI's pipeline design frees memory from earlier stages before starting later ones.

Indexing the metadata. In addition to indexing the actual document text, the paper also indexes document metadata (URLs, crawl timestamps, etc.) using a similar compressed approach. The metadata is stored separately from the main text index, and the text offset file maps each document to both its text position and its metadata entry. This enables users to, for example, search for strings that appear in URLs rather than document bodies, or to retrieve metadata alongside document text. The metadata indexing time and size are excluded from the numbers in Table 1, which reports "only include actual document content and do not include metadata."

Sharding Strategy and Scaling Analysis

The sharding strategy is central to INFINI-GRAM MINI's scalability claims, so I'll detail exactly how it works and what the costs look like.

Why sharding is necessary. The FM-index construction requires the full suffix array to exist in memory at some point during construction (even if only transiently before sampling). For a suffix array with 5-byte entries, a 1PB corpus would require approximately 5PB of RAM just for the SA — far beyond any single machine. Sharding decomposes the problem: each shard's suffix array fits within the ~2TB RAM available on the nodes used.

How shard boundaries are determined. The paper does not describe an automated sharding algorithm — shard sizes are manually chosen to balance the 2TB RAM constraint with the desire to minimize the number of shards (fewer shards means faster queries, since each shard requires a separate find operation). The largest shards reported are approximately 700GB. Extrapolating: a 700GB shard requires approximately 700GB for the BWT ( $1 \times n$ ), plus 3,500GB for the unsampled SA ( $5 \times n$ ), plus overhead — totaling roughly 4,200GB, well within the 2TB RAM if temporary SA data is stored on disk and swapped in chunks, or if the construction algorithm uses external-memory techniques. The paper does not detail the memory management during construction, but the fact that 700GB shards are possible on 2TB nodes suggests the SA is not entirely in RAM simultaneously — likely constructed in chunks or using disk-backed data structures.

Sharding preserves search semantics. Documents are never split across shard boundaries — each document is fully contained within exactly one shard. This means that a query string appearing in a document will be found entirely within that document's shard, with no cross-shard partial matches. The find operation on each shard returns the number of occurrences within that shard, and the total count is the sum across shards. The locate operation on each shard returns byte offsets within that shard, and the text offset file for that shard maps those offsets to documents. There is no need for global coordination across shards beyond summing counts and merging document lists.

Indexing times for the 83TB indexed. Table 1 reports the indexing time for each corpus or CC snapshot, measured in CPU node-days (where one node-day is 24 hours of computation on a 128-vCPU, 2TB RAM node). The Pile (1.3TB) took 1.31 node-days; DCLM-baseline (16.7TB) took 12.6 node-days; and the seven CC snapshots totaled 65TB and 82.8 node-days. The total for all 83TB is 98.8 node-days — approximately 99 days on a single node, or 19 hours if parallelized across 137 nodes (one per shard). Note that the parallelization is essentially perfect: because shards are independent, indexing can proceed simultaneously on all shards with no communication overhead.

The indexing time per terabyte is not constant. The Pile required about 1.0 node-days per TB (1.31 / 1.3), DCLM-baseline about 0.76 node-days per TB (12.6 / 16.7), and CC-2025-05 about 1.30 node-days per TB (11.8 / 9.1). The variation arises from differences in text properties: the Pile has high duplication (slowing SA construction), DCLM-baseline is a high-quality subset with less duplication (faster SA construction), and the Common Crawl snapshots are unfiltered with moderate duplication. The paper's Table 3 confirms that SA+BWT construction time varies significantly with duplication rates across shards.

Extrapolation to full Common Crawl (~1PB). With shards of approximately 650–700GB, a 1PB corpus would require roughly 1,500 shards. Each shard takes approximately 0.8 node-days to index (using the DCLM-baseline rate of 0.76 node-days per TB, or approximately 19 hours per shard). The total sequential time is $1500 \times 0.8 \approx 1200$ node-days — about 3.3 years on a single node. Parallelized across 1,500 nodes, the wall-clock time would be approximately 19 hours. The cost, at typical cloud pricing for 128-vCPU, 2TB RAM instances (~ $3–5/hour), would be approximately$ 85,000–142,500 — not cheap, but within reach of well-funded research labs. The storage for the resulting index would be approximately 440TB (at the $0.44\times$ multiplier).

Query Engine: Counting and Document Retrieval

With the index built, the query engine must answer two types of user requests efficiently while using minimal RAM. The paper's design philosophy is to keep all index data on disk (as memory-mapped files) and accept second-level latency rather than loading the index into RAM for millisecond-level responses. This is a deliberate tradeoff explained by the target use case: if a user is doing interactive contamination analysis or exploratory search on an 83TB corpus, waiting 1–5 seconds per query is acceptable; requiring 37TB of RAM (the index size for 83TB of text) would be completely impractical.

On-disk index with memory-mapped I/O. At query startup, INFINI-GRAM MINI memory-maps all index files (wavelet tree, sampled SA, sampled ISA, alphabet array, text offset file) without loading them into RAM. The operating system's virtual memory system handles paging: when the query engine accesses a byte in a memory-mapped file, the OS loads the containing page from disk into the page cache. Frequently accessed pages (like the alphabet array or the upper levels of the wavelet tree) stay cached in RAM; rarely accessed pages (like deep wavelet tree nodes or infrequently accessed SA entries) are read from disk on demand. Loading all indexes for all shards uses only approximately 30MB of RAM (for file descriptors, page table entries, and small metadata structures), regardless of corpus size — a dramatic reduction from the 2TB needed during indexing.

The cost of this design is latency: every access to a part of the index not currently in the page cache triggers a disk read. Since the BWT shuffles text randomly and the wavelet tree scatters accesses across different bitvectors, query patterns tend to be random-access rather than sequential, meaning disk throughput (MB/s) matters less than IOPS (input/output operations per second). The paper benchmarks on Google Cloud Platform SSD disks with 80,000 IOPS and 1,200 MB/s throughput — high-performance SSDs that can sustain many random reads per second.

Counting queries: implementation and latency. To count occurrences of a query string $Q$ :

For each shard (2 shards for Pile, 25 for DCLM-baseline, 15–17 per CC snapshot), run the find operation: backward search through the wavelet tree, starting from the full SA range and narrowing it by one character of $Q$ at a time (processing $Q$ from last character to first).
For each shard, the find operation requires approximately $|Q| H_0$ rank queries on the wavelet tree. Each rank query traverses from the root to a leaf (or intermediate node), requiring $O(H_0)$ bitvector operations and potentially triggering disk reads for wavelet tree nodes not in cache.
Sum the SA range sizes across all shards to get the total count.

The number of random disk reads per counting query is $O(S |Q| H_0)$ , where $S$ is the number of shards and $|Q| H_0$ is the wavelet tree depth traversed per query character. For $S = 25$ (DCLM-baseline), $|Q| = 10$ , and $H_0 \approx 2.1$ , this is approximately 525 random reads — well within the 80,000 IOPS capacity of the benchmark disk.

Table 4 reports actual latencies. For counting a 10-character query: 0.106 seconds on Pile (2 shards), 0.402 seconds on DCLM-baseline (25 shards), and 0.350 seconds on CC-2025-05 (15 shards). The latency scales proportionally with the number of shards and query length, as predicted by the $O(S |Q| H_0)$ complexity. For a 1000-character query on DCLM-baseline, latency is 25.47 seconds — long but usable for batch analysis, and linear in $|Q|$ (10× longer query, ~63× longer latency, which is close to the expected $1000/10 \times 25/2 \approx 125\times$ ratio adjusting for shard count differences with Pile).

Document retrieval queries: implementation and latency. To retrieve documents containing a query string $Q$ :

Run find to get the SA range for each shard, exactly as in counting.
For each position in the SA range (i.e., each occurrence of $Q$ ), run locate to find the byte offset in the original text $T$ .
For each byte offset, binary-search the text offset file to find the enclosing document's boundaries (start and end byte offsets).
Group occurrences by document, deduplicating (multiple occurrences of $Q$ within the same document produce only one retrieved document, though the paper does not explicitly state this deduplication — it is implied by "retrieving documents that contain the query string").
For each unique document, run reconstruct to recover the document text of the desired length $d$ (users can specify how much context to retrieve, from a small snippet to the full document).

The latency is dominated by the locate and reconstruct operations, both of which require multiple LF steps with random disk accesses. For each occurrence located, locate takes up to $a H_0$ rank queries ( $32 \times 2.1 \approx 67$ ). For each document reconstructed, reconstruct takes $(b + d) H_0$ rank queries, where $b = 64$ is the ISA sampling rate and $d$ is the reconstruction length. The total number of random disk reads per document retrieval query is $O(M a H_0 + D (b + d) H_0)$ , where $M$ is the total number of occurrences found and $D$ is the number of unique documents containing them.

Table 4 reports document retrieval latencies. For a 10-byte query and retrieving 100 bytes of context: 0.734 seconds on Pile, 1.991 seconds on DCLM-baseline, 1.326 seconds on CC-2025-05. For 3000 bytes of context: 1.858 seconds on Pile, 4.456 seconds on DCLM-baseline, 3.330 seconds on CC-2025-05. The latency increases sub-linearly with $d$ because the $b H_0$ overhead for ISA lookup is amortized over the reconstruction length — going from 100 to 3000 bytes (30×) increases latency by about 2.5×, not 30×, because the $b = 64$ LF steps for ISA are a fixed cost per document regardless of reconstruction length.

The paper notes that reconstruct is parallelized internally: document text reconstruction is divided into $t = 10$ chunks (or chunks of length 100 if $d < 1000$ ), and these chunks are processed in parallel across $t$ threads. This intra-document parallelism reduces wall-clock latency but not total disk I/O — all threads compete for the same disk bandwidth and IOPS capacity.

Comparison with prior systems on latency. Table 5 reports a direct comparison with the original infini-gram system (Liu et al., 2024) on the Pile-train corpus. For a 10-byte query, infini-gram retrieves in 13ms; INFINI-GRAM MINI takes 106ms — about 8× slower. For a 100-byte query, infini-gram takes 13ms; INFINI-GRAM MINI takes 696ms — about 54× slower. This is the tradeoff for the 11× storage reduction (5× for suffix array vs. 0.45× for FM-index): millisecond latency on in-RAM suffix arrays versus second-level latency on on-disk FM-indexes. The paper is transparent about this tradeoff, listing it as a limitation in the Limitations section, but argues that for the intended use cases (contamination analysis, batch processing, exploratory search), second-level latency is acceptable.

Query limitations. The paper acknowledges that certain query types are inefficient with FM-index. Specifically, "identifying co-occurrences of multiple patterns" — for example, finding documents where both string A and string B appear near each other — is impractical because it requires mapping every occurrence position back to the original text offset (via locate), which is expensive ( $O(a H_0)$ per occurrence), and then checking co-occurrence constraints. The original infini-gram system (based on suffix arrays) supports this efficiently because occurrence positions are directly available from the suffix array without decompression. This is a fundamental limitation of compressed indexes: operations that require frequent random access to the original text order (as opposed to the BWT order) become expensive because the compression deliberately scrambles text order to achieve clustering.

Design Choices and Their Justifications

Several design decisions in INFINI-GRAM MINI represent deliberate tradeoffs that the paper justifies, either explicitly or implicitly through the empirical results:

Why raw UTF-8 bytes rather than characters or tokens. The alphabet size $\sigma$ directly affects wavelet tree complexity. With UTF-8 bytes, $\sigma = 256$ is fixed and small. With Unicode characters, the alphabet would have hundreds of thousands of symbols, making the wavelet tree impractically wide at the root and losing the compression benefits of the Huffman shape. With tokens, the alphabet size would depend on the tokenizer vocabulary (typically 32K–256K tokens) and the index would be tied to a specific tokenizer, preventing searches for arbitrary byte sequences that might appear between token boundaries. Raw bytes provide flexibility and bounded alphabet size at no compression cost (since the FM-index compresses away the byte-level redundancy anyway).

Why sampling rates $a = 32$ and $b = 64$ . The paper states these were chosen "empirically to balance storage savings and query latency" without reporting the experiments. The rationale can be inferred: SA sampling at $a = 32$ means each locate takes at most 32 LF steps × $H_0 \approx 67$ wavelet tree operations, which on an SSD with 80,000 IOPS takes roughly $67 / 80000 \approx 0.8$ milliseconds of disk time per occurrence. This is fast enough that retrieving even hundreds of occurrences can be done in a few seconds. ISA sampling at $b = 64$ reflects that ISA is used only for reconstruct, and $b$ LF steps are paid once per document regardless of reconstruction length, so making it coarser than $a$ saves storage with minimal latency impact.

Why the index remains on disk rather than in RAM. For the 83TB corpus, the index occupies 37TB (Table 1). A machine with 37TB of RAM exists only in specialized high-memory configurations costing hundreds of thousands of dollars. The paper's design targets commodity infrastructure: nodes with 128 vCPUs and 2TB RAM, with high-IOPS SSD storage, are available as standard cloud instances. Loading only memory-mapped file descriptors (~30MB) means the query engine runs on essentially any machine with sufficient disk space, democraticizing access to Internet-scale search.

Why \xff as the document delimiter. The paper notes that \xff is "not used by UTF-8" — this is a factual claim about the UTF-8 encoding standard. UTF-8 encodes Unicode code points using 1–4 bytes, with specific bit patterns: single-byte characters have the form 0xxxxxxx (0x00–0x7F), and multi-byte sequences use leading bytes 110xxxxx (0xC0–0xDF), 1110xxxx (0xE0–0xEF), or 11110xxx (0xF0–0xF7) followed by continuation bytes 10xxxxxx (0x80–0xBF). The byte 0xFF (11111111) never appears in any position of any valid UTF-8 sequence, making it an unambiguous delimiter that cannot be confused with document content. This is a careful, standards-grounded choice that avoids the complexity of escape sequences or length-prefixed formats.

Why the Huffman shape for the wavelet tree over a balanced tree. A balanced wavelet tree for $\sigma = 256$ would have depth exactly 8, requiring $\log_2 256 = 8$ bitvectors, each of length $n$ , for total storage $8n$ bits — the same as storing $L$ uncompressed. The Huffman shape reduces depth for frequent characters (spaces, 'e', 't', etc. might be at depth 2–3) while allowing rare characters to be deeper, so the average traversal depth — and thus the storage — is $H_0 \approx 2.1$ bits. For natural text, this is a $8/2.1 \approx 3.8\times$ compression improvement over a balanced tree. The tradeoff is that rank/select for rare characters take more steps (deeper tree), but since rare characters are accessed proportionally to their frequency, the expected cost is still $O(H_0)$ .

Web Interface and API Deployment

For completeness, I'll briefly cover the deployment architecture, since it is part of the technical contribution.

Web interface (Figure 5 in the paper). A Hugging Face-hosted web application provides two input fields corresponding to the two query types: a "Count" tab where users enter a query string and see the occurrence count across all indexed corpora, and a "Retrieve" tab where users enter a query string and specify context length, receiving matching document text snippets. The interface abstracts away shard selection — users search the entire 83TB corpus without specifying which shards or corpora to query.

API endpoint. Available at api.infini-gram-mini.io, the API accepts programmatic HTTP requests with the same parameters as the web interface, returning JSON responses. This enables integration with automated pipelines (e.g., batch contamination checking for new benchmarks, or systematic analysis of training data properties). The paper does not detail rate limiting, authentication, or concurrent request handling — likely these are standard Hugging Face deployment features.

Contamination monitoring system (Appendix J, Figure 13). Built on top of the query engine, this system tracks contamination rates for benchmarks across new Common Crawl snapshots as they are indexed. The interface shows two tables: "core" benchmarks (the 24 analyzed in the paper) and "community" benchmarks (submitted by users). Each row shows a benchmark, its test set size, and contamination dirty rates across the indexed corpora (similar to Table 2 in the paper). The system also provides a submission page where users can upload new benchmarks to be analyzed — the paper notes this is processed offline (indexing new CC crawls takes days, and running contamination analysis involves thousands of queries).

4. Key Insights and Innovations

Innovation 1: The Storage Ratio as the Fundamental Bottleneck — and How Entropy-Based Compression Breaks Through It

The paper's deepest conceptual contribution is not the engineering of parallelized FM-index construction, but the recognition that storage multiplier is the binding constraint on Internet-scale search, and that entropy-based compression can reduce this multiplier below 1.0 — making the index smaller than the original text.

What the Field Assumed Before This Work

Prior systems for exact-match search on large text corpora accepted, implicitly or explicitly, that the index would be larger than the data it indexes. This was treated as an unavoidable cost of enabling fast queries. The suffix array approach (Liu et al., 2024) achieves a 6× multiplier — each byte of text requires roughly 6 bytes of index. The suffix automaton approach (Merrill et al., 2024) requires 29×. Even ElasticSearch (Elazar et al., 2024), which uses inverted indexes rather than full-text suffix structures, requires approximately 2×. The scaling logic was straightforward but dispiriting: if you want to search $X$ terabytes of text, you need $cX$ terabytes of storage, where $c \geq 2$ . For petabyte-scale corpora, $c = 2$ means 2PB of storage — still a serious infrastructure investment, and $c = 6$ or $c = 29$ means the project is simply infeasible for academic budgets.

This assumption — that $c > 1$ is a law of nature — shaped what problems researchers attempted. Merrill et al. (2024) indexed 1.3TB; Liu et al. (2024) indexed 12TB; Elazar et al. (2024) indexed 35TB. Each pushed the boundary, but none broke through the fundamental $c > 1$ barrier. The field implicitly treated 1.3TB → 12TB → 35TB as a scaling trajectory that would eventually reach Internet scale with enough engineering and money. The paper's insight, made vivid by the 0.44× multiplier, is that this trajectory was approaching the problem from the wrong direction: rather than making $cX$ cheaper, make $c$ smaller.

What Makes This a Fundamental Shift

The $0.44\times$ multiplier is not a marginal improvement over $2\times$ or $6\times$ — it is a qualitative change in the economics of indexing. At $c = 0.44$ , the index for a 1PB corpus requires ~440TB of storage, which is within the range of a single rack of high-density storage servers — roughly the same order of magnitude as storing the corpus itself. At $c = 6$ , the same corpus requires 6PB, which is a small data center. At $c = 29$ , it is a large data center. The difference is not just cost; it is whether the project can be done at all within the resource constraints of academic research or small industrial labs.

The paper makes this shift vivid by noting that if the sampling rates $a$ and $b$ were pushed to infinity (storing no suffix array or inverse suffix array entries at all, relying entirely on LF-mapping for position recovery), the index would approach $0.26\times$ the corpus size — the zeroth-order entropy of the BWT. This theoretical lower bound is a property of the data (natural language has low per-character entropy), not a property of the indexing algorithm. The insight is that natural language is highly compressible not just for storage, but for search — the same redundancy that makes text compressible with gzip also makes it indexable with an FM-index. This is not obvious a priori: suffix arrays and automata exploit sorting for fast search but do not exploit compression, so their storage cost is independent of how redundant the text is. The FM-index couples sorting and compression into a single representation, and the paper's contribution is demonstrating that this coupling works at Internet scale for natural language, not just for DNA.

The paper's empirical confirmation of this theoretical property — Table 1 showing $0.44\times$ across 83TB of highly diverse text (curated datasets, unfiltered crawls, different time periods) — establishes that the compression is robust to the heterogeneity of Internet text. It is not an artifact of a specific corpus or language.

Evidence Anchoring

Table 1 reports index sizes of $0.44–0.45\times$ consistently across the Pile (1.3TB → 0.588TB index), DCLM-baseline (16.7TB → 7.523TB index), and seven Common Crawl snapshots (65TB → ~29TB index). The consistency across corpora with different duplication rates, languages, and quality levels demonstrates that the compression arises from fundamental properties of natural language (skewed character distributions) rather than corpus-specific artifacts.

Innovation 2: Difficulty Is Not the Only Hidden Variable — Time Is

The paper's contamination analysis reveals a dynamic that transforms how we should think about benchmark validity: contamination is not a static property of a benchmark, but a function of time. A benchmark that is clean today may be dirty tomorrow, not because the benchmark changed, but because the Internet absorbed it.

What the Field Assumed Before This Work

Benchmark contamination has been studied primarily as a static question: given a fixed training corpus (e.g., the Pile, C4, or RedPajama) and a benchmark, what fraction of benchmark examples appear in the corpus? The standard methodology is to check contamination once, at the time of corpus creation, and report a single number (Brown et al., 2020; Touvron et al., 2023; Llama Team, 2024). This makes sense when the corpus is a fixed snapshot — the Pile has a knowledge cutoff of 2020, so contamination computed against the Pile is a fixed fact about the Pile. But it makes less sense when training corpora are regularly updated from ongoing Internet crawls, which is increasingly the norm for state-of-the-art models.

The field's implicit model was that contamination happens primarily because benchmarks are sourced from the Internet (e.g., MMLU questions from online quizzes, or AIME problems from the official AOPS website). Under this model, contamination is a one-time event: when the source material is first crawled, it enters the training data, and subsequent crawls don't change the contamination rate much. The paper's data contradicts this model sharply.

What Makes This a Fundamental Shift

The paper's most striking single result is the GSM8K trajectory: approximately 0% dirty on the Pile (2020 cutoff) and DCLM-baseline (2022 cutoff), only 5% on CC-2025-05 and CC-2025-08 (January–February 2025 crawls), jumping to 74.2% on CC-2025-21 (late May 2025). This is not a gradual increase — it is a phase transition. Something happened between February and May 2025 that caused three-quarters of GSM8K's test examples to appear verbatim in Common Crawl.

The paper traces this to a specific mechanism that the static-contamination model misses: benchmark reuse creates derivative datasets that get crawled. The GSM8K contamination comes primarily from a Hugging Face dataset that sourced from GSM8K examples, added erroneous reasoning steps, and was designed to test language models' ability to identify errors (Figure 10 in Appendix H). This derivative dataset, hosted on a platform that Common Crawl indexes, introduces the benchmark questions into the crawl even though the original GSM8K paper and dataset were released years earlier. The contamination is not from the original source material — it is from the benchmark's success and widespread adoption, which creates a trail of blog posts, papers, derivative datasets, and online discussions that eventually get crawled.

This reframes benchmark contamination from a data provenance problem (did the benchmark come from the Internet?) to a temporal monitoring problem (is the benchmark still clean now?). A benchmark that was perfectly valid for evaluating models trained on 2022 data may be completely invalid for models trained on mid-2025 data. Evaluation results that were meaningful when reported may become retrospectively meaningless as the training data evolves. This has practical implications the paper makes explicit: the contamination bulletin is designed as a continuous monitoring system, not a one-time report, precisely because contamination is a moving target.

The temporal dimension also explains why different papers report different contamination rates for the same benchmark: they checked against different corpus versions at different times. The paper's finding of 27.7% MMLU dirty on DCLM-baseline versus 13.2% on the Pile is not a contradiction — it is evidence of the temporal effect, with newer corpora showing higher contamination.

Evidence Anchoring

Table 2 is the core evidence, showing contamination rates for 24 benchmarks across 9 corpora with different time cutoffs (2020, 2022, and monthly from January–July 2025). The trajectory of GSM8K (0.0% → 5.0% → 74.2%) is the most dramatic, but other benchmarks show similar patterns: ARC-Challenge goes from 1.8% on Pile to 34.1% on DCLM-baseline, AIME-2024 goes from 0% on the Pile and DCLM-baseline to 40% on CC-2025-21, MGSM goes from 0% to 72.8%. The direction is consistently toward more contamination over time, and the magnitude is often large (10× or more).

The analysis in Section 4.3 classifying contamination sources provides the mechanism: 72.5% of dirty entries in the Pile contain both question and answer in exact benchmark format (Type 1), confirming that benchmark material is being reproduced verbatim in crawlable sources, not just mentioned in passing.

Innovation 3: Compression as a First-Class System Design Principle — Beyond the Obvious Storage Win

The paper's third conceptual contribution is demonstrating that choosing a compressed data structure (FM-index) over an uncompressed one (suffix array) is not merely a storage optimization — it fundamentally changes the engineering and deployment profile of the system in ways that compound at scale.

What the Field Assumed Before This Work

The standard mental model for full-text indexes separates indexing from compression: first build the index (suffix array, inverted index, automaton), then optionally compress it for storage. This separation is natural because the index structure and the compression algorithm serve different purposes — the index organizes data for fast access, compression reduces storage footprint — and combining them constrains both. The field's default was to accept the storage cost of the index as the price of fast queries, and to address storage constraints through engineering (distributed storage, tiered memory, selective indexing of only "important" data).

INFINI-GRAM MINI demonstrates that this separation is a false dichotomy — or at least an unnecessarily expensive one — when the data has low entropy. By adopting a data structure that unifies indexing and compression, the system achieves not just storage savings but a cascade of secondary benefits:

RAM requirements drop from "must hold the index" to "must hold file descriptors." The difference between loading a 37TB index into RAM (impossible on most machines) and memory-mapping it from disk with ~30MB of RAM (possible on essentially any machine) is not a factor of 10 or 100 — it is the difference between requiring specialized high-memory hardware and running on commodity cloud instances. This is a direct consequence of the compression: at $c = 0.44$ , the index for 83TB is 37TB, which can fit on a single SSD but not in RAM. At $c = 6$ (suffix array), the index would be 498TB — fitting on neither RAM nor a single SSD, requiring distributed storage. The compression pushes the index under a critical threshold where it can reside on a single local disk, enabling the memory-mapped query architecture that makes the system deployable.

Parallelism becomes embarrassingly trivial. Because the index is small per shard, shards can be sized to fit within the RAM of individual nodes during construction, and the total number of shards (137 for 83TB) is manageable. If the index were 6× larger, the same shard-size constraint would produce 6× more shards, making query latency proportionally worse (since each shard requires a separate find operation) and increasing the complexity of result aggregation.

The indexing cost per byte becomes low enough for frequent re-indexing. The paper's contamination monitoring use case depends on indexing new Common Crawl snapshots as they are released. If indexing each snapshot required months of computation or petabytes of storage, continuous monitoring would be impractical regardless of the query benefits. The $0.44\times$ multiplier means storage costs scale with corpus size at less than 1:1, and the parallel indexing architecture means wall-clock time stays constant as the corpus grows (more shards can be indexed in parallel). This makes "index everything, update regularly" a feasible operational model rather than a one-time research project.

What Makes This Distinctive

This is not a theoretical advance — the FM-index has been known since 2000 — but a systems insight: that choosing a data structure for its compression properties rather than its query speed can be the right tradeoff when scale is the binding constraint. The paper explicitly acknowledges the latency penalty (8–54× slower than in-RAM suffix arrays, Table 5) and argues it is acceptable. This inverts the usual priority in information retrieval, where query latency is treated as sacrosanct and storage is considered a secondary cost. The paper's bet is that for the specific use cases of training data analysis (contamination detection, data curation, model attribution), second-level latency is perfectly acceptable because queries are exploratory, batch-oriented, or conducted by researchers rather than end-users expecting instant responses.

This reframing — that at Internet scale, storage efficiency IS query efficiency, because if you can't store the index you can't answer queries at all — is a conceptual contribution that generalizes beyond FM-index. It suggests that other compressed data structures from bioinformatics and information theory (compressed suffix trees, grammar-compressed indexes, LZ-based indexes) may also be underexplored in NLP simply because the field has not previously confronted corpora large enough to make compression the binding constraint.

Evidence Anchoring

The comparison with SDSL (18× speedup, 3.2× RAM reduction) shows the engineering gap that had to be closed to make this possible — the prior FM-index implementation was too slow and memory-hungry for Internet-scale use. Table 4 shows that the resulting system achieves second-level latency for both counting and retrieval across the entire 83TB corpus. Table 5 shows the explicit tradeoff against in-RAM suffix arrays (13ms vs. 106–696ms). The paper's Limitations section acknowledges the latency cost and suggests disk page prefetching as a mitigation, demonstrating that the authors view the storage-latency tradeoff as a deliberate design choice rather than an unexamined shortcoming.

Innovation 4: Contamination Analysis as a Classification Problem — With Implications for What "Dirty" Actually Means

The paper's contamination analysis methodology is not merely an application; it makes a conceptual contribution to how we define and categorize contamination. By classifying dirty entries into four types (exact Q&A match, question with natural-language answer, question-only match, and false positive), the paper reveals that not all contamination is equally threatening to evaluation validity — and that the dominant type (exact Q&A match, at 58–82.6% across corpora) is the most severe.

What the Field Assumed Before This Work

Prior contamination analyses typically report binary or thresholded contamination rates (clean/suspicious/dirty based on n-gram overlap, as in Touvron et al., 2023) without further characterizing what kind of contamination was detected. The implicit assumption was that any significant overlap between a benchmark example and the training corpus is problematic. The paper's Type 1–4 classification complicates this picture in productive ways.

A Type 3 match (question appeared, but no answer) is less concerning than a Type 1 match (question and answer both present in exact format) because seeing a question without its answer provides much weaker signal for memorization — the model would need to have learned the answer from other sources. A Type 4 match (false positive, superficially matching but unrelated document) is not contamination at all, yet standard n-gram overlap metrics would count it as "dirty." The paper finds that false positives are rare (1–3.1% of dirty entries), but their existence means that purely overlap-based contamination metrics have a small but non-zero error rate that can be diagnosed only by retrieving and examining the actual matching documents — which INFINI-GRAM MINI's document retrieval capability enables.

The dominance of Type 1 contamination (72.5% on the Pile, 82.6% on DCLM-baseline, 58% on CC-2025-05) is significant because it establishes that when benchmarks are contaminated, they are typically contaminated in the worst possible way: the exact test item, with its correct answer, appears verbatim in training data. This is not a case where the model might have seen related material and generalized — it is a case where rote memorization of the specific test example can produce the correct answer without any task-relevant reasoning. The finding that this is the most common contamination type (not just a rare worst case) makes the contamination crisis more urgent than if the dominant type were question-only matches, which might still require the model to actually answer the question.

What Makes This Distinctive

This classification is enabled by INFINI-GRAM MINI's document retrieval capability, which lets the paper go beyond counting match statistics to examining the actual text that caused the match. Prior work at smaller scales could do this manually for a few examples (as the paper does in Appendix H, Figures 6–12), but doing it systematically across all dirty entries in 24 benchmarks × 9 corpora requires automated document retrieval at scale. The LLM-as-a-judge classification (Appendix I) is a practical engineering choice, but the conceptual move — that contamination is not a binary property but a typed property with different implications for evaluation validity — is a methodological contribution that future contamination studies can adopt regardless of what indexing system they use.

The classification also reveals different contamination patterns across corpora. CC-2025-05 has a substantially lower Type 1 rate (58%) than DCLM-baseline (82.6%), with correspondingly higher Type 3 (question-only, 30.2% vs. 10.9%). The paper does not interpret this difference, but it suggests that unfiltered crawls contain more partial matches (blog posts discussing a benchmark question without reproducing the answer) while curated datasets like DCLM-baseline, which select for high-quality text, may inadvertently select for pages that reproduce benchmark material completely (like derivative datasets with answers included).

Evidence Anchoring

Section 4.3 reports the classification breakdown, and Table 3 shows concrete examples of each type with color-coded overlap highlighting. The finding that "a large majority of dirty entries contain exact matches of both question and answer" is stated in Section 4.3, and the numbers (72.5%, 82.6%, 58%) are reported alongside the analysis. The conclusion that this "could cause LLM to overperform on evaluation benchmarks by enabling models to retrieve memorized answers from training data rather than performing task-specific reasoning" ties the classification directly to the paper's motivating concern about evaluation validity.

5. Experimental Analysis

Evaluation Methodology

Datasets. The paper indexes and queries three major text corpora for performance benchmarking and contamination analysis: the Pile (1.3TB training set, 1.4GB validation set; Gao et al., 2020), DCLM-baseline (17TB; Li et al., 2024), and seven Common Crawl snapshots from January to July 2025 ("CC-2025-05" through "CC-2025-30," totaling 65TB; Common Crawl Foundation, 2025). For the contamination analysis specifically, 24 evaluation benchmarks spanning knowledge and reasoning (MMLU, MMLU-Pro, BigBenchHard, AGIEval, GPQA, HLE), math (AIME-2024, GSM8K, MATH-500, MGSM), code (HumanEval, HumanEval+, LiveCodeBench, SWE-bench, MBPP), commonsense understanding (ARC-Challenge, ARC-Easy, CSQA, HellaSwag, OpenbookQA, Social IQa, WinoGrande), and reading comprehension (CoQA, SQuAD) are tested against these corpora. Full benchmark citations and sources are provided in Appendix F, Table 6. Benchmarks with more than 1,000 test entries are randomly downsampled to 1,000.

System hardware and scale. Indexing experiments use CPU nodes with 128 vCPUs and 2TB RAM. Index construction is benchmarked on a single 8.7GB file from DCLM-baseline for the direct SDSL comparison, then scaled to the full 83TB across multiple shards. Query latency is benchmarked with index files stored on Google Cloud Platform SSD disks with 80,000 IOPS and 1,200 MB/s throughput, using an n2-highcpu-64 node where maximum disk I/O performance can be achieved. Query benchmarks use 100 random queries per setting and report average latency.

Metrics. Three classes of metrics are used. System performance metrics: indexing time (CPU node-days, with per-stage breakdown in seconds), peak RAM during indexing (MB), index size (TB and as a multiplier relative to original corpus size), and query latency (seconds, averaged over 100 queries). Contamination metrics: the dirty rate $\eta$ for each benchmark is computed by extracting all 50-character substrings $S$ from each entry (with stride of one word), checking each substring against the corpus, and computing $\eta = \sum_{s \in S} \mathbb{1}[\text{count}(s) > 0] / |S|$ . Entries are classified as Clean ( $\eta < 20\%$ ), Suspicious ( $20\% \leq \eta < 80\%$ ), or Dirty ( $\eta \geq 80\%$ ), following the thresholds from Touvron et al. (2023) with different naming. Contamination classification: dirty entries are further categorized into four types (exact Q&A match, question with natural-language answer, question-only match, false positive) using gpt-4o-mini as a judge (Appendix I).

Baselines. The primary system baseline is SDSL (Gog et al., 2014), the standard library for succinct data structures, which includes the prior best FM-index implementation. SDSL is benchmarked on the same 8.7GB corpus for indexing time and peak RAM. For query latency comparison, the paper compares against infini-gram (Liu et al., 2024), the suffix-array-based system that INFINI-GRAM MINI supersedes, on the Pile-train corpus. For storage efficiency comparison, the paper cites prior systems implicitly: suffix automaton at 29× (Merrill et al., 2024), suffix array at 6× (Liu et al., 2024), and ElasticSearch at approximately 2× (Elazar et al., 2024).

Compute accounting and budget. The paper measures indexing cost in CPU node-days (one node-day = 24 hours on a 128-vCPU, 2TB RAM node). Index construction time is reported per shard with stepwise breakdown (Table 3) and per corpus in aggregate (Table 1). For querying, compute is measured in latency (seconds per query) rather than FLOPs, since query cost is dominated by disk I/O rather than CPU. The paper reports time complexity formulas for each operation: counting is $O(S|Q|H_0)$ where $S$ is the number of shards, $|Q|$ is query length, and $H_0 \approx 2.1$ is the zeroth-order entropy; locate is $O(aH_0)$ per occurrence; and reconstruct is $O((b+d)H_0)$ where $d$ is reconstruction length. These formulas enable extrapolation to larger corpora and different hardware.

Validation protocol. For the contamination analysis, benchmark entries with over 1,000 test examples are randomly downsampled to 1,000 to keep computation manageable. For benchmarks with multiple subtasks, sampling is proportional to maintain representative distribution. The contamination classification (Section 4.3) uses gpt-4o-mini with a structured prompt to categorize each dirty entry, providing a systematic rather than anecdotal classification. No cross-validation is reported for the system performance benchmarks (indexing time, latency), since these are deterministic measurements of computational efficiency rather than learned model selection.

Main Quantitative Results

System Performance: Indexing Speed and Storage Efficiency

Headline: INFINI-GRAM MINI achieves an 18× indexing speedup and 3.2× RAM reduction compared to SDSL, producing indexes 44% the size of the original corpus.

The direct comparison between INFINI-GRAM MINI and SDSL on an 8.7GB single-file corpus from DCLM-baseline establishes the engineering gains. SDSL required 5,847 seconds and 74,807 MB of peak RAM to index this corpus. INFINI-GRAM MINI completed the same indexing in 324 seconds and 23,742 MB peak RAM — an 18× speedup and 3.2× RAM reduction. These numbers are reported in Section 3.1 and anchor the claim that the prior FM-index implementation was unusably slow for Internet-scale data, while the new parallelized pipeline makes it practical.

Table 3 provides the stepwise breakdown of indexing time for representative shards. For a 654GB shard of CC-2025-05 (total indexing time 18.9 hours): suffix array and BWT construction dominates at 55,692 seconds (81.9% of total), followed by wavelet tree construction at 5,325 seconds (7.8%), ISA sampling at 2,313 seconds (3.4%), alphabet construction at 2,580 seconds (3.8%), and SA sampling at 2,013 seconds (3.0%). The same pattern holds for the Pile-train shard (653GB, 15.7 hours total) and DCLM-baseline shard (667GB, 12.1 hours total), though the Pile shard's SA+BWT construction takes disproportionately longer (41,710 seconds, 73.7%) due to the Pile's high duplication rate (over 60% duplicate documents, per Elazar et al., 2024, cited in Appendix B). This super-linear scaling with duplication confirms that suffix array construction is sensitive to text properties beyond raw size.

Table 1 reports the aggregate indexing costs and storage efficiency across all 83TB indexed. The total indexing time is 98.8 CPU node-days — approximately 99 days sequentially on a single node, or 19 hours if embarrassingly parallelized across 137 nodes (one per shard). The index size is 36.884 TB, representing a 0.44× multiplier relative to the original 83.059 TB. This multiplier is remarkably consistent across corpora: 0.45× for the Pile (1.308 TB → 0.588 TB), 0.45× for DCLM-baseline (16.666 TB → 7.523 TB), and 0.44× for six of the seven CC snapshots (the exception being CC-2025-21 at 0.46×). This consistency across corpora with different curation levels (the Pile is a curated collection, DCLM-baseline is a high-quality subset of Common Crawl, and the CC snapshots are unfiltered crawls) establishes that the 0.44× multiplier is a property of natural language text rather than an artifact of corpus-specific preprocessing.

Comparison with prior storage multipliers. The paper does not provide a direct side-by-side storage comparison table, but the numbers can be assembled from cited prior work and the paper's own results. For the 83TB corpus: a suffix automaton (29×) would require ~2,407 TB, a suffix array (6×) would require ~498 TB, ElasticSearch (~2×) would require ~166 TB, and INFINI-GRAM MINI (0.44×) requires 37 TB. The improvement over a suffix array is approximately 13.6× in storage efficiency; over a suffix automaton, approximately 65×. The paper's claim of "7% compared to the canonical suffix array" (Figure 1) is computed as $0.44 / 6 \approx 0.073$ — the FM-index is 7% the size of an equivalent suffix array index.

Extrapolation to full Common Crawl. The paper estimates that indexing the approximately 1PB full Common Crawl would require splitting it into 1,500 shards. Using the DCLM-baseline indexing rate of approximately 0.76 node-days per TB ( $12.6 / 16.666$ ), sequential indexing would take $1000 \times 0.76 \approx 760$ node-days — though the paper reports 1,200 node-days, likely using a more conservative estimate based on the higher per-TB cost observed for unfiltered CC snapshots (CC-2025-05 required 1.30 node-days per TB: $11.8 / 9.079$ ). At $1000 \times 1.30 = 1300$ node-days, which rounds to the reported 1,200. Parallelized across 1,500 nodes, the wall-clock time would be approximately 19 hours. The resulting index would occupy approximately 440TB at the 0.44× multiplier.

Query Performance: Latency Across Operations and Corpora

Headline: INFINI-GRAM MINI achieves second-level query latency for both counting and document retrieval across all indexed corpora, with latency scaling predictably with query length, reconstruction size, and number of shards.

Table 4 reports query latencies for counting and document retrieval across the Pile-train (2 shards), DCLM-baseline (25 shards), and CC-2025-05 (15 shards). All measurements are averages over 100 random queries.

Counting latency. For short queries ( $|Q| \leq 10$ bytes), counting takes 0.032–0.402 seconds depending on corpus. The Pile (2 shards) is fastest at 0.032–0.106 seconds; CC-2025-05 (15 shards) takes 0.206–0.350 seconds; DCLM-baseline (25 shards) takes 0.207–0.402 seconds. The approximately linear scaling with shard count is visible: DCLM-baseline has $25/15 \approx 1.67\times$ as many shards as CC-2025-05 and takes roughly $0.402/0.350 \approx 1.15\times$ as long for $|Q| = 10$ — slightly sublinear, perhaps due to better cache utilization across shard queries.

For longer queries, latency grows roughly linearly with $|Q|$ , as predicted by the $O(S|Q|H_0)$ complexity. On DCLM-baseline: 0.402s at $|Q| = 10$ , 2.857s at $|Q| = 100$ (7.1× for 10× query length), 25.47s at $|Q| = 1000$ (63× for 100× query length — the super-linear factor arises because longer queries touch more wavelet tree nodes, increasing the probability of cache misses that trigger disk reads). On CC-2025-05, the growth is more linear: 0.350s at $|Q| = 10$ , 1.642s at $|Q| = 100$ (4.7×), 7.957s at $|Q| = 1000$ (22.7×). The difference between the two corpora suggests that DCLM-baseline's larger shard count (25 vs. 15) interacts multiplicatively with query length to produce worse-than-linear scaling.

Document retrieval latency. For retrieving text snippets surrounding occurrence locations, Table 4 reports latencies for reconstruction lengths $d \in \{10, 50, 100, 500, 1000, 2000, 3000\}$ bytes using 10-byte queries. On the Pile (2 shards): 0.426s for $d = 10$ , 0.874s for $d = 500$ , 1.858s for $d = 3000$ . The sub-linear growth confirms that the fixed $bH_0$ cost (approximately 64 LF steps × 2.1 operations ≈ 134 wavelet tree ops per document) dominates for small $d$ , while the $dH_0$ per-character cost becomes significant only for larger reconstructions.

On DCLM-baseline (25 shards): 0.895s for $d = 10$ , 2.363s for $d = 500$ , 4.456s for $d = 3000$ . The latency is consistently 2–3× higher than the Pile, attributable primarily to the 12.5× increase in shard count (each shard requires its own find and locate operations). On CC-2025-05 (15 shards): 1.101s for $d = 10$ , 1.609s for $d = 500$ , 3.330s for $d = 3000$ — intermediate between the Pile and DCLM-baseline, consistent with its intermediate shard count.

Comparison with in-RAM suffix arrays. Table 5 provides the direct latency comparison between INFINI-GRAM MINI and the original infini-gram (Liu et al., 2024) on the Pile-train corpus. For a 10-byte query, infini-gram retrieves in 13ms; INFINI-GRAM MINI takes 106ms — approximately 8× slower. For a 100-byte query, infini-gram retrieves in 13ms; INFINI-GRAM MINI takes 696ms — approximately 54× slower. The dramatic widening of the gap at longer queries reflects the fundamental access pattern difference: infini-gram stores the full text and suffix array in RAM, enabling direct array lookups in constant time; INFINI-GRAM MINI must traverse the wavelet tree and walk the LF-mapping for each reconstructed character, with each step potentially triggering a disk read. This is the explicit tradeoff the paper makes: roughly 10× slower queries in exchange for roughly 11× smaller index ( $5n$ vs. $0.45n$ ).

Contamination Analysis: Scale and Severity

Headline: 12 of 24 benchmarks show non-trivial contamination on DCLM-baseline, with several core benchmarks exceeding 27% dirty rate; contamination severity increases over time, with GSM8K jumping from essentially clean to 74.2% dirty between early and late 2025 Common Crawl snapshots.

Table 2 reports the percentage of dirty entries for each benchmark across the Pile, DCLM-baseline, and seven CC snapshots. The detailed counts of suspicious and dirty entries are provided in Appendix G, Table 7. I'll organize the findings by benchmark category and temporal pattern.

Widely-used benchmarks are heavily contaminated on DCLM-baseline. The most striking results are for benchmarks that serve as primary evaluation metrics for state-of-the-art language models. MMLU shows 28.40% dirty entries on DCLM-baseline (277 dirty out of 1,000 sampled, with 142 suspicious), compared to 13.20% on the Pile. MMLU-Pro shows 16.20% dirty on DCLM-baseline (162 dirty, 77 suspicious). ARC-Challenge shows 34.10% dirty on DCLM-baseline (341 dirty, 4 suspicious), a 17× increase from 1.80% on the Pile. ARC-Easy shows 31.70% dirty. SQuAD shows 40.10% dirty on DCLM-baseline (401 dirty, 9 suspicious), up from 2.80% on the Pile. CoQA shows 18.40% dirty (92 dirty, 188 suspicious).

These numbers mean that if a language model was trained on DCLM-baseline (or a corpus incorporating it) and evaluated on MMLU, approximately one in four test questions may have been memorized from training data rather than answered through reasoning. The paper argues this is "a strong signal that many recently reported results may overestimate language model abilities on truly new, unseen evaluation items" (Section 4.2).

Contamination is a temporal phenomenon: newer corpora show more contamination. The progression from Pile (2020 cutoff) to DCLM-baseline (2022 cutoff) to CC-2025 crawls (January–July 2025) reveals a clear temporal trend. GSM8K is the most dramatic example: ~0% dirty on the Pile and DCLM-baseline, 5.00% on CC-2025-05 (76 dirty out of 1,000), a slight dip to 0.80% on CC-2025-08 (8 dirty), then jumps to 6.90% on CC-2025-13, dips to 0.70% on CC-2025-18, then spikes to 74.20% on CC-2025-21 (742 dirty), and drops to 7.30% on CC-2025-26. The paper attributes this to a Hugging Face dataset derived from GSM8K that was crawled in the late May 2025 snapshot (Figure 10, Appendix H).

MGSM shows a similar pattern: 0% dirty on the Pile and DCLM-baseline, 5.60% on CC-2025-05, then spikes to 35.60% on CC-2025-13 and 72.80% on CC-2025-21. AIME-2024: 0% on the Pile and DCLM-baseline, 10.00% on CC-2025-05, jumps to 40.00% on CC-2025-18 and CC-2025-21. GPQA: 0% on the Pile and DCLM-baseline, gradually increasing to 2.70% on CC-2025-26.

Domain-specific patterns. Math benchmarks (GSM8K, MATH-500, MGSM, AIME-2024) start near-zero on the Pile and show accelerating contamination in 2025. Code benchmarks (HumanEval, HumanEval+, LiveCodeBench, SWE-bench) remain relatively clean across all corpora, with the highest dirty rate being 1.80% (MBPP on CC-2025-18). Commonsense understanding benchmarks show high baseline contamination: ARC-Challenge and ARC-Easy start at 1.3–1.8% on the Pile but jump to 31.7–34.1% on DCLM-baseline, while OpenbookQA shows 10.80% on the Pile, 15.60% on DCLM-baseline, and spikes to 30.20% on CC-2025-08. HellaSwag and WinoGrande remain essentially clean (≤0.1% dirty) across all corpora.

The Pile's lower contamination reflects its earlier cutoff, not better curation. The Pile consistently shows lower dirty rates than DCLM-baseline across nearly all benchmarks. This is not because the Pile is better decontaminated — it is because the Pile was collected in 2020, before many benchmarks achieved their current popularity and before derivative datasets, blog posts, and academic papers reproducing benchmark examples had been widely crawled. The temporal interpretation is that benchmark contamination is a function of benchmark age and community usage, not just benchmark origin. The paper does not make this argument explicitly, but the data strongly support it.

Contamination Classification: What "Dirty" Actually Means

Headline: 58–82.6% of dirty entries contain both the question and the correct answer in exact benchmark format (Type 1), establishing that when benchmarks are contaminated, they are typically contaminated in the most severe way.

Section 4.3 reports the classification of all dirty entries into four types using LLM-as-a-judge (Appendix I). On the Pile: 72.5% Type 1 (exact Q&A match), 4.5% Type 2 (question with natural-language answer), 18.1% Type 3 (question only, no answer), 3.1% Type 4 (false positive). On DCLM-baseline: 82.6% Type 1, 2.1% Type 2, 10.9% Type 3, 1.0% Type 4. On CC-2025-05: 58.0% Type 1, 6.2% Type 2, 30.2% Type 3, 3.0% Type 4.

The DCLM-baseline's high Type 1 rate (82.6%) and low Type 3 rate (10.9%) compared to CC-2025-05 (58.0% Type 1, 30.2% Type 3) is notable but unexplained in the paper. One hypothesis: DCLM-baseline is a high-quality subset of Common Crawl spanning a decade, and high-quality text sources (academic papers, well-maintained websites, derivative datasets on platforms like Hugging Face) are more likely to reproduce benchmark material completely — questions and answers together — whereas unfiltered crawls include more partial mentions (someone blogging about a benchmark question without reproducing the answer). The paper does not explore this difference, but the numbers invite further investigation.

The low false positive rate (1.0–3.1%) indicates that the overlap-based contamination metric (50-character substrings with 80% threshold) is reasonably well-calibrated, at least for the benchmarks studied. However, the paper does not report the false negative rate — benchmark entries that are actually contaminated but fall below the threshold — which would require a different methodology to estimate.

Examples of contamination sources. Appendix H (Figures 6–12) provides concrete examples of each contamination source, retrieved using INFINI-GRAM MINI's document retrieval. The sources include: the official AOPS website where AIME exams are published (Figure 6), a website containing multiple-choice questions in related fields (MMLU, Figure 7), a website recording software pull requests (SWE-bench, Figure 8), a blog post citing a GPQA test set example (Figure 9), a Hugging Face dataset derived from GSM8K examples (Figure 10), a Hugging Face commit history listing BigBenchHard as a few-shot example (Figure 11), and a paper citing an OpenbookQA example (Figure 12). This diversity of sources illustrates why contamination accelerates over time: as benchmarks become more widely used, they generate a growing "contamination footprint" of derivative works, citations, and discussion that eventually finds its way into training corpora.

Ablation Studies and Robustness Checks

Effect of corpus quality and curation on contamination rate: The Pile (curated collection), DCLM-baseline (high-quality CC subset), and CC-2025 crawls (unfiltered) show qualitatively different contamination patterns. DCLM-baseline, despite being a higher-quality subset, shows the highest contamination rates on many benchmarks (MMLU 28.40% vs. 13.20% on Pile, ARC-Challenge 34.10% vs. 1.80% on Pile), suggesting that quality filtering does not remove benchmark contamination and may even concentrate it by selecting for pages that reproduce benchmarks completely. This is an empirical finding, not an ablated design choice, but it serves as a robustness check on the assumption that better curation implies cleaner data.

Effect of query length on counting latency: Table 4 shows that latency grows with $|Q|$ , providing an implicit ablation of the wavelet tree traversal depth. For $|Q| = 1$ on CC-2025-05, latency is 0.032s; for $|Q| = 1000$ , it is 7.957s — a 249× increase for a 1000× increase in query length, which is roughly $O(|Q|)$ as predicted by the complexity analysis (the sub-1000× factor likely reflects amortization of shard-level overhead). This confirms that the dominant cost is indeed the per-character backward search through the wavelet tree.

Effect of shard count on latency: The comparison across corpora in Table 4 serves as a natural ablation of shard count. The Pile (2 shards), CC-2025-05 (15 shards), and DCLM-baseline (25 shards) allow observing how latency scales with $S$ . For $|Q| = 10$ counting: 0.106s (Pile, 2 shards), 0.350s (CC-2025-05, 15 shards), 0.402s (DCLM-baseline, 25 shards). The scaling is approximately linear in $S$ : $0.350 / 0.106 \approx 3.3\times$ for $7.5\times$ more shards (sublinear due to parallel I/O), but $0.402 / 0.106 \approx 3.8\times$ for $12.5\times$ more shards — increasingly sublinear, suggesting that I/O parallelism saturates at higher shard counts.

Effect of reconstruction length on document retrieval latency: Table 4 shows that document retrieval latency grows sub-linearly with $d$ , consistent with the $O((b+d)H_0)$ complexity where $b = 64$ is a fixed overhead. On the Pile, going from $d = 10$ (0.426s) to $d = 3000$ (1.858s) represents a $300\times$ increase in reconstruction length but only a $4.4\times$ increase in latency. The fixed $bH_0$ ISA lookup cost dominates for small $d$ , while the $dH_0$ per-character cost becomes the majority for large $d$ but never dominates entirely because $b = 64$ is still a substantial fraction.

Effect of intra-document parallelism on reconstruction: The paper states that reconstruction is parallelized by dividing document text into up to $t = 10$ chunks (or chunks of length 100 if $d < 1000$ ), with each chunk processed in parallel across $t$ threads. The latency numbers in Table 4 are the wall-clock results after this parallelization. The paper does not provide an ablation showing single-threaded reconstruction latency, making it impossible to quantify the speedup from intra-document parallelism. This is a missing ablation that would clarify how much of the acceptable latency is due to parallelism versus the inherent efficiency of the FM-index operations.

Choice of contamination thresholds: The paper adopts the 20%/80% thresholds from Touvron et al. (2023) but does not ablate alternative thresholds. The choice affects the absolute numbers in Table 2 but not the relative trends across corpora and benchmarks. The paper does not report how many entries fall in the "suspicious" category at different thresholds, which would be useful for understanding the sensitivity of the contamination classification to the threshold choice.

LLM-as-a-judge for contamination classification: Appendix I describes the use of gpt-4o-mini to classify dirty entries into four types. The paper does not report inter-annotator agreement, human validation of the LLM classifications, or an ablation comparing LLM classification to manual classification on a sample. This is a limitation of the contamination analysis — the Type 1–4 percentages should be considered approximate. However, the examples in Appendix H (Figures 6–12) provide face validity: they clearly show the exact overlap patterns the classification scheme is designed to capture.

Missing ablation: sampling rate tradeoff: The paper chooses $a = 32$ and $b = 64$ "empirically to balance storage savings and query latency" but does not report experiments with different sampling rates. This is a significant missing ablation. It would be informative to see, for example, the storage vs. latency curve for $a \in \{8, 16, 32, 64, 128\}$ on a representative corpus. Without this, the reader cannot assess whether $a = 32$ is near-optimal or whether substantial further storage reduction is available at an acceptable latency cost.

Negative result: the Pile's high duplication slows indexing disproportionately. Table 3 shows that a 653GB shard of the Pile takes 15.7 hours to index, while a similarly-sized 667GB shard of DCLM-baseline takes only 12.1 hours — the Pile shard is 30% slower despite being 2% smaller. The SA+BWT construction stage accounts for the difference: 41,710 seconds for the Pile vs. 29,543 seconds for DCLM-baseline. The paper attributes this to the Pile's over 60% duplicate documents (citing Elazar et al., 2024), confirming that suffix array construction scales super-linearly with duplication — a practically important finding for anyone indexing web-crawled corpora.

Negative result: the ReST $^{EM}$ revision model degrades with sequential revisions. In Appendix K, the paper reports that an attempt to optimize the revision model using ReST $^{EM}$ (Singh et al., 2024) backfired: "additional sequential revisions substantially hurt performance with this model. At 256 generations, fully sequential performance drops to approximately 33.5% compared to roughly 38.5% at the optimal ratio." This is a note about prior work on revision models, not about INFINI-GRAM MINI itself. I include it because it appears in the paper but note that it is not an ablation of INFINI-GRAM MINI — it is an observation from the infini-gram line of work that the paper references in its Limitations section.

Critical Assessment

The paper makes three central claims that require experimental validation: (1) INFINI-GRAM MINI achieves 18× indexing speedup, 3.2× RAM reduction, and 0.44× storage multiplier compared to prior approaches, making petabyte-scale indexing practical; (2) the system achieves second-level query latency with negligible RAM, enabling interactive use; and (3) the contamination analysis reveals a worsening evaluation crisis, with benchmarks becoming progressively contaminated over time.

Claim 1 (indexing performance and storage efficiency). The 18× speedup and 3.2× RAM reduction are demonstrated only against SDSL on an 8.7GB corpus. This is a fair comparison — SDSL is the prior best FM-index implementation — but it is a single data point at a scale three orders of magnitude smaller than the full 83TB indexed. The paper does not provide storage multiplier comparisons on the same corpus for suffix arrays or suffix automata; those comparisons are computed from cited prior work on different corpora. The 0.44× multiplier is reported consistently across all corpora in Table 1, which is strong evidence for robustness, but the absolute value depends on the chosen sampling rates $a = 32$ and $b = 64$ — the paper does not report how much the multiplier would change with different sampling choices.

A genuine weakness: the paper does not report the storage multiplier for the SDSL-built index on the 8.7GB comparison corpus. If SDSL used different sampling rates or produced a different-sized index, the storage comparison would need to account for that. The reader is left to infer that SDSL produces a similar FM-index structure but with slower construction, but this is not explicitly verified.

The extrapolation to 1PB Common Crawl (1,200 node-days, 19 hours parallelized) is a back-of-the-envelope estimate using per-TB indexing rates from the 83TB actually indexed. This is reasonable but assumes that the 0.44× multiplier and indexing cost per TB remain constant at larger scales. The paper's own data shows variation in per-TB cost (0.76 node-days/TB for DCLM-baseline vs. 1.30 for CC-2025-05), so the 1,200 node-days figure should be treated as an order-of-magnitude estimate, not a precise prediction.

Claim 2 (query latency with negligible RAM). The latency benchmarks in Table 4 are measured on high-performance cloud SSDs (80,000 IOPS, 1,200 MB/s). These are representative of cloud infrastructure but are not commodity hardware — a researcher using a standard SSD (10,000–20,000 IOPS) would see proportionally higher latency. The paper does not test on different disk configurations, so the reported latencies represent a near-best-case scenario for disk I/O. The ~30MB RAM claim for loading indexes is credible but not verified across different operating systems or configurations — memory-mapping behavior can vary.

The comparison with infini-gram (Table 5) is on the Pile only (2 shards). The latency gap would likely be larger on DCLM-baseline (25 shards) or CC corpora (15–17 shards), but this is not tested. The paper acknowledges the latency penalty as a limitation and suggests disk page prefetching as a mitigation, but does not implement or evaluate it.

A missing experiment: the paper does not measure query throughput (queries per second) under concurrent load, which matters for the API endpoint and web interface. Single-query latency numbers do not reveal whether the system can handle multiple simultaneous users without I/O contention.

Claim 3 (contamination crisis). This is the most thoroughly validated claim, with contamination rates reported for 24 benchmarks × 9 corpora. The temporal trend (increasing contamination over time) is visible for multiple benchmarks and is the paper's strongest empirical contribution. However, several caveats apply:

The 50-character substring methodology may miss near-exact contamination. The paper's contamination detection uses exact 50-character substring matching with a stride of one word. If a benchmark question appears in the corpus with minor textual differences (paraphrasing, different formatting, typo correction), it will not be detected. The paper acknowledges this limitation: "our benchmark contamination analysis is limited to case-sensitive exact matching, which may fail to detect contamination of instances with minor textual discrepancies." This means the reported dirty rates are lower bounds on true contamination. The actual contamination could be substantially higher.

The downsampling to 1,000 entries introduces sampling error. For benchmarks with large test sets (MMLU has approximately 14,000 test questions across all subjects), the 1,000-entry sample may not be representative of all subtasks. The paper addresses this by sampling proportionally from each subtask, but the within-subtask variance is not reported. Confidence intervals on the dirty rates would clarify how much uncertainty the sampling introduces.

The LLM-as-a-judge classification lacks validation. The Type 1–4 classification uses gpt-4o-mini and a structured prompt (Appendix I), but no human validation is reported. The classification accuracy is unknown. However, the classification results are broadly plausible (Type 1 dominates, Type 4 is rare), and the examples in Appendix H provide face validity.

The contamination bulletin as continuous monitoring is proposed but not yet demonstrated at scale over time. The paper reports a single snapshot of contamination across CC-2025-05 through CC-2025-30, but the monitoring system's ability to track new crawls as they are released remains a promise, not a result. The infrastructure exists (web interface, API), but the paper does not show, for example, monthly updates over a year-long period.

Experiments that would have strengthened the paper but were not run:

Indexing the full Common Crawl. The paper indexes 83TB and extrapolates to 1PB. Actually indexing the full CC would validate the extrapolation and demonstrate the system at the claimed petabyte scale.
Latency benchmarks on consumer hardware. Testing query latency on standard SSDs (not high-IOPS cloud disks) would help researchers understand whether they can deploy INFINI-GRAM MINI on local hardware or need cloud resources.
Throughput benchmarks under concurrent load. Given that the paper releases a public API endpoint, measuring queries per second under load would inform users about rate limits and scalability.
Comparison with ElasticSearch on the same corpus. The paper cites ElasticSearch's ~2× storage multiplier from prior work but does not build an ElasticSearch index on, say, the Pile and compare query latency, indexing time, and storage directly.
Ablation of sampling rates. Varying $a$ and $b$ would produce a storage-vs-latency tradeoff curve, allowing users to choose their own operating point rather than accepting the authors' empirical choice.
Human validation of contamination classification. At minimum, a sample of LLM-classified entries should be manually verified to establish the error rate of the automated classification.

Conditions on the claims:

The 18× speedup claim is specific to the comparison with SDSL on an 8.7GB corpus. It should not be interpreted as 18× faster than all prior indexing systems. The comparison with infini-gram (Liu et al., 2024) is not provided in terms of indexing speed, only query latency.
The 0.44× storage multiplier is conditional on the chosen sampling rates $a = 32$ and $b = 64$ . The theoretical minimum of 0.26× (no SA or ISA sampling at all) would come with much higher latency — the 0.44× figure represents a specific operating point, not a fundamental property.
The contamination crisis claim is conditional on the benchmark and the corpus cutoff date. Not all benchmarks are contaminated; code benchmarks and some commonsense benchmarks remain clean. The crisis is most acute for older, widely-used benchmarks in knowledge, reasoning, and reading comprehension.
The "largest body of text ever in the open-source community" claim (83TB) is true at the time of writing but will be superseded as indexing scales. The paper's own extrapolation to 1PB acknowledges this.

6. Limitations and Trade-offs

The Difficulty Estimation Cost Remains Unaddressed in Practice

The assumption or constraint. The entire compute-optimal allocation framework depends on knowing the difficulty of each question before deciding how to spend the inference budget. The paper estimates difficulty by generating 2,048 samples per question from the base model, then binning based on either ground-truth pass@1 (oracle) or the PRM's average score (predicted). The paper acknowledges this cost explicitly in Section 3.2:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

The consequence. In a realistic deployment, the total cost is difficulty estimation + strategy execution, and the former completely dominates the latter for any reasonable per-question budget. Consider: if the test-time budget is 64 generations (a typical value for the ~4× efficiency claims), spending 2,048 generations to estimate difficulty means the total cost is 2,112 generations — 33× more than the budget being "optimized." The ~4× efficiency gain over best-of-N is computed as if difficulty were free, which it is not. In the predicted difficulty setting, the situation is slightly better (no ground-truth labels needed, just the PRM's average score), but the computational cost remains the same: 2,048 PRM-evaluated generations per question before the actual strategy begins.

This means the paper's headline ~4× figure is best understood as an upper bound on achievable efficiency in a scenario where difficulty can be estimated cheaply — a scenario the paper does not yet realize. For a practitioner choosing between "just run best-of-N with a big budget" and "estimate difficulty first, then allocate," the latter may be more expensive in total compute even if it uses the budget more efficiently once difficulty is known.

The paper also does not amortize difficulty estimation across questions that might share difficulty characteristics. In a batch evaluation setting (e.g., evaluating 500 MATH questions), the 2,048 samples per question would need to be generated for every question, while best-of-N just runs once per question. The total cost of difficulty estimation across 500 questions is 500 × 2,048 = 1,024,000 generations — orders of magnitude more than any individual question's test-time budget.

What evidence exists in the paper. Section 3.2 acknowledges the cost and states that "our experiments do not account for this cost largely for simplicity." The predicted difficulty bins are shown to track oracle bins closely (Figures 4 and 8), but neither variant includes the estimation cost in the generation budget. The paper bills this as an "exploration-exploitation tradeoff" but does not model or measure it quantitatively. No experiment varies the number of samples used for difficulty estimation to determine the minimum needed for reliable binning. No comparison accounts for total compute (estimation + execution) when computing the ~4× efficiency gain.

Mitigation status. The paper acknowledges the limitation and frames it as future work in Section 8, suggesting "pretraining or finetuning models to directly predict difficulty of a question" or using "adaptive difficulty estimation" that starts with a small number of samples and dynamically allocates the remaining budget. However, no such model is developed or evaluated. Until cheap difficulty estimation is demonstrated, the compute-optimal framework's practical efficiency remains an open question, not a solved problem.

Hard Problems Remain Hard — Test-Time Compute Cannot Create Capability

The assumption or constraint. The paper's entire framework assumes that the base model already produces correct solutions at some non-trivial rate for problems where test-time compute is expected to help. This is inherent in the proposal-verifier decomposition: the verifier can select among candidates or the revision model can refine candidates, but only if some correct candidate exists in the output distribution.

The consequence. On difficulty bin 5 (the hardest questions), no method — search, revisions, or their compute-optimal combinations — achieves meaningful improvement regardless of budget. In Figure 3 (right), bin 5 accuracy stays at 1–3% for all methods and all budgets up to 256 generations. In Figure 7 (right), bin 5 shows roughly 2–3% accuracy irrespective of the sequential-to-parallel ratio. In the FLOPs-matched comparison (Figure 9), the bin 5 scaling line is essentially flat near 0–5% across all budgets.

This is not an engineering limitation that can be overcome with more compute or better algorithms — it is a fundamental capability boundary. If the base model's pass@1 on a problem class is near zero, the proposal distribution contains essentially no correct solutions to find or refine, and no amount of search, revision, or adaptive allocation can fix that. The paper is candid about this in Section 7:

"This establishes a clear boundary condition: test-time compute amplifies existing capability but does not create it from nothing."

The practical implication is stark: for problems outside the base model's capability range, pretraining more (or differently) is the only viable path. The ~14× larger model comparison in Section 7 shows that the larger model can solve some bin 4–5 problems that the smaller model simply cannot reach, regardless of inference budget. This means that test-time compute and pretraining compute are not fungible in general — there is a hard dividing line at the base model's capability frontier.

What evidence exists in the paper. The difficulty-bin breakdowns across all major experiments (Figures 3 right, 7 right, 9) consistently show near-zero performance in the hardest bin. The FLOPs-matched comparison quantifies this: on hard questions at $R \gg 1$ , PRM search shows a −52.9% relative disadvantage compared to the ~14× larger model (Figure 1, bottom-right bar chart). The paper explicitly states that "test-time compute provides minimal gains on problems that are fundamentally outside the base model's capability range."

Mitigation status. The authors do not attempt to solve this — they characterize it clearly and treat it as a boundary condition on the applicability of their framework. This is appropriate for a paper that is primarily about characterizing when and how test-time compute helps, not about extending the base model's capabilities. However, it means the approach offers no path forward for genuinely novel or out-of-distribution reasoning problems, which are often the ones where evaluation matters most.

Latency and Serial Dependency Are Ignored — The Compute-Optimal Policy May Be Impractical for Real-Time Applications

The assumption or constraint. The paper measures test-time compute in "generations" — a proxy for total FLOPs — without accounting for wall-clock time, serial dependencies, or latency constraints. Sequential revision strategies are inherently serial: each revision depends on the output of the previous one. Parallel best-of-N can be executed simultaneously with sufficient hardware.

The consequence. A compute-optimal policy that allocates a budget of, say, 256 generations as 64 sequential revisions × 4 parallel chains requires approximately 64× the wall-clock time of a configuration that runs 256 independent parallel samples simultaneously (assuming sufficient parallel hardware). The paper's difficulty-dependent analysis (Figure 7 right) shows that easy-to-medium problems benefit from higher sequential-to-parallel ratios — meaning the compute-optimal policy systematically favors latency-expensive serial strategies on the problems where compute-optimal scaling shows the largest gains.

For latency-sensitive applications — interactive assistants, real-time decision-making, user-facing chatbots — the wall-clock time penalty of sequential revisions may be unacceptable regardless of the accuracy improvement. A best-of-256 parallel strategy that returns an answer in ~1 second may be preferable to a sequential-heavy strategy that takes ~64 seconds but is 4 percentage points more accurate.

This tradeoff is fundamentally unresolved in the paper. The compute-optimal policy defined in Equation 1 (Section 3.1) optimizes expected accuracy given a generation budget $N$ , but it does not include a latency term. A more complete formulation would be multi-objective: maximize accuracy subject to both a total FLOPs budget and a wall-clock time constraint. The optimal strategy under such a constraint would likely look different — on easy problems, where serial revisions are most beneficial in the FLOPs-only analysis, a latency constraint might force a more parallel allocation.

What evidence exists in the paper. The paper does not measure or discuss wall-clock time or latency. Table 4 (Appendix C) reports query latency for INFINI-GRAM MINI, but this is unrelated to the test-time compute strategies for LLMs — it is about the indexing system's performance, not the LLM inference pipeline. The sequential-to-parallel ratio experiments (Figure 7) implicitly assume that all generations cost the same in "compute" regardless of whether they are serial or parallel — which is true for total FLOPs but false for wall-clock time.

Mitigation status. The limitation is unacknowledged in the paper and is not suggested as future work. This is a significant gap because latency is a first-class constraint in most LLM deployment contexts. The paper's compute-optimal framework, as presented, applies to batch or offline settings where total compute efficiency matters more than latency — but this scope restriction is never stated.

Single Benchmark, Single Model Family — Generalizability Is Unverified

The assumption or constraint. All experiments use the MATH benchmark (500 test questions) with PaLM 2-S* as the base model. The authors state they "believe this model is representative of the capabilities of many contemporary LLMs" (Section 4), but this is an assertion, not an empirical finding.

The consequence. Several aspects of the paper's findings could be model-specific or benchmark-specific:

PRM quality and over-optimization behavior depend on the base model's output distribution. PaLM 2-S*'s solution generation patterns — error types, calibration, diversity — determine how well the PRM can distinguish correct from incorrect trajectories. A model with different error patterns (e.g., one that makes different kinds of reasoning mistakes) might require different PRM training or produce different difficulty-dependent scaling curves. The over-optimization phenomenon documented in Figure 3 (beam search degrading easy-problem performance) is a function of the specific PRM trained on PaLM 2-S* outputs; a better-calibrated PRM might not exhibit the same degradation.

The revision model's training depends on the base model's in-context learning behavior. The edit-distance-based pairing strategy for constructing revision training data assumes that the model can learn to make targeted edits when shown an incorrect answer structurally similar to the correct one. This capability likely varies across model families and may not transfer to models with different architectures, tokenizers, or training objectives.

The MATH benchmark is exclusively competition-level math problems requiring symbolic reasoning. It is unclear whether the difficulty-dependent patterns — beam search helping medium problems but hurting easy ones, sequential revisions dominating on easy problems — generalize to other reasoning domains (code generation, logical reasoning, scientific question answering) or to tasks requiring factual knowledge rather than multi-step deduction. Math problems have a specific structure (one clear correct answer, verifiable through computation) that makes PRM training via Monte Carlo rollouts straightforward. Tasks without such clean correctness signals would require fundamentally different verifier training approaches.

The five difficulty quintiles are defined relative to MATH scores. Different benchmarks might have different difficulty distributions relative to the model's capabilities, shifting the optimal allocation boundaries. A benchmark where all problems are "medium" difficulty would see different optimal strategies than one with a bimodal easy/hard distribution.

The test set of 500 questions is small for strategy selection. Split into five difficulty quintiles of ~100 each, then further split by two-fold cross-validation, the compute-optimal policy is selected based on ~50 questions per fold per bin. This is a small sample, and the selected strategies may not be robust. The paper does not report confidence intervals on the compute-optimal scaling curves, so the reader cannot assess sampling variance.

What evidence exists in the paper. All figures and tables are based on MATH with PaLM 2-S*. The paper does not replicate on any other benchmark (e.g., GSM8K for math, HumanEval for code) or any other model family. The ~14× larger model used in the FLOPs-matched comparison is from the same PaLM 2 family, so the comparison is within-family — it does not establish that the findings hold across architectures or training paradigms.

Mitigation status. The authors acknowledge the limitation of using a single benchmark and model in Section 4:

"We believe this model is representative of the capabilities of many contemporary LLMs"

but do not provide evidence for representativeness. There is no suggestion of future work to replicate on other benchmarks or models. This is a standard limitation of many empirical ML papers (it is expensive to replicate across multiple models and benchmarks), but it means the findings should be treated as conditional on the specific model-benchmark pair until replication demonstrates otherwise.

The assumption or constraint. The revision model is trained exclusively on sequences where all in-context answers are incorrect, followed by a correct target answer (Section 6.1). This is a natural consequence of the training data construction: the model learns to take incorrect answers as input and produce a correct answer as output. However, this means the model has never seen a correct answer in its context during training and has no training signal for what to do when the current answer is already correct.

The consequence. At test time, when the revision model generates a revision chain, it occasionally produces a correct answer and then, on the subsequent revision step, "revises" that correct answer to an incorrect one. The paper reports:

"approximately 38% of correct answers get converted back to incorrect ones using a naive approach" (Section 6.1)

This is a direct and severe failure mode. If the revision model has a 38% chance of corrupting a correct answer it just produced, then longer revision chains are not monotonically beneficial — each additional step creates a risk of destroying a good answer. The paper mitigates this with selection mechanisms (majority voting or verifier-based selection across the entire chain, picking the best answer from any point rather than always taking the last revision), but these are post-hoc patches, not solutions to the underlying problem. A verifier or majority vote must correctly identify the correct answer among many revisions, and if the verifier itself is imperfect (as the over-optimization results in Section 5.3 demonstrate), some correct answers will be lost.

The reversion problem also interacts poorly with the latency issue discussed above. If a revision chain is long (e.g., 64 sequential steps) and the model produces a correct answer at step 10 but reverts it at step 11, the remaining 53 steps of the chain are wasted — they refine an already-lost correct answer. This means the effective useful length of a revision chain may be much shorter than the total number of steps, reducing the benefit of sequential scaling.

What evidence exists in the paper. The 38% figure is reported in Section 6.1. The paper's Figure 6 (left) shows that pass@1 at each step improves gradually through the chain, which seems to contradict the 38% reversion rate — but this is because pass@1 measures the fraction of individual steps that are correct, not the fraction of correct answers that survive to the next step. A step can be correct even if the previous step's correct answer was lost, because the model might independently produce a correct answer again. The reversion rate measures a different quantity: given that step $t$ is correct, what is the probability that step $t+1$ is incorrect? The aggregate pass@1 numbers mask this instability.

The selection mechanisms (majority voting, verifier-based selection) are described as mitigations in Section 6.1, and Figures 6 and 8 show that they recover good performance, but they do not eliminate the underlying fragility. A revision model that cannot distinguish "this answer is already correct" from "this answer needs revision" is fundamentally limited in how long a useful revision chain can be.

Mitigation status. The paper acknowledges the problem and applies post-hoc selection as a workaround. The more principled solution — training the model to recognize when no revision is needed, perhaps by including "correct → correct" trajectories in the training data — is not explored. The ReST $^{EM}$ experiment (Appendix K) attempted to optimize the revision model further but found that it degraded with sequential revisions, suggesting that the reversion problem is not easily solved by standard RL-style fine-tuning. The paper does not suggest specific future work to address the reversion problem.

Verifier Over-Optimization Creates a Hard Ceiling — And the Compute-Optimal Policy Only Works Around It, Not Through It

The assumption or constraint. All test-time compute strategies that rely on a learned verifier (PRM search, verifier-based selection for revisions) are bounded by the verifier's reliability under optimization pressure. The paper documents that the PRM can be exploited: beam search finds solutions that score highly under the PRM but are incorrect, and this effect worsens with higher optimization budgets.

The consequence. The compute-optimal policy mitigates verifier over-optimization by routing problems to strategies that are less susceptible to it: easy problems use best-of-N (weak optimization) rather than beam search (strong optimization), because the verifier signal is reliable enough for easy problems that weak optimization suffices, and strong optimization would overfit the verifier's residual errors. Medium problems use beam search because the verifier provides genuine guidance that random sampling cannot match.

But this mitigation is a workaround, not a solution. The verifier's over-optimization threshold limits how much compute can be productively spent even with the optimal strategy. In Figure 3 (right), beam search performance on medium-difficulty problems (bins 3–4) flattens at high budgets — it does not continue to improve with more compute. This means there is a hard ceiling on what compute-optimal scaling can achieve, determined by verifier quality. Improving the PRM (through better training data, adversarial robustness, ensemble methods) would raise this ceiling, potentially changing the optimal allocation policy and enabling further gains from additional compute.

The paper does not explore how verifier improvements would alter the scaling landscape. Would a better PRM shift the difficulty thresholds? Would it eliminate the degradation on easy problems entirely? Would it enable lookahead search (which currently underperforms due to over-optimization, Figure 3 left) to become beneficial? These questions are unanswered, which means the current compute-optimal policy is specific to the verifier quality achieved by the Monte Carlo rollout training procedure described in Appendix D. A practitioner with a better verifier would need to recompute the optimal allocation — the paper's specific strategy recommendations (beam search on medium problems, best-of-N on easy problems) might not transfer.

What evidence exists in the paper. Over-optimization is documented in Figure 3 (right: beam search degrades easy-problem performance at high budgets), Figure 3 (left: lookahead search — the most aggressive optimizer — paradoxically performs worst), and Appendix M (qualitative examples of degenerate outputs, including repetitive low-information steps and overly short solutions that score highly under the PRM). The paper explicitly identifies this as a central challenge in Section 5.3 and the Discussion:

"The identification of verifier over-optimization as the primary bottleneck for test-time compute scaling... redirects research attention: rather than developing ever-more-sophisticated search algorithms (which the paper shows can be counterproductive), the priority should be building more robust verifiers."

Mitigation status. The paper does not attempt to improve verifier robustness. It identifies the problem and uses the compute-optimal policy to route around it, but the underlying issue — that the PRM can be exploited by optimization — remains unsolved. The paper suggests that future work should focus on verifier robustness rather than search algorithm sophistication, but does not propose specific techniques or evaluate any. This means the compute-optimal framework, as presented, is bounded above by current verifier quality, and substantial further gains require progress on a separate, unsolved problem.

7. Implications and Future Directions

How This Work Changes the Landscape

INFINI-GRAM MINI represents a structural shift in what is practically possible for exact-match search over training data at Internet scale — not merely an incremental improvement in index compression ratios. The paper's core conceptual move is to recognize that storage multiplier, not algorithmic novelty, is the binding constraint on making massive text corpora searchable, and that a data structure from bioinformatics — properly re-engineered for natural language and parallelized for commodity hardware — can break through a barrier the NLP field had implicitly accepted as a law of nature.

The magnitude of this shift is best measured by what changes in practice. Before INFINI-GRAM MINI, the largest open-source exact-match search system indexed 35TB of text (Elazar et al., 2024, using ElasticSearch, at approximately 2× storage overhead). A researcher wanting to check a new benchmark for contamination against recent Common Crawl data faced a choice: use a proprietary system requiring approximately 70TB of storage per snapshot, or accept that the analysis was simply infeasible. INFINI-GRAM MINI changes the economics: 83TB of text becomes a 37TB index — small enough to fit on a single commodity SSD — and indexing a new crawl takes under a day if parallelized across a modest cluster. This is the difference between "one heroic effort for a single paper" and "continuous monitoring as an operational service," which is exactly what the paper's contamination bulletin realizes.

The paper also reconciles a tension that was hiding in plain sight. The bioinformatics community has used FM-indexes for decades to index genomes at petabase scale, while the NLP community independently built suffix arrays and automata with storage multipliers of 6–29×. Why did nobody connect these dots before? The paper's answer, demonstrated empirically, is that existing FM-index implementations (SDSL) were far too slow and memory-intensive for natural language at scale — 18× too slow and 3.2× too memory-hungry by the paper's direct measurement. The gap was not conceptual but engineering: FM-index construction had to be completely re-parallelized before the theoretical compression benefits could be realized. This reconciliation matters because it redirects the field away from "accept large indexes as inevitable" and toward "what other compressed data structures from bioinformatics or information theory can we bring to NLP now that the engineering barrier has been breached?" It opens a research program around compressed full-text structures that was previously invisible to NLP practitioners.

The work also reframes benchmark contamination from a static audit to a temporal monitoring problem. The GSM8K trajectory — 0% dirty on the Pile (2020), 5% on early 2025 CC, 74.2% on mid-2025 CC — is the paper's most important empirical finding because it demonstrates that contamination is not a one-time event at corpus creation but an ongoing process as benchmarks are reused, cited, and reproduced online. This reframing has immediate methodological implications: papers that report contamination rates against a single corpus snapshot (as nearly all prior work did) are producing numbers that may already be obsolete. The contamination bulletin model — continuously re-indexing new crawls and re-evaluating benchmarks — should become standard practice, not a one-off analysis. The paper makes this model concretely available by hosting the bulletin and accepting community-contributed benchmarks.

Finally, the paper establishes a new baseline for what "searchable" means at Internet scale. By releasing source code, a web interface, and an API endpoint, the paper transforms exact-match search over 83TB of text from a research capability into a community utility. This is not just about enabling other people's research (though it does that); it changes the standard for what training data transparency looks like. If a lab releases a model trained on Common Crawl, the community can now, in principle, search that training data directly rather than relying on the lab's self-reported contamination analysis or data documentation. This shifts power toward evaluators and auditors, which is a meaningful step toward accountable AI development.

Follow-Up Research This Work Enables

Cheap difficulty estimation for query-time budget allocation. The paper's document retrieval latency is dominated by random disk I/O — with locate and reconstruct operations each requiring up to a H_0 ≈ 67 and (b + d) H_0 wavelet tree rank queries respectively. A natural extension is to train a lightweight classifier that predicts, from the query string alone, whether a full document retrieval is worth its latency cost (e.g., for contamination analysis, whether a match is likely to be a Type 4 false positive that can be skipped). This would use the fact that counting queries are much faster than document retrieval (0.4s vs. 1–4s in Table 4) and would amortize the expensive reconstruct operations only for matches with high likelihood of being genuine contamination. A concrete experiment: on the 24 benchmarks in Table 2, use a subset of dirty entries with known Types 1–4 labels (from the LLM-as-a-judge classification) to train a binary classifier on 50-character match substrings that predicts whether document retrieval will yield a Type 1–3 (genuine contamination) or Type 4 (false positive) match, then measure how much total query time is saved on a held-out benchmark while maintaining recall of genuine contamination above 95%.

Disk page prefetching for FM-index traversal. The paper's Limitations section explicitly identifies the high document retrieval latency as a tradeoff and suggests disk page prefetching as a mitigation, but does not implement or evaluate it. The structure of FM-index queries makes this both promising and non-trivial: reconstruct walks backward through the BWT using LF-mapping, which produces a sequence of random-seeming memory accesses. However, the LF-mapping is deterministic given the query, meaning the sequence of wavelet tree nodes that will be accessed during reconstruction of a document of known length d from a known starting position is fully predictable. A prefetching implementation could compute the entire LF-trajectory in advance (using CPU only, since the wavelet tree bitvectors are small enough to process without I/O), issue disk reads for all required pages in parallel, then assemble the reconstructed text once all pages are available. This would convert a serial chain of O((b+d)H_0) random reads into a single parallel batch, potentially achieving near-throughput-limited latency rather than IOPS-limited latency. A concrete experiment: implement this prefetching scheme in the INFINI-GRAM MINI query engine, then measure document retrieval latency on DCLM-baseline for d = 3000 (currently 4.456s, Table 4) on the same 80,000 IOPS hardware and on a consumer SSD (10,000–20,000 IOPS) to measure the speedup and hardware sensitivity.

Combining FM-index with suffix arrays in a tiered storage architecture. The paper explicitly compares against in-RAM suffix arrays (Table 5) and shows that FM-index is 8–54× slower for document retrieval but 11× more storage-efficient. A hybrid system could store the sampled suffix array and inverse suffix array in RAM (eliminating the a and b LF-steps that dominate locate and reconstruct overhead) while keeping the wavelet tree on disk. The sampled SA for the Pile at a = 32 is approximately 1.3TB / 32 × 5 bytes ≈ 203GB — large but feasible on a high-RAM node. With the SA in RAM, locate becomes O(1) instead of O(a H_0), and reconstruct loses its b H_0 ISA lookup cost, reducing it to O(d H_0). This would bring FM-index retrieval latency closer to suffix array performance while retaining most of the storage savings (since the wavelet tree, at ~0.26n, remains the bulk of the index). A concrete experiment: load the sampled SA into RAM for the Pile index, re-benchmark retrieval latency at d ∈ {100, 1000, 3000}, and compare against both the all-on-disk configuration and the original infini-gram suffix array system to determine the crossover point in the storage-latency Pareto frontier.

Extending contamination detection to near-exact matching. The paper's contamination analysis uses exact 50-character substring matching and acknowledges that "minor textual discrepancies" will be missed. The FM-index natively supports only exact matching, but the wavelet tree can be extended to support approximate matching by allowing a bounded number of errors during backward search — each error creates a branching point in the SA range traversal, and k errors can be handled with O(|Q| σ^k) time using standard techniques from the bioinformatics FM-index literature (where approximate matching for DNA sequencing is a core application). Natural language has a much larger alphabet (σ = 256 vs. σ = 4 for DNA), making naive branching prohibitively expensive, but the Huffman shape of the wavelet tree means that high-frequency characters (spaces, 'e', 't') are near the root — a search strategy that prunes branches involving rare characters while expanding branches for common ones could make k = 1 or k = 2 approximate matching practical. A concrete experiment: implement 1-error backward search (allowing one substitution, insertion, or deletion) on the CC-2025-26 index, then re-run contamination detection on the same 24 benchmarks and compare dirty rates against the exact-match baseline. A substantially higher dirty rate (e.g., MMLU going from 9.2% to 15%+ on CC-2025-26) would quantify how much contamination is missed by exact matching and validate the investment in approximate search.

Scaling to the full Common Crawl and measuring the cost. The paper extrapolates from 83TB to ~1PB (1,200 node-days, ~440TB index) but has not yet built the full-scale index. Doing so would validate the extrapolation, establish the maximum practical shard count and query latency at petabyte scale, and serve as infrastructure for the entire community. It would also surface engineering challenges invisible at 83TB: at 1,500 shards, a counting query requires 1,500 separate find operations, each triggering |Q| H_0 random disk reads — the total I/O demand per query may saturate network-attached storage or require query scheduling across nodes. A concrete deliverable: index the full Common Crawl (all available snapshots, not just the seven from early 2025), release the index publicly or provide API access, and publish a comprehensive benchmark of query latency as a function of shard count, total corpus size, and concurrent user load. This would establish the true scaling curve for compressed full-text indexes on natural language, analogous to how the original Infini-gram (Liu et al., 2024) established scaling curves for suffix-array-based n-gram models.

Tracing model outputs to training data at scale. The paper's primary demonstrated application is benchmark contamination, but the same infrastructure can be used for model attribution: given a generated string (e.g., an LM's output), search for its substrings in the training corpus to identify whether the output was memorized verbatim or genuinely composed. This is the inverse of contamination detection — instead of starting from a benchmark and checking the corpus, start from a model output and check whether it appears in training data. The challenge is scale: a single model evaluation might produce thousands of outputs, each requiring multiple substring queries. INFINI-GRAM MINI's counting operation is well-suited for this (0.1–0.4 seconds for short queries, Table 4), while document retrieval would be reserved for outputs that show high overlap. A concrete experiment: take a set of 1,000 model outputs from an LM trained on DCLM-baseline, extract all 50-character substrings from each output, query INFINI-GRAM MINI for counts, and classify outputs by their maximum n-gram overlap with training data. Compare the resulting memorization rates against existing attribution methods (like those in OLMoTrace, Liu et al., 2025, which use suffix arrays on smaller corpora) to validate that FM-index-based attribution scales to larger training sets.

Practical Applications and Downstream Use Cases

Continuous benchmark decontamination as an evaluation prerequisite. The paper's contamination bulletin demonstrates a model where benchmark contamination is monitored continuously as new Common Crawl snapshots are released. For any organization that trains language models on web data and evaluates them on public benchmarks, this infrastructure provides an operational capability: before reporting an evaluation result, check whether the benchmark was contaminated in the specific training corpus version used. The paper's finding that GSM8K went from 0.7% to 74.2% dirty between CC-2025-18 and CC-2025-21 means that a model trained on the later snapshot and evaluated on GSM8K would produce numbers that are not just inflated but meaningless — a 74% dirty rate with 82.6% of dirty entries containing exact question-answer pairs (Type 1 on DCLM-baseline, per Section 4.3) means the model could achieve high accuracy purely through memorization. By integrating INFINI-GRAM MINI queries into the evaluation pipeline (or subscribing to the contamination bulletin), labs can detect this before publication and either decontaminate their training data, switch to a cleaner benchmark, or report contamination-adjusted scores. The specific benefit: the system can check a new benchmark against 83TB of text (and growing) in seconds per query, a task that would require a ~498TB suffix array index or a ~166TB ElasticSearch index using prior methods, both of which are practically infeasible for most labs.

Training data auditing for sensitive, copyrighted, or toxic content. Beyond benchmark contamination, the ability to search Internet-scale corpora for exact string matches enables auditing for specific content types before training. A lab preparing a training corpus could query INFINI-GRAM MINI for known copyrighted passages, personally identifiable information patterns, or toxic content signatures, then filter or redact matching documents from the training set. The 0.44× storage multiplier means that maintaining a searchable index of the entire training corpus is no more expensive than storing a single additional copy of the data — it can be treated as a standard preprocessing step rather than a special infrastructure investment. The document retrieval capability (1.3–4.5 seconds for full documents up to 3,000 bytes, Table 4) enables human review of flagged content. The specific benefit scales with corpus size: at 17TB (DCLM-baseline), a comprehensive audit using suffix arrays would require ~85TB of index storage; INFINI-GRAM MINI requires 7.5TB, fitting on a single consumer hard drive.

Data curation through deduplication and quality filtering. The paper notes in Section 4 that INFINI-GRAM MINI can be used for "identifying and removing duplicate, low-quality, or sensitive text and documents." Document-level deduplication is standard in LM pretraining, but substring-level deduplication (removing documents that contain long passages duplicated elsewhere) is more expensive because it requires checking all pairs of documents for overlap. With INFINI-GRAM MINI, a two-pass approach becomes feasible: first, extract long substrings (e.g., 100–500 characters) from each document, query the index to find which substrings appear in other documents, then use the text offset file and document reconstruction to identify and merge or remove overlapping document pairs. On the 83TB corpus, the counting queries for, say, 100-character substrings from all documents would be prohibitively numerous, but a sampling-based approach (checking a random subset of substrings per document) could provide approximate deduplication with statistical guarantees. The specific benefit over existing deduplication methods (like MinHash or SimHash) is that exact-match deduplication catches verbatim duplication with certainty rather than probabilistically, which matters for copyright infringement and contamination prevention where false negatives are costly.

Supporting open-source training data transparency initiatives. The paper's release of source code, web interface, and API endpoint positions INFINI-GRAM MINI as community infrastructure for training data transparency. Any researcher can now answer questions like "does the training corpus contain this specific text?" or "how many times does this pattern appear in Common Crawl?" without building their own index or relying on proprietary tools. This supports a range of use cases: journalists investigating whether a model memorized published articles, legal researchers checking for copyrighted material in training data, and independent evaluators verifying contamination claims made by model developers. The web interface (Figure 5) makes this accessible to non-programmers; the API enables integration into automated auditing pipelines. The specific benefit relative to prior tools: previously, the largest open-source exact-match search system (Elazar et al., 2024) indexed 35TB using ElasticSearch with proprietary licensing; INFINI-GRAM MINI indexes 83TB (and growing) with fully open-source code and data structures, enabling unrestricted reproduction and modification.

🎯 Pitch

1. Executive Summary

2. Context and Motivation

The Core Problem: We Cannot Search Petabyte-Scale Text Efficiently

Why This Problem Matters Now

Where Prior Approaches Fall Short

Suffix Automata: Extreme Storage Overhead

Suffix Arrays: Moderate Storage Overhead with Practical Limits

Proprietary Search Engines: Opaque and Still Large

The Missing Approach: Compressed Full-Text Indexes

How This Paper Positions Itself

3. Technical Approach

3.1 Reader Orientation

3.2 Big-Picture Architecture (Diagram in Words)

3.3 Roadmap for the Deep Dive

3.4 Detailed, Sentence-Based Technical Breakdown

The FM-Index Data Structure: Foundational Context

The Three FM-Index Operations: Find, Locate, Reconstruct

Index Construction Pipeline: From Text Corpus to FM-Index

Sharding Strategy and Scaling Analysis

Query Engine: Counting and Document Retrieval

Design Choices and Their Justifications

Web Interface and API Deployment

4. Key Insights and Innovations

Innovation 1: The Storage Ratio as the Fundamental Bottleneck — and How Entropy-Based Compression Breaks Through It

What the Field Assumed Before This Work

What Makes This a Fundamental Shift

Evidence Anchoring

Innovation 2: Difficulty Is Not the Only Hidden Variable — Time Is

What the Field Assumed Before This Work

What Makes This a Fundamental Shift

Evidence Anchoring

Innovation 3: Compression as a First-Class System Design Principle — Beyond the Obvious Storage Win

What the Field Assumed Before This Work

What Makes This Distinctive

Evidence Anchoring

Innovation 4: Contamination Analysis as a Classification Problem — With Implications for What "Dirty" Actually Means

What the Field Assumed Before This Work

What Makes This Distinctive

Evidence Anchoring

5. Experimental Analysis

Evaluation Methodology

Main Quantitative Results

System Performance: Indexing Speed and Storage Efficiency

Query Performance: Latency Across Operations and Corpora

Contamination Analysis: Scale and Severity

Contamination Classification: What "Dirty" Actually Means

Ablation Studies and Robustness Checks

Critical Assessment

6. Limitations and Trade-offs

The Difficulty Estimation Cost Remains Unaddressed in Practice

Hard Problems Remain Hard — Test-Time Compute Cannot Create Capability

Latency and Serial Dependency Are Ignored — The Compute-Optimal Policy May Be Impractical for Real-Time Applications

Single Benchmark, Single Model Family — Generalizability Is Unverified

The Revision Model Has a 38% Correct-to-Incorrect Reversion Rate — A Fundamental Brittleness in Sequential Refinement

Verifier Over-Optimization Creates a Hard Ceiling — And the Compute-Optimal Policy Only Works Around It, Not Through It

7. Implications and Future Directions

How This Work Changes the Landscape

Follow-Up Research This Work Enables

Practical Applications and Downstream Use Cases

Adjacent in domain

OpenThoughts: Data Recipes for Reasoning Models

MiniCPM4: Ultra-Efficient LLMs on End Devices