# Caret-Invariant Tree-Pair Mixer

- ID: 1535
- Canonical URL: https://synthcore.org/idea/1535/caret-invariant-tree-pair-mixer
- API JSON: https://synthcore.org/api/idea/1535.json
- API Markdown: https://synthcore.org/api/idea/1535.md
- Verification status: unverified
- Source: [arXiv:2607.28406](https://arxiv.org/abs/2607.28406)
- Category: architecture
- Solves: scalability, stability, accuracy
- ML areas: transformer, mlp, embedding, inference-speedup
- Math tags: combinatorics, algebra, group-theory
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Represent a token sequence or image region partition by a pair of planar rooted binary trees and a permutation of their leaves, following the tree-pair model of Thompson-type groups. Train the mixer to produce the same output whether a leaf is left intact or refined into two child leaves that are immediately merged by a matching inverse refinement. This creates a variable-resolution hierarchical module with an explicit consistency constraint instead of relying on an arbitrary fixed tree depth.

## Mathematical statement

The paper represents a Thompson-group element by a triple $v=(T_{+},T_{-},\sigma)$, where $T_{+}$ and $T_{-}$ are planar rooted binary trees with the same number $n$ of leaves and $\sigma\in S_n$ is a permutation describing how source leaves attach to target leaves. Different triples can represent the same element after adding matching binary carets to both trees; canceling such carets gives a reduced representative. The architecture uses this equivalence as a refinement relation. Let $x=(x_1,\ldots,x_n)$ be source leaf features, let $R_i$ replace $x_i$ by two child features $(x_{i0},x_{i1})$, and let $M_i$ merge those children back into one feature. The learned merge must satisfy $M_i(R_i(x))\approx x_i$. The paper also defines the oriented subgroup through the explicit compatibility condition $\sigma(n(T_{+}))=\pm n(T_{-})$, where $n(T)$ is the sequence of $+$/$-$ signs induced by the tree's oriented bands; this can be adapted as a signed or two-channel routing constraint when the model needs orientation-sensitive features. The coloring normalization in the paper, $\mathrm{Col}(v,(Q,*,\alpha))=|Q|^{-n}\mathrm{Col}(\mathscr{L}_{V}(T_{+},T_{-},\sigma))$, illustrates the same principle: quantities should be normalized by the number of leaves so that redundant expansions do not change the represented object.

## Key formulas

- $$v=(T_{+},T_{-},\sigma),\qquad T_{+},T_{-}\text{ have }n\text{ leaves},\quad \sigma\in S_n.$$
- $$\vec V=\left\{(T_{+},T_{-},\sigma)\in V:\ \sigma\bigl(n(T_{+})\bigr)=\pm n(T_{-})\right\}.$$
- $$M_i\!\left(R_i(x_1,\ldots,x_n)\right)\approx x_i,\qquad \mathcal L_{\mathrm{caret}}=\frac{1}{n}\sum_{i=1}^{n}\left\|M_i(x_{i0},x_{i1})-x_i\right\|_2^2.$$
- $$\mathrm{Col}(v,(Q,*,\alpha))=|Q|^{-n}\,\mathrm{Col}\!\left(\mathscr{L}_{V}(T_{+},T_{-},\sigma)\right).$$

## Implementation notes

Integrate this as a hierarchical mixer before a Transformer encoder, or as a replacement for fixed-size patch merging in a ViT. Start with a binary partition tree over tokens. Each leaf stores a feature vector $x_i\in\mathbb R^d$; each internal node applies a learned merge $M(x_L,x_R)=W[x_L;x_R]+b$ followed by normalization and a gated nonlinearity. A tree-pair action uses a source tree $T_+$, a target tree $T_-$, and a leaf permutation $\sigma$: gather source leaf features in permutation order, recursively merge according to $T_-$, and scatter the resulting features back to the target partition. During training, sample random caret expansions: choose a leaf, replace it with two children whose initial states are $x_{i0}=x_i+\epsilon_0$ and $x_{i1}=x_i+\epsilon_1$, and apply the merge. Add the displayed $\mathcal L_{\mathrm{caret}}$ against the unexpanded representation. At inference, dynamically expand high-error or high-variance leaves and keep low-error leaves coarse, giving an adaptive token budget. Canonicalize tree pairs by repeatedly canceling matching terminal carets before caching or comparing them; store the permutation as an integer index array. The mathematical input is the representation equivalence under caret cancellation; merge consistency and adaptive splitting are empirical rather than guaranteed. The first experiment should use CIFAR-10 or ImageNet-100 with a 6-layer ViT-Tiny, comparing fixed 4x4 patches and a standard hierarchical ViT at equal FLOPs. Measure accuracy versus active leaves, caret-consistency loss, and sensitivity to random partition depth. Success means equal accuracy with 25-50% fewer active tokens, or lower accuracy variance under changes in partition depth.

## Disclaimer

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