# Lower bounds for graph reconstruction with maximal independent set queries

Lukas Michel222Mathematical Institute, University of Oxford, United Kingdom
({michel,scott}@maths.ox.ac.uk). Research of Alex Scott supported by EPSRC
grant EP/X013642/1. Alex Scott††footnotemark:

(4 April 2024)

###### Abstract

We investigate the number of maximal independent set queries required to
reconstruct the edges of a hidden graph. We show that randomised adaptive
algorithms need at least $\Omega(\Delta^{2}\log(n/\Delta)/\log\Delta)$ queries
to reconstruct $n$-vertex graphs of maximum degree $\Delta$ with success
probability at least $1/2$, and we further improve this lower bound to
$\Omega(\Delta^{2}\log(n/\Delta))$ for randomised non-adaptive algorithms. We
also prove that deterministic non-adaptive algorithms require at least
$\Omega(\Delta^{3}\log n/\log\Delta)$ queries.

This improves bounds of Konrad, O’Sullivan, and Traistaru, and answers one of
their questions. The proof of the lower bound for deterministic non-adaptive
algorithms relies on a connection to cover-free families, for which we also
improve known bounds.

##  1 Introduction

The graph reconstruction problem is the problem of determining the edges of a
hidden graph $G=(V,E)$ through queries that reveal some partial information
about the graph. For a given type of query, the following natural question
presents itself.

> What is the minimum number of queries required to reconstruct any graph?

This problem has been extensively studied for independent set queries that
reveal whether a queried set of vertices contains an edge. Bounds on the
minimum number of queries required were studied for general graphs [AC08,
AB19], specific families of graphs [AA05, ABK+04], and hypergraphs [AC06,
ABM14]. In related graph problems, other query models were considered. For
instance, maximal matching queries were used to approximate maximum matchings
in a graph [KK20, KNS23], and vertex degree queries were used to estimate the
average degree of a graph [Fei06, GR08].

Konrad, O’Sullivan, and Traistaru [KOT24] recently investigated graph
reconstruction for maximal independent set queries. In this setting, an
algorithm can query a set of vertices $Q\subseteq V$ to obtain a maximal
independent set of the subgraph of $G$ induced by $Q$. Using this information,
the algorithm has to reconstruct all edges of the graph.

There are two important properties that influence the minimum number of
queries required by such an algorithm. Firstly, queries can either be
adaptive, which means that they depend on the outcomes of other queries, or
they are non-adaptive if they do not. While adaptive algorithms require fewer
queries, non-adaptive algorithms are desirable because their queries can be
performed in parallel. Secondly, algorithms can randomise their queries. In
contrast to deterministic algorithms which always reconstruct the graph
correctly, randomised algorithms only succeed with high probability, but they
might use far fewer queries.

Randomised algorithms. One way of choosing non-adaptive queries for a
randomised algorithm is to choose each query by independently including each
vertex with a fixed probability. By analysing this strategy, Konrad,
O’Sullivan, and Traistaru [KOT24] showed that $\mathcal{O}(\Delta^{2}\log n)$
non-adaptive queries suffice to reconstruct graphs with $n$ vertices and
maximum degree $\Delta$ with high probability.

######  Theorem 1.1 (Konrad, O’Sullivan, and Traistaru).

There is a randomised non-adaptive algorithm that uses
$\mathcal{O}(\Delta^{2}\log n)$ queries to reconstruct any graph of maximum
degree $\Delta$ with high probability.

To complement this upper bound, Konrad, O’Sullivan, and Traistaru proved that
any randomised adaptive algorithm that succeeds with probability at least
$1/2$ requires at least $\Omega(\Delta^{2}+\log n)$ queries. They asked
whether an algorithm could attain this lower bound. We show that this is not
possible.

######  Theorem 1.2.

The number of queries of a randomised adaptive algorithm that reconstructs any
graph of maximum degree $\Delta$ with probability at least $1/2$ is at least

$\Omega\mathopen{}\mathclose{{}\left(\frac{\Delta^{2}\log\mathopen{}\mathclose{{}\left(\frac{n}{\Delta}}\right)}{\log\Delta}}\right).$

For non-adaptive algorithms, we further improve this lower bound by a factor
of $\log\Delta$. This matches Theorem 1.1 for $\Delta\leq n^{1-\varepsilon}$
when $\varepsilon>0$ is fixed.

######  Theorem 1.3.

The number of queries of a randomised non-adaptive algorithm that reconstructs
any graph of maximum degree $\Delta$ with probability at least $1/2$ is at
least

$\Omega\mathopen{}\mathclose{{}\left(\Delta^{2}\log\mathopen{}\mathclose{{}\left(\frac{n}{\Delta}}\right)}\right).$

The proofs of these lower bounds rely on graphs that contain a clique of size
$\Theta(\Delta)$ while the remaining vertices form an independent set. We will
show that maximal independent set queries reveal only very little information
about such graphs. Counting the number of these graphs then gives the desired
lower bounds.

Deterministic algorithms. To obtain a deterministic algorithm, Konrad,
O’Sullivan, and Traistaru [KOT24] adapted the idea of their randomised
algorithm. They showed that a fixed collection of sufficiently many random
queries will reconstruct every graph correctly. This gives a deterministic
algorithm with $\mathcal{O}(\Delta^{3}\log n)$ non-adaptive queries.333In
fact, their arguments show that $\mathcal{O}(\Delta^{3}\log(n/\Delta))$
queries are sufficient.

######  Theorem 1.4 (Konrad, O’Sullivan, and Traistaru).

There is a deterministic non-adaptive algorithm that uses
$\mathcal{O}(\Delta^{3}\log n)$ queries to reconstruct any graph of maximum
degree $\Delta$.

Konrad, O’Sullivan, and Traistaru also showed that every deterministic non-
adaptive algorithm needs at least $\Omega(\Delta^{3}/(\log\Delta)^{2}+\log n)$
queries. We provide a lower bound that matches the upper bound from Theorem
1.4 up to a factor of $\log\Delta$.

######  Theorem 1.5.

The number of queries of a deterministic non-adaptive algorithm that
reconstructs any graph of maximum degree $\Delta$ is at least

$\Omega\mathopen{}\mathclose{{}\left(\min\left\\{n^{2},\frac{\Delta^{3}\log
n}{\log\Delta}\right\\}}\right).$

Our proof of Theorem 1.5 relates deterministic non-adaptive algorithms to
cover-free families. Here, a family of sets $\mathcal{F}$ is _$(w,r)$ -cover-
free_ if for all $A_{1},\dots,A_{w}\in\mathcal{F}$ and all
$B_{1},\dots,B_{r}\in\mathcal{F}\setminus\\{A_{1},\dots,A_{w}\\}$ we have

$\bigcap_{i=1}^{w}A_{i}\nsubseteq\bigcup_{i=1}^{r}B_{i}.$

The size of cover-free families has been widely studied because of their
relevance to non-adaptive group testing [HS87, DH00, DH06, AJS19], key
distribution patterns [MP88, DFFT95], superimposed codes [KS64, DR82], and
more [Wei06, Eng96]. For a given $n$, let $t(n,w,r)$ denote the minimal $t$
such that there exists a $(w,r)$-cover-free family
$\mathcal{F}\subseteq\mathcal{P}(t)$ with $n$ sets. We observe the following
connection between cover-free families and deterministic non-adaptive
algorithms.

######  Lemma 1.5.

The minimum number of queries of a deterministic non-adaptive algorithm that
reconstructs any graph of maximum degree $\Delta$ is at least
$t(n,2,2\Delta-2)$ and at most $t(n,2,2\Delta)$.

Upper and lower bounds on $t(n,w,r)$ have been extensively studied. On the
side of upper bounds, it is well-known [DFFT95, Eng96, STW00, SW04] that

$t(n,w,r)=\mathcal{O}\mathopen{}\mathclose{{}\left(\frac{(w+r)^{w+r+1}}{w^{w}r^{r}}\log
n}\right).$

If $w$ is fixed, this yields $t(n,w,r)=\mathcal{O}(r^{w+1}\log n)$ which gives
an alternative proof of Theorem 1.4.

In terms of lower bounds, when $w=1$, D’yachkov and Rykov [DR82] proved that
$t(n,1,r)=\Omega(r^{2}\log n/\log r)$ if $r$ is fixed and $n\to\infty$. Later,
Ruszinkó [Rus94] and Füredi [Für96] gave purely combinatorial proofs of this
result. More generally, for arbitrary $r$ and $n$, the argument of Füredi
gives the following lower bound.

######  Theorem 1.6 (Füredi).

If $1\leq r<n$, then

$t(n,1,r)=\Omega\mathopen{}\mathclose{{}\left(\min\left\\{n,\frac{r^{2}\log
n}{\log r}\right\\}}\right).$

This shows that $t(n,1,r)=\Omega(r^{2}\log n/\log r)$ for
$r=\mathcal{O}(\sqrt{n})$, matching the upper bound up to a factor of $\log
r$, and $t(n,1,r)=\Theta(n)$ for $r=\Omega(\sqrt{n})$.

For $w\geq 2$, previous lower bounds were more complicated. Stinson, Wei, and
Zhu [SWZ00] showed that $t(n,w,r)=\Omega(r^{w+1}\log n/\log r)$ if $r$ is
fixed and $n\to\infty$. It was only later determined by Ma and Wei [MW04] that
this result holds for $r=\mathcal{O}(\sqrt{n})$. For $r=\Omega(\sqrt{n})$,
Abdi and Bshouty [AB16] proved the best lower bounds known. They showed that
$t(n,w,r)=\Omega(r^{w+1}\log n/\log^{k+1}r)$ for $\Omega(n^{(k-1)/k})\leq
r\leq\mathcal{O}(n^{k/(k+1)})$ where $2\leq k\leq w$, and
$t(n,w,r)=\Theta(n^{w})$ for $r=\Omega((n\log n)^{w/(w+1)})$.

Using probabilistic arguments, we generalise Theorem 1.6 to $w\geq 2$. This
improves the previous lower bounds for $r=\Omega(\sqrt{n})$.

######  Theorem 1.7.

If $w\geq 1$ is fixed and $1\leq r<n$, then

$t(n,w,r)=\Omega\mathopen{}\mathclose{{}\left(\min\left\\{n^{w},\frac{r^{w+1}\log
n}{\log r}\right\\}}\right).$

This result implies that $t(n,w,r)=\Omega(r^{w+1}\log n/\log r)$ for
$r=\mathcal{O}(n^{w/(w+1)})$ and $t(n,w,r)=\Theta(n^{w})$ for
$r=\Omega(n^{w/(w+1)})$. Theorem 1.5 is an immediate consequence of this
result in combination with Section 1.

The rest of the paper is organised as follows. In Section 2 we prove Theorem
1.7, our lower bound for cover-free families. We use this result in Section 3
to obtain a lower bound on the number of queries of deterministic algorithms,
proving Theorems 1.5 and 1. In Section 4, we then consider randomised
algorithms and prove Theorems 1.2 and 1.3. We finish with some open problems
in Section 5.

Notation. We denote the dual of a family of sets
$\mathcal{F}\subseteq\mathcal{P}(X)$ by
$\mathcal{F}^{*}=\\{\mathcal{F}_{x}:x\in X\\}$ where
$\mathcal{F}_{x}=\\{F\in\mathcal{F}:x\in F\\}$. Moreover, if $G=(V,E)$ is a
graph and $X\subseteq V$, then $G[X]$ is the subgraph of $G$ induced by $X$,
and $N_{G}(X)$ is the neighbourhood of $X$ in $G$.

##  2 Cover-free families

In this section we prove Theorem 1.7 and show that for any fixed $w\geq 1$,

$t(n,w,r)=\Omega\mathopen{}\mathclose{{}\left(\min\left\\{n^{w},\frac{r^{w+1}\log
n}{\log r}\right\\}}\right).$

We split the proof of this result into two regimes. If
$r=\mathcal{O}(\sqrt{n})$, we use Theorem 1.6 to show that
$t(n,w,r)=\Omega(r^{w+1}\log n/\log r)$. We will do this with the following
result.

######  Lemma 2.0.

If $w,r,s\geq 1$ and $w+r\leq n$, it holds that

$t(n,w+1,r+s)\geq\mathopen{}\mathclose{{}\left(\frac{w+r}{w}}\right)^{w}\cdot
t(n-w-r,1,s).$

###### Proof.

Let $\mathcal{F}\subseteq\mathcal{P}(t)$ be a $(w+1,r+s)$-cover-free family
with $n$ sets, and suppose that

$t<\mathopen{}\mathclose{{}\left(\frac{w+r}{w}}\right)^{w}\cdot t(n-w-r,1,s).$

Pick $A_{1},\dots,A_{w}\in\mathcal{F}$ uniformly and independently at random.
Let $\mathcal{A}=\\{A_{1},\dots,A_{w}\\}$. Then, pick
$B_{1},\dots,B_{r}\in\mathcal{F}\setminus\mathcal{A}$ uniformly and
independently at random and let $\mathcal{B}=\\{B_{1},\dots,B_{r}\\}$. For any
$x\in[t]$, if $\alpha_{x}=\lvert\mathcal{F}_{x}\rvert/n$, we have

$\operatorname{\mathbb{P}}(\mathcal{A}\subseteq\mathcal{F}_{x},\mathcal{B}\subseteq\mathcal{F}_{x}^{c})\leq\mathopen{}\mathclose{{}\left(\frac{\lvert\mathcal{F}_{x}\rvert}{n}}\right)^{w}\mathopen{}\mathclose{{}\left(\frac{n-\lvert\mathcal{F}_{x}\rvert}{n-w}}\right)^{r}=\mathopen{}\mathclose{{}\left(\frac{n}{n-w}}\right)^{r}\alpha_{x}^{w}\mathopen{}\mathclose{{}\left(1-\alpha_{x}}\right)^{r}.$

Note that the term
$\alpha_{x}^{w}\mathopen{}\mathclose{{}\left(1-\alpha_{x}}\right)^{r}$ is
maximised by $\alpha_{x}=w/(w+r)$, and so we get

$\operatorname{\mathbb{P}}(\mathcal{A}\subseteq\mathcal{F}_{x},\mathcal{B}\subseteq\mathcal{F}_{x}^{c})\leq\mathopen{}\mathclose{{}\left(\frac{n}{n-w}}\right)^{r}\mathopen{}\mathclose{{}\left(\frac{w}{w+r}}\right)^{w}\mathopen{}\mathclose{{}\left(\frac{r}{w+r}}\right)^{r}\leq\mathopen{}\mathclose{{}\left(\frac{w}{w+r}}\right)^{w},$

where the last inequality used the fact that $w+r\leq n$. Thus, if

$X=\\{x\in[t]:\mathcal{A}\subseteq\mathcal{F}_{x},\mathcal{B}\subseteq\mathcal{F}_{x}^{c}\\},$

then $\operatorname{\mathbb{E}}(\lvert X\rvert)\leq(w/(w+r))^{w}\cdot
t<t(n-w-r,1,s)$, and so with positive probability we have $\lvert
X\rvert<t(n-w-r,1,s)$. This implies that the sets $F\cap X$ with
$F\in\mathcal{F}\setminus(\mathcal{A}\cup\mathcal{B})$ cannot form a
$(1,s)$-cover-free family444Note that it could happen that $F\cap
X=F^{\prime}\cap X$ for some distinct
$F,F^{\prime}\in\mathcal{F}\setminus(\mathcal{A}\cup\mathcal{B})$. In that
case, we could simply pick $A_{w+1}=F$ and $C_{1}=\dots=C_{s}=F^{\prime}$ in
the argument that follows., and so there exist
$A_{w+1}\in\mathcal{F}\setminus(\mathcal{A}\cup\mathcal{B})$ and
$C_{1},\dots,C_{s}\in\mathcal{F}\setminus(\mathcal{A}\cup\mathcal{B}\cup\\{A_{w+1}\\})$
such that

$A_{w+1}\cap X\subseteq\bigcup_{i=1}^{s}(C_{i}\cap
X)\subseteq\bigcup_{i=1}^{s}C_{i}.$

Now, suppose that $x\in\bigcap_{i=1}^{w+1}A_{i}$. If $x\notin X$, we must have
$x\in\bigcup_{i=1}^{r}B_{i}$. Otherwise $x\in X$, so $x\in A_{w+1}\cap X$ and
therefore $x\in\bigcup_{i=1}^{s}C_{i}$. So,

$\bigcap_{i=1}^{w+1}A_{i}\subseteq\bigcup_{i=1}^{r}B_{i}\cup\bigcup_{i=1}^{s}C_{i}.$

This contradicts the fact that $\mathcal{F}$ is $(w+1,r+s)$-cover-free. ∎

If $r=\Omega(\sqrt{n})$, then $\log r=\Theta(\log n)$, and so the lower bound
we want to show simplifies to $t(n,w,r)=\Omega(\min\\{n^{w},r^{w+1}\\})$.
Using arguments very similar to the proof of the previous lemma, we show that
this is true.

######  Lemma 2.0.

If $w,r,s\geq 1$ and $w+r\leq n$, it holds that

$t(n,w,r+s)\geq\min\left\\{\frac{1}{2}\mathopen{}\mathclose{{}\left(\frac{n}{w}}\right)^{w},\frac{s}{2}\mathopen{}\mathclose{{}\left(\frac{w+r}{w}}\right)^{w}\right\\}.$

###### Proof.

Let $\mathcal{F}\subseteq\mathcal{P}(t)$ be a $(w,r+s)$-cover-free family with
$n$ sets, and suppose that

$t<\min\left\\{\frac{1}{2}\mathopen{}\mathclose{{}\left(\frac{n}{w}}\right)^{w},\frac{s}{2}\mathopen{}\mathclose{{}\left(\frac{w+r}{w}}\right)^{w}\right\\}.$

We proceed as in the proof of Section 2. Pick
$A_{1},\dots,A_{w}\in\mathcal{F}$ uniformly at random and let
$\mathcal{A}=\\{A_{1},\dots,A_{w}\\}$. Then, pick
$B_{1},\dots,B_{r}\in\mathcal{F}\setminus\mathcal{A}$ uniformly at random and
let $\mathcal{B}=\\{B_{1},\dots,B_{r}\\}$. For any $x\in[t]$, we have

$\operatorname{\mathbb{P}}(\mathcal{A}\subseteq\mathcal{F}_{x},\mathcal{B}\subseteq\mathcal{F}_{x}^{c})\leq\mathopen{}\mathclose{{}\left(\frac{w}{w+r}}\right)^{w}.$

Thus, if
$X=\\{x\in[t]:\mathcal{A}\subseteq\mathcal{F}_{x},\mathcal{B}\subseteq\mathcal{F}_{x}^{c}\\}$,
then $\operatorname{\mathbb{E}}(\lvert X\rvert)\leq(w/(w+r))^{w}\cdot t\leq
s/2$, and so $\operatorname{\mathbb{P}}(\lvert X\rvert>s)\leq 1/2$. Moreover,
the event $\\{\mathcal{A}=\mathcal{F}_{x}\\}$ can only happen if
$\lvert\mathcal{F}_{x}\rvert\leq w$, and in that case we have
$\operatorname{\mathbb{P}}(\mathcal{A}=\mathcal{F}_{x})\leq(w/n)^{w}$. So,

$\operatorname{\mathbb{P}}(\mathcal{A}=\mathcal{F}_{x}\text{ for some
}x\in[t])\leq
t\cdot\mathopen{}\mathclose{{}\left(\frac{w}{n}}\right)^{w}<\frac{1}{2}.$

This implies that with positive probability we have $\lvert X\rvert\leq s$ and
$\mathcal{A}\neq\mathcal{F}_{x}$ for all $x\in[t]$. Note that for each $x\in
X$ we have $\mathcal{A}\subseteq\mathcal{F}_{x}$, and so there must exist some
$C_{x}\in\mathcal{F}_{x}\setminus\mathcal{A}$.

Now, suppose that $x\in\bigcap_{i=1}^{w}A_{i}$. If $x\notin X$, we must have
$x\in\bigcup_{i=1}^{r}B_{i}$. Otherwise $x\in X$, and so $x\in C_{x}$.
Therefore,

$\bigcap_{i=1}^{w}A_{i}\subseteq\bigcup_{i=1}^{r}B_{i}\cup\bigcup_{x\in
X}C_{x}.$

This contradicts the fact that $\mathcal{F}$ is $(w,r+s)$-cover-free. ∎

Putting these two lemmas together, we obtain the desired result.

###### Proof of Theorem 1.7.

If $r=\mathcal{O}(\sqrt{n})$, Section 2 together with Theorem 1.6 implies that

$t(n,w,r)\geq\mathopen{}\mathclose{{}\left(\frac{w-1+\left\lceil\frac{r}{2}\right\rceil}{w-1}}\right)^{w-1}\cdot
t\mathopen{}\mathclose{{}\left(n+1-w-\left\lceil\frac{r}{2}\right\rceil,1,\left\lfloor\frac{r}{2}\right\rfloor}\right)=\Omega\mathopen{}\mathclose{{}\left(\frac{r^{w+1}\log
n}{\log r}}\right).$

Otherwise, if $r=\Omega(\sqrt{n})$, Section 2 shows that

$t(n,w,r)\geq\min\left\\{\frac{1}{2}\mathopen{}\mathclose{{}\left(\frac{n}{w}}\right)^{w},\frac{\left\lfloor\frac{r}{2}\right\rfloor}{2}\mathopen{}\mathclose{{}\left(\frac{w+\left\lceil\frac{r}{2}\right\rceil}{w}}\right)^{w}\right\\}=\Omega\mathopen{}\mathclose{{}\left(\min\left\\{n^{w},\frac{r^{w+1}\log
n}{\log r}\right\\}}\right).\qed$

##  3 Deterministic non-adaptive algorithms

In this section, we use the lower bound for cover-free families to prove a
lower bound on the number of queries of deterministic non-adaptive algorithms.
Formally, such an algorithm corresponds to a family of queries
$\mathcal{Q}\subseteq\mathcal{P}(V)$ with the following property: for all
distinct graphs $G$ and $H$ with maximum degree $\Delta$ there exists a query
$Q\in\mathcal{Q}$ such that no set of vertices is a maximal independent set of
both $G[Q]$ and $H[Q]$. We call such a family $\mathcal{Q}$ a _query scheme_.

To bound the number of queries in such schemes, we relate them to cover-free
families. Our main observation is that a family of queries
$\mathcal{Q}\subseteq\mathcal{P}(V)$ is a query scheme if and only if its dual
$\mathcal{Q}^{*}$ is $(2,r)$-cover-free for $r\approx 2\Delta$. This was
essentially already proved by Konrad, O’Sullivan, and Traistaru [KOT24], but
with different terminology. We provide a proof of the direction necessary for
the lower bound in Section 1.

######  Lemma 3.0.

If $\mathcal{Q}\subseteq\mathcal{P}(V)$ is a query scheme, then
$\mathcal{Q}^{*}$ is $(2,2\Delta-2)$-cover-free.

###### Proof.

If $\mathcal{Q}^{*}$ is not $(2,2\Delta-2)$-cover-free, there exist two
distinct vertices $u,v\in V$ and a set of vertices $W\subseteq
V\setminus\\{u,v\\}$ with $\lvert W\rvert\leq 2\Delta-2$ such that
$\mathcal{Q}_{u}\cap\mathcal{Q}_{v}\subseteq\bigcup_{w\in W}\mathcal{Q}_{w}$.
Let $G$ be a graph with the least number of edges that has maximum degree
$\Delta-1$ and satisfies $N_{G}(\\{u,v\\})=W$. Let $H=G\cup\\{uv\\}$.

For every $Q\in\mathcal{Q}$, let $I_{Q}$ be a maximal independent set of
$G[Q]$ with $Q\setminus\\{u,v\\}\subseteq I_{Q}$. We claim that $I_{Q}$ is
also a maximal independent set of $H[Q]$. Indeed, otherwise we must have
$u,v\in I_{Q}\subseteq Q$. Then,
$Q\in\mathcal{Q}_{u}\cap\mathcal{Q}_{v}\subseteq\bigcup_{w\in
W}\mathcal{Q}_{w}$, and so $W\cap Q\neq\varnothing$. This implies that

$N_{G}(\\{u,v\\})\cap I_{Q}=W\cap I_{Q}\supseteq
W\cap(Q\setminus\\{u,v\\})=W\cap Q\neq\varnothing.$

Since $u,v\in I_{Q}$, this contradicts the fact that $I_{Q}$ is an independent
set of $G$. So, for all $Q\in\mathcal{Q}$, $I_{Q}$ is a maximal independent
set of both $G[Q]$ and $H[Q]$. This contradicts the fact that $\mathcal{Q}$ is
a query scheme. ∎

Using arguments from Konrad, O’Sullivan, and Traistaru [KOT24], we can obtain
the following converse.

######  Lemma 3.0.

Let $\mathcal{Q}\subseteq\mathcal{P}(V)$. If $\mathcal{Q}^{*}$ is
$(2,2\Delta)$-cover-free, then $\mathcal{Q}$ is a query scheme.

Using these two results, we can now prove Section 1. Together with Theorem
1.7, this proves Theorem 1.5.

###### Proof of Section 1.

Let $\mathcal{Q}\subseteq\mathcal{P}(V)$ be a query scheme. Then, by Section
3, we know that $\mathcal{Q}^{*}\subseteq\mathcal{P}(\mathcal{Q})$ is
$(2,2\Delta-2)$-cover-free, and so

$\lvert\mathcal{Q}\rvert\geq
t(\lvert\mathcal{Q}^{*}\rvert,2,2\Delta-2)=t(n,2,2\Delta-2).$

On the other hand, if $t=t(n,2,2\Delta)$, there exist a family
$\mathcal{R}\subseteq\mathcal{P}(t)$ with $\lvert\mathcal{R}\rvert=n$ that is
$(2,2\Delta)$-cover-free. By identifying $\mathcal{R}$ with $V$, we obtain a
family $\mathcal{Q}=\mathcal{R}^{*}\subseteq\mathcal{P}(V)$ with
$\lvert\mathcal{Q}\rvert=t$ such that $\mathcal{Q}^{*}\cong\mathcal{R}$ is
$(2,2\Delta)$-cover-free. Then, by Section 3, $\mathcal{Q}$ is a query scheme
with $t=t(n,2,2\Delta)$ queries. ∎

##  4 Randomised algorithms

Finally, we want to lower bound the number of queries of randomised
algorithms, both in the adaptive and non-adaptive setting. We begin with some
general observations.

First, note that any randomised algorithm $\mathcal{A}$ can randomly decide in
advance for every possible execution path which set of vertices it wants to
query next. This gives a deterministic strategy $S$ that the algorithm will
then perform to reconstruct the graph. From now on, we will assume that every
algorithm is of this form. That is, $\mathcal{A}$ randomly selects in advance
a deterministic strategy $S\in\mathcal{S}$ from some family of strategies
$\mathcal{S}$, and it will then execute this strategy to reconstruct the
graph.

The following lemma tells us that by analysing the strategies
$S\in\mathcal{S}$ separately, we can show that there is a graph that will
likely be incorrectly reconstructed by $\mathcal{A}$.

######  Lemma 4.0.

Let $\mathcal{G}$ be a family of graphs and $\mathcal{S}$ be a family of
strategies of a randomised algorithm $\mathcal{A}$. If $G\in\mathcal{G}$ is a
random graph, then there exists a graph $H\in\mathcal{G}$ such that

$\operatorname{\mathbb{P}}(\mathcal{A}\text{ reconstructs
}H)\leq\sup_{S\in\mathcal{S}}\operatorname{\mathbb{P}}(S\text{ reconstructs
}G).$

###### Proof.

Let $p=\sup_{S\in\mathcal{S}}\operatorname{\mathbb{P}}(S\text{ reconstructs
}G)$. Denote the indicator variable of an event $E$ by
$\mathnormal{\mathbbm{1}}_{E}$. Then, it holds that

$\displaystyle\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left(\mathnormal{\mathbbm{1}}_{\\{\mathcal{A}\text{
reconstructs }G\\}}}\right)$
$\displaystyle=\sum_{S\in\mathcal{S}}\operatorname{\mathbb{P}}(\mathcal{A}\text{
selects
}S)\cdot\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left(\mathnormal{\mathbbm{1}}_{\\{S\text{
reconstructs }G\\}}}\right)$
$\displaystyle=\sum_{S\in\mathcal{S}}\operatorname{\mathbb{P}}(\mathcal{A}\text{
selects }S)\cdot\operatorname{\mathbb{P}}(S\text{ reconstructs }G)$
$\displaystyle\leq\sum_{S\in\mathcal{S}}\operatorname{\mathbb{P}}(\mathcal{A}\text{
selects }S)\cdot p=p.$

In particular, there exists a graph $H\in\mathcal{G}$ such that

$\operatorname{\mathbb{P}}(\mathcal{A}\text{ reconstructs
}H)=\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left(\mathnormal{\mathbbm{1}}_{\\{\mathcal{A}\text{
reconstructs }H\\}}}\right)\leq p.\qed$

###  4.1 Randomised adaptive algorithms

We start by providing a lower bound on the number of queries of a randomised
adaptive algorithm. For this, we will consider the family of graphs that
contain a clique $U$ of size $\Theta(\Delta)$ while $V\setminus U$ is an
independent set.

Then, for every query $Q\subseteq V$ of the algorithm, either
$Q\cap(V\setminus U)$ is a maximal independent set, or there is a vertex $u\in
Q\cap U$ such that $(Q\cap(V\setminus U))\cup\\{u\\}$ is a maximal independent
set. So, the answer to a query will always be one out of at most
$\Theta(\Delta)$ many alternatives. This implies that with $t$ queries, the
algorithm can correctly reconstruct at most $\mathcal{O}(\Delta^{t})$ many
graphs. By counting the number of graphs in our family, this yields the
desired lower bound on $t$.

###### Proof of Theorem 1.2.

Let $U\subseteq V$ be a set with $\lvert U\rvert=\lceil\Delta/2\rceil$ and let
$\mathcal{G}$ be the family of graphs $G$ with maximum degree $\Delta$ such
that $U$ is a clique of $G$ and $V\setminus U$ is an independent set of $G$.
Since every vertex of $U$ can have up to $\Delta-(\lvert U\rvert-1)$
neighbours in $V\setminus U$, we get

$\lvert\mathcal{G}\rvert\geq\binom{n-\lvert U\rvert}{\Delta-(\lvert
U\rvert-1)}^{\lvert
U\rvert}\geq\binom{n-\Delta}{\lceil\frac{\Delta}{2}\rceil}^{\lceil\frac{\Delta}{2}\rceil}\geq\mathopen{}\mathclose{{}\left(\frac{n-\Delta}{\lceil\frac{\Delta}{2}\rceil}}\right)^{\lceil\frac{\Delta}{2}\rceil^{2}}\geq\mathopen{}\mathclose{{}\left(\frac{n-\Delta}{\Delta}}\right)^{\frac{\Delta^{2}}{4}}.$

Now, let $\mathcal{S}$ be the family of strategies of a randomised adaptive
algorithm $\mathcal{A}$ with success probability at least $1/2$, and suppose
that $\mathcal{A}$ makes at most $t$ queries. Pick a graph $G\in\mathcal{G}$
uniformly at random, and fix a strategy $S\in\mathcal{S}$.

For every possible query $Q\subseteq V$, note that either $Q\cap(V\setminus
U)$ is a maximal independent set of $G[Q]$, or there is a vertex $u\in Q\cap
U$ such that $(Q\cap(V\setminus U))\cup\\{u\\}$ is a maximal independent set
of $G[Q]$. So, when executing $S$ on graphs from $\mathcal{G}$, the answer to
each query of $S$ is always one out of $\lvert Q\cap U\rvert+1\leq\Delta+1$
different sets. Since $S$ is deterministic and makes at most $t$ queries, it
follows that $S$ will correctly reconstruct at most $(\Delta+1)^{t}$ graphs
from $\mathcal{G}$. Therefore,

$\operatorname{\mathbb{P}}(S\text{ reconstructs
}G)\leq\frac{(\Delta+1)^{t}}{\lvert\mathcal{G}\rvert}.$

Given that the success probability of $\mathcal{A}$ is at least $1/2$, it
follows by Section 4 that $(\Delta+1)^{t}/\lvert\mathcal{G}\rvert\geq 1/2$. If
$\Delta\leq n/3$, this implies that

$t\geq\frac{\log\mathopen{}\mathclose{{}\left(\frac{\lvert\mathcal{G}\rvert}{2}}\right)}{\log(\Delta+1)}\geq\frac{\Delta^{2}\log\mathopen{}\mathclose{{}\left(\frac{n-\Delta}{\Delta}}\right)-4\log
2}{4\log(\Delta+1)}=\Omega\mathopen{}\mathclose{{}\left(\frac{\Delta^{2}\log\mathopen{}\mathclose{{}\left(\frac{n}{\Delta}}\right)}{\log\Delta}}\right).$

For $\Delta\geq n/3$, we can simply apply this argument with $\Delta=n/3$ to
obtain the desired lower bound. ∎

###  4.2 Randomised non-adaptive algorithms

To obtain a lower bound on the number of queries of a randomised non-adaptive
algorithm, we adapt the arguments of the proof from the last section. In this
proof, recall that the answer to a query $Q$ of the algorithm is always one
out of $\lvert Q\cap U\rvert+1$ many alternatives. We used that this is at
most $\Delta+1$, but if $Q\cap U$ is much smaller than this for most queries,
then we should get a better lower bound on the number of queries.

For adaptive algorithms, we cannot hope for this to be true because such
algorithms can easily identify $U$ with the first query and then always ensure
that $U\subseteq Q$. For non-adaptive algorithms, however, a randomly chosen
$U$ will usually have a very small intersection with a query $Q$ of the
algorithm, unless $Q$ is large. But if $Q$ is large, then most vertices of $U$
will have a neighbour in $Q$ which again restricts the number of possible
answers to the query. Using this idea, we can improve the lower bound on the
number of queries for non-adaptive algorithms by a factor of $\log\Delta$.

###### Proof of Theorem 1.3.

For disjoint sets $U,W\subseteq V$ with $\lvert U\rvert=\lceil\Delta/3\rceil$
and $\lvert W\rvert=\lfloor\Delta/3\rfloor$, let $\mathcal{G}_{U,W}$ be the
family of graphs $G$ with maximum degree $\Delta$ such that $U$ is a clique of
$G$, $V\setminus U$ is an independent set of $G$, and all vertices in $U$ are
connected to all vertices in $W$. Let $\mathcal{G}$ be the union of all the
families $\mathcal{G}_{U,W}$. Note that

$N=\lvert\mathcal{G}_{U,W}\rvert\geq\binom{n-\lvert U\rvert-\lvert
W\rvert}{\Delta-(\lvert U\rvert-1)-\lvert W\rvert}^{\lvert
U\rvert}\geq\binom{n-\Delta}{\lceil\frac{\Delta}{3}\rceil}^{\lceil\frac{\Delta}{3}\rceil}\geq\mathopen{}\mathclose{{}\left(\frac{n-\Delta}{\Delta}}\right)^{\frac{\Delta^{2}}{9}}.$

Let $\mathcal{S}$ be the family of strategies of a randomised non-adaptive
algorithm $\mathcal{A}$ with success probability at least $1/2$, and suppose
that $\mathcal{A}$ makes at most $t$ queries. Pick a graph $G\in\mathcal{G}$
at random by first picking the sets $U,W\subseteq V$ uniformly at random and
then picking $G\in\mathcal{G}_{U,W}$ uniformly at random. Fix a strategy
$S\in\mathcal{S}$. Since $\mathcal{A}$ is non-adaptive, the strategy $S$
corresponds of a family of queries $\mathcal{Q}\subseteq\mathcal{P}(V)$ with
$\lvert\mathcal{Q}\rvert\leq t$.

For every query $Q\in\mathcal{Q}$, note that $Q\cap(V\setminus U)$ is a
maximal independent set of $G[Q]$ whenever $Q\cap W\neq\varnothing$.
Otherwise, either $Q\cap(V\setminus U)$ or $(Q\cap(V\setminus U))\cup\\{u\\}$
for some $u\in Q\cap U$ is a maximal independent set of $G[Q]$. So, when
executing $S$ on graphs from $\mathcal{G}_{U,W}$, the answer to each query
$Q\in\mathcal{Q}$ is always one out of $D_{Q}$ different sets, where $D_{Q}=1$
if $Q\cap W\neq\varnothing$ and $D_{Q}=\lvert Q\cap U\rvert+1$ otherwise. It
follows that, $S$ will correctly reconstruct at most
$D=\prod_{Q\in\mathcal{Q}}D_{Q}$ graphs from $\mathcal{G}_{U,W}$. Therefore,
for any $M\geq 0$,

$\operatorname{\mathbb{P}}\mathopen{}\mathclose{{}\left(S\text{ reconstructs
}G\mathrel{|}D\leq M}\right)\leq\frac{M}{N}.$

Note that

$D_{Q}=1+\sum_{u\in U}\mathnormal{\mathbbm{1}}_{\\{u\in Q,W\subseteq
Q^{c}\\}}.$

Therefore,

$\operatorname{\mathbb{E}}(\log D_{Q})\leq\operatorname{\mathbb{E}}(D_{Q})\leq
1+\sum_{u\in
U}\operatorname{\mathbb{E}}\mathopen{}\mathclose{{}\left(\mathnormal{\mathbbm{1}}_{\\{u\in
Q,W\subseteq Q^{c}\\}}}\right)=1+\sum_{u\in U}\operatorname{\mathbb{P}}(u\in
Q,W\subseteq Q^{c}).$

Let $\alpha_{Q}=\lvert Q\rvert/n$. Since $U$ and $W$ are chosen uniformly at
random, we have

$\operatorname{\mathbb{P}}(u\in Q,W\subseteq Q^{c})\leq\frac{\lvert
Q\rvert}{n}\mathopen{}\mathclose{{}\left(\frac{n-\lvert
Q\rvert}{n-1}}\right)^{\lvert
W\rvert}=\mathopen{}\mathclose{{}\left(\frac{n}{n-1}}\right)^{\lvert
W\rvert}\alpha_{Q}(1-\alpha_{Q})^{\lvert W\rvert}.$

The term $\alpha_{Q}(1-\alpha_{Q})^{\lvert W\rvert}$ is maximised by
$\alpha_{Q}=1/(\lvert W\rvert+1)$, and so we get

$\operatorname{\mathbb{P}}(u\in Q,W\subseteq
Q^{c})\leq\mathopen{}\mathclose{{}\left(\frac{n}{n-1}}\right)^{\lvert
W\rvert}\frac{1}{\lvert W\rvert+1}\mathopen{}\mathclose{{}\left(\frac{\lvert
W\rvert}{\lvert W\rvert+1}}\right)^{\lvert W\rvert}\leq\frac{1}{\lvert
W\rvert+1}\leq\frac{3}{\Delta}.$

It follows that $\operatorname{\mathbb{E}}(\log D_{Q})\leq 1+3\lvert
U\rvert/\Delta\leq 4$ and therefore, by Markov’s inequality,

$\operatorname{\mathbb{P}}\mathopen{}\mathclose{{}\left(D\geq
e^{16t}}\right)=\operatorname{\mathbb{P}}\mathopen{}\mathclose{{}\left(\sum_{Q\in\mathcal{Q}}\log
D_{Q}\geq
16t}\right)\leq\frac{\operatorname{\mathbb{E}}(\sum_{Q\in\mathcal{Q}}\log
D_{Q})}{16t}\leq\frac{4t}{16t}=\frac{1}{4}.$

Overall, we get

$\displaystyle\operatorname{\mathbb{P}}(S\text{ reconstructs }G)$
$\displaystyle\leq\operatorname{\mathbb{P}}\mathopen{}\mathclose{{}\left(D\geq
e^{16t}}\right)+\operatorname{\mathbb{P}}\mathopen{}\mathclose{{}\left(S\text{
reconstructs }G\mathrel{|}D\leq
e^{16t}}\right)\operatorname{\mathbb{P}}\mathopen{}\mathclose{{}\left(D\leq
e^{16t}}\right)$ $\displaystyle\leq\frac{1}{4}+\frac{e^{16t}}{N}.$

Given that the success probability of $\mathcal{A}$ is at least $1/2$, it
follows by Section 4 that $e^{16t}/N\geq 1/4$. If $\Delta\leq n/3$, this
implies that

$t\geq\frac{1}{16}\log\mathopen{}\mathclose{{}\left(\frac{N}{4}}\right)\geq\frac{\Delta^{2}}{144}\log\mathopen{}\mathclose{{}\left(\frac{n-\Delta}{\Delta}}\right)-\frac{1}{16}\log
4=\Omega\mathopen{}\mathclose{{}\left(\Delta^{2}\log\mathopen{}\mathclose{{}\left(\frac{n}{\Delta}}\right)}\right).$

For $\Delta\geq n/3$, we can simply apply this argument with $\Delta=n/3$ to
obtain the desired lower bound. ∎

##  5 Open problems

In this paper, we improved the lower bounds on the number of queries required
for graph reconstruction with maximal independent set queries. However, some
gaps between the lower and upper bounds remain.

For deterministic non-adaptive algorithms, we showed that
$\Omega(\Delta^{3}\log n/\log\Delta)$ queries are necessary while the upper
bound $\mathcal{O}(\Delta^{3}\log n)$ was given by Konrad, O’Sullivan, and
Traistaru [KOT24]. This is the same gap as the longstanding gap between the
lower and upper bounds $\Omega(r^{w+1}\log n/\log r)\leq
t(n,w,r)\leq\mathcal{O}(r^{w+1}\log n)$ for cover-free families.

######  Problem 5.0.

Are there $(1,r)$-cover-free families $\mathcal{F}\subseteq\mathcal{P}(t)$
with $t\in\mathcal{O}(r^{2}\log\lvert\mathcal{F}\rvert/\log r)$?

For randomised non-adaptive algorithms, the upper bound of Konrad, O’Sullivan,
and Traistaru [KOT24] is $\mathcal{O}(\Delta^{2}\log n)$. We proved that such
algorithms need at least $\Omega(\Delta^{2}\log(n/\Delta))$ queries, and ask
whether this is tight.

######  Problem 5.0.

Is there a randomised non-adaptive algorithm which uses
$\mathcal{O}(\Delta^{2}\log(n/\Delta))$ queries to reconstruct any graph of
maximum degree $\Delta$ with high probability?

Finally, for adaptive algorithms, we have the same upper bounds as for non-
adaptive algorithms in both the deterministic and randomised setting. However,
our best lower bound drops to $\Omega(\Delta^{2}\log(n/\Delta)/\log\Delta)$ in
both settings. This suggests that adaptive algorithms might perform better
than their non-adaptive counterparts.

######  Problem 5.0.

Is there a deterministic adaptive algorithm that uses
$o(\Delta^{3}\log(n/\Delta))$ queries to reconstruct any graph of maximum
degree $\Delta$?

## References

  * [AA05] Noga Alon and Vera Asodi (2005).  Learning a hidden subgraph.  _SIAM Journal on Discrete Mathematics_ 18(4), 697–712.
  * [AB16] Ali Z. Abdi and Nader H. Bshouty (2016).  Lower bounds for cover-free families.  _Electronic Journal of Combinatorics_ 23(2), Paper 2.45, 7.
  * [AB19] Hasan Abasi and Nader H. Bshouty (2019).  On learning graphs with edge-detecting queries.  _Proceedings of the 30th International Conference on Algorithmic Learning Theory_ , _PMLR_ , vol. 98, 3–30.
  * [ABK+04] Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov (2004).  Learning a hidden matching.  _SIAM Journal on Computing_ 33(2), 487–501.
  * [ABM14] Hasan Abasi, Nader H. Bshouty, and Hanna Mazzawi (2014).  On exact learning monotone DNF from membership queries.  _Algorithmic learning theory_ , _Lecture Notes in Computer Science_ , vol. 8776, 111–124.
  * [AC06] Dana Angluin and Jiang Chen (2006).  Learning a hidden hypergraph.  _Journal of Machine Learning Research_ 7, 2215–2236.
  * [AC08] Dana Angluin and Jiang Chen (2008).  Learning a hidden graph using $O(\log n)$ queries per edge.  _Journal of Computer and System Sciences_ 74(4), 546–556.
  * [AJS19] Matthew Aldridge, Oliver Johnson, and Jonathan Scarlett (2019).  Group testing: an information theory perspective.  _Foundations and Trends in Communications and Information Theory_ 15(3-4), 196–392.
  * [DFFT95] Martin Dyer, Trevor Fenner, Alan Frieze, and Andrew Thomason (1995).  On key storage in secure networks.  _Journal of Cryptology_ 8, 189–200.
  * [DH00] Ding-Zhu Du and Frank K. Hwang (2000).  Combinatorial group testing and its applications, _Series on Applied Mathematics_ , vol. 12.  Second edn. (World Scientific Publishing Co., Inc., River Edge, NJ).
  * [DH06] Ding-Zhu Du and Frank K. Hwang (2006).  Pooling designs and nonadaptive group testing, _Series on Applied Mathematics_ , vol. 18 (World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ).  Important tools for DNA sequencing.
  * [DR82] A. G. D’yachkov and V. V. Rykov (1982).  Bounds on the length of disjunctive codes.  _Problems of Information Transmission_ 18(3), 166–171.
  * [Eng96] Konrad Engel (1996).  Interval packing and covering in the Boolean lattice.  _Combinatorics, Probability and Computing_ 5(4), 373–384.
  * [Fei06] Uriel Feige (2006).  On sums of independent random variables with unbounded variance and estimating the average degree in a graph.  _SIAM Journal on Computing_ 35(4), 964–984.
  * [Für96] Zoltán Füredi (1996).  On $r$-cover-free families.  _Journal of Combinatorial Theory. Series A_ 73(1), 172–173.
  * [GR08] Oded Goldreich and Dana Ron (2008).  Approximating average parameters of graphs.  _Random Structures & Algorithms_ 32(4), 473–493.
  * [HS87] F. K. Hwang and V. T. Sós (1987).  Non-adaptive hypergeometric group testing.  _Studia Scientiarum Mathematicarum Hungarica_ 22, 257–263.
  * [KK20] Lidiya Khalidah binti Khalil and Christian Konrad (2020).  Constructing large matchings via query access to a maximal matching oracle.  _40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science_ , _Leibniz International Proceedings in Informatics (LIPIcs)_ , vol. 182, Art. No. 26, 15.
  * [KNS23] Christian Konrad, Kheeran K. Naidu, and Arun Steward (2023).  Maximum matching via maximal matching queries.  _40th International Symposium on Theoretical Aspects of Computer Science_ , _Leibniz International Proceedings in Informatics (LIPIcs)_ , vol. 254, Art. No. 41, 22.
  * [KOT24] Christian Konrad, Conor O’Sullivan, and Victor Traistaru (2024).  Graph Reconstruction via MIS Queries.  arXiv:2401.05845.
  * [KS64] William Kautz and Roy Singleton (1964).  Nonrandom binary superimposed codes.  _IEEE Transactions on Information Theory_ 10(4), 363–377.
  * [MP88] Chris J. Mitchell and Fred C. Piper (1988).  Key storage in secure networks.  _Discrete Applied Mathematics_ 21(3), 215–228.
  * [MW04] X. Ma and R. Wei (2004).  On a bound of cover-free families.  _Designs, Codes and Cryptography_ 32(1-3), 303–321.
  * [Rus94] Miklós Ruszinkó (1994).  On the upper bound of the size of the $r$-cover-free families.  _Journal of Combinatorial Theory. Series A_ 66(2), 302–310.
  * [STW00] D. R. Stinson, Tran van Trung, and R. Wei (2000).  Secure frameproof codes, key distribution patterns, group testing algorithms and related structures.  _Journal of Statistical Planning and Inference_ 86(2), 595–617.
  * [SW04] D. R. Stinson and R. Wei (2004).  Generalized cover-free families.  _Discrete Mathematics_ 279(1-3), 463–477.
  * [SWZ00] D. R. Stinson, R. Wei, and L. Zhu (2000).  Some new bounds for cover-free families.  _Journal of Combinatorial Theory. Series A_ 90(1), 224–234.
  * [Wei06] Ruizhong Wei (2006).  On cover-free families.  arXiv:2303.17524.


# Optimization of Speed and Network Deployment for Reliable V2I Communication
in the Presence of Handoffs and Interference

Haider Shoaib, Student Member, IEEE, and Hina Tabassum, Senior Member, IEEE H.
Shoaib and H. Tabassum are with the Department of Electrical Engineering and
Computer Science, York University, ON, Canada (e-mail<EMAIL_ADDRESS>hinat@yorku.ca).

###### Abstract

Vehicle-to-infrastructure (V2I) communication is becoming indispensable for
successful roll-out of connected and autonomous vehicles (CAVs). While
increasing the CAVs’ speed improves the average CAV traffic flow, it increases
communication handoffs (HOs) thus reducing wireless data rates. Furthermore,
unplanned density of active base-stations (BSs) may result in severe
interference which negatively impacts CAV data rate. In this letter, we first
characterize macroscopic traffic flow by considering log-normal distribution
of the spacing between CAVs. We then derive novel closed-form expressions for
the exact HO-aware rate outage probability and ergodic capacity in a large-
scale network with interference. Then, we formulate a traffic flow
maximization problem to optimize the speed of CAVs and deployment density of
BSs with HO-aware rate constraints and collision avoidance constraints. Our
numerical results validate the closed-form analytical expressions, extract
useful insights about the optimal speed and BS density, and highlight the key
trade-offs between the HO-aware data rates and CAV traffic flow.

###### Index Terms:

Connected automated vehicles, vehicular networks, network planning, handoffs,
handoff-aware data rate, traffic flow, speed optimization, interference.

##  I Introduction

Vehicle-to-infrastructure (V2I) communication is pivotal to enable autonomous
and well-informed decision-making in connected and autonomous vehicles (CAVs);
thus, improving road safety and traffic flow [1]. Nevertheless, optimizing the
speed of CAVs while maximizing the CAV traffic flow and achieving reliable
connectivity at the same time is challenging. The reason is that while
increasing the CAVs’ speed improves the traffic flow, it also increases
communication handoffs (HOs) as the CAVs switch from one base-station (BS) to
another, thus reducing data rates. Furthermore, unplanned deployment of
network infrastructure such as roadside units or BSs may result in severe
interference which negatively impacts CAV data rate [2]. A fundamental trade-
off thus exists between the communication data rates and CAV traffic flow. In
this context, this letter aims to answer the following questions, i.e., (i)
how to analyze the performance of V2I communication considering HOs and
interference? and (ii) what is the optimal BS density and average CAV speed
that maximize traffic flow?

Prior research works in the realm of V2I communications have considered
mobility in terms of data rates, however traffic flow is typically overlooked.
For instance, in [3], Arshad et al. derived HO-aware data rates as a function
of the speed of the user device and the HO cost from the BSs. In [2], Hossan
et al. presented a stochastic geometry framework to derive the HO-aware
coverage probability of a two-tier wireless network with RF and THz BSs. In
[4], Lin et al. proposed a random way-point mobility model to characterize the
HO rate and sojourn time using stochastic geometry considering randomly
distributed BSs. Recently, in [5], Yan et al. proposed a reinforcement
learning approach for joint V2I network selection and autonomous driving
policies considering both RF and THz BSs. Their results demonstrated inter-
dependency of a CAV’s motion dynamics, HOs, and data rate to adopt safe
driving behaviours for CAVs.

Another series of research contributions characterizes traffic flow using
macroscopic models [6, 7], however V2I communications is typically overlooked.

None of the aforementioned research works considered the problem of CAVs
traffic flow maximization with log-normally distributed CAVs’ spacing and HO-
aware data rate constraints in a large-scale interference-limited wireless
network. To this end, our contributions can be summarized as follows:

$\bullet$ We characterize macroscopic traffic flow by considering log-normal
distribution of the spacing between CAVs. We then derive novel and tractable
closed-form expressions for the probability density function (PDF) and
cumulative density function (CDF) of signal-to-interference-plus-noise ratio
(SINR), HO-aware rate outage probability and ergodic capacity in a large-scale
network with interference. The derived expressions capture the network
parameters such as height of the BSs, safety distance of BSs from the road,
interference from neighboring BSs, and channel fading.

$\bullet$ We develop a novel optimization framework to jointly optimize the
deployment density of the BSs and speed of CAVs to maximize the CAVs’ traffic
flow with collision avoidance and minimum HO-aware data rate constraints.

$\bullet$ Numerical results confirm the accuracy of the derived expressions
and extract useful insights related to dynamics of BS density, CAV minimum
data rate requirements, average CAV speed, BS heights and safety distances,
etc.

##  II System Model and Performance Metrics

Figure 1: Graphical illustration of the V2I communication model for CAVs.

We consider a road of length $L_{R}$ on which $N_{c}$ CAVs travel. We consider
$N$ BSs are deployed alongside the road at a certain distance
$d_{\mathrm{safe}}$ with a density defined as the number of BSs deployed per
unit distance, i.e., $\mu=N/L_{R}$. The distance between BSs is $1/\mu$ as
shown in Fig. 1. The CAVs’ density $k$ on the road is defined as the number of
CAVs per unit distance, and the CAVs’ speed is $v$. According to macroscopic
traffic flow theory, the flow of vehicles is defined as $q=kv$ vehicles per
unit time [8]. Note that $k$ is inversely proportional to $s$, i.e., $k=1/s$
and $s$ is the spacing between neighboring vehicles. Given the PDF of the
density of vehicles $k$ on the road $f_{K}(k)$, the traffic flow can be
defined as follows:

$Q=\int_{0}^{\infty}kvf_{K}(k)\mathrm{d}k.$ (1)

In this paper, we model the inter-vehicle spacing $s$ with a log-normal
distribution. This model has been proven to be accurate for daytime hours
through various empirical studies [9]. The research works observed the traffic
flow behaviour during different times of the day, and proved that the inter-
vehicle spacing distribution is log-normally distributed during day-time hours
(i.e., moderate traffic). Therefore, we consider the inter-vehicle spacing $s$
to be log-normally distributed during day-time hours with PDF given as:

$f_{S}(s)=\frac{1}{s\sigma_{\mathrm{LN}}\sqrt{2\pi}}\exp{\left(-\frac{(\ln{(s)}-\mu_{\mathrm{LN}})^{2}}{2\sigma_{\mathrm{LN}}^{2}}\right)},$

where $\mu_{\mathrm{LN}}$ and $\sigma_{\mathrm{LN}}$ are the logarithmic
average and scatter parameters of log-normal distribution, respectively, and
erf($\cdot$) is the error function. Therefore, (1) can be rewritten as
follows:

$Q=\int_{0}^{\infty}\frac{1}{s}vf_{S}(s)\mathrm{d}s=v\exp{\left(\frac{\sigma^{2}_{\mathrm{LN}}-2\mu_{\mathrm{LN}}}{2}\right)}.$
(2)

Each CAV is assumed to be connected to a single nearest BS at any given time.
Considering the distance-based path-loss and short-term multi-path fading at
the transmission channel, the received signal power at a given CAV $i$ from a
given BS $j$ in the downlink can be modeled as follows:

$S_{i,j}=G_{R}^{\text{tx}}G_{R}^{\text{rx}}\left(\frac{c}{4\pi
f_{R}}\right)^{2}\frac{P_{j}^{\text{tx}}}{d_{i,j}^{\alpha}}\chi_{i,j}=\gamma_{R}P_{j}^{\text{tx}}d_{i,j}^{-\alpha}\chi_{i,j},$
(3)

The signal-to-interference-plus noise ratio (SINR) received at a $i$-th CAV
from $j$-th BS can thus be modeled as follows:

$\mathrm{SINR}_{i,j}=\frac{S_{i,j}}{N_{R}+I_{i}}=\frac{\gamma_{R}P_{j}^{\mathrm{tx}}d_{i,j}^{-\alpha}\chi_{i,j}}{N_{R}+I_{i}},$
(4)

where $G_{R}^{\mathrm{tx}}$ and $G_{R}^{\mathrm{rx}}$ represent the
transmitting and receiving antenna gains, respectively, $P_{j}^{\mathrm{tx}}$
represents the transmit power of the BS $j$, $\chi_{i,j}$ represents the
short-term channel fading of BS $j$ modeled with Rayleigh distribution, $c$
and $f_{R}$ represent the speed of an electromagnetic wave and RF carrier
frequency, respectively, $d_{i,j}$ represents the distance between the $j$-th
BS and $i$-th CAV, and $\alpha$ represents the path-loss exponent.
Furthermore, $N_{R}$ is the thermal noise power at the receiver and
$I_{i}=\sum_{k\neq j}P_{k}^{\mathrm{tx}}\gamma_{R}d^{-\alpha}_{i,k}\chi_{i,k}$
is the cumulative interference at the $i$-th CAV from the interfering BSs,
where $\gamma_{R}=G_{R}^{\mathrm{tx}}G_{R}^{\mathrm{rx}}(c/4\pi f_{R})^{2}$,
$d_{i,k}$ represents the distance between the $i$-th CAV and $k$-th
interfering BS, and $\chi_{i,k}$ is the power of fading from the $k$-th
interfering BS to the CAV.

Furthermore, as detailed in Fig. 1, the distance between a CAV $i$ and BS $j$
can be calculated using their respective coordinates as
$d_{i,j}=\sqrt{x_{i,j}^{2}+h_{\mathrm{bs}}^{2}+d_{\mathrm{safe}}^{2}},$ where
$h_{\mathrm{bs}}$ represents the height of the BSs, $d_{\mathrm{safe}}$
represents the safety distance from the CAV on the road to the BS, and
$x_{i,j}$ is the distance parallel to the road with respect to the location of
the CAV on the road to the BS. Subsequently, given the Shannon-Hartley theorem
for infinite block-length regime, the data rate without mobility between a BS
and CAV can be defined as $R_{i,j}=W\log_{2}(1+\text{SINR}_{i,j})$ where $W$
represents the bandwidth of the channel.

As CAVs drive along the road, HOs between different BSs occur, and due to HO
delays and failures, an increase in the rate of HOs can negatively impact the
CAV data rate. Therefore, we incorporate the effect of these HOs through the
HO-related cost. HO cost is proportional to the HO delay ($h_{d}$) measured in
seconds per HO, and HO rate ($H$) measured in number of HOs per second, i.e.,
$H_{c}=h_{d}\times H.$ Since we assume nearest BS association for CAVs, we
define $H$ as the number of cell boundaries a CAV crosses per second, where a
cell boundary is the coverage range of a BS. Note that the number of
boundaries per unit distance are the same as the BS density $\mu$. By using
the speed of CAVs $v$, we can calculate the number of boundaries covered by a
CAV per second as $H=\mu v$. Thus, we model the HO-aware data rate [3] as:

$M_{i,j}=R_{i,j}(1-H_{c,\text{max}})=R_{i,j}\left(1-h_{d}\frac{\mu
v_{i}}{\mu_{\text{max}}V_{\text{max}}}\right),$ (5)

where
$H_{c,\text{max}}=h_{d}\frac{H}{\mu_{\text{max}}V_{\text{max}}}=h_{d}\frac{\mu
v}{\mu_{\text{max}}V_{\text{max}}}$ is the normalized HO cost in equation (5)
to ensure $0\leq H_{c,\text{max}}<1$, $\mu_{\text{max}}$ is the maximum
regulated BS density, and $V_{\text{max}}$ is the maximum regulated speed of
the CAVs. Finally, a stable CAV connection with the nearest BS requires a
minimum HO-aware data rate $R_{\text{th}}$ which ensures that every CAV
achieves the required QoS.

##  III HO-Aware Rate Outage Probability Analysis

In this section, we derive novel closed-form expressions for the PDF and CDF
of SINR, HO-aware rate outage probability, as well as the ergodic HO-aware
data rate. The HO-aware rate outage probability $P_{\mathrm{out}}$ is defined
as:

$P_{\mathrm{out}}=\mathrm{Pr}\left(M_{i,j}\leq
R_{\mathrm{th}}\right)=\mathrm{Pr}\left(Z=\frac{S_{i,j}}{N_{R}+I_{i}}\leq\gamma_{\mathrm{th}}\right),$
(6)

where $\gamma_{\mathrm{th}}$ is the desired SINR threshold given as
$\gamma_{\mathrm{th}}=2^{\frac{R_{\mathrm{th}}}{W(1-H_{c,\mathrm{max}})}}$ and
$H_{c,\mathrm{max}}=h_{d}\frac{\mu v}{\mu_{\mathrm{max}}V_{\mathrm{max}}}$.
The outage expression can then be derived as shown in the following lemma.

######  Lemma 1 (HO-aware Rate Outage Probability).

Given the PDF and CDF of SINR of $i$th CAV, the closed-form outage expressions
can be given as follows:

$P_{\mathrm{out}}=1-\sum^{N}_{k=1,k\neq j}\frac{a_{i,j}e^{\frac{\lambda
N_{R}}{b_{i,k}}}}{b_{i,k}\gamma_{\mathrm{th}}+a_{i,j}}\prod_{l=1,l\neq
k}\frac{b_{i,k}}{b_{i,k}-b_{i,l}}.$ (7)

###### Proof.

To derive the SINR outage, we first calculate the PDF and CDF of SINR. In the
sequel, we first determine the PDF and CDF of $S_{i,j}$ and $I_{i}$. The
random variable $S_{i,j}$ is a scaled exponential random variable, i.e.,
$S_{i,j}=Y=a_{i,j}\chi_{i,j}$ where
$a_{i,j}=\gamma_{R}P_{j}^{\text{tx}}d_{i,j}^{-\alpha}$. By using a single
variable transformation, the PDF and CDF of $Y$ can be given, respectively, as
follows:

$f_{Y}(y)=\frac{\lambda}{a_{i,j}}e^{-\frac{\lambda}{a_{i,j}}y},\quad
F_{Y}(y)=1-e^{-\frac{\lambda}{a_{i,j}}y}.$ (8)

The interference $I_{i}=\sum_{k\neq
j}P_{k}^{\mathrm{tx}}\gamma_{R}d^{-\alpha}_{i,k}\chi_{i,k}=\sum_{k\neq
j}b_{i,k}\chi_{i,k}$ follows Hypoexponential distribution [10] as $I_{i}$ is
the weighted sum of $n$ independent but non-identical exponential random
variables. Each exponential is scaled with a different factor due to the
different distance between the CAV and the interfering BSs. The PDF of the
interference can thus be given by:

$f_{I_{i}}(I)=\sum^{N}_{k=1,k\neq
j}\frac{\lambda}{b_{i,k}}e^{-\frac{\lambda}{b_{i,k}}I}\prod_{l=1,l\neq
k}\frac{b_{i,k}}{b_{i,k}-b_{i,l}},$ (9)

Now, we define $X=N_{R}+I_{i}$. The PDF of $X$ can be given after a single
random variable transformation as $f_{X}(x)=f_{I}(x-N_{R})$. Finally, given
the statistics of $X$ and $Y$, we derive the PDF of $Z=Y/X$ [11] as:

$\displaystyle f_{Z}(z)=\int_{0}^{\infty}xf_{X}(x)f_{Y}(xz)dx$
$\displaystyle=\sum^{N}_{k=1,k\neq j}\frac{a_{i,j}\>b_{i,k}e^{\frac{\lambda
N_{R}}{b_{i,k}}}}{(b_{i,k}z+a_{i,j})^{2}}\prod_{l=1,l\neq
k}\frac{b_{i,k}}{b_{i,k}-b_{i,l}}.$ (10)

Furthermore, the CDF of $Z$ is as follows:

$F_{Z}(z)=1-\sum^{N}_{k=1,k\neq j}\frac{a_{i,j}e^{\frac{\lambda
N_{R}}{b_{i,k}}}}{b_{i,k}z+a_{i,j}}\prod_{l=1,l\neq
k}\frac{b_{i,k}}{b_{i,k}-b_{i,l}}.$ (11)

Finally, the outage in Lemma 1 can be calculated by substituting
$z=\gamma_{\mathrm{th}}$ in (11). ∎

In the following, we characterize the average HO-aware data rate using the
statistics of SINR.

######  Lemma 2 (Ergodic HO-Aware Data Rate).

Given the PDF and CDF of SINR, the closed-form ergodic rate expression can be
given as follows:

$M_{\mathrm{avg}}(\mu)=W(1-\bar{h}_{d}\mu v)\sum^{N}_{k=1,k\neq
j}\frac{\beta_{k}a_{i,j}e^{\frac{\lambda
N_{R}}{b_{i,k}}}}{a_{i,j}-b_{i,k}}\prod_{l=1,l\neq
k}\frac{b_{i,k}}{b_{i,k}-b_{i,l}},$ (12)

where $\beta_{k}=\ln(a_{i,j}/b_{i,k})+\mathrm{atan2}(\lambda/b_{i,k},0)$, and
$\mathrm{atan2}(y,x)$ is the 2-argument arctangent function.

###### Proof.

We begin by defining the ergodic rate as follows:

$\displaystyle
M_{\mathrm{avg}}(\mu)=\mathbb{E}\left[W\log_{2}\left(1+Z\right)(1-\bar{h}_{d}\mu
v)\right]$ $\displaystyle=W(1-\bar{h}_{d}\mu
v)\mathbb{E}\left[\log_{2}\left(1+Z\right)\right],$ (13)

where $\bar{h}_{d}=h_{d}/(\mu_{\mathrm{max}}V_{\mathrm{max}})$ and $Z$ is a
function of $\mu$. Given the definition of ergodic rate [12], we have:

$\displaystyle
R_{\mathrm{avg}}(\mu)=\mathbb{E}\left[\log_{2}\left(1+Z\right)\right]=\int^{\infty}_{0}\log_{2}(1+Z)f_{Z}(z)dz,$
$\displaystyle=\frac{1}{\ln(2)}\int^{\infty}_{0}\frac{1-F_{Z}(z)}{1+z}dz,$
$\displaystyle=\frac{1}{\ln(2)}\int^{\infty}_{0}\sum^{N}_{k=1,k\neq
j}\frac{a_{i,j}e^{\frac{\lambda N_{R}}{b_{i,k}}}\prod_{l=1,l\neq
k}\frac{b_{i,k}}{b_{i,k}-b_{i,l}}}{(b_{i,k}+a_{i,j})z+b_{i,k}z^{2}+a_{i,j}}dz,$
(14)

where (III) is a function of $\mu$ because $d_{i,j},d_{i,k}$ and in turn
$b_{i,j},b_{i,k}$ are functions of $\mu$. The final step is derived by
substituting (11) into (III). The closed-form ergodic capacity can be derived
by solving the integral as follows:

$R_{\mathrm{avg}}(\mu)=\sum^{N}_{k=1,k\neq
j}\beta_{k}\frac{a_{i,j}e^{\frac{\lambda
N_{R}}{b_{i,k}}}}{a_{i,j}-b_{i,k}}\prod_{l=1,l\neq
k}\frac{b_{i,k}}{b_{i,k}-b_{i,l}},$ (15)

Finally, the HO-aware data rate can be given by substituting (15) into (III).
∎

To simplify the optimization, we also provide a worst-case bound on the
interference.

######  Lemma 3 (Worst-Case Data Rate at CAV $i$).

The worst-case signal power will be observed at a CAV when the CAV is located
at the halfway point between two BSs (i.e. $\frac{1}{2\mu}$) such that
$d_{i,j}=d_{\mathrm{max}}=\sqrt{h_{\mathrm{bs}}^{2}+d_{\mathrm{safe}}^{2}+\frac{1}{4\mu^{2}}}$.
The worst-case interference will also be observed at this location because the
CAV will have maximum signal and interference from the neighbouring BSs such
that.
$d_{i,k}=\sqrt{h_{\mathrm{bs}}^{2}+d_{\mathrm{safe}}^{2}+\frac{(2k+1)^{2}}{4\mu^{2}}}$.
Finally, the ergodic worst-case data rate is given as

$R_{\mathrm{worst}}(\mu)=\sum^{N}_{k=1,k\neq
j}\frac{\beta_{k}d^{-\alpha}_{\mathrm{max}}e^{\frac{\lambda
N_{R}}{\gamma_{R}P^{\mathrm{tx}}_{j}d^{-\alpha}_{i,k}}}}{d^{-\alpha}_{\mathrm{max}}-d^{-\alpha}_{i,k}}\prod_{l=1,l\neq
k}\frac{d^{-\alpha}_{i,k}}{d^{-\alpha}_{i,k}-d^{-\alpha}_{i,l}}.$

##  IV QoS- Constrained Traffic Flow Maximization

In this section, we formulate the macroscopic traffic flow maximization
problem with various constraints to jointly optimize the CAV speed $v$ and the
BS density $\mu$ in the presence of interference. Note that BS density
optimization can also be implemented in practice by dynamically switching the
BSs. We present a closed-form expression for the optimal CAV speed and a
numerical method to compute optimal $\mu$. The traffic flow maximization
problem is formulated as:

$\displaystyle(\textbf{P1})\quad\max_{v,\mu}\qquad
Q=v\exp{\left(\frac{\sigma^{2}_{\mathrm{LN}}-2\mu_{\mathrm{LN}}}{2}\right)}$
$\displaystyle\mathrm{s.t.}$ $\displaystyle(\textbf{C1})\quad
v\leq\frac{\exp{\left(\sigma_{\mathrm{LN}}\sqrt{2}\operatorname{erf}^{-1}{\left(2\epsilon-1\right)+\mu_{\mathrm{LN}}}\right)}}{\tau}=V_{\mathrm{safe}}$
$\displaystyle\textbf{(C2)}\quad
v\leq\frac{1}{\bar{h}_{d}\mu}\left(1-\frac{R_{\mathrm{th}}}{WR_{\mathrm{worst}}(\mu)}\right)=V_{\mathrm{data}}(\mu)$
$\displaystyle(\textbf{C3})\quad R_{\mathrm{th}}\leq WR_{\mathrm{worst}}(\mu)$
$\displaystyle(\textbf{C4})\quad 0<v\leq V_{\text{max}}$
$\displaystyle(\textbf{C5})\quad 0\leq\mu\leq\mu_{\text{max}}$

where C1 is the collision avoidance constraint which ensures that the speed of
the CAVs should not exceed $s/\tau$, i.e.,

$\mathrm{\mathrm{Pr}}\left(v\geq\frac{s}{\tau}\right)=\mathrm{\mathrm{Pr}}\left(s\leq
v\tau\right)\leq\epsilon,$ (16)

where $s$ is the distance between two CAVs and is always greater than zero,
$\tau$ represents the processing time for the CAVs to act on a decision, and
$\epsilon$ is the crash tolerance level. In addition, equation (16) can be
rewritten by substituting the CDF of $s$ where
$\mathrm{\mathrm{Pr}}\left(v\geq\frac{s}{\tau}\right)=\frac{1}{2}\left(1+\mathrm{erf}\left(\frac{\ln{(v\tau)}-\mu_{\mathrm{LN}}}{\sigma_{\mathrm{LN}}\sqrt{2}}\right)\right)$.
By using the inverse error function and taking the inverse log of both sides
and factoring for $v$, (16) can be rewritten as in C1. C1 indicates that speed
is capped to create an adequate safety distance that is traversed during the
processing time. We refer to the right side of C1 as the maximum safe speed
that keeps the crash probability below $\epsilon$. The condition C1 shows that
the maximum safe speed increases with $\epsilon$, but decreases with the
processing time.

Furthermore, C2 is the worst-case HO-aware data rate constraint of the CAV
based on Lemma 3, i.e.,

$M_{\mathrm{worst}}=W(1-\bar{h}_{d}\mu v)R_{\mathrm{worst}}(\mu)\geq
R_{\text{th}}.$ (17)

By factoring out for $v$ we can rewrite (17) as in C2, where we refer to the
right side of C2 as the maximum speed, denoted by $V_{\textrm{data}}(\mu)$
that ensures the minimum data rate requirement of the CAVs. To ensure that C2
does not attain negative values of speed and the problem remains feasible, we
introduce the constraint C3. That is, C3 ensures
$\frac{R_{\text{th}}}{WR_{\mathrm{worst}}(\mu)}\leq 1$. The final two
constraints C4 and C5 cap the speed and BS density to a maximum, respectively.
Note that problem P1 is a non-linear programming problem due to constraints C2
and C3 which are a non-linear function of $\mu$. To solve this problem, we
first compute the optimal speed $v^{*}$ which is then further maximized to
optimize BS density as in the following Lemma.

######  Lemma 4.

Given that $Q$ is linearly increasing with $v$, and that $v$ is bounded from
$V_{\mathrm{max}}$, $V_{\mathrm{safe}}$, and $V_{\mathrm{data}}$, the optimal
speed $v^{*}(\mu)$ is derived as the largest feasible speed that does not
violate the three constraints, such that

$v^{*}(\mu)=\min\\{V_{\mathrm{max}},V_{\mathrm{safe}},V_{\mathrm{data}}(\mu)\\},$
(18)

The optimal BS density $\mu^{*}$ can then be computed using the fminbnd
function in MATLAB which is based on golden-section search algorithm
(GSS)[13]. The GSS method can find the global maximum or minimum of a unimodal
function; whereas, it converges to a local maximum or minimum for a function
containing multiple extrema [14]. GSS is a one-dimensional search that works
by reducing the interval in a golden ratio range, where the minimum of the
interval lies within the interval. In our case, we want to determine the
optimal value of $\mu$ which maximizes $V_{\mathrm{data}}$, so we provide
fmindbnd function with the negative of $V_{\mathrm{data}}$ as the objective
function. The algorithm has a computational complexity of $\mathcal{O}(\log
n)$ [15]. If $\mu^{*}>\mu_{\mathrm{max}}$, we have
$\mu^{*}=\mu_{\mathrm{max}}$. Also, if $\mu^{*}$ violates $R_{\mathrm{th}}\leq
WR_{\mathrm{worst}}(\mu^{*})$, the problem becomes infeasible.

It is important to note that due to the interference expression and its
dependency on BS density, there is no closed-form expression for $\mu^{*}$.
Therefore, we utilize one-dimensional numerical optimization techniques to
solve for $\mu^{*}$.

Finally, by substituting (18) and $\mu^{*}$ into the objective function of P1,
we derive the optimal traffic flow as follows:

$Q=\min\\{V_{\mathrm{max}},V_{\mathrm{safe}},V_{\mathrm{data}}(\mu^{*})\\}\exp{\left(\frac{\sigma^{2}_{\mathrm{LN}}-2\mu_{\mathrm{LN}}}{2}\right)}.$

##  V Numerical Results and Discussions

In this section, we validate the accuracy of the derived expressions through
computer simulations. Furthermore, we demonstrate the sensitivity of optimal
traffic flow by changing key parameters such as crash tolerance level, data
rate thresholds, interference, etc. Unless stated otherwise, the values of the
system parameters [2] are used in the following figures are listed herein.
$V_{\mathrm{max}}=30$ m/s, $\mu_{\mathrm{max}}=0.01$ BSs/m, $h_{d}=3$ s/HO,
$R_{\mathrm{th}}=60$ Mbps, $W=40$ MHz, $G_{R}^{\mathrm{tx}}=1$ dB,
$G_{R}^{\mathrm{rx}}=1$ dB, $c=3\times 10^{8}$ m/s, $f_{R}=2.1$ GHz,
$N_{R}=1.507\times 10^{-13}$ W/$\mathrm{m}^{2}$, $P_{j}^{\mathrm{tx}}=1$ W,
$\alpha=3$, $\lambda=1$, $\epsilon=1\%$, $\tau=6\times 10^{-3}$ sec,
$\mu_{\mathrm{LN}}=0$, $\sigma_{\mathrm{LN}}=1$, $d_{\mathrm{safe}}=5$ m,
$h_{\mathrm{bs}}=8$ m, $L_{R}=2000$ m.

Fig. 4 and Fig. 4 demonstrate the outage probability (7) and ergodic capacity
(15) as a function of $\mu$ for various CAV speeds. The analytical expression
match perfectly with the simulation results. When $\mu$ increases, the outage
increases and rate decreases due to increasing interference and HOs.
Furthermore, higher speeds result in higher probability of outage and lower
ergodic capacity when compared to lower speeds, which is due to more frequent
HOs.

Figure 2: HO-aware rate outage probability as a function of $\mu$ for various
speeds and $R_{\mathrm{th}}=1\times 10^{8}$ bps, $\mu_{\mathrm{max}}=0.02$
BSs/m.

Figure 3: HO-aware capacity as a function of $\mu$ for various speeds for
$R_{\mathrm{th}}=1\times 10^{8}$ bps, $\mu_{\mathrm{max}}=0.02$ BS/m.

Figure 4:  $V_{\mathrm{data}}$ as a function of $\mu$ for $\alpha=3$ (Top) and
$\alpha=4$ (Bottom) with various CAV processing times $\tau$.

Figure 5: Traffic flow $Q$ as a function of $R_{\mathrm{th}}$ with analytical
and simulation results (Top) and optimal BS density $\mu^{*}$ as a function of
$R_{\mathrm{th}}$ (Bottom) for various path-loss exponents.

Figure 6: Traffic flow $Q$ as a function of crash tolerance $\epsilon$ and
various CAV processing times $\tau$.

Figure 7: Traffic flow $Q$ as a function of $\mu$ with various BS safety
distances with and without interference.

Fig. 4 depicts $V_{\mathrm{data}}$ as a function of $\mu$. As $\mu$ increases,
$V_{\mathrm{data}}$ with $\alpha=3$ increases up to a certain point due to
vicinity of BSs. However, beyond that point $V_{\mathrm{data}}$ begins to
decrease due to an increase in HOs and interference, and the CAVs need to
lower their speed. On the other hand, when $\alpha=4$, the benefit of rate
enhancement cannot be seen and a higher $\mu$ only causes more interference
and HOs. Furthermore, we show that different CAV processing times $\tau$
varies $V_{\mathrm{safe}}$, where $v^{*}=V_{\mathrm{safe}}$ for higher $\tau$
values when $V_{\mathrm{safe}}<V_{\mathrm{data}}$.

Fig. 7 depicts the impact of the data rate threshold $R_{\mathrm{th}}$ on
traffic flow $Q$ and the optimal BS density $\mu^{*}$ for various path-loss
exponents. As seen on the top of Fig. 7, as $R_{\mathrm{th}}$ increases, $Q$
decreases as CAVs need to reduce their speed to limit the number of HOs to
meet the required data rate. For the same reason, when $R_{\mathrm{th}}$,
$\mu^{*}$ increases. The environments with higher path-loss exponents require
more dense BS deployment. Note that we consider 100 points (or
$R_{\mathrm{th}}$ values) along the x-axis between $6\times 10^{7}$ bps and
$8\times 10^{7}$ bps to compute analytical traffic flow which requires to
compute the optimal density of BSs $\mu^{*}$ numerically using MATLAB’s
fminbnd function at each $R_{\mathrm{th}}$ value. Therefore, minor
fluctuations are observed due to numerical computations of $\mu^{*}$.

Fig. 7 depicts the relationship between the crash tolerance level $\epsilon$
and optimum traffic flow $Q$ for various CAV processing times. At first,
$V_{\mathrm{safe}}<V_{\mathrm{data}}<V_{\mathrm{max}}$, thus the optimal speed
is bound to $V_{\mathrm{safe}}$ as in Lemma 4, where $V_{\mathrm{safe}}$
increases as the crash intensity level $\epsilon$ increases since we are
relaxing the crash tolerance. After a certain $\epsilon$ value,
$V_{\mathrm{safe}}>V_{\mathrm{data}}$. The optimal speed is bound to
$V_{\mathrm{data}}$ as in Lemma 4, which is constant with respect to
$\epsilon$ and results in an upbound flat curve. For different CAV processing
times $\tau$, the point at which $V_{\mathrm{data}}$ takes over changes. When
the CAV processing time is larger, $V_{\mathrm{safe}}$ is smaller since it
takes a longer time for the CAV to process decisions compared to smaller
$\tau$ values.

Finally, Fig 7 depicts the relationship between BS density $\mu$ and traffic
flow $Q$ with various BS safety distances. At first, when the BS density $\mu$
is lower, $V_{\mathrm{safe}}<V_{\mathrm{data}}<V_{\mathrm{max}}$ so the
optimal speed is bound to $V_{\mathrm{safe}}$ as in Lemma 4.
$V_{\mathrm{safe}}$ is constant with respect to $\mu$ which results in an
upbound flat curve. As $\mu$ increases, HOs and interference increases which
lowers $V_{\mathrm{data}}$ to the point where
$V_{\mathrm{safe}}>V_{\mathrm{data}}$ and the optimal speed is bound to
$V_{\mathrm{data}}$ as in Lemma 4. For different BS safety distances
$d_{\mathrm{safe}}$, the switching point between $V_{\mathrm{safe}}$ and
$V_{\mathrm{data}}$ changes because the further away the BS is from the CAV,
$V_{\mathrm{data}}$ will decrease because of weak signal strength.
Furthermore, the traffic flow without interference results in better traffic
flow as compared to the traffic flow with interference as the interference
deteriorates the data rate, CAV speed, and traffic flow.

##  VI Conclusion

This letter presents a framework for V2I communications for CAVs where we
derive novel expressions for outage probability and ergodic capacity of HO-
aware data rate, and jointly optimize the speed and network deployment in the
presence of HOs between BSs and interference due to neighbouring BSs. Finally,
we demonstrate the trade-off between achievable wireless data rates and
traffic flow.

## References

  * [1] L. Hobert, A. Festag, I. Llatser, L. Altomare, F. Visintainer, and A. Kovacs, “Enhancements of V2X communication in support of cooperative autonomous driving,” _IEEE Commun. Magazine_ , vol. 53, no. 12, pp. 64–70, 2015.
  * [2] M. T. Hossan and H. Tabassum, “Mobility-aware performance in hybrid RF and Terahertz wireless networks,” _IEEE Trans. on Commun._ , vol. 70, no. 2, pp. 1376–1390, 2022.
  * [3] R. Arshad, H. ElSawy, S. Sorour, T. Y. Al-Naffouri, and M.-S. Alouini, “Velocity-aware handover management in two-tier cellular networks,” _IEEE Trans. on Wireless Commun._ , vol. 16, no. 3, pp. 1851–1867, 2017.
  * [4] X. Lin, R. K. Ganti, P. J. Fleming, and J. G. Andrews, “Towards understanding the fundamentals of mobility in cellular networks,” _IEEE Trans. on Wireless Commun._ , vol. 12, no. 4, pp. 1686–1698, 2013.
  * [5] Z. Yan and H. Tabassum, “Reinforcement learning for joint V2I network selection and autonomous driving policies,” in _IEEE Global Commun. Conference_ , 2022, pp. 1241–1246.
  * [6] J. Popping, E. Begeleider, and T. Begeleider, “An overview of microscopic and macroscopic traffic models,” 2013.
  * [7] X. Shi and X. Li, “Constructing a fundamental diagram for traffic flow with automated vehicles: Methodology and demonstration,” _Transportation Research Part B: Methodological_ , vol. 150, pp. 279–292, 2021.
  * [8] R. Mahnke, J. Kaupužs, and I. Lubashevsky, “Probabilistic description of traffic flow,” _Physics Reports_ , vol. 408, no. 1, pp. 1–130, 2005.
  * [9] N. Wisitpongphan, F. Bai, P. Mudalige, V. Sadekar, and O. Tonguz, “Routing in sparse vehicular ad hoc wireless networks,” _IEEE Journal on Selected Areas in Commun._ , vol. 25, no. 8, pp. 1538–1556, 2007.
  * [10] S. Khaled, T. Kadri, and S. Kadry, “Hypoexponential distribution with different parameters,” _Journal of Applied Mathematics_ , vol. 4, pp. 624–631, 04 2013.
  * [11] N. Jawad, A. Nasar, and J. Hadad, “Distributions of the ratio and product of two independent weibull and lindley random variables,” _Journal of Probability and Statistics_ , vol. 2020, 05 2020.
  * [12] M. Monemi and H. Tabassum, “Performance of UAV-assisted D2D networks in the finite block-length regime,” _IEEE Trans. on Commun._ , vol. 68, no. 11, pp. 7270–7285, 2020.
  * [13] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, _Numerical Recipes 3rd Edition: The Art of Scientific Computing_ , 3rd ed. USA: Cambridge University Press, 2007.
  * [14] “Chapter 11 - basic methods,” in _Numerical Methods and Optimization in Finance (Second Edition)_ , second edition ed., M. Gilli, D. Maringer, and E. Schumann, Eds. Academic Press, 2019, pp. 229–271.
  * [15] D. E. Ferguson, “Fibonaccian searching,” _Commun. ACM_ , vol. 3, no. 12, p. 648, 1960.


# Leading Whitespaces of Language Models’ Subword Vocabulary Poses a Confound
for Calculating Word Probabilities

Byung-Doh Oh
Department of Linguistics
The Ohio State University
<EMAIL_ADDRESS>
&William Schuler
Department of Linguistics
The Ohio State University
<EMAIL_ADDRESS>

###### Abstract

Word-by-word conditional probabilities from Transformer-based language models
are increasingly being used to evaluate their predictions over minimal pairs
or to model the incremental processing difficulty of human readers. In this
paper, we argue that there is a confound posed by the subword tokenization
scheme of such language models, which has gone unaddressed thus far. This is
due to the fact that tokens in the subword vocabulary of most language models
have leading whitespaces and therefore do not naturally define stop
probabilities of words. We first prove that this can result in word
probabilities that sum to more than one, thereby violating the axiom that
$\mathsf{P}(\Omega)=1$. This property results in a misallocation of word-by-
word surprisal, where the unacceptability of the current ‘end of word’ is
incorrectly carried over to the next word. Additionally, language models’ such
implicit prediction of word boundaries is incongruous with psycholinguistic
experiments where human subjects directly observe upcoming word boundaries. We
present a simple decoding technique to reaccount the probability of the
trailing whitespace into that of the current word, which resolves this
confound. As a case study, we show that this results in significantly
different estimates of garden-path effects in transitive/intransitive
sentences, where a comma is strongly expected before the critical word.

Leading Whitespaces of Language Models’ Subword Vocabulary Poses a Confound
for Calculating Word Probabilities

Byung-Doh Oh Department of Linguistics The Ohio State University
<EMAIL_ADDRESS>William Schuler Department of Linguistics The Ohio State
University<EMAIL_ADDRESS>

##  1 Introduction

Language models (LMs), which are trained to make predictions about upcoming
words, are at the core of many natural language processing (NLP) applications.
While most contemporary applications involve generating text by sampling from
the LMs’ conditional probability distribution, the magnitudes of the
probabilities they assign to each word in a given sentence have been important
from two perspectives. The first is from the perspective of LM
interpretability, which aims to study their predictions and the linguistic
knowledge encoded in their representations. A well-established paradigm in
this line of research is what has been dubbed ‘targeted syntactic evaluation’
(Linzen et al., 2016; Gulordava et al., 2018; Marvin and Linzen, 2018), in
which probabilities of critical words in minimal pairs (e.g. grammatical vs.
ungrammatical sentences) are compared.

Moreover, in cognitive modeling, conditional probabilities from LMs are used
to model the word-by-word reading times of human subjects, often under the
theoretical link that the contextual predictability of a word determines its
processing difficulty (Hale, 2001; Levy, 2008). Recent work in this line of
research has evaluated surprisal estimates (i.e. negative log probabilities)
from LMs and has shown that surprisal from larger Transformer-based model
variants are less predictive of naturalistic reading times (Oh and Schuler,
2023; Shain et al., 2024; Steuer et al., 2023) and that surprisal greatly
underpredicts the processing difficulty of garden-path constructions (van
Schijndel and Linzen, 2021; Arehalli et al., 2022; Huang et al., 2024).

As such, while the use of word-by-word probabilities from LMs is popular in
computational linguistics research, we argue that there is a confound for
calculating them correctly that has gone unaddressed. This confound is posed
by subword tokenization schemes (e.g. byte-pair encoding; Sennrich et al.,
2016) that are used to define the token-level vocabulary for training most
contemporary LMs (e.g. AI@Meta, 2024; Google Gemini Team, 2024; Jiang et al.,
2023). For languages that use whitespace orthography, these subword
tokenization schemes often build the whitespace character directly into the
front of the tokens, thereby resulting in leading whitespaces. As a
consequence, the stop probability of a word (i.e. the probability of the
trailing whitespace) is never explicitly calculated, and therefore the sum
over the probabilities of all possible whitespace words can exceed one.

We propose a simple and efficient decoding method that reaccounts the
probability of the trailing whitespace into that of the current word, which
resolves this confound. Regression results show that this results in
significantly different surprisal-based estimates of garden-path effects in
transitive/intransitive sentences, where LMs strongly expect a comma before
the critical word.

##  2 Confound From Leading Whitespace and Whitespace-Trailing Decoding

This section provides a proof that the leading whitespace of the LMs’ subword
vocabulary results in inconsistent word probabilities, describes a related
confound, and proposes a simple decoding method for addressing it.

###  2.1 Proof of Inconsistent Word Probabilities

On languages that use whitespace orthography, the vocabulary $V$ defined by
the subword tokenization scheme consists of the set of tokens that begin with
a whitespace $V_{B}$, and the set of tokens that do not begin with a
whitespace $V_{I}$.111$V=V_{B}\cup V_{I}$, and $V_{B}\cap V_{I}=\varnothing$.
The subscripts respectively represent the ‘beginning’ and ‘inside’ of a
whitespace-delimited word. In the context of next-word prediction, the sample
space is $\Omega=\\{x_{1..n}\mid x_{1}{\in}V_{B},\,x_{2..n}{\in}V_{I}\\}$,
where $n\in\mathbb{N}$ is the total number of subword tokens in each
whitespace word as determined by the tokenizer.

#### Theorem

Leading whitespaces of the LMs’ subword vocabulary can result in word
probabilities that violate the Kolmogorov (1933) axiom that
$\mathsf{P}(\Omega)=1$.

#### Existence Proof

Let $\mathsf{P}(x_{1}=j)=1$ and $\mathsf{P}(x_{2}=k\mid x_{1}=j)=1$, where
$j\in V_{B}$ and $k\in V_{I}$. It follows from the chain rule of conditional
probabilities that:

$\displaystyle\mathsf{P}(x_{1}=j,x_{2}=k)$
$\displaystyle=\mathsf{P}(x_{1}=j)\cdot\mathsf{P}(x_{2}=k\mid x_{1}=j)$
$\displaystyle=1\cdot 1=1.$ (1)

If word probabilities are simply defined as the product of the probabilities
of the tokens within those words, then
$\mathsf{P}(x_{1}=j)+\mathsf{P}(x_{1}=j,x_{2}=k)>1$, $\mathsf{P}(\Omega)>1$,
and therefore the axiom is violated. $\blacksquare$

For example, given the minimal pair I was a matron in France and I was a mat
in France, the LM tokenizes the two sentences as follows and calculates the
conditional probability of each token.222In the context of the LM’s tokens,
‘␣’ is used to denote the explicit whitespace character that is part of the
token, and whitespace is used to delimit subword tokens.

I ␣was ␣a ␣mat ron ␣in ␣France (2) I ␣was ␣a ␣mat ␣in ␣France (3)

The presence of leading whitespaces results in an incorrect allocation of
word-by-word surprisal. As can be seen in Example 2, due to this tokenization,
$\mathsf{P}(\textit{\textvisiblespace mat ron}\mid\textit{I \textvisiblespace
was \textvisiblespace a})$ is factorized into
$\mathsf{P}(\textit{\textvisiblespace mat}\mid\textit{I \textvisiblespace was
\textvisiblespace a})\cdot\mathsf{P}(\textit{ron}\mid\textit{I
\textvisiblespace was \textvisiblespace a \textvisiblespace mat})$, and
therefore it follows that $\mathsf{P}(\textit{\textvisiblespace mat
ron}\mid\textit{I \textvisiblespace was \textvisiblespace
a})\leq\mathsf{P}(\textit{\textvisiblespace mat}\mid\textit{I
\textvisiblespace was \textvisiblespace a})$, despite the fact that matron is
more acceptable than mat in the above context. Instead, part of the
‘unacceptability’ of mat is incorrectly carried over to
$\mathsf{P}(\textit{\textvisiblespace in}\mid\textit{I \textvisiblespace was
\textvisiblespace a \textvisiblespace mat})$, where ␣in competes for
probability mass against the highly likely ron (Figure 1(a)).

(a) Surprisal values calculated with leading whitespaces.

(b) Surprisal values calculated with trailing whitespaces.

Figure 1: Surprisal values calculated for the partial sentences I was a matron
in and I was a mat in from the GPT-2 XL LM (Radford et al., 2019), with
leading whitespaces (top; standard practice) and trailing whitespaces (bottom;
proposed in this work).

###  2.2 Confound: Incongruity With Psycholinguistic Experimental Paradigms

Additionally, the presence of leading whitespaces in subword tokens makes the
LM’s predictions incongruous with the self-paced reading paradigm, in which
human readers directly observe the upcoming word boundary.

The cat sat on the mat … (4)

In Example 4, when human readers see mat, they know that the next keystroke
will reveal a new whitespace-delimited word (i.e. analogous to observing a
token in $V_{B}$) and not transform it into e.g. matron (i.e. analogous to
observing a token in $V_{I}$). In contrast, LMs define a probability
distribution over both $V_{B}$ and $V_{I}$ given the sequence The cat sat on
the mat.

While this confound is more apparent for the self-paced reading paradigm, this
is also a potential confound for studying data collected through the typical
eye-tracking paradigm. This is because native speakers of languages with
whitespace orthographies have been shown to be sensitive to the location of
upcoming whitespaces through parafoveal processing and utilize this
information to plan eye movements (Pollatsek and Rayner, 1982; Rayner et al.,
1998; Perea and Acha, 2009). Therefore, although information about word
boundaries is not directly built into the design of the paradigm, it can be
argued that human subjects engaged in the eye-tracking paradigm also face
little uncertainty about upcoming word boundaries.

###  2.3 Proposed Solution: Whitespace-Trailing Decoding

This confound can be resolved by reaccounting the probability of the trailing
whitespace as part of the word’s probability, in lieu of that of the leading
whitespace as LMs currently do (Examples 2 and 3). To this end, we propose
whitespace-trailing (WT) decoding. Given a word $w_{t+1}$ that consists of
subword tokens $x_{n_{t}+1..n_{t+1}}$, where $n_{t}$ is the total number of
subword tokens in $w_{1..t}$, $x_{n_{t}+1}{\in}V_{B}$, and
$x_{n_{t}+2..n_{t+1}}{\in}V_{I}$, WT decoding reallocates the probability of
the leading whitespace of each word to its previous word:

$\mathsf{P}(w^{\prime}_{t+1}\mid w^{\prime}_{1..t})=\\\ \mathsf{P}(w_{t+1}\mid
w_{1..t})\cdot\frac{\mathsf{P}(x_{n_{t+1}+1}{\in}V_{B}\mid
w_{1..t+1})}{\mathsf{P}(x_{n_{t}+1}{\in}V_{B}\mid w_{1..t})}.$ (5)

For instance, applying Eq. 5 to Example 3 yields:

$\mathsf{P}(\textit{mat\textvisiblespace}\mid\textit{I\textvisiblespace\,was\textvisiblespace\,a\textvisiblespace})=\\\
\mathsf{P}(\textit{\textvisiblespace mat}\mid\textit{I\,\textvisiblespace
was\,\textvisiblespace
a})\cdot\frac{\mathsf{P}(\textit{\textvisiblespace}\mid\textit{I\,\textvisiblespace
was\,\textvisiblespace a\,\textvisiblespace
mat})}{\mathsf{P}(\textit{\textvisiblespace}\mid\textit{I\,\textvisiblespace
was\,\textvisiblespace a})}.$ (6)

As WT decoding simply involves the factorization of whitespace probabilities
by marginalizing over tokens in $V_{B}$ and rearranging them, it requires no
modifications to the LM and minimal overhead.333We note that WT decoding does
not resolve other issues with subword units that may be addressed by re-
training LMs with different tokenization schemes (e.g. Nair and Resnik, 2023),
which can however be expensive. Code for implementing WT decoding is available
at: this_anonymous_url. Additionally, the joint probability of the entire
sequence, and therefore metrics like perplexity, changes minimally by a factor
of the probability of the final trailing whitespace with WT decoding.

As can be seen in Figure 1(b), incorporating the probabilities of trailing
whitespaces correctly differentiates between matron and mat in this context,
and removes the inherent relationship between the two probabilities that holds
with leading whitespaces. Additionally, the ‘unacceptability’ of mat that was
incorrectly carried over to ␣in in Example 3 is now reflected in
$\mathsf{P}(\textit{mat\textvisiblespace}\mid\textit{I\textvisiblespace\
was\textvisiblespace\ a\textvisiblespace})$.

LM probabilities with trailing whitespaces are also better aligned with the
self-paced reading paradigm where the upcoming word boundaries are directly
observed. For example, the calculation of
$\mathsf{P}(\textit{mat\textvisiblespace}\mid\textit{The\textvisiblespace\
cat\textvisiblespace\ sat\textvisiblespace\ on\textvisiblespace\
the\textvisiblespace})$ precludes the prediction of tokens in $V_{I}$ directly
after mat, which correctly reflects the fact that the next keystroke in
Example 4 will reveal a new whitespace word.

##  3 Case Study: Impact on Surprisal-Based Estimates of Garden-Path Effects

Eq. 6 shows that WT decoding will result in a decrease (or increase) in
probability to the extent that the next token is unlikely to be in $V_{B}$
proportional to the extent that the current token was likely to be in $V_{B}$.
This experiment demonstrates that the confound posed by leading whitespaces
affects surprisal-based estimates of garden-path effects in
transitive/intransitive sentences (Mitchell, 1987; Gorrell, 1991), which is
caused by syntactic disambiguation that takes place at the critical word
(highlighted in magenta).

After the doctor left the room turned very dark … (7)

The same critical word in the control counterpart is thought to be easier to
process, as the verb left is unambiguous.

After the doctor left, the room turned very dark … (8)

###  3.1 Procedures

We estimated surprisal-based garden-path effects from GPT-2 model variants
(Radford et al., 2019) with and without WT decoding, using the data and
following the procedures of Huang et al. (2024).444Huang et al. (2024) present
results using GPT-2 Small and the LSTM LM from Gulordava et al. (2018). First,
to estimate a linking function between LM surprisal and human reading times,
linear mixed-effects regression (LMER) models with the following formula were
fit to self-paced reading times ($n=995,814$) of filler items from the Provo
Corpus (Luke and Christianson, 2018) for each variant:

    RT ~ surp + surp_prev1 + surp_prev2 + s(length) +
         freq + freq_prev1 + freq_prev2 + s(index) +
         (1 | subject) + (1 | item),

where length is word length in characters, index is the position of the word
within the sentence, and the frequency predictors were log-transformed.

Figure 2: Estimated effects of interest at each region for the
transitive/intransitive garden-path construction, using surprisal from GPT-2
variants with and without WT decoding. Error bars represent 95% confidence
intervals.

These modeling choices assume a linear relationship between surprisal and
reading times (Shain et al., 2024; Wilcox et al., 2023), and that surprisal
and log frequency from two previous words have a lingering influence on the
current word (spillover effects). These LMER models were subsequently used to
predict word-by-word reading times (in ms) for 24 items in the ambiguous
condition (Example 7) and the unambiguous control condition (Example 8) of the
transitive/intransitive construction, which were read by 2,000 subjects
($n{=}15,915$):

The increase in the predicted reading times of the disambiguating critical
word and two subsequent words due to the increase in surprisal across
conditions was estimated using LMER models with the following formula to
quantify the magnitude of surprisal-based garden-path effects at each
word:555Both the ‘filler item’ and ‘reading time increase’ LMER models have
been simplified from the specifications in Huang et al. (2024) due to
convergence issues.

    pred_RT ~ condition + (1 | subject) + (1 | item).

###  3.2 Results

The results in Figure 2 show addressing the confound posed by subword
tokenization through WT decoding lowers the estimated magnitude of garden-path
effects in the first and second spillover regions, the difference in which is
significant at $p<0.05$ level for all comparisons except GPT-2 Large in the
second spillover region. This is due to the decrease in surprisal at the
critical region of the ambiguous condition (turned), as the probability of its
unlikely preceding whitespace666The LMs strongly expect a comma right after
room. is reaccounted for by the previous word (room). The resulting decrease
in surprisal difference across conditions at the critical region is carried
over to the two spillover regions. At the critical region itself, however,
this decrease is not observed as the increase in surprisal difference of its
previous word (room) cancels it out.

##  4 Conclusion

This work calls attention to an inconsistency and a confound that is inherent
in word probabilities calculated from LMs trained with subword tokenization.
These are posed by the fact that tokens have leading whitespaces in most
models, meaning that the stop probability of a whitespace word is never
explicitly calculated, which can result in word probabilities whose sum
exceeds one. We proposed WT decoding as a solution for these issues, and
demonstrated that addressing them results in lower surprisal-based estimates
of transitive/intransitive garden-path effects. Other targeted syntactic
constructions may similarly show systematic changes to probabilities of
critical words.

More generally, addressing these issues will have the biggest impact on
probabilities of words neighboring low-probability whitespaces, such as those
at potential phrasal/clausal boundaries where LMs will likely predict a
punctuation mark. While such cases may be rare in naturalistic corpora,
resolving this confound will lead to qualitatively different predictions about
the location and/or magnitude of processing difficulty at those words.
Additionally, these issues may be more pronounced for LMs that are not able to
predict word boundaries accurately, such as those trained on small amounts of
data. Therefore, future studies using LM word probabilities should be wary of
and control for them.

## Limitations

The confound in the connection between word-by-word conditional probabilities
of Transformer-based language models and self-paced reading times identified
in this work is supported by an experiment using language model variants
trained on English text and data from human subjects that are native speakers
of English. Therefore, the confound identified in this work may not generalize
to other languages, in particular those that do not use whitespace
orthography. Additionally, this work is concerned with the use of language
models as cognitive models of human sentence processing, and therefore does
not relate to their use in natural language processing applications, such as
text generation, summarization, or question answering.

## Ethics Statement

This work used data collected as part of previously published research (Huang
et al., 2024; Luke and Christianson, 2018). Readers are referred to the
respective publications for more information on the data collection and
validation procedures. As this work focuses on studying the connection between
conditional probabilities of language models and human sentence processing,
its potential negative impacts on society appear to be minimal.

## References

  * AI@Meta (2024) AI@Meta. 2024.  Llama 3 model card.  _Accessed from GitHub_.
  * Arehalli et al. (2022) Suhas Arehalli, Brian Dillon, and Tal Linzen. 2022.  Syntactic surprisal from neural models predicts, but underestimates, human processing difficulty from syntactic ambiguities.  In _Proceedings of the 26th Conference on Computational Natural Language Learning_ , pages 301–313.
  * Google Gemini Team (2024) Google Gemini Team. 2024.  Gemini: A family of highly capable multimodal models.  _arXiv preprint_ , arXiv:2312.11805v3.
  * Gorrell (1991) Paul Gorrell. 1991.  Subcategorization and sentence processing.  In R. C. Berwick, S. P. Abney, and C. Tenny, editors, _Principle-Based Parsing: Computation and Psycholinguistics_ , pages 279–300. Springer, Dordrecht.
  * 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_ , pages 1195–1205.
  * Hale (2001) John Hale. 2001.  A probabilistic Earley parser as a psycholinguistic model.  In _Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics on Language Technologies_ , pages 1–8.
  * Huang et al. (2024) Kuan-Jung Huang, Suhas Arehalli, Mari Kugemoto, Christian Muxica, Grusha Prasad, Brian Dillon, and Tal Linzen. 2024.  Large-scale benchmark yields no evidence that language model surprisal explains syntactic disambiguation difficulty.  _Journal of Memory and Language_ , 137:104510.
  * 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, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2023.  Mistral 7B.  _arXiv preprint_ , arXiv:2310.06825.
  * Kolmogorov (1933) Andrey Nikolaevich Kolmogorov. 1933.  _Foundations of the Theory of Probability_.  Julius Springer, Berlin.
  * Levy (2008) Roger Levy. 2008.  Expectation-based syntactic comprehension.  _Cognition_ , 106(3):1126–1177.
  * 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.
  * Luke and Christianson (2018) Steven G. Luke and Kiel Christianson. 2018.  The Provo Corpus: A large eye-tracking corpus with predictability norms.  _Behavior Research Methods_ , 50(2):826–833.
  * Marvin and Linzen (2018) Rebecca Marvin and Tal Linzen. 2018.  Targeted syntactic evaluation of language models.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1192–1202.
  * Mitchell (1987) Don C. Mitchell. 1987.  Lexical guidance in human parsing: Locus and processing characteristics.  In M. Coltheart, editor, _Attention and Performance XII: The Psychology of Reading_ , pages 601–618. Erlbaum, Hillsdale, NJ.
  * Nair and Resnik (2023) Sathvik Nair and Philip Resnik. 2023.  Words, subwords, and morphemes: What really matters in the surprisal-reading time relationship? In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 11251–11260.
  * Oh and Schuler (2023) Byung-Doh Oh and William Schuler. 2023.  Why does surprisal from larger Transformer-based language models provide a poorer fit to human reading times? _Transactions of the Association for Computational Linguistics_ , 11:336–350.
  * Perea and Acha (2009) Manuel Perea and Joana Acha. 2009.  Space information is important for reading.  _Vision Research_ , 49(15):1994–2000.
  * Pollatsek and Rayner (1982) Alexander Pollatsek and Keith Rayner. 1982.  Eye movement control in reading: The role of word boundaries.  _Journal of Experimental Psychology: Human Perception and Performance_ , 8(6):817–833.
  * 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 Technical Report_.
  * Rayner et al. (1998) Keith Rayner, Martin H. Fischer, and Alexander Pollatsek. 1998.  Unspaced text interferes with both word identification and eye movement control.  _Vision Research_ , 38(8):1129–1144.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics_ , pages 1715–1725.
  * Shain et al. (2024) Cory Shain, Clara Meister, Tiago Pimentel, Ryan Cotterell, and Roger Levy. 2024.  Large-scale evidence for logarithmic effects of word predictability on reading time.  _Proceedings of the National Academy of Sciences_ , 121(10):e2307876121.
  * Steuer et al. (2023) Julius Steuer, Marius Mosbach, and Dietrich Klakow. 2023.  Large GPT-like models are bad babies: A closer look at the relationship between linguistic competence and psycholinguistic measures.  In _Proceedings of the BabyLM Challenge at the 27th Conference on Computational Natural Language Learning_ , pages 142–157.
  * van Schijndel and Linzen (2021) Marten van Schijndel and Tal Linzen. 2021.  Single-stage prediction models do not explain the magnitude of syntactic disambiguation difficulty.  _Cognitive Science_ , 45(6):e12988.
  * Wilcox et al. (2023) Ethan G. Wilcox, Tiago Pimentel, Clara Meister, Ryan Cotterell, and Roger P. Levy. 2023.  Testing the predictions of surprisal theory in 11 languages.  _Transactions of the Association for Computational Linguistics_ , 11:1451–1470.