We Query, Therefore We Compute: On Oracle Computation beyond the Machine, with an Application to Agents

We Query, Therefore We Compute. On Oracle Computation beyond the Machine, with an Application to Agents. By Kefan Liu and three others, from the Institute of Computing Technology, Chinese Academy of Sciences, the University of Chinese Academy of Sciences, and three other institutions. Published on the seventh of October. No code repository is linked to it.

Agentic systems use large language models to carry out concrete tasks. Much prior work borrows ideas from operating systems, such as scheduling, caching or isolation, but borrows them piecemeal. The resulting mechanisms share little common ground, and there is only a limited shared view of the two forms an agentic system takes: Workflows and Agents. The authors set out to build one abstract machine that provides both a common foundation and that shared view.

The starting point is a two-stack pushdown automaton. The large language model is treated as an Oracle. The automaton is extended with a single new instruction, which hands the Oracle an entire stack as its query and appends the Oracle's answer to that same stack.

With that one instruction, the machine performs two computations. One is the Oracle's. The other is Turing-complete, and the authors name it the Priestess. Two symmetry breakings, called S in storage and T in transitions, make a Priestess program into the operating system of the programs the Oracle runs. They also produce the Agent and the Workflow as the two possible placements of a task's program. The two forms of agentic system, in other words, fall out of the same machine.

The construction proceeds through a few observations. A stack that the program only ever appends to grows autoregressively, the way an agent's context does, so the machine's stack behaves like a context window. For Oracles that are themselves internally autoregressive, the two computations synchronize at the end of every answer, under certain conditions. Through that synchronization point the authors model caching and analyse scheduling, two of the operating-system ideas that earlier work had borrowed one at a time.

A further result concerns what crosses between the two computations. No guarantee that holds for every Oracle can fix which content crosses that line. But such a guarantee can fix where the line is: the boundary itself.

The last step is realizability. A construction the authors call V fits the machine to a von Neumann computer. To show it can actually be built, they propose ArchNights: an extended RISC-V ISA together with a Linux-style operating system, implementing the machine by design. ArchNights-SE runs on gem5 as a computer system, and becomes an agentic system when an LLM is run as its Oracle. The authors say it will be open source.

The results carry conditions, and the abstract is careful to mark them. The synchronization at the end of every answer is claimed only for Oracles that are internally autoregressive, and only under certain conditions. The modelling of caching and scheduling rests on that synchronization. And the guarantee about crossing content is deliberately limited: what holds for every Oracle fixes the boundary, not what passes over it. The realizability claim, for its part, rests on ArchNights-SE running on gem5, with the open source release still to come.

The ambition is to let agentic systems be designed the way computer systems are. One instruction added to a classic automaton yields an Oracle computation and a Turing-complete one beside it, and from their relationship come operating systems, caching, scheduling, Agents and Workflows. With that foundation and unified view in place, the authors expect future work to share invariants and bounds, each stated together with its conditions.