MASPOB: Bandit-Based Prompt Optimization for Multi-Agent Systems with Graph Neural Networks

MASPOB is een nieuwe, steekproefefficiënte framework dat bandit-algoritmen en Graph Neural Networks combineert om promptoptimalisatie voor multi-agent systemen te verbeteren door de zoekruimte te reduceren en structurele koppelingen te modelleren, wat resulteert in state-of-the-art prestaties.

De kern

Stel je voor dat je een groot, complex project moet uitvoeren, zoals het bouwen van een huis of het organiseren van een grote bruiloft. Je hebt niet één persoon nodig, maar een heel team van specialisten: een architect, een timmerman, een elektricien en een kok. In de wereld van kunstmatige intelligentie noemen we dit een Multi-Agent Systeem (MAS). Elk "agent" is een slimme AI die een specifieke taak heeft.

Het probleem is echter: hoe zorg je ervoor dat deze teamleden perfect samenwerken? Het antwoord ligt in hun prompts (de instructies of "scripts" die je aan elke AI geeft). Als de instructie aan de timmerman vaag is, kan dat de elektricien in de war brengen, en uiteindelijk wordt het hele huis slecht gebouwd.

Deze paper introduceert MASPOB, een slimme methode om die instructies automatisch te verbeteren. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het Grote Dilemma: Te duur om te proberen

In het echte leven (bijvoorbeeld in de zorg of financiën) mag je het "blauwdruk" van het team niet zomaar veranderen. Je kunt niet elke dag de architect vervangen of de volgorde van de bouwstappen wijzigen; dat is te riskant en te duur. Je kunt alleen de instructies (prompts) van de individuele teamleden aanpassen.

Maar er is een probleem:

• Het testen van een nieuwe instructie is duur (het kost tijd en geld om de hele AI-teamwerking te laten draaien).
• Er zijn zoveel mogelijke combinaties van instructies dat je ze niet allemaal kunt uitproberen (dat is als zoeken naar een naald in een hooiberg, maar dan met een miljard hooibergen).
• Als je de instructie van de timmerman verandert, verandert de input voor de elektricien. Alles hangt met elkaar samen.

2. De Oplossing: MASPOB (De Slimme Teamleider)

MASPOB is als een super-slimme teamleider die weet hoe hij met een beperkt budget (weinig testmomenten) het beste team kan vinden. Het doet dit met drie trucs:

Truc 1: De "Grafische Mindmap" (GNN)

Stel je voor dat je een team hebt waarbij de timmerman altijd eerst moet werken voordat de elektricien begint. Als je de instructie van de timmerman aanpast, moet je weten hoe dat de elektricien beïnvloedt.

• Hoe MASPOB het doet: Het gebruikt een Graph Neural Network (GNN). Denk hieraan als een levendige, interactieve mindmap. Deze kaart ziet precies wie met wie praat in het team. In plaats van de AI's als losse eilanden te zien, ziet deze kaart de verbindingen. Als de timmerman zijn instructie krijgt, "weet" de kaart direct hoe dat de elektricien beïnvloedt. Dit helpt de teamleider om slimme voorspellingen te doen zonder alles eerst daadwerkelijk te hoeven testen.

Truc 2: De "Gokker met Verstand" (Bandits & UCB)

Stel je voor dat je in een casino zit, maar je mag maar 50 keer gokken voordat je geld op is. Je wilt winnen, maar je weet niet welke machine het beste uitkeert.

• Hoe MASPOB het doet: Het gebruikt een techniek uit de wiskunde genaamd Bandits. Het balanceert tussen twee dingen:
  1. Exploitatie: Gokken op de machine die tot nu toe het meeste heeft gewonnen (de instructies die al goed lijken).
  2. Exploratie: Gokken op een machine die je nog niet vaak hebt geprobeerd, omdat het misschien een verrassende winnaar is (onzekerheid wegnemen).
     MASPOB gebruikt een formule (UCB) om te beslissen: "Is het de moeite waard om dit nieuwe instructiepaar te testen, of moeten we doorgaan met wat we al weten?" Zo verspillen ze geen enkele test.

Truc 3: De "Stap-voor-Stap" Benadering (Coördinaat Ascent)

Stel je voor dat je een combinatie van 10 sleutels moet vinden om een slot te openen. Als je alle 10 tegelijk probeert te veranderen, is dat onmogelijk.

• Hoe MASPOB het doet: Het verandert niet alles tegelijk. Het houdt 9 instructies vast en verandert alleen die van de timmerman. Kijk of het beter werkt. Dan houdt het de timmerman vast en verandert het de instructie van de elektricien. Het werkt als een trap: je loopt stap voor stap omhoog naar het hoogste punt (de beste prestatie), in plaats van te proberen in één sprong naar de top te komen. Dit maakt het zoeken veel sneller en makkelijker.

Waarom is dit belangrijk?

In de echte wereld kunnen we vaak niet zeggen: "Laten we het hele proces van ziekenhuisbezoek of belastingaangifte opnieuw ontwerpen." Dat is te gevaarlijk. Maar we kunnen wel de instructies aan de AI's die die processen uitvoeren, optimaliseren.

MASPOB bewijst dat je, door slim te kijken naar hoe de teamleden met elkaar verbonden zijn en door je "gokken" (tests) verstandig in te zetten, de prestaties van een AI-team enorm kunt verbeteren zonder het onderliggende proces te veranderen. Het is alsof je een goedlopend orkest niet hoeft te herschikken, maar alleen de partituren van de muzikanten iets aanpast zodat ze perfect in harmonie spelen.

Kortom: MASPOB is de slimme regisseur die met weinig repetities weet precies welke instructies nodig zijn om een team van AI's tot een meesterwerk te laten komen.

Technische samenvatting

Probleemstelling

Grote Taalmodellen (LLMs) worden steeds vaker ingezet als cognitieve ruggengraat van Multi-Agent Systemen (MAS) om complexe workflows te coördineren. Hoewel veel real-world toepassingen (zoals medische protocollen of financiële audits) workflows gebruiken die door experts zijn gevalideerd en niet gewijzigd mogen worden, is de prestatie van deze systemen extreem gevoelig voor de input-prompten van de individuele agenten.

Het optimaliseren van deze prompten in een MAS-omgeving vormt echter een uitdagend combinatorisch probleem met drie kernmoeilijkheden:

1. Hoge Evaluatiekosten: Het evalueren van een prompt-configuratie vereist het volledig uitvoeren van de multi-agent workflow, wat vaak meerdere LLM-aanroepen kost. Dit beperkt het beschikbare "budget" aan evaluaties sterk.
2. Topologie-geïnduceerde Koppeling: Veranderingen in een upstream prompt veranderen de input-distributie voor downstream agenten. Hierdoor is het optimalisatieprobleem niet-scheidbaar; het optimaliseren van agenten onafhankelijk van elkaar leidt tot instabiliteit.
3. Combinatorische Explosie: De gezamenlijke zoekruimte van alle mogelijke prompt-combinaties groeit exponentieel met het aantal agenten, waardoor een exhaustieve zoektocht onmogelijk is.

Bestaande methoden (zoals OPRO of MIPRO) negeren vaak de structurele afhankelijkheden tussen agenten of zijn niet sample-efficiënt genoeg voor deze strenge budgetten.

Methodologie: MASPOB

De auteurs introduceren MASPOB (Multi-Agent System Prompt Optimization via Bandits), een framework dat drie componenten combineert om bovenstaande uitdagingen aan te pakken:

1. Topologie-bewuste Surrogaatmodel (GNN):

   • De MAS-workflow wordt gemodelleerd als een gerichte acyclische graaf (DAG), waarbij agenten knopen zijn en informatiestromen randen.
   • Een Graph Neural Network (GNN), specifiek een Graph Attention Network (GAT), wordt gebruikt als surrogaatmodel.
   • Dit model encodeert de workflow-topologie expliciet en leert representaties van prompt-semantiek die rekening houden met de interacties tussen agenten. Hierdoor kan het de impact van promptwijzigingen op het totale systeem voorspellen zonder de workflow fysiek uit te voeren.

2. Bandit-gebaseerde Exploratie-Exploitatie:

   • Het optimalisatieprobleem wordt geformuleerd als een contextuele bandit (contextual bandit).
   • Er wordt gebruikgemaakt van LinUCB (Linear Upper Confidence Bound) om een balans te vinden tussen het uitbuiten van veelbelovende prompt-combinaties en het verkennen van onzekere gebieden.
   • De onzekerheid wordt gekwantificeerd via een informatie-matrix in de geleerde representatieruimte. De acquisitie-functie combineert de voorspelde prestatie (exploitatie) met een onzekerheidsbonus (exploratie), wat zorgt voor een efficiënte toewijzing van het beperkte evaluatiebudget.

3. Coördinaatstijgende Zoekstrategie (Coordinate Ascent):

   • Om de combinatorische complexiteit te reduceren, wordt de globale zoektocht opgesplitst in een reeks univariate sub-problemen.
   • In plaats van alle agenten tegelijk te optimaliseren, wordt de UCB-functie gemaximaliseerd door achtereenvolgens de prompt van elke agent te optimaliseren terwijl de andere vastgehouden worden.
   • Dit verlaagt de complexiteit per iteratie van exponentieel ($O(\prod |P_i|)$) naar lineair ($O(\sum |P_i|)$), waarbij de GNN en UCB zorgen voor de noodzakelijke koppeling tussen de agenten.

Belangrijkste Bijdragen

• Formalisatie: Het paper formaliseert prompt-optimalisatie voor MAS als een budget-beperkt black-box optimalisatieprobleem met topologie-geïnduceerde koppeling en een discrete combinatorische zoekruimte.
• Novel Framework: MASPOB is het eerste framework dat GNN's combineert met bandit-methoden (UCB) en coördinaatstijging om sample-efficiënte optimalisatie te bereiken in complexe, vaststaande workflows.
• Empirisch Bewijs: Uitgebreide experimenten tonen aan dat MASPOB state-of-the-art prestaties levert, consistent beter presterend dan bestaande baselines zoals AFlow, MIPRO, en single-agent optimalisatie-methoden.

Resultaten

MASPOB werd geëvalueerd op zes benchmarks die variëren van vraag-antwoord (HotpotQA, DROP), code-generatie (HumanEval, MBPP) tot wiskundig redeneren (GSM8K, MATH).

• Prestatie: MASPOB behaalde de beste resultaten op alle zes de benchmarks. In vergelijking met de IO-baseline (Input-Output zonder optimalisatie) leidde dit tot een gemiddelde verbetering van 12,02%. Het presteerde ook significant beter dan geavanceerde multi-agent baselines zoals AFlow (+2,06%) en MIPRO (+1,71%).
• Sample-efficiëntie: Onder een strikt budget van slechts 50 validatie-evaluaties, convergeerde MASPOB sneller naar een optimaal punt dan concurrenten.
• Robuustheid: De methode bleek effectief op zowel eenvoudige als complexe workflow-topologieën (met meer agenten en vertakkingen).
• Ablatie-studies:
  • Het vervangen van de GNN door een standaard MLP (Multi-Layer Perceptron) resulteerde in een prestatieverlies van gemiddeld 2,31%, wat aantoont dat het expliciet modelleren van de workflow-topologie cruciaal is.
  • Het gebruik van een lineaire onzekerheidsschatting (LinUCB) bleek superieur aan neurale onzekerheidsschattingen in dit data-schaarse regime.

Significantie

Deze studie is significant omdat het een praktische oplossing biedt voor een veelvoorkomend probleem in de industrie: het verbeteren van de prestaties van gevalideerde, complexe multi-agent systemen zonder de workflow-structuur zelf te wijzigen.

In sectoren zoals gezondheidszorg en financiën, waar workflows streng gereguleerd zijn en wijzigingen kostbare her-validaties vereisen, biedt MASPOB een veilige en efficiënte route om systemen te optimaliseren. Door de structuur van het systeem te benutten via GNN's en de zoekruimte intelligent te navigeren via bandits, maakt het het mogelijk om substantiële winsten te boeken in redeneervermogen en outputkwaliteit met een minimaal aantal dure LLM-evaluaties. Dit onderstreept dat prompt-optimalisatie op zichzelf, mits correct uitgevoerd, een krachtige hefboom kan zijn voor multi-agent systemen.