Problème
Les modèles de langage choisissent le token suivant à partir d'une distribution de probabilités. Deux réglages la façonnent :
- 'Top-k : ne gardez que les k tokens aux logits les plus élevés (à logits égaux, l''indice le plus petit est mieux classé).'
- 'Température T : divisez les logits gardés par T avant le softmax. Un T bas rend le choix plus prévisible, un T élevé plus aléatoire.'
Pour rendre l'échantillonnage testable, le nombre aléatoire est fourni :
- Gardez les tokens du top-k et listez-les par indice d'origine (croissant).
- Calculez softmax(logit / T) sur les tokens gardés (soustrayez le plus grand avant de calculer e^x).
- Parcourez la liste en additionnant les probabilités ; renvoyez l'indice du premier token pour lequel le total cumulé dépasse
random_value. Si cela n'arrive jamais (arrondi), renvoyez le dernier token gardé.
Avec k = 1, c'est le décodage glouton : toujours le token le plus probable.
Implémentez sample_token(logits, temperature, k, random_value).
Entrée
logits : Un score par token du vocabulaire.
temperature : T, supérieur à 0.
k : Le nombre de meilleurs tokens à garder.
random_value : Un nombre aléatoire dans [0, 1).
Sortie
Renvoyez l'indice du token choisi.
Contraintes
1 ≤ k ≤ nombre de logits ≤ 1 000
0 < temperature ≤ 100, 0 ≤ random_value < 1
-100 ≤ chaque logit ≤ 100
Exemples
Entrée :
logits = [1.0, 3.0, 2.0, 0.5]
temperature = 1.0
k = 1
random_value = 0.99
Sortie attendue :
expected = 1
Entrée :
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;
Sortie attendue :
long long expected = 1;
Entrée :
double[] logits = new double[] {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long k = 1;
double random_value = 0.99;
Sortie attendue :
long expected = 1;
Explication
k = 1 ne garde que le logit le plus élevé, 3.0 à l'indice 1. Sa probabilité vaut 1, il est donc choisi quel que soit le nombre aléatoire : décodage glouton.
Entrée :
logits = [2.0, 1.0, 0.0]
temperature = 1.0
k = 2
random_value = 0.8
Sortie attendue :
expected = 1
Entrée :
std::vector<double> logits = {2.0, 1.0, 0.0};
double temperature = 1.0;
long long k = 2;
double random_value = 0.8;
Sortie attendue :
long long expected = 1;
Entrée :
double[] logits = new double[] {2.0, 1.0, 0.0};
double temperature = 1.0;
long k = 2;
double random_value = 0.8;
Sortie attendue :
long expected = 1;
Explication
Le top-2 garde les indices 0 et 1 (logits 2 et 1). Le softmax donne environ 0.731 et 0.269. Le total cumulé vaut 0.731 après l'indice 0 (pas au-dessus de 0.8) et 1 après l'indice 1, donc l'indice 1 est choisi.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Choisis d’abord les tokens aux logits les plus élevés, en départageant les égalités par le plus petit index, puis remets ces tokens en ordre croissant d’index.
Indice 2
Convertis les logits conservés en probabilités après division par la température, avec un softmax numériquement stable.
Indice 3
En parcourant la probabilité cumulée, renvoie le premier index qui dépasse la valeur aléatoire, mais retombe sur le dernier token conservé si l’arrondi empêche tout dépassement.
Complexité attendue
temps O(m log m), espace supplémentaire O(m)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.