🤖 AI

Qrita: High-performance Top-k and Top-p using Pivot-based Truncation and Selection

Le papier présente Qrita, un algorithme d'échantillonnage Top-k et Top-p déterministe et haute performance pour les grands vocabulaires, qui utilise une troncature et une sélection basées sur des pivots pour atteindre une amélioration du débit allant jusqu'à 1,4 fois et une réduction de la mémoire de 50 % par rapport aux noyaux GPU existants, conduisant à son adoption en tant que sélecteur par défaut dans vLLM.

Auteurs originaux : Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

Publié 2026-05-27

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un chef dirigeant une immense cuisine (un modèle de langage de grande taille) avec un garde-manger contenant 100 000 ingrédients différents (le vocabulaire). Chaque fois que vous devez préparer un plat (générer un mot), vous devez choisir les meilleurs ingrédients parmi ce garde-manger géant pour garantir que le repas ait bon goût sans être ennuyeux.

Dans le monde de l'IA, ce processus de sélection s'appelle Top-k (choisir les k meilleurs ingrédients) et Top-p (choisir le plus petit groupe d'ingrédients dont la somme atteint un certain « score de saveur »).

Le Problème : La Cuisine Lente et Encombrée

Actuellement, la plupart des cuisines gèrent cela en déversant les 100 000 ingrédients sur un immense comptoir, en les triant par « score de saveur » du meilleur au pire, puis en récupérant les meilleurs.

Le Problème : Trier 100 000 éléments est lent et désordonné. Cela occupe une énorme surface de comptoir (mémoire) et les mains du chef se fatiguent (surcharge de calcul).
L'Alternative : Certains chefs tentent simplement de saisir une poignée aléatoire d'ingrédients qui pourraient être bons. Mais c'est risqué ; parfois, vous manquez les meilleurs ingrédients, et parfois le plat sort différent à chaque fois que vous le cuisinez (non déterministe), ce qui est mauvais si vous devez reproduire une recette exactement.

La Solution : Qrita (Le Second de Cuisine Intelligent)

L'article présente Qrita, une nouvelle méthode rapide pour choisir les ingrédients. Considérez Qrita comme un second de cuisine ultra-intelligent qui utilise deux astuces ingénieuses pour éviter complètement le tri désordonné.

Astuce 1 : La « Troncature Sigma Gaussienne » (Le Filtre à Bruit)

Imaginez que dans votre garde-manger de 100 000 ingrédients, 99 000 d'entre eux ne sont que du « bruit » (comme du sel, du sucre et de la farine qui ont tous un goût fade à peu près identique). Seuls quelques centaines sont les « ingrédients vedettes » (comme les truffes ou le safran).

Au lieu d'examiner chaque bocal, Qrita effectue un rapide test d'odorat. Il calcule le goût moyen et le « piquant » (écart-type) du garde-manger. Il trace ensuite une ligne : « Tout ce qui est en dessous de cette ligne n'est que du bruit ; nous n'avons pas besoin de le regarder. »

Le Résultat : Il élimine instantanément 99 % du garde-manger, ne laissant que les 200 bocaux environ qui présentent un intérêt. Cela se produit en un seul passage, fulgurant.

Astuce 2 : La « Recherche par Pivot Quaternaire » (La Division en Quatre)

Maintenant, le chef a une petite pile de 200 ingrédients intéressants. Il doit toujours trouver exactement les 50 meilleurs.

Ancienne Méthode : Vérifier un par un (trop lent) ou diviser la pile en deux (recherche binaire).
Méthode de Qrita : Au lieu de diviser la pile en deux, Qrita la divise en quatre sections à la fois. Il demande : « L'ingrédient le meilleur se trouve-t-il dans le premier quart, le deuxième, le troisième ou le quatrième ? »
Le Bonus : Il dispose également d'une règle spéciale pour les ingrédients dupliqués. Si trois bocaux de « Safran » ont exactement le même score, Qrita sait exactement combien en conserver pour garantir que la recette soit identique à chaque fois (déterministe). Cela empêche le chef de rester bloqué dans une boucle infinie en essayant de décider entre des bocaux identiques.

Pourquoi Cela Compte (Les Résultats)

Les auteurs ont construit Qrita en utilisant un outil spécialisé appelé Triton (un langage de programmation pour les cartes graphiques/GPU) et l'ont testé contre les meilleures méthodes actuelles utilisées par les principaux moteurs d'IA comme vLLM et SGLang.

Vitesse : Qrita est jusqu'à 1,4 fois plus rapide dans des scénarios de service réels et jusqu'à 2 fois plus rapide dans des tests de vitesse brute.
Mémoire : Il utilise la moitié de la mémoire car il n'a pas besoin de stocker toute la liste triée de 100 000 éléments.
Précision : Contrairement à certaines méthodes rapides qui devinent, Qrita vous donne exactement le même résultat que la méthode de tri lente et parfaite. Il ne modifie pas la sortie ; il la trouve simplement beaucoup plus vite.

La Conclusion

Qrita, c'est comme passer d'un chef qui trie manuellement chaque épice du monde à un assistant intelligent qui ignore instantanément les choses ennuyeuses, divise les choses intéressantes en quatre piles à la fois et gère parfaitement les doublons. Cela rend la génération par IA plus rapide et plus efficace sans modifier la qualité des réponses.

Note : L'article mentionne que Qrita est désormais la méthode par défaut pour le chemin GPU dans vLLM, un outil populaire pour exécuter des modèles d'IA, et que le code est disponible pour que d'autres puissent l'utiliser.

Résumé technique : Qrita - Top-k et Top-p haute performance utilisant la truncation et la sélection basées sur un pivot

Énoncé du problème

La mise en œuvre efficace des algorithmes d'échantillonnage Top-k et Top-p pour les grands modèles de langage (LLM) disposant de grands vocabulaires (dépassant souvent 100 000 tokens) reste un défi majeur sur les GPU. Les approches existantes font face à un compromis entre l'efficacité computationnelle et la justesse de la sortie :

Méthodes basées sur le tri : Utilisées par des moteurs comme vLLM, elles fournissent des résultats exacts et déterministes, mais entraînent une surcharge computationnelle et mémoire élevée due au tri du vocabulaire complet et aux accès mémoire non contigus.
Méthodes stochastiques : Des bibliothèques comme FlashInfer et SGLang utilisent l'échantillonnage par rejet pour éviter le tri, offrant un débit élevé. Cependant, elles ne renvoient qu'un seul token échantillonné plutôt que l'ensemble complet des candidats, les rendant incompatibles avec des tâches nécessitant des ensembles de candidats déterministes, telles que la vérification par décodage spéculatif et l'apprentissage par renforcement.
Méthodes de seuil statistique : Des approches comme Top-nσ et Min-p éliminent le tri en utilisant des seuils statistiques (par exemple, la moyenne et l'écart-type). Bien qu'efficaces, elles altèrent la distribution d'échantillonnage et la sortie, conduisant à des débats concernant la qualité et la cohérence de la génération.

Il existe un vide critique pour un algorithme offrant à la fois une efficacité mémoire et un comportement déterministe strict (renvoyant l'ensemble complet des candidats) sans sacrifier la sémantique exacte des Top-k et Top-p.

Méthodologie

Les auteurs proposent Qrita, un algorithme Top-k et Top-p haute performance pour les GPU basé sur la truncation et la sélection basées sur un pivot. Qrita étend la stratégie basée sur un pivot de RTop-k (initialement conçue pour les réseaux de neurones graphiques) pour gérer les grands vocabulaires de LLM tout en garantissant le déterminisme. La méthode repose sur deux techniques clés :

1. Truncation $\sigma$ basée sur une distribution gaussienne

Reconnaissant que les logits des LLM suivent généralement une distribution quasi-gaussienne où les tokens à haute probabilité forment des valeurs aberrantes par rapport à un fond « bruyant », Qrita emploie une étape de pré-filtrage.

Mécanisme : L'algorithme approxime la distribution des logits comme $Z \sim \mathcal{N}(\mu, \sigma^2)$ . Il calcule la moyenne ( $\mu$ ) et l'écart-type ( $\sigma$ ) à partir d'un bloc d'échantillons et détermine un seuil de truncation $t = \mu + \delta \cdot \sigma$ .
Tables de recherche : Le coefficient $\delta$ est déterminé via des tables de recherche précalculées dérivées de la fonction quantile normale, adaptées aux valeurs de $k$ ou $p$ cibles.
Résultat : Cette étape tronque la massive région de « bruit » du vocabulaire en un seul passage. Si la taille de l'ensemble tronqué $|Z_t|$ dépasse le $k$ cible (un « succès de truncation »), la recherche ne procède que sur ce sous-ensemble plus petit. Sinon, elle revient à l'ensemble complet des logits. Cela réduit considérablement l'espace de recherche pour la recherche de pivot ultérieure.

2. Recherche de pivot quaternaire avec gestion des duplicatas

Pour trouver la valeur de pivot exacte $\tau$ (où exactement $k$ éléments sont $\ge \tau$ ) de manière efficace et déterministe :

Recherche quaternaire : Au lieu d'une recherche binaire, Qrita évalue trois pivots (aux percentiles 25, 50 et 75 de la plage de recherche actuelle) à chaque itération. Cela réduit le nombre d'itérations de recherche de moitié par rapport à la recherche binaire.
Gestion des duplicatas : Les recherches de pivot standard peuvent échouer ou devenir non déterministes lorsque des valeurs de logits dupliquées existent (fréquentes dans les distributions de faible précision ou à longue traîne). Qrita suit la valeur de logits minimale supérieure au pivot ( $z_{mn}$ ) et son nombre d'occurrences ( $N_{zmn}$ ).
Condition d'arrêt : La recherche s'arrête lorsqu'un pivot $\tau_n$ est trouvé tel que le nombre d'éléments strictement supérieurs à $\tau_n$ est inférieur à $k$ , mais que le nombre d'éléments supérieurs ou égaux à la valeur minimale dupliquée $z_{mn}$ est supérieur ou égal à $k$ . Cela permet à l'algorithme de déterminer précisément combien d'instances dupliquées de la valeur de limite doivent être conservées pour satisfaire la contrainte Top-k, garantissant des sorties reproductibles et déterministes.

Détails de l'implémentation

Cadre : Implémenté en utilisant Triton, un langage de programmation GPU.
Autotuning : Utilise une stratégie « Autotune de taille de bloc Triton à niveaux ». Étant donné que la taille du vecteur varie considérablement entre l'ensemble complet des logits et l'ensemble tronqué, le compilateur est autorisé à sélectionner des tailles de blocs optimales (par exemple, des blocs plus grands pour les ensembles complets, plus petits pour les ensembles tronqués) afin de maximiser l'utilisation du matériel.
Pipeline : L'algorithme traite les lots en parallèle, appliquant la truncation gaussienne, suivie de la recherche quaternaire, et enfin la génération d'un masque de gestion des duplicatas pour produire la sortie finale.

Contributions clés

Échantillonnage déterministe haute performance : Qrita fournit l'ensemble complet des candidats Top-k/Top-p (contrairement à FlashInfer/SGLang) tout en maintenant la sémantique exacte des algorithmes basés sur le tri, le rendant adapté au décodage spéculatif et à l'apprentissage par renforcement.
Réduction de l'espace de recherche : En exploitant les propriétés statistiques des logits, la truncation $\sigma$ gaussienne réduit drastiquement l'espace de recherche, évitant le tri du vocabulaire complet.
Recherche de pivot robuste : L'introduction de la recherche quaternaire combinée à une gestion explicite des duplicatas garantit un comportement déterministe et réduit le nombre d'itérations, répondant aux inefficacités des méthodes standard basées sur un pivot sur les grands vocabulaires.
Intégration : Qrita est implémenté comme l'échantillonneur Top-k et Top-p par défaut pour le chemin d'exécution GPU de vLLM.

Résultats

Les auteurs ont évalué Qrita par rapport à des références incluant le tri naïf PyTorch, l'échantillonneur par défaut de vLLM, FlashInfer et SGLang sur des GPU NVIDIA H100, RTX4090 et AMD MI355X en utilisant divers modèles (Llama, Qwen, GPT-OSS, Gemma).

Débit : Qrita réalise une amélioration du débit de service de bout en bout allant jusqu'à 1,4 $\times$ par rapport à la référence vLLM sur H100, certaines configurations montrant une amélioration allant jusqu'à 2 $\times$ sur RTX4090. Il surpasse significativement les références basées sur le tri tout en correspondant à la sortie des algorithmes basés sur le tri.
Utilisation mémoire : Qrita réduit l'utilisation mémoire d'environ 50 % par rapport aux méthodes basées sur le tri, principalement en évitant l'allocation de grands tampons intermédiaires requis pour le tri.
Études d'ablation :
- Truncation gaussienne : Fournit l'accélération la plus importante, réduisant la latence d'environ 74 % par rapport à la recherche sur l'ensemble complet des logits.
- Recherche quaternaire : Bien que légèrement plus lente que la recherche binaire dans les cas de « succès de truncation » en raison de l'espace de recherche réduit, elle offre une réduction significative de la latence (~2,3 ms) dans les cas de repli où le vocabulaire complet doit être recherché.
- Gestion des duplicatas : Ajoute une surcharge minimale (~3,5 % d'augmentation de la latence) mais est cruciale pour la justesse et le déterminisme.
- Autotuning : Réduit la latence d'exécution de près de 30 % par rapport à l'utilisation d'une taille de bloc fixe unique.

Importance et revendications

L'article revendique que Qrita comble le fossé entre l'efficacité mémoire et le comportement déterministe strict pour le décodage de grands vocabulaires. Il affirme qu'en évitant le tri du vocabulaire complet et en exploitant la sélection basée sur un pivot avec un pré-filtrage statistique, Qrita offre une solution haute performance pour le décodage des LLM compatible avec des tâches avancées nécessitant des ensembles complets de candidats (par exemple, le décodage spéculatif). Les auteurs positionnent Qrita non pas comme un remplacement des sémantiques statistiques des Top-k/Top-p, mais comme une implémentation efficace qui les préserve exactement, contrairement aux méthodes de seuil statistique heuristiques ou aux échantillonneurs stochastiques de token unique. L'intégration dans vLLM en tant qu'échantillonneur par défaut souligne son utilité pratique dans les environnements de production.