PaperlayerView exact revision on arXiv

Source-linked AI summary

OrBIT: Structure-Guided Embedding Compression

Yunied Puig, Amit Kumar Jaiswal

arXiv:2610.10385v1cs.LG

TL;DR

Embedding tables are a major memory cost, while most compression methods choose a coding geometry before optimization. OrBIT discovers reusable orbit structure to guide shared-codeword compression and reports compression up to 37.9× on GPT-2 and 23.9× on each 7B table at T=7.

  • Problem

    Embedding tables are a major memory cost, while existing methods typically impose coordinate-block, low-dimensional-subspace, or unrestricted-codebook geometry before optimization.

    Source: §1 · p. 1

  • Method

    OrBIT learns orbit scaffolds from anchor sets to constrain shared additive codewords, glues overlapping chart representations, and compiles the orbit machinery into a finite decoder.

    Source: §1 · pp. 1–2

  • Results

    At T=7, OrBIT compresses GPT-2 by 37.9× and each 7B embedding table by 23.9×, with lower distortion than displayed PQ-q8/OPQ-q8 points on three of four tables.

    Source: §4 · pp. 7–8

  • Takeaways & Limitations

    Across all 16 model–chart comparisons, orbit scaffolds outperform every one of 20 Gaussian draws at fixed rank, showing gains not explained by subspace dimension alone.

    Source: §4 · p. 8

    The analysis assumes unit-gain normalization and canonical A-tight gluing.

    Source: §3 · p. 6

Abstract

from arXiv · show

Embedding tables are among the largest components of modern language models. Most compression methods fix a coding geometry such as coordinate blocks, low-rank subspaces, or unrestricted codebooks, and optimize within it. We instead ask whether the coding geometry can itself be discovered. We introduce \emph{OrBIT}, a structure-guided embedding compression framework that learns reusable local geometry from orbit dynamics and uses it to constrain a small set of shared codewords. The global reconstruction residual then decides where the fixed coding budget is spent, while redundant overlapping charts let local errors compensate one another after gluing. Our theory shows how tight-chart geometry controls distortion, how the global residual directs sequential allocation, and how data-geometry-guided refinement improves the codec. The resulting orbit machinery is compiled away, leaving a compact decoder in which the learned structure governs what is stored, where capacity is allocated, and how local information is assembled globally. Across four LLM embedding tables, OrBIT achieves $37.9\times$ compression on GPT-2 and over $23\times$ on each 7B table relative to 16-bit storage, while delivering competitive rate-distortion performance against established quantization and low-rank baselines.

1 INTRODUCTION

Embedding compression usually fixes a coding geometry before optimization; OrBIT instead discovers reusable local geometry from orbit dynamics and coordinates it through overlapping charts. Its local-to-global design uses residuals to direct capacity and redundant synthesis to assemble representations.

Motivation and contribution

  • OrBIT replaces fixed coding geometries with anchor-generated orbit structure that constrains shared codewords and coordinates local representations through overlapping charts.The global residual orders the fixed stage budget and determines each stage target; redundant synthesis allows cross-chart error repair.Source: §1 · p. 1
  • The orbit machinery constructs shared continuous objects rather than directly coding each token, enabling those objects to be amortized across the vocabulary.The finite decoder compiles away the orbit machinery.Source: §1 · p. 2

Contributions

  • OrBIT analyzes surviving local error, derives residual-directed targets for construction and refinement, and accounts for the objects retained by its finite decoder.The experiments distinguish data alignment, refinement, redundancy, and compilation effects.Source: §1 · p. 2

2 RELATED WORK

OrBIT draws on established quantization, shared-codeword, sparse-coding, and frame-reconstruction ideas, combining them with orbit-structured shared compression and overlapping charts.

Quantization and compositional codes

Related methods

  • Compositional codes, hashing, subspace methods, tensor factorization, sparse coding, and dictionary learning offer other ways to share parameters or learn reusable atoms [Chen et al., 2018; Tito Svenstrup et al., 2017; Jaiswal & Liu, 2023; Hrinchuk et al., 2020; Olshausen & Field, 1997; Aharon et al., 2006].OrBIT inherits wrapped shifts, exact block interpolation, and CCDS realization from Puig (2026), applying them to shared compression codewords.Source: §2 · p. 2

Frame representations

  • OrBIT couples local shared-codebook representations with canonical tight-frame synthesis, identifying the local error component removed by synthesis.Its transmitted representation retains charts, shared codewords, and LT token indices, while construction state is discarded; Equation (15) accounts for their storage.Source: §2 · p. 2

3 ORBIT-STRUCTURED ADDITIVE COMPRESSION AND FRAME GLUING

OrBIT constructs shared additive codewords in anchor-generated orbit scaffolds, places them on overlapping charts, and synthesizes a global decoder. Its analysis connects local approximation, residual-directed allocation, and post-gluing refinement to the resulting global reconstruction error.

Orbit scaffold construction

  • A small anchor subset generates a wrapped-shift orbit dictionary and scaffold, which is accepted only when it captures the full local table.Exact block interpolants determine the orbit construction, while acceptance on the local table ensures the scaffold controls the full-table projection bottleneck.Source: §3 · p. 3

Orbit realization and compilation

  • CCDS sparsely realizes a prototype’s component captured by the orbit scaffold; OMP can replace it without changing the local-to-global architecture.Orbit realizations are compiled into finite-bit chart coordinates, and this same map is used for codewords created during allocation or refinement.Source: §3 · p. 3

Error decomposition

  • The global error decomposition separates local approximation, compilation, and inconsistency, with canonical synthesis removing the inconsistency component.This makes the error surviving global gluing the relevant construction objective.Source: §3 · p. 4

Redundant frame gluing

  • Canonical tight-frame synthesis removes the local reconstruction-error component outside the range of the global analysis map, distinguishing redundant overlapping charts from nonredundant product-code geometry.For redundant A-tight charts, canonical gluing removes the component outside Ran R_D; coordinate projections with concatenation give the product-code special case.Source: §3 · p. 4

Residual-directed allocation

  • At each allocation step, the compiled global residual selects the eligible chart with the largest visible residual component and supplies that chart’s target.Each token selects among the resulting actual compiled codewords; later targets account for prior stages across charts.Source: §3 · pp. 4–5

Compiled decoder and storage

  • The decoder amortizes shared codeword coordinates and metadata across tokens, whose token-specific storage consists of LT discrete indices.Orbit construction objects are encoder-side and discarded after compilation; the decoder retains the shared representation map, chart system, quantized codeword coordinates, scales, metadata, and token indices.Source: §3 · pp. 5–6

Post-gluing refinement

  • Post-gluing refinement fits each codeword to the residual of the current global reconstruction while constraining corrections to the learned orbit geometry.The analysis assumes unit-gain normalization and canonical A-tight gluing; with remaining decoder state and assignments fixed, a sufficiently well-captured correction strictly decreases global reconstruction error.Source: §3 · p. 6

Refinement error characterization

  • Cross-chart scaffold compatibility controls aggregate stagewise refinement scaffold error by the original table’s scaffold projection error.When the stored codeword already lies in its scaffold, only the residual contribution remains.Source: §3 · pp. 6–7

4 EXPERIMENTS

Across four embedding tables, OrBIT shows a competitive end-to-end rate–distortion tradeoff and ablations examine learned geometry, refinement, redundancy, and compilation.

4 EXPERIMENTS

  • The evaluation covers GPT-2 and three 7B embedding tables, comparing OrBIT with quantization and truncated-SVD baselines under shared storage accounting.The reported primary distortion is relative reconstruction error in the original embedding space, including representation truncation and coding error.Source: §4 · p. 7
  • 37.9× on GPT-2 and 23.9× on each 7B table; OrBIT beats AQ-q8 on three tables and approximately matches its distortion at lower rate on Mistral-7B-Instruct.At the displayed operating points, OrBIT also has lower distortion than PQ-q8 and OPQ-q8 on the first three tables, while both product quantizers attain lower distortion on Mistral-7B-Instruct.Source: §4 · pp. 7–8, Table 1 · p. 8
  • At matched rank, orbit scaffolds reduce relative projection error versus Gaussian subspaces on all four tables, outperforming all 20 draws in each of 16 model–chart comparisons.Average residuals are 0.4775 versus 0.5011 on GPT-2, 0.4762 versus 0.4994 on Llama-2-7B, 0.4741 versus 0.4993 on Mistral-7B, and 0.4731 versus 0.4993 on Mistral-7B-Instruct.Source: §4 · p. 8
  • At fixed rate, gluing-aware refinement lowers weighted PCA-space error by 2.8–4.1% across models, with no added decoder bits.Of 280 proposed updates, 265 were accepted for GPT-2 and all 280 for each 7B run.Source: §4 · p. 8, Table 2 · p. 9
  • At matched chart-stage budget, redundant gluing lowers global PCA-space error on three 7B models, but GPT-2 sees essentially no net improvement despite over 98% cancellation.The measured global error matches the theoretical identity to approximately 10^-9 or better in every redundancy run.Source: §4 · p. 9, Table 3 · p. 9
  • Across the experiments, OrBIT improves over AQ at codec level, while matched-rate refinement and scaffold diagnostics support the roles of learned geometry and the globally glued objective.Redundant synthesis shows data-dependent net benefit; compilation removes orbit-construction state while reproducing the transmitted decoder output.Source: §4 · pp. 9–10

REPRODUCIBILITY STATEMENT

The paper reports that its proofs, construction procedures, experimental protocol, hyperparameters, and storage accounting are documented in the paper and appendix.

REPRODUCIBILITY STATEMENT

  • Complete proofs of the theoretical results are provided in the appendix.The construction, experimental protocol, hyperparameters, and storage accounting are also reported in the paper and appendix.Source: REPRODUCIBILITY STATEMENT · p. 10

ETHICS STATEMENT

The work studies embedding compression using existing pretrained language models, without human subjects or personal or sensitive data. The tight-frame constant is interpreted as redundancy only after chart maps are normalized to unit gain.

ETHICS STATEMENT

  • The experiments use existing pretrained language models and do not involve human subjects or personal or sensitive data.They study compression mechanisms rather than downstream deployment or decision-making.Source: ETHICS STATEMENT · p. 10
  • The authors report no specific ethical risks beyond those already associated with the underlying models.Source: ETHICS STATEMENT · p. 10

A NORMALIZATION AND INTERPRETATION OF THE TIGHT-FRAME CONSTANT

B FINITE-DIMENSIONAL ENCODER AND IMPLEMENTATION DETAILS

The appendix specifies how OrBIT constructs orbit scaffolds and shared codewords, compiles them into a finite decoder, and refines them against global reconstruction. It also outlines the additional experiments that diagnose the mechanisms and seed stability.

B FINITE-DIMENSIONAL ENCODER AND IMPLEMENTATION DETAILS

  • The finite-table codec uses local embeddings as inputs and targets; it learns no predictor for unseen inputs.Orbit dictionaries realize shared codeword prototypes, rather than encoding tokens directly with tokenwise CCDS.Source: B FINITE-DIMENSIONAL ENCODER AND… · p. 11
  • Boundary full CCDS selects independent dictionary innovations and stops at a relative residual of 10^-2, the support cap, or when no further innovation is available.The resulting sparse realization is compiled using 8-bit codeword coordinates and a 16-bit scale.Source: B FINITE-DIMENSIONAL ENCODER AND… · pp. 12, 14
  • The shared PCA representation is fitted on 10,000 sampled rows, while four charts use cyclic windows covering each ambient coordinate twice.The PCA mean and loading matrix are included in the reported rates.Source: B FINITE-DIMENSIONAL ENCODER AND… · p. 12
  • Anchor sets are built by farthest-point sampling, then partitioned so orbit representatives within each block are numerically independent.Partitions are refined until each block has at most ⌈Mℓ/3⌉ anchors.Source: B FINITE-DIMENSIONAL ENCODER AND… · p. 13
  • Shift optimization changes orbit-dictionary geometry and conditioning, but exact interpolation keeps the scaffold subspace fixed to the anchor-target span.After learning the shift, depths are recomputed and block interpolation residuals are checked.Source: B FINITE-DIMENSIONAL ENCODER AND… · p. 13
  • Scaffold acceptance is based on projection error over the complete local table, using a 10^-3 threshold; unsuccessful candidates are rejected.The encoder evaluates candidates in seeded order and retains the first that meets the criterion.Source: B FINITE-DIMENSIONAL ENCODER AND… · p. 13

C ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS

B FINITE-DIMENSIONAL ENCODER AND IMPLEMENTATION DETAILS

  • OrBIT’s encoder learns a representation and chart system, discovers orbit scaffolds, builds nested shared codebooks, refines them against globally glued reconstruction, and retains only the compiled decoder.All assignments, residual updates, refinement, and distortion measurements use compiled codewords.Source: B FINITE-DIMENSIONAL ENCODER AND… · p. 14

C.1 COMMON PROTOCOL AND IMPLEMENTATION CHECKS

The common protocol compresses reduced embedding tables with a fixed chart and codebook configuration, reports complete compiled rates, and verifies chart properties numerically. Baselines are also re-priced under matched shared-codeword precision.

C.1 COMMON PROTOCOL AND IMPLEMENTATION CHECKS

  • The protocol extracts 12,000 embeddings per model and compresses tables reduced to 64 dimensions for GPT-2 and 192 for the 7B models.The shared representation-map storage is included in every reported rate.Source: §C.1 · p. 14
  • Standard OrBIT uses four A = 2 tight charts and retains the first scaffold passing full-table acceptance.Anchor budgets are 0.75% for GPT-2 and 1.2% for 7B tables; at these budgets, accepted scaffolds attain full chart rank.Source: §C.1 · pp. 14–15
  • The standard compiled codec uses seven additive stages, 32 codewords per chart-stage pair, 5-bit token indices, and quantized shared codewords.The reported rate includes the representation map, chart description, codewords and scales, metadata, and token indices.Source: §C.1 · p. 15
  • Table 4 summarizes the standard OrBIT configuration used in Experiments 1–3 and 5 and as the headline configuration in Experiment 7.Its anchor fraction is measured against the 10,000-token table, and its rate includes the shared representation map.Source: §C.1 · p. 15, Table 4 · p. 15
  • Standard A = 2 chart systems are numerically certified, with observed deviations from unit gain and tightness on the order of 10^-8.The frame-trace estimate of A agrees with 2 to numerical precision.Source: §C.1 · p. 15
  • PQ, OPQ, and AQ are also compared using OrBIT’s 8-bit-coordinate and 16-bit-scale convention, with reconstruction recomputed after quantization.This matched-precision comparison avoids attributing gains merely to cheaper shared-codeword storage.Source: §C.1 · p. 15

C.2 EXPERIMENT 1: ADDITIONAL RATE–DISTORTION DETAILS

The section compares OrBIT with additive and product-quantization baselines, including matched-precision codewords. The comparisons show where OrBIT improves rate–distortion performance and where it does not.

C.2 EXPERIMENT 1: ADDITIONAL RATE–DISTORTION DETAILS

  • The OrBIT curve uses progressively decoded additive stages, making each point an actual truncated compiled decoder; it is empirically monotone on all four tables, not guaranteed to be so.Figure 1 plots rate in bits per token against relative reconstruction error in the original embedding space; lower is better on both axes.Source: §C.2 · p. 15, Figure 1 · p. 16
  • The OrBIT–AQ comparison tests the full structured codec end-to-end, not the orbit constraint alone, because charting, residual allocation, and gluing also differ.Matched q8 baselines quantize shared codewords using the same 8-bit-coordinate and 16-bit-scale convention as OrBIT, so the comparisons are not explained simply by cheaper precision for OrBIT's continuous objects.Source: §C.2 · pp. 16–17
  • OrBIT is strictly better in both rate and distortion than AQ-q8 on GPT-2, Llama-2-7B, and Mistral-7B; on Mistral-7B-Instruct, distortion is tied and rate is about 5.9% lower.At matched q8 accounting, OrBIT and AQ-q8 give 324.15/0.7449 versus 331.88/0.7582 bits/token / relative error on GPT-2; the cited passage reports the corresponding pairs for the other tables.Source: §C.2 · p. 16
  • At representative q8 operating points, OrBIT has lower distortion than PQ-q8 and OPQ-q8 on three tables, while both product-quantization baselines have lower distortion on Mistral-7B-Instruct.The comparisons are at nearby rates; the passage cautions that results do not establish universal dominance.Source: §C.2 · pp. 16–17

C.3 EXPERIMENT 2: LEARNED ORBIT GEOMETRY VERSUS A RANK-MATCHED GAUSSIAN CONTROL

The experiments test whether orbit-derived geometry aligns better with embedding tables than rank-matched random subspaces, and whether refinement improves the globally glued reconstruction at fixed rate.

C.3 EXPERIMENT 2: LEARNED ORBIT GEOMETRY VERSUS A RANK-MATCHED GAUSSIAN CONTROL

  • The Gaussian controls concentrate near the expected root-residual scale of 0.5, calibrating them as the intended rank-matched unstructured null.This follows from r/Mℓ = 0.75 and expected squared unexplained energy of 0.25.Source: §C.3 · p. 17
  • In all 16 model–chart pairs, the orbit scaffold has lower projection error than the best of 20 Gaussian controls, beating all 320 rank-matched random draws.The table compares rank r = 0.75Mℓ scaffolds on the complete local table; lower relative projection error is better.Source: §C.3 · p. 17, Table 5 · p. 18
  • Using less than 1% of the table as anchors, orbit geometry leaves about 9%–10% less unexplained energy than rank-matched random geometry across architectures and charts.At rank 0.75Mℓ, arbitrary subspaces capture approximately 75% of squared energy by dimensionality alone; the orbit construction places those dimensions more effectively.Source: §C.3 · p. 18

C.4 EXPERIMENT 3: GLUING-AWARE REFINEMENT

  • Post-gluing refinement improves every model at identical bitrate, and the global residual enables correction of additional error without spending additional bits.The table reports both the reduced-space objective optimized by refinement and final error after lifting to the original embedding space.Source: §C.4 · pp. 18–19, Table 6 · p. 18

C.5 EXPERIMENT 4: MATCHED-CAPACITY REDUNDANCY AUDIT

The redundancy audit measures error cancellation under matched capacity, while the compilation audit checks whether construction state is needed for decoding.

C.5 EXPERIMENT 4: MATCHED-CAPACITY REDUNDANCY AUDIT

  • At identical bitrate, canonical synthesis removes 77.48%–98.85% of accumulated local error at A = 2 and 87.04%–99.43% at A = 3, while A = 1 has numerically zero inconsistency.The three systems use the same number of chart-stage codebooks and identical bitrate within each model.Source: §C.5 · p. 19
  • Cancellation does not guarantee a lower final residual because redundancy can increase aggregate local error; GPT-2's residual is essentially unchanged despite cancellation above 98%.For the larger tables, the best redundant configuration lowers reduced-space global residual by approximately 2.4% on Llama-2-7B, 4.1% on Mistral-7B, and 3.9% on Mistral-7B-Instruct.Source: §C.5 · p. 19
  • Across all twelve runs, the measured global residual matches the local-error/cancellation decomposition to within an absolute discrepancy below 4 × 10^-9.The audit therefore verifies both cancellation and its quantitative accounting.Source: §C.5 · p. 19

C.6 EXPERIMENT 5: COMPILATION AND DECODER-ONLY AUDIT

  • Decoder-only reconstruction matches the pre-discard reconstruction exactly at reported numerical precision, although the deployed decoder omits orbit dictionaries, anchors, and construction state.The compiled payload alone reproduces every model's reconstruction; the table contrasts explicit retention of construction state with the compiled payload.Source: §C.6 · p. 20, Table 8 · p. 20

C.7 EXPERIMENT 6: ANCHOR-BUDGET AND SCAFFOLD-RANK DIAGNOSTIC

The diagnostics examine the anchor counts needed for accepted scaffolds and the stability of the headline codec across independent runs.

C.7 EXPERIMENT 6: ANCHOR-BUDGET AND SCAFFOLD-RANK DIAGNOSTIC

  • All 96-dimensional charts fail acceptance below the dimensional threshold, while at 100 anchors every chart reaches rank 96 with projection error at the 10^-7–10^-8 scale.Increasing the budget to 120 anchors preserves this regime.Source: §C.7 · p. 20
  • Every tested GPT-2 scaffold is full rank and accepted from the smallest tested budget of 50 anchors, or 0.5% of the table, with projection error at the 10^-7 scale.GPT-2 charts have dimension 32, so this smallest tested budget is already above the dimensional threshold.Source: §C.7 · p. 20
  • The diagnostic indicates that accepted-scaffold data requirements track local chart dimension more than embedding-table size, and the production anchor budgets exceed tested success thresholds.GPT-2 succeeds at 0.5% although the main experiments use 0.75%; the three 96-dimensional models succeed at 1.0% although main experiments use 1.2%.Source: §C.7 · p. 21

C.8 EXPERIMENT 7: THREE-SEED ROBUSTNESS OF THE HEADLINE CONFIGURATION

  • Across three seeds, end-to-end relative-error standard deviation is about 3.1 × 10^-4 for GPT-2 and 1.0 × 10^-3–1.6 × 10^-3 for 7B tables, below 0.2% of each mean.The codecs and transmitted rates are fixed across seeds; nearest-neighbor recall@10 varies most, without corresponding instability in reconstruction error or cosine fidelity.Source: §C.8 · p. 21
  • The seed study reproduces the headline behavior across independently reconstructed orbit geometries, including lower projection error than rank-matched Gaussian controls and stable final compressed operating points.The passage also summarizes fixed-rate refinement, redundancy cancellation, exact compilation, and scaffold recovery near the dimensional threshold.Source: §C.8 · p. 22

D PROOFS OF THE MAIN RESULTS

The proofs connect local chart updates to global reconstruction error by identifying the residual target for each stage. For post-gluing refinement, the stage’s useful improvement depends on how well its constrained realization approximates that target.

D PROOFS OF THE MAIN RESULTS

  • Post-gluing refinement targets the residual after every decoder contribution except the stage being updated has been removed; the stage’s approximation to that target determines its possible improvement.The refinement identity separates a stage-independent error from the part controlled by the replacement stage.Source: D PROOFS OF THE MAIN RESULTS · pp. 23–24
  • The unconstrained replacement codeword is the weighted centroid of the post-gluing chart target for tokens assigned to the current codeword.The assignments and remaining codewords are held fixed while deriving this target.Source: D PROOFS OF THE MAIN RESULTS · pp. 24–26
  • The actual update constrains the target through the learned scaffold, orbit realization, and finite-bit compilation, with the resulting bound tracking each approximation error.The three error terms are scaffold, orbit, and compilation deviations.Source: D PROOFS OF THE MAIN RESULTS · pp. 25–26
Loading 2610.10385v1…