# Boolean Tree Token Routing

- ID: 1169
- Canonical URL: https://synthcore.org/idea/1169/boolean-tree-token-routing
- API JSON: https://synthcore.org/api/idea/1169.json
- API Markdown: https://synthcore.org/api/idea/1169.md
- Verification status: unverified
- Source: [arXiv:2607.19940](https://arxiv.org/abs/2607.19940)
- Category: architecture
- Solves: speedup, stability, scalability
- ML areas: attention, transformer, moe-routing, inference-speedup
- Math tags: combinatorics, graph-theory, algebra
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Replace unconstrained pairwise token grouping with a tree whose edges carry independent merge or cut variables. The connected components of the retained edges define a valid partition at every forward pass, while learned edge gates control the amount of token aggregation. A coarse component-level computation can then replace part of dense attention.

## Mathematical statement

Let U = {1,...,n} be the token set and let T = (U,E) be a tree, so |E| = n - 1. For any edge subset S contained in E, define pi_S as the partition of U into connected components of the forest (U,S): pi_S = CC(U,S). The tree-generated family B_T = {pi_S : S is a subset of E} has 2^(n-1) elements. Each edge is an independent Boolean coordinate: retaining an edge merges the two incident components, while deleting it separates them. Under the convention that the least partition is the all-singleton partition and the largest partition is {U}, the Boolean operations correspond to pi_S meet pi_R = pi_(S intersection R) and pi_S join pi_R = pi_(S union R). The tree's acyclicity is the key transferable property: every combination of local edge decisions is globally realizable, so routing cannot produce an invalid partition. The neural adaptation uses a soft edge probability p_e = sigmoid(w_e divided by tau), where w_e is a learnable logit and tau is a temperature, followed by differentiable message passing or pooling weighted by p_e.

## Key formulas

- $$\pi_S=\operatorname{CC}(U,S)=\{C_1(S),\ldots,C_{m(S)}\},\qquad S\subseteq E,\quad |E|=|U|-1.$$
- $$\mathcal B_T=\{\pi_S:S\subseteq E\},\qquad |\mathcal B_T|=2^{|E|}=2^{|U|-1}.$$
- $$\pi_S\wedge\pi_R=\pi_{S\cap R},\qquad \pi_S\vee\pi_R=\pi_{S\cup R}.$$
- $$p_e=\sigma\!\left(\frac{w_e}{\tau}\right),\qquad h_u'=\phi\!\left(h_u,\sum_{v:(u,v)\in E}p_{uv}\,W h_v\right),\qquad \mathcal L_{\mathrm{gate}}=\lambda\sum_{e\in E}p_e(1-p_e).$$

## Implementation notes

1. Integration point: insert the module before one or more transformer attention blocks and operate on the token tensor H in R^(B x n x d). Start with a fixed balanced binary tree over token positions, or use a chain as the simplest baseline. Give every tree edge e = (u,v) a learnable scalar logit w_e. During training compute p_e = sigmoid(w_e / tau), with tau annealed from 1.0 to 0.1. 2. Pseudocode: `p = sigmoid(w / tau); for each tree level from leaves upward: parent = (1-p_e) * pool(child_left, child_right) + p_e * merge(child_left, child_right); H_route = tree_message_pass(H, p); H_out = H + alpha * H_route`. The tree message pass can use `m_u = sum over neighboring v of p_(u,v) W h_v`, followed by a linear layer and GELU. Add the regularizer `lambda * sum_e p_e * (1-p_e)` to encourage nearly binary gates, and optionally add `lambda_budget * (mean_e p_e - b)^2` to target an average active-edge budget b. 3. At inference, threshold each gate: S = {e : p_e > 0.5}. Compute connected components of (U,S) with union-find. Pool token states within each component, run a small attention layer only over component representatives, and scatter the outputs back to all member tokens. The paper's mathematics supplies the exact valid-partition construction and the edge-coordinate interpretation; the tree topology, gate regularization, temperature schedule, and budget are empirical design choices. 4. First cheap experiment: train a 6-layer transformer with model width 256 on CIFAR-10 patch-token classification or a small WikiText-2 language model. Compare dense attention, fixed random-tree routing, unconstrained pairwise token gates, and learned Boolean tree routing. Record validation accuracy or perplexity, routed-branch FLOPs, peak activation memory, wall-clock time, average number of connected components, and fraction of active edges. A positive result is at least 1.5x lower routed-branch FLOPs or memory at no more than a 1% relative accuracy or perplexity degradation, with stable training and no invalid routing patterns.

## Disclaimer

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