How do you design deadline-aware batch inference scheduling and checkpoint recovery on interruptible GPUs?

Deadline-aware batch inference scheduling assigns large, deferrable LLM workloads to suitable GPU pools while ensuring jobs have a realistic chance of finishing before their deadlines. When cheaper Spot/preemptible GPUs disappear, workers should recover from durably committed job progress, avoid duplicate side effects, and escalate only work whose deadlines require more dependable capacity.

This lesson follows Question 273 (GPU purchasing options and online/batch pool separation), Question 253 (online request deadlines/cancellation) and Question 251 (tenant fairness). Here the focus is on batch job feasibility, remaining-work estimates, durable progress manifests, preemption-safe retries and deadline-driven escalation—not streaming failover or raw cost optimization.

1. Understand the different deadlines

• Job deadline: the externally agreed time by which *all required outputs* must be complete and validated, for example midnight UTC.
• Queue deadline: latest safe time to acquire enough GPUs and start computation so that the overall job remains feasible.
• Task timeout: upper bound for one document/shard attempt. Task timeout is not necessarily the overall job deadline.
• Recovery reserve: time budget for expected interruptions, checkpoint restore, model startup, output validation and object-store consistency.
• Hard versus soft deadline: a hard deadline may require reserved/on-demand GPUs, workload shedding and explicit failure; soft deadlines may trade increased waiting or cost for best-effort completion.

Important: Kubernetes Job \activeDeadlineSeconds\ is an elapsed runtime cap for a Job, not an absolute wall-clock business deadline. If exceeded, Kubernetes terminates running Pods and marks the Job failed; the scheduler must translate business due times into appropriate orchestration policies and requeue decisions.

2. Beginner-friendly feasibility calculation

Suppose a batch contains 12,000 documents, each requiring on average 2 seconds of measured GPU service for the approved model and input/output distribution.

• Total nominal GPU work: \12,000 × 2 = 24,000 GPU-seconds\.
• With 4 comparable GPUs at ideal full effectiveness: \24,000 / 4 = 6,000 seconds = 100 minutes\.
• At an observed end-to-end 80% effective processing efficiency (startup, packing, queue, variable lengths and write overhead): \6,000 / 0.8 = 7,500 seconds = 125 minutes\.
• Add 15 minutes for a conservative measured failure/restore and quality-validation allowance: 140 minutes.
• If the deadline is 150 minutes away, only 10 minutes of slack remain.

If admission predicts 20 minutes of waiting for Spot GPUs, the job is no longer feasible under this configuration because \20 + 140 = 160 > 150\ minutes. The scheduler should increase reliable capacity, change the approved execution plan, or report infeasibility, not quietly admit it as an on-time job.

All throughput and recovery numbers are illustrative. In real LLM batches, long prompt and generated-output lengths produce heavy-tailed task durations; use workload-calibrated upper-quantile estimates and re-estimate remaining work throughout execution.

3. Define slack, predicted finish time and scheduling priority

For a job \j\:

• \remaining_work_j\: estimated prompt/decode token work, corrected using measured service rates per model and GPU SKU.
• \estimated_duration_j(pool)\: remaining processing time given available ready GPUs, expected batching efficiency, checkpoint/restoration and failure risk.
• \slack_j = deadline_j - now - estimated_duration_j\.
• Negative slack means the job is not forecast feasible under the current placement. Do not claim it is impossible under all placements; test larger or faster eligible capacity.

A practical policy combines:

1. Hard constraints: authorized model/adapter, data-residency, GPU memory/model fit, deadline class, quality and dataset access.
2. Admit only with a plausible completion plan: include queue wait and checkpoint reserve.
3. Prioritize urgent feasible work: use earliest-deadline-first or least-slack-time-first *with fairness and starvation limits*. Neither policy automatically guarantees all deadlines on multiprocessor, non-preemptible, variable-length LLM workloads.
4. Pack work into manageable shards: group similar token lengths for efficiency but keep chunks small enough to recover within the deadline.
5. Escalate by slack: when predicted remaining completion time approaches deadline, move checkpointable tasks from Spot to reliable capacity if authorized GPU budget and availability allow.
6. Reject/defer transparently: if no compliant capacity can meet the deadline, mark the job at risk/failing and notify upstream workflows.

4. Build a durable work and checkpoint model

Recommended unit of recovery: a *completed input document or microbatch*, not the ephemeral decoder KV-cache state.

For each batch job persist:

• Immutable job ID, model-weight digest, tokenizer/chat-template version, prompt/template version, generation parameters, input dataset snapshot and output schema version.
• Partition/shard IDs and a manifest enumerating every required input record.
• Status per shard: pending, leased, succeeded, retryable failure, terminal failure; bounded lease expiry and attempt count.
• Durable output URI + checksum for each committed shard, plus quality/schema checks and audit metadata.
• Checkpoint manifest version and timestamp; store in persistent object storage or database outside the Spot node.

Exactly-once effects need an application protocol. Kubernetes Jobs and queues usually provide at-least-once execution in failure cases. Two workers can try the same shard. Prevent duplicate published outputs using an atomic conditional claim/commit, durable idempotency keys and a single authoritative manifest. Do not assume one Pod equals exactly one execution.

5. How to checkpoint safely

A reliable shard process:

1. Claim a shard using an expiring lease or transactional compare-and-swap (CAS) with a unique attempt ID.
2. Read the immutable input snapshot and verify approved model/configuration.
3. Generate outputs and validate schema, correctness constraints and safety requirements.
4. Write results to an attempt-scoped temporary object, with integrity checksum.
5. Atomically mark that shard succeeded in the authoritative manifest if this attempt still owns the lease; publish the committed output reference.
6. If the manifest commit fails, treat the attempt as uncommitted and safely discard or garbage-collect its temporary object.
7. On worker loss, reclaim expired leases and retry unfinished shards up to the job's deadline and retry budget.

Object stores do not universally support atomic cross-object transactions. Use the database/manifest CAS as the commit point, and design readers to ignore uncommitted objects. A temporary output existing in storage does not mean the corresponding shard has completed.

Caution: token-level decoder checkpoints require exact KV/cache and RNG/runtime compatibility, which most serving stacks do not promise across GPUs or engine versions. Replaying a shard from the prompt is often safer, though stochastic decoding can yield a different completion. Restore from stable committed work, not an imaginary portable KV snapshot.

6. Preemption notices and emergency checkpointing

For AWS EC2 Spot:

• A rebalance recommendation may arrive before a two-minute interruption notice, but is not guaranteed to arrive first.
• A normal Spot interruption notice typically provides approximately two minutes before interruption; it can be unavailable or late. Correctness must survive abrupt termination without notice.
• On notification, stop leasing new shards immediately; complete only those likely to finish within the remaining budget, commit finished outputs, and relinquish leases or allow expiry for unfinished work.
• Do not start a costly checkpoint operation that cannot finish or corrupt a durable manifest if interrupted mid-write.
• Keep completed outputs in a persistent store, not only on instance-local ephemeral storage.

AWS recommends small tasks and durable checkpoints, and explicitly suggests testing sudden terminations. Cloud providers have different notice semantics; never hardcode AWS behavior into a multi-cloud scheduler.

7. Checkpoint interval and wasted-work trade-off

Suppose a running worker takes 40 seconds to finish one document/shard and checkpoints only after each 10-shard microbatch:

• Checkpoint interval = \10 × 40 = 400 seconds\ plus commit overhead.
• If an interruption occurs uniformly within that interval, expected lost compute is about 200 seconds (half the interval), assuming no prior durable intermediate commit.
• If it checkpoints after every 2 shards, interval = \2 × 40 = 80 seconds\, and expected lost work falls to 40 seconds.
• More frequent commits incur more object-storage/database writes and CPU time; fewer commits increase expected recomputation after failure.

An approximate checkpoint optimization model with fixed checkpoint overhead \C\ seconds and mean time between interruptions \M\ seconds is \overhead fraction ≈ C/T + T/(2M)\ for checkpoint interval \T\, under simplifying independent-failure and constant-work assumptions. Minimizing gives \T* ≈ sqrt(2CM)\. This is only a heuristic: actual LLM output lengths, shard sizes, checkpoint cost and nonstationary Spot interruptions can violate its assumptions.

Practical choice: commit on stable item/microbatch boundaries, then use a load test and interruption simulation to choose an interval; do not blindly checkpoint every emitted token.

8. Kubernetes and Kueue orchestration

Kubernetes Indexed Jobs assign stable completion indexes to partitions and support \backoffLimitPerIndex\ (stable in current Kubernetes versions). With \restartPolicy: Never\, a failed shard index can retry without restarting all successful indexes. Still, the application must provide durable output/idempotency, because duplicate execution can occur.

Illustrative Job configuration: \\\`yaml apiVersion: batch/v1 kind: Job metadata: name: llm-batch-inference spec: completions: 100 parallelism: 8 completionMode: Indexed backoffLimitPerIndex: 2 template: spec: restartPolicy: Never nodeSelector: capacity-class: spot containers:

• name: worker

image: registry.example.com/llm-batch@sha256:REPLACE_WITH_REAL_DIGEST resources: limits: nvidia.com/gpu: 1 \\\`

Do not deploy this unchanged: replace the example image/digest with a real approved immutable image, verify labels/GPU resources, configure checkpoint storage and IAM, and decide whether a Spot-only placement is acceptable for the job deadline. A Pod index is a *partition identity*, not a durable completed-result guarantee.

Kueue provides quota/resource-flavor admission for Kubernetes batch jobs. Queueing priority, borrowing and topology-aware GPU scheduling can help allocate scarce resources, but Kueue does not automatically calculate LLM-specific deadlines, estimated remaining generated tokens or portable KV checkpoints. Implement those in a separate workload planner or integrate them with custom admission policies.

9. Recovery algorithm after an interruption

1. Receive preemption signal or detect missing worker heartbeat/expired shard lease.
2. Stop assigning new work to a departing worker and persist any fully completed shard outputs.
3. Reconcile in-progress attempts against authoritative manifest and object storage.
4. Return uncommitted shards to pending only after fencing old lease holders, to avoid late duplicate commits.
5. Recompute \remaining_work\, estimated GPU service rate and \slack\ for the deadline.
6. If enough Spot capacity and slack remain, retry on an eligible Spot pool with backoff and rate limits.
7. If slack is insufficient, escalate to pre-approved on-demand/reserved capacity, reduce optional work only if contract permits, or explicitly declare the deadline at risk.
8. Once every required index is committed and validated, atomically mark the job complete; only then notify consumers or downstream workflows.

Be careful with external side effects: if generated outputs trigger emails, purchases or database mutations, process them in a separate idempotent downstream step, not directly from retryable inference attempts.

10. Production incident: “99% finished” but misses deadline

Scenario: A document summarization batch of 50,000 inputs runs cheaply on Spot GPUs. A preemption near the deadline destroys several large uncheckpointed work partitions. Kubernetes restarts Pods, but earlier outputs are mixed with retries and duplicate writes; the batch misses its deadline despite the dashboard showing 99% of GPU work processed.

Root causes:

• Progress was counted from attempts rather than durably committed outputs.
• Long partitions made a single interruption erase many minutes of GPU work.
• The scheduler ignored shrinking deadline slack and continued waiting for cheap Spot GPUs.
• Output writes were not fenced by per-attempt ownership.

Fix: split into manageable durable shards, commit each through a manifest CAS, monitor committed/required output counts, and add deadline-aware promotion to reliable GPUs. Configure retry budgets and backoff, and simulate interruptions at the worst possible commit boundary.

Prevention: require deterministic or acceptance-validated outputs, end-to-end checksum verification, interrupted-worker experiments and a completion audit before exposing “Done” status.

11. Metrics and common mistakes

Monitor:

• Job deadline and slack distribution, predicted finishing time, queued work in input/output tokens, and ready GPU capacity per purchasing class.
• Committed shards / total required, active leases, oldest outstanding shard, per-shard attempts, terminal failures and late completions.
• Checkpoint/manifest write latency, average redo compute after interruption, failed CAS updates, duplicate-attempt suppression and output integrity.
• Spot preemption and unavailable-GPU rate, restart/warmup duration, reliable-capacity escalation cost and late-job frequency.
• Effective dollars per validated, on-time completed batch job, not only dollars per GPU-hour.

Avoid:

• Treating \activeDeadlineSeconds\ as an absolute business due timestamp.
• Claiming zero data loss from ephemeral KV-cache state.
• Publishing a result merely because temporary objects were written.
• Retrying non-idempotent tool actions on every duplicate worker attempt.
• Prioritizing solely by earliest deadline without token-work estimates and fairness.
• Assuming interrupt notice is always delivered or sufficiently long.
• Counting Kubernetes Job \Succeeded\ as proof all model outputs passed application validation.

12. Interview-ready answer

“I'd model each batch job's deadline, estimated remaining token work, ready GPU processing rate, recovery reserve and slack. I'd admit only feasible jobs, prioritize urgent work with fairness, run restartable shards on Spot when slack permits, and escalate to reliable capacity before a deadline becomes unreachable. Each shard would commit validated output through a durable, lease-fenced manifest so duplicate retries are safe. I'd test abrupt interruption, checkpoint-commit races and final output completeness, then optimize dollars per verified on-time job rather than spot-hour discounts.”

Research references:

• Kubernetes — Jobs, Indexed Completion, Retry and Deadlines
• Kubernetes — Pod Failure Policy
• Kueue — Workload Admission
• AWS — Prepare for Spot Interruptions
• AWS — EC2 Spot Best Practices