Executing Arithmetic: Fine-Tuning Large Language Models as Turing Machines

Authors: Junyu Lai, Jiahe Xu, Yang Yao, Yunpeng Huang, Chun Cao, Jingwei Xu
Primary area: foundation or frontier models, including LLMs
Keywords: large language model, arithmetic, learn to execute

Abstract:
Large Language Models (LLMs) have demonstrated remarkable capabilities across a wide range of natural language processing and reasoning tasks. However, their performance in the foundational domain of arithmetic remains unsatisfactory. When dealing with arithmetic tasks, LLMs often memorize specific examples rather than learning the underlying computational logic, limiting their ability to generalize to new problems. In this paper, we propose a Composable Arithmetic Execution Framework (CAEF) that enables LLMs to learn to execute step-by-step computations by emulating Turing Machines, thereby gaining a genuine understanding of computational logic. Moreover, the proposed framework is highly scalable, allowing composing learned operators to significantly reduce the difficulty of learning complex operators. In our evaluation, CAEF achieves nearly $100\\%$ accuracy across seven common mathematical operations on the LLaMA 3.1-8B model, effectively supporting computations involving operands with up to 100 digits, a level where GPT-4o falls short noticeably in some settings.

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

Reviews and discussion:
<thread>
creation date:
1730188611872

thread_type:
official_review

<thread_object>
creator: reviewer_f4pl

<content>
summary:
The paper proposes a new framework, called CAEF (Composable Arithmetic Execution Framework), for enabling large language models (LLMs) to perform arithmetic computations. The framework uses the model to emulate a Turing machine, where an input problem (e.g. 89+2) is solved through a series of <state, command> pairs. States and commands represented in a string format are fed to the model, which performs the computation (transitions) with trained modules for input/output alignment and operation execution. These modules are implemented as LoRA adapters, which are trained separately for different operations, (e.g., there are different adapters for addition and multiplication). Experiments are conducted on LLaMA 3.1, where the framework performance is evaluated per operation in comparison to (a) LLaMA 3.1 fine-tuned with LoRA adapters in an end-to-end fashion, (b) the instruction-tuned version of LLaMA 3.1, and (c) GPT-4o. CAEF often shows substantial gains in performance compared to the baselines, mostly in problems involving numbers with over 10 digits.

strengths:
* The proposed framework is interesting and creative.

* The results show substantial improvements for numbers with >10 digits.

weaknesses:
* While the paper is very interesting, I found it hard to digest as I was struggling to understand the proposed framework and exactly how it is being implemented. Specifically, while I was reading I felt like everything is described on an abstract level, without any grounding in concrete examples or settings. Only at the end of the implementation section (3.3) and after looking at the examples in the appendix, I saw some concrete examples of how the framework is executed. It will be helpful to be more explicit and clear about what a state is, what a command is, what the input and output from the models are exactly, whether there is a single execution of the model or multiple inference passes, etc. There are descriptions of what a state should include and in sections 3.2 and 3.3 there are illustrations for specific examples, but the illustrations are abstract and the explanation is vague.

* If I understand correctly, given a problem (e.g. 89 times 2), the model is executed multiple times, where every transition corresponds to a single inference pass. If this is correct, then I am not sure if the experiments make a fair comparison with the baselines. CAEF executes the model many times using a fine-grained step-by-step solution, while the other baselines solve the problem in an end-to-end manner. Looking at the prompts in the appendix, it seems that the instruct models (e.g. GPT) were not provided with instructions to perform chain-of-thought reasoning or anything that would encourage them to solve the problem step by step.

* There is something problematic about the premise of the paper and specifically the focus on exact arithmetic computations of large numbers (with >10 digits). Why do we need LLMs to perform this kind of computation? Wouldn’t an LLM with an external tool be a better solution in this case? Also related to this point is that one potential argument for an LLM-based solution would be that the LLM could infer the type of problem described and the steps for solving it. However, if I understood correctly, with the proposed framework the model does not make this kind of inference. Namely, the adapters to be used are selected in advance. I may have missed this point, tried to look in the paper but couldn’t find it indicated explicitly anywhere. I assume that the adapters are pre-selected (not by the model) because the results are presented per operator and there are no reported results for the performance on inferring the right adapters for the problem.

questions:
* Missing reference:
Giving BERT a Calculator: Finding Operations and Arguments with Reading Comprehension, EMNLP 2019.

* Figures are very small and hard to read. Consider showing explicitly what the input and output from the model are.

* Line106: incorrect citation format.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730340388768

thread_type:
official_review

<thread_object>
creator: reviewer_wnj4

<content>
summary:
This study proposes to decompose basic arithmetic operations into smaller steps that can be executed by LLMs simulating Turing machines. Specifically, by adapting LLMs into separate aligner and executor modules (both via low-rank adapters), one can map an arithmetic operation into a series of smaller atomic steps that solve the task. At each timestep, the aligner translates the input into a representation that the executor can process. The training data for the aligner and executor are obtained by simulating Turing machine prototypes.

The proposed approach achieves significantly higher accuracies than base LLMs, and generalizes better to inputs with many digits.

strengths:
* The proposed approach performs significantly better than base LLMs on basic arithmetic operations.
* At a high level, I admire the ambition of implementing computational-theoretic data structures using LLMs. If this works well in a wider variety of settings, it could be applied as a natural-language interface to theoretical computational structures that do not require significant human effort to construct. This could have benefits in both educational and software engineering settings, especially if the LLM is capable of explaining each step of its processing.
* The modularity of the aligner and executor setup may make it easier to debug specific components in cases where the approach does not perform well.
* The idea is mostly clearly presented.

weaknesses:
* To generate training data, one needs to create a Turing machine prototype. But once one has this machine, why not just use that to solve the task instead of having an LLM do it? It seems like one is better off having the LLM call the machine as a tool, rather than adapting the LLM to execute this procedure. The one way I could see this approach being beneficial over just using the machine is if the LLM can generalize to harder instances than the original machine was ever designed to handle, or to harder instances than were in the generated training data.
* Basic arithmetic operations represent a relatively easy application. I don’t think this is a significant weakness, since this is otherwise a pretty convincing proof-of-concept, but it may limit the impact of this otherwise neat idea.
* The modularity of the aligner and executor setup means that one must maintain high performance for multiple components over many timesteps. This means that a single point of failure could lead to cascading errors on harder tasks.
* Terminology like “understanding” is abused throughout the paper. In particular, the claim of “general understanding” in the abstract is a significant overclaim, and uses of “understanding” afterwards (especially at L189) are unnecessary and anthropomorphize LLMs. The paper would feel much more objective without this language.
* More of a suggestion than a weakness: the error analysis alluded to in the Limitations section sounds interesting. This would be great as its own Error Analysis section.

questions:
Questions
=== 
1. What is the advantage of using LLMs to simulate the required Turing machine rather than simply using the Turing machine?
2. Rather than using separate aligner and executor modules, is it possible to perform each step in an end-to-end manner (i.e., using just one adapted LLM to do an alignment and execution step)? This could cut the number of possible points of failure in half.

Typos/Suggestions
===
* L50-51: citation or forward reference needed
* L106: \citet -> \citep
* L110-111: run-on
* L133: some examples/citations would be appreciated
* L183: nitpick: The representation isn’t the space in which the computation takes place. The representation is merely a mathematical abstraction that makes it easier for humans to understand.
* The “step” variable is sometimes presented in text mode, and sometimes in math mode. It would be nice to standardize notation.
* L358: small suggestion: “original” -> “unmodified”. “Original” is polysemous, and the sense of “new” interfered with the intended sense of “unmodified” on my first pass
</content>
</thread_object>

</thread>
<thread>
creation date:
1730737525763

thread_type:
official_review

<thread_object>
creator: reviewer_cdn9

<content>
summary:
The paper attempts to address the low performance of LLMs such as llama-3.1 in arithmetic tasks such as addition and multiplication. They have devised a text-based Turing machine for these tasks, and have fine-tuned an LLM to execute it.

strengths:
1- Paper's approach in solving arithmetic tasks is grounded in our concrete knowledge of Turing machines, which is less ubiquitous in the literature of length generalization. 

2- Paper is well-written and every part has come with specific goal. Sections 2 to 4 follow a natural recipe to explain the method, along with the results.

weaknesses:
1- In the abstract, from line 16 to 18, authors claim that their method enables LLMs to execute arithmetic tasks in a more rigorous manner and achieve better generalization. My initial understanding of the passage was that the execution happens in a single query of the LLM, where the output includes the final answer. Whereas in Section 3.2, one realizes that a query to the LLM accounts to running a single step of their control flow. 

2- That said, I'm not convinced the proposed approach can be the primary solution for arithmetic tasks. If I understand correctly, the number of queries increases proportionally to the length of the operands in the task, which is problematic since every query's needed number of auto-regression steps also grows linearly with the length of operands, leading to O(d^2) number of auto-regression steps compared to O(d) for a generating the answer with a decoder-only model (d is the length of operands). The computational analysis is missing in the paper. 

3- In section 4, it's not clear whether the comparison with typical LLMs is done by executing the explained Turing machine with each of them and running the steps in different streams, or asking the answer in a single query to these models. I think a comparison with both methods is necessary when reporting. 

4- To my understanding, the proposed method uses two modules for the implementation: "BASIC EXECUTORS" and "EXECUTOR COMPOSERS". And for working with each of the arithmetic tasks (+, −, ×, ÷, ==, >, and <) they utilize different low rank adapters for fine-tuning. This doesn't give a generic solution for solving arithmetics at test time, where based on the given sample a collection of modules must be placed after each other. 

5- How does the method perform in the presence of text? I do not see any sections discussing this.

questions:
Please address the concerns expressed above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730814114639

thread_type:
official_review

<thread_object>
creator: reviewer_sukz

<content>
summary:
The paper addresses the limitations of Large Language Models (LLMs) in performing arithmetic tasks, where they often memorize examples rather than grasping the underlying computational logic. To overcome this, the authors propose the Composable Arithmetic Execution Framework (CAEF), which enables LLMs to perform step-by-step computations by simulating Turing Machines. This approach helps the models develop a true understanding of computational logic. Additionally, CAEF's scalability allows it to combine learned operators to ease the learning process for complex operations. The framework demonstrated nearly 100% accuracy across seven common mathematical operations using the LLaMA 3.1-8B model, including computations involving operands with up to 100 digits. This performance surpasses that of GPT-4o in certain aspects.

strengths:
1. The paper is clearly presented and supplemented with ample illustrative figures, allowing readers to easily grasp its content. 
For instance, Figure 1 shows the process of CAFE executing multiplication, Figure 2 outlines the CAFE framework, and Figures 3 and 4 detail the execution processes of addition and multiplication, respectively. 

2. This paper addresses a critic issue in real-world applications of LLMs. The arithmetic performance of existing LLMs, whether open-source or proprietary, is often unreliable, making it difficult to trust their output. 

3. The idea presented in the paper is refreshing, as converting seven common arithmetic operations into text language interpretable by LLMs is no easy feat. This is achieved using lora-adapters to build executors and aligners, relying on two specific prompts: state and command. 

4. The main table presents great performance results for the seven types of arithmetic operations. The accuracy exceeds 99% for both 50-digit and 100-digit tasks, demonstrating practical applicability.

weaknesses:
1. It is unfortunate that, as mentioned in Section 6 on limitations, the **efficiency issues**—stemming from *the repeated calls to model.generate()* and the *storage overhead of intermediate prompts and adapter representations*—make this approach challenging to deploy in practical applications.

2. When faced with repeating digit patterns such as "999..." or "456456...", the CAFE's executor and aligner fail to function properly. 
I disagree with the authors' claim that this is an inherent limitation of LLMs. I believe it is more likely due to **the absence of such patterns in the fine-tuning data for the executor and aligner**.
This raises concerns about the robustness of the experimental results and *whether CAFE can consistently handle or fail in other unique digit patterns*.

questions:
Please check Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732282984892

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global rebuttal section -- part 1

comment:
We would like to thank all the reviewers for their their thoughtful and constructive comments and suggestions.

## Methodology for CAEF

First, let us explain the methodology behind our paper. In our vision, the ability to execute computational logic is a fundamental skill for LLMs. To illustrate this concept, we draw inspiration from Daniel Kahneman’s book *Thinking, Fast and Slow* (2011), which introduces two modes of thought: "System 1" and "System 2." "System 1" is fast, instinctive, and automatic, while "System 2" is slower, more deliberate, and logical. For example, solving a simple problem like \\( 2 + 2 \\) typically relies on "System 1" processing, whereas tackling a complex computation like \\( 329,475,349,23 + 238,963,435,739 \\) (similar to the evaluation tasks in our study) requires "System 2" reasoning.

Currently, most LLMs predominantly operate in a manner analogous to "System 1," generating responses based on learned patterns and intuitive fluency. In contrast, our proposed framework, CAEF, introduces a methodology for enabling "System 2" generation in LLMs. This allows models to handle complex tasks that require executing intricate logical rules or searching for optimal solutions (an aspect of our ongoing work), thereby significantly expanding their problem-solving capabilities.

## Clarification Regarding the Use of External Tools and Efficiency Issues

Our approach serves as a methodological exploration aimed at investigating the upper limits of a model's capabilities in arithmetic tasks without relying on external tools. At this stage, our primary focus is on enabling the model to imitate the operations of a Turing machine to achieve high computational accuracy, rather than on applying the method directly to specific downstream applications. However, we acknowledge that the need for multiple calls to `model.generate()` for each computation introduces significant efficiency challenges. Relying on external tools remains a more practical solution for real-world applications at this time.

Alternatively, from another perspective, achieving high accuracy in arithmetic tasks with current generative LLMs, without leveraging external tools, inherently incurs additional time overhead. A comparable case is OpenAI o1 LLM, which, while seemingly producing results in a single inference for users, likely employs internal methods such as MCTS-style search. This process, though transparent to the user, involves multiple steps and incurs substantial time costs.

To address these challenges, we are exploring potential solutions:

1. **Batch Output Generation in a Single Decoding Step**: One potential solution involves modifying the model's architecture to generate a batch of outputs in a single decoding step. In our case, the differences between consecutive computational states \\(s\_i\\) and \\(s\_{i+1}\\) are typically minor, often involving only token reordering. We believe this adjustment could significantly improve efficiency in our specific scenario.

2. **LLM-Friendly Random Access Memory (RAM) Model**: Another interesting research direction involves designing a memory model for LLMs. Currently, LLMs operate like CPUs, executing commands by reading and writing variables encoded as input/output strings. If an LLM-friendly RAM model were developed, the LLM could directly read/write from memory and execute operations only on relevant variables or digits. This would drastically reduce computational costs and improve efficiency.

We believe these directions are promising for addressing the efficiency limitations of our current approach and may also open up broader possibilities for enhancing LLM capabilities in computational tasks.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732605605735

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely appreciate the valuable suggestions provided by all the reviewers. Due to time constraints, we have revised and resubmitted an updated version, with a focus on improving the textual content. Further revisions will follow, including enhancing the clarity of the figures and refining the overall structure of the paper, to ensure that CAEF can be more easily understood by readers.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces the Composable Arithmetic Execution Framework (CAEF), an approach to enhance Large Language Model (LLM) arithmetic capabilities. CAEF simulates a Turing machine within an LLM, breaking down computations into sequential <state, command> pairs processed by specialized LoRA-adapted modules for alignment and execution. The design enables more accurate calculations, especially for large numbers, outperforming both fine-tuned LLaMA and GPT-4o in certain scenarios. This method is a good proof of concept, with well designed experimental results.

However, CAEF suffers from several limitations. The most significant is its inefficiency, requiring multiple LLM queries per computation step and resulting in computational complexity that increases with operand length. This approach is also limited because it does not utilize external tools and cannot automatically select its operation LoRA adapters. There are also questions from reviewers about the robustness of the approach, especially given particular failure modes based on digit repetition and the potential for cascading errors. Though the authors address some of these concerns with further experimentation, the core issues around practicality remain.

Overall, this paper presents an interesting methodology for LLM arithmetic computation, demonstrating improved accuracy for complex arithmetic tasks. While the theoretical concept is sound and the experimental results are promising, the current implementation is not practical due to efficiency constraints and lack of flexibility. It could be strengthened by increased clarity regarding the execution process, a more detailed computational complexity analysis, and further exploration of the identified limitations and error analysis.