The Capability–Availability Mismatch: Three-State Tool Semantics and Forced-Halt Conditions in LLM Agent Protocols

In the paper's words

Agent protocols written for large language models (LLMs) typically assume a binary world: a tool is either available to the agent or it is not. Real deployments exhibit a third state: the capability exists in the toolset but is contextually disabled by policy, budget, or routing. We formalize this capability–availability mismatch.

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

What it claims

PCH is undecidable over the class of arbitrary protocols Π.

Numbers it reports

1. Retrieval-augmented search agents exhibit the mirror-image pathology: a 3B Self-Ask agent runs to its search budget on 78–88% of questions instead of halting on its own [3].

   from 1. Introduction

2. InverseNet benchmarks operator mismatch in compressive imaging: when the assumed forward operator deviates from physical reality in eight parameters, EfficientSCI loses 20.58 dB; under mismatched operators all methods converge to 20.40–21.88 dB on CASSI, erasing the roughly 10 dB ideal-condition advantage of deep learning over classical methods; CACTI suffers degradations up to 20.6 dB; and mask-oblivious architectures such as HDNet show zero oracle recovery ($\Delta_{\text{rec}}=0.00$ dB) while operator-aware ones such as PnP-HSICNN recover with ratio $\rho=56.8\%$ [6].

   from 2. Background and Related Work

3. High-concurrency LLM serving is bottlenecked by KV cache memory overhead, and structural changes are what move concurrency: an adaptive GQA-to-MLA transition limits Llama3-8B perplexity degradation from 6.1 to 12.9 versus 25.8 for the baseline, a 65% reduction in degradation [2].

   from 2. Background and Related Work

4. The mismatch is structurally analogous to operator mismatch in computational imaging, where a reconstruction pipeline that assumes a forward operator differing from physical reality in eight parameters loses 20.58 dB [6]: in both cases the deployed artifact is evaluated against a state model that the environment does not honor.

   from 1. Introduction

5. With gold claims on a Self-Ask 3B agent, HALT reduces loop counts by 37% on 2Wiki, 45% on HotpotQA, and 20% on MuSiQue, with exact-match changes between $-0.9$ and $+1.5$ percentage points; the HotpotQA non-inferiority test fails with a 95% CI of $[-2.6,+0.8]$ pp crossing the $-2$ pp margin, and under open-corpus retrieval shift the fire rate drops from 67.6% to 6.4% on HotpotQA and to 2.4% on Bamboogle [3].

   from 2. Background and Related Work

6. The Halt Vector work internalizes a causal stopping direction at layer 18 into the weights, yielding a per-problem self-halt trained from 24 problems that removes about 24% of thinking at held accuracy; notably, outcome-level length penalties only trim the longest tails and do not move the internal answerable point, and the stop-and-commit tokens are about 0.34% of the token loss, so plain fine-tuning leaves length unchanged [4].

   from 2. Background and Related Work

How it is done

1. Tool state is modeled as a pair (capability, per-context permission), protocol compliance is defined as a predicate over these states, and we ask which protocol designs remain well-defined when the third state occurs.

   from Abstract

2. The agent now sits in a catch-22 constructed entirely by the protocol's wording: if it honestly self-assesses, it concludes the tool is "not available," and the mandate-plus-prohibition pair forces it to halt a task it could in principle execute; if it proceeds, it either fabricates a "live" fetch (violating the prohibition) or claims compliance it cannot verify.

   from 1. Introduction

3. The classical analogue (a stochastic-matrix version of the same question) is decidable, so the gap between the modeled dynamics and the richer dynamics is exactly what introduces undecidability; and mild restrictions, such as trace-preserving channels bounded via the quantum Wielandt theorem, restore efficient decidability.

   from 2. Background and Related Work

4. For a tool $t$ and context $c$ we define two independent bits: $\mathrm{Cap}(t) \in \{0,1\}$: the tool is present in the agent's toolset and the calling path is functional.

   from 3.1 Three-state tool semantics

What would falsify it

1. Platform engineers who disable tools per tenant or per budget envelope must predict agent behavior after the switch, and currently cannot, because the agent's decision procedure was never specified for that state.

   from 1. Introduction

2. A design rule for agent instruction languages — explicit disabled-state signaling plus three-state compliance predicates — and the smallest experiment that would falsify or de-risk it (Sections 5 and 7).

   from 1. Introduction

3. What would falsify the main result.

   from 6. Discussion

Where the claim stops

1. What the results do and do not claim.

   from 6. Discussion

2. R1 is exact arithmetic given the three-state semantics; its only assumption is that the three states are the right state model, which is an empirical question about real platforms.

   from 6. Discussion

3. R3 and R4 are projections resting on assumed rates; R2 is a formal result whose scope is bounded by its modeling choices.

   from 6. Discussion

Where to read

1. Abstract240 words · 1 min
2. 1. Introduction802 words · 3 min
3. 2. Background and Related Work990 words · 4 min
4. 3. Methods910 words · 4 min
5. 4. Analysis1,029 words · 4 min
6. 5. Results337 words · 1 min
7. 6. Discussion745 words · 3 min
8. 7. Practical Implications and Engineering Pathways671 words · 3 min
9. 8. Conclusion210 words · 1 min
10. Provenance and AI Involvement225 words · 1 min