Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees

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

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.

Introduction

Modern machine learning (ML) applications, such as autonomous driving, augmented reality (AR), and industrial robotics, demand a challenging combination of high inference accuracy and ultra-low latency. Currently, developers face a deployment dilemma. Running models directly on end devices (edge execution) ensures low latency but necessitates smaller, less accurate models due to hardware constraints. Conversely, offloading to massive cloud data centers allows for state-of-the-art accuracy but introduces network delays that often exceed strict real-time deadlines (e.g., <10 ms).

To resolve this, we introduce the concept of Inference Delivery Networks (IDNs). Similar to how Content Delivery Networks (CDNs) revolutionized web content distribution, IDNs aim to distribute ML inference capabilities across the entire infrastructure continuum—from base stations and edge servers to regional data centers and the remote cloud.

The Inference Delivery Network Architecture

An IDN consists of a hierarchy of compute nodes that coordinate to serve inference requests. Unlike traditional CDNs, where a requested file is either present or absent, an IDN must manage multiple versions of the same ML model (e.g., full-size, pruned, or quantized) across different nodes. Each node has a limited resource budget (GPU memory, compute cycles), making the placement of these models a complex optimization problem.

Architecture of an Inference Delivery Network (IDN) across the cloud-to-device continuum.

The core challenge in an IDN is determining where to place specific ML models and which versions to use to maximize overall system utility, defined by a balance between inference accuracy and delivery latency. Unlike static caching, ML models have strict throughput limits, requiring the network to manage load as well as placement.

The INFIDA Algorithm

We frame the model allocation problem as a submodular maximization problem under multiple knapsack constraints. Because this is NP-hard and request patterns in real-world networks are often unpredictable, we propose INFIDA (INFerence Intelligent Distributed Allocation). INFIDA is an online, distributed algorithm designed to provide strong performance guarantees even in adversarial settings where request patterns change unpredictably.

INFIDA operates at each node through a two-step process:

  1. State Computation (Online Mirror Ascent): Nodes use lightweight control messages from neighbors to calculate the "marginal gain" of hosting a specific model. They update a fractional state—representing the probability of hosting a model—using a gradient ascent method optimized for high-dimensional spaces.
  2. State Rounding (DepRound): Since nodes cannot host fractional models, INFIDA employs a randomized rounding technique to convert these probabilities into discrete (0 or 1) placement decisions while strictly adhering to hardware budgets.
Trade-off between model quality and serving cost in the IDN optimization framework.

By utilizing a dynamic refresh period, INFIDA allows the network to converge quickly to an optimal state without overwhelming network bandwidth with constant model migrations.

Experimental Evaluation and Results

We evaluated INFIDA using a custom simulation environment modeling a realistic 5-tier ISP network topology. The model catalog included 10 variants of the YOLOv4 object detection model, ranging from high-resolution versions to highly pruned "tiny" versions, profiled for accuracy and inference delay on Titan RTX and GTX 980 GPUs.

The simulation handled 7,500 requests per second across 20 different tasks. We tested INFIDA under both fixed and sliding popularity profiles, where the most requested tasks shifted over time to simulate real-world trend changes.

Key Findings

  • Theoretical Optimality: We mathematically prove that INFIDA achieves a sublinear $(1 - 1/e)$-regret bound. This ensures that over time, the algorithm's performance converges to at least ~63% of the best possible offline strategy that has perfect future knowledge.
  • Dynamic Adaptability: INFIDA successfully adjusts to a user-defined parameter ($α$) that weights latency against accuracy. It pushes smaller models to the edge when latency is critical and routes traffic to larger models deeper in the network when accuracy is the priority.
  • Superior Performance: In scenarios with shifting task popularity, INFIDA outperformed standard Online Load-Aware Greedy (OLAG) heuristics by approximately 10% in normalized time-averaged gain and maintained peak performance where static policies saw a 30% degradation.

Discussion and Future Work

While INFIDA provides a robust framework for inference delivery, several avenues for future research remain. The current implementation assumes reliable communication for control messages and treats models as atomic units. Future enhancements could integrate "model splitting," where individual neural network layers are partitioned across multiple nodes. Additionally, accounting for the computational costs of periodic model re-training and the network overhead of deploying updated weights would further refine the IDN model for production environments.

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},
}
Figure