🤖 AI

LedgerAgent: Structured State for Policy-Adherent Tool-Calling Agents

LedgerAgent is an inference-time method that improves policy-adherent tool-calling agents in customer-service domains by maintaining task states in a separate ledger to ensure consistent decision-making and proactively block policy violations before tool execution.

Original authors: Md Nayem Uddin, Amir Saeidi, Eduardo Blanco, Chitta Baral

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Md Nayem Uddin, Amir Saeidi, Eduardo Blanco, Chitta Baral

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a customer service agent for an airline or a retail store. Your job is to help customers cancel flights, return items, or change plans. To do this, you have a "toolbelt" of digital tools you can use to check records, update accounts, or process refunds.

The problem, according to this paper, is that standard AI agents are like amnesiacs with a very long memory. They can read the entire conversation history (the "transcript"), but they don't have a dedicated notebook to write down the important facts they just found.

Here is the breakdown of the paper's solution, LedgerAgent, using simple analogies:

The Problem: The "Lost in the Noise" Agent

In a standard setup, every time the AI checks a flight reservation or an order status, that information gets dumped into a giant, scrolling chat log.

The Analogy: Imagine trying to find a specific phone number in a stack of 500 pages of handwritten notes. You have to re-read the whole stack every time you need to decide what to do next.
The Failure: Because the AI has to "re-read" the chat log to remember facts, it often gets confused. It might:
1. Forget a crucial detail (like the flight date).
2. Act on old information (thinking a flight is still bookable when it's not).
3. Make a "technically correct" move that breaks the rules (like trying to refund a payment method that doesn't exist) because it didn't double-check the current facts against the policy.

The Solution: The "Ledger" and the "Bouncer"

The authors created LedgerAgent, which adds two simple but powerful features to the AI's workflow.

1. The Ledger (The Organized Notebook)

Instead of just letting facts float around in the chat log, the AI now has a structured ledger.

How it works: Every time the AI successfully uses a tool to read data (like "Get Flight Details"), it doesn't just leave that data in the chat. It immediately copies the key facts into a clean, organized "notebook" (a typed dictionary).
The Metaphor: Think of the chat log as a messy kitchen counter where ingredients are scattered everywhere. The Ledger is a labeled spice rack. When the AI needs to know the price of a flight, it doesn't dig through the messy counter; it just looks at the "Flight Price" jar on the rack.
The Benefit: The AI always knows exactly what it knows, without having to guess or search through old text.

2. The Policy Gate (The Bouncer)

Before the AI is allowed to make a change to the real world (like canceling a flight or issuing a refund), it has to pass through a Policy Gate.

How it works: This gate is a strict rule-checker. It looks at the AI's proposed action and compares it against the facts in the Ledger and the company's rules.
The Metaphor: Imagine a bouncer at a club. The AI (the guest) says, "I want to cancel this flight." The bouncer (the gate) checks the Ledger (the guest list) and the Rulebook (the policy).
- Scenario: The rule says, "You can only cancel within 24 hours." The Ledger shows the flight was booked 48 hours ago.
- Result: The bouncer stops the AI. "No entry. You are violating the 24-hour rule." The AI then tells the customer, "I'm sorry, I can't do that," instead of blindly trying to cancel it and failing.

Why This Matters

The paper tested this system across four different customer service worlds: Airlines, Retail, Telecom, and Telehealth. They used various AI models (both open-source and big commercial ones).

The Results: LedgerAgent was much better at getting tasks right, especially when the task required changing something in the real world (like a refund or a cancellation).
Consistency: The biggest win was consistency. If you asked the standard AI to do the same task 4 times, it might succeed once and fail three times because it got confused by its own chat history. LedgerAgent succeeded much more consistently across all 4 tries.
No Extra Cost: Unlike other methods that try to make the AI "smarter" by training it on more data or using multiple AI brains, LedgerAgent doesn't change the AI's brain at all. It just gives it a better way to organize its notes and a bouncer to check its work.

Summary

LedgerAgent is like giving a chaotic, forgetful assistant a structured filing cabinet (the Ledger) and a strict supervisor (the Policy Gate).

The Filing Cabinet ensures the assistant always knows the current facts without digging through old emails.
The Supervisor ensures the assistant never tries to break the rules before actually doing the action.

The paper claims this simple change makes AI agents much more reliable, accurate, and polite when handling complex customer service tasks.

Technical Summary: LedgerAgent: Structured State for Policy-Adherent Tool-Calling Agents

Problem Statement

In customer-service domains, language agents must maintain task states across multiple turns while interacting with users, retrieving records, and executing tools. These agents are required to adhere to strict domain policies (e.g., refund eligibility, cancellation windows) that depend on the current state of the interaction.

Standard tool-calling agents rely on a prompt-only design, where observations, tool returns, and policy instructions are interleaved in a growing conversation transcript. This design creates two primary failure modes:

Implicit State Grounding: Agents must reconstruct relevant facts from the raw transcript each time they decide on an action. This leads to decisions based on stale, missing, or incorrectly reconstructed information, even if the correct records were previously retrieved.
Policy Boundary Violations: Agents may generate syntactically valid tool calls that violate domain policies because the policy check is not decoupled from the current state. For instance, an agent might attempt to cancel a reservation outside the allowed window because it failed to cross-reference the current date with the reservation date stored in the history.

Existing solutions often focus on improving the model itself (via fine-tuning or reinforcement learning) or adding inference-time scaffolding (planning/reflection). However, these approaches largely preserve the implicit nature of state representation within the prompt, leaving the agent to recover state from an unstructured transcript.

Methodology: LedgerAgent

The authors introduce LedgerAgent, an inference-time method that decouples state management from the raw prompt history. It introduces two deterministic components that operate without modifying model weights or requiring additional LLM calls for state construction:

1. Schema-Anchored Ledger

The agent maintains a separate, typed dictionary (the ledger) that stores observed task states.

Mechanism: When a read-tool returns successfully, the return value is parsed and projected into the ledger based on a pre-defined, domain-specific tool path map (e.g., orders.1234, reservations.UX789).
Properties: The ledger is a compact, typed representation of observed facts, identifiers, and conditions. It is not a summary or long-term memory but a structured view of the external system state as observed by the agent.
Update Rule: The ledger updates only from successful read-tool returns. Write-tool returns do not update the ledger; the agent must issue a subsequent read call to observe the new state, ensuring the ledger remains grounded in the external system.
Integration: Before each model generation, the full ledger is deterministically rendered and injected into the prompt. This allows the model to look up current state via stable paths rather than searching the transcript history.

2. Policy Gate

A policy gate operates immediately before any environment-changing tool call (e.g., refunds, cancellations, updates) is executed.

Function: The gate evaluates the proposed tool call against a set of executable predicates ( $\Pi$ ) defined over the current ledger fields.
Outcomes:
- ALLOW: The call is consistent with the ledger and policy; it proceeds unchanged.
- REVISE: The call violates a policy (e.g., missing evidence). The call is removed, and the model receives feedback identifying the violated predicate.
- BLOCK: The call is explicitly forbidden (e.g., attempting a policy-violating action). The action is refused, and the agent is prevented from changing the environment.
Implementation: Policies are encoded as code predicates over ledger fields (e.g., checking if a flight date is within 24 hours of the current time), rather than relying on natural language reasoning within the prompt.

Agent Loop

The method wraps the standard agent loop. It absorbs tool returns into the ledger, renders the ledger into the prompt, generates a response, and filters environment-changing calls through the policy gate. Crucially, this adds zero additional LLM calls to the inference process; the overhead is limited to deterministic string formatting and predicate evaluation.

Key Contributions

Identification of State Grounding as a Failure Mode: The paper identifies that agents often fail not because they cannot retrieve records, but because they act on stale or incorrectly reconstructed state when that state remains implicit in the prompt.
LedgerAgent Framework: A novel inference-time method that separates state representation (via a typed ledger) from action execution (via a policy gate), ensuring state-dependent policies are checked against observed evidence before environment changes occur.
Empirical Validation: Demonstration that LedgerAgent improves consistency-oriented metrics ( $pass^k$ ) across diverse customer-service domains and backbone models without altering model weights.

Experimental Results

The authors evaluated LedgerAgent across four domains (Airline, Retail, Telecom, Telehealth) using a mix of open- and closed-weight models (including GPT-4.1, GPT-5.2, Kimi K2.5, GLM-5, MiniMax M2.5, and Qwen3).

Performance Gains: LedgerAgent consistently improved average $pass^1$ $p a s s^{1}$ and $pass^4$ $p a s s^{4}$ scores over standard function-calling baselines.
- On non-GPT backbones (e.g., Kimi-K2.5), average $pass^1$ improved by 3.4 points and $pass^4$ by 5.6 points.
- On GPT backbones, improvements were even more pronounced, with average $pass^1$ gains of 12.2 (GPT-4.1) and 15.5 (GPT-5.2) points.
Consistency: The largest gains were observed in $pass^4$ (consistency across four independent trials), indicating that LedgerAgent significantly reduces variance in agent behavior.
Environment-Changing Tasks: The method showed particular strength in tasks requiring write actions (e.g., cancellations, refunds), where preventing policy violations is critical. In the Telecom domain (dual-control setting), LedgerAgent substantially increased action-level reliability.
Efficiency: Unlike context-engineering methods like IRMA (which use helper agents and incur >50% token overhead), LedgerAgent achieved higher performance with 0.0% token overhead relative to the baseline, as it does not add extra LLM calls.

Error Analysis

Analysis of failed trajectories revealed that the remaining errors in LedgerAgent are primarily:

Missed Required Actions (70.3%): The agent completes initial lookups but fails to execute subsequent necessary steps (e.g., transferring to human support prematurely instead of attempting a valid partial fulfillment).
Wrong Action Arguments (20.4%): Errors in extracting or formatting arguments, particularly in domains with complex schemas like Telehealth.
Domain Specificity: Failures vary by domain (e.g., Telecom failures are almost exclusively missed actions; Telehealth has higher argument error rates), suggesting that while the ledger solves state grounding, domain-specific planning and schema awareness remain challenges.

Significance and Claims

The paper claims that LedgerAgent addresses a fundamental architectural gap in tool-calling agents: the reliance on implicit state within a growing prompt. By making observed state explicit and checking actions against a structured ledger before execution, the method:

Shifts the failure boundary from post-hoc correction (fixing errors after they happen) to prevention (blocking policy violations before they occur).
Provides a system-level mechanism for policy adherence that complements the model's reasoning capabilities without requiring retraining or complex multi-agent orchestration.
Demonstrates that state representation is as critical as model capability for reliable tool use in dynamic, policy-constrained environments.

The authors conclude that while LedgerAgent does not replace the need for planning or robust argument construction, it effectively eliminates a major source of unreliability: acting on stale or ungrounded state. The approach is most effective in structured tool-use domains where state can be mapped to a schema and policies can be encoded as executable predicates.