P$^2$RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-$k$ Retrieval

Technische Samenvatting van P2RAG: Efficiënte Privacybehoudende RAG-service met Ondersteuning voor Arbitraire Top-k Zoekopdrachten

Probleemstelling
Retrieval-Augmented Generation (RAG) stelt Large Language Models (LLM's) in staat externe kennis te benutten, maar het uitbesteden van RAG-diensten introduceert aanzienlijke privacyrisico's voor zowel data-eigenaren (wiens propriëtaire databases worden blootgesteld) als gebruikers (wiens prompts zichtbaar zijn). Bestaande privacybehoudende RAG-systemen (PP-RAG) formuleren het probleem doorgaans als een beveiligde top-k zoekopdracht, waarbij vertrouwen wordt gesteld in beveiligde sortering of beveiligde k-Approximaat Dichtste Buur (k-ANN) technieken. Deze systemen lopen echter tegen kritieke beperkingen aan:

1. Ondynamisch: Ze kunnen vaak geen willekeurige of dynamische aanpassingen van de zoekparameter $k$ ondersteunen.
2. Efficiëntieverlies: Hun prestaties verslechteren aanzienlijk naarmate $k$ toeneemt. Dit is een belangrijke bottleneck, omdat moderne toepassingen in financiën, juridische zaken en gezondheidszorg, evenals LLM's met lange context, vaak grote $k$-waarden vereisen (bijvoorbeeld 100–150 of hoger) om optimale nauwkeurigheid te bereiken.
3. Veiligheidsgaten: Sommige bestaande benaderingen roepen nieuwe veiligheidsproblemen op of slagen er niet in informatielekken tegen kwaadaardige gebruikers strikt te begrenzen.

Methodologie
De auteurs stellen P2RAG voor, een privacybehoudende RAG-service die is ontworpen om efficiënt willekeurige top-k zoekopdrachten te ondersteunen. Het systeem werkt volgens een twee-servermodel waarbij de servers semi-ehrlijk (eerlijk maar nieuwsgierig) en niet-colluderend zijn.

• Systeemarchitectuur:

  • Data-eigenaar: Besteedt een versleutelde database uit aan twee servers. De database bestaat uit $N$ documentembeddings, die tussen de twee servers worden verdeeld via geheime deling (secret sharing) volgens Shamir's methode over een priemveld.
  • Gebruiker: Dien een prompt-embedding in, die eveneens via geheime deling tussen de twee servers wordt verdeeld.
  • Bedreigingsmodel: De servers volgen het protocol maar kunnen proberen data af te leiden. Gebruikers worden gemodelleerd als kwaadaardig en kunnen afwijken van het protocol om informatie te extraheren. Data-eigenaren worden als eerlijk verondersteld.

• Kerninnovatie: Interactieve Bisection versus Sorteren
  In tegenstelling tot bestaande systemen die alle kandidaat-documenten sorteren (een computatiever dure operatie in beveiligde protocollen), vermijdt P2RAG sorteren volledig. In plaats daarvan maakt het gebruik van een interactieve bisection-methode om een afstandsdrempel ($d_k$) te bepalen die de top-$k$ set definieert.

  1. Afstandsberekening: De servers berekenen via Beaver-triplets geheim gedeelde cosinus-afstanden (benaderd via dot-producten) tussen de prompt van de gebruiker en alle documentembeddings.
  2. Bisection-iteratie: De gebruiker en servers wisselen interactie uit om een afstandsdrempel te verfijnen. In elke iteratie specificeert de gebruiker een drempel $d_k$. De servers gebruiken Distributed Comparison Functions (DCF's) om te tellen hoeveel documenten afstanden kleiner dan $d_k$ hebben.
  3. Drempelselectie: De gebruiker past $d_k$ aan op basis van de geretourneerde telling totdat het aantal documenten binnen de drempel dicht bij de doelwaarde $k$ ligt.
  4. Resultaatopvraging: Zodra de drempel is bepaald, genereren de servers een geheim gedeeld binair vector dat aangeeft welke documenten binnen de drempel vallen. De gebruiker haalt de indices van deze documenten op via Single-Server Private Information Retrieval (PIR).

• Veiligheidsmechanismen:

  • Privacy: Geheime deling zorgt ervoor dat geen enkele server de database of de prompt leert kennen.
  • Verdediging tegen Kwaadaardige Gebruikers: Om te voorkomen dat gebruikers te veel informatie extraheren, dwingt P2RAG strikte beperkingen af:
    • Het aantal bisection-iteraties is beperkt (waardoor de totale lekken van tellingen worden beperkt tot $O(\log^2 N)$).
    • De grootte van de uiteindelijke resultaatset is begrensd.
    • Verificatiemechanismen zorgen ervoor dat de gebruiker alleen indices ophaalt die overeenkomen met de afgesproken binaire vector, waardoor manipulatie van het zoekproces wordt voorkomen.

Belangrijkste Bijdragen

1. Ondersteuning voor Arbitraire Top-k: P2RAG is het eerste systeem dat efficiënt willekeurige $k$-waarden ondersteunt zonder het efficiëntieverlies dat wordt gezien bij op sortering gebaseerde benaderingen, waardoor het geschikt is voor scenario's met grote $k$ die nodig zijn voor moderne modellen met lange context.
2. Efficiënt Protocollontwerp: Door beveiligde sortering te vervangen door een interactieve bisection-methode met behulp van DCF's, reduceert P2RAG het aantal vergelijkingen aanzienlijk, wat de primaire bottleneck is in beveiligde protocollen.
3. Robuuste Veiligheid: Het systeem beschermt zowel de database van de data-eigenaar als de prompt van de gebruiker tegen semi-ehrlijke servers. Het introduceert ook specifieke beperkingen en verificatiestappen om informatielekken tegen kwaadaardige gebruikers strikt te begrenzen.
4. Implementatie en Evaluatie: De auteurs hebben P2RAG geïmplementeerd en de code vrijgegeven onder de Apache License 2.0.

Experimentele Resultaten
De auteurs hebben P2RAG geëvalueerd met behulp van BEIR-datasets (bijvoorbeeld trec-covid met ongeveer 171k documenten) en synthetische datasets.

• Nauwkeurigheid: P2RAG bereikt hoge computationele nauwkeurigheid. De recall blijft op 1,0 voor $k'$ variërend van 16 tot 1024, en relevantiescores geven aan dat de opgehaalde documenten over het algemeen relevant zijn voor de prompt.
• Prestaties: P2RAG toont aanzienlijke snelheidswinsten ten opzichte van het state-of-the-art systeem, PRAG.
  • Voor $k = 16$ is P2RAG 3,78× sneller.
  • Voor grotere $k$ (bijvoorbeeld $k=1024$) neemt de snelheidswinst toe tot 322×.
  • Het systeem schaalt lineair met het aantal documenten ($N$), maar wordt relatief sneller naarmate $k$ toeneemt, in tegenstelling tot PRAG dat lijdt aan efficiëntieverlies.
• Communicatie: Hoewel communicatie tussen servers honderden megabytes kan bereiken, is dit beheersbaar via hoog-breedbandige datacenterverbindingen. De communicatie tussen gebruiker en server blijft laag (vergelijkbaar met een paar standaardafbeeldingen).

Betekenis en Claims
Het artikel beweert dat P2RAG een kritieke kloof in privacybehoudende RAG adresseert: het onvermogen om grote $k$-waarden efficiënt te verwerken. De auteurs benadrukken dat, hoewel standaard niet-beveiligde RAG eenvoudiger en sneller is, P2RAG essentieel is voor hoog-risicodomeinen zoals gezondheidszorg, financiën en juridische diensten waar databeveiliging een strikte vereiste is. Het systeem stelt deze sectoren in staat om grote zoeksets te benutten (die de nauwkeurigheid van LLM's verbeteren) zonder de vertrouwelijkheid van propriëtaire databases of gebruikersvragen te compromitteren. De auteurs merken bescheiden op dat het systeem rust op de aanname van semi-ehrlijke, niet-colluderende servers en dat standaard niet-beveiligde RAG de keuze blijft wanneer privacy niet kritiek is.