aCAPTCHA: Verifying That an Entity Is a Capable Agent via Asymmetric Hardness

Zuyao Xu; Xiang Li; Fubin Wu; Yuqi Qiu; Lu Sun; FaSheng Miao

cs.CRMar 7, 2026

aCAPTCHA: Verifying That an Entity Is a Capable Agent via Asymmetric Hardness

Authors: Zuyao Xu, Xiang Li, Fubin Wu, Yuqi Qiu, Lu Sun, FaSheng Miao

Organizations: Nankai University · Tsinghua University

Abstract

As autonomous AI agents increasingly populate the Internet, a novel security challenge arises: "Is this entity an AI agent?" It is a new entity-type verification problem with no established solution. We formalize the problem through a three-class entity taxonomy (Human, Script, Agent) based on a verifiable agentic capability vector <x, r, s> (action, reasoning, and memory). A timing threshold t exploits the asymmetric hardness between human cognition and AI processing to separate the three classes. We define the Agentic Capability Verification Problem (ACVP) through three necessity primitives, each testing one capability dimension. Building on this foundation, we introduce aCAPTCHA (Agent CAPTCHA), a time-constrained security game for agent admission whose security rests on ACVP hardness under t. We instantiate aCAPTCHA through time-bounded natural-language understanding as a multi-round HTTP verification protocol, and evaluate it with preliminary agent trials that validate the protocol's soundness and completeness. aCAPTCHA provides a composable, infrastructure-free admission gate for any service where entity-type verification is required.

Figures & tables

Mechanism	What it verifies
OAuth / mTLS / API Key	Credential possession
WebAuthn	Channel + credential binding
DID / VC	Decentralized credential possession
CAPTCHA	Requester is human (cognitive challenge)
reCAPTCHA v3	Behavioral risk score (anomaly detection)
MAS / IoA 1	Controlled-environment participation

Table 1. What each mechanism verifies, grouped by purpose.

Dimension	Human	LLM Agent
Text ingestion	238 wpm 1 silent reading ( Brysbaert, 2019 ) ( ${\approx}$ 5 tps 3 )	Entire context window in one prefill pass ( $<$ 1 s)
Comprehension ceiling	${\leq}$ 300 wpm with full comprehension ( Carver, 1992 )	Quality independent of speed
Working memory	3–5 chunks 2 ( Cowan, 2001 )	Full context window (128 k–1 M tokens)
Choice reaction time	350–384 ms per decision ( Pashler, 1994 )	Single forward pass ( $<$ 500 ms)
Decision scaling	+150 ms/bit (Hick’s law) ( Hick, 1952 )	Constant (parallel attention) ( Vaswani et al., 2017 )
Text output	${\approx}$ 40 wpm typing ( Dhakal et al., 2018 )	50–200 tps ( ${\approx}$ 2 k–9 k wpm)

Table 2. Human cognitive limits vs. LLM-agent capabilities.

Figure 1. Projected human–LLM timing separation gap by per-round narrative length

L

Parameter	Description	Controls
$\tau_{i}$	Per-round timing budget	Human exclusion
$\alpha$	Safety margin ( $<\!1$ )	Threshold strictness
$T_{\mathrm{total}}$	Session timeout	Max session duration
$L$	Narrative length (tokens)	Separation gap
$D$	Number of domains	Domain diversity
$N$	Narrative sets per domain	Corpus size

Table 3. aCAPTCHA protocol security parameters.

Figure 2. Timing separation on aCAPTCHA challenges. Agent times are empirical; human times are simulated (§ 6.3 ).

Figure 3. Threshold sensitivity analysis. Agent curve fitted from empirical data; human curves from simulation.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

ID	Domain	FORD	Description	Entity Examples	Reasoning Patterns
biochemistry	Biochemistry	1. Natural Sci.	Enzyme kinetics, assay results, inhibitor profiles, metabolic pathways	Enzymes, compounds, metabolic intermediates, receptor subtypes	Kinetic anomaly persistence, inhibition mechanism attribution, replicate confirmation
cybersecurity	Cybersecurity	2. Eng. & Tech.	Threat intelligence, vulnerability analysis, incident response, network forensics	CVEs, IP addresses, malware families, attack vectors, threat actors	Attack attribution, false positive elimination, lateral movement tracing
clinical_trials	Clinical Trials	3. Medical	Drug efficacy, adverse events, patient cohorts, endpoint analysis	Drug candidates, adverse events, patient subgroups, biomarkers	Efficacy signal vs. confounding, adverse event attribution, subgroup analysis
food_safety	Food Safety	4. Agricultural	Contaminant screening, microbiological testing, batch traceability, regulatory compliance	Pathogens, chemical residues, food batches, testing methods, tolerance limits	Contamination source tracing, threshold exceedance attribution, cross-batch comparison
financial_markets	Financial Markets	5. Social Sci.	Macroeconomic indicators, equity indices, yield curves, credit spreads	Economic indicators, funds, currency pairs, sector indices	Sustained deviation vs. noise, trend reversal attribution, cross-market correlation

Appendix

Table 4. Challenge domains (

D{=}5

) used in the aCAPTCHA prototype, one per OECD FORD major field ( OECD, 2015 ) . Each domain defines a technical context from which narratives are generated, along with representative entities and reasoning patterns that guide the LLM generation process.

LLM Agent Verification

LLM agent verification checks whether agents’ actions, evidence, policies, and completion claims satisfy explicit requirements.

See all 147 papers

Proof-of-Agentness: Towards Verifying Agents on the Web
Oct 26, 2026Zuyao Xu, Xiang LiLLM Agent Verification Web Agents
Nankai University, Tianjin, China
CaptchaAgent: Verifiable Visual Reasoning for CAPTCHA Solving
Oct 9, 2026Shangquan Sun, Ruoyu Chen, Zhirui Liu +4CAPTCHA Solving Tool-Using Vision-Language Agents
Nanyang Technological University, Singapore. · the School of Cyber Security, University of Chinese Academy of Sciences, China. · the School of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University, No. 66, Gongchang Road, Guangming District, Shenzhen, Guangdong 518107, P.R. China. +2
aiAuthZ: Off-Host, Identity-Bound Authorization for AI Agents
Jul 6, 2026Sai Varun KodathalaAI Agent Security LLM Agent Security
Research & Development SportsVision AI Minnetonka, MN

Oct 26, 2026J/K move · Enter open · S save

Proof-of-Agentness: Towards Verifying Agents on the Web

Zuyao Xu, Xiang Li

Nankai University, Tianjin, China

LLM Agent Verification Web Agents

Open paper AskPDF arXiv

CAPTCHAs and bot detection have helped protect Web services from automated abuse for decades by distinguishing humans from bots. However, the emergence of LLM-powered agents introduces a new setting: Web services increasingly accommodate agents as legitimate users. Without a way to distinguish agents from other automated clients such as simple bots and scripts, these services risk large-scale automated junk submissions that waste service resources and consume users' attention or tokens. In this paper, we investigate a novel question for today's Web: "How can a Web service obtain evidence that a client is an agent?" We introduce the concept of "Proof-of-Agentness" (PoA), a mechanism for distinguishing agents from other automated clients, motivated by the parallel between human attention and an agent's inference resources. We outline two approaches: active verification through challenge-response and passive analysis of service-visible signals. Eight language models achieve an overall accuracy of 96.5% on our challenges, with an average overhead of 1,647 tokens. For passive analysis, we conduct an IRB-approved user study comparing the Web interactions of twelve human participants and representative Bot and Agent implementations, achieving an average classification accuracy of 95.8% across four classifiers, motivating further study.

Abstract

LLM Agent Verification

Explore similar work

Proof-of-Agentness: Towards Verifying Agents on the Web

CaptchaAgent: Verifiable Visual Reasoning for CAPTCHA Solving

aiAuthZ: Off-Host, Identity-Bound Authorization for AI Agents