Oracular Programming: A Modular Foundation for Building LLM-Enabled Software

Jonathan Laurent, André Platzer

Abstract

Building reliable software with Large Language Models (LLMs) currently suffers from a lack of modularity, leading to "spaghetti-code" pipelines where high-level logic is intertwined with low-level search strategies. We propose Oracular Programming, a paradigm that treats LLMs as inductive oracles. By separating problem-solving logic (Strategies) from search algorithms (Policies) and grounding few-shot examples as testable program components (Demonstrations), we create a framework for modular and maintainable AI systems. Our implementation, Delphyne, demonstrates that this structured approach allows smaller models to achieve 100% success on synthesis tasks at 10x lower cost than traditional baselines.

Introduction

The current state of LLM application development is often characterized by brittle pipelines. Developers frequently mix high-level problem decomposition with low-level search mechanics like retry logic, backtracking, and prompt selection. This lack of separation makes systems difficult to maintain and leads to "brittle examples"—few-shot prompts that become obsolete as the underlying code evolves. Oracular Programming addresses these challenges by providing a formal foundation for LLM-enabled software.

The Oracular Programming Triad

The core of this paradigm is the Oracular Programming Triad, which consists of three orthogonal components:

  • Strategies: Nondeterministic programs that define the plan for solving a problem. They specify "choice points" rather than hardcoded LLM calls.
  • Policies: Resource-aware algorithms (e.g., DFS, MCTS) that define how to navigate the search tree generated by a strategy.
  • Demonstrations: Grounded paths through a strategy's search tree. Unlike static text files, these function as unit tests, ensuring examples remain valid as the strategy changes.
The Oracular Programming Triad: Strategy, Policy, and Demonstrations.

Strategies and Search Trees

A key innovation is the "Opaque Space" abstraction. This allows a search policy to treat a simple LLM query and a complex, nested sub-strategy identically. When a strategy is executed, it "reifies" into a search tree. This process allows the system to manage LLM token budgets and costs by construction through a search stream protocol.

Reification of nondeterministic strategies into search trees.

Furthermore, because strategies produce serializable traces, the system can automatically extract successful paths to create new demonstrations. This "Search Reflection" enables a natural self-improvement mechanism reminiscent of Expert Iteration. The authors also experiment with a guess operator, where the system inspects the program's runtime stack to ask the LLM for values satisfying assertions, suggesting a future where "prompt engineering" is replaced by "program state inspection."

Evaluation and Results

The paradigm was evaluated using the Delphyne framework on two primary benchmarks: Code2Inv (loop invariant synthesis) and MiniF2F (formal theorem proving in Lean).

  • Efficiency in Synthesis: On Code2Inv, an oracular agent using gpt-4o-mini achieved a 100% success rate. Crucially, the structured search reduced costs by over 10x compared to standard conversational baselines using the same model.
  • Theorem Proving Scaling: In MiniF2F, the agent initially solved 57% of problems. After one round of automatic self-improvement via search reflection, the success rate climbed to 60%, showing a better scaling trend than the baseline.

Conclusion

Oracular Programming shifts the focus from "prompt engineering" to "program state inspection." While the practical Delphyne framework uses Python for accessibility, the authors acknowledge that Python’s gradual typing is a compromise compared to the full "correctness by construction" of a Haskell model. Future work will explore deeper Search Reflection, analyzing why certain branches failed to automatically refine strategies without human intervention.

Summary updated

Abstract

Large Language Models have proven surprisingly effective at solving a wide range of tasks from just a handful of examples. However, their lack of reliability and modularity limits their capacity to tackle large problems that require many steps of reasoning. In response, researchers have proposed advanced pipelines that leverage domain-specific knowledge to chain smaller prompts, provide intermediate feedback and improve performance through search. However, the current complexity of writing, tuning, maintaining and improving such pipelines has limited their sophistication. We propose oracular programming, a foundational paradigm for building LLM-enabled applications that lets domain experts express high-level problem-solving strategies as programs with unresolved choice points. These choice points are resolved at runtime by LLMs, which generalize from user-provided examples of correct and incorrect decisions. An oracular program is composed of three orthogonal components: a strategy that consists in a nondeterministic program with choice points that can be reified into a search tree, a policy that specifies how to navigate this tree with the help of LLM oracles, and a set of demonstrations that describe successful and unsuccessful search tree navigation scenarios across diverse problem instances. Each component is expressed in a dedicated programming language and can be independently improved or substituted. We address the key programming language design challenges of modularly composing oracular programs and enforcing consistency between their components as they evolve.
BibTeX
@misc{laurent2025oracular,
  author = {Jonathan Laurent and André Platzer},
  title = {{Oracular Programming: A Modular Foundation for Building LLM-Enabled Software}},
  year = {2025},
  eprint = {2502.05310},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.05310},
}
Figure