Best-of-$\infty$ -- Asymptotic Performance of Test-Time LLM Ensembling

Dit onderzoek analyseert de asymptotische prestaties van best-of-$N$ ensembling met meerderheidsstemming voor grote taalmodellen, introduceert een adaptief generatieschema om de inferentiekosten te optimaliseren en toont aan dat gewogen ensembles van meerdere modellen via een gemengd-geheelgetallig lineair programma superieure resultaten kunnen behalen.

De kern

De "Beste van Oneindig": Hoe je een team van AI's slimmer maakt dan één super-AI

Stel je voor dat je een heel moeilijk wiskundeprobleem moet oplossen. Je hebt een slimme vriend (een Large Language Model of LLM) die je kan helpen. Maar soms maakt die vriend een fout, of twijfelt hij. Wat doe je dan? Je vraagt niet aan één vriend, maar aan veel vrienden om hetzelfde probleem op te lossen. Vervolgens kijk je welk antwoord het vaakst voorkomt. Dat noemen onderzoekers "Best-of-N": je vraagt N keer, en kiest de winnaar.

Deze paper, geschreven door Junpei Komiyama en zijn team, gaat over wat er gebeurt als je dit idee tot het uiterste drijft: Best-of-∞ (Beste van Oneindig).

Hier is de uitleg in simpele taal, met wat creatieve vergelijkingen:

1. Het probleem: Oneindig is onmogelijk (maar wel een mooi doel)

Als je oneindig vaak zou vragen aan je AI-vriend, zou je uiteindelijk altijd het juiste antwoord krijgen. Het is alsof je een munt gooit: als je oneindig vaak gooit, zal de verdeling van kop en munt precies 50/50 zijn. Bij een AI betekent "oneindig vragen" dat je de echte "meest waarschijnlijke" gedachte van de machine vindt.

Maar in het echte leven heb je geen oneindig budget. Je kunt niet 10.000 keer vragen aan een AI; dat kost te veel tijd en geld. Dus, hoe krijg je dat "oneindig goede" resultaat met een beperkt budget?

2. De oplossing: De slimme "Stop-Wacht" (Adaptief Sampling)

De auteurs bedachten een slimme manier om te stoppen. In plaats van vast te houden aan een getal (bijv. "vraag altijd 10 keer"), laten ze de AI stoppen zodra ze zeker zijn.

• De analogie: Stel je voor dat je in een lokaal zit met honderden mensen en je vraagt: "Wie is de burgemeester?"
  • Als 99% direct "Jan" roept, hoef je niet langer te wachten. Je stopt direct.
  • Als de menigte verdeeld is tussen "Jan", "Piet" en "Klaas", blijf je luisteren tot er duidelijk een meerderheid ontstaat.
• De techniek: De paper gebruikt een wiskundige methode (Bayesiaanse statistiek) om te berekenen: "Hoe groot is de kans dat het antwoord dat we nu hebben, ook echt het juiste is?" Zodra die kans hoog genoeg is, stopt de computer. Dit bespaart enorm veel tijd op makkelijke vragen, terwijl het genoeg tijd neemt voor moeilijke vragen.

3. De kracht van het team: Een mix van verschillende AI's

De paper gaat nog een stap verder. Wat als je niet één AI gebruikt, maar een team van verschillende AI-modellen?

• Het idee: Soms is AI A heel goed in wiskunde, maar AI B is beter in logica. Als je ze samen laat werken, vullen ze elkaars zwaktes aan.
• De uitdaging: Hoe verdeel je de stemmen? Als AI A 10 keer antwoordt en AI B 1 keer, wie telt dan meer?
• De oplossing: De auteurs hebben een wiskundige formule (een zogenaamd "Mixed-Integer Linear Program") bedacht om de perfecte verdeling te vinden. Het is alsof je een coach bent die precies weet hoeveel minuten elke speler op het veld moet staan om het team te laten winnen. Ze hebben bewezen dat je met de juiste mix van AI's een team kunt maken dat slimmer is dan de slimste individuele AI in het team.

4. Wat hebben ze bewezen?

Ze hebben dit getest met echte, moeilijke wiskundeproblemen (zoals de Amerikaanse wiskunde-olympiade voor middelbare scholieren).

• Resultaat 1: Hun "slimme stop-methode" bereikte bijna hetzelfde hoge niveau als "oneindig vragen", maar gebruikte 2 tot 5 keer minder rekenkracht.
• Resultaat 2: Een team van verschillende AI-modellen, met de juiste gewichten, deed het beter dan welke enkele AI ook. Een zwakkere AI kon helpen door een specifiek type fout te voorkomen die de sterkere AI maakte.

Samenvatting in één zin

In plaats van blindelings te gokken of oneindig te blijven rekenen, gebruiken deze onderzoekers slimme statistiek om te weten wanneer ze genoeg hebben, en ze bouwen een perfect afgestemd team van AI's zodat ze samen slimmer zijn dan de som der delen.

Waarom is dit belangrijk?
Het betekent dat we in de toekomst minder dure computers nodig hebben om super-slimme antwoorden te krijgen, en dat we door verschillende AI's te combineren, problemen kunnen oplossen die voor één AI te moeilijk zijn. Het is de weg naar efficiëntere en slimmere kunstmatige intelligentie.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Best-of-∞– Asymptotic Performance of Test-Time LLM Ensembling" in het Nederlands.

Probleemstelling

Grote Taalmodellen (LLMs) presteren vaak beter bij complexe redeneertaken wanneer er meerdere antwoorden worden gegenereerd en de beste wordt geselecteerd (de "Best-of-N" of BoN strategie). Een veelgebruikte selectiemethode is meerderheidsstemming (majority voting), waarbij het meest voorkomende antwoord wordt gekozen.

De theoretische limiet van deze aanpak is Best-of-∞: het genereren van oneindig veel samples totdat de meerderheid met absolute zekerheid is vastgesteld. Hoewel dit de maximale nauwkeurigheid oplevert, is het in de praktijk onuitvoerbaar vanwege de oneindige rekenkosten. De uitdaging is om deze asymptotische prestatie te benaderen met een beperkt, maar efficiënt, test-tijd budget. Daarnaast is het onbekend hoe men meerdere LLMs het beste kan combineren (ensemble) om deze limiet te bereiken, en welke wegingen hierbij optimaal zijn.

Methodologie

De auteurs stellen twee hoofdcomponenten voor om dit probleem op te lossen:

1. Adaptieve Sampling (Best-of-∞ benadering)
In plaats van een vast aantal $N$ samples te genereren, wordt een adaptieve methode voorgesteld die stopt zodra er voldoende statistisch bewijs is dat het huidige meest voorkomende antwoord de ware meerderheid is.

• Bayesiaanse Modellering: De auteurs gebruiken een Dirichlet-proces prior ($DP(H, \alpha)$) om de onbekende verdeling van antwoorden te modelleren. Dit is essentieel omdat het aantal mogelijke antwoorden (de support) voor LLMs vaak onbekend en potentieel oneindig is.
• Stop-criterium: De methode gebruikt de Bayes-factor (BF) om de hypothese te testen of het meest frequente antwoord de ware meerderheid is ($H_1$) versus het tegendeel ($H_0$).
• Algoritme: Het generatieproces stopt wanneer de Bayes-factor een vooraf bepaald drempelwaarde $B$ bereikt of wanneer het maximale aantal samples $N_{max}$ is bereikt. Dit zorgt ervoor dat makkelijke problemen snel worden opgelost (weinig samples) en moeilijke problemen meer resources krijgen, waardoor de totale token-kost wordt geminimaliseerd bij gelijke nauwkeurigheid.

2. Geoptimaliseerde LLM Ensembles
Het paper breidt het framework uit naar het combineren van meerdere LLMs met verschillende wegingen ($w$).

• Het Optimisatie Probleem: Het vinden van de optimale wegingen voor een ensemble is een niet-concaaf probleem voor een eindige $N$. Echter, in de limiet van $N \to \infty$ wordt het probleem anders.
• MILP Formulering: De auteurs bewijzen dat het maximaliseren van de nauwkeurigheid in de Best-of-∞ limiet kan worden geformuleerd als een Mixed-Integer Linear Programming (MILP) probleem.
  • De ruimte van mogelijke gewichten wordt opgedeeld in polytoepen (gebieden waar een bepaald antwoord de meerderheid wint).
  • Het doel is om een gewichtvector $w$ te vinden die het grootste aantal polytoepen (d.w.z. correcte antwoorden) dekt.
  • Dit maakt het mogelijk om met standaard solvers (zoals HiGHS) de proefbaar optimale wegingen te berekenen, wat eerder als computationeel onhaalbaar werd beschouwd voor dit type probleem.
• Max-Margin Oplossing: Om de robuustheid voor eindige $N$ te verbeteren, kiezen de auteurs voor een "max-margin" oplossing, wat betekent dat ze een gewicht kiezen dat diep in het centrum van het optimale gebied ligt, waardoor het minder gevoelig is voor kleine variaties.

Belangrijkste Bijdragen

1. Best-of-∞ Theorie en Praktijk: Definities en een bewijs van consistentie voor de Best-of-∞ prestatie, gekoppeld aan een praktisch adaptief algoritme dat deze limiet benadert met een eindig budget.
2. Adaptieve Sampling: Een nieuwe methode gebaseerd op Dirichlet-processen en Bayes-factoren om het aantal samples per vraag dynamisch aan te passen, wat leidt tot aanzienlijke besparingen in rekenkracht.
3. Optimale Ensemble Weging: De eerste computerefficiente methode (via MILP) om de proefbaar optimale wegingen te vinden voor een ensemble van LLMs in de context van meerderheidsstemming. Dit toont aan dat het mengen van suboptimale modellen vaak beter presteert dan het kiezen van het beste enkele model.
4. Grootschalige Evaluatie: Een ongeëvenaard dataset van gegenereerde antwoorden (meer dan 100.000 samples over 11 LLMs en 4 zware redeneerbenchmarks), wat een significant grotere schaal is dan eerdere werken.

Resultaten

De experimenten werden uitgevoerd op zware redeneertaken (AIME2024/2025, GPQA-DIAMOND, MATH500) met 11 verschillende open-weight LLMs.

• Efficiëntie van Adaptieve Sampling: De adaptieve methode bereikt dezelfde nauwkeurigheid als een vaste BoN-methode (bijv. $N=100$) met slechts een fractie van de samples (gemiddeld $N \approx 10$). Dit resulteert in een 2x tot 5x reductie in het totale aantal gegenereerde tokens.
• Superioriteit van Ensembles: Geoptimaliseerde ensembles presteerden consequent beter dan het beste enkele model.
  • Voorbeeld: Op de AIME2025 dataset had GPT-OSS-20B een Best-of-∞ nauwkeurigheid van 90,0% en Nemotron-Nano-9B-v2 van 73,0%. Het geoptimaliseerde ensemble bereikte echter 93,3%.
• Vergelijking met Andere Methodes: In een Best-of-5 setting overtrof meerderheidsstemming methoden zoals "LLM-as-a-judge", beloningsmodellen (Reward Models) en zelf-zekerheid (self-certainty).
• Generalisatie: De geoptimaliseerde gewichten die op AIME2024 werden getraind, transferden goed naar AIME2025, waarbij het ensemble in 64% van de gevallen de sterkste individuele modellen overtrof.

Betekenis en Impact

Dit paper biedt een fundamentele doorbraak in het begrijpen en optimaliseren van test-tijd computation voor LLMs:

1. Theoretisch Inzicht: Het verlegt de grens van "Best-of-N" naar een wiskundig beheersbare "Best-of-∞" limiet, waarbij wordt aangetoond dat optimale ensemble-wegingen via lineaire programmering kunnen worden gevonden.
2. Kostenefficiëntie: De adaptieve sampling biedt een praktische manier om de "diminishing returns" van het genereren van extra samples te omzeilen, waardoor de kosten voor het bereiken van hoge nauwkeurigheid drastisch dalen.
3. Synergie: Het bewijst dat het combineren van diverse modellen (zelfs zwakkere modellen) via een slimme weging superieur is aan het vertrouwen op één enkel krachtig model. Dit opent de deur voor kosteneffectieve "mixture-of-experts" systemen zonder extra training.
4. Open Science: De auteurs publiceren een enorme dataset van gegenereerde antwoorden, wat een waardevolle resource is voor toekomstig onderzoek naar test-tijd schaling en ensemble methoden.

Kortom, het paper toont aan dat door slimme adaptieve sampling en wiskundig geoptimaliseerde ensemble-wegingen, LLM-systemen hun theoretische maximale prestaties kunnen benaderen met een haalbare en efficiënte rekeninvestering.