Chandra Shekhara Kaushik Valmeekam, Krishna Narayanan, Dileep Kalathil, Jean-Francois Chamberland, Srinivas Shakkottai
2023 · arXiv
We provide new estimates of an asymptotic upper bound on the entropy of English using the large language model LLaMA-7B as a predictor for the next token given a window of past tokens. This estimate is significantly smaller than currently available estimates in \cite{cover1978convergent}, \cite{lutati2023focus}. A natural byproduct is an algorithm for lossless compression of English text which combines the prediction from the large language model with a lossless compression scheme. Preliminary results from limited experiments suggest that our scheme outperforms state-of-the-art text compression schemes such as BSC, ZPAQ, and paq8h.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
4 selected excerpts · 4 total mentions
You can get much better than that by taking a well-known LLM model and encoding a series of offsets from the most likely sequence of tokens, especially if you are OK with the message being slightly different. https://arxiv.org/abs/2306.04050 https://bellard.org/ts_zip/
To tease out the issues: I see the BPE algorithm as similar to Huffman coding in the way it builds the token list by creating, at any point, a token that is optimal in "compressing" the data in that it represents a commonly occuring sequence. As BPE is going to create tokens for frequent words it is going to gain over just representing over single-byte tokens like "a" or 0xb7 however you get a loss in that "a" is getting puffed up to two bytes or more. In an ordinary implementation of BPE I think the order of the token ids is not relevant so depending on how it was coded up I wouldn't depend on "lower token # = less frequent" but you don't need to leave it to chance and…
you could just sort the tokens by frequency. Then if you wanted to compress the token sequence you could use something like https://en.wikipedia.org/wiki/Golomb_coding or the algorithm used in UTF-8 encoding to use fewer bits for the more common tokens. This doesn't affect the neural network part but it would let you encode the token sequence in fewer bits than it would take otherwise. I'm not sure how it competes with more commonly used compression algorithms. On the other hand if you want to use the whole neural network to compress you can do way better https://arxiv.org/abs/2306.04050 Either using the tokens directly or the LLM you have the disadvantage that the decompressor needs a huge data structure which has been trained on a lot of text, but boy do the people in that last paper get a result way better than has been reported so far.
Two possible implementation: (1) Take your data as a stream. Use your machine learning gadget to give you the (predicted) probability for each of the possible next tokens. Then use those probability in arithmetic coding to specify which token actually came next. (2) Take your data D. Apply lossy compression to it. Store the result L := lossy(D). Also compute the residue R := D - uncompress(L). If your lossy compression is good, R will be mostly zeroes (and only a few actually differences), so it will compress well with a lossless compression algorithm. Approach (1) is a more sophisticated version of (2). None of this is anything I came up with, those approaches are well known. See eg https://arxiv.org/abs/2306.04050 and https://en.wikipedia.org/wiki/Audio_Lossless_Coding or https://ietresearch.onlinelibrary.wiley.com/doi/full/10.1049... (Probably not the best links, but something I could find quickly.)
Paper: https://arxiv.org/abs/2306.04050 > We provide new estimates of an asymptotic upper bound on the entropy of English using the large language model LLaMA-7B as a predictor for the next token given a window of past tokens. > Preliminary results from limited experiments suggest that our scheme outperforms state-of-the-art text compression schemes such as BSC, ZPAQ, and paq8h.
More from the same topics.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan +11
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.
Tom B. Brown, Benjamin Mann, Nick Ryder +28
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
Anders Sandberg, Eric Drexler, Toby Ord
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.