Token Complexity Theory for AI-Augmented Computing

The paper introduces the concept of token complexity, a formal measure quantifying the resource cost (in terms of tokens) associated with achieving specific output quality levels in AI-augmented computing tasks. It presents a framework based on AI-Oracle Turing machines to analyze the interactions between probabilistic Turing machines and stochastic oracles, establishing key properties such as monotonicity, convexity, and price sensitivity of token complexity. This framework is significant for practitioners as it provides a new lens to evaluate the efficiency and cost-effectiveness of deploying AI models in real-world applications, particularly in resource-constrained environments.