3 ms·

No, not nonsense. Both are a lookup table whose key is the entire context window and whose value is a probability distribution for what the next token should b

No, not nonsense. Both are a lookup table whose key is the entire context window and whose value is a probability distribution for what the next token should be. You can say the choice of probability distribution in the value is "leveraging the internal structure of the context" or not, but the same tokens in two different orders are two different lookup keys and saying it's impossible to achieve some result with a Markov chain is factually incorrect. https://arxiv.org/pdf/2410.02724 https://arxiv.org/pdf/2410.02724 describes the equivalence formally.

hackinthebochs 4mo ago
That paper doesn't prove the equivalence of Transformers and Markov chains, it uses Markov chains as a theoretical model to understand the behavior of Transforms. The expressivity of the model matters, and Transformers just are more expressive than Markov chains. >but the same tokens in two different orders are two different lookup keys This is necessarily true for Markov chains and not necessarily true for Transformers. Transformers learn invariance over certain kinds of semantically irrelevant transformations. The Markov chain simply has to learn each input variant independently, resulting in an explosion of state space and data requirements compared to the functionally equivalent transformer. Expressive power matters. I really don't get people's love for saying X is "just" Y (it's just a Markov chain, it's just a Kernel method). It's a strange pathology to focus on the superficial similarity while downplaying the boost in expressive power from where the models diverge.
- Borealid 4mo ago
  The paper presents a constructive transformation from any finite-input (finite vocab, bounded length) transformer to an equivalent Markov chain. Do you have some concrete example of a transformer that cannot be represented as a mapping from inputs to probability distribution of outputs? I say they're equivalent because it is possible to losslessly convert one to the other by wasting massive amounts of disk space and time. As a second example proving the point, imagine you sampled a transformer's output for a certain context 85 trillion times, and put the output token frequencies in a table. Repeat for all possible inputs (of which there are a finite number). Then you built literally a hash map looking up the context and spitting out the distribution. That certainly is NOT a transformer any more (it's a hash map!!!), but the output approaches indistinguishability as the sample count increases - if the transformer is reasoning, so is the hash map built from it. I'm not talking hot air here, they really are provably equivalent because a 1:1, onto mapping exists. For the record, "X is more expressive than Y" means "there exists at least one thing that Y cannot represent and X can". Nothing to do with size or time.
  - hackinthebochs 4mo ago
    >I say they're equivalent because it is possible to losslessly convert one to the other by wasting massive amounts of disk space and time. There is a classical algorithm for every quantum algorithm if you're willing to waste a massive amount of space and time. There is a finite-state automata that can recognize any string some Turing machine can recognize. Yet we recognize these as distinct classes of computation. Mathematicians can get away with ignoring the tractability of finding an object with such and such properties. The rest of us can't. Sure, there is a formal equivalence between LLMs and Markov chains, and this formal equivalence is useful for analysis. But this equivalence is not a constraint on the nature of the computations LLMs are doing. The formal equivalence does not mean that LLMs are "just predicting the next token". A probability distribution is a formal characterization of the statistical relationships between inputs and outputs. But this formalization does not undermine potentially further structure underlying the probability distribution (e.g. a deterministic mapping from inputs to outputs). >if the transformer is reasoning, so is the hash map built from it. Definitely not. "Formal" reasoning is making deductions based on the "form" or shape of some statement. In other words, transitioning from some token sequence to another sequence in virtue of the semantic structure of the token sequence (as opposed to its semantic content). Thus a necessary condition for reasoning is the ability to inspect the structure of the input rather than see it as a formless blob. Transformers can plausibly do this; lookup tables, Markov chains, etc necessarily cannot. >For the record, "X is more expressive than Y" means "there exists at least one thing that Y cannot represent and X can". Maybe expressive is the wrong word. But when a model has to wait for someone else to do the work then copy the answer, I call bullshit on it being (computationally) equivalent.
    - Borealid 4mo ago
      Just to make sure I've understood you... Are you arguing that with a set of identically-behaving black boxes, one could be "reasoning" and one could be "not reasoning", and a person would need to look inside the boxes at how they function to decide? Remember, if the mapping from input to output is identical, there exists no test operating on the machines' output that can differentiate them. You can't tell from "conversing with" a machine whether it is or is not doing what you say around "inspecting" the input.

hackinthebochs 4mo ago

That paper doesn't prove the equivalence of Transformers and Markov chains, it uses Markov chains as a theoretical model to understand the behavior of Transforms. The expressivity of the model matters, and Transformers just are more expressive than Markov chains. >but the same tokens in two different orders are two different lookup keys This is necessarily true for Markov chains and not necessarily true for Transformers. Transformers learn invariance over certain kinds of semantically irrelevant transformations. The Markov chain simply has to learn each input variant independently, resulting in an explosion of state space and data requirements compared to the functionally equivalent transformer. Expressive power matters. I really don't get people's love for saying X is "just" Y (it's just a Markov chain, it's just a Kernel method). It's a strange pathology to focus on the superficial similarity while downplaying the boost in expressive power from where the models diverge.

Borealid 4mo ago
The paper presents a constructive transformation from any finite-input (finite vocab, bounded length) transformer to an equivalent Markov chain. Do you have some concrete example of a transformer that cannot be represented as a mapping from inputs to probability distribution of outputs? I say they're equivalent because it is possible to losslessly convert one to the other by wasting massive amounts of disk space and time. As a second example proving the point, imagine you sampled a transformer's output for a certain context 85 trillion times, and put the output token frequencies in a table. Repeat for all possible inputs (of which there are a finite number). Then you built literally a hash map looking up the context and spitting out the distribution. That certainly is NOT a transformer any more (it's a hash map!!!), but the output approaches indistinguishability as the sample count increases - if the transformer is reasoning, so is the hash map built from it. I'm not talking hot air here, they really are provably equivalent because a 1:1, onto mapping exists. For the record, "X is more expressive than Y" means "there exists at least one thing that Y cannot represent and X can". Nothing to do with size or time.
- hackinthebochs 4mo ago
  >I say they're equivalent because it is possible to losslessly convert one to the other by wasting massive amounts of disk space and time. There is a classical algorithm for every quantum algorithm if you're willing to waste a massive amount of space and time. There is a finite-state automata that can recognize any string some Turing machine can recognize. Yet we recognize these as distinct classes of computation. Mathematicians can get away with ignoring the tractability of finding an object with such and such properties. The rest of us can't. Sure, there is a formal equivalence between LLMs and Markov chains, and this formal equivalence is useful for analysis. But this equivalence is not a constraint on the nature of the computations LLMs are doing. The formal equivalence does not mean that LLMs are "just predicting the next token". A probability distribution is a formal characterization of the statistical relationships between inputs and outputs. But this formalization does not undermine potentially further structure underlying the probability distribution (e.g. a deterministic mapping from inputs to outputs). >if the transformer is reasoning, so is the hash map built from it. Definitely not. "Formal" reasoning is making deductions based on the "form" or shape of some statement. In other words, transitioning from some token sequence to another sequence in virtue of the semantic structure of the token sequence (as opposed to its semantic content). Thus a necessary condition for reasoning is the ability to inspect the structure of the input rather than see it as a formless blob. Transformers can plausibly do this; lookup tables, Markov chains, etc necessarily cannot. >For the record, "X is more expressive than Y" means "there exists at least one thing that Y cannot represent and X can". Maybe expressive is the wrong word. But when a model has to wait for someone else to do the work then copy the answer, I call bullshit on it being (computationally) equivalent.
  - Borealid 4mo ago
    Just to make sure I've understood you... Are you arguing that with a set of identically-behaving black boxes, one could be "reasoning" and one could be "not reasoning", and a person would need to look inside the boxes at how they function to decide? Remember, if the mapping from input to output is identical, there exists no test operating on the machines' output that can differentiate them. You can't tell from "conversing with" a machine whether it is or is not doing what you say around "inspecting" the input.