# Token Complexity Theory for AI-Augmented Computing

arXiv: https://arxiv.org/abs/2606.12647 · HTML: https://mlsanity.com/paper/2606.12647/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 15 references that are in the map.
- First posted on arXiv 10 Jun 2026.

## Builds on (most cited first, 3 of 3)

- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [AI-Oracle Machines for Intelligent Computing](https://mlsanity.com/paper/2406.12213/) (2024)

## Built on by (most cited first, 3 of 3)

- [Token Complexity of Certifying Stochastic-Oracle Reliability](https://mlsanity.com/paper/2606.24074/) (2026)
- [Computing with Stochastic Oracles in AI-Augmented Computation](https://mlsanity.com/paper/2607.06893/) (2026)
- [Computing with Agentic Oracles](https://mlsanity.com/paper/2608.01464/) (2026)

## Abstract (arXiv)

AI-augmented computing delegates natural language queries, code generation requests, and other open-ended tasks to a cluster of AI models that processes queries and generates responses. This paradigm introduces a resource dimension that neither classical time nor space complexity captures: the cost of sending queries to and receiving responses from such a cluster. We introduce token complexity, a formal resource measure defined as the minimum expected token cost to achieve a specified level of output quality on a task, and develop a taxonomy classifying AI systems by the strength of their probabilistic properties. We develop token complexity within the framework of AI-Oracle Turing machines, in which a probabilistic Turing machine interacts with a stochastic oracle via dedicated query and response tapes. We prove basic theorems establishing that token complexity behaves as expected: monotonicity (higher quality costs more tokens), convexity (quality improvements become progressively more expensive), price sensitivity (small price changes produce bounded cost changes), and price-relativity of task ordering (the token complexity ordering of tasks can reverse depending on the query-to-response cost ratio). We prove that the complexity frontier, defined as the set of all feasible resource bounds in tokens, time, and space, is non-empty, upward-closed, and convex.