Task 4 of 5

Find the Cutoff Instead

O(n²) is fine at four thousand and hopeless at four million — ranking a million scores against each other is 10¹² comparisons. Production top-k does something else entirely: it goes looking for a threshold. Find a value t that exactly k scores exceed, and the top k is simply "everything above t". Counting how many scores clear a given t is one linear pass, and the whole problem collapses into a handful of them.

Finding t is a bisection on the value axis. Bracket it: below lo at least k scores pass, above hi fewer than k do. Guess the middle, count, and throw away the half that cannot contain the answer. Eighteen halvings later the bracket is narrower than the gap between two whole numbers, and Math.floor(lo) is the cutoff. Each count is 65,536 elements shared across 256 threads — the same strided walk a reduction uses, where neighbouring threads read neighbouring elements.

One condition, and it is a real one: the k-th and (k+1)-th scores must differ. If they are equal — which is exactly what task 1's data looked like, where the 10th and 11th scores were both 993 — then no threshold on earth separates them and you are back to the index tie-break. These scores are finer-grained on purpose.

eighteen guesses, each one a single counting pass, instead of four billion comparisons — A bisection on the value axis. Each step marks a guess in the middle of the live bracket and labels it with how many scores exceed it — 197, then 11, then 2. The half that cannot contain the cutoff is discarded each time, until the bracket is narrow enough that exactly ten scores clear it.

Goal: count in parallel, bisect in JavaScript, and log the cutoff that exactly 10 of the 65,536 scores clear.

Requirements

The kernel counts a strided slice: element i of thread x is values[i * 256 + x], and it is counted when it is strictly above t
Total the 256 partial counts in plain JavaScript
Bisect: count >= k raises lo to mid, otherwise hi comes down to it
Stop once hi - lo is 0.5 or less, then log Math.floor(lo) and how many scores clear it

Hint 1 — the counting pass

It is a strided partial sum with a comparison in front of it:

if (values[i * this.constants.threads + this.thread.x] > t) hits++;

Thread x walks values[x], values[x + 256], values[x + 512], … so neighbouring threads touch neighbouring elements at every step.

Hint 2 — which half survives

Keep the invariant in your head: at least k scores are above lo, fewer than k are above hi. So if the middle still lets k or more through, the cutoff is at or above it — raise lo. If it lets fewer through, the middle is too high — lower hi. Note the >=: with > the bracket keeps a value that k + 1 scores clear.

Hint 3 — the whole driver

while (hi - lo > 0.5) {
  const mid = (lo + hi) / 2;
  if (total(await countAbove(scores, mid)) >= K) lo = mid;
  else hi = mid;
}
const cutoff = Math.floor(lo);

The scores are whole numbers, so once the bracket is narrower than 1 there is nothing left to resolve.

Same idea elsewhere

Narrowing a value range with counting passes instead of sorting is what real device-side k-selection does: RAFT/cuML's select_k, FAISS's GPU k-selection and CUB's radix-select all count elements into buckets and recurse into the bucket that contains the boundary — a radix bisection rather than a binary one, but the same idea, and the same reason. Sorting a million things to look at ten of them is a bad trade on every platform.

All tasks in Top-K Selection

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.