# Empirical Computation: Prompting versus Programming

arXiv: https://arxiv.org/abs/2503.10954 · HTML: https://mlsanity.com/paper/2503.10954/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 13 Mar 2025.

## Builds on (most cited first, 10 of 10)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Parameter-Efficient Fine-Tuning for Large Models: A Comprehensive Survey](https://mlsanity.com/paper/2403.14608/) (2024)
- [Asleep at the Keyboard? Assessing the Security of GitHub Copilot's Code Contributions](https://mlsanity.com/paper/2108.09293/) (2021)
- [A Systematic Survey of Prompt Engineering in Large Language Models: Techniques and Applications](https://mlsanity.com/paper/2402.07927/) (2024)
- [A Comprehensive Survey on Test-Time Adaptation under Distribution Shifts](https://mlsanity.com/paper/2303.15361/) (2023)
- [Do Users Write More Insecure Code with AI Assistants?](https://mlsanity.com/paper/2211.03622/) (2022)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [Specifications: The missing link to making the development of LLM systems an engineering discipline](https://mlsanity.com/paper/2412.05299/) (2024)
- [Evaluating LLM-Based Regression Test Generation](https://mlsanity.com/paper/2501.11086/) (2025)
- [Software Security Analysis in 2030 and Beyond: A Research Roadmap](https://mlsanity.com/paper/2409.17844/) (2024)

## Abstract (arXiv)

Large Language Models (LLM) can solve *any* computational problem *without* an algorithm in a runtime *independent* of the computational complexity of that problem. Instead of specifying precisely how to solve problem instance using *programming*, we ask an LLM to solve the problem instance using *prompting*. Outputs are sampled from a distribution rather than generated procedurally. In this vision paper, we explore the challenges and opportunities of this new form of computation and observe that its capabilities and limits *cannot* be understood within the classic, rationalist framework of computation. Hence, we appeal to the software engineering (SE) community to develop the foundations and techniques required to analyze the properties of this "empirical computation" as it generates solutions to computational problems: How can we analyze and improve the correctness of LLMs solving a computational problem in the general, in the problem-specific, or in the instance-specific? What are the properties and fundamental limits of empirical computation? This paper aims to establish empirical computation as a field in SE that is timely and rich with interesting problems.