← Все главы

36 · Версия материала 6

Сформируйте распределение следующего токена, затем выберите один токен случайным образом

Разберитесь, как положительная температура и фильтрация top-k с однозначным порядком формируют множество кандидатов, почему носитель распределения в f64 может оказаться меньше этого множества и как воспроизвести генерацию LLM без кэша.

Начните с четырёх логитов и сделайте каждый выбор явным

Декодер выдаёт логиты последней позиции в порядке ID токенов: [0,1,1,2][0,1,1,2]. Если упорядочить токены по убыванию их логитов, а при равных логитах — по возрастанию ID, получится порядок ID [3,1,2,0][3,1,2,0]. Токен 33 однозначно занимает первое место. У токенов 11 и 22 равные логиты, поэтому эта реализация ставит меньший ID раньше. Благодаря этому локальному правилу порядок кандидатов при равенстве остаётся детерминированным.

Сначала отберём все четыре токена и будем менять только положительную температуру. При τ=0.5\tau=0.5 токен 33 получает вероятность 0.7758034925740.775803492574; при τ=1\tau=1 — 0.5344466453890.534446645389; при τ=2\tau=2 — 0.3874556190000.387455619000. Низкая температура усиливает уже существующие различия между логитами, а высокая сглаживает их. Порядок токенов от этого не меняется.

Теперь зададим τ=1\tau=1 и k=2k=2. По рангу отбираются токены [3,1][3,1]. Токен 11 занимает последнее место, входящее в top-k, и получает q^1=0.268941421370\widehat q_1=0.268941421370; токен 22 идёт сразу после него, не попадает в top-k, и его вероятность становится в точности равной нулю. Для токена 33 получаем q^3=0.731058578630\widehat q_3=0.731058578630. Сумма сохранённых вероятностей равна 11.

Отбор по рангу не гарантирует положительную вероятность в арифметике с плавающей точкой. Для логитов [2,2,1][2,2,1], температуры f64::MIN_POSITIVE и k=3k=3 детерминированный порядок задаёт K3=[0,1,2]K_3=[0,1,2]. Сохранённые вероятности двух токенов с максимальным логитом равны 0.50.5 и 0.50.5. Токен 22 тоже отобран по рангу, но его вес после сдвига на максимум округляется до нуля. Поэтому q^2=0\widehat q_2=0, а носитель распределения в f64 содержит только токены с положительной представимой вероятностью: Sτ,3(f64)={0,1}S_{\tau,3}^{(\mathrm{f64})}=\{0,1\}.

При k=3k=3 восемь последовательных вызовов алгоритма случайного выбора с генератором SplitMix64 в начальном состоянии 3636 всегда дают одну и ту же последовательность токенов [3,2,2,2,3,3,3,3][3,2,2,2,3,3,3,3]. Например, второе полученное от генератора случайное число, равномерно распределённое на [0,1)[0,1), равно u=0.338833394523u=0.338833394523. Оно попадает в полуоткрытый интервал токена 22 [0.211941557617,0.423883115234)[0.211941557617,0.423883115234), поэтому выбирается токен 22.

Отфильтруйте кандидатов, затем нормализуйте заново

Для конечных логитов, конечной положительной температуры и 1≤k≤V1\le k\le V идеальную вероятность qi(τ,k)q_i^{(\tau,k)} определяем в арифметике действительных чисел. Реализация сохраняет q^i(τ,k)\widehat q_i^{(\tau,k)} в f64, поэтому носитель распределения в f64 может быть строгим подмножеством множества, отобранного по рангу:

qi(τ,k)=𝟏[i∈Kk]exp⁡(ℓi/τ)∑j𝟏[j∈Kk]exp⁡(ℓj/τ),∣Kk∣=k,Sτ,k(f64)={i∈Kk∣q^i(τ,k)>0}⊆Kkq_i^{(\tau,k)}=\frac{\mathbf{1}[i\in K_k]\exp(\ell_i/\tau)}{\sum_j\mathbf{1}[j\in K_k]\exp(\ell_j/\tau)},\quad \lvert K_k\rvert=k,\quad S_{\tau,k}^{(\mathrm{f64})}=\{i\in K_k\mid\widehat q_i^{(\tau,k)}>0\}\subseteq K_k

Перед вычислением экспонент реализация вычитает из каждого отобранного масштабированного логита наибольший из них. В арифметике действительных чисел такой сдвиг сохраняет отношения вероятностей и предотвращает переполнение, которое могло бы возникнуть из-за большого общего смещения. Однако достаточно малый вес отобранного токена всё ещё может округлиться в f64 до нуля. Вероятность каждого исключённого ID равна нулю, но обратное неверно: токен с нулевой сохранённой вероятностью всё же может входить в KkK_k. Поэтому носитель распределения в f64 определяется условием q^i>0\widehat q_i>0, а не одной лишь принадлежностью множеству, отобранному по рангу.

Температура должна быть строго положительной. Математический предел τ→0+\tau\to0^+ помогает понять концентрацию около единственного максимума, но само значение τ=0\tau=0 привело бы к делению на ноль. Поэтому жадное декодирование оформлено как отдельное правило: оно проверяет те же логиты, выбирает ID токена, стоящего первым в однозначном порядке, и не запрашивает случайное число. Стохастический режим с k=1k=1 выбирает тот же ID, но намеренно запрашивает одно случайное число, поскольку по-прежнему следует правилу случайного выбора.

Не смешивайте логиты, кандидатов и вероятности

  • qi(τ,k)q_i^{(\tau,k)} — идеальная вероятность токена ii после масштабирования логитов температурой, фильтрации top-k и повторной нормализации в арифметике действительных чисел.
  • q^i(τ,k)\widehat q_i^{(\tau,k)} — вероятность токена ii, фактически сохранённая в f64 после вычисления экспонент со сдвигом на максимум и нормализации.
  • Sτ,k(f64)S_{\tau,k}^{(\mathrm{f64})} — носитель распределения в f64: ID токенов, отобранных по рангу и имеющих строго положительную представимую вероятность.
  • τ\tau — конечная положительная температура. Меньшие значения увеличивают различия между масштабированными логитами и концентрируют распределение вероятностей; большие уменьшают эти различия и сглаживают распределение.
  • kk — точное число отобранных ID токенов.
  • VV — размер словаря, поэтому допустимое число кандидатов удовлетворяет условию 1≤k≤V1\le k\le V.
  • KkK_k — множество ID токенов, отобранных по рангу; в нём всегда ровно kk элементов. В этой реализации равные логиты упорядочиваются по возрастанию ID токена.
  • 𝟏[i∈Kk]\mathbf{1}[i\in K_k] равен 11 для отобранного ID и 00 для исключённого.
  • ℓi\ell_i — логит декодера для токена ii в последней позиции префикса.
  • ii — ID токена-кандидата, для которого вычисляется итоговая вероятность.
  • В знаменателе суммирование по jj охватывает весь словарь.
  • exp⁡\exp положительна в арифметике действительных чисел. Результат её вычисления в f64 для достаточно большого отрицательного сдвига может округлиться до нуля.

Эти понятия относятся к разным этапам вычисления. Логит — неограниченная оценка декодера, место в однозначно заданном порядке определяет принадлежность к KkK_k, а строго положительная сохранённая вероятность — принадлежность к Sτ,k(f64)S_{\tau,k}^{(\mathrm{f64})}. Температура изменяет разности логитов до нормализации. Top-k задаёт множество, отобранное по рангу. Вычисления с плавающей точкой могут сузить носитель распределения в f64 уже после отбора по рангу.

Алгоритм просматривает сохранённые вероятности в порядке возрастания ID и пропускает все вероятности, равные нулю. В обычном примере алгоритм берёт случайное число uu, равномерно распределённое на [0,1)[0,1), и выбирает токен ii, если ai≤u<bia_i\le u<b_i, где [ai,bi)[a_i,b_i) — записанный для токена полуоткрытый интервал. Кандидату с нулевой вероятностью интервал не соответствует, поэтому выбрать его нельзя. Границы накопленной вероятности тоже представлены в f64, поэтому глава не утверждает, что для любого словаря каждая положительная сохранённая вероятность обязательно образует непустой достижимый интервал. Для последнего кандидата с положительной вероятностью алгоритм учитывает небольшое расхождение конечной границы из-за суммирования и при этом не выбирает токен с нулевой вероятностью.

От поиска при жёстких ограничениях к свободной генерации LLM

Лучевое декодирование, максимизирующее правдоподобие, полезно, когда исходный текст жёстко ограничивает результат. Но у свободного продолжения много допустимых вариантов: лучевой поиск может давать шаблонный или повторяющийся текст, а при случайном выборе без ограничения множества кандидатов в результат может попасть маловероятный токен из ненадёжного хвоста распределения.

Исследование Фэна, Льюиса и Дофина рассматривает случайный выбор из ограниченного множества слов при свободной генерации. Фэн, Льюис и Дофин на каждом шаге выбирают случайное слово среди десяти наиболее вероятных, настраивают температуру softmax во время генерации и сообщают, что в их задаче продолжения историй такой подход работает лучше лучевого поиска. Выбор без ограничений, напротив, может добавить маловероятное слово, которое серьёзно ухудшит текст.

Отчёт о GPT-2 приводит два конкретных режима случайного выбора для разных задач. В отчёте о GPT-2 случайный выбор top-k с k=2k=2 используется в одном режиме составления краткого изложения, а с k=40k=40 — для свободных продолжений WebText. Это пример усечённого стохастического декодирования в крупной языковой модели на основе архитектуры Transformer, но не утверждение об универсальности одного значения kk.

Исследование Хольцмана и соавторов разбирает компромисс между отсечением ненадёжного хвоста распределения и сохранением разнообразия. Хольцман и соавторы на примере GPT-2 сопоставляют декодирование, максимизирующее правдоподобие, со случайным выбором, определяют top-k как выбор среди kk самых вероятных токенов после повторной нормализации, приводят softmax с температурой и показывают, почему фиксированное kk оказывается несовершенным компромиссом и в контекстах с относительно близкими вероятностями токенов, и в контекстах с резко концентрированным распределением.

Ранние системы генерации историй сочетали температуру softmax с top-k, модель GPT-2 использовала top-k для кратких изложений и длинных продолжений, а последующий анализ GPT-2 подробно описал компромисс между отсечением и повторной нормализацией и показал, почему фиксированное kk подходит не для каждого контекста.

Управляемое стохастическое декодирование задаёт баланс между разнообразием и концентрацией в распределении авторегрессионной LLM. Если восстановить то же состояние генератора псевдослучайных чисел и сохранить однозначные правила разрешения равенств и обхода интервалов, алгоритм случайного выбора сможет воспроизвести свои результаты. Более поздние методы позволяют числу кандидатов зависеть от контекста, не меняя логиты декодера.

Поэтому top-k — понятный первый пример управляемого стохастического декодирования, однако этот метод не гарантирует качество и не защищает от галлюцинаций; исследования способов декодирования им не ограничиваются. В этой реализации порядок токенов с равными логитами определяется по ID, состояние генератора можно восстановить, а поведение при ошибочных настройках, EOS и исчерпании ёмкости контекста задано явно. Всё это обеспечивает воспроизводимость результатов этой реализации и не является утверждением о процитированных системах.

Исполняемый пример показывает работу механизма на четырёх логитах из этой главы. Жадный режим выбирает токен 33, не изменяя состояние генератора. При τ=1\tau=1 и фиксированном k=3k=3 остаются ID [3,1,2][3,1,2]. До повторной нормализации top-k сохраняет 0.9276705118710.927670511871 вероятностной массы исходного распределения softmax и отбрасывает 0.0723294881290.072329488129. Это измерение не определяет, какое правило порождает более качественный текст; оно лишь наглядно показывает, где проходит граница отбора ровно kk кандидатов.

Показать результат жадного выбора и измерить долю вероятностной массы, отброшенную фильтрацией с фиксированным top-k rust/demos/ch36-temperature-top-k/src/lib.rs#historical-decoding-contrast
/// Measures how greedy choice and fixed top-k truncation differ on one logit row.
pub fn historical_decoding_contrast() -> Result<HistoricalDecodingContrast, FixtureError> {
    let full = sampling_distribution(
        &LOGITS,
        SamplingMode::TemperatureTopK {
            temperature: 1.0,
            top_k: LOGITS.len(),
        },
    )?;
    let truncated = sampling_distribution(
        &LOGITS,
        SamplingMode::TemperatureTopK {
            temperature: 1.0,
            top_k: SAMPLE_TOP_K,
        },
    )?;
    let retained_token_ids = truncated.retained_token_ids().to_vec();
    let retained_full_probability_mass = full
        .candidates()
        .iter()
        .filter(|candidate| retained_token_ids.contains(&candidate.token_id()))
        .map(|candidate| candidate.probability())
        .sum::<f64>();
    let removed_full_probability_mass = full
        .candidates()
        .iter()
        .filter(|candidate| !retained_token_ids.contains(&candidate.token_id()))
        .map(|candidate| candidate.probability())
        .sum::<f64>();
    let mut greedy_rng = SplitMix64::from_seed(SAMPLE_SEED);
    let initial_rng_state = greedy_rng.state();
    let greedy = sample_next_token(&LOGITS, SamplingMode::Greedy, &mut greedy_rng)?;

    require(
        retained_token_ids.len() == SAMPLE_TOP_K,
        "historical top-k candidate count changed",
    )?;
    require(
        (retained_full_probability_mass + removed_full_probability_mass - 1.0).abs() < 1e-12,
        "historical full-softmax mass no longer sums to one",
    )?;

    Ok(HistoricalDecodingContrast {
        greedy_token: greedy.token_id(),
        greedy_rng_advanced: greedy_rng.state() != initial_rng_state,
        top_k: SAMPLE_TOP_K,
        retained_token_ids,
        retained_full_probability_mass,
        removed_full_probability_mass,
    })
}

Сначала проверьте входы, однозначно задайте порядок и лишь затем измените состояние генератора

SamplingMode::Greedy и SamplingMode::TemperatureTopK задают два явных режима. В обоих режимах пустой набор логитов или неконечное значение приводит к ошибке. Стохастический режим дополнительно требует конечную положительную температуру и kk в диапазоне 1≤k≤V1\le k\le V. Все проверки завершаются до изменения состояния SplitMix64.

Три функции — sample_next_token, sample_next_token_with_trace и sampling_distribution — начинают с одних и тех же вычислений: они проверяют входные данные, сортируют логиты с конечными значениями по убыванию, а при равенстве — по возрастанию ID, отбирают заданное число кандидатов и преобразуют их логиты в сохранённые вероятности f64. sample_next_token возвращает выбранный ID токена, соответствующий полуоткрытый интервал и, для стохастического режима, случайное число, равномерно распределённое на [0,1)[0,1). Эта функция не формирует записи по каждому токену и отдельный список ID, отобранных по рангу, которые нужны для подробного разбора. sample_next_token_with_trace использует те же рассчитанные вероятности и тот же код выбора по интервалам, но перед обращением к генератору случайных чисел формирует полное распределение для подробного разбора. sampling_distribution формирует такое же распределение, не выполняя случайный выбор. sample_next_token тоже временно хранит массивы с ID токенов в порядке ранжирования и их вероятностями. Дополнительные записи для подробного разбора при этом не создаются.

В распределении для подробного разбора кандидаты расположены по возрастанию ID токена, а отдельный список отобранных ID — по убыванию логита; при равных логитах первым идёт меньший ID. После нормализации со сдвигом на максимум исключённым ID соответствует ровно нулевая вероятность. Сохранённая вероятность отобранного ID тоже может оказаться равной нулю, если соответствующий представимый вес округлится до нуля. Случайный выбор пропускает нулевые сохранённые вероятности по возрастанию ID. Гарантируется именно пропуск нулевых вероятностей, а не непустой достижимый интервал для каждого положительного значения при любом словаре. Жадный режим не запрашивает случайное число, а любой допустимый стохастический вызов запрашивает ровно одно, в том числе при top-k с k=1k=1.

Подготовить отфильтрованное распределение один раз, затем вернуть краткие сведения о выборе или, по явному запросу, полное распределение для подробного разбора rust/crates/llm-from-scratch/src/generation/sampling.rs#sampling-policy
/// The two intentionally distinct next-token policies taught in Chapter 36.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum SamplingMode {
    /// Select the highest logit, resolving equal logits by lower token ID.
    Greedy,
    /// Sample after positive-temperature scaling and stable top-k truncation.
    TemperatureTopK { temperature: f64, top_k: usize },
}

/// One vocabulary entry after ranking and probability construction.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct SamplingCandidate {
    token_id: u32,
    logit: f64,
    rank: usize,
    retained: bool,
    probability: f64,
}

impl SamplingCandidate {
    pub const fn token_id(self) -> u32 {
        self.token_id
    }

    pub const fn logit(self) -> f64 {
        self.logit
    }

    /// One-based rank under descending logit and ascending token-ID ties.
    pub const fn rank(self) -> usize {
        self.rank
    }

    pub const fn retained(self) -> bool {
        self.retained
    }

    /// Whether the final represented probability is strictly positive.
    ///
    /// A token can be retained by top-k rank while falling outside this
    /// positive support when its exponential weight underflows to exact zero.
    pub const fn has_positive_probability(self) -> bool {
        self.probability > 0.0
    }

    pub const fn probability(self) -> f64 {
        self.probability
    }
}

/// The complete token-ID-ordered distribution plus rank-ordered retained IDs.
#[derive(Clone, Debug, PartialEq)]
pub struct SamplingDistribution {
    mode: SamplingMode,
    candidates: Vec<SamplingCandidate>,
    retained_token_ids: Vec<u32>,
}

impl SamplingDistribution {
    pub const fn mode(&self) -> SamplingMode {
        self.mode
    }

    /// Candidates are always returned in ascending token-ID order.
    pub fn candidates(&self) -> &[SamplingCandidate] {
        &self.candidates
    }

    /// Retained IDs are returned in stable descending-logit rank order.
    ///
    /// Membership is determined before probability construction, so this list
    /// can include an ID whose represented probability later underflows to zero.
    pub fn retained_token_ids(&self) -> &[u32] {
        &self.retained_token_ids
    }

    /// Positive represented-probability support in ascending token-ID order.
    pub fn positive_support_token_ids(&self) -> impl Iterator<Item = u32> + '_ {
        self.candidates
            .iter()
            .filter(|candidate| candidate.has_positive_probability())
            .map(|candidate| candidate.token_id())
    }

    pub fn probability_sum(&self) -> f64 {
        compensated_sum(
            self.candidates
                .iter()
                .map(|candidate| candidate.probability),
        )
    }

    pub fn candidate(&self, token_id: u32) -> Option<SamplingCandidate> {
        self.candidates
            .get(usize::try_from(token_id).ok()?)
            .copied()
    }
}

/// One selected token and the half-open categorical interval that selected it.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct SampledToken {
    token_id: u32,
    unit_draw: Option<f64>,
    interval_start: f64,
    interval_end: f64,
}

impl SampledToken {
    pub const fn token_id(self) -> u32 {
        self.token_id
    }

    pub const fn unit_draw(self) -> Option<f64> {
        self.unit_draw
    }

    pub const fn interval_start(self) -> f64 {
        self.interval_start
    }

    pub const fn interval_end(self) -> f64 {
        self.interval_end
    }
}

/// A compact selection paired with the complete distribution used to produce it.
#[derive(Clone, Debug, PartialEq)]
pub struct SamplingDecision {
    sampled: SampledToken,
    distribution: SamplingDistribution,
}

impl SamplingDecision {
    pub const fn token_id(&self) -> u32 {
        self.sampled.token_id()
    }

    pub const fn unit_draw(&self) -> Option<f64> {
        self.sampled.unit_draw()
    }

    pub const fn interval_start(&self) -> f64 {
        self.sampled.interval_start()
    }

    pub const fn interval_end(&self) -> f64 {
        self.sampled.interval_end()
    }

    pub const fn distribution(&self) -> &SamplingDistribution {
        &self.distribution
    }
}

/// A setting or numerical input that cannot define a sampling distribution.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum SamplingError {
    EmptyLogits,
    VocabularyTooLarge {
        classes: usize,
    },
    NonFiniteLogit {
        token_id: usize,
        value: f64,
    },
    InvalidTemperature {
        value: f64,
    },
    InvalidTopK {
        top_k: usize,
        vocabulary_size: usize,
    },
    AllocationFailed {
        values: usize,
    },
    InvalidProbabilitySum {
        value: f64,
    },
}

impl fmt::Display for SamplingError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::EmptyLogits => formatter.write_str("sampling needs at least one finite logit"),
            Self::VocabularyTooLarge { classes } => write!(
                formatter,
                "sampling vocabulary of {classes} classes does not fit u32 token IDs"
            ),
            Self::NonFiniteLogit { token_id, value } => {
                write!(
                    formatter,
                    "logit for token {token_id} is not finite: {value}"
                )
            }
            Self::InvalidTemperature { value } => write!(
                formatter,
                "sampling temperature must be finite and positive, received {value}"
            ),
            Self::InvalidTopK {
                top_k,
                vocabulary_size,
            } => write!(
                formatter,
                "top-k must be in 1..={vocabulary_size}, received {top_k}"
            ),
            Self::AllocationFailed { values } => {
                write!(
                    formatter,
                    "cannot allocate sampling evidence for {values} values"
                )
            }
            Self::InvalidProbabilitySum { value } => write!(
                formatter,
                "sampling probabilities did not normalize to one: {value}"
            ),
        }
    }
}

impl Error for SamplingError {}

fn retained_count(mode: SamplingMode, vocabulary_size: usize) -> Result<usize, SamplingError> {
    match mode {
        SamplingMode::Greedy => Ok(1),
        SamplingMode::TemperatureTopK { temperature, top_k } => {
            if !temperature.is_finite() || temperature <= 0.0 {
                return Err(SamplingError::InvalidTemperature { value: temperature });
            }
            if top_k == 0 || top_k > vocabulary_size {
                return Err(SamplingError::InvalidTopK {
                    top_k,
                    vocabulary_size,
                });
            }
            Ok(top_k)
        }
    }
}

fn compensated_sum(values: impl IntoIterator<Item = f64>) -> f64 {
    let mut sum = 0.0;
    let mut compensation = 0.0;
    for value in values {
        let corrected = value - compensation;
        let next = sum + corrected;
        compensation = (next - sum) - corrected;
        sum = next;
    }
    sum
}

fn stable_ranks(logits: &[f64]) -> Result<Vec<usize>, SamplingError> {
    if logits.is_empty() {
        return Err(SamplingError::EmptyLogits);
    }
    if u32::try_from(logits.len() - 1).is_err() {
        return Err(SamplingError::VocabularyTooLarge {
            classes: logits.len(),
        });
    }
    for (token_id, &value) in logits.iter().enumerate() {
        if !value.is_finite() {
            return Err(SamplingError::NonFiniteLogit { token_id, value });
        }
    }

    let mut ranked = Vec::new();
    ranked
        .try_reserve_exact(logits.len())
        .map_err(|_| SamplingError::AllocationFailed {
            values: logits.len(),
        })?;
    ranked.extend(0..logits.len());
    ranked.sort_unstable_by(|&left, &right| {
        logits[right]
            .partial_cmp(&logits[left])
            .unwrap_or(Ordering::Equal)
            .then_with(|| left.cmp(&right))
    });
    Ok(ranked)
}

fn scaled_gap(logit: f64, maximum: f64, temperature: f64) -> f64 {
    if temperature < 1.0 {
        (logit - maximum) / temperature
    } else {
        logit / temperature - maximum / temperature
    }
}

struct PreparedSampling {
    mode: SamplingMode,
    ranked: Vec<usize>,
    probabilities: Vec<f64>,
    keep: usize,
}

fn prepare_sampling(logits: &[f64], mode: SamplingMode) -> Result<PreparedSampling, SamplingError> {
    let ranked = stable_ranks(logits)?;
    let keep = retained_count(mode, logits.len())?;
    let maximum = logits[ranked[0]];

    let mut probabilities = Vec::new();
    probabilities
        .try_reserve_exact(logits.len())
        .map_err(|_| SamplingError::AllocationFailed {
            values: logits.len(),
        })?;
    probabilities.resize(logits.len(), 0.0);

    match mode {
        SamplingMode::Greedy => probabilities[ranked[0]] = 1.0,
        SamplingMode::TemperatureTopK { temperature, .. } => {
            for (position, &token_id) in ranked[..keep].iter().enumerate() {
                let weight = if position == 0 {
                    1.0
                } else {
                    scaled_gap(logits[token_id], maximum, temperature).exp()
                };
                probabilities[token_id] = weight;
            }
            let weight_sum = compensated_sum(
                ranked[..keep]
                    .iter()
                    .map(|&token_id| probabilities[token_id]),
            );
            if !weight_sum.is_finite() || weight_sum <= 0.0 {
                return Err(SamplingError::InvalidProbabilitySum { value: weight_sum });
            }
            for &token_id in &ranked[..keep] {
                probabilities[token_id] /= weight_sum;
            }
        }
    }

    let probability_sum = compensated_sum(probabilities.iter().copied());
    if !probability_sum.is_finite() || (probability_sum - 1.0).abs() > PROBABILITY_TOLERANCE {
        return Err(SamplingError::InvalidProbabilitySum {
            value: probability_sum,
        });
    }

    Ok(PreparedSampling {
        mode,
        ranked,
        probabilities,
        keep,
    })
}

fn materialize_distribution(
    logits: &[f64],
    prepared: &PreparedSampling,
) -> Result<SamplingDistribution, SamplingError> {
    let PreparedSampling {
        mode,
        ranked,
        probabilities,
        keep,
    } = prepared;

    let mut rank_by_token = Vec::new();
    rank_by_token
        .try_reserve_exact(logits.len())
        .map_err(|_| SamplingError::AllocationFailed {
            values: logits.len(),
        })?;
    rank_by_token.resize(logits.len(), 0);
    for (position, &token_id) in ranked.iter().enumerate() {
        rank_by_token[token_id] = position + 1;
    }

    let mut candidates = Vec::new();
    candidates
        .try_reserve_exact(logits.len())
        .map_err(|_| SamplingError::AllocationFailed {
            values: logits.len(),
        })?;
    for (token_id, ((&logit, &probability), &rank)) in logits
        .iter()
        .zip(probabilities)
        .zip(&rank_by_token)
        .enumerate()
    {
        candidates.push(SamplingCandidate {
            token_id: u32::try_from(token_id).expect("validated token ID must fit u32"),
            logit,
            rank,
            retained: rank <= *keep,
            probability,
        });
    }

    let mut retained_token_ids = Vec::new();
    retained_token_ids
        .try_reserve_exact(*keep)
        .map_err(|_| SamplingError::AllocationFailed { values: *keep })?;
    for &token_id in &ranked[..*keep] {
        retained_token_ids.push(u32::try_from(token_id).expect("validated token ID must fit u32"));
    }
    Ok(SamplingDistribution {
        mode: *mode,
        candidates,
        retained_token_ids,
    })
}

fn select_prepared(prepared: &PreparedSampling, rng: &mut SplitMix64) -> SampledToken {
    if prepared.mode == SamplingMode::Greedy {
        return SampledToken {
            token_id: u32::try_from(prepared.ranked[0]).expect("validated token ID must fit u32"),
            unit_draw: None,
            interval_start: 0.0,
            interval_end: 1.0,
        };
    }

    let draw = rng.next_unit_f64();
    let final_id = prepared
        .probabilities
        .iter()
        .enumerate()
        .rev()
        .find(|(_, probability)| **probability > 0.0)
        .map(|(token_id, _)| token_id)
        .expect("a normalized distribution must have positive support");
    let mut start = 0.0;
    for (token_id, &probability) in prepared
        .probabilities
        .iter()
        .enumerate()
        .filter(|(_, probability)| **probability > 0.0)
    {
        let end = if token_id == final_id {
            1.0
        } else {
            (start + probability).min(1.0)
        };
        if draw < end || token_id == final_id {
            return SampledToken {
                token_id: u32::try_from(token_id).expect("validated token ID must fit u32"),
                unit_draw: Some(draw),
                interval_start: start,
                interval_end: end,
            };
        }
        start = end;
    }
    unreachable!("the final positive-support token covers every unit draw")
}

fn sample_with_observer<T>(
    logits: &[f64],
    mode: SamplingMode,
    rng: &mut SplitMix64,
    observe: impl FnOnce(&PreparedSampling) -> Result<T, SamplingError>,
) -> Result<(SampledToken, T), SamplingError> {
    let prepared = prepare_sampling(logits, mode)?;
    let observation = observe(&prepared)?;
    let sampled = select_prepared(&prepared, rng);
    Ok((sampled, observation))
}

/// Builds a complete, inspectable distribution without consuming randomness.
pub fn sampling_distribution(
    logits: &[f64],
    mode: SamplingMode,
) -> Result<SamplingDistribution, SamplingError> {
    let prepared = prepare_sampling(logits, mode)?;
    materialize_distribution(logits, &prepared)
}

/// Selects one token without retaining the complete inspectable distribution.
pub fn sample_next_token(
    logits: &[f64],
    mode: SamplingMode,
    rng: &mut SplitMix64,
) -> Result<SampledToken, SamplingError> {
    sample_with_observer(logits, mode, rng, |_| Ok(())).map(|(sampled, ())| sampled)
}

/// Selects one token and records the complete distribution used for inspection.
pub fn sample_next_token_with_trace(
    logits: &[f64],
    mode: SamplingMode,
    rng: &mut SplitMix64,
) -> Result<SamplingDecision, SamplingError> {
    let (sampled, distribution) = sample_with_observer(logits, mode, rng, |prepared| {
        materialize_distribution(logits, prepared)
    })?;
    Ok(SamplingDecision {
        sampled,
        distribution,
    })
}

generate_uncached хранит полный префикс. Перед каждым вызовом декодера функция проверяет, не превышает ли длина префикса ёмкость контекста. Затем она выполняет вычисления без записи графа вычислений, берёт строку словарных логитов для последней позиции префикса, выбирает один токен, добавляет его и сохраняет только краткие сведения о шаге: длину префикса, выбранный ID, случайное число и интервал. Поскольку при выборе токена используется функция с кратким результатом, для каждого нового токена полные записи о кандидатах не создаются и не сохраняются. EOS включается в результат до остановки цикла. Поэтому при префиксе длины 22 и ёмкости контекста 22 декодер может выдать ещё один токен, хотя получившуюся последовательность длины 33 уже нельзя подать в следующем вызове.

Заново вычислять каждый полный префикс и останавливаться при появлении EOS, генерации заданного числа токенов или исчерпании ёмкости контекста rust/crates/llm-from-scratch/src/generation/sampling.rs#uncached-generation
/// Settings for one bounded, uncached autoregressive call.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct GenerationConfig {
    mode: SamplingMode,
    eos_token: Option<u32>,
    max_new_tokens: usize,
}

impl GenerationConfig {
    pub const fn new(mode: SamplingMode, eos_token: Option<u32>, max_new_tokens: usize) -> Self {
        Self {
            mode,
            eos_token,
            max_new_tokens,
        }
    }

    pub const fn mode(self) -> SamplingMode {
        self.mode
    }

    pub const fn eos_token(self) -> Option<u32> {
        self.eos_token
    }

    pub const fn max_new_tokens(self) -> usize {
        self.max_new_tokens
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum GenerationStop {
    Eos,
    TokenLimit,
    ContextLimit,
}

#[derive(Clone, Debug, PartialEq)]
pub struct GenerationStep {
    prefix_length: usize,
    token_id: u32,
    unit_draw: Option<f64>,
    interval_start: f64,
    interval_end: f64,
}

impl GenerationStep {
    pub const fn prefix_length(&self) -> usize {
        self.prefix_length
    }

    pub const fn token_id(&self) -> u32 {
        self.token_id
    }

    pub const fn unit_draw(&self) -> Option<f64> {
        self.unit_draw
    }

    pub const fn interval_start(&self) -> f64 {
        self.interval_start
    }

    pub const fn interval_end(&self) -> f64 {
        self.interval_end
    }
}

#[derive(Clone, Debug, PartialEq)]
pub struct GenerationResult {
    prompt: Vec<u32>,
    generated: Vec<u32>,
    steps: Vec<GenerationStep>,
    stop: GenerationStop,
    full_prefix_calls: usize,
}

impl GenerationResult {
    pub fn prompt(&self) -> &[u32] {
        &self.prompt
    }

    pub fn generated(&self) -> &[u32] {
        &self.generated
    }

    pub fn steps(&self) -> &[GenerationStep] {
        &self.steps
    }

    pub const fn stop(&self) -> GenerationStop {
        self.stop
    }

    pub const fn full_prefix_calls(&self) -> usize {
        self.full_prefix_calls
    }
}

#[derive(Debug)]
pub enum GenerationError {
    Sampling(SamplingError),
    Model(DecoderModelError),
    EmptyPrompt,
    PromptTooLong {
        tokens: usize,
        max_positions: usize,
    },
    PromptTokenOutOfBounds {
        position: usize,
        token_id: u32,
        vocabulary_size: usize,
    },
    EosTokenOutOfBounds {
        token_id: u32,
        vocabulary_size: usize,
    },
    LogitCountMismatch {
        expected: usize,
        actual: usize,
    },
    AllocationFailed {
        values: usize,
    },
}

impl fmt::Display for GenerationError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Sampling(error) => error.fmt(formatter),
            Self::Model(error) => error.fmt(formatter),
            Self::EmptyPrompt => formatter.write_str("generation needs a nonempty prompt"),
            Self::PromptTooLong {
                tokens,
                max_positions,
            } => write!(
                formatter,
                "prompt has {tokens} tokens, exceeding context capacity {max_positions}"
            ),
            Self::PromptTokenOutOfBounds {
                position,
                token_id,
                vocabulary_size,
            } => write!(
                formatter,
                "prompt token {token_id} at position {position} is out of bounds for vocabulary {vocabulary_size}"
            ),
            Self::EosTokenOutOfBounds {
                token_id,
                vocabulary_size,
            } => write!(
                formatter,
                "EOS token {token_id} is out of bounds for vocabulary {vocabulary_size}"
            ),
            Self::LogitCountMismatch { expected, actual } => write!(
                formatter,
                "last-position logits need {expected} values, received {actual}"
            ),
            Self::AllocationFailed { values } => {
                write!(
                    formatter,
                    "cannot allocate generation evidence for {values} values"
                )
            }
        }
    }
}

impl Error for GenerationError {
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        match self {
            Self::Sampling(error) => Some(error),
            Self::Model(error) => Some(error),
            _ => None,
        }
    }
}

impl From<SamplingError> for GenerationError {
    fn from(error: SamplingError) -> Self {
        Self::Sampling(error)
    }
}

impl From<DecoderModelError> for GenerationError {
    fn from(error: DecoderModelError) -> Self {
        Self::Model(error)
    }
}

fn generate_with<F>(
    vocabulary_size: usize,
    max_positions: usize,
    prompt: &[u32],
    config: GenerationConfig,
    rng: &mut SplitMix64,
    mut last_logits: F,
) -> Result<GenerationResult, GenerationError>
where
    F: FnMut(&[u32]) -> Result<Vec<f64>, GenerationError>,
{
    if prompt.is_empty() {
        return Err(GenerationError::EmptyPrompt);
    }
    if prompt.len() > max_positions {
        return Err(GenerationError::PromptTooLong {
            tokens: prompt.len(),
            max_positions,
        });
    }
    for (position, &token_id) in prompt.iter().enumerate() {
        if usize::try_from(token_id)
            .ok()
            .is_none_or(|token| token >= vocabulary_size)
        {
            return Err(GenerationError::PromptTokenOutOfBounds {
                position,
                token_id,
                vocabulary_size,
            });
        }
    }
    if let Some(token_id) = config.eos_token
        && usize::try_from(token_id)
            .ok()
            .is_none_or(|token| token >= vocabulary_size)
    {
        return Err(GenerationError::EosTokenOutOfBounds {
            token_id,
            vocabulary_size,
        });
    }
    retained_count(config.mode, vocabulary_size)?;

    let planned_steps = config.max_new_tokens.min(
        max_positions
            .checked_sub(prompt.len())
            .and_then(|remaining| remaining.checked_add(1))
            .ok_or(GenerationError::AllocationFailed { values: usize::MAX })?,
    );
    let prefix_capacity = prompt
        .len()
        .checked_add(planned_steps)
        .ok_or(GenerationError::AllocationFailed { values: usize::MAX })?;

    let mut prompt_copy = Vec::new();
    prompt_copy
        .try_reserve_exact(prompt.len())
        .map_err(|_| GenerationError::AllocationFailed {
            values: prompt.len(),
        })?;
    prompt_copy.extend_from_slice(prompt);

    let mut prefix = Vec::new();
    prefix
        .try_reserve_exact(prefix_capacity)
        .map_err(|_| GenerationError::AllocationFailed {
            values: prefix_capacity,
        })?;
    prefix.extend_from_slice(prompt);
    let mut generated = Vec::new();
    generated
        .try_reserve_exact(planned_steps)
        .map_err(|_| GenerationError::AllocationFailed {
            values: planned_steps,
        })?;
    let mut steps = Vec::new();
    steps
        .try_reserve_exact(planned_steps)
        .map_err(|_| GenerationError::AllocationFailed {
            values: planned_steps,
        })?;
    let mut full_prefix_calls = 0usize;

    if config.max_new_tokens == 0 {
        return Ok(GenerationResult {
            prompt: prompt_copy,
            generated,
            steps,
            stop: GenerationStop::TokenLimit,
            full_prefix_calls,
        });
    }

    let stop = loop {
        let prefix_length = prefix.len();
        let logits = last_logits(&prefix)?;
        full_prefix_calls += 1;
        if logits.len() != vocabulary_size {
            return Err(GenerationError::LogitCountMismatch {
                expected: vocabulary_size,
                actual: logits.len(),
            });
        }
        let decision = sample_next_token(&logits, config.mode, rng)?;
        let token_id = decision.token_id();
        let unit_draw = decision.unit_draw();
        let interval_start = decision.interval_start();
        let interval_end = decision.interval_end();
        prefix.push(token_id);
        generated.push(token_id);
        steps.push(GenerationStep {
            prefix_length,
            token_id,
            unit_draw,
            interval_start,
            interval_end,
        });

        if config.eos_token == Some(token_id) {
            break GenerationStop::Eos;
        }
        if generated.len() == config.max_new_tokens {
            break GenerationStop::TokenLimit;
        }
        if prefix.len() > max_positions {
            break GenerationStop::ContextLimit;
        }
    };

    Ok(GenerationResult {
        prompt: prompt_copy,
        generated,
        steps,
        stop,
        full_prefix_calls,
    })
}

/// Recomputes the complete decoder prefix for every selected token.
pub fn generate_uncached(
    model: &DecoderModel,
    prompt: &[u32],
    config: GenerationConfig,
    rng: &mut SplitMix64,
) -> Result<GenerationResult, GenerationError> {
    let model_config = model.config();
    let vocabulary_size = model_config.vocabulary_size();
    let context = AutogradContext::no_grad();
    generate_with(
        vocabulary_size,
        model_config.max_positions(),
        prompt,
        config,
        rng,
        |prefix| {
            let forward = model.forward_with_context(context, prefix, &[1, prefix.len()])?;
            let logits = forward.logits().value();
            let expected = prefix
                .len()
                .checked_mul(vocabulary_size)
                .ok_or(GenerationError::AllocationFailed { values: usize::MAX })?;
            if logits.len() != expected {
                return Err(GenerationError::LogitCountMismatch {
                    expected,
                    actual: logits.len(),
                });
            }
            let start = expected - vocabulary_size;
            let mut final_logits = Vec::new();
            final_logits
                .try_reserve_exact(vocabulary_size)
                .map_err(|_| GenerationError::AllocationFailed {
                    values: vocabulary_size,
                })?;
            final_logits.extend_from_slice(&logits.as_slice()[start..]);
            Ok(final_logits)
        },
    )
}

Программа загружает точные байты контрольной точки из главы 35 и отдельно сохраняет записанное в ней состояние генератора псевдослучайных чисел. Затем into_model принимает загруженную контрольную точку по значению и перемещает в декодер принадлежащие ей буферы модели; после этого объект контрольной точки больше не нужен. Эта передача владения не меняет ни значения параметров, ни правило случайного выбора. Вызов generate_uncached с промптом [0][0] возвращает последовательность [4,4][4,4] при длинах префикса [1,2][1,2]: декодер дважды обрабатывает полный префикс, после чего генерация останавливается из-за исчерпания ёмкости контекста. Если снова начать с сохранённого состояния генератора, совпадут и сгенерированная последовательность, и конечное состояние генератора. Если назначить токен 44 токеном EOS, результат включает [4][4] и останавливается после одного вызова декодера.

Собрать точные данные о температуре, равных логитах, повторе выбора, контрольной точке, EOS, контексте и ошибках rust/demos/ch36-temperature-top-k/src/lib.rs#learner-evidence
/// Loads the Chapter 35 checkpoint and records sampling plus full-prefix stops.
pub fn learner_evidence() -> Result<LearnerEvidence, FixtureError> {
    let temperatures = temperature_evidence()?;
    let boundary = sampling_distribution(
        &LOGITS,
        SamplingMode::TemperatureTopK {
            temperature: 1.0,
            top_k: BOUNDARY_TOP_K,
        },
    )?;
    let support = sampling_distribution(
        &SUPPORT_LOGITS,
        SamplingMode::TemperatureTopK {
            temperature: SUPPORT_TEMPERATURE,
            top_k: SUPPORT_TOP_K,
        },
    )?;
    let mut greedy_rng = SplitMix64::from_seed(SAMPLE_SEED);
    let greedy_state = greedy_rng.state();
    let greedy = sample_next_token_with_trace(&LOGITS, SamplingMode::Greedy, &mut greedy_rng)?;
    require(
        greedy_rng.state() == greedy_state,
        "greedy sampling unexpectedly consumed RNG state",
    )?;
    let seeded_decisions = seeded_decisions()?;

    let prior = checkpoint_evidence()?;
    let loaded_checkpoint_bytes = prior.encoded.bytes().len();
    let checkpoint = Checkpoint::from_bytes(prior.encoded.bytes())?;
    let loaded_rng_state = checkpoint.rng_state();
    let model = checkpoint.into_model()?;
    let model_config = model.config();
    let loaded_vocabulary_size = model_config.vocabulary_size();
    let loaded_context = model_config.max_positions();
    let generation_config = GenerationConfig::new(
        SamplingMode::TemperatureTopK {
            temperature: 1.0,
            top_k: 3,
        },
        None,
        4,
    );
    let mut loaded_rng = SplitMix64::from_state(loaded_rng_state);
    let loaded = generate_uncached(&model, &LOADED_PROMPT, generation_config, &mut loaded_rng)?;
    let mut replay_rng = SplitMix64::from_state(loaded_rng_state);
    let replay = generate_uncached(&model, &LOADED_PROMPT, generation_config, &mut replay_rng)?;
    let loaded_replay_identical = loaded == replay && loaded_rng.state() == replay_rng.state();
    let first_token = *loaded.generated().first().ok_or(FixtureError::Invariant(
        "loaded generation emitted no token",
    ))?;
    let mut eos_rng = SplitMix64::from_state(loaded_rng_state);
    let eos = generate_uncached(
        &model,
        &LOADED_PROMPT,
        GenerationConfig::new(generation_config.mode(), Some(first_token), 4),
        &mut eos_rng,
    )?;
    let errors = error_evidence();
    let history = historical_decoding_contrast()?;

    require(
        boundary.retained_token_ids() == [3, 1],
        "stable tied top-k boundary changed",
    )?;
    require(
        support.retained_token_ids() == [0, 1, 2]
            && support.positive_support_token_ids().eq([0, 1])
            && support.candidates()[0].probability().to_bits() == 0.5_f64.to_bits()
            && support.candidates()[1].probability().to_bits() == 0.5_f64.to_bits()
            && support.candidates()[2].retained()
            && !support.candidates()[2].has_positive_probability()
            && support.candidates()[2].probability().to_bits() == 0.0_f64.to_bits(),
        "retained top-k IDs and positive represented support no longer differ as expected",
    )?;
    require(
        seeded_decisions
            .iter()
            .map(SamplingDecision::token_id)
            .eq([3, 2, 2, 2, 3, 3, 3, 3]),
        "seeded sampling sequence changed",
    )?;
    require(
        loaded
            .steps()
            .iter()
            .map(|step| step.prefix_length())
            .eq([1, 2])
            && loaded.full_prefix_calls() == 2
            && loaded.stop() == GenerationStop::ContextLimit,
        "loaded uncached context evidence changed",
    )?;
    require(
        loaded_replay_identical,
        "loaded checkpoint and RNG no longer replay generation",
    )?;
    require(
        eos.generated() == [first_token]
            && eos.stop() == GenerationStop::Eos
            && eos.full_prefix_calls() == 1,
        "EOS stopping evidence changed",
    )?;
    require(
        errors.zero_temperature_rejected
            && errors.zero_top_k_rejected
            && errors.nonfinite_logit_rejected
            && errors.rng_unchanged,
        "invalid settings changed RNG state or escaped validation",
    )?;

    Ok(LearnerEvidence {
        temperatures,
        boundary,
        support,
        greedy,
        seeded_decisions,
        loaded_checkpoint_bytes,
        loaded_rng_state,
        loaded_vocabulary_size,
        loaded_context,
        generation_max_new_tokens: generation_config.max_new_tokens(),
        loaded,
        loaded_replay_identical,
        eos,
        errors,
        history,
    })
}

Выполните cargo run --quiet --locked -p ch36-temperature-top-k. Основные результаты программа выводит напрямую:

top_k=k:2 retained:[3,1] tied_boundary:keep:1 remove:2 sum:1.000000000000
support=tau:2.2250738585072014e-308 top_k:3 retained:[0,1,2] positive_support:[0,1] probabilities:[0.500000000000,0.500000000000,0.000000000000]
sample=seed:36 top_k:3 sequence:[3,2,2,2,3,3,3,3] draws:8 greedy_token:3 greedy_draw:none
checkpoint=loaded_bytes:6330 rng_state:0x9e3779b97f4a7c38 vocabulary:5 context:2 eos:none max_new_tokens:4 prompt:[0] generated:[4,4] prefixes:[1,2] stop:context-limit full_prefix_calls:2 replay_identical:true
eos=vocabulary:5 context:2 eos_token:4 max_new_tokens:4 generated:[4] stop:eos full_prefix_calls:1
errors=temperature_zero:true top_k_zero:true nonfinite_logit:true rng_unchanged:true
history=greedy_token:3 greedy_rng_advanced:false top_k:3 retained:[3,1,2] retained_full_mass:0.927670511871 removed_full_mass:0.072329488129
Вывести точный учебный отчёт главы 36 rust/demos/ch36-temperature-top-k/src/main.rs
fn main() -> Result<(), Box<dyn std::error::Error>> {
    print!("{}", ch36_temperature_top_k::learner_report()?);
    Ok(())
}

Проследите путь распределения от масштабирования температурой до генерации без кэша

Сначала схема сопоставляет три распределения, полученные из одних и тех же четырёх логитов при трёх температурах. Затем она отдельно показывает границу при k=2k=2, а на примере [2,2,1][2,2,1] — различие между тремя ID, отобранными по рангу, и двумя ID в носителе распределения в f64. Далее схема показывает правило с τ=1\tau=1, k=3k=3 и начальным значением генератора 3636 и отмечает интервал, в который попало каждое случайное число. После этого схема переходит от искусственного словаря размером V=4V=4 к словарю загруженного декодера размером V=5V=5. Рядом показаны запуск без EOS, который останавливается по ёмкости контекста, и запуск с токеном 44 в роли EOS. Двойная и пунктирная рамки вместе с текстом обозначают состояния «отобран» и «исключён». Таблица и строки данных показывают точный логит каждого токена, его место в порядке, сохранённую вероятность, принадлежность к множеству top-k и к носителю распределения в f64. Поэтому текстовые состояния можно сопоставить с числовыми данными без опоры на цвет или положение.

Температура меняет вероятности, top-k исключает ID токенов, стоящих ниже в порядке ранжирования, а одно случайное число определяет выбранный токен

Точные данные, выведенные программой на Rust, позволяют сравнить три температуры, отделить множество кандидатов, отобранных по рангу, от носителя распределения в f64, проследить полуоткрытые интервалы для восьми случайных чисел, полученных генератором SplitMix64 из начального состояния 36, и понять, почему останавливается генерация с загруженной контрольной точкой.

  • токен отобран — двойная рамка
  • токен исключён — пунктирная рамка
  • токен выбран по случайному числу

Сравните температуры при одних и тех же логитах

Искусственный словарь размером 4 V=4V=4

В распределении остаются ID всех четырёх токенов из словаря; меняются только отношения вероятностей. На каждой полосе текстом указано десятичное значение из примера на Rust.

Более концентрированное распределение вероятностей

τ=0.500000\tau=0.500000

  1. i=0i=0 q^i=0.014209336619\widehat q_i=0.014209336619
  2. i=1i=1 q^i=0.104993585404\widehat q_i=0.104993585404
  3. i=2i=2 q^i=0.104993585404\widehat q_i=0.104993585404
  4. i=3i=3 q^i=0.775803492574\widehat q_i=0.775803492574
Распределение вероятностей при исходном масштабе логитов

τ=1.000000\tau=1.000000

  1. i=0i=0 q^i=0.072329488129\widehat q_i=0.072329488129
  2. i=1i=1 q^i=0.196611933241\widehat q_i=0.196611933241
  3. i=2i=2 q^i=0.196611933241\widehat q_i=0.196611933241
  4. i=3i=3 q^i=0.534446645389\widehat q_i=0.534446645389
Более сглаженное распределение вероятностей

τ=2.000000\tau=2.000000

  1. i=0i=0 q^i=0.142536956597\widehat q_i=0.142536956597
  2. i=1i=1 q^i=0.235003712202\widehat q_i=0.235003712202
  3. i=2i=2 q^i=0.235003712202\widehat q_i=0.235003712202
  4. i=3i=3 q^i=0.387455619000\widehat q_i=0.387455619000

Отберите ID ровно двух токенов, стоящих первыми в однозначном порядке ранжирования

При температуре, равной единице, меньший ID ставится раньше при равных логитах: токен 1 остаётся в множестве из двух кандидатов, а вероятность токена 2 становится в точности равной нулю.

Таблица кандидатов top-k с однозначным порядком при температуре, равной единице
Токен Логит Место в детерминированном порядке Статус top-k Вероятность, сохранённая в f64
i=0i=0 ℓi=0.000000\ell_i=0.000000 ri=4r_i=4 токен исключён — пунктирная рамка q^i=0.000000000000\widehat q_i=0.000000000000
i=1i=1 ℓi=1.000000\ell_i=1.000000 ri=2r_i=2 токен отобран — двойная рамка q^i=0.268941421370\widehat q_i=0.268941421370
i=2i=2 ℓi=1.000000\ell_i=1.000000 ri=3r_i=3 токен исключён — пунктирная рамка q^i=0.000000000000\widehat q_i=0.000000000000
i=3i=3 ℓi=2.000000\ell_i=2.000000 ri=1r_i=1 токен отобран — двойная рамка q^i=0.731058578630\widehat q_i=0.731058578630

Сопоставьте ID токенов, отобранных по рангу, с носителем распределения в f64

Если логиты имеют вид [ℓ0,ℓ1,ℓ2]=[2,2,1][\ell_0,\ell_1,\ell_2]=[2,2,1], значение температуры равно наименьшему положительному нормальному числу типа f64, а k=3k=3, то все ID входят в множество, отобранное по рангу, но представимый вес и сохранённая вероятность токена 2 равны нулю, поэтому в носитель распределения в f64 входят только токены 0 и 1.

Словарь размером 3 с округлением веса до нуля в f64
tau=2.2250738585072014e-308

Множество, отобранное по рангу K3={0,1,2}K_3=\{0,1,2\}

Носитель распределения в f64 Sτ,3(f64)={0,1}S_{\tau,3}^{(\mathrm{f64})}=\{0,1\}

  1. Токен i=0i=0 Множество, отобранное по рангу да, токен отобран по рангу Вероятность, сохранённая в f64 q^0(τ,3)=0.500000000000\widehat q_0^{(\tau,3)}=0.500000000000 Носитель распределения в f64 токен входит в носитель распределения в f64
  2. Токен i=1i=1 Множество, отобранное по рангу да, токен отобран по рангу Вероятность, сохранённая в f64 q^1(τ,3)=0.500000000000\widehat q_1^{(\tau,3)}=0.500000000000 Носитель распределения в f64 токен входит в носитель распределения в f64
  3. Токен i=2i=2 Множество, отобранное по рангу да, токен отобран по рангу Вероятность, сохранённая в f64 q^2(τ,3)=0.000000000000\widehat q_2^{(\tau,3)}=0.000000000000 Носитель распределения в f64 токен не входит в носитель распределения в f64

q^2(τ,3)=0.000000000000\widehat q_2^{(\tau,3)}=0.000000000000 — токен отобран по рангу; сохранённая вероятность равна нулю; токен не входит в носитель распределения в f64

Повторите случайные выборы из категориального распределения после восстановления того же состояния генератора

Размер словаря остаётся равным 4, а число отобранных кандидатов увеличивается с двух до трёх. Применяется правило случайного выбора с температурой 1 и генератором SplitMix64 в начальном состоянии 36. Алгоритм пропускает все сохранённые вероятности, равные нулю, и обходит интервалы в порядке возрастания ID токенов; интервалы записываются при каждом вызове sample_next_token.

Искусственный словарь размером 4 τ=1.000000, k=3, V=4\tau=1.000000,\ k=3,\ V=4 seed=36 retained=[3,1,2] sum=1.000000000000
  1. Случайное число 1 u=0.912888894097u=0.912888894097 Полуоткрытый интервал [0.423883115234,1.000000000000)[0.423883115234,1.000000000000) Выбранный токен i=3i=3
  2. Случайное число 2 u=0.338833394523u=0.338833394523 Полуоткрытый интервал [0.211941557617,0.423883115234)[0.211941557617,0.423883115234) Выбранный токен i=2i=2
  3. Случайное число 3 u=0.295371378932u=0.295371378932 Полуоткрытый интервал [0.211941557617,0.423883115234)[0.211941557617,0.423883115234) Выбранный токен i=2i=2
  4. Случайное число 4 u=0.350092047261u=0.350092047261 Полуоткрытый интервал [0.211941557617,0.423883115234)[0.211941557617,0.423883115234) Выбранный токен i=2i=2
  5. Случайное число 5 u=0.578054529784u=0.578054529784 Полуоткрытый интервал [0.423883115234,1.000000000000)[0.423883115234,1.000000000000) Выбранный токен i=3i=3
  6. Случайное число 6 u=0.660097051275u=0.660097051275 Полуоткрытый интервал [0.423883115234,1.000000000000)[0.423883115234,1.000000000000) Выбранный токен i=3i=3
  7. Случайное число 7 u=0.836130632904u=0.836130632904 Полуоткрытый интервал [0.423883115234,1.000000000000)[0.423883115234,1.000000000000) Выбранный токен i=3i=3
  8. Случайное число 8 u=0.657589579642u=0.657589579642 Полуоткрытый интервал [0.423883115234,1.000000000000)[0.423883115234,1.000000000000) Выбранный токен i=3i=3

Примените правило случайного выбора при генерации без кэша

Здесь искусственный словарь размером 4 сменяется словарём загруженного декодера размером 5. Для каждого запуска показано точное поведение при EOS и при исчерпании ёмкости контекста.

Словарь загруженного декодера размером 5 V=5V=5 Ёмкость контекста в токенах context=2

Явный жадный режим

i=3i=3 — жадный режим выбирает токен с наибольшим логитом; при равенстве — токен с меньшим ID

draw=none

Жадный режим не меняет состояние генератора.

Генерация с загруженной контрольной точкой

Промпт [0][0] Сгенерированная последовательность [4,4][4,4]

ID токена EOS eos=none

Максимальное число новых токенов max_new_tokens=4

Длины префиксов в токенах prefixes=[1,2]

Вызовы декодера для полных префиксов calls=2

генерация останавливается при исчерпании ёмкости контекста; восстановление начального состояния генератора точно воспроизводит сгенерированную последовательность и конечное состояние генератора

Остановка по EOS

iEOS=4i_{\mathrm{EOS}}=4

ID токена EOS eos=4

Максимальное число новых токенов max_new_tokens=4

Сгенерированная последовательность generated=[4]

Вызовы декодера для полных префиксов calls=1

токен EOS остаётся в сгенерированной последовательности

Ошибки без изменения состояния генератора
temperature_zero=true top_k_zero=true nonfinite_logit=true rng_unchanged=true

При некорректных настройках функция выбора следующего токена возвращает ошибку до изменения состояния генератора.

Сначала сделайте предсказания, затем проверьте их

  1. Какой ID выберет жадный режим для логитов [0,1,1,2][0,1,1,2]?
  2. Какой из токенов с равными логитами остаётся в множестве top-k при k=2k=2?
  3. Изменит ли повышение τ\tau порядок токенов?
  4. Почему τ=0\tau=0 недопустимо, хотя предел τ→0+\tau\to0^+ помогает понять поведение распределения?
  5. Запрашивает ли стохастический режим с k=1k=1 случайное число?
  6. В интервал какого токена попадает число u=0.338833394523u=0.338833394523 в примере с k=3k=3?
  7. Включается ли токен EOS в сгенерированную последовательность?
  8. Почему при префиксе длины 22 и ёмкости контекста 22 декодер может выдать ещё один токен до остановки по контексту?
  9. Для логитов [2,2,1][2,2,1], температуры f64::MIN_POSITIVE и k=3k=3 входит ли отобранный по рангу токен 22 в носитель распределения в f64?
Проверьте девять предсказаний
  1. Побеждает токен 33, потому что его логит 22 — единственный максимум.
  2. Остаётся токен 11: при равных логитах меньший ID идёт первым, поэтому токен 11 попадает в top-k, токен 22 исключается, а его вероятность становится в точности равной нулю.
  3. Нет. Положительная температура меняет отношения вероятностей, но сохраняет порядок логитов.
  4. Предел описывает концентрацию, а нулевая температура потребовала бы деления на ноль; детерминированный выбор токена с максимальным логитом поэтому вынесен в отдельный жадный режим.
  5. Да. Он выбирает тот же ID, что и жадный режим, но остаётся стохастическим и запрашивает ровно одно случайное число.
  6. Токену 22 принадлежит интервал [0.211941557617,0.423883115234)[0.211941557617,0.423883115234), содержащий это число.
  7. Да. Токен 44 добавляется в последовательность перед остановкой по EOS.
  8. Декодер ещё может принять префикс длины 22 как вход и предсказать следующий токен. Получившаяся последовательность длины 33 сохраняется как результат, но больше не подаётся в декодер: следующий вызов превысил бы ёмкость контекста.
  9. Нет. Токен 22 входит в K3K_3, но его представимый вес округляется до нуля, поэтому q^2=0\widehat q_2=0, а Sτ,3(f64)={0,1}S_{\tau,3}^{(\mathrm{f64})}=\{0,1\}.

При поэтапной генерации результат должен совпасть с последовательностью без кэша

К этому этапу программа умеет загрузить выбранную контрольную точку, преобразовать строку логитов последней позиции в управляемое распределение следующего токена, повторить выбор после восстановления состояния генератора, остановиться при появлении EOS или исчерпании ёмкости контекста и получить эталонную последовательность без кэша, которую поэтапные вычисления в главе 37 должны точно воспроизвести.

Глава 37 будет сохранять в кэше ранее вычисленные векторы ключей и значений одного слоя внимания. Результат для последней добавленной позиции должен совпасть с результатом вычисления полного префикса из этой главы, прежде чем глава 38 распространит кэширование на весь декодер.