Why strict AI rules can make agents freeze up

In the paper's words

Agent protocols written for large language model (LLM) agents increasingly mandate live tool execution and forbid simulated or placeholder actions outright. Such zero-tolerance semantics can create a specification-level deadlock: the agent recognizes that the required capability exists in its action space, but the protocol provides no representation for the case in which that capability is present yet its invocation is blocked in the current context, so the agent classifies every candidate action as a forbidden simulation and halts. This paper formalizes that failure mode.

The abstract, verbatim; every line below is quoted from the text.

What it claims

$D = (1,1,0)$ is reachable from an admissible initial state.

Numbers it reports

1. An exact combinatorial result: a binary-state protocol over $k$ gated tools covers $(2/3)^{k}$ of the three-state configuration space, computed as $32/243 \approx 0.132$ at $k=5$ and a $59049/1024 \approx 57.7$ state-space ratio at $k=10$ (Section 4).

   from 1. Introduction

2. Verification discipline and epistemic failure. [10] argues that the transition from static LLMs to autonomous agents introduces epistemic failure modes driven by an "Orchestration Penalty" — a factorial increase in verification complexity across multi-step reasoning loops — and that safety is an engineering discipline of managing latency, entropy, and feedback.

   from 2. Background and Related Work

3. This is an upper bound on the deadlock rate itself: a deadlock occurs only if the agent's protocol lacks the middle state (the zero-tolerance condition of Section 3.3) and the blocked invocation is one the task actually requires ($r=1$, $c=1$).

   from 4.5 Per-task deadlock probability (projection)

4. We treat $p_{\mathrm{task}} = 0.40951$ as the exposure rate and note that the realized deadlock rate is $p_{\mathrm{task}}$ multiplied by the fraction of blocked invocations that are required-and-capable, a factor no source in this analysis quantifies.

   from 4.5 Per-task deadlock probability (projection)

5. Computed values: $f(5) = 32/243 \approx 0.132$, with $211/243 \approx 0.868$ of configurations containing at least one tool in the unspecified third state; at $k=10$ the state-space ratio is $3^{10}/2^{10} = 59049/1024 \approx 57.7$, with $58025$ of $59049$ configurations containing at least one blocked-invocation tool.

   from 5. Results

6. The projection assumes blocking events are independent across invocations within a task; correlated blocking (one tenant switch gating many tools) raises the joint probability above $1-(1-q)^{n}$, so $0.40951$ is a lower bound under positive correlation.

   from 6. Discussion

How it is done

1. Such zero-tolerance semantics can create a specification-level deadlock: the agent recognizes that the required capability exists in its action space, but the protocol provides no representation for the case in which that capability is present yet its invocation is blocked in the current context, so the agent classifies every candidate action as a forbidden simulation and halts.

   from Abstract

2. Teams deploying LLM agents in production write protocol instructions of two common kinds: "use the live tool when the task requires it" and "never simulate, fabricate, or placeholder tool output." The first instruction demands capability use; the second, taken alone, is sound engineering, because fabricated tool output is a well-known reliability and audit hazard.

   from 1. Introduction

3. The formal substrate for this paper is the state transition system (STS) model that underlies much agent-communication-protocol work. [1] defines a State Transition System as a tuple $(S, s_{0}, L, T, F)$, where $S$ is a finite set of states, $s_{0} \in S$ is the initial state, $L$ is a finite set of labels, $T \subseteq S \times L \times S$ is a set of transitions, and $F \subseteq S$ is a set of final states; the same definition, with transitions labeled by communication-act classes from the CommOnt ontology, appears in [2].

   from 2. Background and Related Work

4. This paper is a formal analysis: we define a state machine, prove two properties of it, and compute exact combinatorial quantities and labeled projections.

   from 3.1 Modeling approach

What would falsify it

1. What would change if the analysis in this paper holds: protocol authors could add a single explicit middle state ("capability available, invocation not required in this context") and eliminate the halt class by construction; operators could predict which tool-availability configurations deadlock before deployment; and diagnostic effort could shift from model improvement to specification repair.

   from 1. Introduction

2. A repair pathway: a three-state protocol extension that removes the halt class by construction, and the smallest experiment that would confirm or refute the reachability prediction (Section 7).

   from 1. Introduction

3. No experiment, measurement, or simulation on hardware was performed; the empirical study that would test the reachability prediction is specified as a proposal in Section 7.

   from 3.1 Modeling approach

Where the claim stops

1. What the results do and do not claim.

   from 6. Discussion

2. R1 and R2 are exact given the modeling choices; R3 is a formal result whose scope is bounded by its reduction sketch; R4 is a projection resting on assumed rates.

   from 6. Discussion

3. The reachability proof assumes the context can flip $i$ from $1$ to $0$ while $r$ and $c$ stay fixed.

   from 6. Discussion

Where to read

1. Abstract247 words · 1 min
2. 1. Introduction618 words · 3 min
3. 2. Background and Related Work1,430 words · 6 min
4. 3. Methods669 words · 3 min
5. 4. Analysis1,338 words · 6 min
6. 5. Results290 words · 1 min
7. 6. Discussion630 words · 3 min
8. 7. Practical Implications and Engineering Pathways644 words · 3 min
9. 8. Conclusion190 words · 1 min
10. Provenance and AI Involvement240 words · 1 min