Compression, storage and exact lookup for learned n-gram embedding tables.
面向 learned n-gram embedding 表的压缩、存储与精确查询。
FastText builds word vectors from subword n-gram rows. Engram-style LLM memory looks up token n-gram rows and mixes them into hidden states. In both cases the model ends up owning a large frozen table that has to be indexed, stored and queried. NGramStore takes care of that table; training, addressing and aggregation stay in the model.
The project continues the idea of the paper Memory-Efficient FastText: give every n-gram an exact identity, then compact the table after training. The paper describes the idea; this repository has the rebuilt engine and everything measured since (from the paper to now).
The research questions are the paper's, asked again with full experiments: when
is it worth giving every n-gram its own row instead of hashing into buckets, what
redundancy does training leave in the table, and how should it be served? The
experiments are in evidence/.
| Layer | What it does |
|---|---|
| Table engine | Lossless block encoding, original-ID forwarding, mmap, decoded-block cache, batched gather. C ABI and Python |
| N-gram structure (optional) | DATrie index over registered string keys, prefix/suffix representative selection, mark-compact export |
| Model adapters | FastText, Engram / TinyEngram / Qwen memory, CPU text classifiers |
pack and the structural layout/exact modes keep source bytes. joint
sharing (cosine + norm-ratio guard) and quantization change vectors and are
opt-in.
Needs a C compiler and zlib headers, on Linux or macOS. PyTorch is optional.
python -m pip install .Pack an existing table (row-major little-endian float32) and query it:
ngram-store pack --input vectors.f32 --dim 256 --output memory.native
ngram-store inspect --store memory.native
ngram-store query --store memory.native --ids 0 42 0from ngram_store import NativeRows
with NativeRows("memory.native/table.men", cache_bytes=4 * 1024**2) as memory:
original_bytes = memory.rows([0, 42, 0])ngram-store plan --input vectors.f32 --dim 256 counts duplicate rows and
prints the pack command for the smallest layout that still serves lookups at
near raw speed.
ngram-store demo-bags --output demo trains a small model on bundled text and
builds a certified bag table end to end.
The engine guide walks through a complete
example, and concepts explains the terms.
- Distinct rows vs hash buckets. On MultiCounterFact with 20,877 edits on frozen Qwen 0.6B/4B, independent n-gram rows improve H by 0.41/1.24 pp over hashing with matched coverage (report). On smaller grids, held-out perplexity and joint training the gap disappears (details).
- Prefix/suffix structure is learned. Merging order-12 prefix/suffix neighbours at .99 cosine saves 1.34% of n-gram storage after 2k training steps and 41.49% after 32k (report).
- Duplicate rows, not compression, carry the lossless saving. On zero-initialized classifier tables, byte dedup + Zstd saves about 84% but made host lookups 29–79× slower in the deployment grids (report). Profiling showed the cost is block decompression. Dedup without compression saves 85.0–85.8% (vs 85.7–86.6% with Zstd), and the same GPU host path runs 1.09–1.23× raw with identical logits (profile). Without duplicates (uniform initialization) compression saves only 8–9%; raw is better. This is a property of word tables over documents, not of n-gram memories in general: on token n-grams over a text stream the repeat fraction is higher but most of it is keys seen in a single window, which a count threshold removes anyway (token-level check).
- Construction fits in small memory. Disk-backed building cuts peak RSS from 3.1 GiB to 95 MiB for the same output bytes, at 5× the build time (report).
All ~45 reports, grouped by question, are listed in the evidence index.
| Application | Guide |
|---|---|
| FastText word embeddings | prepare → train → export → query |
| Engram LLM memory | official demo and factory |
| TinyEngram / Qwen | checkpoint export and decode |
| CPU news classification | AG News · open-vocabulary hybrids |
| Path | Contents |
|---|---|
native/ |
C engine (meft_rows.c) and structural bridge |
ngram_store/, meft_memory/ |
Python package and CLI |
tools/ |
22 runtime modules and the experiment scripts behind evidence/ |
src/, mylib/ |
FastText-derived C++ trainer/exporter and DATrie libraries (Linux x86-64) |
tests/, examples/, benchmarks/ |
Tests, runnable examples, benchmark configs |
docs/ |
Guides, roadmap, history |
evidence/ |
Experiment protocols, results and verifiers |
The C engine and wheel run on Linux and macOS; the DATrie bridge and FastText facade need Linux x86-64. Tables are read-only at serving time. Runtime details are in the C ABI guide; what comes next is in the roadmap.
NGramStore started as me_fasttext, a 2017 FastText prototype written up in arXiv:2506.01254. It gave every subword n-gram an exact DATrie ID instead of a hash bucket, trained one row per n-gram, and after training merged similar rows and compacted the table, in the spirit of a mark-compact collector. Each part has since been tested on its own:
| Idea in the paper | What the experiments show |
|---|---|
| Exact IDs instead of hash buckets | Pays off when the task stores many per-key facts: +0.41–4.05 pp at 20,877 knowledge edits on frozen Qwen, mixed at 1,024 (result 1) |
| Prefix/suffix neighbours can share rows | They become similar with training: 1.34% saving after 2k steps, 41.49% after 32k (result 2) |
| Compact the table after training | With pooled reads and zero initialization, training itself leaves rows byte-identical; storing each distinct row once, uncompressed, saves 85% and serves near raw speed (result 3) |
| Extend to LLM n-gram memory | Engine and adapters work for Engram, TinyEngram and Qwen. The size savings do not carry over to token n-grams (token-level check) |
The engine itself was rebuilt. Old meft_memory imports, meft-* commands and
file formats still work (compatibility,
documents from the paper's period).
Cite the software through CITATION.cff with the commit you used
(citation guide). Benchmark results and
integration reports are welcome; see CONTRIBUTING.
MIT. Bundled FastText sources keep their original notices. See LICENSE.