4 ms·

>we confirm this result empirically through billions of collision tests on six state-of-the-art language models, and observe no collisions This sounds like a m

>we confirm this result empirically through billions of collision tests on six state-of-the-art language models, and observe no collisions This sounds like a mistake. They used (among others) GPT2, which has pretty big space vectors. They also kind of arbitrarily define a collision threshold as an l2 distance smaller than 10^-6 for two vectors. Since the outputs are normalized, that corresponds to a ridiculously tiny patch on the surface of the unit sphere. Just intuitively, in such a high dimensional space, two random vectors are basically orthogonal. I would expect the chance of two inputs to map to the same output under these constraints to be astronomically small (like less than one in 10^10000 or something). Even worse than your chances of finding a hash collision in sha256. Their claim certainly does not sound like something you could verify by testing a few billion examples. Although I'd love to see a detailed calculation. The paper is certainly missing one.

sebastianmestre 1y ago
I think that the latent space that GPT-2 uses has 768 dimensions (i.e. embedding vectors have that many components).
- sigmoid10 1y ago
  It doesn't really matter which vector you are looking at, since they are using a tiny constraint in a high dimensional continuous space. There's gotta be an unfathomable amount of vectors you can fit in there. Certainly more than a few billion.
  - sebastianmestre 1y ago
    No, yeah, totally. Even assuming binary vectors 2^768 is a ridiculously huge number. The probability of collision even assuming a bad sampling that discards 75% of dimensions is still vanishingly small.
gnfargbl 1y ago
The nature of high-dimensional spaces kind of intuitively supports the argument for invertability though, no? In the sense that: > I would expect the chance of two inputs to map to the same output under these constraints to be astronomically small.
- sigmoid10 1y ago
  That would be purely statistic and not based on any algorithmic insight. In fact for hash functions it is quite a common problem that this exact assumption does not hold in the end, even though you might assume so for any "real" scenarios.
  - gnfargbl 1y ago
    I'm not quite getting your point. Are you saying that their definition of "collision" is completely arbitrary (agreed), or that they didn't use enough data points to draw any conclusions because there could be some unknown algorithmic effect that could eventually cause collisions, or something else?
    - rowanG077 1y ago
      I think they are saying that there is no proof of being injective. The argument with the hash is essentially saying, doing the same experiment with a hash would yield a similar result, yet hash function are not injective by definition. So from this experimental result you cannot conclude language models are injective. That's not really formally true, there are so called perfect hash functions that are injective over a certain domain, but in most parlance hashing is not considered injective.
      - gnfargbl 1y ago
        Sure, but the paper doesn't claim absolute injectivity. It claims injectivity for practical purposes ("almost surely injective"). That's the same standard to which we hold hash functions -- most of us would consider it reasonable to index an object store with SHA256.
Arnt 1y ago
As I read it, what they did there was a sanity-check by trusting the birthday paradox. Kind of: "If you get orthogonal vectors due to mere chance once, that's okay, but you try it billions of times and still get orthogonal vectors every time, mere chance seems a very unlikely explanation."
- fn-mote 1y ago
  Edit: there are other clarifications, eg authors on X, so this comment is irrelevant. The birthday paradox relies on there being a small number of possible birthdays (365-366). There are not a small number of dimensions being used in the LLM. The GP argument makes sense to me.
  - hiisukun 1y ago
    It doesn't need a small number -- rather it relies on you being able to find a pairing amongst any of your candidates, rather than find a pairing for a specific birthday. That's the paradoxical part: the number of potential pairings for a very small number of people is much higher than one might think, and so for 365 options (in the birthday example) you can get even chances with far fewer than 365, and even far fewer than ½x365 people..
    - throwaway127482 1y ago
      I think you're misunderstanding. If you have an extremely large number like 2^256 you will almost certainly never find two people with the same birthday (this is why a SHA256 collision has never been found). That's what the top-level comment was comparing this to.
    - gowld 1y ago
      We're not using precise numbers here, but a large number of dimensions leads a very large number of options. 365 is only about 19^2, but 2^100 is astronomically larger than 10^9
  - Thorrez 1y ago
    The birthday paradox equation is approximately the square root. You expect to find a collision in 365 possibilities in ~sqrt(365) = ~19 tries. You expect to find a collision in 2^256 possibilities in ~sqrt(2^256) = ~2^128 tries. You expect to find a collision in 10^10000 possibilities in ~sqrt(10^10000) = ~10^5000 tries.
vitus 1y ago
I envy your intuition about high-dimensional spaces, as I have none (other than "here lies dragons"). (I think your intuition is broadly correct, seeing as billions of collision tests feels quite inadequate given the size of the space.) > Just intuitively, in such a high dimensional space, two random vectors are basically orthogonal. What's the intuition here? Law of large numbers? And how is orthogonality related to distance? Expansion of |a-b|^2 = |a|^2 + |b|^2 - 2<a,b> = 2 - 2<a,b> which is roughly 2 if the unit vectors are basically orthogonal? > Since the outputs are normalized, that corresponds to a ridiculously tiny patch on the surface of the unit sphere. Since the outputs are normalized, that corresponds to a ridiculously tiny patch on the surface of the unit sphere. I also have no intuition regarding the surface of the unit sphere in high-dimensional vector spaces. I believe it vanishes. I suppose this patch also vanishes in terms of area. But what's the relative rate of those terms going to zero?
- bonzini 1y ago
  > What's the intuition here? Law of large numbers? For unit vectors the cosine of the angle between them is a1*b1+a2*b2+...+an*bn. Each of the terms has mean 0 and when you sum many of them the sum concentrates closer and closer to 0 (intuitively the positive and negative terms will tend to cancel out, and in fact the standard deviation is 1/√n).
- setopt 1y ago
  > > Just intuitively, in such a high dimensional space, two random vectors are basically orthogonal. > What's the intuition here? Law of large numbers? Imagine for simplicity that we consider only vectors pointing parallel/antiparallel to coordinate axes. - In 1D, you have two possibilities: {+e_x, -e_x}. So if you pick two random vectors from this set, the probability of getting something orthogonal is 0. - In 2D, you have four possibilities: {±e_x, ±e_y}. If we pick one random vector and get e.g. +e_x, then picking another one randomly from the set has a 50% chance of getting something orthogonal (±e_y are 2/4 possibilities). Same for other choices of the first vector. - In 3D, you have six possibilities: {±e_x, ±e_y, ±e_z}. Repeat the same experiment, and you'll find a 66.7% chance of getting something orthogonal. - In the limit of ND, you can see that the chance of getting something orthogonal is 1 - 1/N, which tends to 100% as N becomes large. Now, this discretization is a simplification of course, but I think it gets the intuition right.
deleted 1y ago
[deleted]
etatoby 1y ago
> Just intuitively, in such a high dimensional space, two random vectors are basically orthogonal. Which, incidentally, is the main reason why deep learning and LLM are effective in the first place. A vector of a few thousands dimensions would be woefully inadequate to represent all of human knowledge, if not for the fact that it works as the projection of a much higher, potentially infinite-dimensional vector representing all possible knowledge. The smaller-sized one works in practice as a projection, precisely because any two such vectors are almost always orthogonal.
- ahartmetz 1y ago
  Two random vectors are almost always neither collinear nor orthogonal. So what you mean is either "not collinear", which is a trivial statement, or something like "their dot product is much smaller than abs(length(vecA) * length(vecB))", which is probably interesting but still not very clear.
  - empiricus 1y ago
    Well, the actual interesting part is that when the vector dimension grows then random vectors will become almost orthogonal. smth smth exponential number of almost orthogonal vectors. this is probably the most important reason why text embedding is working. you take some structure from a 10^6 dimension, and project it to 10^3 dimension, and you can still keep the distances between all vectors.

sebastianmestre 1y ago

I think that the latent space that GPT-2 uses has 768 dimensions (i.e. embedding vectors have that many components).

sigmoid10 1y ago
It doesn't really matter which vector you are looking at, since they are using a tiny constraint in a high dimensional continuous space. There's gotta be an unfathomable amount of vectors you can fit in there. Certainly more than a few billion.
- sebastianmestre 1y ago
  No, yeah, totally. Even assuming binary vectors 2^768 is a ridiculously huge number. The probability of collision even assuming a bad sampling that discards 75% of dimensions is still vanishingly small.

gnfargbl 1y ago

The nature of high-dimensional spaces kind of intuitively supports the argument for invertability though, no? In the sense that: > I would expect the chance of two inputs to map to the same output under these constraints to be astronomically small.

sigmoid10 1y ago
That would be purely statistic and not based on any algorithmic insight. In fact for hash functions it is quite a common problem that this exact assumption does not hold in the end, even though you might assume so for any "real" scenarios.
- gnfargbl 1y ago
  I'm not quite getting your point. Are you saying that their definition of "collision" is completely arbitrary (agreed), or that they didn't use enough data points to draw any conclusions because there could be some unknown algorithmic effect that could eventually cause collisions, or something else?
  - rowanG077 1y ago
    I think they are saying that there is no proof of being injective. The argument with the hash is essentially saying, doing the same experiment with a hash would yield a similar result, yet hash function are not injective by definition. So from this experimental result you cannot conclude language models are injective. That's not really formally true, there are so called perfect hash functions that are injective over a certain domain, but in most parlance hashing is not considered injective.
    - gnfargbl 1y ago
      Sure, but the paper doesn't claim absolute injectivity. It claims injectivity for practical purposes ("almost surely injective"). That's the same standard to which we hold hash functions -- most of us would consider it reasonable to index an object store with SHA256.

Arnt 1y ago

As I read it, what they did there was a sanity-check by trusting the birthday paradox. Kind of: "If you get orthogonal vectors due to mere chance once, that's okay, but you try it billions of times and still get orthogonal vectors every time, mere chance seems a very unlikely explanation."

fn-mote 1y ago
Edit: there are other clarifications, eg authors on X, so this comment is irrelevant. The birthday paradox relies on there being a small number of possible birthdays (365-366). There are not a small number of dimensions being used in the LLM. The GP argument makes sense to me.
- hiisukun 1y ago
  It doesn't need a small number -- rather it relies on you being able to find a pairing amongst any of your candidates, rather than find a pairing for a specific birthday. That's the paradoxical part: the number of potential pairings for a very small number of people is much higher than one might think, and so for 365 options (in the birthday example) you can get even chances with far fewer than 365, and even far fewer than ½x365 people..
  - throwaway127482 1y ago
    I think you're misunderstanding. If you have an extremely large number like 2^256 you will almost certainly never find two people with the same birthday (this is why a SHA256 collision has never been found). That's what the top-level comment was comparing this to.
  - gowld 1y ago
    We're not using precise numbers here, but a large number of dimensions leads a very large number of options. 365 is only about 19^2, but 2^100 is astronomically larger than 10^9
- Thorrez 1y ago
  The birthday paradox equation is approximately the square root. You expect to find a collision in 365 possibilities in ~sqrt(365) = ~19 tries. You expect to find a collision in 2^256 possibilities in ~sqrt(2^256) = ~2^128 tries. You expect to find a collision in 10^10000 possibilities in ~sqrt(10^10000) = ~10^5000 tries.

vitus 1y ago

I envy your intuition about high-dimensional spaces, as I have none (other than "here lies dragons"). (I think your intuition is broadly correct, seeing as billions of collision tests feels quite inadequate given the size of the space.) > Just intuitively, in such a high dimensional space, two random vectors are basically orthogonal. What's the intuition here? Law of large numbers? And how is orthogonality related to distance? Expansion of |a-b|^2 = |a|^2 + |b|^2 - 2<a,b> = 2 - 2<a,b> which is roughly 2 if the unit vectors are basically orthogonal? > Since the outputs are normalized, that corresponds to a ridiculously tiny patch on the surface of the unit sphere. Since the outputs are normalized, that corresponds to a ridiculously tiny patch on the surface of the unit sphere. I also have no intuition regarding the surface of the unit sphere in high-dimensional vector spaces. I believe it vanishes. I suppose this patch also vanishes in terms of area. But what's the relative rate of those terms going to zero?

bonzini 1y ago
> What's the intuition here? Law of large numbers? For unit vectors the cosine of the angle between them is a1*b1+a2*b2+...+an*bn. Each of the terms has mean 0 and when you sum many of them the sum concentrates closer and closer to 0 (intuitively the positive and negative terms will tend to cancel out, and in fact the standard deviation is 1/√n).
setopt 1y ago
> > Just intuitively, in such a high dimensional space, two random vectors are basically orthogonal. > What's the intuition here? Law of large numbers? Imagine for simplicity that we consider only vectors pointing parallel/antiparallel to coordinate axes. - In 1D, you have two possibilities: {+e_x, -e_x}. So if you pick two random vectors from this set, the probability of getting something orthogonal is 0. - In 2D, you have four possibilities: {±e_x, ±e_y}. If we pick one random vector and get e.g. +e_x, then picking another one randomly from the set has a 50% chance of getting something orthogonal (±e_y are 2/4 possibilities). Same for other choices of the first vector. - In 3D, you have six possibilities: {±e_x, ±e_y, ±e_z}. Repeat the same experiment, and you'll find a 66.7% chance of getting something orthogonal. - In the limit of ND, you can see that the chance of getting something orthogonal is 1 - 1/N, which tends to 100% as N becomes large. Now, this discretization is a simplification of course, but I think it gets the intuition right.

deleted 1y ago

[deleted]

etatoby 1y ago

> Just intuitively, in such a high dimensional space, two random vectors are basically orthogonal. Which, incidentally, is the main reason why deep learning and LLM are effective in the first place. A vector of a few thousands dimensions would be woefully inadequate to represent all of human knowledge, if not for the fact that it works as the projection of a much higher, potentially infinite-dimensional vector representing all possible knowledge. The smaller-sized one works in practice as a projection, precisely because any two such vectors are almost always orthogonal.

ahartmetz 1y ago
Two random vectors are almost always neither collinear nor orthogonal. So what you mean is either "not collinear", which is a trivial statement, or something like "their dot product is much smaller than abs(length(vecA) * length(vecB))", which is probably interesting but still not very clear.
- empiricus 1y ago
  Well, the actual interesting part is that when the vector dimension grows then random vectors will become almost orthogonal. smth smth exponential number of almost orthogonal vectors. this is probably the most important reason why text embedding is working. you take some structure from a 10^6 dimension, and project it to 10^3 dimension, and you can still keep the distances between all vectors.