🤖 AI

Empirical Computation: Prompting versus Programming

This vision paper proposes "empirical computation" as a new paradigm where Large Language Models solve computational problems via prompting rather than traditional programming, arguing that its unique capabilities and limits require the software engineering community to develop new foundational theories and techniques for analyzing correctness and fundamental boundaries.

Original authors: Eric Tang, Jing Liu, Marcel Böhme

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Eric Tang, Jing Liu, Marcel Böhme

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have two ways to get a job done: Programming and Prompting.

The Old Way: Programming (The Strict Architect)

Think of traditional programming like hiring a strict, by-the-book architect. You give them a blueprint with exact measurements, specific materials, and a step-by-step plan.

How it works: You tell the computer exactly how to solve a problem, like sorting a list of numbers. You say, "Use this specific algorithm (Merge Sort), take these inputs, and follow these rules."
The Result: If the architect makes a mistake, you can find the exact broken brick in the blueprint, fix it, and know for a fact the building will stand correctly next time.
The Limit: The time it takes to build depends on the complexity of the math. Sorting a huge list of numbers takes a predictable amount of time based on the size of the list (specifically, $O(n \log n)$ ).

The New Way: Prompting (The Intuitive Artist)

Now, imagine you hire a brilliant, intuitive artist instead. You don't give them a blueprint. You just say, "Hey, here's a messy pile of numbers, could you sort them for me?"

How it works: You use natural language (a "prompt") to describe the problem. The "computer" (a Large Language Model or LLM) doesn't follow a strict set of rules. Instead, it guesses the most likely answer based on everything it has ever read on the internet. It's like a chef tasting a soup and guessing the ingredients rather than following a recipe.
The Result: The answer comes back fast, but it's a guess, not a guarantee. It's the "most likely" answer, not the "proven correct" answer.

What the Paper Found: The "Empirical" Surprise

The authors of this paper ran experiments to see how well this "Intuitive Artist" performs on classic math problems like sorting numbers or finding items in a list. Here is what they discovered:

1. Time doesn't work the same way

Programming: If you double the number of items to sort, the time it takes goes up in a specific, mathematical way.
Prompting: The time it takes the LLM to sort numbers goes up linearly (just a straight line) as the list gets bigger. Why? Not because the math is harder, but because the LLM has to read and write more words (tokens) to handle the longer list. It's like reading a longer book; it takes more time to read the words, not because the story is more complex.

2. Accuracy drops as things get bigger

Programming: A correct program is 100% correct every time.
Prompting: The LLM is great at small tasks but gets confused as the list grows.
- For a list of 50 numbers, the LLM got it right about 90% of the time.
- For a list of 150 numbers, it only got it right about 58% of the time.
- If you ask it to find a specific pattern in a short string, it might fail almost immediately if the string gets slightly longer.
- The "Thinking" Mode: When the LLM is allowed to "think" (reason step-by-step) before answering, it stays very accurate, but it takes much longer.

3. The Language Game

Programming: It doesn't matter if you write the code in English or German; the computer reads the symbols the same way.
Prompting: The LLM is biased by what it has read on the internet.
- If you ask the LLM to sort numbers written as English words ("one, two, three"), it does a great job.
- If you ask it to sort numbers written in German ("eins, zwei, drei"), it fails almost completely.
- Why? The LLM has seen millions of English examples on the internet but far fewer German ones. It's like asking a chef to cook a dish they've never seen before; they might guess wrong.

4. The "Broken Brick" Problem

Programming: If a program fails, you can find the bug, fix the code, and the problem is solved forever.
Prompting: If the LLM gives a wrong answer, you can't easily find "the bug." You can't point to a specific line of code to fix. You might try changing your prompt or asking it to "think harder," but there is no guarantee it will work next time. It's like trying to fix a dream by changing the dreamer's mood.

The Big Takeaway

The paper argues that we are entering a new era called "Empirical Computation."

In the old world, we trusted computers because they followed strict rules (Rationalist framework). In this new world, we are trusting computers because they make "educated guesses" based on data (Empirical framework).

The authors are calling on software engineers to stop trying to analyze these AI systems like old-school programs. We need new tools to measure, test, and understand how these "guessing machines" work, because the old rules of math and logic don't fully apply to them anymore. We need to figure out how to trust a result that is "probably right" rather than "definitely right."

Technical Summary: Empirical Computation: Prompting versus Programming

Problem Statement

The paper identifies a paradigm shift in solving computational problems: moving from programming (specifying precise algorithms and data structures) to prompting (providing informal, natural language descriptions to Large Language Models or agents). While traditional computation relies on deterministic procedures with verifiable correctness and well-defined complexity bounds (e.g., $O(n \log n)$ for sorting), "empirical computation" relies on sampling outputs from a probability distribution.

The core problem is that the capabilities and limits of this new form of computation cannot be understood within the classic, rationalist framework of computer science. Specifically:

Lack of Determinism: Outputs are not procedurally generated but are the "empirically most likely" result, making them susceptible to hallucinations and errors that cannot be localized or repaired via traditional debugging.
Ambiguity in Input: Unlike programming, which requires formal contracts (types, formats), prompting accepts informal inputs where interpretation depends on context and the model's training distribution.
Unclear Complexity: Runtime behavior appears decoupled from classical computational complexity, correlating instead with tokenization and model inference behavior.
Verification Gap: Existing software engineering (SE) techniques (static analysis, formal verification) are ill-equipped to analyze systems where no explicit program exists to verify.

Methodology

The authors conducted preliminary experiments to characterize the efficiency and correctness of empirical computation across five classic computational problems:

Sorting: Ascending order of random numbers.
Searching: Finding an index in sorted and unsorted lists.
Longest Palindromic Substring: Finding the longest palindromic sequence in a string.
Subset Sum Problem (SSP): Finding a subset of numbers that sum to a target value.

Experimental Setup:

Model: The experiments utilized the open-weights model gemma-4-26b-a4b running locally on a MacBook Pro (M5 Pro, 48GB RAM) to eliminate network latency.
Configurations: Three modes were tested:
- Default: Temperature = 1.0.
- Deterministic: Temperature = 0.0.
- Thinking: Reasoning mode enabled.
Metrics:
- Efficiency: Time to solution and time to first correct solution.
- Correctness: Proportion of trials returning the mathematically correct answer.
Variables: Input size ( $n$ ), number precision, and language representation (digits vs. words in various languages: English, German, Korean, Japanese, etc.).
Ground Truth: For non-trivial problems (Substring, SSP), simple Python programs generated the correct answers for validation.

Key Results

1. Efficiency vs. Classical Complexity

Contrary to classical theory, the runtime of empirical computation does not strictly follow the algorithmic complexity of the problem (e.g., $O(n)$ vs. $O(n \log n)$ ).

Linear Scaling: For sorting, searching, and SSP, the time to solution increased linearly with input size ( $O(n)$ ) across all modes. The authors attribute this to the linear increase in input/output tokens rather than computational logic.
Token Dependency: The time taken to increment a number was comparable to predicting plaintext from a SHA-512 hash, suggesting runtime is driven by tokenization and inference mechanics rather than problem difficulty.
Thinking Mode Cost: Enabling "thinking" (reasoning) significantly increased runtime (e.g., up to 275s for sorting 150 elements) but maintained high correctness.

2. Correctness and Input Size

Size Sensitivity: In Default and Deterministic modes, correctness degraded rapidly as input size increased.
- For sorting 50 integers, correctness dropped to ~50% (coin flip probability).
- For sorting 150 integers, correctness fell to ~58% (despite the linear time increase).
- For the Subset Sum problem, correctness approached zero for lists of length 10.
- For the Substring problem, correctness dropped to near zero for strings of length 5.
Thinking Mode Resilience: When reasoning capabilities were enabled, correctness remained high (>90%) even for larger inputs, though within token/time limits.

3. Impact of Natural Language Representation

The study investigated how the language used to represent numbers affects correctness.

Data Representation Bias: Correctness is heavily dependent on the language's representation in the model's training data.
High vs. Low Representation: Sorting numbers written in English (well-represented) yielded >95% correctness for size 20. In contrast, sorting numbers written in German (underrepresented) yielded <1% correctness for the same size.
Conclusion: Empirical computation is not language-agnostic; it is biased toward languages and formats prevalent in the training corpus.

4. Error Characteristics

Unlike traditional programs where faults can be localized to specific lines of code, errors in empirical computation are non-deterministic. The LLM might:

Add numbers not present in the input.
Remove numbers present in the input.
Duplicate numbers.
Fail to sort the entire list.
Truncate large inputs.

Key Contributions

Definition of Empirical Computation: The paper formally introduces "empirical computation" as a distinct field where solutions are generated via prompting and sampling rather than procedural execution.
Empirical Characterization: It provides the first systematic measurement of efficiency and correctness for LLMs solving classic algorithmic problems, revealing that runtime correlates with tokenization rather than algorithmic complexity.
Identification of Limits: The study demonstrates that without reasoning modes, empirical computation fails to scale reliably with input size and is highly sensitive to the linguistic representation of inputs.
Call for New SE Foundations: The authors argue that the software engineering community must develop new tools for "empirical program analysis" (statistical, counterfactual, or causal reasoning) to analyze, estimate, and predict the correctness of these systems.

Significance and Vision

The paper posits that the software engineering community cannot rely on classic rationalist frameworks or existing program analysis tools to ensure the trustworthiness of AI-driven computation. As LLMs and agents become integral to solving computational problems, the field must evolve to address:

How to analyze correctness in the absence of a formal program.
How to define and test the limits of empirical computation.
How to improve correctness for specific problem instances without introducing regressions.

The authors frame this as a timely and rich area for research, urging the development of "empirical program analysis" techniques to bridge the gap between the probabilistic nature of LLMs and the rigorous demands of software engineering. The paper does not claim to solve these problems but aims to establish the field and highlight the urgent need for new theoretical and practical foundations.