Bellman Language Models: Solving the Recurring Decisions of LLM Agents

Adarsh Vatsa; William Eiers

cs.AIOct 17, 2026

Bellman Language Models: Solving the Recurring Decisions of LLM Agents

Authors: Adarsh Vatsa, William Eiers

Organizations: Stevens Institute of Technology

Abstract

A general observation in agentic workflows, especially bounded ones, is that the decision space of the LLM, when we separate a decision from generation, starts approaching saturation: the agent meets the same states again and again, and after enough conversations it stops meeting new ones. LLMs generally don't treat these decisions as an optimization problem and instead re-derive them from their context/prompt on every turn. We show that treating decision making within reasonable bounds as an optimization problem, solving it once, and reusing the solved decisions can often make an agent faster, cheaper and more reliable. Our approach, which we call Discretize, Then Decide, starts from data such as the workflow's own logs or, when none exists, runs of the LLM agent itself. It reads each conversation into discrete states and estimates the probability of each outcome and the cost of each move, 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, sending moves whose content is fixed in the state, such as a tool call or a templated reply, and any state it hasn't seen is sent back to the LLM. We call an LLM run this way a Bellman language model (BLM), after Richard Bellman's equation for the best move in each state. On $τ^2$ -bench telecom, the controller with no model solves 79% of tasks. As a BLM, Qwen3.8-27B, an open model, goes from 29% to 96% with 93% fewer model calls. For Claude Opus 5.5, which solves 96% of tasks on its own, running it as a BLM cuts model calls and cost per task by about 98% and lets it solve 2 more tasks. On InventoryBench, the solved policy with no model beats every published method. Where the hard part is writing content rather than choosing moves, such as resolving SymPy issues, few decisions can be solved in advance, and a BLM helps little.

Figures & tables

Figure 1: Discretize, Then Decide. Top: built once, run every turn. The key point is that when the state fixes the move, the turn never reaches the model. Bottom: tasks solved against agent tokens in telecom, where up and to the left is better. Telling the model the solved policy moves it up. Executing it moves it up and left. Other variants: Table 4 .

Figure 2: Step 1 on the worked example: reading conversations into states. Customers word the same fact in many ways. Notice that the reader keeps only the fact, so different conversations end up in the same state.

Figure 3: Step 2 on the worked example: estimating. Each column is a past task, with a dot for each fault it had. Counting the dots gives the probability of each fault. Notice that roaming is off in six of the eight, the most common fault.

Figure 4: Step 3 on the worked example: solving. Left: the solved policy asks first about the fault with the highest probability per turn. Right: the total turns each of the six orders takes over the eight past tasks, where fewer is better. Notice that the solved order takes the fewest turns, and asking about travel last takes the most.

Figure 5: Step 4 on the worked example: running. A new customer has all three faults. When the state fixes the move, the controller sends it with no model call. Notice that only the off-script question goes to the LLM, and its reply is read back into the state.

Figure 6

Figure 6: The real task the worked example comes from, abridged from the logged transcripts. Dark tags mark each fault an agent fixed. Notice that alone, Qwen3.8-27B never asks about travel and hands the customer to a human. In the BLM, the controller sends every move and fixes all three faults with no model call.

Stage	Check	Fault rate	Turns	Rate per turn	Order: solved / Opus
1	Airplane mode	0.49	1.09	0.45	1 / 1
1	SIM card	0.50	2.86	0.18	2 / 3
2	Roaming (travel question)	0.74	1.20	0.61	3 / 8
2	Data usage	0.51	(1)	0.51	4 / —
2	Mobile data	0.50	1.36	0.37	5 / 2
2	Network mode preference	0.51	1.60	0.32	6 / 6

Table 1: The solved order for picture messaging, beside Opus’s. Stage: the guide’s stages, in order. Fault rate: share of training tasks with the fault. Turns: mean turns Opus spent on the check, with (1) where none were measured. Opus’s order: by when it first asks about each check, and a dash means never. Notice that roaming comes third, behind the first stage.

Figure 7: The cost law (Proposition 4 ) for an example with 120 decision states, 4 moves each, 3 decisions per conversation,

\rho=0.02

and

a=0.02

, and building costing one model call per state and move. Each curve is a fallback share. Notice that savings level off at

1/(\rho+f+a)

: about 14, 7 and 3 times cheaper for 3%, 10% and 25% fallback.

Test set (controller)	Qwen alone	Qwen + BLM	Opus alone	Opus + BLM
Test set 1 (first), of 114	52 (17.9)	94 (4.2)	111 (15.6)	114 (0.43)
Test set 2 (second), of 114	31 (18.4)	102 (4.9)	111 (17.0)	113 (0.61)
Test set 3 (third), of 114	33 (20.9)	109 (1.5)	110 (16.9)	112 (0.25)
Unseen-fault set 1 (first), of 60	22 (19.6)	42 (6.4)	—	—
Test set 2, Opus customer (second), of 64	45 (19.9)	63 (1.6)	64 (17.0)	64 (0.78)

Table 2: Registered

\tau^{2}

-telecom results, one row per test set, each with its own frozen controller. Each cell gives the tasks solved, with the model calls per conversation in parentheses. In unseen-fault set 1, every task contains a type of fault missing from all training tasks. In the last row, Claude Opus 5.5 plays the customer. Notice that as BLMs, both models solve as many tasks or more, with a small fraction of the calls.

Figure 8: Distinct values seen as training conversations accumulate, as a share of the number seen by the end: 1,721 telecom training conversations that ran without a solved policy, replayed in the order they were collected through the third controller’s reader. The decision state the solved policy acts on levels off. The full record of checks made and the agent’s messages keep growing to the end.

Figure 9: Every agent turn on test set 1 with Claude Opus 5.5. Each row is one conversation (114, sorted by model calls) and each cell one agent turn, colored by what produced it. Left: Opus alone calls the model on every turn. Right: notice that in the Bellman model almost every turn is an executed lookup or template, and 82 of the 114 conversations contain no model call at all. Conversations with the BLM have more turns, because each check is a separate instruction.

Agent	pass 1	pass 3	Calls	Agent tokens
Qwen alone	67.2%	40.0%	19.1	181k
Qwen + BLM	97.8%	93.3%	0.97	11k
Qwen + BLM, thinking fallback	100%	100%	0.32	3.2k
Opus alone (41 attempts)	100%	—	16.3	233k
Opus + BLM	100%	100%	0.27	4.1k

Table 3: Unseen-fault set 2: 60 tasks, each with a type of fault missing from all training tasks. Claude Opus 5.5 plays the customer, and each task gets three attempts. pass 1 : share of attempts that succeeded; pass 3 : share of tasks solved in all three attempts. Notice that the BLMs solve nearly every task in all three attempts, at under one model call per conversation.

The policy in the prompt
Agent	Solved	Calls	Tokens (k)
Qwen alone	31	18.4	174
Qwen + BLM (solved order)	102	4.9	59
Qwen + BLM (QMDP / planning over beliefs)	100 / 93	5.0 / 5.1	57 / 57
Opus alone	111	17.0	246
Opus + BLM	113	0.61	10

Table 4: Test set 2 (114 tasks, Qwen3.8-27B as the customer): knowing the solved policy versus executing it. Rows below the first line are unregistered comparisons on the same tasks. Checklist: the solved check order and the procedures in the prompt; with templates: plus every message the controller would send, verbatim. Oracle plan: the benchmark’s list of the actions each task requires. Tokens: the agent’s prompt and completion tokens per conversation, in thousands, including thinking. Notice that telling the model the solved policy leaves 18 to 23 calls per conversation, while executing it leaves about 5 or fewer.

Batch	OR rule	Best published	BLM, QMDP	BLM, planning over beliefs
Real, lead 0	0.671	0.772	0.785	0.786
Real, lead 4	0.302	0.308	0.359	0.421
Real, stochastic	0.210	0.353	0.445	0.454
Synthetic, lead 0	0.818	0.860	0.865	0.865
Synthetic, lead 4	0.536	0.558	0.651	0.662
Synthetic, stochastic	0.107	0.411	0.519	0.525

Table 5: InventoryBench normalized reward. OR rule: the benchmark’s published operations-research rule, which our reimplementation reproduces. Best published: the best score per batch on the leaderboard ( InventoryBench, 2026 ) (three different methods, while the best single method scores 0.538 overall). BLM settings were chosen on the other data split (real or synthetic) only. Notice that the BLM leads on every batch.

Figure 10: Where InventoryBench’s gain comes from. Notice that better beliefs alone bring the published rule to about the best published level, and the solved decision rule does the rest.

Figure 11: The decidable share, measured from the LLM agent’s own conversations, against the model calls BLM removed. Horizontal: the share of the LLM agent’s turns where a frozen controller’s state fixes the content, found by replaying the controller over those conversations (InventoryBench: 100% by construction). Vertical: model calls per conversation removed by the BLM. Telecom: one point per test set. The bar for SymPy spans two ways of matching the agent’s turns to the controller’s moves. Notice that points above the diagonal remove more calls than the share predicts, because the solved policy changes the conversation (Qwen on test set 3) or ends it early (SymPy). In CI (not plotted), the solved policy makes every decision, though it still pays an LLM to read some logs.

Domain (measure)	Most likely / fixed order	QMDP	Planning over beliefs
CI triage ($ per failure)	32.79	16.49	14.16
InventoryBench (reward)	0.546	0.610	0.626
SymPy (solved of 63)	17	16	19
Telecom, test set 1 (solved of 114)	94	86	88
Telecom, unseen-fault set 1 (solved of 60)	42	38	33
Telecom, test set 2 (solved of 114)	102	100	93

Table 6: The three solvers under the same states, probabilities and costs. In telecom, the simplest solver is the fixed order, which ignores the belief. CI: dollars per failure on the 169 failures with all outcomes observed (lower is better). In the other rows, higher is better. Notice that no solver wins everywhere: which one does best follows what the moves do.

Figure 12: Calibration matters only where it flips a decision. Left: expected cost of the three moves that end a CI triage, as a function of the belief

b

that a failure is a regression; the cheapest move changes at

b=0.125

and

b=0.75

. Right: the controller’s beliefs before calibration, against outcomes, on 198 validation failures. Notice that its most confident bin, where it backs out changes, was right 72% of the time (51 of 71), below the 0.75 needed for backing out to pay.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Domain	Observed state $x$	Hidden $h$ (prior from)	Reader	Moves	Cost unit	MDP / QMDP / POMDP as implemented
$\tau^{2}$ -telecom	kind of problem, fixed yet, checks left, what stops a fix; line, bill, usage, travel status	remaining fault set (fault-set frequencies per kind of problem, train split)	regular expressions; tool results	info.: lookups, travel question, re-asks; acting: check templates, payment, resume, refuel, roaming; terminal: hand-off, close	customer turns per check	fixed order by $P(\text{fault})/$ turns / check most likely to address a remaining fault / two-move lookahead
CI triage	platform, duration, suite, test label history, retrigger counts	regression vs intermittent (logistic prior, train window)	retrigger outcome (beta-binomial); LLM log verdict	info.: retrigger, LLM read; terminal: mark intermittent, back out, escalate	dollars	act on $b\geq 0.5$ / best final move under $b$ / two-move search over beliefs
InventoryBench	on hand, outstanding orders and ages, demand history	lead-time distribution, arrival times, demand model	exact arrivals and demand	acting: order quantity (information arrives regardless)	reward $p\cdot$ sold $-\,k\cdot$ stock	most likely arrivals and demand model / newsvendor quantity at arrival over the belief / rollout over sampled futures
SymPy	last test result, attempts, scope, step	agent’s phase before its first edit	Laya; frozen reproduction test	info.: search, read, run, defer; acting: edit; terminal: submit (executed)	billed tokens	table of move values for the most likely phase / move values weighted by the belief / defer when the expected value of perfect information exceeds 1,300 tokens, the cost of one agent step

Appendix

Table 7: How each domain fills in the decision process. “Info.” = information moves. Telecom and SymPy run live with an LLM; CI and InventoryBench are evaluated offline.

What came in	State	What the controller sent
“I’m having trouble sending MMS messages…”	picture messages; unknown; airplane mode	Template: asks for the phone number.
“…my phone number is 555-123-2002.”	unchanged	Four lookups: the customer, two lines (to find the one with this number) and the line’s plan.
The lookup results	unchanged	Template: check airplane mode and the SIM card.
“I can’t perform multiple actions at once.”	unchanged	Template: check airplane mode alone.
“Airplane Mode was on, so I’ve turned it off.”	unknown; SIM card	Template: check the SIM card.
“My SIM card shows as active and working.”	unknown; roaming	Template: are you travelling outside your home country?

Appendix

Table 8: The Bellman model’s conversation of Figure 6 , from the controller’s side (abridged from its log). State: the kind of problem, whether it’s fixed yet, and the first check in the solved order not yet made; nothing stopping a fix was found. Every message on the right was sent by the controller, and none came from the model.

Domain (baseline)	Decidable	Executed	Calls
Telecom, Opus, test sets 1–3	98% [55–61, 97]	97–99%	$-$ 96 to $-$ 99%
Telecom, Qwen, test sets 1–3	76–80% [26–31, 96–99]	80–93%	$-$ 74 to $-$ 93%
SymPy, Qwen	15–22% [1, 15]	3%	$-$ 23%
InventoryBench, CI	100%	100%	all decision calls

Appendix

Table 9: Decidable share of the LLM agent’s turns (in brackets, the share that agrees with the controller’s next move and the share anticipated by some move of the controller), the share of turns the BLM executed, and the change in model calls per conversation. InventoryBench and CI are decision-only by construction.

Test set	Agent	Conversations	Unseen decision state	Unseen record of checks
Test set 1	Qwen alone	114	0 (0 of 2,038 turns)	50
	Opus alone	114	0 (0 of 1,779)	43
Test set 2	Qwen alone	114	0 (0 of 2,095)	65
	Opus alone	114	0 (0 of 1,934)	61
Test set 3	Qwen alone	114	0 (0 of 2,380)	62
	Opus alone	114	1 (1 of 1,923)	62

Appendix

Table 10: Coverage of the test sets by the training conversations: conversations of the LLM on its own that reached a decision state, or a record of checks, not seen in training. Turns in unseen decision states in parentheses.

Figure 13: Tasks solved by number of faults, for each test set with its own frozen controller. Points are success rates with Wilson 95% intervals. Notice that alone, Qwen3.8-27B does worse as faults are added, and as a BLM it declines much less.

Policy	Real outcomes	Simulated:	Simulated:
	(169 failures)	per-test rates	simpler model
BLM, planning over beliefs: the controller we report	$14.16	$8.70	$9.79
the same, without calibration	$16.18	$7.85	$10.10
the same, recalibrated	$14.85	$8.24	$9.51
the simpler controller	$14.98	$10.06	$9.62
BLM, QMDP	$16.49	$12.80	$12.80

Appendix

Table 11: CI triage, cost per failure. Real outcomes: the 169 test failures with all retrigger outcomes observed. The simulated columns score all 1,173 test failures, drawing unobserved retriggers from a pass rate per test fitted on all the data, or from the simpler controller’s outcome model. The best rule is chosen on the training window under each column’s scoring. The recalibrated controller was scored in a separate run. Notice that on real outcomes the simple rule and Qwen are cheapest, while in both simulated columns the planning controllers are.

LLM Decision-Making

LLM decision-making studies how language models choose, act, seek information, and allocate resources under goals, uncertainty, constraints, and social pressures.

See all 229 papers

Oct 15, 2026

JevAgentHarness: Benchmarking, Deploying and Training Decision Models That Share Control with LLMs

Large language model (LLM) agents now fix software, operate computers and serve customers, but their harnesses, the programs that run them, call a large LLM at every step, which makes long tasks slow and costly. Most of these calls end in a multiple-choice decision, such as which tool to call next. Decision models such as Jev answer these questions directly, at a fraction of an LLM call's time and price. We ask how a harness can delegate these decisions to a decision model with little loss of success. To evaluate decision models in agentic tasks, we build AgentDecisionBench, which tests them from isolated questions up to control of a running agent, on public benchmarks and our DecisionGym environment. The decision model most accurate on isolated questions solved only 69.5% of agent tasks, and without a fitted confidence threshold, delegating tool choices lowered success by 19.0 points. Building on these findings, we then design JevAgentHarness, which fits this threshold for each choice on the agent's own trajectories and lets the LLM decide below it. Because existing decision models never see the states an agent reaches after its own mistakes, we train AgentDecision-4B, an open 4B model, on such states with Jev's answers as labels. On tasks unlike its training data, the agent solved 91.5% of them with AgentDecision-4B and 82.0% with Jev. On tasks like their training data, 4B models trained this way made agents 81.1-89.0% cheaper and up to 2.5 times faster, without losing 3 or more points of task success. The models, data, and harness will be released at https://github.com/JevAgentHarness/JevAgentHarness.

Kunlun Zhu, Tao Feng, Xu Han +5

University of Illinois Urbana-Champaign · Princeton University · Google

LLM Agent Harnesses LLM Agents Tool Selection for Language Model Agents LLM Decision-Making AI Agent Benchmarks LLM Agent Training+1

Ask PDF

Apr 9, 2026

Don't Overthink It: Inter-Rollout Action Agreement as a Free Adaptive-Compute Signal for LLM Agents

Inference-time compute scaling has emerged as a powerful technique for improving the reliability of large language model (LLM) agents, but existing methods apply compute uniformly: every decision step receives the same budget regardless of its difficulty. We introduce TrACE (Trajectorical Adaptive Compute via agrEement), a training-free controller that allocates LLM calls adaptively across agent timesteps by measuring inter-rollout action agreement. At each step, TrACE samples a small set of candidate next actions and measures how consistently the model commits to the same action. High agreement signals an easy decision; the controller commits immediately. Low agreement signals uncertainty; the controller samples additional rollouts up to a configurable cap before committing to the plurality action. No learned components, no external verifier, and no human labels are required. We evaluate TrACE against greedy decoding and fixed-budget self-consistency (SC-4, SC-8) on two benchmarks spanning single-step reasoning (GSM8K, n=50) and multi-step household navigation (MiniHouse, n=30), using a Qwen 2.5 3B Instruct model running on CPU. TrACE-4 matches SC-4 accuracy while using 33% fewer LLM calls on GSM8K and 39% fewer on MiniHouse. TrACE-8 matches SC-8 accuracy with 55% fewer calls on GSM8K and 65% fewer on MiniHouse. We further show that inter-rollout agreement is a reliable signal of step-level success, validating the core hypothesis that the model's own output consistency encodes difficulty information that can be exploited without training. TrACE is the first training-free, per-timestep adaptive-compute controller for LLM agents to be evaluated on multi-step sequential decision tasks.

Khushal Sethi

Stanford University

Inference-Time Compute Allocation LLM Inference Efficiency Long-Horizon LLM Agents LLM Uncertainty Estimation

Ask PDF

Sep 22, 2026

REFLEX with Jev for Efficient Selective Control in LLM Agents

LLM agents often use generative models for bounded decisions, raising the question of when these decisions can be handled more efficiently without reducing task success. We study REFLEX, an agent architecture that uses Jev as a fast, typed decision layer and calls a strong LLM when confidence is low, or generation is required. On a frozen 100-task benchmark, REFLEX achieves 95% success with 72.7% fewer strong-model calls than a strong-only agent, with reductions persisting across three fallback families. Controlled interventions show that reliability depends on action-set size and near-valid alternatives near authorization boundaries. External BFCL and

τ

-style evaluations reveal limited advantages over a cheap generative cascade when ordinary routing is already highly accurate. These findings identify when selective control with Jev can reduce computation and where its benefits are limited.

Tiantong Wu, Wei Yang Bryan Lim

Nanyang Technological University Singapore

LLM Inference Efficiency LLM Agent Evaluation LLM Decision-Making LLM Agents LLM Agent Reliability

Ask PDF

Abstract

LLM Decision-Making

Explore similar work

JevAgentHarness: Benchmarking, Deploying and Training Decision Models That Share Control with LLMs

Don't Overthink It: Inter-Rollout Action Agreement as a Free Adaptive-Compute Signal for LLM Agents

REFLEX with Jev for Efficient Selective Control in LLM Agents