4 ms·

adding to this, software deals with non-determinism all the time. For example, web requests are non-deterministic. They depend, among other things, on the stat

adding to this, software deals with non-determinism all the time. For example, web requests are non-deterministic. They depend, among other things, on the state of the network. They also depend on the load of the machine serving the request. One way to think about this is: how easy is it for you to produce byte-for-byte deterministic builds of the software you're working on? If it's not trivial there's more non-determinism than is obvious.

skydhash 1y ago
Mostly the engineering part of software is dealing with non-determinism, by avoiding it or enforcing determinism. Take something like TCP, it's all about guaranteeing the determinism that either the message is sent and received or it is not. And we have a lot of algorithms that tries to guarantee consistency of information between the elements of a system.
- ants_everywhere 1y ago
  Right, you handle determinism by applying engineering. E.g. having fail safes, redundancies, creating robust processes, etc.
- ares623 1y ago
  But there is an underlying deterministic property in the TCP example. A message is either received within a timeout or not. How can that be extralopated with LLMs? How does a system independently know that it's arrived at a correct answer within a timeout or not? Has the halting problem been solved?
  - tptacek 1y ago
    You don't need to solve the halting problem in this situation, because you only need to accept a subset of valid, correct programs.
  - skydhash 1y ago
    > How can that be extralopated with LLMs? How does a system independently know that it's arrived at a correct answer within a timeout or not? That's the catch 22 with LLM. You're supposed to be both the asker and the verifier. Which in practice, it's not that great. LLMs will just find the snippets of code that matches somehow and just act on it (It's the "I'm feeling Lucky" button with extra steps) In traditional programming, coding is a notation too more than anything. You supposed to have a solution before coding, but because of how the human brain works, it's more like a blackboard, aka an helper for thinking. You write what you think is correct, verify your assumptions, then store and forget about all of it when that's true. Once in a while, you revisit the design and make it more elegant (at least you hope you're allowed to). LLM programming, when first started, was more about a direct english to finished code translation. Now, hope has scaled down and it's more about precise specs to diff proposal. Which frankly does not improve productivity as you can either have a generator that's faster and more precise (less costly too) or you will need to read the same amount of docs to verify everything as you would need to do to code the stuff in the first place (80% of the time spent coding). So no determinism with LLMs. The input does not have any formal aspects, and the output is randomly determined. And the domain is very large. It is like trying to find a specific grain of sand on a beach while not fully sure it's there. I suspect most people are doing the equivalent of taking a handful of sand and saying that's what they wanted all along.
    - tptacek 1y ago
      No? These kinds of analyses all seem to rely on the notion that the LLM-caller needs to accept whatever output the LLM provides. In practice, they discard all the outputs that don't compile, and then a further subset of the ones that don't --- those outputs that aren't instantly clear to the caller. My intuition for the problem here is that people are fixated on the nondeterminism of the LLM itself, which is of limited importance to the actual problem domain of code generation. The LLM might spit out ancient Egyptian hieroglyphics! It's true! The LLM is completely nondeterministic. But nothing like that is ever going to get merged into `main`. It's fine if you want to go on about how bad "vibe coding" is, with LLM-callers that don't bother to read LLM output, because they're not competent. But here we're assuming an otherwise competent developer. You can say the vibe coder is the more important phenomenon, but the viber doesn't implicate the halting problem.
anthem2025 1y ago
It’s not trivial largely because we didn’t bother to design deterministic builds because it didn’t seem to matter. There is not much about the actual problem that makes it difficult.
- ants_everywhere 1y ago
  if you don't have deterministic builds then you can't tell whether the executable you're running comes from the source code you can see. It is definitely non-trivial and large organizations spend money to try to make it happen.
  - anthem2025 1y ago
    Yes, I spent years working on exactly that. I personally was working with a compiler team to validate changes to eliminate non-determinism. That’s why I felt qualified to make the statement I did. It’s non trivial because you have to back through decades of tools and fix all of them to remove non determinism because they weren’t designed with that in mind. The hardest part was ensuring build environment uniformity but that’s a lot easier with docker and similar tooling.

skydhash 1y ago

Mostly the engineering part of software is dealing with non-determinism, by avoiding it or enforcing determinism. Take something like TCP, it's all about guaranteeing the determinism that either the message is sent and received or it is not. And we have a lot of algorithms that tries to guarantee consistency of information between the elements of a system.

ants_everywhere 1y ago
Right, you handle determinism by applying engineering. E.g. having fail safes, redundancies, creating robust processes, etc.
ares623 1y ago
But there is an underlying deterministic property in the TCP example. A message is either received within a timeout or not. How can that be extralopated with LLMs? How does a system independently know that it's arrived at a correct answer within a timeout or not? Has the halting problem been solved?
- tptacek 1y ago
  You don't need to solve the halting problem in this situation, because you only need to accept a subset of valid, correct programs.
- skydhash 1y ago
  > How can that be extralopated with LLMs? How does a system independently know that it's arrived at a correct answer within a timeout or not? That's the catch 22 with LLM. You're supposed to be both the asker and the verifier. Which in practice, it's not that great. LLMs will just find the snippets of code that matches somehow and just act on it (It's the "I'm feeling Lucky" button with extra steps) In traditional programming, coding is a notation too more than anything. You supposed to have a solution before coding, but because of how the human brain works, it's more like a blackboard, aka an helper for thinking. You write what you think is correct, verify your assumptions, then store and forget about all of it when that's true. Once in a while, you revisit the design and make it more elegant (at least you hope you're allowed to). LLM programming, when first started, was more about a direct english to finished code translation. Now, hope has scaled down and it's more about precise specs to diff proposal. Which frankly does not improve productivity as you can either have a generator that's faster and more precise (less costly too) or you will need to read the same amount of docs to verify everything as you would need to do to code the stuff in the first place (80% of the time spent coding). So no determinism with LLMs. The input does not have any formal aspects, and the output is randomly determined. And the domain is very large. It is like trying to find a specific grain of sand on a beach while not fully sure it's there. I suspect most people are doing the equivalent of taking a handful of sand and saying that's what they wanted all along.
  - tptacek 1y ago
    No? These kinds of analyses all seem to rely on the notion that the LLM-caller needs to accept whatever output the LLM provides. In practice, they discard all the outputs that don't compile, and then a further subset of the ones that don't --- those outputs that aren't instantly clear to the caller. My intuition for the problem here is that people are fixated on the nondeterminism of the LLM itself, which is of limited importance to the actual problem domain of code generation. The LLM might spit out ancient Egyptian hieroglyphics! It's true! The LLM is completely nondeterministic. But nothing like that is ever going to get merged into `main`. It's fine if you want to go on about how bad "vibe coding" is, with LLM-callers that don't bother to read LLM output, because they're not competent. But here we're assuming an otherwise competent developer. You can say the vibe coder is the more important phenomenon, but the viber doesn't implicate the halting problem.

anthem2025 1y ago

It’s not trivial largely because we didn’t bother to design deterministic builds because it didn’t seem to matter. There is not much about the actual problem that makes it difficult.

ants_everywhere 1y ago
if you don't have deterministic builds then you can't tell whether the executable you're running comes from the source code you can see. It is definitely non-trivial and large organizations spend money to try to make it happen.
- anthem2025 1y ago
  Yes, I spent years working on exactly that. I personally was working with a compiler team to validate changes to eliminate non-determinism. That’s why I felt qualified to make the statement I did. It’s non trivial because you have to back through decades of tools and fix all of them to remove non determinism because they weren’t designed with that in mind. The hardest part was ensuring build environment uniformity but that’s a lot easier with docker and similar tooling.