Подход к систематической декомпозиции сложных задач LLM

Основная информация

• ID статьи: 2510.07772
• Название: An Approach for Systematic Decomposition of Complex LLM Tasks
• Авторы: Tianle Zhou, Jiakai Xu, Guanhong Liu, Jiaxiang Liu, Haonan Wang, Eugene Wu (Колумбийский университет)
• Категория: cs.AI
• Дата публикации: 13 октября 2025 г. (arXiv v2)
• Ссылка на статью: https://arxiv.org/abs/2510.07772v2

Аннотация

Большие языковые модели (LLM) демонстрируют проблемы надёжности при решении сложных задач. Существующие методы декомпозиции являются эвристическими и зависят от агентов или ручной декомпозиции. В данной работе представлен новый систематический фреймворк декомпозиции, называемый анализом сложности, индуцированным ограничениями (ACONIC). Фреймворк моделирует задачи как задачи удовлетворения ограничений и использует формальные меры сложности для направления декомпозиции. На комбинаторных задачах (SAT-Bench) и задачах запросов к базам данных LLM (Spider) декомпозиция задач по мерам сложности значительно повышает производительность агентов (на 10-40 процентных пункта).

Исследовательский контекст и мотивация

1. Проблема, которую необходимо решить

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

2. Значимость проблемы

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

3. Ограничения существующих методов

• Эвристическая декомпозиция: Существующие методы, такие как Chain-of-Thought, в основном полагаются на саму LLM для декомпозиции, что лишено теоретической основы
• Ручная декомпозиция: Зависит от ручного проектирования рабочих процессов экспертами в предметной области, что лишено систематичности
• Отсутствие мер сложности: Невозможно количественно оценить сложность задачи, что затрудняет определение необходимости и способа декомпозиции

4. Исследовательская мотивация

Установить формальный фреймворк сложности задач, обеспечивающий систематические стратегии декомпозиции, предоставляющий возможность исследования задач сравнимой сложности и направляющий, когда требуется инструментальная поддержка.

Основные вклады

1. Предложение фреймворка ACONIC: Первый формальный фреймворк сложности, систематически сводящий задачи LLM к задачам удовлетворения ограничений
2. Установление мер сложности: Использование размера графа ограничений и древесной ширины как мер сложности задачи
3. Систематический метод декомпозиции: Стратегия декомпозиции на основе древесной декомпозиции, минимизирующая сложность подзадач при сохранении глобальной выполнимости
4. Эмпирическая верификация: Проверка границ сложности и эффектов декомпозиции на эталонах SAT-Bench и Spider
5. Повышение производительности: Улучшение на 9-15% на SAT-Bench и на 30-40% на Spider по сравнению с методом Chain-of-Thought

Подробное описание метода

Определение задачи

ACONIC определяет задачу LLM как: учитывая контекст, описывающий набор ограничений, и запрос, который должен рассуждать об ограничениях, свести его к формальной задаче удовлетворения ограничений, а затем разложить и построить рабочий процесс подзадач.

Архитектура модели

1. Сведение к задаче планирования

Использование фреймворка операций агента на основе состояния для формализации задачи как задачи планирования как выполнимости (PaS):

P = ⟨F, A, I, G⟩

где:

• F: конечный набор пропозициональных флюентов, описывающих факты мира
• A: конечный набор действий
• I, G: начальные и целевые флюенты
• Для действия a: P(a) определяет предусловия, A(a) определяет флюенты, становящиеся истинными, D(a) определяет флюенты, становящиеся ложными

2. Сведение к задаче удовлетворения ограничений

Сведение задачи PaS к экземпляру CSP путём кодирования:

• Предусловия fp ∈ P(a)
• Добавляемые эффекты fa ∈ A(a)
• Удаляемые эффекты fd ∈ D(a) как булевых зависимостей ограничений между флюентами и действиями.

3. Стратегия древесной декомпозиции

Использование теории древесной декомпозиции Бодлендера (1998):

• Поиск древесной декомпозиции D* с минимальным максимальным размером мешка (древесная ширина)
• Древесная ширина характеризует внутреннюю сложность задачи
• Локальная согласованность гарантирует глобальную согласованность

Технические инновации

1. Формальная мера сложности: Первое использование древесной ширины из теории графов как количественного показателя сложности задач LLM
2. Гарантия глобальной согласованности: Древесная декомпозиция гарантирует, что согласованность на локальных подграфах означает согласованность глобального решения CSP
3. Оптимальная стратегия декомпозиции: Декомпозиция на основе минимальной древесной ширины минимизирует локальную сложность
4. Автоматическая процедура сведения: Разработка автоматических процедур сведения для конкретных эталонов, снижающих ручное моделирование

Экспериментальная установка

Наборы данных

1. SAT-Bench

• Задачи-истории на естественном языке, построенные на основе задач SAT
• Содержат представление CNF, описание на естественном языке и отображение сущностей на SAT
• Оценка Claude3.5-Sonnet (случайная выборка половины задач) и Llama-3-70B (все задачи)

2. Spider

• Популярный эталон NL2SQL
• Содержит сотни баз данных, каждая с максимум 37 таблицами, 90 внешними ключами и более чем 100 столбцами
• Задачи включают схему базы данных S, запрос на естественном языке q и истинный SQL-запрос q*

Метрики оценки

• SAT-Bench: Коэффициент завершения задачи (успех/неудача)
• Spider: Точность SQL-запроса, оценённая отдельно по уровням сложности (Easy/Medium/Hard/Extra)

Методы сравнения

• Chain-of-Thought (CoT): Стандартный метод подсказки цепочки мышления как базовый уровень
• Полное наблюдение vs разложенное наблюдение: Сравнение доступа к глобальной информации с доступом к информации локальной декомпозиции

Детали реализации

• Использование SageMath для вычисления древесной декомпозиции с эвристикой минимального заполнения и точным решателем
• Для SAT-Bench используется стратегия пошагового присваивания переменных
• Для Spider используется стратегия пошагового построения с предложениями WITH

Результаты экспериментов

Основные результаты

1. Результаты SAT-Bench

• Claude3.5-Sonnet: Улучшение с 49,3% до 58,1% (+8,8%)
• Llama-3-70B: Улучшение с 21,5% до 36,5% (+15,0%)
• Мера сложности чётко определяет границы сложности; ACONIC смещает границы к более сложным задачам

2. Результаты Spider

Значительное улучшение ACONIC по сравнению с базовым уровнем CoT на всех уровнях сложности:

• Easy: Улучшение с 42,7% до 75,8% (+33,1%)
• Medium: Улучшение с 38,1% до 58,1% (+20,0%)
• Hard: Улучшение с 36,2% до 62,7% (+26,5%)
• Extra: Улучшение с 19,3% до 37,9% (+18,6%)

Экспериментальные находки

1. Границы сложности: Эксперименты выявляют фиксированные границы "общей сложности задачи" на основе древесной ширины проблемы и количества мешков
2. Согласованное улучшение: Декомпозиция ACONIC демонстрирует согласованное повышение производительности на двух различных моделях (Claude и LLaMA)
3. Градиент сложности: Более мощные модели (такие как Claude) смещают границы в направлении более сложных задач
4. Эффект декомпозиции: Увеличение количества траекторий слегка улучшает точность, но направляемая сложностью декомпозиция приносит более значительное улучшение

Связанные работы

1. Методы декомпозиции задач

• Серия Chain-of-Thought: Wei et al. (2022), Yao et al. (2023), Khot et al. (2023)
• Методы с инструментальной поддержкой: Wang et al. (2024), Singh et al. (2024)
• Декомпозиция для конкретных предметных областей: Pourreza and Rafiei (2023), Chen et al. (2024)

2. Удовлетворение ограничений и планирование

• Планирование как выполнимость: Классические работы Selman et al.
• Теория древесной декомпозиции: Теоретико-графовая основа Bodlaender (1998)
• Многоагентное планирование пути: Surynek et al. (2016)

3. Применение теории баз данных

• Моделирование графа ограничений: Gottlob et al. (2001)
• Методы NL2SQL: Кодирование, учитывающее отношения, Wang et al. (2019)

Заключение и обсуждение

Основные выводы

1. Эффективность формального фреймворка: ACONIC предоставляет первый фреймворк количественной оценки сложности задач LLM на основе удовлетворения ограничений
2. Преимущества систематической декомпозиции: Декомпозиция на основе сложности значительно превосходит эвристические методы
3. Универсальность: Фреймворк эффективен на различных типах задач (комбинаторные задачи и запросы к базам данных)
4. Теория направляет практику: Концепции теории графов, такие как древесная ширина, предоставляют теоретическую основу для декомпозиции задач LLM

Ограничения

1. Ограничение области применения: Применимо только к задачам, которые удобно моделируются как задачи удовлетворения ограничений
2. Вызовы полного представления: Практические задачи часто не могут быть полностью логически представлены из-за неоднозначности задачи, непрозрачности действий агента или неясной контекстной информации
3. Не полностью автономно: ACONIC не представляет полностью автономную систему декомпозиции или рассуждения
4. Специфичность эталона: Оцениваемые задачи могут быть решены непосредственно с помощью решателей ограничений или простых алгоритмов

Направления будущих исследований

1. Гибридные методы декомпозиции: Исследование гибридных методов, объединяющих логические ограничения и ограничения здравого смысла
2. Более широкие типы задач: Расширение на более широкий спектр практических задач, таких как обнаружение взаимных блокировок, планирование ресурсов и т. д.
3. Полностью автономные системы: Развитие полностью автономных систем декомпозиции и рассуждения
4. Исследование основанной на обучении декомпозиции: Сравнительные исследования с другими теоретически обоснованными или основанными на обучении фреймворками декомпозиции

Глубокая оценка

Преимущества

1. Теоретическая инновация: Первое систематическое применение теории древесной декомпозиции из теории графов к декомпозиции задач LLM
2. Формальная строгость: Предоставление строгого математического фреймворка с полной цепью сведения от PaS к CSP к древесной декомпозиции
3. Достаточная эмпирическая верификация: Проверка на двух различных типах эталонов с согласованными и значительными результатами
4. Сильная интерпретируемость: Мера сложности обеспечивает интуитивное понимание сложности задачи
5. Универсальный фреймворк: Не ограничен конкретными типами задач с хорошей универсальностью

Недостатки

1. Сложность моделирования: Сведение практических задач к CSP требует специальных знаний и ручной инженерии
2. Вычислительные затраты: Сама вычисление древесной декомпозиции может иметь высокую сложность
3. Ограниченное сравнение базовых уровней: Главным образом сравнение с CoT, отсутствие сравнения с другими систематическими методами декомпозиции
4. Ограничение типов задач: Верификация только на двух типах задач; способность к обобщению требует более широкой верификации

Влияние

1. Теоретический вклад: Предоставление новой теоретической перспективы для декомпозиции задач LLM
2. Методологическая ценность: Фреймворк ACONIC может вдохновить больше исследований LLM на основе формальных методов
3. Практическая ценность: Значительное повышение производительности на конкретных типах задач имеет практическую ценность применения
4. Направление исследований: Может открыть новое направление исследований, объединяющее LLM с традиционными символическими методами AI

Применимые сценарии

1. Задачи комбинаторной оптимизации: Планирование, распределение ресурсов и другие задачи, моделируемые как CSP
2. Структурированные задачи запросов: Запросы к базам данных, рассуждение о графах знаний и т. д.
3. Многоограничивающее планирование: Задачи планирования, требующие удовлетворения нескольких условий ограничений
4. Задачи логического рассуждения: Задачи рассуждения, которые могут быть формализованы как логические ограничения

Библиография

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.

Резюме: Предложенный в данной работе фреймворк ACONIC представляет собой важный теоретический прогресс в области декомпозиции задач LLM. Путём введения формальных мер сложности и систематических стратегий декомпозиции он предоставляет новый подход к решению сложных задач LLM. Несмотря на ограничения в области применения и сложность моделирования, значительное повышение производительности на конкретных задачах и теоретические вклады делают эту работу важным вкладом в данную область.