LLM Agents

An LLM agent is a system in which a large language model repeatedly produces an action, receives an observation from executing that action in an environment, and updates its internal reasoning state, continuing until it emits a final answer or exhausts a budget. Formally, we can view this as a partially observable sequential decision process: at each timestep $t$ the agent holds a context $c_t$ (the running transcript of thoughts, actions, and observations), selects an action $a_t \sim \pi_\theta(\cdot \mid c_t)$ where $\pi_\theta$ is the LLM's next-token distribution constrained to a structured action format, receives an observation $o_t = \mathrm{Env}(a_t)$, and forms $c_{t+1} = c_t \Vert a_t \Vert o_t$. This is a Markov decision process over an unbounded context, with the crucial twist that the "policy" is a pretrained language model steered by prompting rather than a network trained end-to-end by reinforcement learning (though RL fine-tuning of agents is an active and increasingly common variant). The canonical instantiation is ReAct (Reason + Act): at each step the model is prompted to produce a Thought (free-form chain-of-thought reasoning about what to do next), an Action (a structured tool call, e.g. `search("flights NYC to Tokyo")`), and then the harness supplies an Observation (the tool's return value) before the next Thought. Interleaving reasoning with acting lets the model use intermediate results to correct its plan — a search may return nothing useful, prompting a reformulated query — something a pure chain-of-thought trace without tool grounding cannot do, because it never touches ground truth. Three components distinguish an agent from a plain prompted model. First, tools: external functions (search, calculator, code execution, database queries, browser actions) that the model invokes via structured Tool Use & Function Calling syntax, extending its effective knowledge and capability beyond its parameters. Second, memory: short-term memory is simply the growing transcript in context; long-term memory may be an external store (a vector database) that the agent reads from and writes to across sessions, since context windows are finite. Third, a control loop and stopping criterion: a program that parses the model's output, dispatches the action, appends the observation, and decides when to terminate — via an explicit "Final Answer" token, a step budget, a success check, or a supervisor's veto.

The agent loop is a straightforward program wrapped around repeated LLM calls, but its correctness depends on careful handling of parsing, error propagation, and termination. Below is a complete, language-agnostic implementation of the ReAct-style loop, including the parts most toy descriptions skip: malformed-action recovery, tool-error handling, and a hard step budget to guarantee termination. ``` function RUN_AGENT(goal, tools, model, max_steps, max_tokens_budget): history = [] # list of (thought, action, observation) tuples step = 0 tokens_used = 0 prompt_prefix = build_system_prompt(goal, tools) while step < max_steps and tokens_used < max_tokens_budget: step += 1

# 1. Assemble context: system prompt + goal + full transcript so far context = prompt_prefix + render(history)

# 2. Query the model for the next reasoning + action raw_output, n_tokens = model.generate(context) tokens_used += n_tokens

# 3. Parse structured output: expect "Thought: ... \n Action: name(args) \n" parsed = parse_action(raw_output) if parsed is PARSE_FAILURE:

# Model produced malformed action syntax — do not crash, correct it observation = "ERROR: could not parse action. Use format Action: tool(args)." history.append((raw_output, None, observation)) continue thought, action_name, action_args = parsed

# 4. Check for termination action if action_name == "FINISH": return SUCCESS(final_answer = action_args, trace = history)

# 5. Validate the tool exists if action_name not in tools: observation = f"ERROR: unknown tool '{action_name}'. Available: {tool_names(tools)}" history.append((thought, action_name, observation)) continue

# 6. Execute the tool, catching runtime failures try: observation = tools[action_name].execute(action_args) except ToolExecutionError as e: observation = f"ERROR: tool failed with: {e}"

# 7. Append this step to the transcript (the agent's growing state) history.append((thought, action_name, observation))

# Budget exhausted without an explicit finish — fail gracefully return TIMEOUT(partial_trace = history) ``` ``` function parse_action(raw_output):

# Extract "Thought:" and "Action:" segments with a strict grammar;

# tolerate whitespace variance but reject anything that doesn't match. match = regex_match(raw_output, THOUGHT_ACTION_GRAMMAR) if match is None: return PARSE_FAILURE return (match.thought, match.action_name, match.action_args) ``` Three design decisions in this pseudocode are load-bearing, not stylistic.

(a) Malformed output never crashes the loop. Because the model's output is free text constrained only by prompting, it will occasionally violate the expected grammar. The loop treats a parse failure as just another observation — an error message fed back in — rather than an exception that halts the program. This mirrors how a compiler reports a syntax error rather than segfaulting.

(b) Every branch converges to `history.append(...)` or a return. This guarantees the loop body always makes forward progress (either by appending a new transcript entry, which will change the next prompt and therefore the next model output, or by returning). Without this invariant, an unhandled branch could spin the model on an identical context, wasting the entire step budget on a repeated request.

(c) Two independent budgets — `max_steps` and `max_tokens_budget` — enforce termination. An LLM agent has no built-in halting proof; nothing in the mathematics of a transformer bounds how long a badly-prompted agent will call tools. Termination is therefore engineered, not derived, and both a step count and a token count are checked because a single verbose step could otherwise exhaust context length before exhausting the step counter.

Per-step cost. Each iteration issues one LLM call whose cost scales with the length of the context, which grows by roughly one thought+action+observation chunk per step. If a chunk contributes on average $k$ tokens and the transformer's forward pass is $O(n^2)$ in sequence length $n$ (for the standard dense self-attention; sub-quadratic and cached-KV implementations reduce the marginal per-token cost but not the asymptotic footprint of very long transcripts), then after $t$ steps the context has length roughly $n_0 + tk$, and the $t$-th step costs $O((n_0 + tk)^2)$ with a naive re-encoding, or $O((n_0+tk) \cdot k)$ per step if key-value caching lets the model only encode the new suffix and reuse cached attention keys/values from prior steps — which is standard practice.

Total cost over $T$ steps. Summing the incremental (KV-cached) per-step cost gives

which is quadratic in the number of steps $T$ — the same asymptotic shape as processing one long sequence of length $Tk$, because the transcript is effectively one growing sequence. This is the fundamental reason agent frameworks impose step budgets and summarization/compaction of old history: without bounding $T$ or periodically compressing `history` into a shorter summary, cost grows quadratically and eventually the context exceeds the model's window, hard-capping feasible episode length regardless of budget.

Space. The context held in memory is $O(n_0 + Tk)$ tokens; if a long-term memory store is used, retrieval adds $O(\log m)$ per lookup for an indexed store of $m$ memories (e.g. approximate nearest-neighbor search over embeddings), amortizing the cost of unbounded history by only pulling in the relevant slice at each step.

Correctness — what can and cannot be guaranteed. There is no proof that an LLM agent reaches a correct final answer, because the "policy" $\pi_\theta$ is not verified against a formal specification — it is a learned distribution over plausible next actions. What can be argued rigorously is a conditional termination guarantee and a conditional progress argument: 1. Termination is guaranteed by construction, not by the model. Because the loop enforces `step < max_steps` and `tokens_used < max_tokens_budget` as loop invariants checked every iteration, and every code path inside the loop body either returns or executes exactly one iteration of `step += 1`, the loop halts within $\max\_steps$ iterations. This is a simple structural invariant, analogous to bounding recursion depth to prevent stack overflow — it is a property of the harness, not of the language model's reasoning quality. 2. Progress toward the goal is only as reliable as the observations are informative and truthful. If tool outputs are grounded (e.g., a search API genuinely returns relevant documents, a calculator genuinely computes the requested arithmetic), each observation reduces the agent's uncertainty about the world state, analogous to how new evidence updates a Bayesian belief — the agent's next Thought conditions on strictly more grounded information than the last. This is why ReAct-style grounding empirically outperforms pure chain-of-thought on knowledge-intensive tasks: chain-of-thought's intermediate "facts" are unverified model outputs that can drift from truth over many steps (a compounding hallucination problem), while tool observations are anchored to an external, checkable source. 3. Compounding error is the dual risk. If step $t$'s observation is wrong or misparsed and the agent does not detect this, that error becomes an unchallenged premise in the context for all subsequent steps — an analogue of error propagation in iterative numerical methods without a correction step. Because nothing in the transformer architecture "notices" that Thought$_5$ contradicts Observation$_2$ unless the model happens to attend to and reconcile it, correctness in practice depends heavily on scaffold-level safeguards: verifiers, self-consistency checks, or a human/automated critic step that can re-open an earlier decision rather than blindly proceeding. The honest summary: the engineering guarantees (bounded steps, no crashes on malformed output, monotone progress through the transcript) are provable from the pseudocode's structure. The semantic guarantee (the agent actually accomplishes the goal) is empirical and probabilistic, resting on the quality of the underlying model, the fidelity of the tools, and the presence of verification steps — not on any theorem.

Goal: "Find the population of the capital of the country whose flag is the Vietnamese flag's mirror image color-wise, then tell me if that population exceeds 10 million." (Deliberately convoluted, to force genuine multi-step tool use and a recoverable error.)

Final answer: "Under the interpretation that the color-inverted flag points to Japan, the capital is Tokyo, with a city population of roughly 14 million — yes, this exceeds 10 million." This trace exercises exactly the properties argued above. Step 2 is a tool failure (`ERROR: 0 relevant results`) that the loop does not crash on — it becomes an observation, and the agent's Step-3 Thought explicitly reacts to it by reformulating the query, which is the grounded-correction behavior that distinguishes ReAct from a single unverified chain-of-thought guess. Step 3's observation is itself soft/uncertain ("closest common answer... treated loosely") and the agent's Step 4 Thought explicitly flags the assumption rather than silently asserting it as fact — good agent behavior surfaces its own uncertainty in the transcript so a downstream reader (or a supervising verifier) can audit the chain. Note also that the transcript length grew by roughly one (Thought, Action, Observation) triple per row, illustrating the linear growth in $n$ that underlies the quadratic total-cost bound derived above.

LLM agents underlie coding assistants that read a repository, run tests, interpret failures, and iteratively patch code — a loop structurally identical to the ReAct pattern, with a test suite serving as the grounding "environment." Browser-automation agents navigate web pages, click elements, and extract information to complete tasks like form-filling or price comparison, treating the DOM as the tool interface. Customer-support and enterprise-workflow agents query internal databases, CRM systems, and ticketing APIs, using the same perceive-think-act loop with domain-specific tools substituted in. Scientific and data-analysis agents call code interpreters and statistical libraries, verifying their own computations against executed code rather than trusting the model's mental arithmetic. Multi-agent systems compose several such loops — a planner agent, a critic agent, an executor agent — communicating through shared transcripts or message-passing, extending the single-loop architecture described here into a small distributed system. Because these agents take real actions with real side effects (sending emails, executing trades, modifying files), the reliability arguments in this article — bounded loops, grounded observations, explicit error handling — are precisely the concerns that motivate the discipline of Safety & Red-Teaming for deployed autonomous systems.

Ask the tutor: How would you redesign the agent loop to support a supervising "critic" model that can veto or revise actions before they are executed?