Aligning two trees means deciding which node of one tree corresponds to which node of the other. The trees might be two SQL query parses, a predicted and a gold constituency parse, or a sentence's syntax in two languages. The best methods add a structural rule: if node A sits above node B in one tree, their partners must keep that relationship in the other tree. Rules of this kind are called hierarchy-preserving or least-common-ancestor (LCA) preserving constraints. Researchers have mostly treated them as an accuracy device. They stop a leaf from being matched to a root, and they cost extra computation. This note argues that the same rule is also the most useful sparsity pattern available to a GPU.
Number each tree's nodes in depth-first order. Every subtree then occupies one contiguous range of indices. Once a few high-level node pairs are committed, the constraint confines every remaining match to a handful of rectangles in the alignment matrix, and each rectangle can be computed as an ordinary dense block. Hardware work shows that "skip the zeros" schemes usually lose to plain dense matrix multiplication unless more than 95–99% of entries are zero. Hierarchical alignment sidesteps that losing regime. Its sparsity arrives already arranged in blocks the hardware runs at full speed.
Core Claim
The claim is that ancestor-preserving tree alignment can be executed as a batch of small dense problems over subtree-pair blocks. This "subtree-block" execution crosses over and beats full dense execution at tree sizes and batch sizes where unstructured sparse kernels still lose. The block layout is what moves the crossover point.
The key fact is simple. In depth-first preorder, the subtree under node $u$ occupies the index interval $I(u) = [\mathrm{pre}(u), \mathrm{pre}(u)+\mathrm{size}(u)-1]$. Suppose a coarse matching commits pairs $(u_k, v_k)$, $k = 1,\dots,K$, between trees with $n$ and $m$ nodes. Ancestor preservation then forces every descendant match into the union of rectangles $I(u_k) \times I(v_k)$, plus an unconstrained residual for unmatched nodes. The fraction of the full $n \times m$ matrix that stays active is
$$ \rho = \frac{1}{nm}\sum_{k=1}^{K} |I(u_k)|\,|I(v_k)|, $$
where $|I|$ is interval length.
Let $c$ be the dense cost per matrix entry and $\tau$ the fixed launch-and-padding cost per block. Block execution then beats full dense execution roughly when
$$ \rho + \frac{K\tau}{c\,nm} < 1. $$
This simple cost model predicts two things. First, the gain grows with tree size, because $\rho$ shrinks roughly by the branching factor at each committed level while $nm$ grows quadratically. Second, at the small sizes of Text-to-SQL trees, the per-block overhead can erase the gain. The second prediction is a real limitation, and the experiments are designed to locate it rather than hide it.
The closest existing work is Conditional Tree Matching (CTreeOT). It extends Sinkhorn optimal transport (an iterative algorithm that softly matches two sets by repeatedly rescaling rows and columns of a score matrix) with edge-level variables that penalize parent-child crossovers. It runs entirely as dense GPU logsumexp operations over full node and edge compatibility tensors. We keep its objective and change only how it is executed. In doing so we test a question CTreeOT leaves open: does the constraint's own structure make sparse execution profitable?
Research Program
The work has three parts.
The first part is a coarse-to-fine solver. It runs CTreeOT's alternating rescaling and message passing on the top levels of both trees, which is cheap because those levels are small. It then commits the top-$k$ candidate partners for each upper node. Keeping $k > 1$ hedges against early mistakes, since a wrong commitment at a high level cannot be repaired lower down. The solver then descends, restricting each subproblem to the rectangles that the committed pairs imply.
This is a soft, differentiable version of the vertical disambiguation that Hierarchical Discrete Relaxation and Graph Matching with Hierarchical Discrete Relaxation found more powerful than horizontal (sibling-order) constraints. Their finding is our motivation for expecting a small $\rho$. Unlike them, we use the pruning to choose a hardware layout, not only to filter clutter.
The second part is the execution layer. Blocks are grouped into a few padded size buckets and processed as batched dense logsumexp and matrix-multiply calls. The design borrows two ideas. From Centrifuge it takes the move of turning sparsity into smaller dense problems instead of calling sparse kernels. From TC-GNN it takes the move of condensing sparse structure into dense tiles. TC-GNN freely reorders graph nodes, which would break ancestor relations. Here the depth-first ordering already gives contiguity, so no topology-violating re-indexing is needed. This is precisely the gap that unconstrained tiling leaves for hierarchical data.
As in Dynasparse, which switches between dense and sparse modes at runtime by measuring density, a dispatcher measures $\rho$ and $K$ for each tree pair and falls back to full dense execution when the inequality above fails.
The third part is a measured crossover map. It records wall-clock time and peak memory as functions of tree size, batch size (number of tree pairs aligned at once), $\rho$, and $K$. Measurements are taken on one recent NVIDIA GPU and on a CPU. The CPU comparison matters because Narayanan's forward-backward study reports a dense-sparse crossover at 32% density on CPU versus 53% on GPU. That gap leads us to expect our crossover to sit at smaller trees on CPU.
We also apply the same block decomposition to the exact $O(n^2m^2)$ dynamic program behind STRUCT-IOU, a parsing metric that aligns predicted and gold constituents under ancestor-descendant constraints. Here the coarse commitments become an approximation. We measure how far the approximate score drifts from the exact one, since that paper notes the metric is sensitive to deleted nodes that break ancestor chains.
Baselines
The naive reference point is the unadapted SmBoP parser on the five Spider schemas used by CTreeOT. SmBoP builds SQL trees bottom-up in parallel. Its micro-average accuracy before adaptation is 57.3% as reported in Conditional Tree Matching. For the systems side, the naive reference is full dense execution with no decomposition at all.
The strongest existing method on both accuracy and speed is dense CTreeOT itself. It reports micro-average accuracy rising from 57.3% to 62.2% and the hardest schema, car_1, rising from 43.3% to 52.8% (Conditional Tree Matching). It is the right competitor because our solver optimizes the same objective. Any accuracy loss is therefore the price of the coarse commitments, and any speed gain comes purely from execution.
For fairness, both run on the same retrieved cases, the same 3.3M-parameter relevance module, the same number of Sinkhorn iterations, the same GPU, and the same tuning budget for temperature and iteration count. Beating it means matching its micro-average within 0.5 points while delivering lower wall-clock time or memory on every workload where $\rho$ falls below the measured break-even.
On the parsing-metric side, the exact STRUCT-IOU dynamic program is the reference. I found no reported result on Lacuna for STRUCT-IOU scores on PTB or NXT-SWBD, nor for its runtime beyond the $O(n^2m^2)$ bound, so we report our own exact values and treat them as ground truth.
Two systems baselines represent the sparse alternatives. The first is unstructured sparse execution with cuSPARSE on the same active entries. The second is Centrifuge-style stripping of near-zero rows and columns of the transport plan followed by dense computation on what remains.
The ablation that isolates the key ingredient keeps exactly the same active entries and the same count of nonzeros, but randomly permutes node indices before block extraction. That destroys the interval contiguity. If the speedup survives this permutation, our explanation is wrong.
A second ablation derives blocks from embedding clusters instead of committed ancestor pairs. It tests whether hierarchy specifically, rather than any grouping, provides both the speed and the accuracy.
Why not just…?
Why not just stay dense, since parse trees are small? This is the most serious objection. On Spider trees of at most about 50 nodes, a single pair fits in cache, and per-block overhead may make our method slower. We expect that outcome and will report it.
The proposal's bet concerns larger regimes: STRUCT-IOU over full treebanks, many retrieved cases aligned against many queries, shared forests of the kind in Alignment of Shared Forests for Bilingual Corpora, and synthetic trees of up to several thousand nodes. In these regimes the dense $nm$ and edge-pair tensors dominate both memory and time. The crossover map settles the objection directly. If dense still wins at a thousand nodes and large batch sizes, the claim fails.
Why not just threshold the transport plan and strip dead rows and columns, as Centrifuge does? A converged alignment plan resembles a soft permutation, so nearly every row and column keeps some mass, and stripping removes almost nothing. Block structure removes the off-block mass inside rows that remain alive. This is an argument, not evidence, so the Centrifuge-style baseline runs on identical inputs. If it matches our speed, the block idea adds nothing and we will say so.
Why not just use vendor sparse kernels on the pruned candidates? Active fractions after one or two committed levels will likely sit in the moderate 30–90% sparsity range. In that range Centrifuge's analysis reports standard sparse GEMM running up to 10× slower than dense. MACKO shows that cuSPARSE is 2.8–13.0× slower than a specialized kernel at 50% sparsity. MACKO-style formats also assume a fixed weight pattern, whereas our pattern changes with every tree pair, so encoding cost would recur per pair. The cuSPARSE baseline confirms or refutes this on our workloads.
Why not just drop the hierarchy constraints and run plain Sinkhorn? This would make the problem easier to accelerate but would give back the accuracy CTreeOT gained over flat matching. We include unconstrained Sinkhorn on Spider so that the reader sees the cost of this shortcut.
Proposed Experiments
On Spider's five held-out schemas, we compare SmBoP, dense CTreeOT, and the subtree-block solver with $k \in \{1, 2, 4\}$ coarse candidates. We report accuracy, latency per query, and peak memory. The decisive accuracy check is that $k = 2$ stays within 0.5 points of 62.2% overall and does not lose ground on car_1.
On PTB, SPMRL 2013 Hebrew, and NXT-Switchboard, we compute STRUCT-IOU exactly and with block decomposition over every predicted-gold pair. We report the absolute score gap, the rank correlation of parser rankings, and the total corpus runtime. The decisive check is a score gap below 0.5 points together with a corpus-level speedup.
For scaling, we generate Galton-Watson branching trees, the local structure analysed in From tree matching to sparse graph alignment, with sizes from 50 to 5000 nodes and controlled branching factors. Paired trees are produced by random node deletions and relabelings. On these we sweep batch size and measure where block execution overtakes dense execution on GPU and on CPU.
The decisive scaling checks are three. The first is whether $\rho$ actually shrinks with tree size as the cost model predicts. If $\rho$ stays near a constant fraction, there is no asymptotic gain. The second is whether the measured crossover point agrees with the inequality given above once $\tau$ is fitted. The third is whether the random-permutation ablation loses the speedup while keeping the same nonzero count. That ablation is the single result most capable of falsifying the central claim that index locality, supplied for free by the hierarchy, is what moves the crossover point.
References
- Conditional Tree Matching for Inference-Time Adaptation of Tree Prediction Models
- Hierarchical Discrete Relaxation
- Graph Matching with Hierarchical Discrete Relaxation
- Unlocking Full Efficiency of Token Filtering in Large Language Model Training
- TC-GNN: Bridging Sparse GNN Computation and Dense Tensor Cores on GPUs
- Dynasparse: Accelerating GNN Inference through Dynamic Sparsity Exploitation
- An Efficient Phone N-Gram Forward-Backward Computation Using Dense Matrix Multiplication
- Structured Tree Alignment for Evaluation of (Speech) Constituency Parsing
- SmBoP: Semi-autoregressive Bottom-up Semantic Parsing
- Alignment of Shared Forests for Bilingual Corpora
- MACKO: Sparse matrix-vector multiplication for low sparsity
- From tree matching to sparse graph alignment