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

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.