# Queues with Small Advice

arXiv: https://arxiv.org/abs/2006.15463 · HTML: https://mlsanity.com/paper/2006.15463/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2020.

## Built on by (most cited first, 9 of 9)

- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Fast Inference for Augmented Large Language Models](https://mlsanity.com/paper/2410.18248/) (2024)
- [Single-Leg Revenue Management with Advice](https://mlsanity.com/paper/2202.10939/) (2022)
- [Queueing, Predictions, and LLMs: Challenges and Open Problems](https://mlsanity.com/paper/2503.07545/) (2025)
- [SkipPredict: When to Invest in Predictions for Scheduling](https://mlsanity.com/paper/2402.03564/) (2024)
- [Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams](https://mlsanity.com/paper/2406.16270/) (2024)
- [Online TSP with Predictions](https://mlsanity.com/paper/2206.15364/) (2022)
- [Credence: Augmenting Datacenter Switch Buffer Sharing with ML Predictions](https://mlsanity.com/paper/2401.02801/) (2024)
- [Intra-request branch orchestration for efficient LLM reasoning](https://mlsanity.com/paper/2509.24957/) (2025)

## Abstract (arXiv)

Motivated by recent work on scheduling with predicted job sizes, we consider the performance of scheduling algorithms with minimal advice, namely a single bit. Besides demonstrating the power of very limited advice, such schemes are quite natural. In the prediction setting, one bit of advice can be used to model a simple prediction as to whether a job is "large" or "small"; that is, whether a job is above or below a given threshold. Further, one-bit advice schemes can correspond to mechanisms that tell whether to put a job at the front or the back for the queue, a limitation which may be useful in many implementation settings. Finally, queues with a single bit of advice have a simple enough state that they can be analyzed in the limiting mean-field analysis framework for the power of two choices. Our work follows in the path of recent work by showing that even small amounts of even possibly inaccurate information can greatly improve scheduling performance.