9 ms·

This is what I've been saying to people, LLMs aren't much smarter than a Markov Chain - a lot of twitter bots and earlier chat agents were driven by them. What

• coldtea 3y ago
  >This is what I've been saying to people, LLMs aren't much smarter than a Markov Chain They're based on the same principles, but extend quite beyond that, and are way smarter than Markov Chains. So, it's not just the infrastructure that's makes the difference (if they were only as effective as Markov Chains, then having the same or even more infrastructure wouldn't make any difference).
• bongodongobob 3y ago
  I've never seen a Markov chain do anything like GPT4. I'm not sure how you can say with a straight face they are basically the same.
  • PheonixPharts 3y ago
    LLMs are Markov chains in latent space, it's the latent representation that give them their power, but ultimately there's not as much difference as one would suspect.
    • esafak 3y ago
      They're different because Markov models are stateless whereas LLMs are stateful. https://en.wikipedia.org/wiki/Markov_property https://en.wikipedia.org/wiki/Markov_property
      • Jensson 3y ago
        Current LLMs are stateless as far as we know, their state when computing a new token is only the preceding text tokens, they don't store any metadata or save state from the previous calculations.
  • adamnemecek 3y ago
    No one has spent 100M on training Markov chains.
    • hiddencost 3y ago
      Google did it. Amazon did it. Plenty of others did. What do you think they were doing before recurrent neural networks?
      • ben_w 3y ago
        100 million USD? No. I'd believe $40 for the energy cost, $120 for very slightly increased wear on their hard drives, and $400 for one engineer's 20% time project for one week. And that's if it was trained on Google's entire internet cache rather than, say, just a Wikipedia snapshot from 2004, which sounds like the kind of thing that Google might have set as a pre-interview coding challenge.
    • edgyquant 3y ago
      For the first few years of smartphones markov chains were used for autocorrect.
    • Al-Khwarizmi 3y ago
      Not 100M I guess, but this is fresh from today's arXiv: "Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens" https://arxiv.org/pdf/2401.17377.pdf https://arxiv.org/pdf/2401.17377.pdf
    • Sohcahtoa82 3y ago
      The trick with Markov chains is that you don't need to. Markov Chains are dead simple. There's not really a "training" as much as it's simply reading data and collecting statistics. They're so simple that you can probably build one nearly as fast as you can read the training data.
    • ben_w 3y ago
      I think it would take some spectacularly bad engineering to be that wasteful. It would need to be so inefficient that getting ChatGPT to write the code won't be bad enough.
  • thwarted 3y ago
    A LLM is a Markov chain with billions of associations and weights. A Makov chain is an LLM of maybe a few dozen associations and weights (so an LM, without the first L). The difference is in the data structure and the size of the atoms/n-grams. The data structure Markov chain implementations use is not efficient for billions of parameters, either in storage or in processing. But the idea is the same: give a likely next token given the last n tokens. The value for n is a narrow window for Markov chains and an extremely wide window for LLM. LLM are able to maintain massive amounts of state compared to a Markov chain implementation.
    • causalmodels 3y ago
      An LLM is a Markov chain in the same sense that a cat is a tiger, technically true but it misses the qualia.
      • candiodari 3y ago
        It's not. There's fundamental architectural differences that couldn't be bigger. A better comparison would be that it's like a windup toy versus a group of humans moving an entire civilization. They both move along a distance, but just listing the systems that the human group has that the windup toy doesn't is too long to fit on a page.
        • Jensson 3y ago
          > It's not. There's fundamental architectural differences that couldn't be bigger. LLM architecture is a markov chain to the core. It isn't a lookup table like old markov chains but it is still a markov chain: next word prediction based on previous words.
          • fjkdlsjflkds 3y ago
            Thanks for repeating this. Seems like most people fail to understand that LLMs (as they are implemented these days) are markov chains by definition, regardless of how much "better" they are compared to "Dissociated Press"-style markov chains based on lookup tables. > A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which *the probability of each event depends only on the state attained in the previous event*. Is the process calculating a probability distribution over "next token", based on a bounded-size context of "previous tokens"? Yes? Then it is a markov chain, by definition. It's like saying that a "human" is not an "animal", since it is so much "better" and "capable" than (other/usual) animals. The more you argue, the more I'll be convinced that you either don't know what the definition of a "human" is, or that you don't know what the definition of an "animal" is (or both).
  • idontpost 3y ago
    [dead]
  • k__ 3y ago
    Fair, but maybe it's more of a computer science-cy type of comparison? We say systems can perform the same types of computations if they're both Turing complete. Yet, we wouldn't implement everything in every "language" that is Turing complete. Perhaps, every LLM could be represented as a Markov chain, and for some it even makes sense (e.g., easier to train, easier to reason about), but in most cases it's a bad idea (e.g., expensive, bad performance).
• guluarte 3y ago
  me too, current LLM are markov chains with context
• chpatrick 3y ago
  "humans aren't much smarter than goldfish"
• hiddencost 3y ago
  The whole point of Transformers is that they broke the Markov assumption (i.e., that the next token probability is strictly conditioned on a window of N preceding tokens).
  • pclmulqdq 3y ago
    That's not actually true, they still have a fixed history window. The idea that transformers capture through the attention mechanism is that not all past tokens are created equal, and that the importance of tokens in that history window depends on what they are.
    • sudosysgen 3y ago
      They also scale differently - Markov Chains scale exponentially with the size of the window, while transformers scale quadratically. So in fact transformers are really more exponentially more efficient, though without bound on resources their capabilities are a strict subset of that of Markov chain.
    • deleted 3y ago
      [deleted]
  • theGnuMe 3y ago
    Look into variable order Markov models.
• CamperBob2 3y ago
  This is what I've been saying to people, LLMs aren't much smarter than a Markov Chain And that's why people have been nodding, smiling politely and reaching behind their back for the doorknob.
  • notso411 3y ago
    [dead]
• axchizhov 3y ago
  Yeah, and Markov chains aren't much smarter than... matrix multiplication. A lot of stuff have been built with it, but these pesky c++ libs like lapack — such a bother to use! Imagine a world where a good infrastructure have been built around it — matrix multiplication certainly would be a blast!
  • edgyquant 3y ago
    What are ANN but fancy matrix multiplication?
    • ASalazarMX 3y ago
      And a reason why GPUs are well suited for AI. 3D transformations are also fancy matrix multiplication.
    • SomeoneFromCA 3y ago
      ANN are non-linear. Much more powerful.
• GuB-42 3y ago
  The big difference is the "deep" in "deep learning". As the article says, Markov chains can be thought of as linear operations, which are very limited, and the reason early neural networks weren't taken seriously. Notoriously, you couldn't implement a XOR operation using these early neural nets. It all changed when we got to multi-layer perceptrons, with backpropagation. The key here is the transfer function, which is non-linear, which allows the network to do infinitely more what you can achieve with simple linear combinations. And it is also differentiable, which allows for learning using backpropagation. This is the theoretical foundation behind LLMs, diffusion models, classifiers, etc... Essentially everything we call "AI" today. So, yes, by being non-linear, LLMs are deeply smarter than Markov chains (pun intended).
• ben_w 3y ago
  > This is what I've been saying to people, LLMs aren't much smarter than a Markov Chain Then you're doing some combination of grossly overestimating the latter and/or underestimating the former. A Markov Chain is a (small) language model with a context length of 1, never more, that's a definitional requirement of a Markov process.
  • jltsiren 3y ago
    Markov chains are defined in terms of states, which are not necessarily the same as tokens. As an example, de Bruijn graphs have been widely used in bioinformatics. There are many definitions, but the key idea is that nodes are strings of length k, and there may be an edge from u to v if the length k-1 suffix of u is the same as the length k-1 prefix of v. It's trivial to turn a de Bruijn graph into a Markov chain with a context of k symbols. If you have the Burrows-Wheeler transform of the training data, you can use it to simulate a Markov chain over a de Bruijn graph with any context length. You can also change the context length on the fly. I toyed a little bit with that idea when I was a grad student ~15 years ago, but nothing really came out of it. Building the model was already cheap back then, while getting data was the real bottleneck. LLMs are basically lossy approximations of Markov chains. If you have a small accurate approximation of a larger model, the approximate model probably has the ability to generalize. And it turns out that good generalization over textual data looks like intelligent behavior.
    • ben_w 3y ago
      > Markov chains are defined in terms of states, which are not necessarily the same as tokens. While true, I don't see how that helps? The example isn't particularly illuminating, yes you can make a Markov chain that encompasses all possible states in principle, but in practice you can't do that with a language model because you can't list all possible states (they mostly don't exist in the training set but even if they did there's no room to store them) and instead have to make a system which is, for lack of a non-anthropomorphic verbs, "trying to guess" the state — most of the cool stuff in the LLM is the system doing the guessing[0]. > If you have the Burrows-Wheeler transform of the training data, you can use it to simulate a Markov chain over a de Bruijn graph with any context length. You can also change the context length on the fly. I toyed a little bit with that idea when I was a grad student ~15 years ago, but nothing really came out of it. Building the model was already cheap back then, while getting data was the real bottleneck. To me, the Burrows-Wheeler transform looks like a way to generate a compact tokenisation that doesn't make presumptions about data structure — while I think that's a good idea (and much better than the naive English language tokenisation of "anything that's not a letter or apostrophe" which IMO probably harmed early NLP), I don't think it's a good argument for drawing similarities between Transformer models (or even RNN models) and Markov models > LLMs are basically lossy approximations of Markov chains. If you have a small accurate approximation of a larger model, the approximate model probably has the ability to generalize. And it turns out that good generalization over textual data looks like intelligent behavior. I wonder if you're using "approximation" to mean something different than I would understand the term? You can map a Turing machine to a sufficiently large Markov chain whose probabilities are always 1 or 0, but that has the same problem: Turing machines and LLMs aren't lossy approximations of Markov chains, they're at least generalisations that only look the same when you construct an extreme form. Hopefully we both agree that it would be very weird to argue that "the language centres of human brains are basically just approximations of Markov chains"? Even though we can probably sufficiently well describe each neuron within a brain by a Markov chain? [0] This reminds me of my issue with John Searle's Chinese room argument: Searle denies the system truly understands Chinese because the human reading the books and following the instructions doesn't know Chinese, I would argue that the intelligence and understanding is encoded in the books, and that the entity lacking understanding is the substrate upon which the instructions are processed. To argue "the system as a whole can't be said to understand because the human doing the data processing doesn't understand" seems to me to map to saying "humans can't be said to understand because the brain cells doing the data processing don't understand", or even "… atoms conveying electrochemical signals across synapses don't understand". But I'm clearly digressing now, so I'm glad I put this in a footnote…