# Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 29 Apr 2026.

## Builds on (most cited first, 13 of 13)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Learning-Augmented Weighted Paging](https://mlsanity.com/paper/2011.09076/) (2020)
- [Online Bin Packing with Predictions](https://mlsanity.com/paper/2102.03311/) (2021)
- [Learning-Augmented Algorithms for Online TSP on the Line](https://mlsanity.com/paper/2206.00655/) (2022)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Scheduling with Speed Predictions](https://mlsanity.com/paper/2205.01247/) (2022)
- [Learning-Augmented Online Packet Scheduling with Deadlines](https://mlsanity.com/paper/2305.07164/) (2023)
- [Online Time-Windows TSP with Predictions](https://mlsanity.com/paper/2304.01958/) (2023)
- [Online TSP with Predictions](https://mlsanity.com/paper/2206.15364/) (2022)
- [Online Bin Covering with Frequency Predictions](https://mlsanity.com/paper/2401.14881/) (2024)

## Abstract (arXiv)

We present a learning-augmented online algorithm for the preemptive FIFO buffer management problem, where packets arrive online to a finite-capacity buffer, must be transmitted in FIFO order, and the algorithm may preemptively discard buffered packets to accommodate future arrivals. Our algorithm simultaneously achieves 1-consistency, η-smoothness, and asymptotic √3-robustness, where η denotes the prediction error. Specifically, it attains an optimal competitive ratio of 1 under perfect predictions, degrades smoothly as the prediction error increases, and maintains an asymptotic competitive ratio of √3 under arbitrarily inaccurate predictions, matching the best-known worst-case guarantee for the classical online problem, established by Englert and Westermann in 2009 [Algorithmica 53(4): 523-548]. A key technical contribution of our work is the introduction of an output-based prediction error metric. Because capacity constraints dictate that only a strictly bounded subset of arriving packets is ultimately transmitted, our metric assesses prediction quality over the resulting optimal schedules rather than the raw input sequences, avoiding artificial error penalties. To guarantee robustness, our algorithm dynamically monitors predictions and executes a buffer-clearing strategy upon transitioning to a worst-case fallback mechanism. We prove that the competitive loss incurred by this clearing operation is bounded by an additive capacity constant that vanishes asymptotically. Finally, we show that our algorithm provides a generalized framework for learning-augmented buffer management: substituting the fallback module with any β-competitive online algorithm immediately yields asymptotic β-robustness.