Paper models LLMs as oracles in a pushdown automaton, unifying Agents and Workflows
China666 · hf · 2026-10-08
This theoretical paper builds a unified formal foundation for agentic systems.
Key ideas:
- Oracle & Priestess: treat the LLM as an Oracle and extend a two-stack pushdown automaton with one instruction that hands the whole stack to the Oracle and appends the answer back; the machine runs both the Oracle's computation and a Turing-complete "Priestess" computation.
- Unifying Agents and Workflows: an append-only stack grows autoregressively like an agent's context; two symmetry breakings make the Priestess program the OS of the Oracle's programs, with Agent and Workflow emerging as two placements of a task's program.
- Caching & scheduling: for internally autoregressive oracles, the computations synchronize per answer under conditions, enabling caching models and scheduling analysis.
- Realizability: construction V maps the machine onto a von Neumann computer; ArchNights, an extended RISC-V ISA plus Linux-style OS, runs on gem5 and becomes an agentic system with an LLM as Oracle. Open source planned.
The upshot: agentic systems can be designed the way computer systems are.
More from coding & agent
- nanoMuse: An Open-Source Personal Agent Spanning Every Device You Own — zju · 2026-10-08
- AI Agents Mean Way More PRs and CI Runs, Boosting Demand for Build & Release Engineers — almmaasoglu · 2026-10-08
- Dev's tests confirm OpenAI Codex computer and browser use fail a lot — jdjohnson · 2026-10-08
- Dev builds a full game from a low-res screenshot using Spawn, calls Google Playground 'garbage' — TAbrodi · 2026-10-08
- Burkov: Codex 6.1 overthinks on High; Sonnet 5.5 Extra remains his pick — burkov · 2026-10-08
- Rust tip: codegen-units = 1 makes uv build 50% faster with 67% less memory — charliermarsh · 2026-10-08