TLDR; How I improve the NanoGPT Speedrun world record from 39.9s to 6.7s with retrieval-augmented n-gram hints. This is a larger improvement than all prior improvements since 2025 combined.
Introduction #
The NanoGPT Speedrun challenges you to train a model to GPT-2-level loss on an 8xH100 node as fast as possible. Since its start in May ‘24, it has seen nearly 100 records, cutting training time from 45 minutes to 39.9 seconds.
Language models struggle to learn from text they have seen only a few times<sup>1</sup>A model is worse at answering a question the fewer training documents contain the relevant facts (Kandpal et al., 2023). A single exposure to a fact barely changes the model, and the small gain is mostly forgotten as training continues (Chang et al., 2024). Models also rarely memorize text that appears only once in the training data (Carlini et al., 2023).. Unfortunately, text is full of passages that repeat only occasionally, like quotes, facts and book excerpts<sup>2</sup>Our validation set contains passages from Revelation 21, Moby-Dick and The Merchant of Venice ("If you prick us, do we not bleed?"), a NASA explainer of the Van Allen belts and an explanation of color theory. Each appears only 1-5 times in our 37B-token hint corpus, so most likely never in the tokens the model trains on. A model trained without hints has a loss of 3.4–4.6 on them, while the record's loss is 0.03–0.19. That said, most of the gains are from more standard short phrases or regular text, such as a birthday wish or an advertisement for buying something..
Until now, the CPUs were mostly idle, so I use them to build a hint corpus: a lookup table of which tokens follow each n-gram (a sequence of n tokens) in the training data. We give the model the most common next tokens as hints, and it learns how much to trust them, resulting in much lower loss on hinted tokens.
This post contains two parts. First, I show that text repeats and how we can exploit it. Then I walk through how we build a large hint corpus quickly.
Long n-gram hints are rare and reliable #
Web text is repetitive, with validation n-grams also appearing in training<sup>3</sup>FineWeb is scraped from the web, where the same page can be crawled twice and the same boilerplate shows up on many sites. 6-grams and even 20-grams are short, so they also catch cookie banners, book excerpts and facts shared by otherwise different documents. Even with fuzzy deduplication of train and validation documents, the hints give large gains, with training finishing in around 10 seconds..
For a 20-gram that also appears in training, the most common next token is correct 98% of the time, and 54% for 6-grams.
If we record which token follows each n-gram in the training data, we can give the model the most common ones as hints for what is likely to come next.
The hints come only from the training data, just like the model's weights, and we never build hints from validation tokens.
Learning to use the hints #
Long hints are usually correct, but how much we trust a hint depends on its length, how often the n-gram appears in the training data (count) and how often the n-gram is followed by the same token (purity). It should also depend on how confident the model is. Rather than mixing the model prediction and n-gram hint distribution,
as infini-gram<sup>4</sup>[Liu et al. (2024)](https://arxiv.org/abs/2401.17377) build an n-gram model over trillions of tokens and interpolate its next-token distribution with a neural language model's at inference time, without training the model to use them. does,
we give the hints to our model and let it decide how to use them[<sup>5</sup>](#fn-5)Training with the hints makes our backbone transformer model slightly worse when evaluated without hints, given the same number of steps..
To give the model a hint, we take the hinted token's embedding from the model's own embedding table.
Each kind of hint, given by its length, count and purity[<sup>6</sup>](#fn-6)The length is the number of tokens in the n-gram (6, 10 or 20). The count is how many times the n-gram appears in the training corpus, and the purity is how often it is followed by the hinted token.We group the counts into 7 buckets and the purities into 6, so with 3 lengths there are 7 × 6 × 3 = 126 trust amounts and trust embeddings., has two learned parameters:
a trust amount that scales the hint embedding up or down, and a trust embedding that we add to it, telling the model what kind of hint it is.
We add the hints to the residual stream in three places. Right after the embedding, in the middle of the layers, and right before the LM head, each time with its own learned scale[<sup>7</sup>](#fn-7)The scales differ since the residual norm grows with depth..
Scaling the hint corpus has strong returns #
We train a model on 70.8M tokens with hints drawn only from tokens we have already trained on and evaluate it with hint corpora from 75M to 37B tokens.
If we train on a large hint corpus from the start, the backbone model relies on the hints too much, so a small hint corpus during training and a large one during validation works better[<sup>8</sup>](#fn-8)Switching to a large hint corpus midway through training is faster, but timing is more fragile, since the CPU needs to finish building the hints right before the GPU needs them..
Loss keeps improving with hint corpus size, and each doubling helps more than the previous.
A larger hint corpus gives more hints.
1% of validation tokens have a 20-gram match in a 75M-token hint corpus, which increases to 11% in a 37B-token one[<sup>9</sup>](#fn-9)With fuzzy document deduplication, 6.6% of validation tokens still have a 20-gram match..
We build the hint corpus on the CPUs while the GPUs train, so a faster builder means a larger hint corpus. Our best hint builder is 500x faster than a naive Python implementation and 11x faster than an auto-researched implementation. The next sections build it step by step, bringing the record from 39.9s to 6.7s.
The naive hint builder is simple, but slow (39.9s -> 39.3s) #
The simplest hint builder is a hash map in Python. The key is a hashed n-gram and the value is a list (with duplicates) of the next tokens. To look up a hint during validation, we compute the hash of the n-gram and count how many times each next token appears. It is easy to write, but the cache locality is bad, we need dynamic heap allocations and different n-gram lengths require separate entries.
## Auto-research helps, but not enough (39.3s -> 21s)
If we give the Python code to a Rust auto-research agent[<sup>10</sup>](#fn-10)Opus 5.5 with 1.5 weeks of a $200 subscription, 48 hours of 8xH100 compute plus around 100k CPU hours (most experiments could be done only on CPUs since a fast hint builder is mostly independent of GPUs)., it is able to improve the cache locality and remove dynamic allocation, but it does more compute per token and it moves more bytes through memory than needed.
It struggled to come up with ideas that deviated from existing practices for general hash maps to an implementation that was tailor-made for our use case, even when given guidance.
## From hash map to slot index (21s -> 18.3s)
Instead of a general-purpose hash map, we pre-allocate one large array of partitions, each split into buckets with a fixed number of slots<sup>11</sup>We have 2<sup>14</sup> partitions with 2<sup>14</sup> buckets each, and each bucket has 176 slots. The slots are 64 bits wide.. The n-gram's hash selects a partition and two buckets inside it, and we write the hint into the first bucket, or into the second once the first is full. That way, if a common n-gram fills its first bucket, the n-grams sharing that bucket can still use their second.
If both buckets are full, we drop the hint.
Each slot holds the next token and a hashed n-gram checksum, which tells the n-grams that share a bucket apart.
To look up hints, we read up to two buckets for the n-gram and count the next tokens in slots with a matching checksum. We now allocate memory only once and lookups take time, no matter how large the hint corpus is. For now, each n-gram length still needs its own slot, and every write goes to a random place in the array.
Shared slot for all hint lengths (18.3s -> 11.5s) #
The 6-gram is the last 6 tokens of the 10-gram, which is the last 10 tokens of the 20-gram, and all three are followed by the same token, meaning they can share one slot. The 6-gram hash selects the partition and buckets, and the slot stores checksum bits for all three n-grams. The 6-gram gets most of the checksum bits, since a 6-gram collision gives the wrong hint, while a 10- or 20-gram collision only affects how much we trust it. To look up hints, we check the 6-, 10- and 20-gram checksums in order, and a longer n-gram only matches if the shorter ones did.
Sort- and branch-free hint builder with L2 cache (11.5s -> 6.7s) #
Writing each hint straight to its slot would cost a random memory access per hint, so we build the table in two stages. First, we hash the n-grams and write them in token order into small per-partition blocks. Second, we place the hints in their buckets without sorting, with one thread responsible for each partition. Partitions are too large to cache, so in both stages each thread first collects hints in small burst lines that fit in L2 cache, and writes a line to memory only once it is full. All critical paths are branch-free.
See the [appendix](#hint-builder-details) for details.
Putting it all together #
Together, these steps take the record from 39.9s to 6.7s: the GPUs train as before, and the idle CPUs build a 37B-token hint corpus in the background. The hints keep helping as the hint corpus grows, so faster hint building should keep paying off.
The hints also work on their own: adding them to Karpathy's original llm.c takes it from 45 minutes to [28 seconds](#llm-c-in-28s),
and building the hints on the GPUs could bring the record down to [3.1 seconds](#hint-building-on-gpu).
Acknowledgements #
I had the idea for the record while working on a research project with my amazing advisor Tatsu Hashimoto. Thanks to Luke Bailey, Neil Band, Adrienne Propp, Jonas De Schouwer and Ryan Welch for feedback on this post, and to Tanishq Kumar, Rajat Dwaraknath and Jerry Liu for sharing their wisdom on twitter storytelling!
Marcel Rød's [gigatoken](https://github.com/marcelroed/gigatoken) was a valuable inspiration for making the CPUs go brr.
Thanks to the NanoGPT Speedrun maintainers and record holders for so many impressive records!
Appendix #
The code for the record is available in a PR to the speedrun repo.
To reproduce all the results in this post, see [this repo](https://github.com/hermabr/n-gram-hinted-lm).
The appendix has four sections:
- [How I used AI](#how-i-used-ai)
- [Training the original 45-minute llm.c in 28 seconds](#llm-c-in-28s)
- [Training in 3.1 seconds by building the hints on GPU](#hint-building-on-gpu)
- [Details on the hint building algorithm](#hint-builder-details)
How I used AI
While nearly all ideation for the project was human, AI was heavily involved in the record. AI wrote nearly all the code, most of which I didn’t even read. This allowed me to test ideas much more quickly, often spending 15 minutes of human time to test an idea that would’ve taken me a day to implement myself, allowing me to test bolder ideas (like gains on the original llm.c code). That said, I found the AI to be surprisingly bad at hill climbing, both when it came to how to giving the LM the hints and on how to build the hint corpus faster. I found this particularly surprising when it comes to building the hint corpus, as that is a very measurable performance task, with quick experiment times and easy correctness tests. In large part, this was due to the model getting stuck in local minima, while the 3x speed ideas required much more out-of-the-box thinking. Many of its ideas were too general or generic, rather than optimizing for exactly our constraints. I wonder if this comes from a lack of good training data. It became much more useful close to the end, when the main ideas of the algorithm and data structure were completed and I wanted to squeeze out more performance from SIMD and flow of data in cache. For instance, it found a faster AVX-512 hash algorithm for the n-grams than the ones I was able to come up with.
Training the original 45-minute llm.c in 28 seconds
As a fun experiment, I added the hints to Karpathy's original 45-minute llm.c code, without any of the speedrun's other improvements, such as Muon, system optimizations or architecture changes. This model learns much more slowly than the record's, so it can't reach the target loss in 7 seconds. However, the longer training leaves more time to build the hint corpus, so I build it from all 100B training tokens, and include hints for n-grams shorter than 6 tokens as well. It reaches the target loss in 28 seconds, faster than all the other incredibly impressive records combined, which together reach 39.9s.
Training in 3.1 seconds by building the hints on GPU
The CPUs build the hint corpus quickly, but the GPUs can build it even faster. To do so, we flip the algorithm: instead of storing hints for every n-gram in the training data, we take each n-gram in the validation data and count how often it appears in the training data, and which tokens follow it. The hints still come only from the training data, but we need to read the validation tokens to know which n-grams to count. The current speedrun rules allow backward passes on the validation data, as long as they happen in the timed region. If counting the validation n-grams falls under the same rule, the GPUs can build an even larger hint corpus in just over 1 second, and then train the model in about 2 seconds, for a total of 3.1 seconds.
That said, this algorithm takes time for training and validation tokens, rather than the runtime that both the existing records and my record have.
Hint corpus details
For computational reasons, we are only able to make hints for a few different n-gram lengths. I found that 6, 10, and 20 work the best. We divide our slot index into 2<sup>14</sup> partitions of 2<sup>14</sup> buckets, with each bucket having 176 slots of 64 bits, for a total of 352 GiB. Inserting hints into the slot index directly in the order of the token stream would be inefficient, since nearly every insert would be a random memory access. We therefore build the slot index in two stages. In the first stage, we compute the hashes for all our hints and assign them to their partitions, in the order they were computed. In the second stage, we place the hints inside each partition into their buckets.
Stage 1: Computing hashes and assigning to partitions
In the first stage, we go from our raw token corpus to an arena (377 GiB) of blocks that hold up to 8k hints each. Each block only holds hints for one partition. In this stage, we only append the hints to the partitions' blocks sequentially and do not care about their order.
We start by dividing our training data into chunks of 64k tokens and assigning them to threads round-robin, so that thread t takes chunks t, t+T, t+2T, etc. for T threads. Threads that finish early take chunks from the slowest threads.
Each thread hashes the 6-, 10- and 20-grams with SIMD, producing 62 bits per hint. Adding the 16 bits for the next token, we have 78 bits: the 14 partition bits and the 64 bits we actually store. While we don't store the 14 partition bits, they still help us avoid collisions since they matter for where each hint is placed.
Since the hashes are random, neighboring hints go to different partitions, so writing each hint straight to its partition's block would be a random memory access with bad cache locality. Instead, each thread keeps a burst line with space for 8 hints (64 bytes) for each partition. With 2<sup>14</sup> partitions, this uses exactly 1 MiB of memory, which fits in the L2 cache of modern Intel CPUs. When a burst line is full, we copy it to a queue, which we drain to the arena blocks every 64 inserts.
We keep all of the main paths branch-free. For each partition, we keep a one-byte count of the hints in its burst line, so we can add hints to the burst lines without any branching.
Since the partitions of our hints are random, we cannot predict whether a burst line is full, which would normally cost around one branch misprediction per 8 inserts. To stay branch-free, we always copy the burst line of the most recent insert to the queue, but only advance the queue's position if the burst line is actually full. That way, only completed burst lines are copied to the arena. Every 64th insert, we copy all completed lines in the queue to the arena. This step has branches, but it is infrequent enough to not be a bottleneck.
Stage 2: Assigning hints to their buckets in each partition
In this stage, we take our hints, which are now grouped by partition into blocks of 8k hints, and place them in their buckets. One thread is responsible for each partition, and the fullest partitions are processed first.
The design mirrors stage 1 in many ways. We load the partition's blocks from the arena one at a time, each holding 8k hints, or 64 KiB. For each of the partition's 2<sup>14</sup> buckets, we keep a burst line in L2 cache that can hold 8 hints. We fill a queue the same way as in stage 1, and copy completed lines to their buckets with non-temporal stores, which bypass the cache.
We place each hint in its first bucket while it has room, and otherwise in its second, without branching.
To do so, we load the fill counts of both buckets and choose between them with select_unpredictable, which compiles to cmp and cmov rather than a jump.
We also need to handle both buckets being full without branching. We set the new fill count to fill + (fill < slots), so the fill count stops at the bucket size. Since the bucket size is a multiple of 8 and we place hints at position fill % 8, a dropped hint is written to the first position of the full bucket's burst line,
which has already been copied to the bucket, so it never reaches the slot index.
-
A model is worse at answering a question the fewer training documents contain the relevant facts (Kandpal et al., 2023 ). A single exposure to a fact barely changes the model, and the small gain is mostly forgotten as training continues (Chang et al., 2024 ). Models also rarely memorize text that appears only once in the training data (Carlini et al., 2023 ).↩︎
-
Our validation set contains passages from Revelation 21, Moby-Dick and The Merchant of Venice ("If you prick us, do we not bleed?"), a NASA explainer of the Van Allen belts and an explanation of color theory. Each appears only 1-5 times in our 37B-token hint corpus, so most likely never in the tokens the model trains on. A model trained without hints has a loss of 3.4–4.6 on them, while the record's loss is 0.03–0.19. That said, most of the gains are from more standard short phrases or regular text, such as a birthday wish or an advertisement for buying something. ↩︎
-
FineWeb is scraped from the web, where the same page can be crawled twice and the same boilerplate shows up on many sites. 6-grams and even 20-grams are short, so they also catch cookie banners, book excerpts and facts shared by otherwise different documents. Even with fuzzy deduplication of train and validation documents, the hints give large gains, with training finishing in around 10 seconds. ↩︎
-
Liu et al. (2024) build an n-gram model over trillions of tokens and interpolate its next-token distribution with a neural language model's at inference time, without training the model to use them.↩︎
-
Training with the hints makes our backbone transformer model slightly worse when evaluated without hints, given the same number of steps. ↩︎
-
The length is the number of tokens in the n-gram (6, 10 or 20). The count is how many times the n-gram appears in the training corpus, and the purity is how often it is followed by the hinted token.We group the counts into 7 buckets and the purities into 6, so with 3 lengths there are 7 × 6 × 3 = 126 trust amounts and trust embeddings. ↩︎
-
The scales differ since the residual norm grows with depth. ↩︎
-
Switching to a large hint corpus midway through training is faster, but timing is more fragile, since the CPU needs to finish building the hints right before the GPU needs them. ↩︎
-
With fuzzy document deduplication, 6.6% of validation tokens still have a 20-gram match. ↩︎
-
Opus 5.5 with 1.5 weeks of a $200 subscription, 48 hours of 8xH100 compute plus around 100k CPU hours (most experiments could be done only on CPUs since a fast hint builder is mostly independent of GPUs). ↩︎
-
We have 2<sup>14</sup> partitions with 2<sup>14</sup> buckets each, and each bucket has 176 slots. The slots are 64 bits wide.↩︎
Oto jump back