Template-based text generation

Deep dive

How it works

In: a list of typed facts per entity (counts, ranks, names) and a seed · Out: a text in which every number and name comes from the facts · State: set of entities already mentioned, last sentence's subject, last template index per message type, RNG state · Cost: O(output length)

1. Content selection: keep facts that pass salience rules (thresholds; "zero goals" is dropped), before the realiser.
2. Sentence planning: order messages; aggregate facts with the same subject into one sentence.
3. Lexical choice: fixed verb and noun per fact type.
4. Referring expressions: full name at first mention, pronoun when the previous sentence had the same subject, else the short name.
5. Template choice: pick one of k alternatives with a seeded RNG, never the one used last for that message type.
6. Surface realisation: fill each {slot} from data; apply morphology (plural by count, ordinal suffix, number format).
7. Join sentences with a space; escape for the output channel (HTML, SMS) last.

Code

use std::fmt::Write;

#[derive(Clone, Copy)]
pub enum Fact { Goals(u32), Assists(u32), Rank(u32), Season(u32) }
pub struct Person<'a> { pub full: &'a str, pub short: &'a str, pub pron: &'a str, pub facts: &'a [Fact] }

/// "1 goal", "0 goals", "2 goals": English CLDR categories one / other.
pub fn count(n: u32, one: &str, other: &str, out: &mut String) {
    write!(out, "{n} {}", if n == 1 { one } else { other }).unwrap();
}
pub fn ordinal(n: u32, out: &mut String) {
    let suffix = match (n % 100, n % 10) { (11..=13, _) => "th", (_, 1) => "st", (_, 2) => "nd", (_, 3) => "rd", _ => "th" };
    write!(out, "{n}{suffix}").unwrap();
}
fn times(n: u32, out: &mut String) {
    match n { 1 => out.push_str("once"), 2 => out.push_str("twice"), _ => write!(out, "{n} times").unwrap() }
}

/// Fill `{slot}`s from `slots`; every value comes from the data, so nothing can be invented.
fn expand(tpl: &str, slots: &[(&str, &str)], out: &mut String) {
    let mut rest = tpl;
    while let Some(i) = rest.find('{') {
        out.push_str(&rest[..i]);
        let j = rest[i..].find('}').expect("unclosed slot") + i;
        let key = &rest[i + 1..j];
        let val = slots.iter().find(|s| s.0 == key).expect("unknown slot").1;
        out.push_str(val);
        rest = &rest[j + 1..];
    }
    out.push_str(rest);
}

const A: [&str; 3] = ["{S} {C}.", "Meanwhile, {S} {C}.", "On the day, {S} {C}."];
const RANK: [&str; 2] = ["{S} finished {O}.", "{S} came in {O}."];
const SEASON: [&str; 2] = ["{S} has {N} this season.", "{S} is up to {N} this season."];

pub struct Realiser { state: u64, last: [usize; 3] }
impl Realiser {
    pub fn new(seed: u64) -> Self {
        let s = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) ^ 0xD1B5_4A32_D192_ED03;
        Realiser { state: if s == 0 { 1 } else { s }, last: [usize::MAX; 3] }
    }
    fn pick(&mut self, kind: usize, k: usize) -> usize { // xorshift64, never the same template twice in a row
        self.state ^= self.state << 13; self.state ^= self.state >> 7; self.state ^= self.state << 17;
        let mut i = (self.state >> 11) as usize % k;
        if i == self.last[kind] { i = (i + 1) % k; }
        self.last[kind] = i;
        i
    }
    /// Referring expression: full name at first mention, pronoun right after the same subject (templates
    /// using it start with {S}), else short name.
    fn subject<'a>(p: &Person<'a>, mentioned: &mut bool, prev_same: bool) -> &'a str {
        if !*mentioned { *mentioned = true; p.full } else if prev_same { p.pron } else { p.short }
    }
    pub fn report(&mut self, people: &[Person], out: &mut String) {
        let mut mentioned = vec![false; people.len()];
        let mut prev: Option<usize> = None;
        let mut sent = |this: &mut Self, who: usize, kind: usize, tpls: &[&str], slots: &[(&str, &str)], out: &mut String| {
            let s = Self::subject(&people[who], &mut mentioned[who], prev == Some(who));
            let mut all = vec![("S", s)]; all.extend_from_slice(slots);
            if !out.is_empty() { out.push(' '); }
            expand(tpls[this.pick(kind, tpls.len())], &all, out);
            prev = Some(who);
        };
        for (i, p) in people.iter().enumerate() {
            let mut clauses: Vec<String> = Vec::new(); // aggregation: one sentence per subject
            for f in p.facts {
                let mut c = String::new();
                match *f {
                    Fact::Goals(n) if n > 0 => { c.push_str("scored "); if n <= 2 { times(n, &mut c) } else { count(n, "goal", "goals", &mut c) } }
                    Fact::Assists(n) if n > 0 => { c.push_str("assisted "); times(n, &mut c) }
                    _ => continue,
                }
                clauses.push(c);
            }
            let joined = match clauses.len() { 0 => String::new(), 1 => clauses[0].clone(), n => format!("{} and {}", clauses[..n - 1].join(", "), clauses[n - 1]) };
            if !joined.is_empty() { sent(self, i, 0, &A, &[("C", &joined)], out); }
            for f in p.facts { if let Fact::Rank(n) = *f { let mut o = String::new(); ordinal(n, &mut o); sent(self, i, 1, &RANK, &[("O", &o)], out); } }
        }
        for (i, p) in people.iter().enumerate() {
            for f in p.facts { if let Fact::Season(n) = *f { let mut c = String::new(); count(n, "goal", "goals", &mut c); sent(self, i, 2, &SEASON, &[("N", &c)], out); } }
        }
    }
}

fn main() {
    let ppl = [Person { full: "Ana Kovac", short: "Kovac", pron: "She", facts: &[Fact::Goals(2), Fact::Assists(1), Fact::Rank(22)] }];
    let mut out = String::new();
    Realiser::new(1).report(&ppl, &mut out);
    println!("{out}"); // "On the day, Ana Kovac scored twice and assisted once. She came in 22nd."
}

Checked in a scratch crate (not shown): exact text per seed; over 1000 seeds every number and capitalised name in the output is in the input and none is dropped; same seed, same text; ordinal and plural edge cases 0, 1, 2, 11, 12, 13, 21, 22, 23, 111.

Complexity and constants

• O(output length); one pass over facts, no search.
• Measured on this Mac (Apple M4 Pro, one core, release): 1,000,000 reports of 7 sentences (218 bytes each) in 1.3 s: about 0.76 M reports/s, 5.3 M sentences/s. This version allocates per report (clause Vec, format!).

Efficiency

• Cost: about 190 ns per sentence on this Mac (Apple M4 Pro, one core), measured above; bound is compute and allocation, not memory or I/O. No energy or $ figure measured.
• Levers:
  • write into one reused String buffer — avoids a per-text allocation (design of the code above) — any hot path
  • precompile templates into segment lists (literal, slot) — skips scanning for { at runtime (gain not measured here) — templates fixed at build time
  • drop the per-report Vec/format! — removes the remaining allocations (not measured) — high volume
• Naive → standard → state of the art:
  • string concatenation with if n == 1 · fast, not translatable
  • templates with slots, plural categories, seeded variants · about 5 million sentences/s (measured above)
  • templates plus a small language model paraphrase, rejected if its numbers or names differ from the input · model cost per text (no figure sourced), facts stay exact

Implementation notes

• Localization: a template per language and CLDR plural category (English one/other; Russian one/few/many/other; Arabic zero/one/two/few/many/other; Japanese other only); ordinals have their own rules. Express it as ICU MessageFormat ({n, plural, one {# goal} other {# goals}}) or Fluent selectors, not code.
• Gender, case, article agreement: store gender per entity (the pron field) and case forms per slot value; a bare name breaks in inflected languages.
• Number and unit formatting is locale-specific (decimal comma, separators): format in the realiser, not in the data.
• Escape for the channel (HTML, SMS) after substitution.
• Test with golden files per seed plus a coverage check of numbers and names against the input.
• Avoid monotony: several templates per message, no immediate repeat, aggregation; log the seed to reproduce a text.

Pitfalls

• Choosing plurals with n == 1: wrong for 0 in some languages, wrong for few/many languages.
• Ordinals by n % 10 alone: "11st", "12nd", "13rd".
• Pronoun with another entity in between: use the name unless the previous sentence has the same subject.
• Concatenated fragments: word order differs by language; translate whole sentences.
• Silent fallbacks for missing data ("null goals"): skip the fact.

Variants and alternatives

In production

• Rule- and template-based data-to-text is the long-standing approach for weather forecasts, sports and financial reports, health summaries, product descriptions and alerts (applications surveyed by Gatt and Krahmer 2018). SimpleNLG was originally developed by Ehud Reiter at Aberdeen (its README).

Implementations

Sources

• Reiter, Dale, Building applied natural language generation systems, Natural Language Engineering 1997. paper
• Gatt, Krahmer, Survey of the State of the Art in Natural Language Generation: Core tasks, applications and evaluation, JAIR 2018. paper
• Gatt, Reiter, SimpleNLG: A Realisation Engine for Practical Applications, ENLG 2009. paper · code
• Wiseman, Shieber, Rush, Challenges in Data-to-Document Generation, 2017. paper
• Unicode CLDR, Language Plural Rules. spec