# Selector-Driven Hierarchical Permutation Mixer

- ID: 1453
- Canonical URL: https://synthcore.org/idea/1453/selector-driven-hierarchical-permutation-mixer
- API JSON: https://synthcore.org/api/idea/1453.json
- API Markdown: https://synthcore.org/api/idea/1453.md
- Verification status: unverified
- Source: [arXiv:2607.26572](https://arxiv.org/abs/2607.26572)
- Category: architecture
- Solves: memory, speedup, scalability
- ML areas: attention, transformer, graph-nn, inference-speedup
- Math tags: algebra, combinatorics, group-theory, representation-theory
- Ratings: usefulness 5/10; difficulty 5/10; novelty 7/10

## Idea description

Replace part of dense token mixing with a small bank of structured permutations acting on a hierarchical token tree. Diagonal inheritance shares the same local permutation across all descendant copies, while selector words activate one connector type at a chosen level and remain inactive on the next type, providing controllable multiscale receptive fields without constructing a dense attention matrix.

## Mathematical statement

Let D=(Y; phi_1,...,phi_k) be an alternating datum at level n, where Y is a finite coordinate set and phi_i maps Y into the local support T_{v_i,n}. For each descendant edge e starting at v_i, define phi_{i,e}(gamma)=phi_i(gamma)e. Proposition 4.4 says that a local alternating permutation sigma is copied to every descendant support: iota_{n,n+1}(A(D)) is the set of products over i and descendant edges e of phi_{i,e} sigma phi_{i,e}^{-1}. In the concrete selector system, b_1 and b_2 have activity vectors (0,1,2,1) and (1,1,1,0) in (Z/3Z)^4, where each coordinate corresponds to a connector type. The selector s_n is b_1^2 b_2 for n congruent to 2 modulo 4, b_1 b_2 for n congruent to 3 modulo 4, b_2 for n congruent to 0 modulo 4, and b_1 for n congruent to 1 modulo 4. Its activity is nonzero on the current connector type and zero on the next type, so conjugating a local cycle by s_n localizes the operation to the desired level. In the neural adaptation, each conjugated group element becomes a sparse token permutation P_out=P_s P_sigma P_s^{-1}, followed by a shared linear feature transform.

## Key formulas

- $$\iota_{n,n+1}\bigl(\mathsf{A}(\mathcal{D})\bigr)=\left\{\prod_{i=1}^{k}\prod_{\substack{e\in E_{n+1}\\\mathbf{s}(e)=v_i}}\phi_{i,e}\sigma\phi_{i,e}^{-1}:\sigma\in\mathsf{A}(Y)\right\},\qquad \phi_{i,e}(\gamma)=\phi_i(\gamma)e.$$
- $$\iota_{n,n+1}(g)=\prod_{x\in\{0_0,1,2\}}g_x,\qquad \iota_{n,n+2}(g)=\left(\prod_{x\in\{0_0,1,2\}}g_{x0_1}\right)\left(\prod_{x\in\{0_0,1,2\}}g_{1x}\right)\left(\prod_{x\in\{0_0,1,2\}}g_{2x}\right).$$
- $$b_1\longmapsto(0,1,2,1),\qquad b_2\longmapsto(1,1,1,0)\quad\text{in }(\mathbb{Z}/3\mathbb{Z})^4.$$
- $$s_n=\begin{cases}b_1^2b_2,&n\equiv2\pmod 4,\\ b_1b_2,&n\equiv3\pmod 4,\\ b_2,&n\equiv0\pmod 4,\\ b_1,&n\equiv1\pmod 4,\end{cases}\qquad P_{\mathrm{out}}=P_{s_n}P_{\sigma_n}P_{s_n}^{-1},\qquad H_{\mathrm{out}}=H+\alpha_n P_{\mathrm{out}}H W_n.$$

## Implementation notes

Integrate the module before the MLP in a Transformer, or use it as a message-passing layer on a rooted tree. Represent every token by a path of symbols in a fixed branching tree and store its local support and level. Choose a small support Y, such as three sibling positions, and precompute sparse permutation indices for 3-cycles and their inverses. Use two base sparse permutations P_b1 and P_b2. At level n, select the word s_n using n modulo 4, compose its permutation, apply a local cycle P_sigma, and conjugate the cycle: P_out=P_s P_sigma P_s^{-1}. Replicate the same local permutation over all descendant supports with the same parent type, exactly as in the diagonal embedding. The forward pass is: `for n in levels: sigma=local_cycle[n]; s=selector[n%4]; P_out=compose(P_s, sigma, inverse(P_s)); H=H+alpha[n]*gather(P_out,H)@W[n]`. Keep P fixed initially, then optionally learn logits over a small set of valid local cycles using a straight-through categorical estimator. The paper determines the replication rule and selector schedule; estimate alpha_n and the number of active levels empirically. Begin with CIFAR-100 using a four-stage vision Transformer and synthetic balanced-tree sequence classification. Compare dense attention, window attention, and this mixer at equal hidden size and parameter count. Measure validation accuracy, peak memory, tokens per second, and effective receptive field. A successful result is at least 1.5x throughput or 30 percent lower activation memory with no more than one percentage point accuracy loss.

## Disclaimer

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