This blog reviews the dynamic beam allocation (DBA) algorithm for constrained text generation.
You can find more details about the DBA algorithm in this paper:
Here, we use the following running example to illustrate this algorithm.
Assume the beam size is 5, and the constraints are as follows:
The vocabulary is something like this:
V = {-s, -ies, -ed, -ing, a, to, its, the, of, in, and, has, have, been, both, from, between, since, former, latter, late, close, relation, 18th, United, Kingdom, States, US, UK, Great, Britain, ranged, close, allay, all-, military, rival, rival, opponent, declare, independence, century, …}.The following sentences satisfy all the constraints.
The DBA algorithm does something that we term "force-and-group", where the core idea is to inject the tokens that attempt to fulfill the constraints at every generation step.
In particular, it performs the following three tasks at every time step:
EXTEND: find the top k most probable next tokens at each branch and append them for consideration. It is precisely the same as the EXTEND step in the traditional beam search.
FORCE: append the additional tokens that will take us closer to fulfilling our constraints.
GROUP: group the extended hypotheses by the number of constraints satisfied. After grouping, we sort all the possible hypotheses into their respective subgroups. Then, a Round-Robin Selection is performed, that is, selecting the most probable output from each subgroup in turn.
Running Example
Presented below are the first two steps of the DBA algorithm for this running example:
Issues of DBA
At time step 3, we observed some undesirable behavior:
"allies America" is syntactically incorrect, but since "America" is forced into the output, and at least 2 slots in the beam are reserved for the group of prefixes that satisfy two constraints, we have to allocate a precious slot for this nonsensical output.
More formally, that means DBA tends to prioritize sequences that satisfy constraints greedily. This led to the nontrivial problem of generating nonsensical outputs.
Another issue is that it often collapses into very similar search paths that are globally suboptimal, resulting in unnatural, repetitive, and incoherent text. This problem is caused by the conflict between limited slots in the beam and the number of subgroups corresponding to different constraint satisfaction stages.
For example, in our running example, it's imaginable there would be many sentences starting with "the" in the final beam. In contrast, the example sentence (2), even though satisfying all the constraints, can never be returned due to this greedy mechanism.
Finally, different constraints may compete for the completion of the same hypothesis, leading to suboptimal solutions. For instance, "ally" and "allies" were competing with each other at every time step in the running example.
Comments