2025-11-24T22:34:17.172236

Exploring Compositional Generalization (in COGS/ReCOGS_pos) by Transformers using Restricted Access Sequence Processing (RASP)

Bruns
Humans understand new combinations of words encountered if they are combinations of words recognized from different contexts, an ability called Compositional Generalization. The COGS benchmark (Kim and Linzen, 2020) arXiv:2010.05465 reports 0% accuracy for Transformer models on some structural generalizations. We use (Weiss et al., 2021) arXiv:2106.06981's Restricted Access Sequence Processing (RASP), a Transformer-equivalent programming language, to demonstrate that a Transformer Encoder-Decoder can perform COGS and the semantically equivalent ReCOGS_pos (Wu et al., 2024) arXiv:2303.13716 systematically and compositionally: Our RASP models attain near perfect scores on structural generalization splits on COGS (exact match) and ReCOGS_pos (semantic exact match). Our RASP models show the (Re)COGS tasks do not require a hierarchical or tree-structured solution (contrary to (Kim and Linzen, 2020) arXiv:2010.05465, (Yao and Koller, 2022) arXiv:2210.13050, (Murty et al., 2022) arXiv:2211.01288, (Liu et al., 2021) arXiv:2107.06516): we use word-level tokens with an "embedding" layer that tags with possible part of speech, applying just once per encoder pass 19 attention-head compatible flat pattern-matching rules (easily identified with specific training examples), shown using grammar coverage (Zeller et al., 2023) to cover the non-recursive aspects of the input grammar, plus masking out prepositional phrases ("pp noun") and/or sentential complements (cp) when recognizing grammar patterns and extracting nouns related to the main verb in the sentence, and output the next logical form (LF) token (repeating until the LF is complete). The models do not apply recursive, tree-structured rules like "np_det pp np -> np_pp -> np", but score near perfect semantic and string exact match on both COGS and ReCOGS pp recursion, cp recursion using the decoder loop.
academic

Исследование композиционной генерализации (в COGS/ReCOGS_pos) трансформаторами с использованием обработки последовательностей с ограниченным доступом (RASP)

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

  • ID статьи: 2504.15349
  • Название: Exploring Compositional Generalization (in COGS/ReCOGS_pos) by Transformers using Restricted Access Sequence Processing (RASP)
  • Автор: William Bruns
  • Классификация: cs.CL (Вычислительная лингвистика)
  • Дата публикации: 14 октября 2025 г. (arXiv v3)
  • Ссылка на статью: https://arxiv.org/abs/2504.15349v3

Аннотация

Люди способны понимать новые комбинации слов, распознанных в различных контекстах — способность, называемая композиционной генерализацией. Тестовый набор COGS сообщает о точности 0% моделей трансформаторов при некоторых структурных обобщениях. В данной работе используется язык RASP (обработка последовательностей с ограниченным доступом) для доказательства того, что кодировщик-декодировщик трансформатора может систематически и композиционно выполнять задачи COGS и семантически эквивалентные ReCOGS_pos: модель RASP достигает почти идеальных результатов на разделе структурной генерализации. Исследование показывает, что задачи (Re)COGS не требуют иерархических или древовидных решений, а вместо этого используют 19 совместимых с вниманием правил плоского сопоставления шаблонов путём маскирования предложных фраз и придаточных предложений для идентификации грамматических шаблонов.

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

Определение проблемы

Основная проблема, которую решает данное исследование, — это ограничения способности моделей трансформаторов в задачах композиционной генерализации, в частности плохая производительность на тестовом наборе COGS (задача композиционной генерализации на основе семантической интерпретации).

Значимость

  1. Теоретическое значение: Композиционная генерализация является ключевой способностью понимания языка человеком; понимание того, как нейронные сети реализуют эту способность, имеет решающее значение для продвижения понимания языка ИИ
  2. Практическое значение: Точность близкая к 0% текущих моделей трансформаторов в задачах структурной генерализации указывает на фундаментальные ограничения, требующие решения

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

  1. Ограничения мелких сетей: 2-слойный кодировщик-декодировщик Kim и Linzen (2020) показывает крайне плохую производительность при структурной генерализации
  2. Ошибочное предположение об иерархии: Существующие исследования предполагают, что для решения задач COGS необходимы древовидные структуры или иерархические представления
  3. Неэффективность глубины: Petty и др. (2024) обнаружили, что даже увеличение до 32 слоёв не улучшает производительность трансформатора при структурной генерализации COGS

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

Автор вдохновлён работой Zhou и др. (2023) по использованию RASP для анализа способности трансформаторов к генерализации и стремится через конструктивное доказательство продемонстрировать, что трансформаторы теоретически могут решать задачи COGS, и проанализировать причины отказа существующих моделей.

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

  1. Конструктивное доказательство: Использование языка RASP для доказательства того, что кодировщик-декодировщик трансформатора теоретически может систематически решать задачи COGS и ReCOGS_pos
  2. Плоское решение: Предложение неиерархического решения на основе 19 правил плоского сопоставления шаблонов без необходимости в рекурсивных древовидных правилах
  3. Анализ ошибок: Предсказание и проверка конкретных ошибочных паттернов базовых трансформаторов через теорию «ошибок притяжения»
  4. Прорыв в производительности: Модель RASP достигает 99,89% точного совпадения строк на COGS и 99,63% семантического точного совпадения на ReCOGS_pos
  5. Новый раздел генерализации: Обнаружение и проверка нового сложного раздела генерализации "v_dat_p2_pp_moved_to_recipient"

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

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

Задачи COGS/ReCOGS требуют преобразования предложений упрощённой английской грамматики в логическую форму (LF):

  • Входные данные: Английское предложение (например, "A scientist lended a cat a donut")
  • Выходные данные: Логическая форма (например, "scientist(1); cat(4); donut(6); lend(2) AND agent(2,1) AND recipient(2,4) AND theme(2,6)")
  • Оценка: Точное совпадение строк (COGS) или семантическое точное совпадение (ReCOGS)

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

Фреймворк программирования RASP

RASP — это язык программирования, компилируемый в веса трансформатора. В данной работе используется для построения модели кодировщик-декодировщик:

  1. Слой встраивания: Отображение токенов уровня слова в метки части речи и типа глагола
  2. Кодировщик: Использование 19 совместимых с вниманием плоских сопоставителей шаблонов
  3. Цикл декодировщика: Авторегрессивное генерирование токенов логической формы

Проектирование основных компонентов

1. Отображение встраивания части речи

Лексема → {det: 1, common_noun: 7, proper_noun: 8, v_dat: 18, ...}

2. Плоские сопоставители шаблонов 19 шаблонов охватывают все нерекурсивные грамматические правила, например:

  • np v_dat_p2 np np (например, "Liam forwarded the girl the donut")
  • np was v_trans_omissible_pp_p2 by np (пассивный залог)

3. Механизм маскирования Ключевое нововведение: маскирование существительных предложных фраз при извлечении отношений существительное-глагол:

no_pp_np_mask = 1 - aggregate((pp_one_after_mask and np_prop_diag_mask) or 
                              (pp_two_after_mask and np_det_diag_mask), 1)

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

1. Нерекурсивное решение

В отличие от традиционных предположений, модель не использует рекурсивные правила типа np_det pp np → np_pp → np, а вместо этого:

  • Идентифицирует основные грамматические шаблоны в кодировщике
  • Развёртывает рекурсивные структуры в декодировщике

2. Избежание ошибок притяжения

Механизм маскирования предотвращает «притяжение» существительных из предложных фраз к неправильным грамматическим отношениям:

Ошибка: The cake on the plate burned → theme(burn, plate)  # ошибка притяжения
Правильно: The cake on the plate burned → theme(burn, cake)   # после маскирования

3. Развёртывание цикла декодировщика

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

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

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

  • COGS: 24 155 примеров обучения, 3 000 примеров тестирования, 21 000 примеров генерализации
  • ReCOGS_pos: Версия ReCOGS с индексами позиций, семантически эквивалентная, но позволяющая семантическое точное совпадение
  • Охват грамматики: Использование метода Zeller и др. (2023) для проверки того, что 19 правил охватывают 100% нерекурсивной грамматики

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

  • Точное совпадение строк: Идентичные строки логической формы
  • Семантическое точное совпадение: Семантически эквивалентные логические формы, но с возможными различиями в индексах и порядке
  • Охват грамматики: Доля грамматических расширений, поддерживаемых моделью, от общей грамматики

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

  • Базовая модель Wu и др. (2024): 2-слойный кодировщик-декодировщик трансформатора
  • Варианты по количеству слоёв: Версии с 3 и 4 слоями
  • Версии с увеличением данных: Добавление примеров с конкретными модификациями предложных фраз

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

  • Использование официального интерпретатора RASP для оценки программ
  • Отображение лексемы основано на всех лексемах в обучающем наборе COGS
  • Детерминированные программы используют доверительный интервал Клоппера-Пирсона

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

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

Производительность модели RASP

COGS (точное совпадение строк)

  • Тестовый набор: 99,97% (99,81-99,99%)
  • obj_pp_to_subj_pp: 100,00% (99,63-100,00%)
  • pp_recursion: 98,40% (97,41-99,08%)
  • cp_recursion: 99,90% (99,44-99,997%)
  • Общая генерализация: 99,89% (99,83-99,93%)

ReCOGS_pos (семантическое точное совпадение)

  • Тестовый набор: 100,00% (99,88-100,00%)
  • obj_pp_to_subj_pp: 92,20% (90,36-93,79%)
  • pp_recursion: 100,00% (99,63-100,00%)
  • cp_recursion: 100,00% (99,63-100,00%)
  • Общая генерализация: 99,63% (99,54-99,71%)

Сравнение производительности базовых трансформаторов

Базовая модель Wu и др. (2024) (ReCOGS_pos)

  • pp_recursion: 40,2% ± 9,3%
  • cp_recursion: 52,4% ± 1,4%
  • obj_pp_to_subj_pp: 19,7% ± 6,1%

Анализ ошибок притяжения

Анализ ошибок базовых трансформаторов подтверждает теоретические предсказания:

  • 96,73% ошибок с одним отношением соответствуют паттерну ошибок притяжения
  • 100% ошибок предложных фраз глубины 2 указывают на ближайшее существительное предложной фразы
  • Подтверждает гипотезу нерекурсивной линейной обработки

Проверка нового раздела генерализации

Раздел генерализации "v_dat_p2_pp_moved_to_recipient":

  • Производительность базовой модели: 13% ± 15,6% (сравнима с самыми сложными разделами)
  • Поддерживает гипотезу плоской обработки вместо древовидной структуры

Неэффективность увеличения количества слоёв

Увеличение количества слоёв трансформатора (3-4 слоя) не улучшает производительность на obj_pp_to_subj_pp, что согласуется с выводами Petty и др. (2024).

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

Исследования композиционной генерализации

  • Тестовый набор COGS: Kim и Linzen (2020) предложили его, сообщив о точности структурной генерализации трансформаторов близкой к 0%
  • Улучшение ReCOGS: Wu и др. (2024) получили ненулевые, но всё ещё низкие результаты через семантическое точное совпадение
  • Иерархические методы: Liu и др. (2021), Weißenhorn и др. (2022) используют явные древовидные структуры для достижения высокой производительности

Применение RASP

  • Оригинальный RASP: Weiss и др. (2021) для анализа способностей кодировщика трансформатора
  • Расширение декодировщика: Zhou и др. (2023) расширили на авторегрессивный декодировщик, анализируя генерализацию по длине
  • Приложения для конкретных задач: Первое применение RASP к сложной задаче семантического анализа

Исследования ошибок притяжения

  • Лингвистические основы: Jespersen (1954) описал ошибки притяжения в согласовании подлежащего и сказуемого
  • Ошибки притяжения в нейронных сетях: van Schijndel и др. (2019), Goldberg (2019) наблюдали аналогичные явления в трансформаторах

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

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

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

Ограничения

  1. Ручное конструирование: Модель RASP разработана вручную, а не обучена
  2. Ограничения лексики: Предполагается известное отображение части речи и типа глагола, не решается лексическая генерализация
  3. Специфичность языка: Применимо только к английскому языку; применимость к другим языкам неизвестна
  4. Специфичность задачи: Модель разработана специально для COGS, не является универсальной языковой моделью

Будущие направления

  1. Алгоритмы обучения: Исследование того, как заставить трансформаторы обучаться аналогичным правилам маскирования
  2. Цели обучения: Изучение методов увеличения данных, обучения по программе, обучения с подкреплением
  3. Улучшения архитектуры: Проектирование лучших индуктивных смещений для содействия композиционной генерализации
  4. Многоязычное расширение: Проверка эффективности метода на других языках

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

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

  1. Теоретический вклад: Конструктивное доказательство уточняет границы теоретических способностей трансформаторов
  2. Методологическая инновация: Предложенное плоское решение оспаривает предположение о необходимости иерархических представлений
  3. Эмпирическая строгость: Подробный анализ ошибок и проверка предсказаний усиливают достоверность выводов
  4. Инженерная полнота: Предоставление полностью воспроизводимого кода и подробной документации реализации
  5. Глубокие инсайты: Теория ошибок притяжения предоставляет новую перспективу для понимания отказов трансформаторов

Недостатки

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

Влияние

  1. Теоретическое влияние: Предоставление нового теоретического фреймворка и инструментов анализа для исследований композиционной генерализации
  2. Методологическое влияние: Метод анализа RASP может быть широко применён к исследованиям других способностей трансформаторов
  3. Практическое руководство: Предоставление конкретных технических направлений для улучшения обучения трансформаторов

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

  1. Исследовательский инструмент: Как теоретический инструмент для анализа способностей трансформаторов
  2. Тестовые наборы: Предоставление эталонной реализации для оценки способностей композиционной генерализации
  3. Учебные ресурсы: Помощь в понимании внутренних механизмов работы трансформаторов
  4. Проектирование алгоритмов: Предоставление вдохновения для разработки лучших алгоритмов композиционной генерализации

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

  1. Kim, N., & Linzen, T. (2020). COGS: A compositional generalization challenge based on semantic interpretation. EMNLP 2020.
  2. Wu, Z., Manning, C. D., & Potts, C. (2024). ReCOGS: How incidental details of a logical form overshadow an evaluation of semantic interpretation. TACL.
  3. Weiss, G., Goldberg, Y., & Yahav, E. (2021). Thinking like transformers. NeurIPS 2021.
  4. Zhou, H., et al. (2023). What algorithms can transformers learn? A study in length generalization. arXiv preprint.
  5. Zeller, A., et al. (2023). Grammar coverage. In The Fuzzing Book.

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