Thompson Sampling via Fine-Tuning of LLMs

Die Arbeit stellt ToSFiT vor, einen skalierbaren Ansatz zur Bayesschen Optimierung in großen diskreten Räumen, der durch Feinabstimmung von Large Language Models die Notwendigkeit der Maximierung von Akquisitionsfunktionen umgeht und dabei sowohl hohe Sample-Effizienz als auch Recheneffizienz in verschiedenen Anwendungsbereichen erreicht.

Das Wesentliche

Das große Problem: Die Suche im Dunkeln

Stellen Sie sich vor, Sie sind ein Schatzsucher in einem riesigen, undurchdringlichen Dschungel (dem „Suchraum"). Ihr Ziel ist es, den einen perfekten Ort zu finden, an dem der größte Goldschatz (die beste Lösung) liegt.

Das Problem: Der Dschungel ist so riesig, dass Sie ihn nicht Schritt für Schritt abgehen können. Es gibt keine Landkarte mit Straßen (keine „Gradienten"), die Ihnen sagen, wohin Sie laufen müssen. Und jedes Mal, wenn Sie einen neuen Ort untersuchen, kostet das viel Zeit und Geld (z. B. ein teures Laborexperiment oder das Testen eines neuen Medikamentenmoleküls).

Frühere Methoden (wie „Bayesian Optimization") waren wie ein sehr vorsichtiger Navigator. Er sagte: „Lass uns hierhin gehen, aber wir müssen erst eine komplizierte Rechnung machen, um sicherzustellen, dass es der beste Ort ist." In einem riesigen Dschungel ist diese Rechnung aber unmöglich durchzuführen – sie würde ewig dauern.

Die Lösung: TOSFIT – Der kluge Navigator mit Intuition

Die Autoren dieses Papiers haben eine neue Methode namens TOSFIT (Thompson Sampling via Fine-Tuning) entwickelt. Sie funktioniert wie folgt:

Statt die komplizierte Rechnung zu machen, nutzen sie einen KI-Sprachmodell-Assistenten (ein Large Language Model, LLM), der bereits viel über die Welt weiß (durch sein Training).

Die Metapher: Der erfahrene Koch

Stellen Sie sich den KI-Assistenten als einen erfahrenen Koch vor, der schon tausende Rezepte gesehen hat.

1. Der Start (Vorwissen): Wenn Sie ihn bitten, ein neues Rezept zu erfinden, nutzt er sofort sein Wissen aus der Vergangenheit. Er weiß, dass Salz und Pfeffer gut zusammenpassen. Er muss nicht bei Null anfangen.
2. Der Test (Belohnung): Sie lassen ihn ein Gericht kochen und probieren es. Es schmeckt gut, aber nicht perfekt.
3. Die Anpassung (Fine-Tuning): Anstatt den Koch zu feuern oder ihm eine neue, komplizierte Anleitung zu geben, feinjustieren Sie ihn. Sie sagen ihm: „Nächstes Mal mach das Salz etwas weniger, aber mehr Knoblauch." Der Koch passt sich langsam an Ihre spezifischen Vorlieben an.
4. Der Trick: Der Koch generiert nicht nur ein Rezept, sondern er wird so trainiert, dass er genau die Rezepte vorschlägt, die mit hoher Wahrscheinlichkeit am besten schmecken werden. Er lernt quasi, „wo der Goldschatz liegt", indem er seine eigenen Ideen immer besser auf die Rückmeldungen abstimmt.

Warum ist das so clever?

In der Wissenschaft gibt es zwei Hauptstrategien, um den besten Ort zu finden:

1. Ausprobieren (Exploration): Gehen Sie an unbekannte Orte, um neue Dinge zu entdecken.
2. Nutzen (Exploitation): Gehen Sie dorthin, wo Sie schon wissen, dass es gut ist.

Frühere KI-Methoden waren oft zu starr oder zu chaotisch. TOSFIT nutzt einen cleveren mathematischen Trick (basierend auf dem „Thompson Sampling"), der dem Koch sagt: „Sei neugierig, aber basiere deine Neugier auf dem, was du schon weißt."

• Der Vorteil: Der Koch (die KI) muss nicht erst eine riesige Landkarte zeichnen. Er nutzt seine Intuition, um direkt gute Kandidaten zu generieren.
• Die Anpassung: Wenn sich herausstellt, dass ein Kandidat (z. B. ein neues Protein oder ein Code-Schnipsel) gut funktioniert, wird der Koch sofort ein bisschen „umprogrammiert", um noch mehr davon zu produzieren.

Wo wird das angewendet?

Die Autoren haben TOSFIT an drei sehr unterschiedlichen Aufgaben getestet:

1. FAQ-Verbesserung: Der KI wurde beigebracht, Antworten auf häufig gestellte Fragen so zu formulieren, dass sie für Menschen am verständlichsten sind.
2. Protein-Suche: Der Dschungel hier ist gigantisch. Es gibt mehr mögliche Aminosäure-Kombinationen für Proteine als Atome im Universum. TOSFIT half, stabile Proteine zu finden, die als Medikamente dienen könnten.
3. Quantencomputer-Design: Der KI wurde beigebracht, komplexe Schaltungen für Quantencomputer zu entwerfen, die Energie sparen.

Das Ergebnis

TOSFIT ist wie ein Super-Navigator.

• Es ist schneller als alle anderen Methoden, weil es keine unnötigen Rechnungen anstellt.
• Es ist sparsamer, weil es mit weniger Versuchen (weniger teuren Experimenten) zum Ziel kommt.
• Es ist intelligent, weil es das Vorwissen der KI nutzt und es Schritt für Schritt perfektioniert.

Zusammenfassend: TOSFIT nimmt einen klugen KI-Assistenten, gibt ihm eine Aufgabe, und lässt ihn durch ständiges Üben und Anpassen lernen, wie man in einem riesigen, unbekannten Dschungel den besten Schatz findet – ohne dabei die Zeit für eine vollständige Landkarte zu verschwenden.

Technische Zusammenfassung

Titel: Thompson Sampling via Fine-Tuning of LLMs (TOSFIT)

Autoren: Nicolas Menet, Aleksandar Terzi´c, Michael Hersche, Andreas Krause, Abbas Rahimi
Veröffentlicht bei: ICLR 2026

---

1. Problemstellung

Bayesische Optimierung (BO) ist ein etabliertes Framework für die Optimierung teurer, schwarzer Kasten-Funktionen, insbesondere in Szenarien mit begrenzten Evaluierungen. Das Hauptproblem besteht darin, BO auf große, unstrukturierte diskrete Räume (z. B. Aminosäuresequenzen, Quantenschaltkreise, Textgenerierung) zu skalieren.

• Herausforderung: Herkömmliche BO-Methoden (wie Upper Confidence Bound oder Thompson Sampling) erfordern die Maximierung einer Akquisitionsfunktion, um den nächsten Kandidaten zu wählen. In kontinuierlichen Räumen kann dies durch Gradientenabstieg gelöst werden. In großen diskreten Räumen fehlen jedoch Gradienten, und eine exhaustive Suche ist aufgrund der kombinatorischen Explosion unmöglich (z. B. übersteigt der Raum von 100 Aminosäuren die Anzahl der Atome im Universum).
• Limitierung bestehender Ansätze: Methoden wie In-Context Learning (z. B. FIBO) oder evolutionäre Suchalgorithmen sind oft ineffizient in der Stichprobennutzung oder skalieren schlecht mit der Anzahl der Iterationen, da sie den Kontext speichern müssen.

2. Methodik: TOSFIT

Die Autoren schlagen TOSFIT (Thompson Sampling via Fine-Tuning) vor, eine skalierbare Alternative, die die Maximierung der Akquisitionsfunktion umgeht, indem sie die Wahrscheinlichkeit der Maximalität (Probability of Maximality, PoM) direkt durch ein Large Language Model (LLM) parametrisiert.

Kernkonzept:
Statt einen Kandidaten durch Maximierung einer Akquisitionsfunktion auszuwählen, wird das LLM so angepasst, dass seine Ausgabe direkt einer Stichprobe aus der PoM-Verteilung entspricht. Dies wird als Thompson Sampling interpretiert.

Algorithmische Schritte:

1. Initialisierung: Ein vortrainiertes, prompt-bedingtes LLM wird als Start-Policy ($\pi_\theta$) verwendet. Dies nutzt das Vorwissen des Modells (z. B. Grammatik, chemische Regeln).
2. Gaussian Process (GP) Modell: Ein GP wird verwendet, um die Reward-Funktion zu modellieren. Um Skalierbarkeit zu gewährleisten, wird ein linearer Kernel über tiefen Embeddings (z. B. von Qwen oder ProtGPT2) verwendet, was eine geschlossene Form für Posterior-Berechnungen ermöglicht.
3. Variational Bayesian Optimistic Sampling (VBOS): Das Ziel ist es, die Policy $\pi_\theta$ so anzupassen, dass sie die VBOS-Objektfunktion maximiert. Diese Funktion balanciert den erwarteten Reward ($\mu_x$) und einen Entropie-basierten Exploration-Bonus ($\sigma_x \sqrt{-2 \ln \pi_x}$).
4. Fine-Tuning: Anstatt die Policy von Null zu lernen, wird das LLM schrittweise (via Gradientenabstieg) an die Posterior-PoM angepasst.
   • Gradientenstabilisierung: Um hohe Varianz bei den Gradienten zu vermeiden, wird eine Reinforce Leave-One-Out (RLOO) Baseline mit Normalisierung verwendet (ähnlich wie bei GRPO).
   • Batch-Verarbeitung: Das Modell generiert Batches von Kandidaten, deren Rewards geschätzt werden, um die Gradienten für das Fine-Tuning zu berechnen.

Theoretische Grundlage:
Die Methode basiert auf der Erkenntnis, dass Thompson Sampling äquivalent zum Ziehen von Punkten gemäß der PoM ist. Durch das Fine-Tuning des LLMs auf diese Verteilung wird die teure Maximierungsschleife eliminiert.

3. Wichtige Beiträge

1. Neue Regret-Schranke für VBOS:
   Die Autoren leiten eine verbesserte kumulative Regret-Schranke für VBOS her: von $\tilde{O}(\sqrt{T|X|})$ auf $\tilde{O}(\sqrt{T \gamma_T})$.

   • $\gamma_T$ ist der maximale Informationsgewinn, der die Korrelationen im Suchraum über den Kernel berücksichtigt.
   • Diese Schranke gilt auch für approximative (gradientenbasierte) VBOS-Policies und zeigt, dass die Methode asymptotisch optimal ist, solange die Divergenz zwischen der gelernten Policy und der exakten VBOS-Policy kontrolliert wird.

2. Algorithmus TOSFIT:
   Ein praktischer Algorithmus, der:

   • Starke Priors durch Pre-Training und Prompting nutzt.
   • Vorsichtiges Fine-Tuning (kleine Lernraten) anwendet, um das Vorwissen nicht zu „vergessen".
   • Keine explizite Maximierung der Akquisitionsfunktion benötigt.

3. Umfassende Validierung:
   Die Methode wurde auf drei sehr unterschiedlichen Aufgaben getestet:

   • FAQ-Response-Verfeinerung: Optimierung von Textantworten basierend auf semantischer Ähnlichkeit.
   • Protein-Suche: Design thermisch stabiler Proteine (Aminosäuresequenzen).
   • Quantenschaltkreis-Design: Generierung von Qiskit-Codes für niedrige Energiezustände.

4. Ergebnisse

• Sample Efficiency (Stichprobeneffizienz): TOSFIT übertrifft in allen drei Aufgaben signifikant den State-of-the-Art. Es findet bessere Lösungen mit weniger Evaluierungen als:
  • Ungeleitete Generierung (Zero-Shot).
  • Nachträglicher Thompson Sampling auf einem festen Pool (Post-Generation TS).
  • Actor-Critic-Methoden (RL).
  • Evolutionäre Suchalgorithmen (sowohl zeichenbasiert als auch LLM-basiert).
  • FIBO (In-Context Thompson Sampling), das aufgrund von Kontextbegrenzungen und fehlenden Parameter-Updates schlechter abschneidet.
• Computational Efficiency: Obwohl Fine-Tuning Rechenkosten verursacht, ist TOSFIT insgesamt rechnerisch effizienter als FIBO, da FIBO bei vielen Iterationen Speicherprobleme hat (quadratisches Wachstum des Kontexts) und TOSFIT durch bessere Sample-Effizienz weniger Gesamt-Evaluierungen benötigt.
• Robustheit: Die Methode funktioniert auch in Batched-Settings (parallele Evaluation mehrerer Kandidaten) und skaliert gut mit größeren Modellen (bis zu 8B Parameter), wobei der Vorteil bei komplexen Aufgaben (Proteine, Quanten) geringer ist als bei reinen Textaufgaben, da hier das Vorwissen des LLMs weniger direkt anwendbar ist.

5. Bedeutung und Fazit

Das Paper demonstriert, dass die Kombination aus Foundation Models und prinzipieller Bayesscher Optimierung ein mächtiges Werkzeug für komplexe diskrete Suchprobleme ist.

• Paradigmenwechsel: Statt das LLM nur als Generator zu nutzen, der durch In-Context-Learning gesteuert wird, wird es als parametrisierte Wahrscheinlichkeitsverteilung behandelt, die durch Fine-Tuning an die Posterior-Verteilung angepasst wird.
• Theoretische Fundierung: Die Arbeit schließt die Lücke zwischen der theoretischen Garantie von Thompson Sampling und der praktischen Machbarkeit in diskreten Räumen, indem sie zeigt, dass eine approximative, gradientenbasierte Anpassung unter bestimmten Bedingungen (gute Initialisierung, vorsichtige Anpassung) die gleichen Regret-Garantien bietet wie exakte Methoden.
• Anwendbarkeit: TOSFIT bietet einen skalierbaren Weg, um in Bereichen wie Drug Discovery, Materialwissenschaft und Quantencomputing zu forschen, wo der Suchraum zu groß für traditionelle Optimierungsmethoden ist.

Zusammenfassend stellt TOSFIT einen Durchbruch dar, der die Rechenkosten der Akquisitionsfunktionsmaximierung eliminiert und gleichzeitig die Stärken von LLMs (Vorwissen, Generierungsfähigkeit) mit der mathematischen Strenge der Bayesschen Optimierung vereint.