7 ms·
There is a formal extensional equivalence between Markov chains & LLMs but the only person who seems to be saying anything about this is Gary Marcus. He is cons
by measurablefunc 1y ago
There is a formal extensional equivalence between Markov chains & LLMs but the only person who seems to be saying anything about this is Gary Marcus. He is constantly making the point that symbolic understanding can not be reduced to a probabilistic computation regardless of how large the graph gets it will still be missing basic stuff like backtracking (which is available in programming languages like Prolog).
I think that Gary is right on basically all counts. Probabilistic generative models are fun but no amount of probabilistic sequence generation can be a substitute for logical reasoning.
- boznz 1y agological reasoning is also based on probability weights, most of the time that probability is so close to 100% that it can be assumed to be true without consequence.
- AaronAPU 1y agoStunningly, though I have been saying this for 20 years I’ve never come across someone else mention it until now.
- Certhas 1y agoI don't understand what point you're hinting at. Either way, I can get arbitrarily good approximations of arbitrary nonlinear differential/difference equations using only linear probabilistic evolution at the cost of a (much) larger state space. So if you can implement it in a brain or a computer, there is a sufficiently large probabilistic dynamic that can model it. More really is different. So I view all deductive ab-initio arguments about what LLMs can/can't do due to their architecture as fairly baseless. (Note that the "large" here is doing a lot of heavy lifting. You need _really_ large. See https://en.m.wikipedia.org/wiki/Transfer_operator https://en.m.wikipedia.org/wiki/Transfer_operator)
- arduanika 1y agoWhat hinting? The comment was very clear. Arbitrarily good approximation is different from symbolic understanding. "if you can implement it in a brain" But we didn't. You have no idea how a brain works. Neither does anyone.
- Certhas 1y agoWe didn't but somebody did so it's possible so probabilistic dynamics in high enough dimensions can do it. We don't understand what LLMs are doing. You can't go from understanding what a transformer is to understanding what an LLM does any more than you can go from understanding what a Neuron is to what a brain does.
- mallowdram 1y agoWe know the healthy brain is unpredictable. We suspect error minimization and prediction are not central tenets. We know the brain creates memory via differences in sharp wave ripples. That it's oscillatory. That it neither uses symbols nor represents. That words are wholly external to what we call thought. The authors deal with molecules which are neither arbitrary nor specific. Yet tumors ARE specific, while words are wholly arbitrary. Knowing these things should offer a deep suspicion of ML/LLMs. They have so little to do with how brains work and the units brains actually use (all oscillation is specific, all stats emerge from arbitrary symbols and worse: metaphors) that mistaking LLMs for reasoning/inference is less lexemic hallucination and more eugenic.
- Zigurd 1y ago"That words are wholly external to what we call thought." may be what we should learn, or at least hypothesize, based on what we see LLMs doing. I'm disappointed that AI isn't more of a laboratory for understanding brain architecture, and precisely what is this thing called thought.
- mallowdram 1y agoThe question is how to model the irreducible. And then to concatenate between spatiotemporal neuroscience (the oscillators) and neural syntax (what's oscillating) and add or subtract what the fields are doing to bind that to the surroundings.
- logicchains 1y agoLLMs are not formally equivalent to Markov chains, they're more powerful; transformers with sufficient chain of thought can solve any problem in P: https://arxiv.org/abs/2310.07923 https://arxiv.org/abs/2310.07923.
- measurablefunc 1y agoIf you think there is a mistake in this argument then I'd like to know where it is: https://markov.dk.workers.dev/ https://markov.dk.workers.dev/.
- CamperBob2 1y agoA Markov chain is memoryless by definition. A language model has a context, not to mention state in the form of the transformer's KV store. The whole analogy is just pointless. You might as well call an elephant an Escalade because they weigh the same.
- measurablefunc 1y agoWhere is the logical mistake in the linked argument? If there is a mistake then I'd like to know what it is & the counter-example that invalidates the logical argument.
- deleted 1y ago[deleted]
- deleted 1y ago[deleted]
- versteegen 1y agoA Transformer with a length n context window implements an order 2n-1 Markov chain¹. That is correct. That is also irrelevant in the real world, because LLMs aren't run for that many tokens (as results are bad). Before it hits that limit, there is nothing requiring it to have any of the properties of a Markov chain. In fact, because the state space is k^n (alphabet size k), you might not revisit a state until generating k^n tokens. ¹ Depending on context window implementation details, but that is the maximum, because the states n tokens back were computed from the n tokens before that. The minimum of course is an order n-1 Markov chain.
- jules 1y agoWhat does this predict about LLMs ability to win gold at the International Mathematical Olympiad?
- measurablefunc 1y agoSame thing it does about their ability to drive cars.
- jules 1y agoSo, nothing.
- measurablefunc 1y agoIt's definitely something but it might not be apparent to those who do not understand the distinctions between intensionallity & extensionallity.
- godelski 1y agoDepends which question you're asking. Ability to win a gold medal as if they were scored similarly to how humans are scored? or Ability to win a gold medal as determined by getting the "correct answer" to all the questions? These are subtly two very different questions. In these kinds of math exams how you get to the answer matters more than the answer itself. i.e. You could not get high marks through divination. To add some clarity, the latter would be like testing someone's ability to code by only looking at their results to some test functions (oh wait... that's how we evaluate LLMs...). It's a good signal but it is far from a complete answer. It very much matters how the code generates the answer. Certainly you wouldn't accept code if it does a bunch of random computations before divining an answer. The paper's answer to your question (assuming scored similarly to humans) is "Don’t count on it". Not a definitive "no" but they strongly suspect not.
- jules 1y agoThe type of reasoning by the OP and the linked paper obviously does not work. The observable reality is that LLMs can do mathematical reasoning. A cursory interaction with state of the art LLMs makes this evident, as does their IMO gold medal scored like humans are. You cannot counter observable reality with generic theoretical considerations about Markov chains or pretraining scaling laws or floating point precision. The irony is that LLMs can explain why that type of reasoning is faulty: > Any discrete-time computation (including backtracking search) becomes Markov if you define the state as the full machine configuration. Thus “Markov ⇒ no reasoning/backtracking” is a non sequitur. Moreover, LLMs can simulate backtracking in their reasoning chains. -- GPT-5
- Anon84 1y agoThere definitely is, but Marcus is not the only one talking about it. For example, we covered this paper in one of our internal journal clubs a few weeks ago: https://arxiv.org/abs/2410.02724 https://arxiv.org/abs/2410.02724
- godelski 1y agoI just want to highlight this comment and stress how big of a field ML actually is. I think even much bigger than most people in ML research even know. It's really unfortunate that the hype has grown so much that even in the research community these areas are being overshadowed and even dismissed[0]. It's been interesting watching this evolution and how we're reapproaching symbolic reasoning while avoiding that phrase. There's lots of people doing theory in ML and a lot of these people are making strides which others stand on (ViT and DDPM are great examples of this). But I never expect these works to get into the public eye as the barrier to entry tends to be much higher[1]. But they certainly should be something more ML researchers are looking at. That is to say: Marcus is far from alone. He's just loud [0] I'll never let go how Yi Tay said "fuck theorists" and just spent his time on Twitter calling the KAN paper garbage instead of making any actual critique. There seems to be too many who are happy to let the black box remain a black box because low level research has yet to accumulate to the point it can fully explain an LLM. [1] You get tons of comments like this (the math being referenced is pretty basic, comparatively. Even if more advanced than what most people are familiar with) https://news.ycombinator.com/item?id=45052227 https://news.ycombinator.com/item?id=45052227
- calf 1y agoI hazard to imagine that LLMs are a special subset of Markov chains, and this subset has interesting properties; it seems a bit reductive to dismiss LLMs as "merely' Markov chains. It's what we can do with this unusual subset (e.g. maybe incorporate in a larger AI system) that is the interesting question.
- measurablefunc 1y agoYou don't have to imagine, there is a logically rigorous argument¹ that establishes the equivalence. There is also nothing unusual about neural networks or Markov chains. You've just been mystified by the marketing around them so you think there is something special about them when they're just another algorithm for approximating different kinds of compressible signals & observations about the real world. ¹https://markov.dk.workers.dev/ https://markov.dk.workers.dev/
- tim333 1y agoHumans can do symbolic understanding that seems to rest on a rather flakey probabilistic neural network in our brains, or at least mine does. I can do maths and the like but there's quite a lot of trial and error and double checking things involved. GPT5 said it thinks it's fixable when I asked it: >Marcus is right that LLMs alone are not the full story of reasoning. But the evidence so far suggests the gap can be bridged—either by scaling, better architectures, or hybrid neuro-symbolic approaches.
- afiori 1y agoI sorta agree with you, but replying to "LLM can't reason" with "an LLM says they do" is wild
- JohnKemeny 1y agoI asked ChatGPT and it agrees with the statement that it is indeed wild
- tim333 1y agoI don't have a strong opinion if LLMs can reason or not. I think they can a bit but not very well. I think that also applies to many humans though. I was stuck that to my eyes GPT5's take on the question seemed better thought out than Garry Marcus's who is pretty biased to the LLMs are rubbish school.
- afiori 1y agoMost of the reasonings for the impossibility of intelligence in LLMs either require very restricted environments (chatgpt might not be able to tell how many r are in strawberry, but it can write a python script to do so and it could call it if given access to shell or similar and it can understand the answer) or implicitly imply that human brains have magic powers beyond turing completeness.
- wolvesechoes 1y agoAnd I though that the gap is bridged by giving another billions to Sam Altman
- vidarh 1y ago> Probabilistic generative models are fun but no amount of probabilistic sequence generation can be a substitute for logical reasoning. Unless you either claim that humans can't do logical reasoning, or claim humans exceed the Turing computable, then given you can trivially wire an LLM into a Turing complete system, this reasoning is illogical due to Turing equivalence. And either of those two claims lack evidence.
- sieabahlpark 1y ago[dead]
- 11101010001100 1y agoSo we just need a lot of monkeys at computers?
- godelski 1y ago> you can trivially wire an LLM into a Turing complete system Please don't do the "the proof is trivial and left to the reader"[0]. If it is so trivial, show it. Don't hand wave, "put up or shut up". I think if you work this out you'll find it isn't so trivial... I'm aware of some works but at least every one I know of has limitations that would not apply to LLMs. Plus, none of those are so trivial... [0] https://en.wikipedia.org/wiki/Proof_by_intimidation https://en.wikipedia.org/wiki/Proof_by_intimidation
- vidarh 1y agoYou can do it yourself by setting temperature to zero and asking an LLM to execute the rules of a (2,3) Turing machine. Since temperature zero makes it deterministic, you only need to test one step for each state and symbol combination. Are you suggesting you don't believe you can't make a prompt that successfully encodes 6 trivial state transitions? Either you're being intentionally obtuse, or you don't understand just how simple a minimal Turing machine is.
- godelski 1y ago> Are you suggesting you don't believe you can't make a prompt that successfully encodes 6 trivial state transitions? Please show it instead of doubling down. It's trivial, right? So it is easier than responding to me. That'll end the conversation right here and now. Do I think you can modify an LLM to be a Turing Machine, yeah. Of course. But at this point it doesn't seem like we're actually dealing with an LLM anymore. In other comments you're making comparisons to humans, are you suggesting humans are deterministic? If not, well I see a flaw with your proof.
- Straw 1y agoThis is utter nonsense. There's a formal equivalence between Markov chains and literally any system. The entire world can be viewed as a Markov chain. This doesn't tell you anything of interest, just that if you expand state without bound you eventually get the Markov property. Why can't an LLM do backtracking? Not only within its multiple layers but across token models as reasoning models already do. You are a probabilistic generative model (If you object, all of quantum mechanics is). I guess that means you can't do any reasoning!
- deleted 1y ago[deleted]
- lowbloodsugar 1y ago1. You are a neural net and you can backtrack. But unlike an algorithm space search, you’lol go “hmm. That doesn’t look right. Let me try it another way. “ 2. Agentic AI already does this in the way that you do it.
- bubblyworld 1y agoIf you want to understand SOTA systems then I don't think you should study their formal properties in isolation, i.e. it's not useful to separate them from their environment. Every LLM-based tool has access to code interpreters these days which makes this kind of a moot point.
- measurablefunc 1y agoI prefer logic to hype. If you have a reason to think the hype nullifies basic logical analysis then you're welcome to your opinion but I'm going to stick w/ logic b/c so far no one has presented an actual counter-argument w/ enough rigor to justify their stance.
- bubblyworld 1y agoI think you are applying logic and demand for rigour selectively, to be honest. Not all arguments require formalisation. I have presented mine - your linked logical analyses just aren't relevant to modern systems. I said nothing about the logical steps being wrong, necessarily.
- measurablefunc 1y agoIf there are no logical errors then you're just waving your hands which, again, you're welcome to do but it doesn't address any of the points I've made in this thread.
- bubblyworld 1y agoLol, okay. Serves me right for feeding the trolls.
- wolvesechoes 1y ago> I have presented mine - your linked logical analyses just aren't relevant to modern systems Assertion is not an argument
- PartiallyTyped 1y agoWhat’s the difference between backtracking and flattening the computation?
- measurablefunc 1y agoDefine your terms. Backtracking is defined in the Prolog specification so you'll need to define "flattening".
- PartiallyTyped 1y agoAll execution has to be serial in one way or the other, even if you backtrack you still spent time at T-i at one state, and then go back to a previous state. An LLM could very well act as simply having a tape of the computations it executed and evaluated in the sense that tokens J-K correspond to state at T-i, and the tokens after correspond to the previous state. In essence, thinking of the computations performed as if logged on an infinitely long tape. Now, an immutable tape without overwrites is at best a finite automaton, but giving it the ability to replace tokens — which we have and can do — gives us an interpreted tape that — in a very handwavey manner and if you really squeeze your eyes — resembles a Turing machine. So backtracking could be simulated by an LLM, no? Is there any “difference” under these conditions up to what an LLM can approximate?
- fluidcruft 1y agoI'm genuinely curious whether neuroscoence has shown that humans perform backtracking? I am sure we can be taught to backtrack and many things may seem similar, but I just haven't heard of anything at the neuroscience level that backtracking is a fundamental capacity of biological neural networks. So to the extent that humans perform symbolic computations I'm not sure it's established that backtracking is necessary vs other strategies.
- hyghjiyhu 1y agoThe head of a Turing machine is a Markov chain, even simpler even as it transitions completely predictably. But give it a tape and it can compute anything.
- moonmagick 1y agoGary Marcus is a broken clock He's been saying LLMs wouldn't scale since GPT-3 came out And yet we all use them every day Who cares about tracing? Prolog can't be multi-threaded on a GPU, why is that even in the conversation lol
- deleted 1y ago[deleted]