use std::collections::HashMap;
use burn::{
Tensor,
tensor::activation::log_softmax,
};
use crate::kits::speech::whisper::decode::TokenDecoder;
#[derive(Debug, Clone, Default)]
struct Finished {
entries: Vec<(Vec<i64>, f32)>,
}
impl Finished {
fn len(&self) -> usize {
self.entries.len()
}
fn score_sequence(
&mut self,
sequence: Vec<i64>,
score: f32,
) {
match self.entries.iter_mut().find(|(s, _)| *s == sequence) {
Some(entry) => entry.1 = score,
None => self.entries.push((sequence, score)),
}
}
fn clip_tails(
&self,
offset: usize,
stop_token: i64,
) -> Vec<(Vec<i64>, f32)> {
self.entries
.iter()
.map(|(sequence, score)| {
let end = sequence[offset..]
.iter()
.position(|&t| t == stop_token)
.map_or(sequence.len(), |i| offset + i);
(sequence[offset..end].to_vec(), *score)
})
.collect()
}
}
#[derive(Debug, Clone)]
pub struct WhisperBeamSearchDecoder {
k: usize,
stop_token: i64,
max_candidates: usize,
finished: Option<Vec<Finished>>,
}
impl WhisperBeamSearchDecoder {
pub fn new(
beam_size: usize,
stop_token: i64,
patience: Option<f64>,
) -> Self {
assert!(beam_size >= 1, "a beam search needs at least one beam");
let patience = patience.unwrap_or(1.0);
let max_candidates = (beam_size as f64 * patience).round() as usize;
assert!(
max_candidates > 0,
"invalid beam size ({beam_size}) or patience ({patience})"
);
Self {
k: beam_size,
stop_token,
max_candidates,
finished: None,
}
}
pub fn beam_size(&self) -> usize {
self.k
}
pub fn max_candidates(&self) -> usize {
self.max_candidates
}
}
impl TokenDecoder for WhisperBeamSearchDecoder {
fn group_size(&self) -> usize {
self.k
}
fn reset(&mut self) {
self.finished = None;
}
fn update(
&mut self,
tokens: &mut Vec<Vec<i64>>,
logits: Tensor<2>,
sum_logprobs: &mut [f32],
reorder: &mut dyn FnMut(&[usize]),
) -> (Vec<i64>, bool) {
let k = self.k;
let rows = tokens.len();
assert_eq!(
rows % k,
0,
"{rows} rows is not a whole number of {k}-beam groups"
);
let n_audio = rows / k;
let finished = self
.finished
.get_or_insert_with(|| vec![Finished::default(); n_audio]);
let (values, indices) = log_softmax(logits, 1).topk_with_indices(k + 1, 1);
let values: Vec<f32> = values.into_data().try_into_vec_as::<f32>().unwrap();
let indices: Vec<i64> = indices.into_data().try_into_vec_as::<i64>().unwrap();
let mut next: Vec<Vec<i64>> = Vec::with_capacity(rows);
let mut next_sums: Vec<f32> = Vec::with_capacity(rows);
let mut sources: Vec<usize> = Vec::with_capacity(rows);
let mut newly_finished: Vec<Finished> = Vec::with_capacity(n_audio);
for audio in 0..n_audio {
let mut candidates: Vec<(Vec<i64>, f32, usize)> = Vec::with_capacity(k * (k + 1));
let mut position: HashMap<Vec<i64>, usize> = HashMap::with_capacity(k * (k + 1));
for beam in 0..k {
let row = audio * k + beam;
for c in 0..=k {
let token = indices[row * (k + 1) + c];
let score = sum_logprobs[row] + values[row * (k + 1) + c];
let mut sequence = tokens[row].clone();
sequence.push(token);
match position.get(&sequence) {
Some(&at) => {
candidates[at].1 = score;
candidates[at].2 = row;
}
None => {
position.insert(sequence.clone(), candidates.len());
candidates.push((sequence, score, row));
}
}
}
}
let mut order: Vec<usize> = (0..candidates.len()).collect();
order.sort_by(|&a, &b| candidates[b].1.total_cmp(&candidates[a].1));
let mut done = Finished::default();
let mut saved = 0;
for &c in &order {
let (sequence, score, source) = &candidates[c];
if sequence.last() == Some(&self.stop_token) {
done.score_sequence(sequence.clone(), *score);
} else {
next_sums.push(*score);
next.push(sequence.clone());
sources.push(*source);
saved += 1;
if saved == k {
break;
}
}
}
assert_eq!(saved, k, "fewer than {k} live candidates for audio {audio}");
newly_finished.push(done);
}
reorder(&sources);
*tokens = next;
sum_logprobs.copy_from_slice(&next_sums);
for (previously, newly) in finished.iter_mut().zip(newly_finished) {
let mut entries = newly.entries;
entries.sort_by(|a, b| b.1.total_cmp(&a.1));
for (sequence, score) in entries {
if previously.len() >= self.max_candidates {
break;
}
previously.score_sequence(sequence, score);
}
}
let completed = finished.iter().all(|f| f.len() >= self.max_candidates);
let feed = tokens
.iter()
.map(|s| *s.last().expect("non-empty"))
.collect();
(feed, completed)
}
fn finalize(
&mut self,
tokens: Vec<Vec<i64>>,
sum_logprobs: Vec<f32>,
prompt_len: usize,
) -> Vec<Vec<(Vec<i64>, f32)>> {
let k = self.k;
let n_audio = tokens.len() / k;
let mut finished = self
.finished
.take()
.unwrap_or_else(|| vec![Finished::default(); n_audio]);
for (audio, set) in finished.iter_mut().enumerate() {
if set.len() < k {
let mut order: Vec<usize> = (0..k).collect();
order.sort_by(|&a, &b| {
sum_logprobs[audio * k + b].total_cmp(&sum_logprobs[audio * k + a])
});
for beam in order {
let row = audio * k + beam;
let mut sequence = tokens[row].clone();
sequence.push(self.stop_token);
set.score_sequence(sequence, sum_logprobs[row]);
if set.len() >= k {
break;
}
}
}
}
finished
.into_iter()
.map(|f| f.clip_tails(prompt_len, self.stop_token))
.collect()
}
}
#[cfg(test)]
mod tests {
use burn::{
prelude::TensorData,
tensor::Device,
};
use super::*;
use crate::support::testing::{
DeviceMemoryGuard,
performance_device,
};
fn logits(
rows: &[&[f32]],
device: &Device,
) -> Tensor<2> {
let vocab = rows[0].len();
let flat: Vec<f32> = rows.iter().flat_map(|r| r.iter().copied()).collect();
Tensor::from_data(TensorData::new(flat, [rows.len(), vocab]), device)
}
const EOT: i64 = 0;
#[test]
#[serial_test::serial]
fn test_first_step_deduplicates() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let mut decoder = WhisperBeamSearchDecoder::new(3, EOT, None);
let mut tokens = vec![vec![7]; 3];
let mut sums = vec![0.0; 3];
let mut sources = Vec::new();
let mut reorder = |s: &[usize]| sources = s.to_vec();
let row: &[f32] = &[-9.0, -9.0, 1.0, 2.0, 3.0];
let (feed, done) = TokenDecoder::update(
&mut decoder,
&mut tokens,
logits(&[row, row, row], &device),
&mut sums,
&mut reorder,
);
assert_eq!(tokens, vec![vec![7, 4], vec![7, 3], vec![7, 2]]);
assert_eq!(feed, vec![4, 3, 2]);
assert!(!done);
assert_eq!(sources, vec![2, 2, 2]);
assert!(sums[0] > sums[1] && sums[1] > sums[2]);
}
#[test]
#[serial_test::serial]
fn test_finished_set_and_patience() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let mut decoder = WhisperBeamSearchDecoder::new(2, EOT, None);
assert_eq!(decoder.beam_size(), 2);
assert_eq!(decoder.max_candidates(), 2);
let mut tokens = vec![vec![7]; 2];
let mut sums = vec![0.0; 2];
let mut reorder = |_: &[usize]| {};
let row: &[f32] = &[3.0, -9.0, 1.0, 2.0];
let (feed, done) = TokenDecoder::update(
&mut decoder,
&mut tokens,
logits(&[row, row], &device),
&mut sums,
&mut reorder,
);
assert_eq!(tokens, vec![vec![7, 3], vec![7, 2]]);
assert_eq!(feed, vec![3, 2]);
assert!(!done, "one finished, two wanted");
let (_, done) = TokenDecoder::update(
&mut decoder,
&mut tokens,
logits(&[row, row], &device),
&mut sums,
&mut reorder,
);
assert!(done);
let out = TokenDecoder::finalize(&mut decoder, tokens, sums, 1);
assert_eq!(out.len(), 1);
assert_eq!(out[0].len(), 2);
assert_eq!(out[0][0].0, Vec::<i64>::new());
assert_eq!(out[0][1].0, vec![3]);
assert!(out[0][0].1 > out[0][1].1);
}
#[test]
#[serial_test::serial]
fn test_patience_and_finalize_fill() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let mut decoder = WhisperBeamSearchDecoder::new(2, EOT, Some(2.0));
assert_eq!(decoder.max_candidates(), 4);
let mut tokens = vec![vec![7]; 2];
let mut sums = vec![0.0; 2];
let mut reorder = |_: &[usize]| {};
let row: &[f32] = &[-9.0, -9.0, 1.0, 2.0];
let (_, done) = TokenDecoder::update(
&mut decoder,
&mut tokens,
logits(&[row, row], &device),
&mut sums,
&mut reorder,
);
assert!(!done);
assert_eq!(tokens, vec![vec![7, 3], vec![7, 2]]);
let out = TokenDecoder::finalize(&mut decoder, tokens, sums, 1);
assert_eq!(
out[0].len(),
2,
"filled up to the beam size from live beams"
);
assert_eq!(out[0][0].0, vec![3], "the better live beam first");
assert_eq!(out[0][1].0, vec![2]);
}
#[test]
#[serial_test::serial]
fn test_groups_are_independent() {
let device = performance_device();
let _memory = DeviceMemoryGuard::new(&device);
let mut decoder = WhisperBeamSearchDecoder::new(2, EOT, None);
let mut tokens = vec![vec![7]; 4];
let mut sums = vec![0.0; 4];
let mut sources = Vec::new();
let mut reorder = |s: &[usize]| sources = s.to_vec();
let a: &[f32] = &[-9.0, -9.0, 1.0, 2.0];
let b: &[f32] = &[-9.0, 2.0, 1.0, -9.0];
let (feed, _) = TokenDecoder::update(
&mut decoder,
&mut tokens,
logits(&[a, a, b, b], &device),
&mut sums,
&mut reorder,
);
assert_eq!(feed, vec![3, 2, 1, 2]);
assert_eq!(sources, vec![1, 1, 3, 3]);
}
#[test]
#[should_panic(expected = "invalid beam size")]
fn test_rejects_zero_candidates() {
let _ = WhisperBeamSearchDecoder::new(1, EOT, Some(0.1));
}
}