# Find the Cutoff Instead

*Task 4 of 5 · [Top-K Selection](https://gpu.rocks/learn/top-k-selection-1ba56df3.md) · GPU.js Learn*

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.

## Figures

- **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

**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:

```js
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

```js
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.

## Starter code

```js
// A cutoff, not a ranking: 18 linear passes instead of 4 billion comparisons.
const gpu = new GPU({ mode });

const K = 10;

const countAbove = gpu.createKernel(function (values, t) {
  let hits = 0;
  for (let i = 0; i < this.constants.chunk; i++) {
    // TODO: count this thread's strided element when it is above t
  }
  return hits;
}, {
  output: [256],
  constants: { threads: 256, chunk: 256 },
});

function total(partials) {
  let sum = 0;
  for (let i = 0; i < partials.length; i++) sum += partials[i];
  return sum;
}

// Bracket the answer: everything is above lo, nothing is above hi.
let lo = scores[0];
let hi = scores[0];
for (let i = 1; i < scores.length; i++) {
  if (scores[i] < lo) lo = scores[i];
  if (scores[i] > hi) hi = scores[i];
}
lo = lo - 1;

// TODO: halve the bracket until it is narrower than 1, keeping the half
// that can still contain the cutoff.

const cutoff = Math.floor(lo);
console.log('cutoff:', cutoff);
console.log('above it:', total(await countAbove(scores, cutoff)));
```

---

Interactive version: https://gpu.rocks/learn/top-k-selection-1ba56df3/4

[Previous task](https://gpu.rocks/learn/top-k-selection-1ba56df3/3.md) · [Next task](https://gpu.rocks/learn/top-k-selection-1ba56df3/5.md)