Problema
Los modelos de lenguaje eligen el siguiente token a partir de una distribución de probabilidad. Dos ajustes le dan forma:
- 'Top-k: conserva solo los k tokens con los logits más altos (con logits iguales, el índice menor queda por delante).'
- 'Temperatura T: divide los logits conservados entre T antes del softmax. Una T baja hace la elección más predecible y una T alta, más aleatoria.'
Para que el muestreo se pueda probar, el número aleatorio se proporciona:
- Conserva los tokens del top-k y lístalos por su índice original (ascendente).
- Calcula softmax(logit / T) sobre los tokens conservados (resta el mayor antes de calcular e^x).
- Recorre la lista sumando probabilidades; devuelve el índice del primer token en el que el total acumulado supera
random_value. Si eso nunca ocurre (redondeo), devuelve el último token conservado.
Con k = 1 esto es decodificación voraz: siempre el token más probable.
Implementa sample_token(logits, temperature, k, random_value).
Entrada
logits: Una puntuación por token del vocabulario.
temperature: T, mayor que 0.
k: Cuántos de los mejores tokens conservar.
random_value: Un número aleatorio en [0, 1).
Salida
Devuelve el índice del token elegido.
Restricciones
1 ≤ k ≤ número de logits ≤ 1.000
0 < temperature ≤ 100, 0 ≤ random_value < 1
-100 ≤ cada logit ≤ 100
Ejemplos
Entrada:
logits = [1.0, 3.0, 2.0, 0.5]
temperature = 1.0
k = 1
random_value = 0.99
Salida esperada:
expected = 1
Entrada:
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;
Salida esperada:
long long expected = 1;
Entrada:
double[] logits = new double[] {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long k = 1;
double random_value = 0.99;
Salida esperada:
long expected = 1;
Explicación
k = 1 conserva solo el logit más alto, 3.0 en el índice 1. Su probabilidad es 1, así que se elige sin importar el número aleatorio: decodificación voraz.
Entrada:
logits = [2.0, 1.0, 0.0]
temperature = 1.0
k = 2
random_value = 0.8
Salida esperada:
expected = 1
Entrada:
std::vector<double> logits = {2.0, 1.0, 0.0};
double temperature = 1.0;
long long k = 2;
double random_value = 0.8;
Salida esperada:
long long expected = 1;
Entrada:
double[] logits = new double[] {2.0, 1.0, 0.0};
double temperature = 1.0;
long k = 2;
double random_value = 0.8;
Salida esperada:
long expected = 1;
Explicación
El top-2 conserva los índices 0 y 1 (logits 2 y 1). El softmax da aproximadamente 0.731 y 0.269. El total acumulado es 0.731 después del índice 0 (no supera 0.8) y 1 después del índice 1, así que se elige el índice 1.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Primero elige los tokens con mayor logit, rompiendo empates por el índice más pequeño, y luego vuelve a ordenar esos tokens por índice ascendente.
Pista 2
Convierte los logits conservados en probabilidades después de dividir por la temperatura, usando una softmax numéricamente estable.
Pista 3
Al recorrer la probabilidad acumulada, devuelve el primer índice que supere el valor aleatorio, pero cae al último token conservado si el redondeo impide que se cruce.
Complejidad esperada
tiempo O(m log m), espacio extra O(m)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.