CMC: Video Transformer Acceleration via CODEC Assisted Matrix Condensing

Transformers applied to video are slow because consecutive frames are mostly the same and the model recomputes everything anyway, and the usual fix — a learned module that predicts which parts to skip — costs real chip area; CMC (Shanghai Jiao Tong) notices that phones and set-top boxes already contain a video codec whose entire job is finding which parts of a frame resemble the previous one, and repurposes that circuit to decide which tokens the transformer can skip.

Why this problem is worth solving

The model spends most of its effort on data that barely changes.

The circuit that solves the redundancy problem was built for compression.

What people did before, and where it broke

• Train a small module to select which tokens matter. Image transformer accelerators do this, learning a predictor that examines the input and keeps only the informative tokens. Where it broke. It costs area — the token selector in the design compared against here occupies half a square millimetre — and the prediction is serial with the computation it is meant to accelerate.
• Predict which attention scores will be negligible. Another line of work learns to identify weak attention connections before computing them, so the hardware evaluates only the strong ones. Where it broke. It is per-frame reasoning, and it needs a detector trained alongside the model.
• Retrain the model to be cheaper. Standard practice when adding a selection mechanism, since the model must learn to work with the pruning. Where it broke. Retraining a video transformer is described here as impractical, both because of the time involved and because access to the training data is often restricted.
• Prune to sparse matrices. The general framework behind most of this work: identify unimportant elements, zero them, and use hardware that skips zeros. Where it broke. The resulting matrices need sparsity encoding and decoding, and the compute array is awkward to keep busy. Prior measurement of dynamic pruning finds real speedup flattening well below the arithmetic reduction.
• Apply an image transformer accelerator to video unchanged. The obvious first move. Where it broke. Everything it does is within a frame, so the similarity between consecutive frames — which is the dominant redundancy in video and the entire basis of video compression — is invisible to it.
• The gap. Every one of these builds new hardware to answer the question “which of these things are similar enough to skip”. Video hardware has contained a highly optimised answer to exactly that question for decades, sitting on the same chip, and nobody had connected the two.

How a codec decides what a transformer can skip

The idea

The redundancy detector was already on the chip, built for something else entirely. The question an accelerator must answer to skip work is whether this piece of data is close enough to a piece already handled that recomputing it is waste. That is, verbatim, the question a video encoder answers thousands of times per frame, and the hardware for it is present in essentially every device that touches video: a grid of units computing absolute differences in parallel, feeding adder trees that aggregate at several block sizes, followed by comparators that pick the closest match. Prior accelerators built a learned module to answer the same question and paid half a square millimetre for it. Reusing the codec costs two added registers, an adder, a comparator group and some wires, and the overall design ends up 18 percent smaller than the one it is compared against — area that goes back into arithmetic. Finding that a circuit put there for an unrelated purpose happens to compute exactly what a new design needs is the same pleasing discovery the encrypted search work covered elsewhere on this site makes about the exclusive-or circuit sitting in flash chips for write scrambling.

Condensing is not pruning, and that distinction is where the hardware benefit lives. Nearly all work on skipping computation produces sparse matrices: the unimportant elements are zeroed in place, and the hardware must then encode the sparsity pattern, navigate it during multiplication, and decode afterwards, all while struggling to keep the arithmetic array fed. What happens here is different in kind. Because whole tokens are being skipped rather than scattered elements, the informative rows can simply be gathered into a smaller matrix, and what follows is an ordinary dense multiplication of a smaller thing. No encoding, no decoding, no irregular access, and a compute array that stays busy. The skipped rows are restored afterwards by copying from their reference, which costs a buffer read and write rather than any arithmetic. The gap between arithmetic saved and time saved is exactly what the dynamic pruning measurement work covered elsewhere on this site was built to expose, finding real speedup flattening far below what the operation counts promised.

Reversing the codec’s interpretation of its own answer is what makes it useful here. In compression, a small difference score is good news: it means a close reference exists, the block can be stored as a small correction, and the file shrinks. Here the same score is read as permission to not compute at all — a token that closely resembles one already being processed has its result copied instead. A token whose best match is still distant is the interesting one, so the threshold runs the opposite way from intuition, with large difference scores marking tokens that must be computed. The reference relationship the codec produces, which it would have written out as a motion vector, becomes the instruction for where to copy the answer from afterwards. And the same machinery works one level down, comparing vectors within a single query matrix rather than tokens across matrices, which the augmented codec supports with no further changes. Predicting which parts of attention can be skipped, rather than discovering it after paying, is the same goal the weak-attention detection work covered elsewhere on this site pursues with a trained predictor instead of a borrowed one.

Following one group of frames through the pipeline

The middle is chosen for two stated reasons: it is usually the most representative of the group, and picking adaptively would need more hardware. It also means a quarter of the work is never eligible to be skipped.

Why it works

• Video is redundant in exactly the way a codec measures. Consecutive frames differ little when motion is slow, and neighbouring patches within a frame often look alike → so many tokens entering an attention block closely resemble tokens already being processed → and the sum of absolute differences, which a codec computes to find compressible blocks, is a direct measurement of precisely that resemblance.
• Skipping whole tokens gives dense matrices rather than sparse ones. Zeroing scattered elements produces a sparsity pattern that has to be encoded, navigated and decoded → but removing entire rows leaves a smaller ordinary matrix → so the arithmetic array runs an unmodified dense multiplication and stays fully occupied.
• The prediction is nearly free because the silicon already exists. A learned token selector costs half a square millimetre and must be trained alongside the model → the codec’s motion estimator computes the same similarity and is already present on any device that handles video → so the additions are two registers, an adder, a comparator group and wiring, and the whole design comes out 18 percent smaller than the alternative.
• Zero padding is safe because of what the metric is. Tokens and blocks have mismatched sizes and the codec supports only three block sizes → but a sum of absolute differences is unchanged by appending zeros to both operands → so a short token can simply be padded up to a supported size and fed through unmodified.
• Recovery costs memory traffic instead of arithmetic. Restoring a skipped token requires knowing what it resembled → the codec already produced that as a reference relationship, which it would ordinarily emit as a motion vector → so the restoration is a pipelined buffer copy rather than any computation, and the recovery module is a small fraction of the area.

What it costs (trade-offs and scope)

• The threshold must be tuned per dataset by trial and error, and the paper says so. It is selected on training data and the sensitivity is steep — moving it from 60 to 200 raises speedup from 40.4 to 47.1 times over a processor while costing more than 7 percent accuracy. The chosen setting is a point on that curve, not a principled value.
• The processor and graphics comparisons are scaled rather than measured. Models are run through a standard framework on real machines, and the times are then scaled by the ratio of core counts to the accelerator. The authors explain why they avoid hand-written kernels, but it means the reported speedup over a graphics processor is a normalisation rather than a head-to-head result.
• One of the stated reasons for the speedup is that the baseline is underutilised. The authors list the limited batch size leaving the graphics processor idle among the four sources of their advantage, which is a fair description and also means part of the gap is about the comparison rather than the design.
• The competing accelerator was reproduced by the authors and not retrained. Retraining is judged impractical for these models, which is reasonable, and it does mean the comparison runs a design outside the conditions it was built for.
• The benefit depends on how much the video moves. On slow footage 51.2 percent of token computation is removed; on fast footage 44.8 percent. Across datasets the speedup over a processor falls from 42.4 times on one with slow scenes to 36.5 times on one with fast motion and scene changes.
• A quarter of the work is never eligible to be skipped. With a group length of four, the reference matrix contributes all of its tokens unconditionally, because adaptive reference selection was judged to need too much hardware.
• The group length is bounded by accuracy. Longer groups mean more candidates and more speedup, but the paper reports accuracy dropping severely at sixteen, so four is chosen as the compromise.
• Recovery is a blunt approximation. A skipped token receives its reference token’s output verbatim. It happens to cost only 0.6 percent accuracy on these benchmarks, but nothing about the mechanism bounds the error.
• The architecture is simulated. A cycle-level simulator for performance, synthesis for area and power, and a modified open-source codec model for the augmented estimator. Nothing was fabricated.
• The premise requires a codec to be present, and available. On a platform without one this becomes an ordinary added prediction module. The paper argues the augmentation does not disturb the codec’s normal functions, which is a statement about functionality rather than about contention — it does not discuss what happens when the same estimator is wanted for decoding the incoming video at the same time.

The evaluation

Check yourself

Sources

The paper is “CMC: Video Transformer Acceleration via CODEC Assisted Matrix Condensing” by Zhuoran Song, Chunyu Qi, Fangxin Liu, Naifeng Jing and Xiaoyao Liang, published at ASPLOS 2024, pages 201-215, DOI 10.1145/3620665.3640393. The authors are at Shanghai Jiao Tong University.

This explainer is written from the full 15-page text. Everything above comes from the paper’s own sections: the background on video transformer structure with its three matrix multiplication stages per attention module, and on video compression covering the classification of frames into reference and predicted types, intra-frame prediction modes, the motion estimation algorithm and its sum-of-absolute-differences metric, and the internal organisation of the motion estimation module with its processing element array, two stages of adder trees supporting three block sizes, and hierarchical comparators; the motivating visualisation of token similarity across successive input matrices and vector similarity within a query matrix; the algorithm covering inter-matrix prediction with its designation of the middle matrix as reference, the score matrices, the identification of nearest matches, the threshold binarisation and the resulting informative and non-informative tables, the intra-matrix prediction applying the same procedure to vectors, the construction of condensed matrices for each of the three stages, and the copy-based recovery of tokens and vectors; the architecture covering the two functions added to the motion estimation module, the time multiplexing scheme for tokens exceeding the largest supported block size, the zero padding for tokens below it, the interface between the augmented codec and the accelerator, the fine-grained buffer management ensuring conflict-free result placement, and the pipelined recovery module; and the evaluation covering the seven models and three datasets, the accuracy and computation reduction figures, the comparison between slow and fast footage, the simulation and synthesis methodology, the scaled comparison against processors and graphics hardware, the execution cycle breakdown, the separate contributions of algorithm, augmented codec and recovery module, the area comparison against a competing accelerator, the energy results, and the sensitivity studies on group length and threshold.