acceptodds
Under review as a conference paper at ICLR 2027

LogicKAN: Alternating Differentiable Rule Learning and Structural Repair for Compact Boolean Program Induction

Abstract

Boolean rule induction seeks to recover an executable logical program from labeled binary examples. Yet high held-out accuracy can conceal disagreements with the target rule elsewhere in the Boolean domain, and learning with a fixed clause budget can produce unnecessarily large programs. We propose Logic-KAN, a differentiable model that assembles positive and negated literals into shared conjunctive clauses and combines them through OR and XOR heads. Continuous parameters learn which literals and clauses to select and how each head combines its clauses, while a thresholded version exposes the current rule during training. Using only labeled training examples, Logic-KAN scores local edits that add, refine, replace, or remove clauses, adapting its structure as gradient learning proceeds. After training, the discrete model is compiled into an executable symbolic program whose clauses and operators can be inspected directly. Separate checks compare the exported program with the discrete model and, when a target formula is available, use SAT to test equivalence over the full Boolean domain. On synthetic DNF and mixed OR/XOR tasks, SAT finds counterexamples in some runs with perfect held-out accuracy. Compared with existing models, Logic-KAN produces smaller programs on both task families and achieves better exact recovery on DNF.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Program synthesis, Neuro-symbolic learning, Boolean function recovery, Differentiable rule learning, Verifiable machine learning

Reviews

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

This paper proposes Logic-KAN, which learns executable Boolean programs from labeled binary samples. The model uses differentiable parameters to select positive literals, negative literals, and omission states, constructs shared conjunctive clauses, and then combines them with an OR/XOR head. During training, gradient updates alternate with discrete structural edits; after training, it further performs program simplification and data-based full candidate selection. The final program is checked by an independent executor and a SAT solver to evaluate compilation consistency and target-function equivalence, respectively.

Critical strengths
  1. The exact recovery results on DNF are convincing. Across two batches of external comparisons, Logic-KAN recovers 95/100 targets in total, whereas RRL, despite exceeding 99.9% test accuracy, still achieves 0/100 exact recovery. This shows that the metric the paper focuses on does reveal differences that ordinary accuracy struggles to capture.
  2. The local edit scoring has a clear motivation and experimental support. Fixing the outer OR masks the correction of some subprograms, and the paper provides a clear analysis of this issue. In the paired ablation, replacing local scoring with global scoring reduces exact recovery from 47/50 to 20/50, supporting the role of this design.
  3. The verification pipeline is clearly differentiated. The authors separately check the consistency between the continuous and discrete models, between the discrete model and the derived program, and between the derived program and the target function, without equating compilation correctness with successful rule recovery. The blind test on new targets after development, which reaches 147/150, further strengthens the credibility of the results.
Critical weaknesses
  1. Some of the successful results rely mainly on specialized post-training candidate construction, and the contribution of the core learning process needs to be further isolated. In Table 11, after removing the affine-XOR, signed-count, and positive-closure candidates, exact recovery on Parity16, Majority7, and Conjunction drops from 5/5, 5/5, and 3/5 to 0/5, respectively. These candidates incorporate direct construction algorithms tailored to the corresponding function families. Using them is reasonable, but a baseline with "candidate generation and selection only" is currently missing, making it impossible to judge how much additional benefit the preceding gradient learning and structural editing contribute on these tasks.
  2. The main Mixed comparison is insufficient to verify OR/XOR compositional capability. Appendix A.5 shows that the functions produced by this generator can be simplified to seven-clause DNF. Therefore, full recovery on Mixed does not require learning the original XOR structure, and BRCG also achieves 100/100. The added Random XOR blind test provides some supplement, but the external method comparison still lacks tasks that genuinely exhibit the advantages of mixed structure.
  3. The claim about program compactness lacks direct evidence. The abstract claims that Logic-KAN produces smaller programs than existing methods on both task types, but the main text and appendix mainly report structural statistics of this work and do not provide a comparison of program size across methods on the same tasks. Recovering the teacher's clause set is not equivalent to proving that the program is smaller. This gap is especially important because the growth-only control reaches 50/50, higher than the full method's 47/50; if the full method's advantage lies in size, the corresponding trade-off should be shown directly.
  4. The comparison does not yet fully rule out the effects of search budget and post-processing. In addition to gradient training, Logic-KAN uses multiple rounds of structural search, post-training simplification, and full candidate selection, whereas the computational budgets of the methods are not matched. The paper also lacks a purely discrete search control under the same grammar and candidate budget. It is therefore still difficult to judge how much of the advantage comes from alternating gradient and editing, and how much comes from additional search and post-processing.
Questions for authors
  1. If neural training is skipped and only the affine-XOR, positive-closure, and signed-count candidate generators are run with the same selection criteria, what are the results on the classical tasks? Could the recovery rates for these tasks also be reported at the checkpoint, after simplification, and after candidate selection?
  2. What are the differences between the full method and growth-only in terms of program size, recovery rate, and runtime? Under the same grammar and search budget, can purely discrete editing achieve comparable results?
  3. Could a comparison of program size across methods on the same tasks be added, along with an explanation of how programs are counted uniformly across different representations? I would also like to see external baseline results on tasks that genuinely require XOR composition and cannot be easily simplified into small DNF.
Reviewer_vNsGOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper presents Logic-KAN, a framework for learning compact and executable Boolean programs from labeled examples. The method combines differentiable learning with discrete structural editing, allowing Boolean rules to be refined during training. It also uses SAT-based verification to assess whether the learned programs are functionally equivalent to the target functions, rather than relying solely on test accuracy. Experiments on a range of synthetic Boolean tasks show strong exact-recovery performance compared with several existing methods. The authors also provide ablation studies to examine the contributions of the main components.

Critical strengths

The paper focuses on the interesting research problem which use netual networks to learn logic programs. Besides, it uses SAT-based equivalence checks to distinguish perfect test accuracy from exact functional recovery, providing a more rigorous evaluation of learned Boolean programs beyond finite test samples.

Critical weaknesses

1.The paper does not systematically compare program complexity across methods or include some closely related approaches, such as Mat_DNF, in its main quantitative evaluation. Therefore, it remains unclear whether Logic-KAN produces more compact programs or offers a clear advantage over existing methods.

  1. All experiments use synthetic Boolean functions. These results limit the evidence for a general advantage of the proposed framework.

  2. The overall presentation of the paper is not well-structured. Figure 1 has a 'bank' term, which is never explained in the main body. The paper lacks an overall Algorithm to show the details.

Questions for authors
  1. In Table 3, the used baselines almost failed. Why do some baselines perform substantially worse than Logic-KAN, given that their configurations and search budgets are not compute-matched? Could the authors clarify the tuning protocol and include additional closely related methods, such as Mat_DNF.
  2. Data splits and robustness. Some low-dimensional tasks use as few as 48 training, 8 validation, and 8 test samples. Given the reported case where the Conjunction model achieves 100% test accuracy despite failing SAT equivalence, how robust are the results to stratified splits and class imbalance?
  3. What are the key differences and similarities between the proposed model and KAN?
  4. What is the definition of OR/XOR tasks shown in Abstract?
Reviewer_BarVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Logic-KAN alternates differentiable learning and structural editing to learn compact Boolean programs from labeled examples. It uses local scores to guide edits and evaluates the resulting programs on synthetic tasks, including SAT-based checks of exact recovery.

Critical strengths

The idea of alternating differentiable learning and structural editing is intuitive. The local scoring strategy has some novelty, as it addresses errors that can be masked by overlapping heads.

Critical weaknesses
  1. Baseline comparisons need stronger justification. The paper should explain baseline selection and implementation differences more clearly. The coverage of the strongest relevant methods is not sufficiently justified. An LLM-based program-induction baseline would also provide useful context.
  2. The framework’s contribution needs clearer attribution. Some classical tasks depend strongly on specialized candidate generators. Although the paper includes ablations, it should explain more clearly what the general framework contributes beyond these task-specific mechanisms. A generator-only baseline would help establish this added value.
  3. A brief introduction to Kolmogorov-Arnold networks (KANs), followed by a clearer explanation of their connection to Logic-KAN, would improve accessibility. I needed substantial effort to understand this connection.
Questions for authors
  1. What motivates the baseline selection, and how do the evaluated implementations differ from the original methods?
  2. How do the specialized candidate generators perform without alternating learning and editing, using the same examples and capacity limits?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.