R041 · Agent principles and patterns › Formal constraints on agent actions

Agent-C: temporal constraints enforced at decode time

Read the original

constrained-decodingformal-verificationagent-governanceagent-reliabilityinference-costbenchmarks

Kamath, Zhang, Xu, Ugare, Singh and Misailovic (UIUC, with Meta), arXiv 2512.23738; code at structuredllm/agent-c.

Agent-C makes ordering and state policies hard constraints on tool calls, and does it cheaper than retrying. Policies like "authenticate before reading data" are written in a small DSL (Before, After, Forall, Exists, Seq, plus developer-written projection functions that read tool state). The DSL compiles to first-order logic; the trace so far plus the proposed call is checked with Z3.

Mechanism. With open weights, the tool call is generated under a tool-call grammar. On a violation the decoder backtracks to the last compliant argument boundary and resamples, so it never pays for a whole new turn. Closed APIs get a reprompting variant that resamples whole calls. If the iteration budget runs out, the agent emits an explicit error tool instead of acting.

Results. On tau-bench retail and airline, plus 17 adversarial variants of each written by the authors:

Why it matters for efficiency. Enforcing inside decoding turns a rejected action from a full round trip into a partial resample. The utility gain says hard constraints also stop the agent from wandering into states it then has to recover from.

Caveats. Z3 and the projection functions are trusted, and someone must write them. Specs cannot refer to future states. Three trials only; the adversarial set is the authors' own. One utility figure in the body (80.5% for Sonnet) differs from the abstract's 75.2%, probably a different setting.

Connections

See R041 on the knowledge map

Part of the Research notes on nowucca.com. Figures and claims are the source's own unless the summary says otherwise.