Every Weight Is a Path of Shared Discrete Decisions

Ammar Ali; Stamatis Lefkimmiatis

Source-linked AI summary

Every Weight Is a Path of Shared Discrete Decisions

Ammar Ali, Stamatis Lefkimmiatis

arXiv:2610.31931v1Oct 22, 2026cs.LG

TL;DR

Neural networks are trained with real-valued weights but deployed as finite bit patterns and circuits, while compression methods and discrete optimization have largely been handled separately. TWIG represents weights as paths of shared discrete decisions and makes compression methods edits of one object. On five large-language-model weight matrices, its flat tree uses fewer additions than GPTQ at equal layer error in the reported 3- and 4-bit settings.

Problem
Training treats weights as real numbers, but deployment uses finite formats and digital circuits, while compression families have separate formats and solvers and discrete optimizers have reached only narrow tasks.
Source: §1 · p. 1
Method
TWIG represents each weight as a path of small discrete decisions, with related weights sharing inherited decisions, and treats compression methods as edits of the same tree.
Source: §1 · p. 2
Results
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.
Source: §1 · p. 3
Takeaways & Limitations
A single budgeted optimizer can choose among pruning, quantization, factorization, codebooks, and weight sharing as edits of one object.
Source: §1 · p. 3
TWIG is not the shortest possible matrix description: more compact graphs, tries, magnitude-based grouping, or entropy coding would require variable-length decoding that breaks fixed addressing.
Source: §4 · p. 12

Abstract

from arXiv · show

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.

1 Introduction

TWIG represents weights as paths of shared discrete decisions, addressing the gap between continuous training and discrete deployment and the separate formats and solvers used for compression, circuit cost, and discrete optimization. It makes common compression methods edits of one tree and reports fewer additions than GPTQ on five language-model matrices at equal layer error.

1 Introduction

TWIG addresses a gap between continuous-valued training and finite, circuit-executed deployment, where compression families otherwise bring separate formats, solvers, and kernels.The paper also identifies fixed-weight circuits’ per-weight constant multipliers and the narrow scope of prior discrete-optimizer applications such as single-layer rounding.Source: §1 · pp. 1–2
Common formats such as group scales, shared exponents, sparse weights, and shared tables already reuse decisions, but each fixes the decision type and sharing levels in advance.TWIG presents itself as extending this trend to paths with decisions shared at multiple levels.Source: §1 · p. 2
TWIG represents each weight as the product of small discrete decisions along a path, with weights that belong together sharing inherited decisions above their leaves.The decisions can include shifts by powers of two, signs, zero gates, or indices into a shared table.Source: §1 · p. 2
Pruning, quantization, factorization, codebooks, and weight sharing become edits of one object, allowing a single budgeted optimizer to choose among them for a network.The paper states that this optimizer is exact under additive costs.Source: §1 · pp. 2–3
With power-of-two decisions, a state tree maps to a circuit made almost entirely of wires and adders, connecting weight precision with circuit size.The paper also frames tree-state selection as a higher-order Boltzmann-machine ground-state problem, with interactions following tree paths.Source: §1 · p. 3
The tree representation includes current number formats as shallow special cases and preserves worst-case representability while using fewer bits when weights share structure.The paper also states that any matrix can be approximated to any precision by a sum of power-of-two trees applied with shifts and additions.Source: §1 · p. 3
A flat tree of signed power-of-two terms chosen per weight saves 9–15% of GPTQ additions at equal layer error with 3- and 4-bit accuracy on typical matrices, and 20–55% on matrices with strong outliers.Source: §1 · p. 3

2 From numbers to state trees

TWIG represents weights as products of decisions along paths, with shared decisions stored once and inherited by the weights below them. The tree can also be applied directly as a circuit, while sums, products, and references expand its expressiveness and expose storage and circuit costs.

2.1 A number is a path of decisions

In floating point, sign, exponent, and mantissa are decisions along a path, and weights with a common exponent can share that path segment.For example, the two weights share the same exponent while differing in sign and mantissa.Source: §2.1 · p. 3

2.3 Multiplying without rebuilding the weight

Three additions replace two multiplications and one addition by shifting each input at the leaves and applying the shared exponent shift to their sum.The weights themselves are never formed as numbers.Source: Figure 2 · p. 4, §2.3 · pp. 4–5

2.2 Sharing a decision at the same precision

Sharing a common exponent exactly reproduces two FP16 weights using 27 bits instead of 32; larger groups approach a 31% reduction without changing values.Several shared halving decisions also let nearby, but not identical, magnitudes share most of their paths.Source: §2.2 · p. 4

2.4 State trees in general

A state tree places matrix entries at leaves and small-alphabet decisions at nodes, where each decision is inherited by every entry below it.Shifts, zero gates, transparent states, signs, and small magnitudes provide common state types; row order affects which entries can share decisions.Source: §2.4 · pp. 5–6

2.5 Combining trees

A tree can combine sums for precision, products for low-rank or transformed matrices, and references for shared tables or dictionaries.References let the structure become a directed acyclic graph.Source: §2.5 · p. 6

2.6 Two prices: bits and additions

Each state tree has two costs: storage bits for its states and circuit additions for summing shifted inputs; sharing can save bits without saving additions.The two costs can favor different trees, and the representation permits trading one against the other.Source: §2.6 · pp. 6–7

2.7 One tree, three readings

The same tree can be read as a compression format, a circuit design, or a discrete optimization problem over state choices.The table maps each tree part to its role across these three readings.Source: §2.7 · p. 7, Table 1 · p. 7

3 What state trees can express

State trees preserve existing formats and worst-case representational capacity, while shared states, sums, rank, and references provide ways to trade storage, precision, and sharing. The section also gives guarantees for shift-and-add approximations and a LLaMA-3-8B quantization example.

3.1 Nothing is lost: today’s formats are shallow state trees

State trees represent existing formats at no greater bit cost, with common formats requiring at most five decision levels per path.Dense formats use exactly their original bit cost, and adding transparent states or enlarging alphabets preserves shallower options.Source: §3.1 · p. 8

3.2 Nothing is lost in the worst case

A tree with K leaf values represents every matrix over those values using log2 K bits per entry, and finely spaced leaves approximate any matrix to any accuracy.For unstructured matrices, state trees cost the same as flat formats; shared states can save when weights have matching structure.Source: §3.2 · p. 9

3.3 No multiplications: shifts and additions suffice

A sum of t power-of-two trees approximates every matrix to relative error 3^-t within its exponent range, using shifts and additions plus m + n genuine multiplications.Each added term divides worst-case error by three and costs one addition; integer matrices of magnitude below 2^b are represented exactly with ⌈(b + 1)/2⌉ terms per entry.Source: §3.3 · p. 9

3.4 The price of sharing

In a binary tree of shift bits, nonzero entries whose closest common node is h levels above differ in magnitude by at most 2^h.Row order therefore matters: similar magnitudes should be grouped, with richer leaves or another tree where neighboring magnitudes differ substantially.Source: §3.4 · p. 9
At 3.33 bits per weight, the LLaMA-3-8B MLP quantizer reached WikiText-2 perplexity 7.78, versus GPTQ’s 8.03 at 3.25 bits.The setup used one balanced tree per column, recursive bisection ordering, and exact dynamic programming with GPTQ-style error feedback; the edge-bit encoding produced identical weights at 3.60 bits.Source: §3.4 · p. 10

3.5 Beyond states: rank and sharing

Rank or sharing alone can describe every matrix with real-valued factors, and the three dials can trade states, rank, and sharing when factors are state trees.A rank-r sum of column-row products describes matrices of rank at most r; shared subtrees can span matrices within or across layers.Source: §3.5 · p. 10

4 Building a tree, step by step

The lossless format groups weights in their natural row order, stores each group’s largest exponent once, and represents each weight by its distance from that exponent plus its sign and mantissa. The fixed-shape tree reproduces BF16 weights exactly while reducing storage, with fixed addressing chosen over more compact but pointer-dependent representations.

Building the tree

Each row’s consecutive weights form a group, whose shared node stores the largest exponent while each weight stores its exponent distance, sign, and mantissa.The group size is 64 in the format; these groups also follow tensor-core memory order without a stored or applied permutation.Source: §4 · p. 11, Figure 5 · p. 12

Step 4: set aside the rare outliers

A 4-bit state represents exponent distances 0–14; state 15 is an escape for farther-out weights, whose exact bits go in a side list.About one weight in ten thousand needs an escape in the tested models.Source: §4 · p. 11

Step 5: count the bits

With groups of 64, the format stores whole models at 12.13 bits per weight, 24% less than BF16, while keeping every weight bit-exact.The count includes rare escapes.Source: §4 · p. 11

Step 6: decode without pointers

Fixed-width fields at fixed offsets let the decoder locate a weight from its index, reconstruct its BF16 pattern, and write it directly into tensor-core registers.The format avoids moving weights through memory in BF16.Source: §4 · p. 12, Figure 6 · p. 13

Why a tree, and not something smaller

More compact graphs, tries, magnitude-based groups, or entropy coding would use pointers, indices, or variable-length codes that break fixed addressing.The authors leave these richer representations for future work and do not claim their tree is optimal.Source: §4 · p. 12

From exact to compressed

Shortening mantissas preserves the tree’s shape but changes it from an exact representation into an approximation, illustrating compression as a tree edit.Keeping the leading three mantissa bits reduces the leaf from 8 to 4 bits.Source: §4 · p. 13

5 Compression is editing one tree

The section recasts compression methods as edits to a shared state-tree representation, then prices and selects those edits under a network-wide budget. Under additive accuracy costs, Pareto-set dynamic programming finds the best choices within the size-grid resolution; the budget can also target additions, latency, or energy.

5 Compression is editing one tree

Pruning, quantization, low-rank factorization, codebooks, and weight sharing become edits of one state-tree object, rather than separate formats.Common compression methods are combinations of edits and rules for choosing new states.Source: §5 · p. 13, §5.1 · p. 13, Table 3 · p. 14

5.1 Every method is an edit

Leaf replacement can prune a weight, shortening mantissas quantizes it, and splitting a leaf into a sum represents residual corrections and additive codebooks.Whole-matrix edits also express low rank, rotations, shared references, weight sharing, and mixed precision.Source: §5.1 · p. 13

5.2 Methods differ only in how they choose states

Methods within a compression family share a representation and differ in their state-selection rule, allowing same-family comparisons and combinations across families.A quantized low-rank factor or a pruned tree reading from a shared codebook is represented as a deeper tree.Source: §5.2 · p. 14

5.3 Pricing an edit

A single accuracy measure can price edits across methods by measuring their effect on layer outputs; correlated inputs make column errors interact, and gradient second moments capture which output directions matter.When these proxies are inadequate, the edit’s price can be measured by running the network with that edit applied.Source: §5.3 · p. 14

5.4 One choice per matrix, one budget for the network

Under additive accuracy costs, Pareto-set dynamic programming selects one edit per matrix exactly up to the size-grid resolution and is never worse than a single method or uniform setting at the same budget.For nested or disjoint candidate groups for shared subtrees, recursion over the groups also keeps the search exact.Source: §5.4 · p. 15
Additions, latency, or energy can replace bytes as the budget, allowing the optimizer to target a hardware-dependent objective.For state trees, the number of additions is a natural budget and leads to reading the tree as a circuit.Source: §5.4 · p. 15, Figure 9 · p. 16

6 From trees to circuits

With power-of-two states, TWIG turns fixed-weight layers into circuits built largely from wires and adders, while shared sums can reduce addition costs. A first comparison on five LLaMA-3-8B matrices finds fewer adders than GPTQ at equal layer error, though addition counts are only a proxy for circuit size.

6.1 A layer becomes wires and adders

For power-of-two states, each weight product becomes shifted inputs summed with adders; shifts and signs are free in fixed-weight circuits, while extra signed-power terms cost adders.Row scales and column bases are the remaining multiplications; they can be folded into neighboring layers when no residual addition or nonlinearity intervenes.Source: §6.1 · p. 16

6.2 Where the circuits pay off

Fixed-at-fabrication circuits gain most because zero digits disappear and weights with few nonzero digits need few wires; programmable hardware and software also have implementation costs.Programmable hardware uses multiplexers to select stored shifts and signs; software can replace multiplications with lookup-table reads, and the discussion assumes fixed-point activations.Source: §6.2 · p. 16

6.3 A whole network

Convolutions reuse a kernel subtree across positions, attention projections can share partial sums, and normalization operations can fold into neighboring layers.Products of two activations and some nonlinear functions remain outside the tree.Source: §6.3 · p. 17

6.4 Sharing additions, and their limit

Outputs can share adders for common shifted-input sums, but for most unstructured n × n matrices of b-bit integers, bounded-shift addition circuits require on the order of n^2b / log(nb) operations.The cited classical bucketing construction comes within a constant factor when b is not exponentially larger than n.Source: §6.4 · pp. 17–18

6.5 A first measurement

At equal layer error, flat state trees use 9–15% fewer adders than GPTQ at 3- and 4-bit accuracy on typical matrices, and up to 55% fewer at 3-bit accuracy on matrices with strong outliers.The comparison covers five LLaMA-3-8B matrices; addition counts are a first-order proxy for circuit size, not measured area.Source: Table 5 · p. 18, §6.5 · p. 18
The comparison chooses a flat signed-digit tree per weight to minimize layer error plus a price per nonzero digit, adjusting that price to match GPTQ's layer error.Both methods are costed with the same adder rule, and the tree's hardwired storage is not counted.Source: §6.5 · p. 18
The reported addition counts omit adder width, which depends on the spread of combined shifts, so they do not measure circuit area.A full whole-network circuit study, including area and energy, is left to future work.Source: §6.5 · p. 19

7 Choosing states is finding a ground state

Choosing a tree's discrete states can be expressed as finding a Boltzmann machine's lowest-energy configuration. The tree determines which units and higher-order interactions exist, while data statistics determine interaction strengths; this connects state selection to established and quantum optimization methods.

7 Choosing states is finding a ground state

Choosing tree states is a ground-state search for a higher-order Boltzmann machine, with interactions determined by data and higher-order terms following tree paths.For fixed row scales and column bases, the ground state gives the best matrix the tree can represent.Source: §7 · p. 19, §7.3 · p. 20

7.1 Boltzmann machines

A Boltzmann machine assigns energy to binary-unit configurations, and lower temperature concentrates probability on its lowest-energy configurations.Pairwise couplings and fields encode interactions among units; higher-order machines also include terms involving three or more units.Source: §7.1 · p. 19

7.2 A machine with two weights

For two correlated inputs, the layer-error term couples the two weights' rounding choices, so the best choice for one depends on the other.Adding a shared node that keeps or halves both weights introduces three-unit interactions along their paths.Source: §7.2 · pp. 19–20

7.3 The Boltzmann machine of a tree

With node states fixed, leaf units form a pairwise machine coupled through input statistics; freeing node states creates higher-order terms that follow tree paths.Auxiliary units can reduce the higher-order machine to pairwise terms.Source: §7.3 · p. 20

7.4 Familiar solvers, and new ones

Rounding ignores couplings, while GPTQ makes a single sequential pass and adaptive rounding formulates layer rounding as a QUBO.The same energy formulation also supports sampling and annealing solvers that can choose zeros, shared shifts, codebook indices, and selectors together.Source: §7.4 · pp. 20–21

7.5 Quantum optimizers

Tree-state energies can be put into Ising form for quantum optimizers, and row-and-column blocks can be sized for current devices within a classical loop.Freeing node states adds auxiliary units and penalty couplings; whether quantum solvers outperform classical ones on the many blocks remains open.Source: §7.5 · p. 21

8 Learning in the space of states

TWIG can be trained directly by relaxing discrete choices into soft state distributions and sharpening them as temperature falls. The resulting trained object already fixes its storage cost, circuit, and format.

8 Learning in the space of states

Deeper trees can be trained by assigning each alphabet a soft distribution over states and sharpening it as temperature falls, so the trained object is already the deployed one.Its storage cost, circuit, and format are fixed by the tree.Source: §8 · p. 21

9 Early evidence and directions

Selected demonstrations apply TWIG to compression, lossless storage and serving, discrete tuning, hardware design, and image coding. They report concrete gains while marking the results as examples rather than a general claim.

Compression

At 3.25 bits per weight without training, the dynamic program lowers perplexity 14–17% versus the strongest GPTQ configuration and closes 58% of GPTQ’s WikiText-2 gap to FP16.The whole-model menu combines quantization, pruning, and low-rank edits, selecting a different edit for each matrix.Source: Table 6 · p. 22, §9 · p. 23

Lossless storage

12.13 instead of 16 bits per weight preserves exact BF16 values; vLLM generation is 1.23× faster at batch size 1.At batch size 32, when serving is compute-bound, the tree runs at a speed comparable to BF16.Source: §9 · pp. 22–23

Discrete optimization

Healing changed 46,239 stored codes, about 0.004% of the model’s codes; WikiText-2 perplexity fell from 13.74 to 12.85 and GSM8K accuracy rose 7.9 points.The reported GSM8K gain comes from a single run; the passage gives an interval of about ±2 points for each accuracy.Source: §9 · pp. 23–24

Image coding

On Kodak, batched GPU decoding reaches 2.9 Gpixel/s, versus 0.45 for HTJ2K and 0.10 for JPEG 2000; JPEG XL compresses photographs better.For a single small image, GPU HTJ2K retains an advantage not shown by the batched timings.Source: Table 8 · p. 24, §9 · p. 25

Hardware

At equal layer error, tree-based circuit design needs 14–55% fewer adders than GPTQ at 3-bit accuracy and 30–63% fewer at 2-bit accuracy.Strong-outlier matrices reach the upper ends; zeros and shifts are free, and there are no group-scale multipliers.Source: §9 · p. 24

Directions

The authors propose training deep trees, compiling hardwired adder circuits, shipping sparse tree updates, extending trees to other data, and testing quantum workloads.The image-coding result is offered as evidence that the representation applies beyond neural-network weights.Source: §9 · p. 25

10 Related work

TWIG connects prior work on shared number formats, path-structured representations, multiplier-free networks, unified compression, and discrete weight optimization. Its stated novelty is a common cost model and representation that treats compression choices and state selection together.

Number formats with shared parts

Group quantization and block floating-point formats share scales or exponents, while microexponents and HiFloat4 add shared shift levels; TWIG permits any decision at any tree level.HiFloat4 reports higher accuracy than NVFP4 on several language models at the same 4.5 bits per weight [50].Source: §10 · p. 26

Path-structured representations

Path-based representations appear in decision diagrams, weighted automata, hierarchical matrices, tensor trains, and vector quantizers; TWIG applies the path structure to neural-network weights.The passage identifies TWIG’s distinguishing additions as its bits-and-additions cost model, unified compression edits, and Boltzmann-machine reading.Source: §10 · p. 26

Multiplier-free networks

Power-of-two weights, sums of such terms, and shift-and-add networks are prior multiplier-free approaches; TWIG describes these families as particular state trees.The passage states that sums of power-of-two terms lose no expressive power under Property 3.Source: §10 · p. 26

Unified and budgeted compression

Earlier frameworks combine selected compression choices, allocate speed budgets, bits, or rank, while TWIG supplies one object whose menu can contain edits from every family.The passage cites Optimal Brain Compression, SPDY, mixed-precision methods, and ROCKET [91].Source: §10 · p. 26

Discrete optimization of weights

Prior discrete-weight methods formulate rounding, quantization, or pruning as optimization problems; TWIG extends the QUBO view to all tree decisions, including shared shifts and codebook indices.The passage cites adaptive rounding, Kronecker-factored rounding, and annealing formulations [58] [82].Source: §10 · p. 26

11 Conclusion

The conclusion presents TWIG as a shared representation for discrete weight decisions, with implications for compression, circuits, and optimization. It also identifies direct training of trees as an open direction.

Motivation

The paper frames the transition from continuous training to discrete deployment as having been handled one method at a time.TWIG is proposed to make that passage explicit with a single representation.Source: §11 · pp. 26–27

Conclusion

TWIG represents each weight as a path of discrete decisions, with shared decisions stored and applied once; current formats are shallow state trees.The conclusion describes compression methods as edits of one object and state selection as a higher-order Boltzmann-machine ground-state problem.Source: §11 · p. 27

Open direction

The conclusion leaves open training trees directly, so networks could discover which decisions to share rather than imposing sharing after training.It describes this as a direction, not a demonstrated result.Source: §11 · p. 27

A Definitions, statements and proofs

The appendix sets notation and distinguishes restated known results from the statements specific to state trees.

Definitions

The appendix defines W as an m × n weight matrix, with rows as outputs and columns as inputs, and P as zero plus signed powers of two.It defines I as the set of matrix-entry indices.Source: A Definitions, statements and proofs · p. 27

Restated results

The appendix restates known results including counting bounds, non-adjacent form, reduced-rank regression, and multiple-choice knapsack.The stated purpose is to keep the paper self-contained.Source: A Definitions, statements and proofs · p. 27

State-tree statements

The appendix identifies Theorems A.9, A.10, A.14, and A.16(ii) as among the statements specific to state trees.It contrasts them with several known results restated with their sources.Source: A Definitions, statements and proofs · p. 27

A.1 Definitions

A state tree represents matrix entries through decisions assigned along root-to-leaf paths, with row scales and column bases. Its broad definition allows ancestor-dependent lookups and shared subtrees.

A.1 Definitions

Each matrix entry is associated with a leaf, and its represented value is determined by decisions along the root-to-leaf path, together with row scales and column bases.A node’s finite alphabet and value map specify its possible decisions; a value map may depend on ancestor states.Source: §A.1 · p. 27
Because node values may depend on ancestor states, a state tree can express any code decoded from the root downward.Trellis codes with overlapping, non-nested windows count as state trees only when treated as codebooks over whole blocks.Source: §A.1 · p. 27
A state-tree graph combines trees using entrywise sums, matrix products, and references; reused references denote shared subtrees.Lookup tables are also represented as shared subtrees.Source: §A.1 · p. 27
Storage cost counts the bits of active node states once per shared subtree, plus the row-scale and column-base costs.Circuit cost counts the two-input additions used to evaluate the matrix transformation; sharing partial sums can reduce it.Source: §A.1 · p. 28

A.2 What state trees express

State trees represent common weight formats and support exact or approximate matrix representations with explicit storage and precision bounds. Their structure also expresses shared shifts, rank-constrained factorization, and shared subtrees.

Existing formats

Existing formats—including floating point, scaled integers, block floating point, ternary weights, codebooks, and N:M sparsity—have state-tree representations with storage cost no greater than their original format.For several listed formats, the state-tree representation uses exactly the format’s fields.Source: §A.2 · p. 28

Refinement and sharing

Refining a tree or adding representable-zero summands preserves its represented matrices, while replacing duplicate subtrees with one reference saves the storage of the copies.Sharing restricts the represented set to assignments in which the formerly separate copies have equal states.Source: §A.2 · pp. 28–29

Representation and storage bounds

For entries drawn from a K-element set, any fixed-length encoding representing every m × n matrix needs at least mn log2 K bits.The lower bound for variable-length codes is mn log2 K − 1 bits.Source: §A.2 · p. 29
For matrices with maximum magnitude at most 1, a flat tree approximates every entry within ε using mn log2⌈1/ε⌉ bits.The stated gap from the lower bound is at most mn log2(1 + ε) + 1 bits; a power-of-two root scale extends the result to general matrices.Source: §A.2 · p. 29

Sums of shift trees

Every real value can be approximated by t signed power-of-two terms with relative error at most 3^-t, yielding shift-and-add matrix evaluation.For integer entries with |Zij| < 2^b, exact representation uses t = ⌈(b + 1)/2⌉ terms; evaluation uses shifts and additions, plus m + n multiplications for the row and column scales.Source: §A.2 · p. 29

Shared shifts

In a perfect binary tree, realizable shared-shift exponents are characterized by bounds on each leaf exponent and subtree-consistency conditions.An alternative node-bit encoding represents the same columns as the edge-bit encoding, using about 3.32 rather than 3.58 bits per weight for large m.Source: §A.2 · pp. 29–30

Rank

A sum of r outer products represents exactly the matrices of rank at most r, and rank-constrained approximation has a truncated-singular-value solution under the stated positive-definite error metric.For the general two-sided metric, the minimizer is obtained by transforming the matrix, truncating its singular values, and transforming back.Source: §A.2 · p. 30

Shared subtrees

For several matrices sharing a factor D, exact representation requires r at least the rank of their vertically stacked matrices.With two matrices and fixed factors, the shared-factor minimizer can be found by generalized eigendecompositions and entrywise division.Source: §A.2 · p. 30

A.3 Compression, circuits and Boltzmann machines

The section describes exact budgeted optimization over compression options, a tree-based Boltzmann-machine formulation, and bounds for shift-and-add circuits. Experimental details cover model compression, discrete-state healing, exact storage, and image coding.

A.3 Compression, circuits and Boltzmann machines

Dynamic programming solves the additive-cost budget problem exactly, and the shared-subtree recursion is exact when candidate shared groups are pairwise disjoint.The resulting optimum is no worse than any single method or uniform setting that fits the budget.Source: §A.3 · pp. 30–31
For almost all matrices in the stated integer range, exact shift-limited straight-line circuits require a lower-bounded instruction count; a construction uses O(N2^b/log N) additions.Convolutions reuse one kernel matrix through references to a shared subtree across shifted-position blocks.Source: §A.3 · pp. 31–32
With node states free, the tree’s error objective becomes a higher-order polynomial whose terms involve at most two root-to-leaf paths, and auxiliary units and penalties reduce it to a quadratic function.When the one-hot penalty exceeds the error range over binary assignments, ground states satisfy the constraints and decode to a minimum-error matrix in the tree’s representation.Source: §A.3 · p. 32

A.4 Experimental details

Common model evaluations use context length 2048 for perplexity and five-shot MMLU and GSM8K, with GPU measurements on an A100-SXM4-40GB.The compression pipeline computes Hessians from 128 FineWeb calibration sequences and retains the attention-sink token.Source: §A.4 · p. 32
The lossless storage scheme uses 12.133 bits per weight on disk, and every tested matrix decodes to its exact BF16 bits.At most 0.014% of weights in any layer use the 16-bit escape side list.Source: §A.4 · p. 32
The whole-model optimizer evaluates quantization, pruning, and low-rank edits alone and in combination, measuring selected plans and resolving the knapsack again until the plan is measured.The 4.25-bit run used 26.6% of FP16 bytes and took nine rounds; the 3.25-bit run used 20.3% of block-weight bytes.Source: §A.4 · pp. 32–33
After 40 healing steps, perplexities were 12.85 on WikiText-2, 19.51 on C4, and 20.02 on FineWeb.The initial run’s rebuild measured 13.74, 20.95, and 20.88 on those datasets, respectively; repeated runs differed by about 0.1.Source: §A.4 · p. 33
8.51 bits per pixel on the 41-image CLIC 2020 professional validation set, versus 7.88 for JPEG XL at effort 9, 8.81 for lossless WebP, and 11.71 for PNG.The GPU codec decoded the set at 2.86 Gpixel/s end to end and 3.46 Gpixel/s for kernels alone.Source: §A.4 · p. 33