# Enforcing Consistency in Weakly Supervised Semantic Parsing

Nitish Gupta
University of Pennsylvania
<EMAIL_ADDRESS>
&Sameer Singh
University of California, Irvine
<EMAIL_ADDRESS>
&Matt Gardner
Allen Institute for AI
<EMAIL_ADDRESS>
Work done while interning with Allen Institute for AI.

###### Abstract

The predominant challenge in weakly supervised semantic parsing is that of
_spurious programs_ that evaluate to correct answers for the wrong reasons.
Prior work uses elaborate search strategies to mitigate the prevalence of
spurious programs; however, they typically consider only one input at a time.
In this work we explore the use of consistency between the output programs for
related inputs to reduce the impact of spurious programs. We bias the program
search (and thus the model’s training signal) towards programs that map the
same phrase in related inputs to the same sub-parts in their respective
programs. Additionally, we study the importance of designing logical
formalisms that facilitate this kind of consistency-based training. We find
that a more consistent formalism leads to improved model performance even
without consistency-based training. When combined together, these two insights
lead to a 10% absolute improvement over the best prior result on the Natural
Language Visual Reasoning dataset.

##  1 Introduction

Semantic parsers map a natural language utterance into an executable meaning
representation, called a logical form or program (Zelle and Mooney, 1996;
Zettlemoyer and Collins, 2005). These programs can be executed against a
context (e.g., database, image, etc.) to produce a denotation (e.g., answer)
for the input utterance. Methods for training semantic parsers from only
(utterance, denotation) supervision have been developed (Clarke et al., 2010;
Liang et al., 2011; Berant et al., 2013); however, training from such weak
supervision is challenging. The parser needs to search for the correct program
from an exponentially large space, and the presence of _spurious programs_
—incorrect representations that evaluate to the correct denotation—greatly
hampers learning. Several strategies have been proposed to mitigate this issue
Guu et al. (2017); Liang et al. (2018); Dasigi et al. (2019). Typically these
approaches consider a single input utterance at a time and explore ways to
score programs.

Figure 1:  Utterance $x$ and its program candidates $z_{1}$-$z_{4}$, all of
which evaluate to the correct denotation (True). $z_{2}$ is the correct
interpretation; other programs are _spurious_. Related utterance $x^{\prime}$
shares the phrase _yellow object above a black object_ with $x$. Our
consistency reward would score $z_{2}$ the highest since it maps the shared
phrase most similarly compared to $z^{\prime}$.

In this work we encourage consistency between the output programs of related
natural language utterances to mitigate the issue of spurious programs.
Consider related utterances, _There are two boxes with three yellow squares_
and _There are three yellow squares_ , both containing the phrase _three
yellow squares_. Ideally, the correct programs for the utterances should
contain similar sub-parts that corresponds to the shared phrase. To
incorporate this intuition during search, we propose a consistency-based
reward to encourage programs for related utterances that share sub-parts
corresponding to the shared phrases (§3). By doing so, the model is provided
with an additional training signal to distinguish between programs based on
their consistency with programs predicted for related utterances.

We also show the importance of designing the logical language in a manner such
that the ground-truth programs for related utterances are consistent with each
other. Such consistency in the logical language would facilitate the
consistency-based training proposed above, and encourage the semantic parser
to learn generalizable correspondence between natural language and program
tokens. In the previously proposed language for the Natural Language Visual
Reasoning dataset (NLVR; Suhr et al., 2017), we notice that the use of macros
leads to inconsistent interpretations of a phrase depending on its context. We
propose changes to this language such that a phrase in different contexts can
be interpreted by the same program parts (§4).

We evaluate our proposed approaches on NLVR using the semantic parser of
Dasigi et al. (2019) as our base parser. On just replacing the old logical
language for our proposed language we see an 8% absolute improvement in
consistency, the evaluation metric used for NLVR (§5). Combining with our
consistency-based training leads to further improvements; overall 10% over the
best prior model, reporting a new state-of-the-art on the NLVR dataset.

##  2 Background

In this section we provide a background on the NLVR dataset Suhr et al. (2017)
and the semantic parser of Dasigi et al. (2019).

### Natural Language Visual Reasoning (NLVR)

dataset contains human-written natural language utterances, where each
utterance is paired with 4 synthetically-generated images. Each (utterance,
image) pair is annotated with a binary truth-value denotation denoting whether
the utterance is true for the image or not. Each image is divided into three
_boxes_ , where each box contains 1-8 _objects_. Each object has four
properties: _position_ (x/y coordinates), _color_ (black, blue, yellow),
_shape_ (triangle, square, circle), and _size_ (small, medium, large). The
dataset also provides a structured representation of each image which we use
in this paper. Figure 1 shows an example from the dataset.

### Weakly supervised iterative search parser

We use the semantic parser of Dasigi et al. (2019) which is a grammar-
constrained encoder-decoder with attention model from Krishnamurthy et al.
(2017). It learns to map a natural language utterance $x$ into a program $z$
such that it evaluates to the correct denotation $y=\llbracket
z\rrbracket^{r}$ when executed against the structured image representation
$r$. Dasigi et al. (2019) use a manually-designed, typed, variable-free,
functional query language for NLVR, inspired by the GeoQuery language Zelle
and Mooney (1996).

Given a dataset of triples ($x_{i}$, $c_{i}$, $y_{i}$), where $x_{i}$ is an
utterance, $c_{i}$ is the set of images associated to it, and $y_{i}$ is the
set of corresponding denotations, their approach iteratively alternates
between two phases to train the parser: Maximum marginal likelihood (MML) and
a Reward-based method (RBM). In MML, for an utterance $x_{i}$, the model
maximizes the marginal likelihood of programs in a given set of logical forms
$Z_{i}$, all of which evaluate to the correct denotation. The set $Z_{i}$ is
constructed either by performing a heuristic search, or generated from a
trained semantic parser.

The reward-based method maximizes the (approximate) expected value of a reward
function $\mathcal{R}$.

$\max_{\theta}\sum_{\forall
i}\mathbb{E}_{\tilde{p}(z_{i}|x_{i};\theta)}\mathcal{R}(x_{i},z_{i},c_{i},y_{i})$
(1)

Here, $\tilde{p}$ is the _re-normalization_ of the probabilities assigned to
the programs on the beam, and the reward function $\mathcal{R}=1$ if $z_{i}$
evaluates to the correct denotation for all images in $c_{i}$, or $0$
otherwise. Please refer Dasigi et al. (2019) for details.

##  3 Consistency reward for programs

Consider the utterance $x$ = _There is a yellow object above a black object_
in Figure 1. There are many program candidates decoded in search that evaluate
to the correct denotation. Most of them are _spurious_ , i.e., they do not
represent the meaning of the utterance and only coincidentally evaluate to the
correct output. The semantic parser is expected to distinguish between the
correct program and spurious ones by identifying correspondence between parts
of the utterance and the program candidates. Consider a related utterance
$x^{\prime}$ = _There are 2 boxes with a yellow object above a black object_.
The parser should prefer programs for $x$ and $x^{\prime}$ which contain
similar sub-parts corresponding to the shared phrase $p$ =  _yellow object
above a black object_. That is, the parser should be consistent in its
interpretation of a phrase in different contexts. To incorporate this
intuition during program search, we propose an additional reward to programs
for an utterance that are consistent with programs for a related utterance.

Specifically, consider two related utterances $x$ and $x^{\prime}$ that share
a phrase $p$. We compute a reward for a program candidate $z$ of $x$ based on
how similarly it maps the phrase $p$ as compared to a program candidate
$z^{\prime}$ of $x^{\prime}$. To compute this reward we need (a)  _relevant
program parts_ in $z$ and $z^{\prime}$ that correspond to the phrase $p$, and
(b) a _consistency reward_ that measures consistency between those parts.

### (a) Relevant program parts

Let us first see how to identify relevant parts of a program $z$ that
correspond to a phrase $p$ in the utterance.

Our semantic parser (from Krishnamurthy et al. (2017)) outputs a linearized
version of the program $z=[z^{1},\ldots,z^{T}]$, decoding one action at a time
from the logical language. At each time step, the parser predicts a normalized
attention vector over the tokens of the utterance, denoted by
$[a^{t}_{1},\ldots,a^{t}_{N}]$ for the $z^{t}$ action. Here,
$\sum_{i=1}^{N}a^{t}_{i}=1$ and $a^{t}_{i}\geq 0$ for $i\in[1,N]$. We use
these attention values as a relevance score between a program action and the
utterance tokens. Given the phrase $p$ with token span $[m,n]$, we identify
the relevant actions in $z$ as the ones whose total attention score over the
tokens in $p$ exceeds a heuristically-chosen threshold $\tau=0.6$.

$A(z,p)=\Big{\\{}z^{t}\;\big{|}\;t\in[1,T]\;\text{and}\;\sum_{i=m}^{n}a^{t}_{i}\geq\tau\Big{\\}}$
(2)

This set of program actions $A(z,p)$ is considered to be generated due to the
phrase $p$. For example, for utterance _There is a yellow object above a black
object_ , with program objExists(yellow(above(black(allObjs))), this approach
could identify that for the phrase _yellow object above a black object_ the
actions corresponding to the functions yellow, above, and black are relevant.

### (b) Consistency reward

Now, we will define a reward for the program $z$ based on how consistent its
mapping of the phrase $p$ is w.r.t. the program $z^{\prime}$ of a related
utterance. Given a related program $z^{\prime}$ and its relevant action set
$A(z^{\prime},p)$, we define the consistency reward $S(z,z^{\prime},p)$ as the
F1 score for the action set $A(z,p)$ when compared to $A(z^{\prime},p)$. If
there are multiple shared phrases $p_{i}$ between $x$ and $x^{\prime}$, we can
compute a weighted average of different $S(z,z^{\prime},p_{i})$ to compute a
singular consistency reward $S(z,z^{\prime})$ between the programs $z$ and
$z^{\prime}$. In this work, we only consider a single shared phrase $p$
between the related utterances, hence $S(z,z^{\prime},p)=S(z,z^{\prime},p)$ in
our paper.

As we do not know the gold program for $x^{\prime}$, we decode top-K program
candidates using beam-search and discard the ones that do not evaluate to the
correct denotation. We denote this set of programs by $Z^{\prime}_{c}$. Now,
to compute a consistency reward $\mathcal{C}(x,z,x^{\prime})$ for the program
$z$ of $x$,we take a weighted average of $S(z,z^{\prime})$ for different
$z^{\prime}\in Z^{\prime}_{c}$ where the weights correspond to the probability
of the program $z^{\prime}$ as predicted by the parser.

$\mathcal{C}(x,z,x^{\prime})=\sum_{z^{\prime}\in
Z^{\prime}_{c}}\tilde{p}(z^{\prime}|x^{\prime};\theta)S(z,z^{\prime})$ (3)

### Consistency reward based parser

Given $x$ and a related utterance $x^{\prime}$, we use
$\mathcal{C}(x,z,x^{\prime})$ as an additional reward in Eq. 1 to upweight
programs for $x$ that are consistent with programs for $x^{\prime}$.

$\max_{\theta}\sum_{\forall
i}\mathbb{E}_{\tilde{p}(z_{i}|x_{i};\theta)}\big{[}\mathcal{R}(x_{i},z_{i},c_{i},y_{i})+\mathcal{C}(x_{i},z_{i},x^{\prime}_{i})\big{]}$

This consistency-based reward pushes the parser’s probability mass towards
programs that have consistent interpretations across related utterances, thus
providing an additional training signal over simple denotation accuracy. The
formulation presented in this paper assumes that there is a single related
utterance $x^{\prime}$ for the utterance $x$. If multiple related utterances
are considered, the consistency reward $\mathcal{C}(x,z,x^{\prime}_{j})$ for
different related utterances $x^{\prime}_{j}$ can be summed/averaged to
compute a single consistency reward $\mathcal{C}(x,z)$ the program $z$ of
utterance $x$ based on all the related utterances.

Model | Dev | Test-P | Test-H
---|---|---|---
Acc. | Cons. | Acc. | Cons. | Acc. | Cons.
Abs. Sup. Goldman et al. (2018) | 84.3 | 66.3 | 81.7 | 60.1 | - | -
Abs. Sup. + ReRank Goldman et al. (2018) | 85.7 | 67.4 | 84.0 | 65.0 | 82.5 | 63.9
Iterative Search Dasigi et al. (2019) | 85.4 | 64.8 | 82.4 | 61.3 | 82.9 | 64.3
\+ Logical Language Design (ours) | 88.2 | 73.6 | 86.0 | 69.6 | - | -
\+ Consistency Reward (ours) | 89.6 | 75.9 | 86.3 | 71.0 | 89.5 | 74.0
Table 1:  Performance on NLVR: Design changes in the logical language and
consistency-based training, both significantly improve performance. Larger
improvements in consistency indicate that our approach efficiently tackles
spurious programs.

##  4 Consistency in Language

The consistency reward (§3) makes a key assumption about the logical language
in which the utterances are parsed: that the gold programs for utterances
sharing a natural language phrase actually correspond to each other. For
example, that the phrase _yellow object above a black object_ would always get
mapped to yellow(above(black)) irrespective of the utterance it occurs in.

On analyzing the logical language of Dasigi et al. (2019), we find that this
assumption does not hold true. Let us look at the following examples:
$x_{1}$: _There are items of at least two different colors_
$z_{1}$: objColorCountGrtEq(2, allObjs)
$x_{2}$: _There is a box with items of at least two different colors_
$z_{2}$: boxExists(
memberColorCountGrtEq(2, allBoxes))
Here the phrase _items of at least two different colors_ is interpreted
differently in the two utterances. In $x_{2}$, a macro function
memberColorCountGrtEq is used, which internally calls objColorCountGrtEq for
each _box_ in the image. Now consider,
$x_{3}$: _There is a tower with exactly one block_
$z_{3}$: boxExists(memberObjCountEq(1,allBoxes))
$x_{4}$: _There is a tower with a black item on the top_
$z_{4}$: objExists(black(top(allObjs)))
Here the phrase _There is a tower_ is interpreted differently: $z_{3}$ uses a
macro for filtering boxes based on their object count and interprets the
phrase using boxExists. In the absence of a complex macro for checking _black
item on the top_ , $z_{4}$ resorts to using objExists making the
interpretation of the phrase inconsistent. These examples highlight that these
macros, while they shorten the search for programs, make the language
inconsistent.

We make the following changes in the logical language to make it more
consistent. Recall from §2 that each NLVR image contains 3 boxes each of which
contains 1-8 objects. We remove macro functions like memberColorCountGrtEq,
and introduce a generic boxFilter function. This function takes two arguments,
a set of _boxes_ and a filtering function f:
$\text{{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}{Set[Obj]}}}\rightarrow\text{{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}{bool}}}$,
and prunes the input set of boxes to the ones whose objects satisfies the
filter f. By doing so, our language is able to reuse the same object filtering
functions across different utterances. In this new language, the gold program
for the utterance $x_{2}$ would be
$z_{2}$: boxCountEq(1, boxFilter(allBoxes,
objColorCountGrtEq(2)))
By doing so, our logical language can now consistently interpret the phrase
_items of at least two different colors_ using the object filtering function
f: objColorCountGrtEq(2) across both $x_{1}$ and $x_{2}$. Similarly, the gold
program for $x_{4}$ in the new logical language would be
$z_{4}$: boxExists(boxFilter(allBoxes, black(top)))
making the interpretation of _There is a box_ consistent with $x_{3}$. Please
refer appendix §A for details.

##  5 Experiments

### Dataset

We report results on the standard development, public-test, and hidden-test
splits of NLVR. The training data contains 12.4k (utterance, image) pairs
where each of 3163 utterances are paired with $4$ images. Each evaluation set
roughly contains 270 unique utterances.

### Evaluation Metrics

(1)  _Accuracy_ measures the proportion of examples for which the correct
denotation is predicted. (2) Since each utterance in NLVR is paired with 4
images, a _consistency_ metric is used, which measures the proportion of
utterances for which the correct denotation is predicted for all associated
images. Improvement in this metric is indicative of correct program prediction
as it is unlikely for a spurious program to correctly make predictions on
multiple images.

### Experimental details

We use the same parser, training methodology, and hyper-parameters as Dasigi
et al. (2019). For discovering related utterances, we manually identify
$\sim$10 sets of equivalent phrases that are common in NLVR. For example,
_there are _NUM_ boxes_, __COLOR1_ block on a _COLOR2_ block_, etc. For each
utterance that contains a particular phrase, we pair it with one other
randomly chosen utterance that shares the phrase. We make 1579 utterance pairs
in total. Refer appendix §B for details about data creation.111We release the
data and code at https://www.github.com/nitishgupta/allennlp-
semparse/tree/nlvr-v2/scripts/nlvr_v2

### Baselines

We compare against the state-of-the-art models; Abs. Sup. Goldman et al.
(2018) that uses abstract examples, Abs. Sup. + ReRank that uses additional
data and reranking, and the iterative search parser of Dasigi et al. (2019).

### Results

Table 1 compares the performance of our two proposed methods to enforce
consistency in the decoded programs with the previous approaches. We see that
changing the logical language to a more consistent one (§4) significantly
improves performance: the accuracy improves by 2-4% and consistency by 4-8% on
the dev. and public-test sets. Additionally, training the parser using our
proposed consistency reward (§3) further improves performance: accuracy
improves by 0.3-0.4% but the consistency significantly improves by
1.4-2.3%.222We report average performance across 10 runs trained with
different random seeds. All improvements in consistency are statistically
significant (p-value $<$ 0.05) based on the stochastic ordering test Dror et
al. (2019). On the hidden-test set of NLVR, our final model improves accuracy
by 7% and consistency by 10% compared to previous approaches. Larger
improvements in consistency across evaluation sets indicates that our approach
to enforce consistency between programs of related utterances greatly reduces
the impact of spurious programs.

##  6 Conclusion

We proposed two approaches to mitigate the issue of spurious programs in
weakly supervised semantic parsing by enforcing consistency between output
programs. First, a consistency based reward that biases the program search
towards programs that map the same phrase in related utterances to similar
sub-parts. Such a reward provides an additional training signal to the model
by leveraging related utterances. Second, we demonstrate the importance of
logical language design such that it facilitates such consistency-based
training. The two approaches combined together lead to significant
improvements in the resulting semantic parser.

## Acknowledgement

We would like to thank Pradeep Dasigi for helping us with the code for
preprocessing NLVR and the Iterative Search model, Alane Suhr for getting us
our model’s evaluation results on the hidden test set in a timely manner, and
the anonymous reviewers for their helpful comments. This work is supported in
part by NSF award #IIS-1817183.

## References

  * Berant et al. (2013) Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013.  Semantic parsing on Freebase from Question-Answer pairs.  In _EMNLP_.
  * Clarke et al. (2010) James Clarke, Dan Goldwasser, Ming-Wei Chang, and Dan Roth. 2010.  Driving semantic parsing from the world’s response.  In _CoNLL_.
  * Dasigi et al. (2019) Pradeep Dasigi, Matt Gardner, Shikhar Murty, Luke Zettlemoyer, and E. Hovy. 2019\.  Iterative search for weakly supervised semantic parsing.  In _NAACL-HLT_.
  * Dror et al. (2019) Rotem Dror, Segev Shlomov, and Roi Reichart. 2019.  Deep dominance-how to properly compare deep neural models.  In _ACL_.
  * Goldman et al. (2018) Omer Goldman, Veronica Latcinnik, Udi Naveh, A. Globerson, and Jonathan Berant. 2018\.  Weakly-supervised semantic parsing with abstract examples.  In _ACL_.
  * Guu et al. (2017) Kelvin Guu, Panupong Pasupat, E. Liu, and Percy Liang. 2017.  From language to programs: Bridging reinforcement learning and maximum marginal likelihood.  In _ACL_.
  * Krishnamurthy et al. (2017) Jayant Krishnamurthy, Pradeep Dasigi, and Matt Gardner. 2017.  Neural semantic parsing with type constraints for semi-structured tables.  In _EMNLP_.
  * Liang et al. (2018) Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoc V. Le, and N. Lao. 2018.  Memory augmented policy optimization for program synthesis and semantic parsing.  In _NeurIPS_.
  * Liang et al. (2011) Percy S. Liang, Michael I. Jordan, and Dan Klein. 2011.  Learning dependency-based compositional semantics.  _Computational Linguistics_.
  * Suhr et al. (2017) Alane Suhr, M. Lewis, James Yeh, and Yoav Artzi. 2017.  A corpus of natural language for visual reasoning.  In _ACL_.
  * Zelle and Mooney (1996) John M Zelle and Raymond J Mooney. 1996.  Learning to parse database queries using inductive logic programming.  In _Proceedings of the national conference on artificial intelligence_.
  * Zettlemoyer and Collins (2005) Luke S Zettlemoyer and Michael Collins. 2005.  Learning to map sentences to logical form: structured classification with probabilistic categorial grammars.  In _UAI ’05_.

##  Appendix A Logical language details

In Figure 2, we show an example utterance with its gold program according to
our proposed logical language. We use function composition and function
currying to maintain the variable-free nature of our language. For example,
action $z^{7}$ uses function composition to create a function from Set[Object]
$\rightarrow$ bool by composing two functions, from Set[Object] $\rightarrow$
bool and Set[Object] $\rightarrow$ Set[Object]. Similarly, action $z^{11}$
creates a function from Set[Object] $\rightarrow$ Set[Object] by composing two
functions with the same signature.

Actions $z^{8}$ \- $z^{10}$ use function currying to curry the 2-argument
function objectCountGtEq by giving it one int=2 argument. This results in a
1-argument function objectCountGtEq(2) from Set[Object] $\rightarrow$ bool.

$x$: _There is one box with at least 2 yellow squares_ $z$: boxCountEq(1,
boxFilter(allBoxes, objectCountGtEq(2)(yellow(square)))) Program actions for
$z$: $z^{1}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{bool}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{[$<$int,[Set[Box]:bool$>$,
int, Set[Box]]}}$ $z^{2}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{$<$int,[Set[Box]:bool$>$}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{boxCountEq}}$
$z^{3}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{int}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{1}}$
$z^{4}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{Set[Box]}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{[$<$Set[Box],$<$Set[Object]:bool$>$:Set[Box]$>$,
Set[Box], $<$Set[Object]:bool$>$]}}$ $z^{5}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{$<$Set[Box],$<$Set[Object]:bool$>$:Set[Box]$>$}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{boxFilter}}$
$z^{6}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{Set[Box]}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{allBoxes}}$
$z^{7}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{$<$Set[Object]:bool$>$}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{[*,
$<$Set[Object]:bool$>$, $<$Set[Object]:Set[Object]$>$]}}$ $z^{8}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{$<$Set[Object]:bool$>$}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{[$<$int,Set[Object]:bool$>$,
int]}}$ $z^{9}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{$<$int,Set[Object]:bool$>$}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{objectCountGtEq}}$
$z^{10}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{int}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{2}}$
$z^{11}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{$<$Set[Object]:Set[Object]$>$}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{[*,
$<$Set[Object]:Set[Object]$>$, $<$Set[Object]:Set[Object]$>$]}}$ $z^{12}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{$<$Set[Object]:Set[Object]$>$}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{yellow}}$
$z^{13}$:
${\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{$<$Set[Object]:Set[Object]$>$}}\rightarrow{\color[rgb]{0,0.375,0.375}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.375,0.375}\texttt{square}}$

Figure 2:  Gold program actions for the utterance _There is one box with at
least 2 yellow squares_ according to our proposed logical language. The
grammar-constrained decoder outputs a linearized abstract-syntax tree of the
program in an in-order traversal.

##  Appendix B Dataset details

To discover related utterance pairs within the NLVR dataset, we manually
identify 11 sets of phrases that commonly occur in NLVR and can be interpreted
in the same manner:

  1. 1.

{ COLOR block at the base, the base is COLOR }

  2. 2.

{ COLOR block at the top, the top is COLOR }

  3. 3.

{ COLOR1 object above a COLOR2 object }

  4. 4.

{ COLOR1 block on a COLOR2 block, COLOR1 block over a COLOR2 block }

  5. 5.

{ a COLOR tower }

  6. 6.

{ there is one tower, there is only one tower, there is one box, there is only
one box }

  7. 7.

{ there are exactly NUMBER towers, there are exactly NUMBER boxes }

  8. 8.

{ NUMBER different colors }

  9. 9.

{ with NUMBER COLOR items, with NUMBER COLOR blocks, with NUMBER COLOR objects
}

  10. 10.

{ at least NUMBER COLOR items, at least NUMBER COLOR blocks, at least NUMBER
COLOR objects }

  11. 11.

{ with NUMBER COLOR SHAPE, are NUMBER COLOR SHAPE, with only NUMBER COLOR
SHAPE, are only NUMBER COLOR SHAPE }

In each phrase, we replace the abstract COLOR, NUMBER, SHAPE token with all
possible options from the NLVR dataset to create grounded phrases. For
example, _black block at the top_ , _yellow object above a blue object_. For
each set of equivalent grounded phrases, we identify the set of utterances
that contains any of the phrase. For each utterance in that set, we pair it
with 1 randomly chosen utterance from that set. Overall, we identify related
utterances for 1420 utterances (out of 3163) and make 1579 pairings in total;
if an utterance contains two phrases of interest, it can be paired with more
than 1 utterance.


spacing=nonfrench

††thanks: These authors have contributed equally to this manuscript. For
correspondence<EMAIL_ADDRESS>These authors have contributed
equally to this manuscript. For correspondence<EMAIL_ADDRESS>
# Estimating the volumes of correlations sets in causal networks

Giulio Camillo  Instituto de Física, Universidade de São Paulo, 05508-220, São
Paulo, Brasil  Pedro Lauand  Instituto de Física “Gleb Wataghin”, Universidade
Estadual de Campinas, 130830-859, Campinas, Brazil  Davide Poderini
International Institute of Physics, Federal University of Rio Grande do Norte,
59078-970, Natal, Brazil  Rafael Rabelo  Instituto de Física “Gleb Wataghin”,
Universidade Estadual de Campinas, 130830-859, Campinas, Brazil  Rafael Chaves
International Institute of Physics, Federal University of Rio Grande do Norte,
59078-970, Natal, Brazil  School of Science and Technology, Federal University
of Rio Grande do Norte, Natal, Brazil

###### Abstract

Causal networks beyond that in the paradigmatic Bell’s theorem can lead to new
kinds and applications of non-classical behavior. Their study, however, has
been hindered by the fact that they define a non-convex set of correlations
and only very incomplete or approximated descriptions have been obtained so
far, even for the simplest scenarios. Here, we take a different stance on the
problem and consider the relative volume of classical or non-classical
correlations a given network gives rise to. Among many other results, we show
instances where the inflation technique, arguably the most disseminated tool
in the community, is unable to detect a significant portion of the non-
classical behaviors. Interestingly, we also show that the use of
interventions, a central tool in causal inference, can enhance substantially
our ability to witness non-classicality.

##  I Introduction

The violation of Bell inequalities [1] represents the strongest signature of
non-classical behavior, as it can be observed in a device-independent context
[2]. Specifically, it demonstrates the incompatibility between quantum
correlations and classical concepts of cause and effect, without relying on
any assumptions about the internal mechanisms involved in the preparation and
measurement of the physical system being analyzed.

In the simplest Bell scenario, two distant parties measure two distinct
dichotomic observables. However, this scenario has been extended and
generalized in various ways. These extensions include incorporating additional
measurements [3] or expanding the number of possible outcomes [4].
Furthermore, the framework has been expanded to involve multiple parties [5]
and relaxations of locality assumptions [6, 7], as well as measurement
independence [8, 9]. Of particular significance are recent advancements that
draw inspiration from causality theory [10]. These generalizations explore
networks with diverse topologies, growing in size and complexity, revealing a
number of novel non-classical phenomena [11, 12, 13, 14, 15, 16, 17, 18].

In the context of a specific causal structure, a central inquiry arises: does
it exhibit a classical-quantum gap? In other words, if the sources within the
network are described by entangled quantum states, can measurements on them
produce correlations that lack a classical interpretation? When considering
networks with a single source, a classical depiction involves the
characterization of a polytope [19]: a convex set defined by a finite number
of extremal points or, equivalently, a finite set of linear Bell inequalities.
However, even in such cases, the problem is recognized as intrinsically
challenging, residing in the NP-hard complexity class [19]. This difficulty is
further amplified when independent sources of correlations exist, as is often
the case in paradigmatic quantum networks. In such scenarios, the correlations
compatible with a given causal structure result in non-convex sets,
necessitating computationally intensive algorithms rooted in algebraic
geometry [20] or various forms of approximation [21, 22, 23, 24, 25, 26]
proposed throughout the years. Not surprisingly, given these difficulties,
there is still a very fragmented picture of the set of correlations causal
networks can give rise to.

Here we propose an alternative route to gather further insights into the
classical description of causal networks and their potential incompatibility
with quantum correlations. Using quadratic optimization techniques (leveraging
the Gurobi optimizer [27]), already employed to address non-convex constraints
originating from causal networks in [28], as well as other tools such as the
inflation technique [26], the covariance approach [24] and Finner inequality
[29], we calculate the volumes [30, 31] of classical and non-classical
probability distributions that various causal structures can yield. As we
show, in spite of its wide applicability and convergence in the asymptotic
limit [32], in computational practice the inflation technique might offer
relatively poor performance, since it is unable to reveal a significant
portion of non-classical behaviors. Interestingly, similarly to what happens
in the standard Bell scenario [33], we observe a concentration effect where
most non-classical points concentrate an average distance from the classical
set, the probability of finding points far away decaying exponentially.
Finally, we show that the use of interventions [34, 35] can significantly
enhance our ability to detect non-classical behaviors.

The paper is organized as follows. In Sec. II we introduce the framework and
methods underlying our work, including the definition of causal models and the
three different causal networks that we study; we also describe the sampling
method and the witness of non-classicality we have employed. In Sec. III, for
each of the three causal networks analyzed, we present the results on the
volume estimation regarding different sets of correlations (classical,
quantum, and non-signaling) as well as using different methods. In Sec. IV we
discuss our findings and point out relevant questions and directions for
future research.

##  II Preliminaries

###  II.1 Causal models

The causal modeling framework [10, 36] offers a powerful language to describe
causal constraints in terms of _directed acyclic graphs_ (DAG). In this
formalism, each node $A\in N(G)$ of the DAG $G$ is associated with a random
variable and causal relationships are defined by the directed edges
$E(G)\subseteq N(G)\times N(G)$ between these nodes. In any real situation, we
do not have access to every relevant cause that can influence our system, we
then ought to distinguish between nodes that are associated with _observable_
variables $\mathcal{O}_{G}\subseteq N(G)$ and unobserved, or _latent_ , ones
$\mathcal{L}_{G}\subseteq N(G)$. Graphically, we will use circles and Latin
letters for the former and triangles and Greek letters for the latter (see for
example Fig. 1). Moreover, the random variables and the nodes will be
represented with uppercase letters $A,B,\ldots$ while we will use the
corresponding lowercase ones $a,b,\ldots$ to denote their outcomes.

Given a DAG $G$, we can define the concept of causal parents
$\operatorname{Pa}(A)$ (or children $\operatorname{Ch}(A)$) of a given
variable $A$ in $G$, as the set of nodes sharing incoming (or outgoing) edges
with $A$. This notion immediately give us a way to define what it means, for a
classical joint distribution $p(\\{a_{i}\\}_{i})$ on the random variables
associated with observable nodes $A_{i}\in\mathcal{O}_{G}$, to be compatible
with a causal DAG $G$.

######  Definition (Classical compatibility).

A distribution $p(\\{a_{i}\\}_{i})$ on the random variable associated with the
nodes $\mathcal{O}(G)$, is compatible with $G$ if it satisfies the following
decomposition:

$p(\\{a_{i}\\}_{i})=\sum_{\lambda\in\mathcal{L}_{G}}\prod_{X\in
N_{G}}p(x|\operatorname{pa}(X))$ (1)

where $\mathcal{L}_{G}\subset N_{G}$ is the set of latent variables in $G$ and
$\operatorname{pa}(X)$ the set of outcomes of all the parents of $X$.

The above decomposition is also called _global Markov condition_. We will use
$\mathcal{C}(G)$ to represent the set of distributions compatible in this
sense with a DAG $G$.

The compatibility notion defined above is valid only if we consider that our
distribution $p$ arises from models where latent variables can be considered
classical systems. If instead, we allow them to be quantum systems, in
general, we obtain a strictly larger set of compatible distributions, which we
can denote by $\mathcal{Q}(G)$ and for which generalizations of the global
Markov condition and the concept of a causal structure have been proposed [37,
38, 39, 40]

In some cases, it might be interesting to consider post-quantum resources
distributed in the network [41]. The distributions that may arise from these
models must respect some basic conditions that reflect the natural assumptions
of no-signaling and independence of the sources (NSI). The core of the notion
of the no-signaling principle to network scenarios is that the outcomes of one
party should be insensitive to whatever the remaining parties do, including
any local modifications in the particular arrangement of the topology of their
part of the network. The set of correlations that arise from NSI has been
explicitly studied primarily in the triangle scenario [42] and in the Evans
scenario [28]. We denote the set of correlations that is compatible with the
principles of no-signaling and independence as $\mathcal{N}(G)$. We remark
that the resulting constraints derived from NSI will be valid for all general
probabilistic theories [43] (GPTs).

###  II.2 Single-source Bell scenario

Bell’s paradigmatic causal structure (and multipartite generalization thereof)
is composed by a number of parties, sharing classical correlations described
by a random variable $\Lambda$, locally measuring different observables
parametrized by $X,Y,Z,\ldots$ with corresponding measurement outcomes
$A,B,C,\ldots$. This classical description is encoded in the class of DAGs
$L_{n}$ represented in Fig. 1(a), implying that the observed distributions
should follow the Markov condition given by

$\displaystyle p(a,b,c,\cdots|x,y,z,\cdots)=$ (2)
$\displaystyle\sum_{\lambda}p(\lambda)p(a|x,\lambda)p(b|y,\lambda)p(c|z,\lambda)\dots.$

$\Lambda$$A$$X$$B$$Y$$C$$Z$ (a) Multipartite Bell scenario

$\Lambda$$\Gamma$$A$$B$$C$$X$$Z$ (b) Bilocality scenario

$A$$C$$\Lambda$$\Gamma$$B$ (c) Evans scenario

$\Lambda$$A$$M$$C$$\Gamma$$B$ (d) Triangle scenario

Figure 1: Causal DAGs a) Multipartite Bell scenario where the correlations
between the distant parties are mediated by a single source of correlations.
b) Bilocality scenario, akin to an entanglement swapping experiment [44],
where two independent sources establish the correlations between three
spatially separated parties. c) The Evans scenario with two independent
sources of correlations but with a crucial difference to the bilocality case:
the inputs for two of the parties are the measurement outputs of the central
node, that is, the correlations are time-like and not space-like separated. d)
The triangle scenario, where every party shares a bipartite and independent
source of correlations with every other party.

In a quantum description, this probability distribution is given by the Born
rule

$p(a,b,c,\cdots|x,y,z,\cdots)=\tr\left[\left(A^{a}_{x}\otimes B^{b}_{y}\otimes
C^{c}_{z}\otimes\cdots\right)\;\rho_{\Lambda}\right]\,,$ (3)

where the measurement inputs and outputs are associated with POVMs (positive
operator valued measurements) and the classical node $\Lambda$ is replaced by
a multipartite (potentially entangled) state $\rho_{\Lambda}$.

Due to the absence of a causal link between nodes associated with different
parties, we also expect any compatible distribution to respect some general
linear constraints, expressing their independence in terms of the observable
distribution, which are called no-signaling constraints [45] defining a set
$\mathcal{N}_{n}$:

$\displaystyle p(a|x,y,z,\ldots)$
$\displaystyle=p(a|x,y^{\prime},z^{\prime},\ldots)\quad\forall
a,y,y^{\prime},z,z^{\prime},\ldots$ $\displaystyle p(b|x,y,z,\ldots)$
$\displaystyle=p(b|x^{\prime},y,z^{\prime},\ldots)\quad\forall
b,x,x^{\prime},z,z^{\prime},\ldots$ $\displaystyle\vdots$ (4)

for each party $A,B,C,\ldots$, where $p(a|x,y,z,\ldots)$ is the
marginalization of the distribution over all the other variables different
from $A$.

In the case of a single source of correlations,
$\mathcal{C}(L_{n}),\mathcal{Q}(L_{n}),\mathcal{N}(L_{n})$ are all convex
sets, and, in particular, $\mathcal{C}(L_{n})$ and $\mathcal{N}(L_{n})$ can be
described by a finite number of constraints, making them convex polytopes.
Moreover, it is known that
$\mathcal{C}(L_{n})\subset\mathcal{Q}(L_{n})\subset\mathcal{N}(L_{n})$. More
recently, the connection between causal modeling and Bell inequalities
prompted the study of the relationships between these correlation sets in more
complex causal scenarios that can also include independence between latent
variables. In this case, the geometry of the correlation sets becomes
considerably more complicated, making them even non-convex in general. In our
paper, we focused on three such models, the bilocality scenario [11], the
triangle scenario [12, 13] and the Evans Scenario [46, 28], which we will now
describe in more detail.

###  II.3 Bilocality scenario

The bilocality scenario [11], represented by the DAG $B$ in Fig. 1(b),
presents two independent sources $\Lambda$ and $\Gamma$ which distribute
correlations to three nodes, $A$, $B$, and $C$ that can perform measurements
chosen by the settings $X$ and $Y$ for $A$ and $C$ respectively, while the
central node $B$ has no external settings. As in the Bell case, we can
distinguish different sets of compatible distributions associated with such a
model. The Markov condition (1) for this structure is given by

$p(a,b,c|x,z)=\\\
=\sum_{\lambda,\gamma}p(\lambda)p(\gamma)p(a|x,\lambda)p(c|z,\gamma)p(b|\lambda,\gamma)\,.$
(5)

As anticipated such a condition complicates considerably the characterization
of the set of allowed correlation $\mathcal{C}(B)$, which is known to be non-
convex, as proved by the existence of polynomial Bell inequalities [22].

Quantum distributions in this scenario $p\in\mathcal{Q}(B)$ are instead
defined by

$p(a,b,c|x,z)=\tr\left[\left(A^{a}_{x}\otimes B^{b}\otimes
C^{c}_{z}\right)\left(\rho_{\Lambda}\otimes\rho_{\Gamma}\right)\right]\,,$ (6)

for any couple of bipartite quantum states $\rho_{\Lambda},\rho_{\Gamma}$ and
any set of POVMs with operators $A^{a}_{x},B^{b},C^{c}_{z}$.

Similarly to the multipartite Bell scenarios, here we have that some of the
correlations in the quantum set $\mathcal{Q}(B)$ are incompatible with a
classical description (5), even when some of them are still compatible with
the one in the tripartite Bell scenario $\mathcal{C}(L_{3})$, showing how the
assumption of independence between $\Lambda$ and $\Gamma$ increases the
possibility to detect nonclassicality.

Also in this scenario, we expect correlations to respect some basic
constraints given in terms of their observable distribution. But differently
from the standard multipartite Bell case, besides the linear constraints (4),
here we have some additional nonlinear ones due to the conditional
independence between the two sources. More specifically, it follows that

$p(a,c|x,z)=\sum_{b}p(a,b,c|x,z)=p(a|x)p(c|z)\,$ (7)

making this set strictly included in the set of non-signaling correlations in
the tripartite Bell scenario $\mathcal{N}_{3}$. We will denote this set of
non-signaling bilocal correlations by $\mathcal{N}(B)\subset\mathcal{N}_{3}$.

(a) 2nd order quantum inflation for the Triangle scenario.

(b) 3rd order quantum inflation for the Triangle scenario.

(c) 2nd order quantum inflation for the Bilocality scenario.

(d) 3rd order quantum inflation for the Bilocality scenario.

Figure 2: The DAGs for the orders used in our analysis for quantum inflation.
Here we, similarly to the classical case, considered the first two levels of
standard quantum inflation hierarchy [47], generated by using $n$ copies of
each latent variable. As in the other figures, latent nodes are represented by
triangles while observable nodes with circles.

###  II.4 Triangle scenario

The triangle scenario [12] is represented by the DAG in Fig. 1(d), where three
bipartite sources distribute systems to three separate parties forming a
triangle-shaped structure. The reason why this network is of particular
interest to the community is that it allows for novel non-classical phenomena
[13, 17, 48]. In particular, it allows for non-classicality even in the
absence of measurement choices for the parties, that is, when they perform a
fixed measurement [12, 16].

Classically, triangle correlations admit models given by

$p(a,b,c)=\sum_{\lambda,\gamma,\mu}p(\lambda)p(\gamma)p(\mu)p(a|\lambda,\mu)p(b|\lambda,\gamma)p(c|\gamma,\mu),$
(8)

while the quantum description is given by 111Note that when evaluating $p$,
one should be attentive to which Hilbert space supports each state and
measurements.

$p(a,b,c)=\tr\left[\left(A^{a}\otimes B^{b}\otimes
C^{c}\right)\left(\rho_{\Lambda}\otimes\rho_{\Gamma}\otimes\rho_{M}\right)\right].$
(9)

Differently from the standard Bell or the bilocality cases, the triangle does
not have a simple NSI description, even though a few approximations have
already been proposed [42, 41, 37, 50, 26].

Furthermore, the case where all parts have binary outputs is particularly
interesting. Recently, [51] has shown that this minimal case supports post-
quantum advantage, i.e. the local set and the non-signaling set do not
coincide, and also that the set of triangle non-signaling correlations lies
outside the quantum set. Strikingly, the conjecture that the local and quantum
sets are identical [52] remains open for this minimal case.

###  II.5 Evans scenario

The last causal structure we will consider is the so-called Evans scenario
[46], which was only recently considered from a quantum perspective [28]. The
DAG $E$ for this structure is represented in Fig. 1(c). Just like in the
bilocality scenario, we have three observable nodes $A,B,C$ and two latent
ones $\Lambda,\Gamma$, with the difference that now there are no external
inputs present, and $B$ can communicate directly its value to both $A$ and
$C$.

Equation (1) in this case becomes

$p(a,b,c)=\sum_{\lambda,\gamma}p(\lambda)p(\gamma)p(a|b,\lambda)p(c|b,\gamma)p(b|\lambda,\gamma),\,$
(10)

and the quantum distribution is given by

$p(a,b,c)=\tr\left[\left(A^{a}_{b}\otimes B^{b}\otimes
C^{c}_{b}\right)\left(\rho_{\Lambda}\otimes\rho_{\Gamma}\right)\right],$ (11)

for quantum states $\rho_{\Lambda},\rho_{\Gamma}$ and POVMs
$A^{a}_{b},B^{b},C^{c}_{b}$.

Despite apparent similarities with the bilocal scenario, the characterization
of the classical and quantum sets $\mathcal{C}(E),\mathcal{Q}(E)$ turns out to
be much more complex [28], and whether the inclusion of the former in the
latter is strict or not is still an open problem.

The set of non-signaling correlations of the Evans scenario is also poorly
understood. Although a general route for deriving such theory-independent
constraints for this causal structure has been proposed in [28], it relies on
Fourier-Motzkin elimination which can be very costly and out of computational
reach even for seemingly simple scenarios. It is known that the non-signaling
set is strictly larger than the classical set of correlations
$\mathcal{C}(E)\subset\mathcal{N}(E)$, at least for $|A|=3$ and $|B|=|C|=2$.

Furthermore, because there is communication between the parts, Evans’s
scenario allows us to go beyond passive observations of the experiment and ask
what would happen if the system is intervened upon [35]. We use do-
conditionals $p(a|do(b))$ (and $p(c|do(b))$) to denote the probability of
Alice’s (Charlie’s) outcome $a$ ($c$) when variable $B$ is set by force to be
$b$. For classical correlations, this can be formalized with the constraint

$p(a|do(b))=\sum_{\lambda}p(\lambda)p(a|\lambda,b)$ (12)

and similarly for $p(c|do(b))$. Analogously, we can define what the do-
conditionals would look like in terms of a quantum strategy

$p(a|do(b))=\tr\left[\left(A^{a}_{b}\otimes\mathbb{I}\right)\rho_{\Lambda}\right]$
(13)

and the same can be done for $p(c|do(b))$.

One might be interested in exploring interventions for post-quantum theories
in the Evans scenario. In order to do so, notice that the do-conditionals can
be expressed in terms of a marginal probability distribution of a particular
interruption of the original graph, which consists in introducing new
independent variables that each inherits one outcoming edge of the original
variable, see section IX of [47] for details. This procedure allows us to map
the restrictions due to no-signaling involving do-conditionals of the Evans
scenario to the no-signaling conditions on the bilocality scenario and
identify the do-conditionals $p(a|do(b))$ and $p(c|do(b))$ with the marginals
$p(a|x=b)$ and $p(c|z=b)$.

###  II.6 Tools for detecting non-classicality

The compatibility problem consists of answering the question: Are the
statistics over the observed variables compatible with the causal structure
under scrutiny? For causal structures with a single latent common cause, e.g.
the Bell scenario, this amounts to a linear feasibility problem. Indeed, it is
known that if we consider a decomposition of the form 2 we can, without loss
of generality, incorporate any local randomness present in the response
functions – i.e. $p(a|x,\lambda)$, $p(b|y,\lambda)$, $p(c|z,\lambda)$ and so
on – to the source $\lambda$ and define a deterministic model. In a
deterministic model, each value of $\lambda$ defines an assignment of one of
the possible outputs to each input. The model is a probabilistic mixture of
these deterministic assignments of outputs to inputs, with $\lambda$
specifying which particular assignment is chosen in each run of the
experiment. For each assignment, there is a corresponding _local deterministic
behavior_ $d_{\lambda}(a,b,c..|x,y,z,..)$ and $p(a,b,c...|x,y,z...)$ is
compatible with the standard Bell scenario _if, and only if_ it can be
expressed as a convex combination of deterministic local points. That is,

$\displaystyle\text{{p} is local }\iff\exists$ $\displaystyle q(\lambda)\text{
s.t. }q(\lambda)\geq 0,\quad\sum_{\lambda}q(\lambda)=1$ (14) $\displaystyle
p(a,...|x,...)=\sum_{\lambda}q(\lambda)d_{\lambda}(a,...|x,...).$

Indeed, determining whether there exist weights $q(\lambda)$ satisfying the
linear constraints in Eq. 14 is a typical instance of a _linear programming
problem_ (LP) [53].

For a generic causal structure, i.e. more than one source, we can use the
inflation technique. Intuitively, the method works by considering the
hypothetical situation where one has access to multiple copies of the sources
and measurement devices that compose the network and can rearrange them in
different configurations. Its core idea is to explore simple (linear)
conditions of this inflated network that ultimately translate to polynomial
inequalities on the observable probabilities. It has been proven in [54] the
existence of a hierarchy of inflations that asymptotically converges to the
classical set of correlations of any network and a test of compatibility of a
given level of this hierarchy can be done via Linear Programming (LP) or Semi-
Definite Programming (SDP) [53]. However, for each level $n$ of this hierarchy
the memory resources required are superexponential on $n$. Notably, this
hierarchy relies on information broadcasting, a primitive that is not allowed
in quantum information.

The inflation technique can constrain not only the set of classical
correlations but also the set of quantum correlations a network may give rise
to. _Quantum inflation_ [47] can be seen as a quantum analog of the classical
inflation technique which avoids the latter’s reliance on information
broadcasting. This is done by adapting the Navascues-Pironio-Acin (NPA)
hierarchy [55], originally developed to characterize quantum correlations in
Bell scenarios, in the _inflated_ scenario which can be tackled via
noncommutative polynomial optimization (NPO) theory [54]. The general goal of
NPO theory is to optimize the expectation value of a polynomial over operators
subject to a number of polynomial operators and statistical constraints. This
optimization is achieved by means of a hierarchy of SDP tests 222These tests
were implemented using [65].. The types of inflations we have used in our work
are shown in Fig. 2. For each inflation level, we then study the set varying
the NPA levels, and we will denote by $\mathcal{Q}_{n,m}(G)$ the corresponding
relaxation associated with $n$-th order inflation and level $m$ of the NPA
hierarchy.

At the core of our numerical approach is the use of quadratic programming (QP)
techniques, like the _branch and bound method_ , that allows us to extend our
optimization problems to include non-linear constraints with reasonable
efficiency [27]. These techniques work by iteratively breaking the variables
domain down into smaller problems that can each be approximated by a
corresponding convex program. This branching subroutine enables primal and
dual tasks to define upper and lower bounds that converge, up to computational
precision ($10^{-9}$), to the global optimal solution.

Using this we can assess classicality for the bilocal and the Evans networks
by directly imposing the independence of the sources
$p(\lambda,\gamma)=p(\lambda)p(\gamma)$. Notice that in both scenarios we can,
without loss of generality, make $\lambda$ determine the outcome $a$ for every
$x$ and, similarly, $\gamma$ determine $c$ for every $z$, while $B$ has a
stochastic response function $p(b|\lambda,\gamma)$. Therefore, we can take
$\lambda=\\{a_{0},...,a_{|x|-1}\\}$, $\gamma=\\{c_{0},...,c_{|z|-1}\\}$ and
$p(a,b,c|x,z)$ is bilocal _if and only if_ ,

$\displaystyle\exists q(\lambda,b,\gamma)\text{ s.t. }$ (15) $\displaystyle
q\geq 0,\quad\sum_{\lambda,b\gamma}q(\lambda,b,\gamma)=1,$ $\displaystyle
q(a_{x}=a,b,c_{z}=c)=p(a,b,c|x,z),$ $\displaystyle\text{ and }\quad
q(\lambda,\gamma)=q(\lambda)q(\gamma).$

which can be cast as a QP. For compatibility with the Evans scenario, it is
sufficient to look at the same conditions but only for $x=z=b$. We also use
the arguments given in [28] to extract tailored infeasibility certificates
from these quadratic programs.

###  II.7 Sampling non-signaling distributions

The starting point for the analysis of the volumes is generating the data sets
to be analyzed. These points must satisfy NSI restrictions, which will be
polynomial in the case of the bilocal scenario. For this, we sample separately
each coordinate of the behavior vector (or its equivalent representation by
correlators) followed by a rejection step to handle the constraints 333Other
ways of sampling were tested, e.g. the Monte Carlo method, which is able to
include more complicated constraints to sample from. However, the rejection
method was the best in terms of numerical performance; the reason for that
being the cardinality of the variables and the number of constraints..
Specifically, we sampled points uniformly within a hypercube and then selected
the subset of interest. We employed the results in [58] to determine how many
data points were necessary to sample the whole space of distributions in each
situation, that is, at least $(\sim 2.1)^{d}$ points uniformly generated in a
hypercube of dimension $d$ are required to estimate a volume close to the
hypercube itself. For example, for a hypercube of dimension eight (the
simplest triangle scenario in this work), one should consider data sets
containing more than four hundred points to start approximating well the
corresponding set of correlations. In view of such uniform distribution, the
fraction of points represented by a target subset can be associated with the
volume it occupies within the set containing it. More than one data set was
used in what follows, therefore we are going to mention them according to
their specific uses.

In all these cases, however, the idea behind them is the same: test membership
of the generated points in a set of interest via LP, SDP, or QP tests. Such
tests can be phrased in terms of feasibility or optimization problems. In what
follows, we also investigate how these points are distributed inside the set.
To this end, we consider a corresponding optimization in which the objective
function to be minimized is the trace distance between the sampled
distribution and some distribution inside the set (see [59]).

The trace distance between two probability distributions $\mathbf{p}(x)$ and
$\mathbf{q}(x)$, is given by

$D(\mathbf{p},\mathbf{q}):=\frac{1}{2}\sum_{x}|p(x)-q(x)|,$ (16)

and the _trace distance-based quantifier_ $Q_{\mathcal{X}}(p)$ of the distance
of a probability distribution $p(a,b,c|x,y,z)$ to a set $\mathcal{X}$ in a
tripartite scenario is computed through

$Q_{\mathcal{X}}(\mathbf{p})=\frac{1}{|x||y||z|}\min_{q(a,b,c|x,y,z)\in\mathcal{X}}D(p,q),$
(17)

and $|x|$, $|y|$, and $|z|$ stand for the cardinality of the set of
measurements for Alice, Bob, and Charlie, respectively. If $\mathcal{X}$ is
the local set, then we have a non-local distance, while if it is the bilocal
set, we have a non-bilocal distance, and similarly to any other set. Finally,
we compare the performance of the aforementioned techniques for different
cases.

##  III Results

###  III.1 Bilocality scenario

In the case of the bilocality scenario, we estimated the relative volume among
the different sets of correlation $\mathcal{C}(B)$, $\mathcal{Q}(B)$ and
$\mathcal{C}(L_{3})$ with respect to randomly sampled points inside
$\mathcal{N}(B)$ for the case where all variables are binary. Fig. 3
schematically illustrates these sets.

For doing so, we parametrize the conditional probability distribution
$p(a,b,c|x,z)$ in terms of the single-, two- and three-party correlators
$\langle A_{x}\rangle$, $\langle B\rangle$, $\langle C_{z}\rangle$, $\langle
A_{x}B\rangle$, $\langle BC_{z}\rangle$, $\langle A_{x}C_{z}\rangle$ =
$\langle A_{x}\rangle$$\langle C_{z}\rangle$ and $\langle A_{x}BC_{z}\rangle$
for all $x,z\in\\{0,1\\}$, where $\langle
A_{x}BC_{z}\rangle=\sum_{a,b,c}(-1)^{a+b+c}p(a,b,c|x,z)$, and similiarly for
the other correlators. This yields a total of 13 parameters in the interval
$[-1,1]$. We generated a set of uniformly distributed points in the
13-dimensional hypercube and, naturally, considered only the ones inside the
region of non-negative probability distributions, i.e. we excluded the points
that do not respect

$\displaystyle p(a,b,c|x,z)=$ (18)
$\displaystyle\dfrac{1}{8}\Big{(}1+(-1)^{a}\langle
A_{x}\rangle+(-1)^{b}\langle B\rangle+(-1)^{c}\langle C_{z}\rangle+$
$\displaystyle+(-1)^{a+b}\langle A_{x}B\rangle+(-1)^{b+c}\langle
BC_{z}\rangle+$ $\displaystyle+(-1)^{a+c}\langle A_{x}\rangle\langle
C_{z}\rangle+(-1)^{a+b+c}\langle A_{x}BC_{z}\rangle\Big{)}\geq 0,$

which gives us a set of uniformly distributed points in $\mathcal{N}(B)$. We
remark that this can be done without loss of generality for all non-signaling
behaviors, i.e. one can always choose some minimal representation or (for the
case of binary outcomes) correlators, i.e. expectation values, representation
to isolate the free parameters and eliminate all equality constraints and, if
necessary, use inequality constraints to filter valid probability
distributions from the data set that are uniformly distributed in the region
under scrutiny.

First, we analyze which points in our data set violate the standard tripartite
Bell locality by computing their trace distance to the local set of
distributions $\mathcal{C}(L_{3})$. Then, for the remaining points, which have
an explicit local decomposition, we analyze different levels of the classical
inflation hierarchy $\mathcal{C}_{n}(B)$ to compute their distances from the
bilocal set $\mathcal{C}(B)$, obtained by solving directly the QP problem,
and, from them, estimate the relative volumes of these sets. The results for
the volumes are presented in Table 1. Interestingly, while the set of non-
local distributions
$\overline{\mathcal{C}}(L_{3})=\mathcal{N}(B)\setminus\mathcal{C}(L_{3})$
amounts to approximately only $2.39\%$, the non-bilocal set
$\overline{\mathcal{C}}(B)=\mathcal{N}(B)\setminus\mathcal{C}(B)$ occupies
$32.6\%$ of the correlation space, a clear signature of the advantage of
considering the independence of the sources when testing the non-classicality
of the data.

$\mathcal{N}(B)$$\mathcal{C}(B)$$\mathcal{C}(L_{3})$$\mathcal{Q}(B)$$F$$G$$H$$I$$M$$N$$O$$P$$Q$$R$$S$$T$
Figure 3: Illustration of the different sets of correlations in the bilocal
scenario; proportions are not supposed to be faithful. Solid black lines
delimit the part of the no-signalling set compatible with the bilocal
conditions, while the blue region with a dashed border determines the local
set and solid blue lines delimit the bilocal subset within it. The hashed
yellow region encompasses quantum behaviors.

Regarding the use of inflation, the best witness of non-classicality is
represented by $\mathcal{C}_{3}$, i.e. $3$rd order inflation, showing that
$13.3\%$ of its volume is non-bilocal, still a significantly smaller value
than that obtained by QP. Besides being less accurate in detecting non-
classicality, the inflation technique is computationally more demanding
(around fifty times more as compared with the QP approach), which is the
reason why we analyzed two independently generated samples of different sizes:
$N=10^{4}$ for the inflation and $N=10^{6}$ in the QP case.

Set | Volume
---|---
$\overline{\mathcal{C}}(L_{3})$ (Non-local) | 0.0239
$\overline{\mathcal{C}}(B)$ (Non-bilocal) | 0.326
$\overline{\mathcal{C}}_{1}(B)$ (Inflation 1st order) | 0.0233
$\overline{\mathcal{C}}_{2}(B)$ (Inflation 2nd order) | 0.0999
$\overline{\mathcal{C}}_{3}(B)$ (Inflation 3rd order) | 0.133
Table 1: Volumes of different correlation sets in the bilocality scenario. In
the first two rows we have the results provided by QP on a data set with
$10^{6}$ samples, while in the last three, we have the volume associated with
the set of non-bilocal behaviors $\overline{\mathcal{C}}_{n}(B)$ computed for
different orders of inflation $n$, on a data set with only $10^{4}$ instances.
Order $n=3$ was the highest configuration analyzed. Which is still
considerably far from the value obtained by the QP approach.

Additionally, considering $\mathcal{Q}_{2,3}$, i.e. $2$nd order of inflation
together with the $3$rd level of the NPA hierarchy, we estimated the ratio of
the quantum volume with respect to the other sets. As can be seen in Table 2,
while the quantum volume (with the NPA level considered) within the non-local
correlations is $43\%$, it increases to about $86\%$ when considering the set
of non-bilocal correlations.

Set | Volume of $\mathcal{Q}_{2,3}(B)$
---|---
$\mathcal{N}(B)$ (Non-signaling) | 0.952
$\overline{\mathcal{C}}(L_{3})$ (Non-local) | 0.43
$\mathcal{C}(L_{3})$ Local | 0.942
$\overline{\mathcal{C}}(B)$ (Non-bilocal) | 0.856
$\mathcal{C}(B)$ (Bilocal) | 1.0
Table 2: Volumes of the behaviors that are compatible with a quantum
description, evaluated considering the relaxation $\mathcal{Q}_{2,3}(B)$, i.e.
the $2$nd order of quantum inflation and NPA level $3$. The results were
obtained with a data set containing $10^{4}$ behaviors.

To gather more information about the structure of different correlation sets,
beyond their relative volumes, we can also estimate how these points are
distributed relative to their trace distances inside $\mathcal{N}(B)$. From
Fig. 4 we can see how the points in $\mathcal{N}(B)$ have their distances from
the local $\mathcal{C}(L_{3})$ and bilocal $\mathcal{C}(B)$ set distributed
according to a Poissonian-like distribution. An interesting observation here
is the presence of a concentration of the distances for behaviors that are
non-classical, i.e. the distribution is peaked at a small distance from the
local and bilocal sets, which can be seen as an instance of the concentration
phenomena reported in [33].

(a) Non-local distances

(b) Non-bilocal set.

(c) Non-bilocal within non-local set.

(d) Non-bilocal within local set.

Figure 4: Distributions of distances in the bilocal scenario. In (4(a)) we
have non-local distances for around $2\times 10^{4}$ behaviors with a gap
precision between primal and dual LP tasks equal to 0%. In (4(b)) one can see
how non-bilocal distances are distributed considering points within the whole
non-bilocal set, while in (c) and (d) we split such set between non-local and
local, respectively, to offer a different perspective and highlight the
concentration observed in (c); results for around $4\times 10^{4}$ behaviors
using precision of 10% for the gap between primal and dual solutions in this
case.

###  III.2 Triangle scenario

Differently from the bilocality and Evans scenarios, for which there is a
natural set of NSI correlations to sample from, in the triangle scenario there
is no simple way to enforce the no-signaling and independence conditions [42].
For this reason, we analyze different volumes of sets of correlations relative
to points sampled inside the 8-dimensional simplex, that is, sampling over all
well-defined probability distributions $p(a,b,c)$ with $a,b,c=0,1$ being
dichotomic variables. Also, given that the triangle scenario imposes non-
quadratic constraints there is no direct manner to use quadratic optimizers,
for this reason we rely on the inflation technique [26, 47] as well as the
covariance approach [23, 24] and the Finner [29] and Shannon-type [60, 37]
inequalities.

First, we compare the set of classical and quantum correlations using the
inflation technique on our data points. Table 3(b) shows the results for
different orders of classical inflations $\mathcal{C}_{m}(T)$ with $m=1,2,3$,
and for different quantum inflations $\mathcal{Q}_{m,n}(T)$ with $m=1,2$ and
up to level $n=5$ of the NPA hierarchy. Notice how we are unable to detect
non-quantum behaviors without considering one extra copy of each source at
least. Moreover, we have found points that are incompatible with a classical
description but are quantum-compatible with $\mathcal{Q}_{2,4}$, i.e. up to
the $2nd$ order inflation and NPA level $4$. These points offer good
candidates to resolve a still open question: whether quantum non-classical
correlations can emerge in the triangle scenario with all variables dichotomic
[61].

Then, we consider the covariance decomposition test — which can only test the
network topology and as such are valid for all GPTs [50] — and the volume
delimited by the Finner and the Shannon-type entropic inequalities found in
[60, 37]; the first of them are proven to follow for all quantum distributions
and conjectured to be satisfied for all non-signaling distributions [29] while
the entropic ones, as the covariance test, tell us about the topology only.
Table 3(a) summarizes these results. Among them, we can see that the
covariance test managed to exclude the largest number of behaviors.

Method | Incompatible volume
---|---
Covariance | 0.0369
Finner | 0.0191
Entropic | 0.00095
(a) Comparison of other methods to detect incompatibility with the triangle
network.

Set | Volume
---|---
$\overline{\mathcal{C}}_{1}(T)$ | 0.0
$\overline{\mathcal{C}}_{2}(T)$ | 0.09592
$\overline{\mathcal{C}}_{3}(T)$ | 0.113*
$\overline{\mathcal{Q}}_{1,5}(T)$ | 0.0
$\overline{\mathcal{Q}}_{2,3}(T)$ | 0.1098
(b) Volumes of behaviors incompatible with a classical or quantum description.
*Here we use about 10% of the data set due to the computational cost.

Table 3: (3(a)) Volume of incompatible distributions calculated with other
known methods, specifically the Finner and the entropic inequalities [60] and
the covariance method [50]. (3(b)) Volumes of points incompatible with
classical $\mathcal{C}_{n}(T)$ and quantum inflations $\mathcal{Q}_{m,n}(T)$
for the triangle scenario using different configurations of $n,m$, on a data
set of around $10^{5}$ instances.

###  III.3 Evans scenario

Now we move our attention to the Evans scenario. We start by pointing out that
the relationship between the Evans and the bilocality scenario, which was
first noticed for classical and quantum correlations [28], indeed holds to all
GPTs. In fact, if one has access to GPT states and measurements one can
uniquely define a mapping between Evans and the bilocal scenario by making an
identification of the measurement effects of the variables $A$ and $C$ in each
scenario, analogously to what was argued in [28]. Therefore, the probability
distribution $p(a,b,c)$ in the Evans scenario is compatible with _any_ GPT _if
and only if_ there exists a bilocal distribution $p_{B}(a,b,c|x,z)$ compatible
with the same GPT which satisfies $p_{B}(a,b,c|x=z=b)=p(a,b,c)$. Using this
mapping, we can explore the set of non-signaling correlations in the Evans
scenario by virtue of the non-signaling conditions of the bilocality scenario.

We can formalize this with the following statement:

$\displaystyle p(a,b,c)\text{ is NSI-compatible}\iff$ (19)
$\displaystyle\exists p_{B}(a,b,c|x,z)\text{non-signaling distribution,}$
$\displaystyle\text{ s.t. }p_{B}(a,b,c|x=z=b)=p(a,b,c)$
$\displaystyle\quad\quad\quad\text{ and }p_{B}(a,c|x,z)=p_{B}(a|x)p_{B}(c|z).$

This tells us how to explore the set of NSI-compatible correlations in the
Evans scenario using a single quadratic program. Furthermore, this fact allows
our test to be conclusive, i.e. if one can prove that the conditions from
LABEL:eq:_NSI_Evans do not hold for some candidate distribution $p(a,b,c)$
then we can conclude the distribution is NSI-incompatible and, conversely, if
one can find a solution then there exists a no-signaling distribution
$p_{B}(a,b,c|x,z)$ that respects the NSI requirements, such that recovers
$p(a,b,c)$ by setting $x=z=b$, leaving no ambiguity up to a small ($\sim
10^{-9}$) computational precision. We remark that this is not the case for the
inflation tests, as they constitute only necessary conditions for
compatibility.

(a) Non-Evans with passive observations.

(b) Non-Evans under intervention.

Figure 5: The distribution of the trace-distances of non-classical behaviors
to the set of those compatible with a classical description when (5(a)) only
passive observations are made and (5(b)) interventional data is also taken
into account. While in (5(a)) all the non-classical instances have been used
in the plot, in (5(b)) only $10\%$ has been considered.

We can, thus, estimate the volume of the Evans non-signaling set
$\mathcal{N}(E)$ inside the simplex of probability distributions, see Table 4,
which includes also results using different numbers of outputs for each party.
Naively, one might believe that non-signaling is not relevant in the presence
of signals between parties of the network and in the absence of inputs, but
this is indeed not true as we can see that, approximately, the non-signaling
set represents $84.94\%$ of the volume relative to the simplex of all
probability distributions. Notice also how the volume increases as we increase
the number of outputs on Bob’s side, whilst a similar change on the other
parties causes the opposite effect.

$|A|$ | $|B|$ | $|C|$ | Volume
---|---|---|---
2 | 2 | 2 | 0.8494
2 | 3 | 2 | 0.9823
3 | 2 | 3 | 0.7475
Table 4: Volume of the non-signaling set $\mathcal{N}(E)$ within the simplex
of valid probability distributions in the Evans scenario for different numbers
of outputs for each party. The number of samples considered in each case was
of the order of $10^{5}$.

Naturally, we also investigated the volume of the classically compatible
distribution in the Evans scenario $\mathcal{C}(E)$ and, remarkably, found a
very small gap ($\approx 0.12\%$) of NSI-compatible non-classical
distributions in the minimal case where all variables are bits. Fig. 5(a)
shows the distribution of the distances to the classical set. All non-
classical distributions that we have found cannot be ruled out by quantum
inflation up to $2nd$ order inflation and NPA level $3$, therefore we cannot
tell that these points are truly post-quantum with our current techniques.
Even the classical version of the inflation technique is unable to exclude any
of the non-classical points we found. This opens the interesting possibility
(with actual candidate probability distributions) that a classical-quantum gap
exists in the Evans scenario, a question that remains open [28].

In particular, starting from these points, we can propose the candidate
distribution

$\displaystyle P_{NS}(1,0,0)=2/81,\quad P_{NS}(0,0,1)=1/55$ (20)
$\displaystyle P_{NS}(0,1,0)=1/11,\quad P_{NS}(1,0,1)=1/5$ $\displaystyle
P_{NS}(1,1,0)=P_{NS}(0,1,1)=1/81,$ $\displaystyle P_{NS}(1,1,1)=1/2\sqrt{2},$
$\displaystyle P_{NS}(0,0,0)=1-\sum_{a,b,c\neq 0,0,0}P_{NS}(a,b,c)$

which satisfies the NSI test LABEL:eq:_NSI_Evans and can be certified to be
non-classical with QP with a corresponding witness given by

$W:=\sum_{a,b,c}(p(a,b,c)-P_{NS}(a,b,c))^{2}\geq\frac{1}{36.853}.$ (21)

Moreover, we analyzed what happens if one considers additional interventional
data $p(a,c|do(b))$. For the particular case of the Evans causal structure, it
is sufficient to provide only $p(a|do(b))$ and $p(c|do(b))$, since
$p(a,c|do(b))=p(a|do(b))p(c|do(b))$. To do so, we use the interruption
technique to map valid non-signaling probability distributions in the bilocal
scenario to valid hybrid data tables in the Evans scenario. This is done by
considering only $p_{B}(a,b,c|x=z=b)$ and the marginals
$p_{B}(a|x)$,$p_{B}(c|z)$ and identifying them with $p(a,b,c)$, $p(a|do(b=x))$
and $p(c|do(b=z))$ respectively.

Similar to the observable case, we can ask what portion of these valid non-
signaling hybrid data tables are classically achievable. Remarkably, we found
that interventions increase the power to detect non-classicality by two orders
of magnitude. Indeed, the non-classical volume, in the case where all
variables are binary, increases to $14.6\%$ relative to the number of non-
signaling distributions sampled, as opposed to $0.12\%$ using only passive
observations. We also look at how these points are distributed relative to
their trace distances inside the NSI set, see Fig. 5(b).

##  IV Discussion

From a modern viewpoint, Bell’s theorem can be seen as an instance of a causal
inference problem, more precisely causal compatibility where we impose a given
causal structure on a quantum experiment and ask whether a classical causal
model can explain the observed correlations. This simple yet powerful
realization led to a number of generalizations of Bell’s theorem for causal
networks of growing size and complexity, showing, for instance, the emergence
of non-classical behavior even without the need for measurement choices [12,
13, 18, 16] or by allowing time-like rather than space-like correlation
scenarios [34]. Of particular relevance, are causal networks composed of
independent sources of correlations, scenarios that unveiled new features such
as the possibility of self-testing all entangled quantum states [62] and
quantum theory itself [14], activation of non-classical behaviour [25, 63],
refined notions of multipartite non-classicality [64, 17] and novel tests of
the role of complex numbers in quantum mechanics [15].

A basic problem within this context is that of characterizing the sets of
correlations allowed by each causal structure according to classical, quantum,
and non-signaling theories. A problem that, differently from the standard Bell
scenario, relies on polynomial causal constraints that impose a non-convex
structure to the set of allowed probability distributions compatible with a
given causal network. Recently a number of different tools have been proposed
to approach this problem but even simple causal networks still have a very
fragmented and partial characterization. Moreover, it is unclear how effective
those different methods are in witnessing non-classicality. To obtain a more
coherent and global picture of both the sets of correlations as well as the
tools designed to address them, we analyzed the volumes of such different sets
of correlations.

Considering the simplest bilocality scenario and using QP we obtained that
only $2.4\%$ of the NSI correlations are non-local while $32.6\%$ are non-
bilocal, thus showing that the ability to witness non-classicality is
significantly enhanced if we take into account the independence of the
sources. Furthermore, the distribution of distances of the non-classical
points to the local and bilocal sets show an exponential decay, meaning that
most of them are concentrated close to the classical sets. In comparison, the
best results we obtained with the inflation technique – corresponding to a
$3$rd order inflation level – provide a lower bound of $13.3\%$ for the volume
of the non-bilocal set, meaning that more than half of the non-bilocal points
are not detected by this method.

In the Evans scenario, we have shown that NSI correlations occupy a
significant volume of the simplex set (the set of all probability
distributions), in some cases surpassing $98\%$. Surprisingly, only $0.12\%$
of those NSI correlations are actually non-classical. In comparison, the
inflation technique again shows relatively poor performance, being unable to
detect any of these non-classical points (up to the level of the hierarchy we
could handle numerically). Remarkably, however, the volume of non-classical
correlations is increased to $14.6\%$ when we consider also the effect of
interventions in the Evans scenario, a clear signature that interventional
data can enhance significantly our ability to witness non-classicality.

For the triangle network, since it involves third-order polynomial
constraints, we cannot directly use QP and, for this reason, we have employed
and compared four specific tools: the inflation technique, the covariance
test, the Finner inequality, and Shannon-type entropic inequalities. Once
more, the $3$rd inflation level was the best approximation we achieved with
the inflation technique, lower bounding the volume of non-classical
correlations to $11.3^{*}\%$ of the total set of tripartite probability
distributions. Interestingly, the lower bound on the volume of post-quantum
correlations is $10.98\%$, pointing out that only a small fraction of the non-
classical correlations in the triangle scenario might have a quantum
description. In comparison, the Finner inequality detects a volume of $1.91\%$
of non-classical correlations while the covariance approach and the entropic
inequalities lead to $3.69\%$ and $0.095\%$, respectively.

In summary, our approach unveils a few interesting features of the non-convex
sets of correlations of causal networks of relevance in the literature. On the
positive side, it shows that taking into account the independence of the
sources as well as interventional data can greatly improve the volume of non-
classical correlations, enhancing our ability to witness them. In turn, the
inflation technique, the most general tool at the disposal, cannot detect a
significant portion of non-classical correlations, at least the approximation
level that was computationally accessible.

This shows that new tools might be needed to advance our understanding of such
networks and the non-classical features they entail. One interesting
possibility is to adapt the inflation method to generate quadratic constraints
only, which could then be efficiently handled by a quadratic optimizer.
Another relevant direction is to use these results as the starting point to
solve open questions. For instance, we have detected non-classical points in
the simplest Evans and triangle scenarios that nonetheless pass the test of
quantum inflation. Those are good candidates for possible quantum violations
of the causal constraints imposed by such networks and we hope our work
motivates further research in those directions.

## Acknowledgements

The authors thank the International Institute of Physics for hosting the
workshop ´´Quantum Causality Retreat”, during which this work has started to
be discussed. This work was supported by the Serrapilheira Institute (Grant
No. Serra-1708-15763), the Simons Foundation (Grant Number 1023171, RC), the
Brazilian National Council for Scientific and Technological Development (CNPq)
(INCT-IQ and Grant No 307295/2020-6), the São Paulo Research Foundation FAPESP
(Grant Nos. 2018/07258-7, 2022/03792-4) and the Brazilian agencies MCTIC,
CAPES and MEC.

##  V Code availability

We provide the codes to reproduce our results at the link
https://github.com/Giuhcs/relative_volumes_tripartite.

## References

  * Brunner  _et al._ [2014] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Reviews of modern physics 86, 419 (2014).
  * Pironio  _et al._ [2016] S. Pironio, V. Scarani, and T. Vidick, New J. Phys 18, 100202 (2016).
  * Collins and Gisin [2004] D. Collins and N. Gisin, Journal of Physics A: Mathematical and General 37, 1775 (2004).
  * Collins  _et al._ [2002] D. Collins, N. Gisin, N. Linden, S. Massar, and S. Popescu, Physical review letters 88, 040404 (2002).
  * Werner and Wolf [2001] R. F. Werner and M. M. Wolf, Physical Review A 64, 032112 (2001).
  * Pironio [2003] S. Pironio, Physical Review A 68, 062102 (2003).
  * Brask and Chaves [2017] J. B. Brask and R. Chaves, Journal of Physics A: Mathematical and Theoretical 50, 094001 (2017).
  * Hall [2010] M. J. Hall, Physical review letters 105, 250404 (2010).
  * Chaves  _et al._ [2015a] R. Chaves, R. Kueng, J. B. Brask, and D. Gross, Physical review letters 114, 140403 (2015a).
  * Pearl [2009] J. Pearl,  _Causality_ (Cambridge university press, 2009).
  * Branciard  _et al._ [2010] C. Branciard, N. Gisin, and S. Pironio, Physical review letters 104, 170401 (2010).
  * Fritz [2012] T. Fritz, New Journal of Physics 14, 103001 (2012).
  * Renou  _et al._ [2019a] M.-O. Renou, E. Bäumer, S. Boreiri, N. Brunner, N. Gisin, and S. Beigi, Physical review letters 123, 140401 (2019a).
  * Weilenmann and Colbeck [2020] M. Weilenmann and R. Colbeck, Physical Review Letters 125, 060406 (2020).
  * Renou  _et al._ [2021] M.-O. Renou, D. Trillo, M. Weilenmann, T. P. Le, A. Tavakoli, N. Gisin, A. Acín, and M. Navascués, Nature 600, 625 (2021).
  * Chaves  _et al._ [2021] R. Chaves, G. Moreno, E. Polino, D. Poderini, I. Agresti, A. Suprano, M. R. Barros, G. Carvacho, E. Wolfe, A. Canabarro, _et al._ , PRX Quantum 2, 040323 (2021).
  * Suprano  _et al._ [2022] A. Suprano, D. Poderini, E. Polino, I. Agresti, G. Carvacho, A. Canabarro, E. Wolfe, R. Chaves, and F. Sciarrino, PRX Quantum 3, 030342 (2022).
  * Polino  _et al._ [2023] E. Polino, D. Poderini, G. Rodari, I. Agresti, A. Suprano, G. Carvacho, E. Wolfe, A. Canabarro, G. Moreno, G. Milani, _et al._ , Nature Communications 14, 909 (2023).
  * Pitowsky [1991] I. Pitowsky, Mathematical Programming 50, 395 (1991).
  * Garcia  _et al._ [2005] L. D. Garcia, M. Stillman, and B. Sturmfels, Journal of Symbolic Computation 39, 331 (2005).
  * Chaves  _et al._ [2014] R. Chaves, L. Luft, T. Maciel, D. Gross, D. Janzing, and B. Schölkopf, in  _Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence_ (AUAI Press, 2014).
  * Chaves [2016] R. Chaves, Physical review letters 116, 010402 (2016).
  * Kela  _et al._ [2019] A. Kela, K. Von Prillwitz, J. Åberg, R. Chaves, and D. Gross, IEEE Transactions on Information Theory 66, 339 (2019).
  * Åberg  _et al._ [2020] J. Åberg, R. Nery, C. Duarte, and R. Chaves, Physical Review Letters 125, 110505 (2020).
  * Pozas-Kerstjens  _et al._ [2019] A. Pozas-Kerstjens, R. Rabelo, Ł. Rudnicki, R. Chaves, D. Cavalcanti, M. Navascués, and A. Acín, Physical review letters 123, 140503 (2019).
  * Wolfe  _et al._ [2019] E. Wolfe, R. W. Spekkens, and T. Fritz, Journal of Causal Inference 7 (2019).
  * Gurobi Optimization, LLC [2022] Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual (2022).
  * Lauand  _et al._ [2023] P. Lauand, D. Poderini, R. Nery, G. Moreno, L. Pollyceno, R. Rabelo, and R. Chaves, PRX Quantum 4, 020311 (2023).
  * Renou  _et al._ [2019b] M.-O. Renou, Y. Wang, S. Boreiri, S. Beigi, N. Gisin, and N. Brunner, Physical review letters 123, 070403 (2019b).
  * Cabello [2005] A. Cabello, Physical Review A 72, 012113 (2005).
  * Wolfe and Yelin [2012] E. Wolfe and S. F. Yelin, Physical Review A 86, 012123 (2012).
  * Navascués and Wolfe [2020] M. Navascués and E. Wolfe, Journal of Causal Inference 8, 70 (2020).
  * Duarte  _et al._ [2018] C. Duarte, S. Brito, B. Amaral, and R. Chaves, Physical Review A 98, 062114 (2018).
  * Chaves  _et al._ [2018] R. Chaves, G. Carvacho, I. Agresti, V. Di Giulio, L. Aolita, S. Giacomini, and F. Sciarrino, Nature Physics 14, 291 (2018).
  * Gachechiladze  _et al._ [2020] M. Gachechiladze, N. Miklin, and R. Chaves, Physical Review Letters 125, 230401 (2020).
  * Spirtes  _et al._ [2000] P. Spirtes, C. N. Glymour, and R. Scheines,  _Causation, prediction, and search_ (MIT press, 2000).
  * Chaves  _et al._ [2015b] R. Chaves, C. Majenz, and D. Gross, Nature communications 6, 5766 (2015b).
  * Pienaar and Brukner [2015] J. Pienaar and Č. Brukner, New Journal of Physics 17, 073020 (2015).
  * Costa and Shrapnel [2016] F. Costa and S. Shrapnel, New Journal of Physics 18, 063032 (2016).
  * Barrett  _et al._ [2019] J. Barrett, R. Lorenz, and O. Oreshkov, arXiv preprint arXiv:1906.10726 (2019).
  * Henson  _et al._ [2014] J. Henson, R. Lal, and M. F. Pusey, New Journal of Physics 16, 113043 (2014).
  * Gisin  _et al._ [2020] N. Gisin, J.-D. Bancal, Y. Cai, P. Remy, A. Tavakoli, E. Zambrini Cruzeiro, S. Popescu, and N. Brunner, Nature communications 11, 2378 (2020).
  * Chiribella  _et al._ [2010] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Phys. Rev. A 81, 062348 (2010).
  * Pan  _et al._ [1998] J.-W. Pan, D. Bouwmeester, H. Weinfurter, and A. Zeilinger, Physical review letters 80, 3891 (1998).
  * Popescu and Rohrlich [1994] S. Popescu and D. Rohrlich, Foundations of Physics 24, 379 (1994).
  * Evans [2016] R. J. Evans, Scandinavian Journal of Statistics 43, 625 (2016).
  * Wolfe  _et al._ [2021] E. Wolfe, A. Pozas-Kerstjens, M. Grinberg, D. Rosset, A. Acín, and M. Navascués, Physical Review X 11, 021043 (2021).
  * Coiteux-Roy  _et al._ [2021] X. Coiteux-Roy, E. Wolfe, and M.-O. Renou, Physical review letters 127, 200401 (2021).
  * Note [1] Note that when evaluating $p$, one should be attentive to which Hilbert space supports each state and measurements.
  * Beigi and Renou [2021] S. Beigi and M.-O. Renou, IEEE Transactions on Information Theory 68, 384 (2021).
  * Pozas-Kerstjens  _et al._ [2023a] A. Pozas-Kerstjens, A. Girardin, T. Kriváchy, A. Tavakoli, and N. Gisin, Post-quantum nonlocality in the minimal triangle scenario (2023a), arXiv:2305.03745 [quant-ph] .
  * Tavakoli  _et al._ [2022] A. Tavakoli, A. Pozas-Kerstjens, M.-X. Luo, and M.-O. Renou, Reports on Progress in Physics 85, 056001 (2022).
  * Boyd and Vandenberghe [2006] S. Boyd and L. Vandenberghe,  _Convex Optimization_ (Cambridge University Press, 2006).
  * Navascués  _et al._ [2008] M. Navascués, S. Pironio, and A. Acín, New Journal of Physics 10, 073013 (2008).
  * Navascués  _et al._ [2007] M. Navascués, S. Pironio, and A. Acín, Phys. Rev. Lett. 98, 010401 (2007).
  * Note [2] These tests were implemented using [65].
  * Note [3] Other ways of sampling were tested, e.g. the Monte Carlo method, which is able to include more complicated constraints to sample from. However, the rejection method was the best in terms of numerical performance; the reason for that being the cardinality of the variables and the number of constraints.
  * Dyer  _et al._ [1992] M. E. Dyer, Z. Füredi, and C. McDiarmid, Random Structures & Algorithms 3, 91 (1992).
  * Brito  _et al._ [2018] S. G. A. Brito, B. Amaral, and R. Chaves, Phys. Rev. A 97, 022111 (2018).
  * Fritz and Chaves [2012] T. Fritz and R. Chaves, IEEE transactions on information theory 59, 803 (2012).
  * Pozas-Kerstjens  _et al._ [2023b] A. Pozas-Kerstjens, A. Girardin, T. Kriváchy, A. Tavakoli, and N. Gisin, arXiv preprint arXiv:2305.03745 (2023b).
  * Šupić  _et al._ [2023] I. Šupić, J. Bowles, M.-O. Renou, A. Acín, and M. J. Hoban, Nature Physics , 1 (2023).
  * Poderini  _et al._ [2020] D. Poderini, S. Brito, R. Nery, F. Sciarrino, and R. Chaves, Physical Review Research 2, 043106 (2020).
  * Pozas-Kerstjens  _et al._ [2022] A. Pozas-Kerstjens, N. Gisin, and A. Tavakoli, Physical review letters 128, 010403 (2022).
  * Boghiu  _et al._ [2023] E.-C. Boghiu, E. Wolfe, and A. Pozas-Kerstjens, Quantum 7, 996 (2023), arXiv:2211.04483 .