Language Models Need Inductive Biases to Count Inductively

1. The meaning of “number word” isn’t immediately clear

We will clarify this borrowed terminology. In cogsci, it is proposed that children initially develop mental representations for “sets of cardinality k”, distinctly from how they represent number words (the meaning they attribute to the utterances of “one”, “two”, “three” …).

Correspondingly, in the LM context, number words are connected to how a model embed linguistic symbols “one”, “two”, “three”, which may differ from how a model represents a set of tokens with cardinality k.

2. Issues with overclaiming in the interpretation and discussion of results.

2.1 Counting requires a “non-trivial budget” is an overclaim

Discussion in this respect might depend on what is regarded as “non-trivial”. Our work begins with questioning the assumption that counting is an atomic function in the formal computational framework of Transformers. An atomic function should be effortlessly implemented or learned, because they are expected to be repeated and composed for tens or hundreds of times throughout a deep model. It is in this regard that we define “trivial”. Thus, a 4L-worth of computation w.r.t to a 32L model is non-trivial, because the model cannot afford repeating and composing a 4L-worth of computation for tens or hundreds of times, let alone interleaving it with other non-trivial computations once a model is expected to be versatile. We are effectively borrowing the scoping of non-trivial from the implicit assumptions already in the literature, it is not a subjective judgement on our part, but we will refine the discussion further to remind the reader of this basis.

2.2 This studies the "inductive bias", i.e. the outcome of the particular training dynamics on this toy problem; it's entirely possible that some other synthetic set up, or even pretrained language models, can be more efficient. Claims like this is better substantiated with interpretability on pretrained language models, or an expressivity argument

We apologize if we have misunderstood this question but are having difficulty understanding the claim.

We assume, the reviewer is not arguing that pretraining with autoregressive losses can imbue a model architecture with new expressivity, thereby shifting its position on the computational hierarchy? So we attempt to outline answers for other interpretations below but would really appreciate it if the reviewer could elaborate or decompose the question, as we have clearly not fully understood their request and would like to!

• We agree that inductive bias can have multiple sources: the architecture, training curriculum, the gradient descent procedure, to name a few. Analyzing multiple sources of inductive bias altogether can either reveal a broader picture, or obscure it. So one has to be careful when navigating multiple factors at play. It is for this reason that we restrict our focus on the inductive bias encoded in the architecture while fixing the task formatting and training procedures. It is true that our results cannot say much about the role played by factors beyond the architecture. But what we are able to say about the architecture, is well grounded and justified through experiments. This is a major contribution and it is unfair to diminish this contribution based on the absence of parallel investigation on task formatting and training procedures.
• The reviewer suggested that we leverage pretrained LMs or other synthetic setups to achieve greater efficiency, which is confusing because our goal is not to propose more efficient approaches on counting, but to provide a broad picture of how current approaches handle counting. Better understandings of where we currently are is always an essential step towards making informed proposals about next steps.
• Interpretability and expressivity are neighboring fields which have common motivation and research questions with this paper. However, it is infeasible to span all these fields in a single paper. We believe our work will interest audiences in both interpretability and expressivity, thereby worthing publication for it to reach its audiences.

2.3 The paper suggested the integration of several PEs without actual experiments. “In fact, your results seem to suggest the opposite: that sometimes having PE with more degrees of freedom can do worse than having fewer”

Thanks for the question. We did not conduct these additional experiments because the potential benefits of integrating PEs is an implication of the main findings, rather than the main argument itself. The actual operationalization of this idea, however, requires nontrivial effort and may become a full paper in its own right. As the reviewer has already noticed, our results suggest both the orthogonal strengths of multiple PEs, AND the interference PEs can cause when incorporated untimely. Therefore, harnessing the orthogonal strengths requires a more organic integration beyond plug-and-play, in order not to suffer from interference. We believe there is a large future venue for such investigation that is beyond the scope of a single paper. But the fact that our findings open up new questions around PEs, and direct research discussions to these questions, justifies the importance of this work.

1. Counting setting far removed from practical language models.

We respectfully disagree with this statement. We may not directly conduct experiments with practical LMs, but there is deep connection between the subject of our investigation and practical scenarios. Such deep connection has been well argued in previous literature. For example, the formal expressivity community has dedicated studies on counting [1] and recognition of counter languages [2,3] with Transformers/self-attention. The LLM community recognizes the need for counting the depth when reasoning through a structured problem space such as graph [4], tree [5], recursive function call [6] or dynamic programming [7]. For a rigorous study, it is necessary to abstract away from the practical scenario in order to peel off confounding factors and make it possible to develop informed and justified arguments.

[1] Yang & Chiang, “Counting like transformers: Compiling temporal counting logic into softmax transformers”

[2] Ebrahimi, et al., “How can self-attention networks recognize dyck-n languages?” Related to numerical reasoning or number sense (borrowed from cognitive science).

[3] Bhattamishra, et al., “On the ability of self-attention networks to recognize counter languages”

[4] Dziri, et al., “Faith and fate: Limits of transformers on compositionality”

[5] Zhu & Li., “Physics of language models: Part 1, context-free grammar”

[6] Zhang, et al., “Can transformers learn to solve problems recursively?”

[7] Del’etang, et al., “Neural networks and the chomsky hierarchy”

3. Why not using base10 representation format of numbers?

Base 10 number representation would lead to much more difficulty in experimental design. When a number could be tokenized into multiple tokens, we could no longer elicit a single-token output for each cardinality, demanding pre- and post-processing to resolve the one-to-many alignment.

3.1 Will base10 help length generalization?

As opposed to bringing help, base10 may introduce unnecessary intricacies, i.e. the mapping back and forth between the concept of a number as a whole and its representation by multiple tokens w.r.t an LM’s vocabulary.

To elaborate on this intricacy, previous studies show that when a word is tokenized into multiple tokens, early Transformer layers serve to "detokenize" —— mapping token spans into internally-represented words, while late Transformer layers take additional reponsibility to "re-tokenize" —— mapping internally-represented words back to token spans. [1, 2]. The implication of these studies on counting is that whole-numbers are preferred as the processing unit in Transformers, while tokenization adds extra complexity of mapping token spans and numbers back and forth. In our setting, we use whole-number tokenization to avoid conflating the complexity of counting with the complexity introduced by tokenization which is orthogonal to our focus.

[1] Section 6.3.2-6.3.3 in Elhage, et al., "Softmax Linear Units", Transformer Circuits Thread

[2] Feucht, et al., "Token Erasure as a Footprint of Implicit Vocabulary Items in LLMs”

3.2 Would base10 yield significantly different results?

Base 10 number representation may remove OOD vocabulary, but it only superficially dissolves the difficulty of counting. As explained in Line88-90, there is an important distinction between numbers in the language context and numbers in the cardinal context. Unseen cardinality values will persist with base10 representation. The reviewer might have missed an important point that OOD extrapolation is hindered by multiple types of OOD issues, including but not limited to: OOD-position, OOD-vocabulary, OOD-cardinality, OOD-range-of-dependency. As pointed out in Line457-460, these issues shall not be confused with each other and shall be targeted by separate remedial techniques. While base10 representation might remove the OOD-vocabulary issue, it leaves other issues unsolved. For this reason, we believe the results wouldn’t differ significantly if we switched to base10 representation.

4. Can you draw high level lessons from this?

Our work offers two high-level messages: 1) counting is not a built-in skill in most LM architectures, 2) counting could be imbued via certain architectural components that encode the relevant inductive bias. The first message calls for the field to reexamine what types of computation are assumed to be atomic. The second message suggests a potential direction for acquiring basic counting skills now that they cannot be taken for granted.

5. How would the findings here help improve the design of position embeddings?

Please see response to 2.3. We do not have concrete ideas at present, but we point out important considerations should a future study formalizes concrete ideas.

3. Lack of novel concepts or methodologies.

Our work does not aim to introduce new methodologies and very explicitly avoids the introduction of new concepts as our work is evidence-based with a focus on making explicit the mismatch between claims in the literature and the lack of rigorous evidence and analysis. Our novel contributions lie in empirical evidence and analysis.

We respectfully point out that our core contributions may not be fully recognized in your review and we’d like to discuss it further. To make discussion easier, we organize them into bullet points below, especially emphasizing those that are already recognized by other reviewers.

• This work operationalizes the assessment of counting ability in LMs with well-designed tasks and well thought through experiments (jHk7, Funv)
• Comparing counting performance across positional embeddings is a new contribution. (jHk7, Funv)
• We not only provide the results, but dig deeper into the hidden factors that help explain the results, e.g. representing implicit BoS (RT8E), position-based modular arithmetic (jHk7),
• Performing analysis from the perspective of what inductive biases are encoded by PEs or the natural recurrence in RNNs, which consequently facilitate counting, is interesting and novel (jHk7, Funv).
• Overall, our work offers two high-level messages: 1) counting is not a built-in skill in most LM architectures, 2) counting could be imbued via certain architectural components that encode the relevant inductive bias. The first message calls for the field to reexamine what types of computation are assumed to be atomic. The second message suggests a potential direction for acquiring basic counting skills now that they cannot be taken for granted.

4. Insufficient contribution compared to what’s already studied by “When can Transformer count to n”

Despite similarity suggested by the title, the referenced paper “When can Transformer count to n” differs from our work in multiple key aspects (detailed below). So we believe that our work and theirs nicely complement each other and that both are important for guiding and shaping future work.

• Different axes of empirical comparison. They did not focus on the PE dimension for comparison (they mainly used APE and NoPE). Nor did they compare against RNN-based architectures.
• Different task formats. Their QC task with the “histogram solution” is similar to our selective counting task, but has a fixed input sequence length, thereby not considering extrapolation. The “count attend solution” is theoretically proved to be able to handle variable length, but there are no accompanying experiments, nor is it clear whether the ability to handle variable length can extrapolate to unseen lengths. Their MFE task only concerns counting the most frequent element rather than keeping counts for every element.
• Different analysis focus. Their analysis focuses on the intricate relationship between hidden dimension and number of unique elements to count, while our analysis is centered around inductive biases needed for counting inductively.

1. Lack of insights into the reasons behind the poor performance.

We apologize if Section 5 of the paper was too dense, but it is entirely devoted to the reasons behind the observed performance. To recap, we describe two generalizable mechanisms, for modular and selective counting, respectively. We provide evidence for why we believe the models are indeed implementing such mechanisms. Each mechanism demands particular inductive biases. Each PE schema either supports or goes against certain inductive biases. The high level explanation, put briefly, is that poor performance is resulted from the mismatch between a particular PE’s inductive bias and the task’s demand. Due to the space limit, we include detailed figures in Appendix D&E. Again, we recognize there are many results and details which answer all of your concerns, but may not have been easy to digest. We hope the reviewer is able to revisit those sections in the manuscript in more detail so we can have a technical discussion about the results.

2. The conclusions are specific to counting tasks and may not generalize to real-world scenarios.

We believe the abstract concept of induction, lying at the core of inductive counting, is a commonality underlying a broad-enough range of real-world tasks.  In fact, the reviewer agreed on the importance of the counting task. We believe that such importance attached to counting exactly reflects the common recognition in the field that counting can be thoroughly studied under clean setting, while having implications outside the clean environment. It is unclear in this mathematical context what the review intends by “real world”, so precise examples of cognitively relevant mathematical phenomena would be greatly appreciated.

1. Framing of the first couple pages

Thank you for your deep engagement with the work. We realize this is a rather intricate paper to write and so we’d be happy to improve and polish any of the writing and would love specific recommendations or points which you feel are unclear. Any framing recommendations will further strengthen the work!

2. Shorten first half of the abstract

Thanks for the suggestion. We have revised the abstract (see the updated submission)

3. Missing reference to the bootstrapping counting paper.

The bootstrapping counting paper is indeed very relevant to our work. We have now cited it in our updated manuscript.

4. Elaboration on the principles that lead to our formatting of counting, and the source of the quote.

The principles that lead to our formatting of counting borrow heavily from the cogsci literature studying how children learn the numerical meaning of number words.

It is proposed that children initially develop mental representations for “sets of cardinality k”, distinctly from how they represent number words (as they hear utterances of “one”, “two”, “three” …). At the subset-knower level, a learner can 1) routinely utter a list of number words up to N (N > 3); 2) associate their mental models of cardinality to only the first few number words, e.g. “one”, “two”, “three”. At the cardinal-principle(CP)-knower level, a learner discovers the abstract relationship between the list of number words and their meanings for cardinality. This suggests that knowing the list of number words up to N is a necessary but not sufficient condition for the ability to count up to N. The missing part is some inductive mechanism that captures the conceptual change from modeling finite associations to generalization towards infinity.

Transferring the insights to the LM context, “succession”, “helper token” and “shiftedstart” formats suggest three possible ways to teach the model the ordering of number words, thus satisfy the necessary condition. Yet the poor model performance verifies that knowing the number word list isn’t sufficient for knowing how to count. “helper token” is reminiscent of a scenario where a human learner receives word-cardinality supervision more frequently with certain objects than with other objects. Yet the learner has to generalize such word-cardinality mapping to all countable objects. “shiftedstart” is a modification tailored to the consideration that a model is implemented with a finite context window.

Source of the quote: Rips, Lance J. ; Asmuth, Jennifer & Bloomfield, Amber (2006). Giving the boot to the bootstrap: How not to learn the natural numbers. Cognition 101 (3):B51-B60. We cite this paper in our updated manuscript.

The original quote reads: If "k" is a number word that refers to the property of collections containing n objects, then the next number word in the counting sequence "next (k)" refers to the property of collections containing one more than n objects.

It is also quoted in: Piantadosi, Steven T, Joshua B. Tenenbaum and Noah D. Goodman. “Bootstrapping in a language of thought: A formal model of numerical concept learning.” Cognition 123 (2012): 199-217.

5. Use activation patching to localize and trace the development of counting states.

Thanks so much for this suggestion. We agree there is an intimate connection between our work and the mechanistic interpretability literature. We have attempted to interpret our Transformer models via attention-visualization and clustering on intermediate states. We did not use more sophisticated techniques like activation patching or DAS because our models are shallow and each layer likely implements a distinct subtask, rather than progressively promoting the confidence of the final counting result. This has been indicated by our preliminary analysis using logit lens. The logit lens shows that the counting state only exists in the 2nd layer of a 2L Transformer, or the 3rd-4th layer of a 4L Transformer. In the future, it is definitely worth investigating deeper models handling more complex tasks that subsume counting. In such a scenario, mechanistic interpretability tools can be very helpful in tracing the implicit development of counting states.