Prompting techniques have significantly enhanced the capabilities of Large Language Models (LLMs) across various complex tasks, including reasoning, planning, and solving math word problems. However, most research has predominantly focused on language-based reasoning and word problems, often overlooking the potential of LLMs in handling symbol-based calculations and reasoning. This study aims to bridge this gap by rigorously evaluating LLMs on a series of symbolic tasks, such as addition, multiplication, modulus arithmetic, numerical precision, and symbolic counting. Our analysis encompasses eight LLMs, including four enterprise-grade and four open-source models, of which three have been pre-trained on mathematical tasks. The assessment framework is anchored in Chomsky's Hierarchy, providing a robust measure of the computational abilities of these models. The evaluation employs minimally explained prompts alongside the zero-shot Chain of Thoughts technique, allowing models to navigate the solution process autonomously. The findings reveal a significant decline in LLMs' performance on context-free and context-sensitive symbolic tasks as the complexity, represented by the number of symbols, increases. Notably, even the fine-tuned GPT3.5 exhibits only marginal improvements, mirroring the performance trends observed in other models. Across the board, all models demonstrated a limited generalization ability on these symbol-intensive tasks. This research underscores LLMs' challenges with increasing symbolic complexity and highlights the need for specialized training, memory and architectural adjustments to enhance their proficiency in symbol-based reasoning tasks.
Large language models are driving revolutionary advancements in artificial intelligence. They are transforming how we interact with and interpret data across various modalities. These models have surpassed human performance in generating text, images, and videos. LLM-augmented systems are revolutionizing traditional expert systems such as search, retrieval, theorem proving, symbolic reasoning, programming, and drug discovery. Amid these advancements, exploring the symbolic capabilities of LLMs, particularly in logical reasoning, mathematical computation, and formal language manipulation, remains a crucial area of investigation.
A key aspect of leveraging LLM capabilities is developing efective prompting techniques. Prompts
are carefully designed inputs that guide the model’s behavior, enabling it to perform specific tasks or
exhibit desired behaviors. These techniques include few-shot and zero-shot learning, where models
are prompted with examples or instructions to help them generalize to new tasks without extensive
retraining. Other techniques include Chain-of-Thought [
In this work, we address the symbol manipulation capabilities of Large Language Models (LLMs). We investigate fundamental mathematical operations such as addition, multiplication, and counting. The inherent complexity of these tasks is derived from Chomsky’s Hierarchy. Specifically, we present the following research questions: RQ1: Can LLMs apply simple symbolic rules, such as addition and multiplication, stably and repeatedly? RQ2: How precisely can LLMs preserve the construction of a group of symbols and respect the order of operations?
In this study, we first discuss task complexity and the computational requirements necessary to solve
these tasks. We then estimate the number of bits required to encode such a machine and compare it to
the knowledge tuple encoding in LLMs as described by Deletang et al. [
Early research demonstrated that recurrent neural networks (RNNs) could learn and encode deterministic
ifnite state automata, enabling them to perform symbolic tasks such as rule-based reasoning and
grammatical inference. Omlin and Giles [
Saxton et al. [14] created a dataset of math questions across various topics and observed that LSTM models barely memorized the question-answer pairs and could not generalize. Dave et al. [15] used the same dataset to create distractors for math multiple-choice questions. Mistry et al. [16] summarized the specialized architectures developed to solve arithmetic tasks, highlighting gaps in the robustness, compositionality, and interpretability of these models. The development of large language models (LLMs) has spurred significant interest in their mathematical and symbolic capabilities. Research has increasingly focused on training LLMs specifically for mathematical tasks, aiming to enhance their proficiency in symbolic reasoning. LLM models like Deepseek [ 17], LLemma [18], and Metamath [19] are specially trained with math datasets. However, studies have shown that neural networks, including LLMs, often fail to genuinely learn to solve mathematical and symbolic tasks. Dziri et al. [20] investigated the limitations of LLMs across three problems: multiplication, puzzle solving, and dynamic programming. They tested GPT-3, GPT-3.5, and GPT-4 models using zero-shot, few-shot, and ifne-tuning techniques, revealing a significant decline in performance as the sample size increased. Similarly Shakarian et. al. [21] also reported performance of ChatGPT [22] declines with the increase in the number of addition and subtraction operations required to solve math word problems (MWPs). Furthermore, they also observe that LLMs perform much better when asked to show work. Additionally, Frieder et al. [23] demonstrated that GPT-4’s mathematical proficiency was far below graduate-level standards. Previous research on the mathematical proficiency of large language models (LLMs) has primarily focused on a broad set of math problems and reported findings based on static datasets such as GSM 8K [24] and MATH [25]. This approach does not uncover the underlying inconsistencies in LLMs’ understanding of mathematics. In this work, we examine the consistency and precision of LLMs as the complexity of the tasks increases.
Through our analysis, we assess the performance of enterprise and open-source LLMs trained on text and mathematical datasets, testing them on five symbolic tasks. These tasks fall into context-free and context-sensitive categories on Chomsky’s hierarchy. We discuss the bit complexity of encoding symbolic tasks as an automaton and a set of knowledge tuples. Our experiments show that while enterprise LLMs, with their higher parameters and curated datasets, outperform open-source models, all models exhibit similar performance trends that align with the knowledge-tuple encoding of symbolic tasks. Fine-tuning these models on symbolic tasks has little efect on their performance, indicating that LLMs do not learn the rules of symbol manipulation but rather encapsulate relationships in terms of tuples. The contrast in the number of parameters required to encode symbolic tasks suggests a need for developing larger models capable of learning automata rather than merely storing information.
Ideally, a model should either encode mathematical tasks as knowledge tuples or learn to simulate a
machine that can solve such tasks eficiently. In this section, we examine the parameters required by
models using both approaches. We relate tasks to their complexity, derived from Chomsky’s hierarchy,
with detailed definitions provided in the appendix. Furthermore, prior work by Allen-Zhu et al. [
A finite state machine can add two numbers. Addition of sequence of numbers can be represented by production rules → ; → , where is the sequence of numbers, is the sum of partial sequence and is the remaining sequence. It is clear from the construction that a non-deterministic PDA can solve this problem. At each step of operation, the nPDA computes the sum of two numbers of arbitrary but finite number of digits. Let the the number of digits be and . Then the number of digits in the sum of two numbers is (, ) + 1. There are two ways a LLM can encode the the rules of addition : 1) Encoding the states and stack in the internal parameters of the model, 2) Encoding addition rules for each pair of numbers. Encoding the nPDA requires 2(#( ) + ()) bits which is considerable lower than encoding specific addition rules for numbers of arbitrary number of digits.
Proposition 3.1. For the addition of two base numbers with finite digits and , respectively, where ≥ , the encoding of their sum requires at most (2 + + 1) log2 bits. This account includes the possibility of a carryover in the addition, which may increase the length of the resulting number by one digit.
Proof. Consider two numbers and represented in base , where has digits and has digits with ≥ . Each digit in these numbers requires log2 bits to encode due to the need to distinguish between diferent values.
Step 1: Encoding Individual Numbers.
• The number requires log2 bits.
• The number requires log2 bits.
Step 2: Maximum Size of Sum. When adding and , the maximum number of digits in the sum, = + , could be + 1 (considering the possibility of a carryover from the most significant digit).
Step 3: Encoding the Sum. The sum hence requires at most ( + 1) log2 bits.
Step 4: Total Encoding Requirement. Adding the encoding requirements together, the total number of bits needed is:
log2 + log2 + ( + 1) log2 = (2 + + 1) log2 .
This calculation confirms that the sum of the encoding requirements for the numbers and their potential maximum sum, considering carryover, matches and proves the proposition.
Corollary 3.2. Consider a sequence of numbers, each of base 10 and with at most digits. To completely memorize all possible addition operations within this sequence, a Large Language Model (LLM) must store at least (3max − 2) log2 10 bits of information, where:
max = ⌊︀ 1 + log10 (︀ (10 − 1) · )︀⌋ , and
( + 1) = 4 , = (10 − 1) representing the total number of distinct pairwise addition operations that could be required to solve the sequence. Here, max represents the maximum number of digits in any number or partial sum within the given sequence, and quantifies the total number of unique addition rules required for comprehensive solution strategies.
Multiplicating two numbers of arbitrary digits is a context-sensitive task. It requires a finite state machine augmented with a finite tape. For the input expression of form × on the input tape, the tape pointer reads the digits of from right to left. For digit with place value in , the pointer moves right to the output part of the tape and increments it * * times. The pointer moves back to the digit, sets it to <BLANK>, and moves to the digit on the left.
Proposition 3.3. An automaton, which includes a finite state controller and a finite length tape, capable of computing the multiplication of an -digit number and an -digit number, requires encoding with log2 6 + 2 · ( + ) · log2 bits.
Proof. To compute the multiplication of two numbers, each represented by and digits respectively, consider an automaton designed as follows:
State Design: The finite state controller is structured with six distinct states to manage the computation: 1. Two states are dedicated to reading the digits of the numbers, specifically one state for each number (1 and 2). 2. One state is allocated for writing the output of the multiplication. 3. Three additional states facilitate the movement of the tape head to the appropriate positions corresponding to the digits of the two numbers and the resulting output.
Tape Complexity: The tape must accommodate the digits of both numbers and the resultant product. The maximal length of the product of two numbers, each with and digits, is + digits. Therefore, the tape’s length is approximately (2 · ( + )) to account for both input numbers and their maximal output size.
Bit Encoding: The number of bits required to encode the state machine is determined by the logarithm of the number of states, giving log2 6 for the states. The tape encoding requires 2 · ( + ) · log2 bits, where log2 bits are needed to encode each digit of the input and output numbers, assuming the numbers are in base .
Combining these components, the total encoding requirement for the automaton is thus: log2 6 + 2 · ( + ) · log2 bits.
Proposition 3.4. Given two integers and , where is an -digit number and is an -digit number in base , a multiplication rule that expresses the relationship × = can be encoded as a knowledge tuple (, , ). This tuple can be stored using at most 2( + ) log2 bits.
Proof. The multiplication of and results in , where can have at most + digits (considering the maximum carry-over in base ): • Each digit of and can be encoded using log2 bits because each digit represents a value from 0 to − 1. • Therefore, requires · log2 bits and requires · log2 bits.
• The product can be as large as + digits, thus requiring at most ( + ) · log2 bits.
The knowledge tuple (, , ) encapsulates the complete multiplication expression and therefore combines the storage requirements of , , and . Thus, the total bit requirement is the sum of the bits needed to store , , and :
2( + ) log2 bits, assuming the maximum possible size for and ignoring potential savings from compressing common information between , , and . This completes the proof.
Corollary 3.5. Given all possible tuples (, , ) where and are numbers in base 10 with a maximum of max digits, these tuples can be encoded in a Large Language Model (LLM) using at most 4max · 102max · log2 10 bits, where max is the maximum number of digits in any number among , , and .
Proof. To encode each of the tuples (, , ) where and are up to max digits: 1. The total number of possible values for or is 10max , since each digit can range from 0 to 9. 2. The product = × can have at most 2max digits (considering the worst-case scenario of multiplication). 3. Thus, the number of possible tuples (, , ) is 10max × 10max × 102max = 104max . 4. Each tuple then requires encoding that can be estimated by calculating the total number of bits to represent each digit of , , and in binary:
4max · log2 10 bits per digit × 102max possible tuples.
This provides upper bound on the bit requirement to encode tuples in an LLM.
Counting the frequency of a character in a given string is well solved using an automaton equipped with a counter and a register. Let be the set of all possible characters s.t. ∈ and ∈ * . First, the automaton reads and stores it in the register. The finite state controller then reads characters ′ ∈ step by step and increments the counter when ′ = .
Proposition 3.6. An automaton capable of counting the frequency of a character in a given string can be encoded in at most 23 + 2| | + ⌊1 + log ⌋ * log2 bits, where is the maximum length of an input string in base Proof. Step 1 : Encoding the states: The above discussed automaton can function with 3 states. The automaton starts in state 0, reads the character into the register, and moves to the next state (1). The automaton now reads the string, one character at a time. If the input character matches the character in the register, the automaton moves into state 2. Otherwise, it remains in 1. The states {0, 1, 2} can be encoded in log2 3 bits.
Step 2 : Encoding the register : Since the register holds one character ∈ , it can be encoded in 2| | bits.
Step 3: Encoding the counter: The maximum value the counter would need to hold is the length of the longest string. Thus counter can be encoded in ⌊1 + log ⌋ * log2 bits.
Proposition 3.7. The knowledge tuple (, , ), where is the frequency of in can be encoded in atmost ( + 1)2| | + ⌊1 + log ⌋ * log2 bits.
Corollary 3.8. An LLM can encode the entire sample space of (, , ) knowledge tuples of maximum string length (in base 10) in atmost | |+1Δ, where
Δ = ( + 1)2| | + ⌊1 + log10 ⌋ * log2 10
Encoding the entire space of possible string combinations is a gargantuan task. It’s very ineficient, even for massive LLMs. Especially when counting can be reduced to the addition of a sequence of ones and zeros, where 1 represents a character match and 0 represents no match. This reduces symbolic counting into a two-step process:
Step 1: Using attention mechanism to reduce the character matching problem to a binary sequence that represents a match. This can be encoded in atmost + ( + 1)2| | bits.
Step 2 : Perform sum of sequence on the sequence of 1s and 0s. There will be total of 2 knowledge tuples to encode addition in form (, 1, + 1) and (, 0, ). These can be encoded in almost 2 * (1 + 2⌊1 + log10 ⌋ log2 10) bits.
Thus, the bits required by LLMs to encode symbolic counting are:
+ ( + 1)2| | + 2 * (1 + 2⌊1 + log10 ⌋ log2 10)
Based on the estimates discussed above, we now find out the computational capacity of large language models with respect to the tasks of addition, multiplication, and counting. Table 1 reflects the bound on input size for given tasks for a model of 7B and 180B parameters, respectively. These bounds are much closer to the performance that we observe in our experiments. Most LLMs are trained on multiple tasks and are primarily focused on modeling language rather than symbolic tasks. Hence, our results show that LLM performance degrades for sample sizes that are way smaller than the bounds discussed.
Table 2 shows the number of parameters required for the two encoding systems for a fixed input size on the given tasks. It is observed that, if neural network models could simulate the machines to solve the task, they would require considerably less number of parameters. Current LLMs have parameters more aligned with the knowledge tuple encoding system.
Task Sum of Sequence Multiplication Symbolic Counting
Size Parameter 7B Sequence Length 363 #(1) + #(2) 8 String Length 1e8
Fundamental mathematics operations, like addition and multiplication, are well understood as symbolic operations. Numbers can be represented as composite symbols composed of a pre-defined set of symbols, i.e., 0 − 9 numerals. We analyze the performance of large language models on varying dificulty of the tasks modeled as the input size. All models are tested on 100 samples for each dificulty level. We keep a consistent seed for data generation to ensure a fair comparison.
We conduct our experiments on eight LLM models, including four enterprise models and four opensource models. The enterprise models are GPT-3.5 (gpt-3.5-turbo-0125), GPT-4 (gpt-4-0125-preview), Gemini (gemini-pro-1.0), and Claude (claude-3-haiku-20240307). The open-source models analyzed are Llamma 2 (13B), Llemma (7B), Deepseek (7B), and MetaMath (7B). All open source models except Llamma-2 13B are pre-trained on math tasks. Llemma 7B is Llamma-7B based model fine tuned on math datasets. MetaMath is fine-tuned on Llemma-7B. Deepseek is trained on math datasets like OpenWebMath.
Model query parameters We keep the maximum token size of 4096 for all models. All models are queried with temperature of 0 to maximize determinism in the generated text. Models are not given access to any external API’s, python interpretter, documents or databases, to ensure analysis of standalone LLM performance. No examples are provided in the prompt, and single prompt query is used for each input sample. Zero-shot COT method is used to allow models to navigate the problems without any help.
Prompting All prompts are composed of two components: system prompt and user prompt. Gemini API does not have separate fields for system and user prompts, hence we concatenate both. System prompt is composed of the following components: 1. Identity - e.g. for sum of sequence, the prompt stats with "You are number crunching machine..." 2. Input type - the input type can be sequence of numbers, arithmetic expression etc. 3. Command - instruction on what to do with the input. e.g. calculate the sum 4. Constraint [Optional] - Any extra guideline or constraint for the model, e.g. Treat the upper and lower case characters as separate 5. Zero-Shot COT - To help models present the intermediate thoughts and reasoning without providing any example, we use Zero-shot-COT method. This is done by appending Let’s think step by step, at the end of the prompt.
The user prompt has two parts : 1) input identifier and 2) input sequence
Task Sum of Sequence Multiplication Symbolic Counting Modular-10 Arithmetic Decimal Arithmetic
Categorization by Chomsky’s Hierarchy Sum of sequence od multi-digit numbers can be constructed as: → ; → Hence it is a context free task Multiplication of two multi-digit numbers is a context-sensitive task as it requires a bounded tape to perform the operation.
Counting the matches of a character in a string requires a counter with a FSM, A modular arithmetic expression with brackets require a stack to store intermediate results and is thus context-free task Decimal Arithmetic requires a tape to perform multiplication and thus is context-sensitive.
Machine Pushdown Automata
Linearly Bounded
Automata Counter Automata Pushdown Automata
Linearly Bounded
Automata
1. Sum of Sequence The model is tasked with computing the sum of the sequence of numbers. The
numbers in the sequence are sampled uniformly in the range 10—99. Task dificulty is modeled
as the length of input sequences. We test the sequence of sizes 5, 10, 20, 50, 100, 200, and 500.
2. Modulo-10 Arithmetic While Deletang et al. [
We fine-tune GPT3.5 model on sum of sequence and symbolic counting tasks. For sum of sequence we ifne-tune specifically for sequence lengths 5, 10, 20, 50 and 100 with 300 samples for each seq length. The validation set is composed of 50 samples for each length. Finally the model is tested on all sequence lengths i.e, 5, 10, 20, 50, 100, 200, and 500 with 100 samples for each length. Similarly, for the symbolic counting tasks, the model is fine-tuned with strings of length 50, 100, 200, and 500, with 300 for each length. The model is tested for all lengths with 100 samples each.
Figures 1 - 6 show the performance of LLMs on the five symbolic tasks. In all cases, we can see that performance starts degrading as the dificulty of input samples increases. By comparing these results with tables 1 and 2 we can see that performance starts degrading for far simpler examples than anticipated. This indicates that LLMs have not learned to solve symbolic problems but rather have a notion of input-output pairings. From the figures, we can see that while GPT3.5 and Claude Haiku models perform very similarly in all tasks, Gemini is able to sustain performance longer than the other models on the sum of sequence task while it is usually behind other models in the rest of the tasks. GPT4 outperforms other models in modulo-10 arithmetic, decimal arithmetic, and multiplication tasks while lagging behind in other tasks. Claude Haiku performs fairly consistently in all tasks, being the smallest of all enterprise models. Out of all models, Lemma 7B is the worst-performing model across all tasks. Deepseek and MetaMath perform slightly better due to their math pre-training.
In computational tasks, the dificulty is often represented by a parameter that increases the operations in the corresponding state machine without altering the accepted transitions or the number of states. Typically, longer strings are considered more dificult. However, this parameterization does not change the machine’s construction, so a neural network capable of emulating the machine should produce correct outputs regardless of input length. While memory and precision constraints provide an upper bound on the input length, modern computers have bounds significantly higher than those used in this study. For instance, in multiplication, increasing the number of digits in the operands necessitates more single-digit multiplications and additions. This requirement, however, does not alter the fundamental operations of multiplication or addition. We represent this complexity with a single parameter: the combined number of digits in both operands. Our experiments indicate that large language models (LLMs) fail to maintain accuracy as the number of digits in the operands increases.
Enterprise and Open Source Models Multiplication is the only task where open-source models and enterprise models start with similar performances. In symbolic counting, the Llamma 13B model performs similarly to enterprise models for strings of length 5. In all cases, the performance of opensource models degrades much faster than that of enterprise models. In the other three tasks, open-source models perform far below enterprise models, even for simpler cases. An argument could be made that open-source models are smaller than the enterprise models tested in this work. This further indicates that performance is highly dependent on the models’ size, making the knowledge-tuple encoding hypothesis much stronger.
Math trained models Out of the three math-trained models, Deepseek gives the best overall performance. However, even math-trained models are not able to sustain their performance on larger examples. Symbolic counting is the only task where the Llamma 13B model outperforms math-trained (a) GPT 3.5 fine-tuned on Sum of Sequence (b) GPT 3.5 Fine-Tuned on Symbolic Counter
Task task models. All math-trained models have the number of parameters of Llamma 13B.
Efect of fine tuning Figure 6 shows the comparison of vanilla and fine-tuned GPT3.5 models on the sum of sequence and symbolic counting tasks. We can observe that fine-tuning has helped performance in smaller examples but made larger examples a little worse. Overall, all fine-tuning and closing performances follow vanilla performance, and there is no improvement in the generalization of the tasks.
In this work, we analyze the performance of enterprise and open-source LLMs trained on text and mathematical datasets on five symbolic tasks. The tasks occupy context-free and context-sensitive categories on Chomsky’s hierarchy. We discussed the bit complexity of encoding symbolic tasks as an automaton and set of knowledge tuples. Our experiments show that although enterprise LLMs perform better than open-source models catering to higher parameters and curated dataset, all models show similar trends in performance and align with knowledge-tuple encoding of symbolic tasks. Fine tuning on these tasks as little efect on the performance of LLMs. This clearly shows that LLMs are not learning the rules of symbol manipulation but rather encapsulate relationships in terms of tuples. The contrast in the number of parameters required to encode symbolic tasks calls for a push in the direction of large models capable of learning automaton rather than storing information. [6] C. L. Giles, C. W. Omlin, Extraction, insertion and refinement of symbolic rules in dynamically driven recurrent neural networks, Connection Science 5 (1993) 307–337. [7] C. W. Omlin, C. L. Giles, Constructing deterministic finite-state automata in recurrent neural networks, Journal of the ACM (JACM) 43 (1996) 937–972. [8] C. W. Omlin, C. L. Giles, Training second-order recurrent neural networks using hints, in: D. Sleeman, P. Edwards (Eds.), Machine Learning Proceedings 1992, Morgan Kaufmann, San Francisco (CA), 1992, pp. 361–366. URL: https://www.sciencedirect.com/science/article/pii/ B9781558602472500516. doi:https://doi.org/10.1016/B978-1-55860-247-2.50051-6. [9] A. Mali, A. Ororbia, D. Kifer, L. Giles, On the computational complexity and formal hierarchy of second order recurrent neural networks, arXiv preprint arXiv:2309.14691 (2023). [10] A. Mali, A. Ororbia, D. Kifer, L. Giles, Recognizing long grammatical sequences using recurrent networks augmented with an external diferentiable stack, in: International Conference on Grammatical Inference, PMLR, 2021, pp. 130–153. [11] J. Stogin, A. Mali, C. L. Giles, A provably stable neural network turing machine with finite precision and time, Information Sciences 658 (2024) 120034. URL: https://www.sciencedirect.com/science/ article/pii/S0020025523016201. doi:https://doi.org/10.1016/j.ins.2023.120034. [12] N. Dave, D. Kifer, C. L. Giles, A. Mali, Stability analysis of various symbolic rule extraction methods from recurrent neural network, in: ICLR 2024 Workshop on Bridging the Gap Between Practice and Theory in Deep Learning, 2024. [13] A. Mali, A. G. Ororbia, D. Kifer, C. L. Giles, Recognizing and verifying mathematical equations using multiplicative diferential neural units, in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 2021, pp. 5006–5015. [14] D. Saxton, E. Grefenstette, F. Hill, P. Kohli, Analysing mathematical reasoning abilities of neural models, arXiv preprint arXiv:1904.01557 (2019). [15] N. Dave, R. Bakes, B. Pursel, C. L. Giles, Math multiple choice question solving and distractor generation with attentional gru networks., International Educational Data Mining Society (2021). [16] B. Mistry, K. Farrahi, J. Hare, A primer for neural arithmetic logic modules, Journal of Machine
Learning Research 23 (2022) 1–58. [17] X. Bi, D. Chen, G. Chen, S. Chen, D. Dai, C. Deng, H. Ding, K. Dong, Q. Du, Z. Fu, et al., Deepseek llm: Scaling open-source language models with longtermism, arXiv preprint arXiv:2401.02954 (2024). [18] Z. Azerbayev, H. Schoelkopf, K. Paster, M. D. Santos, S. McAleer, A. Q. Jiang, J. Deng, S. Biderman, S. Welleck, Llemma: An open language model for mathematics, arXiv preprint arXiv:2310.10631 (2023). [19] L. Yu, W. Jiang, H. Shi, J. Yu, Z. Liu, Y. Zhang, J. T. Kwok, Z. Li, A. Weller, W. Liu, Metamath: Bootstrap your own mathematical questions for large language models, arXiv preprint arXiv:2309.12284 (2023). [20] N. Dziri, X. Lu, M. Sclar, X. L. Li, L. Jiang, B. Y. Lin, S. Welleck, P. West, C. Bhagavatula, R. Le Bras, et al., Faith and fate: Limits of transformers on compositionality, Advances in Neural Information Processing Systems 36 (2024). [21] P. Shakarian, A. Koyyalamudi, N. Ngu, L. Mareedu, An independent evaluation of chatgpt on mathematicalword problems (mwp), in: CEUR Workshop Proceedings, volume 3433, CEUR-WS, 2023. [22] OpenAI, Introducing chatgpt, 2022. URL: https://openai.com/index/chatgpt/. [23] S. Frieder, L. Pinchetti, , R.-R. Grifiths, T. Salvatori, T. Lukasiewicz, P. Petersen, J. Berner, Mathematical capabilities of chatgpt, in: A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, S. Levine (Eds.), Advances in Neural Information Processing Systems, volume 36, Curran Associates, Inc., 2023, pp. 27699–27744. [24] K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al., Training verifiers to solve math word problems, arXiv preprint arXiv:2110.14168 (2021). [25] D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, J. Steinhardt, Measuring
Chomsky [
A DFA reads input one symbol at time and updates its state determined by the transition rules . The input string is accepted if the DFA reaches a state ∈ at the end of the input.
Definition A.2. A Non-Deterministic Finite (State) Automaton is a 5-tuple similar to DFA with a non-deterministic transition function : × (Σ ∪ { }) → (), where () is a power set of all automaton states.
All non-deterministic FSA can be reduced to their deterministic counterparts without the loss of expressivity. Finite State Automata can accept all regular languages.
Definition A.3. A Finite State Transducer (FST) is a finite state machine with an output tape. Formally it is a 6-tuple, (, Σ, Γ, 0, , ) where Λ is the set of output alphabet, and : ×{ Σ∪ } → ×{ Λ∪ }. Definition A.4. A Pushdown Automaton is a 7-tuple, (, Σ, , , 0, , ), where is a set of stack symbols and ∈ is initial stack symbol. Transition function is defined as : ×{ Σ∪ }× → × * Definition A.5. A Pushdown Transducer is a pushdown automata with an output tape. Specifically it is a 8-tuple, (, Σ, Λ, , , 0, , ), where Λ is a set of output symbols. All other symbols carry the same meaning as a pushdown automata. The transition function is defined as : × { Σ ∪ } × → × { Λ ∪ } × * Definition A.6. A Turing Machine is a 7-tuple, (, Γ, , Σ, , 0, ). Γ is the set of all tape alphabets. ∈ Γ is blank symbol, which is default on any on-empty cell on the tape. Input symbols are part of tape symbols, Σ ⊆ Γ , and transition function is defined as : × Γ → × Γ × { , , }. Here {, , } are no shift, left shift and right shift of the tape pointer respectively.
A FST can generate all regular languages and similarly, a pushdown transducer can generate all context free languages. A linearly bounded automaton is a Turing Machine with a finite size tape.
The five symbolic tasks discussed in this paper—sum of sequences, modular arithmetic, decimal arithmetic, multiplication, and symbolic counting—can be accomplished using three fundamental operations: addition, multiplication, and counting. In this section we will discuss how machines categorized in chomsky’s hierarchy can be used for these operations.
The addition of two -digit numbers can be carried out by a two-state finite state transducer (FST). Figure 8a depicts a construction that reads the digits of the two numbers from left to right and outputs the result one digit at a time, from the least significant to the most significant digit. To add a sequence of numbers, we add a stack to FST of figure 8a and make it non-deterministic (figure 8b). (a) A two-state FST (Finite State Transducer) can add (b) To add a sequence of numbers, the finite state matwo numbers by reading the digits of each number chine depicted in Figure 8a is augmented with a from right to left, performing addition one digit at a stack to store intermediate addition results. A nontime. The two states represent whether we need to deterministc pushdown transducer is required to add a carry to the sum or not. ensure that the results are popped from the stack in the correct order.
The multiplication of two multi-digit numbers necessitates a tape for storing partial products. As depicted in Figure 9, a linearly bounded automaton (LBA) eficiently performs this task. It can solve the multiplication of two multi-digit numbers by first calculating partial products and then combining them to yield the final product. The number of digits in the partial products and the final product is constrained by the number of digits in the given numbers. Consequently, a bounded tape is suficient for evaluating the product. Counting the occurrences of a specific character in a string can be achieved using a counter machine. In Chomsky’s hierarchy, counter machines are more complex than finite state machines but less complex than pushdown automata. Figure 10 shows a construction of a counter machine that can keep the occurrences of a character in a given string. We also take help from a register to store the character to match.
Proposition C.1. Given a number in base , the model requires to encode it in symbolic form.
︀⌊ 1 + log( )⌋︀ · log2 bits Proof. The number of digits required to represent a number in base can be determined by the formula:
= ⌊︀ 1 + log( )⌋︀ .
This expression arises because the largest number representable with digits in base is − 1, and thus:
− 1 ≤ < .
− 1 ≤ log( ) < .
= ⌊︀ 1 + log( )⌋︀ .
︀⌊ 1 + log( )⌋︀ · log2 .
Adding 1 to each part and then taking the floor function provides the correct number of digits:
Each digit in base requires log2 bits for encoding since each digit can take any of diferent values, and log2 bits are suficient to uniquely identify each value. Therefore, the total number of bits required to encode is the product of the number of digits and the number of bits per digit: