mlsanityData to 7 Oct 2026

Computability of Agentic Systems

arXiv 2602.13222 ↗First posted 26 Jan 2026cs.CC cs.AI cs.FLcited by 0

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use. Builds on 29 of its 51 references that are in the map. First posted on arXiv 26 Jan 2026.

Builds on

29 of 51 references.

Closest ancestors · 1

Same direction, newest first

  1. 2023A Survey on Large Language Model based Autonomous Agents22 Aug

Other references · 28

  1. 2017Attention Is All You Needcited by 59,932
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  3. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  4. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  5. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  6. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,072
  7. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,064
  8. 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,383
  9. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  10. 2023A Survey of Large Language Modelscited by 2,537
  11. 2022Do As I Can, Not As I Say: Grounding Language in Robotic Affordancescited by 2,302
  12. 2023Retrieval-Augmented Generation for Large Language Models: A Surveycited by 2,185
16 more
  1. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
  2. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 873
  3. 2023Reasoning with Language Model is Planning with World Modelcited by 846
  4. 2023Large Language Models Can Be Easily Distracted by Irrelevant Contextcited by 820
  5. 2016TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systemscited by 660
  6. 2022LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language Modelscited by 459
  7. 2024Graph Retrieval-Augmented Generation: A Surveycited by 320
  8. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  9. 2022Neural Networks and the Chomsky Hierarchycited by 214
  10. 2024Agent AI: Surveying the Horizons of Multimodal Interactioncited by 167
  11. 2023Large Language Models Play StarCraft II: Benchmarks and A Chain of Summarization Approachcited by 79
  12. 2023Boosting Language Models Reasoning with Chain-of-Knowledge Promptingcited by 77
  13. 2024Retrieve, Summarize, Plan: Advancing Multi-hop Question Answering with an Iterative Approachcited by 40
  14. 2023Plan, Verify and Switch: Integrated Reasoning with Diverse X-of-Thoughtscited by 27
  15. 2024Boosting of Thoughts: Trial-and-Error Problem Solving with Large Language Modelscited by 22
  16. 2024Enhancing Long Context Performance in LLMs Through Inner Loop Query Mechanismcited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Computing with Agentic Oracles
  2. 2025Beyond Black-Box Benchmarking: Observability, Analytics, and Optimization of Agentic Systems
  3. 2025Are Agents Probabilistic Automata? A Trace-Based, Memory-Constrained Theory of Agentic AI
  4. 2026From Atomic to Agentic: Towards Interpretable Evaluation of LLMs' Agentic Mathematical Capabilities
  5. 2025Unifying Language Agent Algorithms with Graph-based Orchestration Engine for Reproducible Agent Research
  6. 2026Agentic Artificial Intelligence (AI): Architectures, Taxonomies, and Evaluation of Large Language Model Agents
  7. 2025General Agentic Planning Through Simulative Reasoning with World Models
  8. 2026PRIME: Policy-Reinforced Iterative Multi-agent Execution for Algorithmic Reasoning in Large Language Models