cs.CLApr 28, 2026

Structural Generalization on SLOG without Hand-Written Rules

Authors: Zichao Wei

Organizations: Saarland University

Abstract

Structural generalization in semantic parsing requires systems to apply learned compositional rules to novel structural combinations. Existing approaches either rely on hand-written algebraic rules (AM-Parser) or fail to generalize structurally (Transformer-based models). We present an alternative requiring no hand-written compositional rules, based on a neural cellular automaton (NCA) with a discrete bottleneck: all compositional rules are learned from data through local iteration. On the SLOG benchmark, the system achieves an overall accuracy of 67.3±0.2%67.3 \pm 0.2\% across 10 seeds (AM-Parser: 70.8±4.3%70.8 \pm 4.3\%), with 11 of 17 structural generalization categories at 100%100\% type-exact match, including three where AM-Parser scores 00--74%74\%. Analysis reveals that all 5,539 failure instances reduce to exactly two mechanisms: novel combinations of wh-extraction context with reduced verb types, and modifiers appearing on the subject side of verbs. When we decompose results by CCG structural features, each sub-pattern either succeeds on all instances or fails on all. Intermediate scores (e.g., 41.4%41.4\%) are mixtures of structurally distinct CCG patterns, not partial generalization. These results suggest that CCG directed types provide higher resolution than SLOG's phenomenon-level categories for characterizing structural generalization, and that the success/failure boundary is determined by the coverage of directed operations in the training data.

Explore similar work

Jul 2, 2026cs.CL

On the Role of Directionality in Structural Generalization

Several SLOG test categories explicitly involve directional distinctions (modifier position shifts, argument extraction positions), yet AM-Parser, the previous SOTA, uses an AM algebra whose operations do not encode direction. We redesign the symbolic backend around CCG directed types (deterministic CKY + single linear decoder, 30K learnable parameters). Under the same BERT-base encoder, the system achieves 75.9±\pm6.4% LF exact match, surpassing AM-Parser (70.8±\pm4.3%). Per SLOG's own category groupings, gains are highly directional: the CCG system outperforms AM-Parser on all 5 position-shift categories (+29.9pp), while AM-Parser outperforms on all 6 recursive-depth categories. Replacing the encoder with DeBERTa-v3-large yields 90.7±\pm4.9%, with the largest encoder gains in recursive-depth categories, complementary to directionality's gains. Directional representations shift the bottleneck from the symbolic layer (AM-Parser's 0% category ceiling) to the neural layer, which improves with encoder upgrades.
Zichao Wei
Jul 21, 2026cs.CL

On the Computational Complexity of Structural Generalization

Structural generalization has been measured repeatedly by several benchmarks, yet it has never been formally defined. We give a definition that translates the two premises (compositional structure and unbounded generalization) into mathematical language. The definition itself is neutral: a compiler that hard-codes the rules satisfies it just as well. But structural generalization becomes a scientific question only insofar as the capacity can autonomously emerge from finite data. This question pits the computational lower bound NC1\mathrm{NC}^1 against the learnable ceiling TC0\mathrm{TC}^0 of pure Transformers. Under a Montagovian instantiation, each compositional rule splits into two projections: a syntactic face (FγF_γ) and a semantic face (GγG_γ). Tree evaluation on the GγG_γ side is an instantiation of BFVP, which is NC1\mathrm{NC}^1-complete (Buss, 1987). A pure Transformer must learn both faces at once, but Kraus et al. (2026) prove that its learnable class TC0\subseteq \mathrm{TC}^0. Under the standard assumption TC0NC1\mathrm{TC}^0 \neq \mathrm{NC}^1, a pure Transformer cannot learn structural generalization. Neuro-symbolic systems achieve the best benchmark scores precisely because they inject GγG_γ, sidestepping the genuinely hard half. Benchmark scores cannot distinguish "learned" from "given." This is what this paper sets out to make clear.
Zichao Wei
Jul 9, 2026cs.CL

Holographic Neural PCFG for Unsupervised Parsing

Unsupervised constituency parsing aims to accurately induce latent tree structures from raw text alone. Recent neural parameterizations of PCFGs achieve strong performance in both supervised and unsupervised parsing, yet rely on high-capacity black-box networks for rule scoring -- as exemplified by the Neural PCFG family -- leaving rule probabilities without an interpretable mathematical form. In this paper, we propose Holographic Neural PCFG (Hol-PCFG), which recasts PCFG rule scoring as algebraic relation modeling among grammar-symbol embeddings. Hol-PCFG adapts Holographic Embeddings (Nickel et al., 2016), which scores knowledge-graph triples via circular correlation, to the left-child, right-child, and lexical-emission relations over torus-constrained embeddings, giving every rule probability a closed form that carries the intrinsic structure of grammar rules by construction. Hol-PCFG achieves state-of-the-art parsing performance in six languages while cutting rule-scoring parameters by 99.94% relative to the baseline model and training more stably. Additionally, we demonstrate that Hol-PCFG can parse Japanese directly from characters without any morphological segmentation, retaining nearly the same morpheme-level performance.
Ryosuke Yamaki, Daichi Mochihashi, Nobutaka Shimada +1