Predicting, Fast and Slow: SSD Already Knows Which Guess Is Wrong

Philipp BogdanarXiv 2026 · arXiv

TL;DR

Learned storage controllers like Heimdall often fail to predict SSD latency accurately because their errors are systematic biases rather than random uncertainty. While complex "uncertainty estimators" fail to catch these mistakes, a simple, untrained 16 KiB lookup table—inspired by hardware branch predictors—outperforms them all, identifying wrong guesses with significantly higher accuracy at a fraction of the computational cost.

What Problem Does This Paper Address?

Modern storage systems use "learned controllers" (like Heimdall) to predict whether an incoming read request will be "fast" or "slow." If a read is predicted to be slow, the system can "hedge" by sending the request to a redundant drive to minimize tail latency.

However, these neural networks aren't perfect. When they make a mistake, researchers have previously suggested using uncertainty estimators—algorithms that flag when the model is "unsure"—to decide when to distrust the prediction. This paper investigates a critical gap: do these uncertainty estimators actually work in the high-speed environment of an SSD? The authors find that for the busiest traces, these estimators are essentially no better than flipping a coin.

Methods

The author compares three distinct approaches to identifying when a latency prediction is wrong:

  1. Heimdall’s Baseline: A small neural network trained on I/O traces.
  2. Nine Uncertainty Estimators: A suite of standard and state-of-the-art methods, including distance-based metrics (Euclidean, Mahalanobis), Bayesian networks, ensembles, and "Trust Scores."
  3. The Table (The Novel Approach): A simple 4,096-entry lookup table that tracks the recent history of the drive. It uses four features known at the time of submission:
  4. Request size.
  5. Bytes currently outstanding on the drive.
  6. Age of the oldest outstanding request.
  7. Whether the drive has just been quiet.

The table requires no offline training. It updates its entries using a simple moving average ($1/64$ step) every time a read completes, effectively "learning" the drive's current congestion state in real-time.

Datasets

The study evaluated these methods using 57 held-out traces from two major collections:

  • UMass Trace Repository: Specifically the Financial and Web-Search traces.
  • MSR Cambridge: Media-server and enterprise volumes.
  • Hardware: Evaluation was performed on physical hardware, including WD_BLACK SN770 and enterprise-grade NVMe drives.

Key Insights and Ideas

  • Bias, Not Uncertainty: The primary reason learned controllers fail is bias. Heimdall tends to over-predict "slow" reads (calling 52% slow when only 30% actually are). Because the errors are systematic, estimators looking for "unfamiliar" data (uncertainty) completely miss them.
  • The Drive Already Knows: The physical state of the drive (queue depth and request size) is a much stronger signal for latency than the complex temporal features used by neural networks.
  • Hardware Wisdom: The success of the lookup table mirrors the efficiency of branch predictors in CPUs. It proves that for microsecond-scale decisions, a small, fast, and adaptive heuristic can outperform a heavy-weight machine learning model.
  • The Tail is Stubborn: Surprisingly, the paper finds that even an "Oracle" (which knows exactly which guesses are wrong) doesn't improve p99.9 tail latency significantly more than simpler methods. This suggests that the "tail" might be indifferent to who picks the reads for hedging.

Key Results

  • Accuracy: The lookup table achieved a median AUROC of 0.68 in ranking wrong guesses, whereas all nine uncertainty estimators hovered between 0.46 and 0.52 (random chance is 0.50).
  • Speed: The table makes a decision in just 21 nanoseconds. In contrast, Heimdall’s neural network inference takes 1.7 microseconds—nearly 80 times slower.
  • Predictive Power: The table actually predicts slow reads better than the neural network it was designed to "check," beating Heimdall’s own output on 47 out of 57 traces.

Limitations and Future Work

  • Modest Gains: While the table beats the estimators, a median AUROC of 0.68 is still "modest." Only 16 of the 57 traces reached an AUROC above 0.80.
  • Tail Latency Diminishing Returns: The paper notes that better prediction of "wrong guesses" doesn't translate into massive cuts in tail latency. The authors suggest that the "tail at scale" might be less sensitive to prediction accuracy than previously thought.
  • Reproducibility Gap: The authors were unable to reproduce the 50%+ tail latency cuts reported in previous work (Gohil et al.), seeing only 3% to 24% cuts on their hardware. This highlights the extreme sensitivity of these systems to specific drive models and trace characteristics.

The paper concludes with a poignant piece of advice for system designers: "Ask the device first." Before adding complex ML layers, check if a simple table of the device's own recent history already has the answer.

Summary updated

Abstract

Heimdall, a learned controller, calls slow on 52% of an SSD's reads when 30% are slow. Uncertainty estimators, the remedy prescribed for its wrong guesses, cannot find them: nine of them do no better than a coin. The drive can. On one trace, 2% of the reads of 4 to 8 KiB that found less than 4 KiB outstanding while the drive was answering came back slow, and Heimdall called 96% of them slow. A 4,096-entry table of how the drive's recent reads came back, untrained and 21 ns a decision, ranks the wrong guesses at a median AUROC of 0.68 on 57 held-out traces, where the nine sit at 0.46 to 0.52, and it predicts slow reads better than Heimdall itself.
BibTeX
@misc{bogdan2026predicting,
  author = {Philipp Bogdan},
  title = {{Predicting, Fast and Slow: SSD Already Knows Which Guess Is Wrong}},
  year = {2026},
  eprint = {2611.19457},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19457},
}
Figure