ТЕХНИЧЕСКОЕ ЗАДАНИЕ: Реализовать Tree of Thoughts

1. Цель задачи

Освоить метод Tree of Thoughts (ToT) — продвинутую технику рассуждения, где LLM генерирует и оценивает множество «мыслей» в виде дерева, а поиск (DFS/BFS) выбирает наиболее перспективный путь. Реализовать полный пайплайн: генерация мыслей, их оценка через LLM, стратегия поиска и итоговая агрегация ответа. Сравнить качество с базовым Chain-of-Thought (CoT) на математическом или логическом бенчмарке.

Ключевой результат Рабочий Python-скрипт/ноутбук, который на тестовом наборе демонстрирует точность ответов выше CoT на 10–20%.

2. Исходные данные

Если нет реального API/модели — симулируем:

1. Использовать OpenAI API (бесплатные кредиты ~$5, хватит на 1000–2000 вызовов gpt-4o-mini).
2. Если нет ключа — создать аккаунт на platform.openai.com и получить API-ключ.
3. В крайнем случае — взять Google Colab с TinyLlama-1.1B-Chat-v1.0 (бесплатно, но качество может не дать +10% к CoT; для симуляции приемлемо).
4. Подготовить 50 тестовых примеров из GSM8K (первые 50 из train split).

3. Технологический стек

4. Этапы выполнения

Этап 1: Подготовка данных и baseline CoT (1 час)

Действия

1. Загрузить бенчмарк GSM8K:

   from datasets import load_dataset
   dataset = load_dataset("gsm8k", "main", split="test")
   problems = dataset.select(range(200))  # 200 примеров для теста
   

2. Реализовать простой CoT-промпт (один вызов LLM, без разбиения на шаги внутри кода):

   System: "Ты — математический решатель. Объясни шаги и дай окончательный ответ числом."
   User: "Вопрос: {problem}\nРешение: Давайте думать пошагово:\n"
   

3. Прогнать 200 примеров через CoT, сохранить ответы и точность (accuracy извлечения финального числа).
4. Зафиксировать baseline accuracy (например, 65% на gpt-4o-mini).

Ожидаемый результат этапа Число baseline_accuracy + сохранённый JSON с парами (problem, cot_answer, true_answer).

Этап 2: Реализация модуля "мыслей" (thought generation) (1.5 часа)

Действия

1. Разработать промпт для генерации промежуточных мыслей — список возможных следующих шагов (branch factor K=3):

   System: "Ты генерируешь {K} различных промежуточных шагов для решения задачи. Каждый шаг — это одна строка."
   User: "Задача: {problem}\nТекущий контекст (уже сделанные шаги): {context}\nСгенерируй {K} различных возможных следующих шагов (по одному на строку):"
   

2. Написать функцию generate_thoughts(problem, context, K) -> list[str], возвращающую список из K строк.
3. Обработать ошибки парсинга: если ответ не содержит ровно K строк, ретрай (до 2 раз) или взять первые K.
4. Оценить качество на 10 примерах вручную — разумные ли генерируются шаги.

Ожидаемый результат этапа Функция generate_thoughts с документацией, тест на 10 примерах.

Этап 3: Реализация модуля оценки (state evaluation) (1.5 часа)

Действия

1. Промипт для оценки вероятности успеха (score от 1 до 10 или вероятность в %):

   System: "Оцени вероятность того, что текущий контекст ведёт к правильному ответу. Ответь только числом от 0.0 до 1.0."
   User: "Задача: {problem}\nКонтекст: {context}\nВероятность успеха (0.0-1.0):"
   

2. Функция evaluate_state(problem, context) -> float — извлекает число из ответа LLM (с fallback на 0.5 при ошибке).
3. Использовать ту же LLM, что и для генерации (экономия), но можно экспериментировать с разными промптами.
4. Проверить корреляцию оценки с истинным результатом на 10–20 контекстах (необязательно, но полезно).

Ожидаемый результат этапа Функция evaluate_state, готовая к интеграции.

Этап 4: Реализация поиска (DFS/BFS) и итоговой агрегации (2 часа)

Действия

1. Выбрать стратегию BFS с ограничением глубины (max_depth=5) и ширины (beam_width=5). Или DFS с backpropagation оценок.
2. Реализовать BFS (лучше для математики):
   • Начальный контекст: пустая строка.
   • Для каждого уровня: сгенерировать K мыслей для каждого состояния в текущей очереди (beam).
   • Оценить каждое новое состояние, оставить top beam_width по оценке.
   • Если достигнут лист (глубина max_depth или контекст содержит "Ответ:") — сохранить траекторию.
3. Из сохранённых траекторий (листьев) — агрегировать ответ:
   • Взять состояние с наивысшей оценкой, извлечь из него итоговый ответ (регекс Ответ:?\s*(\d+\.?\d*)).
   • Если несколько — голосование (majority voting).
4. Обработать случаи, когда ни одна траектория не содержит ответа — fallback на CoT.
5. Добавить логирование (уровень, оценка, выбранный путь) для отладки.

Ожидаемый результат этапа Функция solve_tot(problem) -> str (финальный ответ).

Этап 5: Оценка и сравнение с CoT (1 час)

Действия

1. Прогнать 200 тестовых примеров через ToT (с теми же настройками: K=3, beam_width=5, max_depth=5).
2. Сравнить accuracy с baseline CoT: tot_accuracy / cot_accuracy >= 1.1 (т.е. +10%).
3. Собрать статистику:
   • Средняя глубина поиска.
   • Средняя оценка на выбранных путях.
   • Процент падений на CoT fallback.
4. Вывести результаты в виде таблицы:

   Метод	Accuracy	Среднее время на задачу (с)
   CoT	65.0%	1.2
   ToT	73.5%	4.8

5. Записать результаты в файл results.json вместе с гиперпараметрами.

Ожидаемый результат этапа Файл results.json с метриками и сравнением, подтверждённый прирост >=10%.

5. Критерии приемки (Definition of Done)

• Реализован и протестирован модуль generate_thoughts с поддержкой batch-запросов (опционально).
• Реализован и протестирован модуль evaluate_state с корректным парсингом.
• Реализован алгоритм поиска (BFS или DFS) с настраиваемыми гиперпараметрами (K, beam_width, max_depth).
• Скрипт запускается и решает 200 задач из GSM8K за разумное время (<30 мин на gpt-4o-mini).
• Логируется каждая итерация: уровень, оценка, выбранные ветви (включая fallback).
• Итоговая accuracy ToT выше baseline CoT минимум на 10% (относительно).
• Код соответствует PEP8, содержит README с инструкцией по запуску.
• Результаты (accuracy, время, примеры) записаны в results.json и report.md.

6. Ожидаемый результат

• Основной артефакт Python-скрипт tot_solver.py или Jupyter Notebook tot_solver.ipynb со всеми модулями.
• Файл результатов results.json с полями:

  {
    "baseline": {"method": "CoT", "accuracy": 0.65, "avg_time": 1.2},
    "tot": {"method": "ToT", "accuracy": 0.735, "avg_time": 4.8, "params": {"K": 3, "beam_width": 5, "max_depth": 5}},
    "relative_improvement": 13.1
  }
  

• Отчёт report.md (2–3 абзаца): описание подхода, анализ ошибок, выводы.
• Опционально Демонстрация на 5–10 примерах с визуализацией дерева (простая ascii-схема или через networkx + matplotlib).

7. Возможные сложности и их решение

8. Бюджет времени (оценка)

Примечание При первом выполнении может потребоваться до 10 часов из-за отладки API, парсинга и анализа ошибок. Распределите этапы на 2–3 дня.

9. Связанные вопросы из базы знаний

10. Чек-лист самопроверки

• Я реализовал generate_thoughts, которая возвращает ровно K строк (или выбрасывает исключение после 2 ретраев).
• Я протестировал evaluate_state на 5 простых контекстах — для правильного контекста оценка выше 0.7, для неправильного ниже 0.3.
• Я реализовал BFS/DFS с ограничением глубины и ширины — программа не уходит в бесконечный цикл.
• Я запустил полный прогон на 200 примерах и сравнил accuracy — прирост ≥10% зафиксирован в results.json.
• Я написал README с указанием всех зависимостей, инструкцией запуска и ожидаемыми результатами.