Applying Graph Algorithms for MoE Token Batching

Overview

Current LLMs often leverage Expert Parallelism to improve inference throughput. This poses challenges for routing tokens between physical devices while also batching effectively for throughput optimization, particularly for long context inputs. We applied a graph-based algorithm in this project and measured its effectiveness for routing tokens among physical devices assuming a model was deployed using expert parallelism.