Computability of Agentic Systems

• URL: http://arxiv.org/abs/2602.13222v1
• Date: Mon, 26 Jan 2026 16:06:15 GMT
• Title: Computability of Agentic Systems
• Authors: Chatavut Viriyasuthee,
• Abstract summary: The Quest Graph is a formal framework for analyzing the capabilities of agentic systems with finite context.<n>We show that reference-augmented (Turing-complete) systems can be exponentially more efficient at simulating complex graphs than their non-augmented (context-free) counterparts.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces the Quest Graph, a formal framework for analyzing the capabilities of agentic systems with finite context. We define abstractions that model common reasoning techniques and establish their computational power: the base Quest Graph is equivalent to an unrestricted Turing machine; the forward-only Finite Quest Decision Process (FQDP), despite its wide use, is only equivalent to a pushdown automaton (context-free); and the Reference-Augmented QDP (RQDP) regains Turing completeness only when stateful queries are allowed. Since computability affects efficiency, we then analyze the theoretical efficiency of each model by simulating task dependencies in computation graphs. We show that this computational hierarchy translates to concrete performance trade-offs: reference-augmented (Turing-complete) systems can be exponentially more efficient at simulating complex graphs than their non-augmented (context-free) counterparts. This work provides a formal methodology for classifying and understanding the fundamental capabilities of agentic systems.

Related papers

• Certifiable Estimation with Factor Graphs [11.391420452904166]
  We show that factor graph structure is preserved under Shor's relaxation and Burer-Monteiro factorization.<n>Applying these transformations to a QCQP with an associated factor graph representation yields a lifted problem admitting a factor graph model with identical connectivity.
  arXiv  Detail & Related papers  (2026-03-01T20:50:51Z)
• 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)
• IACT: A Self-Organizing Recursive Model for General AI Agents: A Technical White Paper on the Architecture Behind kragent.ai [0.0]
  Interactive Agents Call Tree (IACT) is a general-purpose autonomous system driven purely by user dialogue.<n>We describe the architecture, design principles, and practical lessons behind the deployment of this model in the kragent.ai system.
  arXiv  Detail & Related papers  (2025-12-02T10:10:56Z)
• Graph-Memoized Reasoning: Foundations Structured Workflow Reuse in Intelligent Systems [0.0]
  We introduce Graph-Memoized Reasoning, a formal framework for representing, storing and reusing reasoning as graph-structured memory.<n>By encoding past decision graphs and retrieving them through structural and semantic similarity, our approach enables compositional reuse of subgraphs across new reasoning tasks.
  arXiv  Detail & Related papers  (2025-11-11T07:42:37Z)
• The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner [71.41162392872393]
  This paper proposes Turing MAchine Imitation Learning (TAIL) to improve the length generalization ability of large language models.<n>TAIL synthesizes chain-of-thoughts (CoT) data that imitates the execution process of a Turing Machine by computer programs.<n>Without bells and whistles, TAIL significantly improves the length generalization ability as well as the performance of Qwen2.5-7B on various tasks.
  arXiv  Detail & Related papers  (2025-07-17T17:50:07Z)
• Computational Reasoning of Large Language Models [51.629694188014064]
  We introduce textbfTuring Machine Bench, a benchmark to assess the ability of Large Language Models (LLMs) to execute reasoning processes.<n> TMBench incorporates four key features: self-contained and knowledge-agnostic reasoning, a minimalistic multi-step structure, controllable difficulty, and a theoretical foundation based on Turing machine.
  arXiv  Detail & Related papers  (2025-04-29T13:52:47Z)
• RV-Syn: Rational and Verifiable Mathematical Reasoning Data Synthesis based on Structured Function Library [58.404895570822184]
  RV-Syn is a novel mathematical Synthesis approach.<n>It generates graphs as solutions by combining Python-formatted functions from this library.<n>Based on the constructed graph, we achieve solution-guided logic-aware problem generation.
  arXiv  Detail & Related papers  (2025-04-29T04:42:02Z)
• Learning Task Representations from In-Context Learning [67.66042137487287]
  Large language models (LLMs) have demonstrated remarkable proficiency in in-context learning (ICL)<n>We introduce an automated formulation for encoding task information in ICL prompts as a function of attention heads.<n>The proposed method successfully extracts task-specific information from in-context demonstrations and excels in both text and regression tasks.
  arXiv  Detail & Related papers  (2025-02-08T00:16:44Z)
• On the Diagram of Thought [20.805936414171892]
  Large Language Models (LLMs) excel at many tasks but often falter on complex problems that require structured, multi-step reasoning.<n>We introduce the Diagram of Thought (DoT), a new framework that enables a single LLM to build and navigate a mental map of its reasoning.
  arXiv  Detail & Related papers  (2024-09-16T07:01:41Z)
• On the Complexity of Rational Verification [5.230352342979224]
  Rational verification refers to the problem of checking which temporal logic properties hold of a concurrent multiagent system. We show that the complexity of rational verification can be greatly reduced by specifications. We provide improved results for rational verification when considering players' goals given by mean-payoff utility functions.
  arXiv  Detail & Related papers  (2022-07-06T12:56:22Z)
• SOLIS -- The MLOps journey from data acquisition to actionable insights [62.997667081978825]
  In this paper we present a unified deployment pipeline and freedom-to-operate approach that supports all requirements while using basic cross-platform tensor framework and script language engines. This approach however does not supply the needed procedures and pipelines for the actual deployment of machine learning capabilities in real production grade systems.
  arXiv  Detail & Related papers  (2021-12-22T14:45:37Z)
• Question Answering over Knowledge Bases by Leveraging Semantic Parsing and Neuro-Symbolic Reasoning [73.00049753292316]
  We propose a semantic parsing and reasoning-based Neuro-Symbolic Question Answering(NSQA) system. NSQA achieves state-of-the-art performance on QALD-9 and LC-QuAD 1.0.
  arXiv  Detail & Related papers  (2020-12-03T05:17:55Z)
• Logically Consistent Loss for Visual Question Answering [66.83963844316561]
  The current advancement in neural-network based Visual Question Answering (VQA) cannot ensure such consistency due to identically distribution (i.i.d.) assumption. We propose a new model-agnostic logic constraint to tackle this issue by formulating a logically consistent loss in the multi-task learning framework. Experiments confirm that the proposed loss formulae and introduction of hybrid-batch leads to more consistency as well as better performance.
  arXiv  Detail & Related papers  (2020-11-19T20:31:05Z)

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.