Privacy-Preserving LLMs Routing

1. Problem Statement

Large Language Model (LLM) routing is a critical strategy for balancing model performance and cost-efficiency by dynamically selecting the most suitable model provider for a given query. However, this architecture introduces a significant privacy vulnerability:

• Data Leakage: The routing layer acts as an intermediate node between the user and the LLM provider. In standard implementations, the router sees the raw user query and the intermediate embeddings, creating a potential point of data leakage.
• Third-Party Risk: Routing is often managed by third parties rather than the model providers, complicating the chain of control for sensitive data.
• Performance Bottleneck of MPC: While Secure Multi-Party Computation (MPC) can theoretically protect data by keeping queries and model parameters encrypted, naively applying MPC to LLM routing incurs prohibitive computational and communication overhead.
  • Non-linear operations (e.g., Softmax, GeLU) in Transformer encoders are extremely expensive under MPC.
  • Nearest Neighbor Search (KNN) for model selection requires heavy comparison and sorting, leading to massive latency in encrypted domains.

2. Methodology: The PPRoute Framework

The authors propose PPRoute, an end-to-end privacy-preserving framework designed specifically for embedding-based LLM routing. It optimizes two main bottlenecks: Encoder Inference and Nearest Neighbor Search.

A. MPC-Friendly Operations (Encoder Optimization)

Standard Transformer encoders rely on operations that are inefficient in MPC. PPRoute replaces these with "MPC-friendly" approximations:

• Softmax Approximation: Replaces the exponential-heavy Softmax function with a "2ReLU" approximation:
  $$\text{softmax}(x) \approx \frac{\text{ReLU}(x)}{\sum \text{ReLU}(x)}$$
• GeLU Approximation: Replaces the Gaussian Error Linear Unit (GeLU), which requires complex error function approximations, with the standard ReLU function.
• Result: These replacements drastically reduce the number of multiplications and iterations required during inference, significantly lowering latency.

B. Multi-Stage Training Algorithm

Replacing non-linear functions degrades model accuracy. To mitigate this, PPRoute employs a knowledge distillation strategy:

1. Teacher Model: A standard, high-accuracy encoder (with original Softmax/GeLU) is trained in plaintext.
2. Student Model: An "approximated encoder" (using 2ReLU/ReLU) is trained to mimic the teacher.
3. Hybrid Loss: The student model is trained using a combined loss function:
   $$\mathcal{L}(M_s) = \mathcal{L}_{\text{routing}}(M_s) + \beta \cdot \mathcal{L}_{\text{distill}}(M_t \parallel M_s)$$
   This ensures the student maintains high routing quality while adhering to the constraints of the encrypted domain.
4. Fine-tuning: The encoder is frozen, and only the subsequent MLP layers are fine-tuned to further optimize performance.

C. Unsorted Top-k Algorithm (Secure Retrieval)

Traditional secure KNN involves iterative sorting or global comparisons, which are communication-heavy. PPRoute introduces a novel Unsorted Top-k algorithm:

• Mechanism: It restructures the selection problem into parallelizable matrix operations.
  1. Construct a comparison matrix $C$ where $C_{i,j} = 1$ if $A_{i,j} > B_{i,j}$.
  2. Compute a ranking score vector $S$ by summing columns of $C$ (local addition of secret shares, zero communication cost).
  3. Apply a threshold mask to select the top-$k$ elements.
• Complexity: This approach achieves $O(1)$ communication complexity (constant rounds) regardless of the dataset size, shifting the bottleneck from network latency to bandwidth. This is ideal for LLM routing where the model pool size ($n$) is relatively small.

3. Key Contributions

1. First Systematic Study: The first work to systematically investigate privacy risks in LLM routing and propose a dedicated end-to-end privacy-preserving framework (PPRoute).
2. Efficient Encoder Inference: Introduction of "2ReLU" and ReLU approximations that accelerate MPC inference without sacrificing routing quality.
3. Advanced Training Strategy: A multi-stage distillation algorithm that allows the approximated model to match the performance of the plaintext counterpart.
4. Novel Retrieval Algorithm: The "Unsorted Top-k" algorithm reduces communication rounds to a constant, significantly accelerating secure nearest neighbor search.
5. Generalizability: The framework is demonstrated to work effectively on different embedding-based routing architectures (CSCR and UniRoute).

4. Experimental Results

The authors evaluated PPRoute on three benchmark datasets: EmbedLLM, MixInstruct, and RouterBench, comparing it against naive MPC implementations and plaintext baselines.

• Speedup:
  • PPRoute achieves a ~20× speedup over naive MPC implementations.
  • Specific results for CSCR: Reduced inference time from ~199s to ~9.4s (21.26× speedup) on EmbedLLM.
  • Specific results for UniRoute: Reduced inference time from ~190s to ~9.9s (19.22× speedup) on EmbedLLM.
• Routing Quality:
  • PPRoute achieves performance metrics (AUDC, Peak Accuracy, Query-Normalized Cost) nearly identical to the plaintext (unencrypted) counterparts.
  • For example, on the EmbedLLM dataset, the Area Under the Deferral Curve (AUDC) for PPRoute (0.538) is virtually identical to the Original CSCR (0.539).
• Retrieval Efficiency:
  • The Unsorted Top-k algorithm reduced communication volume by ~60% and communication rounds from 130 to 52 compared to baseline methods, achieving a total execution time of 0.25s (vs. >10s for other sorting-based secure methods).

5. Significance

• Bridging the Gap: PPRoute successfully bridges the gap between strong privacy guarantees (via MPC) and the practical latency requirements of real-time LLM routing.
• Real-World Applicability: By enabling privacy-preserving routing without prohibitive costs, this framework makes it feasible to deploy secure LLM routing in sensitive domains such as healthcare, finance, and enterprise applications, where user query confidentiality is paramount.
• Scalability: The $O(1)$ communication complexity of the retrieval algorithm ensures that the system remains scalable even as the number of available model providers grows, provided the pool size remains within reasonable bounds for matrix operations.

In conclusion, PPRoute demonstrates that it is possible to secure the "middleman" of the LLM ecosystem without sacrificing the efficiency or quality that makes LLM routing valuable in the first place.