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.
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.
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-miniachieved 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