Computing with Stochastic Oracles in AI-Augmented Computation

This paper investigates the computational limits of AI-augmented systems, modeled as Stochastic-Oracle Turing Machines (SOTMs). The core question is how the interaction scheme between a machine and an AI oracle—specifically whether the oracle caches responses or provides fresh, independent responses—affects the machine's ability to solve tasks. The author uses an information-theoretic framework to define performance ceilings, focusing on how the transcript of queries and responses constrains the machine's ability to identify hidden oracle states or produce high-quality outputs.

The study distinguishes between two primary interaction modes. In a cached-response oracle, repeating a query yields the same response, meaning the transcript provides no new information beyond the first call. This imposes a hard ceiling on performance, as the machine cannot reduce ambiguity through repetition. In contrast, a fresh-response oracle provides independent samples for each call. This allows the machine to accumulate evidence, enabling it to overcome the limitations of a single, potentially noisy response. The author shows that for binary tasks, fresh responses allow the error probability to decrease exponentially at the Chernoff rate.

As AI systems are increasingly used as sub-components in larger computational pipelines, understanding the "token cost" of reliability is essential. This paper provides a formal basis for system designers to evaluate whether their chosen oracle architecture—and their strategy for querying it—is sufficient to meet a target quality level. By characterizing the trade-offs between token consumption and output quality, the work helps bridge the gap between abstract AI capabilities and the practical engineering of robust, AI-augmented software.