Source-linked AI summary
Towards Stream Learning on Embedded Systems: Benchmarking the Memory Consumption of Stream Learning Methods
Sebastian Buschjäger, Nuwan Gunasekara, Heitor Murilo Gomes
TL;DR
Stream-learning research often prioritizes predictive performance and drift adaptation without systematically evaluating bounded resource usage over long streams. This paper benchmarks seven classifiers across 13 streams and explicit memory budgets, finding distinct failure modes in ensembles and incremental trees and motivating resource-aware interfaces.
Problem
Resource constraints, particularly memory and latency, remain inconsistently considered in stream-learning evaluation despite their importance for sustained and embedded operation.
Method
The paper benchmarks seven representative learners on 13 streams under fixed memory budgets, measuring predictive performance, model size, budget exhaustion, and latency.
Results
Compact methods lead under the smallest budgets, while adaptive ensembles become competitive with more memory; ensembles can fail immediately from initial footprint, whereas HT and EFDT can exhaust budgets through growth.
Takeaways & Limitations
Bounded resource usage should become a first-class stream-learning design objective alongside drift adaptation, supported by explicit resource-aware evaluation and learner interfaces.
Takeaways & Limitations
Absolute byte-level comparisons are limited because MOA and Shrubs use different memory-accounting techniques and no common embedded deployment stack exists.
Abstract
from arXiv · showhide
Stream learning is commonly evaluated through predictive performance and adaptation to concept drift. However, sustained operation of a stream learner also requires predictable and bounded resource usage even on long streams. This requirement becomes even more critical when learning moves from servers to near-sensor embedded systems where memory and processing are scarce resources. In state-of-the-art stream learning, however, we perceive a strong focus on concept drift adaptation, whereas resource usage is often an evaluation byproduct. To close this gap, we benchmark seven representative stream classifiers on 13 real and synthetic streams under model-size budgets from 128\,KiB to approximately 8\,MiB. Our benchmark comprises a total of 6,463 experiments. We measure failure-aware accuracy, peak model size, time to budget exhaustion, and prediction-plus-update latency. The results reveal two distinct resource failure modes. Adaptive ensembles can exceed small budgets almost immediately because of their initial footprint, even when their size remains stable thereafter. Incremental trees can fit initially but grow throughout a long stream, with HoeffdingTrees (HT) and Extremely Fast Decision Trees (EFDT) increasing by median factors of 7.37 and 5.87. Explicitly compact methods remain the only viable option under the smallest budgets, but are usually overtaken as larger budgets make adaptive ensembles competitive. Hence, many state-of-the-art methods are only partially applicable in embedded systems or for long-running systems. We therefore call on the stream-learning community to make bounded resource usage a first-class design objective alongside drift adaptation, and propose concrete steps toward this goal, including an API through which stream learners can explicitly expose and respect resource budgets.
Introduction
Stream learning for near-sensor devices must combine drift adaptation and predictive performance with bounded memory, stable latency, and sustained operation. This paper addresses the gap by benchmarking representative learners under explicit memory constraints and proposing a resource-aware interface.
- MCU-class devices typically provide kilobytes to a few megabytes of memory, enforcing one-pass processing, no historical-data retention, and memory-bounded learning.
- Long-running stream learners require bounded model size, stable update and prediction time, and robust performance after millions of updates.
- Resource usage is often treated as a reported statistic or implementation safeguard rather than a first-class experimental constraint.
- The benchmark evaluates representative online classifiers across seven real-world and six synthetic streams using predictive performance, model size, latency, and fixed memory budgets.
- The paper defines a framework-independent protocol and resource-aware learner interface covering peak size, budget exhaustion, failure-aware accuracy, and latency.
Related Work
Prior stream-learning work emphasizes incremental prediction and concept-drift adaptation, while explicit resource management remains inconsistent. Existing resource-aware methods and frameworks provide partial solutions but do not generally guarantee hard budget compliance across long streams.
- Foundational and adaptive stream learners primarily address incremental induction and revising model structure under concept drift.
- Resource-aware methods such as SVFDT, CS-ARF, GAHT, Shrubs, and PLASTIC remain exceptions in a literature dominated by predictive performance and drift adaptation.
- Limiting growth or reducing average consumption does not necessarily guarantee compliance with a hard memory budget under peak utilization or arbitrarily long streams.
- TinyML and TinyOL use restricted updates and hardware-specific techniques, but their specialized architectures and implementations are not generally applicable across devices and datasets.
- MOA, CapyMOA, and River support prediction and incremental updates as first-class abstractions but lack a common interface for resource control and model-size reporting.
Experimental Evaluation
The evaluation distinguishes predictive quality, initial memory footprint, and subsequent model growth across diverse streams and constrained implementations. It uses optimistic budget-compliant selection, long-horizon monitoring, and runtime-specific memory accounting to assess deployment readiness.
- The benchmark covers incremental, adaptive, ensemble-based, and explicitly compact learners, including HT, HAT, EFDT, PLASTIC, ARF, SRP, and Shrubs.
- Evaluation uses prequential prediction-then-update processing and selects the highest-accuracy observed configuration that remains peak-compliant over the entire stream.
- Datasets: The streams include binary and multi-class tasks with abrupt, gradual, incremental, and natural non-stationarity, spanning approximately 14,000 to 11 million real-world examples.
- Scope and Measurement Boundary: Absolute byte-level comparisons are constrained because MOA learners use JVM object-graph instrumentation while Shrubs manually counts ensemble data structures.
- Resource budgets: The study targets model-size thresholds from 128 KiB to 8,192 KiB and stops training after budget exceedance while continuing performance evaluation.
- Experimental procedure: Random search samples up to 20 configurations per method, repeats each three times, uses one CPU core, and discards runs exceeding a 12-hour limit.
RQ1: Accuracy Under a Fixed Budget
Under fixed memory budgets, explicitly compact methods lead at the smallest limits, while adaptive ensembles become competitive as more memory is available. The comparison uses average ranks across 13 datasets, with lower ranks indicating better performance.
- Each critical-difference diagram row represents a memory budget, with methods ranked across the 13 datasets and lower average ranks considered better.
- At 128 KiB, ARF and SRP have no peak-compliant configuration, while PLASTIC and Shrubs comply on all 13 datasets and attain the leading ranks.
- For budgets below 1 MB, Shrubs, HT, and EFDT are generally the best methods.
- For larger budgets, ARF and SRP dominate, followed by Shrubs in third place.
RQ2: Long-Horizon Model Growth
Long-stream model growth separates learners that retain and extend tree structure from explicitly bounded methods and dynamically managed ensembles. HT and EFDT risk eventual infeasibility, whereas ARF, SRP, PLASTIC, and Shrubs show comparatively stable size for different structural reasons.
- RQ2: Long-Horizon Model Growth: HT, HAT, and EFDT extend their tree topology and rarely remove existing structures, making continued growth expected over long streams.The analysis tests whether these learners grow materially with stream length, while explicitly bounded methods are expected to stabilize.
- RQ2: Long-Horizon Model Growth: Figure 3 tracks model-size progression over the stream and reports each method’s growth ratio for its highest-accuracy unconstrained configuration.Panel (a) shows progression; panel (b) shows growth ratio per method.
- RQ2: Long-Horizon Model Growth: PLASTIC and Shrubs remain constant, while ARF and SRP show only small relative growth despite using tree-based ensemble members.ARF and SRP allocate a fixed number of members, so much of their footprint is present early in the stream.
- RQ2: Long-Horizon Model Growth: ARF and SRP can be infeasible initially, whereas HT and EFDT may become infeasible only after sustained use.Dynamic replacement or resetting can offset ensemble growth, while retained tree structure accumulates over time.
RQ3: Latency Degradation
Latency generally remains near its early-stream level, but growing trees show measurable slowdown that varies across datasets. Thus, model size is an indirect rather than uniform predictor of processing cost.
- RQ3: Latency Degradation: 1.42× median slowdown for HT and 1.16× for EFDT partially support the expected latency degradation from model growth.Their broad distributions indicate that growth does not produce the same additional work on every dataset.
- RQ3: Latency Degradation: The remaining methods have median slowdown close to 1×, although HAT and PLASTIC produce notable outliers.Values above 1× indicate slower terminal processing than early-stream processing; values below 1× indicate faster processing.
- RQ3: Latency Degradation: Figure 4 shows slowdown distributions computed as terminal latency divided by early-stream latency, with 1× marking unchanged latency.Early latency is the median from 2%–10% of the stream, and terminal latency is the median over the final 10%.
RQ4: Time to Budget Exhaustion
Budget exhaustion occurs through two timing patterns: some large ensembles are infeasible near the stream’s beginning, while initially smaller trees exhaust budgets later as they grow. Increasing the budget delays or removes exhaustion for most learners.
- RQ4: Time to Budget Exhaustion: Figure 5 plots the percentage of accuracy-optimal configurations still within budget over normalized stream progress.A near-origin drop indicates initial infeasibility, whereas a gradual decline indicates exhaustion during operation.
- RQ4: Time to Budget Exhaustion: At 128 KiB, ARF and SRP are almost uniformly infeasible from the beginning, followed quickly by HT, HAT, and EFDT.PLASTIC and Shrubs remain feasible under this smallest representative budget.
- RQ4: Time to Budget Exhaustion: At 512 KiB, exhaustion occurs later but remains an issue for every method except PLASTIC and Shrubs.This indicates that a larger budget postpones failures without eliminating them broadly.
- RQ4: Time to Budget Exhaustion: At 2 MiB, most learners complete the stream within budget, while HAT, EFDT, and ARF still struggle.The analysis uses accuracy-optimal unconstrained configurations and evaluates whether their recorded size progression exceeds each budget.
RQ5: Model Size and Concept Drift
Around known abrupt and gradual drift events, learner mechanisms produce distinct model-size and latency trajectories. The broader results connect these mechanisms to two resource-failure modes and motivate explicit resource handling in stream-learning frameworks.
- RQ5: Model Size and Concept Drift: HT grows throughout both synthetic streams, while adaptive trees can contract, replace structure, and regrow around drift events.The comparison uses AGR streams with abrupt and gradual drift and examines HT, HAT, ARF, and Shrubs.
- RQ5: Model Size and Concept Drift: Fixed-size or explicitly bounded ensembles operate around a more stable size than retained-tree learners.These mechanisms help explain why ARF and SRP can remain comparatively stable while HT and EFDT accumulate structure.
- Discussion and Future Directions: ARF and SRP may exceed budgets immediately through their initial footprint, whereas HT and EFDT may exhaust them later as retained structure accumulates.The two modes distinguish initial infeasibility from growth-driven exhaustion during operation.
- Discussion and Future Directions: Current frameworks provide no common mechanism for expressing, enforcing, or testing resource budgets, motivating a resource-aware learner interface.The paper presents this infrastructural gap alongside the algorithmic problem of learners exceeding MCU-class budgets.
- Discussion and Future Directions: Resource-aware evaluation should report initial footprint, peak model size, budget-exhaustion time, failure-aware performance, and long-stream latency.The proposed resource-aware stream-learning loop measures usage, reports failures, and enforces the budget before training continues.
APPENDIX
The appendix presents trajectories for model size and relative latency across datasets and methods, plus median stream completion before the first budget violation. Figure 9 clarifies that a value of 100 indicates median completion, not universal budget compliance.
- Figures 7 and 8 show model-size trajectories for datasets 1–7 and the remaining datasets.
- Figure 9 reports the median stream percentage before the first observed violation for every configured budget.A value of 100 means the median trajectory completes, not that every trajectory is compliant.
- Figures 10 and 11 show relative-latency trajectories for datasets 1–7 and the remaining datasets.
- Figure 12 shows model-size trajectories for all seven methods.
- Figure 13 shows relative-latency trajectories for all seven methods.