5 ms·

Since LLM’s aren’t deterministic isn’t it impossible? What would keep it from iterating back and forth between two failing states forever? Is this the halting p

by cschep 1y ago

Since LLM’s aren’t deterministic isn’t it impossible? What would keep it from iterating back and forth between two failing states forever? Is this the halting problem?

gloxkiqcza 1y ago
Correct me if I’m wrong but LLMs are deterministic, the randomness is added intentionally in the pipeline.
- deleted 1y ago
  [deleted]
- zekica 1y ago
  The two parts of your statement don't go together. A list of potential output tokens and their probabilities are generated deterministically but the actual token returned is then chosen at random (weighted based on the "temperature" parameter and the probability value).
  - mzl 1y ago
    That depends on the sampling strategy. Greedy sampling takes the max token at each step.
  - galaxyLogic 1y ago
    I assume they use software-based pseudo-random-number generators. Those can typically be given a seed-value which determines (deterministically) the sequence of random numbers that will be generated. So if an LLM uses a seedable pseudo-random-number-generator for its random numbers, then it can be fully deterministic.
    - lou1306 1y ago
      There are subtle sources of nondeterminism in concurrent floating point operations, especially on GPU. So even with a fixed seed, if an LLM encounters two tokens with very close likelihoods, it may pick one or the other across different runs. This has been observed even with temperature=0, which in principle does not involve _any_ randomness (see arXiv paper cited earlier in this thread).
- mzl 1y ago
  LLMs can be run in a mostly deterministic mode (see https://docs.pytorch.org/docs/stable/notes/randomness.html https://docs.pytorch.org/docs/stable/notes/randomness.html for some info on running PyTorch programs). Varying the deployment type (chip model, number of chips, batch size, ...) can also change the output due to rounding errors. See https://arxiv.org/abs/2506.09501 https://arxiv.org/abs/2506.09501 for some details on that.
mzl 1y ago
Many compilers are not deterministic (it is why repeatable builds is not a solved problem), and many LLMs can be run in a mostly deterministic way.
- miningape 1y ago
  Repeatable builds are not a requirement for determinism. Since the outputs can be determined based on the exact system running the code, it is deterministic - even though the output can vary based on the system running the code. This is to say every output can be understood by understanding the systems that produced it. There are no dice rolls required. I.e. if it builds wrongly every other Tuesday, the reason for that can be determined (there's a line of code describing this logic).
  - rthnbgrredf 1y ago
    While I don't disagree with your comment, I would say that a that a large language model, and a Docker build with a complex Dockerfile, where not every version is exactly pinned down, are quite similar. You might have updates from the base image, you might have updates from one of the thousands of dependencies. And each day you rebuild the image, you will get a different checksum. Similar to how you get different answers from the LLM. And just like you can get wrong answers from the LLM, you can also get Docker builds that start to behave differently over time. So this is how it often is in practice. Then there is the possibility to pin down every version, and also some large language models support temperature 0. This is more in the realm of determinism.
daxfohl 1y ago
I'd suggest the problem isn't that LLMs are nondeterministic. It's that English is. With a coding language, once you know the rules, there's no two ways to understand the instructions. It does what it says. With English, good luck getting everyone and the LLM to agree on what every word means. Going with LLM as a compiler, I expect by the time you get the English to be precise enough to be "compiled", the document will be many times larger than the resulting code, no longer be a reasonable requirements doc because it reads like code, but also inscrutable to engineers because it's so verbose.
- dworks 1y ago
  Sure, we cannot agree on the correct interpretation of the instructions. But, we also cannot define what is correct output. First, the term “accuracy” is somewhat meaningless when it comes to LLMs. Anything that an LLM outputs is by definition “accurate” or “correct” from a technical point of view because it was produced by the model. The term accuracy then is not a technical or perhaps even factual term, but a sociological and cultural term, where what is right or wrong is determined by society, and even we sometimes have a hard time determining what is true or note (see: philosophy).
  - miningape 1y ago
    What? What does philosophy have to do with anything? If you cannot agree on the correct interpretation, nor output, what stops an LLM from solving the wrong problem? what stops an LLM from "compiling" the incorrect source code? What even makes it possible for us to solve a problem? If I ask an LLM to add a column to a table and it drops the table it's a critical failure - not something to be reinterpreted as a "new truth". Philosophical arguments are fine when it comes to loose concepts like human language (interpretive domains). On the other hand computer languages are precise and not open to interpretation (formal domains) - so philosophical arguments cannot be applied to them (only applied to the human interpretation of code). It's like how mathematical "language" (again a formal domain) describes precise rulesets (axioms) and every "fact" (theorem) is derived from them. You cannot philosophise your way out of the axioms being the base units of expression, you cannot philosophise a theorem into falsehood (instead you must show through precise mathematical language why a theorem breaks the axioms). This is exactly why programming, like mathematics, is a domain where correctness is objective and not something that can be waved away with philosophical reinterpretation. (This is also why the philosophy department is kept far away from the mathematics department)
pjmlp 1y ago
As much as many devs that haven't read the respective ISO standards, the compiler manual back to back, and then get surprised with UB based optimizations.

by cschep 1y ago

Since LLM’s aren’t deterministic isn’t it impossible? What would keep it from iterating back and forth between two failing states forever? Is this the halting problem?

gloxkiqcza 1y ago

Correct me if I’m wrong but LLMs are deterministic, the randomness is added intentionally in the pipeline.

deleted 1y ago
[deleted]
zekica 1y ago
The two parts of your statement don't go together. A list of potential output tokens and their probabilities are generated deterministically but the actual token returned is then chosen at random (weighted based on the "temperature" parameter and the probability value).
- mzl 1y ago
  That depends on the sampling strategy. Greedy sampling takes the max token at each step.
- galaxyLogic 1y ago
  I assume they use software-based pseudo-random-number generators. Those can typically be given a seed-value which determines (deterministically) the sequence of random numbers that will be generated. So if an LLM uses a seedable pseudo-random-number-generator for its random numbers, then it can be fully deterministic.
  - lou1306 1y ago
    There are subtle sources of nondeterminism in concurrent floating point operations, especially on GPU. So even with a fixed seed, if an LLM encounters two tokens with very close likelihoods, it may pick one or the other across different runs. This has been observed even with temperature=0, which in principle does not involve _any_ randomness (see arXiv paper cited earlier in this thread).
mzl 1y ago
LLMs can be run in a mostly deterministic mode (see https://docs.pytorch.org/docs/stable/notes/randomness.html https://docs.pytorch.org/docs/stable/notes/randomness.html for some info on running PyTorch programs). Varying the deployment type (chip model, number of chips, batch size, ...) can also change the output due to rounding errors. See https://arxiv.org/abs/2506.09501 https://arxiv.org/abs/2506.09501 for some details on that.

mzl 1y ago

Many compilers are not deterministic (it is why repeatable builds is not a solved problem), and many LLMs can be run in a mostly deterministic way.

miningape 1y ago
Repeatable builds are not a requirement for determinism. Since the outputs can be determined based on the exact system running the code, it is deterministic - even though the output can vary based on the system running the code. This is to say every output can be understood by understanding the systems that produced it. There are no dice rolls required. I.e. if it builds wrongly every other Tuesday, the reason for that can be determined (there's a line of code describing this logic).
- rthnbgrredf 1y ago
  While I don't disagree with your comment, I would say that a that a large language model, and a Docker build with a complex Dockerfile, where not every version is exactly pinned down, are quite similar. You might have updates from the base image, you might have updates from one of the thousands of dependencies. And each day you rebuild the image, you will get a different checksum. Similar to how you get different answers from the LLM. And just like you can get wrong answers from the LLM, you can also get Docker builds that start to behave differently over time. So this is how it often is in practice. Then there is the possibility to pin down every version, and also some large language models support temperature 0. This is more in the realm of determinism.

daxfohl 1y ago

I'd suggest the problem isn't that LLMs are nondeterministic. It's that English is. With a coding language, once you know the rules, there's no two ways to understand the instructions. It does what it says. With English, good luck getting everyone and the LLM to agree on what every word means. Going with LLM as a compiler, I expect by the time you get the English to be precise enough to be "compiled", the document will be many times larger than the resulting code, no longer be a reasonable requirements doc because it reads like code, but also inscrutable to engineers because it's so verbose.

dworks 1y ago
Sure, we cannot agree on the correct interpretation of the instructions. But, we also cannot define what is correct output. First, the term “accuracy” is somewhat meaningless when it comes to LLMs. Anything that an LLM outputs is by definition “accurate” or “correct” from a technical point of view because it was produced by the model. The term accuracy then is not a technical or perhaps even factual term, but a sociological and cultural term, where what is right or wrong is determined by society, and even we sometimes have a hard time determining what is true or note (see: philosophy).
- miningape 1y ago
  What? What does philosophy have to do with anything? If you cannot agree on the correct interpretation, nor output, what stops an LLM from solving the wrong problem? what stops an LLM from "compiling" the incorrect source code? What even makes it possible for us to solve a problem? If I ask an LLM to add a column to a table and it drops the table it's a critical failure - not something to be reinterpreted as a "new truth". Philosophical arguments are fine when it comes to loose concepts like human language (interpretive domains). On the other hand computer languages are precise and not open to interpretation (formal domains) - so philosophical arguments cannot be applied to them (only applied to the human interpretation of code). It's like how mathematical "language" (again a formal domain) describes precise rulesets (axioms) and every "fact" (theorem) is derived from them. You cannot philosophise your way out of the axioms being the base units of expression, you cannot philosophise a theorem into falsehood (instead you must show through precise mathematical language why a theorem breaks the axioms). This is exactly why programming, like mathematics, is a domain where correctness is objective and not something that can be waved away with philosophical reinterpretation. (This is also why the philosophy department is kept far away from the mathematics department)

pjmlp 1y ago

As much as many devs that haven't read the respective ISO standards, the compiler manual back to back, and then get surprised with UB based optimizations.