PLR: Plackett-Luce for Reordering In-Context Learning Examples

Probleemstelling

In-Context Learning (ICL) stelt grote taalmodellen (LLMs) in staat om taken uit te voeren door een klein aantal voorbeelden (demonstraties) in de prompt te plaatsen, zonder dat de modelparameters worden bijgewerkt. Hoewel dit efficiënt is, is de prestatie van ICL vaak uiterst gevoelig voor de volgorde waarin deze voorbeelden worden gepresenteerd.

De uitdaging is dat het vinden van de optimale volgorde een zoekprobleem is in een ruimte van $n!$ mogelijke permutaties (waarbij $n$ het aantal voorbeelden is). Een exhaustieve zoektocht is onmogelijk voor zelfs maar een bescheiden aantal voorbeelden. Bestaande methoden vertrouwen vaak op heuristieken gebaseerd op modelvertrouwen (zoals entropie) of label-distributies. Deze methoden hebben echter beperkingen:

1. Ze vereisen vaak een eindige set van labels (via verbalizers), wat ze ongeschikt maakt voor open-ended generatie of wiskundig redeneren met onbegrensde output.
2. Ze zoeken vaak naar één enkele "beste" volgorde (punt-schatting), wat kwetsbaar kan zijn.
3. Ze kunnen rekenkundig duur zijn bij kleine $n$ door factoriële enumeratie.

Methodologie: PLR (Plackett–Luce for Reordering)

De auteurs stellen PLR voor, een probabilistische aanpak die de discrete zoektocht naar een permutatie vervangt door het leren van een kansverdeling over permutaties.

1. Het Model: Plackett–Luce (PL) Distributie

In plaats van één volgorde te zoeken, modelleert PLR de ruimte van permutaties met een Plackett–Luce-verdeling.

• PL-verdeling: Dit is een model dat een permutatie genereert als een sequentie van keuzes. Op elke positie $r$ in de volgorde wordt een item gekozen uit de resterende items met een kans evenredig met zijn gescoreerde waarde (logit).
• Mixture of PL: Om de beperkingen van een enkele PL-verdeling (zoals de "Independence of Irrelevant Alternatives" eigenschap, die interacties tussen items beperkt) te overwinnen, gebruiken de auteurs een mengsel van PL-verdelingen. Dit stelt het model in staat multimodale distributies te leren (d.w.z. meerdere verschillende, goed presterende volgorde-patronen tegelijkertijd).

2. Sampling: De Gumbel Trick

Om efficiënt te kunnen bemonsteren uit deze verdeling, gebruiken de auteurs de Gumbel perturb-and-sort methode:

1. Voor elk item $i$ wordt Gumbel-ruis $g_i$ getrokken.
2. De gesorteerde scores worden berekend als $s_i = \theta_i + g_i$, waarbij $\theta_i$ de leerbare logit is.
3. Items worden gesorteerd op basis van deze verstoorde scores.
   Dit transformeert een complexe sequentiële sampling-procedure in één enkele sorteeroperatie, wat zeer efficiënt en numeriek stabiel is.

3. Trainingsalgoritme

Het proces is iteratief en lijkt op Evolutionary Algorithms of Cross-Entropy Method:

1. Initialisatie: Start met een uniforme verdeling (alle logit-waarden gelijk).
2. Sampling: Bemonster een batch van permutaties via de Gumbel-trick.
3. Evaluatie: Evalueer elke bemonsterde volgorde op een trainingsset (of validatieset) met een taak-specifieke metriek (bijv. nauwkeurigheid).
4. Selectie: Behoud alleen de "elite" (hoogst scorende) permutaties.
5. Update: Pas de parameters van de PL-verdeling aan om de kansmassa te verschuiven naar deze elite-permutaties. De auteurs stellen drie update-methodes voor:
   • EMA (Exponential Moving Average): Een heuristische update gebaseerd op de gemiddelde rang van items in de elite-set.
   • MLE (Maximum Likelihood Estimation): Het maximaliseren van de log-waarschijnlijkheid van de elite-permutaties.
   • EM (Expectation-Maximization): Voor het mengsel van PL-verdelingen, waarbij verantwoordelijkheden worden toegewezen aan verschillende componenten.
6. Iteratie: Herhaal tot convergentie en selecteer de beste gevonden volgorde op een aparte validatieset.

Belangrijkste Bijdragen

1. Conceptueel: Introductie van PLR als een distributiegebaseerde aanpak voor ICL-volgorde. In tegenstelling tot eerdere methoden die afhankelijk zijn van een eindige labelruimte, is PLR label-ruimte onafhankelijk en werkt het ook voor open-ended generatie en numeriek redeneren.
2. Algoritmisch: Een efficiënt iteratief algoritme dat gebruikmaakt van Gumbel-perturbaties voor sampling en drie strategieën voor parameterupdate (EMA, MLE, EM) biedt.
3. Experimenteel: Uitgebreide evaluatie op classificatie- en redeneringsbenchmarks die aantoont dat PLR consistent beter presteert dan bestaande baselines.

Resultaten

De auteurs evalueerden PLR op diverse benchmarks (MR, SST-5, TREC, AG News, SUBJ) en wiskundige redeneringstaken (GSM8K, DeepMath, Math500) met modellen zoals Qwen2.5-7B en Llama3.1-8B.

• Classificatie: PLR-varianten (vooral PLR-EMA en PLR-1) presteerden consistent beter dan statische volgorde, random sampling (Top-K), en methoden gebaseerd op entropie (LocalE/GlobalE) of label-distributie (PDO, DEmO). De prestatieverbetering was het grootst bij een hoger aantal voorbeelden ($k \ge 8$), waar de zoekruimte te groot wordt voor heuristieken.
• Redeneren: Op wiskundige taken, waar label-gebaseerde methoden niet werken (vanwege onbegrensde antwoorden), overtrof PLR de "Top-K" en "Static" baselines aanzienlijk. Dit bewijst dat het leren van een distributie over volgorde effectief is voor complexe redeneertaken.
• Ablaties:
  • Een klein mengsel van componenten (bijv. $K=4$) bleek voldoende om de dominante patronen te vangen; grotere mengsels leverden afnemende meerwaarde op.
  • Er is een sterke monotone relatie gevonden tussen de geleerde waarschijnlijkheid van een permutatie en de werkelijke testnauwkeurigheid: hogere waarschijnlijkheid correleerde met betere prestaties.

Significantie

Dit paper introduceert een fundamentele verschuiving in hoe we omgaan met ICL-volgorde: van het zoeken naar één "juiste" volgorde naar het leren van een kansverdeling over de zoekruimte.

• Generalisatie: Het is de eerste methode die robuust werkt voor zowel gesloten classificatie als open-ended redeneren zonder afhankelijkheid van een vooraf gedefinieerde labelset.
• Efficiëntie: Door gebruik te maken van de Plackett-Luce-verdeling en Gumbel-sampling, wordt de enorme zoekruimte van $n!$ permutaties efficiënt verkend zonder exhaustieve enumeratie.
• Toekomstperspectief: De auteurs suggereren dat deze probabilistische benadering kan worden uitgebreid naar andere prompt-engineering problemen, zoals het gelijktijdig selecteren en ordenen van voorbeelden of het optimaliseren van instructietekst.

Kortom, PLR biedt een wiskundig onderbouwde, schaalbare en effectieve oplossing voor een van de meest kritieke maar vaak verwaarloosde aspecten van prompt engineering: de volgorde van in-context voorbeelden.