Building, Reusing, and Generalizing Abstract Representations from Concrete Sequences

## Abstract

Abstract Humans excel at learning abstract patterns across different sequences, filtering out irrelevant details, and transferring these generalized concepts to new sequences.
In contrast, many sequence learning
models lack the ability to abstract, which leads to memory
inefficiency and poor transfer. We introduce a non-parametric hierarchical variable learning model (HVM) that learns chunks from sequences and abstracts contextually similar chunks as variables. HVM efficiently organizes memory while uncovering abstractions, leading to compact sequence representations. When learning on language datasets such as babyLM, HVM learns a more efficient dictionary than standard compression algorithms such as Lempel-Ziv. In a sequence recall task requiring the acquisition and transfer of variables embedded in sequences, we demonstrate HVM’s sequence likelihood correlates with human recall times. In contrast, large language models (LLMs) struggle to transfer abstract variables as effectively as humans. From HVM’s adjustable layer of abstraction, we demonstrate that the model realizes a precise trade-off between compression and generalization. Our work offers a cognitive model that captures the learning and transfer of abstract representations in human cognition and differentiates itself from the behavior of large language models.

## 1 Introduction

Abstraction plays a key role in intelligence (Konidaris, ). Philosophers traditionally view abstract ideas as formed by identifying commonalities across experiences, distilled from concrete impressions grounded in perception (Kant, ; Fichte, ; STERN, ). Psychologists suggest that abstraction arises from personal experiences, such as forming the concept of “whiteness” by observing various white objects (Yee, ; Barsalou, ). Abstract concepts are thought to build on concrete concepts and on top of the previously learned abstractions, thereby varying in complexity (Cuccio & Gallese, ; Van Oers, ; Collins & Quillian, ; Piaget, ). The ability to abstract, which is often seen as a human-specific trait, enables reasoning, generalization, and problem-solving in novel contexts (Ohlsson & Lehtinen, ; Dehaene et al., ; Duncker, ).

We hypothesize that the world contains patterns across scales of time and abstraction. Intelligent agents-facing sequences with nested hierarchical structures- need to model these structures to store, process, and interact in such environments. As a rational strategy, intelligent agents shall characterize the temporal structure via chunking and characterize the abstract structure via identifying common features and grouping collections of different items that play similar roles. To explore these operations, we design a generative model that produces sequences nested with hierarchical structure and propose an approximate recognition model that conjunctively learns to chunk and abstract.

We go beyond previous proposals that introduce chunking as a mechanism for learning and composing complex structures from elementary perceptual units (Gobet et al., ; Miller, ; Wu et al., ) and propose a cognitive model that combines chunking and abstraction in one single system. The model uses abstraction in two key ways: first, by identifying shared features to facilitate efficient pattern retrieval, such as recognizing patterns from learned animals when fur is observed; and second, by categorizing different sequential items that appear in the same context, much like a variable in a computer program— for example, using the category "animal" to represent a cat, dog, or squirrel. These paired mechanisms enable the model to parse sequences into chunks and form abstract patterns based on both concrete and previously learned abstractions. Abstraction allows for memory-efficient, compact representations and reveals recurring patterns at the level of abstract categories. This allows the model to discover increasingly complex or abstract patterns, layer by layer, with controllably varying degrees of detail.

We first demonstrate the benefits of abstraction in memory efficiency and sequence parsing by comparing our algorithm with previous chunking models and other dictionary-based compression methods. Then, we show that the model exhibits human-like signatures of abstraction in a memory experiment requiring the transfer of abstract concepts. In the same experiment, we contrast the model’s generalization behavior with large language models (LLMs), which have demonstrated rudimentary reasoning abilities (Wei et al., ) in recent years. We show that LLMs do not transfer abstract variables and rely more on associative learning than abstraction. We demonstrate the connection between abstraction level and abstract concept transfer by varying the level of abstraction as a parameter in the model. Our work offers a cognitive model that captures the learning and transfer of abstract representations in human cognition and differentiates itself from the behavior of artificial agents.

Figure: Figure 1: Generative Model. The inventory is initialized with a set of atomic units. These units randomly combine into objects. Some objects are randomly selected to become categories. Categories of existing objects have similar interaction properties. The dashed arrow points from those objects to their corresponding categories. These categories further combine with existing objects. An observational sequence is composed of objects randomly sampled from the existing inventory. Categories are latent and never explicitly observed but are manifested in one of the denoting objects.
Refer to caption: extracted/5953942/generative_model.png

## 2 Generating sequences with objects that contain hierarchical abstract structures

We design a probabilistic generative model that generates sequences by sampling objects from an inventory, with these objects organized hierarchically, resembling the structure found in natural sequences—such as molecules composed of chemical elements or the hierarchical nature of language (Abler, ; Sportiche et al., ; von Humboldt & Losonsky, ).

The generative model creates an inventory of recurring objects over $d$ iterations of expansion. As illustrated in Figure 1, the inventory starts with a set of atomic units $\mathbb{A}$.
On each iteration, a novel object or category is created equiprobably. A new category (graded node) is created by pointing to a random selection of objects from the inventory up to the moment (these objects are treated disjunctively). A new object is created by concatenating a random selection of pre-existing objects or categories from the existing inventory. After the inventory has been expanded up to the $d$-th iteration, the independent occurrence probability in the sequence is sampled from a flat Dirichlet distribution $f(p(c_{1}),...,p(c_{|\mathbb{A}|});\alpha_{1},...,\alpha_{|\mathbb{A}|})=\frac
{1}{\mathbf{B}(\mathbf{a})}\prod_{i=1}^{|\mathbb{A}|}P(c_{i})^{\alpha_{i}-1}$, $\alpha_{i}=1\forall i$ and assigned to each object in the inventory. Similarly, a probability is sampled from a flat Dirichlet to assign the occurrence probability of the objects within each category. More details can be found in the Appendix 1.

To create an observational sequence, objects are randomly drawn from the inventory one after another with the assigned probability until they reach the desired sequence length. If the sampled object contains an embedded category, one of the objects corresponding to the category is sampled. This process is repeated recursively until all categories are replaced by specific objects, resulting in a sequence of discrete atomic units.

Intuitively, objects represent recurring observations of specific entities, such as molecules composed of chemical elements. Categories, on the other hand, represent broader categories of entities that share common properties, such as chemical elements belonging to the same class (e.g., noble gases or alkali metals). The observation sequence forms a nested hierarchy, where entities and their categories frequently interact and combine with others.

## 3 Learning abstractions from sequences

We ask what computational principles could help an agent discover objects and categories from such observational sequences without supervision. We propose that two mechanisms suggested by the cognitive literature are vital: chunk proposal and variable discovery. Chunking concatenates learned objects and forms new ones; variable discovery groups chunks with similar interaction properties into a category. We build on top of the hierarchical chunking model (HCM) (Wu et al., ), which learns a belief set $\mathbb{B}$ of a chunk dictionary $\mathbb{C}$ from discrete sequences. We expand the model so that it can also learn variables while improving the memory efficiency of the model.
By identifying stably recurring entities as chunks and grouping similar entities into categories as variables, the agent can learn a structured inventory of identifiable patterns and use these patterns as entities to parse the sequence, leading to a more compressed factorization of perceptual sequences.

HVM learns a belief set $\mathbb{B}$ that contains both a dictionary of chunks $\mathbb{C}$ and variables $\mathbb{V}$. The variables are proposed as abstract entities based on the transition and marginal counts. As shown in Figure 2a, each variable $v\in\mathbb{V}$ denotes a set of chunks $E(v)=\{c_{j}\}$, $c_{j}\in\mathbb{C}$. The model also learns the probability of each chunk that a variable denotes $\forall v\in\mathbb{V}$, $\sum_{j}P(v\rightarrow c_{j})=1$, $c_{j}\in\mathbb{C}$.

Figure: Figure 2: HVM builds up a representation graph and a parsing graph. a. A representation graph contains the learned chunks (nodes with solid colors) $\mathbb{C}$ and the contained variables (nodes with gradient colors) $\mathbb{V}$. Black arrows denote concatenation. Gray and dashed arrows point from chunks of the same category to the variable node that denotes this category. b. Abstraction organizes memory in a parsing graph. Nodes shaded by gray are abstract chunks being the common prefix intersection of its children. During parsing, to allocate to the matching chunk in $\mathbb{C}$, the model starts searching from the root of the parsing tree and traverses to the deepest node consistent with the upcoming sequence content. c. Upon completing each sequence parse, HVM updates counts on chunk frequencies and transitions and proposes inventory expansions, enabling a layer-wise discovery of recurring patterns per iteration, from specific to the more abstract. d. HVM proposes variables amongst correlated consecutive chunk pairs. e. Chunk proposal.
Refer to caption: extracted/5953942/hvm.png

#### Parsing the sequence one chunk at a time

A fundamental feature of the model is to parse sequences in chunks as the basic cognitive units (Miller, ).
Along with each parse $t$, the transition counts between the previous $c_{L}$ and next chunks $c_{R}$ are recursively updated: $T_{ij}(t+1)=T_{ij}(t)+[i=c_{L}][j=c_{R}]$
($[\cdot]=1$ if the argument is true and 0 otherwise) and along with the identification frequency of each parsed chunk $M_{i}(t+1)=M_{i}(t)+[i=c]$. When modeling human behavior, each entry of $M$ and
$T$ multiplies with a memory decay parameter $\theta$ per parsing
step. The probability of observing a sequence of parsed chunks
$c_{1},c_{2},...,c_{N}$ the becomes $P(c_{1},c_{2},...,c_{N})=\prod_{c_{i}\in\mathbb{C}}P_{\mathbb{C}}(c_{i})$.

To parse a sequence, HCM iteratively chooses the biggest chunk amongst its learned dictionary $\mathbb{C}$ consistent with the upcoming sequence. The end of a previous parse initiates the next parse. As the dictionary size $|\mathbb{C}|$ increases, searching for the biggest consistent chunk becomes computationally expensive (Schreiber et al., ).
In HVM, we introduce one notion of abstraction as finding commonalities amongst memory items to organize memory structure and speed up chunk retrieval during parsing. Memory items in the learned dictionary are organized into a hierarchical parsing graph that connects chunks with their common prefixes. Hence, all children chunks are different except for sharing a common prefix from the parent. The parsing graph arranges the chunks in $\mathbb{C}$ into a prefix Trie structure (Figure 2b), reflecting the cue-based, content-addressable nature of memory retrieval (Cunnings & Sturt, ; Dotlačil, ; Anderson, ). This design reduces search time to retrieve a chunk as arranged in the parsing graph, commonly used in predictive text or auto-complete dictionaries to speed up search steps (Fredkin, ).
At every parsing step, HVM identifies the deepest chunk in the parsing graph that is consistent with the upcoming sequence. The end of the previous parse initiates the next parse. The search process would take the time complexity of $O(D)$, scaling with the depth $D$ of the tree compared to HCM time complexity of $O(|\mathbb{C}|)$ scaling with the size of $\mathbb{C}$. The appendix shows a guarantee to reduce the number of parsing steps for chunk retrieval A.4.

#### Learning chunks

From parsed sequences, the model estimates the occurrence probability of chunk via the entries of $M$ as $P_{\mathbb{C}}(c_{i})=\frac{M_{i}}{\sum_{c_{j}\in\mathbb{C}}M_{j}}$.
The model starts with the null hypothesis $\mathcal{H}_{0}$ that all consecutively parsed chunks $c_{L}$ and $c_{R}$ are statistically independent $P(c_{L},c_{R})=P(c_{L})P(c_{R})$. If a significant correlation is found between consecutively parsed chunk pairs (with $p=0.05$), the null hypothesis is rejected, and the pair is concatenated into a new chunk, $c_{L}\oplus c_{R}$, which is then added to the dictionary $\mathbb{C}$ as a new entry. Upon creating each new chunk, an edge from the left parent chunk (sharing the same prefix) connects to the newly created chunk in the parsing graph. When no parent chunk can be found, an ancestor node is created in the parsing graph, usually the sequence’s atomic units. We prove in the SI section A.3 that under restricted conditions in which the sub-objects constituting the object in the ground truth are parsed faithfully by the model as sub-chunks, then these sub-chunks will be eventually proposed to concatenate into one chunk.

#### Learning variables

A variable denotes distinct observations appearing in the same context (here defined as distinct chunks sharing preceding and succeeding chunks). Given consistent parsing of subchunks as object combination components in the generative model, the true chunks that belong to the same category will necessarily appear in the preadjacency and postadjacency entries (more explanation in SI A.3). HVM proposes variables amongst the significantly correlated chunks ($p\leq 0.05$) in the transition matrix consistent with this structure. For example, consider the case that the sequence includes A-ABC, A-DC, and ABC-ED, DC-ED. This suggests that ABC and DC play similar roles relative to A (coming after) and ED (before). Therefore, ABC and ED can be proposed as a new variable V to represent the abstract property that captures the distinct entities. V denotes ABC and DC, and the model identifies V if either ABC or DC is identified during parsing, as illustrated in Figure 2d and Figure 7 in SI.

Amongst the correlated consecutive chunk pairs, the model identifies all eligible transitions by intersecting the post-adjacency columns with the pre-adjacency rows, proposing a set of chunks $E(v)={c_{1},c_{2},...,c_{j}}$ represented by a new variable $v$. This variable proposal is accepted if the set of chunks that satisfy the condition $T_{min}\leq|E(v)|\leq T_{max}$ and $\sum_{c_{i}}M(c_{i})\geq freq_{T}$.
A variable denotes a set of chunks $E(v)$ and is identified if any of the chunks that it denotes is parsed (Figure 2c). Together, the common preceding chunk, in conjunction with the newly proposed variable, followed by the common succeeding chunk, is concatenated and proposed as a novel chunk $c_{L}\oplus v\oplus c_{R}$ to add to the inventory $\mathbb{C}$. An edge that connects $c_{L}$ to the new chunk $c_{L}\oplus v\oplus c_{R}$ to be added to the parsing graph, as illustrated in Figure 2d. This process introduces chunks with embedded variables and takes the computational complexity of $O(PQ)$, where $P$ and $Q$ are the numbers of unique entries of the adjacency and postadjaency chunks amongst the correlated consecutive chunk pairs. Two variables are merged into one if they share the same preceding and succeeding chunks. During parsing, a chunk is consistent with the sequence if any of its included variables contain a denoting chunk that is consistent with the sequence. Upon identifying a chunk during parsing, the marginal and transition count for both the chunk and the immediate variables that the chunk belongs to is incremented.

#### Representation cleaning

Upon completion of each sequence parsing, the model uses correlations to propose new variables and chunks. It then uses the expanded inventory for the next parse. Unused variables and chunks are deleted upon the completion of each parsing iteration.

## 4 Results

Figure: Figure 3: a. The effect of hierarchical memory structure on parsing search steps. b. Comparison between models in terms of sequence length after parsing. GT denotes the ground truth sequence length by the generative model. c. Model comparison based on sequence likelihood. d. Model comparison based on coding efficiency. Example model comparison with sequence length $|S|=1000$, nested hierarchy depth $d=30$, atomic set of size $|A|=10$.
Refer to caption: extracted/5953942/modelcomparison.png

### 4.1 Model evaluation

HVM is an approximate inverse of the generative model, as
in practice, learning the ground truth hierarchical patterns that generate observed data is a nonidentifiable problem (Post, ; Greibach, ). Therefore, we use a set of measures for model evaluation, focusing on parsing search steps, sequence length, sequence negative log-likelihood, and encoding efficiency.
We trained models on sequences generated by the hierarchical generative model until convergence. For each iteration, the models parse the entire sequence using the dictionary updated from the previous iteration and propose novel chunks/abstractions upon completing the parse. While HVM learns both chunks and variables per iteration, HCM learns only chunks and no variables. Previous research has related human memory in specific tasks to lossy compression (Nassar et al., ), with abstraction playing a crucial role in successful learning and transfer in sequence memory recall tasks. For reference, we also compared the models with LZ78, an off-the-shelf compression algorithm underlying compression schemes such as GIF and PNG, which also parses sequences into chunks and builds a dictionary to compress sequence data (Ziv & Lempel, ). Comparisons are shown in Figure 2.

Organizing chunks in a parsing graph based on common prefix reduces parsing search steps We compared HVM with HCM, which does not organize memory into a hierarchical parsing graph. Figure 3 a. shows that organizing chunks in a parsing graph dramatically reduces the average number of parsing search steps, i.e., the number of search steps needed for the model to locate the biggest chunk per parse. This search step now scales with the depth of the prefix tree compared to the size of the inventory in HCM. More discussions can be found in A.4.

Discovering bigger recurring patterns
We compared HVM with its counterpart, HCM, which does not learn variables at the end of the learning iteration. Figure 3 b compares sequence length $|W|$ after parsing. HVM transforms the sequence $|S|$ into a code with a much smaller size $|W|$ compared to HCM and LZ78 and is on par with the ground truth (GT). Learning variables that denote distinct chunks occurring in similar contexts helps HVM to learn bigger patterns underlying the sequence on the description level of these variables.

Parsing sequences with higher likelihood Figure 3 c compares the negative log likelihood ($-\log P(S)=\prod_{c_{i}\in\mathbb{C}}P(c_{i})$) of the parsed sequence upon convergence. HVM parses sequences more efficiently, as variables recur more frequently in sequences than their representing chunks, and therefore, the model that learns variables parses the sequence with higher likelihood.

Encoding more efficiently
In many applications, the size of the dictionary affects compression efficiency (Navarro & Mäkinen, ; Ferragina & Manzini, ). We compare the encoding efficiency, i.e., the ratio between the dictionary size (number of entries) and the original sequence length $S$. Figure 3d shows the relation between the ratio and the sequence length. To encode a sequence of the same length, LZ78 creates a bigger dictionary than HVM and HCM. Models that harness the embedded hierarchical structure in sequences encode sequences more efficiently and learn a smaller dictionary to encode the same sequence length.

### 4.2 Learning from real-world sequential data

**Table 1: Model comparison on alternative sequences. NLL stands for negative log-likelihood.**
| Data Domain | Model | Compression Ratio | NLL | Coding Efficiency |
| --- | --- | --- | --- | --- |
| CHILDES (MacWhinney, ) | LZ78 | 0.38 | 2837.50 | 0.34 |
| HCM | 0.51 | 2783.71 | 0.05 |  |
| HVM | 0.36 | 1953.01 | 0.06 |  |
| BNC (BNC Consortium, ) | LZ78 | 0.39 | 3136.67 | 0.37 |
| HCM | 0.65 | 3591.60 | 0.06 |  |
| HVM | 0.50 | 3108.33 | 0.08 |  |
| Gutenberg (Gerlach & Font-Clos, ) | LZ78 | 0.39 | 3156.61 | 0.37 |
| HCM | 0.69 | 3770.36 | 0.06 |  |
| HVM | 0.54 | 3252.84 | 0.12 |  |
| Open Subtitles (Lison & Tiedemann, ) | LZ78 | 0.41 | 3395.09 | 0.39 |
| HCM | 0.74 | 4151.89 | 0.07 |  |
| HVM | 0.63 | 3764.48 | 0.07 |  |

Going beyond artificially generated sequences, we evaluate HVM, HCM, and LZ78 in text domains from the BabyLM language dataset, which contain text snippets from a collection of data domains Warstadt et al. (). For each data domain, we took random snippets of 1000 characters and calculated evaluation metrics, including compression ratio (the number of tokens before compression divided by the number of tokens after compression), sequence complexity (negative log-likelihood), and compression efficiency (the length of the compressed sequence divided by the number of dictionary entries).

As shown in table 1, LZ78 performs well in terms of compression efficiency, which is expected given its design purpose. However, the HVM model exhibits notable advantages when considering alternative evaluation metrics. Specifically, for text across the four data domains analyzed, cognitive models that incorporate the hierarchical structure of data outperform traditional compression methods in terms of encoding efficiency.This is because LZ78, which does not make strong assumptions about sequence structure, tends to create redundant entries in its dictionary. While this redundancy reduces the sequence length after compression, it introduces many infrequently used entries. In some data domains, HVM outperforms LZ78 in compression ratio and negative log-likelihood as well. Amongst all domains, HVM compresses the sequence further and parses the sequence with lower complexity than HCM.

### 4.3 HVM resembles human sequence memorization and transfer

Figure: Figure 4: a. A sequence memory task that demands transferring a variable x from the training to the test block. b., c., d., e., Complexity (negative log-likelihood) progression of HVM correlates with human memory recall time in the training (b., c.) and the transfer block (d., e.). Memory decay parameter $\theta=0.996$. Marker size increases with trial number.
Refer to caption: extracted/5953942/human_experiment.png

We take the relation between transfer to learning abstractions to the setting of a memory experiment that demands learning and transferring variables (Wu et al., ).
We ask whether HVM resembles aspects of human learning while enjoying the advantage of learning an interpretable dictionary.

In the experiment, 112 participants were instructed to recall a sequence of presented colors from memory (Figure 4 a). Participants were randomly assigned to a variable group and a control group. During the training block (40 trials), the control group was instructed to remember a fixed sequence BADF DCBF FEDB for each trial (each letter denotes a distinct color). In contrast, the variable group was instructed to remember sequences overlapping in 9 of the 12 colors: BXDF DXBF FXDB. A variable X, however, appeared at serial positions 2, 6, and 10, which could be occupied with the letters A, C, or E with equal probability for each trial. After the training block, both groups were then tested on the transfer block. The transfer sequence overlapped with the training sequence only at the variable positions: DXBF FXDB BXFD. The time participants took to recall the entire sequence for each trial was recorded. Previous studies suggest human recall time relates logarithmically to the perceptual predictability of the sequence (Carpenter & Williams, ; Anderson & Milson, ; Smith & Levy, ; Elman, ). We compare human recall time to the model’s negative log-probability (likelihood) evaluated on the instruction sequence given.

To simulate the sequence likelihood for trial $n$, we used the instruction sequences up to trial $n-1$. This allowed the HVM to learn in an online manner, i.e. abstractions and chunks were proposed upon each parsing completion. For comparison purposes, we also simulated HCM with the same parameter setting, and an associative learning model (AL) that updates first order transitions between atomic sequential units.
The sequence likelihood was evaluated as $-\log P(S)=-\log P(c_{1})\prod_{i=2,...,n}P(c_{i}|c_{i-1})$. $c_{1},c_{2},...,c_{n}$ are the units used to parse the sequence (chunks for HCM and HVM and atomic units for the associative learning (AL) model).

Figure 4 shows the relation between model sequence likelihood and human recall time during the training (b, c) and the transfer block (d, e). The size of the dot represents the trial number, and the shape of the dot represents the group (the triangle being the variable group, the circle is the control group). Figure 4b and d show the R-squared goodness-of-fit regressing the various models’ sequence likelihoods onto human subjects’ sequence recall times.
The sequence negative log-likelihood from the HVM correlates with human recall time during the training ($R=0.86,p\leq 0.001$) and transfer blocks ($R=0.7,p\leq 0.001$). The latter suggests that HVM can generate behavior that resembles that of human knowledge transfer in the memorization of novel sequences with embedded variables.

### 4.4 Comparing abstraction learning and transfer in LLMs

Figure: Figure 5: Comparison between human, variations of cognitive models, and AI models on the transfer block of the memory recall experiment. Bar plot shows the average human sequence recall time, and the sequence negative log-likelihood evaluated by the various cognitive and large language models.
Refer to caption: extracted/5953942/llm.png

Given that large language models (LLMs) have been praised for their emergent abilities (Wei et al., ), yet also compared to "lossy compression" (Chiang, ) and struggle with tasks that demand abstract thought (Fleuret et al., ; Odouard & Mitchell, ), we want to investigate whether models with or without abstraction better describe them. Specifically, we ask whether LLMs abstract similarly to humans and how their behavior compares to cognitive models incorporating abstraction. To explore this question, we conduct the same sequence recall experiment on LLMs.

To do that, we adapt the instructions from the human experiment into prompts for in-context learning in LLMs. The LLMs are tasked with predicting the next subsequent tokens based on the context of previously seen instruction sequences. The specific prompt is taken from the instruction given to the human participants: “Please remember the following sequence: BADFDCBFFEDB, …, BCDFDCBFFADB.” We then calculate the conditional probability of the next token, $z_{i}$, given the instruction sequence history up until the current token $P(z_{i}|prompt)$. After obtaining this probability, the subsequent token in the instruction is added to the prompt, and the LLM’s conditional probability for the following token is updated accordingly.
Using this prompt-chaining method, we can calculate LLM’s negative log-likelihood for the next tokenized instruction sequence: $-\log P(S)=-\log P(z_{1}|prompt)\prod_{i=2,...,n}P(z_{i}|prompt_{i-1})$, analogous to the cognitive models. We apply this approach to evaluate the token prediction likelihood in four large language models: GPT-2 (Radford et al., ) and three variations of the Llama 2 model (Touvron et al., )—Llama with 7 billion parameters (Llama 7B), 13 billion parameters (Llama 13B), and 70 billion parameters (Llama 70B).

Shown in Figure 5 are the transfer behavior across humans, LLMs, and various cognitive models for comparison. Supplementary section A.11 also shows the R-square value regressing model negative log-likelihoods on human recall time. For humans, the group trained on sequences with embedded variables recalls transfer sequences faster than the group trained on control sequences. Relating sequence recall time with sequence negative log-likelihood, the cognitive models HCM and HVM, on average, exhibit lower sequence negative log-likelihood after learning from a training block that shares variables with the transfer block. In contrast, the associative learning model and all variants of large language models do not differentiate between training sequences that share variables with the transfer block and those from a training block without transferrable variables.

### 4.5 Abstraction, distortion, generalization

Figure: Figure 6: a. New chunks or variables are created from previously learned ones, adding increasingly nested structures to the representation graph. b. As the allowable distortion increases (moving right on the x-axis), the required rate to encode the data decreases (moving down on the y-axis). Introducing variables enables a more compressed sequence, which trades off with higher uncertainty introduced by the variables. c. Abstraction and transfer: The higher the abstraction layer, the higher the likelihood (lower negative log-likelihood) that HVM parses novel sequences.
Refer to caption: extracted/5953942/RD.png

With a model that can learn interpretable abstraction, we can delve into the relationship between learning layers of abstraction, compression, and uncertainty. HVM updates its dictionary each iteration by proposing chunks and variables, which are used to parse the sequence for the next iteration. New chunks or variables are created from previously learned ones, adding increasingly nested structures to the representation graph.
This feature affords a controlled accessment of the relation between the level of abstraction, the amount of distortion that abstract representation introduces, and its relation to transfer.
We measure nestedness using the representation complexity
$RC(\mathbb{V})=\sum_{v\in\mathbb{V}}\sum_{u\in\mathbb{E}(v)}-\log P(u|v)$, which is closely related to the encoding cost of the representation graph A.5. We also measured the uncertainty carried by the embedded variables in the chunks via entropy formulated as $\sum_{c\in\mathbb{C}}P(c)\sum_{v\in V(c)}\sum_{u\in E(v)}-P(u|v)\log P(u|v)$.

Figure 6a shows the relation between the three factors as a consequence of increasing abstraction learning iterations. As the representation graph becomes increasingly nested, the newly learned chunks explain a longer part of the sequence, and the chunks to parse the sequence contain more uncertain variables. This trade-off between compression and uncertainty reflects rate-distortion theory specifying that the best possible compression of a signal $X$ contains a lower bound on quality loss specified by the Rate-Distortion Function (R(D)): $R(D)=\inf_{Q}R_{Q}\text{s.t.}\mathbb{E}[d(X,\hat{X})]\leq D$ (Shannon, ; Cover & Thomas, ). Taking representation complexity as a distortion function, as the level of abstraction increases, HVM learns patterns that span and predict longer parts of the sequence while more distortion and uncertainty are introduced. This observation on distortion with the level of abstraction resonates with previous findings on an increased level of mental errors with learning more abstract representations in humans (Lynn et al., ).

Higher levels of abstraction implies more flexible transfer
If learning higher abstraction layers implies more distortion, what would be the benefit apart from compression? We suggest that the other side of the coin lies in generalization and demonstrates the effect of abstraction on model transfer. We trained HVMs with increasing abstraction layers and evaluated the models’ transfer likelihood upon parsing a novel sequence. As shown in Figure 6b, the higher the abstraction layer, the higher the likelihood (lower negative log-likelihood) that HVM parses the transfer sequence.
To compare, we also evaluated the transfer performance of the chunking model (HCM) with an increasing level of iteration. While the transfer performance for HCM improves with more layers of chunk learning, it converges at a higher negative log-likelihood. Learning an increasing abstract representation by the HVM enables it to compress novel transfer sequences in a more succinct way. Furthermore, the more abstraction layers are acquired, the higher the relative advantage for HVM that learns abstraction holds over the HCM that only learns chunks.

## 5 Related Work

Previous modeling work on abstraction can be divided into two categories. The first category implements abstraction as searching for commonalities in explicitly symbolic systems. These are predominately cognitive models meant to explain human abstraction and transfer behavior, such as humans can quickly solve a new problem by finding its conceptual analogies with old problems. Lu et al. () implemented abstraction and concept analogy as finding a common graph structure between a ground problem and an analogical problem in a semantic relational network that captures this property. Another example is the copycat project (Hofstadter & Mitchell, ) that models how people generalize rules shared amongst a couple of examples by searching for rules from a network of concepts. These works model abstraction on symbolic, explicit representations of knowledge graphs but do not address how the explicit knowledge graph itself arises from perceptual data. Our work proposes a mechanism for learning explicit abstraction from sequences of perceptual experience.

The second category implements abstraction in implicit connectionist systems. Works on meta-learning models and LLMs suggest their ability to generalize across contexts and solve problems in a way similar to humans (Wei et al., ; Binz & Schulz, ) in some tasks while failing short on other abstract reasoning tasks (Fleuret et al., ). Meanwhile, abstraction has been argued to be implicitly present in artificial neural networks (Yee, ; Kozma et al., ; Johnston & Fusi, ; Ito et al., ) and biological neural activities (Bernardi et al., ; Goudar et al., ). However, the abstractions neural networks learn are challenging to interpret (Fan et al., ). Relative to this approach, our work provides a reductionist cognitive model that explicitly specifies the minimal components needed for a model to learn interpretable abstract structure from sequences.
Besides cognitive models, our work also differs from other approaches to sequence learning, such as probabilistic context-free grammar (PCFG) (Jelinek et al., ) or adaptor grammar (Johnson et al., ). Our generative mechanism offers a probabilistic, hierarchical sequence generation model relying on chunk-based recursive generation and inventory growth rather than formal grammar rules. HVM’s learning is also inventory-based instead of manipulating many substructures and rules.

## 6 Discussion

Our work has limitations. One is that variables are only proposed to be embedded between chunks and cannot come at the beginning or end of sequences, restricting the location of discoverable variables. Secondly, representation learned later in iteration depends on the earlier acquired representations. Furthermore, sometimes the variable structure can be arbitrarily nested depending on the learned representations up until that moment. Future work may look at optimizing the structure of the representation via refactorization features during learning. Finally, our work focused on the cognitive resemblance of HVM and has not explicitly optimized the model specifically for computational efficiency. Future work may look into optimizing run-time efficiencies of models that exploit hierarchical structures in data adapting to specific application proposes.

Our work opens up interesting future directions both in cognitive science and machine learning. Previously, grammar learning, chunk learning, and statistical/associative learning were studied in isolation as distinct aspects of sequence learning. We propose via HVM that the three can be treated as finding invariant recurring chunks from sequences, the means of it (statistical/associative learning), and the consequence of it (learning grammar-like structures). Our work suggests a normative origin of concrete and abstract chunk learning as a learning agent uncovering the underlying entities that constitute perceptual sequences. Future work can relate this model to the development of concept understanding during development.
Meanwhile, the close tie between abstraction and generalization also urges future hypothesis-driven research regarding preconditions for learning abstract concepts to acquire more abstract representations. This can help to illuminate the emergence of abstract representation during excessive data exposure and training and its relation to the generalizability of machine learning models (Power et al., ; Miller et al., ).

## 7 Conclusion

We propose a hierarchical variable learning model (HVM) that builds up entities of recurring abstract and concrete patterns from perceptual sequences, utilizing chunking, finding commonality, and variable proposal chunking and abstraction to unearth independently recurring entities in sequences with nested hierarchical structures. We show the model’s resemblance to human sequence learning and transfer and highlight the relation between abstraction and generalization. Our work is relevant for cognitive science and the AI community in understanding memory in humans and machines.

## 8 Reproducibility Statement

Detailed information about the HVM algorithm, proof, generative model, test and experimental details and results can be found in the supplementary information section. The code used for the algorithm and experiments will be available as a comment to the reviewers and area chairs as a link to an anonymous repository as soon as the discussion forum for all submitted papers is open.

## Appendix A Appendix / supplemental material

### A.1 Set up

An observational sequence $S$ is made up of discrete, integer valued, size-one elementary observational unit coming from an atomic alphabet set $\mathbb{A}$. One example of such an observational sequence $S$ is:

$$ $010021002112000...$ $$

An example belief set that contains only concrete chunks can be $\mathbb{B}=\{0,1,21,211,12,2112\}$.

Using the belief set to parse the sequence $S$ results in the following partition. 0 1 0 0 21 0 0 2112 0 0 0.

Another example belief set $\mathbb{B}$ that contains chunks $\mathbb{C}=\{21v,0100,000\}$ with embedded variables $\mathbb{V}=\{v\}$. The denoting set of $E(v)=\{00,12\}$. Then the sequence $S$ is parsed as 0100 $21v$ $21v$ 000.

###### Definition 1 (Completeness) .

We say that a belief set is *complete* if at any point during the sequence parsing process, the upcoming observations can be explained by at least one chunk in the belief set.

In this work, the learning mechanism guarantees that the belief set is complete.

###### Definition 2 (Parsing Length $|W|$ ) .

A parsing length $|W|$ of a sequence is the length of the sequence measured in chunks.

###### Definition 1 (Completeness) .

###### Definition 2 (Parsing Length | W | 𝑊 |W| | italic_W | ) .

### A.2 Generative Model

Figure: Algorithm 1 Pseudocode to generate sequences with nested abstract hierarchies.

A new object is created by concatenating a random selection of pre-existing objects or categories from the existing inventory. After the inventory has been expanded up to the $d$-th iteration, objects are assigned with an independent occurrence probability sampled from a flat Dirichlet distribution $f(p(c_{1}),...,p(c_{|\mathbb{A}|});\alpha_{1},...,\alpha_{|\mathbb{A}|})=\frac
{1}{\mathbf{B}(\mathbf{a})}\prod_{i=1}^{|\mathbb{A}|}P(c_{i})^{\alpha_{i}-1}$, $\alpha_{i}=1\forall i$. Where the beta function when expressed using gamma function is: $\mathbf{B}(\mathbf{a})=\frac{\prod_{i=1}^{|\mathbb{A}|}\Gamma(\alpha_{i})}{
\Gamma(\sum_{i}^{|\mathbb{A}|}\alpha_{i})}$, and $\mathbf{a}=(\alpha_{1},..,\alpha_{|\mathbb{A}|})$. The parameters $(\alpha_{1},..,\alpha_{|\mathbb{A}|})$ are identically set to one.

Similarly, a probability is sampled from a flat Dirichlet to assign the independent occurrence probability of the set of object $E(v)$ that each category $v$ denotes. $\forall v\in\mathbb{V}$, $f(p(c_{1}),...,p(c_{|E(v)|});\alpha_{1},...,\alpha_{|E(v)|})=\frac{1}{\mathbf{
B}(\mathbf{a})}\prod_{i=1}^{|E(v)|}P(c_{i})^{\alpha_{i}-1}$, $\alpha_{i}=1\forall i$. This procedure is done for each created category.

### A.3 Approximate Recognition Inverse

###### Theorem 1 .

If the left entity $c_{L}$ and the right $c_{R}$ (which can be either a chunk or a variable) of a ground truth variable $v$ in addition to its denoting chunks $c_{1},c_{2},...,c_{m}$ has been learned, and every parsing of $c_{L}$, $c_{R}$, and $c_{1},c_{2},...,c_{m}$ is consistent with the constitution of the sequence by the its way of generation, then $c_{1},c_{2},...,c_{m}$ will be necessarily proposed by the common adjacency and common preadjacency criterion into a novel variable $v^{\prime}$ and the true denoting entities will be a subset of the denoting set $E(v^{\prime})$, $\{c_{1},c_{2},...,c_{m}\}\in E(v^{\prime})$.

###### Proof.

By definition, $\{c_{1},c_{2},...,c_{m}\}$ is in the adjacency $Adj(c_{L})$ entries of $c_{L}$ and the preadjacency entries of $c_{R}$, $Preadj(c_{R})$.
And therefore, $\{c_{1},c_{2},...,c_{m}\}\in Adj(c_{L})\cap Preadj(c_{R})$ and hence will be included in the set of denoting entities for a new variable.
∎

Figure: Figure 7: Common adjacency and preadjacency structure to identify a variable.
Refer to caption: extracted/5953942/ccce.png

###### Theorem 2 .

In an infinitely long sequence, a chunk $c$ in the generative model is made up by concatinating the entities $\{c_{1},c_{2},...,c_{n}\}$, and these entities $\{c_{1},c_{2},...,c_{n}\}$ are parsed in an identical way as how the generative model samples $c$, then HVM will eventually learn to chunk $c^{\prime}$ including all the entities in $\{c_{1},c_{2},...,c_{n}\}$.

###### Proof.

By contradiction. If any of the entities are not included in the learned chunks, a correlation will still exist in the transition entries between subparts that compose $c$, which will be resolved by the next chunk proposal iteration.
∎

In practice, identifying the ground truth representation graph is much more complicated, as the representations learned by HVM can be mapped to a context-sensitive grammar A.6, learning the correct chunks that exactly match the generative model relates to the non identifiability problem that multiple grammars can generate the same set of observed data (Post, ; Greibach, ). The sequence length comparable to the ground truth is possible to obtain. However, the dataset creation method does not guarantee a single optimal way, this is usually referred to as the undecidability problem in grammar induction literature: inferring the exact grammar from positive examples is undecidable. Also is the case for deciding if two grammar classes are equivalent. Our formulation of the generative model can be shown to be equivalent to context-sensitive grammar A.6, which is more complex and undecidable than context-free grammar. No general algorithm can take any finite set of examples and produce a grammar that will generate all and only those examples. Because of undecidability, heuristic and approximate methods are often used in practice in the linguistics grammar induction literature and formal language theory. These methods aim to find solutions that are good enough rather than exact ones. As the optimality of the ground truth cannot be guaranteed due to the common source of this problem with grammar induction, our approach restricts and simplifies the structures of patterns that are feasible for the HVM. Since there is a theoretical limit to what can be achieved when inferring grammatical structures from data. Our approach to HVM uses approximate, heuristic, and probabilistic methods to tackle this problem by imposing parsimonious computational characteristics that have been pronouncedly observed in the cognitive science learning literature. Instead of comparing the model with the specific chunks of the ground truth, we use a set of evaluation measures to evaluate the model’s performance.

Figure: Algorithm 2 HVM (online version, for learning sequences from human experiments)

###### Theorem 1 .

###### Proof.

###### Theorem 2 .

###### Proof.

### A.4 Parsing Search Steps

HCM retrieves learned chunks to match them with the upcoming sequence, parsing the largest chunk that aligns with the sequence. However, as the dictionary size $|\mathbb{C}|$ grows, the number of search steps increases, leading to inefficiency. To address this, HVM organizes the chunks in $\mathbb{C}$ within a parsing graph, harnessing shared nodes across multiple chunks to speed up the chunk identification process.

###### Definition 3 (Parsing Graph (PG)) .

Parsing graph is a graph for chunk identification. The nodes inside such a graph are the chunks $\mathbb{C}$. Each parent node is the overlap of all of its children.

To parse a chunk, the model traverses the memory tree structure to find the path up to the deepest node inside the tree consistent with the upcoming sequence. Pseudocode 3 describes this process.

Figure: Algorithm 3 Pseudocode for traversing a tree to find a path consistent with an upcoming sequence

###### Definition 4 (Parsing Search Steps) .

Parsing search step refer to the number of search comparison made in the parsing graph to find the deepest chunk in the tree consistent with the upcoming sequence.

###### Definition 3 (Parsing Graph (PG)) .

###### Definition 4 (Parsing Search Steps) .

#### Example

Shown in Figure 8, when the sequence upcoming is 123, one starts from the ancestors of the graph and check whether 1 or 2 is at the beginning of the sequence, identifies 1, and proceeds into the subtree which stems from 1. The leaves are contains 12 and 13. Then HVM checks whether 12 is in the sequence or 13, thereby identifying 12.

The mechanism to identify the biggest concrete chunk that can be used to parse the sequence involves the following steps:

- •
Search from the top of the tree (nodes with no parents)
- •
Find the node in the next layer consistent with sequence
- •
Go to the children of the node until the node contains no more children (leaf node) or none of the node’s children is consistent with the sequence

As illustrated in Figure 8, the parsing search steps of chunk 12 is: $PSS(12)=2+2=|A|+|R(A)|$
For chunk 221: $PSS(221)=2+2+3$
For 21: $PSS(21)=2+2$

Figure: Figure 8: Example process when parsing a chunk using parsing graph. Gray region denotes chunk overlaps, which are the non-leaf nodes inside the parsing graph being the common prefix of their children.
Refer to caption: extracted/5953942/parsing.png

#### The advantage of memory abstraction

###### Theorem 3 (Guarantee on fewer search steps) .

Identifying a chunk in a tree-structured memory takes fewer search steps than without.

###### Proof.

The hierarchically structured memory system reduces the searching step to the number of branches on the path that leads to the identified chunk, which is a subset of all nodes in the tree.
∎

###### Theorem 3 (Guarantee on fewer search steps) .

###### Proof.

#### Expected parsing search steps

For a chunk $c$ that occur with probability $P(c)$, the parsing search steps is denoted as $PSS(c)$.

As an example, three chunks $c_{1}$, $c_{2}$, and $c_{3}$ composes a sequence and they are parsed with probability $P(c_{1})$, $P(c_{2})$, and $P(c_{3})$ in a sequence.

Without the hierarchical memory structure, the average parsing search steps to identify chunks in the sequence is:

$$ $PSS(c_{1})P(c_{1})+PSS(c_{2})P(c_{2})+PSS(c_{3})P(c_{3})$ $$

With the prefix Trie, the number of times needed to check whether a chunk matches a certain abstraction branch requires a number of parsing steps:

$$ $PSS(c)=N_{children}(Pa(c))$ (1) $$

$Pa(c)$ denotes the parent of chunk $c$ in $PG$, $N_{children}(Pa(c))$ is the number of children that chunk $c$’s parent contain.
An abstract chunk $a$ in such a parsing graph can be the prefix intersection of three chunks $c_{1}$, $c_{2}$, and $c_{3}$, $a=c_{1}\cap c_{2}\cap c_{3}$.
Parsing abstraction summarizes all the subordinate chunks that underlies such abstraction. Therefore the abstraction node is more likely to be parsed compared to individual chunks.

$$ $P(a)=(P(c_{1})+P(c_{2})+P(c_{3}))$ $$

Additionally, abstraction can be used as an anchor to find the subsequent denoting chunks. $P(c_{1}|a)$, $P(c_{2}|a)$ and $P(c_{3}|a)$. The expected parsing search steps to identify chunks for such sequence $S$ becomes:

$$ $\mathbb{E}_{S}(PSS)=PL(c_{1}\cap c_{2}\cap c_{3})(P(c_{1})+P(c_{2})+P(c_{3}))+ PL(c_{1}-a)P(c_{1}|a)+PL(c_{2}-a)P(c_{2}|a)+PL(c_{3}-a)P(c_{3}|a)$ $$

Generalizing this formula to any parsing graph, the expected parsing search steps given the parsing graph’s internal abstraction and concrete chunks would be

$$ $EPSS(PG)=\sum_{c\in\mathbb{C}}P(c)\sum_{path(c)}len(N_{children}(PA(c)))$ (2) $$

$path(c)$ is the path starting with the root node of the graph that leads to the identification of the chunk node c. Since $P(c)_{c_{i}\in path(c)}=P(a)\prod_{c_{i}\in path(c)}P(c_{i}|pa(c_{i}))$, one can also give a lower and upper bound on the number of parsing search steps needed to arrive at a random chunk in the parsing graph:

$$ $EPSS(PG)=\sum_{v\in\mathbb{C}}P(v|PA(v))PSS(v-PA(v))$ (3) $$

$PSS(a-b)$ denotes the subgraph that starts from $b$ which reaches $a$.
If $v$ is inside the ancestor nodes, then $ancestor(v)=\varnothing$, and therefore $P(v|ancestor(v))=P(v)$.

The expected parsing search steps for a representation graph can be calculated by averaging out the expected parsing search steps for each sub graph inside the parsing graph. The lower bound is the number of steps that leads to the shallowest node, and the upper bound is the number of steps that leads to the deepest leaf node.

$$ $\arg\min_{c\in\mathbb{C}}\sum_{u\in path(c)}len(n_{children}(PA(c)))\leq \mathbb{E}_{c\in\mathbb{C}}(c)\leq\arg\max_{c\in\mathbb{C}}\sum_{u\in path(c)} len(n_{children}(PA(c)))$ (4) $$

### A.5 Encoding Cost

A representation graph $RG$ specifies a distribution of observation instances encoded in a compositional manner. One can the minimal encoding cost to distinguish all the variables.

$$ $RC(G)=\sum_{v\in G}\sum_{u\in E(v)}-\log P(u|v)+\sum_{v\in G}-\log P(v)+\sum_{ c\in G}-\log P(c)$ (5) $$

The more ambiguous a variable is, the less resources needed to encode the variable; the smaller the variable graph is, the less edges it has, the bigger the probabilities of parsing and variable identification, the smaller the encoding cost. Every time when a new edge points from a pre-existing variable to a new variable, the encoding resource expands by an amount determined by the conditional probability.

#### Example

Representation graphs with different nested structure translates to different encoding cost. In Figure 9, three graphs contains an increasing abstraction specificity. In graph 1, the variable ’world’ is split into two variables: animals and plants. Each of these variables do not denote a specific observation, but serves as a placeholder for any instances of specific observation that fits into that particular category.

Figure: Figure 9: An increasing level of abstractions
Refer to caption: extracted/5953942/abstraction_levels.png

The encoding cost for such a graph, given the specified observational probability on the edges would be:

$$ $EC(g1)=-\log(P(World))-\log(P(Plants|World))-\log(P(Animal|World))=-2\log(0.5)$ (6) $$

Since once the variable $World$ has been identified, one only need to distinguish the subcategories inside the variable $World$, and the minimal code length to distinguish one subcategory (animals) from another (plants) would be the conditional probability: $P(Plants|World)$.

Whereas if $g1$ does not contain a nested structure, one would need to encode the variable world separately from the variable animal and variable plants, in this way, the alternative encoding length without an edge connecting the sub categories with the main category would be:

$$ $EC(\hat{g1})=-\log(P(World))-\log(P(Plants))-\log(P(Animals))=-2\log(0.5)$ (7) $$

For $g2$, the case is slightly different: the variable category that denotes animals is further split into the category of mammals and reptiles. Thereby, extra encoding costs are needed.

$$ $\begin{split}EC(g2)&=-\log(P(World))-\log(P(Plants|World))-\log(P(Animals| World))\\ &-\log(P(Mammals|Animals))-\log(P(Reptiles|Animals))\\ &=-4\log(0.5)\end{split}$ (8) $$

If each of these categories are encoded separately and each variable is not pointed to other variables, the information content to encode a variable graph without edges in the case of $\hat{g2}$ would be:

$$ $\begin{split}EC(\hat{g2})&=-\log(P(World))-\log(P(Plants))\\ &=-\log(P(Animals))-\log(P(Mammals))-\log(P(Reptiles))\\ &=-6\log(0.5)\end{split}$ (9) $$

Since $P(Mammals)=P(mammals|animals)P(animals)$.

This difference is more pronounced going from $g2$ to $g3$:

$$ $\begin{split}EC(g3)&=-\log(P(World))-\log(P(Plants|World))-\log(P(Animals| World))\\ &-\log(P(Mammals|Animals))-\log(P(Reptiles|Animals))\\ &-\log(P(Fungi|Plants))-\log(P(Flowers|Plants))\\ &=-6\log(0.5)\end{split}$ (10) $$

Whereas for $\hat{g3}$, not encoding variables in a nested structure would result in an encoding cost of

$$ $\begin{split}EC(\hat{g3})&=EC(\hat{g2})+-\log(P(Fungi))-\log(P(Flowers))\\ &=-10\log(0.5)\end{split}$ (11) $$

These examples illustrate organizing variables into a nested recursive structure saves encoding cost.

### A.6 Alternative formation as learning a context sensitive grammar

HVM learns a 5-tuple from the sequences $\mathit{G}=\{\mathbb{A},\mathbb{C},\mathbb{V},\mathbb{R},\mathbb{P}\}$.
A set of atomic units $\mathbb{A}=\{a_{l}\}$
A set of chunks $\mathbb{C}=\{c_{k}\}$, $k=1,2,...,$, each chunk $c_{k}$ is a sequence of atomic units and variables. The model uses chunks from $\mathbb{C}$ to parse the observation sequence. Assume a random variable $C$ as the chunk being parsed, taking a value $c$ from $\mathbb{C}$, $c\in\mathbb{C}$, $c\sim P$. $P$ is the parsing probability. $\sum_{c\in\mathbb{C}}P(C=c)=1$
A set of variables $\mathbb{V}=\{v_{i}\}$, $i=1,2,...,$
A set of rules $\mathbb{R}=\{E(v_{1}),E(v_{2}),...,E(v_{n})\}$ that each specifies the set of chunks $E(v)=\{c_{j}\}$ denoting each variable $v\in\mathbb{V}$. Probabilities on variable denoting $\forall i$, $\sum_{j}P(v_{i}\rightarrow c_{j})=1$

### A.7 Rate-Distortion Theory

Rate-distortion theory specifies that the best possible compression of a signal $X$ contains a lower bound on quality loss specified by the Rate-Distortion Function (R(D)): $R(D)=\inf_{Q}R_{Q}\text{s.t.}\mathbb{E}[d(X,\hat{X})]\leq D$ (Shannon, ; Cover & Thomas, ). According to the $RD$ theory, the minimum $R$ (the amount of compression) at which information can be transmitted over a communication channel for a given level of information loss D is specified by the Rate-Distortion Function $(R(D))$: $R(D)=\min_{p(\hat{x}|x):E[d(X,\hat{X})]\leq D}I(X;\hat{X})$. The mutual information quantifies how much information needs to be preserved during compression to achieve this fidelity, and the function minimizes this quantity while satisfying the distortion constraint. Written in another way,$R(D)=\inf_{Q}R_{Q}\text{ s.t.}E[d(X,\hat{X})]\leq D$. $Q$ represents the encoding function that maps from $x$ to $\hat{x}$. RD is agnostic to the choice of the distortion function, and the representation complexity, which measures the nestedness of the variables learned by HVM.

### A.8 Parsing Probability

A sequence $S$ is parsed by the chunks in $\mathbb{C}$ to obtain a distribution of chunk parsing probability $P_{\mathbb{C}}$. This distribution on the support set of chunks has shapes dependent on the parsing mechanism. HVM employs a greedy strategy and chooses the deepest consistent chunk in the memory tree to parse a segment of the upcoming sequence. Other parsing strategies will result in alternative distributions for $P_{\mathbb{C}}$, in addition to the transition probability $P_{\mathbb{C}}(c_{i}|c_{j})$.

Define the set $\mathit{H}_{\mathbb{C}}(S)$ as the set of all distributions results in any parsing method using the chunks in $\mathbb{C}$ to parse a sequence $S$, and any parsing probability $P\in\mathit{H}_{\mathbb{C}}(S)$. Hence each evaluation measure on the representation is bounded by the optimal and the most unfortunate parsing occasions.
Taking the predictive power measure as an example:

$$ $\arg\min_{P\in\mathit{H}_{\mathbb{C}}(S)}\mathbb{E}_{P}|c|\leq\mathbb{E}_{P_{ HVM}}|c|\leq\arg\max_{P\in\mathit{H}_{\mathbb{C}}(S)}\mathbb{E}_{P}|c|$ (12) $$

The measured value is bounded by the expected value from the best parsing distribution and the worst parsing distribution.

### A.9 Uncertainty

Variables introduce uncertainty.
Without variables, the chunks inside $\mathbb{E}_{v}$ needs to be encoded as distinct chunks, consuming an encoding cost of $\sum_{c\in\mathbb{E}_{v}}-\log P(c)$.

We have the ground truth set of sequential observational units $gt$. Let’s say in a recall task, the agent learns a variable chunk to describe the ground truth, the variable denotes to three concrete chunks $c_{1}$, $c_{2}$ and $c_{3}$. The accuracy when $c_{1}$ is being sampled will be $D(gt,c_{1})$, when $D$ is a distance function evaluating the agreement between the ground truth chunk $gt$ and $c_{1}$. Then one can evaluate the expected accuracy within a variable:

$$ $\mathbb{E}(gt,v)=\sum_{c\in\mathbb{E}_{v}}{P(c|v)D(gt,c)}$ (13) $$

$P(c|v)$ is the probability of sampling chunk $c$ given that the variable $v$ is identified.

Compared to chunks without variables, recalling chunks with embedded variables introduces variability, and brings down recall accuracy.
But this strategy is especially suited when encoding resources is limited. Then, it is better when the resources are assigned to the more probable chunks that are predictive of a bigger sequence, while the varying entities that occur with lower probability can be denoted as a variable that serves as a placeholder.

$$ $Uncertainty(G)=\sum_{c\in\mathbb{C}}P(c)\sum_{v\in C}H(v)$ (14) $$

And $H(v)=-\sum_{c\in E(v)}P(c)\log{P(c)}$.

### A.10 Other evaluation measures

Explanatory Volume: $\frac{|S|}{|W|}$ The length of the original sequence (in atomic units) divided by the length of the parsed sequence (in units of chunks), i.e., The average size of the sequence that the current representation graph can explain at each parsing step.
Sequence Negative Log Likelihood: The lower bound of information content needed to encode the sequence $S$, as $S$ is parsed into chunks $(c_{1},c_{2},...,c_{n})$, $-\log P(S)=-\log(\prod_{c_{i}\in\mathbb{C}}P(c_{i}))$.
Representation Entropy: The uncertainty contained within each chunk parse $\sum_{c\in\mathbb{C}}P(c)\sum_{v\in V(c)}\sum_{u\in E(v)}-P(u|v)\log P(u|v)$

### A.11 Regressing LLM on human data

We also regressed the negative log likelihood (NLL) of all LLMs against human sequence recall time and presented the resulting R-squared values in Figure 10. During the training block, the NLL of LLMs shows a stronger correlation with human recall times compared to alternative models. However, when it comes to human transfer, the cognitive models demonstrate a much stronger correlation than the LLMs, with HVM aligning most closely to human transfer performance.

Figure: Figure 10: Regressing all models’ sequence likelihood on human sequence recall time.
Refer to caption: extracted/5953942/llmhuman.png

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: **Questions and improvements:**

1. The work and claims could be strengthened by evaluating on more datasets that focus on abstraction, but have not been generated by the authors. This is only relevant for a major revision.
2. Topic models and various forms of hierarchical latent variable models have been used and discussed extensively in linguistics, machine learning, and cognitive science. How does the HVM relate to commonly used topic models (LDA, and more modern ones)? Ideally this is discussed on a technical level in detail, but at the least it needs to be included with more detail in the related work discussion.
3. How does the generative model relate to the Hierarchical Dirichlet Process (Teh et al. 2006)? 
4. Why was LZ78 chosen as a baseline? It is a lossless general purpose compressor, and has not been designed specifically for natural language data or data with hierarchical structure. Personally I think a much more interesting comparison would be against Context-Tree Weighting (Willems et al. 1995), or maybe the forget-me-not process (Milan et al. 2016), though the latter is perhaps a bit of an overkill (and quite involved to implement).
5. Table 1: “we took random snippets of 1000 characters and calculated evaluation metrics”, that seems like fairly short sequences. Why 1000? Is there a scalability issue with longer sequences? How sensitive are the results, particularly the comparison against LZ78 / CTW to the sequence length?
6. The paper mentions lossy compression multiple times, but as far as I understand all evaluation metrics are lossless in the end (more “lossy” models simply require longer coding lengths / have less coding efficiency)? I am struggling to follow section 4.5 (despite having spent half of my PhD on rate distortion theory). For sure LZ78 is not a lossy compressor - it is lossless. Typically, the distinctive feature of lossy compression is that not all prediction/reconstruction errors matter equally, i.e. the distortion function is typically not the log loss (lossy compression requires a quantitative definition of which information is relevant and to which degree, relative to some task/goal; this is what the distortion function does; the log loss treats all information equally). What is the distortion function in the paper? If one is willing to go lossy, there is a famous trade-off between fidelity and “complexity” (really, the information rate): the rate-distortion curve. I have a hard time relating Fig. 6b to a rate-distortion curve - the “Representation Complexity” seems to be more related to the rate than the distortion, but the figure legend says exactly the opposite. And how is “Abstraction Iterations” (Fig. 6c) related to the abstraction level and representation complexity and thus ultimately the distortion (which also applies to L467-477)? I do agree that lossy compression can be used to formalize a particular kind of abstraction, but it seems to me that what is happening in the paper is more similar to a minimum-description-length argument for *lossless compression* (the more complex the model, i.e. the deeper the tree of abstractions, the better it can compress a sequence, but the price to pay for it is by having a more complex model). The mistake may be fully on my side, but please clarify.
7. Some of the discussion / conclusion is a bit strong. I would not reject the paper based on this, but I have listed concrete issues in the minor comments.
8. Why was the generative model introduced? Were there no suitable generators or datasets in the literature (that are more widely used)? Which shortcomings of previously used data (generators) does the current paper tackle? (I am leaning towards listing this as a minor point, but I also think that any paper that introduces a new data set or data generation procedure should justify it over using what’s been published and used previously by others).

**Minor comments:**
1. L 164 - line break within inline equation.
2. Discussion in L279-284 leaves out that HCM achieves better coding efficiency than HVM if I understand correctly.
3. L 315: “LZ78 performs well in terms of compression efficiency, which is expected given its design purpose”. I don’t fully agree, LZ78 is a general purpose lossless compressor, it has not been specifically developed to compress natural language.
4. L 499: “our work provides a reductionist cognitive model that explicitly specifies the minimal components needed for a model to learn interpretable abstract structure from sequences.” - what makes the model particularly “cognitive”? I also mildly disagree that the model “specifies the minimal components”, rather, it is one solution with few components, but it is unclear that this is the minimum needed (and also minimal in which sense?).
5. L 503: “Our generative mechanism offers a probabilistic, hierarchical sequence generation model relying on chunk-based recursive generation and inventory growth rather than formal grammar rules.” - is this an advantage; does this address some shortcoming in the literature?
6. L 520: “Previously, grammar learning, chunk learning, and statistical/associative learning were studied in isolation as distinct aspects of sequence learning.” - it should be pointed out that this sentence refers to the cognitive science(?) literature (in other fields, like algorithmic information theory, which deals primarily with sequential learning, this distinction does not play a big role).
7. L 523: “Our work suggests a normative origin of concrete and abstract chunk learning” - I think the normative claim is a bit overstated in light of the results and no discussion that rules out all other possibilities.
soundness: 3
strengths: * The model is an interesting, sensible, and original improvement over HCM.
* Empirical results show that the model learns well and works well on synthetic data and some natural language datasets.
* The work is very well put into wider perspective in the introduction.
summary: **Update after rebuttal:** Thanks to the very detailed response by the authors, my questions and potential misunderstandings have been clarified and I have raised my score from a 5 to a 6. I still think the results on a data source specifically designed to highlight the advantages of the model must be taken with a small grain of salt (recognising that there are other good arguments for designing the data source), and the comparison against LZ78 is okay, but it should not be too surprising that LZ78 is not an ideal compressor for the synthetic data source.

---

The paper tackles the problem of discovering useful abstract representations in sequence prediction, that allow for better compression and transfer (generalization) with the aim of “[capturing] the learning and transfer of abstract representation in human cognition”. To this end, the paper extends a previously proposed model for probabilistic hierarchical chunking, HCM, with the ability to include learnable abstract variables into the chunk dictionary. Learning the model and performing inference with it is somewhat involved (as is generally the case for non-parametric probabilistic models), but explained well in the paper. On synthetic data that is designed to embody the assumptions underlying the model, the model performs very well and outperforms HCM and Lempel-Ziv (LZ78) as a baseline. The model also performs favorably on four natural language datasets (cut into sequences of 1000 characters), and correlates better with human recall times in a color memorization task. The paper finds that in-context learning with LLMs (GPT2 and Llama-2) behaves qualitatively differently on a similar task. Finally, the paper draws a connection between learning abstractions and lossy compression.
weaknesses: * Many of the main experiments were conducted on data from a generative model that fits exactly the modeling assumptions for HVM (or tasks inspired by these assumptions). As is often the case when a paper proposes a novel model and a novel data set / generator, the fact that the model works well on data that was specifically designed for the model to work well is not a very strong argument. Luckily the paper also shows good results on “natural” data, and qualitatively matches some aspects of human behavior (recall times) that are not trivially predicted from the synthetic data.
* Hierarchical Dirichlet processes and related models (perhaps most famously many variants of topic models) have been used and discussed exhaustively in the ML, linguistics, and cognitive science literature. But an in-depth discussion and technical comparison of HVM against these is currently missing.
* From a cognitive perspective, a severe limitation is that learning in HVM strongly depends on initial learned representations and the order in which learning experiences are represented. While some human learning mechanisms have these traits, I am not sure whether they apply to the learning of abstract concepts in natural language to the extent that the model would predict.


**Verdict:**
The model as an improvement over HCM is sensible, sound, and results clearly show the benefits. Additionally, the cognitive plausibility (at least on an abstract computational level) of the model is decent (at least to me as a non-linguist), and supported by the experiment with human participants. The paper is well written and presents a nice set of experiments. On the other hand, I think many (but not all!) of the experiments must be taken with a grain of salt, since the data has been either synthetically generated to match the model, or has been designed with the same qualities in mind (like in the color memorization task). The comparison against in-context learning in previous-generation LLMs on the same task (translated into text) is ok, but I am not sure whether there is a big take-away other than saying LLMs in-context learning on this task is different from the model and different from human learning on this task. It is unclear whether LLMs should even be designed to mimic HVM in context (the discussion seems to mildly hint at this by claiming normativity of the model). The work is very interesting to a comp. neurosci. audience and a comp. linguistics audience, but its impact in the ML and AI community is likely to be quite limited (nonetheless, a part of the ICLR audience has a background in the aforementioned fields). Some technical discussion around hierarchical Dirichlet processes (or related models) and topic models is missing. Finally, some of the writing and some claims are perhaps a bit overstated (see concrete points under ‘Questions’). In its current state, for an ML conference, I think the relevance and significance of the current work is fairly limited. I think the paper would benefit from a major revision and could be significantly strengthened to be more impactful. I am therefore currently leaning towards rejection (at a top-tier ML conference).

---

confidence: 4
contribution: 4
initial_rating: 6
presentation: 4
questions: Please answer the two points under weaknesses above.
soundness: 4
strengths: Impressively, this paper presents some novel theoretical contribution, a clear theoretical framework for combining chunking and abstraction in sequence learning, with formal proofs and guarantees.

They also evaluated their model through multiple angles: computational efficiency, correlation with human behavior, comparison with LLMs, a good set of comparisons. 

And I enjoyed their connection to cognitive science: The work bridges computational and cognitive approaches, providing insights into human learning mechanisms.
summary: This paper introduces a hierarchical variable learning model (HVM) that learns abstract patterns from sequences by combining chunking and variable discovery mechanisms. HVM builds on previous chunking models by adding the ability to identify abstract variables that represent groups of chunks that appear in similar contexts. The authors demonstrate that HVM achieves better compression and parsing efficiency compared to baseline models, correlates well with human sequence learning behavior, and provides insights into how abstraction enables better generalization. They evaluate HVM on both synthetic data and real-world language datasets, comparing it against traditional compression algorithms and large language models (LLMs).
weaknesses: 1. The paper's comparison to LLMs is relatively narrow and focuses primarily on a specific sequence recall task and limited to short sequences, and therefore seems slightly contrived situation. The paper would benefit from explorations of slightly more complex abstraction tasks to study the general applicability of their method. 

2. The comparisons in the paper are quite limited and don't adequately address the rich literature on sequence compression and pattern detection. A single example I have in mind of a similar cogntiively-inspired latent variable learning model is CSCGs (https://pmc.ncbi.nlm.nih.gov/articles/PMC8062558/), but there are more.

---

confidence: 4
contribution: 4
initial_rating: 6
presentation: 3
questions: * What is the relationship between this model and other Bayesian Wake-Sleep class of algorithms, like the older Helmholtz machine or the newer generation such as DreamCoder? There are definitely similarities in having a generative and recognition model, but I didn't see a discussion on this in the paper? I think this would be quite relevant to put in the related works section.
soundness: 4
strengths: * I think this is a really innovative algorithm that builds on the recent HCM in a pretty novel and cool way. It's clearly motivated by the human ability to abstract. 

* The evaluation is quite rigorous and showing performance on real world data as well as accounting for human behavior in a relevant task is a very nice touch. 

* There are a lot of rigorous proofs in the appendix. The authors have clearly thought a lot about the theoretical foundations of this algorithm as well as shown good empirical proof of its use.
summary: In this work, the authors build on a previous Hierarchical Chunking Model (HCM - a probabilistic model that learns to produce hierarchical chunks from sequential non-iid data) to create Hierarchical Variable learning Model (HVM), which groups chunks into high-level variable categories that have similar interaction properties. This model aims to compress sequences in a structured manner similar to humans. To test this out, the authors used sequence data from a variety of language datasets (childes, bnc, gutenberg, open subtitles) using HCM and LZW, a classical compression algorithm as baselines. The authors then used the model to account for human behavior in a sequence memory task that requires humans to re-use specific variables (against a control where there isn't a reusable variable). They also compared popular LLMs (GPT2, LLama2) on this task. HVM showed the biggest difference between the control and variable groups, which is the main effect that humans had.
weaknesses: * I think the paper can mainly be improved in clarity. For example, when getting to Figure 3, it's kind of hard to figure out which exact datasets these results are from. In general, most of the text in the work is dedicated to describing the algorithm and results. I think adding some more information on what datasets are being used would be useful. For example, line 310: " BabyLM language dataset, which contain text snippets from a collection of data domains" what data domains are there? It was hard for me to understand what kind of data this was. 

* For Figure 5, I think the authors should plot the difference between the conditions rather than the conditions themselves. Currently, it's hard to understand why HVM shines here more than the LLMs. As I understand, the individual likelihoods don't matter as much as showing a significant decrease from control -> variable conditions. You can put the individual likelihood plots in the supplement. The plot as it is, in my opinion, undersells and obscures the result. 

* (minor weakness) I get the feeling that this algorithm isn't quite as scalable as other powerful sequence learning technologies we have today such as LLMs. This is not to say the algorithm is not useful because of that, because of course you do get more interesting structure and interpretability out of it (and it's also a better model of how humans do sequence learning). But I think this is at least worth mentioning in the discussion. If this model does actually have almost as good or better scalability than tools we have today such as SSMs or transformers, I think that would be a huge bonus and definitely needs mentioning. 

* (minor weakness) I think a potential missed opportunity for this algorithm is interpreting the discovered variables on specific datasets that we know has rich hierarchical structure. For example, can you use this algorithm on musical notes to recover leitmotifs? But there is enough work here that this can count as future work.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: - Would it be possible to use these learned representations for a task that requires abstraction (e.g. abstract reasoning)?
- When humans perform abstractions, semantic content also manners. Can this be integrated into the approach proposed in the paper?
soundness: 3
strengths: - The paper is organized and well written
- The paper includes evaluations of the model from many different perspectives, including evaluation on synthetic and real world language datasets, comparison with human performance on a cognitive task, etc
- The paper has a good level of technical rigour with the addition of definitions, theorems, and algorithms in the appendix.
- The topic of abstraction is of great significance to the field of AI, and the paper proposes a novel approach to tackling this issue
summary: The authors introduce a hierarchical variable learning model (HVM) that learns abstractions on sequence data via chunking and variable learning. Sequences are first parsed according to a parsing graph containing existing chunks hierarchically. If one chunk follows another chunk in a statistically significant manner, their concatenation is added to the list of chunks alongside hierarchical information. Variables are also identified as a set of chunks that consistently occur before/after another chunk. Variables can also be used in chunk formation.

The model is tested on both a synthetic dataset and real world sequential datasets (language modeling) and compared against HCM and LZ78 on parsing search steps, sequence length, sequence negative log-likelihood, and encoding efficiency. It is shown that the design of HVM does indeed provide benefits with respect to these metrics.

The authors also HVM reflects human memorization and transfer performance on a memorization and transfer task.

In addition, the authors compare HVM performance to LLMs and associative learning models on the same cognitive task.

It is also shown that higher levels of abstraction in HVM leads to relatively higher likelihood when parsing unseen sequences compared to HCM, suggesting improved generalization.
weaknesses: - Some small presentation issues in the appendix: equation in line 1020 is too long, figure 7 has a red line from a word processor, figure 8 has a red line that seems to be an error
- While I did praise the comprehensive evaluation, it is almost _too_ much content; it was difficult for me to understand the model without referring to the appendix. I suggest including information about the set up in the main text to improve clarity.
- Since the model builds up chunks by considering frequencies of adjacent chunks, there might be a limit to the expressivity of the formed abstraction. For example, while it might be able to capture the pattern of two chunks consistently being n chunks apart (if the intermediate chunks are all members of the set representing a variable), it cannot capture a pattern of two chunks being a variable number of chunks apart, where the number of chunks is determined by a symbol being present in the sequence.
- The evaluation only considers coding efficiency, compression efficiency, etc as a proxy for abstraction, which I do not believe to be sufficient for the purpose of demonstrating the effectiveness of the learned abstract representations. The demonstration of generalization does provide some evidence (Q1 below related to this point).

Meta-review: This paper introduces the Hierarchical Variable Learning Model (HVM), a novel extension of the Hierarchical Chunking Model (HCM) that learns abstract representations by grouping sequence chunks into higher-level categories based on contextual similarity. This enables HVM to achieve improved compression, parsing, and generalization compared to baselines (learned baseline = HCM, hard-coded baseline for compression = LZ78), and to better correlate with human behavior in sequence memory tasks. The model is evaluated on synthetic data and BabyLM (real language data). The paper also presents a human study in a sequence memory task, and compares people's performance with HCM, HVM and a variety of LLMs. HVM better captures human performance.

This paper is most compellingly read as a contribution to computational cognitive science -- the results are informative about how people might learn chunked, abstract representations, and the paper puts forth a model which better captures this behavior relative to alternatives. Reviewers note that this is both a strength and a weakness. As a strength, HVM is novel, rigorously and thoroughly evaluated, and seemingly a good model of human behavior. As a weakness, there is limited evidence that HVM would be useful in more naturalistic datasets which are more important in AI / ML (although the authors added discussion of this to the paper during the rebuttal period).

Despite the uncertainty raised about the relevance of this work for an AI / ML audience, all reviewers voted to accept this paper after the rebuttal period. I similarly feel that the paper makes a compelling contribution by demonstrating a novel method which can learn abstract, chunked representations, and therefore deserves to be presented at ICLR.

Decision: Accept (Poster)