Algorithmic Language Models with Neurally Compiled Libraries

Authors: Lucas Paul Saldyt, Subbarao Kambhampati
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords: neural compilation, program synthesis, reasoning, algorithms, planning, large language models, fine tuning, tool use

Abstract:
Important reasoning tasks such as planning are fundamentally algorithmic, meaning that solving these tasks robustly requires inducing the underlying 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 the inexpressivity of the transformer architecture. To address this lack of algorithmic ability, our paper proposes augmenting LLMs with an internal reasoning module. This module contains a library of fundamental operations and sophisticated differentiable programs, so that common algorithms do not need to be learned from scratch. To accomplish this, we add memory, registers, basic operations, and adaptive recurrence to a billion-parameter scale transformer architecture built on LLaMA3.2. 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 paper, we study the feasibility of this augmentation by fine-tuning an augmented LLaMA 3.2 on simple algorithmic tasks with variable computational depth, such as a recursive fibonacci algorithm or insertion sort.

Decision: reject
Reviewer scores: 5, 6, 3, 1

Reviews and discussion:
<thread>
creation date:
1729650704742

thread_type:
official_review

<thread_object>
creator: reviewer_h5y9

<content>
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.

strengths:
This paper targets an important problem, integrating programs with neural networks.

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."

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730576258136

thread_type:
official_review

<thread_object>
creator: reviewer_lpaq

<content>
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.

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.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730664258674

thread_type:
official_review

<thread_object>
creator: reviewer_vhlj

<content>
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.

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

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)

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709918254

thread_type:
official_review

<thread_object>
creator: reviewer_efcq

<content>
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.

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.

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.

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”?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732149294189

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Overall Response to Reviewers

comment:
We greatly appreciate the diligent effort and constructive nature of all four reviewers, and thank them for their time. All four reviewers agree that the work is overall “well motivated”, “an important and interesting direction,” and “original, clear and .. could prove invaluable in making foundation models capable of algorithmic reasoning”. However, all four reviewers also mention that the work is preliminary, especially when it comes to positive experimental results. While we see the reasoning for this assessment, we have expanded the experiments, and believe the work has significant value to the research community as it stands. In particular, we’d like to highlight that certain experiments, such as recursive fibonacci or differentiable insertion sort are intended to demonstrate the limits of differentiable computing, namely that differentiability is most effective for shallow and highly parallel algorithms, but struggles as computational depth increases. While this is expected, this insight/confirmation will shape our future work, namely into highly parallel differentiable computers.


We would like to also highlight that, to our knowledge, the idea of augmenting an LLM with a neurally compiled library is entirely novel and has benefits over the current state-of-the-art in algorithmic reasoning. We discuss the most closely-related paper (Transformers Meet Neural Algorithmic Reasoners [1]). In comparison to this work, we are actually attempting to solve a more difficult problem, and do so more efficiently. In particular, the symbolic inputs are not pre-parsed into graph form, and in our setup, parsing must be learned implicitly, which is exceptionally difficult! Beyond this, instead of approximating an algorithm via supervised learning (which requires significant computation and does not carry guarantees), we use neural compilation to create a perfect differentiable version of the algorithm, which provides guarantees and is efficient because it does not involve training to create the algorithmic module.  Because of the ambitious nature of this problem setup (learning parsing/selection from final inputs alone), we consider the sorting results promising and demonstrative even if they are very underwhelming for any practical application. 

Beyond a scenario where a single algorithm is selected and used, our ambition was to provide a diverse library of programs that could be selected and composed to be used in more difficult problems. We believe that this potential for composing algorithms is the ideal way to solve the issue of algorithmic reasoning ability in large language models, which is arguably one of the most important contemporary problems in our field. 

Again, we greatly appreciate the effort given by all reviewers, and hope you are convinced that our work, while preliminary, offers value to the ICLR research community.

[1] Bounsi, W., Ibarz, B., Dudzik, A., Hamrick, J. B., Markeeva, L., Vitvitskyi, A., ... & Veličković, P. (2024). Transformers meet Neural Algorithmic Reasoners. arXiv preprint arXiv:2406.09308.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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!