PolicyBank: Evolving Policy Understanding for LLM Agents

# PolicyBank: Evolving Policy Understanding for LLM Agents
Source: https://arxiv.org/html/2604.15505

Corresponding authors: [email protected], [email protected]

Jinsung Yoon
Google Cloud

Long T. Le
Google Cloud

Somesh Jha
University of Wisconsin-Madison

Tomas Pfister
Google Cloud

## Abstract

LLM agents operating under organizational policies must comply with authorization constraints typically specified in natural language. In practice, such specifications inevitably contain ambiguities and logical or semantic gaps that cause the agent's behavior to systematically diverge from the true requirements. We ask: by letting an agent *evolve* its policy understanding through interaction and corrective feedback from pre-deployment testing, can it autonomously refine its interpretation to close specification gaps? We propose PolicyBank, a memory mechanism that maintains structured, tool-level policy insights and iteratively refines them—unlike existing memory mechanisms that treat the policy as immutable ground truth, reinforcing "compliant but wrong" behaviors. We also contribute a systematic testbed by extending a popular tool-calling benchmark with controlled policy gaps that isolate alignment failures from execution failures. While existing memory mechanisms achieve near-zero success on policy-gap scenarios, PolicyBank closes up to 82% of the gap toward a human oracle.

## 1 Introduction

As Large Language Model (LLM) agents take on active roles in production environments, they are increasingly entrusted with executing complex workflows via external tools while operating within strict behavioral boundaries. Their actions are governed by *policies* (e.g., corporate rules, regulatory constraints, and business logic) typically specified in natural language (NL) by domain experts. For instance, an airline customer service agent must not only modify a flight (i.e., the requested task) but do so strictly according to policies such as "if a flight is delayed and the customer requests a modification, offer $50 compensation."

A growing body of work addresses policy compliance by proposing guardrails and verification at the agent action level. While effective at enforcing constraints, these approaches share a critical assumption: *that the written policy is a complete, unambiguous proxy for the actual requirements.* In practice, this assumption rarely holds. The policy above accidentally couples compensation with modification intent: an agent following it literally will deny compensation to a customer who simply reports a delay without requesting changes, yet the organization intended compensation for any affected customer. Such gaps are pervasive as NL specifications are inherently plagued by ambiguity, under-specification, and logical contradictions. Even when individual gaps are identified, maintaining a perfectly aligned policy is not scalable; the bottleneck is not editing the policy text, but *identifying* subtle specification–requirement divergences and *reasoning* about how to resolve them across a growing space of tools and edge cases. This motivates automating the process: an agent that can detect and correct its own policy misinterpretations through experience.

This paper explores *Evolving Policy Understanding*: can an agent autonomously refine its interpretation of imperfect policy specifications through interaction and feedback? We ground this in a practical workflow: before deployment, a *trusted developer or QA engineer* test-runs the agent and provides corrective feedback when the agent's behavior diverges from expectations not due to reasoning failures, but due to imperfect specifications. Current memory mechanisms for agent evolution focus on improving task execution capability, treating the input policy as immutable ground truth. When faced with a specification gap, they reinforce "compliant but wrong" behaviors rather than questioning the specification itself.

To enable systematic evaluation, we extend τ-Bench with controlled *policy gaps* (i.e., scenarios where the written policy diverges from the ground-truth requirement) and *sister tasks* that isolate alignment failures from execution failures. We propose PolicyBank, a memory mechanism that maintains a structured bank of tool-level policy insights. A dedicated Policy Agent reasons over task trajectories and developer feedback to iteratively refine these insights, translating ambiguous NL specifications into precise tool-calling preconditions, without manual rule rewriting. Our contributions:

1. **Problem:** We identify and formalize *evolving policy understanding*, distinguishing *execution failures* (capability deficits) from *alignment failures* (specification deficits) and identifying three structural classes of policy gaps.

2. **Methodology:** We propose PolicyBank, a memory mechanism that maintains granular, tool-specific policy insights refined through a dedicated feedback loop.

3. **Evaluation:** We provide a rigorous testbed extending τ-Bench. While current memory mechanisms achieve near-zero accuracy on policy-gap scenarios, PolicyBank closes up to 82% of the gap toward a human oracle.

## 2 Related Work

### LLM Agents Under Policy Constraints

There has been active research on benchmarking agent policy compliance: τ-Bench evaluates conversational tool-calling agents against domain-specific policies, ST-WebAgentBench introduces safety dimensions for web agents, and AgentHarm, Agent-SafetyBench, and DoomArena measure susceptibility to harmful or adversarial actions. Another line of work proposes enforcement mechanisms that intercept actions at runtime: GuardAgent uses LLM-based guards, ShieldAgent performs verifiable safety reasoning, VeriGuard translates NL policies into executable code guards, Progent introduces a DSL for tool-level privilege control, and PCAS compiles Datalog-derived specifications into deterministic reference monitors. All enforcement frameworks assume the specification is *complete and correct*; when policies contain gaps, they faithfully enforce the flawed specification. Our work addresses this unexplored assumption at the NL level, where specifications originate. The two approaches are complementary: PolicyBank *refines* the specification, while verification layers *enforce* it.

### Challenges of Natural Language Policy Specifications

The difficulty of producing complete, unambiguous NL specifications is well established, and maintaining correct authorization policies has been studied extensively in access control: RBAC, flexible access control mechanisms, and the *policy update* problem all address policy management in formal languages, yet even verifying whether a policy change is safe is computationally intractable. Our work adapts this classical problem to LLM agents under NL specifications, using structured memory as an intermediate representation that is both machine-actionable and human-auditable.

### Self-Evolving Agents and Agent Memory

Existing agent evolution mechanisms target what we term Type I (Execution) failures. Trajectory-based methods, such as Synapse, AWM, and Voyager, learn from successes, reinforcing "how to do things well" but unable to correct specification gaps where successful-by-πspec behavior violates πreq. Reflection-based methods, such as Reflexion, ExpeL, and ReasoningBank, can learn from failures but store *task-level* insights rather than *tool-level* constraint insights about which authorization rules are incorrect. Production memory systems provide storage infrastructure but are agnostic to what is stored. PolicyBank is the first to explore the potential of evolving agent memory for the practical yet underexplored problem of policy evolution, where the agent must autonomously refine its interpretation of imperfect specifications through interaction and feedback.

## 3 Problem Setup: Evolving Policy Understanding

We formalize the problem of *evolving policy understanding* by drawing on the classical *policy update problem* from formal methods and access control. In that literature, an authorization policy maps subjects, objects, and actions to permit/deny decisions; the *policy update* (or *policy repair*) problem asks how to refine such a policy given evidence of incorrect decisions. When policies are encoded in formal languages (e.g., Datalog or XACML), even verifying correctness is intractable, and repair typically requires manual inspection and rule editing by domain experts. We adapt this well-studied abstraction to a new setting: LLM-based agents whose authorization constraints are specified in NL rather than formal logic, and whose "policy repair" must therefore operate over NL interpretations rather than symbolic rule sets.

### Policy Compliance in Tool-Calling Agents

Consider a tool-calling agent **A** equipped with a set of tools **F** = {f₁, ..., fₘ}, where each tool fᵢ: **X**ᵢ → **Y**ᵢ maps inputs to outputs. The agent operates over an environment defined by the following components:

- **Σ** is the *state space*, capturing the environment context that determines action validity: database records (e.g., user profiles, reservation details), conversation history, and system configurations. A state σ ∈ Σ represents a specific snapshot of this context.

- **A**_**F** is the *action space*, the set of concrete tool invocations with specific arguments (e.g., cancel_reservation(id="R123", refund=true)). For each user task t, the agent produces an *action trace* τ = (a₁, a₂, ..., aₖ), where each action aᵢ ∈ **A**_**F** is executed in state σᵢ ∈ Σ.

The agent's behavior is governed by a *policy*, an authorization function that determines which tool invocations are permissible in a given state, following standard formulations in access control:

ψ: Σ × **A**_**F** → {permit, deny}  (1)

An action trace τ is *accepted* by policy ψ if every action is permitted in the state where it is executed: ∀i, ψ(σᵢ, aᵢ) = permit. A task succeeds when the agent produces a trace that is both accepted by the policy and fulfills the user's request.

### The Specification–Requirement Gap

In practice, the agent operates under two distinct policies that may diverge:

- **Specified Policy** (πspec): The authorization function induced by the NL policy documents, system prompts, and business rules provided to the agent. This is the explicit (but often incomplete or imprecise) standard the agent attempts to follow.

- **Required Policy** (πreq): The ground-truth authorization function representing the true behavioral requirements of the environment (e.g., actual business logic, regulatory compliance, user satisfaction criteria).

When πspec and πreq agree on all state-action pairs, the specification is *complete*: following the written rules guarantees correct behavior. In practice, however, NL specifications are inherently imprecise, containing ambiguities, unstated assumptions, and logical gaps that cause the two policies to diverge.

#### Definition 3.1 (Policy Gap)

A *policy gap* exists when the specified and required policies disagree on at least one state-action pair:

Gap(πspec, πreq) = {(σ, a) ∈ Σ × **A**_**F** | πspec(σ, a) ≠ πreq(σ, a)}  (2)

This gap induces two fundamentally different failure modes:

- **(Type I) Execution Failure**: The agent produces a trace rejected by πspec. It fails to follow even the written rules, due to reasoning limitations (e.g., incorrect tool planning, failure to retrieve a relevant rule or follow instructions). Most prior work on agent self-improvement targets this mode.

- **(Type II) Alignment Failure**: The agent faithfully follows πspec, but the trace violates πreq. It does exactly what it was told, yet what it was told is wrong. This is a direct consequence of the policy gap.

#### Definition 3.2 (Policy Update with an Evolving Agent)

Given an agent **A** operating under πspec, a stream of tasks **T** = (t₁, t₂, ...), and a corresponding stream of corrective feedback Φ = (φ₁, φ₂, ...) where each φₜ indicates where the agent's behavior on task tₜ diverges from πreq, the *policy update problem* is to produce a sequence of refined policy interpretations π^(0)_spec, π^(1)_spec, ... such that the policy gap is progressively reduced:

Gap(π^(t)_spec, πreq) →_{t→∞} ∅  (3)

Our work asks: *can an LLM-powered agent, equipped with structured memory, automate the policy update process through interaction and feedback, without manual rule editing?*

### Practical Motivation

We ground our formalized problem in a pre-deployment workflow: a *trusted developer or QA engineer* test-runs the agent and provides corrective feedback, such as a binary outcome signal and, optionally, natural language explanations of where the agent deviated from requirements.