LLMs may be doing a form of computation that nobody has the right tools to measure yet.
A vision paper posted to arXiv makes a pointed case: large language models can tackle computational problems without an underlying algorithm, producing outputs sampled from a probability distribution rather than generated by deterministic code. The authors call this "empirical computation" and argue it operates outside the boundaries of classical complexity theory — meaning the usual ways software engineers measure correctness, efficiency, and limits simply do not apply. The paper asks whether the field can even define what "correct" means when the same prompt can return different answers on different runs.
The stakes are practical, not just philosophical. If AI agents are increasingly used to solve real computational tasks — data transformation, code generation, logical inference — and those outputs cannot be formally verified with existing tools, the software engineering field has a gap it has not yet named, let alone closed. The authors are explicitly calling on the SE community to build those foundations from scratch.
The paper is candid that this is a vision document, not a proof. What it offers is a framing, not a solution — and framing papers in AI have a mixed record of producing the discipline-wide response they call for. Still, the core observation is hard to dismiss: the industry is already shipping LLM-powered systems into production while the theoretical groundwork for analyzing them remains unbuilt.