# Understanding (Un)Written Contracts of NVMe ZNS Devices with zns-tools

Nick Tehrany, Krijn Doekemeijer, and Animesh Trivedi
VU, Amsterdam

###### Abstract

Operational and performance characteristics of flash SSDs have long been
associated with a set of Unwritten Contracts due to their hidden, complex
internals and lack of control from the host software stack. These unwritten
contracts govern how data should be stored, accessed, and garbage collected.
The emergence of Zoned Namespace (ZNS) flash devices with their open and
standardized interface allows us to write these unwritten contracts for the
storage stack. However, even with a standardized storage-host interface, due
to the lack of appropriate end-to-end operational data collection tools, the
quantification and reasoning of such contracts remain a challenge. In this
paper, we propose zns.tools, an open-source framework for end-to-end event and
metadata collection, analysis, and visualization for the ZNS SSDs contract
analysis. We showcase how zns.tools can be used to understand how the
combination of RocksDB with the F2FS file system interacts with the underlying
storage. Our tools are available openly at https://github.com/stonet-
research/zns-tools.

##  1 Introduction

The emergence of flash solid state drives (SSDs) has resulted in the
redesigning of the host interfaces [53, 49], the block layer [6, 29], I/O
schedulers [16, 52], file systems [28], applications [11], and distributed
systems [4]. Despite the aforementioned significant end-to-end changes to
leverage the characteristics of flash storage, the reasoning and analysis of
modern flash SSDs are governed by many “unwritten contracts” [15] regarding
how user data should be stored, grouped, accessed, and deleted. In parts such
expectations are considered unwritten as SSDs themselves are complex with many
internal hidden details (flash chip sizes, layout, garbage collection (GC)
units, buffer sizes) [30]. Furthermore, the complex architecture of the
layered modern storage stack makes the end-to-end reasoning about the
unwritten contracts challenging.

Figure 1: ZNS integration at the (a) block layer; (b) file system level; and
(c) application-level (example RocksDB). In all three cases, an end-to-end
written contract analysis is missing.

NVMe Zone Namespace Devices and UnWritten Contracts: To address the challenges
of complexity, researchers have advocated for more open interfaces [7, 55,
37], which has culminated in the Zoned Namespace (ZNS) specification [5, 50,
44]. Briefly, a ZNS device divides its storage capacity into multiple zones
that can only be sequentially written (or appended to), thus closely mimicking
how flash chips internally work. Data can be read from anywhere either
sequentially or randomly. I/O on different zones is isolated and done in
parallel, thus a zone represents a unit of parallelism. Beyond these basic
read/write operations, ZNS devices have a number of unique flash/ZNS
management-related commands. Of particular interest is the reset command with
zones, which explicitly resets a zone to be written again. In case there was
any live data, it is the responsibility of the host software (file system,
application) to ensure that the data is copied to a new zone before resetting
the old zone. The significant advantage of such a design is that it clearly
identifies the unit of garbage collection (zone) and the timing when to reset
(under the control of the host software), both of these details are
intricately complex to reverse engineer [30, 10]. Hence, with ZNS devices,
previously “unwritten contracts” are now standardized “written contracts”,
which forces us to re-think the operational design of our storage stacks [44].

Reasoning about the Written ZNS Contracts with Applications in a Layered
Storage Stack: ZNS software support in the storage stack is still under
development. There are multiple ways through which ZNS contracts can be
extended to an application in an end-to-end manner. Figure 1 shows such
possibilities where ZNS software support is needed at the (a) block-level, I/O
scheduler support with mq-deadline [9]; or (b) file system level, currently
F2FS and Btrfs support ZNS [33]; or (c) application-level direct support,
e.g., ZenFS customized file system backend for RocksDB [5]. In such a layered
architecture, it is challenging to ensure and cross-check if the ZNS contracts
are extended and respected by all layers due to the semantic gap between the
layers. For example, the POSIX fadvise and fctnl calls are hints to a file
system that the file system is free to ignore. Similarly, ZNS/flash file
systems themselves have complex bookkeeping operations (garbage collection,
log writing, fragmentation) where previously respected hints can be
transparently overwritten by a file system without the application’s knowledge
(see below two examples in contract violation examples). Hence, in this work,
we argue, there is a need to systematically investigate if and how the new
written ZNS contracts are extended to applications.

Figure 2: Visual representation of zns-tools with (a) zns.fiemap mapping
individual files to zones; (b) zns.segmap mapping multiple files to zones ,
segments and their lifetime classifications; (c) the zns.imap tool mapping the
inode of a file to its ZNS zones (d) zns.trace tracing I/O and zone management
activity to the ZNS zones.

zns-tools: A Framework to Study Written ZNS Contracts: In this work, we
propose a set of open-sourced tools called zns-tools for the ZNS software
stack. Put together, these tools allow us to collect operational data and
events across the stack in a programmed manner. The collected data is then
analyzed and visualized to identify various contract violations. More
specifically, we are interested in understanding the following previously
“unwritten contracts” and how they are (not) followed across the layers: (1)
“Request Scale” with “Locality”: how data placement decisions are made (that
result in large I/O, and parallel requests with minimal FTL overheads in ZNS
SSDs) and how such allocations look on ZNS SSDs; (2) “Grouping by death time”:
how data grouping decisions are made to ensure minimal overheads from GC-
related data movements and overheads; and (3) “Uniform Data Lifetime”: how a
ZNS device’s lifetime is managed by generating and deleting data with a
uniform lifetime, and subsequently explicitly resetting a zone in a ZNS SSD
that (indirectly) controls wear-leveling on the device.

Example: ZNS Contract violation with RocksDB and F2FS: Using zns-tools, we
identify two such violations about data grouping in the state-of-the-practice
combination of RocksDB on F2FS with a ZNS SSD. The first issue is F2FS-
specific. F2FS reclassifies the hotness (hot, warm, cold) of a data block
after a round of GC cycle, where the GC always moves data blocks to cold data.
This reclassification allows previously segregated data blocks under different
hotness classes to be co-located in a new segment together, thus violating
hotness hints from RocksDB. The second issue is RocksDB and F2FS specific.
RocksDB writes SSTable to a file system in two passes, raw data (the table)
and a small footer (less than a page). After writing the raw SSTable data to
hot or cold data, depending on the level of the SSTable , RocksDB synchronizes
the file causing F2FS to flush the data to the ZNS device. Upon completion of
the flush, RocksDB writes the footer of the SSTable, containing a checksum,
which is synchronized to the storage. Due to only a single page for the footer
being dirty in the page cache, which is below the minimum threshold for F2FS
of 16 pages, F2FS sets an inode flag to indicate the data as being hot. As a
result, F2FS writes the footer page to the hot data segment, violating the
contract for the SSTables by ignoring any hints for the SSTable writes. Both
of these incidents are examples of violating the “Grouping by death time”
contract.

In this work we propose a collection of zns-tools that combined constitute a
framework that allows parts-by-parts building an end-to-end understanding of
how data is stored and managed in a layered storage stack on top of ZNS
devices. The primary goal of the zns-tools framework is to allow building a
complete picture of events across the layers that influence data placement and
movement decisions. Section 2.4 shows on such end-to-end example generated
from our framework. Our key contributions in this work include the following:

  * •

Making a case for building end-to-end operational data analysis tools to
reason about previously unwritten, but now written ZNS SSDs storage contracts
for applications.

  * •

zns-tools, an end-to-end framework that provides support for collecting,
analyzing, and visualizing ZNS contracts across the layered storage stack.

  * •

Specific demonstration of the framework’s capability on F2FS with RocksDB
applications for an end-to-end visualization of operational analytics. Section
2.4 shows one such end-to-end example generated from our framework.

  * •

zns-tools are open-sourced and available here: https://github.com/stonet-
research/zns-tools. This paper is available under CC-BY 4.0 License.

##  2 Design of zns-tools Framework

zns-tools is a new framework for ZNS SSDs that is designed to collect
operational data about the ZNS storage stack to identify contract violations.
It comes with tools that aid in extracting and visualizing: (C1) where is user
data stored on ZNS SSDs; (C2) how much I/O is triggered to each zone; (C3)
which zones are subjected to GC resets from the software stack and how data
migrates across zones because of GC. Currently, there are four tools in the
framework, zns.fiemap, zns.segmap, zns.imap, and zns.trace. They are
visualized in Figure 2, and their exact bash command and outputs are shown in
our GitHub repository.

###  2.1 zns.fiemap

zns.fiemap (ZNS file-mapping) is a tool that is designed to extract placement
information from the stack to identify how the “Locality” contract is
followed. The placement of files and data within modern SSDs is not static,
and constantly changes in response to application or file system level events.
Applications can typically provide allocation/location hints (by means of data
temperature), but it is ultimately the file system that decides about the
final data storage location. ZNS SSDs require any live data to be copied
during GC, hence, the data location changes. Furthermore, any log-structured
file system has its own out-of-place update mechanisms. With ZNS SSDs and log-
structured file system, the location of the data is thus dynamic and changes
constantly. The repeated execution of zns.fiemap traces the file data movement
in this dynamic environment to identify how data from different files are
grouped in zones. Furthermore, while moving file extents, if the “Locality”
rule is not followed, that leads to file fragmentation with holes that are
known to cause severe performance degradation [38, 24, 56, 23, 21]. Holes
violate the “Request Scale” contract that recommends large sequential I/O
requests. In ZNS, how a file is stored among zones also determines the amount
of chip-level parallelism, a large file I/O can extract. Hence, zns.fiemap
provides detailed information about the on-device zone-level placement of
files within various file systems (addressing C1,C3).

zns.fiemap retrieves file location mappings from the Linux kernel using the
ioctl() syscall with the FIEMAP flag. Support for FIEMAP is not necessary for
file systems for POSIX compliance, however, all currently available file
systems with ZNS support (F2FS and Btrfs) support this flag. With FIEMAP, file
systems implement the tracking of extents, representing ranges of physically
contiguous data for a file, which are returned to the ioctl() caller. By
iterating over the logical range of a file, zns.fiemap retrieves data mappings
of all the extents for the particular file. The collected extents for the
targeted file are mapped to their respective zone(s) containing the file’s
data using their logical address ranges. For example, on a ZNS SSD with a zone
size of 1MiB, logical addresses between [0, 1MiB) fall within the first zone,
[1MiB, 2MiB) on the second zone, and so on. The zone size and zone size ranges
can be queried with the ZNS device using a zone management command. With all
information about file extents, their addresses, address-to-zone mappings,
zns.fiemap reports a detailed profile of the extent distribution (min, max,
percentiles), hole statistics, and zone-level placement information. Figure 2
(a) illustrates the operational aspect of zns.fiemap, retrieving the extent
mappings of File A using ioctl() with the FIEMAP flag, followed by mapping the
three file extents to zones 1 and 2.

###  2.2 zns.segmap and zns.imap

zns.segmap and zns.imap are tools that collect and quantify metadata around
the “Grouping by death time” contract. This contract is implemented within a
file system that uses application-level lifetime hints (RWH_WRITE_LIFE_* flags
with the fcntl call), or its own data segregation policies based on data
access heatmaps. It recommends that any data that is about to get deleted, or
over-written, should be stored within a single GC unit. With this design, once
data is invalidated, the GC unit can be simply reset without having to copy
any live data, thus reducing GC overheads. Naturally, an accurate grouping
requires coordinated efforts from the application, as well as the file system,
over a lifetime of the data/file(s). Furthermore, such groupings should be
constantly evaluated due to the dynamic nature of data placement with GC
events within the file system.

zns.segmap and zns.imap are tools to extract grouping information for file
data and metadata for F2FS. F2FS does heat-based data grouping in segments. A
file can have its data stored in multiple segments, and a single segment can
contain data from multiple files. By default, F2FS uses 3 classes of
classification (hot, warm, cold) on two types of data, file data, and file
metadata (inodes). zns.segmap extracts the file-to-segment mappings using
zns.fiemap, and reads the segment hotness classification from
procfs111/proc/fs/f2fs/nvme0n1/segment_info. To locate the inode in F2FS,
zns.imap firstly reads the F2FS superblock, which is written at a particular
offset within the storage device, followed by parsing the superblock to
identify the location of the node address table (NAT), where F2FS stores the
block addresses of inodes, and the last checkpoint. Traversing the NAT,
zns.imap retrieves the block address for the file inode to look up, followed
by issuing a single read request to retrieve the inode. The retrieved inode is
mapped to the zone in which it is contained. With these tools, we report for
each F2FS segment, its hotness classification, number of file extents, the
segment-to-zone mapping, and the inode-to-zone mapping. With this information,
we can stitch a complete timeline of user data as it ages in the storage
system (Section 2.4). Though these tools are F2FS-specific, they can be
extended to other file systems that do active data segregation. With F2FS,
this information is available in the /proc file system222We also tried Brtfs
with ZNS, but it was unstable.. The file system-related metadata is also
available as a part of low-level libraries (such as libext2fs or libf2fs) or
can be generated [45]. Figure 2 (b) and (c) illustrate the design of
zns.segmap and zns.imap tools. They retrieve extents for various files
(ioctl() call) and inodes (FS metadata walks) from F2FS, and retrieve F2FS
segment lifetime classifications and the inode location.

###  2.3 zns.trace

(a) RocksDB + F2FS

(b) MongoDB + F2FS

(c) PostgreSQL + F2FS

(d) RocksDB + (aged) F2FS

Figure 3: Reset visualization using zns.trace for an identical YCSB workload-A
for multiple databases on F2FS. Figure (d) has a different heatmap scale
(0-100).

The zns.trace tool identifies performance-critical “Request Scale” and
“Uniform Data Lifetime” contracts by tracking ZNS command calls. zns.trace is
a combination of a BPFtrace [19] script and a plotting tool that traces zone-
level ZNS write, append, read, and reset operations (addressing C2). Tracing
such data is useful for investigating the access patterns to the underlying
storage device independently of file system or application workloads.

zns.trace utilizes BPFtrace [19], which inserts probes into the Linux kernel
functions, that upon being triggered (i.e., the function being called)
initiate data collection. The tracing script captures the NVMe I/O event with
the command I/O sizes (their histogram) and zone reset calls, and maps the
events to their corresponding zone(s). By analyzing the function arguments,
the script identifies the type of operation, and further extracts data fields
based on the request size. Importantly, the tracing supports ZNS devices in
VMs (apart from just the host), where the zone reset command sets the function
argument for the type of command to REQ_OP_DRV_OUT, indicating the host driver
(e.g., vfio-pci when using NVMe passthrough to the VM) is responsible for the
request. This case requires to furthermore analyze the NVMe command and its
zone management command field on the type of zone management action (e.g.,
close, finish, reset, open, offline). zns.trace relies on inserting kernel
probes to parse I/O functions, and is therefore currently limited to kernel-
based ZNS tracing. However, ongoing work is extending the tracing framework
for user-level (e.g., SPDK) I/O and broader zone management request tracing.

To illustrate the utility of zns.trace we run an identical workload on a
number of database/file system and quantify the workload reset profiles. The
number of resets is directly linked to the number of reset cycles that an SSD
can undergo before exhausting flash chips. The “Uniform Data Lifetime”
contract recommends generating data with a uniform lifetime to evenly spread
the device wear. We run experiments on an emulated NVMe ZNS device (QEMU
v6.0.0) with 64 zones of size 64MiB (4GiB in total). Our workload is a YCSB
workload-A (50% update, 50% read) [8] on RocksDB [13](7.4.3), MongoDB
[35](6.06), and PostgreSQL [32](9.6.24) as KV backend targets with F2FS as
file system. Figure 3 shows our results. Here each cell represents a zone, and
the color indicates the total number of resets issued to the zone (since
startup). Blue squares indicate a zone to which no reset commands were issued
at all. There are two interesting observations. Firstly, for an identical
workload, the three KV backends show vastly different profiles. We can see
that for this test configuration PostgreSQL leads to significantly more
resets. Additionally, we can identify that one of the bottom left zones (zone
2) is in all three cases heavily utilized. This zone corresponds to a warm
node zone initialized by F2FS, where the inodes of files are written.
Secondly, file system aging has a significant impact on the reset profile as
shown by Figure 3 (d) which has an aged F2FS (10$\times$ iterations). Both of
these results make a case for a systematic study of how zone resets are called
or consequently, how data grouping by uniform lifetime or death time is done.

###  2.4 RocksDB on F2FS with ZNS Timeline

To demonstrate an end-to-end utility of zns-tools, we build an end-to-end data
placement visualization using RocksDB on F2FS. Using the RocksDB’s db_bench
benchmark with workloads fillrandom and overwrite fills the F2FS file system
on the ZNS device. Minor modifications (less than 100 LOCs) to the RocksDB
source code are made to trace the activity of operations, and retrieve the
data mapping of the generated files. On each compaction or flush operation,
RocksDB calls the zns-tools to map all its files. Section 2.4 illustrates this
end-to-end timeline (automatically generated from traces) with a few salient
events across the layers (applications, file systems, and ZNS device) over the
lifetime of an SSTable. The timeline starts at time 0, where data is flushed
from memory to level-0 (abbreviated L0) as SSTable 31. The file is stored in
the orange zone classified as WARM. Subsequently, F2FS issues a series of
reset calls on several zones. The next logical event is the compaction of file
31 with 33 and 34 to generate file 37 on L2333internal trivial promotion
events such as moving 31 from L0 to L1 are skipped in the visualization for
the sake of clarity.. While file 37 is written as WARM file, old files in
prior zones are deleted (pink lines). In the next round, file 37 is picked up
for compaction with 35 and 38 files to generate two L2 files (41, and 42).
Such a timeline visualization gives an understanding of how the different
RocksDB operation interaction with F2FS affects the utilization of the ZNS
storage space, file classification, and data movement over time, thus making
it easy to spot contract violations visually.

Figure 4: (Abridged) End-to-end event timeline visualized using zns-tools.

##  3 Related Work

Flash SSDs with their complex internal logic and “unwritten contracts” [15]
have also been studied in detail for performance and operation
characterizations [26, 25, 31, 18, 22, 30] and with the impact of GC
operations [39, 48, 27, 17, 47]. There is a rich history of collecting file
system traces, analyzing, and replaying them for understanding the impact of
optimizations [20, 36, 12, 42, 3, 46]. Much of these works only focus on basic
read/write interfaces that are sufficient for HDDs, but not SSDs. None of
these tools track device management-related operations (reset, open, finish,
close), which are now a critical part of ZNS devices. The libzbd ZNS library
also support a basic GUI visualization tool for zone states [2], however, it
lacks any application or file system level information. Beyond these tools,
the eBPF-based BCC framework has emerged as the de-facto API for writing
complex, end-to-end tracking frameworks [1], which we also leverage. Similar
to zns-tools, IOScope uses eBPF-assisted file offset-based I/O tracing [43].
However, its tracing is limited to the files (at the VFS level), and does not
connect the file to its location, which can change based on the file system
and application level operations. Several block-level tracking tools exist
(BCC’s biotop and biosnoop, DTraces’s iosnoop), however, they do not link
block-level I/O back to the file system or applications. MapFS is a file
system interface that presents low-level details from file to storage mappings
for applications to manipulate data-heavy operations via light-weight metadata
operations [51]. Prabhakaran et al. [40] introduce techniques to study file
system behavior with semantic knowledge of events and on-disk data structure
layouts. zns-tools extends such motivation to include workloads with the new
ZNS management operations as well. HintStore is a flexible framework that is
designed to explore the effectiveness of hints with heterogeneous storage
[14]. zns-tools analysis captures the after-effect of the hints, and its
collected data can be used to verify if hints are implemented in an end-to-end
manner. In a distributed setting, systems like Wintermute [34], Apollo [41],
and Beacon [54] provide a distributed framework for operational data
collection and analysis. In comparison to these works, the focus of zns-tools
is on collecting, analyzing, and visualizing written ZNS contracts across
multiple storage stack layers to reason about previously unwritten SSD storage
contracts.

##  4 Conclusion and Ongoing Work

In this work, we have presented a case to systematically reason about
previously “unwritten contracts” for flash SSDs on recently emerged ZNS flash
SSD devices. Due to the unique I/O and management interface of ZNS SSDs, they
make such unwritten contracts, written by putting them under the control of
the host storage stack. To investigate the effectiveness of ZNS contracts, we
have developed and presented a set of zns-tools to collect, analyze, and
visualize ZNS operational data. We are working on tracing events from
PostgreSQL, Aerospike, and scientific workloads on top of BrtFS also, to
develop a broader framework in which such end-to-end contract analysis can be
done.

Acknowledgment: This work in-parts is supported by the donations from Western
Digital.

## Availability

https://github.com/stonet-research/zns-tools.

## References

  * [1] BPF Compiler Collection (BCC).  https://github.com/iovisor/bcc, 2023.  Accessed: 2023-29-03.
  * [2] libzbd User Library.  https://zonedstorage.io/docs/tools/libzbd, 2023.  Accessed: 2023-29-03.
  * [3] Akshat Aranya, Charles P. Wright, and Erez Zadok.  Tracefs: A file system to trace them all.  In 3rd USENIX Conference on File and Storage Technologies (FAST 04), San Francisco, CA, March 2004. USENIX Association.
  * [4] Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobbler, Michael Wei, and John D. Davis.  CORFU: A shared log design for flash clusters.  In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12), pages 1–14, San Jose, CA, April 2012. USENIX Association.
  * [5] Matias Bjørling, Abutalib Aghayev, Hans Holmberg, Aravind Ramesh, Damien Le Moal, Gregory R. Ganger, and George Amvrosiadis.  ZNS: Avoiding the block interface tax for flash-based SSDs.  In 2021 USENIX Annual Technical Conference (USENIX ATC 21), pages 689–703. USENIX Association, July 2021.
  * [6] Matias Bjørling, Jens Axboe, David Nellans, and Philippe Bonnet.  Linux block io: Introducing multi-queue ssd access on multi-core systems.  In 6th International Systems and Storage Conference, SYSTOR 13. ACM, 2013.
  * [7] Matias Bjørling, Javier González, and Philippe Bonnet.  LightNVM: The Linux Open-Channel SSD Subsystem.  In Proceedings of the 15th Usenix Conference on File and Storage Technologies, FAST’17, page 359–373, Santa clara, CA, USA, 2017.
  * [8] Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears.  Benchmarking cloud serving systems with ycsb.  In ACM Symposium on Cloud Computing (SoCC), page 143–154, 2010\.
  * [9] Western Digital.  Zoned Storage - Write Ordering Control.  https://zonedstorage.io/docs/linux/sched, 2023.  Accessed: 2023-29-03.
  * [10] Krijn Doekemeijer, Nick Tehrany, Balakrishnan Chandrasekaran, Matias Bjørling, and Animesh Trivedi.  Performance characterization of nvme flash devices with zoned namespaces (zns).  In (to appear) IEEE International Conference on Cluster Computing, CLUSTER 2023, October 31-November 3, 2023, Santa Fe, New Mexico, USA. IEEE, 2023.
  * [11] Siying Dong, Andrew Kryczka, Yanqin Jin, and Michael Stumm.  Evolution of development priorities in key-value stores serving large-scale applications: The rocksdb experience.  In FAST, pages 33–49, 2021.
  * [12] Daniel Ellard and Margo Seltzer.  New NFS tracing tools and techniques for system analysis.  In 17th Large Installation Systems Administration Conference (LISA 03), San Diego, CA, October 2003. USENIX Association.
  * [13] Facebook.  RocksDB: A Persistent Key-Value Store for Flash and RAM Storage.  https://github.com/facebook/rocksdb.  Accessed: 2023-03-01.
  * [14] Xiongzi Ge, Zhichao Cao, David H. C. Du, Pradeep Ganesan, and Dennis Hahn.  Hintstor: A framework to study I/O hints in heterogeneous storage.  ACM Trans. Storage, 18(2):18:1–18:24, 2022.
  * [15] Jun He, Sudarsun Kannan, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau.  The unwritten contract of solid state drives.  In Proceedings of the Twelfth European Conference on Computer Systems, EuroSys ’17, page 127–144, New York, NY, USA, 2017. Association for Computing Machinery.
  * [16] Mohammad Hedayati, Kai Shen, Michael L. Scott, and Mike Marty.  Multi-queue fair queueing.  In Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC ’19, page 301–314, USA, 2019. USENIX Association.
  * [17] Jian Hu, Hong Jiang, and Prakash Manden.  Understanding performance anomalies of ssds and their impact in enterprise application environment.  In Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’12, page 415–416, New York, NY, USA, 2012. Association for Computing Machinery.
  * [18] H. Howie Huang, Shan Li, Alex Szalay, and Andreas Terzis.  Performance modeling and analysis of flash-based storage devices.  In 2011 IEEE 27th Symposium on Mass Storage Systems and Technologies (MSST), pages 1–11, 2011.
  * [19] iovisor.  Bpftrace.  https://github.com/iovisor/bpftrace.  Accessed: 2023-29-03.
  * [20] Sooman Jeong, Kisung Lee, Jungwoo Hwang, Seongjin Lee, and Youjip Won.  Androstep: Android storage performance analysis tool.  In Stefan Wagner and Horst Lichter, editors, Software Engineering 2013 - Workshopband, pages 327–340, Bonn, 2013. Gesellschaft für Informatik e.V.
  * [21] Cheng Ji, Li-Pin Chang, Liang Shi, Chao Wu, Qiao Li, and Chun Jason Xue.  An empirical study of File-System fragmentation in mobile storage systems.  In 8th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 16), Denver, CO, June 2016. USENIX Association.
  * [22] Myoungsoo Jung and Mahmut Kandemir.  Revisiting widely held ssd expectations and rethinking system-level implications.  In Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’13, page 203–216, New York, NY, USA, 2013. Association for Computing Machinery.
  * [23] Saurabh Kadekodi, Vaishnavh Nagarajan, and Gregory R. Ganger.  Geriatrix: Aging what you see and what you don’t see. A file system aging approach for modern storage systems.  In 2018 USENIX Annual Technical Conference (USENIX ATC 18), pages 691–704, Boston, MA, 2018. USENIX Association.
  * [24] Jaegeuk Kim.  DEFRAG.F2FS.  https://manpages.debian.org/testing/f2fs-tools/defrag.f2fs.8.en.html, 2021\.
  * [25] Jihun Kim, Joonsung Kim, Pyeongsu Park, Jong Kim, and Jangwoo Kim.  Ssd performance modeling using bottleneck analysis.  IEEE Computer Architecture Letters, 17(1):80–83, 2018.
  * [26] Joonsung Kim, Kanghyun Choi, Wonsik Lee, and Jangwoo Kim.  Performance modeling and practical use cases for black-box ssds.  ACM Trans. Storage, 17(2), jun 2021.
  * [27] Tomer Lange, Joseph (Seffi) Naor, and Gala Yadgar.  Offline and online algorithms for ssd management.  Proc. ACM Meas. Anal. Comput. Syst., 5(3), dec 2021.
  * [28] Changman Lee, Dongho Sim, Joo-Young Hwang, and Sangyeun Cho.  F2fs: A new file system for flash storage.  In Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST’15, page 273–286, USA, 2015. USENIX Association.
  * [29] Gyusun Lee, Seokha Shin, Wonsuk Song, Tae Jun Ham, Jae W. Lee, and Jinkyu Jeong.  Asynchronous i/o stack: A low-latency kernel i/o stack for ultra-low latency ssds.  In USENIX Annual Technical Conference, USENIX ATC 19, page 603–616. USENIX Association, 2019.
  * [30] Nanqinqin Li, Mingzhe Hao, Huaicheng Li, Xing Lin, Tim Emami, and Haryadi S. Gunawi.  Fantastic ssd internals and how to learn and use them.  In Proceedings of the 15th ACM International Conference on Systems and Storage, SYSTOR ’22, page 72–84, New York, NY, USA, 2022. Association for Computing Machinery.
  * [31] Shan Li and H. Howie Huang.  Black-box performance modeling for solid-state drives.  In 2010 IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pages 391–393, 2010.
  * [32] Bruce Momjian.  PostgreSQL: introduction and concepts, volume 192.  Addison-Wesley New York, 2001.
  * [33] Aota Naohiro.  Btrfs: Zoned block device support [lwn.net].  https://lwn.net/Articles/833260/, oct 2020.  Accessed: 2023-29-03.
  * [34] Alessio Netti, Micha Müller, Carla Guillen, Michael Ott, Daniele Tafani, Gence Ozer, and Martin Schulz.  Dcdb wintermute: Enabling online and holistic operational data analytics on hpc systems.  In Proceedings of the 29th International Symposium on High-Performance Parallel and Distributed Computing, HPDC ’20, page 101–112, New York, NY, USA, 2020. Association for Computing Machinery.
  * [35] Trong-Dat Nguyen and Sang-Won Lee.  Optimizing mongodb using multi-streamed ssd.  In Proceedings of the 7th International Conference on Emerging Databases: Technologies, Applications, and Theory, pages 1–13. Springer, 2018\.
  * [36] John K. Ousterhout, Hervé Da Costa, David Harrison, John A. Kunze, Mike Kupfer, and James G. Thompson.  A trace-driven analysis of the unix 4.2 bsd file system.  In Proceedings of the Tenth ACM Symposium on Operating Systems Principles, SOSP ’85, page 15–24, New York, NY, USA, 1985. Association for Computing Machinery.
  * [37] Jian Ouyang, Shiding Lin, Song Jiang, Zhenyu Hou, Yong Wang, and Yuanzheng Wang.  Sdf: Software-defined flash for web-scale internet storage systems.  In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’14, page 471–484, New York, NY, USA, 2014. Association for Computing Machinery.
  * [38] Jonggyu Park and Young Ik Eom.  Fragpicker: A new defragmentation tool for modern storage devices.  In Robbert van Renesse and Nickolai Zeldovich, editors, SOSP ’21: ACM SIGOPS 28th Symposium on Operating Systems Principles, Virtual Event / Koblenz, Germany, October 26-29, 2021, pages 280–294. ACM, 2021.
  * [39] Roman Pletka, Ioannis Koltsidas, Nikolas Ioannou, Saša Tomić, Nikolaos Papandreou, Thomas Parnell, Haralampos Pozidis, Aaron Fry, and Tim Fisher.  Management of next-generation nand flash to achieve enterprise-level endurance and latency targets.  ACM Trans. Storage, 14(4), dec 2018.
  * [40] Vijayan Prabhakaran, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau.  Analysis and evolution of journaling file systems.  In Proceedings of the Annual Conference on USENIX Annual Technical Conference, ATEC ’05, page 8, USA, 2005. USENIX Association.
  * [41] Neeraj Rajesh, Hariharan Devarajan, Jaime Cernuda Garcia, Keith Bateman, Luke Logan, Jie Ye, Anthony Kougkas, and Xian-He Sun.  Apollo: An ml-assisted real-time storage resource observer.  In Proceedings of the 30th International Symposium on High-Performance Parallel and Distributed Computing, HPDC ’21, page 147–159, New York, NY, USA, 2021. Association for Computing Machinery.
  * [42] Drew Roselli, Jacob R. Lorch, and Thomas E. Anderson.  A comparison of file system workloads.  In 2000 USENIX Annual Technical Conference (USENIX ATC 00), San Diego, CA, June 2000. USENIX Association.
  * [43] Abdulqawi Saif, Lucas Nussbaum, and Ye-Qiong Song.  Ioscope: A flexible i/o tracer for workloads’ i/o pattern characterization.  In Rio Yokota, Michèle Weiland, John Shalf, and Sadaf Alam, editors, High Performance Computing, pages 103–116, Cham, 2018. Springer International Publishing.
  * [44] Theano Stavrinos, Daniel S. Berger, Ethan Katz-Bassett, and Wyatt Lloyd.  Don’t be a blockhead: Zoned namespaces make work on conventional ssds obsolete.  In Proceedings of the Workshop on Hot Topics in Operating Systems, HotOS ’21, page 144–151, New York, NY, USA, 2021. Association for Computing Machinery.
  * [45] Kuei Sun, Daniel Fryer, Joseph Chu, Matthew Lakier, Angela Demke Brown, and Ashvin Goel.  Spiffy: Enabling File-System aware storage applications.  In 16th USENIX Conference on File and Storage Technologies (FAST 18), pages 91–104, Oakland, CA, February 2018. USENIX Association.
  * [46] Vasily Tarasov, Santhosh Kumar, Jack Ma, Dean Hildebrand, Anna Povzner, Geoff Kuenning, and Erez Zadok.  Extracting flexible, replayable models from large block traces.  In William J. Bolosky and Jason Flinn, editors, Proceedings of the 10th USENIX conference on File and Storage Technologies, FAST 2012, San Jose, CA, USA, February 14-17, 2012, page 22. USENIX Association, 2012\.
  * [47] Benny Van Houdt.  A mean field model for a class of garbage collection algorithms in flash-based solid state drives.  In Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’13, page 191–202, New York, NY, USA, 2013. Association for Computing Machinery.
  * [48] Robin Verschoren and Benny Van Houdt.  On the endurance of the d-choices garbage collection algorithm for flash-based ssds.  ACM Trans. Model. Perform. Eval. Comput. Syst., 4(3), jul 2019.
  * [49] Don H Walker.  A comparison of nvme and ahci.  https://sata-io.org/sites/default/files/documents/NVMe%20and%20AHCI_%20_long_.pdf, Accessed: 2022-05-02.
  * [50] Western Digital.  Ultrastar dc zn540.  https://www.westerndigital.com/products/internal-drives/data-center-drives/ultrastar-dc-zn540-nvme-ssd, Accessed: 2022-05-02.
  * [51] Jake Wires, Mark Spear, and Andrew Warfield.  Exposing file system mappings with MapFS.  In 3rd Workshop on Hot Topics in Storage and File Systems (HotStorage 11), Portland, OR, June 2011. USENIX Association.
  * [52] Jiwon Woo, Minwoo Ahn, Gyusun Lee, and Jinkyu Jeong.  D2FQ: device-direct fair queueing for nvme ssds.  In Marcos K. Aguilera and Gala Yadgar, editors, 19th USENIX Conference on File and Storage Technologies, FAST 2021, February 23-25, 2021, pages 403–415. USENIX Association, 2021.
  * [53] NVM Express Workgroup.  NVM Express NVM Command Set Specification 2.0.  Standard, January 2022.  Available from: https://nvmexpress.org/specifications.
  * [54] Bin Yang, Xu Ji, Xiaosong Ma, Xiyang Wang, Tianyu Zhang, Xiupeng Zhu, Nosayba El-Sayed, Haidong Lan, Yibo Yang, Jidong Zhai, Weiguo Liu, and Wei Xue.  End-to-end I/O monitoring on a leading supercomputer.  In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 379–394, Boston, MA, February 2019. USENIX Association.
  * [55] Jingpei Yang, Rajinikanth Pandurangan, Changho Choi, and Vijay Balakrishnan.  Autostream: Automatic stream management for multi-streamed ssds.  In Proceedings of the 10th ACM International Systems and Storage Conference, SYSTOR ’17, New York, NY, USA, 2017. Association for Computing Machinery.
  * [56] Lihua Yang, Fang Wang, Zhipeng Tan, Dan Feng, Jiaxing Qian, and Shiyun Tu.  Ars: Reducing f2fs fragmentation for smartphones using decision trees.  In Proceedings of the 23rd Conference on Design, Automation and Test in Europe, DATE ’20, page 1061–1066, San Jose, CA, USA, 2020. EDA Consortium.


# Do Deep Neural Networks Capture Compositionality
in Arithmetic Reasoning?

Keito Kudo1 Yoichi Aoki1 Tatsuki Kuribayashi1,2 Ana Brassard3,1
Masashi Yoshikawa1 Keisuke Sakaguchi1,3 Kentaro Inui1,3
1Tohoku University 2Langsmith, Inc. 3RIKEN
{keito.kudo.q4<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Compositionality is a pivotal property of symbolic reasoning. However, how
well recent neural models capture compositionality remains underexplored in
the symbolic reasoning tasks. This study empirically addresses this question
by systematically examining recently published pre-trained seq2seq models with
a carefully controlled dataset of multi-hop arithmetic symbolic reasoning. We
introduce a skill tree on compositionality in arithmetic symbolic reasoning
that defines the hierarchical levels of complexity along with three
compositionality dimensions: systematicity, productivity, and substitutivity.
Our experiments revealed that among the three types of composition, the models
struggled most with systematicity, performing poorly even with relatively
simple compositions. That difficulty was not resolved even after training the
models with intermediate reasoning steps.111Our code and data are available at
https://github.com/keitokudo/dentaku_skill_tree.

##  1 Introduction

Integrating symbolic reasoning capabilities into neural models has been a
crucial goal of artificial intelligence Marcus (2003); d’Avila Garcez and Lamb
(2020). With this in mind, many researchers investigated how well modern
neural models achieve symbolic reasoning Lake and Baroni (2018). However,
recent studies have reported conflicting results on this; some suggest that
neural models can solve complex multi-hop reasoning Clark et al. (2020), while
others claim that models struggle even with performing simple symbolic
operations Qian et al. (2022).

Figure 1: Three dimensionalities of compositionality in arithmetic symbolic
reasoning

As a step toward further understanding neural models’ symbolic reasoning
ability, this study systematically analyzes recently published pre-trained
seq2seq models using a carefully controlled dataset of multi-hop arithmetic
symbolic reasoning. Specifically, our study empirically evaluates the models’
ability to generalize the _compositionality_ underlying arithmetic reasoning,
where we explore three dimensions of compositionality: (i) systematicity, (ii)
productivity, and (iii) substitutivity, as illustrated in Figure 1. Capturing
compositionality is crucial in performing symbolic reasoning since
compositionality is a pivotal property of generalizability over training
instances.

To systematically explore the models’ composition ability, we introduce a
skill tree on compositionality that defined the hierarchical levels of
complexity in arithmetic symbolic reasoning, as illustrated in Figure 2. Using
this hierarchy as a lens, we identify the limitations of the neural seq2seq
models in capturing the compositionality in arithmetic symbolic reasoning. Our
major findings can be summarized as follows:

  * •

Among the three types of composition, the models struggled most with
systematicity, performing poorly even with relatively simple compositions.

  * •

The major difficulty in systematicity was in the access to intermediate
information that is not stated in input but produced during the reasoning.

  * •

Capturing systematicity remained hard for the models trained with the
information of the intermediate reasoning steps.

##  2 Skill tree in arithmetic reasoning

We take arithmetic reasoning as the domain for our exploration because it
allows us to synthesize questions systematically, as we show in this paper,
which helps examine a model’s composition ability in a controlled manner.
Furthermore, the arithmetic reasoning ability of neural models has gained much
attention as modern large language models still struggle with this problems
Rae et al. (2021).

Specifically, we use multi-hop arithmetic reasoning problems as follows:
_Question:_ A=1, B=2, C=A+2, C=?
_Answer:_ 3

Here, the value assigned to the variable C is asked.

###  2.1 Compositionality in multi-hop symbolic reasoning

In this study, we specifically focused on three dimensions: systematicity,
productivity, and substitutivity Hupkes et al. (2020). According to these, we
evaluate how well neural models achieve compositional generalization.

Systematicity refers to the ability of combining known different concepts into
a more complex concept, i.e., structural composition. To evaluate this ability
in models, we first trained with several types of primitive operations (e.g.,
addition; A=1+2,A=? and selection; A=1,B=2,B=?). Then, we measured the
performance in solving problems consisting of combinations of primitives
(e.g., A=1+2,B=2+3,B=?).

Productivity refers to the ability to solve longer/complex problems based on
shorter/simpler ones. To evaluate this ability in models, we first trained
with a short version of a formula (e.g., A=1+2,B=2+3,B=?). Then, we measured
the performance in solving longer problems (e.g., A=1+2,B=2+3,C=3+4,C=?).

Substitutivity refers to the ability to keep the performance even if a
particular constituent in a problem is replaced with another (unseen)
constituent (i.e., lexical composition). To evaluate this ability in models,
we conduct several experiments changing the variable characters between
training and test (e.g., train with A=1+2,A=?; then evaluated with α=1+2,α=?).

###  2.2 Dataset configurations

Typical symbolic reasoning (e.g., procedural programming, assembly language)
consists of at least three primitive symbol manipulations: assignment (a=2),
arithmetic operation (1+2), and reference (a=?). With this in mind, our
dataset is generated by combining the following five basic formulas: (i) A=1
(assignment), (ii) A=B (reference & assignment), (iii) A=1+2 (arithmetic
operation & assignment), (iv) A=B+2 (arithmetic operation & assignment &
reference), (v) A=? (reference). The detailed properties are explained in
Section 3.

###  2.3 Skill tree evaluations

We preliminarily observed that compositionally generalizing complex multi-hop
arithmetic reasoning was difficult for neural seq2seq learners (the
1,2,6$\rightarrow$9 setting in Section 4). Building on this fact, this study
questions what type of composition made it hard for the neural models. To
answer this, we designed a skill tree on compositionality that organizes the
(hierarchical) complexity levels of symbolic reasoning.222The term ”skill
tree” refers to a visualization method of step-by-step learning in the field
of pedagogy Tondello and Nacke (2019), distinct from the ”tree” in graph
theory. Evaluating the models using problems with different complexity of
composition in a step-wise manner, we elucidate the exact weakness of neural
seq2seq models in multi-hop symbolic reasoning.

Figure 2: Skill tree to evaluate compositional generalization. The data format
of primitive operations is gray and others (complex formulas composed of
combinations of primitive operations) are blue .

Specifically, we designed ten versions of symbolic reasoning problems. The
hierarchical relationship of their task levels is illustrated in Figure 2; in
this skill tree, each vertex, i.e., domain, corresponds to different task
settings with different complexity, and edges represent the hierarchical
complexity levels.

By adequately selecting a particular combination of training and test domains,
we evaluated the compositional generalization ability of the models from
various perspectives. Here, the arithmetic expressions used in the test domain
are a combination of those in training domains, creating a semi-order
relationship in the skill tree. For example, using the settings 1 (A=1+2,A=?)
and 2 (A=1,B=2,B=?) as a training set, and 4 (A=1+2,B=2+3,B=?) as a test set,
one can evaluate the model’s systematicity generalization towards the
arithmetic operations (a+b) and assignments (A=$i$,B=$j$,B=?).

|  | base | large | x-large
---|---|---|---|---
Task | Type | ZA | WA | ZA | WA | ZA | WA
1,2 | sys. | 42.0 | 82.1 | 35.2 | 89.8 | 51.7 | 96.7
$\rightarrow$4 | +subst. | 39.1 | 80.4 | 33.2 | 89.4 | 50.7 | 96.7
2,3 | sys. | 33.6 | 75.4 | 32.1 | 85.6 | 35.9 | 94.7
$\rightarrow$5 | +subst. | 33.6 | 77.0 | 31.5 | 87.2 | 36.5 | 94.9
2,3,6 | sys. | 40.8 | 76.5 | 39.1 | 87.7 | 40.5 | 94.6
$\rightarrow$8 | +subst. | 39.3 | 74.7 | 37.5 | 86.4 | 39.2 | 94.9
2,3,6 | sys. | 56.5 | 79.7 | 51.0 | 83.7 | 58.1 | 94.2
$\rightarrow$7 | +subst. | 57.6 | 80.2 | 51.1 | 85.8 | 56.7 | 95.1
1,2,6 | sys. | 24.1 | 28.2 | 23.1 | 29.3 | 27.5 | 32.6
$\rightarrow$9 | +subst. | 25.8 | 28.0 | 24.1 | 31.7 | 28.5 | 34.7
7,8 | sys. | 23.6 | 21.3 | 25.3 | 25.9 | 22.3 | 28.2
$\rightarrow$10 | +subst. | 22.3 | 21.6 | 24.4 | 26.4 | 23.0 | 30.2
1 | prod. | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0
$\rightarrow$3 | +subst. | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0
4 | prod. | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0
$\rightarrow$5 | +subst. | 99.9 | 99.9 | 100.0 | 100.0 | 100.0 | 99.9
9 | prod. | 57.0 | 59.3 | 61.7 | 63.8 | 60.6 | 62.7
$\rightarrow$10 | +subst. | 58.4 | 60.9 | 62.2 | 64.1 | 59.5 | 64.5
Table 1:  Average accuracies in the experiment with 2 different seeds. The
“Task” column exhibits (train$\rightarrow$test) domains corresponding to the
skill-tree (Figure 2). The “Type” column shows the targeted compositionality
type in each setting; here, “sys.,” “prod,” and “subst.” denote the
systematicity, productivity, and substitutivity generalizations, respectively.

##  3 Experimental settings

###  3.1 Data

Dataset: In each experimental setting, we refer to the training domains as
$\mathcal{D}_{\mathrm{train}}=\\{d_{\mathrm{train}1},\cdots
d_{\mathrm{train}k}\\}$ and the test domain as $d_{\mathrm{test}}$. Each
domain has 100,000 training data and 3,200 test data; these are randomly
generated, and there is no overlapped instance. When the training domain
consisted of multiple domains, we used the union of the training data in
$\mathcal{D}_{\mathrm{train}}$. In addition, when the training domain is not
primitive operations (1, 2, 3, and 6 in Figure 2), we further added the
primitive operation data related to the training domain (Appendix A) into the
training data.

Arithmetic expressions: As introduced in Section 2, the input is a sequence of
arithmetic expressions. Formally, each expression is in the format of a=$n$ or
a=$n${+,-,max,min}$m$ except that the final expression asks the number
assigned to a specified variable (b=?). Here, a and b are a member of a
variable name set $\Sigma$; $n$ and $m$ are a member of the variable name set
or number set $\Sigma\cup\mathcal{N}$. Specifically, $\Sigma$ consists of 21
alphabets, and $N$ consists of the integer from 0 to 99. The symbol =
indicates that the result of the left-hand side is substituted into the right-
hand side. The operations (+, -, max, and min) correspond to arithmetic
addition, subtraction, max (returning the larger of its left and right
numbers), and min (returning the smaller of its left and right numbers).

The questions are designed so that the answer is unique, and depending on the
problem set-up, may include mathematical expressions that are not directly
related to the final answer, i.e., distractors. The order of the equations is
arbitrary; the first equation should not necessarily be calculated first.

Substitivity test: In each experimental setting, we evaluate the
substitutivity generalization performance of the model under the situation
where the variable names are replaced with unseen ones, e.g., training with
a=1+2,a=?; then evaluating with α=2+4,α=?. In this setting, we replaced each
variable name in the test set with one of five alphabets that do not overlap
with the training ones.

###  3.2 Trainig and test

Training: The training stops when the accuracy on the validation dataset does
not increase in successive five epochs or until the validation accuracy
reaches 100%. Checkpoints with the highest accuracy in the validation dataset
are used for evaluation. Note that among the experiments, the accuracy in the
training domain reached at least 99.5%; this indicates that the primitive
operations were learnable for the models. Detailed settings for training are
described in Appendix A.

Evaluation metrics: The accuracy is calculated by the test data in the test
domain $d_{\mathrm{test}}$. Here, we used two metrics: (i) zero-shot accuracy
(ZA) and (ii) weighted average of accuracies (WA) to measure the efficiency of
learning Talmor et al. (2020). In measuring WA, a model was further trained
using the training set in the test domain $d_{\mathrm{test}}$; then, the
weighted average of accuracies at every update was calculated (details are in
Appendix B).

###  3.3 Models:

We used three different sizes (base, large, and xl) of T5 Raffel et al.
(2020), which is a widely used pre-trained seq2seq model in numerical
reasoning tasks Pal and Baral (2021); Chung et al. (2022); Yang et al. (2021).
Note that we began our training using the models with learned parameters. We
also evaluated BART variants and randomly initialized models in Appendix C.

##  4 Experiments and results

We adopted nine combinations of training and test domains as shown in the
first column of Table 1 (training domains$\rightarrow$test domain). Six of
them test the systematicity generalization and the other three test
productivity generalization. In each setting, we further tested substitutivity
generalization ability using the test domain data with a different variable
name set (e.g., α instead of A) to that used in the training domain. Table 1
shows the overall results. We observed the following four trends:

  * •

Systematicity generalization was more difficult than productivity
generalization.

  * •

Even in the simple composition (the setting 1,2$\rightarrow$4), the models
struggle with generalization from zero or few examples.

  * •

Models achieved substitutivity generalization.

  * •

Model size did not incur substantial performance difference.

We identified that the systematicity generalization of reference and
arithmetic operations (setting $2,3\rightarrow 5$; from A=1,B=2,C=3,C=? and
A=1+2,A=? to A=1+2,B=2+3,C=4+5,C=?) was a simple setting, yet difficult to
solve (refer to Appendix D for results on other tasks.). To better understand
why neural models struggle with this setting, we decomposed the complexity of
this setting and analyzed the model performance. Note that Kim and Linzen
(2020) also suggested that neural models lack systematicity generalization
ability in the context of semantic parsing; our results corroborate their
findings from the context of arithmetic multi-hop reasoning.

| base | large | x-large
---|---|---|---
Setting | ZA | WA | ZA | WA | ZA | WA
2,3$\rightarrow$5 | 33.6 | 75.4 | 32.1 | 85.6 | 35.9 | 94.7
String | 37.3 | 94.1 | 66.1 | 98.4 | 86.9 | 99.3
Steps | 26.2 | 82.1 | 36.1 | 89.4 | 33.7 | 96.4
Table 2:  Ablation study with the 2,3$\rightarrow$5 (vanilla) setting.
“String” refers to the setting where string operations are used instead of
arithmetic operations. “Step” denotes the setting generating intermediate
steps.

#### Is this difficulty specific to arithmetic symbolic reasoning?

We experimented with the same setting except that the four arithmetic
operations are replaced with string operations (join, reserveJoin, strSub, and
stackJoin; details are in Appendix E.1). The notable difference between
arithmetic and string operations is that the string operation could be
achieved by only copying selective elements in the input (e.g., 12+34=1234),
while arithmetic operation requires the models to access the arithmetic
knowledge stored in their internals (e.g., 1+2=3) and generate new information
not stated in the input context (e.g., 3).

Larger models tended to overcome the weakness in composition with string
operations (e.g., the accuracy of 86.9 in zero-shot evaluation with the
x-large model), while they struggled with arithmetic operations. This suggests
that the major difficulty in systematicity was in the access to the arithmetic
knowledge (e.g., 1+1=2).

#### Does scratchpad training alleviate the difficulty?

Existing studies suggested that showing the intermediate step (scratchpad-
style training/inference) improves the multi-hop reasoning ability of neural
models Wei et al. (2022). We tested whether such an explicit generation of
intermediate information alleviates the difficulty faced in the previous
analysis. Specifically, we trained models with intermediate steps (e,g.
A=1+2,B=2+3,B=?; B=2+3,B=5. Details are in Appendix E.2) during training.

The accuracy was calculated by the exact match of the answer and intermediate
steps (the steps are designed to be uniquely determined). The performance gain
due to explicating the intermediate steps was limited (Table 2), at least with
our T5-based models. This shows that, in our carefully controlled setting,
merely employing the scratchpad-style generation is not substantially
effective.

Complexity | base | large | x-large | Average
---|---|---|---|---
dimensions | ZA | WA | ZA | WA | ZA | WA
$\Delta$#variables | 0.098 | -0.098 | 0.488 | -0.293 | -0.098 | -0.488 | -0.065
$\Delta$#numbers | 0.059 | 0.265 | -0.088 | 0.647 | 0.206 | 0.677 | 0.294
$\Delta$#operations | -0.507 | -0.338 | -0.338 | 0.169 | -0.338 | 0.169 | -0.197
$\Delta$#reference | -0.655 | -0.655 | -0.393 | -0.655 | -0.655 | -0.655 | -0.611
Table 3:  Spearman’s rank correlation coefficient between the increase of
training–test arithmetic complexity and the compositional generalization
performance (accuracy) across the nine settings listed in Table 1. A negative
score indicates that the greater the training–test discrepancy in its
dimension, the more difficult compositional generalization is. In the case
that there are multiple training domains, the maximum value among them is
used.

##  5 Analysis

We conduct a more in-depth analysis of compositional generalization
difficulties from another perspective—complexity of arithmetic expressions.
Specifically, for each pair of training and test domains listed in Table 1
(e.g., 1,2$\rightarrow$4), we quantified the increase of the complexity of
arithmetic formulas from several aspects, e.g., how much the formula’s number
of variables increased in the test domain (setting of 4) compared to the
training domain (setting of 1 and 2). Specifically, we focused on the increase
of the number of variables ($\Delta$#variables), numbers ($\Delta$#numbers),
operations ($\Delta$#operations), and references ($\Delta$#references) from
the training to test domains. Here, “#reference” denotes the number of access
to a particular variable on the right-hand of equations. For example, the
$\Delta$#references is 1 if the training data format is A=$n$,B=A+$m$ and the
test format is A=$n$,B=A+$m$,C=B+$l$. Then, we identified which dimension
strongly relates to the compositional generalization difficulty.

We analyzed the macro trends between formula’s complexity increase and the
difficulty of generalization across the experimental settings. Table 3 shows
Spearman’s rank correlation coefficient between each complexity and the test-
domain accuracy. We found a notable negative correlation in the
$\Delta$#reference; that is, the more references in the test domain compared
to the training domain, the more difficult the compositional generalization
becomes (the cases of 1,2,6$\rightarrow$9 and 9$\rightarrow$10 settings).
Simply put, this reveals the difficulty of compositional generalization with
multi-hop reasoning—retaining the results of a calculation and accessing them
again for another calculation.

##  6 Related work

The analysis of the compositional generalization ability of neural models and
arithmetic multi-hop reasoning problems have typically been studied
separately; this study has merged these two directions. As for composition
generalization analysis, several studies analyzed neural models using datasets
such as SCAN Lake and Baroni (2018), COGS Kim and Linzen (2020), and CFQ
Keysers et al. (2020). These mainly focused on compositionality in the context
of semantic parsing; the composition ability toward symbol manipulations
(e.g., multi-hop arithmetic reasoning) is typically out of focus. As for
arithmetic reasoning, neural models’ abilities have been analyzed typically
using benchmarks such as DROP Dua et al. (2019). It has recently been reported
that such dataset has superficial cues Al-Negheimish et al. (2021), which made
it unclear how much arithmetic reasoning neural model achieves; our study
using a carefully controlled dataset contributed to the exact weakness of
neural models in this context.

##  7 Conclusion

In this study, we have empirically investigated the arithmetic multi-hop
reasoning ability of modern neural models through the lens of compositional
generalization ability. To systematically analyze neural models’ ability, we
have defined a skill tree that organizes the (hierarchical) complexity levels
of the multi-hop symbolic reasoning dataset.

Our experiments have revealed that the major weakness lies in systematicity,
even with a relatively simple composition. Through the ablation studies, we
also have found that difficulty in systematicity is pronounced in accessing
knowledge that is not written in input but stored in models. Furthermore, even
in training models with intermediate steps that explicate the composition,
they struggle to capture systematicity. We also found the difficulty of multi-
hop reasoning in compositional generalization. These highlight the exact
weakness of neural models and encourage studies to overcome such limitations.

## Limitations

In this work, we explored neural networks’ ability to capture compositionality
in symbolic arithmetic reasoning in hopes that it may lead to future
improvements in more general reasoning. However, arithmetic reasoning may not
necessarily generalize to natural language tasks. Furthermore, we explored
several aspects of multi-hop arithmetic reasoning, but these were chosen from
a relatively human-centric perspective, and models may suffer from unforeseen
other difficulties. Finally, while we found several patterns in how model
performance degrades, it is difficult to aggregate this into a full picture of
what a model can and cannot do. Further experiments are needed to gain a more
complete understanding of model performance

## Acknowledgements

We thank four anonymous reviewers who provided valuable feedback. We would
like to also appreciate the member of Tohoku NLP Group for their cooperation
in conducting this research. This work was supported by JST CREST JPMJCR20D2
and JSPS KAKENHI Grant Number JP22H00524，21K21343.

## References

  * Al-Negheimish et al. (2021) Hadeel Al-Negheimish, Pranava Madhyastha, and Alessandra Russo. 2021.  Numerical reasoning in machine reading comprehension tasks: are we there yet? In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 9643–9649, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y. Zhao, Yanping Huang, Andrew M. Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. 2022.  Scaling instruction-finetuned language models.  _CoRR_ , abs/2210.11416.
  * Clark et al. (2020) Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2020.  Transformers as soft reasoners over language.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , pages 3882–3890. International Joint Conferences on Artificial Intelligence Organization.  Main track.
  * d’Avila Garcez and Lamb (2020) Artur S. d’Avila Garcez and Luís C. Lamb. 2020.  Neurosymbolic AI: the 3rd wave.  _CoRR_ , abs/2012.05876.
  * Dua et al. (2019) Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. 2019.  DROP: A reading comprehension benchmark requiring discrete reasoning over paragraphs.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 2368–2378, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Geva et al. (2020) Mor Geva, Ankit Gupta, and Jonathan Berant. 2020.  Injecting numerical reasoning skills into language models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 946–958, Online. Association for Computational Linguistics.
  * Hupkes et al. (2020) Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. 2020.  Compositionality decomposed: How do neural networks generalise? (extended abstract).  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , pages 5065–5069. International Joint Conferences on Artificial Intelligence Organization.  Journal track.
  * Keysers et al. (2020) Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. 2020.  Measuring compositional generalization: A comprehensive method on realistic data.  In _International Conference on Learning Representations_.
  * Kim and Linzen (2020) Najoung Kim and Tal Linzen. 2020.  COGS: A compositional generalization challenge based on semantic interpretation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9087–9105, Online. Association for Computational Linguistics.
  * Lake and Baroni (2018) Brenden M. Lake and Marco Baroni. 2018.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _ICML_.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Marcus (2003) Gary F Marcus. 2003.  _The algebraic mind: Integrating connectionism and cognitive science_.  MIT press.
  * Pal and Baral (2021) Kuntal Kumar Pal and Chitta Baral. 2021.  Investigating numeracy learning ability of a text-to-text transfer model.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 3095–3101, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Qian et al. (2022) Jing Qian, Hong Wang, Zekun Li, Shiyang Li, and Xifeng Yan. 2022.  Limitations of language models in arithmetic and symbolic induction.  _CoRR_ , abs/2208.05051.
  * Rae et al. (2021) Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, H. Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant M. Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d’Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew J. Johnson, Blake A. Hechtman, Laura Weidinger, Iason Gabriel, William S. Isaac, Edward Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving. 2021.  Scaling language models: Methods, analysis & insights from training gopher.  _CoRR_ , abs/2112.11446.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Shazeer and Stern (2018) Noam Shazeer and Mitchell Stern. 2018.  Adafactor: Adaptive learning rates with sublinear memory cost.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 4603–4611. PMLR.
  * Talmor et al. (2020) Alon Talmor, Yanai Elazar, Yoav Goldberg, and Jonathan Berant. 2020.  oLMpics-on what language model pre-training captures.  _Transactions of the Association for Computational Linguistics_ , 8:743–758.
  * Tondello and Nacke (2019) Gustavo F. Tondello and Lennart E. Nacke. 2019.  A pilot study of a digital skill tree in gameful education.  In _Proceedings of the 3rd International Symposium on Gamification and Games for Learning - GamiLearn ’19_. CEUR-WS.org, CEUR-WS.org.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022.  Chain of thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_.
  * Yang et al. (2021) Peng-Jian Yang, Ying-Ting Chen, Yuechan Chen, and Daniel Cer. 2021.  Nt5?! training T5 to perform numerical reasoning.  _CoRR_ , abs/2104.07307.

##  Appendix A Training configurations

#### Training data:

Data of primitive domains (grey domains in Figure 2) are also added to the
training data. Specifically, data in the primitive domains that are reached by
traversing the graph (Figure 2) from the training domain to the left is added.
For example, when the training domain has the domain of 7, the data of
primitive domains of 2, 3, and 6 are added333Task 7,8$\rightarrow$10 do not
incorporate data from the primitive domains into the training data to evaluate
if compositional generalization can be achieved solely from complex
components.. Note that when the domain of 3 is included, the domain of 1 is
not added. Additionally, as the objective of this study does not emphasize the
generalization performance in arithmetic ability, the scope of numbers
utilized in the test domain is adjusted to ensure that the upper limit of the
answers in the test domain does not surpass that of the answers in the train
domain.

#### Hyperparameter:

We used the T5 models (v1.1) as pre-trained
model444https://huggingface.co/docs/transformers/model_doc/t5v1.1. We used
three model sizes: base (250 million parameters), large (800 million
parameters), and xl (3 billion parameters). Following T5 Raffel et al. (2020)
fine-tuning configurations, we use Adafactor Shazeer and Stern (2018) as the
optimizer with a constant learning rate. Also, we specify the learning rate
$1.0\times 10^{-5}$ for training and $5.0\times 10^{-5}$ in measuring the WA.
The batch size is 32 for all experimental settings. We trained each model on
NVIDIA A6000 (48GB memory), A100 (80GB memory). In addition, following
previous research about numerical reasoning Geva et al. (2020), we tokenize
numbers in a digit-by-digit manner.

|  | base | large
---|---|---|---
Task | Type | ZA | WA | ZA | WA
1,2 | sys. | 25.5 | 71.2 | 33.8 | 61.0
$\rightarrow$4 | +subst. | 25.2 | 72.4 | 30.9 | 62.0
2,3 | sys. | 23.0 | 48.7 | 25.4 | 49.1
$\rightarrow$5 | +subst. | 22.1 | 47.5 | 25.7 | 43.5
2,3,6 | sys. | 29.6 | 57.6 | 35.0 | 55.1
$\rightarrow$8 | +subst. | 28.7 | 50.4 | 34.3 | 50.2
2,3,6 | sys. | 36.7 | 59.8 | 40.4 | 48.5
$\rightarrow$7 | +subst. | 39.4 | 57.0 | 38.6 | 39.3
1,2,6 | sys. | 22.0 | 26.1 | 21.1 | 16.1
$\rightarrow$9 | +subst. | 22.6 | 26.7 | 23.5 | 18.2
7,8 | sys. | 24.1 | 28.6 | 32.5 | 25.3
$\rightarrow$10 | +subst. | 24.9 | 27.7 | 34.9 | 29.3
1 | prod. | 92.4 | 99.8 | 100.0 | 83.1
$\rightarrow$3 | +subst. | 91.2 | 99.8 | 100.0 | 82.3
4 | prod. | 60.4 | 93.0 | 89.5 | 90.8
$\rightarrow$5 | +subst. | 63.8 | 95.9 | 91.8 | 87.4
9 | prod. | 33.5 | 49.4 | 41.6 | 21.0
$\rightarrow$10 | +subst. | 34.3 | 48.2 | 43.5 | 22.2
Table 4:  Experimental results when BART is used as a pre-trained model. The
“Task” column exhibits (train$\rightarrow$test) domains corresponding to the
skill-tree (Figure 2). The “Type” column shows the targeted compositionality
type in each setting; here, “sys.,” “prod,” and “subst.” denote the
systematicity, productivity, and substitutivity generalizations, respectively.

##  Appendix B How to calculate WA

As described in Section 3, we used weighted average accuracy (WA). This metric
quantifies the efficiency (ease) of generalization by assigning a high weight
to accuracy in the early training stage. Specifically, the weights $w_{i}$
(where $i$ is the number of validation steps) were calculated using the
following formulae:

$\displaystyle w_{i}$ $\displaystyle=-ai+w_{\mathrm{max}}\;\;,$ (1)
$\displaystyle w_{\mathrm{max}}$ $\displaystyle=\alpha w_{\mathrm{min}}\;\;,$
(2) $\displaystyle w_{\mathrm{min}}$
$\displaystyle=\frac{2}{(N+1)(\alpha+1)}\;\;,$ (3) $\displaystyle a$
$\displaystyle=\frac{(w_{\mathrm{max}}-w_{\mathrm{min}})}{N}\;\;.$ (4)

Here, $N$ is the number of validation steps. $\alpha$ is a hyperparameter that
determines how heavily the accuracy in the early stages is weighted. We set
$\alpha$ to 1000 in all the experiments. Also, We used the first 100
validation steps to calculate WA, so specify $N=100$ for all experiments. WA
was calculated with accuracy on the held-out validation datasets in the test
domain.

##  Appendix C Model variants

###  C.1 BART

To confirm the generality of our results obtained with the T5 models, we also
conduct the same experiment using BART Lewis et al. (2020). We use two model
sizes555https://huggingface.co/facebook/bart-base,
https://huggingface.co/facebook/bart-large: base (140 million parameters) and
large (400 million parameters). Table 4 shows the result using BART. The same
tendency described in Section 4 was observed when BART was used as a language-
pre-training model.

###  C.2 Training from scratch

We also experimented with the case where we started training from randomly
initialized parameters to isolate the effect of the pre-training adopted in
T5. We found that these initialized models failed to learn even primitive
operations and in-domain tasks (Table 5), at least with the hyperparameter
setting666Unlike in the training domain used for the language pre-trained
model, we relax the training stopping criterion. We stopped training when the
accuracy did not increase by 10 epochs in the validation dataset. used in this
study. Thus, we did not proceed to their evaluation of compositionality
generalization.

Task | base | large | x-large
---|---|---|---
1,2 ($\rightarrow$4) | 72.5 | 100.0 | 100.0
2,3 ($\rightarrow$5) | 63.3 | 56.1 | 99.9
1,3,6 ($\rightarrow$7, 8) | 68.6 | 67.9 | 67.5
1,2,6 ($\rightarrow$9) | 99.9 | 76.0 | 76.8
7,8 ($\rightarrow$10) | 48.6 | 37.3 | 24.0
1 ($\rightarrow$3) | 51.1 | 15.1 | 16.3
4 ($\rightarrow$5) | 100.0 | 99.9 | 99.9
9 ($\rightarrow$10) | 99.7 | 99.9 | 99.7
Table 5:  Accuracy on the training held-out dataset when we start training the
model from randomly initialized parameters. (When training began with
parameters pre-trained on language, the accuracy was almost 100% in all
settings.) Each training task includes the primitive operations required to
solve train domain tasks as described in section A.

##  Appendix D Detailed analysis of T5-based models

Figure 3 shows the learning curves (accuracy on validation datasets) for all
tasks demonstrated in Table 1. The graphs also show that the neural language
model struggles to solve tasks that require compositional generalization in
the beginning part of the training.

Figure 3: Learning curves of generalization test for all tasks. |  | base | large | x-large
---|---|---|---|---
Task | Type | ZA | WS | ZA | WS | ZA | WS
1,2 | sys. | 59.2 | 95.9 | 66.9 | 98.5 | 63.9 | 98.9
$\rightarrow 4$ | +subst. | 59.0 | 95.1 | 67.3 | 98.2 | 62.2 | 99.0
$2,3$ | sys. | 37.3 | 94.1 | 66.1 | 98.4 | 86.9 | 99.3
$\rightarrow 5$ | +subst. | 35.9 | 93.5 | 65.2 | 98.6 | 84.2 | 99.0
2,3,6 | sys. | 59.6 | 93.9 | 71.5 | 98.0 | 52.5 | 97.2
$\rightarrow$8 | +subst. | 56.3 | 92.8 | 67.1 | 98.0 | 52.3 | 97.0
2,3,6 | sys. | 34.3 | 91.0 | 46.3 | 93.6 | 32.0 | 95.7
$\rightarrow$7 | +subst. | 34.3 | 91.3 | 48.1 | 93.6 | 34.2 | 96.5
1,2,6 | sys. | 13.2 | 34.3 | 11.6 | 38.1 | 12.3 | 59.6
$\rightarrow$9 | +subst. | 12.7 | 34.9 | 13.0 | 39.0 | 12.4 | 58.8
7,8 | sys. | 26.2 | 61.1 | 20.0 | 61.7 | 21.3 | 67.4
$\rightarrow$10 | +subst. | 26.4 | 61.4 | 19.9 | 60.0 | 20.5 | 68.5
1 | prod. | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0
$\rightarrow$3 | +subst. | 100.0 | 100.0 | 100.0 | 100.0 | 99.9 | 100.0
4 | prod. | 100.0 | 100.0 | 99.9 | 100.0 | 100.0 | 100.0
$\rightarrow$5 | +subst. | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0
9 | prod. | 69.6 | 88.2 | 71.5 | 89.9 | 75.3 | 92.0
$\rightarrow$10 | +subst. | 67.4 | 88.8 | 72.0 | 89.6 | 75.2 | 92.0
Table 6:  Experiments result from string operation ablation. The “Task” column exhibits (train$\rightarrow$test) domains corresponding to the skill-tree (Figure 2). The “Type” column shows the targeted compositionality type in each setting; here, “sys.,” “prod,” and “subst.” denote the systematicity, productivity, and substitutivity generalizations, respectively.  |  | base | large | x-large
---|---|---|---|---
Task | Type | ZA | WS | ZA | WS | ZA | WS
1,2 | sys. | 30.6 | 81.3 | 33.9 | 85.5 | 35.6 | 94.9
$\rightarrow$4 | +subst. | 30.3 | 77.9 | 32.9 | 85.5 | 36.3 | 95.5
2,3 | sys. | 26.2 | 82.1 | 36.1 | 89.4 | 33.7 | 96.4
$\rightarrow$5 | +subst. | 25.4 | 81.3 | 36.1 | 88.1 | 32.9 | 96.4
2,3,6 | sys. | 0.0 | 27.6 | 0.0 | 47.5 | 0.0 | 71.3
$\rightarrow$8 | +subst. | 0.0 | 26.0 | 0.0 | 47.3 | 0.0 | 72.9
2,3,6 | sys. | 0.0 | 43.1 | 0.0 | 59.0 | 0.0 | 75.0
$\rightarrow$7 | +subst. | 0.0 | 40.0 | 0.0 | 56.6 | 0.0 | 73.3
1,2,6 | sys. | 0.0 | 0.2 | 0.0 | 2.5 | 0.0 | 14.3
$\rightarrow$9 | +subst. | 0.0 | 0.1 | 0.0 | 2.7 | 0.0 | 16.4
7,8 | sys. | 0.0 | 17.0 | 0.0 | 33.2 | 0.0 | 55.1
$\rightarrow$10 | +subst. | 0.0 | 17.4 | 0.0 | 32.6 | 0.0 | 55.3
1 | prod. | 100.0 | 100.0 | 100.0 | 100.0 | 96.0 | 99.9
$\rightarrow$3 | +subst. | 100.0 | 100.0 | 100.0 | 100.0 | 95.8 | 99.9
4 | prod. | 100.0 | 100.0 | 100.0 | 99.9 | 100.0 | 99.9
$\rightarrow$5 | +subst. | 100.0 | 100.0 | 100.0 | 99.9 | 100.0 | 99.9
9 | prod. | 0.0 | 50.8 | 0.0 | 72.2 | 0.0 | 80.9
$\rightarrow$10 | +subst. | 0.0 | 51.8 | 0.0 | 69.5 | 0.0 | 79.3
Table 7:  Experiments result from scratchpad ablation. The “Task” column
exhibits (train$\rightarrow$test) domains corresponding to the skill-tree
(Figure 2). The “Type” column shows the targeted compositionality type in each
setting; here, “sys.,” “prod,” and “subst.” denote the systematicity,
productivity, and substitutivity generalizations, respectively.

###  D.1 String operations ablation for all tasks

Table 6 shows the experimental results of the ablation study using string
operations for all tasks.

###  D.2 Scratch pad evaluation for all tasks

Table 7 shows the experimental results of the ablation study using scratchpad
for all tasks.

##  Appendix E Dataset details

Domains | Required premitives | Targeted composition
---|---|---
Task | Example | Assign. | Arith. | Ref. | Sys. | Prod. | Subst.
1 | A=1, B=2, B=? | ✓ |  |  |  |  |
2 | A=1+2, A=? | ✓ | ✓ |  |  |  |
3 | A=1, B=2, C=3, C=? | ✓ |  |  |  | ✓ |
3’ | α=1, β=2, γ=3, γ=? | ✓ |  |  |  | ✓ | ✓
4 | A=1+2, B=2+3, B=? | ✓ | ✓ |  | ✓ |  |
4’ | α=1+2, β=2+3, β=? | ✓ | ✓ |  |  | ✓
---
| ✓
5 | A=1+2, B=2+3, C=3+4, C=? | ✓ | ✓ |  |  | ✓
---
✓ |
5’ | α=1+2, β=2+3, γ=3+4, γ=? | ✓ | ✓ |  |  | ✓
---
✓ | ✓
6 | A=1, B=A, B=? | ✓ |  | ✓ |  |  |
7 | A=1, B=2, C=B+3, C=? | ✓ | ✓ | ✓ |  | ✓
---
|
7’ | α=1, β=2, γ=β+3, γ=? | ✓ | ✓ | ✓ |  | ✓
---
| ✓
8 | A=1+2, B=2+3, C=B, C=? | ✓ | ✓ | ✓ |  | ✓
---
|
8’ | α=1+2, β=2+3, γ=β, γ=? | ✓ | ✓ | ✓ |  | ✓
---
| ✓
9 | A=1+2, B=A+3, B=? | ✓ | ✓ | ✓ | ✓ |  |
9’ | α=1+2, β=α+3, β=? | ✓ | ✓ | ✓ | ✓ |  | ✓
10 | A=1+2, B=A+3, C=B+4, C=? | ✓ | ✓ | ✓ | ✓ | ✓ |
10’ | α=1+2, β=α+3, γ=β+4, γ=? | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Table 8:  Dataset configurations. The “Task” column exhibits (train$\rightarrow$test) domains corresponding to the skill-tree (Figure 2). “Assign.” “Arith.” and “Ref.” in “Required primitives” column mean primitive operations name, “assignment” “arithmetic operations” and “reference” (see subsection 2.2) The “Target composition” column shows the targeted compositionality type in each setting; here, “Sys.,” “Prod,” and “Subst.” denote the systematicity, productivity, and substitutivity generalizations, respectively.  |  Description |  Example
---|---|---
join |  String concatenation. |  12 + 34 = 1234
reverseJoin |  String concatenation + Reverse |  123 ^ 78 = 87321
strSub |  Deletion of duplicate characters. Return 0 if there are no duplicates. |  7873 - 73 = 87
stackJoin |  Select one character from the left side of each string alternately and return the combined string. |  12 * 34 = 1324
Table 9:  Detail of string operation.

Table 8 summarizes the characteristics of each task.

###  E.1 String operations

Table 9 shows the details of the string operations.

###  E.2 Scratch pad formulation

For the additional study using scratchpad in section 4, we generate problems
with ing the intermediate steps. Scratchpad is in the form of straightforward
one-by-one calculations of only those calculations necessary to find the
target variable. The following is an example of scratchpad reasoning:
_Question:_ A=1+2, B=A+3, B=?
_Answer:_ A=1+2;A=3;B=A+3;B=3+3;B=6