ToT
Jak działa
ToT rozszczepia wnioskowanie na trzy komponenty: (1) Generator mysli - LLM produkuje kandydatow na nastepny krok rozumowania, (2) Ewaluator mysli - LLM lub osobna funkcja ocenia obiecujanosc kazdego stanu, (3) Algorytm przeszukiwania - BFS lub DFS (lub beam search) eksploruje drzewo stanow. Model moze cofac sie do poprzedniego stanu i probowac innej galezi.
Rozwiązany problem
Modele jezykowe z CoT sa ograniczone do lewo-prawej, token-po-tokenie decyzji podczas wnioskowania, co nie sprawdza sie na zadaniach wymagajacych eksploracji, strategicznego planowania lub gdy poczatkowe decyzje sa krytyczne.
Komponenty
Komponent oparty na LLM, który generuje k kandydatów na nową myśl. Dwie strategie: 'sample' (niezależne próbkowanie z tego samego promptu - przy bogatej przestrzeni myśli, np. Creative Writing) lub 'propose' (sekwencyjne proponowanie kilku myśli w jednym promptcie - przy ograniczonej przestrzeni, np. Game of 24).
Oficjalna
LLM ocenia każdy stan na dwa sposoby: 'value' (przypisuje wartość liczbową lub kategorialną pojedynczemu stanowi, używane w Game of 24) lub 'vote' (porównuje wiele stanów i głosuje na najlepszy, używane w Creative Writing). Heurystyka jest miękka i zależy od jakości LLM.
Oficjalna
ToT używa klasycznych algorytmów: BFS (Game of 24, Creative Writing - utrzymuje b najobiecujących stanów na każdym poziomie) lub DFS (Mini Crosswords - eksploruje głęboko z cofaniem gdy stan jest oceniony jako mało obiecujący). Algorytm jest niezależny od LLM.
Oficjalna
Implementacja
Ewolucja
Szczegóły techniczne
Hiperparametry (konfigurowalne osie)
Liczba myśli generowanych na każdym kroku przez generator. Większe k = szersza eksploracja, ale liniowo wyższy koszt.
Liczba stanów zachowywanych na każdym poziomie BFS. Klasyczny parametr beam search - kompromis między eksploracją a kosztem.
Liczba wywołań LLM do oceny każdego stanu (uśredniana dla redukcji wariancji).
Maksymalna liczba kroków rozumowania w drzewie. Zależy od zadania (Game of 24: 3, Crosswords: znacznie głębiej).
Wybór strategii generowania myśli: sample (niezależne próbkowanie) lub propose (sekwencyjne propozycje w jednym promptcie).
Wybór strategii oceny stanu: value (niezależna ocena) lub vote (głosowanie nad zbiorem).
Złożoność obliczeniowa
Złożoność czasowa: O(k^T · c_LLM). Złożoność przestrzenna: O(b · T).
Wąskie gardło obliczeniowe
Każdy krok ToT wymaga wielu wywolan LLM: generacja k kandydatow + ewaluacja n_evaluate_sample razy dla kazdego z b stanow. Latencja i koszt API rosna multiplikatywnie z parametrami przeszukiwania.
Paradygmat wykonania
Trajektoria obliczen jest warunkowa - zalezy od ocen stanow. Rozne wejscia produkuja rozne ksztalty drzew i rozne sciezki.
Algorytm przeszukiwania kieruje obliczenia do najobiecujacych galezi drzewa na podstawie scorow z ewaluatora. Nieobiecujace galezie sa przycinane (nie sa dalej rozszerzane).
Równoległość
W obrebie jednego poziomu BFS generacja k kandydatow i ich ewaluacja sa w pelni rownolegle. Miedzy poziomami przeszukiwanie pozostaje sekwencyjne.
Wymagania sprzętowe
ToT to ramka inferencyjna - dziala na dowolnym backendzie zdolnym uruchomic LLM (API, local GPU, TPU). Sam algorytm przeszukiwania jest CPU-bound i lekki.
Lokalne uruchomienie ToT korzysta z GPU dla rownoleglego batchowania k kandydatow i b stanow w jednym wywolaniu inferencji LLM.