Source-linked AI summary
Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computing
Parsa Moradi, Mohammad Ali Maddah-Ali
TL;DR
Coded-computing methods often ignore intrinsic data geometry, although machine-learning computations seek to exploit it. This paper introduces manifold-aware GCC encoding based on graph-derived sample ordering and reports consistently lower recovery error under straggling than standard GCC across neural-network inference and polynomial evaluation.
Problem
Existing coded-computing approaches generally overlook intrinsic data structure, even though computational tasks such as machine learning exploit that structure.
Method
The method builds a distance-weighted sample graph, uses a short Hamiltonian path to order samples, and assigns them to GCC encoder design points.
Results
The manifold-aware method consistently achieves lower MSE than standard GCC in LeNet5 inference and high-dimensional polynomial evaluation under straggling.
Takeaways & Limitations
Manifold-aware ordering keeps coded inputs closer to the data manifold while preserving the standard GCC pipeline.
Abstract
from arXiv · showhide
Existing coded-computing designs do not explicitly exploit the intrinsic structure of the input data. In communication systems, statistical structure and redundancy are often removed through source coding (or compression) before channel coding is applied. This principle, however, does not transfer directly to coded computation. In many computational tasks, particularly in machine learning, the structure of the data is precisely what the computation seeks to exploit to infer outputs or learn meaningful patterns. Consequently, coded-computing schemes should preserve and leverage this structure in their code design, rather than ignoring or eliminating it through source coding. This observation motivates a different perspective on code construction. In many channel-coding schemes, such as Reed-Solomon codes, coded symbols are generated by evaluating a low-dimensional algebraic representation at selected points. In contrast, many high-dimensional datasets naturally concentrate near low-dimensional manifolds. In this paper, we exploit this intrinsic geometry by designing coded samples that follow the natural manifold of the data, rather than imposing an artificial low-dimensional structure unrelated to the data distribution. Inspired by graph-based manifold learning, we propose a manifold-aware encoding strategy for general coded computing (GCC). Experiments on neural network inference and high-dimensional polynomial evaluation demonstrate that the proposed strategy consistently and significantly reduces the mean squared recovery error under straggling compared with standard GCC.
I. INTRODUCTION
The paper argues that coded computing should preserve and exploit intrinsic data structure rather than treating it as redundancy to remove. It proposes ordering samples along learned manifold geometry so encoded inputs remain meaningful and recovery improves.
- Stragglers delay or prevent worker outputs, making their mitigation central to distributed computing.
- Existing coded-computing approaches generally overlook intrinsic statistical structure, even though machine-learning computations exploit that structure.
- A smoother, geometry-following encoder curve can be represented more accurately from limited samples, supporting more accurate recovery.
- High-dimensional datasets often concentrate near low-dimensional manifolds, whose geometry provides intrinsic redundancy for code design.
- The proposed manifold-aware GCC builds a distance-weighted graph, uses a short Hamiltonian path to order samples, and preserves the standard GCC pipeline.
- Arbitrary sample ordering can create complex encoder curves and coded symbols away from the manifold, increasing approximation error and risking unreliable target-function behavior.
II. PROBLEM FORMULATION AND GCC BACKGROUND
The problem formulation considers a master computing batched evaluations of a general high-dimensional function across N workers. Straggling workers are modeled through a varying random subset of workers whose outputs arrive before the deadline.
- The master seeks to compute the batch {f(x_k)} for inputs x_k ∈ R^d using a target function f: R^d → R^m.
- The target function may be a general high-dimensional computation, including a deep neural network used for inference.
- Straggling workers may be delayed, congested, or fail, preventing assigned computations from arriving before the deadline.
- The non-straggling set F varies across rounds and is modeled as a random subset drawn from a distribution P_F over worker subsets.
A. Standard General Coded Computing
Standard GCC encodes a batch through a smoothing-spline curve, evaluates the target function on worker-specific coded inputs, and decodes from non-straggler outputs. Its spline construction is motivated by an optimization-based upper-bound design.
- Standard GCC has encoding, worker computation, and master-node decoding stages.
- Encoding: The encoder fits a second-order smoothing spline through input samples assigned to ordered encoder design points.
- Encoding: Each worker receives a coded input generated by evaluating the encoder spline at its decoder design point.
- Computation: Workers apply the target function to coded inputs, and the master observes outputs only from the non-straggling workers.
- Decoding: The decoder fits another second-order smoothing spline to returned outputs and evaluates it at encoder design points to estimate desired function values.
- Evaluation: Performance is measured by mean squared recovery error averaged over straggling patterns.
III. MANIFOLD-AWARE GENERAL CODED COMPUTING
Manifold-aware GCC orders data according to empirical geometry so the encoder curve is smoother and coded inputs remain near the data manifold. A 2-opt heuristic approximates the exact shortest-path ordering with substantially lower computational cost while retaining comparable recovery performance.
- Geometry-aware ordering: GCC assigns nearby data samples to nearby encoder design points to reduce large transitions through ambient space.This ordering produces a smoother encoder curve and helps keep coded samples near regions supported by the data.
- Efficient optimization: 2-opt ordering closely tracks exact optimal ordering in LeNet5 at (N, K) = (20, 10), while being substantially more efficient to compute.The heuristic repeatedly replaces two path edges when the exchange reduces total path length.
- Geometry-aware ordering: The ordering is chosen by minimizing total path length in a weighted graph whose edge weights measure pairwise data distances.Distances may instead be defined in a feature space, allowing the ordering criterion to reflect task-relevant geometry.
- Efficient optimization: The exact optimization is a shortest Hamiltonian path problem, making dynamic-programming solutions impractical when K is moderately large.Bellman–Held–Karp methods require O(K22^K) time and O(K2^K) memory.
- Evaluation: Fig. 4 compares standard and manifold-aware GCC on LeNet5 and degree-8 polynomial evaluation across increasing straggler counts.The evaluation includes mean squared recovery error, relative accuracy, and a zoomed polynomial-task view.
A. Computational Complexity
The proposed ordering stage adds pairwise-distance computation and iterative 2-opt search to the standard GCC encoder-decoder pipeline. Its total master-side complexity combines these ordering costs with standard GCC encoding and decoding costs.
- Ordering stage: Pairwise distance computation costs O(K2d), and one full scan of the 2-opt neighborhood costs O(K2).With T local-search passes, these contribute O(K2d + TK2) to the ordering stage.
- Total complexity: The total master-side complexity is O(K2d + TK2 + (N + K)d + (|F| + K)m).The first two terms arise from manifold-aware ordering, while the remaining terms are standard GCC encoder and decoder costs.
- Total complexity: Using |F| ≤ N and K2d dominating Kd, the complexity is upper-bounded by O(K2d + TK2 + Nd + (N + K)m).This bound makes the dependence on data dimension, worker count, local-search passes, and decoder dimensions explicit.
IV. EXPERIMENTAL RESULTS
The experiments compare standard GCC with GCC-Manifold on LeNet5 inference and degree-8 polynomial evaluation. Across these tasks, manifold-aware ordering improves recovery, especially as stragglers increase.
- Evaluation tasks: GCC-Manifold is evaluated on LeNet5 inference and high-dimensional degree-8 polynomial evaluation.The experiments test a practical nonlinear machine-learning model and a classic high-dimensional function.
- Experimental setup: The experiments compare standard GCC with the proposed manifold-aware GCC while keeping other hyperparameters identical.Each experiment is repeated 10 times, with averages and 95% confidence intervals reported.
- Evaluation metrics: Performance is measured using mean squared error, with relative accuracy additionally reported for LeNet5 classification.MSE is averaged over input batches and straggling sets; relative accuracy compares coded and uncoded classification accuracy.
- Results: GCC-Manifold consistently achieves lower MSE and higher relative accuracy than standard GCC for LeNet5, with larger gains in the high-straggler regime.The LeNet5 comparison uses (N, K) = (100, 60).
- Results: For degree-8 polynomial evaluation, GCC-Manifold shows more stable recovery and maintains error close to zero across the tested straggler range.Standard GCC exhibits greater variability and increasing recovery error as the number of stragglers grows; the comparison uses (N, K) = (31, 12).