ENCODING NP-COMPLETE PROBLEM INSTANCES INTO NATURAL LANGUAGE FOR LLM PROCESSING

Аннотация

Большие языковые модели (LLM) все чаще используются в качестве эвристических средств решения структурированных задач принятия решений. Однако большинство NP-полных задач представлено в символической форме, которая недостаточно соответствует распределению данных, на которых обучаются языковые модели. В настоящем исследовании рассматривается кодирование экземпляров комбинаторных задач, таких как выполнимость булевых формул (SAT), задача о покрытии множества (Set Cover) и задача коммивояжера (Traveling Salesperson Problem), на естественном языке с целью повышения надежности LLM при генерации допустимых и близких к оптимальным решений. Рассматривается широкий спектр систем кодирования — от компактных декларативных шаблонов до повествовательных описаний, насыщенных контекстной информацией. Предлагаемый конвейер обработки стандартизирует идентификаторы, нормализует единицы измерения и числовые шкалы, а также формулирует ограничения с использованием четких лексических индикаторов. Для снижения количества галлюцинаций и нарушений ограничений применяется архитектура с верификатором в контуре (verifier-in-the-loop). Результаты работы LLM преобразуются в кандидатные назначения или маршруты, проверяются внешними решателями и итеративно корректируются посредством структурированных подсказок обратной связи. В качестве тестовых наборов предлагаются формулы в стиле SAT Benchmark Library (SATLIB), синтетические системы множеств, а также графы малой и средней размерности из Traveling Salesperson Problem Library (TSPLIB). Критерии оценки включают долю допустимых решений, разрыв до оптимального решения и эффективность выборки в пределах заданного токен-бюджета. Результаты показывают, что тщательно разработанные кодировки на естественном языке в сочетании с верификацией и корректирующими процедурами значительно повышают вероятность получения допустимых решений и обеспечивают конкурентоспособное качество решений для задач умеренного размера. Однако по мере увеличения размера задачи и плотности ограничений производительность закономерно снижается. Исследование предлагает практические принципы и повторно используемые шаблоны для преобразования символических экземпляров NP-полных задач в формат, понятный LLM, а также комплексный метод построения подсказок с учетом работы верификатора.