Every Weight Is a Path of Shared Discrete Decisions

AI summary

Overview

Research area: Machine learning model compression and hardware-efficient inference — specifically how neural network weights are represented, stored, and physically computed with, plus the connection between weight selection and discrete (including quantum) optimization.

Technical level: Intermediate. The core idea is explained through small worked examples and needs only a familiarity with floating-point formats and quantization; the formal properties and proofs are confined to an appendix, but the circuit-cost and Boltzmann-machine arguments assume some comfort with digital logic and energy-based models.

Scope: The paper proposes TWIG (Tree-structured Weights with Inherited Gates), a single tree-structured representation in which every weight is the product of shared discrete decisions along a path, and shows that this one object unifies compression formats, maps onto adder-only circuits, and reformulates weight selection as a ground-state problem for higher-order Boltzmann machines.

What This Paper Is About

Neural networks are trained as real numbers but deployed as finite bit patterns computed by logic gates, and the methods that bridge that gap — pruning, quantization, low-rank factorization, codebooks, weight sharing — each come with their own format, solver, and kernel, making them hard to compare or combine. The paper asks for a weight representation that is discrete by construction, that makes explicit which decisions weights share, and that exposes the cost of applying weights rather than only storing them. Its answer is to write every weight as the end of a path of small discrete decisions (a sign, a shift by a power of two, a zero gate, an index into a shared table), with weights that belong together sharing the upper part of the path so each decision is stored once and inherited by everything below it.

Key Contributions

1. The TWIG representation and its two explicit prices. Weights are leaves of a tree whose internal nodes hold small discrete states inherited by all entries below them; each state tree comes with a storage cost (bits of the stored states, counted once when shared, nothing below a closed gate) and a circuit cost (number of additions needed to apply the matrix).

2. Basic properties proved. Today's number formats — floating point, integers with group scales and zero points, block floating point and microscaling including shared microexponents, ternary weights, vector codebooks, and N:M sparsity — are all shallow state trees with at most five levels of decisions on any path, at no more bits than the original format (exactly as many for dense formats). A tree with K leaf values represents every matrix over K values in log2 K bits per entry, and a sum of t power-of-two trees reaches relative error 3^-t per entry using shifts and additions alone, with only m+n genuine multiplications by row scales and column bases.

3. Compression methods become edits of one object. Pruning, quantization, low-rank factorization, codebooks, and weight sharing are all expressed as edits to a single state tree (sums, products, and references), so a single budgeted optimizer can choose among them for a whole network; the optimizer is described as exact under additive costs.

4. Circuit mapping and a first measurement. A tree whose decisions are powers of two turns weight layers into circuits of wires and adders, and choosing the states becomes the ground state of a higher-order Boltzmann machine whose higher-order terms follow the tree's paths — the problem class annealers and quantum optimizers target. On five weight matrices of a large language model, a flat tree with per-weight signed power-of-two terms chosen for circuit cost, with no group scales, needs 9–15% fewer additions than GPTQ at equal layer error at 3- and 4-bit accuracy on typical matrices, and 20–55% fewer on matrices with strong outliers.

Main Findings

• Existing formats cost nothing to adopt: floating point, group-scaled integers, block floating point and microscaling (including shared microexponents and HiFloat4), ternary weights such as BitNet b1.58, vector codebooks such as QuIP#, and N:M sparsity are all shallow state trees; refining a tree never removes options because a new node can always take a transparent (value-one) state.

• Sharing a decision saves bits, not additions: in the paper's two-weight FP16 example (w1 = 0.15625 = (+1)·2^-3·1.25 and w2 = -0.1875 = (-1)·2^-3·1.5), storing the common exponent once needs 5 + 2×11 = 27 bits instead of 32 with identical values; in general g weights sharing an exponent need 5 + 11g bits instead of 16g, approaching a 31% reduction for large groups. The three additions in that example come entirely from the nonzero digits at the leaves — the shared shift saves no addition.

• The running example costs about 3.2–3.3 bits per weight: one column of eight rows stores seven node bits and eight five-state leaves, about 3.2 bits per weight; for long columns the cost approaches 1 + log2 5 ≈ 3.3 bits per weight plus row scales and column bases, and a fractional cost like log2 5 is reached by coding three five-state leaves jointly in 7 bits, since 5^3 < 2^7.

• Two equivalent encodings differ in price: putting shift bits on the edges with leaves {0, ±1} and putting them on nodes with leaves {0, ±1, ±1/2} describe exactly the same columns up to one factor per column, yet the node encoding costs about 3.3 instead of 3.6 bits per weight, because a zero needs no shift so six combinations collapse into five values.

• What shared shifts allow: in a binary tree of shift bits, two nonzero entries whose closest common node lies h levels above them can differ in magnitude by at most a factor of 2^h, and every pattern obeying this rule at every node is reachable — which is why row order matters for bits (not for additions) and why recursive bisection into balanced halves of similar magnitude is a natural ordering.

• Precision equals circuit size: each additional power-of-two term in a weight costs one addition and divides worst-case error by three; a single power-of-two tree is a logarithmic grid with worst-case relative error one third that does not shrink as the tree grows. Integers below 2^b are represented exactly with ceil((b+1)/2) terms per entry, or about b/3 nonzero terms on average.

• First language-model evidence: a flat tree whose signed power-of-two terms are chosen per weight for circuit cost, with no group scales, needs 9–15% fewer additions than GPTQ at equal layer error at 3- and 4-bit accuracy on typical matrices, and 20–55% fewer on matrices with strong outliers, measured on five weight matrices of a large language model.

• Small quantization proof of concept on LLaMA-3-8B: using the running-example tree as a post-training quantizer for the MLP layers only, with one balanced tree per column over rows ordered by recursive bisection of magnitude profiles and states chosen by an exact dynamic program per column with GPTQ-style error feedback, it reached WikiText-2 perplexity 7.78 at 3.33 bits per weight, against 8.03 for GPTQ at 3.25 bits (GPTQ with groups of 128 weights); the edge-bit encoding produced identical weights at 3.60 bits, as the equivalence predicts. The paper notes that a separate table quantizing all linear layers of the transformer blocks with the strongest GPTQ configuration gives 8.09.

• A lossless BF16 format: the step-by-step construction stores BF16 weights exactly in fewer bits using groups of 64 consecutive weights along a row (the worked example uses groups of 4), with an 8-bit shared exponent per group, a 4-bit distance state per weight, and an 8-bit sign-and-mantissa leaf per weight; states 0 to 14 of the 4-bit state encode distances and the remaining slot handles outliers. The shared node does not require exponents within a group to be equal — the states absorb the differences.

• Scope caveat stated by the authors: the properties are proved, but the reported measurements are described as "first evidence on selected models and layers," not a full benchmark study.

Methodology in Plain English

The authors start from an observation about ordinary floating point: a 16-bit float is not really one number but three nested decisions — a sign, an exponent, and a mantissa — read in sequence. Two weights in the same octave of magnitude share their exponent, yet a standard format stores that exponent twice. Because a weight's value is a product of its decisions, any factor two weights have in common can be pulled out and stored once in a node above them, with each weight keeping only what is private to it. Repeating this at many levels of a hierarchy over the matrix's entries gives the state tree: internal nodes hold one small decision (a halving shift, a zero gate, a sign, a table index), leaves hold a little private information, and a weight's value is the product of the states on its path times a row scale and a column base.

The authors then read that same object three ways. As a compressed model, they check that existing formats are shallow trees and that familiar compression methods correspond to edits — adding trees for precision, multiplying trees for low rank, referencing a shared subtree for codebooks. As a circuit, they observe that power-of-two decisions are just wire routing and signs are negations, so applying the matrix reduces to adding shifted copies of inputs; they count additions as the cost and test this on real weight matrices from a large language model against GPTQ at matched layer error. As an optimization problem, they show that picking the states is a higher-order Boltzmann machine ground-state search whose interactions follow the tree. A fully worked small example (a 4×4 BF16 matrix, then scaled up to groups of 64) shows how to build a concrete lossless format decision by decision, with a GPU decoder in mind; formal statements and short proofs are collected in Appendix A.

Why This Matters

Impact on research. The paper argues that separate compression sub-fields — pruning, quantization, low rank, codebooks, sharing — have been converging on shared decisions for years, and that TWIG completes that trend so they can be compared, combined, and optimized jointly under one budget. It also opens a route for annealers, samplers, and quantum optimizers to attack weight selection as a whole rather than only narrow subproblems such as rounding a single layer, and it makes precision and circuit size the same dial.

Real-world applications:

• Circuits whose weights are fixed at fabrication, such as printed classifiers or chips that hardwire an entire language model, where today every weight requires a dedicated constant multiplier; with power-of-two decisions, weight layers become almost entirely wires and adders.
• Post-training compression of large language models, where the reported 9–15% (and 20–55% on outlier-heavy matrices) reduction in additions versus GPTQ at equal layer error at 3- and 4-bit accuracy translates into smaller, cheaper arithmetic.
• Lossless or near-lossless storage of BF16 weights in fewer bits, decoded directly into tensor-core registers on a GPU.
• Edge and embedded inference, where memory bandwidth and adder count, rather than FLOPs alone, bound what can be deployed.

Industry relevance. Multipliers are considerably larger and more energy-hungry than adders in digital logic, so a representation that converts weight multiplications into shifts and additions targets the dominant cost in fixed-weight accelerators; a single format that subsumes group scales, microscaling, codebooks, and sparsity also reduces the current fragmentation into per-method formats and kernels.

Future Directions

• Training directly in the discrete space. The paper outlines (in its Section 8) training a network in the space of tree decisions so that the trained object is already the deployed one, rather than quantizing after training.
• Broader empirical validation. The authors explicitly frame their measurements as first evidence on selected models and layers; scaling the addition-count and perplexity comparisons to whole networks, more models, and more layer types is left open.
• Making the budgeted optimizer practical at network scale. The single optimizer that chooses among pruning, quantization, rank, codebooks, and sharing is described as exact under additive costs; how it behaves with non-additive costs and realistic network-sized search spaces is an open question.
• Handing the ground-state problem to annealers and quantum optimizers. Turning the higher-order Boltzmann machine formulation — with interactions following tree paths — into instances that existing classical and quantum hardware can actually solve is posed as the next step rather than demonstrated.

Target Audience

Researchers and engineers working on model compression, quantization, and low-precision number formats; hardware architects designing fixed-weight accelerators, printed electronics, or adder-only inference circuits; and discrete-optimization researchers interested in whether annealers and quantum optimizers can take on whole-network weight selection. Readers need only a working knowledge of floating-point formats and quantization to follow the main argument, while the appendix-level properties and the circuit-cost accounting will matter most to those who intend to build on or implement the representation.

Authors’ abstract

We introduce TWIG (Tree-structured Weights with Inherited Gates), a representation in which every weight of a neural network is the end of a path of small discrete decisions: a sign, a shift by a power of two, a zero gate, an index into a shared table. Weights that belong together share the upper part of their paths, and each decision is inherited by every weight below it, so it is stored once and applied once. This simple change has three consequences. Any trained network can be written as a TWIG, and when the decisions are powers of two its weight layers become circuits made almost entirely of wires and adders, suited to chips whose weights are fixed at fabrication. Pruning, quantization, low-rank factorization, codebooks and weight sharing become edits of one object, so a single optimizer can choose among all of them for a whole network. And choosing the decisions is the ground-state problem of a higher-order Boltzmann machine whose interactions follow the paths of the tree, the problem class that annealers and quantum optimizers are built to solve. Today these questions are handled apart: each compression method brings its own format and solver, a circuit with fixed weights needs a dedicated constant multiplier for every weight, and discrete solvers reach only narrow subproblems such as rounding. Weight formats have long been moving toward shared decisions, through group scales, shared exponents, microexponents and sparse weights; TWIG takes this trend to its end, and every common format is a shallow TWIG at no extra cost. On five weight matrices of a large language model, a flat tree whose signed power-of-two terms are chosen per weight for circuit cost, with no group scales, needs 9--15\% fewer additions than GPTQ at equal layer error at 3- and 4-bit accuracy on typical matrices, and 20--55\% fewer on matrices with strong outliers.