What is amazing to me is this: imagine that English only had 10,000 words. For each of those 10,000 words there’s 100 valid subsequent words. So there’s 1 million valid bigrams. Now if you want trigrams that takes you to 100 million, and for 4-grams it’ll be 10 billion. Just for that, you’d need 14 bytes per word and gigabytes of storage.
LLMs typically have context windows in the hundreds if not thousands. (Back in my day GPT2 had a context window of 1024 and we called that an LLM. And we liked it.) So it’s kind of amazing that a model that can fit on a flash drive can make reasonable next token prediction on the whole internet and with a context size that can fit a whole book.
Your idea of splitting the probabilities based on whether you're starting the sentence or finishing it is interesting but you might be able to benefit from an approach that creates a "window" of text you can use for lookup, using an LCS[3] algorithm could do that. There's probably a lot of optimization you could do based on the probabilities of different sequences, I think this was the fundamental thing I was exploring in my project.
Seeing this has inspired me further to consider working on that project again at some point.
[0] https://github.com/karpathy/nanoGPT
[1] https://en.wikipedia.org/wiki/Trie
[2] https://en.wikipedia.org/wiki/N-Triples
[3] https://en.wikipedia.org/wiki/Longest_common_subsequence
What I really want is some simple predictive text engine to make writing in English easier (because its not my first language), helping me find more complex words that I don't use because I don't know them well enough.
The goal was to mimic the functionality of the stock iOS keyboard. This approach also opens up the possibility of training (or fine-tuning) the model with specialized vocabularies for various professional fields, such as law, medicine, and engineering, to predict, correct, and autocomplete domain-specific terms. I'm exploring whether this addresses a genuine need or is a solution in search of a problem.
Additionally, I'm considering integrating a comprehensive grammar correction feature directly into the keyboard. While there are existing apps with this capability, they rely on online APIs. My aim is to offer a self-contained, local model as an alternative.
Completr is a plugin that provides auto-completion functionality for obsidian.
> If it can do this in 13kb, it makes me wonder what it could do with more bytes.
Maybe I misunderstand, but is this not just the first baby steps of an LLM written in JS? "what it could do with more bytes" is surely "GPT2 in javascript"?
Your project is delightful -- thank you for sharing. I have explored this realm a bit before [0] [1], but in Python. The tool I made was for personal use, but streaming every keystroke through a network connection added a lot of unnecessary latency.
I used word surprisals (entropy) to calculate the most likely candidates, and gave a boost to words from my own writing (thus, the predictive engine was "fine-tuned" on my writing). The result is a dictionary of words with their probabilities of use. This can be applied to bigrams, too. Your project has me thinking: how could that be pruned, massively, to create the smallest possible structure. Your engine feels like the answer.
My use case is technical writing: you know what you want to say, including long words you have to repeat over again, but you want a quicker way of typing.
Barely got 1 or 2 suggestions while typing that. Am I holding it wrong?
But: The demo is not usable for me on my mobile device, the keyboard is missing a tab key.
The idea is good, though.
Markov chains have been a thing for a long time and predictive text was used before LLMs.
