arXiv preprint ·
Cascade: GPU-Accelerated Out-of-Core Suffix Array Construction for LLM Corpora
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Suffix arrays over LLM (pre)training corpora underpin deduplication, contamination testing, n-gram statistics, and training-data attribution, and every new corpus or tokenizer needs a new one. GPU constructors are fast but bounded by device memory, and out-of-core pipelines run at CPU speed, reaching trillions of tokens by building sharded indexes. Reach is bounded not by the size of the data but by what must stay resident, and in a partitioned construction that is the coupling between partitions. We present Cascade, which requires none of it to stay resident. Splitter K-grams sampled from the corpus fix every partition's range of the final suffix array before any sorting, so the GPU sorts and ranks partitions independently and never merges them. The partitions are still coupled: every round of the method needs ranks that other partitions hold, classically kept in a global rank array (the inverse suffix array) that must stay resident. We instead send each rank to the one partition that needs it, and maintain an invariant ensuring ranks are only ever compared within one partition, so no global rank array is needed. The text and a compact partition map, the only structures read at random, then stay in host memory by choice rather than necessity, one at a time when memory is short; every other structure becomes a stream that can be placed across device memory, host memory, and disk as it is written. On a single GPU node, Cascade builds exact suffix arrays of up to 238B tokens, 2.4-6.8x faster than infini-gram's pipeline and 5.9-10.9x faster than libsais.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Optimal High Probability Bounds for Random Order Online Sorting
Stochastic Weighted Caching with Per-Request Predictions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.