Blame for README.md

---
license: mit
language:
- en
library_name: transformers
pipeline_tag: text-generation
tags:
- llama
- hand-crafted
- compiled
- autocomplete
- no-training
- n-gram
- code
- browser
datasets:
- OpenAssistant/oasst2
- google-research-datasets/mbpp
- neulab/conala
widget:
- text: In Python,
- text: I hope this email
---

# tiny-autocomplete

Ghost-text autocomplete for prompts to a coding assistant. **It's compiled, not
trained.** No gradient descent was run, and no other model or pretrained weights were used.
Every number comes from a closed-form rule in [`build_weights.py`](build_weights.py) applied to
~21,000 lines of human-written text ([sources](data/SOURCES.md)).

It's built to be **confident rather than chatty**. It only suggests when its probability is
high, and otherwise stays quiet.

The same compile produces two artifacts:

| | Browser export (`web/model.bin`) | Transformers model (`model.safetensors`) |
|---|---|---|
| Use it for | embedding in an app: on-device, no server | `transformers`, `pipeline`, research |
| Size | **4.5 MB** | 1.5 GB (380M params, 93% zeros) |
| Per keystroke | **0.5 ms median, 0.9 ms p95** (Bun) | 58 ms per next token (PyTorch CPU) |
| Vocabulary / contexts | 6,612 words / 107,864 contexts | 3,000 words / 24,773 contexts (pruned to fit the dense budget) |

Both are the same kind of network. The browser export stores only the non-zero parts of the
compiled transformer; see [how it works](#how-it-works).

## What it suggests

Real output of `web/autocomplete.ts` with the shipped confidence threshold (72%). Gray is the
ghost text; *(quiet)* means it suggests nothing.

| Typed | Ghost text | Confidence |
|---|---|---|
| `write a python fun` | `ction to` | 98% |
| `how do i conv` | `ert` | 96% |
| `I'm getting an err` | `or` | 100% |
| `can you explain the differ` | `ence between` | 98% |
| `Write a python function to check whether` | ` the` | 72% |
| `I hope this email` | ` finds you` | 85% |
| `what is the best way to` | *(quiet)* | |
| `how to convert a string to` | *(quiet)* | |

## How often it's right

Measured with `python scripts/benchmark.py`. The model is compiled **without** 10% of the
prompts (711 prompts, 42,185 characters), and each of those prompts is then typed
character by character. After every keystroke the model either shows ghost text or stays
quiet.
- **Precision:** the share of shown suggestions that exactly match what the user typed next.
  A wrong word anywhere in the ghost counts as a miss.
- **Coverage:** the share of keystrokes where something is shown.
- **Keystrokes saved:** the share of keystrokes saved when every correct suggestion is accepted
  with Tab.

| Confidence threshold | Precision | Coverage | Keystrokes saved |
|---|---|---|---|
| **0.72 (shipped default)** | **90.3%** | 38.7% | **23.0%** |
| 0.80 | 93.5% | 34.1% | 20.7% |
| 0.90 | 96.4% | 26.9% | 16.4% |
| 0.95 | 97.7% | 20.5% | 11.8% |

The threshold is a runtime setting, so an app can trade coverage for precision without
recompiling. The dense transformers model, with its smaller, more heavily pruned tables,
gets 92.4% precision / 19.0% saved at 0.72.

These numbers come from held-out OpenAssistant, MBPP and CoNaLa prompts. Your users'
prompts may differ, so measure on your own text if you can.

## Use it in your app (browser)

`web/autocomplete.ts` and `tokenizer.ts` are zero-dependency TypeScript with no DOM access, so
they run on the main thread, in a Web Worker, or in Bun/Node.

```ts
import { CompiledAutocomplete } from "./web/autocomplete.ts";

const ac = await CompiledAutocomplete.load(
  "https://huggingface.co/tmickleydoyle/tiny-autocomplete/resolve/main/web/model.bin",
);

input.addEventListener("input", () => {
  const { ghost, prob } = ac.suggest(input.value);       // "" when not confident
  showGhostText(ghost);                                  // Tab -> input.value += ghost
});

ac.suggest(text, { ...ac.policy, tau: 0.9 });            // stricter: ~96% precision
```

Try the demo locally. It's a static page with no server code:

```bash
git lfs install
git clone https://huggingface.co/tmickleydoyle/tiny-autocomplete && cd tiny-autocomplete
bun build web/demo.ts --outfile web/demo.js --target browser   # demo.js is also committed
python3 -m http.server 8080 -d web                             # open http://localhost:8080
bun web/cli.ts "write a python fun"                            # or from the terminal
```

The demo shows the ghost text, the confidence and the latency per keystroke, the model's best
guess when it stays quiet, and a slider for the threshold.

## Use it with transformers

```python
from transformers import pipeline

gen = pipeline("text-generation", model="tmickleydoyle/tiny-autocomplete")
gen("In Python,")[0]["generated_text"]   # 'In Python, you can use the following code:'
```

`model.safetensors` is a plain `LlamaForCausalLM` (no `trust_remote_code`). Its logits are the
compiled n-gram's log-probabilities, matching the reference to within 2e-5 nats. To get the
same confidence-gated ghost text in Python, use `suggest.py` (`Suggester.suggest`).

## Performance: why compile instead of train

On a 10-core Apple Silicon laptop (32 GB RAM), CPU only, no GPU. Raw numbers are in
[`docs/benchmarks.json`](docs/benchmarks.json).

| | |
|---|---|
| Compile the browser export from text | **6.6 s** |
| Compile the 380M-parameter transformers model | **6.9 s** (peak memory 2.4 GB) |
| GPU hours / compute cost | **0 / $0** |
| Reproducible | rebuilds are byte-identical (both artifacts) |
| Browser export: load / keystroke | 51–64 ms load in Chrome (local); 0.5 ms median, 0.9 ms p95 per keystroke |
| Transformers model: next token | 58 ms (PyTorch CPU, 8 threads); 18 tokens/s greedy |

For scale: the sibling experiment [tiny-research](https://tiny-research.vercel.app/)
trained a 34M model with a 5-minute budget on an RTX 4090.

**Why build a model like this:**
- **Iteration in seconds:** edit text, recompile, and measure in under a minute.
- **Calibrated on purpose:** a suggestion only appears when the compiled probability clears a
  threshold whose precision is measured.
- **Auditable:** every neuron is one context from the source text, so any suggestion can be
  traced to the lines that produced it.
- **Editable:** delete a line and recompile to remove a behavior.
- **Deterministic and exact:** the same text always produces the same bytes.

**What it costs you:** it doesn't generalize like a trained model. Next-token top-1
accuracy on held-out prompts is 26.7% (top-3: 40.6%), and 7% of next tokens are outside the
vocabulary. That's why it only speaks when confident.

## How it works

- **The network:** the compiled network is an exact transformer implementation of an
  **interpolated Kneser-Ney 5-gram language model**. It predicts the next token from the
  current token plus the 3 before it, backing off to shorter contexts when a longer one is
  unknown.
- **Attention:** 3 heads with constant queries and keys. Their RoPE phases make each head look
  exactly 1, 2 or 3 tokens back, and each head copies that token's code into its own slot.
- **MLP:** one neuron per kept context (1–4 tokens). A neuron fires only when every token
  matches. It adds `log p(next | context) − log p(next | shorter context)` to the logits, and
  these additions telescope to the log-probability under the longest known context.
- **Browser export:** stores, for each neuron, its context tokens and the logit changes it
  writes (float32), plus the always-on unigram neuron. The runtime evaluates only the neurons
  whose context matches: the same math as the dense model, without the zeros. A test exports
  the dense model's own tables and checks the runtime against PyTorch.
- **Confidence policy** (`suggest.py`, mirrored by `web/autocomplete.ts`):
  - **Partial words:** if the user is mid-word, only words starting with the typed prefix are
    candidates. Their probability is scaled by the chance that a word with this prefix is in
    the vocabulary at all, so rare words don't trigger confident wrong completions.
  - **When to show:** only if that probability is ≥ τ.
  - **Extension:** the suggestion grows word by word while the combined probability stays
    ≥ τ, stopping at end-of-text or after `. ? ! :`.
- **Settings were benchmarked, not tuned by hand:** `scripts/sweep.py` compiled 24
  combinations and picked the one with the most keystrokes saved at ≥ 90% precision. The
  combinations varied context length (4–10 tokens), Witten-Bell vs Kneser-Ney, source weights,
  vocabulary and pruning. The weights themselves are always closed-form counts.
  - **Context length:** 4 tokens won. Longer contexts were slightly worse (22.4–22.8% saved),
    because with ~21k lines they rarely repeat.
  - **Topic head:** an experimental "topic" attention head, conditioning on the last
    language or tool name mentioned, didn't help either (`scripts/experiment_topic.py`).

Details, formulas and the proof of exactness are in [docs/how-it-works.md](docs/how-it-works.md).

## Limitations

- **Short memory and a lookup:** it sees 4 tokens and reproduces frequent patterns. It
  doesn't understand code, and it doesn't write code (code blocks were removed from the data).
- **Narrow domain:** strongest on how people *phrase requests* about code ("write a python
  function to…", "can you explain the difference between…"). It's quiet on most other text.
- **Lowercase:** input is lowercased, so ghost text is lowercase.
- **Limits:** the transformers model has 128 positions. The browser runtime has no length
  limit, but it only ever looks at the last 4 tokens.
- **Authorship:** ~1,100 everyday phrases in `phrases/` were written by an AI coding assistant
  (Claude) for this project. All coding data is human-written; see
  [data/SOURCES.md](data/SOURCES.md).

## Rebuild and verify

```bash
pip install -r requirements.txt
python scripts/fetch_coding_prompts.py   # optional: re-download data/prompts.txt, data/replies.txt
python build_weights.py                  # transformers model  ("hf" in compile_settings.json)
python export_web.py                     # browser export      ("web" + "policy")
python test_model.py                     # HF loading, exactness, TS parity, web runtime == Python == PyTorch
python scripts/sweep.py                  # re-run the settings comparison -> docs/sweep.json
python scripts/benchmark.py              # -> docs/benchmarks.json
```

Tested with transformers 4.52.4 and 5.22.1, Bun 1.3, Node 24 and Chrome.

## Licenses

The model, code and hand-written phrases are MIT. `data/prompts.txt` and `data/replies.txt`
contain excerpts from OpenAssistant oasst2 (Apache-2.0), MBPP (CC-BY-4.0) and CoNaLa (MIT); see
[data/SOURCES.md](data/SOURCES.md) for attribution.

## Files

| File | Purpose |
|---|---|
| `web/model.bin`, `web/autocomplete.ts`, `tokenizer.ts` | browser export and its runtime |
| `web/index.html`, `web/demo.ts`, `web/demo.js`, `web/cli.ts` | demo page and CLI |
| `config.json`, `generation_config.json`, `model.safetensors`, `tokenizer*.json` | transformers model |
| `build_weights.py`, `export_web.py`, `compile_settings.json` | the compiler and its settings |
| `suggest.py` | confidence policy (Python reference) |
| `phrases/*.txt`, `data/*.txt`, `data/SOURCES.md` | source text and attribution |
| `scripts/sweep.py`, `scripts/benchmark.py`, `scripts/experiment_topic.py`, `docs/*.json` | measurements |
| `test_model.py` | verification suite |
| `model.ts`, `autocomplete.ts`, `ui.ts`, `ui.html` | TypeScript runtime for the dense model, CLI and server UI |
| `docs/how-it-works.md` | full construction details |