cs.AIOct 17, 2026
SaveBellman Language Models: Solving the Recurring Decisions of LLM Agents
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 -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: 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, and , and building costing one model call per state and move. Each curve is a fallback share. Notice that savings level off at : 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 -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.
| 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 |
| The policy in the prompt | |||
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 that a failure is a regression; the cheapest move changes at and . 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 | Hidden (prior from) | Reader | Moves | Cost unit | MDP / QMDP / POMDP as implemented |
|---|---|---|---|---|---|---|
| -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 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 / best final move under / 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 sold 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 |
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? |
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 |
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 |
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 |
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.
More in this topic
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