Grammar induction means learning a context-free grammar from raw sentences with no parse trees. One family of methods offers something unusual: a convex formulation. It has no local optima, and on synthetic grammars it beats the standard expectation-maximization (EM) procedure. The catch is that its unknowns are indexed by every way of splitting every span of every sentence. That count grows as the cube of sentence length, so the method has only been run on sentences of ten words or fewer. We propose to keep the algebraic view behind this method but change what is computed. The split-indexed object is stored in factored form. The sum over split points for each span is evaluated as a single triangular matrix product. The large least-squares problems that remain are solved with sparse random projections whose cost tracks the number of nonzero entries in the data. The intended result is spectral-style grammar learning on ordinary-length sentences, roughly 40 words, with memory per sentence quadratic rather than cubic in length.
The case for this rests on a structural coincidence between three literatures. Algebraic treatments of grammars write a weighted context-free grammar (WCFG, a grammar whose rules carry real-valued weights) as vectors and bilinear operators. In that form, the weight of a string is a sequence of matrix–vector operations. Chart parsing gets its cubic cost from summing, for every span, over every split point. Input-sparsity sketching gives regressions and low-rank approximations whose running time is proportional to the number of nonzeros. These are exactly the tools needed when the constraints come from a sparse set of observed sentences. Our claim is that the cubic sum over splits in spectral grammar induction is a matrix product in disguise, and that the regression problems around it are input-sparsity problems in disguise.
Core Claim
Unsupervised Spectral Learning of WCFG as Low-rank Matrix Completion frames induction around a Hankel matrix. Its rows are outside contexts, its columns are inside strings, and each entry is the weight of the sentence formed by inserting the string into the context. The authors show that the rank of this matrix equals the number of nonterminals. They then recover the grammar by nuclear-norm minimization, a convex surrogate for low rank, under recursive structural constraints. In the unsupervised setting, the quantity one would like to observe is the weight contributed by each particular split of a string inside a context, and that quantity is unobserved. Only its sum over splits is pinned down by the observed sentence weight. These split-indexed values are therefore the completion variables, and a sentence of length $n$ contributes $O(n^3)$ of them. The authors themselves note that the problem size scales with the basis and becomes prohibitive for longer sentences. This is the paper our proposal builds on and departs from.
We parametrize the split-indexed Hankel in low-rank factored form. Each factor is a function of a sparse hashed feature vector of the span, such as boundary words and short n-grams. The model therefore never enumerates the $O(n^3)$ variables. The key identity concerns one sentence with fenceposts $0,\dots,n$ and a rank-$q$ factorization with components $u_r, v_r, w_r$. Define $(n{+}1)\times(n{+}1)$ strictly upper-triangular matrices $U^r, V^r, W^r$. Their $(i,j)$ entry is the factor value of span $[i,j]$ for the context, left-child, and right-child roles respectively. The model's predicted weight for every span then follows at once:
$$\hat h_{ij} \;=\; \sum_{r=1}^{q} U^r_{ij} \sum_{i<k<j} V^r_{ik} W^r_{kj} \;=\; \sum_{r=1}^{q} \big(U^r \circ (V^r W^r)\big)_{ij}.$$
Here $\circ$ is the entrywise product. Strict upper-triangularity makes the inner matrix product sum exactly over split points $k$ between $i$ and $j$. All span constraints of a sentence therefore cost $q$ matrix products. That is $O(q\,n^{\omega})$ time in principle, where $\omega \approx 2.37$ is the matrix-multiplication exponent, and in practice it is one batched dense multiply on a GPU. Memory is $O(q\,n^2)$, compared with $O(n^3)$ for the explicit variables.
The connection to known hardness is direct. Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication proves that any sub-cubic parser of a certain retrieval-efficient kind yields fast Boolean matrix multiplication. That result constrains the proposal: it suggests matrix-multiplication time is the right target for split-sum computations, not something to beat. Our identity reaches that target in a weighted, non-Boolean setting.
The second ingredient is sketching. Alternating over the factors turns each update into an overconstrained linear regression. Its rows are the (sentence, span) constraints, of which there are $\sum_s n_s^2/2$ across the corpus, and its columns are factor parameters. We solve each regression by sketch-and-solve with a CountSketch. This sparse random projection hashes each constraint row to one of $k$ buckets with a random sign. Low Rank Approximation and Regression in Input Sparsity Time and Sketching as a Tool for Numerical Linear Algebra show that this solves least squares to relative error $\epsilon$ in time $O(\mathrm{nnz} + \mathrm{poly}(d/\epsilon))$, where $d$ is the number of columns. We supply the method. We use the same results for the low-rank initialization of the context and string factors from the observed sparse Hankel. Input-Sparsity Low Rank Approximation in Schatten Norm provides a Schatten-norm variant that stays closer to the nuclear-norm objective.
What we give up should be said plainly. The factored problem is not convex. The scientific question is whether convexity is worth a ten-word ceiling, or whether a well-initialized factored solver on long sentences learns better grammars.
Research Program
The work has three parts.
The first is algorithmic. We implement the triangular split-sum identity together with its gradient, which reuses the same products transposed. We also implement CountSketch regression updates for the context, left, and right factors, and a separate lexical term for single-word spans. We prove a per-iteration bound of $O(\mathrm{nnz}(\Phi) + \sum_s q\,n_s^{\omega} + \mathrm{poly}(dq/\epsilon))$, where $\Phi$ is the sparse span-feature matrix. We also show that each sketched update is within a $(1+\epsilon)$ factor of the exact alternating update. The second claim is an inherited guarantee, not a new theorem about the global problem.
The second part is analytical. We compare the stationary points of the factored problem with Bailly et al.'s convex solution on instances small enough to solve both ways. We also characterize when hashed features make the low-rank Hankel structure unidentifiable. One case is when distinct substrings collide in the hash buckets that the rank argument relies on.
The third part addresses a known defect. Bailly et al. note that spectral completion can produce negative grammar weights. We study a nonnegative projection of the recovered operators, so that perplexity and Viterbi decoding are well defined, and we report how much fit this projection costs.
Baselines
The naive reference point is Bailly et al.'s convex nuclear-norm completion run where it is feasible, on WSJ10 (Wall Street Journal sentences of at most ten words) and synthetic grammars with short strings. Longer sentences are simply discarded. This "do nothing" option tests whether extending induction to longer sentences buys anything at all. The file reports only qualitative findings for this baseline: lower KL divergence than unsupervised EM on synthetic PCFGs (probabilistic context-free grammars), and decreasing WSJ10 training error as hidden states increase. No reported numerical result was found on Lacuna for Bailly et al. on WSJ10 or Dyck languages, so we will rerun it ourselves.
The strongest practical competitor is inside-outside EM on GPU, with dense chart parallelization in the style of Efficient Parallel CKY Parsing on GPUs. It already scales to long sentences, so it is the method our scaling argument must beat on quality rather than on speed. It is also the method Bailly et al. compare against.
For parse accuracy on the full Penn Treebank (PTB), the strongest number in the file is from Unsupervised Parsing via Constituency Tests. It scores spans with RoBERTa under substitution, movement, and clefting tests and assembles trees by exact CKY, reporting 62.8 unlabeled F1 on PTB and 71.3 F1 when refined with URNNG. That system produces parses, not an explicit grammar, and uses a large pretrained model. We will therefore report it as a reference ceiling rather than a head-to-head target. A fair comparison would give our span features the same RoBERTa embeddings, and we will run that variant.
Two ablations isolate the key ingredients. The first replaces the triangular-matrix-product evaluation with explicit enumeration of all split triples, keeping everything else fixed. This should match our objective exactly and differ only in time and memory. The second replaces CountSketch with uniform subsampling of constraint rows at the same row budget.
All methods get the same training sentences, the same nonterminal count or rank, the same wall-clock budget on one GPU, and the same number of hyperparameter trials. EM and our method each get the same number of random restarts.
Our method beats the baselines on quality if it matches Bailly et al.'s KL on short synthetic strings within noise, and strictly improves KL or F1 once longer sentences are added. It beats EM if it achieves lower KL on synthetic PCFGs at equal compute, and if its variance across restarts is smaller.
Why not just…?
Why not just keep the convex method and restrict to short sentences? Short sentences may carry most of the signal for frequent constructions. If adding sentences of 11 to 40 words does not improve held-out WSJ10 F1 or synthetic KL, our scaling buys nothing. Our core experiment measures exactly this, by training on length caps of 10, 20, and 40 and evaluating on a fixed test set.
Why not just run inside-outside EM on a GPU? This is the real threat. Dense GPU charts make EM fast enough, and Kitaev and Klein parse the whole WSJ development set in about 8 seconds on one GPU (Constituency Parsing with a Self-Attentive Encoder). Speed is therefore not our argument against EM. Our argument is that EM finds poor local optima, as Bailly et al. report. Our factored method is also nonconvex, and its advantage would have to come from the spectral, Hankel-based initialization and objective. Equal-compute KL comparisons on synthetic PCFGs with known ground truth, across restarts, will settle whether that advantage survives factorization.
Why not just subsample split points or constraints uniformly? Uniform sampling is unbiased and trivial to implement. However, constraint rows here are highly non-uniform: long sentences contribute quadratically many rows, and frequent constructions dominate. The guarantees in Low Rank Approximation and Regression in Input Sparsity Time hold for oblivious sketches regardless of row importance, while uniform sampling has none. In-Database Regression in Input Sparsity Time shows that sketched regression kept relative error at 0.66% while giving a 10-fold speedup on MovieLens joins. The uniform-subsampling ablation will show whether this gap actually appears for grammar constraints. If it does not, we will adopt the simpler sampler.
Why not just use a greedy top-down neural parser? A Minimal Span-Based Neural Constituency Parser reaches 91.69 F1 in quadratic time against 91.79 for its chart decoder. That parser is supervised by treebank trees and yields no grammar, prefix probabilities, or density estimates. It answers a different question, and we cite it only as a supervised upper reference.
Why not just prune spans or pre-segment sentences? Segmentation and beam pruning, reviewed in Scaling Syntactic Parsing Beyond Cubic Complexity, make parsing a fixed grammar fast. They do not reduce the size of the completion problem during learning. Pruning before the grammar is known would also bias exactly the statistics the method is trying to estimate.
Proposed Experiments
We use four testbeds: synthetic PCFGs with a known number of nonterminals and controllable string length (10, 20, 40, 80), synthetic Dyck languages, WSJ10, and PTB sentences of at most 40 words. Metrics follow Bailly et al. where possible. For synthetic PCFGs we report KL divergence to the true distribution as sample size grows. For Dyck languages we report $L_1$ distance. For WSJ we report unlabeled bracketing F1 of Viterbi parses from the projected nonnegative grammar, alongside the fraction of weight mass that was negative before projection. Systems measures are wall-clock time per iteration, peak memory, and the empirical exponent of time against sentence length.
The decisive checks are as follows. First, on short strings, the explicit-enumeration ablation and our triangular-product implementation give identical objectives, while our memory grows as $n^2$ rather than $n^3$. Second, the sketched regression error decays roughly as $1/\sqrt{k}$ in sketch size $k$, the rate implied by CountSketch's variance, and it stays small enough that final KL is indistinguishable from exact alternating updates. Third, where the convex solver runs, our solution's KL is within noise of it. Finally, and most importantly, adding longer training sentences strictly improves held-out KL on synthetic grammars and F1 on WSJ10. If the last check fails, the conclusion is that the cubic barrier was not what limited spectral grammar induction, and that is worth knowing.
References
- Unsupervised Spectral Learning of WCFG as Low-rank Matrix Completion
- Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication
- Low rank approximation and regression in input sparsity time
- Sketching as a Tool for Numerical Linear Algebra
- Input-Sparsity Low Rank Approximation in Schatten Norm
- Efficient Parallel CKY Parsing on GPUs
- Unsupervised Parsing via Constituency Tests
- Constituency Parsing with a Self-Attentive Encoder
- In-Database Regression in Input Sparsity Time
- A Minimal Span-Based Neural Constituency Parser