The Primitive That Pays for Itself
A single precomputed table turns the cost of window scanning into arithmetic. The Integral Image accumulates a running sum across the whole image, so the pixel sum inside any axis-aligned rectangle, of any size, comes back in exactly four array reads. Frank Crow built the same structure in 1984 for texture-map antialiasing under the name summed-area table; Viola and Jones reintroduced it in 2001 for face detection, and that reintroduction is the ancestor every later use in this history descends from.
The Viola–Jones Object Detector spends the budget the table buys on an exhaustive search: a 24×24 sub-window slides across every position and scale, and each candidate rectangle feature costs the same four reads no matter its size. What makes the search real-time is not the primitive alone but a 38-stage cascade trained by AdaBoost, where cheap early stages reject almost all background before costlier stages ever run, so an average of ten of the cascade's 6,061 trained features are evaluated per sub-window. The features themselves are still weighted sums of raw intensities compared against boosted thresholds; the next problem is whether even that per-pixel comparison can be made cheaper.
Cheap Tests Replace Expensive Ones
Two more constructions attack the same problem from the comparison side rather than the summation side. The FAST Corner Detector tests a candidate pixel against a 16-pixel Bresenham ring of radius three: an arc of contiguous ring pixels uniformly brighter or darker than the centre by a margin marks a corner. No gradient is ever computed, and a four-point check on the ring's cardinal positions rejects most non-corners before the rest of the ring is read. BRIEF applies the same discipline to description: instead of building a continuous descriptor and compressing it afterward, it runs a fixed table of pixel-pair brighter-than tests on a smoothed patch and packs the results into a binary string, matched by XOR and a population count rather than a nearest-neighbour search over floats.
ORB fuses the two. FAST-9 candidates ranked by Harris cornerness supply the keypoints, and a version of BRIEF's tests, steered to each keypoint's orientation and replaced by 256 tests chosen by a greedy search for low correlation, supplies the descriptor. The result is a detect-and-describe pipeline of integer comparisons alone, fast enough for a 2011 phone. Steering the offset table without relearning it collapses the descriptor's variance; the learned, decorrelated table restores it. Detection and description are now nearly free; the backbone consuming their output is still an unbudgeted stack of full convolutions.
The Backbone Becomes a Budgeted Object
MobileNetV2 does not shrink a standard backbone's layer widths; it restructures the block. The inverted-residual block expands a thin bottleneck into a wide interior, filters that interior with a depthwise convolution, then projects back down to a thin bottleneck with no nonlinearity, and the residual connects the thin ends rather than the wide middle. Dropping the final nonlinearity is deliberate: squashing a low-dimensional feature through a ReLU destroys information a linear projection would keep.
MnasNet changes what the budget is measured in. Rather than trust FLOPs as a stand-in for speed, it measures latency directly on a Pixel phone during search and rewards each sampled network for the accuracy it buys per millisecond, motivated by cases where two networks with nearly identical multiply-add counts ran at very different real speeds. The search builds its candidates from MobileNetV2's inverted-residual block.
MobileNetV3 fuses both lines and adds a third step: MnasNet-style search sets the coarse block structure, a per-layer filter-trimming pass tunes it further, and two costly layers the search still missed are redesigned by hand. A new nonlinearity, h-swish, is piecewise-linear and exact under the arithmetic quantized runtimes use, avoiding the quantisation loss a soft sigmoid would cost. The backbone is now searched, budgeted, and hand-corrected; the next question is whether the discipline survives a decoder that must reconstruct a full-resolution label map instead of a single class score.
The Same Trick for Dense Prediction
Semantic segmentation must produce a label for every pixel, and doing so had forced a tradeoff between spatial detail and receptive field onto a single path. BiSeNet removes the tradeoff by refusing to share a path: a wide, shallow Spatial Path preserves detail while a separate, deep Context Path with global pooling builds receptive field, and a small fusion module merges the two afterward, so accuracy and detail no longer compete for the same layers. The later version of the network goes further, removing the ImageNet-pretrained backbone its context branch depended on and training that branch from scratch instead.
Fast-SCNN notices that two-branch segmenters still pay for early downsampling twice, once per branch, and removes the duplication: a single shared shallow prefix feeds both the high-resolution detail skip and the entry point of the deep global-feature branch. Fine-tuning this network from ImageNet weights improves its accuracy by only about half a point, evidence that a small enough budgeted network does not need the pretraining crutch a larger one relies on. Both networks are compared directly against MobileNetV3's own segmentation head in the same real-time mobile segmentation regime, peer choices at a shared budget rather than one replacing the other. Every trick so far has been designed by hand or discovered by searching a space built from scratch; the next stage inherits a network someone else already paid to train at far larger scale, and has to decide what to keep.
Distillation and Search as the New Discipline
Once the expensive thing is a foundation-scale encoder, the budget trick changes shape. MobileSAM does not build a new architecture from scratch: Segment Anything's cost lives almost entirely in its image encoder, so MobileSAM leaves the prompt encoder and mask decoder frozen at their published weights and distils only the encoder into a much smaller student trained to reproduce the frozen teacher's image embedding. A companion piece keeps the same three-part interface but replaces the dense grid-of-prompts stage with an object-aware detector that proposes far fewer boxes, a swap that alone delivers a greater-than-16x total pipeline speedup.
EfficientAD makes the analogous move for anomaly detection. Rather than design a different, more constrained student architecture to stop it from generalising past the teacher, student and teacher share one architecture and a hard feature loss plus a pretraining penalty alone keep the student from copying the teacher on anomalous input, reaching millisecond latency while still leading its own comparison table. A second branch, a plain autoencoder with no skip connections, is added specifically to target the logical and compositional anomalies the local branch's small receptive field cannot see.
XFeat targets the classical pipeline of FAST corners and BRIEF-style, ORB-steered binary description directly. It starves a VGG-style backbone at high resolution and concentrates channel growth at the smallest stages instead, decouples keypoint detection from the descriptor encoder entirely, and trains its keypoint head by distillation from ALIKE-tiny rather than from a hand-crafted ground truth. Distillation and search have replaced hand design as the mechanism, but each one still narrows a single, already-trained expensive thing down to what one target device can afford.
Who Pays for Cheap
RF-DETR pushes the same discipline one step further. Instead of training one fixed-size detector, or distilling one teacher into one fixed student, it trains a single weight-sharing network once, sampling a different random sub-network configuration at every training step. After training, thousands of configurations, varying resolution, patch size, decoder depth, query count, and window count, are evaluated with no retraining, tracing an entire accuracy-latency Pareto frontier from one run instead of one model per budget.
That frontier is not free. RF-DETR's backbone is a pre-trained DINOv2 checkpoint, a vision transformer trained at internet scale by someone else's compute; the weight-sharing search only picks the operating point on top of it, the resolution, patch size, decoder depth and query count a given latency budget can afford. Once the cheap side of the frontier is a distilled or searched slice of a model someone else pretrained at scale, is budget discipline still winning, or is it spending compute it never paid for?