Algorithmic Language Models with Neurally Compiled Libraries

## Abstract

Abstract Important tasks such as reasoning and planning are fundamentally algorithmic,
meaning that solving them robustly requires acquiring true reasoning or planning algorithms, rather than shortcuts.
Large Language Models lack true algorithmic ability primarily because of the limitations of neural network optimization algorithms, their optimization data and optimization objective, but also due to architectural inexpressivity.
To solve this, our paper proposes augmenting LLMs with a library of fundamental operations and sophisticated differentiable programs, so that common algorithms do not need to be learned from scratch. We add memory, registers, basic operations, and adaptive recurrence to a
transformer architecture built on LLaMA3.
Then, we define a method for directly compiling algorithms into a differentiable starting library, which is used natively and propagates gradients for optimization.
In this preliminary study, we explore the feasability of augmenting LLaMA3 with a differentiable computer, for instance by fine-tuning small transformers on simple algorithmic tasks with variable computational depth.

## 1 Introduction

Machine learning is relaxed program induction, where, implicitly or explicitly, the goal is to find programs that accomplish a given task [solomonoff1964formal, hochreiter1997long, gulwani2017program, chaudhuri2021neurosymbolic].
For example, a large language model trained on math problems must implicitly learn a calculator program internally.
Furthermore, models may aim to induce more complex internal programs, such as sorting algorithms, planning algorithms, or combinatorial solvers.
However, gradient descent has no guarantee of recovering such programs, and often approximates them via statistical features and other shortcuts [liu2022transformers, zhang2022paradox].
To address the issue of inducing already-known programs from data, we define a scalable adaptive neural compilation algorithm, which compiles code into neural network parameters [gruau1995neural, bunel2016adaptive, lindner2024tracr, giannou2023looped], and use this to augment a large language model with a library of differentiable programs.
Also, we enable the model to learn compositions of subprograms, providing a strong inductive bias for general algorithmic ability [ellis2021dreamcoder].

Language models are optimized to model natural language through objectives like masked-token or next-token prediction.
However, these objectives are often insufficient for the emergence of authentic reasoning ability, even when it may appear superficially [dziri2024faith, liu2022transformers, zhang2022paradox, valmeekam2024planbench, valmeekam2024planning].
In general, this lack of reasoning ability is a fundamental flaw that is not easily mitigated via prompting or fine-tuning [stechly2024chain, dziri2024faith].
First, algorithmic reasoning, by definition, requires an architecture to be universally expressive. However, transformer expressivity is upper-bounded by TC^0 [merrill2022saturated].
Furthermore, there is ample empirical evidence that optimization does not recover even programs within TC^0 [dziri2024faith, zhang2022paradox].

Augmentation aims to address the limitations of large language models. For instance, a language modeling objective is often insufficient to induce a robust calculator sub-program, so it is common to augment a language model with a calculator.
Even when appropriate tools are available, a model must use them correctly, by providing the right inputs to the right tool in the right context.
We call this the parsing/selection problem.
Often, this is approached via prompting, fine-tuning, or bootstrapping [mialon2023augmented].
Of these approaches, bootstrapping and fine-tuning are more effective.
Differentiability is advantageous for fine-tuning, as it allows supervising on answers rather than tool inputs.

Furthermore, separating tools from models raises the question of integration – which component is responsible for reasoning?
Overall, augmentation does not guarantee reasoning ability. For instance on a dataset like GSM8K, having a calculator only helps with intermediate calculations, and the overall model must still decompose the problems into steps, which is itself a reasoning problem.
Because of this distinction, our architecture aims to integrate tools natively, which is made possible because compiled programs can be used end-to-end differentiably.

#### Contributions

We augment LLaMA 3 with a differentiable computer, resulting in a model which is universally expressive, adaptive, and interpretable.
We provide a starting algorithm library, and study how a model can adapt given functions and compose library modules for new tasks.

### 1.1 Neural Compilation

Neural compilation is a technique for deterministically transforming code into neural network parameters that express the exact same program in a given architecture.
Precursors to neural compilation were first discussed in \citeauthorsiegelmann1992computational, and then implemented in Gruau et al. [siegelmann1992computational, gruau1995neural].
However, the first adaptive (trainable) neural compilation technique was first defined in \citeauthorbunel2016adaptive [bunel2016adaptive].
Similarly, there are modern approaches to neural compilation, based on the transformer architecture, but these either focus on interpretability, are not universal, or are not adaptive [weiss2021thinking, lindner2024tracr, friedman2024learning, merrill2022saturated, giannou2023looped].

## 2 Related Work

### 2.1 Previous Neural Compilation Techniques

Adaptive Neural Compilation augments a recurrent neural network with memory, registers, and a differentiable interpreter for a minimal assembly language [bunel2016adaptive].
Then, [bunel2016adaptive] compiles algorithms by solving for weights as linear equations.
This model relied on a lookup-table based ALU, unit vector numeric encodings, dot-product memory/register lookups, and probability mixtures for control flow.
This work focused on learning contextual programs, but in contrast we focus on compilation as a means to specify algorithms to Large Language Models.

RASP/Tracr/CoNN describe a neural compilation technique for unaugmented transformers, aimed at interpretability. Specifically, RASP defines a minimal language [weiss2021thinking], Tracr defines a working compiler [lindner2024tracr], and CoNN exploits the Tracr compiler to augment a transformer.
While CoNN compiled addition and subtraction, their mixture-of-experts approach has a basic calculator directly output the answer as a series of tokens, which is limited only to very simple problems and does not support compositionality or training for new tasks [weng2023mastering].
In comparison, our work is the first to experiment with end-to-end trained large language models augmented with universal programs.

Looped Transformer constructs a universal machine within a recurrent transformer architecture.
However, it is not intended to be adaptive, nor is it explicitly constructed for library learning or integration with pretrained LLMs [giannou2023looped].

### 2.2 Differentiable Computing and Program Synthesis

Differentiable computing is the idea that programs can be approximated by neural networks by defining differentiable primitives that support universal computation, for instance by using softmax for array access.
Recurrent neural networks and LSTMs are early instances of differentiable computers, and generally performed well for several decades, but in the limit cannot learn and generalize arbitrary programs from data [deletang2022neural].
One potential reason for these failures is a lack of inductive bias via expressive primitives, but the critical reason is optimization difficulty [pascanu2013difficulty].

Neural Turing Machines [graves2014neural, graves2016hybrid] construct a sophisticated differentiable computer, and demonstrate its application to complex tasks, such as inducing sorting, planning, or graph algorithms. NTMs are foundational to differentiable computing, however, they are exceptionally hard to train, even in comparison to RNNs and LSTMs [collier2018implementing].
This raises possibility of architectures which achieve both the expressiveness of NTMS and the trainability, parallelism, and capacity of transformers [dehghani2018universal].

Program Synthesis is closely related to differentiable computing, and studies the practice of inducing code from specifications, such as data [ArmandoSolar-Lezama, gulwani2017program, chaudhuri2021neurosymbolic, solomonoff1964formal].
Generally this entails symbolic search, with an emphasis on addressing combinatorial explosion via heuristics or pruning.
However, program synthesis also overlaps with differentiable computing significantly, and neural networks are often used as generators or heuristics of programs [devlin2017robustfill, ellis2021dreamcoder].

Sketching improves program synthesis by providing a human-specified template of the desired output, and having an algorithm fill in this template [ArmandoSolar-Lezama, lezama2008program, solar2009sketching]. Contextual programs in [bunel2016adaptive] and our initial library share heritage and draw inspiration from sketching.

Library learning focuses on organizing acquired skills for compositional reuse [ellis2021dreamcoder, bowers2023top].
By creating abstractions, learning more complex algorithms ideally becomes a matter of recomposing library skills, rather than learning from scratch.
Beyond abstractions found by a learning algorithm, this paper aims to provide a foundation of abstractions, which are compiled into the starting library. This foundation can range from simple arithmetic operations to fully defined planning algorithms.
In either case, the goal is to provide an inductive bias for reliably learning algorithmic tasks.

### 2.3 Large Language Model Tool Use

LLM Tool Augmentation has been explored as an alternative method to improve reasoning ability in neural networks.
For instance, models like GPT have been augmented with calculators or Python interpreters [schick2024toolformer] via a text interface.
The primary difference between neural compilation and typical LLM tool use is that because they are differentiable, neurally compiled components require fewer intermediate labels and support fine-tuning with an integrated tool.
Still, differentiability alone is not a guarantee that correct tool use behavior will be learned from answer supervision, so we do not propose replacing conventional approaches to tool use entirely.

Figure: Figure 1: The proposed architecture, which adds a library of differentiable programs to LLaMA3
Refer to caption: x1.png

## 3 Model

Our model augments the LLaMA 3 transformer architecture with a differentiable computer, $\Delta$, and associated program library $\Lambda$.
Fundamentally, an intermediate layer of the transformer provides inputs to the differentiable computer and selects programs to run.
The differentiable computer $\Delta$ is based on the register machine introduced in \citeauthorbunel2016adaptive [bunel2016adaptive].
This machine interprets a set of assembly instructions $A$. A program $\rho$ is a sequence of these instructions, and the library $\Lambda$ is a collection of programs.
The computer has state $S$ in the form of memory $M$ and registers $R$, and tracks execution with an instruction counter $c$ and halting probability $h$.

$$ $\displaystyle S$ $\displaystyle=(M,R,c,h)$ (1) $$

### 3.1 Library Structure

The fundamental contribution of this paper is a differentiable standard library of programs.
The overall model uses the program library by classifying (selecting) programs and inputs to run.

#### Call Instruction

Creating a differentiable library fundamentally relies on introducing a method for calling functions arbitrarily. To achieve this, we add a call primitive, supported by a store instruction, which stores the current program counter in a given register.
Doing this allows returning from functions by designating a special return address register.
The call primitive simply runs store and moves the instruction counter into the new function, and the called function returns to the stored location when finished.

#### Parsing/Selection Problem

The overall model must parse a given natural language input, and provide appropriate inputs for $\Delta$ in the form of an initial state. Then, the model must select a program $\varrho$.
Even if a perfect program has compiled into the library, the model still needs to select it in context, and provide correctly parsed inputs.
We refer to this as the parsing/selection problem.
In our experiments (Section 4), we first study parsing/selection in an isolated form, where a minimal model learns the correct permutation for a task, and then we study the full parsing/selection problem in the context of transformer models with natural language inputs.

Figure: Figure 2: Differentiable Computer
Refer to caption: x2.png

### 3.2 Model Background

#### Differentiable Memory

bunel2016adaptive defines differentiable memory as a matrix $M_{ij}$, where the dimension $i$ is an address and the dimension $j$ is an encoding.
An address $a$ is a unit vector, produced via softmax output.
Reading from memory at an address is done with the dot product:

$$ $\displaystyle r_{j}=M_{ij}a_{i}$ (2) $$

Writing a vector to memory requires updating all of memory using probability mixtures.
First, for an address $a$, vector $c$ being written to $a$, and overall probability of writing, $p$, a memory update is:

$$ $\displaystyle{\underset{\text{write}}{M}}$ $\displaystyle=(1-a)\odot{\underset{\text{old}}{M}}+a\otimes c$ (3) $\displaystyle{\underset{\text{new}}{M}}$ $\displaystyle=(1-p)\odot{\underset{\text{old}}{M}}+p\odot{\underset{\text{ write}}{M}}$ (4) $$

$(1-a)\odot M$ represents kept (unaltered) memory content, and $a\otimes c$ represents new, written content.

#### Differentiable Registers

Registers are defined as a matrix $R_{ij}$. To write an output $c$ to address $a$:

$$ $\displaystyle R_{ij}$ $\displaystyle=(1-a)\odot R_{ij}+a\otimes c$ (5) $$

Reading from an address $a$ to a value $v$ is done with a dot product: $v_{j}=R_{ij}a_{i}$.
The distinction between memory and registers is that instruction inputs/outputs use registers, not memory. Also, registers are always written at every timestep by any instruction, while memory is only written from read or write instructions when they have non-zero probability.

#### Differentiable Register Machine

The computer executes a set of assembly instructions, $A$, representing the computer’s language.
A differentiable program $\varrho$ is structured as a list of these instructions and their arguments, where each instruction can be accessed at its address.
These addresses are tracked via a special instruction counter, $c$.
Then, a differentiable interpreter $I$ runs instructions $A$ in order to execute the program.
See Listing 3.2 for examples of control flow.

[!h]
There are two special instructions necessary: jump and halt, which control program flow.
The jump instruction takes two inputs: a register holding a conditional flag, and a register holding a program address.
If the conditional flag is true (equal to 1), then the program jumps to the new program address.
Finally, the halt instruction simply finishes the control flow, without executing the remainder of the program.
Since this instruction is probabilistic, it is thresholded when executing programs in practice.
A particular probabilistic instruction $\iota$ is a multinomial distribution over all possible instructions in $A$.
Accordingly, each instruction has an individual probability, and in particular we denote the special scalar portions of $\iota$ as $h$, $j$, and $w$ for the components representing halting, jumping, and writing probabilities.
\usemintedstyle
trac\inputminted[xleftmargin=4pt,
fontsize=, tabsize=2, breaklines, autogobble]pythonneurips_2024.listing
Example Assembly

#### Probabilistic Execution

Instructions, the program counter, and addresses are represented as multinomial probability distributions output by softmax.
Accordingly, the program and interpreter is always in superposition.
Instead of running a single instruction at a time, the interpreter runs everything, everywhere, all at once, but with execution and results weighted by the distributions for instructions, program counters, and addresses.
In the case that every distribution is dirac-delta ($100\%$ probability of one possibility), then execution is fully deterministic.
See Figure 1.

Program execution is tracked as a probability mixture between incrementing the instruction counter and jumping to a new location $l$ in the program, based on the condition probability $p$:

$$ $\displaystyle c_{t+1}=(1-j)\cdot{\underset{\text{next line}}{\underbrace{ \texttt{inc}(c_{t})}}}+j\cdot{\underset{\text{jump destination}}{\underbrace{( (1-p)\cdot\texttt{inc}(c_{t})+p\cdot l)}}}$ (6) $$

#### Differentiable Interpreter

An interpreter $I:S_{t},\iota\mapsto S_{t+1}$ runs each instruction by querying a 4D lookup table. This model is based on one-hot encodings of size $n$, so this lookup table $T$ has dimensions $|A|\times n\times n\times n$.
This table is filled according to each instruction, with special cases for reading or writing to registers/memory. For instance $T_{0},:,:,:$ is the addition table.
To run a instruction, first the register values are resolved to $u_{j},v_{j}=R_{ij}r_{i}\forall r$. The final lookup is:

$$ $\displaystyle o_{l}=T_{ijkl}f_{i}u_{j}v_{k}$ (7) $$

Intuitively, this corresponds to first looking up a particular operation (e.g. add), then the first argument (e.g. $2$), and then the second argument ($2$) to get the answer $4$. Each instruction specifies a register to store the output in, so finally $o_{l}$ is written to $R$ using equation 5. Since each operation $f$ and argument $r$ are independent multinomial distributions, this entire operation is probabilistic, so the output $o$ is potentially a mixture of running different instructions with different registers.

## 4 Experimental Results

### 4.1 Preliminary Studies

Before scaling to billion-parameter models, we explore behaviors of components of our differentiable computer, namely lookup tables, circuits, and small programs.
These experiments use a minimal neural network with one layer before the computer and one layer after, on the premise this will inform behavior at the LLM scale. These networks simply need to route inputs/outputs correctly to/from the computer, which is replaced by parsing in case of LLMs. We find that lookup tables are more learnable than circuits, and that we can learn recursive algorithm routing to a certain depth.

Figure: Figure 3: Circuits vs Tables
Refer to caption: extracted/5698977/figures/circuit_v_lookup.png

Impact of Recursion Depth on Trainability via Fibonacci
We use fibonacci as a method for exploring the effect of computation depth on trainability. While the fibonacci function has a closed form, for our study we treat it as an inherently sequential algorithm, so a recursion depth of 1 entails 8 interpreter steps, and a depth of 2 entails 16 interpreter steps.

**Table 1: Impact of Computation Depth on Trainability (Minimal Network)**
| Depth | 1 | 2 | 3 |
| --- | --- | --- | --- |
| Accuracy | 73.21% | 70.52% | 7.07% |

This degradation in performance is expected, and is meant to establish practical limits of using the differentiable computer. We observe similar results in the context of transformer networks.

### 4.2 Small Transformers

Next we study the behavior of small transformers with natural language inputs. First, we establish that it is possible to train these models to use calculators perfectly, and then we study the effect of computational-depth on trainability.
These experiments use small transformers with between 30 million and 100 million parameters. This architecture is identical to LLaMA 3, but with much smaller scale parameters (e.g. hidden size of 128 or 256 and only two transformer layers). Natural language inputs are tokenized with the 128K vocabulary LLaMA3 tokenizer.

#### Modular Arithmetic

First, we provide the model with a lookup table for mod-128 arithmetic operations and train it on natural language versions of one-step arithmetic, e.g. \sayAdd 3 and 4. Solving this problem is a matter of parsing the sentence to extract the operation and operands, and then providing these to the differentiable calculator. Supervision is given only on answers, via cross-entropy. By 62 epochs, the model can use the calculator with $99.2\%$ accuracy on the test set.

#### Recursive Fibonacci

Next, we experiment with giving the model a fibonacci program.
Again the model must extract inputs from a natural language sentence, e.g. \sayCalculate the fibonacci function, starting from inputs 6 and 2, to a recursion depth of 3, and provide them to a library function.
However, because this function call has a longer gradient path, it is less trainable than modular arithmetic.

**Table 2: Impact of Computation Depth on Trainability (Small Transformers)**
| Depth | 1 | 2 | 3 |
| --- | --- | --- | --- |
| Accuracy | 49.19% | 47.87% | 3.07% |

## 5 Conclusion

In this preliminary study, we investigated the feasibility of augmenting large language models with libraries of differentiable programs.
To some extent, differentiability is effective in assisting fine-tuning.
However, there are empirical limits to differentiability, especially as computational depth increases.
Our experimental results establish an initial threshold for computational depths that remain trainable.
Even within this limit, interesting augmentations are still possible.
For example, we establish that a small language model can be fine-tuned to use a calculator effectively.

Neural compilation reveals interesting connections between programs and neural networks. First is the direct transformation (compilation) from symbolic programs into neural network weights. Second, weights can be decompiled back into abstract symbolic programs.
This suggests the possibility of tightly integrating program synthesis and neural networks in a joint optimization algorithm, of neural networks with non-trivial formal guarantees, and general interpretability [gaunt2016terpret, valkov2018houdini, gowal2019scalable, saldyt2022synthesized, bunel2024verified].

## Appendix A Appendix

## Appendix B Lookup Tables

| $\times$ | 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 6 | 8 |
| 3 | 0 | 3 | 6 | 9 | 12 |
| 4 | 0 | 4 | 8 | 12 | 16 |

A grade-school multiplication table, encoded differentiably for modulo $5$:

$$ $\displaystyle\begin{bmatrix}00001&00001&00001&00001\\ 00001&00010&00100&01000\\ 00001&00100&10000&00010\\ 00001&01000&00010&10000\\ \end{bmatrix}$ $$

#### Differentiable Lookup Tables

Tables trade memory for computation by pre-calculating the answers to input combinations.
Intuitively, these take similar form to grade-school arithmetic tables (right).
To access a lookup table differentiably, one-hot encoded unit vectors are used as indices for lookup via sequential dot products.
For instance the number $2$ encodes to $[00100]$ for encoding $n=5$. A dot product in one axis is equivalent to selecting the row or column containing $2$, e.g. $[02468]$. If the other operand is $4$ ($[00001]$), then a second dot product selects the final element, $8$, which is the answer to $2\times 4$, the two index vectors.
In practice, answers in a lookup table such as this are encoded using unit vectors, making a 3D tensor $M_{ijk}$ where the axes $i$ and $j$ correspond to the first operands, and $k$ is the encoding dimension of the answer. Then, a lookup is the einstein summation:

## Appendix C Numerical Representation

#### One-Hot Number Encodings

Algorithmic ability is closely tied to numeracy.
However, neural networks are not natively good at representing numbers.
Often, numbers are represented using unit encodings, e.g. $[00100]$. This can be desirable for doing dot-product based lookup, or when viewing numbers as features, but it is undesirable for scaling properties.
The sparsity of these representations can be advantageous in some ways (number representations are not entangled), but disadvantageous in others (a single number provides only a single bit of supervision, and geometric distance does not correspond to number distance).
Probabilistic unit encodings are calculated using a softmax layer to normalize a dense vector into a multinomial probability distribution. This can represent a wide range of other distributions.

#### Binary Number Encodings

Binary representations are highly advantageous in classical computer science, as they allow encoding an exponential amount of numbers in a linear space, e.g. for a bit vector of length $n$, we can represent numbers up to $2^{n}-1$.
However, binary representations may be too entangled to be used as features in neural networks, e.g. the binary encodings for $2$ and $3$ ($[10]$ and $[11]$) overlap in the most significant bit. A unit vector has a native interpretation as a direct probability distribution over numbers, while a binary vector has a probabilistic interpretation for each bit. However, a probabilistic unit vector encodes more possible distributions than a binary one.

#### Binary to Unit Conversions

Ideally, numbers are always represented in binary, except for when they are needed as features or for differentiable indexing for lookup tables or memory.
Accordingly, we wish to define bidirectional conversions between binary and unit vectors. In particular, we want to preserve the probabilistic representations of both encodings.
To lookup binary vectors from unit encodings, we simply do a dot-product lookup with a $n\times b$ table of binary encodings.
The reverse direction is less obvious, as we are going from $\mathbb{R}^{\log(n)}$ back to $\mathbb{R}^{n}$.
However, it admits a closed form similar to the binomial distribution, but for independent trials. This represents, intuitively, flipping a coin at each bit to produce different numbers.
For instance, for a 2-bit vector $b$, with bits $b_{0}$ and $b_{1}$, the one-hot conversion is $[(1-b_{1})(1-b_{0})\quad(1-b_{1})b_{0}\quad b_{1}(1-b_{0})\quad b_{1}b_{0}]$, which generalizes to higher dimensions.

#### Freezing Library Programs

A typical gradient update modifies every parameter $\theta$ at once:

$$ $\displaystyle\theta_{t}=\eta\nabla\mathcal{L}(\theta,x)+\theta_{t-1}$ (8) $$

However, simply masking parameters element-wise prevents overwriting neural network sections we would like to keep, such as programs in the library. The mask $\mathcal{M}$ is simply a tensor the same shape as $\theta$, with $1$ for every parameter we’d like to update, and 0 0 otherwise.

$$ $\displaystyle\theta_{t}=\eta\nabla\mathcal{L}(\theta,x)\odot\mathcal{M}+\theta _{t-1}$ (9) $$

We use this to explore different architectures: one where the entire library is frozen and no parameterized contextual programs are learned at all, and another architecture which allows parameterized or contextual programs.
The general definition of the mask allows low-level control, for instance freezing all but one library program, or freezing particular lines or terms of a compiled program.

#### Neural Compilation by Memorization

In many contexts, exact algorithmic behavior is desirable, because of the robustness and generalization that it provides.
However, there are contexts where learning approximate algorithmic behavior is sufficient or even desirable. Also, we may wish to specialize programs to a known, static input distribution.
When either of these goals are true, analytical neural compilation is not scalable.
In general, contextual programs, require far more expressive program controllers.
In this context, we hope to find neural network initializations rather than full solutions.
The architecture of the differentiable computer allows us to provide intermediate supervision in the form of programs, and train $\delta$ directly on programs.
Accordingly, we can approximately compile a program by memorizing it.
In other words, we advocate for intentionally overfitting a sub-network to output a particular program. We call this neural compilation by memorization, and explore the trade offs of using this approach.

$$ $\displaystyle\tilde{\theta}=\min_{\theta\in\Theta}\mathcal{L}(\delta(\theta,e( x)))$ (10) $$

## Appendix D Technical Background

First, we provide background on common building blocks used in differentiable computing, and define our full model in Section E. Lookup tables and memory are primarily derived from the math presented in [bunel2016adaptive] and [graves2014neural, graves2016hybrid, hochreiter1997long].

Differentiable Lookup Tables trade memory for computation by pre-calculating the answers to input combinations.
For binary operations like addition, a lookup table is a 3D tensor $M_{ijk}$ where the axes $i$ and $j$ correspond to the first operands, and $k$ is the encoding dimension of the answer. Then, a lookup is the summation
$c_{k}=M_{ijk}a_{i}b_{j}$.
Now we define a lookup table for multiple operations, e.g. the four basic arithmetic operators, or common fundamental programming operations such as max/min/inc/dec. To do so, a new leading dimension is added for the operator, so a lookup table becomes a 4D tensor $T_{hijk}$, which is indexed via three dot products, corresponding to looking up an operator, and then operands, sequentially. This is written with the Einstein summation:

$$ $\displaystyle c_{k}=T_{hijk}f_{h}a_{i}b_{j}$ (11) $$

When memory is abundant, lookup tables are extremely favorable, as they have shallow and stable gradient paths (since they are only tensor contractions).
An issue with lookup tables, and more broadly with unit vector encodings, is that they scale poorly with respect to the maximum representable number.
If the maximum number is $n-1$, then a unit vector is length $n$ (assuming zero is included). A binary-arity lookup table will be $n\times n\times n$, and a composite lookup table will be $o\times n\times n\times n$ for $o$ operations.
Fundamentally, this is not scalable enough to enable arbitrary multiplication beyond very small scales, e.g. even representing a $n=1024$ lookup table requires $32$Gb of memory. This limitation is a byproduct of unit encodings. Alternatives include using binary number encodings or circuit-like representations for basic operations.

#### Differentiable Circuits

An alternative to lookup tables is to encode basic operations via circuits.
This is done by defining differentiable relaxations of common logic gates, and then building conventional circuits, such as the ripple-carry addition circuit, from them.
This has been explored several times in previous literature, and there are multiple options for defining differentiable logic gates with different trade-offs [blondel2024elements].
We opt for probabilistic interpretations of and, or, not and xor:

$$ $\displaystyle\texttt{and(a, b)}=a\cdot b\quad$ or(a, b) $\displaystyle=a\cdot b+(1-a)\cdot b+a\cdot(1-b)$ (12) $\displaystyle\texttt{xor(a, b)}=(1-a)\cdot b+a\cdot(1-b)\quad$ not(a) $\displaystyle=1-a$ (13) $$

Making larger differentiable circuits is a simply a matter of re-defining classical circuits with these differentiable gates.
Accordingly, we define differentiable circuits for addition, multiplication, subtraction, and long division. Compared to lookup tables, circuits require minimal storage space and generalize indefinitely. However, they require binary representations and have long gradient paths.

Figure: Figure 4: Neural compilation (left) compiles code $\rho$ into perfect weights $\theta^{\star}$. A program controller $\delta$ (center) produces a probabilistic program $\varrho$ (center top), which can be decompiled back into a normal program (center left). $\varrho$ is run on a differentiable interpreter (right) using probabilistic execution (center). Memory, registers, and control flow are all defined probabilistically (right).
Refer to caption: x3.png

## Appendix E Model

### E.1 Differentiable Computer

We introduce a differentiable computer $\Delta$ as program controllers $\delta$ with parameters $\theta$, assembly instruction set $A$, interpreter $I$, and state tuple $S$.
Each state consists of memory $M$, registers $R$, instruction counter $c$, and a halting probability $h$.
Furthermore, we introduce a program library $\mathcal{L}$, which augments the low-level language instructions in $A$ with multi-instruction programs written in terms of $A$. This entails that $\delta$ produces high-level programs, which can call both low-level instructions and programs in the standard library.

$$ $\displaystyle\Delta$ $\displaystyle=(\delta,\theta,A,I,\mathcal{L},S)$ (14) $\displaystyle S$ $\displaystyle=(M,R,c,h)$ (15) $$

A controller $\delta$ is a parameterized function which produces probabilistic programs, from inputs $z$. By introducing $z$, it becomes possible to have contextual programs which vary with the overall input.

$$ $\displaystyle\delta:\theta,z\mapsto\varrho$ (16) $$

Probabilistic programs $\varrho_{ij}$ are represented as matrices, where axis $i$ corresponds to the program counter, and axis $j$ is an instruction encoding.
Accordingly, an individual instruction is obtained by taking a dot-product with the program counter, producing a probabilistic mixture over instructions:

$$ $\displaystyle\iota_{i}=\varrho_{ij}c_{i}$ (17) $$

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: How do you differentiate between the selection of different programs? Do you run all of them at once? If not, how do you expect the LLM to learn which program to select if it’s trained only on the error of the outputs?

What are the novel ideas which one can take away from the methodology of this paper?

How do the experiments demonstrate that your method is “universally expressive, adaptive, and interpretable”?
soundness: 1
strengths: Address an important problem, which is well motivated.
The background section is comprehensive and an interesting read.
It proposes an interesting approach of using a differentiable interpreter, as well as preparing a library of programs to choose from, by compiling symbolic programs into differentiable versions.
summary: The paper addresses LLMs’ problem with performing symbolic operations. To this end, they investigate one way to incorporate a differentiable interpreter into LLMs. Given a text input, the authors use LLaMa 3.2 to select the correct program, out of a library of programs, and to generate the program’s inputs. A differentiable interpreter then runs the program. A final neural network is then used to produce the final output.
The paper presents experiments on arithmetic and sorting, as well as ablation experiments with simpler neural network models.
weaknesses: Poor introduction: most of the introduction, apart from the very last paragraph is dedicated to motivating the work. The very last paragraph has 1 sentence which describes the methodology.

Section 3, Methodology: The authors should make it clear what their contributions are. I am left with the impression that the majority of this section (apart from 3.4) are ideas from a previous paper that are just re-stated here. If this is the case, it should be stated more clearly. In itself, 3.4 is very brief and doesn’t describe the method sufficiently well, for example, I am unsure if the method selects only a single program or runs multiple programs during training.

Experiment section, poor presentation:  the setup of each experiment isn’t described clearly: I am unsure what is the set of programs considered, what the neural architecture is for 4.1 and 4.2, what the inputs and outputs look like, what’s the difference between circuits and tables

Experiment section, no baselines: there are no purely neural baselines. Section 4.2 augments and finetunes LLaMa without showing LLaMa’s performance.

Experiment section, unconvincing results: It is not clear to me that the results support the claim in the Introduction that “resulting in a model which is universally expressive, adaptive, and interpretable”.  Specifically, Table 2 presents the result for sorting, where the accuracy is between 33% and 37% which the authors refer to as “decent performance”. I cannot see a way to reaching this conclusion. This leaves an impression that, while the method could perform well in the future, is currently underperforming and unconvincing.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: On page 4  'instruction counter' and  'program counter' are mentioned. Could you please clarify what is the difference?
Do formulae (3) and (4) assume broadcasting?
On page 8.  There is statement 'fine-tuned LLaMA 3.2 can achieve descent performance'. Could you please clarify, what you comparing agains?
'Furthermore, our results highlight the overall shortcomings of gradient-descent based learning, given that even when the ideal algorithm is already present, there are still scenarios where the model may not learn a perfectly generalizable solution.' This is very interesting finding.  I think both paper and community would benefit if more details on training difficulties, what didn't work, etc would be given.
soundness: 2
strengths: - Reasoning, arithmetic and algorithmic abilities are still weak spot of LLM .  'Algorithmic Language Models with Neurally Compiled Libraries' suggest interesting and promising approach to improve capabilities of LLM. 
- Authors analyse impact of recursion depth on trainability on Fibonacci dataset
- They create library of differentiable modules and augment LLM with them
summary: The authors investigated the feasibility of augmenting large language models with libraries of
differentiable programs.  This is important and very interesting direction.
They augment LLaMA 3.2 with a differentiable interpreter,  develop differentiable algorithm library,
and study how a model can utilise given functions.  This could be potentially great work, but lack of experimentation makes it less appealing.
weaknesses: - Neurally Compiled Library is primary experimental work. Therefore I believe work would greatly benefit from extending it's evaluation on more, preferable public datasets. Also more detailed about experiments performed (for example what dataset was used for Airithmetic testing on page 8)  would make it more interesting.
- It would be helpful to have baselines with/without  differential modules (i.e Figure 3,  Table 2)
- Model background section would benefit from either added citations or clear indication what was proposed in current work. (I.e Differentiable Registers, Probabilistic execution, Differentiable Interpreter sections)

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: - Am I to understand that none of the differentiable intepreter's parameters are trained? If not, which ones are?
- Related to the above, it is still not clear to me which algorithms constitute the compiled library for the experiments in section 4 and, most importantly, how are these algorithms compiled into the model before the training runs.
- In section 4.1, the authors assert that a differentiable circuit ALU generalises "beyond lookup tables". How can this be deduced by figure 3, where text accuracy for differentiable circuits is actually lower than for a lookup tables?
- How did the authors pick the training hyperparameters used in section 4.2?
- In section 4.3, to the authors consider generalising to sorting longer lists at test time (e.g., training on list of size 8 and testing on strings of size 12)
- Again in section 4.3, the authors attribute the weak performance of their augmented model to the difficulty of parsing the natural language description of the problem. Can they provide any evidence (e.g. in the appendix) for this statement via some ablation?
soundness: 3
strengths: The authors' proposal is definitely original, the paper outlines it in a mostly clear manner, and there is reason to believe that such augmentations, once refined and properly scaled, could indeed prove to be invaluable in making foundation models capable of algorithmic reasoning.
summary: In this paper, the authors propose to augment LLMs with a differentiable computer equipped with a pre-existing library of functions, as way to to make large foundation models more capable of reliably performing classical algorithms and therefore, in the view of the authors, reasoning. This is in contrast with other tool-use or neurosymbolic approaches, in which LLMs are equipped with an external module (e.g. a calculator, or web browser, or Python interpreter) whose workings are fully interpretable, but which cannot be differentiated through.
weaknesses: Ultimately, the author's proposal does not seem to work well enough given the evaluations they present, and by their own admission their paper is more of a initial proof of concept (and a limited one at that) rather than a practical demonstration of the soundness of their approach. In this regard, I cannot provide any more suggestions for improvement than the authors already do in section 6; the paper in its present state is ultimately more suited to be a workshop publication than a main conference paper.
A related point I wish to make is that the authors do not seem to address, either in the introduction or in their experiments, the issue of length generalisation, which is the main problem to solve in order to make LLMs capable of actually running algorithms rather than just find solutions via shortcuts and pattern matching. Showing that their augmented model is capable to length-generalize, even just on a very simple task such as integer sorting or parity, would significantly enhance this paper's contribution.

---

confidence: 4
contribution: 1
initial_rating: 1
presentation: 1
questions: * For such a parse/unparse model, why do we need differentiable programs? 
* What is the performance of baselines from the LLM Tool Argumentation field?
soundness: 1
strengths: This paper targets an important problem, integrating programs with neural networks.
summary: This paper trains transformers to parse textual inputs into (1) inputs of programs and (2) which program to use from the library. The program's outputs are also unparsed into texts by transformers. 

Specifically, it mainly finetunes Llama (by changing its last layer) to map "Add 3 and 4" into (1) a categorical distribution over programs in the library and (2) categorical distributions over base-128 integers as the programs' inputs. The program's output is a categorical distribution over base-128 integers as well and is then unparsed into texts by neural networks. 

It evaluates such a model in two tasks: 
* Modular Arithmetic (providing arithmetic lookup tables in the library): 100% accuracy
* Sorting (providing insertion sort in the library): ~35% accuracy.
weaknesses: My main concern is about the novelty and the meaningfulness of this work: 
- This paper trains/finetunes transformers to parse/unparse between texts and program inputs/outputs. I do not see the difference between this work and other LLM Tool Argumentation works. Parsing and Unparsing have become much more reliable and accurate with LLMs, let alone the problem here is just to choose one program from the library and retrieve arguments of programs from the text. Differentiable programs may provide more information for program search but they still underperform discrete-search-based methods to synthesize conventional programs. The program search problem here is again too easy to consider those nuances of different program synthesis methods... 

Other concerns include
* The performance is not satisfying. For example, to learn sort with the ground-truth sort algorithm in the library, the accuracy is still lower than 40%. 
* This paper is poorly written and hard to understand. After thoroughly reading the paper, I am still unsure of e.g., 
  - the components of the library, just arithmetic operators, or with sort, or also including some basic logical operators? 
  - why differentiate sorting using differentiable register machines instead of many other works that potentially provide better gradient estimations? 
  - Definition of test accuracies for e.g., sort; 
  - Opinions/Arguments without evidence such as: "While we do not explicitly study them in this work, they almost certainly play a role."

Meta-review: This is a very interesting paper leveraging pre-compiled differentiable neural libraries as part of a language model architecture. In my opinion, this is definitely an idea worth pursuing further. However, it is also evident that the paper's evaluation is still preliminary, with the majority of the Reviewers still voting to reject the paper. I will concur with them and recommend rejection now, but strongly encourage the Authors to pursue this research further and resubmit at the next suitable opportunity!

Decision: Reject