Search papers, labs, and topics across Lattice.
This paper introduces the Stochastic-Oracle Turing Machine (SOTM) framework, which models AI-augmented computation through interactions with probabilistic oracles that provide context-dependent responses. It explores two oracle-response schemes鈥攃ached and fresh responses鈥攈ighlighting how they influence the performance ceilings of the SOTM based on transcript information and response reuse. Key findings reveal that while cached responses impose strict performance limits, fresh responses significantly enhance error reduction and output quality by allowing for the accumulation of independent evidence across multiple queries.
Fresh-response oracles can exponentially decrease error rates by leveraging independent evidence, challenging the limits imposed by cached responses.
The Stochastic-Oracle Turing Machine (SOTM) framework models AI-augmented computation as the interaction of a probabilistic Turing machine with an oracle whose responses are drawn from context-dependent distributions. This paper studies what an SOTM can achieve under two oracle-response schemes: in a cached-response oracle, each distinct query receives one response that is reused on later calls to the same query, while in a fresh-response oracle, each call returns an independent response. In both schemes, the SOTM first computes from its input and internal random source to generate its first query, then proceeds adaptively, computing from its query-response transcript (the record of queries issued and responses received) to generate each subsequent query or produce a final output. Cached responses impose two transcript-based ceilings on achievable performance: a correct-identification ceiling governed by the total variation distance between the transcript distributions induced by the hidden states of the oracle, and an output quality ceiling equal to the expected score of the best output the SOTM can compute from the transcript. Fresh responses can raise these ceilings by allowing repeated calls to accumulate independent evidence toward correct or high-quality outputs. In the binary single-informative-query case, the error probability decreases exponentially in the number of calls to the same query at the Chernoff rate. For output quality, query-count bounds characterize threshold stopping when the score function is incorporated as part of the SOTM, and majority-based amplification bounds characterize the binary candidate-output model when it is not. Together, the results identify how response reuse, transcript information, and access to the score function determine what an SOTM can compute and at what token cost.
