mlsanityData to 7 Oct 2026

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

arXiv 2409.17264 ↗First posted 25 Sep 2024cs.LG cs.DCcited by 12

Not on the map. Why?

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.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 25 of its 43 references that are in the map. First posted on arXiv 25 Sep 2024.

Builds on

25 of 43 references.

References · 25

  1. 2017Attention Is All You Needcited by 59,932
  2. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
  3. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  4. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,581
  5. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,175
  6. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  7. 2019Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelismcited by 1,829
  8. 2024DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Servingcited by 595
  9. 2023Splitwise: Efficient generative LLM inference using phase splittingcited by 536
  10. 2024Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Servecited by 507
  11. 2023Ring Attention with Blockwise Transformers for Near-Infinite Contextcited by 448
  12. 2023OpenChat: Advancing Open-source Language Models with Mixed-Quality Datacited by 250
13 more
  1. 2023L-Eval: Instituting Standardized Evaluation for Long Context Language Modelscited by 232
  2. 2024Mooncake: A KVCache-centric Disaggregated Architecture for LLM Servingcited by 193
  3. 2023SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefillscited by 187
  4. 2024Llumnix: Dynamic Scheduling for Large Language Model Servingcited by 167
  5. 2021Sequence Parallelism: Long Sequence Training from System Perspectivecited by 125
  6. 2024Vidur: A Large-Scale Simulation Framework For LLM Inferencecited by 115
  7. 2024LoongServe: Efficiently Serving Long-Context Large Language Models with Elastic Sequence Parallelismcited by 110
  8. 2024Efficient LLM Scheduling by Learning to Rankcited by 83
  9. 2024LV-Eval: A Balanced Long-Context Benchmark with 5 Length Levels Up to 256Kcited by 80
  10. 2023Fairness in Serving Large Language Modelscited by 77
  11. 2024Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Predictioncited by 64
  12. 2023Striped Attention: Faster Ring Attention for Causal Transformerscited by 52
  13. 2024Andes: Defining and Enhancing Quality-of-Experience in LLM-Based Text Streaming Servicescited by 44

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 7.

12 papers.

  1. 2025Position: Episodic Memory is the Missing Piece for Long-Term LLM Agentscited by 35
  2. 2025TokenLake: A Unified Segment-level Prefix Cache Pool for Fine-grained Elastic Long-Context LLM Servingcited by 5
  3. 2026FleetOpt: Analytical Fleet Provisioning for LLM Inference with Compress-and-Route as Implementation Mechanismcited by 3
  4. 2026GhostServe: A Lightweight Checkpointing System in the Shadow for Fault-Tolerant LLM Servingcited by 3
  5. 2024Tackling the Dynamicity in a Production LLM Serving System with SOTA Optimizations via Hybrid Prefill/Decode/Verify Scheduling on Efficient Meta-kernelscited by 1
  6. 2025Efficient Serving of LLM Applications with Probabilistic Demand Modelingcited by 1
  7. 2026KAIROS: Stateful, Context-Aware Power-Efficient Agentic Inference Servingcited by 1
  8. 2025From Models to Operators: Rethinking Autoscaling Granularity for Large Generative Modelscited by 0
  9. 2026NanoCP: Request-Level Dynamic Context Parallelism for Data-Expert Parallel Decodingcited by 0
  10. 2026Beyond Prediction: Tail-Aware Scheduling for LLM Inferencecited by 0
  11. 2026NELSSA: A GPU-PNM Heterogeneous System for Mixed-Length LLM Serving via Length-based Request Placementcited by 0
  12. 2026Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference servingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Infinite-LLM: Efficient LLM Service for Long Context with DistAttention and Distributed KVCache
  2. 2025Optimizing Long-context LLM Serving via Fine-grained Sequence Parallelism
  3. 2025Apt-Serve: Adaptive Request Scheduling on Hybrid Cache for Scalable LLM Inference Serving
  4. 2024GUIDE: A Global Unified Inference Engine for Deploying Large Language Models in Heterogeneous Environments
  5. 2023Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline
  6. 2025Seesaw: High-throughput LLM Inference via Model Re-sharding
  7. 2024Multi-Bin Batching for Increasing LLM Inference Throughput
  8. 2024Fast Inference for Augmented Large Language Models