The "State Management" Problem

At their core, LLMs are "stateless" next-token prediction machines. They don't "think" in the human sense; they predict the most likely continuation of the text they currently see in their context window. When dealing with complex tasks, it is often helpful to break down the initial problem into smaller pieces and follow logical steps to come to the final solution.

Figure 1: Context Window Illustration and Attention Decay

Doing so requires the ability to keep track of a logical chain of steps, or “states,” which is very difficult to do without an explicit dedicated mechanism. Imagine trying to solve a complex calculus problem without taking notes on paper. You would have to hold every intermediate number and step in your immediate “working memory.” Eventually, your brain gets overwhelmed, you drop a variable, and the final answer is wrong.

Similarly, if you give a complex “one-shot” prompt to an LLM, its "working memory" (the context window) gets flooded with intermediate steps, noise, and instructions. Eventually, it begins to "forget" context or hallucinate details it can no longer track.

Evolving Architectures and Prompting

Recently, researchers have come up with different ways of improving the quality of reasoning of LLMs. Two interesting approaches revolve around either changing the prompt fed to the LLM to force it to follow specific steps, or to give it a better framework for solving a specific problem.

1. Chain of Thought (CoT) Prompting

The first major breakthrough was realizing that if you force the LLM to "show its work," it performs better. Chain of Thought (CoT) involves prompting the model to think step-by-step before giving a final answer. By generating the intermediate steps into its own context window, the LLM effectively creates its own "scratchpad," helping it stay on track longer. However, it still relies entirely on the LLM's internal state and remains highly sensitive to the prompt; changing a single word in the instructions can lead to vastly different reasoning paths.

2. Agentic Systems

An agentic system is a coordinated framework of individual components designed to solve a complex problem. Rather than relying on a single model, this architecture integrates multiple elements, including specialized LLMs, deterministic code, or external APIs, to function as a unified system. By building a modular system, one can effectively separate specific functionalities: one agent solves a narrow piece of the problem, while the critical "state management" is handled externally by a structured database or a deterministic logic loop.

Experiment: Traveling Salesman Problem (TSP)

To highlight the reasoning capabilities of different approaches, we utilized a classic optimization problem: the Traveling Salesman Problem. The objective is to identify the shortest route visiting N cities exactly once. For this experiment, N=15 and the optimal cost is 291. Solving this requires the ability to satisfy simple constraints while keeping track of candidates and their cost during the search for a solution. We conducted this experiment using the Amazon Nova Premier model, one of the most advanced models for dealing with complex tasks.

Scenario A: "Zero-Shot" Attempt

A baseline scenario where we provided the LLM with the full distance matrix and a direct instruction to solve the problem in a single pass.

Prompt:

Solve the Traveling Salesman Problem (TSP) for this Distance Matrix.
Format: Return ONLY the path (e.g., [0, 5, 2...]) and the total cost.
Distance Matrix: {matrix}

Scenario B: Chain of Thought (CoT)

We guided the model to use the Branch and Bound Algorithm, instructing it to explicitly follow a detailed step-by-step process.

Prompt:

You are an expert mathematician solving the Traveling Salesman Problem.
Your goal is to find a valid, low-cost path visiting all cities exactly once.

**Strategy: Step-by-Step Instruction for Branch and Bound Algorithm**
{step by step guide}
**Format your answer exactly like this:**
<Example Step 1>
...
Final Verification:
- Path: [0, 12, ..., 0]
- Total Calculation: 23 + ... = TOTAL

Scenario C: The Agentic System

We move away from a single-prompt interface to a modular system. This architecture consists of two specialized components coordinated via an external state.

Figure 2: Simple Agentic System

The Exploration Engine (LLM)

The LLM acts as the exploration engine of the search. At each iteration, it is provided with the current status of the optimization, including cumulative costs and path depths. Its role is to analyze available partial solutions and strategically select the most promising branches to explore next.

The Compute & State Management Engine (Deterministic Tool)

This script handles the evaluation and state management part of the search. It manages the current search state and update costs, allowing the LLM to focus on exploration without needing to remember numerical details.

Stopping Criteria

The system continues its loop until the agent decides that the optimal solution has been reached or the maximum number of iterations has been reached.