- Rating
- 2
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes learning dynamic BDD variable reordering through archive-assisted tabular Q-learning, then distilling the resulting policies into a structural neural controller.
Critical strengths
- The presentation of this paper is generally good.
- The studied topic is interesting.
- Empirical evaluation is extensive.
Critical weaknesses
- The necessity of the RL teacher is unclear (it introduce training overheads). It's not clear whether this extra cost provide sufficient benifits.
- The scalability is unclear. Extrapolation extends only from 30 to 40 variables, mostly using extracted subfunctions.
- The practical efficiency is not convincing. On 31–40-variable instances, the controller has both worse mean excess BDD size than converging group sifting (12.5% vs. 8.5%) and substantially higher mean runtime (423 vs. 54.1 ms).
- The figures in Section 7 apprear to be LLM-generated.
Questions for authors
Please see Weaknesses.
3 comments
Thank you for your rebuttal. Have you checked the figure you generated? The text labels sometimes overlap with the data points and even with the axes.
It appears that most reviewers have limited expertise in evaluating this paper, as reflected by their low confidence scores (2). I will leave the final decision to the AC.
We sincerely thank the reviewer for highlighting the presentation issues with the figure. :) We have uploaded a revised version of the paper in which the overlapping labels have been corrected.
We sincerely thank the reviewer for taking the time to review our paper and provide feedback, particularly given that the subject matter falls outside their primary area of expertise :)
RL teacher:
We would appreciate some clarification regarding the concern about the necessity of the RL teacher. Are you questioning the use of tabular RL rather than direct neural RL, the use of RL-generated supervision rather than alternative training targets, or whether the offline training cost is justified by the resulting controller's performance? These are distinct questions, and we would be happy to address the specific concern in more detail.
Regarding the first possibility, we experimented with direct neural RL, including Double DQN, but found it considerably less stable than tabular RL, likely due to the rapidly changing BDD structures encountered during exploration. Tabular RL was also substantially cheaper, as BDD canonicity allows us to identify states by hashing variable orderings rather than repeatedly running an expensive neural encoder over potentially large BDDs. Regarding the second, RL exploration allows us to discover good orderings while explicitly accounting for swap distance, rather than simply imitating heuristic solutions that do not consider the cost of reaching those orderings. Establishing the effectiveness of RL is also important for the more challenging sequential control problems motivating this research, as discussed in our response to Reviewer 2. Finally, regarding the justification of training costs relative to runtime performance, we refer to our response to Reviewer 2, where we discuss the distinction between reducing combinatorial search and optimizing wall-clock runtime.
Scalability:
We understand that extrapolating from 30 to 40 variables may seem like a relatively small increase. However, BDD complexity can grow dramatically with even a few additional variables, and our evaluation includes BDDs containing over six million nodes. These results demonstrate that our architecture can successfully process and make effective reordering decisions on substantially larger BDDs than those encountered during training. We naturally intend to investigate scalability to even larger problems in future work. Separately, considerable attention was given to the mathematical scalability of the architecture itself. In particular, the compositional node encoder scales linearly with BDD size, while hierarchical attention avoids the quadratic complexity of applying self-attention across all BDD nodes, restricting it instead to the much smaller set of variable levels.
Runtime:
We acknowledge the concerns regarding practical runtime performance. As Reviewer 2 raised similar concerns, we have addressed these in detail in our response to that review, including the intended objectives of this work, the current inference overhead, and the potential for further optimization.
Figures:
We are unsure what the reviewer means by the suggestion that the figures in Section 7 appear to be LLM-generated. The figures were produced programmatically from actual experimental results, with the underlying per-instance data provided in the supplementary material. We would appreciate clarification if the reviewer has any specific concerns regarding their accuracy or presentation.