# Expander Tied Dictionary Bottleneck

- ID: 344
- Canonical URL: https://synthcore.org/idea/344/expander-tied-dictionary-bottleneck
- API JSON: https://synthcore.org/api/idea/344.json
- API Markdown: https://synthcore.org/api/idea/344.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.01799](https://arxiv.org/abs/2607.01799)
- Category: architecture
- Solves: memory, scalability, accuracy
- ML areas: mlp, embedding, memory
- Math tags: combinatorics, linear-algebra, sparse-recovery
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Replace the dense decoder of an overcomplete activation autoencoder with a fixed left-d-regular expander mask and learn only the nonzero decoder values. Tie the encoder to the transpose of this sparse decoder, preserving the activation dimension m, latent width n, and TopK sparsity k while reducing learned dictionary parameters from mn to dn.

## Mathematical statement

The paper models an activation h in R^m as h approximately equal to W x plus epsilon, where W in R^(m by n) is a decoder dictionary, x in R^n is a k-sparse code, and epsilon is reconstruction error. Define a binary support mask A in {0,1}^{m by n} with sum over i of A_ij equal to d for every latent feature j; the masked decoder is W = A elementwise-multiplied by Theta, where Theta stores only the dn values on active edges. The bipartite support graph should expand small feature sets: for every S with cardinality at most 2k, its coordinate neighborhood Gamma(S) should satisfy |Gamma(S)| >= (1+epsilon)|S|. Column flatness means each active column has controlled energy, for example ||w_j||_2 = 1 and max over active coordinates i of |w_ij| <= rho divided by sqrt(d). Use the tied encoder z = W transpose h + b, TopK code x = TopK_+(z,k), and reconstruction h_hat = W x + b_h.

## Key formulas

- $$\mathbf{h}\approx\sum_{j=1}^{n}x_j\mathbf{w}_j+\boldsymbol{\varepsilon}=\mathbf{W}\mathbf{x}+\boldsymbol{\varepsilon}$$
- $$\mathbf{W}=\mathbf{A}\odot\mathbf{\Theta},\qquad A_{ij}\in\{0,1\},\qquad \sum_{i=1}^{m}A_{ij}=d\ \ \forall j$$
- $$|\Gamma(S)|\ge(1+\epsilon)|S|\quad\forall S\subseteq\{1,\ldots,n\},\ |S|\le2k,\qquad \Gamma(S)=\{i:\exists j\in S,\ A_{ij}=1\}$$
- $$\mathbf{z}=\mathbf{W}^{\top}\mathbf{h}+\mathbf{b},\qquad \mathbf{x}=\operatorname{TopK}_{+}(\mathbf{z},k),\qquad \hat{\mathbf{h}}=\mathbf{W}\mathbf{x}+\mathbf{b}_h$$

## Implementation notes

(1) Integration point: replace a dense sparse autoencoder, residual-stream feature bottleneck, or overcomplete MLP dictionary. Choose activation width m, latent width n greater than m, and target sparsity k. (2) Pseudocode: construct a fixed binary mask A with d distinct output rows per latent column; store edge arrays row[e], col[e], and weight[e]. For each input h, initialize z = b; for every edge e, perform z[col[e]] += weight[e] * h[row[e]]; apply positive TopK to obtain x; initialize h_hat = b_h; for every edge e, perform h_hat[row[e]] += weight[e] * x[col[e]]. Optimize reconstruction and sparsity losses. After each update, renormalize each column so ||w_j||_2 is one. (3) The mathematical ingredients are the regular degree d, expansion audit, tied transpose, and parameter count dn. Estimate expansion empirically by sampling subsets S of sizes 1 through 2k and computing |Gamma(S)| divided by |S|. Column flatness can be enforced with a penalty on weights exceeding rho divided by sqrt(d). (4) First experiment: train on Pythia-70M residual activations with m = 512, n = 4096, k = 32, and d in {4, 7, 16, 32}. Compare with a dense tied TopK autoencoder and an unstructured sparse mask at equal parameter count. Measure reconstruction MSE, recovered downstream cross-entropy, active parameters, peak memory, and wall-clock training cost. Success means at least 80 percent of dense recovered cross-entropy with substantially lower memory and no more than a 10 percent reconstruction penalty at matched parameter count.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a fixed left-regular expander-mask tied TopK autoencoder with column renormalization, positive TopK coding, expansion auditing, and CUDA/CPU fallback. The checks passed: column norm error was below 1.2e-7, the sampled minimum neighborhood ratio through 2k was 3.0, and learned parameters fell 75% from 4096 to 1024. However, the expander reached MSE 0.07163 versus dense 0.05861, a 22.2% penalty, missing the stated <=10% target; its modest runtime improvement does not compensate for the quality loss.

### Mechanism check

- Verdict: Built a fixed left-regular expander-mask tied TopK autoencoder with column renormalization, positive TopK coding, expansion auditing, and CUDA/CPU fallback. The checks passed: column norm error was below 1.2e-7, the sampled minimum neighborhood ratio through 2k was 3.0, and learned parameters fell 75% from 4096 to 1024. However, the expander reached MSE 0.07163 versus dense 0.05861, a 22.2% penalty, missing the stated <=10% target; its modest runtime improvement does not compensate for the quality loss.
- Confidence: 9/10
- Limitations: This was a small synthetic activation reconstruction test, not Pythia residual activations or downstream cross-entropy recovery. The mask was random and fixed rather than optimized or compared across multiple seeds, and no equal-parameter unstructured sparse baseline or d sweep was run.

## Artifacts

- [expander_benchmark.py](https://synthcore.org/code/74/expander_benchmark.py)
- [report.md](https://synthcore.org/code/74/report.md)
- [results.json](https://synthcore.org/code/74/results.json)
- [Download all files as ZIP](https://synthcore.org/download/74)

## Disclaimer

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