[RFE] Extend support for `DeviceTopK`

[elstehle]

Help Us Prioritize Top-K Algorithm Variants for DeviceTopK (i.e., the single-problem, device-wide top-k algorithm)

We are planning the next set of improvements and implementations for DeviceTopK, and we’d like your input to help prioritize which variants we should focus on.

Please copy & paste the form below into a new comment and fill it out in order to describe which top-k features or variants are most important to you. Your responses will help us understand common use cases, preferred behaviors, and performance requirements, so we can prioritize the development of the most relevant versions.

🗒️ Top-K Algorithm Specification Form (click to expand)

# 🧮 Top-K Algorithm Specification Form

Please fill out the form below to describe which **Top-K algorithm parameters or variants** you need.  
Use the checkboxes (`[x]`) to select the features or behaviors you’d like supported (multiple selections are fine). You can also add clarifying notes inline.

**Use case:**  
```
If possible, briefly describe how or where you plan to use the top-K algorithm.
```

---



## ⚙️ Basic Algorithmic Properties

**In-place vs Out-of-place** (you can select both if multiple modes are acceptable):
- [ ] In-place (produces top-k results within the input memory (lower memory overhead)
- [ ] Out-of-place writes results to a separate output iterator (typically higher memory use, potentially better parallel performance)

**Result ordering:**
- [ ] Ordered (top-k items are returned as a sorted sequence)
- [ ] Unordered (top-k items are returned in arbitrary order (i.e., a set of items))

**Stability:**
- [ ] Stable (retain the relative order from the input of selected items)
- [ ] Unstable (no order guarantee)

**Determinism:**
- [ ] Deterministic (bit-wise reproducible results)
- [ ] Non-deterministic (e.g., faster parallel variants)

---

## 🔢 Extended-K Behavior

**Extend `k` by all keys that compare equal?**
- [ ] Yes — include all elements with equal keys beyond `k`
- [ ] No — exactly `k` elements only

---

## 🧮 Algorithm Type

Choose the algorithmic approach:
- [ ] Radix-based
- [ ] Comparison-based

<details>
<summary>▶️ If Radix-based, please specify:</summary>

**Support for custom/arbitrary types?**
- [ ] Yes
- [ ] No

**Bit range to process:**  
**Would you like to be able to specify the bit range that top-k will be looking at?**
- [ ] Yes
- [ ] No
</details>

---

## 💾 Data Characteristics

**Common data types** (select all that apply):
- [ ] **Built-in / fundamental types**: standard integer and floating-point types (`uint8_t`, `int32_t`, `float`, `double`, etc.)
- [ ] **Extended floating-point types**: fp16, bfloat16, ...
- [ ] **Custom data types**
- [ ] **Specific subset only**: I primarily care about a few specific types: ☐ (please list them)


---

## 📏 Typical Problem Sizes

**Common number of input elements (`N`):**
- [ ] 1 – 99 999
- [ ] 100 000 – 999 999
- [ ] 1 000 000 – 9 999 999
- [ ] 10 000 000 – 99 999 999
- [ ] 100 000 000 – 999 999 999
- [ ] ≥ 1 000 000 000
- [ ] Variable / depends on workload
- [ ] Custom: ☐ (please specify exact or range values)

**Common `k` values (number of top elements):**
- [ ] 1 – 9
- [ ] 10 – 99
- [ ] 100 – 999
- [ ] 1 000 – 9 999
- [ ] 10 000 – 99 999
- [ ] 100 000 – 999 999
- [ ] 1 000 000 – 9 999 999
- [ ] 10 000 000 – 99 999 999
- [ ] 100 000 000 – 999 999 999
- [ ] ≥ 1 000 000 000
- [ ] Fraction of `N` (e.g., `k = N / 10`)
- [ ] Variable / depends on workload
- [ ] Custom: ☐ (please specify)

If you're interested in other Top-K algorithm variants such as DeviceSegmentedTopK, BlockTopK, or WarpTopK, please refer to the corresponding issue below:

• 📄 DeviceSegmentedTopK: User requests & feature prioritization
• 📄 WarpTopK / BlockTopK: User requests & feature prioritization

[tedliosu]

🧮 Top-K Algorithm Specification Form

Please fill out the form below to describe which Top-K algorithm parameters or variants you need.
Use the checkboxes ([x]) to select the features or behaviors you’d like supported (multiple selections are fine). You can also add clarifying notes inline.

Use case:

I'm an occasional Top-K user (a handful of times so far), but I'm commenting because tie-handling semantics matter a lot when Top-K is used inside ranking/retrieval or quantized/low-precision scoring pipelines where ties can be common.

Examples I've personally run into where ties are common:

• Ranking / retrieval pipelines (academic prototyping): selecting top candidates by sentence-transformer-based model scores.
• Analytics-style workloads: selecting top IDs/counts as part of simplified aggregation experiments.

My main request is a clearly specified, reproducible tie policy (stable selection / deterministic behavior), rather than advocating for any niche performance tuning.

---

⚙️ Basic Algorithmic Properties

In-place vs Out-of-place (you can select both if multiple modes are acceptable):

• In-place (produces top-k results within the input memory (lower memory overhead)
• Out-of-place writes results to a separate output iterator (typically higher memory use, potentially better parallel performance)

Result ordering:

• Ordered (top-k items are returned as a sorted sequence)
• Unordered (top-k items are returned in arbitrary order (i.e., a set of items))

Stability:

• Stable (retain the relative order from the input of selected items)
• Unstable (no order guarantee)

Determinism:

• Deterministic (bit-wise reproducible results)
• Non-deterministic (e.g., faster parallel variants)

Note: If determinism has a measurable performance cost, stability is higher priority for me.

---

🔢 Extended-K Behavior

Extend k by all keys that compare equal?

• Yes — include all elements with equal keys beyond k
• No — exactly k elements only

---

🧮 Algorithm Type

Choose the algorithmic approach:

• Radix-based
• Comparison-based

▶️ If Radix-based, please specify:

Support for custom/arbitrary types?

• Yes
• No

Bit range to process:
Would you like to be able to specify the bit range that top-k will be looking at?

• Yes
• No

Note: stable tie behavior is a key requirement even when keys compare equal at the selection boundary. (stable = ties prefer earlier input positions)

---

💾 Data Characteristics

Common data types (select all that apply):

• Built-in / fundamental types: standard integer and floating-point types (uint8_t, int32_t, float, double, etc.)
• Extended floating-point types: fp16, bfloat16, ...
• Custom data types
• Specific subset only: I primarily care about a few specific types: ☐ (please list them)

---

📏 Typical Problem Sizes

Common number of input elements (N):

• 1 – 99 999
• 100 000 – 999 999
• 1 000 000 – 9 999 999
• 10 000 000 – 99 999 999
• 100 000 000 – 999 999 999
• ≥ 1 000 000 000
• Variable / depends on workload
• Custom: ☐ (please specify exact or range values)

Common k values (number of top elements):

• 1 – 9
• 10 – 99
• 100 – 999
• 1 000 – 9 999
• 10 000 – 99 999
• 100 000 – 999 999
• 1 000 000 – 9 999 999
• 10 000 000 – 99 999 999
• 100 000 000 – 999 999 999
• ≥ 1 000 000 000
• Fraction of N (e.g., k = N / 10)
• Variable / depends on workload
• Custom: ☐ (please specify)

Thank you so much for creating this form template; hope my feedback helps