Tree-Scan Mixers: Bidirectional State-Space Models That Scan Along the Syntax Tree

Linear-time sequence models called state-space models (SSMs) read a sequence with a running memory that is updated once per token, so their cost grows linearly with length rather than quadratically as in attention. Bidirectional versions run one pass left-to-right and another right-to-left. Recent code models built this way train efficiently and extrapolate to longer inputs. They share one weakness. Their memory decays with distance in the text, and in code the tokens that belong together are often far apart in the text but close in the program's syntax tree. A variable's declaration and its use may sit on either side of a fifty-line loop body. CodeSSM, a bidirectional SSM encoder for code, shows this pattern. It beats transformers on whole-function classification and retrieval but degrades on type inference, which its authors attribute to trouble with fine-grained token interactions.

We propose to keep the linear-time bidirectional recurrence and change the path it travels. Instead of scanning the token sequence forward and backward, the mixer scans the abstract syntax tree (AST), the nested tree a compiler parser builds from source code. It makes one pass upward from leaves to root and one pass downward from root to leaves. How strongly two tokens influence each other then decays with their distance in the tree, not in the text. The cost stays linear in the number of nodes. On a path-shaped tree this construction reduces exactly to an ordinary forward-plus-backward bidirectional SSM, so it is a strict generalization rather than a bolt-on.

Core Claim

Hydra shows that a principled bidirectional SSM is a quasiseparable matrix, meaning a lower-triangular scan plus an upper-triangular scan plus a diagonal term. It beats BERT-Base on GLUE (84.3 vs 83.5) in linear time. The lower and upper halves are the two directions along a path graph. Our claim is that the right bidirectional mixer for code is the same object defined on the AST. Every token or node $j$ influences node $i$ through the product of learned, input-dependent decays along the unique tree path between them:

$$ y_i = D_i x_i + \sum_{j \neq i} c_i^\top \Big(\prod_{e \in \mathrm{path}(j \to i)} A_e\Big) b_j x_j , $$

Here $x_j$ is the input feature of node $j$. $b_j$ and $c_i$ are learned input-dependent projections that write into and read from the memory. $A_e$ is a diagonal, input-dependent decay attached to tree edge $e$, with separate parameters for upward and downward traversal. $D_i$ is a diagonal skip term.

This sum can be computed exactly in two linear passes. The upward pass accumulates, for each node, decayed contributions from its subtree. The downward pass gives each node everything outside its subtree. It does so by taking its parent's outside message plus the parent's total upward sum, then subtracting its own contribution, which is exact because decays are diagonal. The number of sequential steps equals tree depth, and each level is a parallel scatter-add.

The prediction we can falsify is this: fine-grained token-level code tasks are hurt by distance measured in the text, not by recurrence as such. A tree-scan mixer should therefore close CodeSSM's type-inference gap while keeping its efficiency. A flat SSM given the same tree as input features should not close it.

Relation to Prior Work

Two lines of work already put ASTs into bidirectional encoders, and both inject structure through attention. AstBERT prunes the AST, adds node-coordinate embeddings, and restricts CodeBERT's self-attention to tokens in the same syntactic branch. AST-Transformer linearizes the AST in pre-order and lets nodes attend only to ancestors and siblings within a hop threshold $K$, cutting encoding cost by 90–95% on summarization. Both motivate the proposal: structure helps even strong bidirectional models. Both also constrain it. AST-Transformer's hard $K$ cutoff blocks long-range tree dependencies and is left untuned across languages, and AstBERT stays quadratic. Our mixer replaces the hard cutoff with learned soft decay along the tree, reaches every node, and keeps linear cost.

A second group uses the tree only to decide what to corrupt during training and leaves the sequence mixer untouched. AST-T5 masks whole subtrees and chooses segment boundaries that break few subtrees. TreeDiff applies tier-aware AST masking to a diffusion language model. We reuse subtree masking as our pretraining objective. Our contribution is architectural, and it is orthogonal to theirs.

The closest ancestor of the mechanism is BiConTree. It adds a top-down pass to a bottom-up Tree-LSTM on natural-language parse trees and gains 0.7 points from bidirectionality. It is nonlinear and binary-only, and it trains about 2.5× slower than a unidirectional Tree-LSTM. BASTS uses bottom-up-only Tree-LSTMs on split ASTs. We keep BiConTree's up-down idea but make it a linear, n-ary, parallel-per-level recurrence, which is what lets it slot into a pretrained SSM stack.

CodeSSM supplies the backbone and the failure case we target. Its unidirectional ablation (CodeSSM-Uni) drops sharply, which confirms that bidirectionality matters. Its authors explicitly omit ASTs.

Research Program

The model is a CodeSSM-style encoder. Each block pairs a flat bidirectional SSM over subword tokens with a tree-scan mixer over the AST. The flat path keeps left-to-right textual cues. The tree path carries syntactic proximity.

We parse with Tree-sitter and collapse unary chains of internal nodes to control node inflation, the "token explosion" problem both AstBERT and AST-Transformer report. Subword pieces of an identifier attach to their leaf node as an ordered chain of children. Internal nodes get learned type embeddings. Token features are scattered into tree positions and gathered back after the mixer, so the tree path adds roughly the number of retained internal nodes and nothing quadratic.

For broken or partial code we use Tree-sitter's error-recovery nodes. Where a region is unparseable, it degrades to a path, which is exactly the flat SSM. We will report accuracy on deliberately truncated snippets so that parse fragility is measured rather than assumed away.

Pretraining follows AST-T5-style subtree masking on the same corpora CodeSSM used: the CodeSearchNet subset of 1.8M text-code pairs and the 4.8M-sample StarCoder subset. We will use matched parameter counts and matched token budgets.

We will also write a fused kernel that runs the per-level scatter-add and the subtraction trick. Because the file notes that bidirectional-SSM kernels are less mature than attention kernels, wall-clock throughput and memory against CodeSSM and against an attention baseline are a first-class result, not an afterthought.

Baselines

The naive reference point is flat CodeSSM, the bidirectional gated SSM encoder over lexical tokens only. It is retrained with our tokenizer, data, parameter count and the same subtree-masking objective, so that any gain cannot come from the objective. Beating it on type inference is the minimum bar. The file has no numeric type-inference result for CodeSSM, only the qualitative report that it trails RoCoder and BertCoder, so we reproduce all three under identical fine-tuning budgets.

The strongest structure-aware competitor is AST-Transformer-style tree-structure attention, meaning pre-order AST sequence plus $K$-hop ancestor and sibling masks, applied to encoder tasks. It is the most direct existing answer to "use the tree to decide who talks to whom." We give it the same pretraining and sweep $K$ with the same number of tuning runs we give our decay initialization. AstBERT's branch-restricted attention is run as a second structural baseline.

For cross-paper anchoring, the file reports these figures:

  • BigCloneBench F1 of 0.973 for AstBERT and 0.971 for GraphCodeBERT (AstBERT), and 96.5 F1 for CodeBERT (CodeXGLUE).
  • Devign accuracy of 62.08% for CodeBERT (CodeXGLUE).

No reported number was found on Lacuna for CodeSSM's exact Devign or clone scores.

Beating the structural baselines means matching or exceeding their accuracy at equal parameters while using less memory at long lengths. On BigCloneBench, where scores are near ceiling, we treat parity plus the efficiency gain as the realistic win.

Three ablations isolate the key ingredient, which is structure in the transition rather than structure in the input. In the first, the flat SSM receives the pre-order linearized AST including internal-node tokens. In the second, the flat SSM receives AST depth and path embeddings in the style of VuLASTE. In the third, the tree mixer is kept but made upward-only, which tests the bidirectional component on the tree.

Why not just…?

Why not just feed a pre-order linearized AST to CodeSSM or Hydra? In pre-order order a whole subtree is one contiguous span. The next sibling of a large block therefore sits hundreds of steps away, and a flat decay forgets exactly the scope information it needs. That is the same text-distance problem, moved rather than fixed, and the linearization also inflates length. This is our first ablation. If it matches the tree-scan mixer on type inference and on the diagnostic below, our central claim is wrong and we will say so.

Why not just add AST depth or path embeddings to the tokens? Embeddings tell each token where it lives, but the recurrence still mixes by text distance. The model would have to learn to gate its memory on depth changes, which is possible in principle for a selective SSM. VuLASTE's path embeddings help vulnerability detection, but that is a whole-function label where locality matters little. The second ablation settles this on token-level tasks specifically.

Why not just add local attention to the SSM to fix short-range interactions? This is the most serious threat. CodeSSM's own diagnosis blames fine-grained short-range interactions, and a small attention window may repair type inference without any parser. We will run a hybrid with sliding-window attention at matched compute. Our prediction is that a window only helps when the related tokens are textually close. The diagnostic below separates textual gap from tree distance to test exactly this. If the hybrid wins even at large textual gaps, the tree mixer's case reduces to robustness and interpretability, and the note's claim narrows accordingly.

Proposed Experiments

The decisive check is a controlled diagnostic. We generate programs in which a use site must recover a declared type or a variable binding. We hold tree distance fixed while inserting intervening sibling subtrees of increasing size. The tree-scan model's accuracy should stay flat as the textual gap grows. Flat CodeSSM, the linearized-AST ablation and the windowed hybrid should decay once the gap exceeds their effective memory or window.

We then evaluate on real benchmarks. Token-level tasks are type inference, reproducing CodeSSM's setting, and variable-misuse-style localization built from the same functions. Sequence-level tasks are Devign and BigCloneBench from CodeXGLUE, the GHSA cross-language vulnerability set used by VuLASTE, and CodeSearchNet AdvTest retrieval.

Efficiency is measured as memory and throughput from 512 to 8k tokens against the attention baselines. CodeSSM reports up to 64% memory savings at length 2048, which our flat-plus-tree blocks must stay close to.

Robustness tests use identifier renaming and truncated, unparseable snippets. The first probes whether the tree path supplies the invariance reported in the AST literature. The second measures the cost of relying on a parser.

The proposal succeeds if the tree mixer closes most of the type-inference gap to transformer baselines and wins the diagnostic at large textual gaps, where both input-side structure and local attention fall short, while retaining linear scaling.