CCG Revisited: A Multilingual Empirical Study of the K uhlmann- S atta Algorithm (2025)

Abstract: We revisit the polynomial-time CCG parsing algorithm introduced by Kuhlmann & Satta (2014), and provide a publicly available implementation of it. We evaluate its empirical performance against a naive CKY-style parser across the Parallel Meaning Bank (PMB) corpus. While the fast parser is slightly slower on average, relative to the size of the PMB, but the trend improves as a function of sentence length, and the PMB is large enough to witness an inversion. Our analysis quantifies this crossover and highlights the importance of derivational context decomposition in practical parsing scenarios.

## introduction parsing with combinatory categorial grammar (ccg) occupies a crucial space in natural language processing, balancing linguistic expressivity with computational tractability. ccg's position at the bottom of the mildly context-sensitive hierarchy enables the analysis of some long-range dependencies and cross-serial constructions @xcite , but even an o(n 6 ) complexity places it out of reach of several large-scale applications. theoretically, ccg parsing was shown to be polynomial-time in sentence length by @xcite , with a worst-case complexity of o(n 6 ). @xcite much later introduced a simplified algorithm in terms of derivation contexts to handle deep stacks of arguments. through an operational lens, the existence of derivation contexts is the reason that ccg-parsing is polynomial-time. yet, ccg's complexity is more subtle than it appears. @xcite proved that ccg parsing is exponential in the combined size of the grammar and input, contrasting sharply with formalisms like tree-adjoining grammar (tag), in which parsing remains polynomial in both. this raises important questions about the practical utility of polynomial-time ccg algorithms: how often is an innovation like derivation contexts actually triggered in practice? do real-world grammars ever blow up? computational research on ccg, after all, has been driven for two decades by corpora with context-free backbones that use ccg-style notation. to address this gap, we provide the first empirical evaluation of the algorithm introduced by @xcite . we compare it against a closely related cky-style parser that lacks this innovation, widely used in existing ccg systems despite its exponential worst-case runtime. while it is true that traditional parsing algorithms have largely been supplanted by sequential supertagging methods in the research literature, in our experience, a stable and efficient reference algorithm is still important for experimental research in parsing, because it provides all possible parses (not just the most likely as scored by a language model), as well as a filter for derivability that conditions the evaluation statistics of supertagger outputs. our contributions here are threefold: this work thus bridges the gap between ccg parsing theory and empirical behavior, providing a grounded assessment of polynomial-time parsing in nlp pipelines. ## background in this section, we introduce some background and terminology that we will refer to across this paper and our implementation. a ccg category categories in combinatory categorial grammar (ccg) are either atomic elements or unary functions that take a category as input and return another category. more formally, the set of categories c is defined inductively as follows: arity bound as per @xcite , we define c g as a constant representing the maximum arity permitted in a derivation. it is computed as: equivalence in the limit let c g be the arity bound used by the kuhlmann-satta parser. then for any input sentence s, the set of derivable categories produced by the kuhlmann-satta parser with c @xmath0. this follows from the fact that context decomposition is only triggered when the arity of intermediate categories exceeds c g . in the limit, such decomposition never occurs, and the two parsers are functionally identical. chart items let w be an input string of length @xmath1, and let 0 ≤ @xmath2. in cky-style ccg parsing, chart items are of the form ⟨x, i, j⟩ where x is a category that spans the substring w[i : j] foot_0 . while standard application rules suffice for shallow derivation, deeper constructions involving nested argument stacks or crossing dependencies can cause exponential chart growth. to address this, @xcite introduce derivation context items ## analysis and discussion further analysis of our results let t naive (n) denote the runtime of the naive cky-style parser for a sentence of length n, and let t fast (n) be the runtime of the kuhlmann-satta parser on the same input. let |c n | represent the number of chart items produced during parsing. in pathological cases, we empirically observe: to study the crossover empirically, we group sentences by chart size into discrete bins: we define average runtimes over each group as: we observe that s @xmath3, indicating that the naive parser is faster on simple sentences. however, s @xmath4, with s k increasing sharply for higher k. this identifies a crossover point near chart size |c n | ≈ 10, after which the fast parser becomes consistently preferable. moreover, the proportion of sentences that utilize kuhlmann-satta derivation contexts (items of the form ⟨/y, β, i, i ′ , j ′ , j⟩) increases with k, from 1.0% in group 0 to over 80% by group 6. this strongly supports the theoretical intuition that derivation contexts are unnecessary for simple inputs, but crucial for more complex constructions. figure 1 summarizes these trends: the top-left panel reveals a clear crossover in speedup at @xmath5, the top-right panel shows that naive parsing time grows rapidly with complexity, while the fast parser remains stable, the bottom-left panel shows the increasing use of derivation contexts with complexity, and the bottom-right panel reflects sample distribution, affirming the statistical strength of early bins. these results validate the theoretical runtime guarantees of @xcite and demonstrate that their parser provides real-world benefits for high-complexity sentences. context use and syntactic depth our results suggest a strong relationship between derivational complexity and the activation of derivation contexts. let d(s) denote the syntactic depth of a sentence s, and let pr[context | s] denote the probability that at least one derivation context (i.e., kuhlmann item) is used in parsing s. then we conjecture: while we do not measure d(s) directly, we use chart size |c s | as a proxy for derivational complexity. empirically, figure 1 (bottom-left) shows that the proportion of sentences using derivation contexts increases with |c s | on average, though not strictly monotonically. we attribute deviations at high complexity to data sparsity (cf. bottom-right), and to the fact that high chart complexity may also arise from breadth (many constituents) rather than depth (nested arguments). ## conclusion we have presented the first empirical evaluation of the kuhlmann-satta polynomial-time ccg parser, comparing it to a naive cky-style baseline across multiple languages in the parallel meaning bank corpus. while the naive parser is faster on average, we find that the kuhlmann-satta algorithm offers clear advantages on structurally complex inputs, where it avoids exponential blowup within a reasonable overhead and maintains stable runtime behavior. our results validate the theoretical strengths of context decomposition in ccg parsing, and clarify when polynomial-time methods are practically beneficial. this work bridges the gap between parsing theory and real-world efficiency, demonstrating that asymptotic safety is achievable without sacrificing empirical utility. looking ahead, the kuhlmann-satta parser could play a key role in scaling symbolic parsers for tasks like grammar induction, real-time parsing, and multilingual nlp. further research might explore adaptive strategies for setting arity bounds, tighter memory constraints, and hybrid approaches that combine polynomial safety with cky-style heuristics in simpler cases.