DART: Input-Difficulty-AwaRe Adaptive Threshold for Early-Exit DNNs

Traditional TinyML systems for edge devices achieve high accuracy by relying on fixed-depth models that require a constant number of multiply-accumulate (MAC) operations regardless of the input complexity. This approach wastes critical resources in battery-powered Internet-of-Things (IoT) devices and limits the real-time performance of edge cyber-physical systems. Multi-exit execution schemes mitigate these issues and are widely used on high-end devices such as GPUs, but are rarely exploited on edge IoT devices because they require substantial rethinking given their strict memory and computational constraints. We address these aspects by designing and deploying, on an ultra-low-power GWT GAP9 System-on-Chip (SoC), a novel multi-exit computational scheme, demonstrating it on a MobileNetV2 convolutional neural network (CNN) for the ImageNet-100 classification task. Our approach introduces multiple exits at different CNN depths, each with a confidence-based gating mechanism that dynamically and autonomously decides whether to continue or stop inference. Comparing our multi-exit strategy to the standard MobileNetV2 on a GAP9 SoC, we show a 41% reduction in the average computational cost (from 313 MMAC to 185 MMAC), a 29% lower inference time (from 49 to 35 ms), and an energy saving of 24% (from 2.1 to 1.6 mJ per frame). All these improvements come with a ~1% loss in accuracy compared to the full-depth MobileNetV2, which achieves 80.5%. Finally, comparing our adaptable multi-exit scheme with a third-party state-of-the-art adaptive CNN, also deployed on the GAP9, we achieve more than 2x its computational efficiency, increasing it from 8.1 to 17.2 MAC/cycle.

Deep neural networks (DNNs) are widely used for their ability to model complex patterns across domains such as computer vision, speech recognition, and robotics. However, larger models, while often more accurate, are computationally expensive and energy-intensive. Since such a cost is typically needed only for challenging inputs, dynamically selecting lighter models for simpler inputs can improve efficiency with minimal impact on accuracy. We introduce PERTINENCE, a runtime method that selects, from a set of pre-trained models, the lightest model likely to process each input correctly. An ML-based dispatcher performs this selection, and a genetic algorithm explores dispatcher training strategies to identify Pareto-optimal trade-offs between accuracy and computational cost. We evaluate PERTINENCE on CNNs trained on CIFAR-10 and CIFAR-100, ViTs trained on TinyImageNet, and a YOLO-based road occupancy estimation application using real-time intersection camera feeds. Results show that PERTINENCE matches or improves the accuracy of state-of-the-art pre-trained models while reducing operations by up to 36%, with equivalent or lower end-to-end inference time through tunable invocation intervals.

Early-exit neural networks enable adaptive computation by allowing confident predictions to exit at intermediate layers, achieving 2-8$\times$ inference speedup. Despite widespread deployment, their generalization properties lack theoretical understanding -- a gap explicitly identified in recent surveys. This paper establishes a unified PAC-Bayesian framework for adaptive-depth networks. (1) Novel Entropy-Based Bounds: We prove the first generalization bounds depending on exit-depth entropy $H(D)$ and expected depth $\mathbb{E}[D]$ rather than maximum depth $K$, with sample complexity $\mathcal{O}((\mathbb{E}[D] \cdot d + H(D))/ε^2)$. (2) Explicit Constructive Constants: Our analysis yields the leading coefficient $\sqrt{2\ln 2} \approx 1.177$ with complete derivation. (3) Provable Early-Exit Advantages: We establish sufficient conditions under which adaptive-depth networks strictly outperform fixed-depth counterparts. (4) Extension to Approximate Label Independence: We relax the label-independence assumption to $ε$-approximate policies, broadening applicability to learned routing. (5) Comprehensive Validation: Experiments across 6 architectures on 7 benchmarks demonstrate tightness ratios of 1.52-3.87$\times$ (all $p < 0.001$) versus $>$100$\times$ for classical bounds. Bound-guided threshold selection matches validation-tuned performance within 0.1-0.3%.