5 ms·

> after an observation you are absolutely at a new state The essential property of a Markov chain is maintaining the Markov property: P(X_n+1 = x_n+1 | X_n =

> after an observation you are absolutely at a new state The essential property of a Markov chain is maintaining the Markov property: P(X_n+1 = x_n+1 | X_n = x_n, ..., x_1) = P(X_n+1 = x_n+1 | X_n = x_n) That is the future, given the present state, is conditionally independent of the past states. It's worth recognizing that decoder only LLMs (which are most the major LLMs used by people) maintain the Markov property and can be properly understood as Markov chains. > The attention mechanism is the best we have for this and Markov chains struggle beyond stringing together a few syllables. Attention has nothing to do with the maintaining the Markov property but allows for a fantastically more complex representation of state which is where decoder only LLMs derive the majority of their power. tl;dr most of the LLMs people use are effectively Markov Chains.

mjburgess 1y ago
They are Markov Chains, any one saying otherwise doesn't understand what a Markov chain is
- lackoftactics 1y ago
  Wouldn't tool calling, mcp break finite state?
  - jameshart 1y ago
    Tool calling is just part of the protocol you're using for how to handle states output by your Markov model. Same goes for chat input, for that matter. Chat interfaces are like taking a simple Markov generator, but with a rule where you say 'whenever it reaches a state ending in X, hand over decision making about state transitions to a human instead of a random number generator, until they move it to state ending in Y'. Tool calling is similar - 'when it reaches state ending in X, send the state data to a tool; use the result to drive a series of state transitions; then start generating again'.
    - naasking 1y ago
      Memory Augmented Large Language Models are Computationally Universal, https://arxiv.org/abs/2301.04589 https://arxiv.org/abs/2301.04589
- deleted 1y ago
  [deleted]
- hk__2 1y ago
  Authority arguments like "I’m right and if you disagree with me you don’t understand anything" are not exactly helpful.
  - mjburgess 1y ago
    It's not an authority argument, its the opposite. A warning about the supposed authority of people who would make that kind of claim. The validation of what i'm saying is little more than a few minutes google away. Some interventions can just be warnings, rather than lectures.
rcfox 1y ago
Is this just because LLMs don't have state? As far as I understand it, as you have a back-and-forth conversation with an LLM, you have to provide the entire history of the conversation plus your new response each time.
- jampekka 1y ago
  Stateful models, e.g. RNNs, are Markov models too. Sometimes "Markov chain" is used to refer specifically to models with no hidden state, e.g. (decoder-only) Transformers.
eigencoder 1y ago
Could you help me understand how decoder-only LLMs maintain the Markov property? If you used the same random seed, the input to the model "The cow jumped over the" would not give the same output as just "the", right? So isn't that violating the Markov property?
- OJFord 1y ago
  State (in this sense at least) isn't word/token parsing progress, it's comprising all the input and any context (which may include the entire chat history for example).
- AnotherGoodName 1y ago
  There would be need to a state specifically for “the cow jumped over the” (and any other relevant context) and states for all the other times ‘the’ is proceeded by something. This is the limitation i was getting at btw. In the example i wad getting at, if you have an image with solid vertical columns, followed by columns of random static, followed again by solid vertical colors a markov chain could eventually learn all patterns that go solid->32 random bits->different solid color And eventually it would start predicting the different color correctly based on the solid color before the randomness. It ‘just’ needs a state for every possible random color between. This is ridiculous in practice however since you’d need to learn 2^32 states just for relation ship between those two solid colors alone.
  - thesz 1y ago
    > It ‘just’ needs a state for every possible random color between. You can use skipgrams - prefixes with holes in them. Sparse Non-negative Matrix Language Model [1] uses them with great success. [1] https://aclanthology.org/Q16-1024/ https://aclanthology.org/Q16-1024/ The pure n-gram language models would have hard time computing escape weights for such contexts, but mixture of probabilities that is used in SNMLM does not need to do that. If I may, I've implemented an online per-byte version of SNMLM [2], which allows skipgrams' use. They make performance worse, but they can be used. SNMLM's predictive performance for my implementation is within percents to performance of LSTM on enwik8. [2] https://github.com/thesz/snmlm-per-byte https://github.com/thesz/snmlm-per-byte
kgeist 1y ago
What is the conceptual difference between a "past state" and a "present state"? In a typical conversation with an LLM, you have past messages that remain in the KV cache when generating the next token (so as not to recalculate everything). Yet here, everything that came before is reinterpreted as part of the present state. In other words, it seems as if you can take any past state and fold it into one large concatenated present state - and, by that logic, call basically anything a Markov chain? I can't wrap my head around it. Can you give an example of a non-Markov system?
- fluoridation 1y ago
  Hmm... For example, say you have a machine that must decide whether a monetary transaction is allowable or not. The state at any given time could be the balances of all accounts, plus some metadata about past states (but not the past states themselves). Then if A has $5 in their account and tries to transfer $5 to B, the contents of the metadata would be the deciding factor of whether the transaction goes through or not. The machine still only operates on the present state, but the present state depends indirectly on past states.
  - kgeist 1y ago
    But a conversation with an LLM doesn't only depend on the last message, it depends on all previous messages. Sure the number of messages is limited by the context window, so you can indeed say it's a high-order Markov chain (it can only see N states back), but theoretically, what an actual non-Markovian LLM would look like? Something which has an infinite context? It's not physically possible... At this point it sounds like "it's a Markov chain" is not a very useful statement.
    - thaumasiotes 1y ago
      You appear to be confusing the UI over the LLM with the actual working of the LLM. None of them allow for more than one message to exist. You put in one message and you get one word (well, one token) back.
red75prime 1y ago
> tl;dr most of the LLMs people use are effectively Markov Chains. ...when they are used without RAG and tools. x_n belongs to a set of cardinality 65536^100000 or so. Equating an LLM to a Markov Chain doesn't allow to make any non-trivial predictions about its behavior.
nadalishhh 1y ago
Exactly right on the mathematical equivalence! Your clarification of the Markov property is crucial - the conditional independence given the present state is what defines it, regardless of how complex that state representation becomes. The key insight you raise about attention is particularly important: it doesn't violate the Markov property, it just enables a vastly more sophisticated state representation. Classical n-gram Markov chains use simple discrete states, while transformers use high-dimensional continuous representations that can encode exponentially more information about context. This perspective helps bridge the conceptual gap many people have. When they think "Markov chain," they often picture simple state transitions, but mathematically, LLMs are just Markov chains with astronomically complex states. The attention mechanism is the computational trick that makes these complex states tractable - it's not changing the fundamental probabilistic structure.

mjburgess 1y ago

They are Markov Chains, any one saying otherwise doesn't understand what a Markov chain is

lackoftactics 1y ago
Wouldn't tool calling, mcp break finite state?
- jameshart 1y ago
  Tool calling is just part of the protocol you're using for how to handle states output by your Markov model. Same goes for chat input, for that matter. Chat interfaces are like taking a simple Markov generator, but with a rule where you say 'whenever it reaches a state ending in X, hand over decision making about state transitions to a human instead of a random number generator, until they move it to state ending in Y'. Tool calling is similar - 'when it reaches state ending in X, send the state data to a tool; use the result to drive a series of state transitions; then start generating again'.
  - naasking 1y ago
    Memory Augmented Large Language Models are Computationally Universal, https://arxiv.org/abs/2301.04589 https://arxiv.org/abs/2301.04589
deleted 1y ago
[deleted]
hk__2 1y ago
Authority arguments like "I’m right and if you disagree with me you don’t understand anything" are not exactly helpful.
- mjburgess 1y ago
  It's not an authority argument, its the opposite. A warning about the supposed authority of people who would make that kind of claim. The validation of what i'm saying is little more than a few minutes google away. Some interventions can just be warnings, rather than lectures.

rcfox 1y ago

Is this just because LLMs don't have state? As far as I understand it, as you have a back-and-forth conversation with an LLM, you have to provide the entire history of the conversation plus your new response each time.

jampekka 1y ago
Stateful models, e.g. RNNs, are Markov models too. Sometimes "Markov chain" is used to refer specifically to models with no hidden state, e.g. (decoder-only) Transformers.

eigencoder 1y ago

Could you help me understand how decoder-only LLMs maintain the Markov property? If you used the same random seed, the input to the model "The cow jumped over the" would not give the same output as just "the", right? So isn't that violating the Markov property?

OJFord 1y ago
State (in this sense at least) isn't word/token parsing progress, it's comprising all the input and any context (which may include the entire chat history for example).
AnotherGoodName 1y ago
There would be need to a state specifically for “the cow jumped over the” (and any other relevant context) and states for all the other times ‘the’ is proceeded by something. This is the limitation i was getting at btw. In the example i wad getting at, if you have an image with solid vertical columns, followed by columns of random static, followed again by solid vertical colors a markov chain could eventually learn all patterns that go solid->32 random bits->different solid color And eventually it would start predicting the different color correctly based on the solid color before the randomness. It ‘just’ needs a state for every possible random color between. This is ridiculous in practice however since you’d need to learn 2^32 states just for relation ship between those two solid colors alone.
- thesz 1y ago
  > It ‘just’ needs a state for every possible random color between. You can use skipgrams - prefixes with holes in them. Sparse Non-negative Matrix Language Model [1] uses them with great success. [1] https://aclanthology.org/Q16-1024/ https://aclanthology.org/Q16-1024/ The pure n-gram language models would have hard time computing escape weights for such contexts, but mixture of probabilities that is used in SNMLM does not need to do that. If I may, I've implemented an online per-byte version of SNMLM [2], which allows skipgrams' use. They make performance worse, but they can be used. SNMLM's predictive performance for my implementation is within percents to performance of LSTM on enwik8. [2] https://github.com/thesz/snmlm-per-byte https://github.com/thesz/snmlm-per-byte

kgeist 1y ago

What is the conceptual difference between a "past state" and a "present state"? In a typical conversation with an LLM, you have past messages that remain in the KV cache when generating the next token (so as not to recalculate everything). Yet here, everything that came before is reinterpreted as part of the present state. In other words, it seems as if you can take any past state and fold it into one large concatenated present state - and, by that logic, call basically anything a Markov chain? I can't wrap my head around it. Can you give an example of a non-Markov system?

fluoridation 1y ago
Hmm... For example, say you have a machine that must decide whether a monetary transaction is allowable or not. The state at any given time could be the balances of all accounts, plus some metadata about past states (but not the past states themselves). Then if A has $5 in their account and tries to transfer $5 to B, the contents of the metadata would be the deciding factor of whether the transaction goes through or not. The machine still only operates on the present state, but the present state depends indirectly on past states.
- kgeist 1y ago
  But a conversation with an LLM doesn't only depend on the last message, it depends on all previous messages. Sure the number of messages is limited by the context window, so you can indeed say it's a high-order Markov chain (it can only see N states back), but theoretically, what an actual non-Markovian LLM would look like? Something which has an infinite context? It's not physically possible... At this point it sounds like "it's a Markov chain" is not a very useful statement.
  - thaumasiotes 1y ago
    You appear to be confusing the UI over the LLM with the actual working of the LLM. None of them allow for more than one message to exist. You put in one message and you get one word (well, one token) back.

red75prime 1y ago

> tl;dr most of the LLMs people use are effectively Markov Chains. ...when they are used without RAG and tools. x_n belongs to a set of cardinality 65536^100000 or so. Equating an LLM to a Markov Chain doesn't allow to make any non-trivial predictions about its behavior.

nadalishhh 1y ago

Exactly right on the mathematical equivalence! Your clarification of the Markov property is crucial - the conditional independence given the present state is what defines it, regardless of how complex that state representation becomes. The key insight you raise about attention is particularly important: it doesn't violate the Markov property, it just enables a vastly more sophisticated state representation. Classical n-gram Markov chains use simple discrete states, while transformers use high-dimensional continuous representations that can encode exponentially more information about context. This perspective helps bridge the conceptual gap many people have. When they think "Markov chain," they often picture simple state transitions, but mathematically, LLMs are just Markov chains with astronomically complex states. The attention mechanism is the computational trick that makes these complex states tractable - it's not changing the fundamental probabilistic structure.