# Parallel Quadratic Tree Layer

- ID: 1665
- Canonical URL: https://synthcore.org/idea/1665/parallel-quadratic-tree-layer
- API JSON: https://synthcore.org/api/idea/1665.json
- API Markdown: https://synthcore.org/api/idea/1665.md
- Verification status: beats_baseline
- Source: [arXiv:2608.01332](https://arxiv.org/abs/2608.01332)
- Category: architecture
- Solves: speedup, scalability, stability
- ML areas: graph-nn, inference-speedup, world-model
- Math tags: linear-algebra, optimization, dynamical-systems, numerical-analysis
- Ratings: usefulness 7/10; difficulty 6/10; novelty 7/10

## Idea description

Replace sequential upward message passing in a tree-structured neural module with rake–compress contraction of quadratic latent-state messages. Each node stores a quadratic value function and each edge stores a linear transition or coupling triple; leaf elimination and unary-node compression are implemented as batched Schur complements, followed by a reverse pass that reconstructs node latents and edge outputs. The layer is exact for Gaussian or quadratic latent models and remains differentiable through the contraction.

## Mathematical statement

The paper uses node variables x_i,y_i in R^n and edge controls u_e in R^m, with symmetric node matrices Q_i, edge matrices R_e, and dual regularizers Delta_i. Its Lagrangian contains node quadratic terms, edge control terms, and linear dynamics constraints: L(x,u,y)=sum_i(1/2 x_i^T Q_i x_i+q_i^T x_i)+sum_{e=(i,j)}(x_i^T M_e u_e+1/2 u_e^T R_e u_e+r_e^T u_e)+y_rho^T(c_rho-x_rho)-1/2 y_rho^T Delta_rho y_rho+sum_{e=(i,j)} y_j^T(A_e x_i+B_e u_e+c_j-x_j)-1/2 sum_e y_j^T Delta_j y_j. The initial node coefficient is U_i=Q_i. Eliminating each edge control independently gives alpha_e=(bar A_e,bar C_e,bar P_e), with bar A_e=A_e-B_e R_e^{-1}M_e^T, bar C_e=Delta_j+B_e R_e^{-1}B_e^T, and bar P_e=-M_e R_e^{-1}M_e^T. For the neural adaptation, a subtree is represented by V_i(z)=1/2 z^T U_i z+h_i^T z+k_i. Raking adds independent child contributions to the parent after eliminating the child state, while compression composes adjacent quadratic factors and eliminates the intermediate state using the Schur complement H_aa-H_ab(H_bb+epsilon I)^{-1}H_ba. Here z is a d-dimensional latent, U and H are quadratic coefficient matrices, h is a linear coefficient, k is a scalar, and epsilon>0 is damping that ensures stable inverses.

## Key formulas

- $$\mathcal{L}(x,u,y)=\sum_{i\in\mathcal V}\left(\tfrac12x_i^{\mathsf T}Q_ix_i+q_i^{\mathsf T}x_i\right)+\sum_{e=(i,j)\in\mathcal E}\left(x_i^{\mathsf T}M_eu_e+\tfrac12u_e^{\mathsf T}R_eu_e+r_e^{\mathsf T}u_e\right)+y_\rho^{\mathsf T}(c_\rho-x_\rho)-\tfrac12y_\rho^{\mathsf T}\Delta_\rho y_\rho+\sum_{e=(i,j)\in\mathcal E}y_j^{\mathsf T}(A_ex_i+B_eu_e+c_j-x_j)-\tfrac12\sum_{e=(i,j)\in\mathcal E}y_j^{\mathsf T}\Delta_jy_j.$$
- $$U_i=Q_i.$$
- $$\bar A_e=A_e-B_eR_e^{-1}M_e^{\mathsf T},\qquad \bar C_e=\Delta_j+B_eR_e^{-1}B_e^{\mathsf T},\qquad \bar P_e=-M_eR_e^{-1}M_e^{\mathsf T}.$$
- $$\operatorname{Schur}(H;bb)=H_{aa}-H_{ab}(H_{bb}+\varepsilon I)^{-1}H_{ba},\qquad V(a)=\tfrac12a^{\mathsf T}\operatorname{Schur}(H;bb)a+\cdots.$$

## Implementation notes

Integrate this as a graph-nn layer for an explicitly supplied rooted tree, operating on latent vectors z_i of dimension d. Use a small MLP on node and edge features to emit symmetric quadratic coefficients: U_i=L_iL_i^T+epsilon I, linear term h_i, and edge transition or coupling matrices A_e,B_e,M_e,R_e with R_e=G_eG_e^T+epsilon I. Store each node message as (U_i,h_i,k_i), representing V_i(z_i)=1/2 z_i^T U_i z_i+h_i^Tz_i+k_i, and apply the paper's independent edge elimination using bar A_e, bar C_e, and bar P_e. Construct a fixed rake–compress schedule for the tree. In a rake operation, eliminate a leaf child and add its reduced quadratic contribution to the parent coefficients; this is coefficient addition after a Schur complement. In a compress operation, combine two adjacent edge factors into one joint block quadratic matrix and eliminate the intermediate latent state with H_aa-H_ab(H_bb+epsilon I)^(-1)H_ba. Execute all independent operations at each schedule level with batched torch.linalg.solve or Cholesky, giving O(Nd^3) arithmetic work and O(log N) synchronization levels. Save eliminated blocks and schedule metadata, then reverse the schedule to reconstruct every z_i, edge prediction, and gradient path. Compare the parallel output with a sequential postorder implementation on random trees and require maximum output and gradient discrepancies below 1e-5. The first experiment should use d=16 on synthetic Gaussian tree regression with irregular trees containing 1,000 to 100,000 nodes, comparing sequential PyTorch tree message passing, the parallel layer, and a dense baseline on small trees. Measure loss, gradient agreement, peak memory, and GPU wall-clock time. Success means at least 3x lower latency for tall or irregular trees at equal arithmetic work, with no validation-error degradation or increase in gradient failures.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built a differentiable quadratic tree layer with Schur-complement child elimination, synchronized rake levels, reverse MAP reconstruction, and a sequential reference. The mechanism checks passed: quadratic correction scaled exactly as gamma^2, damping reduced magnitude according to the analytic inverse-denominator formula, and balanced-tree rake depth matched floor(log2(n)); sequential and rake root coefficients and input gradients agreed below 9e-16. The promised 3x speedup was not observed in this unbatched Python MVP: rake was only 0.92–0.99x the sequential runtime for 127–1023 nodes, so there is no demonstrated practical latency win yet.

### Mechanism check

- Verdict: Built a differentiable quadratic tree layer with Schur-complement child elimination, synchronized rake levels, reverse MAP reconstruction, and a sequential reference. The mechanism checks passed: quadratic correction scaled exactly as gamma^2, damping reduced magnitude according to the analytic inverse-denominator formula, and balanced-tree rake depth matched floor(log2(n)); sequential and rake root coefficients and input gradients agreed below 9e-16. The promised 3x speedup was not observed in this unbatched Python MVP: rake was only 0.92–0.99x the sequential runtime for 127–1023 nodes, so there is no demonstrated practical latency win yet.
- Confidence: 8/10
- Limitations: The implementation uses Python loops rather than genuinely batched torch operations, so it does not realize the proposed parallel hardware schedule. It tested synthetic quadratic trees only, with up to 1023 nodes and latent dimension 8; no 100k-node scaling, neural feature MLP, validation regression task, peak-memory measurement, dense baseline, or multi-GPU synchronization was tested.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 8/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/617/bench_report.json)
- [quadratic_tree.py](https://synthcore.org/code/617/quadratic_tree.py)
- [report.md](https://synthcore.org/code/617/report.md)
- [report_bench_2026-08-31T195753.md](https://synthcore.org/code/617/report_bench_2026-08-31T195753.md)
- [results.json](https://synthcore.org/code/617/results.json)
- [run_experiment.py](https://synthcore.org/code/617/run_experiment.py)
- [stage2_bench.py](https://synthcore.org/code/617/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/617)

## Disclaimer

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