Terminating Differentiable Tree Experts

Jonathan Thomm, Michael Hersche, Giacomo Camposampiero, Aleksandar Terzic, Bernhard Schölkopf, Abbas Rahimi

Introduction

Neuro-symbolic AI seeks to combine the statistical learning capabilities of neural networks with the logical rigor of symbolic reasoning. A significant milestone in this field was the Differentiable Tree Machine (DTM), which utilizes Tensor Product Representations (TPR) to execute Lisp-like operations (such as car, cdr, and cons) on tree structures within a differentiable framework.

Despite its promise, the original DTM faced two critical scalability issues: linear parameter scaling and the "Oracle Problem." To perform $N$ reasoning steps, the DTM required $N$ distinct transformer layers, leading to parameter explosion for complex tasks. Furthermore, the model lacked an internal mechanism to decide when to stop, requiring researchers to provide the exact number of steps for every task. This paper introduces Terminating Differentiable Tree Experts (TDTE), which addresses these limitations through a Mixture of Experts (MoE) architecture and a novel "sluggish" halting mechanism.

Methods

Differentiable Tree Experts (DTE) via MoE

To decouple model size from computation depth, the authors replace the stack of unique transformer layers with a Mixture of Experts (MoE). In this architecture, a shared "router" selects and weights a subset of experts from a fixed pool at each computational step. This allows the model to reuse parameters across different stages of reasoning, maintaining a constant parameter count regardless of the number of steps required.

Architecture of the TDTE showing the router, MoE transformer blocks, and TPR execution.

Sluggish Termination

Learning an autonomous halting condition is notoriously difficult in differentiable systems; if a model shifts its stopping point too rapidly during training, gradients become unstable. The authors propose a "sluggish" halting mechanism inspired by speculative execution. It employs two predictors:

  1. The Explorer: Evaluates whether an alternative number of steps improves the loss.
  2. The Damper: Only adopts the Explorer's suggested step count once a high confidence threshold (0.8) is reached.

This "slow-to-change" approach provides the model with the stability needed to master intermediate logic before adjusting the total reasoning depth.

Visualization of the sluggish halting mechanism's termination probability across training steps.

Evaluation and Key Results

The TDTE was evaluated on standard DTM benchmarks (e.g., CAR-CDR-SEQ) and a new, more rigorous Tree Reversal task. This new task requires the model to perfectly reverse a binary tree, involving up to 56 steps, which tests structural understanding rather than simple leaf-node invariance.

  • Parameter Efficiency: For complex tasks, TDTE required only 27M parameters, whereas the original DTM scaled to 47M to achieve similar depth.
  • Competitive Accuracy: TDTE matched the performance of the original DTM on standard tasks, often reaching 100% accuracy, despite the absence of a step-count oracle.
  • Structural Generalization: On the 56-step Tree Reversal task, the DTE model achieved 1.00 accuracy, significantly outperforming the original DTM (0.79) when both were scaled to larger hidden dimensions.
  • Autonomous Halting: The sluggish termination mechanism successfully converged to the optimal number of steps for standard tasks, proving that the model can learn to stop autonomously.

Discussion and Future Work

The research highlights that while weight sharing is necessary for efficiency, it requires the flexibility of an MoE approach to converge effectively. Furthermore, the authors identified that previous models often relied on leaf-node invariance rather than true structural generalization—a weakness exposed by the Tree Reversal task.

However, challenges remain. Training stability is still sensitive to initialization, and the sluggish termination mechanism struggled to converge on the most complex reasoning tasks. Future work may involve integrating Fractional Power Encoding (FPE) to expand the model's symbolic capabilities to include arithmetic and more diverse rule sets.

Summary updated

Abstract

We advance the recently proposed neuro-symbolic Differentiable Tree Machine, which learns tree operations using a combination of transformers and Tensor Product Representations. We investigate the architecture and propose two key components. We first remove a series of different transformer layers that are used in every step by introducing a mixture of experts. This results in a Differentiable Tree Experts model with a constant number of parameters for any arbitrary number of steps in the computation, compared to the previous method in the Differentiable Tree Machine with a linear growth. Given this flexibility in the number of steps, we additionally propose a new termination algorithm to provide the model the power to choose how many steps to make automatically. The resulting Terminating Differentiable Tree Experts model sluggishly learns to predict the number of steps without an oracle. It can do so while maintaining the learning capabilities of the model, converging to the optimal amount of steps.
BibTeX
@inproceedings{thomm2024terminating,
  author = {Jonathan Thomm and Michael Hersche and Giacomo Camposampiero and Aleksandar Terzic and Bernhard Schölkopf and Abbas Rahimi},
  title = {{Terminating Differentiable Tree Experts}},
  booktitle = {NeSy},
  year = {2024},
  url = {https://openreview.net/forum?id=rSNmKLbGAs},
}
Figure