Written by Walter Murch?? Like, the guy who is considered maybe the best editor and sound designer of all time, who was nominated for 9 Academy Awards, and won 3??? (Editing perhaps second only to Thelma Schoonmaker.)
4,235 karma · joined August 13, 2010
In essentially all cases, we have no real reason to believe or disbelieve. We choose these bounds because we can't do better. It's often the case that we later prove them wrong with some extremely strange result. Here, we have weird bounds for 3-SAT, and a few weeks ago we had one for integer multiplication.
But this has also happened repeatedly throughout history. In the 50s Kolmogorov conjectured that n-bit integer multiplication was \Omega(n^2). Karatsuba produced O(n^{1.58}) during Kolmogorov's seminar on the topic. Strassen discovered matrix multiplication is O(n^{2.81}) while trying to prove it is O(n^3). And on and on and on.
Maybe P and NP are well-formulated and they do perfectly capture our intuition of "efficient" and "efficiently verifiable" algorithms. Or maybe they don't. We are probably going to keep finding extremely weird, cheesed-out bounds for famous problems, though. You can choose what you want to believe, but I think it would be more remarkable if the reality of P and NP turned out to be as clean as the bounds indicate.
There are many ways it might turn out to be ill-posed, this is just one of them. Impagliazzo's "5 worlds" survey is in some sense a catalog of some of these ways, and includes some of the ways you seem to be referencing (approxmations, probabilistic techniques, average-case efficiency; depending what you mean this could lie in the "Heuristica" world).
This has been marginally debated since the mid 90s, when Impagliazzo published the “5 worlds” survey. Occasionally it is brought up in talks about average case analysis. There is occasionally a workshop about it. But it has never really got the attention it deserved. How many more of these results do we need to take it seriously? (Assuming we do indeed certify it.)
What is happening here is a sign they are changing their view on how this capital allocation works.
To what? We don't know, and I think they might not know yet, either. If you are spending > $4M for a top-end engineer and $8M on their tokens (this refers to a person know personally, it is not hearsay), this will necessarily change the how this allocation works. Maybe it doesn't make sense to park 300 people on tomorrow's PowerBI any more.
What is clear is that we are not in anything approaching an equilibrium state. MSFT (and others like them) clearly do not have enough conviction to fire all the line engineers and only keep the so-called "elite" ones. It's not even clear that they think we're on that trajectory. I think what we are seeing, though, is that they have enough conviction to try to clear the way for more of this kind of spending on these so-called "elite" developers.
Almost everything you'd want to say about it would spoil something interesting about the film. (This is not hearsay. I've seen it and I can't think about how to say anything meaningful about it without spoiling it.)
Go read the transcripts where the AI is “unaligned” and has some very bad impact, like encouraging kids to kill themselves. There is not some obvious piece of knowledge to remove to make it safe. You’d have to basically lobotomize the model to make those conversations impossible. People won’t use a model that’s lobotomized.
In this specific context, the point is that LLMs and MT "predict" lucid-sounding sentences that incorporate linguistic structure (syntactic and semantic) that are well beyond the predictive abilities of the Chomskyan theory of syntax (which is itself a generative model). In other words, the Chomskyan model of syntax is descriptive of much of the rich variation in real-world human language. But it is not predictive in the sense that it does not provide a constructive algorithm to emit lucid-sounding sentences (and does not attempt to, either).
Saying we understand training and deploying machine translation systems that have strong predictive (rather than descriptive) power, apparently has very little overlap with defining a formal, analyzable, mathematical model of language. Mathematician who refer to "understanding" generally mean the second thing, but the first thing is also a kind of understanding. Just messier.
Once sequenced, the thinking goes, we'll be able to do things like: explain and anticipate failures; predict what happens when you modulate the pathway an input takes on its way to becoming output; reconstruct algorithms the models have learned.
I'm not 100% sure this will work out like the mechinterp people think. If the neural representations and pathways are "clean" (organized into a a meaningful-to-humans hierarchy), it seems at least very plausible that the behaviors that AI xrisk people are worried about will mostly boil down to straightforward synthesis (i.e., mostly-linear-interpolation) of mostly-well-cataloged knowledge. And if that is true, then it does not seem hopeful that there would be a way to prevent the output they are worried about, other than just removing a bunch of the knowledge. So maybe there is no alignment solution at all.
This is not true, and it is the crux of an enormous debate we're now having across many, many fields.
Classical Chomskyan syntax (which models sentences as parse trees) has been enormously, astonishingly predictive of the rich structure in real-world human language. But we are quick to forget that we invented concepts like "words" and "noun phrases" specifically to help us analyze and predict things about human language. What LLMs and modern MT shows, definitively, is that there is another, totally separate way to describe these phenomena, which is both vastly less descriptive, and also vastly more predictive.
That these appear to trade-off is unfortunate, but it is NOT the case that we "don't understand why it works." We absolutely understand why it works, if we didn't understand we would not be able to improve these systems. What we do not have is a clean, descriptive theory that boils this down to something that is formally specifiable and analyzable. But those are different things, and this is the root of the disconnect between many communities working in and around these spaces (linguists vs computational linguists; mathematicians vs computational mathematicians; mech interp people vs empiricists).
For those following along, when this user says that attention is kernel smoothing with a "Q-K based distance function", I think (THINK!) what they're trying to say is the second part does more work than it gets credit for when we say attention is "just" a weighted average.
Both of these things are actually true. Attention is indeed "just" a weighted average (there is a proof in the paper in my original reply), AND ALSO, the Q/K are learned, and the similarity between two learned vectors suggests there is more going on than might initially be obvious. (I actually argue in the top comment that the positional information is the #1 reason why attention works, so I agree with this.)
Let's see why.
What are Q and K? The idea in the original paper was: we have some learned embeddings for our tokens, and some "context" we'd like to use to enrich those embeddings. Stuff like the positional information, context accumulated through layers, other learned stuff. So we do this enrichment, and that produces the so-called "query" (Q) and a "key" (K) vectors. Attention is STILL a weighted average, where the weights are determined by how "similar" those vectors are (this is what we're talking about when we discuss the "distance" provided by the so-called "kernel function").
Anyway the reason it's hard for me to parse this reply is because I think a lot is getting lost in the transition from a second language to English. For example, "distance" in this context means something specific, and to be precise the exponential kernel provides a similarity measurement (dot product can encode distance but generally requires fixed-length norms). Similarly, I am confused by their use of "Euclidean" distance (kernel functions do not require this, see p. 203 of the seminal Elements of Statistical Learning which provides a general construction of anisotropic distance-based kernels which is well-accepted), I'm not sure how to interpret "what you feed to the kernel is Euclidean distance" (a pairwise kernel should compute the similarity, not be fed the similarity) and so on. None of this is the end of the world, I am just having a very hard time figuring out what they meant.
[1]: https://mybiostats.files.wordpress.com/2015/03/chapter5-kern...
> because the Vaswani et al transformer (as it is described here) simply does not work until you add the most important ingredient of all: the positional encoding.
This is factually correct. The Viswani et al transformer DOES NOT WORK without positional encodings. A transformer architecture that involves (e.g.) causal masking is a different architecture. If you want to separately discuss one of those architectures I am happy to do that too.
First and most importantly, attention is, formally, kernel smoothing with a particular exponential kernel function, and if you don't believe me, you can read the paper I linked, which proves it.
Second, and less importantly: kernel smoothing absolutely, definitely does NOT require a kernel function representing Euclidean distance, and in fact the entire point of kernel smoothing is that you can pick basically any function that fits your needs. Many use cases find it helpful to have a real-valued kernel function that is positive and semidefinite, or nonnegative and integrating to 1, or whatever. Different kernel functions in these spaces have different properties and trade-offs. The exponential kernel attention uses (if memory serves) is (1) finite and nonnegative, and (2) has a positive total weight so you can normalize.
Third, and least importantly, you definitely can have a kernel function that is "uniform" (i.e., "just" an average) although it's generally not very helpful (e.g., not positive semidefinite).
I’m also not sure why you are talking about why natural languages are not different from other ones. That is what I’m saying, it’s the reason behind the comment that all parsing works the same way.
First of all, the trick relies on imputed 1NN/imputed kNN/imputed weighted kNN. And second of all, you still have to explain how imputed weighted kNN relates to the problem of taking a bunch of x/y pairs and predicting a novel y for some novel x. When you start to unpack all of that it does not look simpler to me than what I wrote.
For the weights, I'm not sure that's as mysterious as you make it seem. The most important thing they learn is, basically syntax. So you have 40k token types to choose from at each prediction, and the vast majority of them are statistically implausible because they are syntactically invalid. At some positions this restriction reduces entropy from ~15-16 bits (or 40k choices) to 2^8 (~200 choices) and in some places it reduces it "only" to 12 or 13 (~8k choices, common when the next token is "approximately a noun").
Once you winnow it down, it's much closer to a moderately big multiple choice problem. And much of that entropy lies just in the model's representation of word co-occurrences.
Aside from that, kernel smoothing has roughly 70 years of literature devoted to every practical aspect you could imagine: approximation, accuracy, pedagogy, behavior under sparsity, relationship to other well-known theories like Bayeisan learning, and so on. Variants like Performer and elliptical attention, all directly arose from the knowledge that attention is intro-grad-stats kernel smoothing. A large portion of our understanding of ICL is directly or indirectly resultant from the fact of this correspondence.