Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Temperatur- und Top-K-Sampling

Wähle das nächste Token wie ein Sprachmodell: Behalte die k höchsten Logits, wende die Temperatur an und ziehe eine Stichprobe.

Das lernst du

  • Die k besten Kandidaten-Tokens behalten
  • Den Zufall mit der Temperatur steuern
  • Aus einer Wahrscheinlichkeitsverteilung ziehen

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:

  1. Behalte die Top-k-Tokens und liste sie nach ihrem ursprünglichen Index (aufsteigend).
  2. Berechne softmax(logit / T) über die behaltenen Tokens (ziehe den größten Wert ab, bevor du e^x berechnest).
  3. 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_value wird. 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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.