PaperlayerView exact revision on arXiv

Source-linked AI summary

Parity Models: A General Framework for Coding-Based Resilience in ML Inference

Jack Kosaian, K. V. Rashmi, Shivaram Venkataraman

arXiv:1905.00863v2cs.DCcs.ITcs.LGmath.IT

TL;DR

Prediction serving systems must meet strict latency targets, but slowdowns and failures inflate tail latency and existing mitigations may be too slow, costly, or inapplicable to inference. ParM encodes queries into parity queries and uses learned parity models to reconstruct unavailable predictions. Across inference tasks, it improves accuracy under unavailability while using 2-4× less additional resources than replication-based approaches.

  • Problem

    Distributed prediction serving must minimize tail latency to meet strict service-level objectives, but slowdowns and failures inflate latency and current mitigations can be too slow or resource-intensive.

    Source: §1 · p. 1

  • Method

    ParM encodes multiple queries into a parity query, runs a learned neural-network parity model on it, and uses simple encoders and decoders to reconstruct unavailable predictions.

    Source: §1 · p. 2

  • Results

    Across inference tasks, ParM improves accuracy under unavailability while using 2-4× less additional resources than replication-based approaches.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Parity models provide a coding-based approach to resource-efficient resilience for varied inference tasks, including image classification, speech recognition, and object localization.

    Source: §1 · p. 3, §7 · p. 14

    ParM does not focus on applying its framework to neural architecture search.

    Source: §3.3 · p. 7

Abstract

from arXiv · show

Machine learning models are becoming the primary workhorses for many applications. Production services deploy models through prediction serving systems that take in queries and return predictions by performing inference on machine learning models. In order to scale to high query rates, prediction serving systems are run on many machines in cluster settings, and thus are prone to slowdowns and failures that inflate tail latency and cause violations of strict latency targets. Current approaches to reducing tail latency are inadequate for the latency targets of prediction serving, incur high resource overhead, or are inapplicable to the computations performed during inference. We present ParM, a novel, general framework for making use of ideas from erasure coding and machine learning to achieve low-latency, resource-efficient resilience to slowdowns and failures in prediction serving systems. ParM encodes multiple queries together into a single parity query and performs inference on the parity query using a parity model. A decoder uses the output of a parity model to reconstruct approximations of unavailable predictions. ParM uses neural networks to learn parity models that enable simple, fast encoders and decoders to reconstruct unavailable predictions for a variety of inference tasks such as image classification, speech recognition, and object localization. We build ParM atop an open-source prediction serving system and through extensive evaluation show that ParM improves overall accuracy in the face of unavailability with low latency while using 2-4$\times$ less additional resources than replication-based approaches. ParM reduces the gap between 99.9th percentile and median latency by up to $3.5\times$ compared to approaches that use an equal amount of resources, while maintaining the same median.

1 Introduction

Prediction serving systems face tail-latency inflation that threatens strict latency targets, while existing mitigations can be too slow, resource-intensive, or unsuitable for neural-network inference. ParM uses learned parity models to make coded resilience practical with simple, fast encoders and decoders.

1 Introduction

  • Distributed prediction serving faces tail-latency inflation from contention, hardware failures, and runtime interactions, while late predictions can be useless under strict service-level objectives.Existing cause-agnostic mitigations may be too slow for prediction serving or require substantial resources through query replication.Source: §1 · p. 1
  • Erasure codes recover unavailable data with less resource overhead than replication, motivating their adaptation to mitigate slowdowns in prediction serving.In coded computation, the decoder reconstructs computation outputs rather than the original input data.Source: §1 · pp. 1–2
  • Most prior coded-computation methods support only restricted computations, such as linear functions and low-degree polynomials, rather than neural networks’ complex nonlinear inference.Coded-computation encodes inputs into parity units, runs the computation on data and parity units, and decodes outputs from the fastest computations.Source: §1 · p. 2
  • Kosaian et al. [53] introduced approximate reconstruction and learned encoders and decoders for neural-network inference, extending coded computation to nonlinear functions.Their learned encoders and decoders can be up to 7× slower than deployed models, limiting their usefulness to the far end of tail latency.Source: §1 · p. 2
  • ParM encodes queries into parity queries and uses neural-network parity models whose outputs let simple encoders and decoders reconstruct unavailable predictions.The encoders and decoders can use operations such as addition and subtraction.Source: §1 · p. 2
  • ParM uses 2-4× less additional resources than replication-based approaches while improving accuracy under unavailability across inference tasks.With half replication’s additional resources, ResNet-18 reconstructions are up to 89% more accurate than default predictions and at most 6.5% less accurate than available predictions.Source: §1 · p. 3

2 Background and Motivation

Prediction serving distributes inference across model instances to meet low-latency, high-throughput demands, but cluster slowdowns threaten latency targets. Coded computation offers a potential remedy, yet nonlinear models and the latency of learned encoders and decoders pose challenges.

2.1 Prediction serving systems

  • Prediction serving systems dispatch client queries to model instances containing deployed models; scale-out supports low latency and throughput, while batching can add latency.Systems may use minimal or no batching, especially on hardware not tailored for batched operation.Source: §2.1 · p. 3

2.2 Challenges and opportunity

  • Prediction serving needs cause-agnostic slowdown mitigation; replication is resource-intensive, while erasure coding offers low-latency recovery with less overhead.Speculative and predictive techniques can add detection or scheduling delays that are problematic for prediction-serving timescales.Source: §2.2 · pp. 3–4

2.3 Coded-computation and its challenges

  • Coded computation encodes inputs into parity units and uses available data- and parity-computation outputs to reconstruct unavailable outputs, but nonlinear functions complicate decoding.For linear functions, parity outputs can support simple recovery; for nonlinear functions, the parity output need not equal the sum of individual outputs.Source: §2.3 · p. 4, Table 1 · p. 4

2.4 Benefits and challenges of learning a code

  • 82% accuracy for reconstructed unavailable ResNet-18 CIFAR-10 predictions, versus 93% for the deployed model, illustrates learned codes’ potential when predictions are approximate [53].The accuracy decrease occurs only when the deployed model is unavailable.Source: §2.4 · p. 5
  • 7× higher average encoding and decoding latency than the deployed model limited learned convolutional encoders and decoders to reducing the far end of tail latency [53].The authors describe this as an average latency up to 7× higher; hardware acceleration could reduce it but would require a more powerful, expensive frontend.Source: §2.4 · p. 5

3 Parity Models Framework

ParM replaces the extra deployed-model copy used in coded computation with a learned neural-network parity model, while keeping encoding and decoding simple and fast. It groups queries into parity queries and uses parity-model outputs to reconstruct unavailable predictions.

3 Parity Models Framework

  • ParM learns neural-network parity models that let simple, fast encoders and decoders reconstruct slow or failed predictions, including for modern machine-learning models.This avoids requiring expensive hardware acceleration for encoding and decoding.Source: §3 · p. 5

3.1 System architecture

  • The frontend groups consecutively dispatched batches into coding groups of k, encodes corresponding queries, and sends the resulting parity batch to a parity model.Parity models use the same amount of resources as deployed models; encoding does not delay query dispatch, and decoding is used only when a prediction batch is unavailable.Source: §3.1 · p. 6

3.2 Encoder and decoder design space

  • With the simple addition/subtraction code, ParM sums queries to form a parity and subtracts the k − 1 available predictions from the parity-model output to reconstruct an unavailable prediction.This simple encoder and decoder are used to demonstrate applicability across image classification, speech recognition, and object localization.Source: §3.2 · p. 6

3.3 Parity model design

  • Parity models are neural networks trained on encoded queries to produce the transformations expected by the decoder; they can use representative deployment queries and available training data or inference queries when that data is unavailable.Matching the deployed model's neural-network architecture can give the parity model the same average runtime, though different architectures are also possible.Source: §3.3 · pp. 6–7

3.4 Example

  • For k = 3, the parity model's output combined with the two available predictions reconstructs an approximation of the prediction from the slowed model instance.The example uses classification outputs represented as vectors of n floating-point values.Source: §3.4 · p. 7, Figure 5 · p. 7

3.5 Handling concurrent unavailabilities

  • ParM can handle concurrent unavailabilities by training r separate parity models to produce different transformations and decoding from any k of the k + r outputs.For k = 2 and r = 2, the example parity outputs are ℱ(X1) + ℱ(X2) and ℱ(X1) + 2ℱ(X2).Source: §3.5 · p. 7

4 Evaluation of Accuracy

ParM’s accuracy evaluation tests reconstruction across classification, speech recognition, and localization, with generic and task-specific encoders. It finds strong degraded-mode accuracy, while higher redundancy and larger k trade reconstruction accuracy for resource efficiency.

4.2 Results

  • 41–89% better degraded-mode accuracy than default predictions; ParM’s CIFAR-10 overall accuracy stays within 0.4%, 1.9%, and 4.1% of available predictions for k = 2, 3, and 4 when fewer than 10% are unavailable.Returning defaults lowers overall accuracy by over 8.3% in that setting.Source: Figure 6 · p. 8, §4.2 · pp. 8–9

4.1 Experimentation setup

  • The evaluation covers image classification, speech recognition, and object localization, using multiple model architectures and test data not used in training.The default setup uses addition encoding and subtraction decoding; mean-squared error is selected to support varied inference tasks.Source: §4.1 · pp. 7–8

4.2.1 Inference tasks

  • With k = 2, ParM’s degraded-mode accuracy is at most 6.5% below available predictions and up to 89% above defaults across the evaluated image-classification and speech-recognition tasks.Fashion-MNIST reconstructions are 70–81% more accurate than defaults across MLP, LeNet-5, and ResNet-18.Source: §4.2.1 · p. 9
  • For object localization, k = 2 reconstructions achieve average IoU 0.674, compared with 0.945 for the deployed model on the full Caltech-UCSD Birds dataset.A sample reconstruction has IoU 0.611 versus 0.880 for the deployed model.Source: §4.2.1 · p. 9

4.2.2 Varying redundancy via parameter k

  • As k rises from 2 to 4, degraded-mode accuracy declines because more queries make each parity query noisier, but it remains significantly above defaults.At expected unavailability levels, overall accuracy remains similar to the deployed model even at higher k.Source: §4.2.2 · p. 9

4.2.3 Inference task-specific encoders and decoders

  • Task-specific image encoders improve degraded-mode accuracy over generic addition and subtraction, reaching 89% and 74% on CIFAR-10 at k = 2 and 4, respectively.On ImageNet with k = 2 and ResNet-50, the approach achieves 61% top-5 degraded-mode accuracy.Source: §4.2.3 · p. 10

5 Evaluation of Tail Latency Reduction

ParM reduces tail latency across evaluated settings while maintaining median latency. Its benefits extend across batch sizes and hardware, and its simple encoders and decoders add little latency.

5 Evaluation of Tail Latency Reduction

  • In load imbalance, ParM reduces 99.9th-percentile latency by up to 48%, bringing it up to 3.5× closer to median latency while maintaining the same median.The evaluation also reports benefits across inference hardware and query rates.Source: §5 · p. 10
  • Under load imbalance, ParM reduces 99.9th-percentile latency by up to 48%, bringing tail latency up to 3.5× closer to median latency while maintaining the same median.With very little load imbalance, it reduces the gap between tail latency and median latency by up to 2.3×.Source: §5 · p. 10
  • ParM’s encoder and decoder latencies are below 200 µs and 20 µs, respectively, and its simpler development and deployment compare favorably with approximate-model approaches.Source: §5 · p. 10

5.1 Implementation and Evaluation Setup

The latency evaluation implements ParM in Clipper and compares it with an equal-resource replication baseline. Experiments use two cluster types and vary query rate and background load.

5.1 Implementation and Evaluation Setup

  • ParM’s encoder and decoder run in the Clipper frontend, while deployed and parity models run in PyTorch containers; latency tests use addition encoding and subtraction decoding.Prediction caching is disabled for end-to-end evaluation, though ParM does not preclude its use.Source: §5.1 · p. 10
  • Equal-Resources uses the same number of extra instances as ParM, placing extra deployed-model copies where ParM places parity models.Source: §5.1 · p. 10
  • Experiments use GPU and CPU clusters, ResNet-18 Cat-vs-Dog queries, and varied Poisson rates; background load primarily shuffles network traffic between model instances.The latency metric excludes client-to-frontend communication and reports the median of three runs.Source: §5.1 · pp. 10–11

5.2 Results

Across tested query rates and load conditions, ParM reduces tail latency against Equal-Resources, with tradeoffs as redundancy increases. Its encoding and decoding overhead is small, and it avoids several drawbacks of approximate backup models.

5.2.1 Varying query rate

  • Compared with Equal-Resources, ParM reduces the 99.9th-percentile–median latency gap by 2.6–3.2× on GPU and 3–3.5× on CPU, while adding less than 0.5 ms to median latency.Source: §5.2.1 · p. 11

5.2.4 Varying degrees and types of load imbalance

  • With 2 or 3 background shuffles, ParM lowers 99.9th-percentile latency by 35% and 39%; with 5 shuffles, its latency gap falls by 3.5× versus Equal-Resources.Under light background inference load without network imbalance, the gap falls by up to 2.3×.Source: Figure 13 · p. 12, §5.2.4 · p. 12, Figure 14 · p. 12

5.2.2 Varying redundancy via parameter k

  • At k = 3 and 4, ParM reduces the 99.9th-percentile-to-median latency gap by up to 2.5× versus Equal-Resources with 33% redundancy.Higher k increases tail latency because more unavailable predictions can exceed reconstruction tolerance and encoding waits for more queries.Source: §5.2.2 · p. 12

5.2.3 Varying batch size

  • At batch sizes 2 and 4, ParM reduces 99.9th-percentile latency by 43% and 47%, respectively, versus Equal-Resources.The gap between 99.9th-percentile and median latency falls by up to 4×.Source: §5.2.3 · p. 12

5.2.6 Comparison to approximate backup models

  • Approximate backup models show tail-latency variations over 36% as query rates rise, while ParM’s 99.9th-percentile latency varies modestly.Approximate models must be k times faster for stability; their speedup varies by hardware, and query replication uses 2× network bandwidth. ParM’s parity models can match deployed-model runtime, receive 1/k of its query rate, and add minor bandwidth overhead.Source: Figure 15 · p. 12, §5.2.6 · p. 13

5.2.5 Latency of ParM’s components

  • For k = 2, 3, and 4, median encoding latencies are 93, 153, and 193 µs, while decoding latencies are 8, 14, and 19 µs.These components are a small fraction of reconstruction latency, which is dominated by parity-model inference.Source: §5.2.5 · p. 12

6 Related Work

Related work addresses inference slowdowns through cause-specific mitigations, coding-based resilience, and latency or accuracy tradeoffs. ParM is positioned as a general alternative that applies across inference tasks and complements performance-optimization techniques.

Mitigating slowdowns

  • Cause-specific slowdown mitigations apply only to certain slowdown types and can be difficult to combine, whereas ParM is agnostic to the cause.Examples include configuration selection, tenant isolation, replica selection, queueing disciplines, and autoscaling.Source: §6 · p. 13
  • Training slowdown techniques exploit iterative computations specific to training and therefore do not apply to inference slowdowns.Source: §6 · p. 13

Coded-computation

  • ParM uses 2-4× less resource overhead than replication and avoids splitting neural-network operations across servers or adding latency when there is no unavailability.The passage contrasts ParM with a polynomial-code approach that uses at least as many resources as replication and a linear-operation approach requiring many decoding steps.Source: §6 · p. 13
  • ParM is a general framework for coding-based resilient inference across image classification, speech recognition, and object localization, unlike the image-classification-specific approach in Narra et al. [64].The approaches use similar concatenation-based encoding, while the passage reports that Narra et al.'s concatenated images can increase network bandwidth by up to 2× for CIFAR-10 when images are not resized.Source: §6 · p. 13

High performance inference methods

  • Inference methods that reduce average latency or improve throughput are complementary to ParM, which targets latency spikes across inference, network transfer, and system faults.Source: §6 · p. 13

Accuracy-latency tradeoff

  • ParM does not proactively degrade prediction accuracy; its inaccuracy occurs only when a prediction experiences slowdown or failure.Other systems and machine-learning techniques actively trade accuracy for latency to handle query-rate variation.Source: §6 · p. 13

7 Conclusion

ParM introduces parity models for coding-based resilience to slowdowns and failures in prediction serving. Evaluation across varied inference tasks reports reduced tail-latency spread versus equal-resource approaches, with the same median latency.

7 Conclusion

  • Up to 3.5× lower gap between 99.9th-percentile and median latency than equal-resource approaches, while maintaining the same median.Source: §7 · p. 14
  • ParM uses parity models with simple, fast encoders and decoders to reconstruct unavailable predictions across image classification, speech recognition, and object localization.Source: §7 · p. 14
  • Evaluation presents ParM as a resource-efficient approach for adding resilience to prediction serving systems.Source: §7 · p. 14

Related papers

Loading 1905.00863v2…