Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents a part empirical / part theoretical analysis of the representational power of non-deterministic stack RNNs.  It is shown theoretically that renormalizing nondeterministic stack RNNs  (RNS-RNNs) have the power to recognize context-free languages and their intersections (Props 1 and 2).  The ability of RNS-RNNs to recognize context-free languages is investigated empirically, whose performance is shown to surprisingly exceed what might be expected theoretically.  The authors show that the model is using the non-deterministic state of the stack to exceed the limitations that would otherwise exist for a deterministic model (Fig. 3).  This prompts the introduction of a novel architecture, where the stack is allowed to store real vectors rather than only discrete symbols, and it is shown that this representation achieves SOTA performance when modeling real language data in terms of perplexity (Table 1).
strength_and_weaknesses: Stengths:

-  The paper is clearly presented, and investigates an interesting phenomena.  Particularly, the comparison of neuro-symbolic models' representational strength using formal languages is a promising approach, which is currently under-explored.
-  The theoretical analysis is thorough,
-  The empirical analysis is convincing, and provides good motivation for why the vector-valued stack should increase the model's power (essentially by allowing the model to choose the number of symbols stored on the stack).

Weaknesses:

-  The theoretical analysis is essentially the translation of a pushdown automata (PDA) construction into a RNS-RNN, which in itself is not surprising (although useful for determining the dimensions of an RNS-RNN equivalent to a given PDA strength).
-  It is unclear if there is a specific advantage to using vector RNS-RNNs with its stack memory model in terms of performance as opposed to say models with access to a key-value based memory model, as in a DQN model.  It would be interesting to see such comparisons, both on the formal and natural language data (for the former, one would expect that there are limitations on representational strength imposed by the number of possible keys, but it is not clear how non-determinism would affect this).
clarity,_quality,_novelty_and_reproducibility: The clarity, quality, novelty and reproducibility are good.
summary_of_the_review: An interesting investigation of the representational strength of a neuro-symbolic model, combining theoretical and empirical analysis.  The work will be of interest to those working on formal languages, deep-learning and natural language processing.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper examines the capacity of renormalizing nondeterministic stack RNN (RNS-RNN), a stack RNN variant proposed by previous work, and proves that it can recognize all context-free languages. It empirically shows that, surprisingly, it performs well in recognizing non-context-free languages, even when the language’s alphabet is larger than the stack’s. To increase its capacity, the paper proposes a new variant that embeds the stack states into vectors and shows that it achieves competitive performance in recognizing large-alphabet formal languages.

strength_and_weaknesses: Strength:
- The paper is fairly clear for how dense it is.
- The experiments are well-designed to support the claims
- It provides new insights into the modeling capacity of stack RNNs.

Weaknesses:
- The paper can be more self-contained. It heavily builds on the RNS-RNN work; for readers unfamiliar with this previous work (like myself), several details need to be verified to examine some of the claims.
- The results are too weak to back up the claim that “nondeterministic stack RNN can recognize many non-context-free languages.”
- The empirical contribution is not the paper’s strength. The results are on synthetic experiments or tiny-scale natural language tasks. This could limit the paper’s impact.

Details:
- I appreciate the detailed description of RNS-RNN; but there are several details I want to double-check with the authors. Regarding the transition weight function above Eq. 1: can the authors confirm that the transition weight function conditions on the state of the stack, through $\mathbf{h}_t$? 
- I assume each row of $\mathbf{W}_a$ can be seen as a vector representation of an action. For example, are “push(x)” and “push(y)” considered different actions and get different representations in $\mathbf{W}_a$?
- Following the above: if “push(x)” and “push(y)” get different vector representations, each symbol is already embedded into a vector representation. If this is the case, can the authors comment on why it is surprising that RNS-RNN can recognize CFLs with large alphabets?
- How does the theoretical result in Section 3 connect to existing conclusions on real-time PDA and context-free languages ([1] and the older works cited therein)?
- Regarding the results in Figure 1: even the best stack RNN variant (RNS 3-3) achieves mixed results compared to the LSTM baseline (outperforms in 2 languages and underperforms in others). The framing is too strong that stack RNNs can recognize “many” non-context-free languages.
- I would appreciate it if the paper could include an evaluation of non-context-free languages with large alphabets.
- Missing references: using vector states in automata was explored in [2] and [3]

[1] https://arxiv.org/pdf/1302.1046.pdf

[2] https://arxiv.org/abs/1805.06061

[3] https://arxiv.org/abs/1808.09357

clarity,_quality,_novelty_and_reproducibility: - The paper is clearly written but can be more self-contained.
- The experiments are well executed.
- Enough experimental details are provided to reproduce the results.
summary_of_the_review: This paper provides new insights into stack RNNs. I vote for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes the properties of nondeterministic stack RNN, and proposes a new version with stacks of vectors. (1) The paper shows that nondeterministic stack RNN can recognize non-context-free languages. (2) The stack RNN with small stack alphabet can recognize languages with a much larger alphabet. (3) RNN with stacks of vectors show improved performance.
strength_and_weaknesses: Strengths: 

(1) The paper is theoretically solid. The analysis of the ability of nondeterministic stack RNN in recognizing formal language is a useful theoretical contribution. 

(2) The proposed stack of vectors is a useful improvement of nondeterministic stack RNN.

Weaknesses: 

(1) The paper relies heavily on the previous paper of DuSell and Chiang, and is not entirely novel. 

(2) The experiments mostly compare with baseline LSTM, which may not be a strong baseline. 

(3) No discussion of related models such as neural Turing machine. 

(4) It is unclear in what sense the model understands natural language. Can it do better than transformer model in terms of language understanding? 
clarity,_quality,_novelty_and_reproducibility: The authors made strong efforts to ensure the reproducibility of the results reported in the paper. 

The paper is a follow-up of DuSell and Chiang, and is thus not entirely original. But the theoretical results are new. The vector stack is also new. 

The paper is readable, but the presentation of nondeterministic stack RNN can be improved with the help of diagram illustration and simplified instances. Some background on formal language can be helpful. 
summary_of_the_review: The paper makes a solid theoretical contribution. The new version with stack of vectors is empirically useful.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper analyzes the capacity of stack-RNNs, with a particular focus on the existing architecture of the renormalizing nondeterministic stack RNN (RNS-RNN), which they contrast with deterministic stacks. First, they prove analytically that the RNS-RNN is capable of recognizing arbitrary context free languages. Then, they prove that the RNS-RNN is capable of recognizing *intersections* of sets of arbitrary CFLs, which is a language class that is not guaranteed to be context free.

They then look experimentally at the ability of stack RNNs to recognize 6 specific non-context free languages. They find that the nondeterministic stack architecture can recognize these languages with some additional explicit hints during training, and an architecture with multiple deterministic stacks can recognize these languages if given more hints. They develop a new architecture by using a stack of vectors instead of symbols, and show that it improves perplexity on penn tree bank and learns Dyck languages better.
strength_and_weaknesses: Strengths:
- This paper is both clear and precise.
- The computational capacity of neural models in general has seen some increased interest lately.
- The result is interesting to me personally: that in theory as well as in practice, the nondeterministic stacks permit the learning of some non context free languages.
- The proposed architecture points to a possible future in which we continue to develop models inspired by discrete symbolic automata, but replacing more and more of them with continuous representations.


Weaknesses:
- This topic is very niche and might not attract much attention, because it’s such a specific analysis of the capacity of a very specific recent architecture. However, in general people have been paying more attention to questions of computational capacity in neural networks, as evidenced by how widely shared https://arxiv.org/abs/2207.02098 (Neural Networks and the Chomsky Hierarchy) recently was.
- I would like to see a little bit more discussion of the exact level of context sensitivity required for the languages being studied. Are they covered by particular indexed grammars? Can we characterize what particular classes of mildly context sensitive languages can be recognized? 
- PTB, the only “realistic” dataset, is a very weak benchmark if you are using Mikolov’s approach, which has a high rate of unknown token masking and word-level tokenization.

Minor/Questions:
- It’s not really clear to me what you mean when you talk about needing multiple time steps for the deterministic case.
- It might be a good idea to briefly explain things like cross serial dependencies. I understand that the target audience probably knows these concepts, though.
- I felt like I would have benefited from a diagram during the extensive description of all of the different variables involved in these architectures.
- “Restricted form” doesn’t seem to be defined explicitly, and I’m not sure what makes these forms restricted.
- Admittedly, my automata theory is somewhat rusty. However, I recall that intersecting context free languages yields an undecidable problem (due to the post correspondence problem). Could you help me understand why undecidability isn’t an issue when you are proving that every intersection of a finite set of CFLs is recognizable by an RNS-RNN?

clarity,_quality,_novelty_and_reproducibility: - Very high quality.
- Mostly clear, though dense.
- This paper is easily reproducible if the authors release the code, but they do not state whether they plan to.
- I don't feel confident in my ability to assess the originality, but as far as I can tell it is a novel contribution to the space, as it analyzes very recently developed architectures.
summary_of_the_review: This topic is very niche and might not attract much attention, because it’s such a specific analysis of the capacity of a very specific recent architecture. However, in general people have been paying more attention to questions of computational capacity in neural networks. The result is interesting to me personally: that in theory as well as in practice, the nondeterministic stacks permit the learning of some non context free languages.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents a surprising ablility of the nondeterministic stack RNNs, which is it can learn not only CFLs but non-CFLs. It can
recognize languages with much larger alphabet sizes than one might expect given the size of its stack alphabet. Finally, to increase the information capacity in the stack and allow it to solve more complicated tasks with large alphabet sizes mbols. The model achieves a siginificant improvenment in experiments conducted in PTB. The reviewers agree that this is a solid contribution to the community. I would recommend acceptance of this paper to ICLR.
Decision: Accept: poster