Caret-Invariant Tree-Pair Mixer

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.