💻 computer science

Towards Distributed Inference of LLMs on a P2P Network

This paper proposes a decentralized, prefix-cache-aware routing scheme for peer-to-peer LLM serving that leverages local radix trees and asynchronous peer metadata to route requests to nodes with the longest matching prefixes, thereby reducing inference latency without requiring centralized coordination or KV-cache transfers.

Original authors: Shabari S Nair, Krishanu Saini

Published 2026-06-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shabari S Nair, Krishanu Saini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive library of knowledge (a Large Language Model) that helps people write stories, answer questions, and solve problems. Every time someone asks a question, the library has to "think" through the first part of the request before it can start giving an answer. This "thinking" phase is slow and uses a lot of energy.

However, often many people ask questions that start with the exact same words—like "Here is a story about a cat..." or "Translate this sentence to French." In a smart library, once the "thinking" for those opening words is done, the library saves that work in a temporary notebook (called a KV Cache) so it doesn't have to re-do it for the next person. This is called Prefix Caching.

The Problem: The "One Library" Bottleneck

In a traditional setup, you might have one giant library building with many shelves (nodes). If a new person walks in, a central manager decides which shelf to send them to.

The Issue: If the manager sends a person to Shelf A, but the "thinking" for their question was saved on Shelf B, Shelf A has to start from scratch. The manager has to constantly check every single shelf to see where the notes are. If the manager gets too busy or breaks down, the whole library slows down.
The Alternative: Some libraries try to copy the notes from Shelf B to Shelf A instantly. But these notes can be huge (like moving entire bookshelves), and it takes too much time and bandwidth to move them around, especially if the shelves are far apart.

The Solution: A Peer-to-Peer "Gossip" Network

This paper proposes a new way to run the library: No central manager. Instead, every shelf (node) is its own librarian, and they all talk to each other directly.

Here is how it works, using a simple analogy:

1. The "Radix Tree" (The Librarian's Mental Map)
Every librarian keeps a mental map (a Radix Tree) of the questions they have recently answered and the notes they have saved.

Example: Librarian Alice knows she has the notes for "How to bake a cake." Librarian Bob knows he has the notes for "How to fix a bike."

2. The "Gossip" (Anti-Entropy)
Instead of a central boss telling everyone what's happening, the librarians gossip. Every few seconds, they whisper a quick summary to their neighbors: "Hey, I just saved notes on 'baking'."

They don't send the heavy notes (the actual data); they just send a tiny list of what topics they have covered.
This happens in the background, so it doesn't slow down the actual work.

3. Making the Decision (Routing)
When a new customer walks in with a request like "How to bake a chocolate cake," the librarian who first sees them checks their mental map.

They ask: "Who else has the notes on 'baking'?"
If they hear from a neighbor that Bob has the notes on "baking," they send the customer to Bob. Bob can skip the "thinking" part and go straight to the answer.
If the librarian's map is slightly old (stale) and they send the customer to the wrong person, it's not a disaster. The wrong person just has to start the "thinking" from scratch. The answer is still correct; it just took a tiny bit longer. Correctness is never lost, only speed.

4. Handling the Crowd (Hotspots)
What if everyone wants to know about "baking"? Bob becomes the "Baking Specialist" and gets overwhelmed.

The system has a safety valve: If Bob gets too busy, he whispers, "I'm full!" to the other librarians.
The other librarians then stop sending baking requests to Bob for a little while, letting him catch up, and send the new requests to someone else who will have to do the "thinking" from scratch.

What the Experiments Showed

The researchers tested this idea in a computer simulation with four "librarians" using a dataset of general knowledge questions (MMLU).

Fast Networks Win: If the librarians can gossip quickly (low network delay), this system is much faster than having no routing at all. It saves a lot of time by reusing the "thinking" work.
Slow Networks Lose: If the gossip takes too long (high network delay), the time spent sending the request to the right person is longer than just doing the work yourself.
Specialization: The system naturally creates "specialists." If a topic is popular, one node will eventually hoard all the notes for it, becoming super fast at that specific topic. However, if the notes get too big, the system automatically kicks out old notes to make room, causing the "specialist" to change over time.

The Bottom Line

This paper suggests that for distributed AI systems, we don't need a heavy, central boss or expensive data transfers. Instead, we can use a decentralized, gossip-based system where nodes share lightweight maps of what they know.

Pros: It's resilient (if one node breaks, the others keep working), it scales well, and it avoids moving huge amounts of data.
Cons: It only works well if the network is fast and the questions have a lot of repetition (like many people asking similar things). If the network is slow or the questions are all unique, the system doesn't gain much speed.

In short: It's like a group of friends sharing a playlist. Instead of one person managing the whole list, everyone tells the others what songs they have. If you want a song, you ask the friend who has it. If they don't have it, you just play it yourself. It's messy, but it works great when everyone is listening to the same hits.

Technical Summary: Towards Distributed Inference of LLMs on a P2P Network

Problem Statement

Large Language Model (LLM) inference is increasingly constrained by redundant computation rather than just model size. In autoregressive generation, requests sharing common prefixes (e.g., system prompts, few-shot demonstrations, or conversation histories) require identical Key-Value (KV) cache states. Recomputing these states for every request wastes GPU cycles and increases latency. While prefix caching effectively mitigates this in single-node settings, scaling to a cluster introduces significant challenges:

Partitioned Caches: In a multi-replica deployment, KV caches are naturally partitioned across nodes. A prefix cached on one worker is not automatically available to others.
Routing Bottlenecks: Existing solutions rely on centralized routers (creating a scalability bottleneck and single point of failure) or shared remote KV-cache storage (expensive due to the high bandwidth cost of transferring large KV tensors, especially for long contexts).
Network Constraints: In peer-to-peer (P2P), edge, or heterogeneous environments, transferring gigabyte-scale KV states is often impractical.

The core problem is how to route requests to the node most likely to hold the relevant prefix cache without centralized coordination or expensive remote KV transfers, while tolerating network latency and stale metadata.

Methodology

The authors propose a fully decentralized, prefix-cache-aware routing scheme for P2P LLM serving. The system operates on the principle that routing decisions can be made using weakly consistent metadata without compromising inference correctness.

Core Architecture

Local Radix Trees: Each node maintains an exact radix tree representing the prefixes currently cached in its own GPU memory.
Distributed Estimates: Each node also maintains approximate, read-only replicas of peer radix trees. These estimates are refreshed asynchronously via periodic anti-entropy (a gossip protocol), where nodes exchange compact cache-state summaries.
Routing Logic: When a request arrives at a node, the local router queries its local view of the cluster to identify the peer with the longest estimated prefix match.
- If a better match is found on a peer, the request is forwarded.
- If the local node has the best match (or no better match is known), the request is processed locally.
Handling Staleness: The system relies on weak consistency. Stale metadata may cause a request to be routed to a node that no longer holds the prefix (a cache miss), forcing a recompute. Crucially, this affects performance (latency) but not correctness, as every node can execute the full LLM independently.

Failure Handling and Safety

Crash Recovery: If a forwarded request fails (e.g., the target node crashes), the originating node detects the failure via timeouts and falls back to local execution or the next-best target. No explicit recovery protocol is needed for correctness.
Hotspot Mitigation: To prevent "specialist push-back" (where a popular prefix causes all traffic to flood a single node), the system employs a push-back mechanism. If a node's queue depth exceeds a threshold, it advertises this in its anti-entropy broadcast. Originating nodes temporarily pause routing to that node, allowing load to disperse.
Asynchrony: The design assumes partial synchrony only for liveness (timeouts must eventually fire). Safety holds under fully asynchronous execution because routing decisions are local and non-blocking.

Key Contributions

Decentralized Architecture: A fully distributed routing system where every node runs identical logic and makes local decisions without a centralized coordinator.
Approximate Radix-Tree Replication: A mechanism for cluster-wide cache awareness using asynchronous anti-entropy to maintain read-only estimates of peer caches, avoiding write-write conflicts.
Coordination-Avoidance Framework: The paper frames cache-aware routing as a coordination-avoidance problem, demonstrating that weak consistency is sufficient because stale decisions only incur performance penalties (cache misses), not semantic errors.
Empirical Evaluation: Evaluation on a simulated four-node cluster using MMLU workloads, analyzing latency, cache-hit rates, and the emergence of specialization-eviction cycles.
Fault Tolerance Analysis: A formal argument that the system requires no explicit recovery protocols for correctness, as failures only impact liveness, not inference quality.

Results

Experiments were conducted on a simulated cluster using the MMLU dataset with a 0.5B parameter model, focusing on prefill-heavy workloads.

Latency Break-Even: The benefit of forwarding requests depends heavily on network latency ( $\Delta_{comm}$ $Δ_{co mm}$ ).
- At 2 ms (LAN conditions), decentralized routing reduces latency (0.310s vs. 0.323s baseline) by effectively reusing remote caches.
- At 200 ms and 1000 ms, the round-trip cost of forwarding exceeds the savings from prefix reuse, making routing detrimental.
Workload Skew: The system shows significant benefits under skewed workloads (Zipfian distribution).
- In skewed scenarios with low latency, routing reduced latency to 0.206s (vs. 0.266s baseline).
- Cache hit rates improved from ~85% (no-routing) to 91.4% (routed) in skewed settings, driven by the formation of "specialist" nodes that accumulate deep caches for dominant prefixes.
Specialization-Eviction Cycle: The study observed a three-phase cycle:
1. Competition: Traffic is dispersed as no node holds the prefix.
2. Specialization: One node captures ~100% of traffic for a topic as its cache fills.
3. Eviction: LRU eviction displaces the prefix, causing traffic to re-disperse.
- This specialization amplifies load imbalance (up to 88% of traffic on one node in skewed settings), which is mitigated by the push-back mechanism and slower anti-entropy polling.

Significance and Claims

The paper claims to explore a new design point in LLM serving: decentralized, weakly consistent, locality-aware inference routing.

Scalability and Availability: By removing the centralized routing tier, the system avoids single points of failure and scales more gracefully under partial failures.
Bandwidth Efficiency: It avoids the prohibitive cost of transferring large KV tensors across the network, exchanging only lightweight metadata.
Deployment Flexibility: The architecture is well-suited for P2P, edge, and multi-router deployments where a global scheduler is undesirable or impractical.
Modest Scope: The authors acknowledge that privacy concerns in P2P cache sharing are application-dependent and outside the scope of this work. They also note that the benefits are contingent on specific conditions: low communication latency, prefill-heavy workloads, and skewed prefix distributions. In high-latency or uniform workloads, the benefits diminish or reverse.

Ultimately, the work demonstrates that lightweight metadata replication and coordination-free peer-to-peer routing can recover much of the benefit of prefix reuse while preserving the scalability and flexibility of distributed systems.