Đề bài
Language models pick the next token from a probability distribution. Two settings shape it:
- Top-k: keep only the k tokens with the highest logits (if logits tie, the lower index ranks higher).
- Temperature T: divide the kept logits by T before softmax. Low T makes the choice more predictable; high T makes it more random.
To make sampling testable, the random number is given:
- Keep the top k tokens, then list them by their original index (ascending).
- Compute softmax(logit / T) over the kept tokens (subtract the largest before taking e^x).
- Walk through the list adding probabilities; return the index of the first token where the running total becomes greater than
random_value. If none does (rounding), return the last kept token.
With k = 1 this is greedy decoding: always the most likely token.
Implement sample_token(logits, temperature, k, random_value).
Input
logits: One score per token in the vocabulary.
temperature: T, greater than 0.
k: How many top tokens to keep.
random_value: A random number in [0, 1).
Output
Return the index of the chosen token.
Ràng buộc
1 ≤ k ≤ number of logits ≤ 1,000
0 < temperature ≤ 100, 0 ≤ random_value < 1
-100 ≤ each logit ≤ 100
Ví dụ
Đầu vào:
logits = [1.0, 3.0, 2.0, 0.5]
temperature = 1.0
k = 1
random_value = 0.99
Kết quả mong đợi:
expected = 1
Đầu vào:
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;
Kết quả mong đợi:
long long expected = 1;
Đầu vào:
double[] logits = new double[] {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long k = 1;
double random_value = 0.99;
Kết quả mong đợi:
long expected = 1;
Giải thích
k = 1 keeps only the highest logit, 3.0 at index 1. Its probability is 1, so it is chosen whatever the random value: greedy decoding.
Đầu vào:
logits = [2.0, 1.0, 0.0]
temperature = 1.0
k = 2
random_value = 0.8
Kết quả mong đợi:
expected = 1
Đầu vào:
std::vector<double> logits = {2.0, 1.0, 0.0};
double temperature = 1.0;
long long k = 2;
double random_value = 0.8;
Kết quả mong đợi:
long long expected = 1;
Đầu vào:
double[] logits = new double[] {2.0, 1.0, 0.0};
double temperature = 1.0;
long k = 2;
double random_value = 0.8;
Kết quả mong đợi:
long expected = 1;
Giải thích
Top-2 keeps indices 0 and 1 (logits 2 and 1). softmax gives about 0.731 and 0.269. The running total is 0.731 after index 0 (not above 0.8) and 1 after index 1, so index 1 is chosen.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
First choose the highest-logit tokens, breaking ties by smaller index, then restore those tokens to ascending index order.
Gợi ý 2
Convert the kept logits into probabilities after dividing by temperature, using a numerically stable softmax.
Gợi ý 3
When scanning cumulative probability, return the first index that crosses the random value, but fall back to the last kept token if rounding prevents a crossing.
Độ phức tạp mong đợi
O(m log m) time, O(m) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.