acceptodds
Under review as a conference paper at ICLR 2027

Learning To Control BDD Size

Abstract

Binary Decision Diagrams (BDDs) are canonical representations of Boolean functions widely used to compactly and exactly represent and query large state spaces across computer science and artificial intelligence. Their principal limitation is a severe dependence on variable ordering, under which the same function can admit exponentially different representation sizes. Dynamic variable reordering (DVR) addresses this problem using hand-designed heuristics that search over orderings through sequences of adjacent variable swaps, often requiring substantial reordering effort to obtain high-quality solutions. We instead formulate DVR as a sequential decision-making problem and investigate whether good reordering decisions can be learned and generalized. First, we show that tabular reinforcement learning can discover orderings that closely match the strongest established heuristics while requiring only a small number of swaps at execution. We then distill these learned action values into a neural controller built around a compositional bottom-up encoder of BDD subgraphs and hierarchical attention that aggregates and contextualizes variable-level structure. The resulting policy generalizes to unseen Boolean functions and to larger variable counts than observed during training, retaining near-teacher reordering quality while using only a small fraction of the swaps required by competitive search-based heuristics. These results suggest that expensive online combinatorial search over symbolic representations can be substantially replaced through learned control.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Reinforcement Learning, Neural Combinatorial Optimization, Neuro-Symbolic AI, Compositional Modeling, Graph Representation Learning, Sequential Decision Making, Binary Decision Diagrams

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_e8bEOpenReview ↗
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

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.

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.

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

This paper tackles variable ordering for binary decision diagrams. The core difficulty is that BDD size is extremely sensitive to variable order, so the same function can differ in size by an exponential factor from one ordering to another. Finding the size-minimizing ordering is NP-complete, and naive search is made worse because unfavorable candidate orderings can blow up the intermediate diagrams, making search cost depend on representations that may be enormous. Standard dynamic variable reordering avoids recompilation by swapping variables in place, but existing heuristics still perform heavy online search, often thousands of swaps or more. The authors recast reordering as a sequential decision problem and learn a controller instead. They model it as a Markov decision process, train an archive-assisted tabular Q-learning teacher, then distill it into a neural controller that encodes BDD subgraphs bottom-up and uses hierarchical attention to model variable-level interactions. On unseen functions, larger variable counts, and a different domain, the controller stays competitive with the strongest heuristics using only a small fraction of their swaps. The remaining cost is neural inference, so the large drop in swaps does not yet yield an equally large drop in wall-clock time.

Critical strengths

The paper proposes a clean, scalable MDP formulation and teacher-signal design. It uses long-range source-to-destination moves instead of per-swap decisions. The reward decomposes into size gain, swap cost and move cost; setting γ=1 lets size terms aggregate into the net reduction. Archive values are estimated from stored endpoint sizes via permutation LCS and swap distances, avoiding intermediate BDD construction. This cuts the action space from O(n²) to two O(n) decisions and yields a lightweight, stable teacher signal — the paper’s strongest contribution.

Critical weaknesses

A key limitation is that the method’s strong reduction in swap count fails to deliver better wall-clock runtime. Though the controller drastically cuts reordering operations and avoids costly online search, neural encoding and inference introduce overhead. On small benchmarks, its mean and median runtime lag behind window-based and sifting heuristics, beating only slower annealing and genetic search. The authors report speedups over equally good baselines on just 303 functions (median 1.87×), and these gains are again against annealing and genetic search. Practical usability, judged by wall-clock time, is therefore limited. The authors note this stems from prototype inference overhead and requires tighter integration with the BDD library and optimized inference.

Questions for authors
  1. Under an equal wall-clock budget, does the controller remain competitive?
1 comment

We sincerely thank the reviewer for taking the time to carefully read and critique our work, and particularly appreciate their thoughtful engagement with the paper's central contributions and intended scope :)

Runtime:

You and Reviewer 3 appear to share similar concerns regarding runtime performance, so we will address these together here to avoid unnecessary repetition.

First, we would like to emphasize that the primary objective of this paper was to investigate whether reinforcement learning and deep learning can learn to navigate the BDD variable-ordering space without extensive online search. Our primary goal was therefore to drastically reduce the number of variable swaps required to achieve competitive BDD size reductions, rather than to outperform decades of optimization in established BDD packages such as CUDD on wall-clock runtime. The former is fundamentally a question of learning effective decision-making strategies, while the latter is largely an optimization problem. As noted in the paper, we believe there remains considerable potential for reducing runtime through more efficient implementations, architectural optimization, and tighter integration with the BDD package, for example by caching reusable node embeddings alongside the BDD nodes themselves.

As already stated in related work, neural-guided SAT solving provides a useful precedent. Early work such as Graph-Q-SAT (NeurIPS 2020) demonstrated that reinforcement learning could substantially reduce SAT search effort, even though neural inference overhead limited its practical runtime benefits. Subsequent work, including NeuroBack (ICLR 2024) and Tönshoff and Grohe (ICLR 2026), developed more efficient forms of neural guidance and demonstrated practical improvements in solver performance. We believe BDD reordering presents a similar opportunity: establishing that learned decisions can substantially reduce combinatorial search is an important contribution in its own right, while improving inference efficiency remains a separate direction for further research.

Finally, we see this work as a first step toward a broader objective that goes beyond runtime optimization: learning to navigate the variable-ordering space during BDD construction to prevent combinatorial explosion. Such explosions can render computations entirely infeasible, and existing BDD packages lack mechanisms for proactively anticipating and avoiding them. We believe our results provide an important foundation for tackling this considerably more challenging problem.

Equal wall-clock budget:

Figure 2 already compares solution quality and runtime across all three test sets. We also report that the neural controller is faster than the fastest heuristic achieving at least the same solution quality on 303 instances. Could the reviewer clarify whether they are requesting an experiment with fixed runtime budgets or further analysis of the existing results? Conventional DVR heuristics are not designed to progressively optimize within arbitrary time budgets, although the converging variants we already evaluate provide a comparison against more extensive search by repeating reordering until no further improvement is achieved.

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

This work proposes a transformer-based solution for controlling the size of binary decision diagrams. The authors implemented a Q-learning-based teacher model to train a transformer as a neural controller for this task via policy distillation. The proposed neural controller was trained on a derived dataset compiled from various benchmarks. The authors evaluated the trained model and compared it with 17 traditional heuristic baselines. Experimental results show that the neural controller achieves competitive final BDD sizes and requires fewer adjacent swaps than strong search-based heuristic baselines.

Critical strengths

Given the complexity of dynamic variable reordering in controlling BDD size to find the globally optimal result, which may be difficult to find within an acceptable time budget, adopting a neural network for this task to find a relatively small BDD is a realistic approach. The designed methods from Q-learning teacher, transformer-based neural controller, to the policy distillation is clear and logical. This work has also widely evaluated their approch with 17 baseline.The current manuscript is well organized.

Critical weaknesses

The current neural controller is trained with policy distillation based on Q-learning methods. Even though the current experiments show it performs well in evaluation compared with traditional heuristic baselines, I still want to know if this neural controller will be limited by the performance of the teacher. A direct comparison among the teacher and the policy-distillation-trained student neural controlle may be able to indicate differences in the performance of the proposed method in this work. And if the teacher cannot successfully reduce the size of a BDD in some complex cases, will the neural controller also fail?

In addition, Figure 2 combines six tables and three figures together, which is a bit difficult to follow. And the authors have not, at least, briefly introduced the baseline methods that were used in evaluation. Maybe it's better to reorganize the experiment results section for better understanding.

Questions for authors

Will the performance of the neural controller be influenced by the quality of the Q-learning teacher? Is the performance of the transformer-based neural controller better than, equal to, or worse than that of the teacher? If the teacher cannot successfully reduce the size of a BDD in some complex cases, will the neural controller also fail?

3 comments

We sincerely thank the reviewer for taking the time to review our work and provide constructive feedback :)

Teacher–student relationship:

The quality of the teacher naturally influences the performance of the student, as is generally the case with policy distillation. However, the student's performance is not strictly bounded by that of its teacher. While the tabular teacher learns independently for each BDD through extensive exploration, the neural controller learns shared structural representations from thousands of functions. It can therefore generalize beyond the decisions discovered by an individual teacher, although it may also inherit weaknesses in the training supervision.

We have additionally run the tabular RL teacher on the test functions for a direct comparison. As expected, the teacher generally achieves better final BDD sizes, with a difference of roughly 6 percentage points in mean excess. However, the neural controller outperforms the teacher on over 100 instances, including around 20 cases where the teacher achieves more than 10% excess while the neural controller achieves less than 2%. The overall performance gap is unsurprising given that the teacher performs extensive instance-specific exploration, involving millions of variable swaps, whereas the neural controller relies entirely on learned predictions.

Presentation of experimental results:

We understand your concern that Figure 2 may appear somewhat dense. However, it follows a consistent structure across the three evaluation sets, each containing a scatter plot showing the trade-off between BDD size and reordering effort, an accompanying table of exact values, and a runtime summary. We believe this provides a compact and informative presentation while allowing direct comparisons across evaluation settings. Separating these components into multiple figures would require considerably more space and make comparisons less convenient, while combining them further would only increase the visual density. We have therefore retained the existing layout but clarified its organization in the accompanying text. If the reviewer has any specific suggestions for improving the figure's presentation, we would be happy to consider them.

Regarding the baseline heuristics, Section 3.2 already introduces the main approaches, including sifting, symmetric and group sifting, converging variants, simulated annealing, and genetic search. We agree that the remaining methods could be better explained and have expanded this section to briefly introduce window-based reordering, lazy sifting, and the randomized baselines.

Thanks for the author's response. I agree that a teacher's quality will influence a student's performance, but a student's performance is not strictly bound by their teacher. However, my last question has not been answered. I asked these questions in my review comments actually just because I was wondering about the generalization of the proposed neural controller. The author answered that the student may outperform the teacher in some cases. However, my last question has not been answered: What will the neural controller perform in cases where the teacher cannot work directly because of, for example, memory or time limitations?

For the figures, I think you can modify the size of the figures and tables to reduce the blank gap between them. Moreover, I'm a little bit confused about the data point you showed in the figure. There are 18 points, but there are only 11 methods in the corresponding table. If you cannot list the measured data for all methods, maybe it's better for you to not plot all methods in the figures. You can put the complete data and figure in the appendix. In addition, as mentioned by Reviewer 3, you can also adjust the label position and the font to improve visibility.

Therefore, I will maintain the current score.

We sincerely thank the reviewer for their additional comments and suggestions :)

Figure: Thank you for your suggestions regarding the figure. We agree that its presentation could be improved, and have addressed the overlapping labels in the newly uploaded version of the paper. We have also increased the size of the scatter plots to make better use of the available whitespace and improve readability.

Regarding the number of plotted methods, we would prefer to retain all 17 heuristic baselines in the scatter plots, as these methods are familiar to researchers working with BDDs and provide a more complete picture of the performance trade-offs. However, you raise a good point regarding the availability of the corresponding numerical results. We have therefore clarified that the tables in the main figure present a representative subset of methods and added complete tables containing the results for all heuristics in the appendix.

If the reviewer has any further concerns or suggestions, we would be happy to address them in the final version of the paper.

Unanswered Question: Regarding your last question, the original question was:

‘If the teacher cannot successfully reduce the size of a BDD in some complex cases, will the neural controller also fail?’

The reasonable interpretation of this question is whether the neural controller will also fail to find a good variable ordering when the teacher fails to do so. Our response directly addressed this by providing empirical evidence that the student can outperform the teacher, even in cases where the teacher achieves poor reductions.

The follow-up now asks a different question, namely whether the controller can operate on instances where the teacher is computationally infeasible due to time or memory constraints. This concerns computational feasibility rather than solution quality, and appears to be a different question from the original one. Unfortunately, with less than 24 hours remaining in the discussion period, we won’t be able to conduct the additional experiments necessary to investigate this new question empirically.

We can, however, offer some clarification. First, what constitutes a teacher "failure" is somewhat ambiguous. If this refers to the teacher being unable to achieve any reduction in BDD size, such cases are difficult to identify in practice. BDD sizes are extremely sensitive to variable ordering, and the space of possible orderings is highly diverse. Unless a function has an ordering-independent representation size, there will generally be opportunities for improvement, making complete failure to achieve any reduction uncommon under sufficiently extensive search. If, instead, failure refers to the teacher producing a relatively poor ordering compared with the heuristic baselines, this is precisely the scenario addressed by our original response, where we demonstrated that the neural controller can outperform the teacher even when the latter achieves relatively poor results.

Regarding computational limitations, the teacher was deliberately provisioned with sufficient resources to achieve strong results across the evaluation instances, including difficult cases, with computational budgets substantially exceeding what was required for most instances. In the vast majority of cases, the teacher successfully identified variable orderings matching the best final BDD sizes obtained by the heuristic baselines. Importantly, our tabular implementation exploits the canonicity of reduced BDDs: for a fixed Boolean function, each variable ordering uniquely determines the corresponding reduced BDD. We can therefore identify and cache previously explored states by hashing their variable orderings, without storing the potentially enormous BDD structures themselves. This substantially reduces the memory required for tabular learning, and we have not encountered cases where teacher training was prevented by memory limitations. Nevertheless, as we scale to larger and more complex problems, the number of states that must be explored and stored may make memory requirements increasingly significant. As discussed in our conclusion, one promising direction for addressing this is to use neural guidance to focus tabular exploration on promising states, thereby reducing the number of states that need to be explored and stored.

More generally, the question also relates to the generalization properties of policy distillation. A teacher's failure on a particular instance does not necessarily imply that its student will also fail, as our experiments demonstrate, although the quality and coverage of teacher supervision naturally influence the student's generalization.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.