Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a differentiable easy-first beam search for structure induction, called Beam Tree Recursive Cells (BT-RC). A couple methods are presented to handle the sparse gradient issue in beam search. There are two sources of sparsity: parent composition and the topk filtering of beams. The two groups of methods presented are Gumbel-BT-GRC, which uses straight-through Gumbel topk for parent composition, and Softpath variants, which use a convex combination of beam elements. The models are evaluated against strong structure-sensitive baselines and perform comparably and in some cases favorably.
strength_and_weaknesses: *Strengths*

The accuracy evaluation is thorough, and the results have convinced me that the method is performant. However, one of the biggest drawbacks of latent structure methods is scalability. I would like to better understand the computational complexity of the method and baselines.

*Weaknesses*

The paper needs an analysis of computational complexity. I believe the method has $O(B^2k)$ runtime. How do the other methods compare? A table with asymptotic runtimes / space complexity is a crucial missing component. An empirical study of the runtime (time per iteration vs sentence length) would greatly improve a scalability argument as well.



*Comments*
* The text description of beam search can be placed in the appendix.
* An illustration of the easy-first beam search with Softpath would be a nice figure to have.
* The paper is missing a citation for easy-first beam search [1].
* What is the connection between state space models and beam search mentioned in the last sentence of the paper?
* I believe beam search + softpath can be interpreted as a continuous relaxation of the sum-and-sample estimator [2], generalized to beam search. The sum-and-sample estimator takes the top-k elements from a proposal distribution and samples an extra element to eliminate bias at the cost of added variance. Instead of sampling to reduce bias, Softpath makes a soft decision that reduces bias less than a sample would but does not add variance.

[1] Ji Ma, Jingbo Zhu, Tong Xiao, and Nan Yang. 2013. Easy-First POS Tagging and Dependency Parsing with Beam Search. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 110–114, Sofia, Bulgaria. Association for Computational Linguistics.

[2] Liu, Runjing et al. “Rao-Blackwellized Stochastic Gradients for Discrete Distributions.” ICML (2019).
clarity,_quality,_novelty_and_reproducibility: The paper is clear overall and I believe the work is original, novel, and reproducible.
summary_of_the_review: I advocate for a weak reject. The method approaches key issues in scaling latent structured models, but is missing crucial analyses. I will be happy to increase my score to accept given more analysis on space/time complexity and empirical speed numbers.

Edit: After updated score from 5->6 after author's response.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors present a novel algorithm for recursive neural network processing of sequence inputs. The algorithm combines easy-first parsing techniques with beam search in order to efficiently explore the space of possible latent tree structures during training and inference. They also present soft relaxations of the framework which lead to improved performance. They include an extensive evaluation of their model variants and many baseline models on synthetic and naturalistic language tasks.
strength_and_weaknesses: - Impressive synthesis of existing recursive neural network models and evaluation on a level playing field.
- Novel model with a reasonable selection of variants, with some improvements in performance over baseline models.
- Limited interpretation and evaluation of why this model works (or why other models work).
clarity,_quality,_novelty_and_reproducibility: - Novelty: The proposed model is a rather small increment on that of Choi et al. (2018), who present an easy-first parsing model which induces tree structure representations for its input, but without beam search decoding. The further model variants (e.g. the Softpath variant, which represents a large distribution over tree representations via a score-weighted combination of vectors) are also not especially surprising.
- Quality
	- Interpretation: The paper attempts an impressive synthesis of the space of models and evaluates them on a level playing field. However, too little space is given to analyzing and understanding the results: the conclusion and much of the result paragraphs read as simple lists of inequalities (X does better than Y on Z), with no interpretation or merely an untested gesture at an interpretation (e.g. "the memory-augmented RNN style setup in it may be more amenable for argument generalization").
	- Results: The evaluation is limited to synthetic logical reasoning tasks except for sentiment analysis (SST). It demonstrates modest (if any) improvement over existing models in the tasks (and lags behind others especially in the only naturalistic task tested). No error analysis is given to help us understand why these performance differences should be interesting.
		- Many of the cited papers in this literature evaluate on other naturalistic tasks, e.g. NLI, language modeling; or interpret the latent tree structures induced by their models / use them as unsupervised parsers. I would suggest the authors consider expanding their work to these kinds of evaluations in order for the results to be more comparable.
		- Even for the most successful results (99% accuracy on ListOps), there is no clear explanation or test showing why this model's success is worth considering, apart from a restatement of the model's design ("are able to get near perfect performance in length generalization ... because Softpath can allow gradient signals to (softly) truncated paths or beams (which would otherwise be completely truncated)").
summary_of_the_review: This paper presents what seems to me a small increment on existing recursive neural network models, which yields modest performance increases. Interpretation of the models' successes are extremely limited. While I appreciate the attempt at a broad evaluation of many recursive neural network models, the results are not well synthesized beyond tables of numbers and lists of qualitative results.

On these grounds I recommend rejection. I recommend the authors work on evaluating and interpreting the model results in order to better support future model development, or push for meaningful performance improvements, especially on naturalistic language datasets.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents BT-Cell, which uses a beam-search style technique to calculate the representation of a sequence with recursive neural networks while automatically determine the best backbone structure. Experiments show improvements in some generalization splits on a synthetic dataset (listops), and results on real datasets are on par with existing state-of-the-art methods.

strength_and_weaknesses: ## Strengths

- The proposed BT-cell shows improved performance on listops long sequences, showing a potential on the length-generalization in real NLP applications.

- Very comprehensive survey and comparison to existing work.

## Weaknesses 

- Lack of qualitative analysis on failure cases: while the improvement by the proposed BT-cell is marginal on listops, it would be good to understand which types of sequences BT-cells help to process.

- Most techniques exist in prior work, while lack of gain on real NLP tasks.

- Missing reference: [1] applies a CKY style algorithm for CCG induction, which improved the performance of generalization on two tasks. Their expected execution results is essentially in the same spirit as this work's list of beam, and both pieces of work focus on generalization.

[1] Mao et al., 2021. [Grammar-Based Grounded Lexicon Learning](https://proceedings.neurips.cc/paper/2021/file/4158f6d19559955bae372bb00f6204e4-Paper.pdf). In NeurIPS. 

clarity,_quality,_novelty_and_reproducibility: **Clarity and Quality**: While this paper is generally clear to me, the following points could be improved:
- The steps in Section 3 could be very hard to digest for those familiar with neither Choi et al. (2018) nor Chowdhury & Caragea (2021). More details with equations would be helpful, especially the ones describing how two children nodes are combined into their potential parent. Here are some additional concrete ideas and questions for presentation:
  - How is each beam represented? If I understood correctly it should be something like a list of (node, score) pairs, where the number of nodes is determined by how many composition steps have been taken as of now. Is this correct? If so, I think it would be helpful to include precise math formulation.
  - Including the form of the score function would be good, or at least define the input and output space of the score function.


**Novelty**: Most of the techniques exist before. The contribution of this paper is to combine the idea of beam search with latent tree structure learning in recursive neural networks, and demonstrate the effectiveness on a synthetic dataset.

**Reproducibility**: The authors have included the code and experiment details in their supplementary material. While I haven't had a chance to try it myself, I believe these materials are sufficient enough to reproduce the results.

summary_of_the_review: This paper presents BT-Cell, which uses a beam-search style technique to calculate the representation of a sequence with recursive neural networks while automatically determine the best backbone structure. The contribution of this paper is to combine the idea of beam search with latent tree structure learning in recursive neural networks, and demonstrate the effectiveness on a synthetic dataset. While the proposed BT-cell achieves improved performance on listops long sequences, showing a potential on the length-generalization in real NLP applications, most techniques exist in prior work. The paper also lacks of qualitative analysis or gain on real NLP tasks. 

I hereby acknowledge the value of this work, but recommend a rejection for this paper as I don't think the content and novelty is sufficient enough for ICLR.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new method, called Beam Tree Recursive Cells, for sentence representation recursively using beam search. The BT-cell extracts a beam of parses (using the same mechanism of easy-first parsing, replacing argmax with top-k) when processing a sentence, and then combining all beams at the end for a sentence representation. Although top-k is non-differentiable, the paper shows that it is quite effective enough for training, without the need for back-prop though top-k. The paper demonstrates that BT-cell is effective for artificial tasks Logical Inference, ListOps, and real tasks SST and IMDB. 
strength_and_weaknesses: The BT-cell is a straightforward extension for argmax-based easy-first parsing and thus it is clear and easy to understand. The paper however does't explain why this extension is helpful. 

Firstly, the paper lacks analyses about the impact of beam search and found structures among the beams. For instance, by examining the beams, can we find *good* structures that support required compositionality? What if we vary the beam size? What are distributions of scores? Also, as the paper claims that top-k is good enough although it is non-differentiable, would there be an analysis looking into the beams to support the argument given right below eq (3)? 

The experiment setting is pretty unfair to the baselines. The paper compares several variations of BT-cells (with different beam sizes, top-k operators...) against the baselines. But that is not much different from fine-tuning on test sets, where hyper-params are beam size and top-k operator. For instance, in Tab1 we can see that BT-GRC performs very well on 'C', with '+softpath' it does better on '7,8,...,12' but much worse on 'C'. BT-cell with different beam sizes also yields different results ( tab1 vs tab3). However in the end, all the conclusions are for BT-cell in general, rather than some specific BT-cell configuration. 

The paper claims that CYK approaches are expensive, but there's no complexity analysis for the proposed BT-cell. 




clarity,_quality,_novelty_and_reproducibility: * Clarity: the paper is easy to read, but relation between BT-cell and CYK can be made clearer. The difference between them is: CYK approach *fuses* subtree representations; whereas BT-cell keeps them separated and only *fuses* them in the end. Seeing this way, BT-cell  has a strong similarity to CYK with (1) top-k pruning, and (2) replace pooling. 

* Quality: the quality of the paper can be improved with experiments on hyper-param choices, analyses on the impact of beam mechanism, and the impact of different components (beam size, top-k operator)

* Originality: the work is quite incremental. There are several ways to see how the work related to existing methods in the literature: for easy-first parsing, the work replaces argmax by top-k. The work can also be seen as a restriction of CYK with "beam"-pooling.   
summary_of_the_review: The paper doesn't meet the acceptance standard: 
* its quality should be improved so that the the choices and their impacts are understood better
* the work is quite incremental, i.e. the contribution doesn't seem significant.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents an algorithm (BT-Cell) for recursive neural network processing of sequence inputs, which combines easy-first parsing with beam search in order to efficiently explore the space of possible latent tree structures during training and inference. The method is an extension of Choi et al. (2018), which didn't include beam search decoding. The authors also present several variants (e.g., soft-path). The paper provides experiments both on synthetic and real data.

The discussions centered around the following three concerns:
1. After discussion, reviewers better understood the paper's differentiation from Choi et al., and the authors response on "BT-Cell novelty" and "Softpath novelty" was quite helpful. While the novelty of the paper is meaningful, the reviewers also felt that the approach is not particularly surprising.
2. The bigger concern was about the experiments, as levels of performance are relatively close to prior work and future versions of the paper should probably better highlight the accuracy vs. efficiency tradeoff. This tradeoff is currently difficult to analyze as accuracies and running times are in different tables, and the authors may want to add Pareto fronts as suggested by one of the reviewers. As the models of the paper do not particularly stand out either in terms of accuracy or speed, the reviewers thought that the empirical contribution of the paper is quite limited.
3. Reviewers were all concerned by the points raised by reviewer dDzD on the ablation of beam size k parameter on the test set. First, as the authors conceded during the discussion, the analysis of the k parameters should have been done on dev sets instead of test sets. While the authors might be right that there are “countless examples of published papers […] where ablations are done in test sets”, these published papers often put their ablations in separate tables. Instead, the authors lump ablations and comparison to prior work in the same *test-set* tables, which is problematic. Indeed, the models of the paper are sometimes shown to “win” (i.e., bold font) with k=5 on some metrics, while winning with k=2 on some other metrics. This is akin to cherry-picking k based on the column (metric) one is looking at, which is not acceptable when done on the test set and especially not in comparisons to models of prior work. Given that the authors only tried two different values of k and results between k=2 and k=5 seem correlated, the problem may not be too serious, but reviewers remained quite concerned as experimental gains are already not a strength of the paper and some of the performance increases over prior work are small and sometimes nonexistent.

Given these three reasons, the reviewers converged on a rejection recommendation during the reviewer-AC meeting, and I side with them. 
justification_for_why_not_higher_score: Limited novelty, mixed results, and flaws in the experiments.
Decision: Reject