Some of the most energy-efficient vision systems now compute the first layers of a neural network in physics rather than software. Examples include optical masks that convolve light before it reaches a sensor, pixels whose transistor sizes encode fixed weights, and neuromorphic chips whose synaptic weights are fused into the silicon. Because none of these weights can change, the only way to cope with a shifted input (fog, sensor noise, a new domain) is a side channel: nudge neuron firing thresholds, search over input prompts with extra forward passes, or fall back to a slower, flexible digital network. Each of these makes the time to finish a request depend on how shifted that particular input is. Meanwhile, deployed systems often promise that once a request is accepted, it will be answered by its deadline. Scheduling theory has precise answers about when such promises can safely be made, but only for jobs whose running time is known when the promise is given.
This note proposes a simple protocol and a matching analysis. The fixed hardware pass is cheap and cannot be interrupted, and its output (prediction entropy, activation statistics) reveals how much adaptation the input will need. The scheduler should therefore run that pass as a probe, and only then decide whether to accept the job and how much adaptation budget to give it. We claim that making the promise after the probe, rather than at arrival or at the start of full execution, recovers the throughput guarantees that scheduling theory gives for known running times. The price is that the probe uses up some of each job's slack. We will test this on corrupted-image streams with real adaptation methods.
Core Claim
Online scheduling with commitment asks when a scheduler must promise to finish a job. Promising at arrival is hopeless: Chen et al. show no algorithm has a bounded competitive ratio (worst-case ratio to the best offline schedule) in that setting. Promising at admission costs little. The same paper shows $O(1/\epsilon^2)$ on one machine, and Eberle, Megow, and Schewior obtain $\Theta(1/\epsilon)$ on unrelated machines. Here $\epsilon$ is the slack, defined by a deadline window $d - r \ge (1+\epsilon)p$ for a job with release time $r$, deadline $d$, and processing time $p$. Their "$\delta$-commitment" result, which promises once remaining slack falls below a fraction $\delta$, gives $O(1/(\epsilon-\delta))$.
All of these results assume $p$ is known. On rigid hardware it is not. A job has a known probe cost $q = \theta p$, which is the non-interruptible fixed-hardware pass. It also has an unknown adaptation cost that is revealed only after the probe and can inflate total work to as much as $\kappa p$. Our main conjecture is that a probe-then-commit scheduler achieves a competitive ratio of order $1/(\epsilon - \theta)$, independent of $\kappa$. It would do this by treating the probe as consumed slack, much as $\delta$-commitment does, and then admitting with the revealed cost. By contrast, committing at start with a worst-case cost estimate needs slack that grows with $\kappa$. We make a second point about the adaptation budget. Forward-only adaptation is anytime: more search iterations buy more accuracy. The scheduler therefore promises a deadline, not a fixed amount of work. After admission it chooses how many adaptation iterations fit, which turns rejection into a graded quality decision.
The idea is new because it moves the commitment point to a place defined by the hardware. The closest theoretical work, the $\delta$-commitment result of Eberle, Megow, and Schewior, picks the commitment point by elapsed slack and assumes $p$ is known. Here the commitment point is the moment information arrives, and $p$ is unknown before it.
Research Program
The theoretical part extends the Blocking Algorithm of Eberle, Megow, and Schewior to a job model with three parts: a non-interruptible probe, uncertain adaptation work revealed after the probe, and an optional digital fallback on a second, unrelated machine. The Blocking Algorithm is our method source because it is decentralized and already handles machines with different speeds, which fits a combined optical and digital pipeline like that of Choi et al.. The probe's non-interruptibility conflicts with the size-based interruption used by the Region Algorithm of Chen et al.. We handle this by making probes atomic and short relative to $\epsilon p$, and we will prove how much the interruption-tree charging argument degrades as a result. For jobs with different values, we will test whether the two-threshold density rule of Eberle can be applied after the probe, using the revealed cost. That paper proves optimality only without commitment, so we treat this step as an empirical question rather than a promised theorem. We will also prove the matching negative result: without a probe, any commit-at-start policy that is robust to $\kappa$ must lose a factor that grows with $\kappa$.
The systems part builds a simulator. Arrivals follow bursty, time-varying traces modeled on the setting of Rigter et al.. Each arrival is an image drawn from a corruption stream whose severity changes over time. The adaptation menu has three options, each with measured latency–accuracy curves:
- threshold modulation for spiking networks (Zhao et al.), in its constant-cost feed-forward version (TM-NORM) and its entropy-based version (TM-ENT);
- forward-only prompt search with an evolution strategy (FOA, Niu et al.), measured at 1 to $K$ search iterations;
- a digital fallback whose latencies are taken from the reported Systolic-CNN figures of 2 ms for AlexNet and 33 ms for ResNet-50 (Dua, Li, and Ren).
The probe signal is the entropy and channel statistics after the fixed-hardware pass. We will measure how well it predicts the adaptation cost needed to reach a target confidence, because the whole proposal depends on this.
Baselines
The naive reference is non-adaptive EDF with commit-at-start. It uses Earliest Deadline First ordering, accepts any job that fits at nominal cost, and applies no adaptation, so it shows what the rigid hardware delivers on its own.
The strongest existing scheduling method is the Blocking Algorithm of Eberle, Megow, and Schewior with commitment at admission. We will run it in two variants. The first is given worst-case cost $\kappa p$, which is safe but conservative. The second is given the average cost, which is efficient but can break promises. It is the strongest competitor because it is optimal for known $p$. No reported empirical result was found on Lacuna for the Blocking Algorithm, the Region Algorithm, or the admission policy of Rigter et al. on inference workloads. We will therefore implement all of them ourselves.
On the adaptation side, the strongest reference is FOA at 63.5% accuracy on an 8-bit ViT on ImageNet-C, compared with 59.6% for full-precision TENT (Niu et al.). Threshold modulation reduces ImageNet-C error from 73.2% to 58.2%, and CIFAR-10-C error from 46.7% to 25.2% with TM-NORM (Zhao et al.). These are offline accuracies with no deadline. We will reproduce them without time limits as an upper-bound sanity check.
All schedulers receive the same arrival traces, the same adaptation menu and latency models, the same hardware budget, and the same tuning budget for their parameters, selected on held-out traces.
Two ablations isolate the key ingredient. The first uses the probe signal only to choose the adaptation budget but still commits at start. The second commits after the probe but uses a fixed adaptation budget.
Our method beats the baselines if it achieves higher correct-on-time throughput, meaning accepted jobs answered correctly by their deadline, weighted by job value, with zero broken promises. We also require that its advantage over the worst-case Blocking variant grows with the spread of corruption severity (larger $\kappa$), as the theory predicts.
Why not just…?
Why not just use TM-NORM, whose cost is fixed, so running time is known again? This is the most serious threat. If feed-forward threshold modulation recovers most of the accuracy at constant cost (3% energy overhead in Zhao et al.), the scheduling problem disappears. We include always-TM-NORM with the Blocking Algorithm as a baseline. If it matches our method across severity mixes, we will report that variable-cost adaptation is not worth scheduling for. The case for our method rests on the gap between 25.2% (TM-NORM) and 24.8% (TM-ENT) error on CIFAR-10-C being small, while on ImageNet-C the costlier, search-based FOA is the stronger adapter. Which regime dominates is an empirical question we will settle directly.
Why not just predict the adaptation cost from the raw input at arrival and commit then? A learned predictor at arrival still commits before the rigid pass. Any prediction error then becomes either a broken promise or wasted capacity, and the impossibility result of Chen et al. applies to adversarial arrivals. On pixel-embedded hardware (Datta et al.), the raw input is not even available without paying for the first layer. We will nonetheless include a raw-input predictor running on a digital side path, and compare how accurately it predicts cost against the probe signal.
Why not just skip commitment and drop jobs that miss their deadline? That changes the problem rather than solving it. Still, dropping without commitment is the natural upper reference point: Chen et al. give $O(1/\epsilon)$ in that setting. We run it to measure how much throughput the promise costs under our protocol, and we expect that cost to shrink to a constant factor once $\theta \ll \epsilon$.
Proposed Experiments
We will build streams from CIFAR-10-C and ImageNet-C, with corruption type and severity switching on a time-varying schedule. We will add a Visual Wake Words stream with synthetic sensor noise to represent the in-pixel setting of Datta et al.. We will also run an optical-encoder stream in which images outside the encoder's reported transfer range are routed to digital fallback (Choi et al.).
Across these streams we will vary slack $\epsilon$ and probe fraction $\theta$. We will measure correct-on-time throughput, rejection rate, broken promises, and energy per correct answer.
Two checks decide whether the proposal holds up. The first is whether the probe signal's correlation with the adaptation cost actually needed exceeds that of a raw-input predictor. If it does not, the method has no information advantage. The second is whether the throughput gap between probe-then-commit and worst-case commit-at-start grows with severity spread $\kappa$ and shrinks as $\theta$ approaches $\epsilon$, as the $1/(\epsilon-\theta)$ form predicts. If the gap is flat in $\kappa$, the theory is wrong for this workload, and the simpler TM-NORM baseline should be preferred.
References
- A general framework for handling commitment in online throughput maximization
- Online Throughput Maximization on Unrelated Machines: Commitment is No Burden
- Transferable polychromatic optical encoder for neural networks
- O(1/ε) Is the Answer in Online Weighted Throughput Maximization
- Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction
- Threshold Modulation for Online Test-Time Adaptation of Spiking Neural Networks
- Test-Time Model Adaptation with Only Forward Passes
- Systolic-CNN: An OpenCL-defined Scalable Run-time-flexible FPGA Accelerator Architecture for Accelerating Convolutional Neural Network Inference in Cloud/Edge Computing
- A processing-in-pixel-in-memory paradigm for resource-constrained TinyML applications