Skip to content

armgit / uzu

Public Imported from GitHub
0

A high-performance inference engine for AI models

7.3 KB
Raw Blame
use itertools::Itertools;
use thiserror::Error;

use crate::{
    backends::common::gpu_types::trie::TrieNode as GpuTrieNode,
    data_type::DataType,
    engine::language_model::grammar::{Grammar, GrammarError},
};

#[derive(Debug, Error)]
pub enum TrieError {
    #[error("child with the same token id is already present")]
    DuplicateTokenId,
}

#[derive(Debug, Error)]
pub enum TrieAcceptError {
    #[error("Grammar error: {0}")]
    Grammar(#[from] GrammarError),
}

#[derive(Debug)]
pub struct TrieNode {
    token: u64,
    seed: u64,
    logprob: f32,
    next: Vec<TrieNode>,
}

#[derive(Debug)]
struct FlatTrieNode<'a> {
    node: &'a TrieNode,
    subtrie_range: (usize, usize),
    height: usize,
}

#[derive(Debug)]
pub struct FlatTrie<'a> {
    tokens: Box<[FlatTrieNode<'a>]>,
}

impl TrieNode {
    pub fn new(
        token: u64,
        seed: u64,
        logprob: f32,
    ) -> Self {
        Self {
            token,
            seed,
            logprob,
            next: Vec::new(),
        }
    }

    pub fn add(
        &mut self,
        next: TrieNode,
    ) -> Result<usize, TrieError> {
        if self.next.iter().any(|n| n.token == next.token) {
            return Err(TrieError::DuplicateTokenId);
        }

        self.next.push(next);
        Ok(self.next.len() - 1)
    }

    pub fn get(
        &self,
        token: u64,
    ) -> Option<&TrieNode> {
        self.next.iter().find(|n| n.token == token)
    }

    #[cfg(test)]
    pub fn token(&self) -> u64 {
        self.token
    }

    #[cfg(test)]
    pub fn logprob(&self) -> f32 {
        self.logprob
    }

    #[cfg(test)]
    pub fn node_count(&self) -> usize {
        1 + self.next.iter().map(TrieNode::node_count).sum::<usize>()
    }

    pub fn prune_to_budget(
        &mut self,
        budget: usize,
    ) {
        assert!(budget > 0, "budget must keep at least the root");

        fn collect_logprobs(
            node: &TrieNode,
            parent_logprob: f32,
            logprobs: &mut Vec<f32>,
        ) {
            let logprob = parent_logprob + node.logprob;
            logprobs.push(logprob);
            for child in &node.next {
                collect_logprobs(child, logprob, logprobs);
            }
        }
        let mut logprobs = Vec::new();
        collect_logprobs(self, 0.0, &mut logprobs);
        if budget >= logprobs.len() {
            return;
        }

        let mut order: Box<[usize]> = (0..logprobs.len()).collect();
        order.sort_by(|&a, &b| logprobs[b].total_cmp(&logprobs[a]));
        let mut kept = vec![false; logprobs.len()];
        for &index in order.iter().take(budget) {
            kept[index] = true;
        }

        fn prune(
            node: &mut TrieNode,
            kept: &[bool],
            cursor: &mut usize,
        ) {
            *cursor += 1;
            let mut children = std::mem::take(&mut node.next);
            children.retain_mut(|child| {
                let child_index = *cursor;
                prune(child, kept, cursor);
                kept[child_index]
            });
            node.next = children;
        }
        prune(self, &kept, &mut 0);
    }

    pub fn linearize(&self) -> FlatTrie<'_> {
        let mut tokens = vec![FlatTrieNode::new(self, (0, 0), 0)];

        let mut stack = vec![(0, 0)];
        while let Some((cur_node_idx, next_child_idx)) = stack.last_mut() {
            let Some(next_node) = tokens[*cur_node_idx].node.next.get(*next_child_idx) else {
                tokens[*cur_node_idx].subtrie_range.1 = tokens.len() - 1;
                stack.pop();
                continue;
            };
            *next_child_idx += 1;

            tokens.push(FlatTrieNode::new(next_node, (tokens.len(), tokens.len()), stack.len()));

            if !next_node.next.is_empty() {
                stack.push((tokens.len() - 1, 0));
            }
        }

        FlatTrie::new(tokens.into_boxed_slice())
    }
}

impl<'a> FlatTrieNode<'a> {
    fn new(
        node: &'a TrieNode,
        subtrie_range: (usize, usize),
        height: usize,
    ) -> Self {
        Self {
            node,
            subtrie_range,
            height,
        }
    }
}

impl<'a> FlatTrie<'a> {
    fn new(tokens: Box<[FlatTrieNode<'a>]>) -> Self {
        Self {
            tokens,
        }
    }

    #[cfg(test)]
    pub fn len(&self) -> usize {
        self.tokens.len()
    }

    pub fn token_ids(&self) -> impl Iterator<Item = u64> {
        self.tokens.iter().map(|n| n.node.token)
    }

    pub fn token_subtrie_ranges(&self) -> impl Iterator<Item = GpuTrieNode> {
        self.tokens.iter().map(|n| {
            let (start, end) = n.subtrie_range;

            GpuTrieNode {
                trie_start: start as u32,
                trie_end: end as u32,
                height: n.height as u32,
            }
        })
    }

    pub fn token_seeds(&self) -> impl Iterator<Item = u64> {
        self.tokens.iter().map(|n| n.node.seed)
    }

    pub fn fill_bitmasks(
        &self,
        bitmasks: &mut [u32],
        vocab_size: usize,
        grammar: &mut Grammar,
    ) -> bool {
        let vocab_size_in_u32s = vocab_size.div_ceil(DataType::U32.size_in_bits());
        assert!(bitmasks.len() == self.tokens.len() * vocab_size_in_u32s);

        let mut any_non_full = false;
        let mut last_token_height = 0;
        for ((token_index, token), bitmask) in
            self.tokens.iter().enumerate().zip_eq(bitmasks.chunks_exact_mut(vocab_size_in_u32s))
        {
            if token_index > 0 {
                if token.height <= last_token_height {
                    grammar.rollback(last_token_height - token.height + 1);
                }
                grammar.accept_token(token.node.token).expect("flat trie doesn't match grammar");
            }

            any_non_full |= grammar.next_bitmask(bitmask);

            last_token_height = token.height;
        }

        if last_token_height > 0 {
            grammar.rollback(last_token_height);
        }

        any_non_full
    }

    pub fn root(&self) -> Option<&TrieNode> {
        self.tokens.first().map(|n| n.node)
    }

    pub fn index(
        &self,
        node: &'a TrieNode,
    ) -> Option<usize> {
        self.tokens.iter().position(|n| std::ptr::eq(n.node, node))
    }

    pub fn accept(
        &self,
        sampled_tokens: &[u64],
        mut grammar: Option<&mut Grammar>,
    ) -> Result<Box<[(usize, u64, u64)]>, TrieAcceptError> {
        let mut current_token = self.root().unwrap();
        let mut accepted = Vec::new();
        loop {
            let current_token_index = self.index(current_token).unwrap();
            let current_token_id = sampled_tokens[current_token_index];

            accepted.push((current_token_index, current_token.token, current_token_id));
            if let Some(grammar) = grammar.as_mut()
                && !grammar.is_terminated()
            {
                grammar.accept_token(current_token_id)?;
            }

            let Some(next_token) = current_token.get(current_token_id) else {
                break;
            };

            // The grammar may already be terminated here: when the draft model
            // proposed the grammar-closing token the trie descends one node
            // further, where the mask only allows stop tokens.
            current_token = next_token;
        }

        Ok(accepted.into_boxed_slice())
    }
}

#[cfg(test)]
#[path = "../unit/trie_test.rs"]
mod tests;