Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees

Tareq Si Salem, Gabriele Castellano, Giovanni Neglia, Fabio Pianese, Andrea Araldo

TL;DR

Modern ML applications demand both high accuracy and ultra-low latency, a combination that neither pure edge execution nor pure cloud offloading can reliably provide. This paper introduces the concept of Inference Delivery Networks (IDNs)—akin to Content Delivery Networks (CDNs) but for ML models—and proposes INFIDA, a distributed algorithm that dynamically places different versions of ML models across the edge-cloud continuum. INFIDA optimizes the latency-accuracy trade-off and comes with strong theoretical performance guarantees, even when user request patterns are highly unpredictable.

What Problem Does This Paper Address?

As machine learning becomes ubiquitous in latency-critical applications like autonomous driving, AR/VR, and industrial robotics, developers face a deployment dilemma.

  • Edge execution: Running models directly on end devices or local edge servers ensures low latency but forces the use of smaller, less accurate models due to hardware constraints.
  • Cloud execution: Offloading to massive data centers allows for highly accurate, complex models but introduces network latency that can violate strict real-time deadlines (e.g., <10 ms).

To bridge this gap, the authors propose an Inference Delivery Network (IDN). In an IDN, a hierarchy of compute nodes (from base stations to regional data centers to the cloud) coordinates to serve inference requests. The core problem is an incredibly complex routing and resource allocation challenge: Where should we place ML models, and which versions of those models (e.g., full-size vs. pruned/quantized) should we use, given the limited GPU/memory budgets at each node?

Methods

The authors frame ML model allocation as a submodular maximization problem under multiple knapsack constraints—a notoriously NP-hard problem.

To solve this dynamically, they introduce INFIDA (INFerence Intelligent Distributed Allocation). Unlike static optimization heuristics, INFIDA is an online, distributed algorithm designed to operate in an adversarial setting (meaning it assumes request patterns can change unpredictably and maliciously).

INFIDA works in two main steps at each node:

  1. State Computation (Online Mirror Ascent): Nodes use lightweight control messages from their neighbors to calculate the "marginal gain" of hosting a specific model. They update a fractional state—essentially the probability that a node should host a given model—using a gradient ascent method tailored for high-dimensional spaces.
  2. State Rounding (DepRound): Because a node cannot host a "fraction" of a model, INFIDA uses a randomized rounding technique to convert these probabilities into discrete placement decisions (0 or 1) while strictly respecting the node's hardware budget (e.g., GPU memory).

Datasets

Because IDNs are a novel architectural concept, the authors evaluate INFIDA using a custom simulation environment modeling a realistic 5-tier ISP network topology (ranging from base stations to a remote cloud).

  • Models: The catalog consists of 10 variants of the YOLOv4 object detection model (ranging from high-resolution 608p down to highly pruned and "tiny" versions). These were profiled for accuracy (mAP on MS COCO) and inference delay on two different GPUs (Titan RTX and GTX 980).
  • Workloads: They simulated 20 different object detection tasks with requests arriving at 7,500 requests per second. Request popularity was modeled using a Zipf distribution, tested under both a Fixed Popularity Profile and a Sliding Popularity Profile (where the most requested tasks shift over time).

Key Insights and Ideas

  • Inference is not just Caching: IDNs might sound exactly like CDNs, but they have crucial differences. In a CDN, a requested video is either cached or it isn't. In an IDN, a request can be served by multiple different models with varying degrees of accuracy. Furthermore, ML models have strict throughput limits (requests per second), whereas serving a static file is largely bound only by network bandwidth.
  • Adversarial Robustness is Key: By designing INFIDA to mathematically guarantee performance against an "adversary" choosing the worst-case request patterns, the algorithm is inherently robust to real-world flash crowds, shifting trends, and unpredictable workload spikes.
  • Virtual Learning, Physical Laziness: INFIDA continuously updates its "fractional" (virtual) allocation probabilities every time slot, but physical models are massive and expensive to move over the network. The authors show that using a dynamic refresh period—updating the physical models frequently at first, then slowing down—allows the network to converge quickly without choking the bandwidth with constant model migrations.

Key Results

  • Theoretical Guarantees: The authors mathematically prove that INFIDA achieves a sublinear $(1 - 1/e)$-regret bound. In plain English: over time, INFIDA's performance converges to a mathematically guaranteed fraction (~63%) of the absolute best offline strategy that perfectly knows the future.
  • Adaptability: INFIDA successfully adapts to a user-defined parameter ($\alpha$) that weights the importance of latency vs. accuracy. When latency is prioritized, it pushes tiny models to the edge; when accuracy is prioritized, it routes traffic to larger models deeper in the network.
  • Outperforming Heuristics: In simulations with shifting task popularity, static offline policies suffered a ~30% performance degradation. INFIDA maintained peak performance, outperforming an Online Load-Aware Greedy (OLAG) heuristic by roughly 10% in Normalized Time-Averaged Gain, while also scaling better under heavy request loads.

Limitations and Future Work

  • Communication Overhead: The algorithm relies on control messages passing up and down the network path to calculate gradients. The authors assume a reliable communication channel, though they note the algorithm is robust to unbiased noise.
  • Re-training Costs: The paper assumes models are pre-trained and static in their capabilities. It does not account for the computational or network costs of periodically re-training and re-deploying updated weights.
  • Model Splitting: The current framework treats models as atomic units. The authors note that "model splitting" (partitioning the layers of a single neural network across multiple discrete computing units) is an orthogonal technique that could be integrated into a future, enhanced IDN scheme.

Summary updated

Abstract

An increasing number of applications rely on complex inference tasks that are based on machine learning (ML). Currently, there are two options to run such tasks: either they are served directly by the end device (e.g., smartphones, IoT equipment, smart vehicles), or offloaded to a remote cloud. Both options may be unsatisfactory for many applications: local models may have inadequate accuracy, while the cloud may fail to meet delay constraints. In this paper, we present the novel idea of inference delivery networks (IDNs), networks of computing nodes that coordinate to satisfy ML inference requests achieving the best trade-off between latency and accuracy. IDNs bridge the dichotomy between device and cloud execution by integrating inference delivery at the various tiers of the infrastructure continuum (access, edge, regional data center, cloud). We propose a distributed dynamic policy for ML model allocation in an IDN by which each node dynamically updates its local set of inference models based on requests observed during the recent past plus limited information exchange with its neighboring nodes. Our policy offers strong performance guarantees in an adversarial setting and shows improvements over greedy heuristics with similar complexity in realistic scenarios.
BibTeX
@inproceedings{salem2021towards,
  author = {Tareq Si Salem and Gabriele Castellano and Giovanni Neglia and Fabio Pianese and Andrea Araldo},
  title = {{Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees}},
  booktitle = {MedComNet},
  year = {2021},
  url = {https://openreview.net/forum?id=I8s-u-cu3v},
}

Loading related content...

Figure