9 ms·
Infini-Gram: Scaling unbounded n-gram language models to a trillion tokens
- Genbox 2y agoA web interface for the Infini-gram engine can be found here: https://huggingface.co/spaces/liujch1998/infini-gram https://huggingface.co/spaces/liujch1998/infini-gram
- novaomnidev 2y agoThe hugging face demo site doesn't seem to work with any of the examples. It returns an error in every case.
- kmeisthax 2y agoMy current mental model of LLMs is that attention refines information from the input (e.g. "red balloon" becomes some vector that means red + balloon), and that the feed-forward layers are lossy compressed indexes into the training set. From the paper, having a better n-gram index is giving as much perplexity improvement as a 10x increase in parameters. I wonder if it would make sense to train new foundation models with more attention heads and use infinigram in lieu of the feed-forward layer.
- sigmoid10 2y agoAttention just allows the model to attend to elements across the input sequence. The feed forward is what gives it (and basically all other architectures) its universal function abilities. The only reason why we don't use dense layers directly across the input sequence and instead go for things like convolution, recursion or transformers, is because that is prohibitively expensive computationally. But replacing the dense layer with n-grams would make LLMs exactly what so many people falsely believe them to be right now: Pure stochastic parrots instead of functions that can actually learn to generalize from examples.
- Chrupiter 2y agoAren't human stochastic parrots in the end? I mean, when we "learn", don't we model our internal stochastic functions? Whether it is walking, learning a language, or anything else.
- fnordpiglet 2y agoNo, because we are able to extrapolate from our experience. The ability to synthesize something coherent that doesn’t map directly into our training set is a major difference between human intelligence and what we call AI today.
- alexeldeib 2y agoIsn’t there an argument we’re simply better at brain statistics and modeling than current AI? Forget architectural limitations. What is the nature of the extrapolation? How do individuals balance their experiences and determine likely outcomes?
- fnordpiglet 2y agoMaybe! But even so there’s facilities AI lack that are more capability based than model based. For instance we demonstrate agency, we can simulate things in our mind alone, such as arriving at Maxwells Equations, or general relativity, or any number of other profound insights that aren’t based on our training data but are an extrapolation through our mind into domains we’ve no experience with and arrive at profound insights never conceived of before. Statistical models generally aren’t able to do this - they’re reflections of their training set, even if very complex ones. The human mind can create its own training set and that’s a remarkable capability.
- strangescript 2y ago"extrapolate from our experience" "synthesize something coherent" These are non-scientific concepts. You are basically saying "humans are doing something more, but we can't really explain it". That assumption is getting weaker by the day. Our entire existence is a single, linear, time sequence data set. Am I "extrapolating from my experience" when I decide to scratch my head? No, I got a sequential data point of an "itch" and my reward programming has learned to output "scratch".
- novaRom 2y agoTL;DR we've trained n-gram model implemented in a form of suffix array on very large data set, it shows good perplexity
- throwaway81523 2y agoIs this sort of like Dissociated Press in Emacs?
- bglazer 2y agoSomewhat off-topic, but has anyone tried training a random forest at LLM scale? Like an RF with millions of trees and billions of branches? My intuition says it could be much more efficient on CPUs, provided it works at all.
- skyde 2y agoForest are good at classification but they cannot leverage pre-training on unclassified data.
- ColonelPhantom 2y agoAren't LLMs a classification problem in a sense? "Given this text, classify it based on the next token" seems like a viable interpretation of the problem. Although there are a couple thousand or so classes, which might be a lot (but I know very little about this field).
- thesz 2y agohttps://gradientdescending.com/unsupervised-random-forest-example/ https://gradientdescending.com/unsupervised-random-forest-ex... You can cluster data using unsupervised random forests and then use these cluster indices as features.
- solresol 2y agoI'm working on it, but with a loss function that penalises hypernyms/hyponyms less than other kinds of mistakes. I'm vaguely optimistic that this is going to be more efficient.
- Der_Einzige 2y agoI’ve been talking about this for years! It’s fully possible!
- tgv 2y agoWhat this shows, IMO, is that quite a lot of the expected output is almost literally present in the training data.
- flawsofar 2y agoPhrases and ideas repeat, because the universe has patterns and structure.
- tgv 2y agoBut it also suggests that the neural networks are not the miracle as some proclaim. They get their knowledge from compressing a very large amount of text, but add little in terms of inference. Its success is then a function of its size, but that size cannot grow much. It also ties in with the idea that the current ANNs don't discriminate text, and repeat bad input as readily as anything else.
- naasking 2y agoCompressing nearly all of human knowledge into a desktop PC that can converse in natural language and translate between languages is the miracle.
- tgv 2y agoIt's miraculous, but it's not nearly nearly all of human knowledge. Ask anything slightly specialist, and it'll give wrong answers. ChatGPT's translation is also not well developed. Llama doesn't have any, I believe.
- matt4711 2y agoA paper [1] we wrote in 2015 (cited by the authors) uses some more sophisticated data structures (compressed suffix trees) and Kneser–Ney smoothing to get the same "unlimited" context. I imagine with better smoothing and the same larger corpus sizes as the authors use this could improve on some of the results the authors provide. Back then neural LMs were just beginning to emerge and we briefly experimented with using one of these unlimited N-gram models for pre-training but never got any results. [1] https://aclanthology.org/D15-1288.pdf https://aclanthology.org/D15-1288.pdf
- inciampati 2y agoThe formulation of a succinct full text index as an "infinite n-gram model" is both genius in connecting with the ML literature, but also blind-eye, in that it ignores all the work on using exactly this data structure (well, the FM-index) over DNA. bwa mem is the OG ∞-gram aligner.
- jltsiren 2y agoThe idea is far older than BWA. The entire point of the Burrows-Wheeler transform is to create a compact order-k "language model" for every value of k simultaneously. And then use that for data compression. David Wheeler reportedly had the idea in the early 80s, but he rejected it as impractical. Then he tried publishing it with Michael Burrows in the early 90s, but it was rejected from the Data Compression Conference. Algorithms researchers found the BWT more interesting than data compression researchers, especially after the discovery of the FM-index in 2000. There was a lot of theoretical work done in the 2000s, and the paper mentioned by GP cites some of that. The primary application imagined for the FM-index was usually information retrieval, mostly due to the people involved. But some people considered using it for DNA sequences and started focusing on efficient construction and approximate pattern matching instead of better compression. And when sequencing technology advanced to the point where BWT-based aligners became relevant, a few of them were published almost simultaneously. And if you ask Heng Li, he gives credit to Tak-Wah Lam: https://lh3.github.io/2024/04/12/where-did-bwa-come-from https://lh3.github.io/2024/04/12/where-did-bwa-come-from
- drdeca 2y agoA few thoughts this brings to mind: 1) this reminds me of how I was thinking about “what if you tried to modify an n-gram model to incorporate a poor-man’s approximation of the copying heads found in transformer models? (one which is also based just on counting)” 2) What if you trained a model to, given a sequence of tokens, predict how many times that sequence of tokens appeared in the training set? And/or trained a model to, given a sequence of tokens, predict the length of longest suffix of it which appears in the training set. Could this be done in a way that gave a good approximation to the actual counts, while being substantially smaller? (Though, of course, this would fail to have the attribution property that they mentioned.) 3) It surprised me that they just always use the largest n such that there is a sample in the training set. My thought would have been to combine the different choices of n with some weighting. Like, if you have one example in the training set of “a b c d”, and a million examples of “b c e”, and only one or two other examples of “b c d” other than the single instance of “a b c d”, does increasing the number of samples of “b c e” (which aren’t preceded by “a”) really give no weight towards “e” rather than “d” for the next token?
- hiddencost 2y agoUnfortunately, single digit millisecond is quite slow for n-gram language models. Weighted Finite State Transducers are where they really shine; you tend to want to do massive parallel operations, and you want to do the without being bottle necked on memory access. I think these challenges make this framework challenging to adopt.
- snats 2y agoI recently wrote a writeup on bigrams and the infinigram outputs[1]. I genuinely believe that ngrams are making a comeback. For query searching it's really good. [1] https://snats.xyz/pages/articles/from_bigram_to_infinigram.html https://snats.xyz/pages/articles/from_bigram_to_infinigram.h...
- tarasglek 2y agoWould love to follow your blog but no rss
- omeze 2y agoThis is a really cool paper, reminds me of the simple exercise Karpathy goes through in his NN vid series with a bigram predictor. Looks like in practice there’s still some grounding issues when attempting to use them for instruction-tuned applications, but clever direction to explore!
- mfornet 2y agoAs I see it, this model will be able to predict “easy” to derive tokens but will no chance on “hard” tokens. For example doing a sum of random numbers. If the token you are trying to predict is not in the training data, even if similar patterns exist, this model defaults to the Neural Model. I guess then it is an aide to the neural model on filling the easy patterns.
- om8 2y agoPerplexity results are impressive. I wonder, how does combined models perform on MMLU and other problem-solving benchmarks. It can be that this infini-gram method is exactly the thing that “hacks” perplexity without adding any “understanding” to the model.
- om8 2y agoP.S. They acknowledge this: “... our preliminary experiments show that such method might not be helpful, and even harmful, to open-ended text generation tasks. During generation, ∞-gram can make odd mistakes (e.g., predicting totally irrelevant tokens) which makes the model to digress. Thus this combined model is not ready to replace neural LMs. Additional investigation is required to make inf-gram best contribute to text generation.”
- FloatArtifact 2y agoI can't help but want complex grammers for speech recognition :-). There really needs to be a hybrid between speech recognition grammar based commands and natural language for commands.
- bmc7505 2y agoIt's coming! CMUSphinx used to have something like this, and there are some [1] solutions [2] on the horizon. [1]: https://github.com/alphacep/vosk-api/issues/55 https://github.com/alphacep/vosk-api/issues/55 [2]: https://github.com/outlines-dev/outlines?tab=readme-ov-file#using-context-free-grammars-to-guide-generation https://github.com/outlines-dev/outlines?tab=readme-ov-file#...
- FloatArtifact 2y ago> It's coming! CMUSphinx used to have something like this, and there are some [1] solutions [2] on the horizon. > > [1]: https://github.com/alphacep/vosk-api/issues/55 https://github.com/alphacep/vosk-api/issues/55 > > [2]: https://github.com/outlines-dev/outlines?tab=readme-ov-file#using-context-free-grammars-to-guide-generation https://github.com/outlines-dev/outlines?tab=readme-ov-file#... It's interesting as speech recognition has become more popular than ever through services like Alexa, and other iot devices support for OS speech recognition has very little development. Don't get me started with accessibility apis either... Unfortunately most implementations (especially those that are iot focused) don't have very important features for robust speech recognition. 1. Ability to enable and disable a grammar 2. Modify grammars while the engine is loaded 3. Scoped grammars that are context-specific 4. Recognition callbacks 5. Multiple grammars active simultaneously. Unfortunately I don't think vosk api will ever support those features. I know there's a few PRs that address a few of those points but have not been merged for years. Given the criteria above there's very little open source that allows for complex grammars that's easy to run for an end user locally.
- mirekrusin 2y agoCould be used to dedup training data.
- thesz 2y agoThe paper does not cite [1], which describes prediction by partial match algorithm with unbounded context length. [1] https://www.researchgate.net/publication/2473004_Unbounded_Length_Contexts_for_PPM https://www.researchgate.net/publication/2473004_Unbounded_L... That is from 2003 and actually quite interesting. It shows, for example, that these models were applied to rather small texts, because of the presence of context with length of -1 (uniform distribution). When text is large the need for such context vanishes, but for small texts it can give an advantage.
- renonce 2y agoI think this leaves we find that explore in language models regularized (or maybe augmented?) by a n-gram model: instead of predicing next token without any external knowledge, the n-gram predictions can be added to the softmax head as a “default” prediction. The language model’s job would then be to improve the accuracy on top of the n-gram prediction. This shifts some of the language model’s job to the n-gram predictor, which relies on traditional methods and not GPUs, saving a lot of computation. EDIT: Oh so this thing takes 10TB disk space to keep an index while a LLM takes… 175GB (assuming GPT-3 in fp16). A huge resource requirement that cannot be ignored.
- DoctorOetker 2y agoSome observations: 1) If we view N gram counts as observation counts, we can generalize Norman Megill's estimation of Bernouilli probabilities to manysided dice (as many sides as token alphabet): (O+1)/(T+S) where O is the number of Occurences, T is the number of Trials and S is the Size of the alphabet or number of Sides. Having 0 observations does not result in probability of 0. 2) Since the method allows for collecting occurences in the corpus, this could be used to provide alternative language models contexts in the corpus.