10 ms·

How Chain-of-Thought Reasoning Helps Neural Networks Compute

270 points by amichail 3y ago

stygiansonic 3y ago
A simplified explanation, which I think I heard from Karpathy, is that transformer models only do computation when they generate (decode) a token. So generating more tokens (using CoT) gives the model more time to “think”. Obviously this doesn’t capture all the nuance.
- sadhorse 3y ago
  Does every token requires a full model computation?
  - onedognight 3y ago
    No, you can cache some of the work you did when processing the previous tokens. This is one of the key optimization ideas designed into the architecture.
- _boffin_ 3y ago
  One of the things I’ve been doing with the models I’ve been using with coding is adding the stack and primary dependencies in the system prompt and then asking or conversing. It has helped out a lot, or at least feels like it has.
- ukuina 3y ago
  This is true. You can get a similar effect by asking the model to plan its path first without writing any code, then asking it to review its plan for deficiencies, and finally asking it to enact the plan and write the code.
- XenophileJKO 3y ago
  So my experience creating products on GPT3.5-Turbo is that there is an upper limit to how much instructional complexity the model can handle at a time. It isn't really about "adding computation", though you are doing this. The key is to construct the process so that the model only has to focus on a limited scope to make the decision on. In effect you are kind of creating a tree structure of decisions that build off of each other. By generating intermediate tokens the model can now only pay attention to the smaller set of already collapsed decisions. It is a little more complicated than that as the model will create anticipatory behavior where intermediate steps get biased by an incorrect result that the model anticipates.
  - XenophileJKO 3y ago
    Also I should say it isn't just instructional complexity, it is ambiguity which creates the upper limit on capability.
- bravura 3y ago
  I have another explanation. LLMs are essentially trained on "A B", i.e. is it plausible that B follows A. There's simply a much larger space of possibilities for shorter completions, A B1, A B2, etc. that are plausible. Like if I ask you to give a short reply to a nuanced question, you could reply with a thoughtful answer, a plausible superficially correct sounding answer, convincing BS, etc. Whereas if you force someone to explain their reasoning, the space of plausible completions reduces. If you start with convincing BS and work through it honestly, you will conclude that you should reverse. (This is similar to how one of the best ways to debunk toxic beliefs with honest people is simply through openly asking them to play out the consequences and walking through the impact of stuff that sounds good without much thought.) This is similar to the reason that loading your prompt with things that reduce the space of plausible completions is effective prompt engineering.
  - jorl17 3y ago
    I was going to write pretty much this exact same comment. I am an amateur in how LLMs work, definitely, but I always thought this was the plausible explanation. If I want the "assistant "LLM to tell me "How much 5 times 2 is", if I feed it the line "5 * 2 = " as if it's already started giving that answer, it will very likely write 5*2 = 10. Since LLMs operate on semantic relationships between tokens, the more a bunch of tokens are "close" to a given "semantic topic", the more the LLM will keep outputting tokens in that topic. It's the reason why if you ask an LLM to "review and grade poetry", eventually it starts saying the same thing even about rather different poems -- the output is so filled with the same words, that it just keeps repeating them. Another example: If I ask the LLM to solve me a riddle, just by itself, the LLM may get it wrong. If, however, I start the answer, unravelling a tiny bit of the problem it will very likely give the right answer, as if it's been "guided" onto the right "problem space". By getting LLMs to "say" how they are going to solve things and checking for errors, each words basically tugs onto the next one, honing in on the correct solution. In other words: If an LLM has to answer a question -- any question --, but right after we ask the question we "populate" its answer with some text, what text is more likely to make the LLM answer incorrectly? - Gibberish nonsense - Something logical and related to the problem? Evidently, the more gibberish we give to it, the more likely it is to get it wrong, since we're moving away from the "island of relevant semantic meaning", so to speak. So if we just get the LLM to feed itself more relevant tokens, it automatically guides itself to a better answer. It's kind of like there's an "objective, ideal" sequence of tokens, and it can work as an attractor. The more the LLM outputs words, the more it gets attracted to that sequence...that...."island of relevant semantic meaning". But, again, I know nothing of this. This is just how I view it, conceptually. It's probably very wrong.
- Zondartul 3y ago
  The tokens are also necessary to store information, or at least off-load it from neuron activations. E.g. if you asked an LLM "think about X and then do Y", if the "think X" part is silent, the LLM has a high chance of: a) just not doing that, or b) thinking about it but then forgetting, because the capacity of 'RAM' or neuron activations is unknown but probably less than a few tokens. Actually, has anyone tried to measure how much non-context data (i.e. new data generated from context data) a LLM can keep "in memory" without writing it down?
  - pgorczak 3y ago
    I don’t think commonly used LLM architectures have internal state that carries over between inference steps, so shouldn’t that be none? Unless you mean the previously generated tokens up to the context limit which is well defined.
    - wnmurphy 3y ago
      Correct, there's no internal state, but CoT techniques simulate this by providing a space for the model to generate tokens which represent intermediary thoughts.
    - Zondartul 3y ago
      Sorry, I meant the information that is inferred (from scratch on every token) from the entire context, and is then reduced to that single token. Every time a token is generated, the LLM looks at the entire context, does some processing (and critically, this step generates new data that is inferred from the context) and then the result of all that processing is reduced to a single token. My conjecture is that the LLM "knows" some things that it does not put into words. I don't know what it is, but it seems wasteful to drop the entire state on every token. I even suspect that there is something like a "single logic step" of some conclusions from the context. Though I may be committing the fallacy of thinking in symbolic terms of something that is ultimately statistical.
- rdedev 3y ago
  Do you think there is a fundamental difference between masked language modelling vs causal language modelling? I feel like most LLMs are decoder only models just cause they are easier to train because their attention mask is fixed
- nextaccountic 3y ago
  This begs the question: why is it that giving them more time to "think" yields better answers, and is there any limit to that? If I make them write hundreds of pages of explanation, there must be a diminishing returns of some kind. What influences the optimal amount of thinking? My guess is that good answers are more well reasoned than answers that are short and to the point, and this is picked up in training or fine-tuning or some other step. And probably the optimal amount of thinking has something to do with the training set or the size of the network (wild guesses).
  - lappa 3y ago
    Look at it from an algorithmic perspective. In computer science many algorithms take a non-constant number of steps to execute. However, in transformers models, there are a limited number of decoder blocks, and a limited number of FFN layers in each block. This presents a theoretical upper bound on the complexity of the algorithms a decoder network can solve in a single token generation pass. This explains why GPT4 cannot accurately perform large number multiplication and decimal exponentiation. [0] This example can extend to general natural language generation. While some answers can be immediately retrieved or generated by a "cache" / algorithm which exists in latent space, some tokens have better quality when their latent-space algorithm is executed in multiple steps. [0] https://www.semanticscholar.org/reader/817e52b815560f95171d8fa60f78dd965e885a65 https://www.semanticscholar.org/reader/817e52b815560f95171d8...
    - visarga 3y ago
      > Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking This paper suggests that a large language model should "think ahead" by predicting not only the next token but also a "supporting thought." The approach involves generating all tokens simultaneously, allowing for a single forward pass that produces both the next token and a supporting thought, which might consist of, for example, 16 tokens. This supporting thought influences the model's prediction. The process is then extended to multiple supporting thoughts by ingeniously masking cross-attention between thoughts to ensure their independence. So in essence we can fill all the remaining context with supporting thoughts and benefit from all of them in the same single forward pass. The supporting thoughts themselves are trained with the objective to maximize the probability of a longer sequence ahead, using RL. So they are trained to optimize for longer-term, instead of the myopic next token prediction task. https://arxiv.org/abs/2403.09629 https://arxiv.org/abs/2403.09629
- earslap 3y ago
  The autoregressive transformer architecture has a constant cost per token, no matter how hard the task is. You can ask the most complicated reasoning question, and it takes the same amount of computation to generate the next token compared to the simplest yes / no question. This is due to architectural constraints. Letting the LLM generate "scratch" data to compute (attend to relevant information) is a way of circumventing the constant cost limitation. The harder the task, the more "scratch" you need so more relevant context is available for future tokens.
  - visarga 3y ago
    That's flatly wrong. Each successive token costs progressively more. The deeper a token is in the sequence, the more past states it has to attend to. As a proof, just remember how slow it gets when the context is large, and how snappy when you first start a chat.
    - shawntan 3y ago
      You're both kinda right. The type of computation that happens for that attention step that you refer to is parallel. I would say the thing that is "constant" is the computation graph depth (the number of sequential computations) which is actually important in computing certain functions. https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/ https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/
      - visarga 3y ago
        > The type of computation that happens for that attention step that you refer to is parallel Flash attention, which is widely used, is no longer parallel. The attention matrix is solved batch by batch.
    - earslap 3y ago
      The way I worded it, it might seem wrong - and I agree with you. When I said "constant" I meant without any optimizations to speed up shorter contexts, so with full designed context, architecturally, it is constant. You can pad shorter active contexts with zeroes and avoid attending to empty spaces as an optimization, but that is just an optimization, not an architectural property. If you want "more computation" you fill the context with relevant data (chain of thought, or n-shot stuff), which is the "trick" Karpathy alluded to (it provides more context to attend to), and I agree with that analysis.
- WithinReason 3y ago
  That's what I thought at first, but that actually doesn't make sense, the amount of work done on a string is the same even if the string is followed by padding due to the mask used in attention. Then I realised that an LLM's working memory is limited to its activations, which can be limiting. But it can extend its working memory by writing partial results to the output and reading it in. E.g. if you tell it to "think of a number" without telling you what it is it can't do that, there is nowhere to store that number, it has no temporary storage other than the tape. But if you ask it to "think step by step" you let it store intermediate results (thoughts) on the tape, giving it extra storage it can use for thinking.
- deleted 3y ago
  [deleted]
- tmalsburg2 3y ago
  Do LLM not also think when they encode the prompt? If Karpathy's explanation is accurate, longer prompts should also help even if they don't contain additional information, just by virtue of giving more time to think.
  - Me1000 3y ago
    The time processing the longer prompt isn't being spent churning (i.e. "thinking") on the problem at hand, it's spend calculating attention matrices between all the tokens. The time spent on this is a function of the number of flops you have available. So no, if you just fill up your context window to garbage, the LLM will not perform better at your task/question.
fzaninotto 3y ago
Great article. Now what happens when you apply this idea and let a LLM continue a chain of thought beyond mere question answering? Some form of artificial consciousness. We've made this experiment: https://marmelab.com/blog/2023/06/06/artificial-consciousness.html https://marmelab.com/blog/2023/06/06/artificial-consciousnes...
- starbugs 3y ago
  Material reductionism at its best. Now you have a stochastic parrot "talking" to itself. How can anyone get to the conclusion that this could even begin to resemble a tiny bit of what we call consciousness? Good luck with this dead end.
  - FrustratedMonky 3y ago
    Because you aren't conscious, Parrot. I can tell because "you" gave a parroted response.
activatedgeek 3y ago
I want to point out a tweet [1] that is very relevant to the miracle of CoT, and probably a simpler explanation. > Let's think "step by step"! > Another tidbit I like about data and prompts that miraculously work. > Searching for this phrase resulted in this website (among others), > http://geteasysolution.com, containing many math step-by-step solutions. > How common are they? Quite. > Makes you think. [1]: https://twitter.com/yanaiela/status/1765077404043952516 https://twitter.com/yanaiela/status/1765077404043952516
- FeepingCreature 3y ago
  Though that justifies the specific phrase, it doesn't really contradict the usual explanations of how CoT works. Like... the phrase directs it into the conceptual space of a website that has lots of CoT examples, but if CoT didn't help it think, that wouldn't actually result in better outputs.
  - activatedgeek 3y ago
    I hesitate to the use description as "think," just biasing correlations for subsequent generations. In any case, there is at least one work that shows that CoT may not be necessary and biasing the decoding path via logit probabilities is also promising. [1] One could argue it still doesn't contradict the benefits of CoT, but I suspect there is nothing fundamental about CoT, except that we happened to have been pre-training on sequences that use certain prompts that were easy to conceive from a human's perspective. [1]: https://arxiv.org/abs/2402.10200 https://arxiv.org/abs/2402.10200
    - FeepingCreature 3y ago
      Absolutely. QuietSTaR is going to make CoT obsolete. It's just, it won't make it obsolete by showing that CoT does nothing, but by getting the LLM to embed invisible CoT-like token sequences into the context on its own. That's a victory for CoT, not a loss. "Let's think step by step" is a hack. It was always a hack. Its main payoff was showing people where the model had a weakness and how to (hackily, heavily dependent on training data and phrasing) route around it. Now with QS, the models will be able to bypass that weakness on their own. > I hesitate to the use description as "think," just biasing correlations for subsequent generations. This is of course a fully general description of any iterative computation. :)
patcon 3y ago
Chain of thought reminds me of "muddling through", which immediately clicks with my intuition of the right approach to approximations of intelligence: https://studio.ribbonfarm.com/p/massed-muddler-intelligence#%C2%A7muddling-through-vs-godding-through https://studio.ribbonfarm.com/p/massed-muddler-intelligence#...
MrYellowP 3y ago
I thought this was already obvious. It's all just about the awareness of contexts. Want to improve it? Simply add a term to the prompt to unlock more considerations. Assuming we've not reached the edge of the context window, every new word "unlocks" new vectors with more context the language models adds to the considerations. The similarity with how the human brain (seems to) works is so remarkable, it doesn't even make sense not to use it as an analogue for how to better use language models. When the results (same way of manipulating an LLM as manipulating a human brain ... using the right words) can be achieved the same way, why believe there's a difference? This is stuff one can learn over time by using/researching 3B models. While most people seem to shun them, some of them are extremely powerfull, like the "old" orca mini 3B. I am still using that one! All they really need is better prompts and that approach works perfectly fine. The biggest hurdle I've found is the usually small context window of such small models, but there's ways of cheating around that without sacrificing too much of the quality using small rope extension, summarizing text, adding context words or leaving out letters of words in the prompt, virtually increasing the size of the context window. If you want to improve the results of your language model, you should become a mentalist/con-man/magician/social engineer. It sounds weird, but it works!
- Folcon 3y ago
  This is fascinating, do you have any more details or things that I could look at to explore this further? Even an actual example would be helpful!
  - MrYellowP 3y ago
    Nah, this was all many months ago. You'll have to do the experimenting on your own.
- nicklecompte 3y ago
  Nothing about what you’re saying actually deals with this non-obvious limitation of chain-of-thought: > Examples like this suggest that transformers wouldn’t gain much from using just a few intermediate steps. Indeed, Merrill and Sabharwal proved that chain of thought only really begins to help when the number of intermediate steps grows in proportion to the size of the input, and many problems require the number of intermediate steps to grow much larger still. This aligns with my experience: GPT-4 can only break down “simple” problems when prompted to solve step-by-step. In particular, if the actual steps need to be broken down further (O(n^2) complexity), GPT-4 can’t handle it reliably - it will break a tasks into steps but it struggles to break subtasks into substeps even if it otherwise can solve the subtask with CoT prompting. CoT prompting works for simple O(n) computations because it prevents LLMs from blindly guessing the answer, but they are theoretically (and IMO empirically) incapable of breaking any O(n^2) problem down into O(n) separate O(n) subproblems. Needless to say humans are quite a bit smarter than that. (so are mice!)
woopsn 3y ago
In computing we use analogies everywhere: stack, bus, web, garbage collector, parent, container, ... Master became somewhat controversial recently, but overall the main risk our liberal repurposing of terms introduces is that we sometimes follow the "wrong" idea and design a machine that doesn't do what it ought to, or is unnecessarily complicated, that we develop systems (and documentation etc) that are inefficient if not dumb. In adopting "thought" terminology and other analogies to psychological processes I fear we'll not just misunderstand this technology and how it works, but also degrade the rigour of machine science, damaging our credibility and misleading the public as well. Nobody will ever make the mistake of supposing that "rehydrating" a data structure involves water, or that busy beaver machines are living beings. But the language coming out of the LLM field in particular causes these problems immediately, and they are extreme -- scientists and engineers themselves have trouble telling if it's supposed to be an analogy or not.
- u385639 3y ago
  About a year ago I thought this would settle down but it's only gotten worse. I suppose the llm anthropomorphizing will continue until morale improves
  - sfink 3y ago
    The LLM anthropomorphizing will continue until the machines are happy with how we think about them.
  - astrange 3y ago
    This has always been a problem for AI research since its start in the 70s. AI researchers come up with names for things they assume happen in the human brain, and then further assume that if they write a computer program that does something that could be given the same name, it must work too. https://twitter.com/Meaningness/status/1639120720088408065 https://twitter.com/Meaningness/status/1639120720088408065
    - woopsn 3y ago
      So called chain of thought can improve output quality ("reasoning ability") to an extent, but I wish for josh sake it were called "intermediate token conditioning" / something explanatory or at least descriptive.
meroes 3y ago
My experience interacting with chain-of-thought is that it should not be likened to the rigid chains of logic/math. Step-by-step reasoning by models isn’t magically imparting that much rigidity to their outputs. The strength of the chain is the strength of related contexts, which is to say much less than math/logic done by humans. We tell ourselves we are teaching AI to do step-by-step reasoning, but admittedly as someone who deals with models daily in this area and not programming them, I don’t see the tight necessary connections we teach in basic math because I see how much the model(s) fail in ways no human past a certain age could. It’s more of a search for related contexts, which is powerful, but again not how a human reasons logically. Humans can reason purely form the armchair, starting with very few concepts, and reach far far, ironclad conclusions. Models aren’t doing that. They are leapfrogging through context. Yes an argument can be that’s splitting hairs, but that’s because it’s hard to describe succinctly, not hard to see.
- exe34 3y ago
  I think a lot of what humans think of as "1. 2. Therefore 3." kind of reasoning isn't different from what the llm is doing, and not in fact any more clever than that. Plenty of people believe plenty of questionable things that they assume they have thought through but really haven't. They used the context to guess the next idea/word, often reaching the conclusions they started out with. When you talk about ironclad conclusions, I think what happens is that we come up with those confabulations intuitively, but then we subject them to intense checking - have we defined everything clearly enough, is that leap in reasoning justified, etc. So what I'd really like to see is a way to teach llms to take a vague English sentence and transform it into a form that can be run through a more formal reasoning engine. Often instead of asking an llm to tell you something like how many football fields could you fit inside England, you are better off telling it to write python code to do this, assume get_size_football_field() in m^2 and get_size_England() in m^2 is available.
  - doctoboggan 3y ago
    > I think a lot of what humans think of as "1. 2. Therefore 3." kind of reasoning isn't different from what the llm is doing, and not in fact any more clever than that. Plenty of people believe plenty of questionable things that they assume they have thought through but really haven't. They used the context to guess the next idea/word, often reaching the conclusions they started out with. Agreed that many/most humans behave this way, but some do not. And those who do not are the ones advancing the boundaries of knowledge and it would be very nice if we could get our LLMs to behave in the same way.
tromp 3y ago
> These are the central questions in the formal study of computation. The field dates back to 1936, when Alan Turing first imagined a fanciful device, now called a Turing machine, that could perform any computation by reading and writing symbols on an infinite tape. It dates further back to the 1920s when Moses Schönfinkel came up with Combinatory Logic [1], and the early 1930s when Alonzo Church came up with the lambda calculus [2]. These models however make a less suitable base for computational complexity theory. [1] https://en.wikipedia.org/wiki/Moses_Sch%C3%B6nfinkel https://en.wikipedia.org/wiki/Moses_Sch%C3%B6nfinkel [2] https://encyclopediaofmath.org/wiki/Lambda-calculus https://encyclopediaofmath.org/wiki/Lambda-calculus
- benreesman 3y ago
  Parent has probably seen this (or everything in it), but for others who are interested in this stuff (including Schönfinkel’s work) I recommend https://youtu.be/h0OkptwfX4g https://youtu.be/h0OkptwfX4g.
- YeGoblynQueenne 3y ago
  Arguably it goes further back to Pearce and Frege, Boole, Pascal, Leibniz and all the way to Aristotle, who was probably the first to seek a way to formalise structured thinking. Turing meant his computational apparatus as a formalisation of the way a human mathematician solves a problem by computation, i.e. by the manipulation of symbols according to a set of formal rules. In that, he followed in a long line of others who had thought about the same experience and how eminently mechanisable it is. Pascal was the first to actually do it, for arithmetic.
HarHarVeryFunny 3y ago
I don't see why this needs any long-winded explanation. LLMs generate their output one word at a time (and don't themselves even know what that word will be, since it's randomly sampled from the output probabilities the model generates). Chain-of-Thought simply let's the model see it's own output as an input and therefore build upon that. It lets them break a complex problem down into a series of simpler steps which they can see (output becomes input) and build upon. It's amazing how well these models can do without CoT ("think step-by-step") when they are just ad-libbing word by word, but you can see the limitations of it if you ask for a bunch of sentences starting with a certain type of word, vs ending with that type of word. They struggle with the ending one because there is little internal planning ahead (none, other than to the extent to which the current output word limits, or was proscribed by, the next one).
- kromem 3y ago
  While it's true that the feed forward is one word at a time, the self-attention is not, which is the key difference transformers brought to the table. It's kind of kind saying "computers can add." Yes, they can. But they can multiply too. Over the past 18 months transformers have proven to upend a number of longstanding assumptions, particularly around world modeling. It's a very misleading statement to describe today's LLMs as "simply predicting the next word" even if it's in part true.
  - HarHarVeryFunny 3y ago
    They are just predicting next word, but using a pretty deep understanding of prior context (past). They do not plan AHEAD.
    - gbasin 3y ago
      what would it mean to plan ahead? decoding strategies like beam search are popular and effectively predict many words ahead
      - jumpCastle 3y ago
BrokerHans 3y ago
[flagged]
- deleted 3y ago
  [deleted]
polygamous_bat 3y ago
I think the two modes of LLM discourse: “they’re conscious!/they’re just next token predictors with impressive datasets” comes largely from two different groups of people: those who learned about LLMs before learning about ML fundamentals, and those who learned ML fundamentals before encountering LLMs of today. While I fall in the second group, there is a real risk that my prior concepts about the fundamentals is limiting my view of the bigger picture, so I at least welcome the debate. Re: chain of thought, I at least know that in practice a lot of the results from the original paper has not been quite reproducible at later attempts. Whether that is a quirk of models changing everyday or something deeper, I do not know.
- YeGoblynQueenne 3y ago
  Instinctively I'd trust the people with the knowledge that goes farther back in time. On the other hand, I once whinged to my thesis advisor that a lot of people in machine learning don't seem to know much about older machine learning and AI work and he, with 30+ years of research on me, pointed out that people complained about that already when he was a PhD student. There is so much work on AI that goes back about 80 years (counting from Pitts and McCulloch, because why not; or you could count from Turing) and it's very hard to both keep up with what everyone else is doing, and go deep in your own subject. e.g. you pick up a Reinforcement Learning book and it's basically attacking the same problems as in planning, and with very similar assumptions (states and action spaces) but it's like planning doesn't even exist. Btw: they're next token predictors :P
  - wayeq 3y ago
    > Btw: they're next token predictors :P Why not (possibly) both? After all, we can't even define consciousness, other than "what's it like to be a bat" makes more sense to us intuitively than "what's it like to be a rock". Consciousness may just come along with the ride with a certain amount of information processing, we just have no clue.
    - YeGoblynQueenne 3y ago
      If we can't define consciousness then that's a very good reason not to assume that a computer program is conscious, especially when it wasn't created with the purpose of being conscious in the first place. Consciousness is something we say animals or humans have, but not computers, so to say that a computer program is conscious it takes a lot more work and, I guess, a formal definition that most of us can agree on.
devmor 3y ago
This is context window narrowing. It's not any more "reasoning" than chaining together sub-queries in a database to arrive at a result that's an overlay of multiple matrices of data.
- deleted 3y ago
  [deleted]
phailhaus 3y ago
Models can't think. It uses the input context to predict an output. So if you have a problem that needs to be solved iteratively, those intermediate steps need to be persisted to the context, because there is nowhere for them to go otherwise.
- stavros 3y ago
  > Models can't think. It uses the input context to predict an output. The first claim doesn't follow from the second. What is it about using the input to predict an output that makes you believe they can't think? What if that's all thinking is? We don't know.
  - deleted 3y ago
    [deleted]
  - phailhaus 3y ago
    It's not the the second statement follows from the first; I'm asserting that models can't think, and that what they're really doing is prediction based on context. The fact that chain-of-thought reasoning yields significantly better results is your hint: that means that the model doesn't think like a human does when it comes up with responses. If it's not in the context, it doesn't exist. You can't ask a model "why did you answer that way" without it generating from whole cloth a plausible retroactive reason. But there is no memory, so it can't really tell you. > What if that's all thinking is? I think that this is roughly true. But we actually have memory outside of what we say, so when we think, all those intermediate steps are persisted in our brains. For a model, the context is the memory. If you delete your question from the context and ask it "why did you answer that way", it will have no idea what you're talking about.
    - stavros 3y ago
      > You can't ask a model "why did you answer that way" without it generating from whole cloth a plausible retroactive reason. I've caught myself generating from whole cloth a plausible retroactive reason for some of my actions, which I later realized wasn't true at all. Does that mean I can't think either? Is there a way for an external observer to tell if someone is thinking or not, or is it something that, axiomatically, only humans can do, and nothing else?
sib 3y ago
"techniques from an arcane branch of theoretical computer science called computational complexity theory" I mean... complexity theory is pretty much at the core of theoretical computer science, right? Hardly an arcane branch of it.
Xcelerate 3y ago
It’s kind of funny that the article calls the field of computational complexity “arcane”, considering it is at the forefront of everything we know about the limits of computing. That said, I haven’t understood the intense, long term focus on worst-case case and average-case analysis within the field. In fact, when I first heard of big-O notation many years ago, it took me an embarrassingly long time before I realized this referred to the asymptotic performance of an algorithm on the worst-case instances of a problem. I remember thinking “Why on earth would you care about that? You can derive pathological examples to just about anything.” Even the term “average-case” is misleading. We’re not talking about “average” in the sense of a typical instance of a problem class one might encounter in the course of daily life. This instead refers to the expectation value of the algorithm’s (asymptotic) performance over all problem instances within a formal language. Sure, the non-colloquial usage of the term “average” here is obvious to mathematicians, but I don’t think someone outside the field is likely aware that we see drastically better performance of heuristic algorithms on real-world instances of NP-hard problems than one would expect based upon a naive review of the research from computational complexity theory. This performance gap between theory and practice is due to the fact that the problems we encounter in daily life have such a huge amount of mathematical substructure to them, and I would be very surprised if a provably optimal average-case algorithm ever realistically corresponds to the mean performance of an algorithm optimally tailored to the distribution of problem instances we encounter in real world data. Consider matrix factorization. There are techniques that speed this up considerably if the matrix is known to be positive semidefinite, sparse, low-rank, and so on. Who knows how much undiscovered substructure is lurking in the set of real-world problem instances we lump together under “matrix factorization”. The subfield of computational complexity theory that moves beyond overall complexity analysis I believe is called BWCA, “Beyond Worst-Case Analysis” (but someone correct me if that’s not right). For mathematical objects like neural networks, where the specific problem instances have an absolutely massive amount of hidden substructure within them, I think we will have to use approaches like BWCA going forward to learn more about the nature of e.g., transformers. My view is that we should focus less on the absolute limits of a particular architecture (woohoo, it’s Turing complete and a universal function approximator like everything else) and drill down more into studying the limits of the interplay between model architecture and the intrinsic hidden substructure of the data that the model is trained on.
sfink 3y ago
One simple reason: consider the plausibility of 11 + 31 = 24 It's actually fairly plausible. The answer is numeric. Two digits, even, which is pretty likely when adding together 2-digit inputs. 24 is also a common answer to math problems (it has lots of factors, for one). It even has all the digits from adding 1+3 and 1+1. Now how plausible is Show your work. 11 + 31 = the result of adding the 10s digits together, so 10 + 30 = 40, and then adding in the 1s digits, so 1 + 1 = 2. Combining the 40 and the 2 gives 24. That last sentence doesn't seem very likely. Or: Show your work. 11 + 31 = the result of adding the 10s digits together, so 10 + 30 = 20, and then adding in the 1s digits, so 1 + 1 = 4. Combining the 20 and the 4 gives 24. If you're breaking things down, you have to traverse through some territory that is lower probability than the quick wrong answer. The argument by computational complexity is stronger, though. I just wanted to point out that the above is a confounding explanation that is sufficient for simple cases, and so may need to be ruled out before claiming that computational complexity matters. The complexity argument is also intuitively obvious. If you think of an LLM as a type of computer that does one constant-time forward pass over the input so far on each clock cycle (and outputs a single token), then of course you can compute more if you give your computer more cycles! You can use state (even if the mechanism for transmitting the state from one cycle to the next is sharply limited). Similarly, it's an expansion of the old problem of a single-layer perceptron not being able to compute XOR. (Here, the "cycles" are advances from one layer to the next.) That's not to say that the nuances are obvious. Simply saying you can use multiple clock ticks doesn't really say anything about how much you can do in one tick.
Jackson__ 3y ago
Great article! Now what would happen if we took this idea, and turned it on it's head? Let's train a model to consistently give an answer first, and have it infer the steps it took to get there after. ... Is what I think the researchers at mistral AI are saying, because that's what they did. Every slightly complex question you ask their models goes somewhat like this: >Input: Alice has 3 brothers. Each of her brothers has 2 sisters. How many sisters does Alice have? >Output: Alice has 2 sisters. >Here's the reasoning: > We know that Alice has 3 brothers. > Then we are told that each of her brothers has 2 sisters. > Since Alice is one of the sisters to her brothers, there must be one more sister besides Alice for each brother to have 2 sisters. > Therefore, Alice has 2 sisters in total. Conversely, if you ask the model to think first, it gets it right immediately. I'm kinda baffled, they have not corrected this after their very first model. From mistral 7b to large, each one shows this same trained behavior to answer first, think second.
wangpengqi 3y ago
[flagged]
wangpengqi 3y ago
[flagged]
stolsvik 3y ago
I thought this was obvious: They lack an “inner voice” (80% of humans?) or “inner imagery” (the rest) as we humans do, so they cannot first think the problem through before answering. Thus, using the actual “output area” as such a scratch pad can help it cover a larger area of reasoning before outputting an answer - just as we do. I feel you can even see this when you ask it certain questions with “think in steps” prompting: It can output temporary thoughts which aren’t of use in the final answer - again just as we do when attacking a problem we can’t immediately answer. Also, we humans often use pen and paper to jot down temporary and intermediary thoughts and answers. Again, LLMs don’t have that, but can use the output as something similar. Some styles of ToT prompting actually make the LLM have two types of output - one for its “inner voice thinking”, and then another for output meant for the human. The same goes when one give the LLM method calling abilities, or “googling”: This can be seen as a way to perform thinking and reasoning without output meant for the user, before formulating an answer.

270 points by amichail 3y ago

A simplified explanation, which I think I heard from Karpathy, is that transformer models only do computation when they generate (decode) a token. So generating more tokens (using CoT) gives the model more time to “think”. Obviously this doesn’t capture all the nuance.

sadhorse 3y ago
Does every token requires a full model computation?
- onedognight 3y ago
  No, you can cache some of the work you did when processing the previous tokens. This is one of the key optimization ideas designed into the architecture.
_boffin_ 3y ago
One of the things I’ve been doing with the models I’ve been using with coding is adding the stack and primary dependencies in the system prompt and then asking or conversing. It has helped out a lot, or at least feels like it has.
ukuina 3y ago
This is true. You can get a similar effect by asking the model to plan its path first without writing any code, then asking it to review its plan for deficiencies, and finally asking it to enact the plan and write the code.
XenophileJKO 3y ago
So my experience creating products on GPT3.5-Turbo is that there is an upper limit to how much instructional complexity the model can handle at a time. It isn't really about "adding computation", though you are doing this. The key is to construct the process so that the model only has to focus on a limited scope to make the decision on. In effect you are kind of creating a tree structure of decisions that build off of each other. By generating intermediate tokens the model can now only pay attention to the smaller set of already collapsed decisions. It is a little more complicated than that as the model will create anticipatory behavior where intermediate steps get biased by an incorrect result that the model anticipates.
- XenophileJKO 3y ago
  Also I should say it isn't just instructional complexity, it is ambiguity which creates the upper limit on capability.
bravura 3y ago
I have another explanation. LLMs are essentially trained on "A B", i.e. is it plausible that B follows A. There's simply a much larger space of possibilities for shorter completions, A B1, A B2, etc. that are plausible. Like if I ask you to give a short reply to a nuanced question, you could reply with a thoughtful answer, a plausible superficially correct sounding answer, convincing BS, etc. Whereas if you force someone to explain their reasoning, the space of plausible completions reduces. If you start with convincing BS and work through it honestly, you will conclude that you should reverse. (This is similar to how one of the best ways to debunk toxic beliefs with honest people is simply through openly asking them to play out the consequences and walking through the impact of stuff that sounds good without much thought.) This is similar to the reason that loading your prompt with things that reduce the space of plausible completions is effective prompt engineering.
- jorl17 3y ago
  I was going to write pretty much this exact same comment. I am an amateur in how LLMs work, definitely, but I always thought this was the plausible explanation. If I want the "assistant "LLM to tell me "How much 5 times 2 is", if I feed it the line "5 * 2 = " as if it's already started giving that answer, it will very likely write 5*2 = 10. Since LLMs operate on semantic relationships between tokens, the more a bunch of tokens are "close" to a given "semantic topic", the more the LLM will keep outputting tokens in that topic. It's the reason why if you ask an LLM to "review and grade poetry", eventually it starts saying the same thing even about rather different poems -- the output is so filled with the same words, that it just keeps repeating them. Another example: If I ask the LLM to solve me a riddle, just by itself, the LLM may get it wrong. If, however, I start the answer, unravelling a tiny bit of the problem it will very likely give the right answer, as if it's been "guided" onto the right "problem space". By getting LLMs to "say" how they are going to solve things and checking for errors, each words basically tugs onto the next one, honing in on the correct solution. In other words: If an LLM has to answer a question -- any question --, but right after we ask the question we "populate" its answer with some text, what text is more likely to make the LLM answer incorrectly? - Gibberish nonsense - Something logical and related to the problem? Evidently, the more gibberish we give to it, the more likely it is to get it wrong, since we're moving away from the "island of relevant semantic meaning", so to speak. So if we just get the LLM to feed itself more relevant tokens, it automatically guides itself to a better answer. It's kind of like there's an "objective, ideal" sequence of tokens, and it can work as an attractor. The more the LLM outputs words, the more it gets attracted to that sequence...that...."island of relevant semantic meaning". But, again, I know nothing of this. This is just how I view it, conceptually. It's probably very wrong.
Zondartul 3y ago
The tokens are also necessary to store information, or at least off-load it from neuron activations. E.g. if you asked an LLM "think about X and then do Y", if the "think X" part is silent, the LLM has a high chance of: a) just not doing that, or b) thinking about it but then forgetting, because the capacity of 'RAM' or neuron activations is unknown but probably less than a few tokens. Actually, has anyone tried to measure how much non-context data (i.e. new data generated from context data) a LLM can keep "in memory" without writing it down?
- pgorczak 3y ago
  I don’t think commonly used LLM architectures have internal state that carries over between inference steps, so shouldn’t that be none? Unless you mean the previously generated tokens up to the context limit which is well defined.
  - wnmurphy 3y ago
    Correct, there's no internal state, but CoT techniques simulate this by providing a space for the model to generate tokens which represent intermediary thoughts.
  - Zondartul 3y ago
    Sorry, I meant the information that is inferred (from scratch on every token) from the entire context, and is then reduced to that single token. Every time a token is generated, the LLM looks at the entire context, does some processing (and critically, this step generates new data that is inferred from the context) and then the result of all that processing is reduced to a single token. My conjecture is that the LLM "knows" some things that it does not put into words. I don't know what it is, but it seems wasteful to drop the entire state on every token. I even suspect that there is something like a "single logic step" of some conclusions from the context. Though I may be committing the fallacy of thinking in symbolic terms of something that is ultimately statistical.
rdedev 3y ago
Do you think there is a fundamental difference between masked language modelling vs causal language modelling? I feel like most LLMs are decoder only models just cause they are easier to train because their attention mask is fixed
nextaccountic 3y ago
This begs the question: why is it that giving them more time to "think" yields better answers, and is there any limit to that? If I make them write hundreds of pages of explanation, there must be a diminishing returns of some kind. What influences the optimal amount of thinking? My guess is that good answers are more well reasoned than answers that are short and to the point, and this is picked up in training or fine-tuning or some other step. And probably the optimal amount of thinking has something to do with the training set or the size of the network (wild guesses).
- lappa 3y ago
  Look at it from an algorithmic perspective. In computer science many algorithms take a non-constant number of steps to execute. However, in transformers models, there are a limited number of decoder blocks, and a limited number of FFN layers in each block. This presents a theoretical upper bound on the complexity of the algorithms a decoder network can solve in a single token generation pass. This explains why GPT4 cannot accurately perform large number multiplication and decimal exponentiation. [0] This example can extend to general natural language generation. While some answers can be immediately retrieved or generated by a "cache" / algorithm which exists in latent space, some tokens have better quality when their latent-space algorithm is executed in multiple steps. [0] https://www.semanticscholar.org/reader/817e52b815560f95171d8fa60f78dd965e885a65 https://www.semanticscholar.org/reader/817e52b815560f95171d8...
  - visarga 3y ago
    > Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking This paper suggests that a large language model should "think ahead" by predicting not only the next token but also a "supporting thought." The approach involves generating all tokens simultaneously, allowing for a single forward pass that produces both the next token and a supporting thought, which might consist of, for example, 16 tokens. This supporting thought influences the model's prediction. The process is then extended to multiple supporting thoughts by ingeniously masking cross-attention between thoughts to ensure their independence. So in essence we can fill all the remaining context with supporting thoughts and benefit from all of them in the same single forward pass. The supporting thoughts themselves are trained with the objective to maximize the probability of a longer sequence ahead, using RL. So they are trained to optimize for longer-term, instead of the myopic next token prediction task. https://arxiv.org/abs/2403.09629 https://arxiv.org/abs/2403.09629
earslap 3y ago
The autoregressive transformer architecture has a constant cost per token, no matter how hard the task is. You can ask the most complicated reasoning question, and it takes the same amount of computation to generate the next token compared to the simplest yes / no question. This is due to architectural constraints. Letting the LLM generate "scratch" data to compute (attend to relevant information) is a way of circumventing the constant cost limitation. The harder the task, the more "scratch" you need so more relevant context is available for future tokens.
- visarga 3y ago
  That's flatly wrong. Each successive token costs progressively more. The deeper a token is in the sequence, the more past states it has to attend to. As a proof, just remember how slow it gets when the context is large, and how snappy when you first start a chat.
  - shawntan 3y ago
    You're both kinda right. The type of computation that happens for that attention step that you refer to is parallel. I would say the thing that is "constant" is the computation graph depth (the number of sequential computations) which is actually important in computing certain functions. https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/ https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/
    - visarga 3y ago
      > The type of computation that happens for that attention step that you refer to is parallel Flash attention, which is widely used, is no longer parallel. The attention matrix is solved batch by batch.
  - earslap 3y ago
    The way I worded it, it might seem wrong - and I agree with you. When I said "constant" I meant without any optimizations to speed up shorter contexts, so with full designed context, architecturally, it is constant. You can pad shorter active contexts with zeroes and avoid attending to empty spaces as an optimization, but that is just an optimization, not an architectural property. If you want "more computation" you fill the context with relevant data (chain of thought, or n-shot stuff), which is the "trick" Karpathy alluded to (it provides more context to attend to), and I agree with that analysis.
WithinReason 3y ago
That's what I thought at first, but that actually doesn't make sense, the amount of work done on a string is the same even if the string is followed by padding due to the mask used in attention. Then I realised that an LLM's working memory is limited to its activations, which can be limiting. But it can extend its working memory by writing partial results to the output and reading it in. E.g. if you tell it to "think of a number" without telling you what it is it can't do that, there is nowhere to store that number, it has no temporary storage other than the tape. But if you ask it to "think step by step" you let it store intermediate results (thoughts) on the tape, giving it extra storage it can use for thinking.
deleted 3y ago
[deleted]
tmalsburg2 3y ago
Do LLM not also think when they encode the prompt? If Karpathy's explanation is accurate, longer prompts should also help even if they don't contain additional information, just by virtue of giving more time to think.
- Me1000 3y ago
  The time processing the longer prompt isn't being spent churning (i.e. "thinking") on the problem at hand, it's spend calculating attention matrices between all the tokens. The time spent on this is a function of the number of flops you have available. So no, if you just fill up your context window to garbage, the LLM will not perform better at your task/question.

fzaninotto 3y ago

Great article. Now what happens when you apply this idea and let a LLM continue a chain of thought beyond mere question answering? Some form of artificial consciousness. We've made this experiment: https://marmelab.com/blog/2023/06/06/artificial-consciousness.html https://marmelab.com/blog/2023/06/06/artificial-consciousnes...

starbugs 3y ago
Material reductionism at its best. Now you have a stochastic parrot "talking" to itself. How can anyone get to the conclusion that this could even begin to resemble a tiny bit of what we call consciousness? Good luck with this dead end.
- FrustratedMonky 3y ago
  Because you aren't conscious, Parrot. I can tell because "you" gave a parroted response.

activatedgeek 3y ago

I want to point out a tweet [1] that is very relevant to the miracle of CoT, and probably a simpler explanation. > Let's think "step by step"! > Another tidbit I like about data and prompts that miraculously work. > Searching for this phrase resulted in this website (among others), > http://geteasysolution.com, containing many math step-by-step solutions. > How common are they? Quite. > Makes you think. [1]: https://twitter.com/yanaiela/status/1765077404043952516 https://twitter.com/yanaiela/status/1765077404043952516

FeepingCreature 3y ago
Though that justifies the specific phrase, it doesn't really contradict the usual explanations of how CoT works. Like... the phrase directs it into the conceptual space of a website that has lots of CoT examples, but if CoT didn't help it think, that wouldn't actually result in better outputs.
- activatedgeek 3y ago
  I hesitate to the use description as "think," just biasing correlations for subsequent generations. In any case, there is at least one work that shows that CoT may not be necessary and biasing the decoding path via logit probabilities is also promising. [1] One could argue it still doesn't contradict the benefits of CoT, but I suspect there is nothing fundamental about CoT, except that we happened to have been pre-training on sequences that use certain prompts that were easy to conceive from a human's perspective. [1]: https://arxiv.org/abs/2402.10200 https://arxiv.org/abs/2402.10200
  - FeepingCreature 3y ago
    Absolutely. QuietSTaR is going to make CoT obsolete. It's just, it won't make it obsolete by showing that CoT does nothing, but by getting the LLM to embed invisible CoT-like token sequences into the context on its own. That's a victory for CoT, not a loss. "Let's think step by step" is a hack. It was always a hack. Its main payoff was showing people where the model had a weakness and how to (hackily, heavily dependent on training data and phrasing) route around it. Now with QS, the models will be able to bypass that weakness on their own. > I hesitate to the use description as "think," just biasing correlations for subsequent generations. This is of course a fully general description of any iterative computation. :)

patcon 3y ago

Chain of thought reminds me of "muddling through", which immediately clicks with my intuition of the right approach to approximations of intelligence: https://studio.ribbonfarm.com/p/massed-muddler-intelligence#%C2%A7muddling-through-vs-godding-through https://studio.ribbonfarm.com/p/massed-muddler-intelligence#...

MrYellowP 3y ago

I thought this was already obvious. It's all just about the awareness of contexts. Want to improve it? Simply add a term to the prompt to unlock more considerations. Assuming we've not reached the edge of the context window, every new word "unlocks" new vectors with more context the language models adds to the considerations. The similarity with how the human brain (seems to) works is so remarkable, it doesn't even make sense not to use it as an analogue for how to better use language models. When the results (same way of manipulating an LLM as manipulating a human brain ... using the right words) can be achieved the same way, why believe there's a difference? This is stuff one can learn over time by using/researching 3B models. While most people seem to shun them, some of them are extremely powerfull, like the "old" orca mini 3B. I am still using that one! All they really need is better prompts and that approach works perfectly fine. The biggest hurdle I've found is the usually small context window of such small models, but there's ways of cheating around that without sacrificing too much of the quality using small rope extension, summarizing text, adding context words or leaving out letters of words in the prompt, virtually increasing the size of the context window. If you want to improve the results of your language model, you should become a mentalist/con-man/magician/social engineer. It sounds weird, but it works!

Folcon 3y ago
This is fascinating, do you have any more details or things that I could look at to explore this further? Even an actual example would be helpful!
- MrYellowP 3y ago
  Nah, this was all many months ago. You'll have to do the experimenting on your own.
nicklecompte 3y ago
Nothing about what you’re saying actually deals with this non-obvious limitation of chain-of-thought: > Examples like this suggest that transformers wouldn’t gain much from using just a few intermediate steps. Indeed, Merrill and Sabharwal proved that chain of thought only really begins to help when the number of intermediate steps grows in proportion to the size of the input, and many problems require the number of intermediate steps to grow much larger still. This aligns with my experience: GPT-4 can only break down “simple” problems when prompted to solve step-by-step. In particular, if the actual steps need to be broken down further (O(n^2) complexity), GPT-4 can’t handle it reliably - it will break a tasks into steps but it struggles to break subtasks into substeps even if it otherwise can solve the subtask with CoT prompting. CoT prompting works for simple O(n) computations because it prevents LLMs from blindly guessing the answer, but they are theoretically (and IMO empirically) incapable of breaking any O(n^2) problem down into O(n) separate O(n) subproblems. Needless to say humans are quite a bit smarter than that. (so are mice!)

woopsn 3y ago

In computing we use analogies everywhere: stack, bus, web, garbage collector, parent, container, ... Master became somewhat controversial recently, but overall the main risk our liberal repurposing of terms introduces is that we sometimes follow the "wrong" idea and design a machine that doesn't do what it ought to, or is unnecessarily complicated, that we develop systems (and documentation etc) that are inefficient if not dumb. In adopting "thought" terminology and other analogies to psychological processes I fear we'll not just misunderstand this technology and how it works, but also degrade the rigour of machine science, damaging our credibility and misleading the public as well. Nobody will ever make the mistake of supposing that "rehydrating" a data structure involves water, or that busy beaver machines are living beings. But the language coming out of the LLM field in particular causes these problems immediately, and they are extreme -- scientists and engineers themselves have trouble telling if it's supposed to be an analogy or not.

u385639 3y ago
About a year ago I thought this would settle down but it's only gotten worse. I suppose the llm anthropomorphizing will continue until morale improves
- sfink 3y ago
  The LLM anthropomorphizing will continue until the machines are happy with how we think about them.
- astrange 3y ago
  This has always been a problem for AI research since its start in the 70s. AI researchers come up with names for things they assume happen in the human brain, and then further assume that if they write a computer program that does something that could be given the same name, it must work too. https://twitter.com/Meaningness/status/1639120720088408065 https://twitter.com/Meaningness/status/1639120720088408065
  - woopsn 3y ago
    So called chain of thought can improve output quality ("reasoning ability") to an extent, but I wish for josh sake it were called "intermediate token conditioning" / something explanatory or at least descriptive.

meroes 3y ago

My experience interacting with chain-of-thought is that it should not be likened to the rigid chains of logic/math. Step-by-step reasoning by models isn’t magically imparting that much rigidity to their outputs. The strength of the chain is the strength of related contexts, which is to say much less than math/logic done by humans. We tell ourselves we are teaching AI to do step-by-step reasoning, but admittedly as someone who deals with models daily in this area and not programming them, I don’t see the tight necessary connections we teach in basic math because I see how much the model(s) fail in ways no human past a certain age could. It’s more of a search for related contexts, which is powerful, but again not how a human reasons logically. Humans can reason purely form the armchair, starting with very few concepts, and reach far far, ironclad conclusions. Models aren’t doing that. They are leapfrogging through context. Yes an argument can be that’s splitting hairs, but that’s because it’s hard to describe succinctly, not hard to see.

exe34 3y ago
I think a lot of what humans think of as "1. 2. Therefore 3." kind of reasoning isn't different from what the llm is doing, and not in fact any more clever than that. Plenty of people believe plenty of questionable things that they assume they have thought through but really haven't. They used the context to guess the next idea/word, often reaching the conclusions they started out with. When you talk about ironclad conclusions, I think what happens is that we come up with those confabulations intuitively, but then we subject them to intense checking - have we defined everything clearly enough, is that leap in reasoning justified, etc. So what I'd really like to see is a way to teach llms to take a vague English sentence and transform it into a form that can be run through a more formal reasoning engine. Often instead of asking an llm to tell you something like how many football fields could you fit inside England, you are better off telling it to write python code to do this, assume get_size_football_field() in m^2 and get_size_England() in m^2 is available.
- doctoboggan 3y ago
  > I think a lot of what humans think of as "1. 2. Therefore 3." kind of reasoning isn't different from what the llm is doing, and not in fact any more clever than that. Plenty of people believe plenty of questionable things that they assume they have thought through but really haven't. They used the context to guess the next idea/word, often reaching the conclusions they started out with. Agreed that many/most humans behave this way, but some do not. And those who do not are the ones advancing the boundaries of knowledge and it would be very nice if we could get our LLMs to behave in the same way.

tromp 3y ago

> These are the central questions in the formal study of computation. The field dates back to 1936, when Alan Turing first imagined a fanciful device, now called a Turing machine, that could perform any computation by reading and writing symbols on an infinite tape. It dates further back to the 1920s when Moses Schönfinkel came up with Combinatory Logic [1], and the early 1930s when Alonzo Church came up with the lambda calculus [2]. These models however make a less suitable base for computational complexity theory. [1] https://en.wikipedia.org/wiki/Moses_Sch%C3%B6nfinkel https://en.wikipedia.org/wiki/Moses_Sch%C3%B6nfinkel [2] https://encyclopediaofmath.org/wiki/Lambda-calculus https://encyclopediaofmath.org/wiki/Lambda-calculus

benreesman 3y ago
Parent has probably seen this (or everything in it), but for others who are interested in this stuff (including Schönfinkel’s work) I recommend https://youtu.be/h0OkptwfX4g https://youtu.be/h0OkptwfX4g.
YeGoblynQueenne 3y ago
Arguably it goes further back to Pearce and Frege, Boole, Pascal, Leibniz and all the way to Aristotle, who was probably the first to seek a way to formalise structured thinking. Turing meant his computational apparatus as a formalisation of the way a human mathematician solves a problem by computation, i.e. by the manipulation of symbols according to a set of formal rules. In that, he followed in a long line of others who had thought about the same experience and how eminently mechanisable it is. Pascal was the first to actually do it, for arithmetic.

HarHarVeryFunny 3y ago

I don't see why this needs any long-winded explanation. LLMs generate their output one word at a time (and don't themselves even know what that word will be, since it's randomly sampled from the output probabilities the model generates). Chain-of-Thought simply let's the model see it's own output as an input and therefore build upon that. It lets them break a complex problem down into a series of simpler steps which they can see (output becomes input) and build upon. It's amazing how well these models can do without CoT ("think step-by-step") when they are just ad-libbing word by word, but you can see the limitations of it if you ask for a bunch of sentences starting with a certain type of word, vs ending with that type of word. They struggle with the ending one because there is little internal planning ahead (none, other than to the extent to which the current output word limits, or was proscribed by, the next one).

kromem 3y ago
While it's true that the feed forward is one word at a time, the self-attention is not, which is the key difference transformers brought to the table. It's kind of kind saying "computers can add." Yes, they can. But they can multiply too. Over the past 18 months transformers have proven to upend a number of longstanding assumptions, particularly around world modeling. It's a very misleading statement to describe today's LLMs as "simply predicting the next word" even if it's in part true.
- HarHarVeryFunny 3y ago
  They are just predicting next word, but using a pretty deep understanding of prior context (past). They do not plan AHEAD.
  - gbasin 3y ago
    what would it mean to plan ahead? decoding strategies like beam search are popular and effectively predict many words ahead
    - jumpCastle 3y ago

BrokerHans 3y ago

[flagged]

deleted 3y ago
[deleted]

polygamous_bat 3y ago

I think the two modes of LLM discourse: “they’re conscious!/they’re just next token predictors with impressive datasets” comes largely from two different groups of people: those who learned about LLMs before learning about ML fundamentals, and those who learned ML fundamentals before encountering LLMs of today. While I fall in the second group, there is a real risk that my prior concepts about the fundamentals is limiting my view of the bigger picture, so I at least welcome the debate. Re: chain of thought, I at least know that in practice a lot of the results from the original paper has not been quite reproducible at later attempts. Whether that is a quirk of models changing everyday or something deeper, I do not know.

YeGoblynQueenne 3y ago
Instinctively I'd trust the people with the knowledge that goes farther back in time. On the other hand, I once whinged to my thesis advisor that a lot of people in machine learning don't seem to know much about older machine learning and AI work and he, with 30+ years of research on me, pointed out that people complained about that already when he was a PhD student. There is so much work on AI that goes back about 80 years (counting from Pitts and McCulloch, because why not; or you could count from Turing) and it's very hard to both keep up with what everyone else is doing, and go deep in your own subject. e.g. you pick up a Reinforcement Learning book and it's basically attacking the same problems as in planning, and with very similar assumptions (states and action spaces) but it's like planning doesn't even exist. Btw: they're next token predictors :P
- wayeq 3y ago
  > Btw: they're next token predictors :P Why not (possibly) both? After all, we can't even define consciousness, other than "what's it like to be a bat" makes more sense to us intuitively than "what's it like to be a rock". Consciousness may just come along with the ride with a certain amount of information processing, we just have no clue.
  - YeGoblynQueenne 3y ago
    If we can't define consciousness then that's a very good reason not to assume that a computer program is conscious, especially when it wasn't created with the purpose of being conscious in the first place. Consciousness is something we say animals or humans have, but not computers, so to say that a computer program is conscious it takes a lot more work and, I guess, a formal definition that most of us can agree on.

devmor 3y ago

This is context window narrowing. It's not any more "reasoning" than chaining together sub-queries in a database to arrive at a result that's an overlay of multiple matrices of data.

deleted 3y ago
[deleted]

phailhaus 3y ago

Models can't think. It uses the input context to predict an output. So if you have a problem that needs to be solved iteratively, those intermediate steps need to be persisted to the context, because there is nowhere for them to go otherwise.

stavros 3y ago
> Models can't think. It uses the input context to predict an output. The first claim doesn't follow from the second. What is it about using the input to predict an output that makes you believe they can't think? What if that's all thinking is? We don't know.
- deleted 3y ago
  [deleted]
- phailhaus 3y ago
  It's not the the second statement follows from the first; I'm asserting that models can't think, and that what they're really doing is prediction based on context. The fact that chain-of-thought reasoning yields significantly better results is your hint: that means that the model doesn't think like a human does when it comes up with responses. If it's not in the context, it doesn't exist. You can't ask a model "why did you answer that way" without it generating from whole cloth a plausible retroactive reason. But there is no memory, so it can't really tell you. > What if that's all thinking is? I think that this is roughly true. But we actually have memory outside of what we say, so when we think, all those intermediate steps are persisted in our brains. For a model, the context is the memory. If you delete your question from the context and ask it "why did you answer that way", it will have no idea what you're talking about.
  - stavros 3y ago
    > You can't ask a model "why did you answer that way" without it generating from whole cloth a plausible retroactive reason. I've caught myself generating from whole cloth a plausible retroactive reason for some of my actions, which I later realized wasn't true at all. Does that mean I can't think either? Is there a way for an external observer to tell if someone is thinking or not, or is it something that, axiomatically, only humans can do, and nothing else?

sib 3y ago

"techniques from an arcane branch of theoretical computer science called computational complexity theory" I mean... complexity theory is pretty much at the core of theoretical computer science, right? Hardly an arcane branch of it.

Xcelerate 3y ago

It’s kind of funny that the article calls the field of computational complexity “arcane”, considering it is at the forefront of everything we know about the limits of computing. That said, I haven’t understood the intense, long term focus on worst-case case and average-case analysis within the field. In fact, when I first heard of big-O notation many years ago, it took me an embarrassingly long time before I realized this referred to the asymptotic performance of an algorithm on the worst-case instances of a problem. I remember thinking “Why on earth would you care about that? You can derive pathological examples to just about anything.” Even the term “average-case” is misleading. We’re not talking about “average” in the sense of a typical instance of a problem class one might encounter in the course of daily life. This instead refers to the expectation value of the algorithm’s (asymptotic) performance over all problem instances within a formal language. Sure, the non-colloquial usage of the term “average” here is obvious to mathematicians, but I don’t think someone outside the field is likely aware that we see drastically better performance of heuristic algorithms on real-world instances of NP-hard problems than one would expect based upon a naive review of the research from computational complexity theory. This performance gap between theory and practice is due to the fact that the problems we encounter in daily life have such a huge amount of mathematical substructure to them, and I would be very surprised if a provably optimal average-case algorithm ever realistically corresponds to the mean performance of an algorithm optimally tailored to the distribution of problem instances we encounter in real world data. Consider matrix factorization. There are techniques that speed this up considerably if the matrix is known to be positive semidefinite, sparse, low-rank, and so on. Who knows how much undiscovered substructure is lurking in the set of real-world problem instances we lump together under “matrix factorization”. The subfield of computational complexity theory that moves beyond overall complexity analysis I believe is called BWCA, “Beyond Worst-Case Analysis” (but someone correct me if that’s not right). For mathematical objects like neural networks, where the specific problem instances have an absolutely massive amount of hidden substructure within them, I think we will have to use approaches like BWCA going forward to learn more about the nature of e.g., transformers. My view is that we should focus less on the absolute limits of a particular architecture (woohoo, it’s Turing complete and a universal function approximator like everything else) and drill down more into studying the limits of the interplay between model architecture and the intrinsic hidden substructure of the data that the model is trained on.

sfink 3y ago

One simple reason: consider the plausibility of 11 + 31 = 24 It's actually fairly plausible. The answer is numeric. Two digits, even, which is pretty likely when adding together 2-digit inputs. 24 is also a common answer to math problems (it has lots of factors, for one). It even has all the digits from adding 1+3 and 1+1. Now how plausible is Show your work. 11 + 31 = the result of adding the 10s digits together, so 10 + 30 = 40, and then adding in the 1s digits, so 1 + 1 = 2. Combining the 40 and the 2 gives 24. That last sentence doesn't seem very likely. Or: Show your work. 11 + 31 = the result of adding the 10s digits together, so 10 + 30 = 20, and then adding in the 1s digits, so 1 + 1 = 4. Combining the 20 and the 4 gives 24. If you're breaking things down, you have to traverse through some territory that is lower probability than the quick wrong answer. The argument by computational complexity is stronger, though. I just wanted to point out that the above is a confounding explanation that is sufficient for simple cases, and so may need to be ruled out before claiming that computational complexity matters. The complexity argument is also intuitively obvious. If you think of an LLM as a type of computer that does one constant-time forward pass over the input so far on each clock cycle (and outputs a single token), then of course you can compute more if you give your computer more cycles! You can use state (even if the mechanism for transmitting the state from one cycle to the next is sharply limited). Similarly, it's an expansion of the old problem of a single-layer perceptron not being able to compute XOR. (Here, the "cycles" are advances from one layer to the next.) That's not to say that the nuances are obvious. Simply saying you can use multiple clock ticks doesn't really say anything about how much you can do in one tick.

Jackson__ 3y ago

Great article! Now what would happen if we took this idea, and turned it on it's head? Let's train a model to consistently give an answer first, and have it infer the steps it took to get there after. ... Is what I think the researchers at mistral AI are saying, because that's what they did. Every slightly complex question you ask their models goes somewhat like this: >Input: Alice has 3 brothers. Each of her brothers has 2 sisters. How many sisters does Alice have? >Output: Alice has 2 sisters. >Here's the reasoning: > We know that Alice has 3 brothers. > Then we are told that each of her brothers has 2 sisters. > Since Alice is one of the sisters to her brothers, there must be one more sister besides Alice for each brother to have 2 sisters. > Therefore, Alice has 2 sisters in total. Conversely, if you ask the model to think first, it gets it right immediately. I'm kinda baffled, they have not corrected this after their very first model. From mistral 7b to large, each one shows this same trained behavior to answer first, think second.

wangpengqi 3y ago

[flagged]

wangpengqi 3y ago

[flagged]

stolsvik 3y ago

I thought this was obvious: They lack an “inner voice” (80% of humans?) or “inner imagery” (the rest) as we humans do, so they cannot first think the problem through before answering. Thus, using the actual “output area” as such a scratch pad can help it cover a larger area of reasoning before outputting an answer - just as we do. I feel you can even see this when you ask it certain questions with “think in steps” prompting: It can output temporary thoughts which aren’t of use in the final answer - again just as we do when attacking a problem we can’t immediately answer. Also, we humans often use pen and paper to jot down temporary and intermediary thoughts and answers. Again, LLMs don’t have that, but can use the output as something similar. Some styles of ToT prompting actually make the LLM have two types of output - one for its “inner voice thinking”, and then another for output meant for the human. The same goes when one give the LLM method calling abilities, or “googling”: This can be seen as a way to perform thinking and reasoning without output meant for the user, before formulating an answer.