9 ms·

The New XOR Problem

199 points by yeesian 4y ago

yarg 4y ago
What about recurrency?
- shawntan 4y ago
  Recurrency will help, see the empirical results in this paper: https://arxiv.org/abs/2207.02098 https://arxiv.org/abs/2207.02098. LSTMs can solve the PARITY problem, generalising to longer lengths of the problem without issue. The issue with re-introducing recurrency is that no one wants to bear the O(N) growth in computation time. I wonder if we are settling in for a local-optima of bounded-depth architecture for a while due to the obsession with rapid scaling.
  - yarg 4y ago
    You don't necessarily need to move to depth N, just because you went recurrent. You can probably design a modular network that can implement the logarithmic version.
    - shawntan 4y ago
      I guess I should say the recurrence growing as a function of the input size is something people don't seem to be willing to afford, not specifically the linear dependence. Not to mention parity here is a toy problem to highlight the issue, but there can be other problems that require recurrence linear or quadratic in the size of the input.
      - yarg 4y ago
        Sure, but a toy problem that's substitutable for many other functions. In this case you could substitute the XOR function for any other merge function. As far as the variable depth is concerned, utilisation is an issue that introduces additional complexity, but otherwise I don't see the problem. (No one's expecting fixed compute time for differently sized data elements.) You can get around that one by building a log(n) threaded pipeline for your log(n) depth network (something like this: https://imgur.com/a/xL4rhFu https://imgur.com/a/xL4rhFu).
  - _0ffh 3y ago
    The RWKV people seem to have adapted a recursive model so it can be trained in a special parallel mode like attention. https://github.com/BlinkDL/RWKV-LM https://github.com/BlinkDL/RWKV-LM
    - shawntan 3y ago
      Yeah I really like this project, and I've been meaning to dive into it.
- mturmon 3y ago
  Reasonable point - in the case of parity, one bit of recurrent state avoids the combinatorial issues mentioned in OP (as OP more or less says in writing the finite state automaton). It's interesting to think about parity in relation to the image classification tasks that sparked the ANN renaissance. In image classification, the class does not strongly depend on a single feature - you don't change from cat to dog by altering one pixel, and then back to cat by altering a different pixel. But parity does depend strongly on each bit in the input. I think it's important to keep this special aspect of the parity problem in mind when thinking about good architectures for various applications.
  - yarg 3y ago
    As I noted elsewhere, the structure's not specific to parity/XOR but works on n-ary merge operations in general. It will impact the breadth and depth required for the module; the {2, 2, 1} module structure required for XOR is not generally useful - but it's a substitutable component. A bigger problem is keeping your processor fed with the decaying layer size (you'll want to target a fixed wave size if you're running on a GPU, mostly empty waves are a bad thing), but you can get around that reasonably easily (at least for base-2).
krackers 4y ago
For the PARITY problem mentioned here, I recall from undergrad cs theory that there are some pretty neat provable lower-bounds on arithmetic circuit complexity, e.g. parity is not in AC0 (bounded-depth, unlimited fan-in logic gates) circuits. Even providing more computational power via mod p gates still really doesn't buy you much: Razborov-Smolensky theorem shows that even adding mod-p gates you still can't compute modulo q, for p and q being distinct primes. See also https://blog.computationalcomplexity.org/2023/02/why-cant-little-chatty-do-math.html https://blog.computationalcomplexity.org/2023/02/why-cant-li... for more discussion of LLMs from a circuit-complexity perspective.
- shawntan 4y ago
  There's more detailed examination of Transformers from circuit complexity in this paper: https://arxiv.org/abs/2106.16213 https://arxiv.org/abs/2106.16213 There are a few references also in the blog post.
  - krackers 4y ago
    Thank you! I'd love more articles analyzing LLMs from a circuit-complexity perspective! Also seems modeling the transformer as in the TC0 class, in principle it should be able to do division and multiplication of numbers.
tempodox 4y ago
> A large issue was in not managing expectations when it came to AI, and we’ve had 2 cycles to learn that hype trains can maglev themselves into a 10-year ditch. With all the hype around language models I don't get the impression that this lesson has been learned particularly well. All those proponents of “AI” remind me more and more of used-car salesmen.
- jiggawatts 4y ago
  The difference is that people are actually paying for ChatGPT because it is immediately useful for day-to-day work tasks. As a random example, ChatGPT 4 is noticeably better at grammar checking than Microsoft Word. If I feed it a couple of paragraphs of text, it'll spot several small errors that Word can't. I don't bother sending documents for internal review any more, I just get the AI to do it in seconds!
  - fhd2 4y ago
    Wouldn't it potentially leak everything you send it? ChatGPT that is, I heard with the API it's different.
    - camel-cdr 4y ago
      So does any non self hosted grammar checker.
      - eru 4y ago
        Unless you personally host it yourself, that's maybe true. If someone else in your company hosts it, they are only bound by contracts. You can also use contracts to bind other companies, when you aren't self-hosting.
    - jiggawatts 4y ago
      It's no worse than using, say, Microsoft Teams or Microsoft 365. I also make sure not to paste anything sensitive into it. The kind of thing I've find it to be useful for is massaging the one-paragraph intros to be more readable. For example, Microsoft docs tend to use the word "you", which doesn't fit into certain styles of design documents. I used to have to rewrite the product overview paragraphs myself to clean them up, now I just ask ChatGPT to do it.
espadrine 4y ago
While there is some mention of chain-of-thought prompting, the idea of chain-of-thought can go further, and can actually solve the problem exactly. The LLM can produce working code (or broken code that it can fix from reading the errors), which, when paired with a sandbox, can give the result of the computation back to the LLM. The direction things are going is one where some tokens output by the LLM are hidden, just like human thoughts. That is what Bing Chat is doing, for instance.
- shawntan 4y ago
  Yea this is a good solution so long as the task that needs to be outsourced to, say a python interpreter, is explicitly known and can be prompt engineered.
- rain1 4y ago
  But then it's an LLM augmented with a tool that is solving the problem, and not the LLM itself.
  - espadrine 4y ago
    The transformer neural network itself only computes the next token probabilities; the sampling of the token, and the mechanism by which the token it generates is concatenated to the input to make it generate the token after, are technically not part of the LLM. So we can either study the LLM strictly from single-token outputs, or from how it combines into larger constructs. The former excludes not just CoT, but a large part of the benchmarks on which they are tested. Looking at it another way, how would humans solve PARITY? I don’t think anyone would read the string, close their eyes, then give an answer without a single thought. At the very least, I would place my finger on each digit successively, effectively using a tool that acts as a memory storage (storing a cursor through the string). The reason I would do that, is that I would have devised an algorithm that requires going through digits one at a time.
  - magicalhippo 4y ago
    And? Our brains aren't just doing the exact same things all over, we have centers focused on certain tasks. For example we have[1] neurons that do addition and some others that do subtraction. Our brains are limited to using neurons as building blocks, but why should an AI be limited in the same way? [1]: https://www.sciencedaily.com/releases/2022/02/220214121241.htm https://www.sciencedaily.com/releases/2022/02/220214121241.h...
smeagull 4y ago
Any problem is solvable with two layers. The first layer consists of 1 node per input pattern, with activation and weights such that only one node is active that matches the pattern. And a second layer of weights that provides the output per input pattern.
- aezart 3y ago
  True but not very useful. That's like writing an "isPrime" function with a switch statement for every possible input number, rather than coming up with a general algorithm. It can't give you any answer you don't already know.
shawntan 4y ago
I'm the original author of this blogpost. I've had discussions that range from "we need to fix this" to "maybe human thought isn't Turing complete..." and I'm interested in hearing what yall think about the topic. P.S. I'm graduating soon and looking for research scientist roles.
- abetusk 4y ago
  My apologies, I've only skimmed, but maybe this encapsulates the main idea of your post? """ How MLPs could be trained was an open problem at the time, I think, but the field could easily have chugged along and we’d have been where we are now, just 30 years earlier. """ The main idea here is that we got an AI winter because expectations were too high and the reality didn't meet them? I think this is fundamentally missing why we're making rapid progress now. In my opinion, the AI winter wasn't primarily because of a backlash against overhyped promises, it was because computation just wasn't there. We're just now starting to get access to the compute and storage needed, at a price point that's reasonable, to make progress in these areas. In other words, the AI winter came about because the ground wasn't fertile. Now that we have economic massive computational resources, we're in an AI spring. As a back of the envelope calculation, the human brain is estimated at around 2.5 Pb of storage [0]. At today's prices, that works out to about $50k. The cost of 2.5Pb of storage in 1969 was around $675B [1]. [0] https://www.scientificamerican.com/article/what-is-the-memory-capacity/ https://www.scientificamerican.com/article/what-is-the-memor... [1] https://ourworldindata.org/grapher/historical-cost-of-computer-memory-and-storage?country=~OWID_WRL https://ourworldindata.org/grapher/historical-cost-of-comput...
  - BlueTemplar 3y ago
    I had the same thought : what would it have cost to make one of those early deep neural networks that restarted the field, but without hardware virtualization : with the same kind of physical neurons than the Perceptron, but with better tech, say mid-AI winter?
  - emmelaich 3y ago
    Agree so much that I had assumed this was the standard common view.
rain1 4y ago
I've experimented with this problem a bit https://github.com/rain-1/gpt-incontextlearning-experiments/tree/main/problem%206%20-%20parity https://github.com/rain-1/gpt-incontextlearning-experiments/... - the results were that they can kind of do it, but they do go off the rails fairly easily and get wrong answers.
IanCal 4y ago
> I’ve attempted this prompt several different ways on ChatGPT without a working solution, but I imagine this could work. I've tried a couple of things, it seems OK with a basic approach but starts falling apart when you get close to 50 bits. A more interesting merge approach looks OK at 50 with some quick testing. What sort of scale do you mean when you talk about a working solution? Edit - stats may not be holding up the merge approach at 50. It's close, sometimes getting it right or being one out.
YeGoblynQueenne 3y ago
>> All this to say: I think there are fundamentals we need to view all of this progress through. Lower-bound complexities of problems that we learn in Algorithms 101 shouldn’t get thrown out the window because linear algebra, ReLUs and attention mechanisms are involved. Sorting, for example, has a provable lower-bound complexity of Ω(NlogN). When someone tells you there is a way to do it in O(logN) time, it’s best to squint and ask a few questions. When someone tells you you can gain a speed-up in computing primes, on a naive algorithm, it’s best to ask if that method also has correctness covered. Keep this thought please. There is a very obvious feeling that "now we have LLMs we don't need CS anymore", or don't need maths, science, knowledge... In fact, this goes rather further back than Transformers. I was just reading this old interview of Vladimir Vapnik [1], where he's taking the position that only the "easy" questions in science have explanatory answers, and that for the "hard questions" we can only hope to build predictive models. Vapnik is one of my herores of AI, but on that I think he's not just wrong, but pointing the way to a new dark ages, where we lose the little knowledge we have. Similar "intuitions" are expressed in the "Bitter Lesson" blogpost by Rich sutton [2]. Vapnik is right, of course, in that there are "hard" questions for which we don't know any good answers, and our current framework may not be enough to give any simple, explanatory answer anyway. Certainly, CS is full of bottomless pits of despair, undecidabilities, incompletenesses and intractabilities. I think that just says we're shit at creating formal frameworks. All the ones we've created have some flaw. Arithmetic is incomplete. Logic (even first-order logic) is undecidable. You can't divide by 0, there are tons of calculations that cannot be performed because they sink into uncountable infinities after two steps, etc etc and so on. We just suck at making universal abstractions, that are useful in the first instance, but don't end up painting ourselves into a corner, somewhere down the line. Well, so what? So far we've done pretty well in terms of science, in the sense of understanding the world and how it works. We're not going to give up now! If our tools are not good enough to take our knowledge to the next level, well, then, we just need to make better tools. Better maths. Better Computer Science. Better scientific methods. That has happened in the past at least once, if not many many times. Why can we not do it again? Why do we have to abandon our fate to unknowing, all-predicting machines? That doesn't make sense. ______________ [1] http://www.learningtheory.org/learning-has-just-started-an-interview-with-prof-vladimir-vapnik/ http://www.learningtheory.org/learning-has-just-started-an-i... [2] http://incompleteideas.net/IncIdeas/BitterLesson.html http://incompleteideas.net/IncIdeas/BitterLesson.html
SeanLuke 3y ago
NXOR is normally called Equal, is it not?
- shawntan 3y ago
  Yeah it is. I've only learned it while looking up material for this post. I figured people know NAND is NOT(AND(.)), so NXOR might be more familiar counterpart to XOR.
jostmey 3y ago
After reading this article, my reaction is that yes, transformers are not the optimal model for NLP and reasoning, but transformers are good enough and scale really well on current GPU hardware. Going forward, I think hardware is the constraint upon which new architectures will need to accommodate
klik99 3y ago
It occurs to me that LLM have the exact opposite strengths and weaknesses of traditional computing - where trad comp is good at hard calculation and storage and bad at soft interpretive, LLMs are good at soft interpreting but bad at anything that requires runtime state storage. It seems like we’re going to plateau and see incremental improvements in AI and will take a novel technique to bridge that gap. This isn’t a new idea of course, but as someone with only light AI knowledge this article helped me understand why that is
- retrac 3y ago
  Similar idea has occurred to me. In a lot of ways, 'traditional' rules-based AI has more 'understanding' than a LLM can have. Because those rules are fixed by humans to the machine's inputs, and they create a relationship between the software's model and reality, and usually in human-understandable terms (a database entry on a specific person with their facts listed, for example). That doesn't really exist in a LLM. It's entirely self-referential to itself. Which is why it's not possible for it to explain its reasoning, or give a (real) source for a fact. There is no fixed anchor, no reference point, to validate the LLM's output with.
phkahler 3y ago
>> The key takeaway? Depth is important for certain functions. I thought the key takeaway is that nonlinearity is important. Multilayer perceptrons can be collapsed into an equivalent single layer if there isn't nonlinearity thrown in. multi-input XOR can be solved using a form of sin(x) function after summing in a single layer (sin squared if you don't like negative numbers). Upon reading this I also kept thinking "why not use the same transformer weights on each later?" and then the author goes there with the Universal Transformer concept. How many iterations should one use? Why should that be a question at all? As humans we might need to "think about it for a while" and get back to you when we figure it out. One thing all this AI research keeps ignoring is that real biological neurons are running in real time, not some batch process. We might also be doing training and inference at the same time, but I'm not certain how much - see dreams and other forms of background or delayed processing.
- shawntan 3y ago
  > I thought the key takeaway is that nonlinearity is important. Multilayer perceptrons can be collapsed into an equivalent single layer if there isn't nonlinearity thrown in. multi-input XOR can be solved using a form of sin(x) function after summing in a single layer (sin squared if you don't like negative numbers). Some element of this is used in this paper: https://arxiv.org/pdf/2202.12172.pdf https://arxiv.org/pdf/2202.12172.pdf More broadly, as I've alluded to in other replies, XOR is not the problem in itself, but illustrates a bigger problem. Yes, non-linearities can solve problems, but one hidden layer and the wrong non-linearity (sigmoid instead of sin in this case) may not. Which leads us to the question: What do we include in the broad set we label "non-linearities"? All Turing-complete functions? (This issue is alluded to here: https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493/112604/Saturated-Transformers-are-Constant-Depth https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493...) Then we're back to analysing the computability of a given non-linearity, which in itself has multiple steps of iteration. It's turtles all the way down.
  - phkahler 3y ago
    >> What do we include in the broad set we label "non-linearities"? Recursion/iterarion/thinking time.
danbruc 3y ago
This is how I imagine the human brain works. In principle we think iteratively, do one small computation, memorize the result, then do the next step based on the input and the result from the previous step. If things get too complicated, we grab some paper and write down intermediate results on external storage. But fundamentally we memorize some raw facts and otherwise learn algorithms that allow us doing new things by combining existing abilities. Ignoring memory limitations humans are Turing-complete. As we repeatedly solve similar tasks, we develop optimizations, the brain learns to perform a couple of steps in one go instead of going through all the individual steps. When children learn to read, to write or to do math, they learn to do it in small steps, they draw and recognize letters and numbers by looking at and drawing individual lines and circles. When they learn to draw lines or circles they first make very deliberate movements with the pen - up, down, left, right - before drawing a circle becomes a primitive. When they learn to add, they break numbers down into digits and only memorize how to add those, larger numbers are added iteratively digit by digit. With time and practice the brain learns to do many of those things in one step, you read and write letters or words, not deliberately draw individual strokes. You will still fall back to this if you have to deal with characters from a unknown alphabet. You will no longer perform additions digit by digit for small or commonly used numbers but you will fall back to this for big numbers. When you learn to drive, you first very deliberately look at traffic signs, think about turning the steering wheel this way or that way while parking or think about switching on the turn signals. Again with practice many of those things become automatic and you no longer have to think about them. So overall I think the brain is just following sequential algorithms, combining primitives into more complex result. Then with practice common tasks get reimplemented in some kind of fixed function unit that can do a specific task - maybe under some limited circumstances and maybe only approximately - in one step and this can then be used as a new primitive where appropriate. Actually those fixed function units could internally use iteration but this iterative process would be hidden from the primary loop. Language models like ChatGPT seem to be more on the fixed function side, they see a set of tokens and spit out a response. The attention mechanism has some similarity with a loop executing an algorithm step by step, it just has a fixed number of iterations and has been unrolled. When prompted to reason in steps, this adds another loop with additional storage for intermediate results. The difference is that this process is externally visible and that the model must be instructed to do so instead of the model deciding on its own to solve the problem in steps and hiding those steps from the outside. For questions like adding or multiplying numbers or finding the parity of some long bit string the model has some neurons that could directly provide an answer and the answer will probably be correct for simple tasks but the longer the input the more likely it becomes that those neurons will not produce the correct answer. And the model does not know in which region those neurons can be trusted. But the model also knows the underlying algorithm to solve the task, say computing the parity of a long bit string or adding large numbers, and where the steps only involve computations that the model can perform correctly, i.e. adding two digits or XORing two bits. So you can get the correct result out of a model like ChatGPT if you can make it follow the iterative algorithm instead of it trying to give the sum of two 20 digit numbers directly. And I would guess you could - at least to some extend - use ChatGPT itself to rewrite and iteratively solve harder problems. The primary obstacle is probably that it is hard to tell what tasks the model can reliably perform correctly and what tasks must be broken down further.
exabrial 3y ago
side note: What a beautiful blog. Clean design. Great graphics. More importantly: The lack of Javascript is refreshing. Loads instantly. Works with js disabled too (other than the top-left graphic)
- bheadmaster 3y ago
  Also looks great on mobile. Folks sometimes forget that raw HTML is by itself responsive :)
- shawntan 3y ago
  Top-left graphic is Conway's Game of Life. Activates when you hit the Konami code (https://en.wikipedia.org/wiki/Konami_Code https://en.wikipedia.org/wiki/Konami_Code)
phaedrus 3y ago
The article quotes a paper by, "Hao et. al." which concludes: "Finally, given the success that Transformers have had as models of natural language, it is perhaps surprising that these models’ expressive power seems to be best characterized (or at least bounded) in terms of circuit complexity. Mathematical explorations of natural language have most commonly employed the approach to language complexity afforded by the Chomsky hierarchy and its refinements, which is based on automata and formal grammars. The apparent incomparability of these approaches suggests that the exploration of different types of Transformer models might offer a new approach to the study of the formal properties of natural language." A few years ago I found a paper that made the argument that Chomsky's hierarchy of formal languages is not necessarily the only mathematical hierarchy that can exist over languages. The author advocated that other ways of systematizing the classification of languages could lead to both a different hierarchy and new insights. He lamented that the strength of Chomsky's work and reputation might have inadvertently discouraged us from questioning it and looking for alternatives - especially ones which do more to capture what we intuitively mean by natural language parsing ability. Edit: The OP article author interprets the first quote as, "maybe human language is simpler than we thought, and doesn't require higher levels of the Chomsky hierarchy... We might be Transformers!" However in light of that other paper I mentioned, it's more like there might be another hierarchy of languages different from and parallel to Chomsky's hierarchy, with different boundaries for the levels that cover the space differently than Chomsky's. As for how such a thing is possible in detail, remember that a lot of the Chomsky language hierarchy require looking at behavior "in the limit" or "unbounded" in the sense that no finite parser of a lower level can parse all (unbounded) sentences of the higher complexity language. (But an arbitrarily sized lesser-complexity parser can parse sentences of bounded subset of the higher-complexity language.) And it may be that for parsing actual human language pertaining to a non-infinite world, such arguments as the Chomsky hierarchy deals with are no more relevant than arguing that our physical computers aren't truly universal Turing machines because they have finite memory. Technically correct, yet also irrelevant to most of the practical uses we have found for them!
adg33 3y ago
I've skimmed up and down and read some sections a few times - I'm still not 100% sure what the main conclusions are. A summary section would make the article more accessible and valuable to others. My understanding is that the main point here is: - some problems require reasoning through many steps of computation, - transformers have limited depth, so cannot solve problems that require many steps. Am I missing anything else?

The New XOR Problem

199 points by yeesian 4y ago

yarg 4y ago

What about recurrency?

shawntan 4y ago
Recurrency will help, see the empirical results in this paper: https://arxiv.org/abs/2207.02098 https://arxiv.org/abs/2207.02098. LSTMs can solve the PARITY problem, generalising to longer lengths of the problem without issue. The issue with re-introducing recurrency is that no one wants to bear the O(N) growth in computation time. I wonder if we are settling in for a local-optima of bounded-depth architecture for a while due to the obsession with rapid scaling.
- yarg 4y ago
  You don't necessarily need to move to depth N, just because you went recurrent. You can probably design a modular network that can implement the logarithmic version.
  - shawntan 4y ago
    I guess I should say the recurrence growing as a function of the input size is something people don't seem to be willing to afford, not specifically the linear dependence. Not to mention parity here is a toy problem to highlight the issue, but there can be other problems that require recurrence linear or quadratic in the size of the input.
    - yarg 4y ago
      Sure, but a toy problem that's substitutable for many other functions. In this case you could substitute the XOR function for any other merge function. As far as the variable depth is concerned, utilisation is an issue that introduces additional complexity, but otherwise I don't see the problem. (No one's expecting fixed compute time for differently sized data elements.) You can get around that one by building a log(n) threaded pipeline for your log(n) depth network (something like this: https://imgur.com/a/xL4rhFu https://imgur.com/a/xL4rhFu).
- _0ffh 3y ago
  The RWKV people seem to have adapted a recursive model so it can be trained in a special parallel mode like attention. https://github.com/BlinkDL/RWKV-LM https://github.com/BlinkDL/RWKV-LM
  - shawntan 3y ago
    Yeah I really like this project, and I've been meaning to dive into it.
mturmon 3y ago
Reasonable point - in the case of parity, one bit of recurrent state avoids the combinatorial issues mentioned in OP (as OP more or less says in writing the finite state automaton). It's interesting to think about parity in relation to the image classification tasks that sparked the ANN renaissance. In image classification, the class does not strongly depend on a single feature - you don't change from cat to dog by altering one pixel, and then back to cat by altering a different pixel. But parity does depend strongly on each bit in the input. I think it's important to keep this special aspect of the parity problem in mind when thinking about good architectures for various applications.
- yarg 3y ago
  As I noted elsewhere, the structure's not specific to parity/XOR but works on n-ary merge operations in general. It will impact the breadth and depth required for the module; the {2, 2, 1} module structure required for XOR is not generally useful - but it's a substitutable component. A bigger problem is keeping your processor fed with the decaying layer size (you'll want to target a fixed wave size if you're running on a GPU, mostly empty waves are a bad thing), but you can get around that reasonably easily (at least for base-2).

krackers 4y ago

For the PARITY problem mentioned here, I recall from undergrad cs theory that there are some pretty neat provable lower-bounds on arithmetic circuit complexity, e.g. parity is not in AC0 (bounded-depth, unlimited fan-in logic gates) circuits. Even providing more computational power via mod p gates still really doesn't buy you much: Razborov-Smolensky theorem shows that even adding mod-p gates you still can't compute modulo q, for p and q being distinct primes. See also https://blog.computationalcomplexity.org/2023/02/why-cant-little-chatty-do-math.html https://blog.computationalcomplexity.org/2023/02/why-cant-li... for more discussion of LLMs from a circuit-complexity perspective.

shawntan 4y ago
There's more detailed examination of Transformers from circuit complexity in this paper: https://arxiv.org/abs/2106.16213 https://arxiv.org/abs/2106.16213 There are a few references also in the blog post.
- krackers 4y ago
  Thank you! I'd love more articles analyzing LLMs from a circuit-complexity perspective! Also seems modeling the transformer as in the TC0 class, in principle it should be able to do division and multiplication of numbers.

tempodox 4y ago

> A large issue was in not managing expectations when it came to AI, and we’ve had 2 cycles to learn that hype trains can maglev themselves into a 10-year ditch. With all the hype around language models I don't get the impression that this lesson has been learned particularly well. All those proponents of “AI” remind me more and more of used-car salesmen.

jiggawatts 4y ago
The difference is that people are actually paying for ChatGPT because it is immediately useful for day-to-day work tasks. As a random example, ChatGPT 4 is noticeably better at grammar checking than Microsoft Word. If I feed it a couple of paragraphs of text, it'll spot several small errors that Word can't. I don't bother sending documents for internal review any more, I just get the AI to do it in seconds!
- fhd2 4y ago
  Wouldn't it potentially leak everything you send it? ChatGPT that is, I heard with the API it's different.
  - camel-cdr 4y ago
    So does any non self hosted grammar checker.
    - eru 4y ago
      Unless you personally host it yourself, that's maybe true. If someone else in your company hosts it, they are only bound by contracts. You can also use contracts to bind other companies, when you aren't self-hosting.
  - jiggawatts 4y ago
    It's no worse than using, say, Microsoft Teams or Microsoft 365. I also make sure not to paste anything sensitive into it. The kind of thing I've find it to be useful for is massaging the one-paragraph intros to be more readable. For example, Microsoft docs tend to use the word "you", which doesn't fit into certain styles of design documents. I used to have to rewrite the product overview paragraphs myself to clean them up, now I just ask ChatGPT to do it.

espadrine 4y ago

While there is some mention of chain-of-thought prompting, the idea of chain-of-thought can go further, and can actually solve the problem exactly. The LLM can produce working code (or broken code that it can fix from reading the errors), which, when paired with a sandbox, can give the result of the computation back to the LLM. The direction things are going is one where some tokens output by the LLM are hidden, just like human thoughts. That is what Bing Chat is doing, for instance.

shawntan 4y ago
Yea this is a good solution so long as the task that needs to be outsourced to, say a python interpreter, is explicitly known and can be prompt engineered.
rain1 4y ago
But then it's an LLM augmented with a tool that is solving the problem, and not the LLM itself.
- espadrine 4y ago
  The transformer neural network itself only computes the next token probabilities; the sampling of the token, and the mechanism by which the token it generates is concatenated to the input to make it generate the token after, are technically not part of the LLM. So we can either study the LLM strictly from single-token outputs, or from how it combines into larger constructs. The former excludes not just CoT, but a large part of the benchmarks on which they are tested. Looking at it another way, how would humans solve PARITY? I don’t think anyone would read the string, close their eyes, then give an answer without a single thought. At the very least, I would place my finger on each digit successively, effectively using a tool that acts as a memory storage (storing a cursor through the string). The reason I would do that, is that I would have devised an algorithm that requires going through digits one at a time.
- magicalhippo 4y ago
  And? Our brains aren't just doing the exact same things all over, we have centers focused on certain tasks. For example we have[1] neurons that do addition and some others that do subtraction. Our brains are limited to using neurons as building blocks, but why should an AI be limited in the same way? [1]: https://www.sciencedaily.com/releases/2022/02/220214121241.htm https://www.sciencedaily.com/releases/2022/02/220214121241.h...

smeagull 4y ago

Any problem is solvable with two layers. The first layer consists of 1 node per input pattern, with activation and weights such that only one node is active that matches the pattern. And a second layer of weights that provides the output per input pattern.

aezart 3y ago
True but not very useful. That's like writing an "isPrime" function with a switch statement for every possible input number, rather than coming up with a general algorithm. It can't give you any answer you don't already know.

shawntan 4y ago

I'm the original author of this blogpost. I've had discussions that range from "we need to fix this" to "maybe human thought isn't Turing complete..." and I'm interested in hearing what yall think about the topic. P.S. I'm graduating soon and looking for research scientist roles.

abetusk 4y ago
My apologies, I've only skimmed, but maybe this encapsulates the main idea of your post? """ How MLPs could be trained was an open problem at the time, I think, but the field could easily have chugged along and we’d have been where we are now, just 30 years earlier. """ The main idea here is that we got an AI winter because expectations were too high and the reality didn't meet them? I think this is fundamentally missing why we're making rapid progress now. In my opinion, the AI winter wasn't primarily because of a backlash against overhyped promises, it was because computation just wasn't there. We're just now starting to get access to the compute and storage needed, at a price point that's reasonable, to make progress in these areas. In other words, the AI winter came about because the ground wasn't fertile. Now that we have economic massive computational resources, we're in an AI spring. As a back of the envelope calculation, the human brain is estimated at around 2.5 Pb of storage [0]. At today's prices, that works out to about $50k. The cost of 2.5Pb of storage in 1969 was around $675B [1]. [0] https://www.scientificamerican.com/article/what-is-the-memory-capacity/ https://www.scientificamerican.com/article/what-is-the-memor... [1] https://ourworldindata.org/grapher/historical-cost-of-computer-memory-and-storage?country=~OWID_WRL https://ourworldindata.org/grapher/historical-cost-of-comput...
- BlueTemplar 3y ago
  I had the same thought : what would it have cost to make one of those early deep neural networks that restarted the field, but without hardware virtualization : with the same kind of physical neurons than the Perceptron, but with better tech, say mid-AI winter?
- emmelaich 3y ago
  Agree so much that I had assumed this was the standard common view.

rain1 4y ago

I've experimented with this problem a bit https://github.com/rain-1/gpt-incontextlearning-experiments/tree/main/problem%206%20-%20parity https://github.com/rain-1/gpt-incontextlearning-experiments/... - the results were that they can kind of do it, but they do go off the rails fairly easily and get wrong answers.

IanCal 4y ago

> I’ve attempted this prompt several different ways on ChatGPT without a working solution, but I imagine this could work. I've tried a couple of things, it seems OK with a basic approach but starts falling apart when you get close to 50 bits. A more interesting merge approach looks OK at 50 with some quick testing. What sort of scale do you mean when you talk about a working solution? Edit - stats may not be holding up the merge approach at 50. It's close, sometimes getting it right or being one out.

YeGoblynQueenne 3y ago

>> All this to say: I think there are fundamentals we need to view all of this progress through. Lower-bound complexities of problems that we learn in Algorithms 101 shouldn’t get thrown out the window because linear algebra, ReLUs and attention mechanisms are involved. Sorting, for example, has a provable lower-bound complexity of Ω(NlogN). When someone tells you there is a way to do it in O(logN) time, it’s best to squint and ask a few questions. When someone tells you you can gain a speed-up in computing primes, on a naive algorithm, it’s best to ask if that method also has correctness covered. Keep this thought please. There is a very obvious feeling that "now we have LLMs we don't need CS anymore", or don't need maths, science, knowledge... In fact, this goes rather further back than Transformers. I was just reading this old interview of Vladimir Vapnik [1], where he's taking the position that only the "easy" questions in science have explanatory answers, and that for the "hard questions" we can only hope to build predictive models. Vapnik is one of my herores of AI, but on that I think he's not just wrong, but pointing the way to a new dark ages, where we lose the little knowledge we have. Similar "intuitions" are expressed in the "Bitter Lesson" blogpost by Rich sutton [2]. Vapnik is right, of course, in that there are "hard" questions for which we don't know any good answers, and our current framework may not be enough to give any simple, explanatory answer anyway. Certainly, CS is full of bottomless pits of despair, undecidabilities, incompletenesses and intractabilities. I think that just says we're shit at creating formal frameworks. All the ones we've created have some flaw. Arithmetic is incomplete. Logic (even first-order logic) is undecidable. You can't divide by 0, there are tons of calculations that cannot be performed because they sink into uncountable infinities after two steps, etc etc and so on. We just suck at making universal abstractions, that are useful in the first instance, but don't end up painting ourselves into a corner, somewhere down the line. Well, so what? So far we've done pretty well in terms of science, in the sense of understanding the world and how it works. We're not going to give up now! If our tools are not good enough to take our knowledge to the next level, well, then, we just need to make better tools. Better maths. Better Computer Science. Better scientific methods. That has happened in the past at least once, if not many many times. Why can we not do it again? Why do we have to abandon our fate to unknowing, all-predicting machines? That doesn't make sense. ______________ [1] http://www.learningtheory.org/learning-has-just-started-an-interview-with-prof-vladimir-vapnik/ http://www.learningtheory.org/learning-has-just-started-an-i... [2] http://incompleteideas.net/IncIdeas/BitterLesson.html http://incompleteideas.net/IncIdeas/BitterLesson.html

SeanLuke 3y ago

NXOR is normally called Equal, is it not?

shawntan 3y ago
Yeah it is. I've only learned it while looking up material for this post. I figured people know NAND is NOT(AND(.)), so NXOR might be more familiar counterpart to XOR.

jostmey 3y ago

After reading this article, my reaction is that yes, transformers are not the optimal model for NLP and reasoning, but transformers are good enough and scale really well on current GPU hardware. Going forward, I think hardware is the constraint upon which new architectures will need to accommodate

klik99 3y ago

It occurs to me that LLM have the exact opposite strengths and weaknesses of traditional computing - where trad comp is good at hard calculation and storage and bad at soft interpretive, LLMs are good at soft interpreting but bad at anything that requires runtime state storage. It seems like we’re going to plateau and see incremental improvements in AI and will take a novel technique to bridge that gap. This isn’t a new idea of course, but as someone with only light AI knowledge this article helped me understand why that is

retrac 3y ago
Similar idea has occurred to me. In a lot of ways, 'traditional' rules-based AI has more 'understanding' than a LLM can have. Because those rules are fixed by humans to the machine's inputs, and they create a relationship between the software's model and reality, and usually in human-understandable terms (a database entry on a specific person with their facts listed, for example). That doesn't really exist in a LLM. It's entirely self-referential to itself. Which is why it's not possible for it to explain its reasoning, or give a (real) source for a fact. There is no fixed anchor, no reference point, to validate the LLM's output with.

phkahler 3y ago

>> The key takeaway? Depth is important for certain functions. I thought the key takeaway is that nonlinearity is important. Multilayer perceptrons can be collapsed into an equivalent single layer if there isn't nonlinearity thrown in. multi-input XOR can be solved using a form of sin(x) function after summing in a single layer (sin squared if you don't like negative numbers). Upon reading this I also kept thinking "why not use the same transformer weights on each later?" and then the author goes there with the Universal Transformer concept. How many iterations should one use? Why should that be a question at all? As humans we might need to "think about it for a while" and get back to you when we figure it out. One thing all this AI research keeps ignoring is that real biological neurons are running in real time, not some batch process. We might also be doing training and inference at the same time, but I'm not certain how much - see dreams and other forms of background or delayed processing.

shawntan 3y ago
> I thought the key takeaway is that nonlinearity is important. Multilayer perceptrons can be collapsed into an equivalent single layer if there isn't nonlinearity thrown in. multi-input XOR can be solved using a form of sin(x) function after summing in a single layer (sin squared if you don't like negative numbers). Some element of this is used in this paper: https://arxiv.org/pdf/2202.12172.pdf https://arxiv.org/pdf/2202.12172.pdf More broadly, as I've alluded to in other replies, XOR is not the problem in itself, but illustrates a bigger problem. Yes, non-linearities can solve problems, but one hidden layer and the wrong non-linearity (sigmoid instead of sin in this case) may not. Which leads us to the question: What do we include in the broad set we label "non-linearities"? All Turing-complete functions? (This issue is alluded to here: https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493/112604/Saturated-Transformers-are-Constant-Depth https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493...) Then we're back to analysing the computability of a given non-linearity, which in itself has multiple steps of iteration. It's turtles all the way down.
- phkahler 3y ago
  >> What do we include in the broad set we label "non-linearities"? Recursion/iterarion/thinking time.

danbruc 3y ago

This is how I imagine the human brain works. In principle we think iteratively, do one small computation, memorize the result, then do the next step based on the input and the result from the previous step. If things get too complicated, we grab some paper and write down intermediate results on external storage. But fundamentally we memorize some raw facts and otherwise learn algorithms that allow us doing new things by combining existing abilities. Ignoring memory limitations humans are Turing-complete. As we repeatedly solve similar tasks, we develop optimizations, the brain learns to perform a couple of steps in one go instead of going through all the individual steps. When children learn to read, to write or to do math, they learn to do it in small steps, they draw and recognize letters and numbers by looking at and drawing individual lines and circles. When they learn to draw lines or circles they first make very deliberate movements with the pen - up, down, left, right - before drawing a circle becomes a primitive. When they learn to add, they break numbers down into digits and only memorize how to add those, larger numbers are added iteratively digit by digit. With time and practice the brain learns to do many of those things in one step, you read and write letters or words, not deliberately draw individual strokes. You will still fall back to this if you have to deal with characters from a unknown alphabet. You will no longer perform additions digit by digit for small or commonly used numbers but you will fall back to this for big numbers. When you learn to drive, you first very deliberately look at traffic signs, think about turning the steering wheel this way or that way while parking or think about switching on the turn signals. Again with practice many of those things become automatic and you no longer have to think about them. So overall I think the brain is just following sequential algorithms, combining primitives into more complex result. Then with practice common tasks get reimplemented in some kind of fixed function unit that can do a specific task - maybe under some limited circumstances and maybe only approximately - in one step and this can then be used as a new primitive where appropriate. Actually those fixed function units could internally use iteration but this iterative process would be hidden from the primary loop. Language models like ChatGPT seem to be more on the fixed function side, they see a set of tokens and spit out a response. The attention mechanism has some similarity with a loop executing an algorithm step by step, it just has a fixed number of iterations and has been unrolled. When prompted to reason in steps, this adds another loop with additional storage for intermediate results. The difference is that this process is externally visible and that the model must be instructed to do so instead of the model deciding on its own to solve the problem in steps and hiding those steps from the outside. For questions like adding or multiplying numbers or finding the parity of some long bit string the model has some neurons that could directly provide an answer and the answer will probably be correct for simple tasks but the longer the input the more likely it becomes that those neurons will not produce the correct answer. And the model does not know in which region those neurons can be trusted. But the model also knows the underlying algorithm to solve the task, say computing the parity of a long bit string or adding large numbers, and where the steps only involve computations that the model can perform correctly, i.e. adding two digits or XORing two bits. So you can get the correct result out of a model like ChatGPT if you can make it follow the iterative algorithm instead of it trying to give the sum of two 20 digit numbers directly. And I would guess you could - at least to some extend - use ChatGPT itself to rewrite and iteratively solve harder problems. The primary obstacle is probably that it is hard to tell what tasks the model can reliably perform correctly and what tasks must be broken down further.

exabrial 3y ago

side note: What a beautiful blog. Clean design. Great graphics. More importantly: The lack of Javascript is refreshing. Loads instantly. Works with js disabled too (other than the top-left graphic)

bheadmaster 3y ago
Also looks great on mobile. Folks sometimes forget that raw HTML is by itself responsive :)
shawntan 3y ago
Top-left graphic is Conway's Game of Life. Activates when you hit the Konami code (https://en.wikipedia.org/wiki/Konami_Code https://en.wikipedia.org/wiki/Konami_Code)

phaedrus 3y ago

The article quotes a paper by, "Hao et. al." which concludes: "Finally, given the success that Transformers have had as models of natural language, it is perhaps surprising that these models’ expressive power seems to be best characterized (or at least bounded) in terms of circuit complexity. Mathematical explorations of natural language have most commonly employed the approach to language complexity afforded by the Chomsky hierarchy and its refinements, which is based on automata and formal grammars. The apparent incomparability of these approaches suggests that the exploration of different types of Transformer models might offer a new approach to the study of the formal properties of natural language." A few years ago I found a paper that made the argument that Chomsky's hierarchy of formal languages is not necessarily the only mathematical hierarchy that can exist over languages. The author advocated that other ways of systematizing the classification of languages could lead to both a different hierarchy and new insights. He lamented that the strength of Chomsky's work and reputation might have inadvertently discouraged us from questioning it and looking for alternatives - especially ones which do more to capture what we intuitively mean by natural language parsing ability. Edit: The OP article author interprets the first quote as, "maybe human language is simpler than we thought, and doesn't require higher levels of the Chomsky hierarchy... We might be Transformers!" However in light of that other paper I mentioned, it's more like there might be another hierarchy of languages different from and parallel to Chomsky's hierarchy, with different boundaries for the levels that cover the space differently than Chomsky's. As for how such a thing is possible in detail, remember that a lot of the Chomsky language hierarchy require looking at behavior "in the limit" or "unbounded" in the sense that no finite parser of a lower level can parse all (unbounded) sentences of the higher complexity language. (But an arbitrarily sized lesser-complexity parser can parse sentences of bounded subset of the higher-complexity language.) And it may be that for parsing actual human language pertaining to a non-infinite world, such arguments as the Chomsky hierarchy deals with are no more relevant than arguing that our physical computers aren't truly universal Turing machines because they have finite memory. Technically correct, yet also irrelevant to most of the practical uses we have found for them!

adg33 3y ago

I've skimmed up and down and read some sections a few times - I'm still not 100% sure what the main conclusions are. A summary section would make the article more accessible and valuable to others. My understanding is that the main point here is: - some problems require reasoning through many steps of computation, - transformers have limited depth, so cannot solve problems that require many steps. Am I missing anything else?