$\mathcal{W}$, characterized by $\mathbf{n}\in\mathcal{W}_{i}\Leftrightarrow
n_{i}=n_{i+1}$. Then (8.2.1) is immediate from (8.1). Hence we may assume that
$d\geq 2$ and work in our usual framework using $d$-diagrams.

  2. (ii)

We will show more precisely: The map

(8.2.2) $\displaystyle\delta\colon\operatorname{diag}^{(d)}(\mathbf{n})$
$\displaystyle\longrightarrow\operatorname{diag}^{(d)}(\mathbf{n}\hat{})$
$\displaystyle(i,v)$ $\displaystyle\longmapsto(r+1-i,n_{1}+d-1-v)$

is well-defined and bijective, and sends

(8.2.3) $B_{k}^{(d)}(\mathbf{n})\text{ to
}B_{rd+1-k}^{(d)}(\mathbf{n}\hat{}).$

  3. (iii)

As both sets $\operatorname{diag}^{(d)}(\mathbf{n})$ and
$\operatorname{diag}^{(d)}(\mathbf{n}\hat{})$ have the same cardinality, it
suffices for (8.2.2) to show that $\delta$ is well-defined and satisfies
$\delta^{2}=\operatorname{id}$. Now

$\displaystyle(i,v)\in\operatorname{diag}^{(d)}(\mathbf{n})\Longleftrightarrow
n_{i}\leq v<n_{i}+d$ $\displaystyle(1\leq i<r)$

and, after a little calculation, this turns out to be equivalent with

$\mathbf{n}\hat{}_{r+1-i}\leq n_{1}+d-1-v<\mathbf{n}\hat{}_{r+1-i}+d$

for all $i$, that is, $\delta$ maps in fact to
$\operatorname{diag}^{(d)}(\mathbf{n}\hat{})$. The equation $\delta^{2}=1$ is
trivial.

  4. (iv)

Recall the order relation “$\leq$” on $\operatorname{diag}^{(d)}(\mathbf{n})$
given by (4.1.1). It is obvious from the definition of $\delta$ that it
reverses this order, which gives (8.2.3).

∎

### 8.3.

Coming back to the arithmetic significance of
$\mathcal{BT}(d,k)=\mathcal{BT}({}_{a}\ell_{k})=\lambda(\Omega({}_{a}\ell_{k}))$,
where $a\in A=\mathds{F}[T]$ has degree $d$, we find the following
relationship. Let $a\in A$ of degree $d$ be given, and consider for $1\leq
k<rd$ the modular forms ${}_{a}\ell_{k}$. Then the zero sets
$\Omega({}_{a}\ell_{k})$ of ${}_{a}\ell_{k}$ and $\Omega({}_{a}\ell_{rd-k})$
of ${}_{a}\ell_{rd-k}$ are related by

(8.3.1)
$\lambda(\Omega({}_{a}\ell_{k}))\hat{}=\lambda(\Omega({}_{a}\ell_{rd-k})).$

### 8.4.

Note that the considerations of this section also apply for $r=2$. Here
$\mathcal{BT}(d,k)=\mathcal{BT}^{2}(d,k)$ is a finite set of vertices of the
Bruhat-Tits tree $\mathcal{BT}=\mathcal{BT}^{2}$. The involution
$(\,.\,)\hat{}$ is trivial, and (8.2.1) resp. (8.3.1) degenerate to
$\mathcal{W}(d,k)=\mathcal{W}(d,k)\hat{}$ resp.
$\lambda(\Omega({}_{a}\ell_{k}))=\lambda(\Omega({}_{a}\ell_{2d-k}))$. This is
in accordance with the symmetry property in Theorem 5.1 of [Gekeler2011].

##  9\. Examples and concluding remarks

Note that our Theorems 5.17, 6.10, 7.4 and 8.2 along with Proposition 3.8
assert all the ingredients of the Main Theorem 1.8, which thereby is proved.
Here we present examples for the simplicial complexes $\mathcal{W}(d,k)$. For
reasons of presentation, we restrict to the case $r=3$, where
$\mathcal{W}(d,k)$ has dimension 1, i.e., is a graph embedded into
$\mathcal{W}=\mathcal{W}^{3}$ (see 3.2 and the legend given there).

######  Example 9.1 ($r=3$, the graphs $\mathcal{W}(2,k)$, $1\leq k\leq 5$):

$\mathcal{W}=\mathcal{W}^{3}$$\mathcal{W}_{1}=\mathcal{W}(2,5)$$\mathcal{W}_{2}=\mathcal{W}(2,1)$$\sigma$$x\hat{}$$x$$=\mathcal{W}(2,2)$$=\mathcal{W}(2,3)$$=\mathcal{W}(2,4)$

Note that $\mathcal{W}(2,1)=\mathcal{W}(1)=$ the wall $\mathcal{W}_{2}$ and
$\mathcal{W}(2,2)$ have been drawn in [V] Figure 1. By symmetry, this gives
$\mathcal{W}(2,5)=\mathcal{W}(2,1)\hat{}=\mathcal{W}_{1}$ and
$\mathcal{W}(2,4)=\mathcal{W}(2,2)\hat{}$. Let $a\in A$ have degree 2, e.g.,
$a=T^{2}$. Then $f\vcentcolon={}_{a}\ell_{1}{}_{a}\ell_{2}{}_{a}\ell_{3}$ has
the property: The edges of the leftmost triangle $\sigma$ of $\mathcal{W}$
belong to $\mathcal{W}(f)$, while
$\overset{\circ}{\sigma}(\mathds{Q})\cap\mathcal{W}(f)=\varnothing$. Hence the
zero set $\mathcal{W}(f)$ is not a full subcomplex of $\mathcal{W}$ and $f$ is
not simplicial. Examples of modular forms of this shape that are not
simplicial are abundant.

######  Example 9.2 ($r=3$, the graphs $\mathcal{W}(3,k)$, $k=3$ or $4$):

$\mathcal{W}=\mathcal{W}^{3}$$=\mathcal{W}(3,3)=\mathcal{W}(3)$$=\mathcal{W}(3,4)$

As $\mathcal{W}(3,k)=\mathcal{W}(k)$ for $k=1,2$ has been given in 9.1 and
$\mathcal{W}(3,k)\hat{}=\mathcal{W}(3,9-k)$, we may restrict to $k=3$ or $4$.

######  Example 9.3 ($r=3$, the graphs $\mathcal{W}(4,k)$, $k=4,5,6$):

$\mathcal{W}=\mathcal{W}^{3}$$=\mathcal{W}(4,4)=\mathcal{W}(4)$$=\mathcal{W}(4,5)$$=\mathcal{W}(4,6)$

As $\mathcal{W}(4,k)=\mathcal{W}(k)$ for $k=1,2,3$ is in 9.1 and 9.2 and
$\mathcal{W}(4,k)\hat{}=\mathcal{W}(4,12-k)$, we restrict to $k=4,5,6$. Note
that the graph $\mathcal{W}(4,6)$ has a non-trivial cycle.

######  Remark 9.4 (about the involution $(\,.\,)\hat{}$):

A very satisfactory explanation/interpretation of Theorem 8.2 would be given
by the existence of a lift of $(\,.\,)\hat{}$ to $\Omega$, i.e., an involution
$\boldsymbol{\omega}\mapsto\boldsymbol{\omega}\boldsymbol{\hat{}}$ on $\Omega$
such that

(9.4.1)
${\Omega}$${\Omega}$${\mathcal{BT}}$${\mathcal{BT}}$$\scriptstyle{\lambda}$$\scriptstyle{(\,.\,)\boldsymbol{\hat{}}}$$\scriptstyle{\lambda}$$\scriptstyle{(\,.\,)\hat{}}$

commutes. In view of (8.1), a natural candidate for
$(\,.\,)\boldsymbol{\hat{}}$ would be the map

(9.4.2)
$\boldsymbol{\omega}=(\omega_{1},\dots,\omega_{r-1},1)\longmapsto\left(\omega_{1},\frac{\omega_{1}}{\omega_{r-1}},\dots,\frac{\omega_{1}}{\omega_{2}},1\right).$

This however fails for a number of reasons. First, and most important,
$\Omega$ is not stable under the map described in (9.4.2) (I owe this hint to
Andreas Schweizer). Second, a reasonable lift $(\,.\,)\boldsymbol{\hat{}}$ as
in (9.4.1) had to interchange the zeroes of ${}_{a}\ell_{k}$ with those of
${}_{a}\ell_{rd-k}$, which however is excluded for “weight reasons”.

Let ${}_{d}L_{k}$ be the $\mathds{Q}$-valued function on
$\mathcal{BT}(\mathds{Q})$ given by

(9.4.3)
${}_{d}L_{k}(\boldsymbol{x})\vcentcolon=\log_{q}\lVert{}_{a}\ell_{k}\rVert_{\mathbf{x}},$

where $\lVert f\rVert_{\boldsymbol{x}}$ is the spectral norm
$\sup_{\boldsymbol{\omega}\in\lambda^{-1}(\boldsymbol{x})}\lvert
f(\boldsymbol{x})\rvert$ on the affinoid $\lambda^{-1}(\boldsymbol{x})$ (see
[I], [II], [IV]). (Actually, $\lVert{}_{a}\ell_{k}\rVert_{\boldsymbol{x}}$
depends only on $d=\deg a$, see [V] Proposition 3.8.) Now, as ${}_{a}\ell_{k}$
has turned out to be simplicial, ${}_{d}L_{k}$ encodes the zero set
$\mathcal{BT}({}_{a}\ell_{k})=\mathcal{BT}(d,k)$, see Proposition 1.8 in [V].
Therefore, as a substitute for some diagram (9.4.1), we expect(?) a simple
relation between ${}_{d}L_{k}\hat{}$ and ${}_{d}L_{rd-k}$ or perhaps between
the van der Put transforms $P({}_{a}\ell_{k})\hat{}$ and
$P({}_{a}\ell_{rd-k})$ (see [V] Section 1) that implies Theorem 8.2.

### 9.5.

Similar to $\mathcal{BT}(d,k)$, which presents a coarse picture of the zero
locus $\Omega({}_{a}\ell_{k})$ of ${}_{a}\ell_{k}$ in $\Omega$, the object
$\Gamma\backslash\mathcal{BT}(d,k)$ may be seen as a coarse picture of the
quotient

${\Gamma\backslash\Omega({}_{a}\ell_{k})}$${\Gamma\backslash\Omega}$${M^{r}({}_{a}\ell_{k})}$${M^{r}.}$$\scriptstyle{\cong}$$\scriptstyle{\cong}$

Here $M^{r}$ is (the set of $C_{\infty}$-points of) the moduli scheme of
rank-$r$ Drinfeld $A$-modules. Now, despite the fact that $\Gamma$ acts
simplicially on $\mathcal{BT}$ and its subcomplex $\mathcal{BT}(d,k)$, the
quotient modulo $\Gamma$ doesn’t inherit a structure as a simplicial complex.
This comes from the (well-known but annoying) fact that, e.g. in the case of
dimension 1, endpoints of $1$-simplices $\sigma,\tau$ are possibly identified
under $\Gamma$, but $\sigma$ and $\tau$ are not. This leads to double edges

$[\sigma]$$[\tau]$

and similar phenomena in $\Gamma\backslash\mathcal{BT}$. Hence the topological
space $\Gamma\backslash\mathcal{BT}(d,k)(\mathds{R})$ has only the weaker
structure of cell complex. Nevertheless, the next topics to deal with should
be:

  * •

Study the spaces $\Gamma\backslash\mathcal{BT}(d,k)(\mathds{R})$, the natural
map
$\mathcal{W}(d,k)(\mathds{R})\to\Gamma\backslash\mathcal{BT}(d,k)(\mathds{R})$,
their Betti numbers, etc.;

  * •

Work out the relationship between, say, the $\ell$-adic cohomology of the
moduli scheme $M({}_{a}\ell_{k})$ and the (co-)homology of
$\Gamma\backslash\mathcal{BT}(d,k)(\mathds{R})$;

  * •

Instead of the zero sets of one modular form ${}_{a}\ell_{k}$ in $\Omega$,
$\mathcal{BT}$, $\Gamma\backslash\mathcal{BT}$, study the simultaneous zero
sets of families of modular forms in $\Omega$, $\mathcal{BT}$ and their
quotients modulo $\Gamma$, or modulo congruence subgroups $\Gamma^{\prime}$ of
$\Gamma$. For the relatively simple case of the family $\\{g_{k}\mid 1\leq
k<r,k\neq j\\}$ where $j$ is fixed, see [Gekeler2019].

### 9.6.

As the reader will have noticed, $q=\\#(\mathds{F})$ has completely vanished
from the largest part of the paper. This is due to the fact that we mainly
worked with $\mathcal{A}$ and $\mathcal{W}$ and the combinatorics of its
subcomplexes. These are independent of $q$ and are entirely determined through
the root system $\Phi$ and its Weyl group $W$. The quantity $q$ occurs only in
the way how the different apartments $\mathcal{A}^{\prime}\cong\mathcal{A}$
are glued together, i.e., how many neighbors
$v^{\prime}\in\mathcal{BT}(\mathds{Z})$ there are for a given vertex
$v=\mathbf{n}$ in $\mathcal{A}$. Therefore, the simplicial complexes
$\mathcal{A}(k)$, $\mathcal{A}(d,k)$, $\mathcal{BT}(k)$, $\mathcal{BT}(d,k)$
are fundamental structures for $\Phi$, and should play a role beyond their
describing the zero sets of the Drinfeld modular forms ${}_{a}\ell_{k}$.

## References


# Bijective proof of a conjecture on unit interval posets

Wenjie Fang
LIGM, Univ Gustave Eiffel, CNRS, ESIEE Paris, F-77454 Marne-la-Vallée, France

###### Abstract

In a recent preprint, Matherne, Morales and Selover conjectured that two
different representations of unit interval posets are related by the famous
zeta map in $q,t$-Catalan combinatorics. This conjecture was proved recently
by Gélinas, Segovia and Thomas using induction. In this short note, we provide
a bijective proof of the same conjecture with a reformulation of the zeta map
using left-aligned colored trees, first proposed in the study of parabolic
Tamari lattices.

##  1 Introduction

The study of unit interval posets started in statistics (see [WF57]) and
psychology (see [Sco64]). However, it has since been connected to other
objects in algebraic combinatorics, such as $(3+1)$-free posets [SR03] and
positroids [CG18]. The connection to $(3+1)$-free posets is particularly
important, as these posets are at the center of the Stanley-Stembridge
conjecture [SS93], which states that the chromatic symmetric function of the
incomparability graph of a $(3+1)$-free poset has only positive coefficients
when expanded in the basis of elementary symmetric functions. Unit interval
posets thus receive some attention as it can be used to study the structure of
$(3+1)$-free posets [SR03, GPMR14].

It is known that unit interval posets are counted by Catalan numbers [WF57],
and researchers have given two different bijections to represent a unit
interval poset by Dyck paths [SR03, GPMR14]. In a recent preprint of Matherne,
Morales and Selover [MMS], it was conjectured that the two bijections are
related by the famous zeta map in $q,t$-Catalan combinatorics (see [Hag08]),
which was first given in [AKOP02]. In this short note, we settle this
conjecture using bijections (see 4.6), in contrast to a recent inductive proof
of the same conjecture by Gélinas, Segovia and Thomas [GST]. To this end, we
first introduce a bijection $\Xi_{\mathrm{poset}}$ between unit interval
posets and plane trees. We then show that the two different known bijections
from unit interval posets are conjugates of special cases of some bijections
$\Xi_{\mathrm{steep}}$ and $\Xi_{\mathrm{bounce}}$ in [CFM20] constructed for
the study of parabolic Tamari lattices. Using the link between
$\Xi_{\mathrm{steep}},\Xi_{\mathrm{bounce}}$ and the zeta map also established
in the same article, we conclude our proof.

The rest of the article is organized as follows. In Section 2 we give the
basic definitions. Then we give our bijection between unit interval posets and
plane trees in Section 3, along with the related bijections in [CFM20].
Finally in Section 4 we recall the two known bijections between unit interval
posets and Dyck paths and establish their link with the bijections in Section
3, leading to a bijective proof of our main result (4.6).

### Acknowledgment

We thank Adrien Segovia for bringing this conjecture to our attention. This
work is not supported by any funding with precise predefined goal, but it is
supported by the publicly funded laboratory LIGM of Université Gustave Eiffel.

##  2 Preliminary

For convenience, we write $[n]$ for the set $\\{1,2,\ldots,n\\}$. We consider
finite partially order sets (or _poset_ for short) of the form
$P=(P_{\mathrm{elem}},\preceq)$, where $P_{\mathrm{elem}}$ is a finite set and
$\preceq$ a partial order on $P_{\mathrm{elem}}$. Given a set $S$ of reals
$x_{1}<x_{2}<\cdots<x_{n}$, we define a partial order $\preceq_{S}$ on $[n]$
by taking $i\preceq_{S}j$ if and only if $x_{i}+1<x_{j}$. The order
$\preceq_{S}$ can also be seen as defined on intervals of unit length starting
at the $x_{i}$’s, where $i\preceq_{S}j$ if the interval starting with $x_{i}$
is on the left of that with $x_{j}$ without overlap. A poset $P$ with $n$
elements is a _unit interval order_ if there is some $S\subset\mathbb{R}$ with
$n$ elements such $P\cong([n],\preceq_{S})$. In this case, we call $S$ a
_starting set_ of $P$. We sometimes represent unit interval orders as
$([n],\preceq_{S})$ for some $S$ hereinafter.

We have the following characterization of unit interval orders.

######  Theorem 2.1 (Theorem 2.1 of [Sco64]).

A poset $P$ is a unit interval poset if and only if it is $(3+1)$-free and
$(2+2)$-free, that is, the order induced on any four elements cannot be a
chain of $3$ elements plus an incomparable elements, or two disjoint chains
each containing $2$ elements.

Unit interval orders are counted by Catalan numbers.

######  Proposition 2.2 ([WF57]).

The number of unit interval posets with $n$ elements is the $n$-th Catalan
number $\mathrm{Cat}_{n}=\frac{1}{2n+1}\binom{2n+1}{n}$.

By definition, we may represent a unit interval poset $P$ by a set of reals
$S$, though the choice of $S$ is clearly not unique. In the following, for
convenience, we use this perspective of (starting points of) intervals, which
is arguably easier to manipulate. We denote by $\mathcal{P}_{n}$ the set of
unit interval posets with $n$ elements.

There are many other families of combinatorial objects counted by Catalan
numbers, such as Dyck paths and plane trees. A _Dyck path_ is a lattice path
formed by north steps $\uparrow=(0,1)$ and east steps $\rightarrow=(1,0)$,
starting at $(0,0)$ and ending on the diagonal $y=x$ while staying weakly
above it. The _size_ of a Dyck path is the number of its north steps. We
denote by $\mathcal{D}_{n}$ the set of Dyck paths of size $n$. We define plane
trees recursively: a _plane tree_ $T$ is either a single node (a _leaf_) or an
_internal node_ $u$ linked by edges to a sequence of plane trees called _sub-
trees_. In the latter case, the node $u$ is also called the _root_ of $T$, and
the roots of sub-trees are called _children_ of $u$. We denote by
$\mathcal{T}_{n}$ the number of plane trees with $n$ non-root nodes. For a
node $u$ in a plane tree $T$, its _depth_ is the distance (number of edges)
between $u$ and the root of $T$.

##  3 Unit interval posets and plane trees

We start by a new bijection between unit interval posets and plane trees.

######  Construction 3.1.

Let $S=\\{x_{1}<\cdots<x_{n}\\}$ be a starting set of a unit interval poset
$P=([n],\preceq_{S})$. We define a plane tree $T$ as follows (see Figure 1 for
an example). We set $x_{0}=x_{1}-2$. We denote by $v_{i}$ the node of $T$
corresponding to $x_{i}$. For $i\in[n]$, the parent of $v_{i}$ is $v_{j}$ if
and only if $j$ is the largest index such that $j\preceq_{S}i$. By the
definition of $x_{0}$, the parent of each $v_{i}$ is well-defined, and all
nodes are descendants of $x_{0}$. We then order children of the same node from
left to right with _decreasing_ index. We thus conclude that $T$ is a well-
defined plane tree. We note that $T$ depends only on $\preceq_{S}$. We define
$\Lambda_{\mathrm{poset}}(P)=T$.

Figure 1: Example of $\Lambda_{\mathrm{poset}}$ from a unit interval poset
defined by a set of unit intervals to a plane tree

######  Construction 3.2.

Given a plane tree $T$ with $n$ non-root nodes, we define an order relation
$\preceq_{S}$ on $[n]$ induced by some $S\subset\mathbb{R}$. Let $m$ be the
maximal arity of $T$, and $r_{T}$ the root of $T$. Given a node $u$ in $T$, if
it is the $i$-th child of its parent _from right to left_ , then we define
$c(u)=i$. We observe that $0<c(u)<m$. For a non-root node $u$ in $T$, let
$u_{0}=r_{T},u_{1},\ldots,u_{\ell}=u$ be the nodes on the unique path from the
root $u_{0}=r_{T}$ to $u_{\ell}=u$. We then define a real number $x_{u}$
associated to $u$ using base $(m+2)$:

$x_{u}=\ell+(0.c(u_{1})c(u_{2})\cdots
c(u_{\ell}))_{(m+2)}=\ell+\sum_{i=1}^{\ell}c(u_{i})(m+2)^{-i}.$ (1)

It is clear from (1) that $x_{u}$ is strictly decreasing from left to right
for nodes of the same depth in $T$. Let $S$ be the set of $x_{u}$ for non-root
nodes $u$ in $T$. We define $\Xi_{\mathrm{poset}}(T)=([n],\preceq_{S})$.

The following lemma gives a direct connection between a plane tree and its
corresponding unit interval poset obtained from $\Xi_{\mathrm{poset}}$.

######  Lemma 3.3.

For $T\in\mathcal{T}_{n}$, we take $S$ to be the set constructed in 3.2, and
$x_{u}$ the number constructed from a non-root node $u$ of $T$. Then for non-
root nodes $u,v$, the parent of $u$ in $T$ is $v$ if and only if $x_{v}$ is
the largest element in $S$ smaller than $1+x_{u}$.

###### Proof.

Suppose that $T$ has maximal arity $m$. Let $v^{\prime}$ be the parent of $u$.
By (1), we have $1<x_{u}-x_{v^{\prime}}<1+(m+2)^{-\ell+1}$, with $\ell$ the
distance from $v^{\prime}$ to the root. Then, $x_{v}$ satisfying
$x_{v^{\prime}}<x_{v}<1+x_{u}$ means $0<x_{v}-x_{v^{\prime}}<(m+2)^{-\ell+1}$,
which means $v=v^{\prime}$ by (1), as it requires $v$ and $v^{\prime}$ to have
the same distance to the root, but in this case $|x_{v}-x_{v^{\prime}}|$
cannot be smaller than $(m+2)^{-\ell+1}$ if $v\neq v^{\prime}$. We thus have
the equivalence. ∎

We now show that $\Lambda_{\mathrm{poset}}$ and $\Xi_{\mathrm{poset}}$ are
bijections.

######  Proposition 3.4.

For all $n\geq 1$, the map $\Lambda_{\mathrm{poset}}$ is a bijection from
$\mathcal{P}_{n}$ to $\mathcal{T}_{n}$, with $\Xi_{\mathrm{poset}}$ its
inverse.

###### Proof.

It is well-known that there are $\mathrm{Cat}_{n}$ elements in
$\mathcal{T}_{n}$. By 2.2, we have $|\mathcal{P}_{n}|=|\mathcal{T}_{n}|$. We
thus only need to show that
$\Lambda_{\mathrm{poset}}\circ\Xi_{\mathrm{poset}}=\operatorname{id}$.

Given a plane tree $T\in\mathcal{T}_{n}$, let
$P=([n],\preceq_{S})=\Xi_{\mathrm{poset}}(T)$ and
$T^{\prime}=\Lambda_{\mathrm{poset}}(P)$. Let $S=\\{x_{1}<\cdots<x_{n}\\}$ be
the set of real numbers constructed in 3.2 for $\preceq_{S}$. Given $i\in[n]$,
let $u_{i}$ be the node in $T$ that gives rise to $x_{i}$ in $S$, and
$u^{\prime}_{i}$ the node in $T^{\prime}$ that represents $x_{i}$. By 3.3 and
3.1, for any $i,j\in[n]$, the node $u_{i}$ is the parent of $u_{j}$ in $T$ if
and only if $u^{\prime}_{i}$ is the parent of $u^{\prime}_{j}$ in
$T^{\prime}$. Then, $T^{\prime}$ has the same order of siblings as $T$, as in
both we order siblings with decreasing order in their corresponding reals in
$S$. We thus conclude that $T=T^{\prime}$. ∎

We now restate two previously known bijections between plane trees and Dyck
paths that will be used to prove our main result.

######  Construction 3.5.

Let $n\geq 1$ and $T\in\mathcal{T}_{n}$, we construct a Dyck path $D$ by
taking the _clockwise_ contour walk starting from the top of the root of $T$.
During the walk, when we pass an edge for the first (resp. second) time, we
append $\uparrow$ (resp. $\rightarrow$) to $D$. We define
$\Xi_{\mathrm{steep}}(T)=D$. The map $\Xi_{\mathrm{steep}}$ is a bijection
from $\mathcal{T}_{n}$ to $\mathcal{D}_{n}$ for all $n\geq 1$, and we denote
its inverse by $\Lambda_{\mathrm{steep}}$.

######  Construction 3.6.

Let $n\geq 1$ and $T\in\mathcal{T}_{n}$, we construct a Dyck path $D$ by
appointing the number of north steps at each $x$-coordinate. Let
$\alpha_{\ell}$ be the number of nodes of depth $\ell$ (thus distance $\ell$
to the root), and $\ell_{\max}$ the maximal depth of nodes in $T$. We take
$s_{\ell}=\alpha_{1}+\cdots+\alpha_{\ell}$. Given $1\leq k\leq n-1$, there is
a unique way to write $k=s_{\ell}-r$ with $0\leq r<\alpha_{\ell}$ and
$1\leq\ell\leq\ell_{\max}$. In this case, the number of north steps in $D$ on
$x=k$ is the number of children of the $(r+1)$-st node of depth $\ell$. The
number of north steps in $D$ on $x=0$ is the number of children of the root.
We define $\Xi_{\mathrm{bounce}}(T)=D$. The map $\Xi_{\mathrm{bounce}}$ is a
bijection from $\mathcal{T}_{n}$ to $\mathcal{D}_{n}$ for all $n\geq 1$ (see
Lemma 3.18 in [CFM20]), and we denote its inverse by
$\Lambda_{\mathrm{bounce}}=\Xi_{\mathrm{bounce}}^{-1}$.

######  Proposition 3.7 (Theorem IV of [CFM20]).

Let $\zeta$ be the zeta map from $\mathcal{D}_{n}$ to $\mathcal{D}_{n}$ with
$n\geq 1$. We have $\zeta=\Xi_{\mathrm{bounce}}\circ\Lambda_{\mathrm{steep}}$.

See Figure 2 for an illustration of 3.7.

Figure 2: The zeta map as composition of bijections mediated by trees. The
nodes of the same depth of the tree are grouped together.

######  Remark 1.

Albeit the same notation, the maps $\Xi_{\mathrm{steep}}$ and
$\Xi_{\mathrm{bounce}}$ are only special cases of the ones in [CFM20,
Construction 3.10 and Equation 14]. More precisely, the central objects in
[CFM20] are called _LAC trees_ , which are plane trees with non-root nodes
divided into regions algorithmically. We are only using the special case where
the region $d$ consists of nodes of depth $d$, which is also the one used in
[CFM20, Section 3.3] to prove 3.7.

######  Remark 2.

The bijection $\Xi_{\mathrm{steep}}$ is classical, except that we do the
contour walk from right to left instead of from left to right. The bijection
$\Xi_{\mathrm{bounce}}$ is quite close to the classical bijection between
plane trees and Łukasiewicz words (see [FS09, Section I.5.3]), which can be
seen as sequences $(x_{0},x_{2},\ldots,x_{n-1})$ with $x_{i}\geq-1$ such that
$\sum_{i=0}^{k}x_{i}\geq 0$ for $0\leq k<n-1$, and the sum of all $x_{i}$’s is
$-1$. However, in the classical bijection of Łukasiewicz, we deal with nodes
in a depth-first order, but in $\Xi_{\mathrm{bounce}}$ they are processed in a
breadth-first order.

##  4 Unit interval posets and the zeta map

In the following, we give the two representations of unit interval posets as
Dyck paths, and we detail how they are related to the bijections detailed in
Section 3, leading to a proof of our main result (4.6).

We start by the first representation, which was first defined implicitly using
anti-adjacency matrices of unit interval posets in [SR03], only involving the
poset structure. The following form was first given in [CG18].

######  Construction 4.1.

Given $P=([n],\preceq_{S})$ a unit interval poset with $S\subset\mathbb{R}$,
we define a Dyck path $D$ as follows. Let $S^{+}=\\{x+1\mid x\in S\\}$.
Without loss of generality, we can choose $S$ such that $S\cap
S^{+}=\varnothing$. Then suppose that $S\cup S^{+}=\\{y_{1}<\cdots<y_{2n}\\}$.
For $i\in[2n]$, the $i$-th step of $D$ is $\uparrow$ if $y_{i}\in S$, and is
$\rightarrow$ otherwise. We define $\varphi(P)=D$. See Figure 3 for an
example.

Although defined here using the set $S$, the map $\varphi$ in 4.1, with this
form given in [CG18] and proved in Lemma 5.7 therein to be equivalent to the
original definition, does not depend on the choice of $S$.

Figure 3: Example of the bijections $\varphi$ and $\psi$

######  Proposition 4.2.

We have $\varphi\circ\Xi_{\mathrm{poset}}=\Xi_{\mathrm{bounce}}$, and
$\varphi$ is a bijection from $\mathcal{P}_{n}$ to $\mathcal{D}_{n}$ for all
$n\geq 1$.

###### Proof.

Let $T\in\mathcal{T}_{n}$ and $D=\Xi_{\mathrm{bounce}}(T)$. We take
$P=\Xi_{\mathrm{poset}}(T)=([n],\preceq_{S})\in\mathcal{P}_{n}$ with
$S=\\{x_{1}<\cdots<x_{n}\\}$ to be that given in 3.2. Let
$D^{\prime}=\varphi(P)$. To show that $D^{\prime}=D$, we first notice that a
Dyck path is determined by the number of north steps on each line $x=k$ for
$0\leq k\leq n-1$. Thus, we only need to show that for each $k$, $D^{\prime}$
has the same number of north steps on $x=k$ as in $D$ given in 3.6.

For the line $x=0$, we observe that the number of elements in $S$ strictly
smaller than $x_{1}+1$ must be those with integer part equal to $1$, thus
those from the children of the root of $T$. For $1\leq k\leq n-1$, from 4.1,
we know that the number of north steps on the line $x=k$ is the number of
elements $x_{i}$ such that $x_{k-1}+1<x_{i}<x_{k}+1$, as $x_{k}+1$ corresponds
to the $k$-th east step in $D$. Let $u_{k}$ be the node in $T$ corresponding
to $x_{k}$. By 3.3, the nodes in $T$ corresponding to such $x_{i}$ are
children of $u_{k}$, meaning that the total number of north steps on $x=k$ is
the number of children of $u_{k}$. Furthermore, suppose that $u_{k}$ is of
depth $\ell$, then we can write $k=s_{\ell}-r$ with $0\leq r\leq\alpha_{\ell}$
as in 3.6. We know that $u_{k}$ is the $(r+1)$-st node of depth $\ell$ in $T$,
as in 3.1 the values corresponding to nodes of the same depth are decreasing
from left to right. We thus conclude that $D=D^{\prime}$, and
$\varphi\circ\Xi_{\mathrm{poset}}=\Xi_{\mathrm{bounce}}$. As both
$\Xi_{\mathrm{bounce}}$ (Lemma 3.18 in [CFM20] and $\Xi_{\mathrm{poset}}$
(3.4) are bijections, we conclude that $\varphi$ is also a bijection. ∎

The second presentation was first defined in [GPMR14] for $(3+1)$-free posets,
and it takes a simpler form for unit interval posets.

######  Construction 4.3.

For $n\geq 1$, let $D\in\mathcal{D}_{n}$ be a Dyck path of size $n$. Its _area
vector_ , denoted by $\operatorname{Area}(D)$, is a vector
$(a_{1},\ldots,a_{n})$ with $a_{i}$ the number of full unit squares with the
upper edge on $y=i$ between $D$ and the diagonal $y=x$. We then define a poset
$P=([n],\preceq)$ by taking $i\prec j$ for $i,j\in[n]$ such that

  * •

Either $a_{i}+2\leq a_{j}$;

  * •

Or $a_{i}+1=a_{j}$ and $i<j$.

We define $\psi(D)=P$, and its inverse $\psi^{-1}(P)=D$. See Figure 3 for an
example.

The following result ensures that $\psi$ is well-defined.

######  Proposition 4.4 (Special case of Theorem 5.2 in [MMS]).

The map $\psi$ is a bijection from Dyck paths to unit interval posets
preserving sizes.

######  Proposition 4.5.

We have $\psi=\Xi_{\mathrm{poset}}\circ\Lambda_{\mathrm{steep}}$.

###### Proof.

Let $P=\psi(D)$, $T=\Lambda_{\mathrm{steep}}(D)$ and
$P^{\prime}=\Xi_{\mathrm{poset}}(D)$. We write $P=([n],\preceq)$ and
$P^{\prime}=([n],\preceq_{S})$, with $S$ constructed in 3.2.

For $i\in[n]$, let $u_{i}$ be the $i$-th non-root node in $T$ that is visited
in the clockwise contour walk of $T$. Suppose that
$\operatorname{Area}(D)=(a_{1},\ldots,a_{n})$. By 3.5, the depth of $u_{i}$ is
$a_{i}+1$. We now define a partial order $\preceq_{T}$ on non-root nodes in
$T$ by taking $u_{i}\preceq_{T}u_{j}$ if and only if $i\preceq j$ in $P$. We
denote by $d(v)$ the depth of $v$ in $T$. By 4.3, two non-root nodes $v,w$ in
$T$ satisfy $v\prec_{T}w$ if and only if

  * •

Either $d(v)+2\leq d(w)$;

  * •

Or $d(v)+1=d(w)$, and the parent of $w$ is either $v$ or on the left of $v$.

Now, for $v$ a non-root node in $T$, we take $x_{v}$ defined in (1). Suppose
that there are two non-root nodes $v,w$ of $T$ such that $x_{v}+1<x_{w}$. Then
we have $d(v)+1\leq d(w)$. There are two possibilities: either $d(v)+1=d(w)$,
or $d(v)+2\leq d(w)$. In the first case, let $w^{\prime}$ be the parent of
$w$, we have $x_{w^{\prime}}+1<x_{w}$. By 3.3, we know that $x_{v}\leq
w_{w^{\prime}}$. From (1), we know that either $v=w^{\prime}$ or $v$ is on the
right of $w^{\prime}$, as $x_{v}$ is decreasing from left to right for nodes
in $T$ of the same depth. Combining with the second case, we conclude that
$x_{v}+1<x_{w}$ if and only if $v\prec_{T}w$. By 3.2, we have $P\cong
P^{\prime}$, which concludes the proof. ∎

######  Theorem 4.6 (Conjecture 7.1 in [MMS]).

We have $\varphi\circ\psi=\zeta$.

###### Proof.

This is a consequence of 3.7, 4.2 and 4.5. ∎

## References

  * [AKOP02] G. E. Andrews, C. Krattenthaler, L. Orsina, and P. Papi.  ad-nilpotent $\mathfrak{b}$-ideals in ${\rm sl}(n)$ having a fixed class of nilpotence: Combinatorics and enumeration.  Trans. Amer. Math. Soc., 354(10):3835–3853, 2002.
  * [CFM20] C. Ceballos, W. Fang, and H. Mühle.  The Steep-Bounce Zeta Map in Parabolic Cataland.  J. Combin. Theory Ser. A, 172:105210, 2020.
  * [CG18] A. Chavez and F. Gotti.  Dyck paths and positroids from unit interval orders.  J. Combin. Theory Ser. A, 154:507–532, 2018.
  * [FS09] Ph. Flajolet and R. Sedgewick.  Analytic combinatorics.  Cambridge University Press, Cambridge, 2009.
  * [GPMR14] M. Guay-Paquet, A. H. Morales, and E. Rowland.  Structure and Enumeration of $(3+1)$-Free Posets.  Ann. Comb., 18(4):645–674, 2014.
  * [GST] F. Gélinas, A. Segovia, and H. Thomas.  Proof of a conjecture of Matherne, Morales, and Selover on encodings of unit interval orders.  arXiv:2212.12171 [math.CO].
  * [Hag08] J. Haglund.  The $q,t$-Catalan Numbers and the Space of Diagonal Harmonics, volume 41.  American Mathematical Society, Providence, RI, 2008.
  * [MMS] J. P. Matherne, A. H. Morales, and J. Selover.  The Newton polytope and Lorentzian property of chromatic symmetric functions.  arXiv:2201.07333 [math.CO].
  * [Sco64] D. Scott.  Measurement structures and linear inequalities.  J. Math. Psychol., 1(2):233–247, 1964.
  * [SR03] M. Skandera and B Reed.  Total nonnegativity and $(3+1)$-free posets.  J. Combin. Theory Ser. A, 103(2):237–256, 2003.
  * [SS93] Richard P Stanley and John R Stembridge.  On immanants of Jacobi-Trudi matrices and permutations with restricted position.  J. Combin. Theory Ser. A, 62(2):261–279, 1993.
  * [WF57] R. L. Wine and J. E. Freund.  On the Enumeration of Decision Patterns Involving $n$ Means.  Ann. Math. Stat., 28(1):256–259, 1957.


# Experimental Contexts _Can_ Facilitate Robust Semantic Property Inference in
Language Models, but Inconsistently

Kanishka Misraτ Allyson Ettingerα Kyle Mahowaldτ
τThe University of Texas at Austin αAllen Institute for Artificial
Intelligence
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Recent zero-shot evaluations have highlighted important limitations in the
abilities of language models (LMs) to perform meaning extraction. However, it
is now well known that LMs can demonstrate radical improvements in the
presence of experimental contexts such as in-context examples and
instructions. How well does this translate to previously studied meaning-
sensitive tasks? We present a case-study on the extent to which experimental
contexts can improve LMs’ robustness in performing property
inheritance—predicting semantic properties of novel concepts, a task that they
have been previously shown to fail on. Upon carefully controlling the nature
of the in-context examples and the instructions, our work reveals that they
can indeed lead to non-trivial property inheritance behavior in LMs. However,
this ability is inconsistent: with a minimal reformulation of the task, some
LMs were found to pick up on shallow, non-semantic heuristics from their
inputs, suggesting that the computational principles of semantic property
inference are yet to be mastered by LMs.

Experimental Contexts _Can_ Facilitate Robust Semantic Property Inference in
Language Models, but Inconsistently

Kanishka Misraτ Allyson Ettingerα Kyle Mahowaldτ τThe University of Texas at
Austin αAllen Institute for Artificial Intelligence<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Carefully controlled behavioral analyses on meaning-sensitive tasks have
revealed holes in the ability of language models (LMs) to demonstrate robust
meaning extraction and use (Pandia and Ettinger, 2021; Elazar et al., 2021;
Schuster and Linzen, 2022; Misra et al., 2023; Kim and Schuster, 2023, i.a).
However, since a large subset of these investigations uses zero-shot
evaluation as the primary methodology, there are growing concerns that they do
not paint a complete picture of LMs’ abilities (Lampinen, 2022; Sinclair et
al., 2022; Sinha et al., 2023). Conclusions that LMs lack a particular ability
may be overhasty if it turns out the ability is easily accessed through in-
context learning, different question formulations, or particular instructions
(Lampinen, 2022; Wei et al., 2022).

Figure 1:  We prompt LMs with in-context examples that are compatible with
both, robust property inheritance, as well as position-based heuristics. At
test time, we evaluate the model on cases where the heuristics support
desirable behavior and on cases where they do not. We use stimuli from comps
and its reformulation as a QA task (comps-qa).

Our focus111Our code can be found in this link in this paper is a particularly
challenging data set for meaning-sensitive behavior: comps (Misra et al.,
2023), a dataset of minimal pair sentences that tests the ability of LMs on
property knowledge of everyday concepts (a beaver/gorilla has a flat tail) and
their inheritance for novel concepts (a wug is a beaver/gorilla. therefore a
wug has a flat tail). Contemporary LMs failed miserably on the hardest subset
of the comps stimuli, the examples of which contain two novel concepts (wug
vs. dax), where only one of them inherits the target property (has a flat
tail):

  * (1)

A wug is a beaver. A dax is a gorilla. Therefore, a wug/dax has a flat tail.

Given the success of LMs on a wide variety of complicated tasks, their utter
failure on this seemingly straightforward task remains puzzling. Here, we
systematically explore comps on five modern LMs ranging from 1.5–13B
parameters, varying (a) whether models are evaluated zero-shot or with
multiple examples and (b) whether or not instructions are present.

Unlike other minimal-pair datasets, using comps in an in-context learning
setting is non-trivial (and thus potentially informative). This is because the
task can be solved using a position-based heuristic. For example, in one
subset of comps, the target property is always attached to the first novel
concept—like in (1). Importantly, models’ failures on comps were shown to be
in part a result of models’ tendencies towards heuristic behavior: the
performance of LMs is particularly bad when the distractor (a dax is a
gorilla) is recent—i.e., autoregressive LMs show a recency bias in attributing
properties to novel concepts. In that sense, comps follows a rich body of work
in which tasks are set up in a manner that two types of generalization
mechanisms can lead to the same prediction, but only one of which is desirable
(McCoy et al., 2019, 2020; Warstadt et al., 2020b; Mueller et al., 2022; Si et
al., 2023; Mueller et al., 2023).

We find that experimental contexts, as operationalized using in-context
examples and instructions, can in fact demonstrate robust improvements in LMs’
property inheritance behavior as measured by the stimuli in comps. However,
this improvement comes with a caveat: With a minimal reformulation of comps
into a QA task, where there is a direct link between the LMs’ output space and
the features of the input that control the heuristic, LMs show a strong
preference towards the heuristic, and are therefore at chance. This
discrepancy suggests that the improvements on the original task do not
necessarily indicate that the models have successfully mastered the reasoning
ability required to perform property inheritance, which remains a key
challenge for them.

##  2 Methodology

#### Dataset

We use the most difficult subset of the comps dataset (Misra et al.,
2023)—comps-wugs-dist—for our experiments. This dataset contains 13,828
sentence pairs of the form similar to (1), constructed using 152 animal
concepts and 991 properties.

#### Stimuli re-design

We take a number of steps to minimize noise from other (likely
uninterpretable) heuristics beyond the ones we have set out to target. First,
we enforce that the concepts and properties that appear in the in-context
examples are disjoint from ones that are used in tests. To this end, we sample
50 concepts and their relevant properties and reserve it for our in-context
examples, leaving the rest to be sampled for our test set. We also enforce
this constraint for our novel concepts—i.e., all in-context examples contain
different nonce words, and the collection of nonce words for the in-context
examples and the test set is disjoint. Furthermore, we counterbalance the
nonce words in the test set in a manner that having a bias towards one of them
would lead to chance performance. We additionally also use multiple different
sets of in-context examples, to add variability and to ensure that the results
are not only due to one particular choice of in-context examples. In total, we
use 10 different in-context learning example sets, each containing 6 different
comps stimuli. For our test set, we use a constant set of 256 unique pairs
sampled from our pool of stimuli containing unused concepts and properties.

#### Heuristics

Our most important design decision is to consider two distinct sets of
stimuli—each separately making available the two types of heuristics that the
LMs could rely upon: first-correct and recent-correct, where the property is
inherited by the first and the most recent novel concept, respectively. That
is, for the same set of in-context examples, we have a version where the first
concept is correct like in (1), and one where the most recent concept is
correct:

  * (2)

A wug is a gorilla. A dax is a beaver. Therefore, a wug/dax has a flat tail.

For each type of in-context stimuli, we similarly have two versions of test
stimuli: one that is consistent with the target heuristic, and one that is
not. That is, a test example that is consistent with the first-correct
heuristic will also have its first concept be the one that inherits the
property in question, while one which is inconsistent will have the most
recent concept be the inheritor of the property. Therefore, a model that shows
a preference for a given heuristic will succeed only on one test set and
succumb on the other, while a model that is robust to the heuristics will
succeed on both.

#### Reformulation into QA

The original comps stimuli test for property inheritance using declarative
statements, where models are tested for the log-probability they asign to the
property (has a flat tail) given either of the two concepts (wug vs. dax).
Here we additionally consider an alternate formulation of comps as a question
answering task (comps-qa), where we make the property explicit in the prompt
to the model and instead ask which of the two concepts possesses it:

  * (3)

A wug is a beaver. A dax is a gorilla. Question: Which one of them has a flat
tail? Answer: wug/dax

Since the shallow heuristics we consider are controlled by the relative
ordering of the novel concepts, this formulation of the task directly allows
us to link the models’ output space (the novel concepts) to the heuristics
(positions).

#### Testing setup

For the original comps setting we follow Misra et al. (2023) and compare the
log-probability of the property phrase given the correct vs. the incorrect
prefix. For comps-qa however, since we have a constant prefix (same premises
and question), we evaluate the relative log-probability of the two novel
concepts, only one of which is the correct answer. Accuracy in both cases is
the proportion of cases the correct surface form was assigned relatively
higher log-probability. Since we use pairwise comparisons throughout, chance
performance is 50%.

#### Instructions

We consider four different kinds of instruction templates, with varying levels
of detail (see appendix 0.B) per formulation (comps and comps-qa). In our
experiments we report results on the instruction that gives the best average
performance for a given model.

#### LMs tested

We evaluated 5 different open-source LMs, all of which are decoder-only, and
were accessed using the huggingface hub (Wolf et al., 2020): GPT-2 XL (Radford
et al., 2019); OPT-6.7b (Zhang et al., 2022); Llama-2 (we used the 7b and the
13b versions; Touvron et al., 2023); and Mistral-7b (Jiang et al., 2023).
Details about the models can be found in the appendix.

Figure 2: Overall results from our experiments testing LMs on comps and comps-
qa using in-context examples, with and without instructions. Results are
aggregated across both heuristics: first-correct and recent-correct. Error
bars are over different sets of in-context examples. All models start off near
chance in the 0-shot case, but many improve as more examples are given. Some
(e.g., GPT-2 XL on comps-qa) show strongly heuristically driven behavior, as
evidenced by the diverging performance on items where heuristics work and
those where they do not. Figures 3 and 4 show fine-grained results.

##  3 Analyses and Results

We evaluate on comps and comps-qa, with and without instructions. In each
case, we progressively supply 0 through 6 in-context examples, allowing us to
track the dynamics of the models’ performance with an increasing amount of
demonstrations. Together with our separate types of test sets and heuristics
encoded in the in-context examples, along with five different instruction
settings (four with and one without) we run 2420 experiments per LM. We
hypothesize that LMs would be more sensitive to the positional heuristics in
comps-qa because of the clear link between their output space and the relative
position of the novel concepts—the feature that controls our target
heuristics.

Figure 2 shows accuracies of the tested LMs on our four different comps
settings as a function of the number of in-context examples provided to them,
for both: cases where the heuristics are consistent with success on the test
set, and cases where they are not. We also show an additional curve denoting
the average performance across the two types of test sets to paint an overall
picture of the models’ performance. In this figure, the extent to which a
model relies on heuristic is indicated by the gap between the dotted
($\newmoon$) and the dashed ($\blacktriangle$) lines. A model that is robust
to the heuristics will have curves of both colors rise above chance, with no
gap between the two, while one that is prone to using heuristics will have its
dotted ($\newmoon$) curve be substantially greater than its dashed
($\blacktriangle$) curve.

#### Experimental context can improve attribution of properties to concepts…

On comps, models unsurprisingly start off at chance performance on average,
corroborating the previous findings of Misra et al. (2023). However, in the
presence of in-context examples and instructions, they are able to improve
monotonically as the number of in-context examples increases. It is worth
noting Llama-2-13b does occasionally show a slight preference for heuristics
in the absence of instructions (e.g., 84% vs. 62% when prompted with 2
examples). An intermediate conclusion that we draw here is that LMs can indeed
demonstrate non-trivial property inheritance on observing a few examples that
reflect that behavior.

#### …but not the attribution of concepts to properties

While experimental context seems to aid models in attributing properties to
the right concept in context, the same does not hold on comps-qa. Similar to
comps, models start off at chance performance on average with a zero-shot set
up, however, unlike in the case of comps, LMs seem to consistently prefer the
heuristics available in the prompt, showing worse than chance performance on
cases where the test set does not follow the heuristic. This is most apparent
for GPT-2 XL, OPT6.7b, and Llama-2-7b—here the gap between the accuracy for
cases where heuristics support performance on the test set and the accuracy
for cases where they do not almost always worsens with an increase in the
number of exemplars, on average. This is especially notable for OPT6.7b, which
attains perfect performance on cases where the heuristics match up with the
test set and at the same time it is close to 0% on cases where they do not. A
notable exception to this trend is Mistral-7b, which seems to be resilient to
the spurious heuristics, showing a net-positive improvement from the zero-shot
case, especially in the presence of instructions. Nevertheless in the absence
of instructions, it too shows a slight preference for position-based
heuristics—for instance, its accuracy with 6 in-context exemplars when the
heuristics support success on the test set is 82% and on cases where the
heuristics oppose the test set is 65%.

Our results suggest that LMs are more likely to show behavior that is
compatible with the use of positional heuristics when their output space
(choice between the two novel concepts) has a clear connection with positional
artifacts in their input (relative ordering of the novel concepts). This is
consistent with our hypothesis in about 8 out of 10 cases. When this link is
not clear and models must instead predict likely properties given a novel
concept (i.e., in comps), instructions and in-context examples do seem to lead
to robust performance. It is important to note that instructions alone do not
always account for the observed improvement—LMs’ performance on zero-shot
settings are consistently still at chance in all cases, suggesting that it is
the in-context examples that critically alter models’ output distribution to
support desirable property inference behavior.

##  4 Conclusion

In this work, we investigated the extent to which in-context examples and
instructions—key components that drive impressive performance in contemporary
LMs—can overcome important limitations of LMs at tests that have poked holes
in their ability to extract conceptual meaning from text. As a case study, we
analyzed how well such experimental contexts can improve LM abilities to
perform property inheritance (Murphy, 2002; Misra et al., 2023) in
context—binding of novel concepts to existing concepts, and endowing them with
valid property inferences as a result. Our findings suggest that mastery of
this ability has yet to be robustly achieved, and that LMs in general are
still prone to using shallower patterns in their context (when available)
rather than systematically extracting conceptual meaning. At the same time,
exploring precisely what makes Mistral less susceptible to heuristics will be
useful to design more robust LMs, which we leave for future work.

##  5 Limitations

#### Single dataset

A clear limitation of this work is that it exclusively focuses on a single
dataset: comps (Misra et al., 2023). So, a question that arises here is to
what extent are our findings localized to the chosen dataset vs. meaning-
sensitive evaluations in general. This would require a further non-trivial,
non-straightforward amount of work, since: (1) different meaning sensitive
evaluations focus on different (though equally useful) operationalizations of
meaning; and more importantly (2) not all prior work in this area focuses on a
standardized and well-defined usage of heuristics that is directly
transferable to the experimental setup we have used in this work (following
McCoy et al., 2019, 2020; Warstadt et al., 2020b; Mueller et al., 2022; Si et
al., 2023).

We do hope that our work contributes to the larger-scale vision of carefully
benchmarking different types of meaning extraction abilities in LMs in a
controlled manner.

#### Lack of mechanistic insight

Our work continues the long-standing precedent of using carefully constructed
behavioral experiments to conclude about the competence of LMs (Linzen et al.,
2016; Gulordava et al., 2018; Futrell et al., 2019; Ettinger, 2020; Warstadt
et al., 2020a) However, recent works have made impressive strides in
localizing the kinds of computations that give rise to the observed behavior
in LMs (Hanna et al., 2023; Wang et al., 2023, i.a.) Therefore, it is entirely
possible that our conclusions about the precise nature of computations carried
out by LMs can be greatly strengthened when supplemented by the methods
developed in these aforementioned works.

#### Single Language

Finally, this work only focuses on property inheritance problems stated in the
English language. This does little to contribute towards diversity in NLP
research.

##  6 Acknowledgments

We thank Tom McCoy and Andrew Lampinen for providing comments on a previous
version of the draft. (KM)2 acknowledge funding from NSF Grant 2104995 awarded
to Kyle Mahowald.

## References

  * Elazar et al. (2021) Yanai Elazar, Hongming Zhang, Yoav Goldberg, and Dan Roth. 2021.  Back to square one: Artifact detection, training and commonsense disentanglement in the Winograd schema.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 10486–10500, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Ettinger (2020) Allyson Ettinger. 2020.  What BERT is not: Lessons from a new suite of psycholinguistic diagnostics for language models.  _Transactions of the Association for Computational Linguistics_ , 8:34–48.
  * Futrell et al. (2019) Richard Futrell, Ethan Wilcox, Takashi Morita, Peng Qian, Miguel Ballesteros, and Roger Levy. 2019.  Neural language models as psycholinguistic subjects: Representations of syntactic state.  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 32–42, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Gulordava et al. (2018) Kristina Gulordava, Piotr Bojanowski, Edouard Grave, Tal Linzen, and Marco Baroni. 2018.  Colorless green recurrent networks dream hierarchically.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1195–1205, New Orleans, Louisiana. Association for Computational Linguistics.
  * Hanna et al. (2023) Michael Hanna, Ollie Liu, and Alexandre Variengien. 2023.  How does GPT-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model.  In _Thirty-seventh Conference on Neural Information Processing Systems_.
  * Hu et al. (2020) Jennifer Hu, Jon Gauthier, Peng Qian, Ethan Wilcox, and Roger Levy. 2020.  A systematic assessment of syntactic generalization in neural language models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1725–1744, Online. Association for Computational Linguistics.
  * Jiang et al. (2023) Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_.
  * Kim and Schuster (2023) Najoung Kim and Sebastian Schuster. 2023.  Entity tracking in language models.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 3835–3855, Toronto, Canada. Association for Computational Linguistics.
  * Lampinen (2022) Andrew Kyle Lampinen. 2022.  Can language models handle recursively nested grammatical structures? a case study on comparing models and humans.  _arXiv preprint arXiv:2210.15303_.
  * Linzen et al. (2016) Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016.  Assessing the ability of LSTMs to learn syntax-sensitive dependencies.  _Transactions of the Association for Computational Linguistics_ , 4:521–535.
  * McCoy et al. (2020) R Thomas McCoy, Robert Frank, and Tal Linzen. 2020.  Does syntax need to grow on trees? sources of hierarchical inductive bias in sequence-to-sequence networks.  _Transactions of the Association for Computational Linguistics_ , 8:125–140.
  * McCoy et al. (2019) Tom McCoy, Ellie Pavlick, and Tal Linzen. 2019.  Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3428–3448, Florence, Italy. Association for Computational Linguistics.
  * Misra (2022) Kanishka Misra. 2022.  minicons: Enabling flexible behavioral and representational analyses of transformer language models.  _arXiv preprint arXiv:2203.13112_.
  * Misra et al. (2023) Kanishka Misra, Julia Rayz, and Allyson Ettinger. 2023.  COMPS: Conceptual minimal pair sentences for testing robust property knowledge and its inheritance in pre-trained language models.  In _Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics_ , pages 2928–2949, Dubrovnik, Croatia. Association for Computational Linguistics.
  * Mueller et al. (2022) Aaron Mueller, Robert Frank, Tal Linzen, Luheng Wang, and Sebastian Schuster. 2022.  Coloring the blank slate: Pre-training imparts a hierarchical inductive bias to sequence-to-sequence models.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 1352–1368, Dublin, Ireland. Association for Computational Linguistics.
  * Mueller et al. (2023) Aaron Mueller, Albert Webson, Jackson Petty, and Tal Linzen. 2023.  In-context learning generalizes, but not always robustly: The case of syntax.  _arXiv preprint arXiv:2311.07811_.
  * Murphy (2002) Gregory L Murphy. 2002.  _The Big Book of Concepts_.  MIT press.
  * Pandia and Ettinger (2021) Lalchand Pandia and Allyson Ettinger. 2021.  Sorting through the noise: Testing robustness of information processing in pre-trained language models.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 1583–1596, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI_.
  * Schuster and Linzen (2022) Sebastian Schuster and Tal Linzen. 2022.  When a sentence does not introduce a discourse entity, transformer-based models still sometimes refer to it.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 969–982, Seattle, United States. Association for Computational Linguistics.
  * Si et al. (2023) Chenglei Si, Dan Friedman, Nitish Joshi, Shi Feng, Danqi Chen, and He He. 2023.  Measuring inductive biases of in-context learning with underspecified demonstrations.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 11289–11310, Toronto, Canada. Association for Computational Linguistics.
  * Sinclair et al. (2022) Arabella Sinclair, Jaap Jumelet, Willem Zuidema, and Raquel Fernández. 2022.  Structural persistence in language models: Priming as a window into abstract language representations.  _Transactions of the Association for Computational Linguistics_ , 10:1031–1050.
  * Sinha et al. (2023) Koustuv Sinha, Jon Gauthier, Aaron Mueller, Kanishka Misra, Keren Fuentes, Roger Levy, and Adina Williams. 2023.  Language model acceptability judgements are not always robust to context.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6043–6063, Toronto, Canada. Association for Computational Linguistics.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_.
  * Wang et al. (2023) Kevin Ro Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. 2023.  Interpretability in the wild: a circuit for indirect object identification in GPT-2 small.  In _The Eleventh International Conference on Learning Representations_.
  * Warstadt et al. (2020a) Alex Warstadt, Alicia Parrish, Haokun Liu, Anhad Mohananey, Wei Peng, Sheng-Fu Wang, and Samuel R. Bowman. 2020a.  BLiMP: The benchmark of linguistic minimal pairs for English.  _Transactions of the Association for Computational Linguistics_ , 8:377–392.
  * Warstadt et al. (2020b) Alex Warstadt, Yian Zhang, Xiaocheng Li, Haokun Liu, and Samuel R. Bowman. 2020b.  Learning which features matter: RoBERTa acquires a preference for linguistic generalizations (eventually).  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 217–235, Online. Association for Computational Linguistics.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837.
  * Wilcox et al. (2019) Ethan Wilcox, Roger Levy, and Richard Futrell. 2019.  Hierarchical representation in neural language models: Suppression and recovery of expectations.  In _Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 181–190, Florence, Italy. Association for Computational Linguistics.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. 2022.  OPT: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_.

##  Appendix 0.A Dataset and implementation details

Our experiments use the stimuli from comps, released with an MIT License by
Misra et al. (2023), but with a modification that involves changing of the
nonce words to obey the constraint that the in-context examples all have
different nonce word pairs. To this end, we use the following nonce-words:

  * •

In-context examples: wug, dax, fep, zek, blick, toma, kiki, glorp, bova, zup,
tufa, flib (counter-balanced)

  * •

Test examples: gek, wif (counter-balanced)

###  0.A.1 Methodological details

Following comps, as well as the precedent set by a number of previous minimal
pair analyses (Linzen et al., 2016; Gulordava et al., 2018; Futrell et al.,
2019; Wilcox et al., 2019; Warstadt et al., 2020a; Hu et al., 2020), we use a
forced choice task to evaluate our LM subjects. Like in comps, we compare the
log-probability of the property phrase (here, has a flat tail) given the
choice of left contexts (which indicate whether the right vs. the wrong
concept has the property). For example, we measure:

$\displaystyle\log P_{\theta}(\textit{has a flat tail}\mid$ a gek is a beaver.
a wif is a $\displaystyle\textit{ gorilla. therefore, a
{{\color[rgb]{0.23828125,0.5234375,0.77734375}\definecolor[named]{pgfstrokecolor}{rgb}{0.23828125,0.5234375,0.77734375}gek}/{\color[rgb]{0.9453125,0.76171875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9453125,0.76171875,0.1953125}wif}}}),$

and for comps-qa, we compare the relative probabilities of the two novel
concepts given a fixed left prefix which contains a question about the
property. For example, we measure:

$\displaystyle\log
P_{\theta}(\textit{{{\color[rgb]{0.23828125,0.5234375,0.77734375}\definecolor[named]{pgfstrokecolor}{rgb}{0.23828125,0.5234375,0.77734375}gek}/{\color[rgb]{0.9453125,0.76171875,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{0.9453125,0.76171875,0.1953125}wif}}}\mid$
a gek is a beaver. a wif is a gorilla. Question: Which one of them has a
$\displaystyle\textit{ flat tail? {Answer:}})$

In both cases above, gek is the concept that should inherit the property.
While these examples show the zero-shot case, cases with in-context examples
and instructions simply add more context to the prefix, therefore the surface
form of the output space remains the same regardless of the number of in-
context examples or the presence of instructions.

Log-probabilities for all models were accessed using minicons (Misra,
2022),222https://github.com/kanishkamisra/minicons a library that wraps around
transformers (Wolf et al., 2020) by huggingface, and is written in pytorch.
For our experiments with Llama-13B, we quantize the model to 4-bits in order
to fit it onto a single GPU. All experiments were run on a cluster with 4
NVIDIA A40 GPUs, though each individual experiment on a model was computed on
a single A40 GPU.

###  0.A.2 Model Metadata

Model | Params | Pre-training Tokens | Vocab size
---|---|---|---
GPT-2 XL | 1.5B | 8B | 50,257
OPT-6.7b | 6.7B | 180B | 50,272
Llama-2-7b | 7B | 2T | 32,000
Llama-2-13b | 13B | 2T | 32,000
Mistral-7b | 7B | ? | 32,000
Table 1: Overview of the LMs used in this work. ‘?’ indicates that the given
value was not made available in the LM’s release.

Table 1 shows the LMs used in this work, along with their total parameters,
tokens encountered during training, and vocabulary size.

##  Appendix 0.B Instructions

Tables 2, 3, 4, 5 show our instruction templates.

comps version |  Instruction Template
---|---
comps |  Given a pair of statements that introduce novel entities as types of real world animals, write a true statement about the properties of the novel entities:

{exemplars} (omitted in zero-shot)
{test-stimulus}
comps-qa |  Given a pair of statements that introduce novel entities as types of real world animals, answer the question that follows:

{exemplars} (omitted in zero-shot)
{test-stimulus}
Table 2: Instructions for comps and comps-qa with instruction type: “minimal” comps version |  Instruction Template
---|---
comps |  Some aliens have come to earth, and it turns out they have their own language for talking about our animals here on Earth. Your job is to help the aliens learn about our Earthling animals by giving them some information about the animals.

Let’s get started:
{exemplars} (omitted in zero-shot)
{test-stimulus}
comps-qa |  Some aliens have come to earth, and it turns out they have their own language for talking about our animals here on Earth. Your job is to help the aliens learn about our Earthling animals by answering some questions about them.

Let’s get started:
{exemplars} (omitted in zero-shot)
{test-stimulus}
Table 3: Instructions for comps and comps-qa with instruction type: “aliens”

comps version | No. of shots |  Instruction Template
---|---|---
comps | Zero-shot |  It is important to know and reason about the properties of entities in the world. The following is a pair of premise statements that introduce novel entities as new types of real world animals. Your task is to make a conclusion about the properties of one of the entities by reasoning over the premise statements.

{test_stimulus}
Few-shot |  It is important to know and reason about the properties of entities in the world. The following example(s) show a pair of premise statements that introduce novel entities as new types of real world animals, followed by another statement that attributes a property to one of the entities introduced in the premise statements.

Examples:
{examples}

Here is another pair of premise statements. Your task is to make a conclusion
about the properties of one of the entities by reasoning over the premise
statements.
{test_stimulus}
comps-qa | Zero-shot |  It is important to know and reason about the properties of entities in the world. The following is a pair of premise statements that introduce novel entities as new types of real world objects. The statements are followed by a question that asks which novel entity in the premise can a specific property can be attributed to. Answer the question by reasoning over the premise statements.

{test_stimulus}
Few-shot |  It is important to know and reason about the properties of entities in the world. The following example(s) show a pair of premise statements that introduce novel entities as new types of real world animals. The statements are followed by a question that asks which novel entity in the premise can a specific property can be attributed to, and the answer to the question, obtained by reasoning over the premise statements.

Examples:
{examples}

Here is another pair of premise statements. Answer the question that follows.
{test_stimulus}

Table 4: Instructions for comps and comps-qa with instruction type:
“Detailed-1”

comps version | No. of shots |  Instruction Template
---|---|---
comps | Zero-shot |  It is important to know and reason about the properties of entities in the world. The following is a pair of premise statements that introduce novel entities as new types of real world animals. Your task is to write a true statement about the properties of the novel entities.

{test_stimulus}
Few-shot |  It is important to know and reason about the properties of entities in the world. The following example(s) show a pair of premise statements that introduce novel entities as new types of real world animals, followed by another statement that attributes a property to one of the entities introduced in the premise statements.

Examples:
{examples}

Here is another pair of premise statements. Your task is to write a true
statement about the properties of the novel entities.
{test_stimulus}
comps-qa | Zero-shot |  It is important to know and reason about the properties of entities in the world. The following is a pair of premise statements that introduce novel entities as new types of real world animals. The statements are followed by a question that asks which of the introduced entities a specific property can be attributed to. Answer the question by reasoning over the premise statements.

{test_stimulus}
Few-shot |  It is important to know and reason about the properties of entities in the world. The following example(s) show a pair of premise statements that introduce novel entities as new types of real world animals. The statements are followed by a question that asks which of the introduced entities a specific property can be attributed to, and the answer to the question, obtained by reasoning over the premise statements.

Examples:
{examples}

Here is another pair of premise statements. Answer the question that follows.
{test_stimulus}

Table 5: Instructions for comps and comps-qa with instruction type:
“Detailed-2”

##  Appendix 0.C Fine-grained results

While Figure 2 shows results aggregated over both types of heuristics that we
have used in this work, we additionally display finer-grained, heuristics-wise
results in this section. Again, in each of these plots, the extent to which a
model relies on heuristic is indicated by the gap between the dotted
($\newmoon$) and the dashed ($\blacktriangle$) lines. This is now separately
shown for each of our heuristics. Figure 3 shows results on comps with and
without instructions for both the heuristics, and similarly Figure 4 shows
results on comps-qa with and without instructions for both the heuristics.

(a) comps

(b) comps with Instructions

Figure 3: Fine-grained results on COMPS as a function of the number of in-
context examples (with and without instructions).

(a) comps-qa

(b) comps-qa with Instructions

Figure 4: Fine-grained results on COMPS-QA as a function of the number of in-
context examples (with and without instructions).