crit-hub

lookup-table-rows

Lookup-table rows from disk

A large embedding or n-gram table stays on disk, and each token reads only its own rows, exactly and in parallel, instead of megabytes of read-ahead.

The animation needs JavaScript; How it works below says the same in words.

The problem

  • Token embeddings and n-gram tables (rows picked by a hash of the last few tokens) can be larger than the rest of the model, yet each token reads only a few rows of them.
  • Through a plain read or a default memory mapping, the operating system also reads ahead around every row, often megabytes for a row of a few kilobytes.

How it works

  1. The engine opens the table with random-access advice (posix_fadvise on a file, madvise on a mapping), which turns read-ahead off. Where there is no such advice, as on Windows, every read is exactly one row.
  2. A token's rows are looked up first in a cache of hot rows in host memory, and a row found there is a hit. A row the token asks for twice is fetched once.
  3. Cold rows, the ones not in the cache, go to a small pool of workers. Each makes one positioned read of exactly one row, at the table's offset plus the row number times the row size, and checks it got every byte.
  4. The reads finish in any order, but every row lands in the place the token asked for it.
  5. Newly read rows join the cache. When it is full, the row used least recently leaves.

Configuration

Its options, set per engine in configuration.json. Each is checked against its type and range when the engine loads.

OptionDefaultValuesWhat it sets
workers8int, at least 1Rows read in parallel
cache_rows0int, at least 0Hot rows kept in memory (0: none)
directory""strFolder of the table file
readers64int 1 to 1024device form: threads of the native row reader's positioned reads
prefetch_rows262144int, at least 0device form: rows the hot-row cache holds (prefetch fills it; 0: no cache, prefetch does nothing)
ring4int 1 to 64device form: buffer sets per lookup size of a file table, used in turn by eager lookups (a lookup's rows stay valid until this many later lookups of its size); each captured lookup (a round, a prompt bucket) keeps one for its graph, so give one more than the captures of a size
nativetruetrue, falsedevice form: the native row reader (built at load); false: Python threads, which a CUDA graph cannot capture
configuration.json
{"plugins": {
  "use":     {"embeddings": "lookup-table-rows"},
  "options": {"lookup-table-rows": {"workers": 8, "cache_rows": 0, "directory": ""}}
}}

Pays off when

  • The table is too large to keep in memory, so it stays in a file or a mapping.
  • Tokens and n-grams recur, so many rows come from the cache instead of the disk.
  • The disk serves many small reads at once, as an SSD does.

Doesn't pay off when

  • The table fits in host or device memory and can be loaded once.
  • The table is so small that its reads never show in a pass.

What must stay true

  • The table is never read ahead, by advice or by reads of exactly one row.
  • Every read is checked for its full length, and a short read is an error, never part of a row.
  • Rows come back in the order they were asked for, repeated rows included.