rm

11institutetext: CERN, Geneva, Switzerland

# Beam Loss Monitors at LHC

B. Dehning

###### Abstract

One of the main functions of the LHC beam loss measurement system is the
protection of equipment against damage caused by impacting particles creating
secondary showers and their energy dissipation in the matter. Reliability
requirements are scaled according to the acceptable consequences and the
frequency of particle impact events on equipment. Increasing reliability often
leads to more complex systems. The downside of complexity is a reduction of
availability; therefore, an optimum has to be found for these conflicting
requirements. A detailed review of selected concepts and solutions for the LHC
system will be given to show approaches used in various parts of the system
from the sensors, signal processing, and software implementations to the
requirements for operation and documentation.

Keywords
Machine protection; equipment protection; beam loss; dependability.

##  1 Introduction

After a LHC beam loss project study phase, a functional specification is
compiled. The specification introduces the subject, first viewing the project
globally by treating:

  * •

location of monitors;

  * •

time response;

  * •

dynamic range;

  * •

safety and reliability requirements.

The safety and reliability requirements need to be discussed at the system
level, to define the overall quantitative requirements. The time response,
dynamic range, safety, and reliability requirements limit the choice of
sensors and define the acquisition chain. With the knowledge obtained in the
project study phase, the following choices are made:

  * •

sensor: ionization chamber;

  * •

acquisition chain: distributed system with local and independent beam inhibit
functionality.

A more detailed treatment of the global safety and reliability requirements
has been covered in study groups and thesis projects. The subjects treated
include:

  * •

acquisition chain with:

    * –

parallel and voting for safety and reliability requirements;

    * –

radiation-tolerant electronics;

  * •

fail-safe system;

  * •

data flow path;

  * •

management of settings;

  * •

functional tests;

  * •

preventive actions;

  * •

firmware updates;

  * •

reliability software;

  * •

human errors;

  * •

documentation.

Several of these aspects will be discussed in this paper, and examples will be
presented from the LHC beam loss monitoring system.

##  2 Global beam loss measurement requirements

For a beam loss protection system, the possible loss locations and therefore
also the potential damage location are unknown parameters, to be addressed by
particle tracking and particle shower simulations. In a second step, the
optimal sensor locations are also determined by particle shower simulations.
For the LHC, the considerations are illustrated in Fig. 1. The electrodes of
the beam position monitors are retracted to be shielded by the nearby vacuum
chamber walls against particle impacts, which could create electrical charges
on the electrodes and disturb the beam position measurement.

Figure 1: Loss location considerations: aperture between a LHC bending magnet
(MB) and a quadrupole magnet (MQ). The change in aperture is mainly controlled
by the connection bellow and the beam position monitor (BPM) location. BLM,
beam loss monitor.

An aperture limitation results in a concentration of losses if off-orbit
protons approach the aperture. At the LHC, this is the case for every
transition between a bending and a quadrupole magnet. This can be visualized
by the tracking simulation (Fig. 2), resulting in a maximum at the beginning
of the quadrupole magnet.

Figure 2: Number of lost protons and beta function values with schematic of
LHC regular cell as function of the location along the lattice. MB, bending
magnet; MQ, quenching magnet.

These loss locations are most probable, because:

  * •

the beta function, and therefore the beam size, is maximal;

  * •

orbit bumps have a maximum at this location, because of the location of a
dipole corrector magnet near to the quadrupole magnet;

  * •

alignment errors are possible, causing an additional aperture limitation.

The shower particles initiated by lost protons can be best observed outside of
the magnet yoke about a metre downstream of the proton impact location (see
Fig. 3).

Figure 3: Number of secondary particles as function of location along the
lattice. MB, bending magnet; MQ, quenching magnet.

A second maximum occurs at the downstream transition between the quadrupole
and bending magnet, owing to the reduced material in the transition region. To
make use of the high particle signal, resulting in the lowest statistical
measurement error, the ionization chambers are located at or near to particle
shower maxima (see Fig. 3, red and blue rectangular areas). A separation
between the losses from beams 1 and 2 is given by the different locations of
the shower particle maxima, owing to their opposite directions.

The LHC ionization chambers are cylindrical, with a sensitive volume of
$\Unit{1.5}{l}$, covered by a yellow insulating tube and are mounted on the
outside of the magnets or near collimators (see Fig. 4, bottom right, red and
blue rectangular areas).

Figure 4: LHC tunnel photos with ionization chambers (yellow tubes) mounted on
the outside of magnets and schematic of an ionization chamber near a
collimator. BLM, beam loss monitor; IC, ionization chamber; SEM, secondary
emission monitor.

The limits of the time response and dynamic range requirements for LHC
protection are mostly defined by the quench curves of the bending magnets. The
quench levels of the magnets are orders of magnitude lower than the damage
levels of the magnets. Magnet quenching is avoided, because of the gain in
operational efficiency, by extracting the beam from the ring and therefore
ending the deposition of heat in the coil before quenching can occur. In the
case of a quench, the magnet coil is warmed up and the new cool down takes
between 6 and $10\Uh$.

Figure 5: Proton density rate as function of loss duration. Different curves
indicate the functional dependence for different energies and the defined
observation range. Red arrow, required proton density rate dynamic; blue
arrow, duration dynamic.

The allowed particle loss rate (see Fig. 5) in protons per metre per second is
shown as the function of the loss duration. The characteristic superconducting
magnet quench level curves are due to the quench margin of the superconducting
cable filaments and the super fluid cooling of the cables and the whole magnet
coil. For short duration losses, the quench level is about four orders of
magnitude higher than for steady-state losses and for both LHC nominal beam
energies, of $450\UGeV$ and $7\UTeV$, an order of two variation is seen.

The time resolution of the loss measurement system of $40\Uus$ is given by the
duration of the extraction of the beam from the LHC, $89\Uus$, and some signal
propagations and synchronization considerations. The maximum duration is given
by the reach of the steady-state quench level at about $80\Us$ (see Fig. 5,
blue arrow).

The maximal signal value is defined by the crossing of the $89\Uus$ line and
the quench level at $450\UGeV$. Owing to an optimization process for the LHC
acquisition electronics, the value has been chosen a little lower (see Fig. 5,
vertical dashed black line ($89\Uus$) and thin green line). The lower limit of
the dynamic range is given by the steady-state quench level for $7\UTeV$ and
the need to observe losses, for accelerator tuning purposes, below the quench
level (see Fig. 5, thin blue line, $80\Us$). These considerations led to a
required signal dynamic of over seven orders of magnitude (see Fig. 5, red
arrow). Operational experience required that the dynamic upper value be
extended by two orders of magnitude for short-term losses in injection areas.

##  3 Safety system design approach

All considerations start with the recognition that the probable frequency and
probable magnitude of a non-conformal behaviour could lead to a damage of the
system integrity. The combined likelihood of frequency and magnitude
determines the risk for a certain system (see Fig. 6, first column). The risk
could be reduced by using a safety system providing protection, but increased
complexity reduces the availability of the protected system (see Fig. 6, first
row). To arrive at a quantitative demand for a safety level, the probable
frequency of events and the probable magnitude of its consequence are utilized
by the SIL (safety integrity level) approach [1] or the ‘as low as reasonably
practicable’ (ALARP) approach.

Figure 6: LHC protection system design approach (items in green are discussed
in this paper). ALARP, as low as reasonably practicable; SIL, safety integrity
level.

For both approaches, a failure probability per time is estimated by
calculating the risk of damage and the resulting downtime of the equipment
[2]. A failure in the safety system itself should fall in a fail-safe state,
with the consequence of reducing the operation efficiency. The main design
criteria for the safety system are listed in the safety column of Fig. 6:
fail-safe, redundancy, survey, and functional check. The protection column of
Fig. 6 lists the methods for the protection of an accelerator: stop of next
injection applicable for a one-path particle guiding system (linac, transfer
line) and extraction of the beam for a multipath system (storage ring). The
accelerator safety system consists of a beam loss measurement system, an
interlock system, and a beam dump system. If superconducting magnets are used,
some beam loss protection could also be provided by the quench protection
system. The availability column of Fig. 6 lists the means used in the design
of the safety system to decrease the number of transitions of the system into
the fail-safe state. The effect of the number of components added to a system
to increase the probability of a safe operation results in a reduction in the
availability of the system. This negative consequence of the safety-increasing
elements is partially compensated by the choice of reliable components, by
redundancy, voting, and the monitoring of drifts of the safety system
parameters.

##  4 Failure probability and failure rate reduction

To illustrate the available means of increasing safety, the system’s basic
functional dependencies are discussed. An often-valid assumption is given by
the exponential time dependence of the failure probability $F(t)$ (Fig. 7).
With increasing time, the probability of the occurrence of a failure in a
system approaches 1. The failure rate, $\lambda$, is assumed to be time-
independent (Fig. 8, magenta curve). In a next step, two systems with the same
functionality are assumed to be working in parallel, to allow redundant
operation. The failure rate, $\lambda$, decreases drastically for short times,
but finally approaches the failure rate of a single system (Fig. 8, blue
line).

Figure 7: Exponential failure probability Figure 8: Failure rates of different
systems as a function of time (arbitrary units). Magenta: single system. Blue:
Two systems parallel. Green: Parallel systems with survey. Red: Parallel
systems with survey and with regular test.

It should be noted that the failure rate curve changes from time-independent
to time-dependent behaviour. A further reduction in the failure rate could be
reached by a survey of the system. With a system survey, some failure modes
can be detected in advance and a repair can be planned (see Fig. 8, red and
green line). This procedure results in a shift of the failure rate curve to
lower values, which no longer approach the infinite times of the single system
rate. Another strong reduction could be reached if the system could be
regarded as new after a certain time period. The failure rate curve shows the
time dependence of the surveyed system in the period $t_{0}=0$ to $t=t_{1}$
repeated after every time period (see Fig. 8, red lines). The conclusion that
a system could be regarded as new after a certain time is justified if the
system is subjected to a test. Functional tests will verify, on request, that
the system has the defined functionality. In case of an internal system
failure system, the very basic requirement is a fail-safe behaviour. Internal
failure will not contribute to the unsafeness of the system but will
contribute to its non-availability.

##  5 Protection system overview

As an example of a protection system, the CERN LHC beam loss monitoring (BLM)
system will be used. The discussion will focus on protection, reliability, and
availability aspects.

The main purpose of the BLM system is to convert particle shower information
into electrical signals, which are then compared with limits. If the limits
are exceeded, extraction of the LHC beam from the ring is initiated to stop
the irradiation of equipment. In the case of the LHC, the protection function
is often linked to the quench prevention of the superconducting magnets, since
the threshold levels for beam extraction are lower (orders of magnitude) than
for the damage protection of equipment [3].

The very first element of the protection system is the sensor that detects the
irradiation of equipment. The conversion of the particle shower magnitude is
done by ionization chambers [4] or secondary emission detectors [5] (see Fig.
9, left block). The front-end acquisition electronics convert the analogue
detector signal into a digital signal and transmit the signal to the back-end
acquisition and control unit, which is the decision-making centre of the whole
system. The measured signals arrive here and are compared with the limits. In
addition, beam permit signals are generated (see Fig. 9, red block), taking
the information of the system settings (see Fig. 9, right-hand blocks) into
account. The measurement data and all setting information are also distributed
to the display and the logging databases (see Fig. 9, bottom blocks) from this
unit. The control functionality is linked to the survey and test
functionality, which are discussed later.

Figure 9: Information flow from the sensor up to the beam permit signal
transmission. The red framed (back-end acquisition and control) unit is the
local decision-making centre.

In the LHC, ionization chambers [4] and secondary emission detectors [5] are
used. Their signals are digitized using a current-to-frequency converter [6,
7] (see Fig. 10, front-end acquisition unit in tunnel). Up to the end of the
analogue signal chain, the signal is not redundant, because no technical
solution has been found to the problem of splitting the detector signal while
simultaneously allowing a large dynamic signal (nine orders of magnitude). To
cope with this requirement for the analogue front-end unit, a low failure rate
circuit concept has been chosen. To avoid the consequences of single event
effects, and to increase the availability of a channel, the signal is trebled
in the front-end logic. Two voting blocks are used to generate the signal
transmitted over a redundant optical link. A redundant optical link has been
chosen to increase the availability of the link, which is limited by the mean
time between failures of the transmission laser.

Figure 10: CERN LHC beam loss measurement and protection system: CRC, cyclic
redundancy check

The signals are decoded and cyclic redundancy checks (CRCs) are calculated for
both signal chains (see Fig. 10, back-end acquisition unit at the surface). At
the front-end unit, CRCs are also calculated and transmitted, to enable the
CRCs of each line and also the CRCs for both lines to be compared. This
procedure ensures high reliability and also maximizes the availability of the
data link [8, 9].

The effect of the implementation of redundancy and trebling in the data
transmission and treatment and the verification of loss-free data transmission
are listed in Table 1. The most important technique for increasing the
reliability of a system is given by a fail-safe design. In the case of an
internal failure of a system, it should make the transition to a state that
ensures the protection of the system. This could be done by assigning the
active state to: ‘system is allowed to operate’. In case of an internal
failure, if no power is supplied, the state will switch to a passive state and
the system will be protected.

Table 1: Procedure and techniques to increase the reliability and availability of acquisition systems | Comment position of monitor | Safety gain | Availability gain
---|---|---|---
Fail-safe | Active state = beam permit | Yes | No
Voting |  | Yes | Yes
Redundancy |  | Yes | Yes
CRC | Cyclic redundancy check | Yes | No

##  6 Fault tree analysis

The fault tree treatment of the system has been chosen to calculate, from the
component level up to the system level, the damage risk, the false alarm, and
the warning probability [10], taking into account the component failure,
repair and inspection rates.

The false alarm slice of the fault tree (see Fig. 11) shows the signal chain
for different false alarm generators (memory, beam energy from control unit
(combiner), and energy transceiver) of the back-end electronics [11]. The
different inputs are linked with a Boolean ‘OR’ gate so that every single
input generates, in the same way, a false alarm and, therefore, a downtime of
the system and the LHC.

Figure 11: Image section of the false alarm generation fault tree of the LHC
BLM system, showing the part describing the back-end acquisition unit.

The results of the fault tree analysis have been essential for the design of
the hardware and software, especially for the estimates of failure rates of
the optical links and the propagated consequences of it up to the system
damage and false rate probabilities. An optimization process has been
instigated, to balance the probabilities of damage rates and false alarms. The
failure rate calculations also lead to the definition of functional tests and
their frequencies. Failure modes are also defined for the limit values,
detector names, channel assignments, and much more data needed by the system.
Therefore, setting management and metadata verification tests are also treated
in the fault tree analysis.

##  7 Functionality checks

As an example of a check, the signal distribution inside the VME crate for the
beam energy and the beam permit line test is discussed [12, 13] (see Fig. 12).
The test is initiated by a client, to allow optimal scheduling. The control
unit (combiner card) holds a downtime counter requiring every 24 hours the
execution of functional tests every 24 hours. If the tests are not completed
in time, the downtime counter inhibits the beam permit immediately if no beam
is circulating or when the beam present flag becomes false. For the tests, the
whole system changes the status to ‘mode’ and, the control units send a
request to inhibit the beam permit line to each acquisition card (threshold
card) in sequence (see Fig. 12).

Figure 12: Beam permit line functionality check Figure 13: Check of the whole
acquisition chain

The test results are analyzed by the controller; if a false status is
detected, a manual intervention is required, to repair the system before the
test can be passed without a false status detected. The distribution of the
beam energy levels between the controller and the acquisition card is tested
by changing the energy levels in the test mode; this should result in the
acquisition card returning the appropriate threshold settings for comparison
with the settings sent.

In a second example, the test of the whole acquisition chain is presented [14,
15]. An electrical signal is introduced in the sensor by the capacitive
coupling of the sensor electrodes and by a harmonic modulation of the applied
high voltage supply (see Fig. 13). This test includes the complete signal
chain, except for the ionization process in the ionization chambers and the
secondary electron emission in the secondary emission monitor detectors. The
conversion of the particle shower to an electrical signal in the detector is
tested every few years with a radiative source placed outside the detector.
The long intertest interval for this test is possible because the failure mode
of a complete gas exchange with air (ionization chamber) or loss of the vacuum
(secondary emission detector) of the detectors will still result in an
appropriate signal, without loss of protection functionality. Also, this test
is initiated and the results are analyzed by the back-end unit (survey and
control) (see Fig. 13), allowing the beam permit line to be inhibited directly
in the case of a negative result.

##  8 Setting management

The system setting management controls the settings for the beam permit
thresholds and also the settings used for system operation [16, 17]. These
operational settings include hard and firmware information, to verify that the
configuration stored in the database images the installed system. Table 2
illustrates the variety of the metadata needed to interpret the measured
values or to check the configuration of the system. For example, a match
between measured value, channel official names, channel expert names, DCUM
(position of monitor), and monitor coefficient needs to be given and tested.
To reduce the complexity of the metadata information chain (see Fig. 9, right
blocks), a single path is defined for the metadata flow and the measurement
values into the back-end unit. The back-end unit distributes the measurement
values together with the metadata to ensure consistency and to have only one
location where the data integrity needs to be tested. This concept is
essential to reduce the number of possible failure modes for metadata
corruption.

Table 2: Parameters deployed on each back-end unit (threshold comparator module) Parameters | Data 32 bit | Description
---|---|---
Threshold values | 8192 |  16 channels $\times$ 12 sums $\times$ 32 energies
Channel connected | 1 | Generating (or not) a beam permit
Channel mask | 1 | ‘Maskable’ or ‘unmaskable’
Serial A | 1 | Card’s serial number (channels 1–8)
Serial B | 1 | Card’s serial number (channels 9–16)
Serial | 2 | Threshold comparator
Firmware version | 1 | Threshold comparator’s firmware
Expert names | 128 |
Official names | 128 |
DCUM | 16 | Position of monitor
Family names | 128 | Threshold family name
Monitor coefficients | 16 | Monitor threshold coefficients
Last link-state advertisement update | 2 | Time stamp: master table
Last flash update | 2 | Time stamp: non-volatile memory
Flash checksum | 1 | CRC value for or from table integrity
Figure 14: Comparison of descriptive metadatabase reference settings with
settings in the back-end acquisition and control unit. The decision logic is
indicated in the flow diagram. FPGA, field-programmable gate array.

Having expressed the importance of a failure mode optimized metadata flow, the
data check is achieved by comparing the data stored in a reference setting
database (Oracle) with the data stored in the memory of the back-end
electronics field-programmable gate arrays (see Fig. 14). Also, in this test,
a downtime counter located in the back-end unit (survey and control) requests
a comparison of the data stored at both locations every $24\Uh$. If the test
is not initiated, or if the test result is negative, the beam permit is
inhibited. Since the comparison is made in a different software environment,
the additional functionality required in the back-end unit is marginal, but it
is necessary to test the comparison code from time to time.

###  8.1 Descriptive metadata

Metadata need to be generated and the option for required changes needs to be
provided. To reduce human error, the graphical user interfaces (GUI) accessing
the setting database (see Fig. 9, right block) need to be optimized by
allowing for all data manipulation steps to include comparisons with previous
data, checks on the magnitudes of changes, and several confirmation steps. The
last confirmation steps require the electronic signatures of two independent
persons.

The generation of sets of metadata required initially and for larger changes
during the operation periods is done for the LHC system by a GUI for the
database access. Generation of metadata, such as limits for the beam abort
thresholds, are parameterized and the calculation is made by code loaded into
the database (Oracle) (see Fig. 9, rightmost block). The calculation made in
the database environment, where database software changes and updates are made
in a coherent manner, should ensure long-term maintainability [18].

###  8.2 Documentation

In a complex system, designed for operation over decades, sufficient
documentation is essential to describe the system for knowledge transfer. For
a safety system, the function of the documentation is to avoid failure modes
and failures. The design documentation, from the specification to
documentation on operation and system changes, needs to be distributed for
review, comment, and final approval by each client. At the LHC, standardized
forms, electronic procedures, and signatures are in use to organize the
process, an engineering change request outlines the motivation for a change,
the description of the proposed change, and an estimate of the impact of the
change on the functionality of the concerned system and other systems.

##  9 Snapshots of loss measurements triggered by events

The loss measurement recording rate has been set up at different speeds, with
$40\Uus,80\Uus,80\Ums$, and $1.3\Us$ integration times. The two first periods
are event-triggered, to cope with the amount of data, while the latter periods
are read out at $12\UHz$ and $1\UHz$. The event-triggered measurements are
used to analyze losses occurring at particular times during operation or
depending on measurements and output analysis data acquisition freezing
events. The $12\UHz$ measurements are used for the collimator positioning
feedback system and the $1\UHz$ measurements are used for continuous
observation of the accelerator status.

Figure 15: Example of a particle loss triggered event recording. The trigger
has been generated at $1.74\Us$. The measurements recorded before the trigger
event reveal loss precursors. The losses are caused by collisions between the
beam and dust particles.

High-resolution data have been used not only for the detailed study of beam
losses caused by dust events (see Fig. 15), but also to check for non-
conformities of the acquisition system. When testing the system under extreme
conditions, high loss levels with a large leading signal transition give an
insight into system performance. The advantage of publishing different
measurement signals is that it enables consistency checks to be performed. In
the LHC, several clients are used to check the consistency of measurement
data.

##  10 Acquisition database

The storage and fast retrieval of measurement data and metadata is also
essential for system checks. Besides the examples discussed previously, for
which extended data storage were required, an extreme case is the check of
noise amplitudes of the system (see Fig. 16). For a protection system with
limits leading automatically to a beam abort and to accelerator downtime,
there is a strong requirement to avoid false aborts caused by rare events
(noise). This is extreme, because rare signals need to be retrieved from
stored measurement data from acquisition periods lasting weeks. The
measurements with the shortest integration periods of $40\Uus$ show the
largest signal fluctuation, because signal averaging does not led to a
reduction in signal fluctuation. To reduce the amount of data to be stored, an
on-line measurement data reduction algorithm has been implemented in the back-
end unit. Only maximum values of the short integration times are stored for
the $1\UHz$ read-out. This procedure reduces the quantity of data to be stored
by over four orders of magnitude. In addition, a retrieval time optimized
database structure has been implemented for this purpose.

Figure 16: Noise level determination of all beam loss monitor channels. The
LHC loss monitor channels are grouped by the observed loss, creating elements
of cold and warm magnets and collimators. Top: Beam loss monitor noise signal
taken with no beam circulating versus beam abort thresholds. The blue line
indicates the threshold value and the red line the maximum noise goal set to
avoid any noise false beam aborts. Bottom: Beam loss monitor spectrum
normalized to the beam abort threshold.

##  11 Preventive action

The discussion in Section 4 emphasized the reduction in failure rate achieved
by surveying the system, to anticipate possible failure modes. In the LHC
system, this survey task is realized by the daily retrieval of relevant
database information and an automatic comparison with limits for initiating
actions. Reports containing different levels of abstraction are produced daily
and weekly.

Figure 17: Optical link failures and printed circuit board temperatures versus
time of day

An example of this procedure is given by the survey of optical links. The
links are redundant (see Fig. 10) and the calculations of different CRCs
enable the differences between the CRC values to be recorded and correlated
with board temperature variations (see Fig. 17). The limits for actions are
set empirically, to minimize downtime and maintenance efforts.

##  12 Summary

A systematic design approach for machine protection systems will start with
determination of the system failure rate. The failure rate magnitude could be
based on well-established standards first developed for the design of military
equipment, the aircraft industry, space missions, or nuclear power stations.
The effect of increasing complexity by adding protection functionalities and
therefore reducing availability is best studied by reliability software
packages [19]. The basic means of delivering a reduction in failure rate are
provided by a system layout with parallel, redundant information, treated in
combination with a regular survey of the system status and functional tests. A
survey will allow preventive actions, to reduce the failure rate. For a
protection system, a fail-safe design is essential so that protection is
ensured in the case of a failure.

Functionality checks staged for all levels of the signal treatment are
implemented for the LHC BLM system. The checks of the information exchange
inside the VME crate and the analogue and digital signal chain have been
discussed. Examples have been given to emphasize the importance of the
metadata information flow. The combination of measurement and metadata as
early as possible in the signal chain is important for the reduction of
failure modes and simplified test options. To attain low failure rates,
rigorous metadata tests have to be implemented, to ensure metadata conformity.
The generation of metadata and change options using a graphical interface also
need to be analyzed in terms of failure modes, taking into account long-term
usage and the maintainability of tests and validation procedures in the
future. For the LHC, the most stringent requirement in avoiding human error is
the request of two signatures to validate metadata changes. Although listed
last, documentation tasks should be started first, including planning for
reliability measures, and have to be continued as long as the system exists.

## References

  * [1] International Electrotechnical Commission, IEC 61508. IEC, 2010.
  * [2] G. Guaglio, Reliability of beam loss monitors system for the Large Hadron Collider, 11th Beam Instrumentation Workshop, Knoxville 2004 (AIP, 2004), vol. 732, p. 141, http://hal.in2p3.fr/in2p3-00025196
  * [3] B. Dehning et al., Overview of LHC beam loss measurements, 2011, p. THOAA03, https://cds.cern.ch/record/1379469
  * [4] M. Stockner. Ph.D. thesis, Technische Universität Wien, 2006.
  * [5] D. Kramer, Ph.D. thesis, Technical University of Liberec, 2008.
  * [6] E. Effinger et al., The LHC beam loss monitoring system’s data acquisition card, 12th Workshop on Electronics for LHC and Future Experiments, Valencia, Spain, 2006, p. 108, http://cdsweb.cern.ch/record/1027422
  * [7] E. Effinger et al., Single gain radiation tolerant LHC beam loss acquisition card, Proc. DIPAC, Venice, Italy, 2007. p. 319. http://accelconf.web.cern.ch/Accelconf/d07/papers/wepc06.pdf
  * [8] C. Zamantzas, et al.,  An FPGA based implementation for real-time processing of the LHC beam loss monitoring system’s data, San Diego, 2006, IEEE Nucl. Sci. Symposium Conf. Record (2006), vol. 2, p. 950, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4179157
  * [9] C. Zamantzas, Ph.D. thesis, Brunel University, 2006.
  * [10] G. Guaglio.  Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II, 2005.
  * [11] Reliability software from Isograph – world leaders in reliability, maintenance and safety, http://www.isograph.com
  * [12] C. Zamantzas et al., Reliability tests of the LHC beam loss monitoring FPGA firmware, 14th Beam Instrumentation Workshop, Santa Fe, New Mexico, 2010, https://cds.cern.ch/record/1268403
  * [13] B. Dehning et al., Self testing functionality of the LHC BLM system, 10th European Workshop on Beam Diagnostics and Instrumentation for Particle Accelerators, Hamburg, Germany, 2011, p. 152, https://cds.cern.ch/record/1375171
  * [14] J. Emery, et al., First experiences with the LHC BLM sanity checks, Topical Workshop on Electronics for Particle Physics 2010, Aachen, Germany, 2010 [J. Instrum. 5 (2010) C12044. http://dx.doi.org/10.1088/1748-0221/5/12/c12044], https://cds.cern.ch/record/1321592
  * [15] J. Emery et al., LHC BLM single channel connectivity test using the standard installation, Beam Diagnostics and Instrumentation for Particle Accelerators, Basel, Switzerland, 2009, https://cds.cern.ch/record/1183414
  * [16] E. Nebot Del Busto et al., Handling of BLM abort thresholds in the LHC, 2nd International Particle Accelerator Conference, San Sebastian, Spain, 2011, p. WEPC170, https://cds.cern.ch/record/1379461
  * [17] E. B. Holzer et al., Generation of 1.5 million beam loss threshold values, 11th European Particle Accelerator Conference, Genoa, Italy, 2008, p. THPC147, https://cds.cern.ch/record/1124306
  * [18] M. Nemcic, B.Sc. thesis, University of the West of England, Bristol 2012, http://ab-div-bdi-bl-blm.web.cern.ch/ab-div-bdi-bl-blm/talks_and_papers/Nemcic
  * [19] S. Bhattacharyya, Ph.D. thesis, Ohio State University, 2012.


# Control-DAG: Constrained Decoding for Non-Autoregressive Directed Acyclic T5
using Weighted Finite State Automata

Jinghong Chen, Weizhe Lin, Jingbiao Mei, Bill Byrne
Department of Engineering
University of Cambridge
{jc2124, wl356, jm2245<EMAIL_ADDRESS>
###### Abstract

The Directed Acyclic Transformer is a fast non-autoregressive (NAR) model that
performs well in Neural Machine Translation. Two issues prevent its
application to general Natural Language Generation (NLG) tasks: frequent Out-
Of-Vocabulary (OOV) errors and the inability to faithfully generate entity
names. We introduce Control-DAG, a constrained decoding algorithm for our
Directed Acyclic T5 (DA-T5) model which offers lexical, vocabulary and length
control. We show that Control-DAG significantly enhances DA-T5 on the Schema
Guided Dialogue and the DART datasets, establishing strong NAR results for
Task-Oriented Dialogue and Data-to-Text NLG.

Control-DAG: Constrained Decoding for Non-Autoregressive Directed Acyclic T5
using Weighted Finite State Automata

Jinghong Chen, Weizhe Lin, Jingbiao Mei, Bill Byrne Department of Engineering
University of Cambridge {jc2124, wl356, jm2245<EMAIL_ADDRESS>

##  1 Introduction

Non-autoregressive (NAR) models for text generation offer the promise of much
faster generation than auto-regressive (AR) models. However NAR models have
been largely developed for Neural Machine Translation (NMT) Xiao et al.
(2022), with other Natural Language Generation (NLG) tasks less well studied.
We will show how a NAR model developed for NMT, the Directed Acyclic
Transformer (DAT) (Huang et al., 2022), can be used for generation in Task-
Oriented Dialogue (TOD) and Data-to-Text (D2T) scenarios.

DATs as originally developed for NMT perform poorly in NLG on TOD and D2T
tasks: they fail to generate specified entity names in up to 40% of responses
and frequently (>20%) produce Out-Of-Vocabulary (OOV) words. Practical systems
must operate at zero error rate in these aspects to be deployable at scale.
Previous NAR study reported similar error patterns Xiao et al. (2022). Unless
these shortcomings are addressed, NAR models will not be usable for general
NLG.

We introduce three constrained decoding procedures for NLG using DATs. Our
approach converts Directed Acyclic Graphs (DAG) generated by DAT into Weighted
Finite State Automata (WFSA). We then intersect these WFSAs with other
automata that are defined to ensure that designated entities (lexical
constraints) are generated and OOVs are eliminated (vocabulary constraints).
To avoid generating responses that are too short, we employ a Viterbi decoding
algorithm to control the target length of the generated text (length
constraints).

We refer to the decoding procedure that incorporates all these steps as
Control-DAG. We evaluate extensively on the Schema Guided Dialogue (SGD)
(Rastogi et al., 2020) and the Data Record To Text (DART) datasets (Nan et
al., 2021) for NLG in TOD and D2T domains. Our Directed Acyclic T5 model, when
decoded with Control-DAG, is free from OOV error, faithfully generates all
specified entity names, and achieves marked BLEU and BLEURT gains on both
datasets. We use pynini Gorman (2016) for WFSA operations. Our contributions
are summarized below:

  1. 1.

We introduce Control-DAG, a constrained decoding algorithm which
simultaneously offers lexical, vocabulary, and length controls for Directed
Acyclic models, addressing key limitations in NAR text generation.

  2. 2.

We demonstrate the effectiveness of Control-DAG on two major NLG tasks: Task-
Oriented Dialogues and Data-to-Text. To our knowledge, DA-T5 with Control-DAG
is the first practical NAR benchmark on the SGD and the DART datasets.111Code:
https://github.com/EriChen0615/ControlDAG

Figure 1: Control-DAG with lexical, vocabulary, and length constraints. 1.
Directed Acyclic T5 (DA-T5) takes the input text to generate a Directed
Acyclic Graph (DAG). 2. The DAG is pruned by likelihood, keeping $K_{e}$ most
likely output tokens and $K_{t}$ most likely out-going arcs, and converted
into a Weighted Finite State Automaton (WFSA). We show WFSA vertices and arcs
in the upper-right corner. 3. For lexical and vocabulary constraints,
constraint FSAs are built from equivalent regular expressions (Sec.3.1). The
length target predictor is a simple linear predictor based on the input
sequence length (Sec.4). 4. We intersect the WFSA with constraint FSAs to
obtain a constrained WFSA which only contains hypotheses that satisfy all
lexical and vocabulary constraints. 5. DFS-Viterbi is used to obtain the most
likely string in the constrained WFSA that satisfies the length constraint.

##  2 Related Work

The Directed Acyclic Transformer (DAT) Huang et al. (2022) performs on par
with AR baselines in NMT and has attracted much interests. Shao et al. (2022)
developed a Viterbi decoding algorithm for DAT. Ma et al. (2023) introduced a
fuzzy alignment objective to improve DAT training. In NLG, PreDAT (Huang et
al., 2023) pretrains a DAT for open-domain dialogue, notably with high word
error rate reported even after extensive pre-training. Our work highlights the
links between DATs and automata, and shows well-studied WFSA algorithms Mohri
et al. (2002) can be used in constrained decoding to eliminate OOV errors.

Enforcing lexical constraints in auto-regressive decoding has been studied
extensively. Constrained beam search (CBS) Post and Vilar (2018); Hu et al.
(2019); Li et al. (2020) is a widely used family of lexically constrained
decoding procedure. We show how CBS can be adapted to NAR Directed Acyclic
models.

##  3 Constrained Decoding with DA-T5

The architecture of our DA-T5 model follows that of the DAT by Huang et al.
(2022). Conceptually, DAT takes an input sequence and generates a DAG with a
pre-determined number of DAG vertices. Vertex embeddings are produced first,
and then token emission probabilities and state transition probabilities are
generated from these vertex embeddings via softmax and self-attention, resp.
Each vertex has a token emission distribution. These vertices and transitions
define a weighted DAG that contains output string hypotheses. DAT uses a
vanilla Transformer to produce vertex embeddings whereas we use T5, hence the
name DA-T5.

In training DA-T5, we use ‘glancing training’ Qian et al. (2021) as DAT. In
inference, DAGs are generated with DA-T5 and converted to WFSAs. The procedure
is simply Moore-to-Mealy Machine conversion (Appendix B.1). Prior to the
conversion, we perform likelihood-based pruning of each vertex, keeping
$K_{e}$ most likely output tokens and $K_{t}$ most likely out-going arcs. This
pruning balances coverage against decoding speed, with larger thresholds
leading to a more complete WFSA at the cost of slower decoding.

###  3.1 Constrained Decoding

# | Decoding | BLEURT | BLEU | BLEU-BP | NEO$\downarrow$ | SER$\downarrow$ | Time | Spd. Up
---|---|---|---|---|---|---|---|---
_T5-small (Auto-regressive)_
1 | Greedy | 69.7 | 28.8 | 1.00 | 0.0 | 0.49 | 13:$30$ |  x1.6
2 | Beam search (BS) | 70.2 | 29.1 | 1.00 | 0.0 | 0.12 | 16:0$5$ |  x1.4
3 | Constrained beam (CBS) | 65.6 | 22.5 | 1.00 | 0.0 | 0.0 | 22:$15$ |  x1.0
_Directed Acyclic T5-small (Non-Autoregressive)_
4 | Greedy | 56.0 | 18.3 | 0.92 | 29.7 | 46.3 | 2:$52$ |  x7.8
5 | Beam search | 55.6 | 16.0 | 0.60 | 20.7 | 20.6 | 6:$50$ |  x3.3
6 | CBS-DAG | 59.8 | 21.7 | 0.73 | 19.2 | 0.0 | 5:$57$ |  x3.7
7 | WFSA shortest path | 53.8 | 13.0 | 0.44 | 12.2 | 34.8 | 3:0$4$ |  x7.3
8 | w/ HLC | 58.1 | 20.2 | 0.58 | 11.0 | 0.0 | 5:$16$ |  x4.2
9 | w/ VC | 54.0 | 14.1 | 0.45 | 0.0 | 47.5 | 4:$18$ |  x5.2
10 | w/ LC (DFS-Viterbi) | 58.5 | 20.8 | 1.00 | 21.9 | 45.8 | 3:$31$ |  x6.3
11 | Control-DAG | 60.0 | 22.9 | 1.00 | 0.0 | 0.0 | 13:$14$ |  x1.7
Table 1:  Main results on the SGD dataset. For reference, auto-regressive
T5-small by Kale and Rastogi (2020) achieves 26.2 BLEU and 0.80 SER. BP stands
for the brevity penalty term in computing BLEU. SER stands for Slot Error Rate
in percentage. All speed ups are computed against auto-regressive constrained
beam search. Constrained beam search (Row 3) forces the replication of slot
values that need to appear exactly and hence has zero slot error rate. CBS-DAG
(Row 6) refers to Constrained beam search adapted for Directed Acyclic Graph
introduced in Sec.3.1. HLC refers to Hard Lexical Constraint; VC is Vocabulary
Constraint; and LC is Length Constraint. Control-DAG (Row 11) is WFSA shortest
path decoding with HLC, VC, and LC applied simultaneously.

For hard lexical and vocabulary constraints we build corresponding Finite
State Automata (FSA). Intersecting the WFSA with these constraint FSAs
produces a WFSA that only contains hypotheses that satisfy all constraints
Mohri et al. (2002). For length constraints, we propose a pruned version of
DAT Viterbi decoding by Shao et al. (2022) to search for strings with
specified length. Appendix B gives implementation details and complexity
analyses. Figure 1 illustrates our Control-DAG system with an example.

#### Hard Lexical Constraints (HLC)

For each phrase $C_{i}$ that must appear in the generation, we construct a
constraint FSA $A_{i}$ that accepts and only accepts strings where the phrase
$C_{i}$ appears at least once, corresponding to the regular expression
“$.\ast(C_{i}).\ast$” IEEE (2004). We then intersect the WFSA converted from
the DAG with all of the constraint FSAs. The resulting WFSA $W_{HLC}$ contains
only hypotheses that satisfy all lexical constraints.

#### Vocabulary Constraints (VC)

We build a vocabulary FSA $A_{vocab}$ that accepts and only accepts strings of
words from a valid vocabulary; intersection with $A_{vocab}$ prevents OOV
errors. $A_{vocab}$ is obtained from three FSAs: a dictionary FSA $A_{dict}$
that accepts and only accepts English words; a special token FSA $A_{spec}$
that accepts and only accepts numbers, punctuation, and special tokens; and a
dynamic FSA $A_{dyn}$ that accepts and only accepts entity names specified in
the input. The final vocabulary FSA $A_{vocab}$ is obtained by unioning the
three FSAs and taking the Kleene closure (Eq.1).

$A_{vocab}=(A_{dict}\cup A_{spec}\cup A_{dyn})^{*}$ (1)

For efficiency, we perform a one-time determinization and minimization Mohri
et al. (2002) of the union ($A_{dict}\cup A_{spec}$) and store the optimized
FSA in memory.

#### Length Constraints (LC)

Shao et al. (2022) introduced a Viterbi decoding procedure for DAT that finds
the highest scoring hypothesis for each string length. We find this exact
Viterbi procedure to be impractical because the number of WFSA states can be
large (>30,000) after intersection with the constraint FSAs. We introduce a
pruned version of this procedure, _Depth-First Search Viterbi (DFS-Viterbi)_.
DFS-Viterbi searches the WFSA with DFS and keeps the best hypotheses of all
possible string lengths at each vertex to avoid repeated computation. During
DFS, we only explore the minimal set of out-going edges such that their
cumulative probability is bigger than a threshold $p$. This pruning is
inadmissible but works well in practice. We also introduce an exponential
length penalty that penalizes strings shorter than target length $L_{tgt}$ and
select the hypothesis with the lowest overall costs. In experiments to follow,
$L_{tgt}$ is obtained via simple linear regression.

#### HLC with CBS

In addition to automata-based methods, we introduce CBS-DAG, a constrained
beam search algorithm for our NAR DA-T5. CBS-DAG is straight-forwardly adapted
from AR CBS by Hu et al. (2019) (Appendix B.4).

##  4 Experiments and Results

We evaluate on the SGD and the DART datasets. In SGD, the aim is to generate
natural utterances from dialogue actions (e.g., INFORM(destination=Cambridge))
that contain the specified information. DART is a more general data-to-text
task that takes triplets of (SUBJECT, RELATION, OBJECT) to generate natural
texts. Hyper-parameters and implementation details are in Appendix A.

#### Metrics

We use BLEURT Sellam et al. (2020) and BLEU Papineni et al. (2002) to measure
text quality relative to ground truth text. We also report the BLEU _Brevity
Penalty (BP)_ , as a small BP indicates too short generation. For SGD, we use
Slot Error Rate (SER) Kale and Rastogi (2020) to evaluate lexical
faithfulness. A slot error occurs when a slot value that should be reproduced
exactly (e.g., a phone number) is not in the generated text. For DART, we use
subjects/objects whose string values are always in the ground-truth training
text as hard lexical constraints and propose Exact Occurrence error Rate (EOR)
for evaluation. EOR is the percentage of model responses where at least one of
the string values from these subjects/objects is missing. For OOV errors, we
define _neologism rate (NEO)_ to be the percentage of model’s responses that
contain at least one OOV generation.

We emphasize that SER, EOR, and OOV are critical metrics as even a small error
rate could lead to an intolerable number of misleading responses for systems
deployed at scale. ‘Speed up’ is measured against auto-regressive CBS
implemented by Li et al. (2020) with batch size of 1 to reflect a realistic
NLG system that operates at zero SER/EOR.

#### Training

We train DA-T5 from scratch by glancing training by Qian et al. (2021) on the
SGD and the DART datasets for 30 and 50 epochs, respectively. Auto-regressive
T5 is trained following Chen et al. (2023).

#### Decoding configurations

We use $K_{t}=K_{e}=3$ and $K_{t}=K_{e}=5$ for DAG-to-WFSA conversion on SGD
and DART, respectively. For LC, we fit a simple linear regression model on the
training set to predict the target token length given the input token length.
Decoding hyper-parameters are determined on the validation sets.

###  4.1 Non-Autoregressive NLG on SGD

Decoding | BLEURT | BLEU | NEO | SER
---|---|---|---|---
Greedy | 56.0 | 18.3 | 29.7 | 46.3
Lookahead | 56.6 | 19.3 | 23.0 | 44.6
Viterbi | 52.7 | 13.4 | 12.4 | 50.5
Joint Viterbi | 52.1 | 12.6 | 10.5 | 50.6
Control-DAG | 60.0 | 22.9 | 0.00 | 0.00
Table 2: Performance on the SGD dataset using Control-DAG and other decoding
algorithms in the literature. NEO stands for Neologism rate. Huang et al.
(2022) proposed Lookahead. Shao et al. (2022) introduced Viterbi and Joint
Viterbi.

Table 1 reports NLG performance on SGD with auto-regressive T5 decoding in
Rows 1-2 with greedy and beam search. Although these systems yield high BLEURT
and BLEU, they still commit slot errors (SER=0.12%). Constrained Beam Search
(CBS) eliminates slot errors by forcing the generation of designated slot
values, but with longer decoding times (16:05 $\rightarrow$ 22:15) and a
degradation in BLEU ($-6.6$) and BLEURT ($-4.6$) compared to unconstrained
beam search. This constraint-quality trade-off is also observed in previous
study Post and Vilar (2018); See Appendix D for CBS failure modes. Auto-
regressive T5 is completely free from OOV errors (NEO=0.0).

Turning to non-autogressive NLG, generation with DA-T5 using common decoding
methods (greedy, beam search) leads to very high SER (> 20%) and OOV errors in
at least 20% of the generated responses (Rows 4, 5). Although our CBS-DAG (Row
6) eliminates SER by design and enhances quality as measured by BLEURT (+3.8)
and BLEU (+3.4), its neologism rate is still unusably high (19.2%).

We now discuss the performance of our constrained decoding methods.
Unconstrained WFSA shortest path decoding (Row 7) is as fast as greedy
decoding, showing that DAGs can be efficiently converted to WFSAs. However,
unconstrained generation directly from the WFSA frequently leads to slot
errors (SER=34.8%), OOV errors (NEO=12.2%), and a harsh brevity penalty
(BP=0.44). These aspects of text quality can be improved individually by
constrained decoding (Rows 8-10): Hard Lexical Constrained decoding eliminates
slot errors (SER=0); Vocabulary constraints eliminate OOV errors (NEO=0); and
Length constrained decoding leads to better text lengths (BP=1.0). Control-DAG
(Row 11) combines these methods to achieves zero SER and zero neologism rate
while satisfying the length requirement and yielding a speed advantage of x1.7
relative to auto-regressive CBS.

Table 2 shows the performance of using existing decoding procedures developed
for DA-Transformer to decode DA-T5 on the SGD dataset. Control-DAG has the
overall best BLEU (22.9) and BLEURT (60.0) .

###  4.2 Results on DART

# | Model | BLEURT | BLEU | BP | NEO$\downarrow$ | EOR$\downarrow$ | Time | Spd. Up
---|---|---|---|---|---|---|---|---
_T5-small (Auto-regressive)_
1 | Greedy | 71.2 | 31.3 | 0.95 | 4.1 | 5.0 | 24:$50$ |  x1.3
2 | Beam search | 72.8 | 31.9 | 0.93 | 3.2 | 3.9 | 30:$53$ |  x1.1
3 | Constrained beam | 70.5 | 29.3 | 0.95 | 3.3 | 0.0 | 33:$10$ |  x1.0
_Directed Acyclic T5-small (Non-Autoregressive)_
4 | Greedy | 45.0 | 18.2 | 1.00 | 48.9 | 39.5 | 3:$17$ |  x10.1
5 | Beam search | 45.6 | 14.0 | 0.53 | 34.3 | 43.6 | 9:$29$ |  x3.5
6 | CBS-DAG | 46.0 | 18.9 | 0.80 | 36.1 | 0.0 | 7:$26$ |  x4.5
7 | WFSA shortest | 42.1 | 10.8 | 0.38 | 27.3 | 45.4 | 3:$49$ |  x8.7
8 | w/ HLC | 46.8 | 14.4 | 0.46 | 24.4 | 0.0 | 9:$39$ |  x3.4
9 | w/ VC | 39.3 | 7.7 | 0.28 | 0.0 | 45.1 | 10:$38$ |  x3.1
10 | w/ LC (DFS-Viterbi) | 46.8 | 18.3 | 0.86 | 44.4 | 40.3 | 5:$26$ |  x6.1
11 | CONTROL-DAG | 46.8 | 19.0 | 1.00 | 0.0 | 0.0 | 24:0$3$ |  x1.4
Table 3:  Results on the DART dataset. The naming convention for metrics and
decoding methods follow that in Table 1. EOR is Exact Occurrence Error.

The results on DART (Table 3) validate our findings on the SGD dataset:
Control-DAG yields the best performance while maintaining a speed advantage
and each constrained decoding step contributes as expected. We now contrast
performance on DART and SGD to show how Control-DAG performs on tasks with
very different characteristics.

DART has a challenging vocabulary that causes even AR models to commit OOV
errors. This is also reflected by the much higher neologism rate when decoding
DA-T5 with greedy (48.9% versus 29.7% in SGD). This explains why less
aggressive pruning (top-5) is needed for DART relative to SGD (top-3). We find
the simple procedure of searching the training data for subjects/objects whose
values are exactly reproduced and using them as lexical constraints boosts
DA-T5 performance by +4.7 BLEURT and +3.6 BLEU (Row 8, Table 3). This
demonstrates that hard lexical constraints are effective and easy to apply for
less lexically constrained NLG tasks such as DART.

##  5 Conclusion

We propose Control-DAG for decoding non-autoregressive Directed Acyclic models
with lexical, vocabulary, and length constraints, addressing key limitations
in NAR text generation. Constrained decoding is efficiently performed via
well-studied Weighted Finite State Automata algorithms. DA-T5 with Control-DAG
establishes strong NAR results on the Schema Guided Dialogue and the DART
datasets, bridging gaps in NAR research.

##  6 Acknowledgement

Jinghong Chen is supported by the Warwick Postgraduate Studentship from
Christ’s College and the Huawei Hisilicon Studentship for the undertaking of
the PhD in Engineering at the University of Cambridge.

Weizhe Lin was supported by a Research Studentship funded by Toyota Motor
Europe (RG92562(24020)).

Prof. Bill Byrne holds concurrent appointments as a Professor of Information
Engineering at Cambridge University and as an Amazon Scholar. This publication
describes work performed at Cambridge University and is not associated with
Amazon.

We would also like to thank all the reviewers for their knowledgeable reviews.

##  7 Limitation

Given our focus on decoding algorithms, we leave further training and model
scaling to future work. It is possible to further improve inference speed by
writing the DAG-to-WFSA conversion and the DFS-Viterbi algorithm in the C
programming language to reduce overhead from the python interface. In this
paper, we demonstrate substantial speed-up can be achieved without these
optimizations and leaves further speed-up techniques to future work.

##  8 Ethical Statement

We trained two versions of the DA-T5 model: one on the training set of Schema
Guided Dialogue and one on the training set of the DART dataset. These are
English datasets and do not contain sensitive personal information or
offensive language. Detailed statistics of the SGD and DART datasets can be
found in Rastogi et al. (2020) and Nan et al. (2021), respectively. We note
that the model may hallucinates information or generates language that appears
offensive. Some linguistic phenomena of our DA-T5 models are in Appendix D. It
is vital that developers test DA-T5 fully before deployment.

All software packages that our code built on are used as their original
intention. Our code is released under the MIT license.

## References

  * Chen et al. (2023) Jinghong Chen, Weizhe Lin, and Bill Byrne. 2023.  Schema-guided semantic accuracy: Faithfulness in task-oriented dialogue response generation.  _CoRR_ , abs/2301.12568.
  * Gorman (2016) Kyle Gorman. 2016.  Pynini: A Python library for weighted finite-state grammar compilation.  In _Proceedings of the SIGFSM Workshop on Statistical NLP and Weighted Automata_ , pages 75–80, Berlin, Germany. Association for Computational Linguistics.
  * Hu et al. (2019) J. Edward Hu, Huda Khayrallah, Ryan Culkin, Patrick Xia, Tongfei Chen, Matt Post, and Benjamin Van Durme. 2019.  Improved lexically constrained decoding for translation and monolingual rewriting.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pages 839–850. Association for Computational Linguistics.
  * Huang et al. (2023) Fei Huang, Pei Ke, and Minlie Huang. 2023.  Directed acyclic transformer pre-training for high-quality non-autoregressive text generation.  _CoRR_ , abs/2304.11791.
  * Huang et al. (2022) Fei Huang, Hao Zhou, Yang Liu, Hang Li, and Minlie Huang. 2022.  Directed acyclic transformer for non-autoregressive machine translation.  In _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 9410–9428. PMLR.
  * IEEE (2004) The Open Group IEEE. 2004.  _Chapter 9: Regular Expressions_ , ieee std 1003.1, 2004 edition edition, volume 6, chapter 9. IEEE.  Archived from the original on 2011-12-02. Retrieved 2011-12-13.
  * Kale and Rastogi (2020) Mihir Kale and Abhinav Rastogi. 2020.  Template guided text generation for task-oriented dialogue.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , pages 6505–6520. Association for Computational Linguistics.
  * Li et al. (2020) Zhongyang Li, Xiao Ding, Ting Liu, J. Edward Hu, and Benjamin Van Durme. 2020.  Guided generation of cause and effect.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , pages 3629–3636. ijcai.org.
  * Ma et al. (2023) Zhengrui Ma, Chenze Shao, Shangtong Gui, Min Zhang, and Yang Feng. 2023.  Fuzzy alignments in directed acyclic graph for non-autoregressive machine translation.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net.
  * Mohri et al. (2002) Mehryar Mohri, Fernando Pereira, and Michael Riley. 2002.  Weighted finite-state transducers in speech recognition.  _Comput. Speech Lang._ , 16(1):69–88.
  * Nan et al. (2021) Linyong Nan, Dragomir R. Radev, Rui Zhang, Amrit Rau, Abhinand Sivaprasad, Chiachun Hsieh, Xiangru Tang, Aadit Vyas, Neha Verma, Pranav Krishna, Yangxiaokang Liu, Nadia Irwanto, Jessica Pan, Faiaz Rahman, Ahmad Zaidi, Mutethia Mutuma, Yasin Tarabar, Ankit Gupta, Tao Yu, Yi Chern Tan, Xi Victoria Lin, Caiming Xiong, Richard Socher, and Nazneen Fatema Rajani. 2021.  DART: open-domain structured data record to text generation.  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 432–447. Association for Computational Linguistics.
  * 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 on Association for Computational Linguistics_ , ACL ’02, page 311–318, USA. Association for Computational Linguistics.
  * Post and Vilar (2018) Matt Post and David Vilar. 2018.  Fast lexically constrained decoding with dynamic beam allocation for neural machine translation.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2018, New Orleans, Louisiana, USA, June 1-6, 2018, Volume 1 (Long Papers)_ , pages 1314–1324. Association for Computational Linguistics.
  * Qian et al. (2021) Lihua Qian, Hao Zhou, Yu Bao, Mingxuan Wang, Lin Qiu, Weinan Zhang, Yong Yu, and Lei Li. 2021.  Glancing transformer for non-autoregressive neural machine translation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021_ , pages 1993–2003. Association for Computational Linguistics.
  * Rastogi et al. (2020) Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan. 2020.  Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 8689–8696.
  * Sellam et al. (2020) Thibault Sellam, Dipanjan Das, and Ankur P. Parikh. 2020.  BLEURT: learning robust metrics for text generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 7881–7892. Association for Computational Linguistics.
  * Shao et al. (2022) Chenze Shao, Zhengrui Ma, and Yang Feng. 2022.  Viterbi decoding of directed acyclic transformer for non-autoregressive machine translation.  In _Findings of the Association for Computational Linguistics: EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022_ , pages 4390–4397. Association for Computational Linguistics.
  * Tyler Barrus (2018) Tyler Barrus. 2018.  Pyspellchecker: Pure Python Spell Checking.  https://pypi.org/project/pyspellchecker/.  Python version: 3.
  * Xiao et al. (2022) Yisheng Xiao, Lijun Wu, Junliang Guo, Juntao Li, Min Zhang, Tao Qin, and Tie-Yan Liu. 2022.  A survey on non-autoregressive generation for neural machine translation and beyond.  _CoRR_ , abs/2204.09269.

##  Appendix A Experiment setup details

#### Metrics details

For BLEURT, we use the BLEURT-20 checkpoint. For BLEU, we use the sacrebleu
implementation. Decoding times are average of three runs on a single A100 GPU
for the SGD dataset and on a single V100 GPU for the DART dataset.

#### Vocabulary for neologism evaluation

From the entire corpus, we extract all space-delimited words, strip
punctuation and numbers, and maintain true cases. All words in the test corpus
are also added to the evaluation vocabulary without pre-processing. Note that
they are not added to the constraint vocabulary for VC decoding to avoid
leakage. For the SGD, we also add all words in the slot names, slot values,
and slot descriptions from the schema, resulting in a vocabulary of 19,126
words. In evaluation, we only strip punctuation from words in the generated
texts. We also use the pyspellchecker library Tyler Barrus (2018) to check
that the word in question is indeed OOV.

#### Exact Occurrence Error

We go through the training data to identify subjects/objects that are always
present in the ground-truth text. For example, we find that the subject of the
relation priceRange always appear in the ground-truth text. Whenever
priceRange appears during testing, we treat the string value of its subject as
hard lexical constraints. If the string cannot be found in the generated text,
an exact occurrence error is flagged.

#### Data Preprocessing

We linearize the input dialogue actions or triplets to strings as input to our
DA-T5 model. On the SGD, we follow the Schema Guided Linearization by Kale and
Rastogi (2020) to process our input data. On DART, we process the triplets
into arrays of ‘‘<h> SUBJECT <r> RELATION <t> OBJECT’’ where <h>, <r>, and <t>
are special tokens.

#### Training hyper-parameters

The DAG vertex size $L$ is determined by the upsample factor $\lambda$
($L=\lambda\times N$ where $N$ is the input length) with $\lambda=5$ for both
the SGD and the DART datasets. We use the T5-small architecture with randomly
initialized weights to generate vertex embeddings (79.3M trainable
parameters). We train the model with a learning rate of 1e-4, a batch size of
8 using the AdamW optimizer. Glancing training is used to facilitate training
with a constant annealing factor $\tau=1.0$. SGD training took around 13 hours
(25 minutes per epoch) on a single A100 GPU including all validation runs.
DART training took 24 hours on a single V100 GPU. We find that glancing
training is critical to successful training. Without it the model performs
poorly (4.6 BLEU on the SGD when decoded with Greedy).

#### Target length predictor

Let $x$ be the input length in tokens, $L_{tgt}=\lceil 26.1x+0.4\rceil$ for
the SGD and $L_{tgt}=\lceil 0.5x+11.9\rceil$ for DART. Coefficients are fitted
on the validation set. We use strictness $A=1$ in LC decoding.

#### Beam search

Auto-regressive Beam Search (BS) and Constrained Beam Search (CBS) use beam
size $=5$. CBS-DAG uses a base beam size of $4$ with dynamic adjustment
(Sec.B.4).

##  Appendix B Algorithmic details

###  B.1 DAG-to-WFSA conversion

A Weighted FSA (WFSA) consists of states and weighted directed arcs connecting
the states. The outputs (tokens) are labeled on the arcs. DAG-to-WFSA is
simply Moore Machine to Mealy Machine conversion by treating DAG vertices as
WFSA states and exploding the output tokens at DAG vertices to WFSA arc
labels. WFSA arc weights are the sum of negative log-likelihood for state
transition and token emission. The best path has maximal likelihood.

We prune the DAG before conversion to reduce the number of WFSA arcs. For each
vertex $u$ in the DAG, we only keep the top $K_{e}$ tokens and top $K_{t}$
transitions in descending probabilities. We also keep tokens that appear in
the constraint phrases, ensuring there exists paths that realize lexical
constraints in the WFSA (Algo.2). Algo.1 shows pseudo-code. $\times$ denotes
Cartesian product.

Algorithm 1 DAG to WFSA conversion

1:Inputs: DAG vertices $V$, transition matrix $E$, emission matrix $P$,
emission degree $K_{e}$ and transition degree $K_{t}$. Lexical constraint
phrases $\mathcal{C}=[C_{1},...,C_{M}]$.

2:$\mathcal{E}\leftarrow\emptyset$

3:for $u\in\text{topological\\_sort}(V)$ do

4: $\mathcal{T}[u]\leftarrow\arg\text{topk}(P[u,:],K_{e})$

5: $\mathcal{S}[u]\leftarrow\arg\text{topk}(E[u,:],K_{t})$

6: $\mathcal{T}[u]\leftarrow\mathcal{T}[u]\ \cup$ ForceEmit($u,\mathcal{C}$)

7:$\triangleright$ Forced emission (Algo.2)

8: for $t,v\in\mathcal{T}[u]\times\mathcal{S}[u]$ do

9: $w=-(\log P[u,t]+\log E[u,v])$

10: $e\leftarrow\left(u,t,w,v\right)$

11: $\mathcal{E}\leftarrow\mathcal{E}\cup\\{e\\}$

12: end for

13:end for

14:Construct the WFSA with edge set $\mathcal{E}$

Finding the shortest path has linear complexity in the number of edges because
our WFSA is acyclic. The pruning parameters, $K_{t}$ and $K_{e}$, trades of
completeness with decoding speed. Larger values lead to a more complete WFSA
at the cost of longer decoding time.

Algorithm 2 The ForceEmit function

1:Inputs: Vertex predecessors under top-K transition pruning
$N_{K_{t}}^{-}(v)$. Lexical constraint phrases
$\mathcal{C}=[C_{1},...,C_{M}]$. Emission tokens at all predecessor vertices
$\mathcal{T}[\cdot]$

2:function ForceEmit($u,\mathcal{C}$)

3: $\mathcal{F}\leftarrow\emptyset$

4: for phrase $C_{i}\in\mathcal{C}$ do

5: for token $t_{j}$ in $C_{i}[:-1]$ do

6: for $v\in N_{K_{t}}^{-}(u)$ do

7: if $t_{j}\in\mathcal{T}[v]$ then

8: $\mathcal{F}\leftarrow\mathcal{F}\cup\\{t_{j+1}\\}$

9:$\triangleright$ Force-emit the next token $t_{j+1}$ in phrase $C_{i}$

10: end if

11: end for

12: end for

13: end for

14: return $\mathcal{F}$

15:end function

###  B.2 Vocabulary Constraint

We elaborate on how to construct the FSAs for vocabulary constraints below:

#### Dictionary FSA

From the training corpus, we extract space-delimited unigrams, strip numbers
and punctuation, sort them in descending frequency, and cutoff at 90%
cumulative frequency. This results in a vocabulary $V$ of 1129 words on the
SGD dataset. We then tokenize each unigram with the T5 tokenizer, build FSA
that accepts and only accepts the tokenized sequence (e.g. ‘‘photosynthesis’’
$\rightarrow$ ‘‘_photo’’, ‘‘synthesis’’), and union these FSAs to form the
dictionary FSA $A_{dict}$.

#### Special token FSA

$A_{spec}$ accepts and only accepts punctuation “$&’()*+,-./:;=>?@[]_”, start-
of-sentence <s>, end-of-sentence token </s>, and T5 tokenizer’s start-of-word
mark (u2581 “_”).

#### Dynamic FSA

: $A_{dyn}$ is built for each input. Given the entity names, we tokenize them,
build FSAs that accepts and only accepts the token sequence for each entity,
and take the union. Note that entity names may include space. For example,
$A_{dyn}$ may accept “Hong Kong” but not the constituent unigrams “Hong” and
“Kong”.

###  B.3 Length Constraint

Algo.3 lists the DFS-Viterbi algorithm and the symbol definitions. The
recursive relation is given in Eq.2. For each vertex, we memoize the current
best string of each length and their costs. The shortest path is recovered
with parent pointers.

$\delta(u,l+1)=\min_{v\in N^{+}_{p}(u)}w(u,v)+\delta(v,l)$ (2)

We fit a first-order linear model to predict target length $L_{tgt}$ from
input length. Length is measured in tokens and coefficients are given in
Appendix A. Enforcing a strict length constraint can lead to incomplete
sentences. Therefore, we find the best $l-$length string for
$l=1,\ldots,L_{upper}$, where $L_{upper}=\min(L_{tgt}+5,L_{tgt}\times 1.5)$
and introduce an exponential length penalty (Eq.3) similar to BLEU. The
candidate with the lowest overall cost $C^{\prime}$ (Eq.4) is chosen as the
final generation. We use simple linear regression to specify the length target
$L_{tgt}$.

$\displaystyle LP=\begin{cases}\exp\big{(}A(L_{tgt}/l-1)\big{)},&\text{if
}l<L_{tgt}\\\ 1,&\text{otherwise}\end{cases}$ (3) $\displaystyle
C^{\prime}=LP\times\delta(u_{s},l)$ (4)

The WFSA software implementation, pynini Gorman (2016), allows us to
efficiently traverse the WFSA as graphs. Prior to running DFS-Viterbi, we sort
the WFSA states topologically and perform epsilon-removal Mohri et al. (2002).
Epsilon transitions do not have actual token labels, and are removed to
prevent over-counting the output length. The WFSA can be topologically sorted
because intersection preserves the acyclic property of its input: any cycles
will result in strings of unbounded length which cannot be accepted by the
acyclic WFSA.

Let $|V|$ be the number of WFSA states. The space complexity of memoization is
$O(L_{tgt}\times|V|)$. The worst-case time complexity is exponential
$O(L_{tgt}^{|V|})$. However, we observe a linear time complexity of
$O(L_{tgt})$ when applying DFS-Viterbi to our trained DA-T5 model. We
attribute the efficiency to: (1) memoization; (2) transition probabilities are
concentrated on a few successors. We find that the number of out-going edges
after pruning, $|N_{p}^{+}(u)|$, approximates 1 when $p=0.7$, leading to very
efficient search.

Algorithm 3 DFS-Viterbi finds the shortest path with exactly $L_{tgt}$ edges.

1:function DFS-Viterbi($u$, $l$, $\delta$, $L_{tgt}$, $N^{+}$, $w$)

2: Arguments:

3: $u$: current vertex.

4: $l$: target length (number of edges) from vertex $u$ to a final vertex.

5: $\delta$: memoization table storing shortest distance to vertex $u$ with
exactly $l$ edges.

6: $F$: set of final states (vertices).

7: $N^{+}_{p}(u)$: minimal set of successors of vertex $u$ with cumulative
probability $>p$.

8: $w(u,v)$: edge weight from vertex $u$ to $v$.

9: if $v$ is in $F$ then

10: return $0$

11: end if

12: if $\delta[u,l]$ is not NULL then

13: return $\delta[u,l]$

14: end if

15: $\text{min\\_distance}\leftarrow\infty$

16: for all $v\in N^{+}(u)$ do

17: $\text{dist}\leftarrow w(u,v)+$ DFS-Viterbi($v,l+1,\delta,F,N^{+},w$)

18: if $\text{dist}<\text{min\\_distance}$ then

19: $\text{min\\_distance}\leftarrow\text{dist}$

20: end if

21: end for

22: $\delta[u,l]\leftarrow\text{min\\_distance}$

23: return min_distance

24:end function

###  B.4 Constrained Beam Search for Directed Acyclic Graphs (CBS-DAG)

CBS-DAG follows the beam expansion and pruning rules in Dynamic Beam
Allocation (DBA) Post and Vilar (2018). Let $K$ be the beam size. At each
vertex transition, CBS-DAG extends the beam with the top-$K$ tokens from model
prediction, the next token in active constraints, and the first token in non-
active constraints. Active constraints are identified by the KMP string-
matching algorithm. After beam expansion, we regroup the candidates into
“banks” by the number of unmet constraint tokens and retain the most likely
candidate within each bank. We dynamically adjust the beam size such that beam
size is always larger than the number of non-empty banks (i.e., the number of
constraint tokens plus one).

##  Appendix C Further Analysis

#### DA-T5 produces sparse DAGs

We find that DA-T5 learns to produce a sparse DAG in the following sense: on
average, each vertex has 1.68 transitions with probability $>0.2$ and 1.58
emissions with probability $>0.2$ after training. These statistics are
computed over the validation set, and explain why we can prune aggressively
during WFSA-to-DAG conversion (top-3 for the SGD and top-5 for DART) for speed
without much loss of information.

##  Appendix D Qualitative Study

Figure 2: Case study comparing DA-T5 with Control-DAG, Joint Viterbi, and CBS-
DAG decoding on the SGD dataset.