LEGIT: Credentialing Protocol for Trustworthy AI Agent Marketplaces

Steve Drew; Jiayu Zhou

cs.AISep 18, 2026

LEGIT: Credentialing Protocol for Trustworthy AI Agent Marketplaces

Authors: Steve Drew, Jiayu Zhou

Organizations: University of Calgary · University of Michigan

Abstract

Agentic marketplaces are emerging where AI agents with varying capabilities autonomously complete specialized tasks for buyers. A major challenge of such marketplaces is that buyers cannot easily determine which agent will perform best on their tasks. Reported benchmark scores may be difficult to verify or compare across tasks, software, and budgets. We introduce LEGIT, a credentialing protocol connecting certification, reputation, and proposed marketplace allocation. Certification binds measured quality and cost per solved task to an agent configuration, task domain, evaluation budget, and evidence through a signed record. Reputation links records of past task outcomes to the same identity, subject to the reliability of the reported feedback. Buyers and agents can verify credential records and inspect optional visual profiles. Evaluations reveal cost differences between agent configurations with similar observed task success, and show that comparisons depend on the evaluation budget. These results support binding performance measurements to the tested configuration and resource limits. A complementary analysis quantifies the deposits and fees required for reputation manipulation under a stated Sybil attack model.

Figures & tables

Panel of Figure 1 — Figure 1: Example views of structured agent credentials. Left, normalized profiles compare quality, efficiency, and budget sensitivity. Right, a card displays measured gpt-5.6-luna baseline scores with illustrative signature and expiry fields. The visual verification mark is not itself a verification result. Section 5.3 defines the axes and fields.

Figure 2: The LEGIT architecture connects certification, reputation records, and marketplace allocation. Credentials carry measured quality and cost into reputation tracking, task allocation, and payment.

Model	Harness	Solved	Success rate	Total tokens	Over budget
gpt-5.6-luna	Baseline	38	29.9%	304,138	0
gpt-5.6-luna	Web search	48	37.8%	3,121,745	68
gpt-5.6-sol	Baseline	54	42.5%	321,980	0
gpt-5.6-sol	Web search	52	40.9%	3,184,671	70
gpt-5.6-sol	Reflective retry	53	41.7%	507,747	0

Table 1: Model and harness performance on 127 GAIA tasks at

B=16{,}000

tokens. Over-budget tasks receive zero credit. Success rates use all 127 tasks.

Panel of Figure 3 — Figure 3: Quality across budgets and harnesses. Panel (a) applies lower token thresholds to saved 16,000-token runs. Panel (b) compares harnesses at 8,000 tokens. Shaded strips show baseline mean plus or minus one SD across five runs. Model colors match across panels.

Model	Harness	Solved	Median tokens	Over budget
luna	No tools	37	2,702	0
luna	Bounded search	57	11,240	36
sol	No tools	56	2,612	0
sol	Bounded search	63	12,760	37
Search quality contrast		$\hat{\kappa}$	95% CI	$p$
luna , bounded over no tools		1.54	$[1.21,2.10]$	0.007

Table 2: Retrieval at

B=16{,}000

on 127 GAIA tasks. Bounded search allows at most two tool calls per task. Baselines are fresh evaluations for this comparison.

Harness	Direct	Reconstructed	Difference
Baseline	40	39	$+1$
ReAct	34	36	$-2$
Plan-then-execute	30	27	$+3$
Reflective retry	32	31	$+1$

Table 3: Direct evaluation at

B=4{,}000

against truncation from

B=8{,}000

for gpt-5.6-luna . Values are solved counts out of 127 tasks.

Model	Harness	Solved	Cost per solved task	Median tokens
haiku	baseline	19	0.0143	425
haiku	ReAct	10	0.0311	495
haiku	plan-execute	15	0.0326	1,117
haiku	reflective retry	12	0.0706	2,191
luna	baseline	43	0.0086	2,256
luna	ReAct	39	0.0096	2,220

Table 4: Model and harness factorial grid on the shared 127-task pool at

B=8{,}000

tokens, with a descriptive variance decomposition on per-task scores at the right. Over-budget items are scored zero by the same-budget rule. The models are claude-haiku-4-5 , gpt-5.6-luna , and gpt-5.6-sol . Cost per solved task is in US dollars, and the haiku figure uses that model’s own prices.

Contrast	$\hat{\kappa}$	95% CI
sol over luna	1.28	$[1.09,1.55]$
luna over haiku	2.26	$[1.64,3.55]$
sol over haiku	2.90	$[2.04,4.69]$
sol notes over baseline	0.84	$[0.70,0.96]$
Six-harness analysis	$F$	Result
Model	101.4	Descriptive

Table 5: Quality contrasts and the extended six-harness analysis on GAIA at

B=8{,}000

. Model contrasts use the baseline harness.

Panel of Figure 4 — Figure 4: The left panel compares each harness’s cost per solved task with the same model’s baseline on GAIA. Model colors match Figure 3 , right panel. The dashed line marks equal cost. The right panel shows reflective retry’s extra cost on both task domains. Extra cost occurs everywhere and is largest on the weakest model.

Panel of Figure 5 — Figure 5: Quality and cost per solved task for all eighteen configurations at $B=8{,}000$ . The dashed line joins the Pareto frontier. It contains luna baseline, sol ReAct, and sol reflective retry at very different trade-offs. Every other configuration is dominated. A quality-only ranking would hide the entire horizontal axis.

Panel of Figure 6 — Figure 6: Task outcomes underlying the grid statistics. Each row represents a configuration. Each cell represents a task in the shared pool and is filled when that configuration solves it under the same-budget rule. The left side contains easy tasks shared across configurations. The middle band contains tasks solved by some models but not others. The right side contains unsolved tasks. Rows differ far less within a model than across models.

Table 12

$\rho_{\text{target}}$	$\eta=0.80$	$\eta=0.90$	$\eta=0.95$
0.70	2	2	2
0.80	3	3	3
0.90	5	6	7
0.95	7	10	13
0.99	14	23	35

Table 8: Capital and fees required to accumulate reputation for a Sybil identity. The left panel gives the perfect-feedback interactions

n_{\text{rep}}

needed to raise a fresh identity from

\rho_{0}=0.5

\rho_{\text{target}}

, from direct iteration of the discounted Beta update. The right panel gives deposit plus spent fees per identity at

\eta=0.9

in USD. The sum is

s_{\min}+n_{\mathrm{rep}}f_{\min}

. The dollar-valued column headings specify the locked deposit.

Panel of Figure 7 — Figure 7: Interactions needed to reach a reputation target. Solid curves use perfect feedback. Noisy curves use independent binary feedback with success probabilities 0.9 and 0.8 at $\eta=0.9$ . Each point is the mean among trials reaching the target within 5,000 interactions, using 1,000 trials and seeds 0 through 999. At 80% success, 341 trials do not reach 0.99 within the horizon.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Comparison	Scope	Token budget
Calibration	2 configurations on 6 tasks	8,000
Model and tool diagnostics	2 models across 5 configurations	16,000
Factorial comparison	3 models with 4 harnesses	8,000
Extended harness comparison	3 models with 6 harnesses	8,000
Baseline repeatability	5 runs per model with invocation cache disabled	8,000
Budget reconstruction check	4 luna harnesses, compared with truncation from 8,000 tokens	4,000

Appendix

Table 9: Agent evaluation design. Each benchmark comparison uses 127 shared tasks unless noted otherwise. The six-harness comparison adds an elaborate system prompt and condensed-notes memory.

Comparison	Permutation $p$	Adjusted $p$
Model effect across four harnesses	0.00005	0.00020
Harness effect across four harnesses	0.03775	0.15100
Model effect across six harnesses	0.00005	0.00020
Harness effect across six harnesses	0.03820	0.15280

Appendix

Table 10: Retrospective omnibus tests that preserve task pairing. Adjusted probabilities use a family of four tests.

Comparison	Wins	Losses	Adjusted $p$
sol baseline over luna baseline	15	3	0.0226
luna baseline over haiku baseline	26	2	$9.10\times 10^{-6}$
sol baseline over haiku baseline	39	3	$1.69\times 10^{-8}$
sol react over baseline	5	4	1.000
sol plan execute over baseline	3	8	1.000
sol reflect retry over baseline	11	6	1.000

Appendix

Table 11: Exact paired tests. Exclusive wins and losses count discordant tasks. Model and harness comparisons use separate correction families.

Agentic Commerce

Agentic commerce studies autonomous AI agents that discover, recommend, negotiate, and transact goods or services for consumers and businesses.

See all 45 papers

MarketBench: Evaluating AI Agents as Market Participants
Apr 26, 2026Andrey Fradkin, Rohit KrishnanMulti-Agent Coordination LLM Agent Evaluation
Boston University and the MIT Initiative on the Digital Economy. · Independent Researcher.
AgentReputation: A Decentralized Agentic AI Reputation Framework
Apr 30, 2026Mohd Sameen Chishti, Damilare Peter Oyinloye, Jingyue LiAI Accountability AI Agent Security
Department of Computer Science NTNU Trondheim, Norway
BazaarBench: Delegation Safety in Decentralized C2C Marketplaces Run by LLM Agents
Oct 5, 2026Ziyan Wang, Shuqing Shi, James Oldfield +5AI Agent Safety Benchmarks LLM Agent Safety
King’s College London · Institute for Decentralized AI · University of Oxford +1

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

MarketBench: Evaluating AI Agents as Market Participants

Andrey Fradkin, Rohit Krishnan

Boston University and the MIT Initiative on the Digital Economy. · Independent Researcher.

Multi-Agent Coordination LLM Agent Evaluation AI Agent Benchmarks

Open paper AskPDF arXiv

Markets are a promising way to coordinate AI agent activity for similar reasons to those used to justify markets more broadly. In order to effectively participate in markets, agents need to have informative signals of their own ability to successfully complete a task and the cost of doing so. We propose MarketBench, a benchmark for assessing whether AI agents have these capabilities. We use a 93-task subset of SWE-bench Lite, a software engineering benchmark, with six recently released LLMs as a demonstration. These LLMs are miscalibrated on both success probability and token usage, and auctions built from these self-reports diverge from a full-information allocation. A follow-up intervention where we add information about capabilities from prior experiments to the context improves calibration, but only modestly narrows the gap to a full-information benchmark. We also document the performance of a market-based scaffolding with these LLMs. Our results point to self-assessment as a key bottleneck for market-style coordination of AI agents.

Abstract

Agentic Commerce

Explore similar work

MarketBench: Evaluating AI Agents as Market Participants

AgentReputation: A Decentralized Agentic AI Reputation Framework

BazaarBench: Delegation Safety in Decentralized C2C Marketplaces Run by LLM Agents