Skip to content

[Example] Add fused DSA indexer top-k selection for SM90 - #4382

Open
ajpqs wants to merge 1 commit into
tile-ai:mainfrom
ajpqs:dsa-fused-topk
Open

ajpqs wants to merge 1 commit into
tile-ai:mainfrom
ajpqs:dsa-fused-topk

Conversation

@ajpqs

@ajpqs ajpqs commented Nov 15, 2026

Copy link
Copy Markdown

Problem

DeepSeek sparse attention picks, for every query, the topk keys with the best
lightning-indexer score sum_h w[i, h] * relu(q[i, h] . k[j]). Training on long
contexts cannot afford the dense route: one causal document of 131,072 tokens
has a 64 GiB fp32 score matrix.

Approach

examples/dsa_indexer_topk adds a selection-only kernel for SM90 with the
same inputs (bf16 q [Sq, H, D], weights [Sq, H], k [Sk, D]) and a
per-query key range [lo, hi), which covers causal masks, packed documents and
windows of queries over a longer key sequence.

  • A block of 256 threads serves two queries. With GemmWarpPolicy.FullCol each
    warp group computes one query's heads against a tile of 128 keys, or of 64
    keys for topk <= 512, where the smaller tile lets two blocks share an SM.
  • Key tiles come through TMA into two alternating buffers. The next tile is
    requested before the current one is scored, so the load overlaps the GEMM.
  • ReLU, head weights and the head sum stay in registers. A key is appended to
    the query's candidate list only if it beats the current k-th score; the test
    runs on the threads that hold the sums, so scores never pass through shared
    memory.
  • A candidate list holds up to 2 * topk entries. Before it can overflow, an
    8-bit radix selection keeps the best topk: one coarse pass over all
    candidates, then byte-wise refinement of the bucket that contains the k-th
    score, first on the score bits and then on the key id. Equal scores go to the
    smaller id, so the selected set does not depend on thread timing.
  • Barriers are placed by hand (TL_DISABLE_THREAD_STORAGE_SYNC). The scan uses
    one __syncthreads per key tile, which publishes the tile's appends and
    releases the buffer that a later TMA load overwrites, and one per pair of
    tiles after the overflow check, so that every thread has read the candidate
    counts before any thread appends again.

Measurements

H100 80GB, CUDA 12.9. One causal document, every position a query, H = 64, D = 128, random bf16 inputs,
median of 5 runs timed with CUDA events. The baseline is
indexer_topk_reducesum_interface from examples/dsa_sparse_finetune on the
same inputs. The timing script is not part of this PR.

tokens topk this PR (ms) indexer_topk_reducesum (ms) ratio
4,096 2048 0.59 4.42 7.5
8,192 2048 2.33 15.9 6.8
16,384 2048 8.24 64.6 7.8
32,768 2048 29.8 267 9.0
65,536 2048 108 1081 10.0
131,072 2048 397 not run
8,192 512 1.97 10.4 5.3
32,768 512 22.4 156 6.9

The baseline also returns the softmax of the selected scores, which this kernel
does not compute.

Tests

test_dsa_indexer_topk.py compares against a dense fp32 reference.

  • Integer-valued inputs make every score exact in fp32 and produce many equal
    scores, so the selected set, the tie-break and the lengths are compared
    exactly; the expected length is taken from the key range, not from the
    scores. Cases cover every supported topk and H, D pair, several
    selections per row, rows shorter than topk, an odd query count, a single
    query with fewer keys than a tile, packed documents, unrelated and empty
    ranges, a block without any keys, all scores equal, all scores negative, and
    a k-th score beyond the float16 range of the coarse pass.
  • Random inputs: a selected key may differ from the reference only within
    rounding distance of the k-th score.

Scope and limits

  • SM90 only: the kernel relies on WGMMA and TMA, and the tests are gated on
    compute capability 9.0. Other architectures are not tested.
  • topk is a power of two from 128 to 2048, H is 32 or 64 and D is 64 or
    128; the wrapper rejects other sizes. H = 128 does not fit shared memory
    at topk = 2048.
  • Scores must stay finite in fp32. Finite inputs do not guarantee that: a key
    whose score overflows to -inf or becomes NaN is never selected.
  • Key ranges are clipped to [0, Sk).
  • Ids come back unordered, valid ones first and -1 after them.
  • Tested with CUDA 12.9 only.

@github-actions

Copy link
Copy Markdown

👋 Hi! Thank you for contributing to the TileLang project.

Please remember to run pre-commit run --all-files in the root directory of the project to ensure your changes are properly linted and formatted. This will help ensure your contribution passes the format check.

We appreciate you taking this step! Our team will review your contribution, and we look forward to your awesome work! 🚀

@coderabbitai

coderabbitai Bot commented Nov 15, 2026 •

Copy link
Copy Markdown
Contributor

Explain Change →

No actionable comments were generated in the recent review.

Walkthrough

Adds an SM90 TileLang indexer that computes weighted ReLU query-key scores and selects top keys without materializing the dense score matrix. It also adds causal key-range construction, a dense reference function, an executable example, and CUDA and CPU tests.

Changes: Top-K Indexing

Layer / File(s) Summary
Ranges and indexer interface
examples/dsa_indexer_topk/example_dsa_indexer_topk.py
causal_key_ranges creates half-open ranges from positions and optional packed-sequence boundaries. indexer_topk checks supported devices, shapes, and alignment; empty inputs return padded IDs and zero lengths.
Fused scoring and top-k selection
examples/dsa_indexer_topk/example_dsa_indexer_topk.py
The fused kernel processes query pairs over their key-range union, computes weighted ReLU scores, and periodically selects candidates using score and key-ID ordering. It writes selected IDs with -1 padding and reports row lengths.
Reference outputs and validation
examples/dsa_indexer_topk/example_dsa_indexer_topk.py, examples/dsa_indexer_topk/test_dsa_indexer_topk.py
Adds dense fp32 reference scores and an executable example. Tests cover selection ordering, score cases, key ranges, empty inputs, and supported GPU behavior.

Estimated code review effort: 4 (Complex) | ~45 minutes

Change: Feature

Sequence Diagram(s)

sequenceDiagram
  participant Caller
  participant indexer_topk
  participant fused_kernel
  participant topk_selection
  indexer_topk->>fused_kernel: Launch with queries, weights, keys, and key ranges
  fused_kernel->>topk_selection: Refine candidate scores and key IDs
  topk_selection-->>fused_kernel: Return selected candidates and threshold
  fused_kernel-->>indexer_topk: Write padded IDs and row lengths
  indexer_topk-->>Caller: Return IDs and lengths
Loading

Suggested labels: enhancement

Suggested reviewers: chengyupku

Merge Risk: Minimal · up to d86e6

This PR adds a self-contained SM90 top-k indexer example with tests. It does not change existing behavior, and no concrete merge-blocking risk was found. The kernel has not been run on a GPU in this review.

Pre-merge checks: Passed 4

Check name Status Explanation
Title check Passed The title names the main change: adding a fused DSA indexer top-k selection kernel for SM90. It also carries the [Example] tag, which matches the examples/ directory. The changeset adds the kernel, it…
Description check Passed The description covers the problem, the kernel approach, benchmark measurements against indexer_topk_reducesum_interface, test coverage against a dense fp32 reference, and scope limits (SM90 only, sup…
Linked Issues check Passed Check skipped because no linked issues were found for this pull request.
Out of Scope Changes check Passed Check skipped because no linked issues were found for this pull request.
Full details: Title check

Explanation

The title names the main change: adding a fused DSA indexer top-k selection kernel for SM90. It also carries the [Example] tag, which matches the examples/ directory. The changeset adds the kernel, its wrapper functions, and tests, so the title covers the primary change.

Full details: Description check

Explanation

The description covers the problem, the kernel approach, benchmark measurements against indexer_topk_reducesum_interface, test coverage against a dense fp32 reference, and scope limits (SM90 only, supported topk/H/D values). It relates directly to the changeset's added files and functions.

Finishing Touches

Generate unit tests (beta)

  • Create a new PR
  • Autofix · Keep fixing CodeRabbit findings and required CI, and resolving merge conflicts

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

Share

Recent review info

Run configuration

Commits

Reviewing files that changed from the base of the PR and between 210611d and d86e67f.

Files selected for processing: 2

  • examples/dsa_indexer_topk/example_dsa_indexer_topk.py
  • examples/dsa_indexer_topk/test_dsa_indexer_topk.py

Included review availability: This review used your included allowance. Your plan provides up to 8 included reviews per hour; 7 remain after this review.

@coderabbitai
coderabbitai Bot requested a review from chengyupku November 15, 2026 14:03
@coderabbitai coderabbitai Bot added the enhancement New feature or request label Nov 15, 2026

This branch has not been deployed

No deployments
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

enhancement New feature or request

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant