Are Agents Just Automata? On the Formal Equivalence Between Agentic AI and the Chomsky Hierarchy

• URL: http://arxiv.org/abs/2510.23487v1
• Date: Mon, 27 Oct 2025 16:22:02 GMT
• Title: Are Agents Just Automata? On the Formal Equivalence Between Agentic AI and the Chomsky Hierarchy
• Authors: Roham Koohestani, Ziyou Li, Anton Podkopaev, Maliheh Izadi,
• Abstract summary: This paper establishes a formal equivalence between the architectural classes of modern agentic AI systems and the abstract machines of the hierarchy.<n>We demonstrate that simple reflex agents are equivalent to Finite Automata, hierarchical task-decomposition agents are equivalent to Pushdown Automata, and agents employing readable/writable memory for reflection are equivalent to TMs.
• Score: 4.245979127318219
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This paper establishes a formal equivalence between the architectural classes of modern agentic AI systems and the abstract machines of the Chomsky hierarchy. We posit that the memory architecture of an AI agent is the definitive feature determining its computational power and that it directly maps it to a corresponding class of automaton. Specifically, we demonstrate that simple reflex agents are equivalent to Finite Automata, hierarchical task-decomposition agents are equivalent to Pushdown Automata, and agents employing readable/writable memory for reflection are equivalent to TMs. This Automata-Agent Framework provides a principled methodology for right-sizing agent architectures to optimize computational efficiency and cost. More critically, it creates a direct pathway to formal verification, enables the application of mature techniques from automata theory to guarantee agent safety and predictability. By classifying agents, we can formally delineate the boundary between verifiable systems and those whose behavior is fundamentally undecidable. We address the inherent probabilistic nature of LLM-based agents by extending the framework to probabilistic automata that allow quantitative risk analysis. The paper concludes by outlining an agenda for developing static analysis tools and grammars for agentic frameworks.

Related papers

• The Auton Agentic AI Framework [5.410458076724158]
  The field of Artificial Intelligence is undergoing a transition from Generative AI to Agentic AI.<n>This transition exposes a fundamental architectural mismatch: Large Language Models (LLMs) produce unstructured outputs, whereas the backend infrastructure they must control requires deterministic, schema-conformant inputs.<n>The present paper describes the Auton Agentic AI Framework, a principled architecture for the creation, creation, and governance of autonomous agent.
  arXiv  Detail & Related papers  (2026-02-27T06:42:08Z)
• El Agente Gráfico: Structured Execution Graphs for Scientific Agents [7.47895130442454]
  We present El Agente Grfico, a single-agent framework that embeds large language models (LLMs)-driven decision-making within a type-safe execution environment.<n>Central to our approach is a structured abstraction of scientific concepts and an object-graph mapper that represents computational state as typed Python objects.<n>We evaluate the system by developing an automated benchmarking framework across a suite of university-level quantum chemistry tasks.
  arXiv  Detail & Related papers  (2026-02-19T23:47:05Z)
• RocqSmith: Can Automatic Optimization Forge Better Proof Agents? [0.07696728525672149]
  We evaluate how different automatic agents perform when applied to the task of optimizing a Rocq proof-generation agent.<n>Our results show that while several bootstraps yield measurable improvements, simple few-shot bootstrapping is the most consistently effective.
  arXiv  Detail & Related papers  (2026-02-05T15:28:26Z)
• An Agentic Framework for Autonomous Materials Computation [70.24472585135929]
  Large Language Models (LLMs) have emerged as powerful tools for accelerating scientific discovery.<n>Recent advances integrate LLMs into agentic frameworks, enabling retrieval, reasoning, and tool use for complex scientific experiments.<n>Here, we present a domain-specialized agent designed for reliable automation of first-principles materials computations.
  arXiv  Detail & Related papers  (2025-12-22T15:03:57Z)
• Towards Efficient Agents: A Co-Design of Inference Architecture and System [66.59916327634639]
  This paper presents AgentInfer, a unified framework for end-to-end agent acceleration.<n>We decompose the problem into four synergistic components: AgentCollab, AgentSched, AgentSAM, and AgentCompress.<n>Experiments on the BrowseComp-zh and DeepDiver benchmarks demonstrate that through the synergistic collaboration of these methods, AgentInfer reduces ineffective token consumption by over 50%.
  arXiv  Detail & Related papers  (2025-12-20T12:06:13Z)
• AgentRouter: A Knowledge-Graph-Guided LLM Router for Collaborative Multi-Agent Question Answering [51.07491603393163]
  tAgent is a framework that formulates multi-agent QA as a knowledge-graph-guided routing problem supervised by empirical performance signals.<n>By leveraging soft supervision and weighted aggregation of agent outputs, Agent learns principled collaboration schemes that capture the complementary strengths of diverse agents.
  arXiv  Detail & Related papers  (2025-10-06T23:20:49Z)
• The AI Agent Code of Conduct: Automated Guardrail Policy-as-Prompt Synthesis [0.19336815376402716]
  We introduce a novel framework that automates the translation of unstructured design documents into verifiable, real-time guardrails.<n>"Policy as Prompt" uses Large Language Models (LLMs) to interpret and enforce natural language policies.<n>We validate our approach across diverse applications, demonstrating a scalable and auditable pipeline.
  arXiv  Detail & Related papers  (2025-09-28T17:36:52Z)
• AgentGuard: Runtime Verification of AI Agents [1.14219428942199]
  AgentGuard is a framework for runtime verification of Agentic AI systems.<n>It provides continuous, quantitative assurance through a new paradigm called Dynamic Probabilistic Assurance.
  arXiv  Detail & Related papers  (2025-09-28T13:08:50Z)
• Is the `Agent' Paradigm a Limiting Framework for Next-Generation Intelligent Systems? [0.0]
  The concept of the 'agent' has profoundly shaped Artificial Intelligence (AI) research.<n>This paper critically re-evaluates the necessity and optimality of this agent-centric paradigm.
  arXiv  Detail & Related papers  (2025-09-13T16:11:27Z)
• SI-Agent: An Agentic Framework for Feedback-Driven Generation and Tuning of Human-Readable System Instructions for Large Language Models [0.0]
  System Instructions (SIs) are pivotal for guiding Large Language Models (LLMs)<n>Existing automated methods frequently generate non-human-readable "soft prompts," sacrificing interpretability.<n>This paper introduces SI-Agent, a novel agentic framework designed to automatically generate and iteratively refine human-readable SIs.
  arXiv  Detail & Related papers  (2025-07-03T23:44:50Z)
• AI Agents vs. Agentic AI: A Conceptual Taxonomy, Applications and Challenges [3.7414278978078204]
  This review critically distinguishes between AI Agents and Agentic AI, offering a structured, conceptual taxonomy, application mapping, and analysis of opportunities and challenges to clarify their divergent design philosophies and capabilities.
  arXiv  Detail & Related papers  (2025-05-15T16:21:33Z)
• Agent-as-a-Judge: Evaluate Agents with Agents [61.33974108405561]
  We introduce the Agent-as-a-Judge framework, wherein agentic systems are used to evaluate agentic systems. This is an organic extension of the LLM-as-a-Judge framework, incorporating agentic features that enable intermediate feedback for the entire task-solving process. We present DevAI, a new benchmark of 55 realistic automated AI development tasks.
  arXiv  Detail & Related papers  (2024-10-14T17:57:02Z)
• Gödel Agent: A Self-Referential Agent Framework for Recursive Self-Improvement [112.04307762405669]
  G"odel Agent is a self-evolving framework inspired by the G"odel machine.<n>G"odel Agent can achieve continuous self-improvement, surpassing manually crafted agents in performance, efficiency, and generalizability.
  arXiv  Detail & Related papers  (2024-10-06T10:49:40Z)
• Automated Machine Learning, Bounded Rationality, and Rational Metareasoning [62.997667081978825]
  We will look at automated machine learning (AutoML) and related problems from the perspective of bounded rationality. Taking actions under bounded resources requires an agent to reflect on how to use these resources in an optimal way.
  arXiv  Detail & Related papers  (2021-09-10T09:10:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.