const CHARS_PER_TOKEN: usize = 4;
const PUNCT_TOKENS_NUMERATOR: usize = 2;
const PUNCT_TOKENS_DENOMINATOR: usize = 3;
const WORD_CEILING_NUMERATOR: usize = 3;
const WORD_CEILING_DENOMINATOR: usize = 4;
pub fn approx_tokens(text: &str) -> usize {
let mut word_chars = 0usize;
let mut punct_chars = 0usize;
let mut wide = 0usize;
for c in text.chars() {
if c.is_ascii_alphanumeric() {
word_chars += 1;
} else if c.is_ascii() {
if !c.is_whitespace() {
punct_chars += 1;
}
} else {
wide += c.len_utf8().saturating_sub(1);
}
}
word_chars.div_ceil(CHARS_PER_TOKEN)
+ (punct_chars * PUNCT_TOKENS_NUMERATOR).div_ceil(PUNCT_TOKENS_DENOMINATOR)
+ wide
}
pub fn max_tokens(text: &str) -> usize {
let mut ceiling = Ceiling::new();
for c in text.chars() {
ceiling.push(c);
}
ceiling.tokens()
}
#[derive(Debug, Clone, Copy, Default)]
pub(crate) struct Ceiling {
settled: usize,
run: Run,
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
enum Run {
#[default]
None,
Word {
chars: usize,
has_letter: bool,
has_digit: bool,
inner_capital: bool,
},
Space {
chars: usize,
first: char,
uniform: bool,
},
}
impl Ceiling {
pub(crate) fn new() -> Ceiling {
Ceiling::default()
}
pub(crate) fn push(&mut self, c: char) {
match (&mut self.run, classify(c)) {
(
Run::Word {
chars,
has_letter,
has_digit,
inner_capital,
},
Class::Word,
) => {
*inner_capital |= c.is_ascii_uppercase();
*has_letter |= c.is_ascii_alphabetic();
*has_digit |= c.is_ascii_digit();
*chars += 1;
}
(
Run::Space {
chars,
first,
uniform,
},
Class::Space,
) => {
*uniform &= c == *first;
*chars += 1;
}
(_, class) => {
self.settled += self.run.tokens(true);
self.run = match class {
Class::Word => Run::Word {
chars: 1,
has_letter: c.is_ascii_alphabetic(),
has_digit: c.is_ascii_digit(),
inner_capital: false,
},
Class::Space => Run::Space {
chars: 1,
first: c,
uniform: true,
},
Class::Other => {
self.settled += c.len_utf8();
Run::None
}
};
}
}
}
pub(crate) fn tokens(&self) -> usize {
self.settled + self.run.tokens(false)
}
}
impl Run {
fn tokens(&self, folded: bool) -> usize {
match *self {
Run::None => 0,
Run::Word {
chars,
has_letter,
has_digit,
inner_capital,
} => {
let plain = has_letter && !has_digit && !inner_capital;
if plain {
(chars * WORD_CEILING_NUMERATOR)
.div_ceil(WORD_CEILING_DENOMINATOR)
.max(1)
} else {
chars
}
}
Run::Space {
chars,
first: _,
uniform,
} => {
let paid = chars.saturating_sub(usize::from(folded));
if uniform {
paid.div_ceil(2)
} else {
paid
}
}
}
}
}
enum Class {
Word,
Space,
Other,
}
fn classify(c: char) -> Class {
if c.is_ascii_alphanumeric() {
Class::Word
} else if c.is_ascii_whitespace() {
Class::Space
} else {
Class::Other
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct TokenBudget {
pub per_page: Option<usize>,
pub total: Option<usize>,
}
impl TokenBudget {
pub const fn unlimited() -> TokenBudget {
TokenBudget {
per_page: None,
total: None,
}
}
pub const fn total(tokens: usize) -> TokenBudget {
TokenBudget {
per_page: None,
total: Some(tokens),
}
}
pub const fn per_page(tokens: usize) -> TokenBudget {
TokenBudget {
per_page: Some(tokens),
total: None,
}
}
pub const fn and_per_page(mut self, tokens: usize) -> TokenBudget {
self.per_page = Some(tokens);
self
}
pub const fn is_unlimited(&self) -> bool {
self.per_page.is_none() && self.total.is_none()
}
pub fn split(&self, costs: &[usize]) -> Vec<usize> {
let capped: Vec<usize> = costs
.iter()
.map(|cost| match self.per_page {
Some(cap) => (*cost).min(cap),
None => *cost,
})
.collect();
let Some(total) = self.total else {
return capped;
};
let weight: u128 = capped.iter().map(|cost| *cost as u128).sum();
if weight <= total as u128 {
return capped;
}
let mut shares: Vec<usize> = Vec::with_capacity(capped.len());
let mut remainders: Vec<(u128, usize)> = Vec::with_capacity(capped.len());
for (index, cost) in capped.iter().enumerate() {
let exact = *cost as u128 * total as u128;
shares.push(usize::try_from(exact / weight).unwrap_or(total));
remainders.push((exact % weight, index));
}
let mut spare = total.saturating_sub(shares.iter().sum::<usize>());
remainders.sort_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(&b.1)));
for (_, index) in remainders {
if spare == 0 {
break;
}
if let Some(share) = shares.get_mut(index) {
*share += 1;
spare -= 1;
}
}
shares
}
}
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::expect_used,
clippy::panic,
clippy::unreachable,
clippy::indexing_slicing,
clippy::string_slice
)]
use super::*;
#[test]
fn nothing_costs_nothing() {
assert_eq!(approx_tokens(""), 0);
assert_eq!(max_tokens(""), 0);
}
#[test]
fn the_estimate_grows_with_the_text() {
let short = "The quick brown fox.";
let long = "The quick brown fox jumps over the lazy dog, twice, and then rests.";
assert!(approx_tokens(long) > approx_tokens(short));
let doubled = format!("{long} {long}");
let ratio = approx_tokens(&doubled) as f64 / approx_tokens(long) as f64;
assert!((1.9..=2.1).contains(&ratio), "ratio was {ratio}");
}
#[test]
fn the_estimate_is_close_to_four_characters_a_token_on_prose() {
let prose = "Spider fetches a page and hands back what you asked for, which is \
usually a great deal less than the page itself weighed.";
let estimate = approx_tokens(prose) as f64;
let chars = prose.chars().count() as f64;
let per_token = chars / estimate;
assert!(
(3.0..=5.0).contains(&per_token),
"{per_token} characters a token"
);
}
#[test]
fn punctuation_costs_more_than_the_same_run_of_letters() {
let letters = approx_tokens("abcdefgh");
let punctuation = approx_tokens("{}[]<>()");
assert!(
punctuation > letters,
"{punctuation} should be more than {letters}"
);
}
#[test]
fn the_ceiling_never_reads_below_the_estimate() {
for text in [
"",
" ",
"\n\n\n",
"a",
"The quick brown fox jumps over the lazy dog.",
"蜘蛛云是一个网页抓取服务。它把网页转换成结构化的数据。",
"ウェブページを取得して、必要な部分だけを返すサービスです。",
"a3f9c2e1b7d4508f6a2c9e3b1d7f4085c6a29e3b1d7f4085",
"<div class=\"grid\" data-testid=\"x\"><img src=\"data:image/png;base64,iVBOR\"></div>",
"{\"price\":12.5,\"title\":\"Steel widget\",\"tags\":[\"a\",\"b\"]}",
"🚀🔥✨ shipped 👨👩👧👦 today",
"Сервис извлекает веб-страницы и возвращает только то, что вы просили.",
] {
assert!(
approx_tokens(text) <= max_tokens(text),
"the ceiling read below the estimate on {text:?}"
);
}
}
#[test]
fn the_ceiling_covers_what_a_byte_pair_tokenizer_charges() {
let measured: &[(&str, usize)] = &[
("蜘蛛云是一个网页抓取服务。它可以把任何网页转换成结构化的数据,供大型语言模型使用。", 74),
("ウェブページを取得して、必要な部分だけを返すサービスです。", 44),
("웹 페이지를 가져와서 필요한 부분만 돌려주는 서비스입니다.", 44),
("漢漢漢漢漢漢漢漢漢漢", 20),
("Сервис извлекает веб-страницы и возвращает только то, что вы просили.", 40),
("यह सेवा वेब पेज लाती है", 39),
("🚀🔥✨🎉💡📦🧪🌍🐍⚡", 30),
("👨👩👧👦", 14),
("a3f9c2e1b7d4508f6a2c9e3b1d7f4085c6a29e3b1d7f4085c6a29e3b1d7f4085", 54),
("iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJ", 20),
("HTML XML JSON API URL HTTP TLS SDK CLI", 21),
("The quick brown fox jumps over the lazy dog.", 10),
];
for (text, charged) in measured {
assert!(
max_tokens(text) >= *charged,
"the ceiling read {} for text a tokenizer charges {charged} for: {text:?}",
max_tokens(text)
);
}
}
#[test]
fn a_chinese_page_no_longer_reads_at_a_quarter_of_its_cost() {
let page = "蜘蛛云是一个网页抓取服务。它可以把任何网页转换成结构化的数据,\
供大型语言模型使用。我们提供多种返回格式,包括纯文本、Markdown、\
清理过的 HTML 以及页面链接列表。";
assert!(max_tokens(page) >= 150, "{}", max_tokens(page));
assert!(approx_tokens(page) >= 100, "{}", approx_tokens(page));
}
#[test]
fn whitespace_is_free_between_words_and_costs_something_on_its_own() {
assert_eq!(max_tokens("a b"), max_tokens("a") + max_tokens("b"));
assert!(max_tokens(" \n\n\t \r\n ") >= 3);
}
#[test]
fn whitespace_outside_ascii_does_not_pull_the_ceiling_under_the_estimate() {
for text in [
"\u{3000}",
"\u{3000}\u{3000}\u{3000}",
"\u{a0}",
"\u{2003}\u{2009}",
"漢\u{3000}漢",
"a\u{3000}b",
"\u{feff}\u{3000}",
] {
assert!(
approx_tokens(text) <= max_tokens(text),
"the ceiling read {} under the estimate {} on {text:?}",
max_tokens(text),
approx_tokens(text)
);
}
}
#[test]
fn a_run_that_looks_like_a_hash_costs_more_than_a_run_that_looks_like_a_word() {
assert!(max_tokens("a3f9c2e1") > max_tokens("elephant"));
assert!(max_tokens("HTML") > max_tokens("html"));
}
#[test]
fn reading_one_character_at_a_time_costs_what_reading_the_whole_prefix_costs() {
let text = "Steel widget, 40mm. 不锈钢部件 🚀 https://example.com/p/89?a=1";
let mut ceiling = Ceiling::new();
let mut taken = String::new();
for c in text.chars() {
ceiling.push(c);
taken.push(c);
assert_eq!(
ceiling.tokens(),
max_tokens(&taken),
"walking {taken:?} disagreed with reading it whole"
);
}
}
#[test]
fn a_budget_with_no_total_only_applies_its_page_cap() {
let budget = TokenBudget::per_page(100);
assert_eq!(budget.split(&[50, 200, 100]), vec![50, 100, 100]);
assert!(!budget.is_unlimited());
assert!(TokenBudget::unlimited().is_unlimited());
}
#[test]
fn a_total_splits_in_proportion_to_what_each_page_costs() {
let budget = TokenBudget::total(1000);
let shares = budget.split(&[1000, 2000, 3000]);
assert_eq!(shares.iter().sum::<usize>(), 1000);
assert_eq!(shares, vec![167, 333, 500]);
}
#[test]
fn pages_that_already_fit_are_left_alone() {
let budget = TokenBudget::total(5000);
assert_eq!(budget.split(&[100, 200]), vec![100, 200]);
}
#[test]
fn a_page_cap_and_a_total_both_apply() {
let budget = TokenBudget::total(600).and_per_page(200);
let shares = budget.split(&[1000, 1000, 1000]);
assert_eq!(shares, vec![200, 200, 200]);
assert_eq!(shares.iter().sum::<usize>(), 600);
}
#[test]
fn a_split_holds_its_total_on_costs_too_large_to_multiply() {
let budget = TokenBudget::total(3);
let shares = budget.split(&[usize::MAX / 2, usize::MAX / 2, 4]);
assert!(
shares.iter().sum::<usize>() <= 3,
"shares {shares:?} against a total of 3"
);
let budget = TokenBudget::total(usize::MAX / 4);
let shares = budget.split(&[usize::MAX / 2, usize::MAX / 2]);
assert!(shares.iter().all(|share| *share <= usize::MAX / 4));
assert!(shares.iter().sum::<usize>() <= usize::MAX / 4);
}
#[test]
fn splitting_nothing_hands_back_nothing() {
assert_eq!(TokenBudget::total(100).split(&[]), Vec::<usize>::new());
assert_eq!(TokenBudget::total(100).split(&[0, 0]), vec![0, 0]);
}
}