TensorTonic
Problems
Top-k and Top-p Sampling
JAX
Medium

Choose one token for each row of logits using temperature scaling, a top-k filter, a top-p (nucleus) filter and inverse-CDF sampling with the supplied uniform numbers.

For every row, apply these rules in order.

  1. Divide the logits by temperature.
  2. Keep the top_k tokens with the largest scaled logits and give every other token zero probability.
  3. Take the softmax over the kept tokens to get their probabilities.
  4. Rank the kept tokens from most to least likely. A token stays in the nucleus when the total probability of the tokens ranked before it is less than top_p, so the most likely token always stays and so does the token that first carries the total past top_p.
  5. Divide the nucleus probabilities by their sum and give every token outside the nucleus probability 0.
  6. Walk the vocabulary in index order 0, 1, ..., V - 1, keeping a running total cjc_jcj​ of the final probabilities, and choose the smallest index jjj with cj>uc_j > ucj​>u, where uuu is the row's entry of uniform. The comparison is strict, so a token with probability 0 is never chosen, even when uuu is 0.

Here logits has shape (B, V) for B rows over a vocabulary of V tokens, uniform has shape (B,) with one number per row, temperature is the number the logits are divided by, top_k is how many tokens the top-k filter keeps, and top_p is the nucleus threshold.

Your function is called under jax.jit with logits and uniform traced and with temperature, top_k and top_p passed as static Python numbers, so every intermediate array needs a shape that does not depend on the data.

Return an int32 JAX array of shape (B,) holding the chosen token index for each row.

Examples

Input: logits = [[2.0,1.0,0.5,-1.0]], uniform = [0.8], temperature = 1.0, top_k = 4, top_p = 1.0

Output: [1]

Explanation: Nothing is filtered, so the probabilities are the softmax of [2, 1, 0.5, -1], about [0.6095, 0.2242, 0.136, 0.0303]. The running totals are about [0.6095, 0.8337, 0.9697, 1], and the first one greater than u = 0.8 is at index 1.

Input: logits = [[0.1,1.5,1.2,-0.3,0.9],[2.0,-1.0,0.0,1.0,0.5]], uniform = [0.9,0.3], temperature = 0.5, top_k = 2, top_p = 1.0

Output: [2,0]

Input: logits = [[1.0,3.0,2.5,0.0,-2.0,1.5]], uniform = [0.95], temperature = 1.0, top_k = 6, top_p = 0.6

Output: [2]

Hint 1

values, idx = jax.lax.top_k(logits, k); values[..., -1:] is the cut-off.

Hint 2

jnp.sort then jnp.cumsum along axis=-1 gives the mass ranked before each token.

Hint 3

jnp.argmax(cum > u, axis=-1) returns the first index where the condition is True.

Requirements

  • Remove tokens by masking with jnp.where, for example with a logit of negative infinity or a probability of 0, instead of boolean-mask indexing.
  • Use the supplied uniform numbers as the only source of randomness, without calling jax.random.
  • Compute the probabilities in float32.

Constraints

  • B is between 1 and 3 and V is between 4 and 8.
  • The logits in each row are distinct finite float32 values.
  • Every value in uniform lies in [0, 0.999], so some running total always exceeds it.
  • temperature is between 0.5 and 2.0, top_k is an integer from 1 to V, and top_p is between 0.05 and 1.0.
Try Similar Problems
Grouped-Query Decode StepMediumRotary Position EmbeddingEasyKV Cache Update at a PositionEasyPad and Mask to Bucket LengthMediumHessian-Vector ProductMediumPer-Example Gradient ClippingMediumStraight-Through Estimator with Custom VJPMediumTraced Learning Rate ScheduleMediumExponential Moving Average with ScanMediumSpectral Norm by Power IterationMediumBatched Attention with vmapMediumPairwise Distances with Nested vmapMedium

Accepts: array

Accepts: array

Accepts: number

Accepts: integer

Accepts: number

You must run your code first.
Top-k and Top-p Sampling

Top-k and Top-p Sampling

JAX
Medium

Choose one token for each row of logits using temperature scaling, a top-k filter, a top-p (nucleus) filter and inverse-CDF sampling with the supplied uniform numbers.

For every row, apply these rules in order.

  1. Divide the logits by temperature.
  2. Keep the top_k tokens with the largest scaled logits and give every other token zero probability.
  3. Take the softmax over the kept tokens to get their probabilities.
  4. Rank the kept tokens from most to least likely. A token stays in the nucleus when the total probability of the tokens ranked before it is less than top_p, so the most likely token always stays and so does the token that first carries the total past top_p.
  5. Divide the nucleus probabilities by their sum and give every token outside the nucleus probability 0.
  6. Walk the vocabulary in index order 0, 1, ..., V - 1, keeping a running total cjc_jcj​ of the final probabilities, and choose the smallest index jjj with cj>uc_j > ucj​>u, where uuu is the row's entry of uniform. The comparison is strict, so a token with probability 0 is never chosen, even when uuu is 0.

Here logits has shape (B, V) for B rows over a vocabulary of V tokens, uniform has shape (B,) with one number per row, temperature is the number the logits are divided by, top_k is how many tokens the top-k filter keeps, and top_p is the nucleus threshold.

Your function is called under jax.jit with logits and uniform traced and with temperature, top_k and top_p passed as static Python numbers, so every intermediate array needs a shape that does not depend on the data.

Return an int32 JAX array of shape (B,) holding the chosen token index for each row.

Examples

Input: logits = [[2.0,1.0,0.5,-1.0]], uniform = [0.8], temperature = 1.0, top_k = 4, top_p = 1.0

Output: [1]

Explanation: Nothing is filtered, so the probabilities are the softmax of [2, 1, 0.5, -1], about [0.6095, 0.2242, 0.136, 0.0303]. The running totals are about [0.6095, 0.8337, 0.9697, 1], and the first one greater than u = 0.8 is at index 1.

Input: logits = [[0.1,1.5,1.2,-0.3,0.9],[2.0,-1.0,0.0,1.0,0.5]], uniform = [0.9,0.3], temperature = 0.5, top_k = 2, top_p = 1.0

Output: [2,0]

Input: logits = [[1.0,3.0,2.5,0.0,-2.0,1.5]], uniform = [0.95], temperature = 1.0, top_k = 6, top_p = 0.6

Output: [2]

Hint 1

values, idx = jax.lax.top_k(logits, k); values[..., -1:] is the cut-off.

Hint 2

jnp.sort then jnp.cumsum along axis=-1 gives the mass ranked before each token.

Hint 3

jnp.argmax(cum > u, axis=-1) returns the first index where the condition is True.

Requirements

  • Remove tokens by masking with jnp.where, for example with a logit of negative infinity or a probability of 0, instead of boolean-mask indexing.
  • Use the supplied uniform numbers as the only source of randomness, without calling jax.random.
  • Compute the probabilities in float32.

Constraints

  • B is between 1 and 3 and V is between 4 and 8.
  • The logits in each row are distinct finite float32 values.
  • Every value in uniform lies in [0, 0.999], so some running total always exceeds it.
  • temperature is between 0.5 and 2.0, top_k is an integer from 1 to V, and top_p is between 0.05 and 1.0.
Try Similar Problems
Grouped-Query Decode StepMediumRotary Position EmbeddingEasyKV Cache Update at a PositionEasyPad and Mask to Bucket LengthMediumHessian-Vector ProductMediumPer-Example Gradient ClippingMediumStraight-Through Estimator with Custom VJPMediumTraced Learning Rate ScheduleMediumExponential Moving Average with ScanMediumSpectral Norm by Power IterationMediumBatched Attention with vmapMediumPairwise Distances with Nested vmapMedium

Accepts: array

Accepts: array

Accepts: number

Accepts: integer

Accepts: number

You must run your code first.
Problems
Loading...
1 / 1