# Reversible Mealy Token Mixer

- ID: 504
- Canonical URL: https://synthcore.org/idea/504/reversible-mealy-token-mixer
- API JSON: https://synthcore.org/api/idea/504.json
- API Markdown: https://synthcore.org/api/idea/504.md
- Verification status: beats_baseline
- Source: [arXiv:2607.06942](https://arxiv.org/abs/2607.06942)
- Category: architecture
- Solves: stability, memory, scalability
- ML areas: ssm, transformer, memory, training
- Math tags: dynamical-systems, probability, combinatorics, algebra
- Ratings: usefulness 6/10; difficulty 5/10; novelty 8/10

## Idea description

Replace a recurrent token-mixing operation with a finite-state carrier scan over binary or quantized token features. The local transition table is constrained to conserve a scalar token weight and to be bijective, making the mixer reversible, constant-memory, and less prone to activation drift than a generic recurrent layer.

## Mathematical statement

The paper defines a Mealy automaton \(\mathscr A=(Q,S,\varphi,\psi)\), where \(Q\) is a finite carrier-state set, \(S\) is the input/output alphabet, \(\varphi:Q\times S\to Q\) updates the carrier, and \(\psi:Q\times S\to S\) emits the transformed symbol. Particle preservation is the exact local conservation law from Definition II.1, \(w(q)+w(s)=w(\varphi(q,s))+w(\psi(q,s))\), where \(w\) assigns a scalar weight to carrier states and symbols and is nonconstant on \(S\). For binary symbols, the paper notes that one may normalize \(w(s)=s\), so the constraint becomes \(w(q)+s=w(\varphi(q,s))+\psi(q,s)\). On a bi-infinite sequence \(\eta\in\{0,1\}^{\mathbb Z}\), the carrier state entering position \(n\) is defined by the stabilized left scan \(Q_n=\lim_{k\to\infty}\varphi(q;\eta_{n-k}\eta_{n-k+1}\cdots\eta_n)\), provided the limit exists and is independent of the initial carrier \(q\). The induced sequence map is \((T_{\mathscr A}(\eta))_n=\psi(Q_{n-1},\eta_n)\). We adapt this to finite sequences by initializing \(Q_0=q_0\), scanning left to right, and enforcing bijectivity of the pair map \((q,s)\mapsto(\varphi(q,s),\psi(q,s))\) over \(Q\times S\). The conservation law guarantees exact preservation of total symbol-plus-carrier weight, while bijectivity supplies an inverse scan for reversible training or checkpoint-free backpropagation. As an optional invariant-statistics diagnostic, estimate input pair frequencies \(\hat P_{ab}\) and output pair frequencies \(\hat P'_{ab}\), and penalize \(\|\hat P'-\hat P\|_2^2\).

## Key formulas

- $$w(q)+w(s)=w(\varphi(q,s))+w(\psi(q,s)),$$
- $$w(q)+s=w(\varphi(q,s))+\psi(q,s)\qquad (S=\{0,1\}),$$
- $$Q_n=\lim_{k\to\infty}\varphi\bigl(q;\eta_{n-k}\eta_{n-k+1}\cdots\eta_n\bigr),$$
- $$\bigl(T_{\mathscr A}(\eta)\bigr)_n=\psi(Q_{n-1},\eta_n).$$

## Implementation notes

1. Integration point: insert the mixer after a token projection and before the feed-forward sublayer in a small Transformer, or use it as a standalone SSM-like residual branch. Quantize one feature channel per token to \(s_n\in\{0,1\}\) using a straight-through threshold, or use several independent binary channels. Use \(Q=\{0,\ldots,K-1\}\), initially \(K=3\), matching the paper's automata. 2. Construct a lookup table containing \((\varphi(q,s),\psi(q,s))\) for every \((q,s)\). Enumerate candidate tables offline and retain only tables for which the pair map is bijective and there exist carrier weights \(c_q\) satisfying \(c_q+s=c_{\varphi(q,s)}+\psi(q,s)\). During an initial experiment, select one valid table randomly or learn a soft mixture over valid tables with Gumbel-softmax, then project to the nearest valid table after each epoch. 3. Forward pseudocode: set \(q=q_0\); for \(n=1,\ldots,L\), read \(s=s_n\), set \((q_{new},y_n)=table[q,s]\), optionally add a learned embedding \(e_{q,s}\) to the continuous token vector, then set \(q=q_{new}\). Return the residual output \(x_n+W_o e_{q_{n-1},s_n}\). For reverse-mode memory savings, reconstruct the previous pair by applying the inverse lookup table while scanning from the final carrier state. 4. Compute from the paper's mathematics: exact local conservation and inverse-table validity. Estimate empirically: output mean, pair-frequency drift, gradient norm, and language-model loss. Add \(\lambda\|\hat P'-\hat P\|_2^2\) only if statistics drift significantly; \(\hat P_{ab}\) is the minibatch frequency of adjacent binary pairs \((a,b)\). 5. First experiment: compare a one-layer 3-state mixer against a GRU with matched hidden-state size and against a depthwise-convolution token mixer on TinyStories or CIFAR-10 sequence patches. Measure validation loss or accuracy, peak activation memory, gradient explosions, and throughput for sequence lengths 512, 2K, and 8K. A successful result is stable training without gradient clipping, lower memory than the GRU, and equal or better loss at matched parameters; for language modeling, also test whether the reversible scan permits at least 1.5x longer sequences at fixed memory.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built a reversible 3-state Mealy mixer using the paper’s BBS-C(2) transition table. All six local transitions satisfy exact particle conservation and form a bijection; exhaustive inverse testing over 8,191 binary words up to length 12 passed, as did a 4,096-token random scan. The claimed constant-carrier-state property is demonstrated, but no language-model or optimization win was established.

### Mechanism check

- Verdict: Built a reversible 3-state Mealy mixer using the paper’s BBS-C(2) transition table. All six local transitions satisfy exact particle conservation and form a bijection; exhaustive inverse testing over 8,191 binary words up to length 12 passed, as did a 4,096-token random scan. The claimed constant-carrier-state property is demonstrated, but no language-model or optimization win was established.
- Confidence: 8/10
- Limitations: The test uses a fixed discrete BBS-C(2) table rather than learned continuous token features, and does not measure language-model loss, gradient behavior, checkpoint-free backpropagation, GPU throughput, peak allocator memory, or matched-parameter training. The NumPy scan is a correctness prototype, not an optimized production mixer; the GRU activation comparison is a simple per-token output proxy rather than instrumented autograd memory.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0163
- Paired wins: 7/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/1360/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/1360/bench_report.json)
- [experiment.py](https://synthcore.org/code/1360/experiment.py)
- [report.md](https://synthcore.org/code/1360/report.md)
- [report_bench_2026-09-04T171134.md](https://synthcore.org/code/1360/report_bench_2026-09-04T171134.md)
- [results.json](https://synthcore.org/code/1360/results.json)
- [Download all files as ZIP](https://synthcore.org/download/1360)

## Disclaimer

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