Bellman Language Models: Optimizing LLM Agent Decisions with Reinforcement Learning

When building LLM agents, one often-overlooked fact is that many decision scenarios are in fact highly repetitive. As an agent works through a task, it repeatedly encounters the same states, and the LLM has to re-derive a decision from context every single time—which is both slow and expensive. A recent study proposes a method called "Bellman Language Models (BLM)" that models repeated decisions as a Markov Decision Process (MDP), solves it once, and then reuses the solution, greatly improving efficiency.

Repeated Decisions: The Hidden Killer of Agent Efficiency

In agent workflows of bounded scope, the decision space gradually saturates. The agent repeatedly encounters the same states, and after enough conversations it almost never sees a new state. Traditional LLMs, however, do not treat these decisions as an optimization problem—they re-derive them from the prompt on every turn. This "reinventing the wheel" approach keeps the number of model calls high and makes costs hard to control.

The research points out that treating decisions within a reasonable scope as an optimization problem—solving once and reusing—often makes agents faster, cheaper, and more reliable. The underlying insight is that many decisions are essentially about choosing an action rather than generating content, and choosing an action can be fully optimized through a precomputed policy.

Markov Decision Process (MDP) is the standard mathematical framework of reinforcement learning. It describes a sequential decision problem with a five-tuple $(S, A, P, R, \gamma)$: $S$ is the state set, $A$ is the action set, $P(s'|s,a)$ is the state transition probability, $R(s,a)$ is the immediate reward (or, equivalently here, the negative cost), and $\gamma$ is the discount factor. Its core property is the "Markov property"—the next state depends only on the current state and action, not on earlier history. This is exactly the premise for modeling repeated agent decisions as an MDP: as long as the current dialogue state is fully characterized, there is no need to look back at the entire context. Once transitions and costs are known, the optimal policy $\pi^*(s)$—i.e., "which action to choose in each state"—can be computed offline via dynamic programming, policy iteration, or value iteration. BLM's reuse builds directly on this offline solvability.

Discretize, Then Decide

The method is called "Discretize, Then Decide." Starting from workflow logs or the LLM agent's own runtime data, it reads each conversation as a discrete state and estimates the probability of each outcome and the cost of each action, until no new states appear and the probabilities stop changing. It then solves the resulting Markov Decision Process.

The solution runs as a controller around the model: for actions whose content is fixed within a state (such as tool calls or templated replies), the controller sends them directly; for unseen states, the task is handed back to the LLM. This architecture separates the LLM's generative ability from decision optimization, letting the model focus on the parts that truly require creativity.

State discretization refers to mapping continuous, free-text dialogue context into a finite set of enumerable discrete states (usually via clustering, hashing, or semantic equivalence checks). This step directly determines the size of the MDP state space and the reliability of transition estimates: too fine a granularity leads to state explosion, sparse samples per state, and noisy probability and cost estimates; too coarse a granularity merges essentially different situations, causing the learned policy to fail during real execution. The convergence criterion in the paper—"until no new states appear and the probabilities stop changing"—is in effect checking whether the state space has saturated and whether the empirical transition distribution has stabilized. This is also the fundamental reason the method only applies to scenarios where "the decision space is enumerable and convergent."

Experimental Data: Gains in Both Efficiency and Performance

On the τ²-bench telecom benchmark, a model-free controller solved 79% of tasks. As a BLM runtime, the open-source model Qwen3.8-27B raised its task solve rate from 29% to 96% while reducing model calls by 93%. For Claude Opus 5.5, which already solves 96% of tasks on its own, running it in BLM mode cut model calls and per-task cost by about 98% and additionally solved 2 more tasks.

On InventoryBench, the solved policy (model-free) beat all published methods. This shows that for decision-intensive tasks, a pre-solved policy can outperform pure LLM approaches. However, the study also found that when the difficulty lies in writing content rather than choosing actions (for example, solving SymPy problems), few decisions can be resolved in advance, and BLM offers little help. This defines the method's applicable boundary.

τ²-bench is an evaluation benchmark for tool-calling agents (such as telecom customer service and airline rebooking). It is characterized by requiring multi-turn interaction, calls to external tools, and adherence to domain rules, so the same kind of subtask recurs with highly similar intermediate states—making it very well suited to testing the hypothesis that "repeated decisions can be reused." InventoryBench is an inventory-management decision benchmark, where the action space is relatively limited and decisions lean toward selection rather than writing, so a model-free policy can already beat published methods. Understanding the difference between these two benchmarks helps clarify the scope of the paper's conclusions: the gains are concentrated on tasks dominated by "choosing actions" rather than "generating content."

Implications and Limitations

The core contribution of Bellman Language Models is bringing classic ideas from reinforcement learning into LLM agent optimization. It reminds us that not all agent decisions require real-time reasoning—many repetitive choices can be accelerated through offline solving. For teams building production-grade agents, this means substantially lower inference costs along with greater consistency.

But the method is not a panacea. It relies on the enumerability and stability of the decision space, and its advantages are limited for highly open or generation-intensive tasks. Moreover, the quality of state discretization directly affects policy performance and requires careful design. Even so, BLM offers a promising direction for optimizing agent efficiency and is worth further exploration.

One-line Summary

BLM models repeated agent decisions as an MDP, solves offline, and reuses the policy to cut costs and boost efficiency.

Paragraph Summary

The article introduces an agent optimization method called "Bellman Language Models (BLM)." Its starting point: in bounded workflows, LLM agents repeatedly encounter the same states yet re-derive decisions from context every time, leading to many model calls and high costs. The proposed "Discretize, Then Decide" pipeline discretizes dialogue logs into states, estimates transition probabilities and action costs, solves a Markov Decision Process, and runs the resulting policy as a controller around the model: fixed actions are sent directly, and only unseen states go back to the LLM. On τ²-bench, Qwen3.8-27B's solve rate rose from 29% to 96% with 93% fewer calls; Claude Opus 5.5's cost dropped by about 98%. But the method depends on an enumerable decision space and offers limited help for generation-intensive tasks.