Computing with Agentic Oracles

This paper formalizes the concept of an 'agentic oracle' within the Stochastic-Oracle Turing Machine (SOTM) framework. While traditional stochastic oracles are stationary—meaning they respond to identical queries with the same probability distribution—agentic oracles are autonomous. They can decompose goals, manage internal state, and interact with external environments (e.g., file systems, APIs, or databases) to complete tasks.

The author distinguishes between two types of token costs: orchestration costs (visible at the query-response interface) and agentic costs (internal, hidden operations). By internalizing state and intermediate reasoning steps, an agentic oracle can reduce the total token expenditure required to reach a specific quality threshold. This creates a significant efficiency advantage over stationary oracles, which must repeatedly pass intermediate context back and forth across the query-response interface.

A critical contribution of this work is the formalization of 'goal-loss risk.' Unlike stationary oracles, where an error simply necessitates a retry, agentic oracles operating in environments can perform irreversible actions. If an action renders a goal unachievable, the computation fails regardless of how many additional queries are made. The paper provides criteria for avoiding such states and establishes lower bounds on token complexity, demonstrating that the risk of goal loss can impose a hard ceiling on the achievable quality of a task.

As AI systems transition from passive responders to autonomous agents that execute multi-step workflows, understanding the economics of their operation becomes vital. This framework provides a rigorous way to evaluate whether the autonomy of an agentic system is cost-effective compared to traditional, stateless model calls, while also highlighting the inherent risks of allowing AI to modify external environments.