Abstract
Большие языковые модели (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, а также комплексный метод построе-ния подсказок с учетом работы верификатора.