3 ms·

> that's no guarantee that the LLM will be able to compress it efficiently Your LLM here is 600MB which is a grossly inefficient compression of the sort space.

> that's no guarantee that the LLM will be able to compress it efficiently Your LLM here is 600MB which is a grossly inefficient compression of the sort space. If LLMs "learned algorithms", the best compression would be on the order of bytes. The python to generate this list is c. 1kb -- and you're using an obscene 600MB to do it! What do you think all those MBs are doing? They're the extraordinary cost of the "statistical shortcut" of modelling the empirical distribution of sorted numbers. NNs exploit distributional structure in the training data to compress it --- in this case there's huge amounts of distributional structure in numbers. I think you've misunderstood the "statistical parrot" claim to be somehow that NNs are engaged in wrote memorization... or, what? The claim is simply that all they do is statistically approximate the empirical distribution of the training dataset structure --- and if you force interpolation, then they provide arbitrarily precise compressions of that structure. I'm not sure what a NN which can sort numbers shows, other than the distributional structure of a sort-numbers dataset is such that a NN can compress it into 600MB... To be clear, the "statistical parrot" claim is that the statistical distribution of the empirical dataset D = (X, y) is being approximated by the weights, W = Compress(D) -- and that this distribution fails to be a representational model of y -- because no entailments of X (other than those in D) are captured. Whereas representational models are not confined to the distribution of historical cases, ie., I can imagine variations on X leading to any given y; and variations on y leading to any given X -- without ever having experienced either. You're showing the system vast amounts of numbers being sorted, so it learns the distribution of that data, so it can replay those sorts. I'm not exactly sure why you think this is a reply to the relevant claims.

jstanley 3y ago
> The python to generate this list is c. 1kb -- and you're using an obscene 600MB to do it! This isn't a fair comparison. The python code to sort a list is leveraging an enormous amount of information that is stored outside the python code, whereas the GPT version basically has to do it "from scratch", and in a very convoluted computing model. A better comparison would be "how many bits does it take to encode a configuration of NAND gates that describes a computer that can sort 127-byte lists of number 1..100?" I'm sure it's not as much as 600 megabytes, but it'll be a lot more than the python code.
- YeGoblynQueenne 3y ago
  The model the OP trained also runs on a computer. If I'm not mistaken, it also runs on Python itself. Which means you don't need to count all the bytes in the infrastructure all the way down to the electric grid, maybe. You can compare a sorting algorithm to a sorting model, as stand-alone programs, on their relative size, and that will give you a good idea of how much work each is doing.
jbay808 3y ago
> If LLMs "learned algorithms", the best compression would be on the order of bytes. Yes. Except: (1) the model size is fixed during training, it would be impossible to obtain a bytes-sized result regardless of what it learns to represent. One might even open the thing up and find bubblesort* inside followed by 599 MB of junk DNA; that size is dictated by how it was initialized. (2) I'm not claiming this model is a minimal size; I started with the biggest model I could train on my wimpy GPU and succeeded on my first and only try, which I think is a fairer representation of how GPT-4 was built than if I'd started by proving the minimum size of transformer that could represent the task** and then (surprise!) obtained it. (3) Compared with the size of a map of all 10^80 unique input lists to all 10^36 correctly-corresponding sorted outputs, 600 MB is a remarkable compression ratio, even if it's not reducing it all the way down to exec("sort(input)"). (4) Nowhere do I make any claim that transformers are minimal or even space-efficient representation of an algorithm (or a world-model); in fact, they seem quite terrible in this respect, especially compared to arbitrary code. And doubtless there are a bunch of weights that got trained to near-zero and could be trimmed to make the matrices more sparse, or quantized, which is the kind of thing people do to compress an LLM itself but I didn't bother. What transformers do seem to do very well at, despite the overhead, is the differentiability that allows them to be trained in the first place, and also the flexibility to handle different kinds of problems. I could have trained the same blank-slate starting model to one that shuffles or reverses each list, or perhaps to do one or the other depending on whether the first number is odd or even, or any number of other tasks. > You're showing the system vast amounts of numbers being sorted, so it learns the distribution of that data, so it can replay those sorts. It's almost definitely the case that every list it's tested on, and sorts 100% correctly, is a list it has never seen in training (unless it's a very short list, but I control for that). My training dataset is only about 100 MB; given the number of random lists, it's vanishingly unlikely that it's seen almost any of them, let alone the 100% of them that it is able to sort correctly. (The tests, of course, were not drawing from the validation set either; I test the model by generating new lists on the fly, because that's easy to do). > statistically approximate the empirical distribution of the training dataset structure Can you provide more details about what you mean by this distributional structure that can be compressed without a generally-correct sorting algorithm? How would you define a similarity measure between distinct random lists that allows for this kind of interpolation? * Well, probably RASP-sort, not bubblesort. Also, it would need to include definitions of things like the comparison operator between all tokens, because it doesn't have a numeric datatype built in, or even the idea of numbers as an ordered set; it has to learn all that. ** (the Weiss paper does this, and lo and behold, transformers can indeed sort).

jstanley 3y ago

> The python to generate this list is c. 1kb -- and you're using an obscene 600MB to do it! This isn't a fair comparison. The python code to sort a list is leveraging an enormous amount of information that is stored outside the python code, whereas the GPT version basically has to do it "from scratch", and in a very convoluted computing model. A better comparison would be "how many bits does it take to encode a configuration of NAND gates that describes a computer that can sort 127-byte lists of number 1..100?" I'm sure it's not as much as 600 megabytes, but it'll be a lot more than the python code.

YeGoblynQueenne 3y ago
The model the OP trained also runs on a computer. If I'm not mistaken, it also runs on Python itself. Which means you don't need to count all the bytes in the infrastructure all the way down to the electric grid, maybe. You can compare a sorting algorithm to a sorting model, as stand-alone programs, on their relative size, and that will give you a good idea of how much work each is doing.

jbay808 3y ago

> If LLMs "learned algorithms", the best compression would be on the order of bytes. Yes. Except: (1) the model size is fixed during training, it would be impossible to obtain a bytes-sized result regardless of what it learns to represent. One might even open the thing up and find bubblesort* inside followed by 599 MB of junk DNA; that size is dictated by how it was initialized. (2) I'm not claiming this model is a minimal size; I started with the biggest model I could train on my wimpy GPU and succeeded on my first and only try, which I think is a fairer representation of how GPT-4 was built than if I'd started by proving the minimum size of transformer that could represent the task** and then (surprise!) obtained it. (3) Compared with the size of a map of all 10^80 unique input lists to all 10^36 correctly-corresponding sorted outputs, 600 MB is a remarkable compression ratio, even if it's not reducing it all the way down to exec("sort(input)"). (4) Nowhere do I make any claim that transformers are minimal or even space-efficient representation of an algorithm (or a world-model); in fact, they seem quite terrible in this respect, especially compared to arbitrary code. And doubtless there are a bunch of weights that got trained to near-zero and could be trimmed to make the matrices more sparse, or quantized, which is the kind of thing people do to compress an LLM itself but I didn't bother. What transformers do seem to do very well at, despite the overhead, is the differentiability that allows them to be trained in the first place, and also the flexibility to handle different kinds of problems. I could have trained the same blank-slate starting model to one that shuffles or reverses each list, or perhaps to do one or the other depending on whether the first number is odd or even, or any number of other tasks. > You're showing the system vast amounts of numbers being sorted, so it learns the distribution of that data, so it can replay those sorts. It's almost definitely the case that every list it's tested on, and sorts 100% correctly, is a list it has never seen in training (unless it's a very short list, but I control for that). My training dataset is only about 100 MB; given the number of random lists, it's vanishingly unlikely that it's seen almost any of them, let alone the 100% of them that it is able to sort correctly. (The tests, of course, were not drawing from the validation set either; I test the model by generating new lists on the fly, because that's easy to do). > statistically approximate the empirical distribution of the training dataset structure Can you provide more details about what you mean by this distributional structure that can be compressed without a generally-correct sorting algorithm? How would you define a similarity measure between distinct random lists that allows for this kind of interpolation? * Well, probably RASP-sort, not bubblesort. Also, it would need to include definitions of things like the comparison operator between all tokens, because it doesn't have a numeric datatype built in, or even the idea of numbers as an ordered set; it has to learn all that. ** (the Weiss paper does this, and lo and behold, transformers can indeed sort).