Abstract machine unifies agents and workflows using oracle queries
We Query, Therefore We Compute: On Oracle Computation beyond the Machine, with an Application to Agents
Artificial Intelligence
Summary
Many systems that use AI language models to act like assistants borrow ideas from operating systems in bits and pieces, making it hard to have a shared understanding. This paper builds a single abstract machine that treats the language model as a kind of oracle answering queries. It runs two computations together: one for the oracle (the AI model) and one called the Priestess that controls how tasks get done. This model helps explain how caching, scheduling, and different task types work coherently, and they propose a computer design called ArchNights to make such agentic systems built like traditional software systems.
What this means in practice
- •For operating system developers: Design operating systems that natively support AI agent tasks by integrating oracle computation concepts for scheduling and caching.
- •For embedded system engineers: Implement agentic systems on RISC-V hardware using the ArchNights ISA to run language model oracles efficiently.
Authors
Kefan Liu, Fengning Ou, Yelin Luo, Jingdi Lei
Abstract
Agentic systems use large language models (LLMs) to carry out concrete tasks. Prior work often borrows abstractions such as scheduling, caching or isolation piecemeal from operating systems, so the mechanisms it builds share little common ground, and the shared view of the two forms of agentic system, Workflows and Agents, is limited. We construct an abstract machine that provides both. We treat the LLM as an Oracle and extend a two-stack pushdown automaton with one instruction, which hands the Oracle a whole stack as its query and appends the answer to that same stack. The machine thus performs two computations, the Oracle's and a Turing-complete one that we call the Priestess. A stack that the program only appends to grows autoregressively, as an agent's context does. Two symmetry breakings, S in storage and T in transitions, make a Priestess program the operating system of the programs the Oracle runs, and produce the Agent and the Workflow as the two placements of a task's program. For internally autoregressive Oracles, the two computations synchronize at the end of every answer under certain conditions, and through that synchronization we model caching and analyse scheduling. No guarantee that holds for every Oracle can fix which content crosses between the two computations, but such a guarantee does fix the boundary itself. The construction V fits the machine to a von Neumann computer. To show that it is realizable, we propose ArchNights, an extended RISC-V ISA and a Linux-style operating system implementing the machine by design. ArchNights-SE runs on gem5 as a computer system, becomes an agentic system when it runs an LLM as the Oracle, and will be open source. Agentic systems can then be designed as computer systems are. With a foundation built and a unified view, future work can share invariants and bounds, each with its conditions.