Tree of Thoughts (ToT)

Tree of Thoughts (ToT) là framework prompt engineering, trong đó một mô hình ngôn ngữ lớn (LLM) giải quyết vấn đề bằng cách tìm kiếm trên cây các lời giải từng phần. Ở mỗi bước, model đề xuất một số bước tiếp theo khả dĩ, gọi là các thought, đánh giá mức độ triển vọng của từng trạng thái kết quả, rồi thuật toán tìm kiếm quyết định nhánh nào cần mở rộng, giữ lại hoặc loại bỏ. Trong khi prompt chuỗi suy nghĩ chỉ theo một mạch lập luận từ token đầu tiên, ToT có thể nhìn trước và quay lui. Shunyu Yao cùng các cộng sự tại Đại học Princeton và Google DeepMind giới thiệu phương pháp này trong Tree of Thoughts: Giải quyết vấn đề có chủ đích bằng mô hình ngôn ngữ lớn, được trình bày tại NeurIPS 2023; cùng tháng đó, Jieyi Long đề xuất một hệ thống tìm kiếm dạng cây tương tự để giải Sudoku bằng LLM. Với câu đố Game of 24, ToT nâng tỷ lệ thành công của GPT-4 từ 4% khi dùng prompt chuỗi suy nghĩ lên 74%.

Cách Tree of Thoughts hoạt động#

Yao và cộng sự định nghĩa ToT qua bốn lựa chọn thiết kế:

• Phân rã thought: Mỗi bước là gì. Trong Game of 24, một thought là một phương trình; trong sinh văn bản sáng tạo, đó là kế hoạch cho đoạn văn; trong trò ô chữ, đó là một từ cần điền.
• Bộ tạo thought: Cách tạo các phương án. Model có thể lấy mẫu độc lập nhiều thought, phù hợp với các bước mở, hoặc đề xuất danh sách các lựa chọn riêng biệt trong một prompt để tránh trùng lặp khi số lựa chọn bị giới hạn.
• Bộ đánh giá trạng thái: Cách đánh giá tiến độ. Model tự chấm từng trạng thái, chẳng hạn "chắc chắn", "có thể" hoặc "không thể" đạt mục tiêu, hoặc bình chọn trạng thái tốt nhất trong số nhiều trạng thái. Các đánh giá này đóng vai trò heuristic tìm kiếm, tương tự vai trò của hàm chấm điểm do con người viết trong thuật toán tìm kiếm cổ điển.
• Thuật toán tìm kiếm: Cách khám phá cây. Tìm kiếm theo chiều rộng giữ lại b trạng thái tốt nhất ở mỗi cấp; tìm kiếm theo chiều sâu đi theo nhánh triển vọng nhất, cắt bỏ trạng thái mà bộ đánh giá loại trừ và quay lui.

Ví dụ: Game of 24#

Game of 24 đưa ra bốn số cần kết hợp bằng +, -, x và / để tạo thành 24, mỗi số chỉ được dùng một lần. ToT chia lời giải thành ba bước, mỗi bước là một phương trình gộp hai số. Với đầu vào 4 9 10 13, prompt đề xuất liệt kê các phương án như:

13 - 9 = 4 (left: 4 4 10)
10 - 4 = 6 (left: 6 9 13)
4 + 9 = 13 (left: 10 13 13)
4 x 13 = 52 (left: 9 10 52)

Sau đó, prompt đánh giá hỏi liệu mỗi tập số còn lại có thể đạt 24 hay không. "4 4 10" được đánh giá là chắc chắn, vì (10 - 4) x 4 = 24; "6 9 13" cũng vậy, vì (13 - 9) x 6 = 24; còn "10 13 13" và "9 10 52" là không thể, nên quá trình tìm kiếm chỉ mở rộng hai nhánh đầu. Đi theo nhánh thứ nhất sẽ có 10 - 4 = 6 (còn lại: 4 6), rồi 4 x 6 = 24.

Trong thí nghiệm của bài báo trên 100 câu đố khó, tìm kiếm theo chiều rộng giữ lại 5 trạng thái tốt nhất ở mỗi bước, và mỗi trạng thái được đánh giá ba lần. ToT với GPT-4 giải được 74% câu đố, so với 7,3% khi prompting trực tiếp, 4,0% với chuỗi suy nghĩ và 9,0% với chuỗi suy nghĩ kết hợp tính nhất quán tự thân. Ngay cả chuỗi suy nghĩ tốt nhất trong 100 chuỗi được lấy mẫu cũng chỉ đạt 49%; ToT chỉ giữ một trạng thái mỗi bước đạt 45%.

Vị trí của Tree of Thoughts#

ToT hữu ích với các vấn đề mà lựa chọn ban đầu giới hạn những bước sau và khó sửa sai nếu bước đầu tiên sai: câu đố, lập kế hoạch và toán nhiều bước. Trong trò ô chữ mini 5x5, ToT theo chiều sâu có cắt tỉa điền đúng 60% số từ và giải được 4 trong 20 câu đố. Đổi lại là chi phí tính toán: mỗi cấp của cây cần nhiều lệnh gọi sinh và đánh giá, nên một câu trả lời có thể cần hàng chục lệnh gọi model trở lên và nhiều token hơn hẳn một chuỗi, kéo theo độ trễ suy luận tương ứng.

Vòng lặp sinh, đánh giá và mở rộng tương tự cũng xuất hiện ở quy mô lớn hơn nhiều trong tìm kiếm thí nghiệm tự động, chẳng hạn như tinh chỉnh siêu tham số. Trong AutoTrain của Ultralytics Platform, Ask AI có thể huấn luyện một số model Ultralytics YOLO khác nhau ở một thiết lập, chẳng hạn kích thước ảnh 640, 800 và 960; so sánh các lượt chạy đã hoàn tất theo mAP50-95 trên tập validation; rồi đề xuất thí nghiệm tiếp theo dựa trên kết quả tốt nhất.

Tree of Thoughts và các phương pháp liên quan#

• Prompt chuỗi suy nghĩ: Một mạch lập luận duy nhất, tương đương cây chỉ có một nhánh ở mỗi cấp.
• Prompt ReAct: Đan xen lập luận với hành động trong môi trường bên ngoài, chẳng hạn tìm kiếm hoặc gọi công cụ, rồi tiếp tục dựa trên kết quả của các hành động đó. ToT tìm kiếm trên các thought khả dĩ do chính model tạo ra.
• Tính nhất quán tự thân: Lấy mẫu một số chuỗi hoàn chỉnh rồi chọn câu trả lời cuối cùng theo đa số, không đánh giá các bước từng phần trong quá trình lập luận.
• Graph of Thoughts: Khái quát hóa cây thành đồ thị, trong đó các suy nghĩ cũng có thể được hợp nhất và tinh chỉnh; phương pháp này báo cáo chất lượng sắp xếp tốt hơn ToT 62% với chi phí thấp hơn hơn 31%.
• Tìm kiếm cây Monte Carlo (MCTS): Thuật toán tìm kiếm đứng sau AlphaGo, cân bằng giữa việc khám phá các nhánh mới và khai thác các nhánh tốt, đồng thời có thể thay thế tìm kiếm theo chiều rộng hoặc chiều sâu trên các suy nghĩ.
• Các model suy luận: Được huấn luyện bằng học tăng cường để tạo các chuỗi suy luận dài trong một lần sinh; ToT sử dụng chương trình tìm kiếm bên ngoài để tạo nhánh và quay lui quanh một model thông thường.