tiny-autocomplete / README.md
tmickleydoyle's picture
Confidence-gated ghost text for coding prompts: Kneser-Ney compile, 4.5 MB browser export + zero-dep runtime, held-out precision/keystrokes-saved benchmarks
4113449 verified
|
Raw History Blame Contribute Delete
11.7 kB
---
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 |