Queueing, Predictions, and LLMs — Mitzenmacher & Shahout
Explicit research-question bullets from the March 2025 author version (published in Stochastic Systems). Definitions and existing-result bullets are context, not new records. Systems-design directions are labeled programmes.
42 catalogue entries · 42 new problem records · 42 catalogue entries linked to problem records
Catalogue entries can be source pointers, solved items or groups of questions. They are not added to the main problem count. Status reflects the saved source, inspected 2026-09-10.
Original collection ↗Attribution and reuse
http://creativecommons.org/licenses/by/4.0/; attributed adaptation; HTML converted to Markdown with original mathematical notation and source links.
42 matching entries
Clear filtersRealistic prediction-error models for queues
Status unassessed2.1 Extensions of Standard Queueing Models
Numerical analysis tools for prediction-aware M/G/1 queues
Status unassessed2.1 Extensions of Standard Queueing Models
Queue analysis with selectively available predictions
Status unassessed2.1 Extensions of Standard Queueing Models
Implementable Gittins policies with predicted sizes
Status unassessed2.1 Extensions of Standard Queueing Models
Scheduling with distribution-valued job-size predictions
Status unassessed2.1 Extensions of Standard Queueing Models
Monitoring and disabling degraded job-size predictors
Status unassessed2.1 Extensions of Standard Queueing Models
Error models for one-bit job-size predictions
Status unassessed2.2 1-Bit Predictions
Training predictors for a chosen scheduling policy
Status unassessed2.2 1-Bit Predictions
Response-time tradeoffs with multi-bit predictions
Status unassessed2.2 1-Bit Predictions
Sharper graceful-degradation constants in queue scheduling
Status unassessed2.3 Uniform Bounds
Scheduling guarantees beyond rank-based policies
Status unassessed2.3 Uniform Bounds
Prediction-aware queue performance beyond mean response time
Status unassessed2.3 Uniform Bounds
Models for the cost of acquiring job-size predictions
Status unassessed2.4 Accounting for Prediction Costs
Load-dependent decisions to obtain predictions
Status unassessed2.4 Accounting for Prediction Costs
Selective prediction with FIFO for unpredicted jobs
Status unassessed2.4 Accounting for Prediction Costs
Effective dedicated prediction servers
Status unassessed2.4 Accounting for Prediction Costs
Economic incentives for job-size prediction
Status unassessed2.4 Accounting for Prediction Costs
Multi-server queueing theory with predictions
Status unassessed2.5 Multiple Server Systems
Fluid limits for power-of-two routing with richer predictions
Status unassessed2.5 Multiple Server Systems
Scheduling jobs with predicted speedups across server counts
Status unassessed2.5 Multiple Server Systems
Ranking LLM requests across prefill and decode
Status unassessed4.1 Dynamic Batching and Preemption in LLM Inference
Adaptive thresholds for costly LLM preemption
Status unassessed4.1 Dynamic Batching and Preemption in LLM Inference
Limited-preemption SPRPT and response-time tails
Status unassessed4.1 Dynamic Batching and Preemption in LLM Inference
Cost and latency targets in adaptive LLM scheduling
Status unassessed4.2 Adaptive Scheduling
Joint scheduling of interactive and background requests
Status unassessed4.2 Adaptive Scheduling
Prompt sharing without delaying small standalone requests
Status unassessed4.2 Adaptive Scheduling
Combining pooled and dedicated GPU allocation
Status unassessed4.3 GPU Resource Allocation
Heterogeneous GPUs across prefill and decode
Status unassessed4.3 GPU Resource Allocation
Tandem queue analysis of split-phase LLM serving
Status unassessed4.3 GPU Resource Allocation
When many smaller GPUs outperform one larger GPU
Status unassessed4.3 GPU Resource Allocation
Adapting allocation to the bottleneck LLM phase
Status unassessed4.3 GPU Resource Allocation
Scheduling guarantees for API-augmented LLM requests
Status unassessed5.1 Augmented LLMs
Load balancing API-augmented inference with quality tradeoffs
Status unassessed5.1 Augmented LLMs
Tandem queue models of speculative decoding
Status unassessed5.2 Multiple LLMs Available
Routing requests among LLMs under cost and latency limits
Status unassessed5.2 Multiple LLMs Available
Reconciling predictions with live inference feedback
Status unassessed5.2 Multiple LLMs Available
Queueing tradeoffs between LLM accuracy and time
Status unassessed5.2 Multiple LLMs Available
Scheduling parallel and dependent multi-LLM tasks
Status unassessed5.3 Multiple LLMs Needed
Queueing and job-shop models for multi-stage LLM inference
Status unassessed5.3 Multiple LLMs Needed
Scheduling expansion and aggregation in LLM reasoning
Status unassessed6 Scheduling in LLM Reasoning Systems
Sharing KV caches across reasoning paths
Status unassessed6 Scheduling in LLM Reasoning Systems
Scheduling with predicted reasoning depth
Status unassessed6 Scheduling in LLM Reasoning Systems