Atalanta: A Bit is Worth a "Thousand" Tensor Values

Alberto Delmas Lascorz, Mostafa Mahmoud, Ali Hadi Zadeh, Milos Nikolic, Kareem Ibrahim, Christina Giannoula and 2 others

Quantizing a neural network to 8-bit integers still wastes space, because the one fixed width has to cover a few rare large values while most values are small and common — and the near-optimal fix, arithmetic coding, needs a 256-entry probability table and slow bit-at-a-time arithmetic that no accelerator can afford; this paper from the University of Toronto builds Atalanta, a tiny lossless compressor that captures almost all of arithmetic coding's benefit by tracking probabilities over just 16 value sub-ranges instead of every value, shrinking a quantized model's off-chip memory traffic to around half and speeding a Tensorcore accelerator by 1.44 times.

The argument in one glance

Problem

A quantized model still stores its common small values in too many bits

The memory footprint of deep-learning models keeps growing, and moving tensors to and from off-die memory dominates their energy and often their speed. Quantization already shrinks each value to, say, 8 bits, but it has to choose one width wide enough for the rare high-magnitude outliers in a tensor. So the many small, common values are stored in far more bits than they deserve, and a lossless-compression opportunity sits unused.
What people did

Reach for arithmetic coding, which is provably near-optimal

Arithmetic coding represents a whole sequence of values as a single number in the range from 0 to 1, spending bits in proportion to how surprising each value is. Uniquely, it can encode a very frequent value in effectively less than one bit, so it approaches the theoretical minimum footprint for the data.
Why it fell short

Arithmetic coding is too big, too slow, and too arithmetic-heavy for an accelerator

To reach that efficiency, classic arithmetic coding needs the expected frequency of every possible value: for 8-bit data that is a 256-entry probability table, and the table and its lookups are prohibitive once replicated for bandwidth. It is inherently sequential, emitting only a few bits per step, which clashes with the wide streaming that accelerators need. And it uses wide multiplications and divisions. One practical configuration would add 93.6 percent power on top of the DRAM itself.
This paper's idea

Track probabilities over a handful of value sub-ranges, not every value

Atalanta partitions each tensor value range into at most 16 sub-ranges, and codes only which sub-range a value falls in, storing its position within the range as a few raw bits. Now the probability table has 16 entries, not 256; the arithmetic collapses to shifts and narrow fixed-point operations done in one step per value; and because activation distributions barely change with input, the sub-ranges can be chosen once by offline profiling.

Why this problem is worth solving

The whole exercise begins from a specific, deliberate imperfection introduced earlier in the pipeline.

Quantization takes a model trained in floating point and re-expresses its weights and activations in a narrower, cheaper representation — most commonly 8-bit fixed-point integers — because narrower values are cheaper to store, move, and compute on, and 8-bit inference usually costs little or no accuracy on many tasks. But quantization normally assigns one fixed bit width to a whole tensor, layer, or network, and that width has to be large enough for the largest-magnitude value present. Since only a handful of values actually need the full width while most are small, the representation is uniform where the data is not, and that mismatch is exactly the slack a compressor can still recover without touching accuracy at all.

The ideal tool for recovering that slack is a classic from information theory, and understanding why it is ideal explains why it is also unaffordable.

Arithmetic coding is a near-optimal entropy coder: it turns a sequence of symbols into a single real number in the interval from 0 to 1, progressively narrowing that interval as each symbol arrives, by an amount tied to the symbol’s probability. Frequent symbols shrink the interval little and so cost few bits — effectively fewer than one bit each — while rare symbols cost more, and the total lands close to the information-theoretic minimum. The price of that optimality is steep in hardware: it wants a probability entry for every possible value, it produces the code one or a few bits at a time in a strictly sequential loop, and it leans on wide multiplications and divisions, all of which are the wrong shape for the wide, parallel, low-power data paths an accelerator is built from.

What people did before, and where it broke

Use a general-purpose memory compressor. Hardware compressors for ordinary programs exploit common address prefixes and repeated byte patterns. Where it broke. Deep-learning tensors follow smooth, Gaussian-like distributions with a few outliers and essentially none of those repetitive patterns, so general compressors find little to grip.
Run-length encode the zeros. Many DL compressors encode runs of zeros, or of repeated values, as (value, count) pairs. Where it broke. This pays off only when tensors are sparse or heavily pruned; on a dense, quantized tensor there are few long runs, so it barely compresses and sometimes expands.
Compress only the weights. Techniques in the Deep Compression line focus on shrinking the trained weight parameters. Where it broke. Activations are produced at run time and often account for as much off-die traffic as weights, and leaving them uncompressed forfeits half the opportunity.
Give each small group its own width (ShapeShifter). Split a tensor into fixed groups and store each group at the minimum width its own values need. Where it broke. A group’s width is still set by its single largest value, so every smaller value in the group is padded to that width; it captures some slack but stays far from optimal, and fails outright on some models.
Use a heavyweight general coder like Deflate or LZMA. These combine dictionary matching with Huffman coding and compress very well. Where it broke. Their hardware is enormous — one reported Deflate engine needs tens of thousands of lookup tables and hundreds of block RAMs for its dictionary — which is far too costly to sit inline at a memory controller running at full bandwidth.
Use full arithmetic coding. It is near-optimal and would recover almost all the slack. Where it broke. The 256-entry table, the strictly sequential bit-at-a-time operation, and the wide arithmetic make it slow and power-hungry, adding on the order of 93.6 percent power over the DRAM in a practical configuration.
The gap. Near-optimal coding existed but could not be afforded inline; affordable coders left most of the compression on the table. No one had near-arithmetic-coding efficiency at a hardware cost small enough to drop transparently in front of any accelerator’s memory.

How Atalanta keeps most of the coding gain at a tiny cost

From one fixed width per tensor to a per-sub-range code

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Let the sub-range, not the outlier, decide how many bits each value costs. The waste in fixed-width quantization is that one width serves everyone, so a value that is almost always small is stored as if it might be large. Atalanta breaks a value into two parts that are priced separately: which sub-range it lies in, and where inside that sub-range it sits. The sub-range is a symbol, and because a handful of sub-ranges hold the overwhelming majority of values, the common symbols are arithmetic-coded in less than a bit each; the position inside the range is an offset written as just a few raw bits, as many as that range’s spread demands and no more. The rare large values still cost their full width, but they no longer tax the common ones — the bits spent on a value now track how often values like it actually occur. Spending a scarce, fixed bit budget where the values really concentrate, instead of provisioning uniformly for a magnitude that seldom appears, is the same reallocation the edge-Transformer number-format work covered elsewhere on this site makes when it argues a format should lavish its precision near the magnitudes a network’s values actually cluster around rather than spreading it evenly.

Take the algorithm that is provably ideal and machine it down to shifts and a small window. Arithmetic coding is not a new idea; it is a decades-old near-optimal coder whose only problem is that its exact form is hostile to hardware. Atalanta’s second move is engineering rather than theory: keep the coder’s essential behaviour but replace everything expensive about it. The 256-entry table becomes 16 entries because probabilities are tracked per sub-range. The strictly sequential, bit-at-a-time loop becomes a single bit-parallel step per value, so a unit emits one value per cycle. The wide multiplications and divisions become shifts and narrow fixed-point operations over a 16-bit window into the conceptually infinite-precision interval, with a 5-bit counter that records “underflow” bits so the finite window can still represent the same code the ideal algorithm would. The result keeps nearly all the coding efficiency while fitting in under 50 bytes of internal storage per unit. Borrowing a mature, standard coding technique and re-engineering it to be cheap enough for a deep-learning data path is the same manoeuvre the video-Transformer codec-assisted work covered elsewhere on this site pulls off, taking the compression machinery already proven in an established domain and adapting it so the accelerator pays almost nothing for it.

Because the statistics are stable, the hard part can be done once, offline. Arithmetic coding normally needs the value distribution known in advance, which is awkward for activations that are only produced at run time. Atalanta’s escape is an empirical regularity: a layer’s activation distribution barely changes from one input to the next, so the sub-ranges and their probabilities can be chosen once by profiling a few sample inputs, then reused for every inference. Weights are even easier, since they never change and a single pass suffices. A software optimizer does this per tensor, searching sub-range boundaries to minimize the encoded footprint, trading off that a wider sub-range means fewer symbol bits but more offset bits. To stay strictly lossless when a value never seen in profiling does appear, the table “steals” a sliver of probability from a populated entry so every possible value remains encodable. Moving the expensive optimization offline by leaning on a workload’s stable statistics, so the run-time hardware only has to execute a precomputed plan, is the same division of labour the recommendation-table statistical-placement work covered elsewhere on this site uses when it profiles the access statistics once and then lets the system serve them from the right memory without re-deciding at run time.

Following one 8-bit value through Atalanta

Encoding a single quantized value, and getting it back

The tensor is already quantized to 8-bit integers. Atalanta is lossless: what comes out of the decoder is bit-for-bit what went in.

Step 1 of 5

Profile the tensor and carve up to 16 sub-ranges

The optimizer builds a histogram of the tensor's 256 possible values and partitions the range into at most 16 contiguous sub-ranges, choosing the boundaries to make the total encoded stream as small as possible.

The search balances a real tension: a wider sub-range needs fewer bits to name (its symbol is more frequent) but more raw offset bits to locate a value inside it. In practice more than 16 sub-ranges improved compression by 0.1 percent or less.

Why it works

Per-sub-range probabilities shrink the table by more than ten times. Full arithmetic coding needs a probability entry per value, 256 of them for 8-bit data → but tracking probability at the granularity of at most 16 sub-ranges needs only 16 entries → so each coder unit holds its whole model in under 50 bytes and can be replicated 64-fold without the table cost exploding.
Frequent sub-ranges are coded in less than a bit. The common small values almost all fall into a few sub-ranges → whose symbols the arithmetic coder represents in effectively under one bit each → so the footprint tracks how often values actually occur rather than the fixed width the outliers forced, cutting weights to 60 percent and activations to 48 percent on average.
Storing the offset raw keeps it cheap and exact. The position of a value inside its sub-range is uniform-ish and carries little structure → so it is written verbatim in exactly the number of bits the range spans, with no probability model → which costs almost nothing to encode and, being a faithful copy, is what makes the whole scheme losslessly reversible.
Bit-parallel single-step coding meets the bandwidth need. Classic arithmetic coding emits a few bits per sequential step, far too slow for wide tensors → but Atalanta collapses the per-bit loop into one operation per value and chunks tensors across many units → so it sustains one value per cycle per unit, the streaming rate accelerators require.
Offline profiling removes the run-time distribution problem. Arithmetic coding wants the distribution known in advance, awkward for run-time activations → but activation distributions barely shift between inputs, so the table is built once by profiling and reused → and stealing a count for unseen values keeps it exactly lossless even when an input strays from the profile.

What it costs (trade-offs and scope)

The end-to-end speedup only helps memory-bound models. The 1.44-times average acceleration on a Tensorcore accelerator comes from removing off-die transfer stalls; for models that are already compute-bound, such as BERT and pruned AlexNet and GoogLeNet, the speedup is minimal and only the energy improves — the headline number should be read as a memory-bound-case result.
It is a 65nm, synthesized-and-simulated evaluation. The hardware is implemented and measured in a 65nm node, chosen for licensing reasons and quite old; there is no fabricated chip, and area, power, and the 4.7 percent DRAM-power overhead come from synthesis, layout, and DRAM power models rather than silicon.
It compresses quantized tensors; it does not quantize. Atalanta is a lossless coder that rides on top of whatever quantization or pruning was already applied, and its benefit grows with how skewed those methods make the distribution — it complements them but cannot substitute for them, and on a poorly skewed model it gains little.
Compression varies widely by model. The averages hide a large spread: weights compress anywhere from 1.13 to 11.4 times and activations from 1.43 to 4.2 times, and some models barely move (MobileNet_v1 activations only to 0.86 of baseline), so the 60-percent and 48-percent headlines are geometric-mean outcomes, not guarantees.
Variable-length output complicates access. Each tensor compresses to a variable-size stream plus metadata (the value count and the small table), which makes random access and addressing harder than fixed-width storage — a cost the paper manages with chunking but does not make disappear.
Every tensor needs an offline optimizer pass and a stored table. The sub-range boundaries come from a per-tensor software search (fast in a C implementation, but still a step), and a small per-tensor table must travel with the data, so there is a one-time preparation cost and a little metadata overhead.
Activation gains rest on the stability assumption. The offline profile is reused across inputs, and while the count-stealing trick preserves losslessness for out-of-distribution values, the compression ratio can degrade when an input’s activations stray from the profiled distribution.
The main rival is the authors’ own re-implementation. ShapeShifter, the strongest comparison point, is modelled by the same group in the same node and design flow, and the end-to-end comparison is limited to the model traces their ShapeShifter simulator supports — a fair but self-run baseline rather than an independent one.

The evaluation

Three ways to shrink a quantized tensor's off-die traffic

Property	Group-width or zero coders (ShapeShifter, RLE)	Full arithmetic coding	Atalanta: per-sub-range coding
Coding efficiency (closeness to optimal)
Probability table size	Tiny (a width per group)
Throughput
Hardware and power cost
Off-die traffic and end-to-end result

Comparison over a wide set of 8-bit (and some 4-bit and BFloat16) models spanning vision, language, and recommendation, with hardware modelled in a 65nm node and integrated with a Tensorcore-based accelerator over dual-channel DDR4-3200 memory.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Atalanta is a lossless compressor that sits on top of quantization, not a replacement for it, so its gains ride on how skewed the already-quantized distribution is and vary a lot by model — weights compress from 1.13 to 11.4 times, and a few models barely move, so the 60-percent-weights and 48-percent-activations figures are averages, not floors. The end-to-end 1.44-times speedup is a memory-bound-case result: compute-bound models like BERT and pruned AlexNet see almost no speedup and gain only in energy. The hardware is evaluated at 65nm through synthesis, layout, and DRAM power models rather than a fabricated chip, and the 4.7-percent power overhead is measured at a specific DRAM operating point. The strongest baseline, ShapeShifter, is the authors’ own re-implementation in the same node, and the end-to-end study is limited to the traces their simulator supports. Practical costs remain: variable-length output complicates random access, every tensor needs an offline optimizer pass and a small stored table, and the activation gains assume the profiled distribution holds — though a count-stealing trick keeps the coding strictly lossless even when it does not. What is genuinely strong is the core result: near-arithmetic-coding efficiency at a tiny, replicable cost, achieved by pricing sub-ranges and offsets separately and machining the ideal coder down to shifts and a 16-bit window.

Background

Why memory traffic is the thing to attack

It helps to step back and see why so much effort goes into shaving bits off tensors rather than making the arithmetic faster. On modern accelerators the compute units are cheap and plentiful; what limits both speed and energy is feeding them, because reading a value from off-die DRAM costs orders of magnitude more energy than the multiply-add it will take part in, and a memory-bound layer leaves expensive compute idle waiting for data. That inverts the intuition that computation is the expensive part: for a great many deep-learning layers, the bottleneck is the traffic between the chip and its memory, so anything that moves fewer bytes over that link — without changing the answer — buys both time and energy directly. Atalanta attacks exactly that link, compressing tensors transparently right before the memory controller so the bytes on the wire shrink while the accelerator above is none the wiser. This is the same pressure the perceptual display-compression work covered elsewhere on this site responds to, where a headset spends a large fraction of its energy simply moving pixels to and from memory and the win comes from sending fewer bits across that path. The broader lesson is that in data-movement-bound systems the highest-leverage optimizations are often not in the compute at all but in the encoding of what has to travel, and that a decades-old idea from information theory, made cheap enough to run inline, can be worth more than another arithmetic unit.

If you remember only three things

1. Quantizing a network to a fixed bit width wastes space because the one width must cover rare large values while most values are small and common, and the near-optimal remedy, arithmetic coding, is too big (a 256-entry table), too slow (bit-at-a-time), and too arithmetic-heavy to run inline at a memory controller.
2. Atalanta captures almost all of arithmetic coding's benefit cheaply by splitting each value into a sub-range symbol and an in-range offset: it arithmetic-codes only which of at most 16 sub-ranges a value falls in (frequent ones cost under a bit) and stores the offset as a few raw bits, shrinking the probability table to 16 entries and the whole coder to under 50 bytes, while replacing wide arithmetic with shifts over a 16-bit window and choosing sub-ranges once by offline profiling.
3. Dropped in transparently before the off-die memory controller, it reduces weight traffic to about 60 percent and activation traffic to about 48 percent on average and speeds a Tensorcore accelerator by 1.44 times at a 4.7-percent power overhead — but it is a lossless layer atop quantization whose gains vary widely by model, helps end-to-end only when the model is memory-bound, and is evaluated at 65nm in simulation against the authors' own baseline.

Check yourself

Check your understanding

1. Why does fixed-width quantization leave compression opportunity on the table?
2. What is Atalanta's central trick for getting near-arithmetic-coding efficiency cheaply?
3. How does Atalanta handle the fact that arithmetic coding normally needs the value distribution known in advance?
4. Which qualification most affects how the headline results should be read?

Sources

The paper is “Atalanta: A Bit is Worth a ‘Thousand’ Tensor Values” by Alberto Delmas Lascorz, Mostafa Mahmoud, Ali Hadi Zadeh, Milos Nikolic, Kareem Ibrahim, Christina Giannoula, Ameer Abdelhadi, and Andreas Moshovos, published at ASPLOS 2024, pages 85-102, DOI 10.1145/3620665.3640356. The authors are at the University of Toronto.

This explainer is written from the full 18-page text. Everything above comes from the paper’s own sections: the introduction on off-die memory as the bottleneck and why general-purpose and prior DL compressors fall short; the discussion of quantization, both direct fixed-point and indirect dictionary forms, and its interplay with compression; the arithmetic-coding primer and its four hardware challenges, including the 256-entry table and the 93.6-percent power overhead of a practical full-AC configuration; the Atalanta design, with its sub-range partitioning into value-plus-offset pairs, the at-most-16-entry table, the single-step bit-parallel encoding and decoding with the 16-bit HIGH and LOW window and the underflow-bit counter, the encoder and decoder implementations and their under-50-byte storage, and the software table optimizer with its per-tensor search and the count-stealing adjustment for unseen activation values; and the evaluation covering off-die traffic and energy versus ShapeShifter and run-length methods, the 65nm area and power (1.14 square millimetres and 179.2 milliwatts for 64 units, a 4.7-percent DRAM-power overhead), the Tensorcore integration giving 1.44-times speedup and 1.37-times energy efficiency, the per-model compression ranges, the sub-range-count sensitivity, the comparisons against Deflate and LZMA, and the applications to BFloat16 exponents, dictionary methods, and training.

Atalanta: A Bit is Worth a &#34;Thousand&#34; Tensor Values