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

AI summary

Overview

Research area: Formal foundations of agentic AI systems, at the intersection of computability theory (oracle machines), programming-language semantics (call-by-push-value), operating systems, and computer architecture.

Technical level: Advanced. The paper is written in the idiom of theoretical computer science and systems research, with formal definitions, propositions, theorems and a hardware/prototype realization.

Scope in one sentence: The paper constructs an abstract machine that extends a Turing-complete two-stack pushdown automaton with a single instruction that queries a black-box Oracle, derives an operating system on that machine through two symmetry breakings, and realizes it as ArchNights, an extended RISC-V ISA with a Linux-style kernel running on the gem5 simulator.

(Paper: "We Query, Therefore We Compute: On Oracle Computation beyond the Machine, with an Application to Agents," by Kefan Liu, Fengning Ou, Yelin Luo and Jingdi Lei; arXiv:2610.09243v1 [cs.AI], 07 Oct 2026, licensed CC BY-NC-SA 4.0.)

What This Paper Is About

Agentic systems are currently built by borrowing abstractions piecemeal from operating systems—scheduling, caching, isolation—so the resulting mechanisms share little common ground on which they can be stated or compared. At the same time, the two forms of agentic systems, Workflows and Agents, are usually studied separately, and the shared view that subsumes them is limited.

The paper's goal is to build one abstract machine that supplies that common ground and that unified view, then to derive from it invariants and bounds that hold no matter who or what answers the queries—a language model or a person—and to show the machine can actually be realized on a von Neumann computer.

Key Contributions

1. The machine (§2). The O-2-PDA: a two-stack pushdown automaton, Turing complete, extended with one instruction that queries a black-box Oracle with the whole content of a stack and appends the answer to that same stack. While the program only appends, the history on a stack grows autoregressively, as an agent's context does (Proposition 2.7).

2. The operating system derived on it (§3). Two symmetry breakings—S on storage and T on transitions—make a Priestess program the operating system of the programs the Oracle runs. The authors state these are the weakest breakings that keep the two placements of a task's program apart for every program (Proposition 3.12). The kernel contract K1–K4 is an invariant of the machine, for every Oracle (Theorem 3.4); with a budget, control also returns (Proposition 3.7). Agent and Workflow follow as the two placements of a task's program (Definition 3.10).

3. The realization (§§5–6). The construction V fits the machine to a von Neumann computer: stacks become segments of one memory, the Oracle operation is one instruction, and O-mode has no addressable code. ArchNights, an extended RISC-V ISA with a Linux-style kernel, runs on gem5 and is offered as evidence that the machine can be built and can serve as the basis of an agent harness.

4. Derived results the authors classify as "instances," not further contributions. The paper explicitly says the cache model, the scheduling analysis, the Agent/Workflow correspondence and the safety boundary are instances of the theory whose number shows the construction to be coherent, and that they are "not further contributions." Each holds under named hypotheses.

Main Findings

• The kernel contract is an invariant (K1–K4, Theorem 3.4). Whatever the model answers, a task reads and writes only its own stack, control returns only at the one fixed entry, and to the Priestess every answer is data: none becomes a code address, and none grants itself a right to execute. This assumes none of the paper's three named assumptions and holds for every Oracle.

• Control returns under a budget (K5, Proposition 3.7). On a "good machine"—one on which no history reached in O-mode is rejected—control also comes back to the Priestess when a budget is present.

• Two placements define Agent and Workflow (Definition 3.10). An Agent carries its program in its history, on the Oracle side, with the Priestess as its operating system. A Workflow's program is Priestess code on the privileged side, so no operating system mediates it and the model's output is data. A hybrid has part of its program on each side.

• An Agent can always run in Workflow form (Proposition 3.11). Through an interpreter in the Priestess that makes the same queries with the same answers; the guarantees of the fixed entry and of task confinement then become obligations of the interpreter's code.

• The breakings are minimal (Proposition 3.12). They are the weakest that keep the two placements of a task's program apart for every program. Reversing S would relabel the two colours (Appendix E.6); reversing T rewrites the transition rules (Appendix E.5).

• Autoregressive growth (Proposition 2.7). If the program only appends to a stack between queries, each query contains the whole preceding history, so the Oracle sees the history grow autoregressively from call to call (query, answer, tool result, query), as a model's context does. The paper calls this the autoregressive form and locates it in the interaction, not in the model.

• Frame synchronization (Theorem 4.4). For an Oracle that is autoregressive inside, the two computations synchronize at the end of every answer that yields.

• Excess recomputation is exactly the encoder's loss (Proposition 4.9). Holding under Frame-faithfulness, this links what a cache hierarchy recomputes in excess to what re-encoding the history discards.

• Prefix chain across tool calls; each token computed once (Proposition 4.10). For certain Oracles and kernels—with hypotheses including that the tokenizer encodes the text between yield symbols piece by piece, that the model is called one whole answer at a time and writes each answer back as it generated it, and that the kernel only appends records ending with the yield symbol—a private cache that keeps every state computes each token of a history once. Compaction and truncation rewrite the history and break this reuse; the paper cites LMCache reporting that truncation can halve the hit ratio of a prefix cache.

• Keep-or-discard costs a factor of two (Proposition 4.11). Without knowing when a task returns, the best a deterministic Oracle-side choice between keeping and discarding can guarantee is twice the cost of a choice that knows.

• The safety boundary (Theorem 4.12) and its limit (Proposition 4.13). The Priestess wrote whatever an Oracle call reads, apart from the answers the Oracle appended to that stack, and the Oracle's answers reach the Priestess's control only at the trap and at three instructions that read content. A guarantee that holds for every Oracle can fix where content crosses but not which content crosses. The paper states plainly that the boundary does not make the machine a defence against prompt injection; it says where defences outside the Oracle have to sit.

• Two schedulers work from estimates of each other (§4.3). The Priestess side (a harness or a workflow's program) knows which histories it will submit next; the Oracle side (an inference server) knows what it has cached.

• Prototype results (§6.6). With deepseek-v4.1-flash as the Oracle, ArchNights-SE performs comparably on Terminal-Bench 2.1 to two reference harnesses run with the same model in the same setting: mini-swe-agent and Terminus 2, the benchmark's own agent. No numeric scores are reported in the paper content. Given a virtual display and audio output, ArchNights-SE also produces a music video of world.execute(me);, working both as an agent harness and as a general-purpose computer.

• What the paper claims and does not claim. The authors claim only that the works they cite do not make these statements, not that no other formalism could. They name three assumptions used along the way—factorization at the yield symbol (Definition 4.3), Frame-faithfulness (§4.1) and the Lynchpin hypothesis (§5.4)—and state that the kernel contract, the two placements and the safety boundary assume none of the three.

Methodology in Plain English

The work proceeds in two methodological steps the authors name explicitly, followed by two extensions.

Relativization. The language model is separated from the rest of the computation and treated as a black-box Oracle, in the tradition of Turing's 1939 oracle machines—with the deliberate difference that this Oracle "may well be one": a language model on hardware of its own. The interaction between the Oracle and the rest becomes a machine. The starting point is a two-stack pushdown automaton written as a program, in the style of Shepherdson and Sturgis's register machines, with a numbered list of instructions (push, pop, jeq, halt) and a program counter. Adding one oracle s l_e instruction yields the O-2-PDA. Its computation divides in two: the computation inside the Oracle, and the Turing-complete rest that queries it, which the authors call the Priestess. One stack is coloured O and the other P; a split-stacks lemma (Lemma 2.2) lets a stack be divided into logical stacks separated by markers, so the machine can be described at "observable steps."

Symmetry breaking. The machine is first typed with call-by-push-value, in which a stack entry is either data or a suspended program, much as a page's permissions say whether it may be executed. Then two breakings are applied. S (storage) decides where the Oracle may find a program: only on an Oracle stack; on a Priestess stack, whatever the Oracle answers is data. T (transitions) decides who chooses the next transition: it adds O-mode, in which the machine queries one Oracle stack again and again and appends each answer, with no Priestess instruction between queries, until an answer ends with a fixed yield symbol, at which point control traps to one fixed label in the Priestess's code. Outside O-mode the machine is in privileged P-mode. The machine with both breakings is the O-2-PDA-TS.

Opening the Oracle and fitting it to hardware. §4 opens the black box for Oracles that are autoregressive inside, taking the history in through an encoder (for a language model, its tokenizer), and deriving the cache hierarchy, the scheduling analysis and the safety boundary. §5 gives the construction V, which fits the O-2-PDA-TS to a von Neumann computer to obtain the O-2-PDA-TSV: stacks become memory segments with a base, a top and a limit, the Oracle operation is one instruction with no code in O-mode, and O-mode is allowed to run only Oracles that are autoregressive inside, while P-mode may call any Oracle. A semantic delegation call, evaluated by the Priestess, can stand for several system calls.

Prototype. ArchNights extends the RV64 ISA with an Oracle mode below user mode that has no addressable code and with an Oracle instruction compatible with RoCC, Rocket Chip's interface for custom coprocessors; the simulated processor runs the Oracle mode by microcode. The Linux-style kernel PRTS takes control back from every task at one fixed entry, confines ordinary tasks to a virtual file system, and checkpoints and compresses their histories. ArchNights-SE is implemented in gem5's syscall-emulation mode and will be open source; ArchNights-FS is a full-system design with a kernel named ZOOT, for a physical processor implementing the instruction set.

Why This Matters

The paper's stated payoff is methodological: if agentic systems can be designed as computer systems are designed, each design choice can be argued from the theories or the experience of computer systems. It supplies invariants and bounds that quantify over every Oracle, or over every Oracle meeting a stated condition, plus an operating system derived on the same machine as the Oracle's computation—two ingredients

Authors’ 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.