SemDHT: Certified Semantic Discovery for Peer-to-Peer Agent Networks over Exact-Key DHTs

Taotao Wang; Chonghe Zhao; Shengli Zhang; Soung Chang Liew

cs.NISep 20, 2026

SemDHT: Certified Semantic Discovery for Peer-to-Peer Agent Networks over Exact-Key DHTs

Authors: Taotao Wang, Chonghe Zhao, Shengli Zhang, Soung Chang Liew

Organizations: Shenzhen University · Guangzhou University · The Chinese University of Hong Kong

Abstract

Agents may need capabilities exposed through external agent endpoints or service APIs. When a requester is not already bound to a provider, it must discover advertised capabilities matching its task and interface requirements. Over exact-key distributed hash tables (DHTs), broad retrieval transfers large candidate lists, whereas selective retrieval may miss relevant providers or require more replication and lookups. Open publication also lets providers inflate their exposure unless publication bounds are enforceable. We present SemDHT, a certified semantic index for discovering agent-accessible capabilities over exact-key DHTs. A two-layer semantic sketch uses coarse cells to group nearby descriptors and residual codes to narrow candidate selection. Providers publish at a bounded set of derived keys, while requesters probe precision keys before broader recall keys within a lookup budget. Anchor committees certify each descriptor's publication-key set, enabling storage services and requesters to enforce descriptor-to-key consistency. On real API descriptors and task queries, SemDHT achieves recall@10 of 0.955 against exact embedding-space neighbors and 0.947 against ToolBench relevance labels. On a corpus with controlled density augmentation, it matches the candidate exposure of tuned locality-sensitive hashing (LSH) over a DHT at recall 0.95 with 7.7x fewer lookups and reduces publication fan-out from 16 to 10. A Go/libp2p prototype deployed on same-region and cross-region 200-peer cloud overlays replays 299 Internet queries. With parallel probes and cold certificate caches, SemDHT achieves mean completion-time speedups of 3.64x and 4.11x over LSH, respectively.

Figures & tables

Panel of Figure 1 — Figure 1: SemDHT compiles semantics before the DHT. (a) Matching hard constraints ensure that the descriptor’s namespace label $n(d)$ belongs to the query’s allowed namespace-label set $\mathcal{N}_{q}$ ; nearby embeddings $z_{q},z_{d}$ yield overlapping coarse-cell ID sets $Z_{q},Z_{d}$ and similar residual codes. (b) These codes become exact keys: the publication-key set $K_{\mathrm{pub}}(d)$ and budgeted probe-key set $K_{\mathrm{qry}}(q;L_{q})$ overlap on $\kappa_{1},\kappa_{3}$ . Publication uses at most $\rho(1+J)$ keys, where $\rho$ is the number of selected coarse cells and $J$ is the number of residual-code families (one recall publication key plus $J$ precision publication keys per coarse cell); queries use at most $L_{q}$ . (c) Publication and lookup for each shared key follow unchanged exact-key routing to the same responsible peer, whose posting-list service returns postings for local merge. The ring denotes ownership only, not Chord; evaluation uses Kademlia-style routing.

Panel of Figure 2 — Figure 2: Publication and lookup share the semantic-key construction. Namespace labels select compatible providers; coarse cells and residual codes match tasks within that scope. The committee recomputes publication keys from the complete descriptor and certifies their membership. The provider publishes the certified postings. Exact-key DHT routing reaches posting-list services; the requester verifies returned postings and reconstructs candidates. The clinic advertises an appointment-query capability through an appointment assistant agent or a service API. The user’s personal assistant is the service requester; it discovers candidates under supported interface contracts and queries live slots afterward.

Panel of Figure 3 — Figure 3: Left: $z_{d}$ selects top- $\rho{=}2$ coarse-cell IDs $Z_{d}=\{17,42\}$ (blue/orange), while a farther centroid $\mu_{9}$ (gray) is not selected. Right: inside cell 17, the residual $r_{d,17}=z_{d}-\mu_{17}$ is discretized by a sign-projection residual-code family into a residual code; each residual-code family uses independent projection vectors, giving residuals separated by one projection boundary additional opportunities to match.

recall target	$(\rho,J,\ell,r_{H},L_{q})$	recall	exposure	fan-out
0.90	$(3,4,3,1,32)$	0.902	62.6%	15
0.95	$(2,3,3,1,128)$	0.950	72.8%	8
0.97	$(3,2,3,2,64)$	0.970	80.1%	9

Table 1: Selectivity-first operating points from the full parameter sweep. “exposure” is the fraction of the query’s reachable candidate population actually exposed at that budget—lower is more selective at the same recall.

Figure 4: Recall versus exposure for 432 budgeted operating points from 48

(\rho,J,r_{H})

configurations on the combined corpus. Blue points are the 276 operating points retained by the four-objective Pareto filter; the curve traces the two-dimensional recall–exposure frontier. The three marked operating points correspond to Table 1 .

Figure 5: Mean exact-key DHT lookups issued to reach a given recall target, SemDHT versus the best-tuned LSH-on-DHT configuration at that target, using the data presented in Table 10 . SemDHT is cheaper at all four targets; the gap is largest at recall

0.95

and narrows at

0.97

because the matched LSH optimum switches from the hash-width/radius pair

(w_{\mathrm{LSH}},r_{H})=(8,2)

(6,1)

Figure 6: Measured single-family hit probability versus residual angle

\theta

at a representative calibrated configuration (

\rho{=}2,\ell{=}3,r_{H}{=}1

), against the closed-form

p_{\ell,r_{H}}(\theta)

prediction from Appendix B.1 . Marker area is proportional to the number of real observations in that bin; error bars are 95% confidence intervals. The fit is close across the well-populated

30^{\circ}

–

100^{\circ}

range and only visibly departs in the sparsely observed tails.

Deployment	Region	VMs	Peers/VM	vCPU	RAM
Same-region	Frankfurt	8	25	4	8 GB
Cross-region	Eight regions	8	25	4	8 GB
Requester	Frankfurt	1	–	8	16 GB

Table 2: Network-replay deployment. Each overlay has eight virtual machines (VMs), each hosting 25 peer processes. The cross-region deployment places one VM in each of Frankfurt, Tokyo, Singapore, Hong Kong, Virginia, Silicon Valley, São Paulo, and Dubai. Peers/VM counts overlay service processes; hardware specifications are per VM. All machines use Intel Xeon Platinum CPUs and 64-bit Ubuntu 24.04, with 10 Mb/s of configured bandwidth per machine.

Figure 7: Measured lookup completion with parallel scheduling and a cold certificate cache. Bars show the weighted mean and P95; error bars are 95% query-cluster bootstrap intervals. Sample: 299 complete queries.

Placement	System	Lookups	RPCs	MiB
Same	SemDHT	32.59	130.91	2.913
Same	LSH	256.00	777.85	2.945
Cross	SemDHT	32.59	130.91	2.913
Cross	LSH	256.00	777.85	2.945

Table 3: Weighted mean work per query, parallel scheduling and cold certificate cache. Lookups count logical keys; RPCs include replica reads and pagination; MiB counts requester application-message frames.

Placement	System	Cache	Mean difference [95% CI] (s)	P95 difference [95% CI] (s)
Same	SemDHT	Cold	0.157 [0.075, 0.235]	1.118 [-0.948, 2.124]
Same	SemDHT	Warm	-0.091 [-0.139, -0.045]	-0.127 [-0.246, 0.291]
Same	LSH	Cold	-0.067 [-0.175, 0.044]	0.014 [-0.618, 0.742]
Same	LSH	Warm	0.000 [-0.118, 0.116]	-0.064 [-0.521, 0.809]
Cross	SemDHT	Cold	2.679 [2.540, 2.834]	4.133 [2.315, 5.101]
Cross	SemDHT	Warm	2.259 [2.114, 2.409]	0.854 [-0.478, 3.830]

Table 4: Scheduling contrasts over the same 299 query clusters: stage-barrier minus parallel completion time. Positive values indicate longer completion with barriers. P95 contrasts subtract the two weighted P95 estimates; they are not percentiles of per-query differences. Intervals retain query pairing and frozen sample weights.

Validation path	Mean (ms)	95% CI (ms)
Cold certificate	10.6496	[10.5570, 10.7422]
Verified certificate cached	0.0487	[0.0471, 0.0504]

Table 5: Per-posting validation with five of seven committee signers and a 16-key publication set. Cache hits retain posting-specific checks.

		CPU (%)		RSS (MiB)
Scheduler	Cache	SemDHT	LSH	SemDHT	LSH
Parallel	Cold	0.326	0.394	52.17	52.85
Parallel	Warm	0.291	0.440	52.16	53.00
Stage-barrier	Cold	0.336	0.410	52.50	52.68
Stage-barrier	Warm	0.294	0.431	51.68	52.89

Table 6: Observed per-node resource use during the query phase on the Hong Kong VM. Values average three rounds of 50 queries per condition. Appendix E.8 reports baseline values, round-to-round ranges, and query-validation results.

Figure 8: Query-weighted candidate-acceptance amplification versus malicious-provider fraction under perfect routing and uncompromised certification. Membership verification keeps the measured ratio at

1.000\times

across the sweep.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Transition	Certified change and publication action
Lease renewal	Keep the epoch and certified state identity; extend the lease and replace postings with newly signed posting bodies.
Version update	Advance the epoch by one; certify the successor and publish at its publication keys.
Revocation	Advance the epoch by one; issue a tombstone and disseminate it through the stable anchor and prior publication keys.

Appendix

Table 7: Lineage transitions. Supersession is derived locally from an observed successor.

Placement	System	Schedule	Cache	Mean [95% CI] (s)	P95 [95% CI] (s)	RPC errors
Same	SemDHT	Parallel	Cold	3.819 [3.490, 4.156]	10.289 [8.949, 12.742]	1
Same	SemDHT	Parallel	Warm	3.009 [2.725, 3.315]	8.879 [7.339, 10.099]	0
Same	SemDHT	Barrier	Cold	3.977 [3.618, 4.334]	11.407 [9.195, 13.323]	0
Same	SemDHT	Barrier	Warm	2.918 [2.634, 3.215]	8.751 [7.630, 9.779]	0
Same	LSH	Parallel	Cold	13.897 [13.628, 14.157]	19.721 [18.591, 20.157]	0
Same	LSH	Parallel	Warm	13.565 [13.301, 13.843]	18.929 [18.141, 19.786]	0

Appendix

Table 8: All network-replay conditions for the archived 299-query sample. Estimates retain frozen sample weights and all error-bearing queries. Each interval resamples complete query clusters; errors count application RPC failures, not failed logical lookups.

Encoded object	Bytes
Posting body	253
Provider signature	64
Membership certificate	266
Committee signature	103
Certificate with committee signature	372
Merkle inclusion proof	143

Appendix

Table 9: Protocol-v2 fixture sizes. The complete posting includes the signed body, certificate, committee signature, and inclusion proof.

recall target	exposure/probes	exposure/probes
	SemDHT	LSH-on-DHT
0.80	47.5% / 30.6	47.1% / 102.1
0.90	62.1% / 33.7	61.6% / 173.2
0.95	72.7% / 32.9	72.7% / 253.5
0.97	79.0% / 65.2	83.5% / 110.2

Appendix

Table 10: SemDHT versus the best-tuned LSH-on-DHT configuration at matched recall, interpolated from measured budget curves. “probes” is the mean number of exact-key DHT lookups actually issued.

Schedule	Lookups	Recall
		Clean	Attacked
One entry	59.1	0.9500	0.7957
Two, full prefix	118.3	0.9500	0.9191
Two, fixed cost	59.1	0.8553	0.8273

Appendix

Table 11: Mean physical lookups and recall at entry-path capture probability

f=0.20

. Both two-entry schedules repeat the same keys across entries; the fixed-cost schedule uses a shorter prefix.

Figure 9: Hottest-node response-work versus query Zipf skew, sharded (balanced policy) versus unsharded (log-scale

y

-axis). The benefit grows with skew; the arrow marks the 192-to-50 reduction at Zipf

1.2

Figure 10: Minimum discoverability in the controlled reindexing model under uniform rollout. Old and new publication-key sets are disjoint; query observations switch within one rollout unit. A one-unit Move window covers that interval.

Read-repair	Stale-exposure integral	p95 time	Messages
Off	3.037	17.96	0
On	1.288	8.95	1,538

Appendix

Table 12: Read-repair at turnover rate

0.10

. Times are normalized units; messages count direct read-repair messages for the 512-lineage run, averaged over three seeds. Both arms include background anti-entropy.

			CPU (%)		RSS (MiB)
System	Scheduler	Cache	Baseline	Query phase [range]	Baseline	Query phase [range]
SemDHT	Parallel	Cold	0.399	0.326 [0.323, 0.328]	51.87	52.17 [52.09, 52.25]
SemDHT	Parallel	Warm	0.411	0.291 [0.288, 0.296]	52.25	52.16 [51.76, 52.44]
SemDHT	Stage-barrier	Cold	0.414	0.336 [0.326, 0.354]	52.12	52.50 [52.29, 52.62]
SemDHT	Stage-barrier	Warm	0.416	0.294 [0.284, 0.307]	51.76	51.68 [51.47, 51.87]
LSH	Parallel	Cold	0.409	0.394 [0.382, 0.408]	52.44	52.85 [52.58, 53.11]

Appendix

Table 13: Per-node resource observations in the separate 400-node deployment. Baseline and query-phase values are means of three rounds, each averaging 25 cloud nodes. Brackets give the minimum and maximum of the three query-phase batch means. CPU 100% denotes one logical core.

Semantic Search

Semantic search retrieves information by meaning, matching queries and documents even when they use different words.

See all 42 papers

May 12, 2026

Trade-offs in Decentralized Agentic AI Discovery Across the Compute Continuum

Agentic systems deployed across the compute continuum need discovery mechanisms that remain effective across cloud, edge, and intermittently connected domains. In some emerging agentic architectures, decentralized discovery is already an active design direction, placing DHT-based lookup on the path toward agent directories. This paper studies the trade-offs among major structured-overlay families for agent discovery, comparing Chord, Pastry, and Kademlia as candidate indexing substrates within a shared control-plane framework. Using a benchmark subset centered on a 4096-node stationary comparison and a representative 4096-node churn benchmark, the paper characterizes how discovery reliability, startup behavior, and control-plane overhead vary across these overlays. The goal is to clarify the operating points they expose for agent discovery across edge-to-cloud environments.

Patrizio Dazzi, Emanuele Carlini, Matteo Mordacchini +1

Department of Computer Science University of Pisa Pisa, Italy · Institute of Information Science and Technologies National Research Council of Italy Pisa, Italy · Institute of Informatics and Telematics National Research Council of Italy Pisa, Italy

Topic pending

Ask PDF

Apr 25, 2026

Usable Agent Discovery for Decentralized AI Systems

Large-scale agentic systems run on distributed infrastructures where many software agents share physical hosts and are discovered via peer-to-peer mechanisms. Discovery must handle node-level churn from failures and host departures and agent-level churn from demand-driven activation, deactivation, and state changes. Their interaction reshapes classic trade-offs between structured and unstructured overlays. We study decentralized agent discovery under this two-level churn, assuming nodes host multiple agents, overlays are structured or gossip-based, and agents switch between warm and cold states. Using Kademlia as a structured and Cyclon+Vicinity as a gossip baseline, we compare stable, node-churn-only, agent-cooling-only, and combined regimes to see when routing efficiency, resilience, and service readiness align or favor different designs. Structured overlays are more robust and efficient in stable and node-churn regimes, while gossip-based overlays remain competitive and can be faster when readiness dominates.

Patrizio Dazzi, Emanuele Carlini, Matteo Mordacchini +1

Department of Computer Science University of Pisa · Institute of Information Science and Technologies National Research Council of Italy · Institute of Informatics and Telematics National Research Council of Italy

Multi-Agent Systems

Ask PDF

Aug 24, 2026

Enrich-Retrieve-Rank: Scaling Capability Discovery Beyond In-Context Routing

Agent ecosystems now include thousands of MATS components (Models, Agents, Tools, and Skills), yet their discovery still relies on in-context routing. These systems read a registry (names, hints, or descriptions, as context budget permits), pick a candidate, invoke it, and retry on failure. This pattern degrades with scale, and registries are growing fast. We recast capability discovery as search over a registry by defining an offline enrichment step that turns sparse metadata into searchable profiles, and an online retrieve-then-rank pipeline that returns a ranked shortlist without invoking any candidates online. We show that from N=10 to 7,278 capabilities, in-context routing's top-1 accuracy (Match@1) collapses (0.85 to 0.12), while retrieve-then-rank degrades more gently (0.81 to 0.39) because its reranker still ranks the right capability first 0.70-0.87 of the time once retrieval finds it. In the Nova Micro sweep, the crossover is around N=500. We compare against two in-context baselines. Full-Ctx puts the whole registry in the prompt and asks the LLM to pick. Search&Pick gives the LLM a search tool to narrow candidates before it picks. At full scale the pipeline leads Search&Pick by 6.5 percentage points (pp) on Match@1 at about half the cost. It reduces cost 70x versus Full-Ctx. We use a fixed configuration (same enrichment, retriever, and scorer weights) across agent, tool, and skill registries. The pipeline runs in production as the default capability-discovery layer of a large-scale multi-agent platform.

Nazib Sorathiya, Daniel Zhang, Bardiya Akhbari

Amazon AGI Seattle, WA, USA

LLM Agent Routing Agentic Retrieval

Ask PDF

Abstract

Semantic Search

Explore similar work

Trade-offs in Decentralized Agentic AI Discovery Across the Compute Continuum

Usable Agent Discovery for Decentralized AI Systems

Enrich-Retrieve-Rank: Scaling Capability Discovery Beyond In-Context Routing