💻 computer science

Reinforced Graph of Thoughts: RL-Driven Adaptive Prompting for LLMs

This paper proposes Reinforced Graph of Thoughts (RGoT), an automated framework that utilizes reinforcement learning to dynamically adapt the graph of operations in Graph of Thoughts prompting, thereby overcoming the rigidity of manually defined structures to better handle complex problem-solving tasks.

Original authors: Manuel Noah Riesen, Peter Alfred von Niederhäusern

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Manuel Noah Riesen, Peter Alfred von Niederhäusern

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart but sometimes scattered assistant (a Large Language Model, or LLM) who is great at writing stories but struggles with complex math or organizing messy data. If you just ask them to "solve this," they might get confused or make mistakes, especially if the problem is huge.

To help them, researchers usually give them a "recipe" or a step-by-step plan.

Chain of Thought: Like a straight line of instructions: "Do A, then B, then C."
Tree of Thoughts: Like a family tree where the assistant tries different branches, sees which one looks good, and backtracks if it hits a dead end.
Graph of Thoughts (GoT): The most advanced version. Imagine a subway map. The assistant can split a problem into different lines, solve them separately, and then merge the results back together. This is great for big problems, but it's hard to use. You, the human, have to draw the entire subway map yourself before the assistant starts working. If you draw the wrong map, the assistant fails.

The Problem: The "Static Map"

The original "Graph of Thoughts" is like a rigid, pre-drawn subway map. It works perfectly if the problem is exactly what you expected. But if the problem gets bigger or more complicated (like a list of numbers that is twice as long as you thought), your fixed map breaks. The assistant gets lost because the map didn't account for the new size.

The Solution: Reinforced Graph of Thoughts (RGoT)

The authors of this paper, Manuel Noah Riesen and Peter Alfred von Niederhäusern, built a system called RGoT. Instead of you drawing the map, they gave the assistant a GPS that learns as it drives.

Here is how it works, using a simple analogy:

The "Summing" Game
Imagine the task is to add up a very long list of numbers.

The Old Way: You tell the assistant, "Add these numbers." If the list has 5 numbers, they do it. If it has 50, they get confused and give a wrong answer.
The RGoT Way: The system has a toolbox of basic moves:
- Split: Cut the big list into two smaller lists.
- Sum: Add up a small list.
- Merge: Combine two small results into one big result.

Instead of you deciding when to split or merge, the system uses a Reinforcement Learning (RL) agent. Think of this agent as a video game character trying to beat a level.

The Game: The "level" is the list of numbers.
The Moves: The character can choose to "Split," "Sum," "Merge," or "Stop."
The Reward: If the final answer is correct, the character gets points. If it fails, they lose points.

The Magic of Learning
At first, the agent is clueless. It might try to sum a list of 100 numbers all at once and fail. But because it's playing a "game" (using Reinforcement Learning), it learns from its mistakes.

It realizes: "Hey, when the list is huge, I get a penalty if I try to sum it all at once. But if I Split it first, then Sum the small parts, and finally Merge them, I get a huge reward!"
Over time, the agent learns to build its own "subway map" (the Graph of Operations) on the fly, perfectly tailored to the size of the problem.

What They Actually Did

The researchers tested this on several tasks:

Summing lists: Adding up numbers.
Sorting lists: Putting numbers in order.
Counting keywords: Finding how many times a word appears in a text.
Merging documents: Combining several texts into one without repeating information.

They didn't just use the real AI models to train (which would be too expensive and slow). Instead, they created a simulation. They figured out how likely the AI was to make a mistake on a list of 10 items, 20 items, 50 items, etc., and programmed that into the game. The agent learned in this simulation, and then they tested it on the real AI.

The Results

The paper claims that:

Adaptability: The agent learned to automatically change its strategy based on how hard the problem was. If the list was short, it did a simple sum. If the list was huge, it automatically decided to split it up first.
Better than the basics: The agent solved complex problems much more reliably than just asking the AI to "do it" in one go (the "Input-Output" method).
Generalization: Even when they gave the agent a list size it had never seen during training (like a list of 60 items when it only practiced on lists up to 30), it still figured out a good strategy.

The Bottom Line

The paper presents a way to make advanced AI problem-solving automatic. Instead of a human expert needing to know exactly how to structure a complex task, the system uses a "learning agent" to figure out the best step-by-step plan (the graph) for any given problem size. It turns a rigid, manual process into a flexible, self-adjusting one.

Note: The paper focuses entirely on these specific tasks (math, sorting, counting, merging) and does not claim this method works for medical diagnosis, legal advice, or other real-world applications outside of these defined logic problems.

Technical Summary: Reinforced Graph of Thoughts (RGoT)

Problem Statement

Large Language Models (LLMs) have demonstrated significant capabilities in deliberate problem-solving through prompting paradigms such as Chain of Thought (CoT), Tree of Thoughts (ToT), and Graph of Thoughts (GoT). While GoT offers a generalized framework where thoughts are structured as arbitrary graphs to allow for aggregation and complex reasoning, the existing implementation relies on a static, manually defined graph of operations.

This manual definition presents two primary limitations:

Accessibility: Constructing a GoT graph requires in-depth knowledge of the problem solution and the specific ordering of operations, creating a high barrier to entry for users.
Adaptability: Static graphs are rigid. They cannot adapt to the varying complexity of input instances or the non-deterministic, entropic nature of LLM outputs. Consequently, a graph designed for a specific complexity level may fail when applied to inputs with different properties.

While prior work (Ha et al., 2024) has attempted to automate GoT, it relies on the underlying LLM's logical capabilities to construct the graph. This paper addresses the need for an approach that does not depend on the LLM's planning abilities to generate the reasoning topology itself.

Methodology

The authors propose Reinforced Graph of Thoughts (RGoT), an automated approach that utilizes Reinforcement Learning (RL) to adaptively generate a graph of operations from a human-defined set of available operations.

Core Framework Components

The system decouples the Graph of Operations (GoO) from the Graph of Thoughts (GoT):

Graph of Operations (GoO): A directed acyclic graph (DAG) that defines the sequence and structure of operations. It is constrained by maximum depth ( $d_{max}$ ) and breadth ( $b_{max}$ ). To ensure convergence, a divergence cutoff depth ( $d_{\neg div}$ ) is enforced, after which the graph must converge toward a single sink.
Graph of Thoughts (GoT): The actual execution trace where LLM thoughts are generated. Each thought references the operation that created it.
Operations: Defined as either Prompt Operations (LLM calls) or Execution Operations (programmatic functions). A Score Operation evaluates the quality of a thought, returning a numerical score.

Reinforcement Learning Formulation

The RGoT agent operates within a custom RL environment to construct the GoO layer-by-layer.

State Space ( $S$ ): A composition of discrete spaces including current graph depth, breadth, task complexity, local complexity, the sequence of operations in the current graph, previous actions, and the previous score.
Action Space ( $A$ ): Discrete actions including stop (end graph construction), backtrack (remove the sink layer), and append(o) (add a new layer with operation $o$ ).
Reward Function: Designed via reward shaping to penalize excessive depth, reward valid operations, and provide a significant positive reward for successfully solving the task (final state).
Simulation: To mitigate the high cost of training with real LLM calls, the LLM's behavior is simulated. The success probability of an operation at a given complexity $c$ is modeled as a Bernoulli experiment with probability $P(c)$ , empirically estimated by prompting the target LLM (e.g., gpt-3.5-turbo-0125) 100 times per complexity level.

Experimental Setup

The authors evaluated RGoT on five tasks:

Sum List: Summing a list of integers (primary example).
Sort List: Sorting integers.
Intersect Set: Finding set intersections.
Count Keywords: Counting keyword occurrences in text.
Merge Documents: Merging documents while maximizing retention and minimizing redundancy.

The experiments utilized the Proximal Policy Optimization (PPO) algorithm with a 2-layer network architecture (64 units). The agents were trained on a specific range of complexities and then evaluated on both in-distribution and out-of-distribution (higher complexity) instances.

Key Results

Adaptive Construction: The RL agents successfully learned to construct graphs of operations that adapt to task complexity. As complexity increased, the agents automatically increased the branching (divergence) and depth of the graph to decompose the problem, a behavior not explicitly programmed but learned through the reward signal.
Performance vs. Baseline: RGoT agents significantly outperformed the standard Input-Output (IO) prompting baseline. While IO strategies failed as complexity increased beyond the LLM's direct capability, RGoT agents maintained high success rates by decomposing tasks.
Generalization: The agents demonstrated the ability to solve out-of-distribution complexities (complexities higher than those seen during training), achieving a total average solved rate of $0.7512 \pm 0.1089$ .
Variance: The authors observed variance in agent performance across different random seeds, particularly in out-of-distribution regions. This is attributed to the sparse reward signal at high complexities and the on-policy nature of PPO, which limits the agent's ability to recover from early suboptimal trajectory commitments.

Significance and Claims

The paper claims to be the first work to present an automated approach for constructing a graph of thoughts by generating and traversing a graph of operations without relying on the language model's ability to plan or understand the task's properties.

Key contributions include:

Automation of GoT: Removing the need for manual graph definition, thereby making the GoT paradigm more accessible to users who only need to define the set of available operations.
Adaptability: Demonstrating that an automated agent can dynamically adjust the reasoning topology based on input complexity, overcoming the rigidity of static graphs.
Model Agnosticism: The framework is agnostic to the specific LLM used. By simulating the LLM's success probabilities, the system can be trained cost-effectively and applied to various models, including those with different capability ranges.
Complementarity: The authors note that RGoT (structuring the reasoning topology) is complementary to Knowledge Graph of Thoughts (KGoT), which structures externally retrieved knowledge, suggesting potential for combined future applications.

The authors maintain a modest tone, acknowledging that while the approach shows promise under specific constraints and for defined tasks, the variance in performance and the reliance on simulation for training remain areas for consideration. They do not claim universal superiority over all prompting methods but highlight the specific utility of adaptive, automated graph construction for complex, decomposable tasks.