Problem
Sprachmodelle wählen das nächste Token aus einer Wahrscheinlichkeitsverteilung. Zwei Einstellungen formen sie:
- 'Top-k: Behalte nur die k Tokens mit den höchsten Logits (bei gleichen Logits rangiert der kleinere Index höher).'
- 'Temperatur T: Teile die behaltenen Logits vor dem Softmax durch T. Ein niedriges T macht die Wahl vorhersehbarer, ein hohes T zufälliger.'
Damit das Sampling testbar ist, wird die Zufallszahl vorgegeben:
- Behalte die Top-k-Tokens und liste sie nach ihrem ursprünglichen Index (aufsteigend).
- Berechne softmax(logit / T) über die behaltenen Tokens (ziehe den größten Wert ab, bevor du e^x berechnest).
- Gehe die Liste durch und addiere die Wahrscheinlichkeiten; gib den Index des ersten Tokens zurück, bei dem die laufende Summe größer als
random_valuewird. Passiert das nie (Rundung), gib das letzte behaltene Token zurück.
Mit k = 1 ist das Greedy-Decoding: immer das wahrscheinlichste Token.
Implementiere sample_token(logits, temperature, k, random_value).
Eingabe
logits: Ein Score pro Token im Vokabular.
temperature: T, größer als 0.
k: Wie viele Top-Tokens behalten werden.
random_value: Eine Zufallszahl in [0, 1).
Ausgabe
Gib den Index des gewählten Tokens zurück.
Einschränkungen
1 ≤ k ≤ Anzahl der Logits ≤ 1.000
0 < temperature ≤ 100, 0 ≤ random_value < 1
-100 ≤ jeder Logit ≤ 100
Beispiele
Eingabe:
logits = [1.0, 3.0, 2.0, 0.5]
temperature = 1.0
k = 1
random_value = 0.99
Erwartete Ausgabe:
expected = 1
Eingabe:
std::vector<double> logits = {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long long k = 1;
double random_value = 0.99;
Erwartete Ausgabe:
long long expected = 1;
Eingabe:
double[] logits = new double[] {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long k = 1;
double random_value = 0.99;
Erwartete Ausgabe:
long expected = 1;
Erläuterung
k = 1 behält nur den höchsten Logit, 3.0 bei Index 1. Seine Wahrscheinlichkeit ist 1, also wird er unabhängig von der Zufallszahl gewählt: Greedy-Decoding.
Eingabe:
logits = [2.0, 1.0, 0.0]
temperature = 1.0
k = 2
random_value = 0.8
Erwartete Ausgabe:
expected = 1
Eingabe:
std::vector<double> logits = {2.0, 1.0, 0.0};
double temperature = 1.0;
long long k = 2;
double random_value = 0.8;
Erwartete Ausgabe:
long long expected = 1;
Eingabe:
double[] logits = new double[] {2.0, 1.0, 0.0};
double temperature = 1.0;
long k = 2;
double random_value = 0.8;
Erwartete Ausgabe:
long expected = 1;
Erläuterung
Top-2 behält die Indizes 0 und 1 (Logits 2 und 1). Softmax ergibt etwa 0.731 und 0.269. Die laufende Summe ist nach Index 0 0.731 (nicht über 0.8) und nach Index 1 gleich 1, also wird Index 1 gewählt.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Wähle zuerst die Tokens mit dem höchsten Logit, bei Gleichstand mit kleinerem Index, und ordne diese Tokens dann wieder nach aufsteigendem Index.
Hinweis 2
Wandle die behaltenen Logits nach Division durch die Temperatur in Wahrscheinlichkeiten um, mit einer numerisch stabilen Softmax.
Hinweis 3
Beim Durchlaufen der kumulativen Wahrscheinlichkeit gib den ersten Index zurück, der den Zufallswert überschreitet, falle aber auf das letzte behaltene Token zurück, falls Rundung ein Überschreiten verhindert.
Erwartete Komplexität
Zeit O(m log m), zusätzlicher Speicher O(m)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.