Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Temperature and Top-K Sampling

Choose the next token like a language model does: keep the top k logits, apply temperature, and sample.

Bạn sẽ học được gì

  • Keep the top k candidate tokens
  • Control randomness with temperature
  • Sample from a probability distribution

Đề bài

Xem bản dịch

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:

  1. Keep the top k tokens, then list them by their original index (ascending).
  2. Compute softmax(logit / T) over the kept tokens (subtract the largest before taking e^x).
  3. 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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.