# Spectral Budgeted Embeddings

- ID: 138
- Canonical URL: https://synthcore.org/idea/138/spectral-budgeted-embeddings
- API JSON: https://synthcore.org/api/idea/138.json
- API Markdown: https://synthcore.org/api/idea/138.md
- Verification status: audited
- Source: [arXiv:2608.24592](https://arxiv.org/abs/2608.24592)
- Category: architecture
- Solves: accuracy, memory, sample-efficiency
- ML areas: embedding, transformer, mlp
- Math tags: optimization, spectral-theory, approximation-theory, statistics
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace uniform embedding dimensions with a globally budgeted allocation based on the estimated spectral complexity of each categorical feature. Tables whose category representations have large leading singular-value energy receive more dimensions, while high-cardinality tables are penalized because each extra dimension consumes more parameters.

## Mathematical statement

The model represents a categorical input using f(x;Theta)=w^T phi(x)+b, where x is an input, b is an intercept, w is the downstream linear coefficient vector, and phi(x) concatenates numerical features z(x) with category embeddings u_j(c_j(x)); c_j(x) is the category of predictor j and u_j(c) is its embedding vector. For predictor j, let sigma_{j,1} >= sigma_{j,2} >= ... >= 0 be singular values of a category-representation matrix, and let V_j=sum_k sigma_{j,k}^2 be its total spectral energy. Approximate the truncation error at dimension d_j by A_j(d_j)=V_j/d_j, or estimate A_j directly from a pilot SVD. If c_j is the parameter cost per embedding dimension, typically c_j=N_j for a table with N_j categories, the continuous allocation solves min_{d_j>0} sum_j V_j/d_j subject to sum_j c_j d_j <= B. The Lagrange multiplier calculation gives d_j=B*sqrt(V_j/c_j)/sum_l sqrt(V_l c_l). Thus the square-root rule balances approximation value against per-dimension parameter cost. The exact finite-dimensional implementation can replace V_j/d_j with the measured singular-value tail A_j(d_j)=sum_{k>d_j} sigma_{j,k}^2 and use marginal-gain greedy rounding under the same budget.

## Key formulas

- $$f(\mathbf{x};\Theta)=\mathbf{w}^{\top}\boldsymbol{\phi}(\mathbf{x})+b,$$
- $$\boldsymbol{\phi}(\mathbf{x})=\Bigl[\mathbf{z}(\mathbf{x})^{\top},\;\mathbf{u}_{1}(c_{1}(\mathbf{x}))^{\top},\;\ldots,\;\mathbf{u}_{m}(c_{m}(\mathbf{x}))^{\top}\Bigr],$$
- $$\min_{d_1,\ldots,d_m>0}\;\sum_{j=1}^{m}\frac{V_j}{d_j}\quad\text{s.t.}\quad\sum_{j=1}^{m}c_jd_j\le B,\qquad d_j^{\star}=\frac{B\sqrt{V_j/c_j}}{\sum_{\ell=1}^{m}\sqrt{V_\ell c_\ell}},$$
- $$A_j(d)=\sum_{k>d}\sigma_{j,k}^{2},\qquad \Delta_j(d)=A_j(d)-A_j(d+1)=\sigma_{j,d+1}^{2}.$$

## Implementation notes

Integrate this at model construction for every categorical embedding table, before full training. Let table j have N_j categories and maximum candidate dimension D_max. First train a cheap pilot model with all tables at D_max for a small number of steps, or initialize each table with a random or learned matrix E_j in R^{N_j x D_max}. Compute a truncated SVD E_j=U_j diag(sigma_j)V_j^T; if a pilot table is unreliable, use category-conditioned hidden-state means or target/residual statistics instead. Set c_j=N_j, or set c_j=N_j multiplied by the number of optimizer states if the budget is intended to count training memory rather than weights. Estimate V_j=sum_k sigma_{j,k}^2, then compute the continuous dimensions using d_j=B*sqrt(V_j/c_j)/sum_l sqrt(V_l c_l). Clamp each dimension to [d_min,D_max], round to integers, and repair the budget by repeatedly adding one dimension to the table with largest marginal gain sigma_{j,d_j+1}^2 per cost c_j, or removing one from the smallest such ratio. Pseudocode: inputs are E_j, N_j, B; obtain singular values; initialize d_j=max(d_min,round(B*sqrt(V_j/c_j)/Z)); while sum_j c_j d_j>B remove argmin_j sigma_{j,d_j}^2/c_j; while budget remains add argmax_j sigma_{j,d_j+1}^2/c_j; replace each embedding table by its selected-width parameter matrix and train normally. The paper-derived quantities are the spectral-tail approximation proxy, parameter budget, and square-root allocation; the pilot spectrum, minimum dimensions, and rounding policy are empirical engineering choices. Start with a small Transformer or tabular MLP on Criteo, Avazu, or a synthetic task with heterogeneous category effects. Compare uniform dimensions and common cardinality heuristics at exactly equal total embedding parameters. Success is higher validation accuracy or lower log loss at fixed parameter count, especially when tables have different category counts and spectral decay; also measure calibration and whether the pilot allocation remains stable across random seeds.

## Verification

- Status: audited
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built Spectral Budgeted Embeddings with square-root allocation, exact singular-tail greedy repair, CUDA execution, and CPU fallback. The math check selected the exhaustive integer optimum with objective 21.5083 and dimensions [4,3,4]. In the equal-budget synthetic experiment, spectral allocation [9,6,6,2,2] reduced test MSE from 0.03197 to 0.02741, a 14.3% improvement, and reduced the spectral-tail proxy from 7.1470 to 5.8331. This is promising but was demonstrated on only one synthetic seed.

### Mechanism check

- Verdict: Built Spectral Budgeted Embeddings with square-root allocation, exact singular-tail greedy repair, CUDA execution, and CPU fallback. The math check selected the exhaustive integer optimum with objective 21.5083 and dimensions [4,3,4]. In the equal-budget synthetic experiment, spectral allocation [9,6,6,2,2] reduced test MSE from 0.03197 to 0.02741, a 14.3% improvement, and reduced the spectral-tail proxy from 7.1470 to 5.8331. This is promising but was demonstrated on only one synthetic seed.
- Confidence: 7/10
- Limitations: The pilot model is trained, but the synthetic diagnostic uses known ground-truth category matrices for spectrum estimation instead of extracting spectra from learned pilot embeddings. Only one random seed and one synthetic regression task were tested; no real tabular dataset, repeated-seed confidence interval, calibration, wall-clock, or memory comparison was performed.

## Artifacts

- [report.md](https://synthcore.org/code/52/report.md)
- [report_super_2026-08-30T102404.md](https://synthcore.org/code/52/report_super_2026-08-30T102404.md)
- [results.json](https://synthcore.org/code/52/results.json)
- [spectral_budgeted_embeddings.py](https://synthcore.org/code/52/spectral_budgeted_embeddings.py)
- [supercheck_movielens.py](https://synthcore.org/code/52/supercheck_movielens.py)
- [supercheck_report.md](https://synthcore.org/code/52/supercheck_report.md)
- [supercheck_results.json](https://synthcore.org/code/52/supercheck_results.json)
- [Download all files as ZIP](https://synthcore.org/download/52)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.