CoChat
Sign Up
Cited by 12Advanced Queuing Theory AnalysisAge of Information OptimizationOptimization and Search Problems

Queueing, Predictions, and Large Language Models: Challenges and Open Problems

Open access
Mitzenmacher, Michael, Shahout, Rana·2025·Stochastic Systems
DOI 10.1287/stsy.2025.0106
Open this paper in CoChat — free account

Abstract

Queueing systems present many opportunities for applying machine learning predictions, such as estimated service times, to improve system performance. This integration raises numerous open questions about how predictions can be effectively leveraged to improve scheduling decisions. Recent studies explore queues with predicted service times, typically aiming to minimize job time in the system. We review these works, highlight the effectiveness of predictions, and present open questions on queue performance. We then move to consider an important practical example of using predictions in scheduling, namely large language model (LLM) systems, which presents novel scheduling challenges and highlights the potential for predictions to improve performance. In particular, we consider LLMs performing inference. Inference requests (jobs) in LLM systems are inherently complex; they have variable inference times, dynamic memory footprints that are constrained by key-value store memory limitations, and multiple possible preemption approaches that affect performance differently. We provide background on the important aspects of scheduling in LLM systems and introduce new models and open problems that arise from them. We argue that there are significant opportunities for applying insights and analysis from queueing theory to scheduling in LLM systems. Funding: M. Mitzenmacher was supported in part by the National Science Foundation [Grant CCF-2101140]. R. Shahout was supported in part by the Schmidt Futures Initiative and the Zuckerman Institute. M. Mitzenmacher and R. Shahout were supported in part the National Science Foundation [Grants CNS-2107078 and DMS-2023528].

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1287/stsy.2025.0106

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Scheduling for LLM inference differs from classical scheduling problems primarily because of bottlenecks introduced by the KV cache, namely linear memory usage growth and the KV cache's dynamic behavior.

    “Scheduling for LLM inference differs from classical scheduling problems primarily because of the bottlenecks introduced by the KV cache as we articulated above (i.e., the linear memory usage growth, and the KV cache's dynamic behavior).”

    From Online Scheduling for LLM Inference with KV Cache Constraints (2025) · cites this paper as Mitzenmacher and Shahout [2025]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 105

  1. Abhyankar R, He Z, Srivatsa V, Zhang H, Zhang Y (2024) InferCept: Efficient intercept support for augmented large language model inference. Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, Berkenkamp F, eds. Proc. 41st Internat. Conf. Machine Learn. (ICML 2024), vol. 238 (PMLR, New York), 8056–8082.Google Scholar
  2. Achiam J, Adler S, Agarwal S, Ahmad L, Akkaya I, Aleman FL, Almeida D, et al. (2023) GPT-4 technical report. Preprint, submitted March 15, https://arxiv.org/abs/2303.08774.Google Scholar · arXiv
  3. Agrawal A, Kedia N, Panwar A, Mohan J, Kwatra N, Gulavani BS, Tumanov A, Ramjee R (2024) Taming throughput-latency tradeoff in LLM inference with Sarathi-serve. Preprint, submitted March 4, https://arxiv.org/abs/2403.02310.Google Scholar · arXiv
  4. Akbari-Moghaddam M, Down DG (2023) SEH: Size estimate hedging scheduling of queues. ACM Trans. Model. Comput. Simulation 33(4):14.Google Scholar
  5. Azar Y, Leonardi S, Touitou N (2021) Flow time scheduling with uncertain processing time. Khuller S, Vassilievska Williams V, eds. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (STOC) (ACM, New York), 1070–1080.Google Scholar
  6. Azar Y, Leonardi S, Touitou N (2022) Distortion-oblivious algorithms for minimizing flow time. Naor J (Seffi), Buchbinder N, eds. Proc. 2022 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 252–274.Google Scholar
  7. Baeza-Yates R, Ribeiro-Neto B (1999) Modern Information Retrieval, vol. 463 (ACM Press, New York).Google Scholar
  8. Belinkov Y (2022) Probing classifiers: Promises, shortcomings, and advances. Comput. Linguistics 48(1):207–219.Google Scholar
  9. Besta M, Blach N, Kubicek A, Gerstenberger R, Podstawski M, Gianinazzi L, Gajda J, et al. (2024) Graph of thoughts: Solving elaborate problems with large language models. Wooldridge M, Dy J, Natarajan S, eds. Proc. Thirty Eighth AAAI Conf. Artificial Intelligence (AAAI-24), vol. 38(16) (AAAI Press, Palo Alto, CA), 17682–17690.Google Scholar
  10. Blum A, Srinivas V (2025) Competitive strategies to use “warm start” algorithms with predictions. Azar Y, Panigrahi D, eds. Proc. 2025 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 3775–3801.Google Scholar
  11. Boyar J, Favrholdt LM, Kudahl C, Larsen KS, Mikkelsen JW (2017) Online algorithms with advice: A survey. ACM Comput. Surveys 50(2):93–129.Google Scholar
  12. Brand J, Forster S, Nazari Y, Polak A (2024) On dynamic graph algorithms with predictions. Woodruff DP, ed. Proc. 2024 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2024) (SIAM, Philadelphia), 3534–3557.Google Scholar
  13. Brown TB, Mann B, Ryder N, Subbiah M, Kaplan JD, Dhariwal P, Neelakantan A, et al. (2020) Language models are few-shot learners. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 1877–1901.Google Scholar
  14. Burke PJ (1956) The output of a queuing system. Oper. Res. 4(6):699–704.Link, Google Scholar
  15. Charlet N, Van Houdt B (2024) Tail optimality of the nudge-M scheduling algorithm. Sigmetrics Performance Evaluation Rev. 52(2):21–23.Google Scholar
  16. Chen Y, Dong J (2021) Scheduling with service-time information: The power of two priority classes. Preprint, submitted February 16, https://arxiv.org/abs/2105.10499.Google Scholar · arXiv
  17. Chen JCY, Saha S, Bansal M (2023b) ReConcile: Round-table conference improves reasoning via consensus among diverse LLMs. Preprint, submitted September 22, https://arxiv.org/abs/2309.13007.Google Scholar · arXiv
  18. Chen C, Borgeaud S, Irving G, Lespiau JB, Sifre L, Jumper J (2023a) Accelerating large language model decoding with speculative sampling. Preprint, submitted February 3, https://arxiv.org/abs/2302.01318.Google Scholar · arXiv
  19. Chen L, Chen Z, Tan B, Long S, Gašić M, Yu K (2019) Agentgraph: Toward universal dialogue management with structured deep reinforcement learning. IEEE/ACM Trans. Audio Speech Language Processing 27(9):1378–1391.Google Scholar
  20. Chen M, Tworek J, Jun H, Yuan Q, Pinto HPDO, Kaplan J, Edwards H, et al. (2021) Evaluating large language models trained on code. Preprint, submitted July 7, https://arxiv.org/abs/2107.03374.Google Scholar · arXiv
  21. Cheng K, Hu W, Wang Z, Du P, Li J, Zhang S (2024) Enabling efficient batch serving for LMaaA via generation length prediction. Preprint, submitted June 7, https://arxiv.org/abs/2406.04785.Google Scholar · arXiv
  22. Dao T (2023) Flashattention-2: Faster attention with better parallelism and work partitioning. Preprint, submitted July 17, https://arxiv.org/abs/2307.08691.Google Scholar · arXiv
  23. Dao T, Fu D, Ermon S, Rudra A, Ré C (2022) Flashattention: Fast and memory-efficient exact attention with IO-awareness. Adv. Neural Inform. Processing Systems 35:16344–16359. Google Scholar
  24. Dell’Amico M (2019) Scheduling with inexact job sizes: The merits of shortest processing time first. Preprint, submitted July 10, https://arxiv.org/abs/1907.04824.Google Scholar · arXiv
  25. Dell’Amico M, Carra D, Michiardi P (2015) PSBS: Practical size-based scheduling. IEEE Trans. Comput. 65(7):2199–2212.Google Scholar
  26. Dell’Amico M, Carra D, Pastorelli M, Michiardi P (2014) Revisiting size-based scheduling with estimated job sizes. Proc. 2014 IEEE 22nd Internat. Sympos. Model. Anal. Simulation Comput. Telecomm. Systems (IEEE Computer Society, Washington, DC), 411–420.Google Scholar
  27. Dinitz M, Im S, Lavastida T, Moseley B, Niaparast A, Vassilvitskii S (2024) Binary search with distributional predictions. Preprint, submitted November 25, https://arxiv.org/abs/2411.16030.Google Scholar · arXiv
  28. Dong J, Ibrahim R (2024) Shortest-job-first scheduling in many-server queues with impatient customers and noisy service-time estimates. Oper. Res., ePub ahead of print December 14, https://doi.org/10.1287/opre.2022.310.Google Scholar · DOI
  29. Dong Q, Li L, Dai D, Zheng C, Ma J, Li R, Xia H, et al. (2022) A survey on in-context learning. Preprint, submitted December 31, https://arxiv.org/abs/2301.00234.Google Scholar · arXiv
  30. Faiz A, Kaneda S, Wang R, Osi R, Sharma P, Chen F, Jiang L (2023) LLMcarbon: Modeling the end-to-end carbon footprint of large language models. Preprint, submitted September 25, https://arxiv.org/abs/2309.14393.Google Scholar · arXiv
  31. Feng X, Wan Z, Wen M, McAleer SM, Wen Y, Zhang W, Wang J (2023) Alphazero-like tree-search can guide large language model decoding and training. Preprint, submitted September 29, https://arxiv.org/abs/2309.17179.Google Scholar · arXiv
  32. Fu Y, Chen J, Zhu S, Fu Z, Dai Z, Qiao A, Zhang H (2024a) Efficient LLM scheduling by learning to rank. Preprint, submitted August 28, https://arxiv.org/abs/2408.15792.Google Scholar · arXiv
  33. Fu Y, Chen J, Zhu S, Fu Z, Dai Z, Qiao A, Zhang H (2024b) Efficiently serving LLM reasoning programs with certaindex. Preprint, submitted December 30, https://arxiv.org/html/2412.20993v1.Google Scholar
  34. Gao Y, Xiong Y, Gao X, Jia K, Pan J, Bi Y, Dai Y, Sun J, Wang M, Wang H (2023) Retrieval-augmented generation for large language models: A survey. Preprint, submitted December 18, https://arxiv.org/abs/2312.10997.Google Scholar · arXiv
  35. Grosof I (2024) Optimal scheduling in multiserver queues. ACM SIGMETRICS Performance Evaluation Rev. 51(3):29–32.Google Scholar
  36. Grosof I, Mitzenmacher M (2022) Incentive compatible queues without money. Preprint, submitted February 11, https://arxiv.org/abs/2202.05747.Google Scholar · arXiv
  37. Guo T, Chen X, Wang Y, Chang R, Pei S, Chawla NV, Wiest O, Zhang X (2024) Large language model based multi-agents: A survey of progress and challenges. Preprint, submitted January 21, https://arxiv.org/abs/2402.01680.Google Scholar · arXiv
  38. Guo D, Yang D, Zhang H, Song J, Zhang R, Xu R, Zhu Q, et al. (2025) Deepseek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning. Preprint, submitted January 22, https://arxiv.org/abs/2501.12948.Google Scholar · arXiv
  39. Hao S, Gu Y, Ma H, Hong JJ, Wang Z, Wang DZ, Hu Z (2023) Reasoning with language model is planning with world model. Preprint, submitted May 24, https://arxiv.org/abs/2305.14992.Google Scholar · arXiv
  40. Harchol-Balter M (2013) Performance Modeling and Design of Computer Systems: Queueing Theory in Action (Cambridge University Press, Cambridge, UK).Google Scholar
  41. Harlev A, Yu G, Scully Z (2024) A Gittins policy for optimizing tail latency. ACM SIGMETRICS Performance Evaluation Rev. 52(2):15–17.Google Scholar
  42. Hewitt J, Liang P (2019) Designing and interpreting probes with control tasks. Preprint, submitted September 8, https://arxiv.org/abs/1909.03368.Google Scholar · arXiv
  43. Hewitt J, Manning CD (2019) A structural probe for finding syntax in word representations. Proc. North Amer. Chapter Assoc. Comput. Linguistics Human Language Tech. (Association for Computational Linguistics, Stroudsburg, PA).Google Scholar
  44. Jaiswal S, Jain K, Simmhan Y, Parayil A, Mallick A, Wang R, Amant RS, et al. (2025) Serving models, fast and slow: Optimizing heterogeneous LLM inferencing workloads at scale. Preprint, submitted February 20, https://arxiv.org/abs/2502.14617.Google Scholar · arXiv
  45. Jin Y, Wu CF, Brooks D, Wei GY (2023) S3: Increasing GPU utilization during generative inference for higher throughput. Advances in Neural Information Processing Systems, vol. 36 (Curran Associates Inc., Red Hook, NY), 18015–18027.Google Scholar
  46. Jo A (2023) The promise and peril of generative AI. Nature 614(7947):214–216. Google Scholar
  47. Juravsky J, Brown B, Ehrlich R, Fu DY, Ré C, Mirhoseini A (2024) Hydragen: High-throughput LLM inference with shared prefixes. Preprint, submitted February 7, https://arxiv.org/abs/2402.05099.Google Scholar · arXiv
  48. Khattab O, Singhvi A, Maheshwari P, Zhang Z, Santhanam K, Haq S, Sharma A, et al. (2024) DSPY: Compiling declarative language model calls into state-of-the-art pipelines. Proc. Twelfth Internat. Conf. Learn. Representations (ICLR 2024) (ICLR, Appleton, WI).Google Scholar
  49. Kwon W, Li Z, Zhuang S, Sheng Y, Zheng L, Yu CH, Gonzalez J, Zhang H, Stoica I (2023) Efficient memory management for large language model serving with pagedattention. Proc. 29th Sympos. Operating Systems Principles (ACM, New York), 611–626.Google Scholar
  50. Leviathan Y, Kalman M, Matias Y (2023) Fast inference from transformers via speculative decoding. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn. (ICML 2023), vol. 202 (PMLR, New York), 19274–19286.Google Scholar
  51. Li J, Wang M, Zheng Z, Zhang M (2024) LooGLE: Can long-context language models understand long contexts? Preprint, submitted November 8, https://arxiv.org/abs/2311.04939.Google Scholar · arXiv
  52. Li Y, Choi D, Chung J, Kushman N, Schrittwieser J, Leblond R, Eccles T, et al. (2022) Competition-level code generation with AlphaCode. Preprint, submitted February 8, https://arxiv.org/abs/2203.07814.Google Scholar · arXiv
  53. Lin C, Han Z, Zhang C, Yang Y, Yang F, Chen C, Qiu L (2024) Parrot: Efficient serving of LLM-based applications with semantic variable. Proc. 18th USENIX Sympos. Operating Systems Design Implementation (OSDI ’24) (USENIX Association, Santa Clara, CA), 929–945.Google Scholar
  54. Liu A, Feng B, Xue B, Wang B, Wu B, Lu C, Zhao C, et al. (2024) DeepSeek-V3 technical report. Preprint, submitted December 27, https://arxiv.org/abs/2412.19437.Google Scholar · arXiv
  55. Mailach R, Down DG (2017) Scheduling jobs with estimation errors for multi-server systems. Proc. 29th Internat. Teletraffic Congress (ITC 29), vol. 1 (IEEE, Piscataway, NJ), 10–18.Google Scholar
  56. Mialon G, Dessì R, Lomeli M, Nalmpantis C, Pasunuru R, Raileanu R, Rozière B, et al. (2023) Augmented language models: A survey. Preprint, submitted February 15, https://arxiv.org/abs/2302.07842.Google Scholar · arXiv
  57. Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12(10):1094–1104.Google Scholar
  58. Mitzenmacher M (2020) Scheduling with predictions and the price of misprediction. Vidick T, ed. Proc. 11th Innovations Theoret. Comput. Sci. Conf. (ITCS 2020), LIPIcs, vol. 151 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 14:1–14:18.Google Scholar
  59. Mitzenmacher M (2021) Queues with small advice. Bender MA, Gilbert J, Hendrickson B, Sullivan BD, eds. Proc. 2021 SIAM Conf. Appl. Comput. Discrete Algorithms (ACDA 2021) (SIAM, Philadelphia), 1–12.Google Scholar
  60. Mitzenmacher M, Dell’Amico M (2022) The supermarket model with known and predicted service times. IEEE Trans. Parallel Distributed Systems 33(11):2740–2751.Google Scholar
  61. Mitzenmacher M, Vassilvitskii S (2020) . Roughgarden T, ed. Beyond the Worst-Case Analysis of Algorithms (Cambridge University Press, Cambridge, UK), 646–662.Google Scholar
  62. Mitzenmacher M, Vassilvitskii S (2022) Algorithms with predictions. Comm. ACM 65(7):33–35.Google Scholar
  63. Moseley B, Newman H, Pruhs K, Zhou R (2025) Robust Gittins for stochastic scheduling. Preprint, submitted April 14, https://arxiv.org/abs/2504.10743.Google Scholar · arXiv
  64. Ong I, Almahairi A, Wu V, Chiang WL, Wu T, Gonzalez JE, Kadous MW, Stoica I (2024) RouteLLM: Learning to route LLMs with preference data. Preprint, submitted June 26, https://arxiv.org/abs/2406.18665.Google Scholar · arXiv
  65. Patel P, Choukse E, Zhang C, Shah A, Goiri Í, Maleki S, Bianchini R (2024) Splitwise: Efficient generative LLM inference using phase splitting. Proc. 51st Annual ACM/IEEE 51st Internat. Sympos. Comput. Architecture (ISCA 2024) (IEEE, Piscataway, NJ), 3775–3801.Google Scholar
  66. Patil SG, Zhang T, Wang X, Gonzalez JE (2023) Gorilla: Large language model connected with massive APIs. Preprint, submitted May 24, https://arxiv.org/abs/2305.15334.Google Scholar · arXiv
  67. Pope R, Douglas S, Chowdhery A, Devlin J, Bradbury J, Heek J, Xiao K, Agrawal S, Dean J (2023) Efficiently scaling transformer inference. Proc. Machine Learn. Systems 5:606–624.Google Scholar
  68. Qin Y, Liang S, Ye Y, Zhu K, Yan L, Lu Y, Lin Y, et al. (2023) ToolLLM: Facilitating large language models to master 16000+ real-world APIs. Preprint, submitted July 31, https://arxiv.org/abs/2307.16789.Google Scholar · arXiv
  69. Qiu H, Mao W, Patke A, Cui S, Jha S, Wang C, Franke H, Kalbarczyk Z, Başar T, Iyer RK (2024a) Power-aware deep learning model serving with -serve. Proc. 2024 USENIX Annual Tech. Conf. (USENIX ATC ’24) (USENIX Association, Santa Clara, CA), 75–93.Google Scholar
  70. Qiu H, Mao W, Patke A, Cui S, Jha S, Wang C, Franke H, Kalbarczyk ZT, Başar T, Iyer RK (2024b) Efficient interactive LLM serving with proxy model-based sequence length prediction. Preprint, submitted April 12, https://arxiv.org/abs/2404.08509.Google Scholar · arXiv
  71. Radford A, Wu J, Child R, Luan D, Amodei D, Sutskever I (2019) Language models are unsupervised multitask learners. OpenAI Blog 1(8):1–24.Google Scholar
  72. Ramesh A, Pavlov M, Goh G, Gray S, Voss C, Radford A, Chen M, Sutskever I (2021) Zero-shot text-to-image generation. Meilă M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn. (ICML 2021), vol. 139 (PMLR, New York), 8821–8831.Google Scholar
  73. Rawal R, Saifullah K, Farré M, Basri R, Jacobs D, Somepalli G, Goldstein T (2024) Cinepile: A long video question answering dataset and benchmark. Preprint, submitted May 14, https://arxiv.org/abs/2405.08813.Google Scholar · arXiv
  74. Reich E (1957) Waiting times when queues are in tandem. Ann. Math. Statist. 28(3):768–773.Google Scholar
  75. Salman SM, Papadopoulos AV, Mubeen S, Nolte T (2023a) Evaluating dispatching and scheduling strategies for firm real-time jobs in edge computing. Proc. 49th Annual Conf. IEEE Indust. Electronics Soc. (IECON 2023) (IEEE, Piscataway, NJ), 1–6.Google Scholar
  76. Salman SM, Dao VL, Papadopoulos AV, Mubeen S, Nolte T (2023b) Scheduling firm real-time applications on the edge with single-bit execution time prediction. Proc. 2023 IEEE 25th Internat. Sympos. Real-Time Distributed Comput. (ISORC 2023) (IEEE, Piscataway, NJ), 207–213.Google Scholar
  77. Sanh V, Debut L, Chaumond J, Wolf T (2019) DistilBERT: A distilled version of BERT: Smaller, faster, cheaper and lighter. Preprint, submitted October 2, https://arxiv.org/abs/1910.01108.Google Scholar · arXiv
  78. Schick T, Dwivedi-Yu J, Dessi R, Raileanu R, Lomeli M, Hambro E, Zettlemoyer L, Cancedda N, Scialom T (2023) Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems, vol. 36 (Curran Associates Inc., Red Hook, NY), 68539–68551.Google Scholar
  79. Scully Z, Harchol-Balter M (2018) SOAP bubbles: Robust scheduling under adversarial noise. Proc. 56th Annual Allerton Conf. Comm. Control Comput. (Allerton 2018) (IEEE, Piscataway, NJ), 144–154.Google Scholar
  80. Scully Z, Harchol-Balter M (2021) The Gittins policy in the M/G/1 queue. Proc. 19th Internat. Sympos. Model. Optim. Mobile Ad Hoc Wireless Networks (WiOpt 2021) (IEEE, Piscataway, NJ), 248–255.Google Scholar
  81. Scully Z, Grosof I, Harchol-Balter M (2020a) The Gittins policy is nearly optimal in the M/G/k under extremely general conditions. Proc. ACM Measurement Anal. Comput. Systems 4(3):43.Google Scholar
  82. Scully Z, Grosof I, Mitzenmacher M (2022) . Braverman M, ed. 13th Innovations Theoret. Comput. Sci. Conf. ITCS, LIPIcs, vol. 215 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 114:1–114:30.Google Scholar
  83. Scully Z, Harchol-Balter M, Scheller-Wolf A (2018) SOAP: One clean analysis of all age-based scheduling policies. Proc. ACM Measurement Anal. Comput. Systems 2(1):16.Google Scholar
  84. Scully Z, Van Kreveld L, Boxma O, Dorsman JP, Wierman A (2020b) Characterizing policies with optimal response time tails under heavy-tailed job sizes. Proc. ACM Measurement Anal. Comput. Systems 4(2):30.Google Scholar
  85. Shahout R, Mitzenmacher M (2024) SkipPredict: When to invest in predictions for scheduling. Globerson A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak J, Zhang C, eds. Advances in Neural Information Processing Systems, vol. 37 (Curran Associates, Inc., Red Hook, NY).Google Scholar
  86. Shahout R, Malach E, Liu C, Jiang W, Yu M, Mitzenmacher M (2025a) Don’t stop me now: Embedding based scheduling for LLMs. Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
  87. Shahout R, Liang C, Xin S, Lao Q, Cui Y, Yu M, Mitzenmacher M (2025b) Fast inference for augmented large language models. Preprint, submitted October 25, https://arxiv.org/abs/2410.18248.Google Scholar · arXiv
  88. Srivatsa V, He Z, Abhyankar R, Li D, Zhang Y (2024) Preble: Efficient distributed prompt scheduling for LLM serving. Preprint, submitted May 8, https://arxiv.org/abs/2407.00023.Google Scholar · arXiv
  89. Stojkovic J, Zhang C, Goiri Í, Torrellas J, Choukse E (2024) DynamoLLM: Designing LLM inference clusters for performance and energy efficiency. Preprint, submitted August 1, https://arxiv.org/abs/2408.00741.Google Scholar · arXiv
  90. Touvron H, Lavril T, Izacard G, Martinet X, Lachaux MA, Lacroix T, Rozière B, et al. (2023) LLaMA: Open and efficient foundation language models. Preprint, submitted February 27, https://arxiv.org/abs/2302.13971.Google Scholar · arXiv
  91. Vvedenskaya ND, Suhov YM (1997) Dobrushin’s mean-field approximation for a queue with dynamic routing. Markov Processes Related Fields 3(4):493–526.Google Scholar
  92. Wang Y, Ma X, Chen W (2024b) Augmenting black-box LLMs with medical textbooks for biomedical question answering. Findings 2024 Conf. Empirical Methods Natl. Language Processing (EMNLP 2024) (Association for Computational Linguistics, Stroudsburg, PA), 1754–1770.Google Scholar
  93. Wang X, Wei J, Schuurmans D, Le Q, Chi E, Narang S, Chowdhery A, Zhou D (2022) Self-consistency improves chain of thought reasoning in language models. Preprint, submitted March 21, https://arxiv.org/abs/2203.11171.Google Scholar · arXiv
  94. Wei J, Wang X, Schuurmans D, Bosma M, Xia F, Chi E, Le QV, Zhou D, et al. (2022) Chain-of-thought prompting elicits reasoning in large language models. Adv. Neural Inform. Processing Systems 35:24824–24837.Google Scholar
  95. Wierman A, Nuyens M (2008) Scheduling despite inexact job-size information. Proc. 2008 ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Systems (SIGMETRICS ’08) (ACM, New York), 25–36.Google Scholar
  96. Wu Y, Sun Z, Li S, Welleck S, Yang Y (2024) Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models. Preprint, submitted August 1, https://arxiv.org/abs/2408.00724.Google Scholar · arXiv
  97. Wu B, Zhong Y, Zhang Z, Huang G, Liu X, Jin X (2023) Fast distributed inference serving for large language models. Preprint, submitted May 10, https://arxiv.org/abs/2305.05920.Google Scholar · arXiv
  98. Yu G, Scully Z (2024) Strongly tail-optimal scheduling in the light-tailed M/G/1. Proc. ACM Measurement Anal. Comput. Systems 8(2):27.Google Scholar
  99. Yu GI, Jeong JS, Kim GW, Kim S, Chun BG (2022) Orca: A distributed serving system for transformer-based generative models. Proc. 16th USENIX Sympos. Operating Systems Design Implementation (OSDI ’22) (USENIX Association, Berkeley, CA), 521–538.Google Scholar
  100. Zhao P, Zhang H, Yu Q, Wang Z, Geng Y, Fu F, Yang L, Zhang W, Jiang J, Cui B (2024) Retrieval-augmented generation for AI-generated content: A survey. Preprint, submitted February 29, https://arxiv.org/abs/2402.19473.Google Scholar · arXiv
  101. Zheng Z, Ren X, Xue F, Luo Y, Jiang X, You Y (2024) Response length perception and sequence scheduling: An LLM-empowered LLM inference pipeline. Advances in Neural Information Processing Systems, vol. 36 (Curran Associates Inc., Red Hook, NY), 65517–65530.Google Scholar
  102. Zheng L, Yin L, Xie Z, Huang J, Sun C, Yu CH, Cao S, et al. (2023) Efficiently programming large language models using SGLang. Preprint, submitted December 12, https://arxiv.org/abs/2312.07104.Google Scholar · arXiv
  103. Zheng L, Yin L, Xie Z, Sun CL, Huang J, Yu CH, Cao S, et al. (2025) SGLang: Efficient execution of structured language model programs. Advances in Neural Information Processing Systems, vol. 38 (Curran Associates Inc., Red Hook, NY), 62557–62583.Google Scholar
  104. Zhong Y, Liu S, Chen J, Hu J, Zhu Y, Liu X, JX, Zhang H (2024) DistServe: Disaggregating prefill and decoding for goodput-optimized large language model serving. Preprint, submitted January 18, https://arxiv.org/abs/2401.09670.Google Scholar · arXiv
  105. 9 January 2026 | Jurnal Kecerdasan Buatan dan Teknologi Informasi, Vol. 5, No. 3

Cited by

Sorted by citations

Authors
Mitzenmacher, M., & Shahout, R.
Affiliations
Harvard University (US)
Corresponding author
Shahout, Rana
ORCID
Venue
Stochastic Systems
Publisher
Institute for Operations Research and the Management Sciences (INFORMS)
Published
2025-09
Volume
15
Issue
3
Pages
195-219
ISSN
1946-5238 (ISSN-L)
DOI
10.1287/stsy.2025.0106
OpenAlex
W4412572711
Cited by
12
References
3
Citations by year
2026: 10 · 2025: 2
FWCI
10.34
Type
journal article
Language
en
Open access
Licence
cc-by
Locations
  • Stochastic Systems (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Funders
National Science Foundation (2023528, 2101140, 2107078)
Topics
  • Social Sciences › Business, Management and Accounting › Management Information Systems › Advanced Queuing Theory Analysis
  • Physical Sciences › Computer Science › Computer Networks and Communications › Age of Information Optimization
  • Physical Sciences › Computer Science › Computer Networks and Communications › Optimization and Search Problems
Keywords
queueing systems, machine learning prediction, scheduling, large language models, preemption, queue performance, open problems

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review