# Observing quantum coherence from photons scattered in free-space

Shihan Sajeed  Institute for Quantum Computing, University of Waterloo,
Waterloo, ON, N2L 3G1 Canada  Department of Physics and Astronomy, University
of Waterloo, Waterloo, ON, N2L 3G1 Canada<EMAIL_ADDRESS>Thomas
Jennewein  Institute for Quantum Computing, University of Waterloo, Waterloo,
ON, N2L 3G1 Canada  Department of Physics and Astronomy, University of
Waterloo, Waterloo, ON, N2L 3G1 Canada

###### Abstract

Quantum channels in free-space, an essential prerequisite for fundamental
tests of quantum mechanics and quantum technologies in open space, have so far
been based on direct line-of-sight because the predominant approaches for
photon-encoding, including polarization and spatial modes, are not compatible
with randomly scattered photons. Here we demonstrate a novel approach to
transfer and recover quantum coherence from scattered, non-line-of-sight
photons analyzed in a multimode and imaging interferometer for time-bins,
combined with photon detection based on a 8x8 single-photon-detector-array.
The observed time-bin visibility for scattered photons remained at a high
$95\%$ over a wide scattering angle range of $-45\mathrm{\SIUnitSymbolDegree}$
to $+45\mathrm{\SIUnitSymbolDegree}$, while the individual pixels in the
detector array resolve or track an image in its field of view of ca. 0.5
degrees. Using our method we demonstrate the viability of two novel
applications. Firstly, using scattered photons as an indirect channel for
quantum communication thereby enabling non-line-of-sight quantum communication
with background suppression, and secondly, using the combined arrival time and
quantum coherence to enhance the contrast of low-light imaging and laser
ranging under high background light. We believe our method will instigate new
lines for research and development on applying photon coherence from scattered
signals to quantum sensing, imaging, and communication in free-space
environments.

## Introduction

Quantum coherence is a key ingredient in many fundamental tests and
applications of quantum mechanics including quantum communication [1],
characterization of single-photon sources [2], generation of non-classical
states [3], quantum metrology [4], quantum teleportation [5], quantum
fingerprinting [6], quantum cloning [7], demonstrating quantum optical
phenomena [8], and quantum computing [9] etc. The ability to transfer quantum
coherence via scattering surfaces and its successful recovery from scattered
photons enhances several applications of quantum technologies. For instance,
quantum communication capable of operating over a scattering channel could
accommodate free space communication with non-line-of-sight between multiple
users such as indoors around corners, or with short range links with moving
systems. Furthermore, the photon coherence recovered from scattered light
could be utilized to improve noise performance in low-light and 3D imaging,
around-the-corner imaging [10], velocity measurement [11], light detection and
ranging (LIDAR), surface characterization, or biomedical sample
identification.

Currently, the predominant photon encoding used on free-space quantum channels
is polarization, because it is not impacted by turbulent atmosphere for clear
line-of-sight transmission[12]. When photons are scattered, however, their
polarization states are inherently disturbed and the quantum encoding is
degraded. A previous study [13] showed that the observed polarization
visibility depends on the scattering-surface material, and even the best
material (cinematic silver screen) showed a strong dependence on the photon
scattering angles with only a total angle of less than
$45\mathrm{\SIUnitSymbolDegree}$ was suitable for quantum communications.
Another approach to encode free-space channels is the use of higher-order
spatial modes, recently utilized for intracity quantum key distribution [14],
yet these photon states are directly impacted by wavefront distortion and are
expected to completely vanish upon random scattering from a surface [15, 16].

Here we utilize quantum coherence encoded in time-bins [17, 18, 1] which –
although widely used for single-mode optical fibers [19, 20, 21, 18, 22] – has
rarely been demonstrated for free-space channels until recently [23, 24, 25].
This encoding is robust upon scattering. The multimode states of light have
been utilized using field-widened interferometers, or imaging interferometers,
thereby solving the wavefront distortions caused by turbulent media. Such
interferometers have the additional benefit of preserving an image. (An
alternate approach could be to convert the multimode optical beam back into a
single-mode at the receiver by means of adaptive optics, however at the cost
of additional losses [26]). We thus implemented an imaging time-bin
interferometer equipped with a single-photon-detector-array (SPDA) sensor,
with 8x8 pixels covering a field of about $0.5\mathrm{\SIUnitSymbolDegree}$.
The photon detector achieves high temporal precision of $\approx
120\leavevmode\nobreak\ \mathrm{p}\mathrm{s}$, combined with the ability to
spatially resolve the field-of-view with excellent time-bin visibility across
the whole sensor area. We demonstrate that our system allows imaging a target
that was illuminated with photons prepared with specific phase-signatures,
that are recovered from the scattered photons with excellent phase coherence
by the illuminated pixels. We discuss the viability of our method in the
context of two relevant applications.

## Experiment

The experimental setup is shown in Fig. 1 (see Methods for additional
details). Each pulse from the laser passes through the Converter – an
unbalanced Michelson interferometer (UMI) – that converts it into two coherent
pulses separated by a time delay according to the path difference
$\Delta_{C}$. These signals are sent towards the target sample covered with a
diffusive material (regular white paper) acting as the _scattering surface_ ,
which can be rotated to vary the angle of incidence. Some of the photons
scattered from the surface are captured and guided through the Analyzer, a
second UMI with path difference $\Delta_{A}$. Finally, the photons emerging
from the Analyzer are focused into a single-photon-detector-array (SPDA)
containing $64$ single-photon avalanche photo-diodes – hereafter referred to
as pixels – arranged in a $8\times 8$ row-column configuration, which are
free-running and individually time-tagged. Each detected photon could have
traversed one of the four possible paths: short-short (SS), short-long (SL),
long-short (LS) and long-long (LL) with first (second) letter denoting the
path taken inside Converter (Analyzer). The path-differences of the two UMI
are tightly matched, i.e., $\Delta_{C}\approx\Delta_{A}$, and interference can
be observed, as shown in Fig. 2. Piezoelectric actuators are placed at the
short arm of each interferometer to vary their respective phase. To compensate
for variable angle of incidence and mode-distortion, a
$118\mathrm{m}\mathrm{m}$ long glass cube with refractive index $1.4525$ is
placed in the long arm of both interferometers.

Figure 1: The experimental setup. Optical pulses from a laser are sent through
a phase Converter, which creates the initial time-bin states, while the multi-
mode Analyzer measures the signals scattered off the target (regular white
paper). A single-photon-detector-array is used as the detection device, with 8
x 8 individual pixels which are time-tagged separately. During the initial
alignment, the incident angle = reflected angle = $25\leavevmode\nobreak\
\mathrm{\SIUnitSymbolDegree}$. Figure 2: Observed interference. Top left:
Histograms of the arrival times of photons at pixel number $(4,4)$ (row 4,
column 4). The three separate peaks correspond to photons coming via SS
(right), SL or LS (middle), and LL (left) paths (see text for more detail).
Five different phase-instances are shown. The visibility at this pixel –
calculated by curve-fitting – was $V_{(4,4)}\approx 0.95$. Top right: Middle-
peak intensity at the illuminated pixels at the corresponding phase-instances.
Bottom: visibilities of the illuminated pixels calculated after fitting the
curves. The visibilities range from $0.9-0.95$. Both the color and the size of
the _sqaure_ marker in each pixel area are indicators of the visibility. Pixel
number $(1,1)$ was used as a trigger. The temporal precision was $\approx
120\leavevmode\nobreak\ \mathrm{p}\mathrm{s}$. Figure 3: Visibility with
scattered light and coherence among the pixels. a. The incident angle $\theta$
was varied by rotating the scattering surface about point $P$ by an angle
$\phi$ from $-45\mathrm{\SIUnitSymbolDegree}$ to
$+45\mathrm{\SIUnitSymbolDegree}$ while keeping the position of laser and
camera constant. b. Variation of visibility and intensity with rotation angle.
Here, rotation angle $\phi=0$ corresponds to incidence angle of
$\theta=25\mathrm{\SIUnitSymbolDegree}$ as shown in Fig. 1. For rotation
angles higher than $\pm 45\mathrm{\SIUnitSymbolDegree}$, sufficient amount of
photon could not be collected by the camera. The average intensity for each
angle is shown on the right axis. The collection time for each data point is
$20\sec$. c. Variation of counts versus phases applied at the Converter for
the illuminated pixels. Pixel number $(1,1)$ was used as a trigger.

A sinusoidal phase difference was introduced between the two interfering (SL
and LS) pulses by applying a $0.1\leavevmode\nobreak\ \mathrm{Hz}$ $10V$ peak-
to-peak ramp voltage at the Analyzer piezoelectric actuator (i.e., the length
of the $LS$ path was varied with respect to $SL$). The resultant outcomes are
shown in Fig. 2. The top left columns shows histograms of detection times –
with respect to trigger signal – at one of the central pixels $(4,4)$ (row 4,
column 4) for five different phase-instances. The three peaks correspond to
photons coming via SS (right), SL or LS (middle) and the LL (left) paths. The
temporal precision was $\approx 120\leavevmode\nobreak\ \mathrm{p}\mathrm{s}$.
The measured visibility – calculated by fitting the curve – was
$V_{(4,4)}\approx 0.95$. The right column shows the corresponding middle-peak
intensity for other illuminated pixels. In this case, only the events detected
during the $0.6\leavevmode\nobreak\ \mathrm{n}\mathrm{s}$ window – centred
around the middle-peak – was post-selected. The data collection time was
$1\leavevmode\nobreak\ \sec$ for the left and $0.1\leavevmode\nobreak\ \sec$
for the right columns. The visibilities of the illuminated pixels – calculated
after fitting the curves – are shown at the bottom which range from
$0.9-0.95$.

### Robust and stable phase coherence under scattering angle variations

During the initial alignment, specular reflection was used by setting the
incident angle = reflected angle = $25\mathrm{\SIUnitSymbolDegree}$. We refer
to the incident angle as $\theta$. Then, using a rotational mount, the
scattering surface was rotated about $P$ to vary $\theta$ while keeping the
position of the camera fixed (see Fig. 3a). For different rotation angle
$\phi$, the corresponding average intensity and visibilities are shown in Fig.
3b for pixel number $(4,4)$. For $\theta=25\mathrm{\SIUnitSymbolDegree}$
($\phi=0\mathrm{\SIUnitSymbolDegree}$), the majority of photons collected by
the camera was due to specular reflection. As $\theta(\phi)$ was varied, the
intensity followed the typical scattering pattern consisting of specular and
diffusive reflection [27]. At larger rotation angles $\phi$, the collected
photons were mainly due to scattering from the diffused surface. For
$\phi>\absolutevalue{45\mathrm{\SIUnitSymbolDegree}}$, the amount of photons
collected were too low. However, within the range
$\phi\in\\{-45\mathrm{\SIUnitSymbolDegree},+45\mathrm{\SIUnitSymbolDegree}\\}$,
although the number of detected photons varied, the visibility remained fairly
constant at around $95\%$ with less than $10\%$ variation. The same behavour
was observed for other illuminated pixels.

### Recovery of coherence while imaging

As we will demonstrate, this approach offers the unique ability for individual
pixels in this imaging analyzer to fully detect the coherence, while at the
same time resolving spatial modes of the scattered photons. To ensure that the
camera received mostly scattered photons, the scattering surface was rotated
to set $\phi=20\leavevmode\nobreak\ \mathrm{\SIUnitSymbolDegree}$ (see Fig.
3a) at which the value of visibility was still close to $0.95$. Similar to
Fig. 2, only the pixels in the center of the sensor were illuminated. By
applying a periodic voltage to the piezoelectric actuator in the Converter
interferometer, a sinusoidal phase variation was induced among the outgoing
time-bin photons. For each phase $\theta_{c}$, the corresponding counts at the
illuminated pixels were recorded. No voltage was applied at the Analyzer
piezoelectric actuator. The fitted count-versus-phase curves for the
illuminated pixels are shown in Fig. 3c. The result verified that although
each pixel saw a different set of spatial modes of the incoming light, the
phase $\theta_{c}$ was preserved by the modes even after going through
diffused scattering, and was successfully recovered from the scattered photons
by each individual pixel independently. The test was repeated by illuminating
all pixels of the SPDA for different scattering angles $\phi$, yielding
similar results.

### Quantum communication with scattered light

We now show the applicability of our setup in implementing quantum
communication (QC) with scattered photons in a non-line-of-sight (nLOS)
scenario. Here, nLOS refers to the fact that no direct path exists between
sender and receiver; neither do they have access to any specular reflector,
i.e. mirror surface, at any intermediate point. More specifically, we consider
the implementation of the phase-encoded Bennett-Brassard 1984 (BB84) QKD
protocol [28]. The experimental setup was similar to Fig. 1 where the laser
and Converter can be considered to be at sender’s (Alice’s) lab while the
Analyzer and the camera at receiver’s (Bob’s) lab. Photons from Alice’s laser
were scattered off the diffused surface (white paper) before being measured by
Bob. For our experiment, we rotated the scattering surface by
$\phi=20\leavevmode\nobreak\ \mathrm{\SIUnitSymbolDegree}$ to ensure that
photons detected by Bob were mostly due to scattering from the diffusive
surface. The four phase-encoded BB84 states sent by Alice are:

$\ket{\psi_{A}}=\ket{e}+e^{i\theta_{A}}\ket{l}.$ (1)

Here, $\ket{e}\leavevmode\nobreak\ (\ket{l})$ denotes the state of the photon
that took the early (late) path at the Converter, and
$\theta_{A}\in\\{0,\pi/2,\pi,3\pi/2\\}$ is the phase difference applied at the
Converter. These states can be generated by applying specific voltages to the
piezoelectric actuator placed at the long arm of the Converter. Bob’s
measurement basis can be chosen by applying phase difference
$\theta_{B}\in\\{0,\pi\\}$ at the Analyzer piezo actuator. Figure 3c shows the
variation of counts versus $\theta_{A}$ at the illuminated pixels for Bob’s
measurement basis $\theta_{B}=0$. Similar variation was observed when Bob’s
basis was changed to $\theta_{B}=\pi$ (not shown). The visibilities were in
the range of $0.9-0.95$ for all the illuminated pixels. The result verifies
that even though there was no direct line of sight between Alice and Bob, and
the photons were being scattered by a diffused surface on their way from
sender to receiver, they could still be used for implementing the BB84
protocol with high visibility. Our proof-of-principle implementation makes it
an ideal candidate for real-world quantum communication applications over
scattering and nLOS channels.

We emphasize that the SPDA sensor enhances the robustness of the QKD receiver,
in addition to allowing nLOS operation. Firstly, the imaging information for
each pixel can be used for tracking a transmitter beam that feeds into an
active beam steering mechanism, or simply used to passively suppress
background counts in processing. Secondly, the implementation of multiple
photon detector pixels appears to be more robust against certain powerful
quantum attacks. For example, the class of detector control attacks [29, 30]
could be prevented by adopting the method presented in [31]. The efficiency
mismatch type attacks [32] – where an eavesdropper attacks by modifying the
spatial modes of the incoming light – could be easily detected as changing the
spatial mode will change the spatial distribution of detection events.

### Low-light imaging in high photon background

Figure 4: Enhancing the contrast of an image. a. The top and bottom row show
the illuminated object (size $4\times 3.6\mathrm{m}\mathrm{m}$) – with the
scattering surface rotated at four different angles
$\phi\in\\{-60\mathrm{\SIUnitSymbolDegree},-40\mathrm{\SIUnitSymbolDegree},-60\mathrm{\SIUnitSymbolDegree},40\mathrm{\SIUnitSymbolDegree}\\}$
– and the corresponding images observed in the camera. b. The variation of
detector counts as a function of the applied phase-signature. This is the
expected count pattern, the reference pattern, for high signal-to-noise ratio
scenario. c. The observed pattern in response to the phase-signature for two
neighbouring pixels $(4,3)$ and $(4,4)$ for rotation
$\phi=40\mathrm{\SIUnitSymbolDegree}$. d. Image captured by the SPDA imager in
the low-light and noisy environment. The observed pattern at the same two
neighbouring pixels $(4,3)$ and $(4,4)$ are also shown. e. The image
reconstructed by cross-correlating the observed pattern with the reference
pattern (see text and Methods for more details).

.

It is important to note that the ability to reveal quantum coherence can be
directly used to enhance the contrast of an image under a low-light and noisy
environment. The experimental setup is similar to Fig. 1, but now the laser
focusing condition is adjusted such that all pixels of the SPDA were
illuminated. Fig. 4 a shows the conventional intensity-based images of the
object for four different rotations of the scattering surface. For these tests
the scattering surface was rotated to $\phi=40\mathrm{\SIUnitSymbolDegree}$,
ensuring that the specular reflection no longer reaches the camera, and the
detected photons were only due to diffusive scattering.

A periodic ramp voltage ($0.1\leavevmode\nobreak\ \mathrm{Hz},\pm 5V$ peak-to-
peak) was applied to the Converter piezoelectric actuator, to encode a
periodic phase-signature pattern among the outgoing time-bin states. The count
pattern expected at the SPDA pixels in response to this phase-signature was
pre-characterized as shown in Fig. 4b. All the pixels followed roughly the
same pattern. From now on, we shall refer to this as the _reference pattern_.

Figure 4c shows the observed pattern at two neighbouring pixels $(4,3)$ and
$(4,4)$. The observed patterns appear distorted due to low SNR, however the
correlation with the reference pattern is clearly visible. A similar
correlation was observed for all the pixels. However, since bright pixels
(such as $(4,4)$) receive more photons than dark pixels (such as $(4,3)$) –
due to the feature of the object – they are affected less by the noise, i.e.,
less distorted. This particular feature has been exploited to enhance the
contrast as described next.

In order to simulate a noisy low-light environment, the laser was highly
attenuated and a lamp was placed in front of the camera to create a high level
of background signals. The scattering surface rotation was kept at
$\phi=40\mathrm{\SIUnitSymbolDegree}$. The image captured by the imaging array
is shown in Fig. 4d. As expected, the presence of high background noise
severely degraded the image contrast. The observed pattern in response to
applied phase-signature at the same two neighbouring pixels $(4,3)$ and
$(4,4)$ are also included in figure 4d. Due to the high background, the DC
level of the observed patterns have shifted up considerably, but the
correlation with the reference pattern is still visible. For each pixel, we
calculated the correlation between the observed and reference pattern (see
Methods for more details). We have chosen a threshold of $2.4$, and Fig. 4e
shows only those pixels having a correlation higher than this value. The
result is a reconstruction of the object image with much-enhanced contrast. We
note that during measuring the observed patterns, only photons from the SL and
LS paths have been considered. In other words, from the three peaks shown in
Fig. 2, we only post-selected the detections from the middle-peak which
required the timing data for each pixel. As a result, our approach is a
combination of utilizing arrival times for coherence analysis, that can also
be utilized for LIDAR applications.

We emphasize that instead of intensity, we used the correlation between
observed and reference pattern to differentiate the bright pixels from the
dark, i.e., instead of choosing an intensity threshold, we chose a correlation
threshold. When intensity is used as a detection parameter, the contrast
degrades with decreasing SNR. On the other hand, visibility – or more
specifically correlation – does not drop as much with decreasing SNR as seen
in Fig. 3b. Nevertheless, as a single parameter, visibility cannot generate
the image as all the illuminated pixels roughly have the same visibility (see
Fig. 6a in Methods). But correlation drops with low SNR as pixels with low SNR
are distorted more. As a result, the correlation is an efficient parameter –
combined with arrival time data – for imaging an object with enhanced
contrast.

We would like to note that the above approach is just a proof-of-principle way
to demonstrate how the quantum coherence observed from scattered photons could
be used in enhancing the contrast. It is in no way the optimum approach, and
better approaches could certainly be devised. For example, the Analyzer
interferometer could be realigned to access both the outputs having intensity,
$P_{\pm}(\Theta)=S_{\pm}(\Theta)+N/2$, with $P_{\pm}(\Theta)(N/2)$ being the
intensity (background noise) at the two output arms for a phase difference
$\Theta$ (here, channel noise is assumed to be equally divided among the
output arms). Then, instead of using statistics from a single-arm,
measurements from both arms like $P(\Theta)=P_{+}(\Theta)-P_{-}(\Theta)$,
could be used to nullify the effect of noise to improve the result. However,
finding a more sophisticated image-reconstruction method is out of this
paper’s scope and will be analyzed elsewhere.

## Discussion

This work has demonstrated a novel and robust approach to transfer and recover
quantum coherence via scattered photons by realizing a multimode, imaging
time-bin interferometer equipped with a single-photon-detector-array sensor.
Our quantum receiver achieves excellent temporal precision of $\approx
120\leavevmode\nobreak\ \mathrm{p}\mathrm{s}$ as well as the ability to
spatially resolve the field-of-view with excellent time-bin visibility across
the whole sensor area. Each pixel independently received the coherence from
the spatial modes of the scattered photons. The maximum observed visibility
was $95\%$, which remained within a $<10\%$ variation over a wide scattering
angle range of $-45\mathrm{\SIUnitSymbolDegree}$ to
$+45\mathrm{\SIUnitSymbolDegree}$. recovered from photons through a
scattering, non-line-of-sight channel. All these features have the potential
to open up new avenues in many applications, including quantum communication
around-the-corner, low-light and 3D imaging, background noise rejection,
around-the-corner imaging [10], velocity measurement [11], LIDAR, object
detection and identification, etc.

We demonstrated the application potential of our method by showing two
potential applications, one is non-line-of-sight quantum communications, the
other is enhancing the contrast of single-photon images. A more detailed and
quantitative analysis of these applications will be given elsewhere. We
believe our results will instigate further research on the application of
coherence in quantum sensing, imaging, and communication and lead to novel
areas of application.

## Author contribution

S.S. performed the analyses and experiments. T.J. conceptualized the idea and
supervised the study. Both authors contributed to writing the manuscript.

## Acknowledgement

We thank Duncan England, Bhashyam Balaji, Ramy Tannous, Youn Seok Lee and Alex
Kirillova for discussions and technical support. This work was supported by
the National Research Council Canada, Defence Research Development Canada,
Industry Canada, Canada Fund for Innovation, Ontario MRI, Ontario Research
Fund, and NSERC (programs Discovery, CryptoWorks21, Strategic Partnership
Grant) and Canada First Research Excellence Fund (TQT).

## Disclosures

The authors declare no conflicts of interest.

## References

  * [1] Rubenok, A., Slater, J. A., Chan, P., Lucio-Martinez, I. & Tittel, W.  Real-world two-photon interference and proof-of-principle quantum key distribution immune to detector attacks.  _Phys. Rev. Lett._ 111, 130501 (2013).  URL https://link.aps.org/doi/10.1103/PhysRevLett.111.130501.
  * [2] Michler, P. _et al._ A quantum dot single-photon turnstile device.  _Science_ 290, 2282–2285 (2000).  URL https://science.sciencemag.org/content/290/5500/2282.  https://science.sciencemag.org/content/290/5500/2282.full.pdf.
  * [3] Lee, H., Kok, P. & Dowling, J. P.  A quantum rosetta stone for interferometry.  _Journal of Modern Optics_ 49, 2325–2338 (2002).  URL https://doi.org/10.1080/0950034021000011536.  https://doi.org/10.1080/0950034021000011536.
  * [4] Flamini, F. _et al._ Thermally reconfigurable quantum photonic circuits at telecom wavelength by femtosecond laser micromachining.  _Light: Science & Applications_ 4, e354–e354 (2015).
  * [5] Pirandola, S., Eisert, J., Weedbrook, C., Furusawa, A. & Braunstein, S. L.  Advances in quantum teleportation.  _Nature Photonics_ 9, 641–652 (2015).
  * [6] Xu, F. _et al._ Experimental quantum fingerprinting arXiv:1503.05499v1, 1503.05499v1.
  * [7] Irvine, W. T. M., Lamas Linares, A., de Dood, M. J. A. & Bouwmeester, D.  Optimal quantum cloning on a beam splitter.  _Phys. Rev. Lett._ 92, 047902 (2004).  URL https://link.aps.org/doi/10.1103/PhysRevLett.92.047902.
  * [8] Pan, J.-W. _et al._ Multiphoton entanglement and interferometry.  _Rev. Mod. Phys._ 84, 777–838 (2012).  URL https://link.aps.org/doi/10.1103/RevModPhys.84.777.
  * [9] Spring, J. B. _et al._ Boson sampling on a photonic chip.  _Science_ 339, 798–801 (2013).  URL https://science.sciencemag.org/content/339/6121/798.
  * [10] Gariepy, G., Tonolini, F., Henderson, R., Leach, J. & Faccio, D.  Detection and tracking of moving objects hidden from view.  _Nature Photonics_ 10, 23–26 (2016).
  * [11] Erskine, D. J. & Holmes, N. C.  White-light velocimetry.  _Nature_ 377, 317–320 (1995).
  * [12] Höhn, D.  Depolarization of a laser beam at 6328 a due to atmospheric transmission.  _Appl. Opt._ 8, 367 (1969).
  * [13] Bourgoin, J.-P. _et al._ Experimentally simulating quantum key distribution with ground-to-satellite channel losses and processing limitations (manuscript in preparation).
  * [14] Sit, A. _et al._ High-dimensional intracity quantum cryptography with structured photons.  _Optica_ 4, 1006–1010 (2017).  URL http://www.osapublishing.org/optica/abstract.cfm?URI=optica-4-9-1006.
  * [15] Paterson, C.  Atmospheric turbulence and orbital angular momentum of single photons for optical communication.  _Phys. Rev. Lett._ 94, 153901 (2005).  URL https://link.aps.org/doi/10.1103/PhysRevLett.94.153901.
  * [16] Malik, M. _et al._ Influence of atmospheric turbulence on optical communications using orbital angular momentum for encoding.  _Opt. Express_ 20, 13195–13200 (2012).  URL http://www.opticsexpress.org/abstract.cfm?URI=oe-20-12-13195.
  * [17] Brendel, J., Gisin, N., Tittel, W. & Zbinden, H.  Pulsed energy-time entangled twin-photon source for quantum communication.  _Phys. Rev. Lett._ 82, 2594–2597 (1999).  URL https://link.aps.org/doi/10.1103/PhysRevLett.82.2594.
  * [18] Stucki, D., Brunner, N., Gisin, N., Scarani, V. & Zbinden, H.  Fast and simple one-way quantum key distribution.  _Appl. Phys. Lett._ 87, 194108 (2005).
  * [19] Townsend, P. D., Rarity, J. G. & Tapster, P. R.  Single photon interference in 10 km long optical fibre interferometer.  _Electron. Lett._ 29, 634–635 (1993).
  * [20] Muller, A. _et al._ “Plug and play” systems for quantum cryptography.  _Appl. Phys. Lett._ 70, 793–795 (1997).
  * [21] Inoue, K., Waks, E. & Yamamoto, Y.  Differential phase shift quantum key distribution.  _Phys. Rev. Lett._ 89, 037902 (2002).
  * [22] Stucki, D. _et al._ High rate, long-distance quantum key distribution over 250 km of ultra low loss fibres.  _New J. Phys._ 11, 075003 (2009).
  * [23] Jin, J. _et al._ Demonstration of analyzers for multimode photonic time-bin qubits.  _Phys. Rev. A_ 97, 043847 (2018).  URL https://link.aps.org/doi/10.1103/PhysRevA.97.043847.
  * [24] Jin, J. _et al._ Genuine time-bin-encoded quantum key distribution over a turbulent depolarizing free-space channel.  _Opt. Express_ 27, 37214 – 37223 (2019).  URL http://www.opticsexpress.org/abstract.cfm?URI=oe-27-26-37214.
  * [25] Vallone, G. _et al._ Interference at the single photon level along satellite-ground channels.  _Phys. Rev. Lett._ 116, 253601 (2016).  URL https://link.aps.org/doi/10.1103/PhysRevLett.116.253601.
  * [26] Cao, Y. _et al._ Long-distance free-space measurement-device-independent quantum key distribution 2006.05088.
  * [27] Tan, K. & Cheng, X.  Specular reflection effects elimination in terrestrial laser scanning intensity data using phong model.  _Remote Sensing_ 9 (2017).  URL https://www.mdpi.com/2072-4292/9/8/853.
  * [28] Bennett, C. H. & Brassard, G.  Quantum cryptography: Public key distribution and coin tossing.  In _Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing_ , 175–179 (IEEE Press, New York, Bangalore, India, 1984).
  * [29] Lydersen, L. _et al._ Hacking commercial quantum cryptography systems by tailored bright illumination.  _Nat. Photonics_ 4, 686–689 (2010).
  * [30] Lydersen, L., Skaar, J. & Makarov, V.  Tailored bright illumination attack on distributed-phase-reference protocols.  _J. Mod. Opt._ 58, 680–685 (2011).
  * [31] Gras, G., Rusca, D., Zbinden, H. & Bussieres, F.  Countermeasure against quantum hacking using detection statistics 2010.08474.
  * [32] Sajeed, S. _et al._ Security loophole in free-space quantum key distribution due to spatial-mode detector-efficiency mismatch.  _Phys. Rev. A_ 91, 062301 (2015).
  * [33] Agne, Sascha.  _Exploration of Higher-Order Quantum Interference Landscapes_.  Ph.D. thesis (2017).  URL http://hdl.handle.net/10012/12307.

## Methods

### Detailed experimental setup

The experimental setup consists of two unbalanced Michelson interferometers
(UMIs). The first UMI – _Converter_ – creates the coherence while the second
one – _Analyzer_ – measures the coherence. The laser (Picoquant laser diode
LDH 8-1-596, PDL-800B driver) emits $697\leavevmode\nobreak\
\mathrm{n}\mathrm{m}$, $300\mathrm{p}\mathrm{s}$ multimode light pulses at a
rate of $5$MHz. Lights coming out of the multimode fiber are collimated and
sent through the Converter. The path difference $\Delta_{C}$ between the long
and short arms turns each incoming state into a coherent superposition of two
time-bins separated by $0.57\mathrm{n}\mathrm{s}$. They are sent towards the
scattering surface and the scattered photons are collected by the Analyzer.
The path difference between the short and the long arm in the Analyzer is
$\Delta_{A}$. A photon coming out of the Analyzer could have traversed one of
the four possible paths: short-short (SS), short-long (SL), long-short (LS)
and long-long (LL). If the path-differences in each UMI match, i.e.,
$\Delta_{C}\approx\Delta_{A}$, the probabilities of a photon coming via SL and
LS paths become indistinguishable and result in interference. Piezoelectric
crystals are placed in the short arm of each interferometer to adjust the path
difference. The photons emerging from the Analyzer are focused into an SPDA
containing $64$ single-photon avalanche photo-diodes. The pixels of the SPDA
are arranged in a $8\times 8$ row-column configuration, with a pitch of
$75\leavevmode\nobreak\ \mathrm{\SIUnitSymbolMicro}\mathrm{m}$. A focusing
lens (Canon EF-S 18-200mm f/3.5-5.6) is used to illuminate the desired range
of pixels with its focal length set to about 60 mm, thus yielding an angular
resolution of $0.07\leavevmode\nobreak\ \mathrm{\SIUnitSymbolDegree}$, and a
total angular field of $0.5\leavevmode\nobreak\ \mathrm{\SIUnitSymbolDegree}$.

Figure 5: The experimental setup. The Converter creates two pulses seperated
by $0.6\mathrm{n}\mathrm{s}$. The path difference between the two short-long
(SL) and long-short (LS) pulses can be adjusted using the piezoelectric
actuator placed in the short arm. A glass cube is present in the long arm of
both interferometers to make the interferometers balanced in the spatial
domain. The Analyzer recombines the pulses coming via SL and LS paths and the
output is studied by the $8\times 8$ SPDA. During the initial alignment, the
incident angle $\theta=25\leavevmode\nobreak\ \mathrm{\SIUnitSymbolDegree}$
(figure not to scale).

### Compensation for spatial mode distortion

A time-bin encoded photon entering an Analyzer with variable angle of
incidence causes a lateral offset between the paths impinging at the exit
beam-splitter [33, 23] causing degradation of interference visibility. Channel
induced spatial-mode distortions further lower the interference quality. The
root cause of this is the inherent asymmetry of the unbalanced Michelson
interferometers. A compensation technique is to use a glass material with
appropriate length and refractive index to create a virtual mirror closer to
the beamsplitter. In this way, the interferometer, although asymmetric in
time, becomes symmetric in the spatial-mode domain. We placed a 118 mm-long
glass cube with refractive index 1.4825 at the long arm to match the distance
between beam-splitter-to-virtual-mirror with the short arm (see [33] for more
details and the analytical formula). This compensation not only improves
performance at higher AOI, but is also necessary to enable high interference
visibility with a multimode beam.

### Correlation of patterns

Here we describe the method by which Fig. 4e was plotted. Figure 6a shows the
same image (right) along with the observed visibility (left) across all the
SPDA pixels. The visibility was calculated as
$V=(I_{max}-i_{min})/(I_{max}+I_{min})$ where $I_{max}\leavevmode\nobreak\
(I_{min})$ is the maximum (minimum) count in a phase-signature cycle. Pixel
$(1,1)$ was the trigger, and $(1,2),(2,2)$ and $(5,8)$ had very high dark
counts. The observed pattern at these three defected pixels are shown in
Figure 6b where no correlation with the reference pattern was visible. Fig. c
shows the observed pattern at the bottom six pixels of column 4. The
resemblance with the _reference pattern_ was quite pronounced. On the other
hand, fig d shows the observed patterns for the bottom three pixels of column
1 that detected relatively fewer number of photons and are much more
distorted. They are in the middle of the two previous extremes and the
correlation value with the reference pattern for them lies in the middle.
Before calculating the cross-correlation, both the reference and observed
patterns were shifted downward by $0.5$ for the ease of analysis.

Figure 6: Visibility and patterns observed at different pixels of the SPDA
imager. a. visibility across all the pixels (left) and the reconstructed image
drawn from correlation (right) b. observed pattern at the three defective
pixels having high dark counts. The correlation with the reference pattern is
lower than threshold. c. observed pattern at the bottom six pixels of column
four. The correlation with the reference pattern is higher than the threshold.
d. observed pattern at bottom three pixels of column one. The correlation with
the reference pattern is between the two previous extremes but still lower
than the chosen threshold. By plotting the pixels with correlation higher than
the threshold, the image was reconstructed with enhanced contrast as shown in
fig a (right).

.

### The single-photon-detector-array sensor

The SPDA camera is composed of 64 single photon avalanche diodes arranged in a
square pattern with 8 rows and 8 columns. Each row and column has eight
$30\mathrm{\SIUnitSymbolMicro}\mathrm{m}$ diameter detectors with X and Y
pitch equal to $75\leavevmode\nobreak\ \mathrm{\SIUnitSymbolMicro}\mathrm{m}$.
The average dark count rate was $35$ cps, deadtime was
$150\leavevmode\nobreak\ \mathrm{n}\mathrm{s}$ and the timing resolution was
$100\mathrm{p}\mathrm{s}$. The electrical output from the camera (Samtec
Cable, SEAC-30-08-XX.X-TU-TU-2) contains 64 LVDS detection signal from the
pixels along with other control signals. An adapter board was designed to
match the electrical signal interface of the camera to that of the time tagger
(Universal quantum devices) as shown in Fig. 7. The developed board translates
the $64$ LVDS camera outputs into four groups of $16$ LVDS channels going into
the time-tagger. As a result, time stamps from the camera can be read by the
tagger at a rate of approximately $1$ GTag/s through an external-PCI-express
interface. The adapter board provide the option to sacrifice upto four pixels
($1,8,58$ and $64$) to be used as external trigger. In this work only one
trigger was used. When triggering is not required, the pixels can function as
normal detectors.

Figure 7: Interface board. The camera output (64 LVDS pairs) are linked to an
interface board, and divides the signals to 4 blocks of 16 LVDS pairs, as well
as provides control signal inputs. The 4 signal blocks are directly interfaced
with a high-speed time-tagger that can handle 64 input channels, up to 1
GTag/s.


# PiVe: Prompting with Iterative Verification
Improving Graph-based Generative Capability of LLMs

Jiuzhou Han♮ Nigel Collier♯ Wray Buntine♭ Ehsan Shareghi♮
♮ Department of Data Science & AI, Monash University
♭ College of Engineering and Computer Science, VinUniversity
♯ Language Technology Lab, University of Cambridge
<EMAIL_ADDRESS>
###### Abstract

Large language models (LLMs) have shown great abilities of solving various
natural language tasks in different domains. Due to the training objective of
LLMs and their pre-training data, LLMs are not very well equipped for tasks
involving structured data generation. We propose a framework, Prompting with
Iterative Verification (PiVe), to improve graph-based generative capability of
LLMs. We show how a small language model could be trained to act as a verifier
module for the output of an LLM (i.e., ChatGPT), and to iteratively improve
its performance via fine-grained corrective instructions. Additionally, we
show how the verifier module could apply iterative corrections offline for a
more cost-effective solution to the text-to-graph generation task. Experiments
on three graph-based datasets show consistent improvement gained via PiVe.
Additionally, we highlight how the proposed verifier module can be used as a
data augmentation tool to help improve the quality of automatically generated
parallel text-graph datasets. 111Our code and data are available at
https://github.com/Jiuzhouh/PiVe

##  1 Introduction

Large language models (LLMs) like ChatGPT and GPT-4 (OpenAI, 2023) have been
quite successful in solving different generative and reasoning tasks. The
combination of their abilities in leveraging in-context learning as well as
instruction following have unlocked new state-of-the-art results across the
natural language processing (NLP) field. The existing LLMs are mostly pre-
trained on a huge volume of unstructured data from the internet including
books, articles, webtexts, repositories, Wikipedia, etc. Training on
unstructured data naturally leads to relatively poor performance when dealing
with tasks that demand organizing text into structured machine-readable
format.

A semantic graphs, as a form of graph-structured data, stores information in a
machine-accessible way (van Harmelen et al., 2008). Generating a semantic
graph from text is known as text-to-graph (T2G) generation and is previously
attempted mostly by fine-tuning small language models (Xu et al., 2022; Guo et
al., 2020). However, generating graph-structured data remains a challenge for
LLMs even in the presence of reasonable number of few-shot examples. In fact,
regardless of the number of few-shot examples, the outputs from LLMs (e.g.,
GPT-3.5) still contain errors and require correction.

In this paper, we focus on how to improve the graph-based generative
capability of LLMs. To this end, we propose the Prompting through Iterative
Verification (PiVe) framework shown in Figure 1. Specially, PiVe involves
leveraging an external verifier module (i.e., a much smaller LM) and
incorporating the feedback from verifier module into the prompt. PiVe
iteratively utilises the verifier module and refines the prompts, via
corrective instructions, before sending them back into the LLM, leading to
substantially improved quality of the generated semantic graphs.

Figure 1: Framework of PiVe.

In particular, to train the verifier modules, we start from a seed dataset of
text and graph (T,G) pairs, and construct an arbitrarily large graph-
perturbation dataset via a simple procedure which takes any graph G from the
seed set and perturbs it arbitrarily on its entities (E), relations (R), or
triples (Tr). The text and perturbed graph ($\bar{\texttt{G}}$), along with a
corrective description to invert the applied perturbation (IP) form a
verification dataset of (T,$\bar{\texttt{G}}$,IP) triples which serve as the
training data for self-supervised learning of our verifier module. The
verification dataset could be as large as desired (i.e., for any seed dataset
D, containing graphs of |E| entities, |R| relations, |Tr| triples, it could
produce $\mathcal{O}$(|D|$\times$|E|$\times$ |R|$\times$|Tr|) perturbations
only by _deleting_.222We did not try other possibilities such as random
replacement or swapping in this work. We then devise fine-tuning and
instruction-tuning to train domain-specific and unified verifiers,
respectively.

During the T2G generation via the LLM (e.g., in the zero-shot setting
"_Transform the text into a semantic graph: Text: … Graph:_ "), the verifier
takes the text T, the output graph from the LLM, and sends a corrective signal
to the LLM (e.g., "_Transform the text into a semantic graph and add the given
triples to the generated semantic graph: Text: … Triple: … Graph:_ "). This
process continues till the verifier module verifies the output as _correct_
and terminates. We refer to this as _Iterative Prompting_. Additionally, there
is another (more cost effective) mode to the verifier module, which starts by
calling the LLM once at the start to get an initial graph, and then the rest
of the corrective steps are all applied step-by-step and iteratively through
the verifier offline. We refer to this as _Iterative Offline Correction_.

Our extensive experiments on three graph-based datasets and the results
demonstrate the effectiveness of the proposed PiVe framework in _consistently_
improving the quality of the LLM output via providing iterative corrective
guidance by an average of 26% across 3 datasets. We also show that the
verifier module can be used as a data augmentation tool to help create high
quality parallel text and graph datasets. We alos show how PiVe could be
leveraged as a data augmentation technique to improve the quality of
automatically constructed text-graph datasets.

##  2 Basic Definitions

A semantic graph is a network that represents semantic relations between
entities. Each semantic graph has its corresponding verbalisation, and can
have different textual representations. A set of triples (i.e., [subject,
predicate, object]) represents a semantic graph. Given a text, the task of
text-to-graph generation is to query an LLM to generate a semantic graph of
the text. The semantic graph should cover the information in the text as much
as possible.

To prompt the LLM, we use few-shot (i.e., 1-shot and 6-shot) by showing an
example of T2G in the prompt to specify the expected format of the semantic
graph (i.e., set of triples). The instruction we use in the prompt is
"Transform the text into a semantic graph." followed by a text and a semantic
graph pair as a demonstration. Different demonstrations are used for different
datasets to adapt to the style of different datasets. We show the used
demonstrations in Appendix D.

##  3 The PiVe Framework

In this section we first explain our training protocol for the verifier module
(§3.1), and then present our framework of iterative verification prompting
(§3.2).

###  3.1 Verifier Module

The quality of the generated semantic graph from LLM prompting could be quite
poor. For instance the LLM often misses triples in the generated graph. In
other words, some semantic relations between entities in the text are
difficult to be captured for LLMs when they are generating a semantic graph.
To detect the missing or incorrect parts of the generated semantic graph, we
design a verifier module.

The verifier module is trained on a small pre-trained LM (§4.2). A typical
graph-based dataset contains parallel text and semantic graph (T,G) pairs. For
different graph-based datasets, we use their corresponding training data for
the seed dataset to create data for the verifier module. In particular, for
each text-graph pair in the original dataset, we create one correct instance
and one perturbed instance. We concatenate the text with graph using a
separator token <S> and the target is to generate a specific output, denoted
as IP, during training. For correct instances, the IP is simply the word
"Correct". For perturbed instances, we have two methods to create them:

  * •

Random method: if the graph contains more than one triple, we randomly omit
one triple from it and concatenate the text with perturbed graph using a
separated token <S>. The target is to generate the missing part (e.g., triple
Tr).

  * •

Heuristic method: Based on the observation that LLMs tend to miss the triples
whose subject and object are not in the text, in addition to randomly omitting
one triple from the graph we also omit the triple from the graph if subject
and object of it are not in the text.

The output to generate for perturbed examples is the missing triple, Tr. By
utilising these two methods, we can create an arbitrarily large verification
dataset to train a verifier module which will be used at inference time during
prompting the LLM.

###  3.2 Iterative Prompting

During the LLM prompting, the generated semantic graphs from LLMs is fed into
the verifier module and the outputs from the verifier module is collected. If
verifier generated "Correct" in its output, it means we do not need to make
changes to the generated graph. Otherwise, the generated output from the
verifier is added to the original prompt to create a new prompt. The new
prompt is then used to query the LLM again. We repeat the whole process
iteratively. The iteration process will stop when it meets a stopping
criterion, described shortly.

#### New Prompt Design

As with the prompt used in the first iteration, we still provide an example in
the new prompt for the subsequent iterations. The new prompt is "Transform the
text into a semantic graph and also add the given triples to the generated
semantic graph." In addition to the text, we also include some triples
predicted by the verifier module which LLMs are likely to miss. This
explicitly instructs the LLM to generate semantic graph and include the given
triples. The given triple set contains the predicted missing triples from each
iteration, which prevents the LLM from making the same mistakes as in previous
iterations. See Appendix D for the used demonstrations.

#### Stopping Criterion

The stopping criterion for the iteration process is decided by the verifier
module. As mentioned in Section 3.1, the verifier module can predict whether
the generated semantic graph is correct or not. Based on the ratio of the
generated outputs being "Correct", for each iteration we calculate the
accuracy over the whole test cases. We set up a threshold $\theta$ as the
stopping criterion. Specifically, for each iteration, when the calculated
accuracy achieves the threshold $\theta$, the iteration stops.

###  3.3 Iterative Offline Correction

Similar to Iterative Prompting, the Offline Correction starts from the online
LLM, but then continues with the step-by-step verification and correction
steps offline. This approach is more cost effective as it relies only on 1 API
call per instance (as opposed to several API calls of iterative prompting),
however it is potentially weaker as it relies on the capability of the small
verifier LM to both verify and apply the needed corrections. The offline
correction stop under the same stopping criterion to Iterative Prompting.

##  4 Experiments

In this section, we describe the datasets and pre-processing method (§4.1),
introduce the models and implementation details (§4.2) and the evaluation
metrics (§4.3). In Subsection 4.4, we describe the main result from PiVe, and
compare the two modes of verifier: Iterative Prompting vs. Iterative Offline
Correction. In Subsection 4.5, we show how PiVe could be used for data
augmentation of automatically generated graph-text datasets (e.g., GenWiki).

###  4.1 Datasets and Preprocessing

We evaluate our PiVe on three graph-based datasets, KELM (Agarwal et al.,
2021), WebNLG+2020 (Gardent et al., 2017) and GenWiki (Jin et al., 2020).

#### KELM

is a large-scale synthetic corpus that consists of the English Wikidata KG and
the corresponding natural text sentences. It has $\sim$15M sentences
synthetically generated using a fine-tuned T5 model. Each graph in KELM is a
linearised KG containing a list of triples of the form [subject, relation,
object]. If a triple has a sub-property, then it is quadruplet instead. We use
a subset ($\sim$60K) of KELM which is named as KELM-sub. The creation of KELM-
sub follows two criteria. We found that most graphs in KELM contain no more
than six triples and only around 2,500 graphs contain more than six triples.
Therefore, 1) we only consider the graphs with no more than six triples, and
2) we do not consider the graphs containing any triple with a sub-property.
Based on these two criteria, for each size of graph (from one triple to six
triples), we sampled equal number of (T,G) pairs. In total, the created KELM-
sub contains 60,000/1,800/1,800 samples as train/validation/test set.

#### WebNLG+2020

contains a set of triples extracted from DBpedia (Auer et al., 2007) in 16
distinct DBpedia categories and text description generated using diverse
lexicalisation patterns. It contains $\sim$38K graphs and each graph has at
most three different descriptions.

#### GenWiki

is a large-scale, general-domain dataset collected from general Wikipedia
which contains 1.3 million non-parallel text and graphs with shared content.
It has two versions: GenWikiFULL ($\sim$1.3M), and a fine version, GenWikiFINE
($\sim$750K), which adds constraints on the text and graphs to force them to
contain highly overlapped entity sets. Both datasets are collected in a
scalable and automatic way. GenWiki also has a human-annotated test set of
1,000 parallel text-graph pairs with high quality. Since both GenWikiFULL and
GenWikiFINE are non-parallel text and graphs datasets, we cannot use it to
train the verifier module. However, the relation types in GenWiki and WebNLG
have some overlaps, so we use the verifier module trained on WebNLG+2020 and
test it on GenWiki test set.

Dataset | Train | Dev
---|---|---
KELM-sub | 110,000 | 3,300
WebNLG & GenWiki | 70,630 | 2,500

Table 1: Statistics of the seed datasets for training the verifier modules on
three datasets.

We use the method described in Section 3.1 to create the data for training the
verifier module. Table 1 shows the statistics of the created training data on
these three seed datasets.

|  | Single Verifier Module | Unified Verifier Module
---|---|---|---
|  | T-F1↑ | G-F1↑ | G-BS↑ | GED↓ | T-F1↑ | G-F1↑ | G-BS↑ | GED↓
KELM-sub | Iteration 1 | 13.50 | 4.89 | 83.92 | 13.20 | 13.50 | 4.89 | 83.92 | 13.20
Iteration 2 | 17.92 | 5.78 | 85.91 | 12.37 | 19.64 | 6.00 | 86.39 | 12.08
Iteration 3 | 19.46 | 6.44 | 86.57 | 12.08 | 22.11 | 6.44 | 87.31 | 11.68
Iteration 4 | 20.17 | 6.61 | 86.83 | 11.95 | 23.11 | 7.50 | 87.70 | 11.35
WebNLG | Iteration 1 | 17.29 | 13.43 | 89.59 | 11.46 | 17.29 | 13.43 | 89.59 | 11.46
Iteration 2 | 18.32 | 14.00 | 89.74 | 11.23 | 18.22 | 13.83 | 89.67 | 11.23
Iteration 3 | 18.57 | 14.00 | 89.82 | 11.22 | 18.55 | 13.88 | 89.74 | 11.20
GenWiki | Iteration 1 | 20.13 | 6.60 | 88.48 | 10.99 | 20.13 | 6.60 | 88.48 | 10.99
Iteration 2 | 20.54 | 6.80 | 88.70 | 10.87 | 20.88 | 6.70 | 88.66 | 10.90
Iteration 3 | 21.09 | 6.80 | 88.78 | 10.83 | 20.99 | 6.70 | 88.91 | 10.88
Table 2: Results of using PiVe on three datasets across all metrics. Single
verifier module represents single dataset-specific verifier module trained on
T5-Large and Unified verifier module is trained on Flan-T5-XXL using
instruction-tuning.

###  4.2 The LLM and Verifier Models

As our LLM, we use ChatGPT (gpt-3.5-turbo) to perform the T2G task. For
verifier module, we use T5-Large (Raffel et al., 2020), and FLAN-T5-XXL (Chung
et al., 2022) as the backbone models for dataset-specific verifier module, and
unified verifier module, respectively. T5 models follow the encoder-decoder
architecture and treat all NLP tasks as unified text-to-text transduction
tasks. Flan-T5 is instruction-finetuned version of T5 which was trained on
1,836 NLP tasks initialized from finetuned T5 checkpoint. For T5-large, we
finetune all parameters for separate verifier modules per each dataset. While
for Flan-T5-XXL, we use LoRA (Hu et al., 2022) as a parameter-efficient
finetuning method, to train a unified verifier module which can follow the
instruction. When using the unified verifier, we specify the dataset name in
the instructions as datasets have different naming convention for relations.

The verifiers are implemented using Pytorch (Paszke et al., 2019) and
Transformers (Wolf et al., 2020). For the training, we use Adam optimizer
(Kingma and Ba, 2015). Details about hyperparameter setting is provided in
Appendix A. For the implementation of parameter efficient training method used
in FLAN-T5-XXL, we use PEFT (Mangrulkar et al., 2022) and 8-bit quantization
technique (Dettmers et al., 2022). All training was done using a single A40
GPU with 48GB of RAM.

###  4.3 Evaluation Metrics

To evaluate the quality of the generated graphs given the ground-truth graphs,
we use four automatic evaluation metrics: Triple Match F1 (T-F1) calculates F1
score based on the precision and recall between the triples in the generated
graph and the ground-truth. We calculate the F1 scores for all test samples
and compute the average F1 score as the final triple Match F1 score. Graph
Match F1 (G-F1) focuses on the entirety of the graph and evaluates how many
graphs are exactly produced the same. For all test samples, we calculate the
F1 score based on the precision and recall between all predicted graphs and
all ground-truth graphs. This F1 score is the final Graph Match F1 score.
Since graphs are represented in a linearised way, we could not simply use the
string match method to check whether two graphs are the same. Instead, we
first build directed graphs from linearised graphs using NetworkX (Laboratory
et al., 2008), then we consider the two graphs to be the same when all node
and edge attributes match. G-BERTScore (G-BS) is a semantic-level metric
proposed by (Saha et al., 2021), which extends the BERTScore (Zhang et al.,
2020) for graph-matching. It takes graphs as a set of edges and solve a
matching problem which finds the best alignment between the edges in predicted
graph and those in ground-truth graph. Each edge is considered as a sentence
and BERTScore is used to calculate the score between a pair of predicted and
ground-truth edges. Based on the best alignment and the overall matching
score, the computed F1 score is used as the final G-BERTScore. Graph Edit
Distance (GED) (Abu-Aisheh et al., 2015) computes the distance between the
predicted graph and the ground-truth graph. It measures how many edit
operations (addition, deletion, and replacement of nodes and edges) are
required for transforming the predicted graph to a graph isomorphic to the
ground-truth graph. Lower GED between two graphs indicates the two graphs are
more similar. In practice, the cost of each operation is set to be 1. For each
sample, GED is normalized by a normalizing constant which is the upper bound
of GED to make sure it is between 0 and 1. For demonstration, we multiply GED
by 100 to show more decimals.

Figure 2: The calculated accuracy from single dataset-specific verifier module
of each iteration of verification. Based on the empirical result, we set the
threshold $\theta$ in stopping criterion to 0.97 (red dashed line). Figure 3:
An example from KELM-sub test set using unified verifier module.

|  | Iterative Prompting | Iterative Offline Correction
---|---|---|---
|  | T-F1↑ | G-F1↑ | G-BS↑ | GED↓ | T-F1↑ | G-F1↑ | G-BS↑ | GED↓
Single Verifier | Iteration 1 | 13.50 | 4.89 | 83.92 | 13.20 | 13.50 | 4.89 | 83.92 | 13.20
Iteration 2 | 17.92 | 5.78 | 85.91 | 12.37 | 17.76 | 5.83 | 86.42 | 12.37
Iteration 3 | 19.46 | 6.44 | 86.57 | 12.08 | 18.51 | 6.11 | 86.91 | 12.19
Iteration 4 | 20.17 | 6.61 | 86.83 | 11.95 | 18.55 | 6.17 | 86.94 | 12.18
Unified Verifier | Iteration 1 | 13.50 | 4.89 | 83.92 | 13.20 | 13.50 | 4.89 | 83.92 | 13.20
Iteration 2 | 19.64 | 6.00 | 86.39 | 12.08 | 16.99 | 5.67 | 87.08 | 12.95
Iteration 3 | 22.11 | 6.44 | 87.31 | 11.68 | 17.76 | 5.67 | 87.48 | 12.96
Iteration 4 | 23.11 | 7.50 | 87.70 | 11.35 | 17.85 | 5.67 | 87.52 | 12.96

Table 3: Comparison between Iterative Prompting and Iterative Offline
Correction on KELM dataset across all metrics using Single Verifier and
Unified Verifier.

###  4.4 Results

One key factor to be decided in PiVe is the threshold $\theta$ used in
stopping criterion. To find the optimal $\theta$, we run the iterative
prompting and plot the percentage of time (denoted as accuracy) the verifier
generates "Correct" along the way. Figure 2 reports this for the each single
verifier module. By checking the quality of the generated graph from each
iteration, we found that setting $\theta$ to be 0.97 could generate the
optimal result for each dataset. This means for WebNLG and GenWiki, the
iteration process stops after Iteration 3; for KELM, the the iteration process
stops after Iteration 4. We run same iterations for unified verifier module.

We report the evaluation results of using PiVe with ChatGPT on the test set of
three datasets in Table 2. By utilising PiVe, on each dataset, we can see the
consistent improvement of the quality of the generated graphs. For instance,
in GenWiki which uses the same verifier module that was trained on the
training data of WebNLG, the improvement of the scores over all metrics
indicates the effectiveness of PiVe. Graph Match F1 (G-F1) is the most strict
metric among. Since the graphs are generated by the LLM through one-shot
learning, it is hard to get high G-F1 score (basically aiming for exact match
without any minor deviation in wording, spelling, entities, or relations).

On WebNLG and GenWiki datasets, single verifier module performs slightly
better than unified verifier module. While on KELM-sub dataset, unified module
performs far better. We speculate this is due to the size of training data for
KELM-sub verifier module being larger than that for WebNLG and GenWiki (as
shown in Table 1). Since unified verifier module combines the training data of
different datasets, more training data leads to better performance for
instruction-tuning.

#### Qualitative Example.

In Figure 3, we demonstrate an example from KELM-sub test set using unified
verifier module. In Iteration 1, based on the prediction from the LLM, the
verifier module predicts the missing triple ["Gord Stellick", "sex or gender",
"male"]. By suggesting this missing triple in the next iteration of prompt,
the prediction from LLM includes it. Then, the verifier module predicts the
missing triple ["Gord Stellick", "country of citizenship", "Canada"]. In
Iteration 3, both of these two missing triples are included in the prediction
from LLM, and at this time, the verifier module predicts "Correct". The
prediction from Iteration 3 contains all information correctly in the
reference. See another example in Appendix C.

#### Iterative Prompting vs. Iterative Offline Correction.

Instead of iteratively prompting the LLM, another way to utilise the results
from verifier module is to append the predicted missing triples to the
previously generated graph. The results of the comparison between iterative
prompting and iterative offline correction using single verifier module and
unified verifier module on KELM dataset is shown in Table 3. Iterative offline
correction performs worse than iteratively prompting. This might be because
iteratively prompting has the chance of doing self-correction. In each
iteration, when we prompt the LLM, the generated graphs can probably correct
the mistakes that were made in previous iteration. Due to the page limit, we
report the comparison results on WebNLG and GenWiki datasets in Appendix B.
Similarly, iterative prompting can achieve better results than iterative
offline correction over all using different verifier modules. This indicates
the necessity of doing iteratively prompting in PiVe.

#### More shots impact.

While in all our experiments, for cost reason, we used only one-shot
demonstrations for the LLM prompting (i.e., GPT-3.5), we show that PiVe is
effective in improving the results regardless of the underlying number of
shots. Here we report the results of 6-shot333Since there are six different
sizes of graphs in KELM-sub dataset, we randomly choose one demonstration for
each size. with the iterative offline correction (i.e., only using the LLM
once to get the initial graph, while the correction steps are all applied
step-by-step and offline). Table 4, demonstrates the results on KELM-sub using
unified verifier with iterative offline correction. The results show that
adding more demonstrations, as expected, improves the quality of the generated
initial graphs from the LLM, while using the verifier module can consistently
improve the produced output further.

| T-F1↑ | G-F1↑ | G-BS↑ | GED↓
---|---|---|---|---
Iteration 1 | 35.25 | 10.78 | 85.43 | 10.19
Iteration 2 | 36.96 | 12.56 | 88.20 | 10.14
Iteration 3 | 37.25 | 12.61 | 88.47 | 10.13
Iteration 4 | 37.37 | 12.68 | 88.54 | 10.13

Table 4: Results of doing 6-shot learning on KELM-sub using Unified Verifier
with Iterative Offline Correction.

###  4.5 PiVe as Data Augmentation

Training a good G2T or T2G model requires a large amount of high-quality
parallel text and graph pairs or pre-training protocols to accommodate for
lack of data Han and Shareghi (2022). However, creating the parallel data by
human is a labour-intensive and time-consuming work. Jin et al. (2020)
proposed GenWiki, an automatically constructed large dataset containing non-
parallel text and graphs with shared content. Although the text and graphs in
GenWiki contain shared content, it can still only be used for unsupervised
training due to the low entity and relation overlap between text and graph.
Our verifier module can naturally serve as a data augmentation tool to improve
the overlap between the text and graph of automatically constructed datasets.

#### Iterative Augmentation.

Based on GenWikiFINE ($\sim$750K), first we filter out the text that has
little overlap with the graph. After filtering, we got around 110K text-graph
pairs. Then following the process described in Section 3.1, we use the WebNLG
verifier module and the iterative offline correction to improve the coverage
and quality of the 110k pairs and formed GenWiki-HIQ. We ran this for four
iterations, and the stopping criterion was based on the results from Table 5
(i.e., when the improvement was smaller than 5%, we stopped the iteration.).

To evaluate the effectiveness of the verifier module as data augmentation
tool, as well the quality of the generated graph, first we use FLAN-T5-XL
model to generate a description of each graph in zero-shot setting by using
the prompt "Transform the semantic graph into a description." for each
iteration. Then we leverage automatic quality evaluation metrics to calculate
the score between the generated description and the corresponding text.
Ideally, the higher the similarity between the graph and the corresponding
text, the higher the score of the generated description and corresponding
text. We use four commonly used quality evaluation metrics which are BLEU
(Papineni et al., 2002), METEOR (Banerjee and Lavie, 2005), TER (Snover et
al., 2006), BERTScore.

| BLEU↑ | METEOR↑ | TER↓ | BERTScore↑
---|---|---|---|---
Iteration 1 | 4.75 | 18.02 | 80.72 | 89.47
Iteration 2 | 11.86 | 26.25 | 73.79 | 91.49
Iteration 3 | 14.90 | 29.69 | 72.29 | 92.00
Iteration 4 | 15.93 | 31.05 | 72.01 | 92.14

Table 5: Results of iterative augmentation on filtered 110K text-graph pairs
from GenWikiFINE across four metrics after each iteration. We take the text-
graph pairs from Iteration 4 as the created GenWiki-HIQ dataset.

#### Result.

We used the dataset-specific verifier module to do the data augmentation. We
conducted four iterations and the evaluation results are shown in Table 5. The
results in Iteration 1 represent the scores over non-parallel graph-text pairs
from GenWikiFINE, which have low overlap between graph and text. By using
verifier module iteratively, we add more missing triples to the original
graph, thus leading the higher quality scores. As the iteration progresses,
fewer missing triples are added and we take the augmented graph-text pairs
from the last iteration as the final created GenWiki-HIQ dataset, which is
released along with our code.

#### Qualitative Example.

In Figure 4, we demonstrate an example from the created GenWiki-HIQ dataset
and the original graph in GenWikiFINE. After data augmentation process, the
graph in GenWiki-HIQ contains more information in text.

Figure 4: An example from GenWiki-HIQ compared to the original graph in
GenWikiFINE.

##  5 Background and Related Work

###  5.1 In-Context Learning

With the scaling of model size and training corpus size (Brown et al., 2020;
Chowdhery et al., 2022), LLMs demonstrate new abilities of learning from a few
demonstrations which contain some training examples (Dong et al., 2023). As a
new paradigm, In-Context Learning does not require parameter updates and
directly performs predictions on the pre-trained language models. The provided
demonstration examples in the prompt follow the same format, which are usually
written in natural language templates. By concatenating a query question with
the demonstrations in the prompt, LLMs can learn from the given examples and
make a prediction of the query question. Previous research (Liu et al., 2022;
Lu et al., 2022) has shown that the number of the demonstrations and the order
of the demonstrations can influence the In-context Learning performance. These
are further points of future investigation, which could potentially improve
the initial graph produced by the LLM, which could further be corrected with
the PiVe framework.

###  5.2 Instruction-Tuning

Instruction-Tuning (Mishra et al., 2022; Wang et al., 2022; Longpre et al.,
2023) is a framework of doing multi-task learning, which enables the use of
human-readable instructions to guide the prediction of LLMs. This novel
training paradigm can improve the performance of the downstream tasks and also
shows great generalisation ability on unseen tasks (Chung et al., 2022; Sanh
et al., 2022). Wang et al. (2023) proposed a unified information extraction
framework based on multi-task instruction-tuning. Zhou et al. (2023) utilised
instruction-tuning to perform controlled text generation following certain
constraints. In our work, we use instruction-tuning to train a unified
verifier module, which can follow the instruction to perform predictions on
different datasets.

###  5.3 Verifiers

Leveraging small models could further improve the performance of LLMs. Cobbe
et al. (2021) proposed to solve math word problem by utilising verifier. The
verifier is used to judge the correctness of model-generated solutions. During
test time, based on multiple candidate solutions generated, verifier
calculates the correctness probability and the final answer will be selected
by the verifier from the ranked list. Welleck et al. (2023) proposed self-
correction, an approach that trains a small models to iteratively apply self-
correction. The idea of self-correction looks similar to our PiVe. While
Welleck et al. (2023) focuses on the design of a self-correcting language
model, PiVe presents a very simple verifier module design and a simple data
perturbation strategy to train such model. The ideas presented in our work are
developed concurrently and independently.

##  6 Conclusion

We proposed PiVe, an iterative verification framework, to improve the graph-
based generative capability of LLMs. We illustrated how a simple perturbation
technique could be used to build data for training a verifier module which
both verifies and corrects outputs from an LLM. We used different training
strategies to build both dataset-specific verifiers with finetuning, and a
unified verifier with instruction-tuning. Our verifier module could act both
as an iterative prompting guide to improve outputs of an LLM, as well as an
iterative offline correction system that starts from an LLM outputs but
continuously improves it offline. The experimental results on 3 graph-based
datasets demonstrates the effectiveness of PiVe. Furthermore, PiVe can also be
used as a data augmentation technique to help improve the quality of
automatically generated parallel text-graph datasets. By using verifier
module, we create GenWiki-HIQ, a dataset containing 110K parallel text and
graphs for future research.

## Limitations

Since training of the verifier module requires human-created dataset, it would
be more effective if more heuristic methods are used when creating the
dataset. In this work, we only focus on the triple missing mistake made by
LLMs, so that the verifier module is not sensitive to the order of the head
entity and tail entity. This means when the order of the head entity and tail
entity in a triple of a generated graph from LLMs is incorrect, verifier
module is not able to detect this type of mistake.

## Ethics Statement

Our work is built on top of existing pre-trained language models. Our goal was
not to attend to alleviate the well-documented is- sues (e.g., privacy,
undesired biases, etc) that such models embody. For this reason, we share the
similar potential risks and concerns posed by these models.

## References

  * Abu-Aisheh et al. (2015) Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, and Patrick Martineau. 2015\.  An exact graph edit distance algorithm for solving pattern recognition problems.  In _ICPRAM 2015 - Proceedings of the International Conference on Pattern Recognition Applications and Methods, Volume 1, Lisbon, Portugal, 10-12 January, 2015_ , pages 271–278. SciTePress.
  * Agarwal et al. (2021) Oshin Agarwal, Heming Ge, Siamak Shakeri, and Rami Al-Rfou. 2021.  Knowledge graph based synthetic corpus generation for knowledge-enhanced language model pre-training.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021_ , pages 3554–3565. Association for Computational Linguistics.
  * Auer et al. (2007) Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary G. Ives. 2007.  Dbpedia: A nucleus for a web of open data.  In _The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC 2007, Busan, Korea, November 11-15, 2007_ , volume 4825 of _Lecture Notes in Computer Science_ , pages 722–735. Springer.
  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  METEOR: an automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization@ACL 2005, Ann Arbor, Michigan, USA, June 29, 2005_ , pages 65–72. Association for Computational Linguistics.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022.  Palm: Scaling language modeling with pathways.  _CoRR_ , abs/2204.02311.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y. Zhao, Yanping Huang, Andrew M. Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. 2022.  Scaling instruction-finetuned language models.  _CoRR_ , abs/2210.11416.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021.  Training verifiers to solve math word problems.  _CoRR_ , abs/2110.14168.
  * Dettmers et al. (2022) Tim Dettmers, Mike Lewis, Sam Shleifer, and Luke Zettlemoyer. 2022.  8-bit optimizers via block-wise quantization.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.
  * Dong et al. (2023) Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, Lei Li, and Zhifang Sui. 2023.  A survey for in-context learning.  _CoRR_ , abs/2301.00234.
  * Gardent et al. (2017) Claire Gardent, Anastasia Shimorina, Shashi Narayan, and Laura Perez-Beltrachini. 2017.  The webnlg challenge: Generating text from RDF data.  In _Proceedings of the 10th International Conference on Natural Language Generation, INLG 2017, Santiago de Compostela, Spain, September 4-7, 2017_ , pages 124–133. Association for Computational Linguistics.
  * Guo et al. (2020) Qipeng Guo, Zhijing Jin, Xipeng Qiu, Weinan Zhang, David Wipf, and Zheng Zhang. 2020\.  Cyclegt: Unsupervised graph-to-text and text-to-graph generation via cycle training.  _CoRR_ , abs/2006.04702.
  * Han and Shareghi (2022) Jiuzhou Han and Ehsan Shareghi. 2022.  Self-supervised graph masking pre-training for graph-to-text generation.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 4845–4853, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Hu et al. (2022) Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2022.  Lora: Low-rank adaptation of large language models.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.
  * Jin et al. (2020) Zhijing Jin, Qipeng Guo, Xipeng Qiu, and Zheng Zhang. 2020.  Genwiki: A dataset of 1.3 million content-sharing text and graphs for unsupervised graph-to-text generation.  In _Proceedings of the 28th International Conference on Computational Linguistics, COLING 2020, Barcelona, Spain (Online), December 8-13, 2020_ , pages 2398–2409. International Committee on Computational Linguistics.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Laboratory et al. (2008) Los Alamos National Laboratory, United States. Department of Energy. Office of Scientific, and Technical Information. 2008.  _Exploring Network Structure, Dynamics, and Function Using Networkx_.  United States. Department of Energy.
  * Liu et al. (2022) Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. 2022.  What makes good in-context examples for gpt-3? In _Proceedings of Deep Learning Inside Out: The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures, DeeLIO@ACL 2022, Dublin, Ireland and Online, May 27, 2022_ , pages 100–114. Association for Computational Linguistics.
  * Longpre et al. (2023) Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoc V. Le, Barret Zoph, Jason Wei, and Adam Roberts. 2023.  The flan collection: Designing data and methods for effective instruction tuning.  _CoRR_ , abs/2301.13688.
  * Lu et al. (2022) Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022\.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022_ , pages 8086–8098. Association for Computational Linguistics.
  * Mangrulkar et al. (2022) Sourab Mangrulkar, Sylvain Gugger, Lysandre Debut, Younes Belkada, and Sayak Paul. 2022.  Peft: State-of-the-art parameter-efficient fine-tuning methods.  https://github.com/huggingface/peft.
  * Mishra et al. (2022) Swaroop Mishra, Daniel Khashabi, Chitta Baral, and Hannaneh Hajishirzi. 2022.  Cross-task generalization via natural language crowdsourcing instructions.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022_ , pages 3470–3487. Association for Computational Linguistics.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 technical report.  _CoRR_ , abs/2303.08774.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, July 6-12, 2002, Philadelphia, PA, USA_ , pages 311–318. ACL.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 8024–8035.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21:140:1–140:67.
  * Saha et al. (2021) Swarnadeep Saha, Prateek Yadav, Lisa Bauer, and Mohit Bansal. 2021.  Explagraphs: An explanation graph generation task for structured commonsense reasoning.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021_ , pages 7716–7740. Association for Computational Linguistics.
  * Sanh et al. (2022) Victor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Arun Raja, Manan Dey, M Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma Sharma, Eliza Szczechla, Taewoon Kim, Gunjan Chhablani, Nihal V. Nayak, Debajyoti Datta, Jonathan Chang, Mike Tian-Jian Jiang, Han Wang, Matteo Manica, Sheng Shen, Zheng Xin Yong, Harshit Pandey, Rachel Bawden, Thomas Wang, Trishala Neeraj, Jos Rozen, Abheesht Sharma, Andrea Santilli, Thibault Févry, Jason Alan Fries, Ryan Teehan, Teven Le Scao, Stella Biderman, Leo Gao, Thomas Wolf, and Alexander M. Rush. 2022.  Multitask prompted training enables zero-shot task generalization.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.
  * Snover et al. (2006) Matthew G. Snover, Bonnie J. Dorr, Richard M. Schwartz, Linnea Micciulla, and John Makhoul. 2006.  A study of translation edit rate with targeted human annotation.  In _Proceedings of the 7th Conference of the Association for Machine Translation in the Americas: Technical Papers, AMTA 2006, Cambridge, Massachusetts, USA, August 8-12, 2006_ , pages 223–231. Association for Machine Translation in the Americas.
  * van Harmelen et al. (2008) Frank van Harmelen, Vladimir Lifschitz, and Bruce W. Porter, editors. 2008.  _Handbook of Knowledge Representation_, volume 3 of _Foundations of Artificial Intelligence_.  Elsevier.
  * Wang et al. (2023) Xiao Wang, Weikang Zhou, Can Zu, Han Xia, Tianze Chen, Yuansen Zhang, Rui Zheng, Junjie Ye, Qi Zhang, Tao Gui, Jihua Kang, Jingsheng Yang, Siyuan Li, and Chunsai Du. 2023.  Instructuie: Multi-task instruction tuning for unified information extraction.  _CoRR_ , abs/2304.08085.
  * Wang et al. (2022) Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Atharva Naik, Arjun Ashok, Arut Selvan Dhanasekaran, Anjana Arunkumar, David Stap, Eshaan Pathak, Giannis Karamanolakis, Haizhi Gary Lai, Ishan Purohit, Ishani Mondal, Jacob Anderson, Kirby Kuznia, Krima Doshi, Kuntal Kumar Pal, Maitreya Patel, Mehrad Moradshahi, Mihir Parmar, Mirali Purohit, Neeraj Varshney, Phani Rohitha Kaza, Pulkit Verma, Ravsehaj Singh Puri, Rushang Karia, Savan Doshi, Shailaja Keyur Sampat, Siddhartha Mishra, Sujan Reddy A, Sumanta Patro, Tanay Dixit, and Xudong Shen. 2022.  Super-naturalinstructions: Generalization via declarative instructions on 1600+ NLP tasks.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022_ , pages 5085–5109. Association for Computational Linguistics.
  * Welleck et al. (2023) Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. 2023.  Generating sequences by learning to self-correct.  In _The Eleventh International Conference on Learning Representations_.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, EMNLP 2020 - Demos, Online, November 16-20, 2020_ , pages 38–45. Association for Computational Linguistics.
  * Xu et al. (2022) Yi Xu, Luoyi Fu, Zhouhan Lin, Jiexing Qi, and Xinbing Wang. 2022.  INFINITY: A simple yet effective unsupervised framework for graph-text mutual conversion.  _CoRR_ , abs/2209.10754.
  * Zhang et al. (2020) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020\.  Bertscore: Evaluating text generation with BERT.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Zhou et al. (2023) Wangchunshu Zhou, Yuchen Eleanor Jiang, Ethan Wilcox, Ryan Cotterell, and Mrinmaya Sachan. 2023.  Controlled text generation with natural language instructions.  _CoRR_ , abs/2304.14293.

## Appendix

##  Appendix A Hyperparameter Setting

Table 6 and Table 7 show the hyperparameters for training single verification
module and unified verification module, respectively.

Hyperparameter | Assignment
---|---
Model | T5-Large
Epoch | 5
Batch Size | 16
Optimizer | Adam
Learning Rate | $2\times 10^{-5}$
Warm-up Step | 500
Beam Size | 5

Table 6: Hyperparameters of single verification module.

Hyperparameter | Assignment
---|---
Model | FLAN-T5-XXL
Epoch | 2
Batch Size | 48
Optimizer | Adam
Learning Rate | $3\times 10^{-5}$
Warm-up Step | 100
Beam Size | 4

Table 7: Hyperparameters of unified verification module.

##  Appendix B Additional Experiment Result

Table 8 and Table 9 show the results of the comparison between iteratively
prompt and iterative offline correction on WebNLG and GenWiki datasets.

|  | Iterative Prompting | Iterative Offline Correction
---|---|---|---
|  | T-F1↑ | G-F1↑ | G-BS↑ | GED↓ | T-F1↑ | G-F1↑ | G-BS↑ | GED↓
Single Verifier | Iteration 1 | 17.29 | 13.43 | 89.59 | 11.46 | 17.29 | 13.43 | 89.59 | 11.46
Iteration 2 | 18.32 | 14.00 | 89.74 | 11.23 | 18.03 | 13.55 | 89.16 | 11.52
Iteration 3 | 18.57 | 14.00 | 89.82 | 11.22 | 18.10 | 13.55 | 89.19 | 11.51
Unified Verifier | Iteration 1 | 17.29 | 13.43 | 89.59 | 11.46 | 17.29 | 13.43 | 89.59 | 11.46
Iteration 2 | 18.22 | 13.83 | 89.67 | 11.23 | 18.02 | 13.49 | 89.21 | 11.61
Iteration 3 | 18.55 | 13.88 | 89.74 | 11.20 | 18.06 | 13.49 | 89.07 | 11.65

Table 8: Comparison between Iterative Prompting and Iterative Offline
Correction on WebNLG dataset across all metrics using Single Verifier and
Unified Verifier.

|  | Iterative Prompting | Iterative Offline Correction
---|---|---|---
|  | T-F1↑ | G-F1↑ | G-BS↑ | GED↓ | T-F1↑ | G-F1↑ | G-BS↑ | GED↓
Single Verifier | Iteration 1 | 20.13 | 6.60 | 88.48 | 10.99 | 20.13 | 6.60 | 88.48 | 10.99
Iteration 2 | 20.54 | 6.80 | 88.70 | 10.87 | 20.24 | 6.70 | 89.00 | 10.95
Iteration 3 | 21.09 | 6.80 | 88.78 | 10.83 | 20.32 | 6.80 | 89.07 | 10.93
Unified Verifier | Iteration 1 | 20.13 | 6.60 | 88.48 | 10.99 | 20.13 | 6.60 | 88.48 | 10.99
Iteration 2 | 20.88 | 6.70 | 88.66 | 10.90 | 20.37 | 6.60 | 89.08 | 10.96
Iteration 3 | 20.99 | 6.70 | 88.91 | 10.88 | 20.42 | 6.60 | 89.11 | 10.94

Table 9: Comparison between Iterative Prompting and Iterative Offline
Correction on GenWiki dataset across all metrics using Single Verifier and
Unified Verifier.

##  Appendix C PiVe Example

In Figure 5, we illustrate another example of PiVe from WebNLG test set using
single verification module. In Iteration 1, the verification module predict
the missing triple ["Agremiação Sportiva Arapiraquense", "ground", "Estádio
Municipal Coaracy da Mata Fonseca"], even though there is a similar triple but
containing mistakes in the prediction from the LLM. In Iteration 2, the LLM
corrects the mistakes in the previous iteration, and also includes the
predicted missing triple. Based on the prediction from the LLM, the
verification module predict the missing triple ["Campeonato Brasileiro Série
C", "country", "Brazil"]. In Iteration 3, the verification module predict
"Correct" to the final prediction from the LLM. After three iterations using
PiVe, the predicted graph contains all information in the reference.

Figure 5: An example from WebNLG test set using single verification module.

##  Appendix D Demonstrations in Prompt

Figure 6 shows the demonstrations used for KELM-sub and Figure 7 shows the
demonstrations used for WebNLG and GenWiki. In Iteration 1, we use the
demonstration that does not contain the missing triples. For subsequent
iterations, we include the missing triples in the demonstration.

Figure 6: The demonstrations used in prompt for KELM-sub. Figure 7: The
demonstrations used in prompt for WebNLG and GenWiki.