# No Request Left Behind: Tackling Heterogeneity in Long-Context LLM Inference with Medha

arXiv: https://arxiv.org/abs/2409.17264 · HTML: https://mlsanity.com/paper/2409.17264/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 43 references that are in the map.
- First posted on arXiv 25 Sep 2024.

## Builds on (most cited first, 25 of 25)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [Ring Attention with Blockwise Transformers for Near-Infinite Context](https://mlsanity.com/paper/2310.01889/) (2023)
- [OpenChat: Advancing Open-source Language Models with Mixed-Quality Data](https://mlsanity.com/paper/2309.11235/) (2023)
- [L-Eval: Instituting Standardized Evaluation for Long Context Language Models](https://mlsanity.com/paper/2307.11088/) (2023)
- [Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving](https://mlsanity.com/paper/2407.00079/) (2024)
- [SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills](https://mlsanity.com/paper/2308.16369/) (2023)
- [Llumnix: Dynamic Scheduling for Large Language Model Serving](https://mlsanity.com/paper/2406.03243/) (2024)
- [Sequence Parallelism: Long Sequence Training from System Perspective](https://mlsanity.com/paper/2105.13120/) (2021)
- [Vidur: A Large-Scale Simulation Framework For LLM Inference](https://mlsanity.com/paper/2405.05465/) (2024)
- [LoongServe: Efficiently Serving Long-Context Large Language Models with Elastic Sequence Parallelism](https://mlsanity.com/paper/2404.09526/) (2024)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [LV-Eval: A Balanced Long-Context Benchmark with 5 Length Levels Up to 256K](https://mlsanity.com/paper/2402.05136/) (2024)
- [Fairness in Serving Large Language Models](https://mlsanity.com/paper/2401.00588/) (2023)
- [Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction](https://mlsanity.com/paper/2404.08509/) (2024)
- [Striped Attention: Faster Ring Attention for Causal Transformers](https://mlsanity.com/paper/2311.09431/) (2023)
- [Andes: Defining and Enhancing Quality-of-Experience in LLM-Based Text Streaming Services](https://mlsanity.com/paper/2404.16283/) (2024)

## Built on by (most cited first, 13 of 13)

- [Position: Episodic Memory is the Missing Piece for Long-Term LLM Agents](https://mlsanity.com/paper/2502.06975/) (2025)
- [TokenLake: A Unified Segment-level Prefix Cache Pool for Fine-grained Elastic Long-Context LLM Serving](https://mlsanity.com/paper/2508.17219/) (2025)
- [FleetOpt: Analytical Fleet Provisioning for LLM Inference with Compress-and-Route as Implementation Mechanism](https://mlsanity.com/paper/2603.16514/) (2026)
- [GhostServe: A Lightweight Checkpointing System in the Shadow for Fault-Tolerant LLM Serving](https://mlsanity.com/paper/2605.00831/) (2026)
- [Tackling the Dynamicity in a Production LLM Serving System with SOTA Optimizations via Hybrid Prefill/Decode/Verify Scheduling on Efficient Meta-kernels](https://mlsanity.com/paper/2412.18106/) (2024)
- [Efficient Serving of LLM Applications with Probabilistic Demand Modeling](https://mlsanity.com/paper/2506.14851/) (2025)
- [KAIROS: Stateful, Context-Aware Power-Efficient Agentic Inference Serving](https://mlsanity.com/paper/2604.16682/) (2026)
- [Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving](https://mlsanity.com/paper/2608.06557/) (2026)
- [From Models to Operators: Rethinking Autoscaling Granularity for Large Generative Models](https://mlsanity.com/paper/2511.02248/) (2025)
- [NanoCP: Request-Level Dynamic Context Parallelism for Data-Expert Parallel Decoding](https://mlsanity.com/paper/2605.21100/) (2026)
- [Beyond Prediction: Tail-Aware Scheduling for LLM Inference](https://mlsanity.com/paper/2606.18431/) (2026)
- [NELSSA: A GPU-PNM Heterogeneous System for Mixed-Length LLM Serving via Length-based Request Placement](https://mlsanity.com/paper/2607.26633/) (2026)
- [Scaling LLM Inference via Parallelism: Throughput-Latency Trade-off](https://mlsanity.com/paper/2610.19405/) (2026)

## Abstract (arXiv)

Deploying million-token Large Language Models (LLMs) is challenging because production workloads are highly heterogeneous, mixing short queries and long documents. This heterogeneity, combined with the quadratic complexity of attention, creates severe convoy effects where long-running requests stall short, interactive ones, degrading system responsiveness. We present Medha, a serving system that eliminates these convoys by introducing fine-grained, preemptive scheduling to LLM inference. Medha makes preemption practical with a co-designed set of mechanisms -- including Adaptive Chunking and Stream Pipeline Parallel that overcome the perceived inefficiencies and scaling challenges of chunking. Additionally, we present a new parallelism strategy KV-Cache Parallelism to reduce the decode latency and afford interactivity despite very long context. These mechanisms are orchestrated by a Length-Aware Relative Slack (LARS) scheduler, a deadline and heterogeneity-aware scheduling policy that prevents both the convoy effect and the starvation that plagues simpler policies. Under a heterogeneous workload, Medha improves throughput by 5.7x while reducing median and 99th percentile latency by 30x and 174x, respectively, compared to state-of-the-art non-preemptive systems.