Pith. sign in

REVIEW 6 minor 43 references

General Non-Clairvoyant KV-Cache Scheduling via Regime-Aware Routing

T0 review · 0 major / 6 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The first constant-competitive non-clairvoyant scheduler for batched LLM inference under a hard KV-cache budget works for arbitrary prompt and response lengths.

desk verdict First O(1)-competitive non-clairvoyant KV-cache completion-time result for unrestricted prompts and responses; the regime-routing construction is real and the proof chain holds. read the letter →

arxiv 2607.09248 v1 pith:NMIX6A55 submitted 2026-07-10 cs.DS

Yiding Feng , Siyu Liu , Zonghan Yang , Yuhao Zhang This is my paper
classification cs.DS
keywords non-clairvoyantschedulingKV-cacheLLMinferencecompetitiveanalysisregime-awareroutingtotalcompletiontimerectanglestriponlinearrivals
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Serving large language models under a fixed Key-Value cache memory budget forces a hard trade-off: pack many requests for throughput, but killing a request discards its accumulated cache and wastes work. Response lengths are unknown until a request finishes, so the scheduler is non-clairvoyant and memory demand grows with every decoded token. Prior theoretical guarantees needed extra assumptions such as identical prompts or large memory. This paper shows that a fully non-clairvoyant algorithm can still keep total completion time within a constant factor of the best schedule that knows every response length in advance. The method does not use one universal priority rule; instead it classifies jobs by memory-growth geometry, runs specialized sub-schedulers, and routes each job as execution reveals which class it belongs to. The same framework also gives constant-factor guarantees for makespan and for online arrivals.

What carries the argument

Regime-aware routing: jobs are split by prompt cutoff into large, small prompt-heavy, and small response-heavy regimes; Rect (budget-doubling greedy rectangle packing) and Response (area-geometric slicing with staggered pipeline scheduling) handle the regimes; a meta-scheduler time-shares the memory budget in doubling stages and routes a small job from the prompt-heavy branch to the response-heavy branch once it has generated more tokens than its prompt length.

What would settle it

Construct a response-heavy instance with widely varying prompt lengths under the paper's SPS proxy, run Response, and check whether observed peak memory and phase utilization still match the claimed Peak(k, τ, s) bound and the 236/3 competitive ratio; a large utilization gap or unbounded ratio would falsify the branch guarantee.

Watch

Extended reading notes

Core claim

For every feasible batch KV-cache instance with arbitrary prompt lengths and arbitrary response lengths, there is a fully non-clairvoyant polynomial-time algorithm whose total completion time is O(1) times the optimal clairvoyant total completion time. With the paper's concrete parameters the analysis yields a ratio of at most 996. No extra assumptions on prompts, responses, or memory size are required.

Load-bearing premise

The response-heavy branch leans on a prior peak-memory formula for staggered pipeline packing of identical proxy jobs; if that utilization bound fails for real heterogeneous prompts, the constant competitive ratio for that branch (and therefore for the whole router) collapses.

Editorial extensions

If this is right

  • The same routing algorithm is O(1)-competitive for makespan on arbitrary instances.
  • An online-arrival variant remains O(1)-competitive for total completion time when jobs reveal only prompt lengths on arrival.
  • In the clairvoyant setting the framework yields a 16-approximation for general instances and a (3+o(1))-approximation when every job is small relative to memory.
  • A multi-replica deployment that routes geometric classes to separate replicas can avoid single-budget time-sharing and improve the practical competitive ratio over the single-replica theoretical bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Global routers in production LLM stacks already know prompt lengths; classifying and dispatching by the three geometric regimes could be a low-friction systems change that inherits the paper's worst-case guarantees without running the theoretical meta-scheduler on one GPU.
  • The impossibility of any single priority rule (Proposition 1) suggests that other growing-resource non-clairvoyant problems may also need regime decomposition rather than one global ordering.
  • Because total flow time admits super-constant lower bounds under adversarial arrivals, completion-time competitiveness is likely the strongest constant-factor latency guarantee one can hope for in this model.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies non-clairvoyant batch scheduling of LLM inference requests under a hard KV-cache memory budget M. Each job has known prompt length s_i and unknown response length o_i; memory grows as s_i plus decoded tokens, and killing a job discards its cache. The objective is total completion time versus the optimal clairvoyant schedule. The authors give the first O(1)-competitive algorithm for arbitrary prompts and responses (Theorem 1), via a regime decomposition into large (s_i > Λ), small prompt-heavy (s_i ≤ Λ, o_i ≤ s_i), and small response-heavy (s_i ≤ Λ, o_i > s_i) jobs. Large and prompt-heavy jobs are handled by a new non-clairvoyant rectangle-strip scheduler Rect with budget-doubling and queue monotonicity; response-heavy jobs use geometric response caps plus the SPS subroutine of Feng et al. (2026). A routing meta-scheduler Route time-shares memory across branches and certifies small jobs online. Explicit analysis yields Route(J) ≤ 996·Opt(J) for Λ = M/4. The framework also gives constant guarantees for makespan, online-arrival completion time, and clairvoyant approximations (including 16-approx and 3+o(1) in the large-memory regime).

Significance. If correct, this is a genuine first result in the non-clairvoyant KV-cache model without identical-prompt, large-memory, or clairvoyance restrictions that prior work required. The regime-aware routing idea is technically natural and well motivated by the impossibility of a single priority rule (Proposition 1). The rectangle-strip scheduler and its queue-monotonicity argument appear of independent interest beyond LLM serving. Explicit constants, polynomial-time event-driven implementation, and clean extensions to makespan and online arrivals strengthen the contribution. The systems discussion (route by geometry across replicas) is a useful bridge from theory to practice. The large constant (996) is a weakness for immediate practical use but is acceptable for a first O(1) existence result in a new model; the layered proof structure is a clear strength.

minor comments (6)
  1. The explicit competitive ratio 996 (proof of Theorem 1) is easy to miss; state it in the abstract or Theorem 1 statement, and briefly note that multi-replica routing (as discussed in §1.1) would improve the constant by removing meta-scheduler time-sharing.
  2. Fact 1 (SPS peak memory) is imported from Feng et al. 2026. Lemma 8 correctly reduces heterogeneous prompts to the proxy instance, but a short self-contained restatement of Peak(k,τ,s) and why k* ≥ ⌊(2M-τ+1)/(2s+τ+1)⌋ holds would make Section 5 more readable without the companion paper.
  3. In Algorithm 1 and Lemma 4, clarify the tie-breaking rule for simultaneous events and for equal area budgets; the proof assumes an arbitrary fixed order, which is fine but should be stated once in the algorithm description.
  4. Notation for dummy jobs in BlackBoxMeta/Route is slightly informal. A one-sentence invariant (“completed jobs remain in the pool with zero remaining work and do not consume memory”) would prevent confusion with true idle slots.
  5. Related-work placement of concurrent Kong et al. [2026] and Feng et al. [2026] is appropriate; ensure arXiv identifiers and claimed ratios match the final versions at camera-ready.
  6. Minor prose: “memory-time area simply as area” is repeated; “Oα(1)” in Theorem 3 could be written O_α(1) for consistency with standard notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: competitive ratio is proven against independent clairvoyant Opt via standard area/processing lower bounds; SPS is a black-box subroutine with independently checkable peak-memory math.

full rationale

The paper is a pure competitive-analysis result in scheduling theory. Theorem 1 bounds Route(J) by a constant times Opt(J), where Opt is the minimum total completion time of any clairvoyant feasible schedule on the same instance—an external benchmark defined by the model, not by the algorithm or by any fitted parameter. The proof chain is: (i) regime partition into large / prompt-heavy / response-heavy; (ii) Rect with queue monotonicity and width-utilization (Lemmas 4–7, Propositions 2–3); (iii) Response with geometric caps and SPS packing (Theorem 3); (iv) black-box and routing meta-schedulers with explicit per-job completion multipliers (Lemmas 10–11). All charging is to Lemma 1 (area-order), Lemma 2 (deletion), and Lemma 3 (processing)—standard, algorithm-independent lower bounds. The only self-citation of substance is Fact 1 (SPS Peak and k* from Feng et al. 2026, overlapping authors). That fact is a deterministic peak-memory formula for an identical-prompt staggered schedule; Lemma 8 reduces the heterogeneous case to the proxy instance by domination (s_i ≤ τ_r), so feasibility is not assumed by fiat. The formula does not encode the target competitive ratio and is externally checkable from the stated Peak expression. There is no self-definitional loop, no fitted-input-as-prediction, no uniqueness theorem imported to forbid alternatives, and no renaming of an empirical pattern. Score 0 is therefore the correct outcome.

Assumptions & free parameters 2 free parameters · 5 assumptions · 3 invented entities

The result is pure competitive analysis in a discrete kill-and-restart memory model. Load-bearing modeling choices are individual feasibility and hard memory; algorithmic free choices are the prompt cutoff and geometric base. The only external algorithmic primitive is SPS peak memory from concurrent prior work. No empirical free parameters.

free parameters (2)
  • prompt cutoff Λ = M/4
    Set to M/4 to balance large-branch and prompt-heavy utilization constants (both become 36). Hand-chosen for clean constants, not fitted to data.
  • geometric scaling factor α = 2
    Response phase caps use α=2; other α>1 give O_α(1). Chosen for the explicit 236/3 ratio.
assumptions (5)
  • domain assumption Each job is individually feasible: s_i + o_i ≤ M for all i.
    Stated in Section 2; without it a single job can be infeasible and Opt is undefined in the model.
  • domain assumption Killing an active attempt discards all progress (restart model); no pause that retains partial decode state.
    Defines the non-clairvoyant cost of eviction; used throughout competitive analysis.
  • standard math System supplies at most M units of memory-time area per round; Opt ≥ area-order lower bound (Lemma 1).
    Standard packing lower bound used to charge algorithm waiting time against Opt.
  • domain assumption SPS peak memory Peak(k,τ,s) and k*(τ,s) bounds from Feng et al. 2026 (Fact 1) hold.
    Black-box input to Response feasibility (Lemma 8) and phase efficiency (Lemma 13).
  • domain assumption Clairvoyant Opt may not benefit from pause/preempt beyond delayed start (footnote in Section 2).
    Used to treat Opt as a clean benchmark; stated without full proof.
invented entities (3)
  • Three geometric regimes (large, small prompt-heavy, small response-heavy) with cutoff Λ
    purpose: Partition jobs so each class admits a constant-competitive specialized scheduler.
    Defined in Section 3; not a physical entity but a new algorithmic classification that the routing depends on.
  • Regime-aware routing meta-scheduler (Route)
    purpose: Time-share one memory budget and certify response-heavy jobs online without knowing o_i a priori.
    Core algorithmic contribution (Algorithm 4); competitive loss bounded in Lemma 11.
  • Non-clairvoyant rectangle-strip scheduler Rect with area-budget queue monotonicity
    purpose: Handle large and prompt-heavy jobs as fixed-width rectangles with geometric caps.
    Section 4; claimed of independent interest for strip scheduling.

how reviews work

0 comments
Cite this review

Pith. "Pith review of General Non-Clairvoyant KV-Cache Scheduling via Regime-Aware Routing." pith.science (2026). https://pith.science/paper/NMIX6A55

@misc{pith2026260709248,
  author       = {Pith},
  title        = {Pith review of: General Non-Clairvoyant KV-Cache Scheduling via Regime-Aware Routing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NMIX6A55}},
  note         = {Machine review of arXiv:2607.09248}
}
read the original abstract

We study non-clairvoyant scheduling for batched Large Language Model (LLM) inference under a hard Key-Value (KV) cache memory budget. Each request has a known prompt length but an unknown response length, and its memory footprint comprises a fixed prompt component together with a response component that grows with each decoded token. At each decoding round, the scheduler chooses a feasible batch of active requests; evicting a request discards its accumulated cache states, wasting prior computation. The goal is to minimize total completion time against the optimal clairvoyant schedule that knows all response lengths. We present the first constant-competitive algorithm for arbitrary prompt lengths and arbitrary response lengths with no additional assumptions. Rather than relying on a single universal scheduling policy, our algorithm is built on a novel regime-aware routing framework. Specialized sub-schedulers handle different memory-growth geometries, while a meta-scheduler time-shares the memory budget across them and dynamically routes each job as its execution progressively reveals its behavior. This framework also yields constant-competitive guarantees for makespan and for total completion time under online arrivals.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 19 canonical work pages

  1. [1]

    Hardness of approximation for strip packing

    Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, and Michal Pilipczuk. Hardness of approximation for strip packing. ACM Trans. Comput. Theory , 9 0 (3): 0 14:1--14:7, 2017. doi:10.1145/3092026. URL https://doi.org/10.1145/3092026

    work page doi:10.1145/3092026 2017

  2. [2]

    Approximating minimum-area rectangular and convex containers for packing convex polygons

    Helmut Alt, Mark de Berg, and Christian Knauer. Approximating minimum-area rectangular and convex containers for packing convex polygons. J. Comput. Geom., 8 0 (1): 0 1--10, 2017. doi:10.20382/JOCG.V8I1A1. URL https://doi.org/10.20382/jocg.v8i1a1

    work page doi:10.20382/jocg.v8i1a1 2017

  3. [3]

    Optimizing LLM inference: Fluid-guided online scheduling with memory constraints

    Ruicheng Ao, Gan Luo, David Simchi - Levi, and Xinshang Wang. Optimizing LLM inference: Fluid-guided online scheduling with memory constraints. CoRR, abs/2504.11320, 2025. doi:10.48550/ARXIV.2504.11320. URL https://doi.org/10.48550/arXiv.2504.11320

    arXiv doi:10.48550/arxiv.2504.11320 2025

  4. [4]

    Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines

    Luca Becchetti and Stefano Leonardi. Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM , 51 0 (4): 0 517--539, 2004. doi:10.1145/1008731.1008732. URL https://doi.org/10.1145/1008731.1008732

    doi:10.1145/1008731.1008732 2004

  5. [5]

    Semi-clairvoyant scheduling

    Luca Becchetti, Stefano Leonardi, Alberto Marchetti - Spaccamela, and Kirk Pruhs. Semi-clairvoyant scheduling. Theor. Comput. Sci., 324 0 (2-3): 0 325--335, 2004. doi:10.1016/J.TCS.2004.05.023. URL https://doi.org/10.1016/j.tcs.2004.05.023

    work page doi:10.1016/j.tcs.2004.05.023 2004

  6. [6]

    Non-clairvoyant scheduling with partial predictions

    Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predictions. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 3506--3538. PMLR , 2024. URL https://proceedings.mlr.press/v235/benomar24a.html

    2024

  7. [7]

    Non-clairvoyant scheduling with progress bars

    Ziyad Benomar, Romain Cosson, Alexander Lindermayr, and Jens Schl \" o ter. Non-clairvoyant scheduling with progress bars. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2025, NeurIPS 2025 , 2025. URL https://papers.nips.cc/paper_files/paper/2025/hash/868f2266086530b2c71006ea1908b14a-Abs...

    2025

  8. [8]

    Natarajan, and Clifford Stein

    Chandra Chekuri, Rajeev Motwani, B. Natarajan, and Clifford Stein. Approximation techniques for average completion time scheduling. SIAM J. Comput. , 31 0 (1): 0 146--166, 2001. doi:10.1137/S0097539797327180. URL https://doi.org/10.1137/S0097539797327180

    work page doi:10.1137/s0097539797327180 2001

Show all 43 references
  1. [9]

    Online scheduling via gradient descent for weighted flow time minimization

    Qingyun Chen, Sungjin Im, and Aditya Petety. Online scheduling via gradient descent for weighted flow time minimization. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, Ja...

    2025 doi

  2. [10]

    Adaptively robust LLM inference optimization under prediction uncertainty

    Zixi Chen, Yinyu Ye, and Zijie Zhou. Adaptively robust LLM inference optimization under prediction uncertainty. CoRR, abs/2508.14544, 2025 b . doi:10.48550/ARXIV.2508.14544. URL https://doi.org/10.48550/arXiv.2508.14544

    2025 doi arXiv

  3. [11]

    A theoretical and empirical study of job scheduling in cloud computing environments: The weighted completion time minimization problem with capacitated parallel machines

    Ilan Reuven Cohen, Izack Cohen, and Iyar Zaks. A theoretical and empirical study of job scheduling in cloud computing environments: The weighted completion time minimization problem with capacitated parallel machines. Ann. Oper. Res., 338 0 (1): 0 429--452, 2024. doi:10.1007/S...

    2024 doi

  4. [12]

    J. G. Dai, Tianze Deng, Yueying Li, and Tianyi Peng. Throughput-optimal scheduling algorithms for LLM inference and AI agents. CoRR, abs/2504.07347, 2025. doi:10.48550/ARXIV.2504.07347. URL https://doi.org/10.48550/arXiv.2504.07347

    2025 doi arXiv

  5. [13]

    Lower bounds for on-line single-machine scheduling

    Leah Epstein and Rob van Stee. Lower bounds for on-line single-machine scheduling. Theor. Comput. Sci., 299 0 (1-3): 0 439--450, 2003. doi:10.1016/S0304-3975(02)00488-7. URL https://doi.org/10.1016/S0304-3975(02)00488-7

    2003 doi

  6. [14]

    Competitive non-clairvoyant kv-cache scheduling for LLM inference

    Yiding Feng, Zonghan Yang, and Yuhao Zhang. Competitive non-clairvoyant kv-cache scheduling for LLM inference. CoRR, abs/2601.22996, 2026. doi:10.48550/ARXIV.2601.22996. URL https://doi.org/10.48550/arXiv.2601.22996

    2026 doi

  7. [15]

    Efficient LLM scheduling by learning to rank

    Yichao Fu, Siqi Zhu, Runlong Su, Aurick Qiao, Ion Stoica, and Hao Zhang. Efficient LLM scheduling by learning to rank. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Advances in Neural Information Pr...

    2024

  8. [16]

    Hall, Andreas S

    Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res., 22 0 (3): 0 513--544, 1997. doi:10.1287/MOOR.22.3.513. URL https://doi.org/10.1287/moor.22.3.513

    1997 doi

  9. [17]

    Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints

    Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. J. ACM , 65 0 (1): 0 3:1--3:33, 2018. doi:10.1145/3136754. URL https://doi.org/10.1145/3136754

    2018 doi

  10. [18]

    Non-clairvoyant scheduling with predictions

    Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. ACM Trans. Parallel Comput. , 10 0 (4): 0 19:1--19:26, 2023. doi:10.1145/3593969. URL https://doi.org/10.1145/3593969

    2023 doi

  11. [19]

    Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling

    Sven J \" a ger, Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt, and Philipp Warode. Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling. Math. Program., 210 0 (1): 0 457--509, 2025. doi:10.1007/S10107-024-02118-8. URL https://doi.org/10...

    2025 doi

  12. [20]

    The power of proportional fairness for nonclairvoyant polytope scheduling

    Sven J \" a ger, Alexander Lindermayr, and Nicole Megow. The power of proportional fairness for nonclairvoyant polytope scheduling. SIAM J. Comput. , 55 0 (2): 0 247--279, 2026. doi:10.1137/25M1763974. URL https://doi.org/10.1137/25M1763974

    2026 doi

  13. [21]

    Online scheduling for llm inference with kv cache constraints

    Patrick Jaillet, Jiashuo Jiang, Konstantina Mellou, Marco Molinaro, Chara Podimata, and Zijie Zhou. Online scheduling for llm inference with kv cache constraints. arXiv preprint arXiv:2502.07115, 2025. URL https://arxiv.org/abs/2502.07115

    2025

  14. [22]

    Closing the gap for single resource constraint scheduling

    Klaus Jansen and Malin Rau. Closing the gap for single resource constraint scheduling. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, Lisbon, Portugal (Virtual Conference), September 6-8, 2021 , volume 204 of...

    2021 doi

  15. [23]

    Maximizing the total profit of rectangles packed into a rectangle

    Klaus Jansen and Guochuan Zhang. Maximizing the total profit of rectangles packed into a rectangle. Algorithmica, 47 0 (3): 0 323--342, 2007. doi:10.1007/S00453-006-0194-5. URL https://doi.org/10.1007/s00453-006-0194-5

    2007 doi

  16. [24]

    Geometry-aware online scheduling for llm serving: From theoretical bound to system practice

    Li Kong, Qi Qi, Yinyu Ye, and Zijie Zhou. Geometry-aware online scheduling for llm serving: From theoretical bound to system practice. arXiv preprint arXiv:2606.22327, 2026

    2026 arXiv

  17. [25]

    Improved approximations for translational packing of convex polygons

    Adam Kurpisz and Silvan Suter. Improved approximations for translational packing of convex polygons. In Inge Li G rtz, Martin Farach - Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, The Netherlands, Se...

    2023 doi

  18. [26]

    Efficient memory management for large language model serving with pagedattention

    Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Jason Flinn, Margo I. Seltzer, Peter Druschel, Antoine Kaufmann, and...

    2023 doi

  19. [27]

    Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations

    Shi Li. Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. SIAM J. Comput. , 49 0 (4), 2020. doi:10.1137/17M1156332. URL https://doi.org/10.1137/17M1156332

    2020 doi

  20. [28]

    Two-dimensional packing problems: A survey

    Andrea Lodi, Silvano Martello, and Michele Monaci. Two-dimensional packing problems: A survey. Eur. J. Oper. Res., 141 0 (2): 0 241--252, 2002. doi:10.1016/S0377-2217(02)00123-6. URL https://doi.org/10.1016/S0377-2217(02)00123-6

    2002 doi

  21. [29]

    Sasha Luccioni, Yacine Jernite, and Emma Strubell. Power hungry processing: Watts driving the cost of AI deployment? In The 2024 ACM Conference on Fairness, Accountability, and Transparency, FAccT 2024, Rio de Janeiro, Brazil, June 3-6, 2024 , pages 85--99. ACM , 2024. doi:10....

    2024 doi

  22. [30]

    Phillips, and Eric Torng

    Rajeev Motwani, Steven J. Phillips, and Eric Torng. Non-clairvoyant scheduling. Theor. Comput. Sci., 130 0 (1): 0 17--47, 1994. doi:10.1016/0304-3975(94)90151-1. URL https://doi.org/10.1016/0304-3975(94)90151-1

    1994 doi

  23. [31]

    Efficiently scaling transformer inference

    Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. In Dawn Song, Michael Carbin, and Tianqi Chen, editors, Proceedings of the Sixth Conference on ...

    2023

  24. [32]

    Kalbarczyk, Tamer Basar, and Ravishankar K

    Haoran Qiu, Weichao Mao, Archit Patke, Shengkun Cui, Saurabh Jha, Chen Wang, Hubertus Franke, Zbigniew T. Kalbarczyk, Tamer Basar, and Ravishankar K. Iyer. Efficient interactive LLM serving with proxy model-based sequence length prediction. CoRR, abs/2404.08509, 2024. doi:10.4...

    2024 doi arXiv

  25. [33]

    Wayne E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3 0 (1-2): 0 59--66, 1956. doi:10.1002/nav.3800030106. URL https://doi.org/10.1002/nav.3800030106

    1956 doi

  26. [34]

    Steinberg

    A. Steinberg. A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. , 26 0 (2): 0 401--409, 1997. doi:10.1137/S0097539793255801. URL https://doi.org/10.1137/S0097539793255801

    1997 doi

  27. [35]

    TAPAS: thermal- and power-aware scheduling for LLM inference in cloud platforms

    Jovan Stojkovic, Chaojie Zhang, \' I \ n igo Goiri, Esha Choukse, Haoran Qiu, Rodrigo Fonseca, Josep Torrellas, and Ricardo Bianchini. TAPAS: thermal- and power-aware scheduling for LLM inference in cloud platforms. In Lieven Eeckhout, Georgios Smaragdakis, Katai Liang, Adrian...

    2025 doi

  28. [36]

    Dynamollm: Designing LLM inference clusters for performance and energy efficiency

    Jovan Stojkovic, Chaojie Zhang, \' I \ n igo Goiri, Josep Torrellas, and Esha Choukse. Dynamollm: Designing LLM inference clusters for performance and energy efficiency. In IEEE International Symposium on High Performance Computer Architecture, HPCA 2025, Las Vegas, NV, USA, M...

    2025 doi

  29. [37]

    Llumnix: Dynamic scheduling for large language model serving

    Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li, and Wei Lin. Llumnix: Dynamic scheduling for large language model serving. In Ada Gavrilovska and Douglas B. Terry, editors, 18th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2024,...

    2024

  30. [38]

    La Poutr \' e

    Rob van Stee and Johannes A. La Poutr \' e . Minimizing the total completion time on-line on a single machine, using restarts. J. Algorithms, 57 0 (2): 0 95--129, 2005. doi:10.1016/J.JALGOR.2004.10.001. URL https://doi.org/10.1016/j.jalgor.2004.10.001

    2005 doi

  31. [39]

    Gomez, Lukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30, pages 5998--6008, 2017. URL https://proceedings.neurips.cc/paper_fi...

    2017

  32. [40]

    LLM serving optimization with variable prefill and decode lengths

    Meixuan Wang, Yinyu Ye, and Zijie Zhou. LLM serving optimization with variable prefill and decode lengths. CoRR, abs/2508.06133, 2025. doi:10.48550/ARXIV.2508.06133. URL https://doi.org/10.48550/arXiv.2508.06133

    2025 doi arXiv

  33. [41]

    Orca: A distributed serving system for transformer-based generative models

    Gyeong - In Yu, Joo Seong Jeong, Geon - Woo Kim, Soojeong Kim, and Byung - Gon Chun. Orca: A distributed serving system for transformer-based generative models. In Marcos K. Aguilera and Hakim Weatherspoon, editors, 16th USENIX Symposium on Operating Systems Design and Impleme...

    2022

  34. [42]

    Gonzalez, Clark W

    Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark W. Barrett, and Ying Sheng. Sglang: Efficient execution of structured language model programs. In Amir Globersons, Lester Mack...

    2024

  35. [43]

    Response length perception and sequence scheduling: An llm-empowered LLM inference pipeline

    Zangwei Zheng, Xiaozhe Ren, Fuzhao Xue, Yang Luo, Xin Jiang, and Yang You. Response length perception and sequence scheduling: An llm-empowered LLM inference pipeline. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances...

    2023

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.