Watch an AI agent handle a long task and you see a strange scene. It never rests. It searches, opens files, issues commands. And yet an hour later the task hasn't budged. It repeats the same actions, backtracks to states it already passed through, and keeps piling up information that's useless right now. It stays "busy but going nowhere" until the budget runs dry. This paper calls that the belief trap, and it's the heart of the story.
By "agent" here we mean an AI that handles multiple steps on its own, in place of a person. The usual diagnosis for this kind of spinning is "not enough memory." So we got a flood of techniques — bigger context windows, bolt-on external memory, conversation compression and summarization. The paper argues something different. The problem isn't memory; it's judgment. The agent has no coherent picture of what the situation actually is right now.
Picture a warehouse. No matter how many boxes you stack, without a ledger that says "how much stock we have right now and where it is," you have to dig through the boxes from scratch every time you need something. The raw record of an agent's actions and observations — call it the raw trajectory — is exactly those stacked boxes. All the evidence is in there. It's just that past evidence and interim judgments are tangled together in chronological order.
And the boxes don't sit still. When the agent acts, the environment changes, and a new observation can overturn the reasoning from a moment ago. So it gets harder over time to tease out "which facts still hold, which inferences still have grounds, and what's still unfinished."
Memory techniques sort through and compress this pile of boxes. That's not useless. But being able to reach the boxes doesn't mean the ledger writes itself. The authors frame the real task not as "archiving a record" but as "maintaining the present state." In other words: write a separate ledger, and keep revising it.
The idea itself isn't new. Classical agent theory already has a framework for estimating "how likely each possible state of the world is right now" and updating that estimate as observations come in (this estimate is called the belief state). But once a language model, rather than a person, starts keeping this ledger, two failure modes appear.
First, the ledger contradicts itself. The paper's example is vivid. If you record a microwave as both "open" and "closed," you can't even tell whether you need to open the door before putting the mug in.
Second, even without contradictions, the agent circles in place. This is the belief trap mentioned earlier. A contradiction is a wrong ledger; a trap is a ledger that isn't wrong but can't move forward. How you handle these two is where PoS earns its keep.
PoS (Progression of States) attacks the problem with a three-stage mechanism. First it systematically records a belief about the current situation (belief modeling); then it verifies every single action so that belief doesn't lose its way (belief-grounded interaction); and when the agent falls into a trap anyway, it detects that and pulls the agent out (trap detection and recovery). In warehouse terms: write the ledger properly, have a meticulous manager audit it, and when the physical inventory count doesn't match, find the cause and set it right.
A PoS belief has four pieces: an estimate of the current world state, the task goal, "what we don't yet know" (the knowledge gap), and "what we haven't yet achieved" (the achievement gap). Of these, the world state is written by placing objects and actors as nodes, describing the current understanding of each in natural language, and drawing edges to show how they relate. Each entry carries a source and a confidence, and where possible the supporting evidence too.
The clever choice is that it doesn't try to map the world exhaustively. It keeps only what bears on action possibilities, outcome judgments, and goal achievement. A ledger is useful precisely when it's a summary of "what matters right now," not a floor plan of the entire warehouse.
The key design decision is splitting the two gaps apart. "Don't know" and "haven't done" call for different prescriptions. If you don't know, you need to find out more; if you haven't done it, you need to act. Lump them together and you get the confusion of "trying to execute when you should be digging for information."
A ledger may list several gaps. Treat them all as equally urgent and the agent dabbles in this and that and finishes none of them. So PoS keeps the full ledger intact but picks the single most worthwhile one to tackle right now — the active gap — and focuses there.
Meanwhile the Belief Sentinel does its work. As the name says, it's the sentry guarding the ledger — in warehouse terms, the meticulous manager who audits each newly written line for whether it's internally consistent and backed by evidence. It's this manager that catches the microwave contradiction above.
This is where the authors dig in sharply. Prior work with a similar concern usually stops right there. It prunes useless trajectories during training, or uses a mechanism that blocks actions under certain conditions to cut off unproductive information-gathering. It only cuts and halts. PoS tries to revive progress itself while the reasoning is still running. When the inventory count is off, it doesn't close the warehouse doors — it finds out why the count is off and corrects it.
First it checks the ledger's health with three signals: whether the same gap keeps going unsolved, whether progress has stalled, and whether the belief is circling the same spot.
If that were the end, it would be no different from "stopping." Here's the crux. It diagnoses the nature of the trap along two axes: how the agent is spinning, and whether the gap it's stuck on is a "don't know" gap or a "haven't done" gap. Based on that diagnosis, it pushes subsequent actions in a different direction. The same stuck state gets different prescriptions. Stuck for lack of information: "go find out more." Stuck because the work didn't get done: "change your approach and execute." The ledger design that split "don't know" from "haven't done" in the first place leads, at this very moment, to two different rescue methods.
The evaluation ran on four benchmarks. For execution — the hands-on side of carrying out tasks — they used ALFWorld and LOCA-Bench; for diagnosis — pinpointing causes — they used RCA-100 and ClinDiag. And they ran it swapping in three different foundation language models that serve as the agent's brain — call it the backbone. PoS posted the best overall performance on all four benchmarks.
Each benchmark measures with a different yardstick. ALFWorld is scored on overall success rate — whether the task was carried through to the end — while RCA-100 is scored on joint accuracy, which gives credit only when both the fault type and the root-cause entity are correct. Joint accuracy is a strict measure that awards points only when several judgments are all correct at once — in other words, one miss and you get zero. On both benchmarks PoS beat the strongest existing method. More importantly, this edge held even when the backbone was swapped out. That means it wasn't a particular model doing the work; the framework itself was.
The more interesting part of the experiments is the ablation study — a method that removes components one at a time to measure each one's contribution. Here the two axes of auditing the ledger (consistency verification) and pulling the agent out of traps (recovery) turned out to matter just as much as writing the belief explicitly. Writing the ledger alone isn't enough. It only works once auditing and rescue are there to back it up. The authors also report that existing context-management techniques don't always improve the raw trajectory — the same point that tidying the boxes alone won't do it. Robustness as the context grows was confirmed as well.
It isn't free. Writing and auditing the ledger at every step demands extra tokens and extra inference. The paper includes an analysis of the trade-off between token consumption and performance. Performance goes up, but so does cost. So "how long a task, and how expensively, is it worth maintaining a ledger for?" becomes the practical question that decides adoption. Slap per-step auditing onto work that wraps up quickly and you may spend more than you gain.
The second limit is more fundamental. The authors are blunt: "a better decision context does not substitute for execution ability or domain knowledge." The ledger is only a tool for thinking clearly — not magic that conjures up skill or domain knowledge that was never there.
Open questions remain, too. Keeping "only what matters" in the world state is efficient, but misjudge what matters and you leave out the very fact you needed. Since that selection itself leans on the language model's judgment, where the sentry misses edge cases is worth a closer look.
So how does this concept get used on the ground? Look at the everyday problems of an AI PM through the lens of the belief trap, and a fairly concrete picture emerges.
Say ONTLE's AI PM has been carrying a customer project for several weeks. One day the customer asks to "pull the deadline in by two weeks." The conversation log already runs hundreds of lines. A PM that only holds the long log has to retrace from scratch every time — reconstructing from the log which tasks are done, what's pending a decision, what has to be sacrificed to pull the deadline in. The moment that reconstruction drifts a little each time is exactly where the belief trap blooms. It asks again about scope that's already locked, touches finished work again, and gathers only material it doesn't need right now. The customer feels, "they keep working — so why isn't it done?"
ONTLE already pins project status to six types on the customer screen and shows work as a chronological flow. That's a ledger made for people to read. What PoS adds is the idea of using that same ledger not just on the human-facing screen but as the PM's decision-making material. The moment a deadline change comes in, the PM pulls out its "current belief" and writes it split apart. What it doesn't yet know: "how far the customer will compromise on quality" (knowledge gap). What it hasn't yet achieved: "rearranging the work to fit the pulled-in schedule" (achievement gap).
From here on this is our own design sketch, not a result the paper validated. ONTLE's auto_proceed gate is a mechanism that automatically decides whether to wait for a customer reply or move to the next step. We layer a PoS-style signal onto it. When the PM starts circling the same deadline item, the gate diagnoses along two axes: is the block right now because "the customer hasn't told us how far they'll compromise on quality," or because "we can't find a way to rearrange"? If the former, stop the circling and post the customer exactly one clear question. If the latter, cut off the mere gathering of more material and change the scheduling approach itself. The ledger that split "don't know" from "haven't done" splits here into two different prescriptions: "ask" and "change the method."
The cost calculation rides along with it. ONTLE uses a different model at each step. So it's realistic to lay ledger-keeping and auditing on thick at judgment-heavy steps like chat and intake, and go light on simple execution steps. A decision like a deadline change is worth auditing expensively, but there's no reason to audit the ledger every time for something like renaming a file.
A strict format can't take in facts that don't fit the mold. The situations you meet in long-horizon tasks are hard to fit entirely into predefined slots. PoS chose to write the state as a natural-language description but attach a source, confidence, and evidence alongside — keeping the flexibility while securing verifiability. In exchange, that flexibility is backed by the sentry's consistency check.
The full belief doesn't disappear; it stays intact. Focus is only a choice of "what to tackle right now" — the remaining gaps stay in the ledger. If circumstances change and another gap becomes more worthwhile, the active gap is reselected. It's a structure that finishes one thing at a time but keeps re-choosing which to do first.
Because they're different kinds of work. Execution tasks are a chain of actions that change the environment; diagnosis tasks center on reasoning that gathers evidence to pinpoint a cause. Winning on both sides is grounds that the ledger approach isn't a trick that only works on one task type.