acceptodds
Under review as a conference paper at ICLR 2027

BIP: Online Scheduling for LLM Batch Inference with Predictions

Abstract

The growing deployment of large language models (LLMs) has created a large demand for offline batch inference, where jobs must be executed under deadlines on heterogeneous GPU clusters. Unlike online serving, this setting is throughput-driven and job-oriented. We introduce BIP, a scheduling framework that combines output-length prediction, rolling-horizon integer programming, and online correction of underestimated workloads. The scheduling model captures job deadlines, GPU-type-dependent speeds, parallel execution, and slot-boundary preemption. We develop three formulations for completed jobs, normalized service, and completion time, and establish the interpretation and feasibility conditions of their objectives. Simulations using batches constructed from instruction–response data show that the best-of-three formulation envelope improves deadline-completion rates over FCFS and SJF across the tested configurations. At normalized load 1.0 and relative job size 1.0, the corrected envelope completes 55.3% more jobs than FCFS and 32.4% more than SJF. These results demonstrate the potential of combining workload predictions with job-level deadline scheduling for offline LLM inference.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
LLM Inference, Scheduling

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_1eJiOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces a scheduling framework called BIP, which combines output-length prediction, rolling-horizon integer programming, and online correction of underestimated workloads. It captures job deadlines, GPU-type-dependent speeds, parallel execution, and slot-boundary preemption.

Critical strengths
  1. BIP combines instruction-tuned length prediction, rolling-horizon integer programming, and online workload correction.

  2. These three modes of expression cover, respectively, the throughput of completed tasks, normalized service levels, and task completion times subject to strict deadlines.

Critical weaknesses
  1. The reported performance relies on selecting the best-performing formulation among ILP-1, ILP-2, and ILP-3 after execution, whereas an online scheduler must commit to a policy before the actual completion rate is known.

  2. The current evaluation only compares BIP against FCFS and SJF. We recommend adding additional baseline methods to better demonstrate the effectiveness of the proposed framework.

  3. The extensibility of BIP is limited, as the predictive performance observed on reference answers may not necessarily apply directly to content generated by other models, nor to results produced using different decoding configurations.

  4. The scheduling results are derived from simulations and do not account for throughput, GPU utilization, or end-to-end service costs in terms of actual wall-clock time.

  5. A comprehensive related work investigation should be conducted, as several important recent works (2024-2026) are missing.

  6. The simulation results reported in this paper do not cover how solver runtime varies with problem scale, nor do they include statistics on feasibility or timeouts for the various modeling approaches.

  7. BIP employs an abstract model based on "constant speed" and "total workload," and it assumes that this model is pre-loaded. The authors should provide more detailed and realistic assumptions regarding these pre-loaded models.

  8. The evaluation is really limited, as only one figure is given for the deadline-completion rates across normalized-load settings and relative job sizes.

  9. There is no reproducibility statement, and the code is not available.

Questions for authors
  1. It is unclear how the individual job deadlines are generated in the experimental setup. Please explain the rationale for assigning deadlines.

  2. Can the proposed framework maintain its effectiveness when the target inference model changes? Please provide additional experimental results for both length prediction and task scheduling across different target LLMs.

  3. The reported performance relies on selecting the best-performing formulation among ILP-1, ILP-2, and ILP-3 after execution, whereas an online scheduler must commit to a policy before the actual completion rate is known. Please explain how a formulation should be selected at runtime.

Reviewer_oxzCOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies job-oriented scheduling for offline LLM batch inference on a heterogeneous GPU cluster. Each job consists of many prompts, has a release time and an individual deadline, and is counted as completed only if all of its prompts finish by that deadline. Because output lengths are unknown before decoding, the authors instruction-tune LLaMA3-8B with LoRA to predict per-prompt output token counts, aggregate these into a scalar per-job workload estimate W_j, and use them in a rolling-horizon integer program that re-allocates GPUs over H slots at every epoch and executes only the first slot. Three formulations are given — ILP-1 (weighted completed jobs), ILP-2 (weighted normalized service), ILP-3 (weighted completion time under hard deadlines) — together with an analysis of their feasibility and objective semantics (Prop. 1, Lemma 1). If a job remains unfinished after receiving at least its estimated workload, its effective workload is doubled and the plan recomputed. Validation is simulation-only, on synthetic batches constructed from Alpaca: the authors report 53.1% deadline-completion for the post-hoc best-of-three envelope at normalized load 1.0 and relative job size 1.0, against 34.2% (FCFS) and 40.1% (SJF). The two baselines do not consider deadlines, and the reported figures are selected after the runs rather than produced by a single pre-specified online policy.

Critical strengths

The problem formulation targets a real and underexplored objective. The observation that job-level completeness — a job counts as zero unless all of its prompts finish — makes request-level optimality insufficient is correct and consequential, and the deadline-completion objective corresponds to genuine production semantics: batch APIs such as OpenAI's cancel unfinished requests when the completion window expires, return the completed portion, and charge only for it.

Critical weaknesses
  1. The scheduling abstraction is not validated against actual LLM inference cost. WjW_j contains only predicted output tokens and excludes input-dependent prefill cost, while the fixed speed sts_t does not capture batch-dependent throughput, continuous batching, or KV-cache constraints. Consequently, jobs with similar predicted output lengths but substantially different execution costs can appear identical to the optimizer. Since the simulator adopts the same abstraction and no real-system calibration is provided, the evaluation cannot establish that the reported gains transfer to actual serving systems.
  2. The evidence does not support the claimed gains. FCFS and SJF ignore deadlines, while standard deadline-aware baselines such as EDF and least-laxity-first are absent. The reported BIP numbers are also post-hoc best-of-three envelopes over ILP-1/2/3, not results from a pre-specified online policy, and correction is not evaluated per formulation. Together with the unspecified deadline-generation rule and the unaccounted cost of the LLa
Questions for authors

Q1. How are deadlines generated, and what are the main simulation settings? Q2. What are the separate results for ILP-1/2/3, and which formulation would be selected online? Q3. How does BIP compare with simple deadline-aware baselines such as EDF or least-laxity-first? Q4. How does the predictor compare with existing output-length predictors, and how sensitive is deadline completion to prediction error?

Reviewer_bpQwOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper combines a scheduling framework with output prediction, mathematical programming, and online workload estimation. The authors provide modelling, prediction, and experiments to illustrate its effectiveness. They compare the scheduler with FCFS and SJF using synthetic batches.

Critical strengths

This paper provides a complete optimization framework from prediction to scheduling on inference. The ILP framework is important, clear, and well-defined.

Critical weaknesses

The experiments with simulation are weak. The baseline of FCFS and SJF is weak compared to existing work, hybrid offline-online scheduling method for LLM inference optimization, optimizing LLM inference: fluid-guided online scheduling with memory constraints, etc.

Questions for authors

Can you provide some end-to-end runtime experiments on LLM inference using a real LLM and real online arrivals to illustrate the effectiveness of your work? What is the solving time or overhead for your ILP? In related work, we find that solving time could be a bottleneck for mathematical programming models to employ.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.