Une Approche pour la Décomposition Systématique des Tâches Complexes des LLM

Informations Fondamentales

• ID de l'article : 2510.07772
• Titre : An Approach for Systematic Decomposition of Complex LLM Tasks
• Auteurs : Tianle Zhou, Jiakai Xu, Guanhong Liu, Jiaxiang Liu, Haonan Wang, Eugene Wu (Columbia University)
• Classification : cs.AI
• Date de publication : 13 octobre 2025 (arXiv v2)
• Lien de l'article : https://arxiv.org/abs/2510.07772v2

Résumé

Les grands modèles de langage (LLM) présentent des problèmes de fiabilité sur les tâches complexes, et les méthodes de décomposition existantes sont heuristiques, dépendant d'agents ou de décompositions manuelles. Ce travail introduit un nouveau cadre de décomposition systématique, appelé Analyse de Complexité Induite par Contraintes (ACONIC), qui modélise les tâches comme des problèmes de satisfaction de contraintes et utilise des mesures de complexité formalisées pour guider la décomposition. Sur les problèmes combinatoires (SAT-Bench) et les tâches de requête de base de données LLM (Spider), en décomposant les tâches selon les mesures de complexité, les performances des agents s'améliorent considérablement (10-40 points de pourcentage).

Contexte et Motivation de la Recherche

1. Problème à Résoudre

Les grands modèles de langage échouent souvent à produire des résultats corrects en une seule passe avant lors du traitement de tâches complexes nécessitant un raisonnement multi-étapes approfondi ou une recherche combinatoire, présentant des problèmes de fiabilité.

2. Importance du Problème

Avec l'application généralisée des LLM dans diverses tâches de raisonnement, de programmation et de résolution de problèmes, la décomposition systématique des tâches complexes pour améliorer les performances du modèle devient un défi clé. Les méthodes existantes manquent de mesures de complexité et de stratégies de décomposition fondées sur des principes.

3. Limitations des Méthodes Existantes

• Décomposition heuristique : Les méthodes existantes telles que Chain-of-Thought dépendent principalement de la décomposition par le LLM lui-même, manquant de fondement théorique
• Décomposition manuelle : Dépend de la conception manuelle des flux de travail par des experts du domaine, manquant de systématicité
• Absence de mesure de complexité : Incapacité à quantifier la complexité des tâches, rendant difficile la détermination du moment et de la manière de décomposer

4. Motivation de la Recherche

Établir un cadre formel de complexité des tâches, permettant des stratégies de décomposition systématiques, fournissant la capacité d'étudier des tâches de difficulté comparable, et guidant quand l'assistance d'outils est nécessaire.

Contributions Principales

1. Proposition du cadre ACONIC : Premier cadre de complexité formalisé réduisant systématiquement les tâches LLM à des problèmes de satisfaction de contraintes
2. Établissement de mesures de complexité : Utilisation de la taille du graphe et de la largeur d'arborescence du graphe de contraintes comme mesures de complexité des tâches
3. Méthode de décomposition systématique : Stratégie de décomposition basée sur la décomposition en arborescence, minimisant la complexité des sous-tâches tout en préservant la satisfiabilité globale
4. Vérification empirique : Validation des limites de difficulté définies par les mesures de complexité et des effets de décomposition sur les repères SAT-Bench et Spider
5. Amélioration des performances : Amélioration de 9-15% sur SAT-Bench et de 30-40% sur Spider par rapport à la méthode Chain-of-Thought

Explication Détaillée de la Méthode

Définition de la Tâche

ACONIC définit une tâche LLM comme suit : étant donné un contexte décrivant un ensemble de contraintes et une requête qui doit raisonner sur les contraintes, la réduire à un problème formel de satisfaction de contraintes, puis la décomposer et construire un flux de travail de sous-tâches.

Architecture du Modèle

1. Réduction à un Problème de Planification

Utilisation d'un cadre d'opérations d'agent basé sur l'état, formalisant la tâche comme un problème de Planification en tant que Satisfiabilité (PaS) :

P = ⟨F, A, I, G⟩

Où :

• F : Ensemble fini de fluents propositionnels décrivant les faits du monde
• A : Ensemble fini d'actions
• I, G : Fluents initiaux et objectifs
• Pour une action a : P(a) détermine les préconditions, A(a) détermine les fluents devenant vrais, D(a) détermine les fluents devenant faux

2. Réduction à un Problème de Satisfaction de Contraintes

Réduction du problème PaS à une instance CSP, par codage :

• Préconditions fp ∈ P(a)
• Effets additifs fa ∈ A(a)
• Effets suppressifs fd ∈ D(a) comme contraintes de dépendance booléenne entre fluents et actions.

3. Stratégie de Décomposition en Arborescence

Utilisation de la théorie de décomposition en arborescence de Bodlaender (1998) :

• Recherche de la décomposition en arborescence D* avec la plus petite taille maximale de sac (largeur d'arborescence)
• La largeur d'arborescence caractérise la complexité intrinsèque du problème
• La cohérence locale garantit la cohérence globale

Points d'Innovation Technique

1. Mesure de complexité formalisée : Première utilisation de la largeur d'arborescence de la théorie des graphes comme indicateur quantitatif de la complexité des tâches LLM
2. Garantie de cohérence globale : La décomposition en arborescence assure que la cohérence sur les sous-graphes locaux implique la cohérence des solutions CSP globales
3. Stratégie de décomposition optimale : La décomposition basée sur la largeur d'arborescence minimale minimise la complexité locale
4. Procédure de réduction automatique : Développement de procédures de réduction automatique pour des repères spécifiques, réduisant la modélisation manuelle

Configuration Expérimentale

Ensembles de Données

1. SAT-Bench

• Problèmes de récit en langage naturel construits sur la base de problèmes SAT
• Contient des représentations CNF, des descriptions en langage naturel et des mappages d'alignement d'entités vers SAT
• Évaluation de Claude3.5-Sonnet (échantillonnage aléatoire de la moitié des tâches) et Llama-3-70B (toutes les tâches)

2. Spider

• Repère populaire NL2SQL
• Contient des centaines de bases de données, chacune avec jusqu'à 37 tables, 90 clés étrangères, plus de 100 colonnes
• Les tâches incluent le schéma de base de données S, la requête en langage naturel q et la requête SQL réelle q*

Métriques d'Évaluation

• SAT-Bench : Taux de complétion des tâches (succès/échec)
• Spider : Précision des requêtes SQL, évaluée séparément par niveau de difficulté (Facile/Moyen/Difficile/Supplémentaire)

Méthodes de Comparaison

• Chain-of-Thought (CoT) : Méthode standard de chaîne de pensée comme ligne de base
• Observation complète vs Observation décomposée : Comparaison entre l'accès aux informations globales et l'accès aux informations locales décomposées

Détails d'Implémentation

• Utilisation de SageMath pour calculer la décomposition en arborescence, avec heuristique de remplissage minimal et solveur exact
• SAT-Bench utilise une stratégie d'assignation de variables progressive
• Spider utilise une stratégie de construction incrémentale avec clauses WITH

Résultats Expérimentaux

Résultats Principaux

1. Résultats SAT-Bench

• Claude3.5-Sonnet : Amélioration de 49,3% à 58,1% (+8,8%)
• Llama-3-70B : Amélioration de 21,5% à 36,5% (+15,0%)
• Les mesures de complexité définissent clairement les limites de difficulté, ACONIC pousse les limites vers des problèmes plus complexes

2. Résultats Spider

Améliorations significatives par rapport à la ligne de base CoT à tous les niveaux de difficulté :

• Facile : Amélioration de 42,7% à 75,8% (+33,1%)
• Moyen : Amélioration de 38,1% à 58,1% (+20,0%)
• Difficile : Amélioration de 36,2% à 62,7% (+26,5%)
• Supplémentaire : Amélioration de 19,3% à 37,9% (+18,6%)

Découvertes Expérimentales

1. Limites de complexité : Les expériences révèlent des limites de « complexité totale des tâches » fixes basées sur la largeur d'arborescence et le nombre de sacs du problème
2. Amélioration de la cohérence : La décomposition ACONIC montre des améliorations de performance cohérentes sur deux modèles différents (Claude et LLaMA)
3. Gradient de difficulté : Les modèles plus puissants (comme Claude) déplacent les limites vers des problèmes plus complexes
4. Effet de décomposition : L'augmentation du nombre de trajectoires améliore légèrement la précision, mais la décomposition guidée par la complexité apporte des améliorations plus significatives

Travaux Connexes

1. Méthodes de Décomposition de Tâches

• Série Chain-of-Thought : Wei et al. (2022), Yao et al. (2023), Khot et al. (2023)
• Méthodes assistées par outils : Wang et al. (2024), Singh et al. (2024)
• Décomposition spécifique au domaine : Pourreza and Rafiei (2023), Chen et al. (2024)

2. Satisfaction de Contraintes et Planification

• Planification en tant que Satisfiabilité : Travaux classiques de Selman et al.
• Théorie de la Décomposition en Arborescence : Fondements de théorie des graphes de Bodlaender (1998)
• Planification de Chemin Multi-Agents : Surynek et al. (2016)

3. Application de la Théorie des Bases de Données

• Modélisation de Graphes de Contraintes : Gottlob et al. (2001)
• Méthodes NL2SQL : Codage conscient des relations de Wang et al. (2019)

Conclusion et Discussion

Conclusions Principales

1. Efficacité du cadre formel : ACONIC fournit le premier cadre de quantification de la complexité des tâches LLM basé sur la satisfaction de contraintes
2. Avantages de la décomposition systématique : La décomposition basée sur la complexité surpasse considérablement les méthodes heuristiques
3. Universalité : Le cadre est efficace sur différents types de tâches (problèmes combinatoires et requêtes de base de données)
4. Théorie guidant la pratique : Les concepts de théorie des graphes tels que la largeur d'arborescence fournissent une base théorique pour la décomposition des tâches LLM

Limitations

1. Restriction de l'applicabilité : Applicable uniquement aux tâches pouvant être commodément modélisées comme des problèmes de satisfaction de contraintes
2. Défis de représentation complète : Les problèmes réels ne peuvent souvent pas être complètement représentés logiquement en raison de l'ambiguïté des problèmes, de l'opacité des actions des agents ou d'informations contextuelles floues
3. Non-complètement autonome : ACONIC ne constitue pas un système de décomposition ou de raisonnement complètement autonome
4. Spécificité des repères : Les tâches d'évaluation peuvent être résolues directement par des solveurs de contraintes ou des algorithmes simples

Directions Futures

1. Méthodes de décomposition hybride : Recherche de méthodes de décomposition hybride combinant contraintes logiques et contraintes de sens commun
2. Types de tâches plus larges : Extension à davantage de problèmes pratiques, tels que la détection de blocages, la planification des ressources, etc.
3. Système complètement autonome : Développement vers un système de décomposition et de raisonnement complètement autonome
4. Comparaison des décompositions basées sur l'apprentissage : Recherche comparative avec d'autres cadres de décomposition basés sur la théorie ou l'apprentissage

Évaluation Approfondie

Points Forts

1. Innovation théorique : Première application systématique de la théorie de la décomposition en arborescence de la théorie des graphes à la décomposition des tâches LLM
2. Rigueur formalisée : Fournit un cadre mathématique strict avec une chaîne de réduction complète de PaS à CSP puis à décomposition en arborescence
3. Vérification empirique suffisante : Validation sur deux repères de types différents, avec des résultats cohérents et significatifs
4. Forte interprétabilité : Les mesures de complexité fournissent une compréhension intuitive de la difficulté des tâches
5. Cadre universel : Non limité à des types de tâches spécifiques, avec une bonne universalité

Insuffisances

1. Complexité de la modélisation : La réduction des tâches pratiques en CSP nécessite des connaissances spécialisées et de l'ingénierie manuelle
2. Surcharge de calcul : Le calcul de la décomposition en arborescence lui-même peut avoir une complexité élevée
3. Comparaisons de base limitées : Comparaison principalement avec CoT, manquant de comparaisons avec d'autres méthodes de décomposition systématique
4. Restriction des types de tâches : Validation sur seulement deux types de tâches, la capacité de généralisation nécessite une vérification plus large

Impact

1. Contribution théorique : Fournit une nouvelle perspective théorique pour la décomposition des tâches LLM
2. Valeur méthodologique : Le cadre ACONIC peut inspirer davantage de recherches LLM basées sur des méthodes formalisées
3. Valeur pratique : L'amélioration significative des performances sur des types de tâches spécifiques a une valeur d'application pratique
4. Direction de recherche : Peut ouvrir une nouvelle direction de recherche combinant les LLM avec les méthodes symboliques de l'IA traditionnelle

Scénarios Applicables

1. Problèmes d'optimisation combinatoire : Planification, allocation de ressources et autres problèmes modélisables en tant que CSP
2. Tâches de requête structurées : Requêtes de base de données, raisonnement sur graphes de connaissances, etc.
3. Planification multi-contraintes : Tâches de planification nécessitant de satisfaire plusieurs conditions de contrainte
4. Tâches de raisonnement logique : Problèmes de raisonnement formalisables en tant que contraintes logiques

Références

1. Bodlaender, H. L. (1998). A partial k-arboretum of graphs with bounded treewidth. Theoretical computer science, 209(1-2):1–45.
2. Wei, J., et al. (2022). Chain-of-thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903.
3. Yu, T., et al. (2019). Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.
4. Gottlob, G., Leone, N., & Scarcello, F. (2001). Hypertree decompositions: A survey. International Symposium on Mathematical Foundations of Computer Science.

Résumé : Le cadre ACONIC proposé dans cet article représente un progrès théorique important dans le domaine de la décomposition des tâches LLM. En introduisant des mesures de complexité formalisées et des stratégies de décomposition systématiques, il fournit une nouvelle perspective pour résoudre les tâches complexes des LLM. Malgré les limitations en termes de portée d'applicabilité et de complexité de modélisation, son amélioration significative des performances sur des tâches spécifiques et ses contributions théoriques en font un travail important dans ce domaine.