acceptodds
Withdrawn from ICLR 2027

Neuro-symbolic Syntactic Parsing: Shaping a Neural Network with the CYK Algorithm

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

In this paper, we show the possibility of a direct injection of algorithms into neural network architecture. We focus on a complex algorithm, that is, Cocke-Youger-Kasami (CYK) for parsing context-free grammars in Chomsky Normal Form and we propose CYKNN, a simple recurrent neural network architecture for encoding the CYK algorithm in trainable matrix-vector multiplications.We experimented with a very simple grammar with 4 variations showing that our approach outperforms existing LLMs with more than 20B parameters with an in-context learning setting and smaller LLMs of the Qwen family fine-tuned with LoRA. Our attempt paves the way to a different approach to neuro-symbolic methodologies.

Primary area:
interpretability and explainable AI
Keywords:
Neuro-symbolic approaches, Parsing, CYK, NLP

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_kU2oOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes CYKNN, a neural architecture that attempts to directly encode the classical Cocke–Younger–Kasami parsing algorithm into a trainable neural network. The authors use Holographic Reduced Representations to represent symbols, CYK tables, and grammar rules as matrices, and reformulate parts of the CYK dynamic-programming procedure as matrix multiplications and recurrent updates. The main idea is to directly shape a neural architecture using the structure of a known symbolic algorithm rather than requiring the model to rediscover the algorithm purely from data. The experiments use data generated from a simple synthetic grammar and compare CYKNN with finetuned and in-context-learning language models, together with several architectural and initialization variants. Overall, the paper presents a potentially interesting neuro-symbolic idea, but the current theoretical analysis, experimental validation, and presentation are insufficient to establish the claimed contribution.

Critical strengths

The main strength is the attempt to directly exploit the structure of a known symbolic algorithm when designing a neural architecture. Within the current synthetic setting, the ablation results also indicate that explicitly injected grammar structure is useful: CYKNN initialized with the correct grammar substantially outperforms the randomly initialized and non-context-free variants.

Critical weaknesses
  1. The main conclusions go beyond what is supported by the current theoretical and experimental evidence Based on experiments with relatively simple synthetic grammars, the paper draws strong conclusions regarding the algorithmic learning capabilities of Transformers, memorization behavior, and the generality of the proposed approach. However, the current evidence is insufficient to support these claims. CYKNN explicitly incorporates the structure of the CYK algorithm and grammar priors, whereas the language models are required to generate complete CYK tables as serialized text. The two settings therefore differ substantially in inductive bias, task interface, output representation, and training procedure, making it difficult to attribute the observed performance differences directly to an inherent inability of Transformers to learn the algorithm. Moreover, the experiments are largely restricted to simple synthetic grammars, leaving it unclear whether the proposed method remains effective for more complex grammars, longer sequences, or realistic parsing tasks.

  2. The manuscript has a low level of overall polish, with substantial presentation, figure, and formatting issues I read the paper several times and still found substantial parts of it difficult to follow. The manuscript contains numerous spelling errors, naming inconsistencies, problematic figure captions, and low-quality figure presentation. Several figures are poorly designed or labeled, and terminology and model names are used inconsistently, including the mixed use of CYKNN and CKYNN, along with multiple obvious typographical errors. These issues occur repeatedly throughout the manuscript and substantially affect its readability and overall presentation quality. In addition, the Limitations section appears on page 10 of the PDF and precedes the References, which appears to violate the nine-page main-text limit.

Questions for authors

The issues that I would like the authors to address are already described in the Critical Weaknesses section.

Reviewer_ktxbOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces CYKNN, a recurrent neural network architecture designed to encode the CYK parsing algorithm using Holographic Reduced Representations. The core idea is to "inject" the algorithm directly into the network architecture by representing symbols and grammar rules as matrices.

Critical strengths

No strength.

Critical weaknesses
  1. The comparison between CYKNN and LLMs is severely biased. CYKNN's grammar matrices are explicitly initialized with the exact target grammar G_0, meaning the model is essentially open-book and pre-programmed with the ground-truth rules. In contrast, LLMs are asked to infer both the rules and the rigid output format from scratch.

  2. The paper claims to reduce CYK's complexity from O(n^3) to O(n). This is mathematically misleading. Each iteration involves a d×d matrix multiplication, which costs at least O(d^3). Given the large embedding dimension d=2000 and extremely short sequences n<=16, the actual computational cost of CYKNN is much higher than traditional CYK O(n^3).

  3. The framework appears unable to scale in two critical dimensions. First, it is entirely deterministic and cannot handle Probabilistic Context-Free Grammars (PCFGs), which are essential for real-world natural language parsing. Second, the HRR mechanism sums all grammar rules into a single matrix. As the number of rules increases, this summation will suffer from severe crosstalk and noise, making it impossible to handle realistic grammars with hundreds of rules.

Questions for authors

Please refer to weaknesses.

Reviewer_jpB7OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a new architecture called CYKNN with a novel idea to inject CYK algorithm, based on holographic reduced representations to capture the applied grammar. A CYKNN is essence a recurrent neural network with trainable weights encoding CYK algorithm.

The paper shows that CYKNN is more effective in parsing with pretty simple CFGs, compared to some existing LLMs.

Critical strengths

The paper is easy to understand, with good ideas about using holographic reduced representations to encode symbolic reasoning in neural networks.

As claimed, the paper shows a novel way to inject CKY algorithm into neural networks.

Critical weaknesses

Three most serious problems of the paper.

First, it's unclear how well the proposed method can scale. The paper doesn't show the time and memory complexity analyses. Besides, the experiments use a very simple grammar (3 unary rules and 5 binary rules), which is too small to be useful to handle natural languages. Yet, d was set 2000, which is very large w.r.t. the very small size of the used grammar.

Second, the experiments don't compare CYKNN against neural parsing models in the literature (e.g. [1]). LLMs aren't good baselines as they are not designed for parsing. Besides, the experiments results for CYKNN aren't really good, with F-score (full test) is just 0.775 (with such small grammar). Note: it's unclear why the paper uses their own metrics rather than those metrics widely adopted in the parsing community.

It's unclear about the applicability of CYKNN. Also, how to extend the proposed method to other algorithms.

[1] Kitaev, Nikita, and Dan Klein. "Constituency parsing with a self-attentive encoder." Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2018.

Questions for authors
  • could the authors provide comparisons between CYKNN against popular neural parsing architectures in the literature?
  • could the authors provide time and memory complexity analysis?
  • could the authors state how scalable CYKNN is? If possible, showing how CYKNN performs on real parsing data.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.