すべてのチャレンジ
中級 0件解決済み 正答率0%

Temperature and Top-K Sampling

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

このチャレンジで学べること

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

問題

翻訳を表示

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.

制約

1 ≤ k ≤ number of logits ≤ 1,000

0 < temperature ≤ 100, 0 ≤ random_value < 1

-100 ≤ each logit ≤ 100

例

例 1
入力:
logits = [1.0, 3.0, 2.0, 0.5]
temperature = 1.0
k = 1
random_value = 0.99

期待される出力:
expected = 1
入力:
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;

期待される出力:
long long expected = 1;
入力:
double[] logits = new double[] {1.0, 3.0, 2.0, 0.5};
double temperature = 1.0;
long k = 1;
double random_value = 0.99;

期待される出力:
long expected = 1;

解説

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.

例 2
入力:
logits = [2.0, 1.0, 0.0]
temperature = 1.0
k = 2
random_value = 0.8

期待される出力:
expected = 1
入力:
std::vector<double> logits = {2.0, 1.0, 0.0};
double temperature = 1.0;
long long k = 2;
double random_value = 0.8;

期待される出力:
long long expected = 1;
入力:
double[] logits = new double[] {2.0, 1.0, 0.0};
double temperature = 1.0;
long k = 2;
double random_value = 0.8;

期待される出力:
long expected = 1;

解説

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.

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

First choose the highest-logit tokens, breaking ties by smaller index, then restore those tokens to ascending index order.

ヒント 2

Convert the kept logits into probabilities after dividing by temperature, using a numerically stable softmax.

ヒント 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.

目安の計算量

O(m log m) time, O(m) extra space

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。