PaperlayerView exact revision on arXiv

Source-linked AI summary

Semantica: Decentralized Search using a LLM-Guided Semantic Tree Overlay

Petru Neague, Quinten Stokkink, Naman Goel, Johan Pouwelse

arXiv:2502.10151v1cs.IRcs.DCcs.NIcs.SYeess.SY

TL;DR

Decentralized search struggles to retrieve semantically relevant documents accurately and quickly without a central index. Semantica uses pre-trained LLM embeddings to organize peers in a semantic tree, and its experiments report improved peer discovery and document retrieval over comparison methods.

  • Problem

    Decentralized systems lack a central index for routing semantic text queries, and network communication makes matching centralized search accuracy and speed challenging.

    Source: §I · p. 1

  • Method

    Semantica uses pre-trained LLM embeddings to organize peers in a decentralized semantic tree, with soft clustering allowing users to occupy multiple branches when near split centroids.

    Source: §I · p. 2, A. Tree construction · p. 5

  • Results

    At two hops, Semantica retrieves 12.75% of required documents while other methods achieve less than 6%, and it improves peer discovery and retrieval accuracy over random and graph-diffusion approaches.

    Source: B. Document retrieval accuracy with… · p. 10, §X · p. 13

  • Takeaways & Limitations

    The tree overlay and neighbor expansion provide a foundation for scalable decentralized semantic search using pre-trained LLM embeddings.

    Source: §X · p. 13

    Semantica's clustered peers may be farther from users seeking documents outside their group's interests; combining tree-based and random meetings may help connect disparate groups.

    Source: C. Semantica tree versus diffusion… · p. 10

Abstract

from arXiv · show

Centralized search engines are key for the Internet, but lead to undesirable concentration of power. Decentralized alternatives fail to offer equal document retrieval accuracy and speed. Nevertheless, Semantic Overlay Networks can come close to the performance of centralized solutions when the semantics of documents are properly captured. This work uses embeddings from Large Language Models to capture semantics and fulfill the promise of Semantic Overlay Networks. Our proposed algorithm, called Semantica, constructs a prefix tree (trie) utilizing document embeddings calculated by a language model. Users connect to each other based on the embeddings of their documents, ensuring that semantically similar users are directly linked. Thereby, this construction makes it more likely for user searches to be answered by the users that they are directly connected to, or by the users they are close to in the network connection graph. The implementation of our algorithm also accommodates the semantic diversity of individual users by spawning "clone" user identifiers in the tree. Our experiments use emulation with a real-world workload to show Semantica's ability to identify and connect to similar users quickly. Semantica finds up to ten times more semantically similar users than current state-of-the-art approaches. At the same time, Semantica can retrieve more than two times the number of relevant documents given the same network load. We also make our code publicly available to facilitate further research in the area.

I. INTRODUCTION

Centralized search raises concerns about concentrated power, while decentralized systems struggle to retrieve semantically relevant documents accurately and quickly. Semantica uses pre-trained LLM embeddings and a tree-based peer overlay to bring semantic search to decentralized networks.

I. INTRODUCTION

  • Decentralized search must route semantic text queries without a central index, while network communication and node churn make centralized-level accuracy and speed difficult to match.Existing DHT and publish-subscribe approaches support other retrieval models, but semantic text retrieval has not seen wide adoption.Source: §I · p. 1
  • Semantic overlay networks connect users by semantic context, allowing similar users to be queried first; prior work found low latency and high retrieval accuracy comparable to centralized approaches.That performance depends on accurately capturing document semantics.Source: §I · pp. 1–2
  • Earlier embedding-navigation work did not map directly to decentralized networks; Semantica uses pre-trained general-purpose LLMs to build decentralized semantic search trees without single-purpose training.The passage describes De-DSI as requiring periodic online learning to update its index.Source: §I · p. 2
  • Semantica is presented as a predictive decentralized document-search algorithm that builds an LLM-based semantic overlay tree maintained and updated through peer-to-peer interactions.The introduction frames this as a response to concerns about centralized web technologies and the limited adoption of decentralized alternatives.Source: §I · pp. 1–2

II. SETTING

The setting is decentralized semantic search among users with partial local knowledge, where queries must be routed through limited neighbor lists. Related work spans semantic indexing, learned retrieval, and structured or diffusion-based overlays, with differing assumptions about training, content placement, and search scope.

II. SETTING

  • Users store overlapping subsets of documents and route textual semantic queries through local neighbor lists; the setting assumes perfect local search while nodes may join, leave, or change addresses.The paper scopes its optimization to query routing rather than local search.Source: §II · p. 2
  • In AOL4PS, 6,978 of 12,907 users shared at least one website with another user, and maximum BERT-embedding cosine similarity was mostly above 0.93.The dataset contains 187,521 websites and 1,339,101 queries collected over three months in 2006.Source: §II · p. 2
  • The design goal is an overlay built from local LLM embeddings that supports semantic matching, predictive connections, distributed scaling, and reduced reliance on large-scale training.Embeddings can be computed locally or obtained from an external service.Source: §II · pp. 2–3
  • Adaptive overlays must accommodate changing interests and embeddings, node churn, and limited bandwidth and computation, especially on commodity or mobile hardware.Nodes may discover new documents, relocate, or leave.Source: §II · p. 3

III. RELATED WORK

  • Related retrieval approaches differ in semantic search, predictive caching, distribution, and training requirements; other structured networks often assume known publishers or hash keys, while ontology trees assume a reliable taxonomy.The paper states it does not assume known publishers or a taxonomy.Source: §III · pp. 3–4
  • Latent semantic indexing has multiple implementations; prior matrix-based SVD indexing outperformed faster TF-IDF retrieval, while pre-trained LLMs are available without further training.The related-work discussion describes GloVe and BERT as trained embedding approaches and notes LLMs' lower computing requirements relative to earlier models.Source: §III · p. 4
  • DSI trains a transformer to retrieve document identifiers, while De-DSI decentralizes retrieval through document exchange and global-network fine-tuning.The paper says De-DSI's efficiency at scale is not yet considered and its time complexity increases with network size.Source: §III · p. 4
  • Graph-Diffusion spreads summarized node content using Personalized PageRank [10], and forwards queries by neighbor relevance under a hop limit.The cited work's accuracy decreases as document density and search radius increase.Source: §III · p. 4

IV. DESIGN OF SEMANTICA

Semantica organizes peers hierarchically in embedding space so users with similar document interests are placed near one another. It derives document embeddings with an LLM and begins tree construction from a root node.

IV. DESIGN OF SEMANTICA

  • Semantica constructs a hierarchically clustered tree in embedding space to place users with similar item interests near one another.The example diagram illustrates the tree construction with rudimentary clustering for presentation.Source: §IV · p. 4, Figure 2 · p. 5
  • Each user applies an identical LLM to embeddings of accessed documents, then computes a user embedding as the mean of the document embeddings.The document-level embedding is denoted D_ij for document d_ij.Source: §IV · p. 4
  • Tree construction initializes a root node as a leaf that can hold a limited number of users before further processing.The algorithm processes users to be added to the tree in a loop.Source: §IV · p. 5

A. Tree construction

Semantica builds a binary semantic tree by splitting overfull leaves with k-means and routing users by centroid distance. Users near both centroids can follow both branches, while the resulting tree approximates costly optimal neighborhoods.

A. Tree construction

  • Overfull leaves split into two k-means clusters, and users near both centroids clone into both child branches when their distance difference is below ∆.The tree uses k = 2 throughout; cloning places the same user on both paths to reach more highly similar users.Source: A. Tree construction · p. 5
  • Users traverse the tree by comparing their embeddings with child centroids, choosing the closer branch or both branches when the cloning condition holds.Users are assigned to a non-full leaf, and the process supports users joining dynamically without a prescribed order.Source: A. Tree construction · p. 5
  • The tree’s hierarchical clustering makes users in the same leaf more likely to hold common documents than users far apart in the tree.Branching lines divide the embedding space recursively, with left and right clusters labeled 0 and 1.Source: A. Tree construction · pp. 5–6
  • This tree approximates optimal user neighborhoods because computing every user’s most-similar peers is impractical under decentralized communication costs.Source: A. Tree construction · p. 6

B. Semantic neighbor discovery

After tree placement, Semantica gathers nearby peers for each clone and ranks contacts by cosine similarity. Periodic expansion rounds can discover closer peers missed by the approximate tree clustering.

B. Semantic neighbor discovery

  • Each clone gathers nearby users, searching adjacent leaves with breadth-first search when its own leaf contains too few contacts to reach ncc.Users combine contacts from all clones and retain the ncu most similar peers as their closest-users list.Source: B. Semantic neighbor discovery · p. 6
  • Periodic expansion asks a randomly chosen closest user for a closer peer, adding that peer when it beats the current ncu-th closest user.This procedure addresses highly similar peers that the approximate tree may place in different leaves.Source: B. Semantic neighbor discovery · p. 6
  • Expansion rounds use cosine similarity to refine connections, whereas tree construction uses Euclidean distance to cluster users.The rounds proceed asynchronously across peers.Source: B. Semantic neighbor discovery · p. 6

C. Query Model

Semantica uses chain-hopping to route a query through peers ranked by similarity to its embedding. The search stops when a matching document is found or the hop limit is reached.

C. Query Model

  • Chain-hopping forwards a query to the closest user by query-embedding similarity, repeating until a document is found or the maximum hop limit is reached.The method dynamically adapts the path based on semantic similarity.Source: C. Query Model · p. 7
  • Each hop sends one message, giving O(ℓ) network messages and O(ℓ·k) local similarity-computation cost for a closest-users list of size k.At each hop, the current user compares the query embedding with all users in that list.Source: C. Query Model · p. 7
  • Chain-hopping prioritizes semantically relevant paths without flooding unnecessary network nodes.Source: C. Query Model · p. 7

V. IMPLEMENTATION AND PERFORMANCE ANALYSIS

The evaluation uses AOL4PS data and tests the semantic tree’s retrieval and clustering methods. The experimental setup filters and splits user histories, builds embeddings and a capacity-limited tree, and refines users’ closest-peer lists.

V. IMPLEMENTATION AND PERFORMANCE ANALYSIS

  • The evaluation focuses on retrieval accuracy and clustering effectiveness under different query mechanisms and conditions.The experimental setup requires data preparation, embedding implementation, and parameterization of the tree and user discovery.Source: §V · p. 7, A. Experimental Setup · p. 7

A. Experimental Setup

  • Users with fewer than 30 unique documents are excluded, repeat accesses are removed, and each remaining user’s documents are randomly split into 10 test documents and a training set.Different URLs from the same domain may occur in both sets; the authors treat them as distinct documents with distinct embeddings.Source: A. Experimental Setup · p. 7
  • User embeddings are the mean embeddings of training document titles, and nodes split when they exceed a capacity of 50 users.Users near both centroids are cloned into both child nodes.Source: A. Experimental Setup · p. 7
  • Each user builds a known-users list from peers in the same or nearby leaves, then keeps the ncu most similar peers in its closest-users list.Source: A. Experimental Setup · p. 7
  • Users refine closest-users lists by querying random neighbors for closer peers until a preset interaction count is reached or the list stabilizes.The setup uses random document splitting; timestamp-based splitting is identified as a possible future alternative.Source: A. Experimental Setup · pp. 7–8

B. Experiment designs

The experiments test Semantica’s ability to identify similar peers, retrieve documents through a decentralized network, and reduce distances to target documents. They assess peer similarity against a cosine-similarity ground truth and compare network structure with a degree-matched random graph.

Experiment 1: Closest-User Identification with a Limited Number of Interactions

  • Experiment 1 measures closest-user identification by intersecting locally discovered peers with each user's 50 globally closest peers, defined by cosine similarity.The intersection size is the absolute-recall-out-of-50 measure, referred to as recall.Source: B. Experiment designs · p. 8
  • The first experiment varies ∆ and compares expansion-round recall with a Barabási–Albert graph matched to Semantica’s average graph size.The comparison assesses how quickly Semantica identifies embedding-space neighbors versus random identification.Source: B. Experiment designs · p. 8

Experiment 2: Document Retrieval Mechanisms

  • Experiment 2 forwards a query from the user with the closest query embedding to the neighbor with the highest cosine similarity, stopping at a maximum hop limit.Performance is the percentage of test queries resolved within that hop limit.Source: B. Experiment designs · p. 8

Experiment 3: Smallest Distance to a Target Document

  • Experiment 3 measures the minimum hops from a randomly selected user to any user holding a target document, while network efficacy is compared with a degree-matched Barabási–Albert graph.The graph comparison evaluates hop distances while preserving the structural efficiency of the network.Source: B. Experiment designs · p. 8

VI. RESULTS AND DISCUSSION

Semantica’s tree improves closest-peer recall over random contacts, with expansion rounds finding nearly all target peers when ∆ is positive. The results also show that cloning supports recall gains, while larger ∆ values increase clone counts and computational burden.

A. Closest User Recall

  • With ∆>0, 20 expansion rounds find more than 40 of the required closest peers for every tested ∆, whereas ∆=0 shows no significant recall increase.The ∆=0 limitation is attributed to users in the same leaf sharing identical neighbors, making expansion queries largely redundant.Source: A. Closest User Recall · pp. 8–9
  • At initialization, Semantica recall exceeds 5 across configurations versus about 0.4 for random contacts; by round 10, recall is about 35 at ∆=0.001 and 30 at ∆=0.0005, versus about 5 randomly.Figure 4 compares closest-neighbor recall across expansion rounds and ∆ values.Source: Figure 4 · p. 9, A. Closest User Recall · p. 9
  • At ∆=0.001, about 5,100 of 6,980 users remain uncloned, and the clone-count distribution follows a decreasing exponential trend.Figure 5 shows the distribution of clones per user at ∆=0.001.Source: Figure 5 · p. 9, A. Closest User Recall · p. 9
  • At ∆=0.005, the expected number of clones per user exceeds 7; clone counts begin rising more rapidly at approximately ∆=0.001.The reported clone-growth findings are specific to AOL4PS, and the threshold may vary with dataset characteristics.Source: A. Closest User Recall · p. 9, Table II · p. 9

B. Document retrieval accuracy with query chain-hopping

Semantica’s chain-hopping retrieval is compared with random hopping and graph diffusion, then its hop-distance trade-offs and complexity assumptions are discussed.

B. Document retrieval accuracy with query chain-hopping

C. Semantica tree versus diffusion graph trade-offs

  • The tree shifts many documents to one hop but also pushes some to three or more hops and leaves some unreachable; the random graph may overtake at high hop counts.The longer distances arise as peers cluster and hold fewer connections outside their groups; combining tree-based and random meetings is suggested for chain-hopping.Source: C. Semantica tree versus diffusion… · p. 10

VII. ALGORITHM COMPLEXITY

  • The complexity analysis compares near-balanced and highly skewed embedding distributions, treating 768-dimensional embeddings as a constant factor.Source: §VII · pp. 10–11

A. Complexity of Tree Construction

Tree construction inserts users by traversing centroid splits, with costs depending on tree balance; clustering, cloning, and expansion rounds add further work and network messages.

A. Complexity of Tree Construction

  • For a near-balanced tree, inserting N users costs O(N log N), with O(log N) traversal and network hops per insertion.Source: A. Complexity of Tree Construction · p. 11
  • A rare, highly unbalanced tree can reach O(N) height and O(N^2) total insertion cost, though the described embedding structure is considered very unlikely.Source: A. Complexity of Tree Construction · p. 11
  • Splitting a leaf with more than M users uses k=2 means clustering; across splits, its O(N · I) cost is typically dominated by insertion when I is small.Source: A. Complexity of Tree Construction · p. 11
  • With moderate ∆, cloning at an average rate cavg keeps message complexity near O(N log N); very large ∆ can cause excessive cloning, so implementations cap ∆ or detect duplicates.Source: A. Complexity of Tree Construction · p. 11
  • Expansion rounds query known users for closer peers, using O(rmax N) messages and O(N log N + N rmax kmean) total computation with tree construction.Sharing every neighbor instead of computing similarity would exponentially increase neighbors and overwhelm the network with messages.Source: A. Complexity of Tree Construction · pp. 11–12

B. Query Complexity

Queries use semantic chain-hopping, forwarding each request to the most similar known neighbor until a relevant document is found or the hop limit is reached. The analysis gives per-query message and local-computation costs, alongside construction and expansion bounds.

B. Query Complexity

  • Each query checks local documents and forwards to the most similar known neighbor; over ℓ hops, it uses at most ℓ messages and O(ℓ · (k + d)) local computation.For Q queries, total network overhead is O(Q · ℓ).Source: B. Query Complexity · p. 12

C. Summary and Remarks

  • Tree insertion is typically O(N log N), expansions add O(rmax N) messages and O(rmax k N) local cost, and bounded average cloning preserves O(N log N) insertion cost.Source: C. Summary and Remarks · p. 12
  • Under extreme skew, insertion can degrade to O(N^2); under moderate ∆ and typical data, construction and expansion remain O(N log N) plus O(rmaxN).Source: C. Summary and Remarks · p. 12

VIII. DEPLOYMENT CONSIDERATIONS

Semantica’s deployment design organizes peers into a hierarchical overlay without a global coordinator, using local custodians and peer interactions. The conclusion reports improved peer discovery and document retrieval accuracy over random and graph-diffusion approaches, with efficient construction and neighbor expansion under typical embedding distributions.

VIII. DEPLOYMENT CONSIDERATIONS

  • Peers operate autonomously with local network knowledge; bootstrap discovery can use an out-of-band root, and multiple roots or topic-specific trees can coexist.The decentralized implementation avoids a global coordinator or centralized index.Source: §VIII · pp. 12–13
  • A custodian stores each split-node’s centroids and child addresses, passing notice to its parent custodian to maintain a route through the tree.Source: §VIII · p. 12
  • Joining peers follow the closest child centroids to a leaf; when its user count exceeds M, local k-means splits the leaf and members are reassigned.Source: §VIII · p. 13
  • Peers periodically query a known neighbor for closer peers and update their closest-users list, refining a limited neighbor set incrementally.Source: §VIII · p. 13
  • Custodian departure can make centroid data unavailable, and unaddressed peer dropout can leave leaves depopulated and the tree imbalanced.Backup custodians and rebalancing are suggested but outside the work’s scope.Source: §VIII · p. 13
  • Experiments do not rank search results; the paper notes that users can rank retrieved documents locally using query-document cosine similarity.Source: §VIII · p. 13

X. CONCLUSION

  • Semantica improves peer discovery and document retrieval accuracy over random baselines and graph-diffusion approaches, with chain-hopping and neighbor expansion supporting high retrieval rates and near-complete recall of relevant peers.The conclusion also reports minimal communication overhead.Source: §X · p. 13
Loading 2502.10151v1…