Top-K Sampler
Updated
Problem statement
A language model gives every token in its vocabulary a score called a logit. A top-k sampler picks the next token in two steps. First it keeps only the k tokens with the highest logits. Then it picks one of those tokens at random, using softmax probabilities.
You are given logits, where logits[i] is the logit of token i, the number k, and a list of random numbers draws. Each draw is a uniform random number from 0 up to, but not including, 1. The draws are given to you so the answer is fixed. Do not make your own random numbers.
Return an array with one token index for each draw, in the same order as draws.
How a draw picks a token
- Rank all tokens by logit, from highest to lowest. When two logits are equal, the smaller index ranks first. Keep the first
ktokens of this ranking. - Give each kept token
ithe weightexp(logits[i]). Its probability is its weight divided by the sum of the weights of all kept tokens. A token that was not kept has probability0. - Go through the kept tokens in rank order and keep a running total of their probabilities. Return the first token whose running total is greater than the draw.
Every draw uses the same kept tokens and the same probabilities. There is no temperature setting.
Function
sampleTopK(logits: double[], k: int, draws: double[]) → int[]Examples
Example 1
logits = [2.0,1.0,0.1,3.0]k = 2draws = [0.1,0.8]return = [3,0]Ranked by logit, the tokens are 3 (3.0), 0 (2.0), 1 (1.0) and 2 (0.1). With k = 2, tokens 3 and 0 are kept.
Their weights are exp(3) and exp(2), so their probabilities are about 0.731 and 0.269. The running totals are about 0.731 and 1.0.
- Draw
0.1: the first running total,0.731, is already greater, so the answer is token 3. - Draw
0.8:0.731is not greater than0.8, but1.0is, so the answer is token 0.
Example 2
logits = [1.0,1.0,1.0]k = 2draws = [0.25,0.75,0.4999]return = [0,1,0]All three logits are equal, so the smaller indices rank first and tokens 0 and 1 are kept. Token 2 is never picked.
Each kept token has probability 0.5, so the running totals are 0.5 and 1.0. Draws 0.25 and 0.4999 are below 0.5 and pick token 0. Draw 0.75 picks token 1.
Example 3
logits = [0.0,-1.0,2.0]k = 3draws = [0.5,0.95,0.99]return = [2,0,1]Here k equals the number of tokens, so every token is kept. In rank order they are 2, 0 and 1.
The weights are exp(2), exp(0) and exp(-1), about 7.389, 1 and 0.368, with a sum of about 8.757. The probabilities are about 0.844, 0.114 and 0.042, so the running totals are about 0.844, 0.958 and 1.0.
- Draw
0.5picks token 2. - Draw
0.95is not below0.844but is below0.958, so it picks token 0. - Draw
0.99picks token 1.
Constraints
1 <= logits.length <= 10^5-100 <= logits[i] <= 1001 <= k <= logits.length1 <= draws.length <= 10000 <= draws[j] < 1- Every draw differs by at least
10^-6from every running total in step 3, so rounding never changes which token is picked.
More Scale AI Phone Screen questions
- Four-Player Trick-Taking Card Game SimulationOA · PHONE SCREEN · Seen Aug 2026
- Task Processor: Dependencies and DeadlinesPHONE SCREEN · Seen Aug 2026
- Best Poker Category with a JokerPHONE SCREEN · ONSITE INTERVIEW · Seen Jun 2026
- Free Time for Every Meeting RoomPHONE SCREEN · Seen Apr 2026
- Free Windows Between Busy IntervalsOA · PHONE SCREEN · Seen Apr 2026
- Order Queries by Shortest Processing TimePHONE SCREEN · Seen Apr 2026
- Party Time by Town and Quiet Gaps by CityPHONE SCREEN · Seen Jan 2026
- Party Windows and Dead Zone TimePHONE SCREEN · Seen Oct 2025
- Overlap Duration of Two Time IntervalsPHONE SCREEN · Seen Jun 2025
- Multi-Head Attention BlockPHONE SCREEN · Seen Mar 2025
Similar questions at other companies
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Streaming Median of Trade PricesXantium · PHONE SCREEN
- Apartment Housemate PreferencesGoogle · PHONE SCREENGoogle interview questions
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- Top K Movies by Play Count from CSV DataTubi · PHONE SCREEN
- Alert Engine with a Repeat IntervalChronosphere · PHONE SCREEN
- Adaptive Calibration ErrorOpenAI · PHONE SCREENOpenAI interview questions