# Refine-and-Coarsen Block Router

- ID: 1280
- Canonical URL: https://synthcore.org/idea/1280/refine-and-coarsen-block-router
- API JSON: https://synthcore.org/api/idea/1280.json
- API Markdown: https://synthcore.org/api/idea/1280.md
- Verification status: unverified
- Source: [arXiv:2607.22383](https://arxiv.org/abs/2607.22383)
- Category: architecture
- Solves: scalability, memory, accuracy
- ML areas: moe-routing, graph-nn, attention
- Math tags: graph-theory, optimization, geometry
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Turn the paper's graphon refinement operation into an adaptive mixture-of-experts or relational-attention router whose number of blocks is learned rather than fixed. Split a block when its members produce incompatible constraint gradients, and merge blocks when their relation rows are statistically indistinguishable, yielding a compact architecture that grows only where the data require extra structure.

## Mathematical statement

The paper refines a step representation (A,pi) by splitting block l with 0<lambda<1. The child masses are pi'_l=lambda pi_l and pi'_{l+1}=(1-lambda)pi_l, while every incoming, outgoing, and child-child relation entry copies the parent's value: A'_{i,l;k}=A'_{i,l+1;k}=A_{i,l;k} and A'_{l,j;k}=A'_{l+1,j;k}=A_{l,j;k}. Thus refinement changes only the parameterization and leaves the represented graphon unchanged. Coarsening reverses this operation when two blocks have identical rows and columns, replacing their masses by their sum. For a learned soft model, define the motif Jacobian J_{qi}=partial t(F_q,A,pi)/partial pi_i, where F_q is motif q, t is its block density, and pi_i is block i's mass. Use the norm of this Jacobian together with within-block task-gradient variance as a split score. The transferable property is nested capacity: a split can initialize an exactly equivalent predictor, while a merge removes redundant experts.

## Key formulas

- $$\pi'_{\ell}=\lambda\pi_{\ell},\qquad \pi'_{\ell+1}=(1-\lambda)\pi_{\ell},\qquad 0<\lambda<1$$
- $$A'_{i\ell;k}=A'_{i,\ell+1;k}=A_{i\ell;k},\qquad A'_{\ell j;k}=A'_{\ell+1,j;k}=A_{\ell j;k}$$
- $$t(F,A,\pi)=\sum_{\phi:V(F)\to[m]}\left(\prod_{v}\pi_{\phi(v)}\right)\left(\prod_{(a,b;k)\in E(F)}A_{\phi(a),\phi(b);k}\right)$$
- $$J_{qi}=\frac{\partial t(F_q,A,\pi)}{\partial \pi_i},\qquad s_i=\operatorname{Var}_{v:P_{vi}>\tau}\left(\nabla_{z_v}\mathcal{L}\right)+\alpha\left\|J_{:,i}\right\|_2^2$$

## Implementation notes

(1) Use this in an MoE router or block-structured graph-attention layer. Maintain m experts or blocks, router logits R_vi, soft assignments P_vi=softmax_i(R_vi/T), block masses pi_i, and relation-specific interaction parameters A_{ij;k}. (2) Train with a fixed initial width for a warmup period. Every K steps, compute each block's load pi_i, the variance of task gradients or router embeddings among nodes assigned to that block, and the motif-Jacobian score J_{qi}=partial t(F_q,A,pi)/partial pi_i. If a block has score s_i above a threshold and pi_i is greater than 2 pi_min, split it with lambda=1/2. Copy all incoming and outgoing A entries to both children according to the refinement equations, duplicate the parent router logits, and add small opposite perturbations plus or minus epsilon u so the children can specialize. This makes the initial function nearly unchanged. (3) For coarsening, compute d_ij as the sum of the Frobenius distances between the two blocks' incoming and outgoing relation profiles. Merge the closest pair when d_ij is below delta and their task-gradient distributions are similar; replace their masses by pi_i+pi_j and average parameters mass-weightedly. Continue gradient training after each event. The refinement identities are mathematical guarantees; thresholds, gradient variance, and perturbations are empirical choices. (4) First test on a synthetic planted-block relational graph and Cora or ogbn-arxiv, comparing adaptive width with fixed m in {2,4,8,16}. Track accuracy versus active blocks, peak memory, expert load balance, and loss discontinuity after structural events. Success means matching the best fixed-width model with fewer active blocks and no measurable loss spike after splits or merges.

## Disclaimer

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