If you are referring to what is theoretically possible with arbitrary computation in the model, it's called Kolmogorov complexity and it's not computable.
762 karma · joined May 18, 2020
I've seen lots of headlines like "1-bit quantization" (including this one and https://arxiv.org/abs/2310.16795). What I've found in this space is that the headlines can often be intentionally misleading about what is actually achieved. If you read closer the abstract of this paper, it claims 8.41 perplexity on LLaMA2-70B at 1 bit, which is a HUGE decrease from 3.120 perplexity in FP16 and they will never mention that in the headline. Even LLaMA2-7B at INT8 achieves 5.677 perplexity with half of storage place (better with LESS space and LESS training). Some claim 1.58-bit quantization (each weight is either -1, 0 or 1) but in practice require very small group sizes, which means one or two extra FP16 numbers for every 64 weights and that means another 0.5 bit, so it's actually 2-bit quantization. And every quantization algorithm can claim they make language models smaller, speedier, and use less energy, so there's nothing special about these.
Here are the key metrics that I suggest checking when comparing quantization schemes:
* Perplexity. Note that it also depends on the dataset (either WikiText2 or C4, WikiText2 numbers are usually lower than C4) and context size (1024, 2048 or 4096, higher context sizes usually means less perplexity). Dataset and context size must match to make a meaningful comparison.
* Quantization bits. Many algorithms claiming 2-bit or 1-bit quantization has lots of extra parameters elsewhere, such as grouping. Download the quantized version of the model, check its file size, multiply by 8 and divide by the number of parameters. That gets you the ACTUAL quantization bits.
* Performance. Weights may need to be dequantized during inference which could introduce overhead. Some libraries have custom matmul kernel for dequantization that achieves performance close to FP16, others can be slower. Check its generation speed and inference speed.
Newer architectures such as Ampere contains INT8 cores which may make quantized version even faster than FP16, I haven't tried out yet.
There is also a lot of misleading comparisons in this space. Some methods like GPTQ only provide vector-matrix multiplication kernels, which means only a single token can be generated and batched inference (which is needed for generating initial KV cache, or for serving multiple users) can be much slower. If an algorithm claims a 3x speedup for something, check if they refer to single stream latency or multiple stream throughput. Some of that speedup comes from running a model on 2 cards instead of 5 cards without specifying if the cards have NVLink configured (you shouldn't run inference on multiple cards without NVLink, or you should expecet huge slowdown simply because of using 5 cards).
* Base model. Pick a STRONG base model like Llama-2-7b or Llama-3-8b etc. Not an undertrained model like SwitchTransformer etc which may have lots of redundant parameters in itself.
My personal favourite remains QuIP# (https://github.com/Cornell-RelaxML/quip-sharp). It lacks in the "performance" part as its matrix multiplication performance isn't on par yet but there is room for improvement, and it wins every other metric. And sad news: it's very likely we won't have practical 1-bit LLMs, never ever. We are reaching the end game between 2.5~4 bits. By "practical" I mean it should beat 3-bit LLMs with 3x less parameters or 2-bit LLMs with half as many parameters. There is a Shannon limit to quantization whatever methods you use.
> A sports car is a car designed with an emphasis on dynamic performance, such as handling, acceleration, top speed, the thrill of driving, and racing capability.
How would lowering suspension turn a passenger bus to a sports car?
Now the question becomes why these components are built in the kernel and not in userspace? The answer is clear for each individual component. See how the in-tree NTFS driver eventually replaces NTFS-3g. Basically when an in-tree solution exists it just gets preferred over userspace solutions because of performance and reliability etc.
I'm more familiar with cryptography so the most famous problem in BQP for me is discrete logarithm. Once you have this primitive, the following things are very clear:
1. How Shor's algorithm for factorization works: it consists of a classical algorithm that reduces factorization to calculation of group order of an element (which is a special case of discrete logarithm), then uses a quantum computer to solve the group order problem. This breaks RSA.
2. Breaking elliptic cryptography: Modern elliptic cryptography constructs an elliptic curve (in the form of y^2=x^3+Ax+B) and defines multiplication on top of the points on the curve. It turns out that multiplication is very easy but discrete logarithm is hard and that hardness is used to prove that Diffie-Hellman key exchange is hard to break, but what if it's not? Moreover, elliptic curves usually only have 256~512 bits since it's sufficient to guarantee security in the classical case, compared to RSA with 2048~4096 bits. While it's harder to break elliptic curves using classical methods, it turns out to be even easier for quantum computers.
What quantum computers is NOT is a parallel computer with 2^n threads running in parallel that would collapse to the thread that gives the correct results. This would imply BQP=NP which is not known to be true and however many qubits we build it won't be any more likely to become true.
I'm not sure about the field of physics but in deep learning there are hundreds of papers published every day while no more than a percent of them tries to make the paper less mythical and instead they keep inventing buzzwords and claiming positive results to make them even more mythical
> Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list.
Why would you delete the word already on the list by flipping coins? Doesn't this reduce the accuracy by counting less words than expected? And will the word be added to the list later?
After thinking about it for a while and reading the paper, I've finally developed a good mental model for how this algorithm works as below, which should convince even a high schooler why the algorithm works:
1. You are given a streaming set of elements from [n] (a finite set of n distinct elements). Now let's give each element a random uniform real number in [0,1]. This helps us choose the elements we want: if we choose all elements with the number below 0.5, we get about half of the elements.
2. Assume for a moment we have unbounded memory. Now we maintain a table of already seen elements, and for each element we keep the last real number attached with that element: so if an element A appears three times with the number 0.3, 0.7, 0.6, we keep A with the number 0.6.
3. Our memory is bounded! So we keep only the elements below a threshold 2^-r, that is, 1, 0.5, 0.25, etc. So at first we will keep all elements, but when we don't have enough memory, we will need to filter existing elements according to the threshold. It's easy to see that when we decrease threshold, only elements already in memory will meet the criteria and continue to exist in memory. No other elements in the stream will be below threshold. Also note that whether an element is in memory depends only on its last occurence. It can exist in memory for a while, get dropped because a later element does not meet the threshold, and get back in.
4. We don't actually have a real number attached to every element! But we can pretend as if there is one. For each new element X from the stream, we replace the number in memory with its attached number, and we only care if its attached number is below 2^-r or not. If it is, it should be in our memory, and if it's not, it should be out. Once the number is in memory, it's a random number in [0,2^-r] and we care no further.
When increasing r, we only care about whether the number is in [0,2^{-r-1}]. This has exactly 1/2 probability. So each number has 1/2 probability of getting out, and 1/2 probability of being kept in memory.
5. Now it's easy to see that whether an element is in the memory depends solely on the real number attached to its last occurence. That is, each distinct element has exactly 2^-r probability of being in memory. 2^r multiplied by the number of elements in memory gives a good estimate of number of distinct elements.
They criticized previous approaches as relying on hash functions. A simplified version of the approach is as follows:
1. Make a hash function that maps distinct elements to different uniform real numbers. So all As compute to 0.3, all Bs compute to 0.7, etc.
2. Use that hash function to transform all elements. The same element maps to the same real number, and different elements map to different real numbers.
3. Keep a set of N smallest distinct real numbers. This works by inserting numbers from the stream to the set. It's easy to see that adding the same element multiple times has exactly no effect; it's either too big to be in the set or the same as an existing number in the set.
4. This gives the Nth smallest real number in the set as K. The number of distinct elements is approximated as N/K.
This algorithm is remarkable, but not in that it's efficient or it's new. Both algorithm using a hash function and algorithms without hash functions has been around and is optimal. I assume this algorithm is the first optimal algorithm without hash functions that is very easy to understand even by undergraduates.
Wondering if anyone would be surprised that a huge amount of progress in AI is on the engineering side (optimizing matmuls), and that a huge portion of the engineering is about reverse engineering NVIDIA chips
Llama-3-70b-Instruct responded with the following starting paragraph:
> [meta.llama3-70b-instruct-v1:0] As the train rumbled on, carrying its passengers through the countryside, two strangers found themselves drawn to each other in the quiet carriage. The air was thick with tension as they locked eyes, their gazes burning with a desire that neither could ignore.
(10s of paragraphs omitted for brevity)
Claude-3-opus and GPT-4 both refused my request. Kudos for open source models!
Any detail on this? For speculative decoding you need a smaller model to generate "branches" which are fast but maybe inaccurate and verify these branches later with a larger model. However, only memory equivalent to a single token is needed for speculative decoding, and tokens in other branches are simply masked out during inference. With a context size of 1000 and ~30 branches for 5 tokens, the memory overhead would be 3% which is negligible. If your context size is much smaller compared to the number of branches - would someone who use a generative LLM with a context window of just 50 tokens care about generation speed?
Also, speculative decoding techniques are not restricted to greedy sampling - it's expected to behave exactly the same as the original model and sample with the expected probabilities. Most literature on speculative decoding already reports 2.6x-3.5x speedup. The blog post here reports 2.4x-3.4x generation speed - which isn't that much of an upgrade?
While I mentioned speculative decoding above and Medusa2 and Eagle seems to be the techniques that the author compares against, the core problem remains: whatever method you use to predict tokens ahead of time, there is a specific point where the previous tokens are absolutely needed before predicting the next token. It doesn't depend on what your model is or what your techniques are, it's just about what is mathematically achievable. How can you predict 5 tokens at once if the probability distribution of the 5th next token depends heavily on the previous 4 tokens? Speculative decoding, Jacobi decoding, multi-token parallel decoding, whatever.
If only greedy sampling is supported for this, then I wonder what are the advantages of this method, not to mention that other techniques already achieve the expected speedup. Comparing greedy sampling speedups to random sampling speedups is comparing apples to oranges, and I doubt if the speedup described by the method would remain after this method is adapted to random sampling (due to the core problem mentioned above).
> AlphaFold3 can predict many biomolecules in addition to proteins. AlphaFold2 predicts structures of proteins and protein-protein complexes. AlphaFold3 can generate predictions containing proteins, DNA, RNA, ions,ligands, and chemical modifications. The new model also improves the protein complex modelling accuracy. Please refer to our paper for more information on performance improvements.
AlphaFold 2 generally produces looping “ribbon-like” predictions for disordered regions. AlphaFold3 also does this, but will occasionally output segments with secondary structure within disordered regions instead, mostly spurious alpha helices with very low confidence (pLDDT) and inconsistent position across predictions.
So the criticism towards AlphaFold 2 will likely still apply? For example, it’s more accurate for predicting structures similar to existing ones, and fails at novel patterns?
I mean Hetzner has a reputation for renting bare metal servers at the cheapest price in the market. Try AX102 which has very close performance to a M3 Max (CPU only): https://www.hetzner.com/dedicated-rootserver/matrix-ax/
While the OP's solution has a lot of advantages like being able to own the device and including GPU, but at least we do have cloud servers with comparable costs available.
I mean there is a great amount of actual work where the complexity is inevitable, say homomorphic encryption or zero-knowledge proofs, but they are based on solid foundations, starting with the definition of group theory with just four axioms and building up and so on, where every definition is either simple or has lots of uses elsewhere. In contrast, in machine learning and operating systems research, people just seem to like to build algorithms from scratch and make it look incredibly complex (whether it actually is complex) and that just makes my life harder just to read the paper. It's getting close to the point where reading the paper takes more cognitive load than conducting the research myself (having to understand 100s of papers to find the one that's useful for my case). When it does, what would be the point of publishing it?
I recognize there is a lot of useful work in academia but it's really hard to enjoy doing it when the results you would be most proud of is not likely to be well recognized.
They want you to pay for it, don't they?
What I do think would be worth it is micropayments, so for each usage you will pay just $0.2 or so. Unfortunately such a payment scheme is not practical under current Visa/Mastercard system.
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.
I mean it's great but at the current state it seems better suited for tasks where an explicit formula exists (though not known) and the goal is to predict it on unknown points (and be able to interpret the formula as a side effect). Deep learning tasks are more of a statistical nature (think models with a cross entropy loss - it's statistically predicting the frequency of different choices of the class/next token), it requires a specialized training procedure and it is designed to fit 100% rather than somewhat close (think linear algebra - it won't be good at it). It would very likely take a radically different idea to apply it to deep learning tasks. The recently updated "Author's note" also mentions this: "KANs are designed for applications where one cares about high accuracy and/or interpretability."
It's great but let's be patient before we see this improve LLM accuracy or be used elsewhere.