LLMs Offer Alternative to Traditional Programming Through Sampling-Based Computation

A research paper from the software engineering community suggests that large language models represent a fundamentally different paradigm for computation—one where solutions emerge from statistical sampling rather than algorithmic specification.

The Shift from Algorithms to Prompts#

Rather than implementing precise step-by-step procedures to solve computational problems, this approach leverages LLM agents to find solutions through natural language prompts. The key departure is that results are drawn from a probability distribution instead of being generated through deterministic logic. Importantly, the runtime for such solutions remains independent of the traditional computational complexity measures used to analyze conventional algorithms.

New Questions for Software Engineering#

This unconventional computation model raises critical challenges that existing computer science frameworks struggle to address. The authors argue that understanding empirical computation—computation based on statistical sampling—requires fresh perspectives beyond the classical, rationalist theories of computation.

The paper identifies three levels of investigation:

• General correctness: How can we establish and improve reliability across LLM-based solutions broadly?
• Problem-specific analysis: What techniques work for particular problem domains?
• Instance-specific evaluation: How do we assess performance on individual problem instances?

Establishing a New Field#

The vision is to position empirical computation as an active research area within software engineering. This would involve developing foundational techniques to characterize the capabilities and limits of this probabilistic form of problem-solving—questions that conventional algorithmic theory cannot fully answer.