# Real-time Transmission of Geometrically-shaped Signals using a Software-
defined GPU-based Optical Receiver

Sjoerd van der Heide1  Ruben S. Luis2  Sebastiaan Goossens1  Benjamin J.
Puttnam2  Georg Rademacher2  Ton Koonen1  Satoshi Shinada2  Yoshinari Awaji2
Alex Alvarado1  Hideaki Furukawa2  Chigo Okonkwo1  1Department of Electrical
Engineering, Eindhoven University of Technology, PO Box 513, 5600 MB,
Eindhoven, the Netherlands
2National Institute of Information and Communications Technology, Photonic
Network System Laboratory, 4-2-1, Nukui-Kitamachi, Koganei, Tokyo, 184-8795,
Japan<EMAIL_ADDRESS>
###### Abstract

A software-defined optical receiver is implemented on an off-the-shelf
commercial graphics processing unit (GPU). The receiver provides real-time
signal processing functionality to process 1 GBaud minimum phase (MP) 4-, 8-,
16-, 32-, 64-, 128-ary quadrature amplitude modulation (QAM) as well as
geometrically shaped (GS) 8- and 128-QAM signals using Kramers-Kronig (KK)
coherent detection. Experimental validation of this receiver over a 91 km
field-deployed optical fiber link between two Tokyo locations is shown with
detailed optical signal-to-noise ratio (OSNR) investigations. A net data rate
of 5 Gbps using 64-QAM is demonstrated.

††journal: oe††articletype: Research Article

ignore

##  1 Introduction

In recent years, graphics processing units (GPUs) have been proposed as an
alternative to field-programmable gate arrays (FPGAs) [1, 2, 3] and
application-specific integrated circuits (ASICs) for optical communications
[4, 5, 6, 7, 8, 9, 10, 11, 12]. More than a decade of steady exponential
improvement of computation capacity (45% yearly increase [13]) and energy
efficiency (25% yearly increase [14]) of GPUs have accelerated its potential
applications in the field of optical communications. Recent demonstrations
include real-time forward error correction (FEC) decoding [4, 5], physical-
layer functionality [6, 7, 8], differential quaternary phase-shift-keying
(DQPSK) detection [9], and flexible multi-modulation format detection using
directly detected pulse-amplitude modulated signals, and coherently detected
quadrature amplitude modulation (QAM) signals [10, 11, 12] using Kramers-
Kronig (KK) detection [15]. We demonstrated a real-time receiver over a
$10000\text{\,}\mathrm{k}\mathrm{m}$ straight-line link [12] and a field-
deployed fiber [11].

In this work, the flexible, software-defined real-time multi-modulation format
receiver is optimized for improved performance and demonstrated modulation
formats are extended with odd-power QAM and geometric shaping (GS). A
commercial off-the-shelf GPU is used for real-time digital signal processing
of minimum phase (MP) 4-, 8-, 16-, 32-, 64-, and 128/̄QAM as well as
geometrically-shaped 8/̄QAM and 128/̄QAM signals using KK coherent detection
[15]. The receiver is experimentally validated using a field-deployed
transmission link between two Tokyo locations with dynamic components of the
receiver digital signal processing (DSP) handling fluctuations of the
environmental conditions. Detailed investigations into optical signal-to-noise
ratio (OSNR) performance are shown and carrier-to-signal power ratio (CSPR) is
optimized for all transmission scenarios. Net throughput is calculated for the
evaluated formats and multiple hard decision forward error correction (HD-FEC)
algorithms, with 64/̄QAM paired with a 20% overhead HD-FEC achieving a net
throughput of $5\text{\,}\mathrm{G}\mathrm{b}\mathrm{p}\mathrm{s}$ at
$28.2\text{\,}\mathrm{d}\mathrm{B}$ OSNR.

This paper is an extension to [11]. The demonstrated capabilities of the real-
time receiver are extended to show support for odd-power QAM and
geometrically-shaped constellations. Furthermore, the performance of the
receiver with respect to [11] is improved through several optimizations;
Firstly, the power of the digitally-inserted carrier tone with respect to the
signal (CSPR) is optimized. In [11], a static CSPR value was used, here, a
detailed investigation into the influence of CSPR on transmission performance
is presented. Secondly, the reconfigurable optical add-drop multiplexers
(ROADMs) are removed from the transmission path and replaced by an erbium-
doped fiber amplifier (EDFA) at the remote site, enabling evaluation of the
receiver at higher OSNR. Thirdly, the
$1\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$ photodiode is replaced by a
$6.5\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$ model, significantly improving
the receiver bandwidth. Fourthly, the gap between the signal and digitally-
inserted carrier is optimized, resulting in the use of a smaller gap. Fifthly,
launch power is optimized, but we observe no significant launch power
dependence on OSNR performance. These changes and optimizations substantially
improve transmission performance compared to what we presented in [11].
Finally, more modulation formats are evaluated, 4-, 8-, GS-8-, 16-, 32-, 64-,
128-, and GS-128/̄QAM to comprehensively demonstrate multi-modulation format
receiver capability.

Figure 1: Real-time Kramers-Kronig digital signal processing chain including
GPU profiler trace, additional details in [11].

##  2 Digital signal processing chain

Fig. 1 shows the real-time DSP chain for KK coherent N/̄QAM signals. Here, an
overview of its GPU-based implementation is given. A more detailed description
can be found in [11]. First, buffers containing 222 digitized samples are
transferred from analog-to-digital converter (ADC) to GPU in real time using
direct memory access (DMA). The signal processing starts with a GPU kernel
converting samples received as 12-bit fixed point to 32-bit floating point
numbers, adding the appropriate DC offset, and performing the square root and
logarithm KK front-end operations. This first kernel is annotated by the
number 1 in Fig. 1. In step 3, enabled by a pair of 100% overlap-save
1024-point fast Fourier transforms (FFTs), the phase of the optical signal is
recovered by a frequency-domain Hilbert transform. This phase is combined with
the amplitude calculated in step 1 to reconstruct the optical signal [15]
which is subsequently downconverted for further processing. Another pair of
FFTs supports frequency-domain static equalization and resampling from 4 to 2
samples-per-symbol. Finally, a 4-tap adaptive time-domain widely-linear [16]
decision-directed least mean square (DD-LMS) equalizer is employed to recover
the signal. The minimum Euclidean distance decisions made by the equalizer are
demapped into bits and sent to random-access memory (RAM).

Full utilization of GPU resources is achieved through massive parallelization
within kernels as well as operating multiple processing streams in parallel.
Most of the kernels operating within each stream are highly parallel
themselves, e.g. the FFTs, Hilbert transform, and the frequency-domain
equalizer. However, algorithms such as the adaptive time-domain equalizer are
hard to parallelize due to its sequential nature and time-dependencies of the
tap updates. The use of multiple processing streams allows these hard-to-
parallelize algorithms to run next to easy-to-parallelize algorithms.
Therefore, even though the adaptive equalization takes up significant amount
of time as shown in the GPU profiler trace in Fig. 1, significant amount of
resources is not required. This concept and many other implementation
strategies are discussed in detail in [11]. Constellation cardinality only
slightly influences GPU resource utilization. The KK algorithm and static
equalization take up the majority of computational resources.

Note that several parameters of the real-time receiver are static and
optimized offline. Since the ADC is AC-coupled, the DC-term of the signal is
lost. This DC-term is crucial for correct signal reconstruction and is added
in step 1 as described above. The question remains how to determine the
optimal value since it is dependent on the signal power, noise power, and
CSPR. Throughout this work, all measurements are performed multiple times
using different DC offset values to ensure the optimal performance is
observed. Alternatively, one could implement an algorithm to calculate and
update the optimal DC-term in real time [17].

Similarly, the 203-tap static frequency-domain equalizer is optimized offline
using a training sequence every time that the data aquisition is initialized.
Therefore, the entire signal processing chain up to the adaptive equalizer is
agnostic to the modulation format. The adaptive equalizer only needs to know
the constellation since, after initial setup and convergence using a training
sequence, it is updated in a blind decision-directed fashion where part of a
buffer is used to update equalizer taps for subsequent buffers. Also, the
symbol decisions are demapped into bits and are considered as the output of
the DSP chain. The constellation points and bit mapping are uploaded to the
GPU for the equalizer to make decisions based on a minimum Euclidean distance
criterion. Note that no phase compensation algorithm is required since the KK
coherent receiver scheme is free of phase noise. Furthermore, the DSP chain
does not rely on specific properties of modulation formats such as symmetry.
Therefore, support for various geometrically-shaped constellations is achieved
by uploading the location of the constellation points and corresponding bit
mapping for the equalizer and demapper to use.

Figure 2: Experimental setup with a field-deployed link between Koganei and
Otemachi, Tokyo, Japan.

##  3 Experimental Setup

Fig. 2 shows the experimental setup using the field-deployed link between
Koganei and Otemachi, Tokyo. First, an 8-bit
$12\text{\,}\mathrm{G}\mathrm{S}\mathrm{/}\mathrm{s}$ arbitrary-waveform
generator (AWG) generates MP
$1\text{\,}\mathrm{G}\mathrm{B}\mathrm{a}\mathrm{u}\mathrm{d}$ QAM signals
with 1% rolloff root-raised-cosine (RRC) pulse shaping with a digitally
inserted carrier tone at $0.516\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$. The
220 N-ary symbol sequence is generated using PCG64 pseudo-random numbers and
mapped to the desired modulation format. Both conventional and geometrically
shaped QAM formats are employed, the latter optimized for the additive white
Gaussian noise (AWGN) channel and generated through an iterative optimization
process similar to [18]. Further details can be found in Section 5.

A $16\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$ in-phase and quadrature
modulator (IQM) modulates the signal onto a
$100\text{\,}\mathrm{k}\mathrm{H}\mathrm{z}$ linewidth
$1550.51\text{\,}\mathrm{n}\mathrm{m}$ external cavity laser (ECL). The
amplified signal is launched into $45.5\text{\,}\mathrm{k}\mathrm{m}$ of
field-deployed standard single-mode fiber (SSMF) at a fixed launch power. At
the other location in Otemachi, Tokyo, an EDFA amplifies the signal again to
the same launch power and it is transmitted back to Koganei via
$45.5\text{\,}\mathrm{k}\mathrm{m}$ of SSMF. 56% of this fiber is installed in
underground ducts and the remainder on aerial paths and in the surface along
railway tracks.

At the receiver, the signal is amplified, combined with amplified spontaneous
emission (ASE) from a noise-loading stage to vary the OSNR, and filtered using
a $5\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$ bandpass filter (BPF). A variable
optical attenuator (VOA) controls the optical power into the
$6.5\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$ photodiode such that the
electrical output swing fills the $1\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$
$4\text{\,}\mathrm{G}\mathrm{S}\mathrm{/}\mathrm{s}$ 12-bit ADC detection
range. Receiver clock is synchronized to the transmitter and DSP is performed
in real time on the GPU with 5120 processing cores as described in Section 2.
Error counting is performed offline over 98 buffers containing 220 symbols
each.

Several optimizations have been employed to increase OSNR performance.
Firstly, no significant dependence of launch power on OSNR performance was
observed. Therefore, the launch power was fixed. Next, the gap between the
digitally-inserted carrier required for KK detection was optimized. With the
1% roll-off RRC $1\text{\,}\mathrm{G}\mathrm{B}\mathrm{a}\mathrm{u}\mathrm{d}$
signal ending at $0.505\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$ and the
carrier tone at $0.516\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$, a gap of only
$11\text{\,}\mathrm{M}\mathrm{H}\mathrm{z}$ was left. One would expect a
larger gap to be more beneficial since it reduces signal-signal beat
interference (SSBI) which when not entirely removed by the KK algorithm leaves
reconstruction errors. However, the ADC has a limited
$3\text{\,}\mathrm{d}\mathrm{B}$ bandwidth of
$1\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$, thus impairing the signal after
detection but crucially before the KK algorithm, leading to imperfect
reconstruction. It is expected that the penalty from increased imperfect
reconstruction obstructs the use of a larger gap. Finally, the power of the
digitally-inserted carrier tone relative to the signal, the CSPR, is varied
and reported in the next section.

##  4 Results

Figure 3: Q-factor versus OSNR after transmission through
$91\text{\,}\mathrm{k}\mathrm{m}$ of field-deployed SSMF for 4-QAM and 16-QAM
for various CSPRs. Insets show constellations with highest Q-factor without
noise loading with $12\text{\,}\mathrm{d}\mathrm{B}$ CSPR for 4-QAM and
$14\text{\,}\mathrm{d}\mathrm{B}$ for 16-QAM.

Fig. 3 shows the Q-factor versus OSNR for 4/̄QAM and 16/̄QAM for multiple
CSPRs. It is clear that lower CSPR values perform better in the low OSNR
regime and higher CSPRs at higher OSNR. Note that total signal power as
defined in the OSNR includes both the carrier tone and the N/̄QAM signal.
Therefore, if CSPR is increased, signal power decreases, signal-to-noise ratio
(SNR) decreases, and Q-factor decreases. This is especially relevant at low
OSNRs, because optical noise is dominant in this regime. Conversely, if CSPR
is increased, carrier power increases, SSBI decreases, fewer reconstruction
errors occur, and Q-factor increases. This is relevant at higher OSNRs,
because reconstruction errors are dominant in this regime. Reconstruction
errors originate from minimum-phase condition violations and predominantly
distort the outer points of a constellation as can be seen in the insets of
Fig. 3 [15]. The CSPR trade-off between noise and reconstruction errors is
observed for all tested modulations.

4/̄QAM with $6\text{\,}\mathrm{d}\mathrm{B}$ CSPR reaches the 6.7% overhead
HD-FEC Q-factor threshold of $8.35\text{\,}\mathrm{d}\mathrm{B}$ [19] at
$6.5\text{\,}\mathrm{d}\mathrm{B}$ OSNR. For this specific CSPR, the Q-factor
never exceeds $12\text{\,}\mathrm{d}\mathrm{B}$ whilst higher CSPRs have a
lower error floor or Q-factor ceiling. The optimal CSPR depends on the
operating regime of the transmission link, the modulation format, and the FEC
algorithm employed. Q-values above $15\text{\,}\mathrm{d}\mathrm{B}$ are not
displayed in Fig. 3 because too few errors were recorded for statistical
significance. 16/̄QAM reaches the 20% overhead HD-FEC Q-factor threshold of
$6.70\text{\,}\mathrm{d}\mathrm{B}$ [20, 21] at
$14.6\text{\,}\mathrm{d}\mathrm{B}$ OSNR using a CSPR of
$8\text{\,}\mathrm{d}\mathrm{B}$. The 6.7% overhead HD-FEC is reached at an
OSNR of $17.6\text{\,}\mathrm{d}\mathrm{B}$ using
$10\text{\,}\mathrm{d}\mathrm{B}$ CSPR.

OSNR performance for 32/̄QAM and 64/̄QAM are shown in Fig. 4. 32/̄QAM is able
to reach both the 20% and 6.7% overhead FEC limit at
$19.9\text{\,}\mathrm{d}\mathrm{B}24.9\text{\,}\mathrm{d}\mathrm{B}$,
respectively. However, 64/̄QAM is not able to reach the 6.7% overhead FEC
threshold, but reaches the other threshold at
$28.2\text{\,}\mathrm{d}\mathrm{B}$. The successful transmission of 64/̄QAM is
enabled by improving receiver bandwidth, increasing OSNR, and optimizing CSPR.

Fig. 5 depicts the OSNR performance for both conventional and geometrically-
shaped 8/̄QAM. The GS format outperforms its conventional counterpart and
reaches the 6.7% overhead threshold at $12.0\text{\,}\mathrm{d}\mathrm{B}$
versus $13.0\text{\,}\mathrm{d}\mathrm{B}$ for the conventional format.
Similarly, at the 20% threshold, GS-8/̄QAM outperforms 8/̄QAM by
$1.0\text{\,}\mathrm{d}\mathrm{B}$ and reaches the threshold at
$9.4\text{\,}\mathrm{d}\mathrm{B}$ compared to
$10.4\text{\,}\mathrm{d}\mathrm{B}$ for 8/̄QAM.

Figure 4: Q-factor versus OSNR after transmission through
$91\text{\,}\mathrm{k}\mathrm{m}$ of field-deployed SSMF for 32-QAM and 64-QAM
for various CSPRs. Insets show constellations with highest Q-factor without
noise loading with $16\text{\,}\mathrm{d}\mathrm{B}$ CSPR. Figure 5: Q-factor
versus OSNR after transmission through $91\text{\,}\mathrm{k}\mathrm{m}$ of
field-deployed SSMF for 8-QAM and GS-8-QAM for various CSPRs. Insets show
constellations with highest Q-factor without noise loading with
$12\text{\,}\mathrm{d}\mathrm{B}$ CSPR.

Fig. 6(a) shows the Q-factor as a function of OSNR for all evaluated
modulation formats aggregated in one figure. For each OSNR, the highest
measured Q-factor for that modulation format is plotted, effectively tracing a
line along the maximum Q-factor of each modulation format in Figs. 3, 4 and 5
and 128- and GS-128/̄QAM. As a result, CSPR is optimized for each OSNR. Using
this optimization approach, 4-, GS-8-, 8-, 16-, and 32/̄QAM reach the 6.7% HD-
FEC threshold. 64/̄QAM only reaches the 20% HD-FEC threshold, but 128- and
GS-128/̄QAM unfortunately stay below the thresholds.

Fig. 6(b) estimates the net throughput of the transmission system at various
OSNRs. For each of the HD-FEC threshold crossings mentioned above, the net
data rate after FEC decoding at the OSNR of the crossing is plotted. This
figure reveals interesting choices for the system designer. If the system
operates above an OSNR of $28.2\text{\,}\mathrm{d}\mathrm{B}$, 64/̄QAM
combined with a 20% overhead HD-FEC can be employed for a net data rate of
$5\text{\,}\mathrm{G}\mathrm{b}\mathrm{p}\mathrm{s}$. Alternatively, a lower
complexity HD-FEC with an overhead of 6.7% can be paired with 32/̄QAM for a
net data rate of $4.7\text{\,}\mathrm{G}\mathrm{b}\mathrm{p}\mathrm{s}$,
requiring $24.9\text{\,}\mathrm{d}\mathrm{B}$ OSNR. The multi-modulation
format software-defined DSP allows for efficient operation from
$6\text{\,}\mathrm{d}\mathrm{B}$ up to $28\text{\,}\mathrm{d}\mathrm{B}$ OSNR,
flexibly switching modulation format depending on OSNR.

(a) Q-factor versus OSNR for all evaluated modulation formats at optimized
CSPR.

(b) Net throughput as a function of OSNR for the evaluated modulation formats
and HD-FEC thresholds.

Figure 6: Further analysis of all measurements.

##  5 Discussion

Fig. 7 shows the GS formats used in this work compared with their conventional
counterparts. Both GS-8/̄QAM and GS-128/̄QAM are optimized for the AWGN
channel at SNR values of
$14\text{\,}\mathrm{d}\mathrm{B}20\text{\,}\mathrm{d}\mathrm{B}$,
respectively. The optimization uses an iterative approach similar to [18]. The
constellations are initialized using the conventional layout and optimized by
iterating between adding perturbations in the form of Gaussian noise to a
randomly chosen single point and swapping the binary labels of two randomly
chosen constellation points until convergence is reached. After each
iteration, the generalized mutual information (GMI) for the AWGN channel is
evaluated and if gains are found, the modified constellation is taken as the
new baseline. GS-8/̄QAM, see Fig. 7(b), resembles a circular 8/̄QAM with
center constellation point [22], but is different since it is not symmetric.
Symmetries are added to GS-128/̄QAM to aid convergence of the constellation
design. The result of the optimization algorithm is to increase the Euclidean
distance between constellation points that differ more than 1 bit.

GS formats for SNRs were created in steps of $1\text{\,}\mathrm{d}\mathrm{B}$
ranging from $5\text{\,}\mathrm{d}\mathrm{B}14\text{\,}\mathrm{d}\mathrm{B}$
and $17\text{\,}\mathrm{d}\mathrm{B}23\text{\,}\mathrm{d}\mathrm{B}$ for
8/̄QAM and 128/̄QAM, respectively, and were experimentally tested using the
field-deployed link since there is no a priori knowledge of the AWGN channel
that best resembles the transmission scenario. Many of the GS formats tested
on the transmission link perform worse than their conventional counterparts,
but GS-8/̄QAM optimized for $14\text{\,}\mathrm{d}\mathrm{B}$ SNR and
GS-128/̄QAM optimized for $20\text{\,}\mathrm{d}\mathrm{B}$ show significant
experimental gains and are included in this work. The constellation design
technique optimizes for AWGN, which is a substantially different channel than
the one employed in this work. The gain of GS-8/̄QAM with respect to 8/̄QAM in
the AWGN channel is $0.5\text{\,}\mathrm{d}\mathrm{B}$ at both FEC thresholds.
Fig. 8 shows the influence of KK reconstruction errors on OSNR for various
CSPRs. The insets shows that the outer points of a constellation are
predominantly distorted. The employed GS-8/̄QAM is more resilient against
these distortions than 8/̄QAM, enabling operation at lower CSPR. Therefore, it
is expected that more advanced optimization techniques taking into account the
channel including CSPR and KK reconstruction errors will produce better
performing modulation formats. However, determining the best GS modulation
format for the transmission scenario was not the goal of this investigation.
These suboptimal constellations are included as a proof-of-concept for using
GS formats in the flexible multi-modulation format receiver, to demonstrate
that the receiver supports non-symmetrical modulation formats, and to
demonstrate the use of GS/̄QAM in KK coherent detection.

(a) Conventional 8-QAM

(b) GS-8-QAM

(c) Conventional 128-QAM

(d) GS-128-QAM

Figure 7: Comparison between conventional and geometrically-shaped
constellations. Drawn using the same scale with normalized power. Figure 8:
Q-factor versus OSNR after transmission through
$91\text{\,}\mathrm{k}\mathrm{m}$ of field-deployed SSMF for 8-QAM and
GS-8-QAM for various CSPRs. Values indicate OSNR gain of GS-8-QAM with respect
to 8-QAM at the specified FEC threshold calculated using a polynomial fit.
Insets show constellations with highest Q-factor at
$34\text{\,}\mathrm{d}\mathrm{B}$ OSNR.

In [11], we note that the error floor or Q-factor ceiling of high-cardinality
formats is most likely due to low-pass filtering at the receiver causing KK
reconstruction errors. Here, we use a photodiode with higher bandwidth,
enabling successful processing of 64/̄QAM signals reaching the 20% overhead
HD-FEC Q-factor threshold. Further gains could be made by employing a higher
bandwidth ADC as well. Note that the KK reconstruction errors are caused by
filtering effects between direct detection at the photodiode and conversion in
the ADC [23]. Alternatively, one could implement a second static equalizer
before the KK algorithm to counter these filtering effects [24]. The current
implementation almost fully utilizes the GPU processing capabilities, but
further optimization of the implementation can free up resources for such an
additional filtering step.

The main factor limiting baud and data rates in this work is the ADC. The off-
the-shelf commercial 12-bit
$4\text{\,}\mathrm{G}\mathrm{S}\mathrm{/}\mathrm{s}$ ADC has a
$3\text{\,}\mathrm{d}\mathrm{B}$ bandwidth of
$1\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$, limiting the baud rate to
$1\text{\,}\mathrm{G}\mathrm{B}\mathrm{a}\mathrm{u}\mathrm{d}$. The ADC uses
an eight-lane PCIe Gen 3 interface to communicate with the GPU, which limits
the sampling rate of the ADC. Future ADCs, employing PCIe Gen 4 or additional
lanes, are expected to offer greater sampling rates and bandwidth. Proprietary
interfaces such as NVIDIA NVLink (at the time of writing is not available in
off-the-shelf ADCs) can support an order of magnitude higher throughput from
ADC to GPU and may enable greater increases in sampling rates.

##  6 Conclusion

A commercial off-the-shelf GPU is used for real-time digital signal processing
of minimum-phase 4-, 8-, 16-, 32-, 64-, and 128/̄QAM as well as geometrically-
shaped 8/̄QAM and 128/̄QAM signals detected with a KK coherent receiver [15].
This real-time, flexible, multi-modulation format receiver is experimentally
validated using a field-deployed link between two Tokyo locations. A net data
rate of $5\text{\,}\mathrm{G}\mathrm{b}\mathrm{p}\mathrm{s}$ is demonstrated
using $1\text{\,}\mathrm{G}\mathrm{B}\mathrm{a}\mathrm{u}\mathrm{d}$ 64/̄QAM.
This shows the potential of GPUs for software-defined signal processing
functionality in optical communication systems.

Funding This work was partly supported by the Dutch NWO Gravitation Program on
Research Center for Integrated Nanophotonics under Grant GA 024.002.033. The
work of A. Alvarado and S. Goossens has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No. 757791).

Data availability Data underlying the results presented in this paper are not
publicly available at this time but may be obtained from the authors upon
reasonable request.

Disclosures The authors declare no conflicts of interest

## References

  * [1] S. Beppu et al.  “Real-time strongly-coupled 4-core fiber transmission”  In _Optical Fiber Communication Conference (OFC) 2020_ Optical Society of America, 2020, pp. Th3H.2  DOI: 10.1364/OFC.2020.Th3H.2
  * [2] Shohei Beppu et al.  “Weakly coupled 10-mode-division multiplexed transmission over 48-km few-mode fibers with real-time coherent MIMO receivers”  In _Opt. Express_ 28.13 OSA, 2020, pp. 19655–19668  DOI: 10.1364/OE.395415
  * [3] S. Randel et al.  “First real-time coherent MIMO-DSP for six coupled mode transmission”  In _2015 IEEE Photonics Conference (IPC)_ , 2015  DOI: 10.1109/IPCon.2015.7323761
  * [4] R. Li et al.  “A multi-standard efficient column-layered LDPC decoder for Software Defined Radio on GPUs”  In _2013 IEEE 14th Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_ , 2013, pp. 724–728  DOI: 10.1109/SPAWC.2013.6612145
  * [5] T. Suzuki et al.  “Demonstration of 10-Gbps Real-Time Reed–Solomon Decoding Using GPU Direct Transfer and Kernel Scheduling for Flexible Access Systems”  In _Journal of Lightwave Technology_ 36.10, 2018, pp. 1875–1881  DOI: 10.1109/JLT.2018.2793938
  * [6] T. Suzuki et al.  “10-Gb/s Software Implementation of Burst-Frame Synchronization Using Array-Access Bitshift and Dual-Stage Detection for Flexible Access Systems”  In _Journal of Lightwave Technology_ 36.23, 2018, pp. 5656–5662  DOI: 10.1109/JLT.2018.2870912
  * [7] Takahiro Suzuki, Sang Yuep Kim, Jun Ichi Kani and Jun Terada  “Software Implementation of 10G-EPON Upstream Physical-Layer Processing for Flexible Access Systems”  In _J. of Lightw. Technol._ 37.6, 2019, pp. 1631–1637  DOI: 10.1109/ACCESS.2019.2904083
  * [8] T. Suzuki, S. Kim, J. Kani and J. Terada  “Demonstration of Fully Softwarized 10G-EPON PHY Processing on a General-Purpose Server for Flexible Access Systems”  In _Journal of Lightwave Technology_ 38.4, 2020, pp. 777–783  DOI: 10.1109/JLT.2019.2948333
  * [9] T Suzuki, S Kim, J Kani and J Terada  “Real-Time Implementation of Coherent Receiver DSP Adopting Stream Split Assignment on GPU for Flexible Optical Access Systems”  In _J. of Lightw. Technol._ 38.3, 2020, pp. 668–675  DOI: 10.1109/JLT.2019.2950155
  * [10] Sjoerd P Heide et al.  “Real-time, Software-Defined, GPU-Based Receiver Field Trial”  In _ECOC We1E5_ , 2020  DOI: 10.1109/ECOC48923.2020.9333244
  * [11] Sjoerd P Heide et al.  “Field Trial of a Flexible Real-Time Software-Defined GPU-Based Optical Receiver”  In _J. Lightwave Technol._ 39.8 OSA, 2021, pp. 2358–2367  DOI: 10.1109/JLT.2021.3050304
  * [12] S P Heide et al.  “10,000 km Straight-line Transmission using a Real-time Software-defined GPU-Based Receiver”  In _2021 Optical Fiber Communications Conference and Exhibition (OFC)_ , 2021, pp. 1–3  DOI: 10.1364/OFC.2021.W1I.3
  * [13] P.. Winzer and D.. Neilson  “From Scaling Disparities to Integrated Parallelism: A Decathlon for a Decade”  In _J. of Lightw. Technol._ 35.5, 2017, pp. 1099–1115  DOI: 10.1109/JLT.2017.2662082
  * [14] Yifan Sun, Nicolas Bohm Agostini, Shi Dong and David Kaeli  “Summarizing CPU and GPU Design Trends with Product Data”  In _arXiv:1911.11313 [cs]_ , 2019
  * [15] Antonio Mecozzi, Cristian Antonelli and Mark Shtaif  “Kramers Kronig coherent receiver”  In _Optica_ 3.11, 2016, pp. 1220  DOI: 10.1364/OPTICA.3.001220
  * [16] E.. da Silva and D. Zibar  “Widely Linear Equalization for IQ Imbalance and Skew Compensation in Optical Coherent Receivers”  In _Journal of Lightwave Technology_ 34.15, 2016, pp. 3577–3586  DOI: 10.1109/JLT.2016.2577716
  * [17] Ruben S. Luís et al.  “Simple method for optimizing the DC bias of Kramers-Kronig receivers based on AC-coupled photodetectors”  In _Opt. Express_ 28.3 OSA, 2020, pp. 4067–4075  DOI: 10.1364/OE.383369
  * [18] Bin Chen, Chigo Okonkwo, Domaniç Lavery and Alex Alvarado  “Geometrically-shaped 64-point Constellations via Achievable Information Rates”  In _2018 20th International Conference on Transparent Optical Networks (ICTON)_ , 2018, pp. 1–4  DOI: 10.1109/ICTON.2018.8473932
  * [19] Y Miyata et al.  “UEP-BCH product code based hard-decision FEC for 100 Gb/s optical transport networks”  In _OFC/NFOEC_ , 2012, pp. 1–3  DOI: 10.1364/NFOEC.2012.JW2A.7
  * [20] Michael Scholten, Tim Coe, John Dillard and Frank Chang  “Enhanced FEC for 40G/100G”  In _2009 European Conference on Optical Communication (ECOC)_ , 2009, pp. 1–12
  * [21] Alexandre Amat and Laurent Schmalen  “Forward Error Correction for Optical Transponders” Table 7.5  In _Springer Handbook of Optical Networks_ Cham: Springer International Publishing, 2020, pp. 177–257  DOI: 10.1007/978-3-030-16250-4_7
  * [22] Markus Nölle et al.  “Performance Comparison of Different 8QAM Constellations for the Use in Flexible Optical Networks”  In _Optical Fiber Communication Conference_ Optical Society of America, 2014, pp. W3B.2  DOI: 10.1364/OFC.2014.W3B.2
  * [23] Xi Chen et al.  “Kramers–Kronig Receivers for 100-km Datacenter Interconnects”  In _Journal of Lightwave Technology_ 36.1, 2018, pp. 79–89  DOI: 10.1109/JLT.2018.2793460
  * [24] X. Chen et al.  “Impact of O/E Front-End Frequency Response on Kramers-Kronig Receivers and its Compensation”  In _2018 European Conference on Optical Communication (ECOC)_ , 2018, pp. 1–3  DOI: 10.1109/ECOC.2018.8535239


#  A Secure Web-Based File Exchange Server
Software Requirements Specification Document

CIISE Security Investigation Initiative

Represented by:

Serguei A. Mokhov
Marc-André Laverdière
Ali Benssam
Djamel Benredjem
<EMAIL_ADDRESS>

Montréal, Québec, Canada

(December 14, 2005)

###### Contents

  1. 1 Introduction
    1. 1.1 Purpose
    2. 1.2 Scope
    3. 1.3 Definitions and Acronyms
  2. 2 Overall Description
    1. 2.1 Product Perspective
      1. 2.1.1 System interfaces
      2. 2.1.2 User Interfaces
      3. 2.1.3 Hardware Interfaces
      4. 2.1.4 Software Interfaces
    2. 2.2 Product Functions
  3. 3 Specific Requirements
    1. 3.1 Functional Requirements
      1. 3.1.1 Domain Model
      2. 3.1.2 Use Case Model
    2. 3.2 Software System Attributes
      1. 3.2.1 Security
      2. 3.2.2 Reliability
      3. 3.2.3 Availability
      4. 3.2.4 Maintainability
      5. 3.2.5 Portability
    3. 3.3 Logical Database Requirements

###### List of Figures

  1. 3.1  SFS system packages
  2. 3.2  Normal user use-case
  3. 3.3  Administrator use-case

##  Chapter 1 Introduction

Building Trust is the basis of all communication, especially electronic one,
as the identity of the other entity remains concealed. To address problems of
trust, authentication and security over the network, electronic communications
and transactions need a framework that provides security policies, encryption
mechanisms and procedures to generate manage and store keys and certificates.

This software requirements specification (SRS) document demonstrates all the
concerns and specifications of the secure web-based file exchange server
(SFS). SFS is a security architecture that we propose here to provide an
increased level of confidence for exchanging information over increasingly
insecure networks, such as the Internet. SFS is expected to offer users a
secure and trustworthy electronic transaction.

###  1.1 Purpose

The intent of implementation and deployment of SFS facilities is to meet its
basic purpose of providing Trust. Presently, SFS needs to perform the
following security functions:

  * •

_Mutual authentication of entities taking part in the communication:_ Only
authenticated principals can access files to which they have privileges.

  * •

_Ensure data integrity:_ By issuing digital certificates which guarantee the
integrity of the public key. Only the public key for a certificate that has
been authenticated by a certifying authority should work with the private key
possessed by an entity. This eliminates impersonation and key modification.

  * •

_Enforce security:_ Communications are more secure by using SSL to exchange
information over the network.

###  1.2 Scope

SFS is implemented to secure sensitive resources of the organization and avoid
security breaches. The SFS allows trustworthy communication between the
different principals. These principals must be authenticated and the access to
the resources (files) should be secured and regulated. Any principal wants to
access to the database needs to perform the following steps:

  * •

_Mutual authentication:_ The Web Server via which the database is contacted
authenticates the principal using its digital certificate and username to
ensure that it is who it claims to be . The principal authenticates also the
server using its certificate information.

  * •

_Principal validation:_ To validate the principal, the server looks up
information from an LDAP server which contains the hierarchy of all principals
along with certificates and credentials.

  * •

_Enforcing security:_ The security is enforced by using SSL to communicate
between the Web Server and the LDAP server, the Web Server and the database
and between the principal and Web Server.

  * •

Principal authentication: Upon successful authentication, the Web Server will
allow the principal to perform actions on the database according to a pre
specified Access Control List.

  * •

Kinds of principals: There are two kinds of principals, administrators and
clients: _Clients_ have the ability to upload, download, delete and view
files. _Administrators_ have the ability to: Upload, download, delete and view
files; Add, delete and modify users; Generate user’s certificate, with all
required information; Generate ACL to users; Manage groups, Perform
maintenance.

Finally, this infrastructure allows additional features such as the ability to
assign users to groups in order to provide users with the access to files
prepared by other group members.

###  1.3 Definitions and Acronyms

  * •

PKI: Public Key Infrastructure

  * •

OpenLDAP : is a free, open source implementation of the Lightweight Directory
Access Protocol (LDAP).

  * •

OpenSSL: an open source SSL library and certificate authority

  * •

Apache Tomcat: A Java based Web Application container that was created to run
Servlets and JavaServer Pages (JSP) in Web applications

  * •

PostgreSQL: An open source object-relational database server

  * •

SSL: Secure Socket Layer

  * •

JSP: Java Server Pages

  * •

JCE: Java Cryptography Extension

  * •

API: Application Programming Interface

  * •

JDBC: Java Database Connectivity

  * •

JNDI: Java Naming and Directory Interface

  * •

LDAP: Lightweight Directory Access Protocol

  * •

X.509: A standard for defining a Digital Certificate used by SSL

  * •

SRS: Specification Request Document

  * •

SDD: Specification Design Document

  * •

DER: Distinguished Encoding Rules

  * •

Mutual Authentication: The process of two principals proving their identities
to each other

  * •

SFS: Secure File Exchange Server, this product

  * •

COTS: Commercial Off The Shelf, common commercially or freely available
software

The coming sections of the SRS are a description of all the requirements to be
implemented in SFS system. The requirements specifications are organized in
two major sections: Overall Description and Specific Requirements.

##  Chapter 2 Overall Description

In this chapter we provide an overall insight of the general factors that
affect the SFS system and its requirements.

###  2.1 Product Perspective

The SFS system is intended to operate in a distributed environment: clients
machines, application server, database server, and LDAP server. SFS is
accessed via secure connections we intend to provide in this work. The
system’s user can be either a normal user or an administrator. A normal user
has the ability to upload, download, delete and view files. An administrator
is able to: Upload, download, delete and view files; add, delete and modify
users; generate user certificates along with all required information;
generate an ACL to each and every user; manage groups; perform various
maintenance actions such as: check log files, delete files, etc.

####  2.1.1 System interfaces

The various parts of the SFS application will be installed on client machines
and different servers. The client that uses the system has to have the
certificate installed on his machine to provide client authentication. The
servers are responsible of one of the following functions: provide the
database, provide the LDAP server functionalities, and provide the application
server for different clients.

####  2.1.2 User Interfaces

The user interfaces consist of web-based graphical components that allow the
user to interact with the SFS system. The user will use a web browser to send
and receive data. If the user is the administrator, s/he will have more
options to add, delete, etc. users, generate users certificates, generate ACL
for each user, etc.

####  2.1.3 Hardware Interfaces

The hardware interfaces will be achieved through the abstraction layer of the
Java Virtual Machine (JVM). The keyboard and the mouse are examples of such
hardware interfaces that allow users to interact with the SFS system.

####  2.1.4 Software Interfaces

Among the most important software interfaces used in this project, we have:

  * •

The SFS system is OS-independent due to the cross platform Java
implementation. It will support web browsers such as Internet Explorer,
Mozilla Fireworks, etc.

  * •

Access to databases will be provided by JDBC 3 on both Windows and Linux
environment.

  * •

JXplorer? will be used to provide a graphical access to LDAP server.

  * •

OpenLDAP? is used to host users’ certificates.

  * •

Java 1.5 JDK from Sun.

  * •

JRE 1.5 from Sun.

  * •

Servlets for client and administrator interfaces.

  * •

Apache Tomcat5 server as the web server used in this project.

  * •

PostegreSQL? is the database used to host users information, files, etc.

  * •

OpenSSL toolkit to generate the certificates for users.

Hereafter, we provide the software and documentation’s locations related to
these interfaces:

  * •

OpenLDAP? software and documentation found at: _http://www.openldap.org/_

  * •

PostgreSQL database and documentation found at: _http://www.postgresql.org/_

  * •

Java development kit 1.5 available at: _http://java.sun.com/j2se/_

  * •

JSP documentation found at: _http://java.sun.com/products/jsp/_

  * •

OpenSSL Toolkit found at: _http://www.openssl.org/_

  * •

Apache Tomcat 5.0 web server found at: _http://tomcat.apache.org/_

###  2.2 Product Functions

The SFS system will implement the following functionalities:

  * •

_Server authentication:_ This use case allow the user to authenticate the web
server is connecting to.

  * •

_Client authentication:_ This is use case allow the server to authenticate the
user he is trying to connect to.

  * •

_Secure communication:_ Between users over the network.

  * •

_Files handling:_ Such as downloading, uploading, and deletion files.

  * •

Users management: Administrator has the ability to add and delete users, add
and delete groups, and assign users to groups.

##  Chapter 3 Specific Requirements

In this section we describe the software requirements to design the SFS
system. The system design should satisfy the following requirements.

###  3.1 Functional Requirements

Hereafter, we express the expectations in terms of system functions and
constraints. This includes the domain model and the most important use case
diagrams of the SFS system.

####  3.1.1 Domain Model

The SFS system domain model consists of many packages.

  * •

_Client authentication module:_ used to provide users the ability to
authenticate the server.

  * •

_Server authentication module:_ used to provide the server the ability to
authenticate the clients.

  * •

_LDAP connection module:_ used to provide connection to the LDAP server in
order to check clients’ credentials.

  * •

_Database connection module:_ used to provide users the ability to connect to
the database server in a secure mode.

Figure 3.1:  SFS system packages

####  3.1.2 Use Case Model

The SFS system consists of a set of use cases manageable by the users of the
application. There are two types of users of the system: normal users and
administrator. Normal can view, delete, download, and upload files. For the
administrator, s/he can: add, delete, etc. users; generate users’
certificates; generate ACL for each user, etc.

The diagram in Figure 3.2 shows the capabilities of a normal user.

Figure 3.2:  Normal user use-case

The diagram in Figure 3.3 shows the capabilities of the administrator user.

Figure 3.3:  Administrator use-case

###  3.2 Software System Attributes

There are a number of software attributes that can serve as requirements. It
is important that required attributes by specified so that their achievement
can be objectively verified. The following items are some of the most
important ones: security, reliability, availability, maintainability, and
portability.

####  3.2.1 Security

Security is the most important attribute of the SFS design and implementation.
The mutual authentication between the server and clients is crucial for the
system use. The system should be able to authenticate users and differentiate
among them, either are normal users or administrator. In order to achieve the
security feature expected from the SFS system, the following tasks have to be
realized:

  * •

Utilize cryptographic techniques

  * •

Check users’ credentials before using the system and accessing the database

  * •

Provide secure communications between different parts of the system

####  3.2.2 Reliability

The basis for the definition of reliability is the probability that a system
will fail during a given period. The reliability of the whole system depends
on the reliability of its components and on the reliability of the
communication between its components. The SFS system is based mainly on some
standard components such as OpenLDAP, OpenSSL, JDBC, PostgreSQL, etc. The
reliability of these service components is already proved. This fact improves
the reliability of the system and restricts the proof work on assuring only of
the reliability of the added components and the communications between the
different components. In addition, the system must ensure the security of the
communications which is the most important issue of the SFS system.

####  3.2.3 Availability

The SFS system must be able to work continuously in order to provide users
with an access to different server’s parts of the system. However, since this
system depends on distributed information systems and databases, many
constraints should be taken into account such as:

  * •

The connection to the web server that provides access to the system

  * •

The interconnection between different parts of the system should always be
available; otherwise, the users cannot complete their tasks using the system.

  * •

The database should be available in the database server side

  * •

The LDAP server should be always available in order to check users’
credentials

  * •

The web server should be also available in order to allow users connecting to
the system.

####  3.2.4 Maintainability

Maintainability is defined as the capacity to undergo repairs and
modifications. The main goal in designing SFS system is to keep it easy to be
modified and extended.

####  3.2.5 Portability

The portability is one of the main specifications of Java. Since SFS is
implemented using the Java programming language, the portability is
automatically satisfied and the system is able to run on any machine or
operating system which supports the execution of a Java virtual machine.

###  3.3 Logical Database Requirements

The rationale behind SFS system is to provide secure connections for users
accessing databases to view, delete, upload, and download files through a web
server and LDAP server. After analyzing the requirements we propose using a
relational database model to meet our requirements. This database is required
to store information about users, files, groups of users, etc. The database is
expected to work on 24 hours and 7 days in order to provide nonstop access to
the users. Therefore, backup of the database should be taken periodically
(daily or weekly. The relational database itself guarantees the flexibility,
simplicity and elimination of redundancy once designed carefully. The entity
relationship model will be elaborated in detail in the database design of the
design part, in this document.

## Bibliography

  * [Apa11] Apache Foundation.  Apache Jakarta Tomcat.  [online], 1999–2011.  http://jakarta.apache.org/tomcat/index.html.
  * [CBH03] Suranjan Choudhury, Katrik Bhatnagar, and Wisam Haque.  Public Key Infrastructure, Implementation and Design.  NIIT Books, 2003.
  * [Deb05] Mourad Debbabi.  INSE 6120: Cryptographic protocols and network security, lecture notes.  Concordia Institute for Information Systems Engineering, Concordia University, Montreal, Canada, 2005.  http://users.encs.concordia.ca/~debbabi/inse6120.html.
  * [E+11] Eclipse contributors et al.  Eclipse Platform.  eclipse.org, 2000–2011.  http://www.eclipse.org, last viewed February 2010.
  * [GB11] Erich Gamma and Kent Beck.  JUnit.  [online], Object Mentor, Inc., 2001–2011.  http://junit.org/.
  * [Lar06] Craig Larman.  Applying UML and Patterns: An Introduction to Object-Oriented Analysis and Design and Iterative Development.  Pearson Education, third edition, April 2006.  ISBN: 0131489062.
  * [Leu05] Leuvens Universitair.  A few frequently used SSL commands.  [online], Leuvens Universitair Dienstencentrum voor Informatica en Telematica, 2005.  http://shib.kuleuven.be/docs/ssl_commands.shtml.
  * [Ope05a] OpenLDAP Community.  OpenLDAP: The open source for LDAP software and information.  [online], 2005.  www.openldap.org.
  * [Ope05b] OpenSSL Community.  OpenSSL: The open source toolkit for SSL/TLS.  [online], 2005.  http://www.openssl.org.
  * [O’R05a] O’Reilly.  Home of com.oreilly.servlet.  [online], 2005.  http://servlets.com/cos.
  * [O’R05b] O’Reilly.  JXplorer – a Java LDAP browser.  [online], 2005.  http://sourceforge.net/projects/jxplorer/.
  * [Sun05a] Sun Microsystems, Inc.  Java servlet technology.  [online], 1994–2005.  http://java.sun.com/products/servlets.
  * [Sun05b] Sun Microsystems, Inc.  JavaServer pages technology.  [online], 2001–2005.  http://java.sun.com/products/jsp/.
  * [The11] The PostgreSQL Global Development Group.  PostgreSQL – the world’s most advanced open-source database.  [ditigal], 1996–2011.  http://www.postgresql.org/, last viewed January 2010.

## Index

  * Introduction Chapter 1


# HopPG: Self-Iterative Program Generation for Multi-Hop Question Answering
over Heterogeneous Knowledge

Yingyao Wang1, Yongwei Zhou111footnotemark: 1, Chaoqun Duan2, Junwei Bao2,
Tiejun Zhao1
1Harbin Institute of Technology 2JD AI Research
{yywang<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>The
first two authors contribute equally to this work.

###### Abstract

The semantic parsing-based method is an important research branch for
knowledge-based question answering. It usually generates executable programs
lean upon the question and then conduct them to reason answers over a
knowledge base. Benefit from this inherent mechanism, it has advantages in the
performance and the interpretability. However, traditional semantic parsing
methods usually generate a complete program before executing it, which
struggles with multi-hop question answering over heterogeneous knowledge.
Firstly, a complete multi-hop program relies on multiple heterogeneous
supporting facts, and it is difficult for models to receive these facts
simultaneously. Secondly, these methods ignore the interaction information
between the previous-hop execution result and the current-hop program
generation. To alleviate these challenges, we propose a self-iterative
framework for multi-hop program generation (HopPG) over heterogeneous
knowledge, which leverages the previous-hop execution results to retrieve
supporting facts and generate subsequent programs iteratively. We evaluate our
model on MMQA-T2111A subset of MMQA, we detailed introduce the MMQA-T2 dataset
in Section 1 and Section 4.1.. The experimental results show that HopPG
outperforms existing semantic-parsing-based baselines, especially on the
multi-hop questions.

##  1 Introduction

Question answering is a fundamental task and plays a crucial role in the field
of natural language processing Cui et al. (2020); Kwiatkowski et al. (2019);
Liu et al. (2020); Choi et al. (2018); Fan et al. (2019). In recent years,
question-answering tasks based on heterogeneous knowledge (HQA) have
increasingly gained the attention of researchers Chen et al. (2020b, a); Zhu
et al. (2021); Talmor et al. (2021); Chen et al. (2021). These tasks require
models to perform multi-hop reasoning on different structured knowledge, i.e.,
tables and texts. One category of the existing HQA method performs implicit
answer reasoning, which takes the question and knowledge as input and performs
reasoning in the semantic space, and then directly outputs the answer Pan et
al. (2020); Sun et al. (2021); Wang et al. (2022); Eisenschlos et al. (2021);
Kumar et al. (2021). Although this approach has proven effective in HQA tasks,
it lacks interpretability, scalability, and symbolic reasoning abilities. In
contrast, the semantic parsing-based (SP-based) approach explicitly derives
answers by generating and executable programs, remedying the above-mentioned
deficiencies and enabling researchers to monitor and improve each step of the
derivation process.

SP-based methods have been widely used in question-answering tasks on
homogeneous knowledge sources, such as tables, knowledge graphs, and texts Yih
et al. (2014); Bao et al. (2014, 2016); Abdelaziz et al. (2021); Zhou et al.
(2022a). Nevertheless, the SP-based question-answering methods over
heterogeneous knowledge still require further exploration. Recently, Zhou et
al. (2022b) introduced UniRPG, a SP-based model designed for HQA. They defined
a set of general atomic and higher-order operations for discrete reasoning
over heterogeneous knowledge resources. During the program generation process,
UniRPG takes questions and supporting facts as input pairs of BART Lewis et
al. (2020) to generate a complete program in a single step.

Although UniRPG has the ability to generate programs with tables and passages
as supporting facts, it still struggles with multi-hop question answering for
the following two reasons. First, generating a complete multi-hop program
usually depends on multiple heterogeneous supporting facts, making it
challenging for the model to receive and understand all the facts
simultaneously due to the length limitation. On the other hand, intuitively,
the reasoning results from the current hop are useful for selecting supporting
facts and program generation in the next step. However, generating a complete
program sequence before executing ignores the interaction between the
reasoning results of the current hop and the subsequent program generation. To
tackle these issues, we introduce HopPG, an iterative program generation
framework designed explicitly for multi-hop answer reasoning based on
heterogeneous knowledge. HopPG leverages the execution results of the previous
program to select supporting facts and generate subsequent programs
iteratively. In comparison to UniRPG, HopPG reduces the knowledge complexity
used in each program generation step and incorporates information from the
previous steps, enhancing the model’s capability for multi-hop reasoning.

In this paper, we utilize a subset of the MMQA dataset Talmor et al. (2021)
for evaluating the effectiveness of HopPG. Specifically, we only focus on
questions based on tables and texts, which we refer to as MMQA-T2, excluding
those requiring images as knowledge. It possesses the following notable
characteristics: 1) questions are based on heterogeneous knowledge, 2)
questions require multi-hop reasoning, and 3) MMQA-T2 provides detailed
annotations of the supporting facts and intermediate results for each hop,
allowing us to construct more accurate pseudo programs. The experimental
results show that HopPG outperforms existing SP-based baselines, especially on
the multi-hop questions.

Our contributions are summarized as follows:

  * •

We propose HopPG, a self-iterative program generation framework for multi-hop
question answering over heterogeneous knowledge. The framework successfully
addresses the limitations of existing SP-based models.

  * •

We construct the MMQA-T2 dataset based on MMQA, which only contains multi-hop
questions over tabular and textual knowledge. Moreover, we construct pseudo-
multi-hop programs for each question in MMQA-T2 to train the program generator
with weak supervision.

  * •

We conduct extensive experiments and ablation studies on the MMQA-T2 dataset.
The experimental results show that HopPG outperforms the existing SP-based QA
model, especially on the multi-hop questions.

##  2 Related Work

###  2.1 Question Answering over Heterogeneous Knowledge

Previous works have attempted to leverage knowledge with various background
knowledge for question-answering, e.g., knowledge graphs and texts Sun et al.
(2019); Han et al. (2020). However, these researches are limited to using one
type of knowledge as auxiliary information during answer reasoning and have
not fully explored multi-hop reasoning across heterogeneous knowledge (HQA).
To fill this gap, Chen et al. (2020b) first propose the HybridQA dataset,
which provides a WiKiTable accompanied by hyperlinked Wikipedia passages as
evidence for each question. Based on HybridQA, Wenhu Chen (2021) proposed the
OTT-QA dataset, requiring the system to retrieve relevant tables and texts for
their given question. Additionally, Zhu et al. (2021) and Chen et al. (2021)
introduced TAT-QA and FinQA, both requiring numerical reasoning over
heterogeneous data.

###  2.2 Semantic Parsing-based Methods

The semantic parsing-based methods reason answers by translating questions
into executable programs such as SPARQL Xiong et al. (2022) and SQLHui et al.
(2022). Previous semantic-parsing-based question-answering methods always
research over homogeneous knowledge resources, i.e., texts Zhou et al.
(2022a), tables Liu et al. (2022) and knowledge graphs Yih et al. (2016). Zhou
et al. (2022b) proposed UniRPG, which first applies the semantic parsing-based
method on question answering over heterogeneous knowledge including tables and
texts. Based on their work, we propose HopPG in this paper to address the
limitations of UniRPG in generating multi-hop programs based on heterogeneous
knowledge.

Figure 1: The framework of HopPG. This figure gives a 2-hop question as the
example.

##  3 Methodology

###  3.1 Task Definition

Multi-hop question answering over heterogeneous knowledge, i.e., tables and
texts, aims to retrieve the supporting facts from the given knowledge and
derive the answer to the question. Given a $H$-hop question $\mathcal{Q}$ and
$K$ fact candidates $\mathcal{T}=\\{t^{1},...t^{K}\\}$, the model requires
deriving the final answer $a^{H}$ from $\mathcal{T}$. Apart from $a^{H}$, we
use $\\{a^{1},...,a^{H-1}\\}$ to represent the intermediate reasoning results
in each hop. Each $a^{h}$, where $h\leq H$, can be a table cell, a text span,
or a math calculation result. The task is formalized as follows:

$\displaystyle a^{H}=\arg\max P(a^{H}|\mathcal{Q},\mathcal{T};\theta).$ (1)

In this work, $\mathcal{T}$ contains a table and a set of texts. We assume
that $t^{1}$ represents the table and the others $\\{t^{2},...,t^{K}\\}$ are
the $K$-$1$ texts. Specifically, the table $t^{1}$ consists of $m\times n$
cells $\\{c_{ij}\\}$, where $m$ and $n$ are the numbers of rows and columns.

Reasoning Type | Multi-hop Program Templates
---|---
HOP-1 | HOP-2
Span Extraction |  $\mathtt{CELL}$ $(s,e)$ |
$\mathtt{CELL\\_VALUE}$ $(s,e)$ |
$\mathtt{SPAN}$ $(s,e)$ |
$\mathtt{SPAN\\_VALUE}$ $(s,e)$ |
$\mathtt{MULTISPAN(CELL_{1}/SPAN_{1},...,CELL_{m}/SPAN_{m})}$ |
YesNo |  $\mathtt{YESNO}$ $(s,e)$ |
Compare | $\mathtt{ARGMAX(KV_{1},KV_{2})}$ |
$\mathtt{ARGMIN(KV_{1},KV_{2})}$ |
Calculation | $\mathtt{SUM(CV_{1},...,CV_{m})}$ |
$\mathtt{AVG(CV_{1},...,CV_{m})}$ |
$\mathtt{COUNT(CV_{1},...,CV_{m})}$ |
Compose + Span Extraction | $\mathtt{COMPOSE(CELL/SPAN)}$ | $\mathtt{CELL/SPAN/MULTISPAN}$
Compose + YesNo | $\mathtt{COMPOSE(CELL/SPAN)}$ | $\mathtt{YESNO}$
Intersect | $\mathtt{INTERSECT(MULTISPAN)}$ | $\mathtt{MULTISPAN}$
Table 1: The defined multi-hop program templates for MMQA-T2.

###  3.2 Definition of Multi-hop Program

####  3.2.1 Operations

UniRPG Zhou et al. (2022b) defined 15 operations, containing 4 atomic
operations and 11 high-order operations. This work inherits a subset of their
fundamental operations including ${\mathtt{CELL}}$, ${\mathtt{SPAN}}$,
${\mathtt{CELL\\_VALUE}}$, ${\mathtt{SPAN\\_VALUE}}$, ${\mathtt{KV}}$,
${\mathtt{MULTISPAN}}$, ${\mathtt{COUNT}}$, ${\mathtt{SUM}}$,
${\mathtt{AVG}}$, ${\mathtt{ARGMAX}}$, and ${\mathtt{ARGMIN}}$. Additionally,
we extend an atomic operation and two high-order operations to enable the
programs to solve multi-hop questions and more reasoning types. The extended
operations are listed as follows:

  * •

${\mathtt{YESNO}}$: This is an atomic operation designed for "yes or no"
reasoning. HopPG converts this reasoning type as a test span extraction
problem. Specifically, we connect two words, "yes" and "no", at the beginning
of the input sequence of the generator. The arguments of ${\mathtt{YESNO}}$
are the same as the other atomic operations, which are $(s,e)$. During
execution, ${\mathtt{YESNO}}$ checks the extracted span, if its content is
"no", ${\mathtt{YESNO}}$ returns "no" as the answer. For all other cases, the
operation returns "yes".

  * •

${\mathtt{COMPOSE}}$: This operation means the current hop is an intermediate
hop, and the answering reasoning requires iteration. The argument of the
${\mathtt{COMPOSE}}$ is one of the atomic operations, ${\mathtt{CELL}}$ or
${\mathtt{SPAN}}$, and ${\mathtt{COMPOSE}}$ directly returns the result of the
atomic operation as the current-hop result.

  * •

${\mathtt{INTERSECT}}$: This operation also means the current hop is an
intermediate hop. Its argument is a high-order operation
${\mathtt{MULTISPAN}}$, and ${\mathtt{INTERSECT}}$ directly returns the
results of ${\mathtt{MULTISPAN}}$, a set of table cells or text spans.

####  3.2.2 Program Templates

We define multi-hop program templates for questions of different reasoning
types. These templates are used to construct pseudo programs for weakly
supervised training and to constrain program generation. We decompose the
multi-hop reasoning into multiple single-hop programs. In this work, we set
the maximum hop count $H$=2. The defined templates are listed in Table 1.
Specifically, for questions of "compose" reasoning types, HopPG directly
outputs the execution results of the 2-hop program as the final answer. In
contrast, when tackling "intersect" questions, HopPG compares the results from
the two hops and outputs the overlap cells or spans as the final answers. We
execute the pseudo programs constructed using our templates and evaluate the
question-answering performance on the development set of MMQA-T2, the EM and
F1 scores are 91.27% and 93.89%, respectively.

###  3.3 Framework of HopPG

We first decompose H-hop reasoning into multiple single hops, and define the
corresponding programs as $\mathcal{P}$=$\\{p^{1},...,p^{H}\\}$. Based on our
program templates, HopPG generates the program $p^{h}$ hop by hop in an
iterative way.

As Figure 1 shows, the framework of our HopPG mainly contains three modules:
fact retriever, program generator, program executor, and a iteration detection
process. During $h$-hop reasoning, the fact retriever first selects a
supporting fact $t^{h}$ for the current hop based on the question $Q$ and the
previous-hop result $a^{h-1}$. After that, the program generator receives $Q$,
$a^{h-1}$ and $t^{h}$ as inputs and generate the program $p^{h}$.
Subsequently, $p^{h}$ is executed by the program executor and $a^{h}$ can be
derived. Notably, for programs comprising multi-level operations, the executor
executes from the atomic operations to the high-order operations. At this
point, the iteration detection process checks if the high-order operation of
$p^{h}$ is a multi-hop operation222${\mathtt{COMPOSE}}$ and
${\mathtt{INTERSECT}}$, which are defined in Section 3.2. If it is, HopPG
returns $a^{h}$ to iterate the above process. Otherwise, HopPG terminates the
iteration and outputs $a^{h}$ as the final answer.

In HopPG, the fact retriever and the program generator are trainable and
trained separately among these modules. We will introduce their details in the
following sections.

####  3.3.1 Supporting Fact Retriever

The retriever in HopPG aims to select the supporting fact $t^{h}$ for the
h-hop program generation from the provided candidates, including a table and a
set of texts. for the $h$-hop program generation. Following Yoran et al.
(2022), we finetune the BART-large Lewis et al. (2020) model using the
training set of MMQA-T2 as our retriever. The input of the retriever is a
sequence consisting of the question $Q$, the golden execution result of the
previous hop $\bar{a}^{h-1}$, and one of the fact candidates $t^{i}$:

$\text{Inp}^{h}_{R}=[\langle s\rangle;Q;\langle\backslash
s\rangle;\bar{a}^{h-1};\langle\backslash s\rangle;t^{i}]$ (2)

Notably, the table $t^{1}$ is flattened by connecting its rows. For a first-
hop example, the previous-hop execution result $]\bar{a}^{0}$ is set to
"$\mathtt{None}$". The retriever receives the input sequences of all
candidates and outputs a score vector $\bm{\delta}$=$(s^{1},...,s^{K})$ of
them, then the model is fine-tuned using the following loss function, where
$l$ is the golden fact’s index:

${\mathcal{L}}=\mathtt{CrossEntropy}(l,\mathtt{Softmax}(\bm{\delta}))$ (3)

After tuning, the supporting fact retrieval accuracy of our retriever is
90.7%. During the program generation process, the tuned retriever ranks all
candidate inputs and selects the fact $t^{h}$=$argmax(\bm{\delta})$ as the
supporting fact of the current hop $h$.

Knowledge | Question Type | Hop | Distribution
---|---|---|---
Only Table | Span Extraction | 1 | 42.5%
YesNo | 1 | 3.1%
Compare | 1 | 5.8%
Calculation | 1 | 0.6%
Intersect | 2 | 2.8%
Compose + Span Extraction | 2 | 6.0%
Only Text | Span Extraction | 1 | 10.7%
YesNo | 1 | 5.1%
Table + Text | Intersect | 2 | 4.1%
Compose + Span Extraction (table to text) | 2 | 9.4%
Compose + Span Extraction (text to table) | 2 | 4.8%
Compose + YesNo (table to text) | 2 | 2.0%
| Compare (Compose + Span Extraction (text to table)) | 3 | 3.0%
Table 2: The question type distribution of the training set of MMQA-T2.  | Extraction | Compare | Compose | YesNo | Calculation | Intersect | Compose_Compare | Total
---|---|---|---|---|---|---|---|---
Train | 7512 | 819 | 3463 | 1170 | 101 | 978 | 425 | 14122
Dev | 834 | 90 | 346 | 130 | 11 | 108 | 47 | 1566
Test | 748 | 70 | 383 | 142 | 6 | 88 | 64 | 1501
Table 3: Basic statistics of MMQA-T2.

####  3.3.2 Program Generator

The program generator aims to generate the corresponding program for each hop.
In this work, the generator is a BART-based model equipped with a structure-
aware knowledge reader Zhang et al. (2020), which is designed to enhance the
table understanding ability of the encoder. We use the training set of MMQA-T2
together with our constructed pseudo programs to train the UniRPG.
Specifically, for the $h$th-hop program generation, the input sequence
consists of the question $Q$, the execution result of the previous-hop program
$a^{h-1}$, and the supporting fact $t^{h}$ selected by the retriever. We
connect a text span "Yes or No" to the question to transfer the
$\mathtt{YESNO}$ reasoning type into a span extraction problem. Formally, the
$h$th-hop input of our generator is represented as follows:

$\text{Inp}^{h}_{G}=[\langle s\rangle;\textit{yes or no};Q;\langle\backslash
s\rangle;a^{h-1};\langle\backslash s\rangle;t^{h}]$ (4)

The input sequence is fed into the structure-aware knowledge reader, which
injects table structure information into the self-attention layers of the
BART-encoder with structure-aware attention. The reader learns the input and
outputs the representations of input tokens. Then, we feed it into the encoder
to learn the representation $\mathbf{K}=\\{\mathbf{k}_{i}\\}_{i=1}^{L}$, where
$L$ is the length of the input sequence.

Subsequently, the representations vectors $\mathbf{K}$ of the input tokens are
used to decode the program based on our defined operations. For the generator
training, we collect the golden supporting fact and the corresponding program
for each hop of the questions. All these data are utilized to train the
program generator.

####  3.3.3 Program Executor

To perform answer derivation, we implement a symbolic program executor for
HopPG that executes the generated programs based on their meanings. When
dealing with programs comprising multiple levels of operations, the executor
executes from the atomic operations to the high-order operations.

####  3.3.4 Iteration Detector

In HopPG, we add an iteration detection process after the program execution to
determine whether further hop generation and reasoning are needed. During the
inference phase of HopPG, the iteration detection process checks the outermost
operation of the current generated program to determine if it is one of the
multi-hop operations, which include $\mathtt{COMPOSE}$ and
$\mathtt{INTERSECT}$. If the operation belongs to multi-hop operations, HopPG
performs the next hop generation iteratively. Otherwise, the current result is
considered as the final answer.

Model | MMQA | MMQA-T2
---|---|---
| Overall | Single-hop | Multi-hop | Overall | Single-hop | Multi-hop
AutoRouting | 42.10 / 49.05 | - | - | - | - | -
Implicit-Decomp | 48.80 / 55.49 | 51.61 / 58.36 | 44.59 /51.19 | 54.30 / 62.15 | 57.34 / 64.75 | 46.23 / 55.26
UniRPG† | 53.87 / 60.20 | 57.22 / 64.05 | 48.87 / 54.45 | 63.09 / 70.29 | 65.05 / 72.72 | 56.69 / 63.84
HopPG (ours) |  54.61 / 61.00 |  58.38 / 64.92 |  48.98 / 55.18 |  63.76 / 71.14 |  66.42 / 73.54 |  57.91 / 64.77
Table 4: Results on the complete MMQA and the MMQA-T2 datasets. Type | Implicit-Decomp | UniRPG† | MHPG
---|---|---|---
TableQ |  72.35 / 79.89 | 63.41 / 69.93 | 65.04 / 70.33
TextQ | 49.65 / 50.01 | 65.60 / 73.64 |  67.13 / 75.19
Compose(TableQ,TextQ) | 50.00 / 56.70 | 70.73 / 75.80 |  71.95 / 75.99
Compose(TextQ,TableQ) | 37.96 / 49.89 | 50.93 / 60.67 |  56.48 / 68.05
Intersect(TableQ,TextQ) | 48.98 / 54.24 | 44.89 / 48.63 |  48.98 / 55.24
Compare(TableQ,Compose(TableQ,TextQ)) |  67.19 / 71.55 | 40.00 / 46.67 | 45.31 / 47.63
Table 5: Results on questions with different types of MMQA-T2.

##  4 Experiments

###  4.1 Dataset

The MMQA-T2 used in this paper is a subset of MMQA Talmor et al. (2021).
Specifically, we collect all questions based on tables and texts and exclude
questions using images from MMQA, in a total of 15688 training instances and
1501 development instances. Each question in MMQA is provided with 1 table
together with 10 texts as candidate facts. The question type of the collect
instances is shown in Table 2. Based on the question types, we re-split the
training instances we collected in a ratio of 9:1 as the training set of the
development set of MMQA-T2, respectively. The collected development instances
from MMQA are directly used as the test set of MMQA-T2. We give the final
basic statistics of MMQA-T2 in Table 3.

To further demonstrate MMQA-T2, we present the distribution of the training
set questions in Table 2 based on knowledge utilized, reasoning type, and the
number of hops. It can be observed that 38.5% of the questions are multi-hop,
with 23.3% of those requiring both tables and text to derive answers. These
statistics indicate that MMQA-T2 is a suitable dataset for evaluating HopPG,
designed to improve question-answering performance in multi-hop reasoning over
heterogeneous knowledge.

###  4.2 Implementation Details

The program generator of HopPG is initialized using BART-base and optimized
with AdamW. The training settings are consistent with UniRPG. Specifically,
the learning rate, batch size and weight decay are set to 1e-4, 128 and 0.01,
respectively. When generating programs, we set the Beam Size of the beam
search method as 4. The experiments are conducted on NVIDIA A100 GPU.

###  4.3 Baselines

##### AutoRouting and Implicit-Decomp

These two baselines are from Talmor et al. (2021). We compare HopPG’s
question-answering performance with these baselines on the original MMQA
dataset. For questions requiring images, we directly use the prediction
results from Implicit-Decomp.

##### UniRPG

We reproduce the UniRPG-base version to directly generate complete multi-hop
programs based on our operations. We select the top 2 candidate knowledge
ranked by retrieval scores as the supporting facts. Then the question and the
two facts are concatenated as input for UniRPG. In addition, we cut off the
over-length input directly.

###  4.4 Main Results

Table 4 shows the question-answering results of our HopPG and the baseline
models. We use EM and F1 scores as the evaluation metrics and report the
results on both the original MMQA and MMQA-T2 datasets. For image-based
questions in MMQA, we use the predictions of Implicit-Decomp. As the table
shows, UniPRG, the first semantic parsing-based method on HQA tasks, achieves
significant performance on MMQA-T2 by 63.09 EM and 70.29 F1. It is proved that
UniRPG can effectively solve the answer reasoning over tabular and textual
knowledge by generating executable programs.

Based on the results of UniRPG, our HopPG further brings improvements on
MMQA-T2. The EM scores increase by 1.37 on the single-hop questions and 1.22
on the multi-hop questions. The improvements are from the ability of HopPG to
reduce the complexity of the supporting facts, and sufficiently utilize
previous-hop execution results during program generations. These improvements
demonstrate the effectiveness of HopPG.

| Model | Golden Program | Generated Program
---|---|---|---
Q1 | UniRPG | $\mathtt{SPAN(86,89)}$ | $\mathtt{SPAN(86,164)}$
HopPG-h1 | $\mathtt{SPAN(88,91)}$ | $\mathtt{SPAN(88,91)}$
HopPG-h2 | - | -
Q2 | UniRPG | $\mathtt{CELL(244,248)}$ | $\mathtt{MULTISPAN(CELL(58,69),...,CELL(244,264))}$
HopPG-h1 | $\mathtt{COMPOSE(MULTISPAN(CELL(71,76),CELL(100,101)))}$ | $\mathtt{COMPOSE(MULTISPAN(CELL(71,76),CELL(71,76)))}$
HopPG-h2 | $\mathtt{CELL(252,256)}$ | $\mathtt{CELL(252,256)}$
Q3 | UniRPG | $\mathtt{CELL(352,356)}$ | $\mathtt{CELL(352,373)}$
HopPG-h1 | $\mathtt{COMPOSE(CELL(354,358))}$ | $\mathtt{COMPOSE(CELL(354,358))}$
HopPG-h2 | $\mathtt{CELL(356,360)}$ | $\mathtt{CELL(356,360)}$

Table 6: Case studies.

###  4.5 Ablation Studies

To provide a more detailed and intuitive demonstration of HopPG’s performance
on different question types, we compare the question-answering results between
HopPG and baselines in Table 5, where the results are reported on questions
with different hop numbers and knowledge sources.

####  4.5.1 Questions with Homogeneous Knowledge

The results in the table indicate that Implicit-Decomp performs excellently on
table-based questions, because it utilizes the table pre-trained model, TAPAS
Herzig et al. (2020), for table-based question answering. Compared to TAPAS,
semantic parsing-based models like UniRPG and HopPG offer the advantage of
interpretability and avoid the need for expensive pre-training on a large
number of tables. The table also shows that HopPG outperforms the baseline
models on text-based questions because it generates programs using only the
selected text as input, rather than simply concatenating complex and
heterogeneous knowledge. This greatly reduces the difficulty of model
inference.

####  4.5.2 Multi-hop Questions with Heterogeneous Knowledge

As expected, HopPG achieves significant improvements in multi-hop question
answering, which are mainly from the following three reasons: 1) Compared to
directly generating complete programs, HopPG improves the accuracy of program
generation at each hop by reducing the complexity of knowledge. 2) The program
generation for each hop can refer to the execution results of the previous
hop. 3) In HopPG, the errors in the program generated at the previous hop do
not directly lead to incorrect results in the final output, which to some
extent reduces error propagation.

In addition, the bottom row of the table also shows that our framework has
limited performance on the three-hop questions. This is because the maximum
number of iterations of HopPG is set to $2$ in this paper, making HopPG cannot
tackle more complex multi-hop questions well. We will focus on the program
generation of more complex multi-hop questions in the future work.

###  4.6 Case Studies

In Table 6, we present three cases of questions that UniRPG fails to answer
but were fixed by HopPG. Among them, Q1 is a single-hop question with the
answer contained in a given textual knowledge. For UniRPG, all candidate texts
are concatenated with flattened tables as input the sequence. In this
experiment, the pseudo-program for Q1 is the same in both UniRPG and HopPG. As
shown in the first row of the table, UniRPG incorrectly predicts the end index
of the answer string in the serialized knowledge, while HopPG successfully
extracts the answer. This is because UniRPG directly concatenates all
candidate supporting facts as input, which makes it difficult for the model to
understand the knowledge and reason about the answer due to the redundant
information. In contrast, HopPG reduces the complexity of the input knowledge
by retrieving the necessary supporting fact for each hop, thereby improving
the reasoning accuracy.

UniRPG cannot handle Q2, a multi-hop question, due to its limited operation
set for multi-hop reasoning. Therefore, in UniRPG, Q2 is treated as a single-
hop question and directly annotated with the span extraction pseudo-program.
As shown in Table 6, the model is confused and incorrectly predicts the
$\mathtt{MULTISPAN}$ operation for Q2 instead of $\mathtt{SPAN}$. because the
question format of multi-hop questions is different from that of single-hop
questions. The incorrect operation further leads to the generation of a series
of wrong string indices. For simplicity, we omits the intermediate
$\mathtt{CELL}$ operations in UniRPG’s result for Q2 in Table 6. In contrast,
HopPG generates two-hop programs iteratively for this question. Although the
generated first-hop program is not entirely correct, the lack of information
about an intermediate result does not have a decisive impact on the generation
of the program for the second iteration. HopPG ultimately successfully
generates the correct second-hop program for Q2 and obtains the correct
answer.

Q3 is also a multi-hop question. As shown in the table, UniRPG predicts the
correct operation, but it incorrectly predict the string index for the answer.
In contrast, HopPG successfully generates a two-hop program for the question
not only obtaining the correct answer but also making the reasoning process
interpretable, demonstrating the advantage of HopPG in handling multi-hop
questions.

###  4.7 Error Analysis

To conduct error analysis over the test set of MMQA-T2, we collected the
programs generated by HopPG that are inconsistent with the pseudo programs we
annotated. These wrong programs are primarily caused by two reasons: incorrect
operation prediction and incorrect string index $(s,e)$ prediction. According
to our statistical analysis, among the wrong cases of single-hop questions,
27% of them have incorrect operation predictions, while 99% have incorrect
string index predictions. The proportions of these two reasons in the cases of
two-hop questions (’COMPOSE’ reasoning type) also align with the
aforementioned trend. Specifically, for their first-hop program generation,
the proportions of incorrect operation prediction and incorrect string index
prediction are 32.4% and 100%, respectively. For the second-hop, the
proportions of these two factors are 7% and 98%, respectively. This indicates
that if the operation selection is incorrect, the model will struggle to
accurately retrieve the require information from the knowledge.

Additionally, in the wrong cases of two-hop questions, the proportions of
errors in the first-hop and second-hop program generation are 50.0% and 69.9%,
respectively. Based on our observations, an error in the first-hop program
does not necessarily lead to an error in the second-hop generation, as the
execution results of the first-hop program only serve as input information for
the second-hop. In fact, among the cases where the first-hop program
generation are incorrect, 60.2% of them generate the correct second-hop
programs and obtain the correct answers to the questions. This proves that the
iterative generation way of HopPG can to some extent mitigate the impact of
reasoning errors in previous hops on the final result.

##  5 Conclusion

We propose HopPG, a self-iterative program generation approach for multi-hop
question answering over heterogeneous knowledge. Unlike directly generating
complete programs for multi-hop questions, HopPG iteratively generates
programs for each hop based on the execution results from the previous-hop
program. We evaluate our model using a subset of MMQA that only contains text-
based and table-based questions and construct pseudo programs for each
instance to train HopPG under weak supervision. The experimental results
demonstrate that HopPG brings significant improvements for multi-hop question
answering over heterogeneous knowledge, outperforming semantic parsing-based
question-answering models that directly generate complete programs.

## References

  * Abdelaziz et al. (2021) Ibrahim Abdelaziz, Srinivas Ravishankar, Pavan Kapanipathi, Salim Roukos, and Alexander Gray. 2021.  A semantic parsing and reasoning-based approach to knowledge base question answering.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 35, pages 15985–15987.
  * Bao et al. (2016) Junwei Bao, Nan Duan, Zhao Yan, Ming Zhou, and Tiejun Zhao. 2016.  Constraint-based question answering with knowledge graph.  In _Proceedings of COLING 2016, the 26th international conference on computational linguistics: technical papers_ , pages 2503–2514.
  * Bao et al. (2014) Junwei Bao, Nan Duan, Ming Zhou, and Tiejun Zhao. 2014.  Knowledge-based question answering as machine translation.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 967–976.
  * Chen et al. (2020a) Wenhu Chen, Ming Wei Chang, Eva Schlinger, William Wang, and William W. Cohen. 2020a.  Open question answering over tables and text.
  * Chen et al. (2020b) Wenhu Chen, Hanwen Zha, Zhiyu Chen, Wenhan Xiong, Hong Wang, and William Wang. 2020b.  Hybridqa: A dataset of multi-hop question answering over tabular and textual data.
  * Chen et al. (2021) Zhiyu Chen, Wenhu Chen, Charese Smiley, Sameena Shah, and William Yang Wang. 2021\.  Finqa: A dataset of numerical reasoning over financial data.
  * Choi et al. (2018) Eunsol Choi, He He, Mohit Iyyer, Mark Yatskar, Wen-tau Yih, Yejin Choi, Percy Liang, and Luke Zettlemoyer. 2018.  Quac: Question answering in context.  _arXiv preprint arXiv:1808.07036_.
  * Cui et al. (2020) Leyang Cui, Yu Wu, Shujie Liu, Yue Zhang, and Ming Zhou. 2020.  Mutual: A dataset for multi-turn dialogue reasoning.  _arXiv preprint arXiv:2004.04494_.
  * Eisenschlos et al. (2021) Julian Martin Eisenschlos, Maharshi Gor, Thomas Müller, and William W. Cohen. 2021\.  Mate: Multi-view attention for table transformer efficiency.  _arXiv e-prints_.
  * Fan et al. (2019) Angela Fan, Yacine Jernite, Ethan Perez, David Grangier, Jason Weston, and Michael Auli. 2019.  Eli5: Long form question answering.  _arXiv preprint arXiv:1907.09190_.
  * Han et al. (2020) Jiale Han, Bo Cheng, and Xu Wang. 2020.  Open domain question answering based on text enhanced knowledge graph with hyperedge infusion.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1475–1481, Online. Association for Computational Linguistics.
  * Herzig et al. (2020) Jonathan Herzig, Pawel Krzysztof Nowak, Thomas Müller, Francesco Piccinno, and Julian Eisenschlos. 2020.  TaPas: Weakly supervised table parsing via pre-training.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4320–4333, Online. Association for Computational Linguistics.
  * Hui et al. (2022) Binyuan Hui, Ruiying Geng, Lihan Wang, Bowen Qin, Yanyang Li, Bowen Li, Jian Sun, and Yongbin Li. 2022.  S2SQL: Injecting syntax to question-schema interaction graph encoder for text-to-SQL parsers.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 1254–1262, Dublin, Ireland. Association for Computational Linguistics.
  * Kumar et al. (2021) Vishwajeet Kumar, Saneem Chemmengath, Yash Gupta, Jaydeep Sen, Samarth Bharadwaj, and Soumen Chakrabarti. 2021.  Multi-instance training for question answering across table and linked text.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. 2019.  Natural questions: a benchmark for question answering research.  _Transactions of the Association for Computational Linguistics_ , 7:453–466.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Liu et al. (2020) Jian Liu, Leyang Cui, Hanmeng Liu, Dandan Huang, Yile Wang, and Yue Zhang. 2020\.  Logiqa: A challenge dataset for machine reading comprehension with logical reasoning.  _arXiv preprint arXiv:2007.08124_.
  * Liu et al. (2022) Qian Liu, Bei Chen, Jiaqi Guo, Morteza Ziyadi, Zeqi Lin, Weizhu Chen, and Jian-Guang Lou. 2022.  TAPEX: Table pre-training via learning a neural SQL executor.  In _International Conference on Learning Representations_.
  * Pan et al. (2020) Liangming Pan, Wenhu Chen, Wenhan Xiong, Min Yen Kan, and William Yang Wang. 2020\.  Unsupervised multi-hop question answering by question generation.
  * Sun et al. (2019) Haitian Sun, Tania Bedrax-Weiss, and William W Cohen. 2019.  Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text.  _arXiv preprint arXiv:1904.09537_.
  * Sun et al. (2021) Haitian Sun, William W. Cohen, and Ruslan Salakhutdinov. 2021.  Iterative hierarchical attention for answering complex questions over long documents.  _arXiv e-prints_.
  * Talmor et al. (2021) Alon Talmor, Ori Yoran, Amnon Catav, Dan Lahav, Yizhong Wang, Akari Asai, Gabriel Ilharco, Hannaneh Hajishirzi, and Jonathan Berant. 2021.  Multimodalqa: Complex question answering over text, tables and images.
  * Wang et al. (2022) Yingyao Wang, Junwei Bao, Chaoqun Duan, Youzheng Wu, Xiaodong He, and Tiejun Zhao. 2022.  Muger2: Multi-granularity evidence retrieval and reasoning for hybrid question answering.
  * Wenhu Chen (2021) Ming-wei Chang Wenhu Chen. 2021.  Open question answering over tables and text.  _Proceedings of ICLR 2021_.
  * Xiong et al. (2022) Guanming Xiong, Junwei Bao, Wen Zhao, Youzheng Wu, and Xiaodong He. 2022.  Autoqgs: Auto-prompt for low-resource knowledge-based question generation from sparql.  In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_, pages 2250–2259.
  * Yih et al. (2014) Wen-tau Yih, Xiaodong He, and Christopher Meek. 2014.  Semantic parsing for single-relation question answering.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 643–648.
  * Yih et al. (2016) Wen-tau Yih, Matthew Richardson, Chris Meek, Ming-Wei Chang, and Jina Suh. 2016\.  The value of semantic parse labeling for knowledge base question answering.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 201–206, Berlin, Germany. Association for Computational Linguistics.
  * Yoran et al. (2022) Ori Yoran, Alon Talmor, and Jonathan Berant. 2022.  Turning tables: Generating examples from semi-structured tables for endowing language models with reasoning skills.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6016–6031, Dublin, Ireland. Association for Computational Linguistics.
  * Zhang et al. (2020) Hongzhi Zhang, Yingyao Wang, Sirui Wang, Xuezhi Cao, Fuzheng Zhang, and Zhongyuan Wang. 2020.  Table fact verification with structure-aware transformer.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1624–1629, Online. Association for Computational Linguistics.
  * Zhou et al. (2022a) Yongwei Zhou, Junwei Bao, Chaoqun Duan, Haipeng Sun, Jiahui Liang, Yifan Wang, Jing Zhao, Youzheng Wu, Xiaodong He, and Tiejun Zhao. 2022a.  Opera: Operation-pivoted discrete reasoning over text.  _arXiv preprint arXiv:2204.14166_.
  * Zhou et al. (2022b) Yongwei Zhou, Junwei Bao, Chaoqun Duan, Youzheng Wu, Xiaodong He, and Tiejun Zhao. 2022b.  UniRPG: Unified discrete reasoning over table and text as program generation.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 7494–7507, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Zhu et al. (2021) Fengbin Zhu, Wenqiang Lei, Youcheng Huang, Chao Wang, Shuo Zhang, Jiancheng Lv, Fuli Feng, and Tat Seng Chua. 2021.  Tat-qa: A question answering benchmark on a hybrid of tabular and textual content in finance.