Agentic Graph of Thoughts: a Reasoning Framework for LLM Agents

Modern Large Language Models (LLMs) exhibit structural limitations that reduce their reliability, including opaque reasoning, error propagation, and limited exploration of alternative solution paths. Existing prompting techniques such as Chain of Thoughts (CoT), Tree of Thoughts (ToT), and Graph of Thoughts (GoT) partially make reasoning more explicit, but GoT-style approaches usually require task-specific graph structures designed before execution. This thesis introduces an Agentic Graph of Thoughts (AGoT) architecture based on a runtime-generated graph, in which the LLM reasoning is guided by a directed graph constructed dynamically during execution. Such a graph contains various kinds of nodes, each representing a specific step: reasoning generation, tool invocation, response evaluation, and backtracking to alternative paths. Moreover, this approach supports the dynamic tool crafting mechanism when no available tool is sufficient to solve the problem. A dedicated agent generates and registers new tools at runtime, extending the system’s capabilities without requiring human intervention. Intermediate reasoning process is evaluated by an LLM judge with an adaptive threshold based on the estimated complexity of the problem. The framework is evaluated on the Hendrycks MATH benchmark, comparing the proposed architecture against a Zero-Shot CoT baseline across three different Gemini models. The results suggest that the AGoT can make more robust models with stronger reasoning capabilities, where the backtracking mechanism and multi-path exploration help recover from incorrect intermediate steps.