We Query, Therefore We Compute: On Oracle Computation beyond the Machine, with an Application to Agents
Organizations: Institute of Computing Technology, CAS · University of Chinese Academy of Sciences · Nanjing University · Institute of Automation, CAS · Nanyang Technological University
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.
Figures & tables
| Oracle side (amber) | Priestess side (blue) | |
|---|---|---|
| computation | the Oracle : the source of the answers, treated as a black box; an LLM or a person (§ 2.3 ) | the Priestess : the Turing-complete computation that queries the Oracle (§ 2.3 ) |
| letters | O names the colours, the modes and the order of the sides, and nothing more (§ 2.2 , § 3 ) | P likewise |
| stack | Oracle stack : the only kind that may hold a program the Oracle runs (S) | Priestess stack : whatever the Oracle produces there is data (S) |
| mode | O-mode : the Oracle answers again and again until an answer yields; no Priestess code runs between the queries (T) | P-mode : the Priestess program chooses the next transition (T) |
| a task’s program | Agent form : the program is the task’s history, which the Oracle runs | Workflow form : the program is Priestess code; the model’s output is data |
| control crossing | an answer ending with yields : it traps to the one fixed label , the system call | the kernel enters tasks with and serves their traps; its library declares the services (Defs. 3.3 , 3.8 ) |
| Transfer of control | In CBPV | Who decides what |
|---|---|---|
| entry: P to O, | the Priestess forces the thunk on | the Priestess decides when to enter, and which stack the Oracle sees |
| trap: O to P, a yield trap to | the Oracle call forces , which reads what the excursion appended since the Priestess last wrote | the Oracle’s answer decides when; where is fixed |
| return: the reply appended to , then | returns to the task, which binds it with | the Priestess decides what is, and when the task receives it |
| a P-mode Oracle call, with no switch | binds the answer as a value | the Priestess’s code: it continues at , or at on rejection |
| Trusted party / acting subject | Oracle | Priestess |
|---|---|---|
| Priestess (this machine; an untrusted Oracle such as a language model) | Agent : an Agent operating a computer; the Priestess is the operating system | Workflow : non-OS; Oracle output is data |
| Oracle (privilege reversed; a trusted Oracle such as a human) | human–computer interaction : a human using a computer, the counterpart of an Agent operating one; non-OS, the program is on the trusted side | automated systems : a Priestess program runs by itself, confined, and the human decides at the switches; the human is the operating system |
| Scheduler | Schedules its own side | Schedules the other side |
|---|---|---|
| Oracle side | the Oracle’s computations: batching, paging and sharing of the state cache [ 16 , 17 , 75 , 76 , 18 ] , its tiers [ 61 , 77 , 62 , 37 ] , and its placement across devices [ 78 ] | when a program continues: scheduling each call by the program it belongs to [ 65 , 66 , 67 ] , and the state of a task kept, dropped or swapped while its tool call runs [ 32 , 33 , 73 ] , and the shared prefixes of a workflow kept or prefetched by how soon each will be used [ 34 ] |
| Priestess side | the program’s own work, tools and environments: planned calls dispatched in parallel [ 79 , 80 ] , tool resources [ 67 ] ; in PRTS, the ready queue | the Oracle’s work: which task enters O-mode, when, and for how long, in PRTS the slice; the strategy by which a program’s calls are executed, changed by effect handlers [ 81 ] ; programs that drive the generation loop and the cache inside the server [ 82 ] |
| What a realization keeps | In ArchNights | Lost if it fails | |
|---|---|---|---|
| Ia. Rules kept by the processor, whatever the kernel: K1–K4, Corollary 3.5 , Theorem 4.12 | |||
| I-1 | An Oracle operation appends only inside the window it is given, and an answer that does not fit is refused and writes nothing (Definition 5.2 , Proposition 5.3 ) | the controller checks the window before evaluation; an answer that does not fit is refused at publication; the descriptor lies inside the window, past the top, so it changes no store realized | K1 |
| I-2 | O-mode fetches no instruction and has no addressable code (Definition 3.3 , Insight 5.3 ) | the Oracle mode, run by microcode | K1, K2 |
| I-3 | Each transition, a Step or a Frame, is published whole, and an exception publishes no part of one (§ 5.3 ) | the controller publishes after evaluation; an exception keeps only what was published before it | K1, whose appends are whole answers |
| I-4 | Control leaves O-mode at a place that no answer can select (Definition 3.3 ) | completes, and the processor continues at the next instruction, with the cause in the destination register | K3 |
| I-5 | A P-mode operation continues at the next instruction whatever its answer, and no Oracle operation sets the program counter (Definition 3.3 , § 5.2 ) | STEP or RUN in P-mode, issued by ask , by the session reading a line from the person and by the summary of a swap; a rejection shows in the status, and a branch on it is the program’s own, as a is | the first part of K4 |
| What a realization keeps | In ArchNights | Lost if it fails | |
|---|---|---|---|
| III. Hypotheses of the conditional results of § 4 , which the machine does not fix | |||
| III-1 | O-mode runs only Oracles, the O constraint (§§ 5.1 and 5.3 ) | PROBE reports it, and O-mode operations on other Oracles are refused | the cache model for that task, not the contract |
| III-2 | The encoder accepts every word over , , and the kernel writes only words over (Proposition 4.5 ) | not met by a language model: its input is bounded (§ 5.1 ), and some histories, such as a request without its reply, fail to encode | a good machine, which II-2 replaces for K5 |
| III-3 | Append-only epochs: within one, the kernel changes a history only by (§ 4.2 ) | kernel code changes a history only through push, pop and its metadata, and a direct write, not prevented, is undefined behaviour; exec, a swap and a back-off start new epochs | Proposition 4.10 ; the coherence of the encoding cache |
| III-4 | Every word the kernel pushes onto a history ends with (Proposition 4.10 ) | kept for an Oracle with STEP disabled, which is called through the Frame interface | Proposition 4.10 |
| III-5 | The encoder factorizes at , and the Oracle is Frame-faithful (Definition 4.3 , Theorem 4.4 ) | not claimed: properties of each Oracle and its codec, which ArchNights-SE does not yet analyse (§ 8 ) | the Frame-boundary case of Proposition 4.9 ; Proposition 4.10 |
| Instruction | Encoding | Operands | What it does |
|---|---|---|---|
| PROBE | custom-0, R-type | none | reports the profiles the unit implements, whether answers carry a descriptor, and what the bound Oracle can do |
| STEP | custom-0, R-type | a segment, its top and a bound on what one step may write | in P-mode, one step of the Oracle’s own autoregression, appended past the top |
| RUN | custom-0, R-type | a segment, its top and a budget | in P-mode, a Frame, appended past the top |
| none; O-mode fetches no instruction | none | absorbed into O-mode’s transitions: an answer that ends with the yield symbol traps to the kernel as an would | |
| custom-1 | none | enters O-mode on the task its registers describe; completes when the excursion ends | |
| Result | the destination register | how the operation ended, how many of the Oracle’s steps it took, how many bytes it published |
| Family | Operators | What one call does |
|---|---|---|
| Standard streams | input , print | read standard input, a named file or a result channel, as far as there is data, with end of file reported together with the last data; write a whole text to standard output or to the parent |
| Programs | run , fork , execve , waitpid , exit , yield | run a command line as a pipeline; the process calls of Unix |
| Names | open , close | give a file or a directory a name, or drop it |
| Editing | file_read , file_write , file_patch | read, write or patch a file in one call, guarded by a stamp of the version read |
| Paths | stat , list , mkdir , remove , rename , chdir | one file-system operation each |
| Information | context , time , sleep | the task’s own arguments and environment; the simulated clock |
| All | Solvable | Other | |
|---|---|---|---|
| Configuration | 89 | 79 | 10 |
| ArchNights-SE, minimal, extra prompt | 74 (83.1) | 66 | 8 |
| mini-swe-agent | 72 (80.9) | 65 | 7 |
| Terminus 2 | 70 (78.7) | 62 | 8 |
| ArchNights-SE, minimal, default prompt | 69 (77.5) | 61 | 8 |
| ArchNights-SE, full, default prompt | 69 (77.5) | 61 | 8 |
| Design | In this structure | What the paper says of it |
|---|---|---|
| A tool-calling loop [ 162 ] | an excursion that yields with a request; the tool’s result is the reply, appended before the next | the Agent form (§ 3 ) |
| Several calls in one answer; a planned graph of calls [ 79 ] | several calls in one answer, one request, all served before the task runs again; a plan that Priestess code executes is an answer the Priestess interprets | several calls in one answer are one request of an Agent task; a planned graph that Priestess code executes runs in Workflow form, with the Agent paradigm, since the model wrote the plan (§ 3.5 ); its parallelism is the Priestess’s |
| Code as the action [ 171 , 31 ] | the answer is a program that Priestess code runs: an interpretation by the Priestess | the answer gains no execution right by itself (K4); checking it first is the Priestess’s obligation |
| Sub-agents and delegation [ 169 , 29 ] | spawn or fork; fork answers one request twice, and the two histories share their prefix | fork is one kernel service that builds the prefix tree (§ 4 ); the child’s result reaches the parent only through the parent’s read (§ 6 ) |
| Compaction of the context | the kernel rewrites the task, and the summary, the answer of a P-mode call, is data the kernel writes | a new epoch: the prefix chain breaks after the part of the history the rewrite keeps (§ 4 ); in PRTS, a swap that keeps the head (§ 6.3 ) |
| Memory tiers paged into the context [ 104 ] | moving content out is a rewrite by the Priestess; bringing it back is a read the Oracle requests | as with compaction; an interrupt becomes content appended at a switch |
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
| Term or symbol | Meaning | Defined in |
|---|---|---|
| Oracle stack, Priestess stack | a stack coloured , | Def 2.3 |
| P-mode , O-mode | the two modes of T, each with the form of its configurations | Def 3.3 |
| , yield | the yield symbol; an answer that ends with it | Def 3.3 |
| the trap label, where every trap continues | Def 3.3 | |
| enters O-mode on the stack , which under S is an Oracle stack | Def 3.3 | |
| trap, yield trap, excursion | a transition from O- to P-mode; one caused by a yield; a maximal O-mode segment with its and trap | Def 3.3 |
| Agent form (generation in O-mode) | Workflow form (generation in P-mode) | |
|---|---|---|
| Key of the next Oracle access | , known to the kernel when it dispatches | , known when the call is issued |
| Prefix chain | a machine invariant within an append-only epoch | a property of the program; sufficient: no |
| Encoding cache | valid within an epoch; the kernel invalidates it when it rewrites the task | valid while the program only pushes onto ; the program invalidates it when it rebuilds |
| Prefix tree | a kernel service that copies a history | calls whose operands share a pushed prefix, as in parallelization |
| What breaks the chain | the kernel rewrites the task; a Frame that does not re-encode to itself; a budget trap inside a Frame | the program rebuilds its operand; a Frame that does not re-encode to itself, when answers are fed back |
| Program | Operating system | What protects the operating system from the program | What protects the program from the other side | |
|---|---|---|---|---|
| Agent form | Oracle | Priestess: kernel and library | T with the locality lemma: a task writes only its own stack, and requests enter only at (K1, K3) | nothing in the machine: the kernel is privileged, may rewrite the task, and is trusted, as in a conventional operating system |
| Workflow form | Priestess | none mediates the task | nothing to protect | S and T: answers are data, reach only their operand and gain no execution right at the call (K4); validating them before a promotion is the program’s obligation |
| Bits | Field | Value or meaning |
|---|---|---|
| 31:25 | funct7 | reserved[6:5] ; profile[4:3]: 00 P0, 01 P1, 10 P2, 11 P32; op[2:1]: 00 PROBE, 01 STEP, 10 RUN, 11 reserved; dir[0]: 0 down, 1 up |
| 24:20 | rs2 | the offset of the top, with the budget (RUN) or the write bound (STEP) |
| 19:15 | rs1 | the segment’s base and its capacity in pages |
| 14:12 | funct3 | 111 : read rs1 and rs2, write rd |
| 11:7 | rd | the result |
| 6:0 | opcode | 0001011 (custom-0) |
| Profile | XLEN | offset | steps | budget | pages | bound | largest |
|---|---|---|---|---|---|---|---|
| P0 | 64 | 24 | 36 | 40 | 12 | 40 B | 4095 |
| P1 | 64 | 28 | 32 | 32 | 16 | 32 B | 65535 |
| P2 | 64 | 32 | 24 | 24 | 20 | 24 P | 1048575 |
| P32 | 32 | 22 | 6 | 6 | 12 | 10 P | 1023 |
| Code | Part | Meaning |
|---|---|---|
| 0 | Continue: a Step that did not yield | |
| 1 | Halt: the answer ended with the yield symbol | |
| 4 | decoder | no room: the answer, or a STEP’s write bound, does not fit |
| 5 | controller | budget spent before a yield |
| 6 | encoder | short input: the content is too short to form a request |
| 8 | encoder | illegal argument, refused before evaluation |
| Group | Calls |
|---|---|
| Processes | spawn, exec, fork, wait, exit, sleep, yield, shutdown |
| Files | open, close, read, write, truncate, stat, list, mkdir, remove, rename, chdir, getcwd |
| Descriptors | name a descriptor, find a descriptor by its name |
| Pipes | create a pipe, query its state |
| Terminal | read a line, ask a question, print |
| Credentials | check an access, require a right |