Empirical Computation: Prompting versus Programming

2026-07-08 · Source: cs.SE updates on arXiv.org · Field: Technology & Digital — Software Development & Engineering, Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, long

Summary

This vision paper introduces "empirical computation," a paradigm where solutions are empirically most likely rather than necessarily correct, contrasting it with traditional "formal computation" (programming). It calls for the software engineering community to develop new foundations and techniques to analyze the properties of this approach. Experiments using GPT-3.5 Turbo on problems like sorting and searching demonstrate that LLM execution time is independent of computational complexity, but correctness significantly decreases as input size increases. For instance, sorting 50 numbers yields a 50% correctness probability. The study also found that correctness improves for "familiar" problem instances (e.g., LLM-generated) and is higher when inputs are provided in languages well-represented on the internet, such as English, compared to underrepresented languages like Korean.

Key takeaway

For software engineers integrating LLMs for computational tasks, recognize that "empirical computation" prioritizes probabilistic likelihood over guaranteed correctness. You should anticipate correctness degradation with increasing input size and consider prompt engineering, fine-tuning, or test-time training to improve reliability. Be aware that input language and "familiarity" significantly influence LLM performance, necessitating careful input design and validation for critical applications.

Key insights

Empirical computation, driven by LLMs, yields probabilistically correct solutions, demanding new software engineering analysis methods.

Principles

• LLM computation time is complexity-agnostic.
• Correctness decreases with input size.
• "Familiarity" and language representation impact accuracy.

Method

Experiments used LLM-GPT-Sort with GPT-3.5 Turbo, varying input properties like precision, magnitude, and array length for sorting, searching, longest palindromic substring, and subset sum problems.

In practice

• Use prompt engineering to maximize correctness.
• Consider fine-tuning or reinforcement learning for improvement.
• Provide inputs in well-represented languages for better accuracy.

Topics

• Empirical Computation
• Large Language Models
• Software Engineering
• Computational Complexity
• Prompt Engineering
• Correctness Analysis
• GPT-3.5 Turbo

Code references

• njmarko/llm-gpt-sort

Best for: AI Scientist, Software Engineer, Research Scientist

Related on AIssential

• Improving Alignment Between Human and Machine Codes: An Empirical Assessment of Prompt Engineering for Construct Identification in Psychology — Empirical prompt engineering, focusing on construct definition and examples, significantly improves LLM text classification alignment with human expert judgment.
• An Empirical Study of LLM-Generated Specifications for VeriFast — LLMs preserve functional behavior in VeriFast specifications but achieve modest verification success due to domain-specific knowledge gaps.
• Code, Chaos, and the Invisible Logic of LLMs — LLMs predict words probabilistically, not with human intention, leading to potential misunderstandings in code generation.
• The Context Dilemma: Prompting vs. RAG vs. Fine-Tuning — Prompting, RAG, and fine-tuning are distinct LLM techniques for managing context and grounding, not interchangeable solutions.
• How I think about LLM prompt engineering — LLMs extend Word2Vec's emergent word arithmetic into complex "vector programs" via self-attention and deep architectures.
• From Heuristic Selection to Automated Algorithm Design: LLMs Benefit from Strong Priors — Integrating benchmark code examples into prompts significantly enhances LLM-driven algorithm optimization performance and robustness.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.SE updates on arXiv.org.