[HN Gopher] Ask HN: How are Markov chains so different from tiny...
___________________________________________________________________
Ask HN: How are Markov chains so different from tiny LLMs?
I polished a Markov chain generator and trained it on an article by
Uri Alon and al
(https://pmc.ncbi.nlm.nih.gov/articles/PMC7963340/). It generates
text that seems to me at least on par with tiny LLMs, such as
demonstrated by NanoGPT. Here is an example:
jplr@mypass:~/Documenti/2025/SimpleModels/v3_very_good$
./SLM10b_train UriAlon.txt 3 Training model with order
3... Skip-gram detection: DISABLED (order < 5)
Pruning is disabled Calculating model size for JSON
export... Will export 29832 model entries
Exporting vocabulary (1727 entries)... Vocabulary
export complete. Exporting model entries...
Processed 12000 contexts, written 28765 entries (96.4%)...
JSON export complete: 29832 entries written to model.json
Model trained and saved to model.json Vocabulary size:
1727
jplr@mypass:~/Documenti/2025/SimpleModels/v3_very_good$ ./SLM9_gen
model.json _Aging cell model requires comprehensive incidence
data. To obtain such a large medical database of the joints are
risk factors. Therefore, the theory might be extended to describe
the evolution of atherosclerosis and metabolic syndrome. For
example, late-stage type 2 diabetes is associated with collapse of
beta-cell function. This collapse has two parameters: the fraction
of the senescent cells are predicted to affect disease threshold .
For each individual, one simulates senescent-cell abundance using
the SR model has an approximately exponential incidence curve with
a decline at old ages In this section, we simulated a wide range of
age-related incidence curves. The next sections provide examples of
classes of diseases, which show improvement upon senolytic
treatment tends to qualitatively support such a prediction. model
different disease thresholds as values of the disease occurs when a
physiological parameter ph increases due to the disease. Increasing
susceptibility parameter s, which varies about 3-fold between BMI
below 25 (male) and 54 (female) are at least mildly age-related and
25 (male) and 28 (female) are strongly age-related, as defined
above. Of these, we find that 66 are well described by the model as
a wide range of feedback mechanisms that can provide homeostasis to
a half-life of days in young mice, but their removal rate slows
down in old mice to a given type of cancer have strong risk factors
should increase the removal rates of the joint that bears the most
common biological process of aging that governs the onset of
pathology in the records of at least 104 people, totaling 877
disease category codes (See SI section 9), increasing the range of
6-8% per year. The two-parameter model describes well the strongly
age-related ICD9 codes: 90% of the codes show R 2 > 0.9) (Figure
4c). This agreement is similar to that of the previously proposed
IMII model for cancer, major fibrotic diseases, and hundreds of
other age-related disease states obtained from 10-4 to lower cancer
incidence. A better fit is achieved when allowing to exceed its
threshold mechanism for classes of disease, providing putative
etiologies for diseases with unknown origin, such as bone marrow
and skin. Thus, the sudden collapse of the alveoli at the outer
parts of the immune removal capacity of cancer. For example, NK
cells remove senescent cells also to other forms of age-related
damage and decline contribute (De Bourcy et al., 2017). There may
be described as a first-passage-time problem, asking when mutated,
impair particle removal by the bronchi and increase damage to
alveolar cells (Yang et al., 2019; Xu et al., 2018), and immune
therapy that causes T cells to target senescent cells (Amor et al.,
2020). Since these treatments are predicted to have an exponential
incidence curve that slows at very old ages. Interestingly, the
main effects are opposite to the case of cancer growth rate to
removal rate We next consider the case of frontline tissues
discussed above._
Author : JPLeRouzic
Score : 111 points
Date : 2025-11-17 20:36 UTC (3 days ago)
| MarkusQ wrote:
| LLMs include mechanisms (notably, attention) that allow longer-
| distance correlations than you could get with a similarly-sized
| Markov chain. If you squint hard enough though, they are Markov
| chains with this "one weird trick" that makes them much more
| effective for their size.
| Sohcahtoa82 wrote:
| A Markov Chain trained by only a single article of text will very
| likely just regurgitate entire sentences straight from the source
| material. There just isn't enough variation in sentences.
|
| But then, Markov Chains fall apart when the source material is
| very large. Try training a chain based on Wikipedia. You'll find
| that the resulting output becomes incoherent garbage. Increasing
| the context length may increase coherence, but at the cost of
| turning into just simple regurgitation.
|
| In addition to the "attention" mechanism that another commenter
| mentioned, it's important to note that Markov Chains are
| _discrete_ in their next token prediction while an LLM is more
| fuzzy. LLMs have latent space where the meaning of a word
| basically exists as a vector. LLMs will generate token sequences
| that didn 't exist in the source material, whereas Markov Chains
| will ONLY generate sequences that existed in the source.
|
| This is why it's impossible to create a digital assistant, or
| really anything useful, via Markov Chain. The fact that they only
| generate sequences that existed in the source mean that it will
| never come up with anything creative.
| johnisgood wrote:
| > The fact that they only generate sequences that existed in
| the source mean that it will never come up with anything
| creative.
|
| I have seen the argument that LLMs can only give you what its
| been trained on, i.e. it will not be "creative" or
| "revolutionary", that it will not output anything "new", but
| "only what is in its corpus".
|
| I am quite confused right now. Could you please help me with
| this?
|
| Somewhat related: I like the work of David Hume, and he
| explains it quite well how we can imagine various creatures,
| say, a pig with a dragon head, even if we have not seen one
| ANYWHERE. It is because we can take multiple ideas and combine
| them together. We know how dragons typically look like, and we
| know how a pig looks like, and so, we can imagine (through our
| creativity and combination of these two ideas) how a pig with a
| dragon head would look like. I wonder how this applies to LLMs,
| if they even apply.
|
| Edit: to clarify further as to what I want to know: people have
| been telling me that LLMs cannot solve problems that is not in
| their training data already. Is this really true or not?
| jldugger wrote:
| Well, there's kind of two answers here:
|
| 1. To the extent that creativity is randomness, LLM inference
| samples from the token distribution at each step. It's
| possible (but unlikely!) for an LLM to complete "pig with"
| with the token sequence "a dragon head" just by random
| chance. The temperature settings commonly exposed control how
| often the system takes the most likely candidate tokens.
|
| 2. A markov chain model will literally have a matrix entry
| for every possible combination of inputs. So a 2 degree chain
| will have n^2 weights, where N is the number of possible
| tokens. In that situation "pig with" can never be completed
| with a brand new sentence, because those have literal 0's in
| the probability. In contrast, transformers consider huge
| context windows, and start with random weights in huge neural
| network matrices. What people hope happens is that the NN
| begins to represent ideas, and connections between them. This
| gives them a shot at passing "out of distribution" tests,
| which is a cornerstone of modern AI evaluation.
| thaumasiotes wrote:
| >> The fact that they only generate sequences that existed in
| the source
|
| > I am quite confused right now. Could you please help me
| with this?
|
| This is pretty straightforward. Sohcahtoa82 doesn't know what
| he's saying.
| Sohcahtoa82 wrote:
| I'm fully open to being corrected. Just telling me I'm
| wrong without elaborating does absolutely nothing to foster
| understanding and learning.
| thaumasiotes wrote:
| If you still think there's something left to explain, I
| recommend you read your other responses. Being restricted
| to the training data is not a property of Markov output.
| You'd have to be very, very badly confused to think that
| it was. (And it should be noted that a Markov chain
| itself doesn't contain any training data, as is also true
| of an LLM.)
|
| More generally, since an LLM is a Markov chain, it
| doesn't make sense to try to answer the question "what's
| the difference between an LLM and a Markov chain?" Here,
| the question is "what's the difference between a tiny LLM
| and a Markov chain?", and assuming "tiny" refers to
| window size, and the Markov chain has a similarly tiny
| window size, they are the same thing.
| johnisgood wrote:
| He said LLMs are creative, yet people have been telling
| me that LLMs cannot solve problems that is not in their
| training data. I want this to be clarified or elaborated
| on.
| shagie wrote:
| Make up a fanciful problem and ask it to solve it. For
| example,
| https://chatgpt.com/s/t_691f6c260d38819193de0374f090925a
| is unlikely to be found in the training data - I just
| made it up. Another example of wizards and witches and
| warriors and summoning...
| https://chatgpt.com/share/691f6cfe-
| cfc8-8011-b8ca-70e2c22d36... - I doubt that was in the
| training data either.
|
| Make up puzzles of your own and see if it is able to
| solve it or not.
|
| The blanket claim of "cannot solve problems that are not
| in its training data" seems to be something that can be
| disproven by making up a puzzle from your own human
| creativity and seeing if it can solve it - or for that
| matter, _how_ it attempts to solve it.
|
| It appears that there is some ability for it to reason
| about new things. I believe that much of this "an LLM
| can't do X" or "an LLM is parroting tokens that it was
| trained on" comes from trying to claim that all the
| material that it creates was created before, by a human
| and any use of an LLM is stealing from some human and
| thus unethical to use.
|
| ( ... and maybe if my block world or wizards and warriors
| and witches puzzle was in the training data somewhere,
| I'm unconsciously copying something somewhere else and my
| own use of it is unethical. )
| wadadadad wrote:
| This is an interesting idea, but as you stated, it's all
| logic; it's hard to come up with an idea where you don't
| have to explain concepts yet still is dissimilar enough
| to be in the training.
|
| In your second example with the wizards- did you notice
| that it failed to follow the rules? Step 3, the witch was
| summoned by the wizard. I'm curious as to why you didn't
| comment either way on this.
|
| On a related note, instead of puzzles, what about
| presenting riddles? I would argue that riddles are
| creative, pulling bits and pieces of meaning from words
| to create an answer. If AI can solve riddles not seen
| before, would that count as creative and not solving
| problems in their dataset?
|
| Here's one I created and presented (the first incorrect
| answer I got was Escape Room; I gave it 10 attempts and
| it didn't get the answer I was thinking of):
|
| ---
|
| Solve the riddle:
|
| _Chaos erupts around_
|
| _The shape moot_
|
| _The goal is key_
| purple_turtle wrote:
| 1) being restricted to exact matches in input is
| definition of Markov Chains
|
| 2) LLMs are not Markov Chains
| thaumasiotes wrote:
| > 1) being restricted to exact matches in input is
| definition of Markov Chains
|
| Here's wikipedia:
|
| > a Markov chain or Markov process is a stochastic
| process describing a sequence of possible events in which
| the probability of each event depends only on the state
| attained in the previous event.
|
| A Markov chain is a finite state machine in which
| transitions between states may have probabilities other
| than 0 or 1. In this model, there is no input; the
| transitions occur according to their probability _as time
| passes_.
|
| > 2) LLMs are not Markov Chains
|
| As far as the concept of "Markov chains" has been used in
| the development of linguistics, they are seen as a tool
| of text generation. A Markov chain for this purpose is a
| hash table. The key is a sequence of tokens (in the
| state-based definition, this sequence is the current
| state), and the value is a probability distribution over
| a set of tokens.
|
| To rephrase this slightly, a Markov chain is a lookup
| table which _tells you_ "if the last N tokens were s_1,
| s_2, ..., s_N, then for the following token _you should
| choose_ t_1 with probability p_1, t_2 with probability
| p_2, etc... ".
|
| Then, to tie this back into the state-based definition,
| we say that when we choose token t_k, we emit that token
| into the output, and we also dequeue the first token from
| our representation of the state and enqueue t_k at the
| back. This brings us into a new state where we can
| generate another token.
|
| A large language model is seen slightly differently. It
| is a function. The independent variable is a sequence of
| tokens, and the dependent variable is a probability
| distribution over a set of tokens. Here we say that the
| LLM _answers the question_ "if the last N tokens of a
| fixed text were s_1, s_2, ..., s_N, what is the following
| token likely to be?".
|
| Or, rephrased, the LLM is a lookup table which tells you
| "if the last N tokens were s_1, s_2, ..., s_N, then the
| following token _will be_ t_1 with probability p_1, t_2
| with probability p_2, etc... ".
|
| You might notice that these two tables contain the same
| information organized in the same way. The transformation
| from an LLM to a Markov chain is the identity
| transformation. The only difference is in what you say
| you're going to do with it.
| koliber wrote:
| Here's how I see it, but I'm not sure how valid my mental
| model is.
|
| Imagine a source corpus that consists of:
|
| Cows are big. Big animals are happy. Some other big animals
| include pigs, horses, and whales.
|
| A Markov chain can only return verbatim combinations. So it
| might return "Cows are big animals" or "Are big animals
| happy".
|
| An LLM can get a sense of meaning in these words and can
| return ideas expressed in the input corpus. So in this case
| it might say "Pigs and horses are happy". It's not limited to
| responding with verbatim sequences. It can be seen as a bit
| more creative.
|
| However, LLMs will not be able to represent ideas that it has
| not encountered before. It won't be able to come up with
| truly novel concepts, or even ask questions about them.
| Humans (some at least) have that unbounded creativity that
| LLMs do not.
| marcellus23 wrote:
| > A Markov chain can only return verbatim combinations. So
| it might return "Cows are big animals" or "Are big animals
| happy".
|
| Just for my own edification, do you mean "Are big animals
| _are_ happy "? "animals happy" never shows up in the source
| text so "happy" would not be a possible successor to
| "animals", correct?
| vidarh wrote:
| > However, LLMs will not be able to represent ideas that it
| has not encountered before. It won't be able to come up
| with truly novel concepts, or even ask questions about
| them. Humans (some at least) have that unbounded creativity
| that LLMs do not.
|
| There's absolutely no evidence to support this claim. It'd
| require humans to exceed the Turing computable, and we have
| no evidence that is possible.
| koliber wrote:
| If you tell me that trees are big, and trees are made of
| hard wood, I as a human am capable of asking whether
| trees feel pain. I don't think what you said is false and
| I am not familiar with computational theory to be able to
| debate it. People occasionally have novel creative
| insights that do not derive from past experience or
| knowledge, and that is what I think of when I think of
| creativity.
|
| Humans created novel concepts like writing literally out
| of thin air. I like how the book "Guns, Steels, and
| Germs" describes that novel creative process and
| contrasts it via a disseminative derivation process.
| fragmede wrote:
| > However, LLMs will not be able to represent ideas that it
| has not encountered before.
|
| Sure they do. We call them hallucinations and complain that
| they're not true, however.
| koliber wrote:
| Hmmm. Didn't think about that.
|
| In people there is a difference between unconscious
| hallucinations vs. intentional creativity. However, there
| might be situations where they're not distinguishable. In
| LLMs, it's hard to talk about intentionality.
|
| I love where you took this.
| Sohcahtoa82 wrote:
| > I have seen the argument that LLMs can only give you what
| its been trained on, i.e. it will not be "creative" or
| "revolutionary", that it will not output anything "new", but
| "only what is in its corpus".
|
| LLMs can absolutely create things that are creative, at least
| for some definition of "creative".
|
| For example, I can ask an LLM to create a speech about cross-
| site scripting the style of Donald Trump:
|
| > _Okay, folks, we 're talking about Cross-Site Scripting,
| alright? I have to say, it's a bit confusing, but let's try
| to understand it. They call it XSS, which is a fancy term. I
| don't really know what it means, but I hear it's a big deal
| in the tech world. People are talking about it, a lot of
| people, very smart people. So, Cross-Site Scripting. It's got
| the word "scripting" in it, which sounds like it's about
| writing, maybe like a script for a movie or something. But
| it's on the internet, on these websites, okay? And
| apparently, it's not good. I don't know exactly why, but it's
| not good. Bad things happen, they tell me. Maybe it makes the
| website look different, I don't know. Maybe it makes things
| pop up where they shouldn't. Could be anything! But here's
| what I do know. We need to do something about it. We need to
| get the best people, the smartest people, to look into it.
| We'll figure it out, folks. We'll make our websites safe, and
| we'll do it better than anyone else. Trust me, it'll be
| tremendous. Thank you._
|
| Certainly there's no text out there that contains a speech
| about XSS from Trump. There's some snippets here and there
| that likely sound like Trump, but a Markov Chain simply is
| incapable of producing anything like this.
| johnisgood wrote:
| Oh, of course, what I want answered did not have much to do
| with Markov Chain, but LLMs, because I saw this argument
| often against LLMs.
| 0cf8612b2e1e wrote:
| Sure that specific text does not exist, but the discrete
| tokens that went into it would have been.
|
| If you similarly trained a Markov chain at the token level
| on a LLM sized corpus, it could make the same. Lacking an
| attention mechanism, the token probabilities would be
| terribly non constructive for the effort, but it is not
| impossible.
| Sohcahtoa82 wrote:
| Let's assume three things here:
|
| 1. The corpus contains every Trump speech.
|
| 2. The corpus contains everything ever written about XSS.
|
| 3. The corpus does NOT contain Trump talking about XSS,
| nor really anything that puts "Trump" and "XSS" within
| the same page.
|
| A Markov Chain _could not_ produce a speech about XSS in
| the style of Trump. The greatest tuning factor for a
| Markov Chain is the context length. A short length (like
| 2-4 words) produces incoherent results because it only
| looks at the last 2-4 words when predicting the next
| word. This means if you prompted the chain with "Create
| a speech about cross-site scripting the style of Donald
| Trump", then even with a 4-word context, _all the model
| processes_ is "style of Donald Trump". But the time it
| reached the end of the prompt, it's already forgotten the
| beginning of it.
|
| If you increase the context to 15, then the chain would
| produce _nothing_ because "Create a speech about cross-
| site scripting in the style of Donald Trump" _has never
| appeared in its corpus_ , so there's no data for what to
| generate next.
|
| The matching in a Markov Chain is _discrete_. It 's
| purely a mapping of (series of tokens) -> (list of
| possible next tokens). If you pass in a series of tokens
| that was never seen in the training set, then the list of
| possible next tokens is an empty set.
| umanwizard wrote:
| > I have seen the argument that LLMs can only give you what
| its been trained on, i.e. it will not be "creative" or
| "revolutionary", that it will not output anything "new", but
| "only what is in its corpus".
|
| People who claim this usually don't bother to precisely
| (mathematically) define what they actually mean by those
| terms, so I doubt you will get a straight answer.
| pama wrote:
| LLMs have the ability to learn certain classes of algorithms
| from their datasets in order to reduce errors when
| compressing their pretraining data. If you are technically
| inclined, read the reference:
| https://arxiv.org/abs/2208.01066 (optionally followup work)
| to see how llms can pick up complicated algorithms from
| training on examples that could have been generated by such
| algorithms (in one of the cases the LLM is better than
| anything we know; in the rest it is simply just as good as
| our best algos). Learning such functions from data would not
| work with Markov chains at any level of training. The LLMs in
| this study are tiny. They are not really learning a language,
| but rather how to perform regression.
| godelski wrote:
| > I have seen the argument that LLMs can only give you what
| its been trained
|
| There's confusing terminology here and without clarification
| people talk past one another.
|
| "What its been trained on" is a distribution. It can produce
| things from that distribution and only things from that
| distribution. If you train on multiple distributions, you get
| the union of the distribution, making a distribution.
|
| This is entirely different from saying it can only reproduce
| _samples_ which it was trained on. It is not a memory machine
| that is surgically piecing together snippets of memorized
| samples. (That would be a mind bogglingly impressive
| machine!)
|
| A distribution is more than its samples. It is the things
| between too. Does the LLM perfectly capture the distribution?
| Of course not. But it's a compression machine so it
| compresses the distribution. Again, different from
| compressing the samples, like one does with a zip file.
|
| So distributionally, can it produce anything novel? No, of
| course not. How could it? It's not magic. But sample wise can
| it produce novel things? Absolutely!! It would be an
| incredibly unimpressive machine if it couldn't and it's
| pretty trivial to prove that it can do this. Hallucinations
| are good indications that this happens but it's impossible to
| do on anything but small LLMs since you can't prove any given
| output isn't in the samples it was trained on (they're just
| trained on too much data). > people have been
| telling me that LLMs cannot solve problems that is not in
| their training data already. Is this really true or not?
|
| Up until very recently most LLMs have struggled with the
| prompt Solve: 5.9 = x + 5.11
|
| This is certainly in their training distribution and has been
| for years, so I wouldn't even conclude that they can solve
| problems "in their training data". But that's why I said it's
| not a perfect model of the distribution. > a
| pig with a dragon head
|
| One needs to be quite careful with examples as you'll have to
| make the unverifiable assumption that such a sample does not
| exist in the training data. With the size of training data
| this is effectively unverifiable.
|
| But I would also argue that humans can do more than that.
| Yes, we can combine concepts, but this is a lower level of
| intelligence that is not unique to humans. A variation of
| this is applying a skill from one domain into another. You
| might see how that's pretty critical to most animals
| survival. But humans, we created things that are entirely
| outside nature require things outside a highly sophisticated
| cut and paste operation. Language, music, mathematics, and so
| much more are beyond that. We could be daft and claim music
| is simply cut and paste of songs which can all naturally be
| reproduced but that will never explain away the feelings or
| emotion that it produces. Or how we formulated the sounds in
| our heads long before giving them voice. There is rich depth
| to our experiences if you look. But doing that is odd and
| easily dismissed as our own familiarity deceives us into our
| lack of.
| franciscator wrote:
| Creativity need to be better defined. And the rest is a
| learning problem. If you keep on training, learning what you
| see ...
| andoando wrote:
| That little quip from Hume has influenced my thinking so much
| Im happy to see it again
| hugkdlief wrote:
| > we can imagine various creatures, say, a pig with a dragon
| head, even if we have not seen one ANYWHERE. It is because we
| can take multiple ideas and combine them together.
|
| Funny choice of combination, pig and dragon, since Leonardo
| Da Vinci famously imagined dragons themselves by combining
| lizards and cats: https://i.pinimg.com/originals/03/59/ee/035
| 9ee84595586206be6...
| johnisgood wrote:
| Hah, interesting. Pig and dragon just sort of came to mind
| as I was writing the comment. :D But we can pretty much
| imagine anything, can't we? :)
|
| I should totally try to generate images using AI with some
| of these prompts!
| thfuran wrote:
| >Markov Chains will ONLY generate sequences that existed in the
| source.
|
| A markov chain of order N will only generate sequences of
| length N+1 that were in the training corpus, but it is likely
| to generate sequences of length N+2 that weren't (unless N was
| too large for the training corpus and it's degenerate).
| Isamu wrote:
| Right, you can generate long sentences from a first-order
| markov model, and all of the transitions from one word to the
| next be in the training set but the full generated sentence
| may not.
| Sohcahtoa82 wrote:
| Well yeah, but N+2 but the generation of the +2 loses the
| first part of N.
|
| If you use a context window of 2, then yes, you might know
| that word C can follow words A and B, and D can follow words
| B and C, and therefore generate ABCD even if ABCD never
| existed.
|
| But it could be that ABCD is incoherent.
|
| For example, if A = whales, B = are, C = mammals, D =
| reptiles.
|
| "Whales are mammals" is fine, "are mammals reptiles" is fine,
| but "Whales are mammals reptiles" is incoherent.
|
| The longer you allow the chain to get, the more incoherent it
| becomes.
|
| "Whales are mammals that are reptiles that are vegetables
| too".
|
| Any 3-word fragment of that sentence is fine. But put it
| together, and it's an incoherent mess.
| Y_Y wrote:
| That _are_ reptiles!
| vjerancrnjak wrote:
| If you learn with Baum Welch you can get nonzero ood
| probabilities.
|
| Something like Markov Random Field is much better.
|
| Not sure if anyone managed to create latent hierarchies from
| chars to words to concepts. Learning NNs is far more tinkery
| than brutality of probabilistic graphical models.
| ssivark wrote:
| Uhhh... the above comment has a bunch of loose assertions that
| are not quite true, but with a enough truthiness that makes
| them hard to refute. So I'll point to my other comment for a
| more nuanced comparison of Markov models with tiny LLMs:
| https://news.ycombinator.com/item?id=45996794
| psychoslave wrote:
| > You'll find that the resulting output becomes incoherent
| garbage.
|
| I also do that kind of things with LLM. The other day, I don't
| remember the prompt (something casual really, not trying to
| trigger any issue) but le chat mistral started to regurgitate
| "the the the the the...".
|
| And this morning I was trying a some local models, trying to
| see if they could output some Esperanto. Well, that was really
| a mess of random morphs thrown together. Not syntactically
| wrong, but so out of touch with any possible meaningful
| sentence.
| lotyrin wrote:
| Yeah, some of the failure modes are the same. This one in
| particular is fun because even a human, given "the the the"
| and asked to predict what's next will probably still answer
| "the". How a Markov chain starts the the train and how the
| LLM does are pretty different though.
| papyrus9244 wrote:
| > This is why it's impossible to create a digital assistant, or
| really anything useful, via Markov Chain. The fact that they
| only generate sequences that existed in the source mean that it
| will never come up with anything creative.
|
| Or, in other words, a Markov Chain won't hallucinate. Having a
| system that only repeats sentences from it's source material
| and doesn't create anything new on its own is quite useful on
| some scenarios.
| Sohcahtoa82 wrote:
| > Or, in other words, a Markov Chain won't hallucinate.
|
| It very much can. Remember, the context windows used for
| Markov Chains are usually very short, usually in the single
| digit numbers of words. If you use a context length of 5,
| then when asking it what the next word should be, it has _no
| idea_ what the words were before the current context of 5
| words. This results in incoherence, which can certainly mean
| hallucinations.
| AndrewKemendo wrote:
| Your example is too sparse to make a conclusion from
|
| I'd offer an alternative interpretation: LLMs follow the Markov
| Decison modeling properties to encode the problem but use a very
| efficient policy for solver for the specific token based action
| space.
|
| That is to say they are both within the concept of a "markovian
| problem" but have wildly different path solvers. MCMC is a solver
| for an MDP, as is an attention network
|
| So same same, but different
| aespinoza wrote:
| Would you be willing to write an article comparing the results ?
| Or share the code you used to test? I am super interested in the
| results of this experiment.
| spencerflem wrote:
| Iirc there was some paper that showed that LLMs could be
| converted to Markov chains and vice versa, but the size of the
| chain was much much higher
| benob wrote:
| Was it this one? https://infini-gram.io/
| inciampati wrote:
| Markov chains have exponential falloff in correlations between
| tokens over time. That's dramatically different than real text
| which contains extremely long range correlations. They simply
| can't model long range correlations. As such, they can't be
| guided. They can memorize, but not generalize.
| zwaps wrote:
| This is the correct answer
| kittikitti wrote:
| As someone who developed chatbots with HMM's and the
| Transformers algorithms, this is a great and succinct answer.
| The paper, Attention Is All You Need, solved this drawback.
| vjerancrnjak wrote:
| Markov Random Fields also do that.
|
| Difference is obviously there but nothing prevents you from
| undirected conditioning of long range dependencies. There's
| no need to chain anything.
|
| The problem from a math standpoint is that it's an
| intractable exercise. The moment you start relaxing the joint
| opt problem you'll end up at a similar place.
| kleiba wrote:
| Markov chains of order n are essentially n-gram models - and this
| is what language models used to be for a very long time. They are
| quite good. As a matter of fact, they were so good that more
| sophisticated models often couldn't beat them.
|
| But then came deep-learning models - think transformers. Here,
| you don't represent your inputs and states discretely but you
| have a representation in a higher-dimensional space that aims at
| preserving some sort of "semantics": proximity in that space
| means proximity in meaning. This allows to capture nuances much
| more finely than it is possible with sequences of symbols from a
| set.
|
| Take this example: you're given a sequence of n words and are to
| predict a good word to follow that sequence. That's _the_ thing
| that LM 's do. Now, if you're an n-gram model and have never seen
| that sequence in training, what are you going to predict? You
| have no data in your probabilty tables. So what you do is
| _smoothing_ : you take away some of the probability mass that you
| have assigned during training to the samples you encountered and
| give it to samples you have not seen. How? That's the secret
| sauce, but there are multiple approaches.
|
| With NN-based LLMs, you don't have that exact same issue: even if
| you have never seen that n-word sequence in training, it will get
| mapped into your high-dimensional space. And from there you'll
| get a distribution that tells you which words are good follow-
| ups. If you have seen sequences of similar _meaning_ (even with
| different words) in training, these will probably be better
| predictions.
|
| But for n-grams, just because you have seen sequences of similar
| meaning (but with different words) during training, that doesn't
| really help you all that much.
| esafak wrote:
| https://en.wikipedia.org/wiki/Distributional_semantics
| ActorNightly wrote:
| In theory, you could have a large enough markov chain that
| mimicks an LLM, you would just need it to be exponentially
| larger in width.
|
| After all, its just matrix multplies start to finish.
|
| A lot of the other data operation (like normalization) can be
| represented as matrix multiplies, just less efficiently. In the
| same way that a transformer can be represented inefficiency as
| a set of fully connected deep layers.
| tlarkworthy wrote:
| Markov chains learn a fixed distribution, but transformers learn
| the distribution of distributions and latch onto what the current
| distribution based on evidence seen so far. So that's where the
| single shot learning comes from in transformer. Markov chains
| can't do that, they will not change the underlying distribution
| as they read.
| thatjoeoverthr wrote:
| Others have mentioned the large context window. This matters.
|
| But also important is embeddings.
|
| Tokens in a classic Markov chain are discrete surrogate keys.
| "Love", for example, and "love" are two different tokens. As are
| "rage" and "fury".
|
| In a modern model, we start with an embedding model, and build a
| LUT mapping token identities to vectors.
|
| This does two things for you.
|
| First, it solves the above problem, which is that "different"
| tokens can be conceptually similar. They're embedded in a space
| where they can be compared and contrasted in many dimensions, and
| it becomes less sensitive to wording.
|
| Second, because the incoming context is now a tensor, it can be
| used with differentiable model, back propagation and so forth.
|
| I did something with this lately, actually, using a trained BERT
| model as a reranker for Markov chain emmisions. It's rough but
| manages multiturn conversation on a consumer GPU.
|
| https://joecooper.me/blog/crosstalk/
| yobbo wrote:
| A hidden markov model (HMM) is theoretically capable of modelling
| text just as well any transformer. Typically, HMMs are
| probability distributions over a hidden discrete state space, but
| the distribution and state space can be anything. The size of the
| state space and transition function determines its capacity. RNNs
| are effectively HMMs, and recent ones like "Mamba" and so on are
| considered competent.
|
| Transformers can be interpreted as tricks that recreate the state
| as a function of the context window.
|
| I don't recall reading about attempts to train very large
| discrete (million states) HMMs on modern text tokens.
| qoez wrote:
| From a core openai insider who have likely trained very large
| markov models and large transformers:
| https://x.com/unixpickle/status/1935011817777942952
|
| Untwittered: A Markov model and a transformer can both achieve
| the same loss on the training set. But only the transformer is
| smart enough to be useful for other tasks. This invalidates the
| claim that "all transformers are doing is memorizing their
| training data".
| currymj wrote:
| bigram-trigram language models (with some smoothing tricks to
| allow for out-of-training-set generalization) were state of the
| art for many years. Ch. 3 of Jurafsky's textbook (which is modern
| and goes all the way to LLMs, embeddings etc.) is good on this
| topic.
|
| https://web.stanford.edu/~jurafsky/slp3/ed3book_aug25.pdf
|
| I don't know the history but I would guess there have been times
| (like the 90s) when the best neural language models were worse
| than the best trigram language models.
| ssivark wrote:
| The Markov property means that the next token is determined
| purely by the current token. Well, if it were a _Hidden_ Markov
| Model, the next state would actually be determined by the current
| state, and the respective tokens would be a lossy representation
| of the states.
|
| The problem with HMMs is that the sequence model (Markov
| transition matrix) accounts for much less context than even Tiny
| LLMs. One natural way to improve this is to allow the model to
| have more hidden states, representing more context -- called
| "clones" because these different hidden states would all be
| producing the same token while actually carrying different
| underlying contexts that might be relevant for future tokens. We
| are thus taking a non-Markov model (like a transformer) and re-
| framing its representation to be Markov. There have been sequence
| models with this idea aka Cloned HMMs (CHMMs) [1] or Clone-
| Structured Cognitive Graphs (CSCGs) [2]. The latter name is
| inspired by some related work in neuroscience, to which these
| were applied, which showed how these graphical models map nicely
| to "cognitive schemas" and are particularly effective in
| discovering interpretable models of spatial structure.
|
| I did some unpublished work a couple of years ago (while at
| Google DeepMind) studying how CHMMs scale to simple ~GB sized
| language data sets like Tiny Stories [3]. As a subjective
| opinion, while they're not as good as small transformers, they do
| generate text that is surprisingly good compared with naive
| expectations of Markov models. The challenge is that learning
| algorithms that we typically use for HMMs (eg. Expectation
| Maximization) are somewhat hard to optimize & scale for
| contemporary AI hardware (GPU/TPU), and a transformer model
| trained by gradient descent with lots of compute works pretty
| well, and also scales well to larger datasets and model sizes.
|
| I later switched to working on other things, but I still
| sometimes wonder whether it might be possible to cook up better
| learning algorithms attacking the problem of disambiguating
| contexts during the learning phase. The advantage with an
| explicit/structured graphical model like a CHMM is that it is
| _very interpretable_ , and allows for _extremely flexible
| queries_ at inference time -- unlike transformers (or other
| sequence models) which are trained as "policies" for generating
| token streams.
|
| When I say that transformers don't allow flexible querying I'm
| glossing over in-context learning capabilities, since we still
| lack a clear/complete understanding and what kinds of pre-
| training and fine-tuning one needs to elicit them (which are
| frontier research questions at the moment, and it requires a more
| nuanced discussion than a quick HN comment).
|
| It turns out, funnily, that these properties of CHMMs actually
| proved very useful [4] in understanding the conceptual
| underpinnings of in-context learning behavior using simple Markov
| sequence models instead of "high-powered" transformers. Some
| recent work from OpenAI [5] on sparse+interpretable transformer
| models seems to suggest that in-context learning in transformer
| LLMs might work analogously, by learning schema circuits. So the
| fact that we can learn similar schema circuits with CHMMs makes
| me believe that what we have is a _learning challenge_ and it 's
| not actually a fundamental representational incapacity (as is
| loosely claimed sometimes). In the spirit of full disclosure, I
| worked on [4]; if you want a rapid summary of all the ideas in
| this post, including a quick introduction to CHMMs, I would
| recommend the following video presentation / slides [6].
|
| [1]: https://arxiv.org/abs/1905.00507
|
| [2]: https://www.nature.com/articles/s41467-021-22559-5
|
| [3]: https://arxiv.org/abs/2305.07759
|
| [4]: https://arxiv.org/abs/2307.01201
|
| [5]: https://openai.com/index/understanding-neural-networks-
| throu...
|
| [6]: https://slideslive.com/39010747/schemalearning-and-
| rebinding...
| Anon84 wrote:
| Not that different. In fact, you can use Markov Chain theory as
| an analytical tool to study LLMs:
| https://arxiv.org/abs/2410.02724
|
| You could probably point your code to Google Books N-grams
| (https://storage.googleapis.com/books/ngrams/books/datasetsv3...)
| and get something that sounds (somewhat) reasonable.
| robot-wrangler wrote:
| Previously: https://news.ycombinator.com/item?id=39213410
| lukev wrote:
| Other comments in this thread do a good job explaining the
| differences in the Markov algorithm vs the transformer algorithm
| that LLMs use.
|
| I think it's worth mentioning that you have indeed identified a
| similarity, in that both LLMs and Markov chain generators have
| the same algorithm _structure_ : autoregressive next-token
| generation.
|
| Understanding Markov chain generators is actually a really really
| good step towards understanding how LLMs work, overall, and I
| think its a really good pedagogical tool.
|
| Once you understand Markov generating, doing a bit of handwaving
| to say "and LLMs are _just like this_ except with a more
| sophisticated statistical approach " has the benefit of being
| true, demystifying LLMs, and also preserving a healthy respect
| for just how powerful that statistical model can be.
| canjobear wrote:
| Right there in the second sentence. The sentence is ungrammatical
| because the n-gram model can't handle long term dependencies. "To
| obtain such a large medical database of the joints are risk
| factors" -- the verb should be singular and the predicate should
| be something else, like "to obtain such a large medical database
| ... _is_ difficult"
| kleiba wrote:
| What's a _tiny_ LLM, given that the first L stands for "large"?
| OvrUndrInformed wrote:
| Markov Processes are a pretty general concept that can be used to
| model just about anything if you let the "state" also incorporate
| some elements of the "history". I assume that the way
| transformers are used to model language (next token prediction)
| can be considered a Markov process where the transition function
| is modeled by the LLM. Transitions between a state (given by [n]
| previous tokens, which are the context + text generated so far)
| and the next state (given by state[n+1] tokens, which are the
| context + text generated so far + the newest generated token) are
| given by the probability distribution output by the LLM.
| Basically I think you can consider auto-regressive LLMs as
| parameterized Markov processes. Feel free to correct me if I'm
| wrong.
| unoti wrote:
| If you're not sure about what a Markov Chain is, or if you've
| never written something from scratch that _learns_ , take a look
| at this repo I made to try to bridge that gap and make it simple
| and understandable. You can read it in a few minutes. It starts
| with nothing but Python, and ends with generating text based on
| the D&D Dungeon Master Manual. https://github.com/unoti/markov-
| basics/blob/main/markov-basi...
| bilsbie wrote:
| It wouldn't be a Markov chain but I'd imagine you could make
| something functionally close to an LLM with creative uses of word
| frequency counts and probabilities over the massive amounts of
| text.
___________________________________________________________________
(page generated 2025-11-20 23:00 UTC)