Pith. sign in

REVIEW 5 major objections 6 minor 37 references

This paper claims that a resource-fair scheduling constraint bounding decode-progress disparity can be enforced by a hybrid batching policy, ISJL, that retains at least 3/4 of optimal fair-schedule throughput while bounding the batching ext

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-04 10:47 UTC pith:S4SZ4G7Z

load-bearing objection The B=2 analysis and the cost decomposition are real contributions; the advertised 3/4 guarantee for all batch sizes is not actually proven. the 5 major comments →

arxiv 2608.02244 v1 pith:S4SZ4G7Z submitted 2026-08-03 cs.DC cs.SYeess.SY

Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling

Dayi Yao , Zijie Zhou This is my paper
classification cs.DC cs.SYeess.SY MSC 68M2090B35
keywords resource-fair schedulingLLM servingbatching externalityKV cachecompetitive ratiocontinuous batchingtoken-metered pricingthroughput guarantee
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper tries to establish that the decode-phase batching externality in LLM serving — short requests paying latency and GPU cost set by longer co-batched requests — can be controlled without giving up much throughput. It formalizes resource fairness as a constraint that keeps decode progress, equivalently KV-cache footprint, within α tokens across each batch. It then proposes ISJL, a hybrid batching policy, and proves a worst-case competitive ratio of 3/4 against the optimal fair schedule for any batch size B≥2. Under token-metered pricing, it proves a cost decomposition showing that fairness bounds the schedule-induced batching externality by α times total token workload, so profit loss is additive and controlled. A reader should care because this turns a known systems pathology into a quantifiable scheduling trade-off with an explicit tunable budget.

Core claim

At the center of the paper is the claim that bounded resource heterogeneity is enough to make efficient batching fair: if every active batch has max–min decode progress at most α, then the max-driven per-step cost stays close to each request's own footprint. The paper proves that ISJL, which packs short jobs around the longest active job and then fills freed slots while the progress spread is still ≤α, achieves at least 3/4 of the optimal α-fair schedule's throughput on every backlogged instance. It sharpens this to a piecewise bound in γ=α/o1, with the minimum 3/4 exactly at γ=1/2. It further proves that any α-fair schedule has batching externality at most αO(I), and combines this with the

What carries the argument

The central object is the α-fairness constraint: at every time step, the difference between the largest and smallest decode progress (equivalently, KV-cache size) among co-batched requests is at most α. ISJL is the mechanism built on this constraint: Phase ONE packs short jobs under per-worker budgets min{2α, o1−oj+α} around the longest requests, and Phase TWO continuously admits the longest unprocessed request whenever the current maximum progress is ≤α. The adversarial analysis splits losses into over-inserting and under-inserting cases; a standard list-scheduling bound covers Phase TWO. On the cost side, the paper decomposes inference cost into a schedule-independent workload term τQ(I),

Load-bearing premise

The whole argument rests on a compute-bound model in which a batch step's wall-clock cost is governed by the longest KV-cache footprint and every step advances every active request one token; in a memory-bound regime, or if GPU cost scales with total tokens rather than the max, the fairness constraint does not control real latency or cost.

What would settle it

Measure per-step wall-clock latency of a fixed batch while varying one request's KV-cache length and holding all others short; if latency grows with total tokens rather than the max, the max-driven cost premise and the externality bound E≤αO(I) fail on real hardware.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • If the 3/4 bound is correct, any backlogged workload served with ISJL is guaranteed at least 75% of the throughput of the best possible α-fair schedule, while every batch keeps its KV-cache spread within α tokens.
  • The fairness parameter α becomes a tunable dial: small α approaches LJF's cost alignment, large α recovers continuous batching's throughput, and the γ-dependent bound tells the operator where the worst case is.
  • Under token-metered pricing, the batching externality is bounded by α times the total token workload, so a provider can compute an upper bound on the profit lost to unfair co-batching before running anything.
  • When output lengths are unknown, Robust-ISJL still satisfies the fairness constraint and keeps a 3/4-style guarantee degraded only by the packable residual prediction error, not by raw upper-bound slack.
  • In the online arrival model, no deterministic policy can guarantee the offline 3/4 ratio against a clairvoyant optimum, so the guarantee is specifically for backlogged instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same fairness-budget mechanism should transfer to memory-bound serving if α is expressed in KV-cache bytes instead of tokens; the externality bound would then bound HBM footprint spread rather than wall-clock latency.
  • The γ-dependent bound suggests α should be calibrated relative to the longest request, with γ≈1/2 as the most robust default; operators can set α≈o1/2 without knowing the full length distribution.
  • The paper's many-server pooling discussion implies a testable prediction: ISJL's advantage over FCFS should shrink as the pending pool grows, since length-clustering alone can form homogeneous batches.
  • The cost decomposition gives operators a direct accounting tool: measure E_A from logs and the fairness constraint's dollar cost is known exactly, making α a budgetary rather than heuristic choice.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 6 minor

Summary. The paper studies a scheduling problem for batched LLM decode, formalizing the max-driven KV-cache externality as a resource-fairness constraint that bounds the decode-progress gap among co-batched requests. It proposes LJF as a fully fair baseline and ISJL as a hybrid policy, claiming a competitive-ratio lower bound of 3/4 for ISJL for all batch sizes B≥2, a parameterized bound CR(γ), a robustness extension under interval-length predictions, and a profit decomposition under token-metered pricing. The paper also reports simulations on synthetic workloads and LMSYS-Chat-1M.

Significance. If the 3/4 guarantee were established, the paper would make a useful contribution: it gives a clean formal model of an important operational externality in LLM serving, a concrete policy with a worst-case throughput certificate, and a cost decomposition that separates schedule-dependent makespan effects from batching-externality effects. The explicit scope limitations (offline backlog model, compute-bound regime, exogenous demand) and the online impossibility result are praiseworthy. However, the main theorem currently rests on an unproven generalization from B=2 to B≥2, so the paper's central claim is conditional until that proof is supplied.

major comments (5)
  1. [Section 3.3, Theorem 3] The B≥2 proof is a sketch, not a proof. It asserts that for each i∈[2,B], considering o1 and o_i, idle time is bounded by Lemma 2 or 3, and that Phase TWO is bounded by Proposition 3. Lemmas 2–3 are proven for a single B=2 stage with one L_r, one S_r, and one P_r. In Phase ONE of Algorithm 3, up to B−1 short-job packs run concurrently with o1, and the stage makespan is a maximum over workers, not a sum. Pairwise idle-time bounds do not lower-bound the combined B-worker makespan; a coupled argument is required. The appendix proves only the two B=2 lemmas. Since Theorem 3 is the load-bearing 3/4 claim, this gap must be closed.
  2. [Section 3.2, Proposition 3] The Phase TWO analysis invokes Graham's LPT bound, but Phase TWO is not unconstrained list scheduling. In both Algorithm 2 and Algorithm 3, a new job is admitted only if the fairness check A_max≤α is satisfied; otherwise the algorithm breaks and re-enters Phase ONE, creating idle time and restarts absent from Graham's model. Moreover, Graham's LPT bound assumes all jobs are initially available and no prior loads, whereas Phase TWO starts after Phase ONE has created partial progress. Thus the statement that Phase TWO is bounded by 3B/(4B−1) is unsupported, and this affects both Theorem 2 and Theorem 3.
  3. [Section 3.3, Algorithm 3] Algorithm 3 is under-specified. Lines 18–21 never explicitly instruct worker 1 to run o1; line 19 says to idle worker 1, which conflicts with the prose that o1 is held on worker 1. The Phase TWO admission test can block o2 because o2's progress is 0 while o1 has advanced beyond α, and the text defines A_max inconsistently as 'maximum remaining processing time' one place and 'current maximum output length' in the pseudocode. Cases where M<2 or where no job satisfies the threshold for o_k are not defined. Without a precise event-driven specification, the claimed fairness invariant and makespan bound cannot be checked.
  4. [Section 4.2, Theorem 6] The 'Generalization' paragraph repeats the same pairwise reduction: for each i∈[2,B], consider o1 and o_i and apply Lemmas 4–5. No argument is given that the combined B-worker makespan obeys the same lower envelope CR(γ); the appendix proves only the B=2 lemmas. Consequently, the refined parameterized bound inherits the gap in Theorem 3 and cannot be considered established for B≥2.
  5. [Section 3.2, Lemmas 2–3] The ratio orientation should be reconciled with the definition of CR in Section 2. Lemma 2 says CR(ISJL) = (L_r+P_r)/(S_r+P_r+Q_r) and claims it increases in L_r and decreases in S_r,Q_r; that is the behavior of ALG/OPT, whereas the paper defines CR = OPT/ALG. Lemma 3 uses the opposite orientation. The inequality directions in Lemmas 2–3 and Theorem 2 need to be consistent, or the B=2 lower bound is not derived correctly.
minor comments (6)
  1. [Section 3.1] The proof of Theorem 1 states 'W.L.O.G., let nB jobs', which silently assumes n is a multiple of B. The leftover-jobs case should be handled or explicitly discounted.
  2. [Section 3.2] The sentence 'Noticing that the competitive ratio in Phase TWO is larger than that obtained in Phase ONE' appears to have the direction wrong: the Graham bound gives 3/4, while the Phase ONE optimum is about 0.77. Please correct.
  3. [Section 4.1] The Jigsaw Effect discussion says Proposition 3 gives a competitive-ratio bound 'under this adversary' without explaining how Graham's LPT bound transfers to ISJL's phase structure. This needs a proper derivation or should be removed.
  4. [Section 5.2 / Section 6] Numerical results are reported without error bars or significance tests. Table 3 appears to be a single realization; Section 5.2 says values are averages over five replications but gives no standard deviations. Please report variability and number of seeds.
  5. [Proposition 1] The NP-hardness claim cites Lee and Chen (2001), a transportation-scheduling paper, without a direct reduction. Since this proposition is not load-bearing for the main results, please either provide a direct reduction or replace the citation with one that supports the exact unconstrained model.
  6. [General] There are small presentation issues: 'Correspondance' should be 'Correspondence'; Figures referenced as 'Figure below' are not numbered or embedded in the text; the caption of Table 2 uses values for τE that differ slightly from Table 1.

Circularity Check

0 steps flagged

No significant circularity: the 3/4 bound is derived from an adversarial analysis and an external Graham bound, with only contextual self-citations.

full rationale

The central claim is Theorem 3, CR(ISJL) >= 3/4 for all B >= 2. The derivation chain is: the fairness constraint (Eq. 1) defines feasible batches; Lemma 2 and Lemma 3 bound the B=2 stage cost under over- and under-inserting adversaries; Proposition 3 (Graham 1969) is invoked as an external list-scheduling bound for Phase TWO; and Theorem 3 combines these pieces for B>=2. None of these steps fits a parameter to the data being 'predicted': alpha and beta are algorithmic inputs, not calibrated values, and the competitive ratio is an infimum over all instances rather than an evaluation on fitted instances. The profit decomposition in Section 5 is also derived algebraically from the definitions of cost and externality, not assumed as the conclusion. The paper cites prior work by the same authors (Jaillet et al. 2025, Wang et al. 2025, Chen et al. 2025), but those citations are contextual framework references and are not load-bearing in the proof of Theorem 3 or Theorems 5-8. If the B>=2 generalization is underjustified because pairwise B=2 bounds do not automatically control the makespan of a multi-worker stage, that is a correctness gap, not circularity: the conclusion is not equivalent to an input by construction. The appropriate finding is therefore no significant circularity; the score of 2 reflects only the presence of minor, non-load-bearing self-citations.

Axiom & Free-Parameter Ledger

2 free parameters · 6 axioms · 0 invented entities

The theoretical results are self-contained relative to a logical-step inference model. The main domain assumptions are max-driven batch cost and the compute-bound regime; neither is empirically validated with wall-clock measurements. Graham's bound is imported as standard, and Robust-ISJL adds prediction intervals as inputs rather than fitted constants.

free parameters (2)
  • alpha (fairness budget) = operator-chosen; e.g., 50-500 in experiments
    Bounds allowed max-min decode progress within a batch. Central results hold for any alpha, so it is not fitted to make theorems work, but experiments sweep it.
  • beta (ISJL packing parameter) = (sqrt(17)-1)/4 * alpha for B=2; beta = alpha for B>=2
    Chosen to maximize the competitive lower bound in Theorem 2; derived analytically, not fitted to data.
axioms (6)
  • domain assumption Max-driven wall-clock batch cost: per-step cost is governed by the largest active KV-cache footprint, not the sum or average.
    Section 2 uses this to justify the fairness constraint and the batching externality. If false, the central motivation weakens.
  • domain assumption Logical token-step abstraction: makespan counts scheduling steps, each advancing every active request by one token, with equal cost per step.
    Section 2 explicitly separates the step count from GPU milliseconds, so competitive ratios are about steps, not wall-clock time.
  • domain assumption Compute-bound regime: only the number of concurrent requests B constrains the batch; KV memory is not a binding constraint.
    Remark 2 states this is the regime adopted; memory-bound regimes are left to future work.
  • domain assumption Offline clairvoyance: true output lengths o_i are known at admission time for the main competitive-ratio results.
    Stated in Section 2; relaxed in Section 3.4 via prediction intervals.
  • standard math Graham's multiprocessor list-scheduling bound: makespan of Phase TWO is at most (4/3 - 1/(3B)) times optimal.
    Proposition 3 imports this as an external standard result used to bound Phase TWO.
  • domain assumption Exogenous token-metered linear pricing and fixed accepted workload.
    Section 5 assumes revenue is additive and schedule-independent; demand response is explicitly out of scope.

pith-pipeline@v1.3.0-daily-deepseek · 31543 in / 15062 out tokens · 175828 ms · 2026-08-04T10:47:50.859996+00:00 · methodology

0 comments
read the original abstract

This paper studies a resource-allocation inefficiency in batched large language model (LLM) serving: heterogeneous requests that share a decode batch impose max-driven computational costs on one another. Because the wall-clock cost of a batch step is largely governed by the largest active KV-cache footprint, a short request co-batched with a long request can experience latency and GPU-resource consumption disproportionate to its own token workload. We formalize this phenomenon as a resource-fair scheduling problem. We develop a mathematical scheduling model that connects within-batch resource fairness to system throughput. The proposed fairness constraint bounds the disparity in decode progress, equivalently KV-cache footprint, among co-batched requests. Based on this model, we design the Insert-Short-Jobs-with-Limit (ISJL) algorithm, a parameterized hybrid batching policy. We prove that ISJL achieves a global competitive-ratio lower bound of $3/4$. We further examine the profit implications of resource-fair scheduling under the token-metered pricing convention used by commercial LLM APIs. Numerical experiments show that ISJL occupies a favorable middle ground between FCFS, which has large batching externalities, and LJF, which is cost-aligned but sacrifices batching flexibility. Thus, ISJL provides a bi-criterion scheduling policy: it maintains high throughput while aligning max-driven batch cost with token-metered revenue.

Figures

Figures reproduced from arXiv: 2608.02244 by Dayi Yao, Zijie Zhou.

Figure 1
Figure 1. Figure 1: An example of LJF Proposition 2. Algorithm LJF is fair, which satisfies the constraint (1) for any α > 0. Proposition 2 states that LJF is fair for any α > 0. The proof is straightforward: within any batch S (t) , all requests start simultaneously. Therefore, the instantaneous acceleration for each request is equal, i.e., maxi∈S(t) a (t) i = mini∈S(t) a (t) i , satisfying the fairness condition. However, a… view at source ↗
Figure 2
Figure 2. Figure 2: Over and Under Inserting Lemma 2 (Cost of over-inserting 2). For any stage r of Phase ONE, the worst competitive ratio 14 [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Jigsaw Effect Jigsaw Effect As shown in [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Competitive Ratio as a Function of γ 27 [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Cost decomposition and profit–throughput frontier under linear pricing. [PITH_FULL_IMAGE:figures/full_fig_p035_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Profit difference between ISJL and LJF as the fixed per-step overhead [PITH_FULL_IMAGE:figures/full_fig_p036_6.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 1 canonical work pages

  1. [8]

    Evaluating the feasibility of ChatGPT in healthcare: an analysis of multiple clinical and research scenarios.Journal of medical systems47, 1 (2023),

    2023

  2. [9]

    Bo Chen, Chris N Potts, and Gerhard J Woeginger

    Logistics scheduling with batching and transportation.European journal of operational research189, 3 (2008), 871–876. Bo Chen, Chris N Potts, and Gerhard J Woeginger

    2008

  3. [12]

    Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al

    Adaptively Robust LLM Inference Optimization under Prediction Uncertainty.arXiv preprint arXiv:2508.14544(2025). Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al

    Pith/arXiv arXiv 2025

  4. [13]

    40 DeepSeek

    Palm: Scaling language modeling with pathways.Journal of Machine Learning Research24, 240 (2023), 1–113. 40 DeepSeek

    2023

  5. [14]

    Accessed: 2026-06-10

    Models & Pricing — DeepSeek API Docs.https://api-docs.deepseek.com/quick_ start/pricing. Accessed: 2026-06-10. Naveen Garg, Anupam Gupta, Amit Kumar, and Sahil Singla

    2026

  6. [16]

    Online resource allocation with convex-set machine- learned advice.arXiv preprint arXiv:2306.12282(2023). Google

    Pith/arXiv arXiv 2023

  7. [17]

    Ac- cessed: 2026-06-10

    Gemini Developer API Pricing.https://ai.google.dev/gemini-api/docs/pricing. Ac- cessed: 2026-06-10. R. L. Graham

    2026

  8. [19]

    Patrick Jaillet, Jiashuo Jiang, Konstantina Mellou, Marco Molinaro, Chara Podimata, and Zijie Zhou

    Orlm: A customizable framework in training large models for automated optimization modeling.Operations Research(2025). Patrick Jaillet, Jiashuo Jiang, Konstantina Mellou, Marco Molinaro, Chara Podimata, and Zijie Zhou

    2025

  9. [20]

    Redwan Ibne Seraj Khan, Kunal Jain, Haiying Shen, Ankur Mallick, Anjaly Parayil, Anoop Kulkarni, Steve Kofsky, Pankhuri Choudhary, Renee St Amant, Rujia Wang, et al

    Online Scheduling for LLM Inference with KV Cache Constraints.arXiv preprint arXiv:2502.07115 (2025). Redwan Ibne Seraj Khan, Kunal Jain, Haiying Shen, Ankur Mallick, Anjaly Parayil, Anoop Kulkarni, Steve Kofsky, Pankhuri Choudhary, Renee St Amant, Rujia Wang, et al

    arXiv 2025

  10. [21]

    Qingxia Kong, Chung-Yee Lee, Chung-Piaw Teo, and Zhichao Zheng

    Ensuring Fair LLM Serving Amid Diverse Applications.arXiv preprint arXiv:2411.15997(2024). Qingxia Kong, Chung-Yee Lee, Chung-Piaw Teo, and Zhichao Zheng

    Pith/arXiv arXiv 2024

  11. [24]

    Online batch scheduling of simple linear deteri- orating jobs with incompatible families.Mathematics8, 2 (2020),

    2020

  12. [27]

    Appointment scheduling with limited distributional information.Management Science61, 2 (2015), 316–334. OpenAI

    2015

  13. [28]

    arxiv 2303.08774.View in Article2, 5 (2023)

    GPT-4 technical report. arxiv 2303.08774.View in Article2, 5 (2023). OpenAI

    Pith/arXiv arXiv 2023

  14. [29]

    Accessed: 2026-06-10

    API Pricing.https://openai.com/api/pricing/. Accessed: 2026-06-10. 41 Pratyush Patel, Esha Choukse, Chaojie Zhang, Aashaka Shah, ´I˜ nigo Goiri, Saeed Maleki, and Ricardo Bianchini

    2026

  15. [30]

    Julien Robert and Nicolas Schabanel

    Splitwise: Efficient generative LLM inference using phase splitting.Power400, 700W (2023), 1–75. Julien Robert and Nicolas Schabanel

    2023

  16. [31]

    In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, Shang-Hua Teng (Ed.)

    Non-clairvoyant scheduling with precedence constraints. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, Shang-Hua Teng (Ed.). SIAM, 491–500.http: //dl.acm.org/citation.cfm?id=1347082.1347136 Malik Sallam

    arXiv 2008

  17. [32]

    Rana Shahout, Eran Malach, Chunwei Liu, Weifan Jiang, Minlan Yu, and Michael Mitzenmacher

    The utility of ChatGPT as an example of large language models in healthcare education, research and practice: Systematic review on the future perspectives and potential limitations.MedRxiv (2023), 2023–02. Rana Shahout, Eran Malach, Chunwei Liu, Weifan Jiang, Minlan Yu, and Michael Mitzenmacher

    2023

  18. [33]

    Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E Gonzalez, and Ion Stoica

    Don’t Stop Me Now: Embedding Based Scheduling for LLMs.arXiv preprint arXiv:2410.01035(2024). Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E Gonzalez, and Ion Stoica

    Pith/arXiv arXiv 2024

  19. [34]

    Zhixiang Wei, James Yen, Jingyi Chen, Ziyang Zhang, Zhibai Huang, Chen Chen, Xingzi Yu, Yicheng Gu, Chenggang Wu, Yun Wang, et al

    LLM Serving Optimization with Variable Prefill and Decode Lengths.arXiv preprint arXiv:2508.06133(2025). Zhixiang Wei, James Yen, Jingyi Chen, Ziyang Zhang, Zhibai Huang, Chen Chen, Xingzi Yu, Yicheng Gu, Chenggang Wu, Yun Wang, et al

    Pith/arXiv arXiv 2025

  20. [35]

    Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun

    Equinox: Holistic Fair Scheduling in Serving Large Language Models.arXiv preprint arXiv:2508.16646(2025). Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun

    Pith/arXiv arXiv 2025

  21. [36]

    Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang

    LMSYS-Chat-1M: A large-scale real-world LLM conversation dataset.arXiv preprint arXiv:2309.11998(2023). Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang

    Pith/arXiv arXiv 2023

  22. [37]

    Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving.arXiv preprint arXiv:2401.09670(2024). 42 Online Appendix EC.1 Supplementary Materials for Section 3 EC.1.1 Optimal Scheduling with Integer Programming (IP) We index discrete time by a finite horizonHlarge enough to contain any feasible schedule (e.g., H= Pn ...

    Pith/arXiv arXiv 2024

  23. [1641]

    2023.Dissecting Batching Effects in GPT Inference

    Lequn Chen. 2023.Dissecting Batching Effects in GPT Inference. le.qun.ch.https://le.qun.ch/en/ blog/2023/05/13/transformer-batching/ Zixi Chen, Yinyu Ye, and Zijie Zhou

    2023

  24. [1969]

    Bounds on Multiprocessing Timing Anomalies.SIAM J. Appl. Math.17, 2 (1969), 416–429.http://www.jstor.org/stable/2099572 Chenyu Huang, Zhengyang Tang, Shixi Hu, Ruoqing Jiang, Xin Zheng, Dongdong Ge, Benyou Wang, and Zizhuo Wang

    arXiv 1969

  25. [1998]

    A review of machine scheduling: Complexity, algorithms and approximability.Handbook of Combinatorial Optimization: Volume1–3(1998), 1493–

    1998

  26. [2001]

    Wenhua Li, Libo Wang, Xing Chai, and Hang Yuan

    Machine scheduling with transportation considerations.Journal of scheduling4, 1 (2001), 3–24. Wenhua Li, Libo Wang, Xing Chai, and Hang Yuan

    2001

  27. [2002]

    doi:10.1016/S0166-218X(01)00272-4Special Issue devoted to Foundation of Heuristics in Combinatoria l Optimization

    On-line scheduling with precedence constraints.Discrete Applied Mathematics119, 1 (2002), 169–180. doi:10.1016/S0166-218X(01)00272-4Special Issue devoted to Foundation of Heuristics in Combinatoria l Optimization. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Aman...

    work page doi:10.1016/s0166-218x(01)00272-4special 2002

  28. [2008]

    A survey of scheduling problems with setup times or costs.European journal of operational research187, 3 (2008), 985–1032. Amazon

    2008

  29. [2013]

    Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica

    Scheduling arrivals to a stochastic service delivery system using copositive cones.Operations research61, 3 (2013), 711–726. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica

    2013

  30. [2015]

    Thodoris Lykouris and Sergei Vassilvitskii

    Online unbounded batch scheduling on parallel machines with delivery times.Journal of Combinatorial Optimization29 (2015), 228–236. Thodoris Lykouris and Sergei Vassilvitskii

    2015

  31. [2019]

    In46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece (LIPIcs, Vol

    Non-Clairvoyant Precedence Con- strained Scheduling. In46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece (LIPIcs, Vol. 132), Christel Baier, Ioannis Chatzigian- nakis, Paola Flocchini, and Stefano Leonardi (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 63:1–63:14. doi:10.4230/L...

    doi:10.4230/lipics.icalp.2019.63 2019

  32. [2020]

    Marco Cascella, Jonathan Montomoli, Valentina Bellini, and Elena Bignami

    Language models are few-shot learners.Advances in neural information processing systems33 (2020), 1877–1901. Marco Cascella, Jonathan Montomoli, Valentina Bellini, and Elena Bignami

    2020

  33. [2021]

    Ho-Yin Mak, Ying Rong, and Jiawei Zhang

    Competitive caching with machine learned advice.Journal of the ACM (JACM)68, 4 (2021), 1–25. Ho-Yin Mak, Ying Rong, and Jiawei Zhang

    2021

  34. [2023]

    Susanne Albers

    Sarathi: Efficient LLM inference by piggybacking decodes with chunked prefills.arXiv preprint arXiv:2308.16369(2023). Susanne Albers

    Pith/arXiv arXiv 2023

  35. [2024]

    Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, and Ramachandran Ramjee

    Taming throughput-latency tradeoff in LLM inference with Sarathi-Serve.arXiv preprint arXiv:2403.02310(2024). Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, and Ramachandran Ramjee

    Pith/arXiv arXiv 2024

  36. [2025]

    Yossi Azar and Leah Epstein

    Optimizing LLM Inference: Fluid- Guided Online Scheduling with Memory Constraints.arXiv preprint arXiv:2504.11320(2025). Yossi Azar and Leah Epstein

    Pith/arXiv arXiv 2025

  37. [2026]

    Accessed: 2026-06-10

    Pricing — Claude API Docs.https://platform.claude.com/docs/en/about-claude/ pricing. Accessed: 2026-06-10. Ruicheng Ao, Gan Luo, David Simchi-Levi, and Xinshang Wang

    2026