# Budgeted Tree Message-Passing Planner

- ID: 2637
- Canonical URL: https://synthcore.org/idea/2637/budgeted-tree-message-passing-planner
- API JSON: https://synthcore.org/api/idea/2637.json
- API Markdown: https://synthcore.org/api/idea/2637.md
- Verification status: unverified
- Source: [arXiv:2608.20894](https://arxiv.org/abs/2608.20894)
- Category: architecture
- Solves: speedup, scalability
- ML areas: graph-nn, inference-speedup, moe-routing
- Math tags: optimization, dynamic-programming, graph-theory, combinatorics
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Before or during graph-neural-network inference, use a tree dynamic program to choose a limited set of active computation nodes and upgraded message-passing edges. A node receives an embedding from an active landmark only when the selected path has enough residual communication radius, so the planner directly optimizes weighted coverage under a joint node-and-edge budget. The resulting active subgraph is then used by a sparse GNN or graph transformer.

## Mathematical statement

The paper's unified optimization is $\max\{\sum_{k\in N}h_k z_k\mid (x,z)\in\mathcal F,\ \sum_{e\in\overline E}c^E_e x_e\leq\bar b,\ x_e,z_k\in\{0,1\}\}$, where $N$ is the graph-node set, $h_k\geq0$ is the importance weight of node $k$, $z_k$ indicates coverage, $x_e$ indicates an activated or upgraded edge, $c^E_e$ is its cost, and $\mathcal F$ contains connectivity and coverage constraints. For a rooted binary tree, $V(v,b,r)$ is the maximum covered weight in the subtree rooted at $v$ using budget $b$, given residual coverage radius $r$ entering from the parent. The no-incoming-coverage state is $\mathcal A(v,b)=\max_{b_1+b_2\leq b}[V(v_1,b_1,0)+V(v_2,b_2,0)]$. The incoming-coverage state is $\mathcal B(v,b,r)=\max_{b_1+b_2\leq b,\ x_{e_1},x_{e_2}\in\{0,1\}}[V(v_1,b_1-c^E_{e_1}x_{e_1},rx_{e_1})+V(v_2,b_2-c^E_{e_2}x_{e_2},rx_{e_2})]$. Here $v_1,v_2$ are the children, $e_i$ are parent-child edges, and an unselected edge forces the child's incoming radius to zero. A landmark at node $j$ is represented by a facility decision $y_j\in\{0,1\}$, with its own cost. Adapt $h_k$ to token or node importance, $z_k$ to whether node $k$ receives a valid sparse representation, and $x_e$ to whether message passing across edge $e$ is enabled.

## Key formulas

- $$\max\Bigl\{\sum_{k\in N}h_kz_k\Bigm|(x,z)\in\mathcal F,\;\sum_{e\in\overline E}c^E_ex_e\leq\bar b,\;x_e,z_k\in\{0,1\}\Bigr\}.$$
- $$\mathcal A(v,b)=\max_{b_1+b_2\leq b}\Bigl[V(v_1,b_1,0)+V(v_2,b_2,0)\Bigr].$$
- $$\mathcal B(v,b,r)=\max_{\substack{b_1+b_2\leq b\\x_{e_1},x_{e_2}\in\{0,1\}}}\Bigl[V(v_1,b_1-c^E_{e_1}x_{e_1},rx_{e_1})+V(v_2,b_2-c^E_{e_2}x_{e_2},rx_{e_2})\Bigr].$$
- $$\max_{\substack{x,z\in\{0,1\}}}\sum_{k\in N}h_kz_k\quad\text{s.t.}\quad\sum_{j\in N}c^{\mathrm{land}}_jy_j+\sum_{e\in E}c^{\mathrm{edge}}_ex_e\leq B,\quad z_k\leq\mathbf 1\!\left[\exists j:\ y_j=1,\ x\text{ activates a }j\!\to\!k\text{ path of length }\leq R\right].$$

## Implementation notes

Integrate this at graph-neural-network inference time, immediately before the expensive message-passing layers. The inputs are a rooted tree or a block-cut-tree approximation of the graph, node importance scores $h_k$ such as gradient sensitivity or a learned positive scorer, landmark costs $c^{land}_j$, edge activation costs $c^{edge}_e$, total budget $B$, and maximum receptive-field radius $R$. First precompute subtree tables $V(v,b,r)$ for integer budgets $b=0,\ldots,B$ and residual radii $r=0,\ldots,R$. For each leaf, enumerate whether the node is selected as a landmark and whether it is covered. For each internal node, enumerate budget splits $b_1+b_2\leq b$, edge decisions $x_{e_1},x_{e_2}\in\{0,1\}$, and the resulting child residual states $r x_{e_i}$; add the node's weight when the node is covered, then retain the maximum value and backpointers. Use $\mathcal A$ when no coverage enters from the parent and $\mathcal B$ when coverage enters. At the root, backtrack to obtain selected landmarks and active edges, then run the GNN only on the induced sparse communication pattern. Cache the DP plan for every budget from $0$ through $B$ to obtain an anytime accuracy-versus-latency curve. Compute the DP exactly; estimate $h_k$ from a frozen pilot model, node gradients, attention mass, or a cheap auxiliary scorer. For graphs that are not trees, construct a block-cut tree, solve each biconnected block with a small local integer program or enumerate only the block's boundary states, and combine child tables through selector variables. The first experiment should use a 2--8 layer GCN or graph transformer on synthetic trees and real low-treewidth molecular or road graphs, comparing dense inference, independent top-$k$ node pruning, and greedy edge pruning at equal message-passing FLOPs. Measure weighted node accuracy, end-task accuracy, active-edge count, and planning overhead. Success means higher accuracy than independent pruning at the same budget, or a useful monotone accuracy-versus-budget curve with less than 5% planning overhead.

## Disclaimer

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