jschuster.org
Specifications, Not Determinism: Why LLMs Are Not Compilers
There are many legitimate criticisms to be levied at LLMs. The environmental damage, the unauthorized use of mass quantities of intellectual property, the decreased trust in our sources of information, and more are issues we should be deeply concerned about.
However, there’s one problem that I think we’re mis-identifying: the notion that LLMs are nondeterministic.
This most often comes up in the context of code generation. Some LLM enthusiasts will claim that asking an LLM to generate code from a prompt is no different than asking a compiler to generate assembly code from a higher-level language. Therefore, we shouldn’t have to review the LLM’s output. “It’s just another level of abstraction,” they say. “You don’t hand-write your assembly code or review the compiler’s output line-by-line, right?”
The other side is quick to rebut: “But an LLM isn’t deterministic like my compiler is! It might generate different code each time I run the prompt, so how can I know what to expect?”
The sentiment of that rebuttal is right, but the diagnosis is wrong. _Something_ about LLM-based code generation is qualitatively different than traditional compilation. But the problem isn’t nondeterminism. Consider this statement:
x = (1 + 2) * (3 + 4)
1 | x = (1 + 2) * (3 + 4)
---|---
A compiler could translate that statement down to assembly code that looks roughly like this:
[crayon-6aba6e82c6448788719694 inline="1" lang="default" decode="true" ]temp1 = 1 + 2 temp2 = 3 + 4 x = temp1 * temp2
123 | [crayon-6aba6e82c6448788719694 inline="1" lang="default" decode="true" ]temp1 = 1 + 2temp2 = 3 + 4x = temp1 * temp2
---|---
[/crayon]
But the order in which we evaluate the expressions in parentheses doesn’t matter, right? So a sufficiently smart compiler could decide it’s more efficient to output this code instead:
temp1 = 3 + 4 temp2 = 1 + 2 x = temp2 * temp1
123 | temp1 = 3 + 4temp2 = 1 + 2x = temp2 * temp1
---|---
Same high-level program, two different assembly programs. That’s a nondeterministic transformation. Yet I bet you would accept either one without a second thought.
“But the _behavior_ of the program is still deterministic!”, you say. “Either way, we end up with x = 21.” Ok, then how about this program?
<code>fn sleepAndPrintFoo(): sleep(1000) print("foo") fn sleepAndPrintBar(): sleep(1000) print("bar") fn main(): t1 = Thread.start(sleepAndPrintFoo) t2 = Thread.start(sleepAndPrintBar) waitForAllThreadsToComplete(t1, t2)</code>
123456789101112 | <code>fn sleepAndPrintFoo(): sleep(1000) print("foo") fn sleepAndPrintBar(): sleep(1000) print("bar") fn main(): t1 = Thread.start(sleepAndPrintFoo) t2 = Thread.start(sleepAndPrintBar) waitForAllThreadsToComplete(t1, t2)</code>
---|---
You can’t know which thread is going to execute first ahead of time: that depends on your OS’s thread scheduler. So this program might print “foobar” or “barfoo”. Either one is completely valid.
So a traditional compiler has nondeterminism in both the transformation to assembly code, and in the observable behavior of the resulting program. Yet this still _feels_ different from asking an LLM write a program from a prompt. Why?
This feels different because programming languages and compilers have _specifications_. A specification is some statement of a program’s behavior that the author guarantees that the program provides. Sure, different language specs may be at different places on the rigor/ambiguity spectrum from “fully formalized, mathematically defined spec” to “whatever the compiler does is the spec”. But in any of those cases, you can reasonably expect specific behavior from those compilers, and you’re justified in filing a bug if the behavior doesn’t match expectations.
LLMs, though, don’t have that kind of specification. If we defined an LLM’s interface as a function “executePrompt” of type “String -> String”, what could the author of executePrompt guarantee to the user? Not much. We can say that _probably_ the output will be something that looks like a plausible response to the input. But even that weak specification can’t be guaranteed to the same extent that we guarantee “(1 + 2) * (3 + 4)” results in 21.
So that’s where we land, and that’s why “prompts are just another level of abstraction” doesn’t make sense to so many engineers. The whole concept of software engineering is built on the idea of abstraction and modularity: programming against a specified interface so that we can separate implementation details from intended behavior. When there is no specification, then there’s nothing to rely on, so we’re left trying to assemble a reliable system from unreliable components.
Is “nondeterminism” versus “specifications” a nitpick about terminology? Yes, a bit. But if we’re trying to figure out how LLMs fit into the practice of software engineering, then I think it behooves us to correctly identify their shortcomings. Only the best possible diagnoses will help us find the best possible resolutions.
So next time you’re talking about LLMs and the ways they might fit into software engineering, remember: nondeterminism per se isn’t the problem. We’ve been wrestling with nondeterminism for decades, and while it’s not easy, we have methods for handling it. But a lack of any kind of specification to describe what we can expect from that non-deterministic output? That’s a big problem, and requires a totally new kind of approach to handle.
