Navigation : Index | << Précédent | Suivant >>

Semantic-fleet : router les prompts par préfixe — le PromptMatcher radix-tree

Série : SemanticKernel — démos interactives (C# .NET Interactive) · Niveau : intermédiaire · Durée : ~40 min

Le problème du routage

Le sous-module semantic-fleet héberge depuis 2023 le connecteur MultiConnector : une flotte de connecteurs de complétion (des grands modèles aux petits moteurs spécialisés) derrière une seule façade, avec l’idée directrice de differential text completion with online vetting — chaque prompt est routé vers un connecteur capable et bon marché, et les réponses peuvent être confrontées.

Pour router, le MultiConnector ne regarde pas le sens du prompt : il regarde son préfixe. Un catalogue de signatures — "Traduis en anglais:", "Résume le texte suivant:"… — associe chaque préfixe à un réglage de connecteur. La question algorithmique : pour un prompt entrant, quelle entrée du catalogue est le plus long préfixe qui lui correspond ?

  • L’implémentation historique de v0.34.3 (SimpleMatchPromptSettings) fait un scan linéaire : FirstOrDefault(p => prompt.StartsWith(p.Signature.PromptStart)) — O(n) par requête, et elle renvoie la première correspondance, pas la plus longue.
  • L’Axe 4 de l’Epic #1210 a livré dans le sous-module un remplacement drop-in : RadixTreePromptMatcher, un arbre radix (trie compactée) dont le coût de recherche est proportionnel à la longueur du préfixe lu — pas à la taille du catalogue.

Ce notebook consomme l’organe réel du sous-module (tools/radix, net9.0, zéro dépendance) — pas une réimplémentation. Sa jumelle pédagogique Aspire 07 redistille la physique du MultiConnector (files, vetting, télémétrie) en BCL pur ; ici, c’est le routage qui est étudié, sur le code mergé.

Prérequis (une fois par machine)

git submodule update --init MyIA.AI.Notebooks/GenAI/SemanticKernel/semantic-fleet
dotnet build MyIA.AI.Notebooks/GenAI/SemanticKernel/semantic-fleet/tools/radix/src/SemanticFleet.Radix.csproj

Le notebook référence la DLL produite (convention de la série MGS-vs-mealpy pour MetaGeneticSharp). Sans appel réseau : tout se joue sur des catalogues et des prompts synthétiques.

// L'organe reel : DLL construite depuis le sous-module semantic-fleet (tete 9df3603).
// Prerequis : git submodule update --init + dotnet build tools/radix/src/SemanticFleet.Radix.csproj
#r "semantic-fleet/tools/radix/src/bin/Debug/net9.0/SemanticFleet.Radix.dll"

using SemanticFleet.Radix;
using System.Diagnostics;

La surface minimale du matcher

Quatre types publics composent le module. C’est volontairement minuscule : le vrai MultiTextCompletionSettings de semantic-fleet porte en plus le routage par connecteur, les politiques de retry et les coûts — hors périmètre du matching.

public sealed record CompletionJob(string Prompt);                          // la requête entrante
public sealed record SignaturePrefix(string PromptStart);                    // le préfixe signataire
public sealed record PromptMultiConnectorSettings(SignaturePrefix Signature);// une entrée du catalogue

public static class RadixTreePromptMatcher                                   // l'organe Axe 4
{
    public static PromptMultiConnectorSettings? Match(job, settings);        // drop-in (reconstruit l'arbre à chaque appel)
    public static RadixTree<PromptMultiConnectorSettings> BuildTree(settings);// arbre pré-construit
    public static PromptMultiConnectorSettings? MatchWithTree(job, tree);    // recherche sur arbre pré-construit
}
public static class SimpleMatchPromptSettings                                // la baseline v0.34.3, verbatim
{
    public static PromptMultiConnectorSettings? Match(job, settings);        // FirstOrDefault(StartsWith) — O(n)
}

Le PromptMatcher de semantic-fleet est un délégué configurable — la forme Func<CompletionJob, IEnumerable<PromptMultiConnectorSettings>, PromptMultiConnectorSettings?> est exactement celle du hook : le matcher radix s’y branche sans toucher au cœur du connecteur.

// Un catalogue realiste : cinq signatures de prompts, chacune mene a un reglage de connecteur different.
var catalogue = new[]
{
    new PromptMultiConnectorSettings(new SignaturePrefix("Traduis en anglais:")),
    new PromptMultiConnectorSettings(new SignaturePrefix("Traduis en")),
    new PromptMultiConnectorSettings(new SignaturePrefix("Résume le texte suivant:")),
    new PromptMultiConnectorSettings(new SignaturePrefix("Relis ce code et signale:")),
    new PromptMultiConnectorSettings(new SignaturePrefix("Extrais les entités de:")),
};

Console.WriteLine($"Catalogue : {catalogue.Length} signatures");
foreach (var e in catalogue)
    Console.WriteLine($"  - [{e.Signature.PromptStart.Length,2} car.] {e.Signature.PromptStart}");
Catalogue : 5 signatures
  - [19 car.] Traduis en anglais:
  - [10 car.] Traduis en
  - [24 car.] Résume le texte suivant:
  - [25 car.] Relis ce code et signale:
  - [23 car.] Extrais les entités de:

L’arbre radix et la sémantique du plus long préfixe

Un arbre radix est un trie où les chaînes de nœuds à enfant unique sont compactées : une arête porte un segment de clé, pas un caractère. BuildTree insère chaque signature ; LongestPrefixLookup descend le long du prompt en mémorisant la dernière valeur rencontrée sur un nœud terminal — le plus long préfixe enregistré qui préfixe le prompt.

Comparons les trois régimes sur des prompts triviaux :

// Trois requetes : correspondance exacte, correspondance partielle, aucune correspondance.
var arbre = RadixTreePromptMatcher.BuildTree(catalogue);
Console.WriteLine($"Arbre construit : {arbre.Count} cles terminales\n");

string[] prompts =
{
    "Traduis en anglais: hello world",
    "Traduis en espagnol: buenos dias",   // correspond a la signature courte, pas a la longue
    "Rédige-moi un sonnet",               // aucune signature ne prefixe
};

foreach (var p in prompts)
{
    var viaArbre = RadixTreePromptMatcher.MatchWithTree(new CompletionJob(p), arbre);
    var viaScan  = SimpleMatchPromptSettings.Match(new CompletionJob(p), catalogue);
    Console.WriteLine($"prompt   : {p}");
    Console.WriteLine($"  arbre  -> {viaArbre?.Signature.PromptStart ?? "(null)"}");
    Console.WriteLine($"  scan   -> {viaScan?.Signature.PromptStart ?? "(null)"}\n");
}
Arbre construit : 5 cles terminales

prompt   : Traduis en anglais: hello world
  arbre  -> Traduis en anglais:
  scan   -> Traduis en anglais:

prompt   : Traduis en espagnol: buenos dias
  arbre  -> Traduis en
  scan   -> Traduis en

prompt   : Rédige-moi un sonnet
  arbre  -> (null)
  scan   -> (null)

Deux observations déjà :

  • pour "Traduis en espagnol:…", l’arbre renvoie "Traduis en" (plus long préfixe enregistré qui correspond) alors que le scan renvoie aussi "Traduis en anglais:"… ou pas : StartsWith est faux ici, le scan retombe sur la même entrée. La vraie divergence d’ordre arrive dès que deux préfixes compatibles sont dans le désordre — c’est l’exercice 1.
  • pour un prompt sans correspondance, les deux renvoient null : le comportement « aucune signature → null » est celui que le connecteur historique attend.

Exercice 1 — première correspondance contre plus longue correspondance

Le scan FirstOrDefault renvoie la première entrée qui préfixe le prompt, dans l’ordre du catalogue ; l’arbre renvoie la plus longue. Ces deux sémantiques ne coïncident pas toujours.

Objectif : construire un catalogue de trois signatures ("Résume", "Résume le", "Résume le texte", dans cet ordre) et déterminer ce que renvoie chaque matcher pour "Résume le texte suivant : …", avant d’exécuter la vérification.

Indice : seul l’ordre du catalogue distingue les deux — l’arbre ignore l’ordre, le scan y est sensible.

Etape 1 : noter votre prédiction pour les deux matchers (laquelle des trois signatures chacun renvoie-t-il ?).

Etape 2 : compléter la fonction ci-dessous pour exécuter les deux matchers et comparer à la prédiction.

// Exercice 1 : premiere vs plus longue correspondance.
public static (string arbre, string scan) Exercice1PremiereContrePlusLongue()
{
    // TODO etudiant
    // Etape 2 : construire le catalogue ["Résume", "Résume le", "Résume le texte"] (dans cet ordre),
    // appeler RadixTreePromptMatcher.BuildTree + MatchWithTree ET SimpleMatchPromptSettings.Match
    // sur le prompt "Résume le texte suivant : ...", et renvoyer les deux PrefixStart.
    return (null, null); // TODO etudiant : remplacer par les deux valeurs mesurees
}

var (reponseArbre, reponseScan) = Exercice1PremiereContrePlusLongue();
Console.WriteLine($"arbre -> {reponseArbre ?? "(non complete)"}");
Console.WriteLine($"scan  -> {reponseScan ?? "(non complete)"}");
arbre -> (non complete)
scan  -> (non complete)

La motivation de l’Axe 4 : le coût du routage quand le catalogue grandit

Un catalogue de cinq signatures se scanne en un éclair. Mais la vision MultiConnector — * chaque famille de prompt sa signature, chaque signature son réglage coût/latence* — fait grossir le catalogue linéairement avec le nombre de cas d’usage routés. À n entrées, chaque complétion paie un scan O(n) en StartsWith.

L’arbre radix paie sa construction une fois (O(longueur totale des signatures)), puis chaque recherche descend le prompt : O(longueur du préfixe lu). La troisième version, RadixTreePromptMatcher.Match, reconstruit l’arbre à chaque appel — la doc du module la réserve aux catalogues jetables ; elle sert ici de troisième jambe pour visualiser le prix de la reconstruction.

Mesurons les trois régimes sur un catalogue synthétique de 2 000 signatures et 5 000 requêtes :

// Benchmark : scan lineaire vs arbre pre-construit vs reconstruction par appel.
// Catalogue synthetique : 2000 signatures "task<k:D5>:", requetes tires dessus.
var random = new Random(42); // graine fixe : mesures reproductibles
int nSignatures = 2_000, nRequetes = 5_000;

var grosCatalogue = Enumerable.Range(0, nSignatures)
    .Select(k => new PromptMultiConnectorSettings(new SignaturePrefix($"task{k:D5}:")))
    .ToArray();
var requetes = Enumerable.Range(0, nRequetes)
    .Select(i => new CompletionJob($"task{random.Next(nSignatures):D5}: traite la demande {i}"))
    .ToArray();

long Mesurer(Func<CompletionJob, PromptMultiConnectorSettings> matcher)
{
    matcher(requetes[0]); // echauffement
    var sw = Stopwatch.StartNew();
    foreach (var r in requetes) matcher(r);
    return sw.ElapsedMilliseconds;
}

var arbrePreconstruit = RadixTreePromptMatcher.BuildTree(grosCatalogue);
long msScan    = Mesurer(job => SimpleMatchPromptSettings.Match(job, grosCatalogue));
long msArbre   = Mesurer(job => RadixTreePromptMatcher.MatchWithTree(job, arbrePreconstruit));
long msRebuild = Mesurer(job => RadixTreePromptMatcher.Match(job, grosCatalogue));

Console.WriteLine($"{nSignatures} signatures, {nRequetes} requetes :");
Console.WriteLine($"  scan lineaire (O(n)/req)          : {msScan,5} ms");
Console.WriteLine($"  arbre pre-construit (O(|prefix|))  : {msArbre,5} ms  (x{msScan / (double)Math.Max(msArbre, 1):F0})");
Console.WriteLine($"  arbre reconstruit par appel        : {msRebuild,5} ms  (x{msRebuild / (double)Math.Max(msArbre, 1):F0} vs pre-construit)");
2000 signatures, 5000 requetes :
  scan lineaire (O(n)/req)          :  4208 ms
  arbre pre-construit (O(|prefix|))  :     6 ms  (x701)
  arbre reconstruit par appel        : 11197 ms  (x1866 vs pre-construit)

La lecture attendue : l’arbre pré-construit domine nettement le scan ; la reconstruction par appel est un anti-pattern à catalogues stables — chaque requête repaie la construction complète. C’est exactement le distinguo que la documentation du module inscrit dans ses remarques.

Exercice 2 — où est le point de bascule ?

Objectif : faire varier la taille du catalogue (500, 1 000, 2 000, 4 000, 8 000) et mesurer le rapport scan/arbre pré-construit pour chaque taille. À partir de quelle taille l’arbre devient-il strictement plus rapide ?

Indice : réutiliser Mesurer et le générateur synthétique ci-dessus, dans une boucle sur les tailles.

Indice : le rapport scan/arbre croît à peu près linéairement avec n — pourquoi (coût par requête de chaque régime) ?

Etape 1 : produire la table tailles -> ms scan, ms arbre, rapport.

Etape 2 : conclure en une phrase : en dessous de quel n un scan est-il indiscernable de l’arbre ?

// Exercice 2 : point de bascule scan vs arbre selon la taille du catalogue.
public static string Exercice2PointDeBascule()
{
    // TODO etudiant
    // Etape 1 : pour chaque taille dans {500, 1000, 2000, 4000, 8000}, generer catalogue + requetes,
    // mesurer les deux regimes et accumuler une ligne "n=... scan=...ms arbre=...ms ratio=x..".
    // Etape 2 : renvoyer la table + la phrase de conclusion.
    return null; // TODO etudiant
}

Console.WriteLine(Exercice2PointDeBascule() ?? "Exercice a completer");
Exercice a completer

Le branchement drop-in dans le MultiConnector

Le hook PromptMatcher de MultiTextCompletionSettings est un délégué : Func<CompletionJob, IEnumerable<PromptMultiConnectorSettings>, PromptMultiConnectorSettings?>. Le remplacement est un assignation — aucune classe à dériver, aucun cœur à forker. Simulons le cycle de vie complet d’un service qui construit l’arbre quand le catalogue est (re)chargé, puis sert des requêtes :

// Cycle de vie : chargement du catalogue -> arbre -> service de requetes.
Func<CompletionJob, IEnumerable<PromptMultiConnectorSettings>, PromptMultiConnectorSettings> promptMatcher;

void RechargerCatalogue(IEnumerable<PromptMultiConnectorSettings> nouveauCatalogue)
{
    var arbre = RadixTreePromptMatcher.BuildTree(nouveauCatalogue); // paie une fois, au rechargement
    promptMatcher = (job, _) => RadixTreePromptMatcher.MatchWithTree(job, arbre);
}

RechargerCatalogue(catalogue);
foreach (var p in new[] { "Traduis en anglais: good morning", "Extrais les entités de: le contrat 42" })
{
    var reglage = promptMatcher(new CompletionJob(p), catalogue);
    Console.WriteLine($"{p,-42} -> {reglage?.Signature.PromptStart ?? "(aucun reglage)"}");
}
Traduis en anglais: good morning           -> Traduis en anglais:
Extrais les entités de: le contrat 42      -> Extrais les entités de:

Exercice 3 — doublons de signatures : dernier inséré contre premier trouvé

La doc de MatchWithTree documente une divergence subtile : sur des signatures en doublon, l’arbre retient le dernier inséré (sémantique « last writer wins », comme un Dictionary), tandis que le scan renvoie la première entrée correspondante (FirstOrDefault). En production, un doublon de signature est presque toujours un bug de configuration — deux équipes déclarent la même famille de prompts avec des réglages différents.

Objectif : (1) démontrer la divergence avec un catalogue contenant deux entrées de même PromptStart ; (2) écrire une garde SansDoublons qui refuse un catalogue avec signatures dupliquées.

Indice : pour distinguer deux entrées de même préfixe, les comparer par ReferenceEquals sur l’objet renvoyé.

Etape 1 : construire le catalogue en doublon, comparer les objets (pas les chaînes) renvoyés par chaque matcher.

Etape 2 : ecrire la garde (renvoyer la liste des prefixes dupliques, liste vide = catalogue sain).

// Exercice 3 : divergence sur doublons + garde anti-doublons.
public static List<string> Exercice3SansDoublons(IEnumerable<PromptMultiConnectorSettings> catalogueAVerifier)
{
    // TODO etudiant
    // Etape 2 : renvoyer les prefixes presents plus d'une fois (liste vide = catalogue sain).
    return null; // TODO etudiant
}

var catalogueDupliques = new[]
{
    new PromptMultiConnectorSettings(new SignaturePrefix("Traduis en anglais:")), // reglage equipe A
    new PromptMultiConnectorSettings(new SignaturePrefix("Traduis en anglais:")), // reglage equipe B, meme prefixe
};
var demonstration = Exercice3SansDoublons(catalogueDupliques);
Console.WriteLine(demonstration is null ? "Exercice a completer"
    : demonstration.Count == 0 ? "catalogue sain (la garde ne voit rien -- a verifier !)"
    : $"garde : {demonstration.Count} prefixe(s) en doublon");
Exercice a completer

Ce qu’il faut retenir

  • Le routage MultiConnector est un problème de plus long préfixe : le matcher arbre radix le résout en O(longueur du préfixe lu), indépendamment de la taille du catalogue ; la baseline v0.34.3 scanne en O(n) et renvoie la première correspondance, pas la plus longue.
  • Deux régimes, deux usages : BuildTree + MatchWithTree pour un catalogue stable (l’arbre se paie au rechargement) ; Match seul pour un catalogue jetable — jamais en boucle chaude.
  • Le hook est un délégué : le matcher se branche sans forker le cœur du connecteur — c’est la propriété qui a rendu l’Axe 4 possible comme module autonome (net9.0, zéro dépendance).
  • La sémantique des doublons diffère (dernier inséré contre premier trouvé) : une détection à l’entrée du catalogue vaut mieux qu’un arbitrage à la requête.

Pour aller plus loin : l’Epic #1210 (histoire du sous-module, baseline v0.34.3, les 7 axes) · la jumelle Aspire 07 (la physique files/vetting/télémétrie du MultiConnector) · les sources : semantic-fleet/tools/radix/src/ (matcher, trie, baseline) et leurs tests.

Retour au sommet