Optimize MoE routing counts with torch.bincount

#165

Summary

Replace the dense [num_tokens, num_experts] temporary used to count routed tokens in KimiSparseMoeBlock.moe_infer with a direct torch.bincount over flattened expert IDs.

The routing indices come from torch.topk, so each token has distinct selected experts. Under that invariant, the histogram is exactly equivalent to the existing scatter-and-sum count.

Why

Kimi K3 has 896 routed experts and selects 16 per token. The current reference path allocates and reduces a dense count matrix even though only num_tokens * top_k assignments need to be counted. This change reduces the visible counting work from O(num_tokens * num_experts) storage/work to O(num_tokens * top_k + num_experts).

Maintained reference measurement

Windows CPU, PyTorch 2.11 CPU, one thread, 3 warmups, 15 measured repetitions:

Token rows Existing median Proposed median Ratio Avoided dense temporary
1,024 0.1615 ms 0.0450 ms 3.59x 7 MiB
4,096 1.2993 ms 0.1622 ms 8.01x 28 MiB
16,384 11.8752 ms 0.6254 ms 18.99x 112 MiB

These are expression-level CPU microbenchmarks of the counting operation. They are not end-to-end Kimi K3 inference results and do not claim a GPU or full-model speedup. The later CPU synchronization and Python expert loop remain unchanged.

Validation

The public reproducer is pinned to parent revision 9f62e4e9fffbd0a83ddd60e1c209d828994b3569 and source SHA-256 9e3564c70ac21854ce5a090cc946c5dc76b70d1050ef50840449181a20fff44a.

Ready to merge
This branch is ready to get merged automatically.

Sign up or log in to comment