Giới thiệu

Các mô hình ngôn ngữ đã đạt được những tiến bộ đáng kể. Chúng thể hiện hiệu suất xuất sắc trong nhiều loại nhiệm vụ khác nhau. Tuy nhiên, các mô hình này thường hoạt động theo một khuôn mẫu tuần tự, từng bước và một mạch từ đầu tới cuối . Điều này không thực sự lý tưởng với các task cần phải lên kế hoạch trước, xem xét và điều chỉnh lại các bước trước đó, hoặc khi các quyết định ban đầu có ảnh hưởng tới các bước sau.

Để giải quyết vấn đề này, một phương pháp mới được giới thiệu, được gọi là "Tree of Thoughts" hay ToT. Đây là một cải tiến so với phương pháp "Chain of Thought" truyền thống. Phương pháp ToT cho phép các mô hình ngôn ngữ "suy nghĩ" nhiều đoạn text khác nhau. Nhờ đó, các mô hình này có thể xem xét các lựa chọn, suy nghĩ theo các hướng suy luận khác nhau và thậm chí là tự đánh giá các quyết định của mình để xác định hướng đi tiếp theo . Các mô hình cũng có khả năng lập kế hoạch cho tương lai hoặc quay lại sửa đổi các quyết định trước đó khi phải giải quyết những tình huống khác nhau.

Các thử nghiệm đã cho thấy rằng phương pháp ToT cải thiện đáng kể khả năng giải quyết vấn đề của các mô hình ngôn ngữ, đặc biệt trong các nhiệm vụ liên quan tới lập kế hoạch hoặc tìm kiếm, ví dụ như trò chơi 24 (Game of 24), Viết sáng tạo (Creative Writing), và Ô chữ Mini (Mini Crosswords). Với trò chơi 24, phương pháp truyền thống chỉ giải quyết thành công 4% số nhiệm vụ, trong khi phương pháp ToT mới đã đạt tỷ lệ thành công ấn tượng lên đến 74%.

Background

Input-output (IO) prompting

Kỹ thuật "input-output prompting" trong các mô hình ngôn ngữ liên quan đến việc định dạng đầu vào cho mô hình ngôn ngữ một cách cụ thể sao cho nó có thể tạo ra đầu ra mong muốn. Điều này đặc biệt quan trọng với các mô hình như GPT, vốn có khả năng tạo ra nhiều loại phản hồi khác nhau dựa trên đầu vào được cung cấp.

Nói một cách khác, "input-output prompting" đòi hỏi việc sử dụng đoạn văn bản đầu vào sao cho có chứa các gợi ý hoặc dấu hiệu nhằm hướng dẫn mô hình ngôn ngữ tạo ra loại đầu ra mà bạn mong muốn.

Chain-of-thoughts (CoT) prompting

Trong một số tình huống, mối quan hệ giữa đầu vào ($x$) và đầu ra ($y$) có thể không rõ ràng. Ví dụ như trong trường hợp một bài toán phức tạp, nơi mà đầu vào là câu hỏi và đầu ra là đáp án cuối cùng dưới dạng số, lộ trình đến lời giải sẽ bao gồm nhiều bước trung gian .

Ý tưởng đằng sau kỹ thuật "CoT prompting" là trình bày một chuỗi các bước trung gian, được gọi là Chain-of-thoughts ($z_1, \ldots, z_n$). Mỗi "suy nghĩ" ($z_i$) trong chuỗi này là một mô tả bằng ngôn ngữ tự nhiên đại diện cho một bước trung gian hướng tới việc giải quyết vấn đề.

Việc $z_i$ nên là một cụm từ, một câu, hay một đoạn văn vẫn còn mơ hồ. Cơ bản, CoT prompting nhằm làm cho quá trình giải quyết vấn đề của mô hình trở nên minh bạch và dễ quản lý hơn bằng cách tạo ra một chuỗi các bước trung gian liên quan và có ý nghĩa. Điều này có thể đặc biệt hữu ích trong các nhiệm vụ phức tạp, khi mà các bước để có lời giải chưa thật sự rõ ràng khi chỉ có thông tin đầu vào.

Kĩ thuật Self-Consistency with Chain-of-Thought (CoT-SC) prompting

CoT-SC, viết tắt của "Chain of Thought with Self-Consistency", phương pháp này dựa trên việc tạo và sử dụng nhiều "chuỗi suy nghĩ" độc lập và có phân phối giống nhau (independent and identically distributed - i.i.d.) để đưa ra quyết định hoặc giải quyết vấn đề. Cụ thể như sau:

Tạo ra Chuỗi Suy Nghĩ (Chain of Thought)

• Đầu vào là $x$.
• Mỗi "chuỗi suy nghĩ" được biểu diễn như là một dãy các bước suy nghĩ $[z^{(i)}_1, z^{(i)}_2, ..., z^{(i)}_n]$ dẫn đến một kết quả $y^{(i)}$.
• $i$ là chỉ số của mỗi chuỗi suy nghĩ, với $i$ chạy từ 1 đến $k$, $k$ là số lượng chuỗi suy nghĩ được tạo ra.
• Mỗi chuỗi suy nghĩ là độc lập và được tạo ra dựa trên cùng một phân phối, đảm bảo tính đồng nhất.

Lựa chọn kết quả cuối cùng

• Phương pháp này chọn ra kết quả xuất hiện nhiều nhất ($y$) từ các chuỗi suy nghĩ. Cụ thể, nó tìm ra $y$ mà có số lần xuất hiện nhiều nhất.
• Số lần xuất hiện được đếm bằng công thức: $\#\{i | y^{(i)} = y\}$, nghĩa là số lần xuất hiện của $y$ trong tất cả $k$ chuỗi suy nghĩ.
• Kết quả cuối cùng là $y$ với số lượng đếm cao nhất, được tìm ra thông qua hàm: $\text{arg max}_y$.

Ưu điểm của CoT-SC so với CoT

• CoT-SC sử dụng nhiều cách suy nghĩ khác nhau có thể dẫn đến giải pháp của cùng một vấn đề. Với kĩ thuật này ta có thể tiếp cận với nhiều giải pháp tiềm năng và tạo ra một bộ kết quả đầu ra đa dạng và phong phú hơn.
• Bằng cách sử dụng nhiều chuỗi suy nghĩ, CoT-SC cung cấp một bộ bước trung gian phong phú, có thể dẫn đến một kết quả cuối cùng đáng tin cậy hơn.

Hạn chế

• Trong mỗi chuỗi suy nghĩ, không có sự khám phá địa phương cụ thể về các bước suy nghĩ khác nhau. Phương pháp cũng không xét đến các lộ trình thay thế trong từng chuỗi suy nghĩ.
• Heuristic "phổ biến nhất" để chọn kết quả cuối cùng chỉ thực sự hiệu quả khi không gian đầu ra bị giới hạn, ví dụ như trong các bài toán trắc nghiệm.

Tree of Thoughts (ToT)

Hãy tưởng tượng khi giải quyết một bài toán, chúng ta bắt đầu suy nghĩ duyệt từng trường hợp có thể xảy ra của bài toán. Mỗi trường hợp này có thể coi là một nhánh, mỗi nhánh dẫn ta đến một ý tưởng hoặc giải pháp nào đó. Chúng ta thường sử dụng một phương pháp kinh nghiệm nào đó để chọn nhánh phù hợp.

Các mô hình hiện nay khi giải quyết vấn đề thường bỏ qua hai điều quan trọng:

1. Chúng không xem xét nhiều cách tiếp cận khác nhau trong một lần suy nghĩ, tức là không thử nghiệm nhiều "nhánh" khác nhau. Điều này giống như khi bạn chỉ nhìn thẳng một hướng mà không nhìn ngó xung quanh để tìm thêm lựa chọn.

2. Chúng không lên kế hoạch hoặc dự đoán trước được những gì sẽ xảy ra sau đó, hoặc không thử quay lại bước trước nếu cách tiếp cận hiện tại bị bế tắc. Điều này giống như khi bạn cố gắng giải quyết một câu đố mà không thử nghiệm các giả thuyết khác nhau hoặc kiểm tra lại các bước trước đó có thể đã sai ở đâu.

Để giải quyết vấn đề này, ToT đề xuất một cách mới để máy "suy nghĩ" giống như cách chúng ta giải quyết một bài toán: Coi bài toán như một hành trình trên cây, mỗi bước suy nghĩ của máy được xem như là một node trên cây, node này chứa đựng cả thông tin vấn đề lẫn các suy nghĩ trước đó. Điều này giúp máy có thể khám phá nhiều hướng giải quyết khác nhau một cách linh hoạt hơn.

Khi thực hiện ToT, chúng ta cần xem xét 4 câu hỏi chính:

1. Phân chia quá trình trung gian thành các bước suy nghĩ

Câu hỏi đặt ra là làm thế nào để chia nhỏ một quá trình hoặc vấn đề thành các bước riêng lẻ hoặc "suy nghĩ" mà mô hình có thể theo dõi. Tưởng tượng rằng bạn đang giải một bài toán phức tạp, để giải quyết nó, bạn cần phân tách thành các phần nhỏ hơn. ToT yêu cầu mô hình làm điều tương tự: xác định các "bước suy nghĩ" cụ thể để tiến gần đến giải pháp.

2. Tạo ra các suy nghĩ tiềm năng từ mỗi trạng thái

Từ một node hoặc trạng thái cụ thể trên cây (nói một cách khác, một giai đoạn cụ thể trong quá trình giải quyết vấn đề), mô hình nên có khả năng tạo và phát triển các bước tiềm năng khác nhau. Các chiến lược để tạo ra các ứng viên cho bước suy nghĩ tiếp theo như sau:

a. Sample các suy nghĩ độc lập và có phân phối giống nhau (i.i.d.)

Chiến lược này liên quan đến việc lấy mẫu các suy nghĩ i.i.d. từ một prompt theo kĩ thuật Chain-of-Thought (CoT). Đối với mỗi $j$ từ 1 đến $k$, một suy nghĩ $z^{(j)}$ được lấy mẫu dựa trên trạng thái hiện tại $s$.

Ví dụ như trong task Creative Writing, các bạn có thể tham khảo các bước trong ảnh dưới:

Chiến lược này phù hợp khi không gian suy nghĩ phong phú, tức là có nhiều bước tiếp theo hoặc suy nghĩ mà mô hình có thể xem xét.

b. Đề xuất suy nghĩ một cách tuần tự

Trong chiến lược này, mô hình đề xuất các suy nghĩ một cách tuần tự bằng cách sử dụng một "proposed prompt". Tức là, một chuỗi suy nghĩ $[z^{(1)}, \ldots, z^{(k)}]$ được lấy mẫu dựa trên trạng thái hiện tại $s$. Chiến lược này hoạt động tốt khi không gian suy nghĩ bị hạn chế, ví dụ khi mỗi suy nghĩ tương đối nhỏ hoặc đơn giản.

Một ví dụ áp dụng cách thức này là trong "Game of 24".

Bằng cách đề xuất các suy nghĩ khác nhau trong cùng một bối cảnh một cách tuần tự, phương pháp này giúp tránh sự trùng lặp trong các suy nghĩ được tạo ra.

3. Đánh giá Heuristic của các trạng thái

Để giúp mô hình ngôn ngữ giải quyết vấn đề một cách hiệu quả, có một bước quan trọng là đánh giá các trạng thái: Xác định xem mỗi bước tiềm năng hoặc giải pháp có khả năng thành công như thế nào. Điều này tương tự như cách con người sử dụng các kinh nghiệm hoặc đánh giá trực giác khi giải quyết vấn đề. Ở đây, một "trạng thái" đề cập đến một bước tiềm năng hoặc giải pháp mà mô hình đang xem xét.

a. Đánh giá từng trạng thái độc lập

Trong chiến lược này, mỗi trạng thái $s$ trong "biên giới" (frontier - tập hợp các trạng thái đang được khám phá, ký hiệu là $S$) được đánh giá một cách độc lập. Một "value prompt" được sử dụng để suy luận về trạng thái $s$ và tạo ra một giá trị vô hướng $v$, có thể là một điểm số (ví dụ, từ 1 đến 10) hoặc phân loại (ví dụ, chắc chắn/có thể/không thể) có thể được chuyển thành giá trị một cách heuristic.

Việc đánh giá có thể bao gồm nhiều hình thức suy luận, bao gồm cả mô phỏng nhìn trước và đánh giá thông thường, giúp nâng cao các trạng thái "tốt" và loại bỏ các trạng thái "xấu". Việc đánh giá giá trị không cần phải hoàn hảo mà chỉ mang tính tương đối

b. Bỏ phiếu qua các trạng thái

Trong chiến lược này, các trạng thái được đánh giá cùng nhau thay vì một cách độc lập. Một trạng thái "tốt" $s^*$ được chọn thông qua một "vote prompt" so sánh các trạng thái khác nhau trong $S$. Phương pháp này hữu ích trong trường hợp đánh giá trực tiếp theo process của vấn đề gặp khó khăn (ví dụ, khi đánh giá tính nhất quán của một đoạn văn). Khi này việc so sánh các solution với nhau sẽ là khả thi hơn .

Đối với cả hai chiến lược, LM có thể được prompt nhiều lần để tổng hợp kết quả giá trị hoặc bỏ phiếu, cân nhắc giữa thời gian, nguồn lực và chi phí để đổi lấy các heuristic đáng tin cậy và mạnh mẽ hơn.

4. Lựa chọn thuật toán tìm kiếm

Trong việc lựa chọn thuật toán để duyệt và tìm kiếm các giải pháp, ta có thể sử dụng nhiều loại thuật toán khác nhau tùy thuộc vào cấu trúc của cây.

Có 2 thuật toán cơ bản:

1. Tìm kiếm theo chiều rộng (Breadth-first search - BFS): Thuật toán này giữ một tập hợp các trạng thái tiềm năng nhất $b$ ở mỗi bước. Nó thích hợp cho các bài toán như "Game of 24" và "Creative writing", nơi độ sâu của cây hạn chế $(T ≤ 3)$ và các bước suy nghĩ ban đầu có thể được đánh giá và cắt giảm xuống một tập hợp nhỏ $(b ≤ 5)$. BFS duyệt qua các node ở độ sâu hiện tại trước khi chuyển sang các node ở độ sâu tiếp theo.

2. Tìm kiếm theo chiều sâu (Depth-first search - DFS): Thuật toán này tìm kiếm trạng thái tiềm năng nhất trước và tiếp tục theo con đường này cho đến khi tới kết quả cuối cùng $(t > T)$, hoặc bộ đánh giá trạng thái xác định rằng không thể giải quyết vấn đề từ trạng thái hiện tại $s$ (nếu giá trị của trạng thái $s$ nhỏ hơn hoặc bằng một ngưỡng nhất định). Nếu tình huống sau xảy ra, cây con từ $s$ sẽ được cắt bỏ. Nếu một trong hai điều kiện này được đáp ứng, DFS sẽ quay lại trạng thái cha của $s$ để tiếp tục tìm kiếm.

Bằng cách giải quyết những vấn đề này, phương pháp "ToT" nhằm cung cấp một khung sườn cho phép các mô hình ngôn ngữ khám phá nhiều lộ trình suy luận và đánh giá các lựa chọn theo cách giống con người hơn.

Kết luận

Phương pháp "Tree of Thoughts" đánh dấu một tiến bộ đáng kể trong lĩnh vực trí tuệ nhân tạo, bằng cách hợp nhất khả năng suy luận tự nhiên của các mô hình ngôn ngữ với kỹ thuật tìm kiếm trên cây. Qua đó, nó không chỉ tái hiện phương pháp giải quyết vấn đề cổ điển trong một khuôn khổ hiện đại, mà còn vượt qua một số hạn chế của các phương pháp truyền thống bằng cách mở rộng khả năng giải quyết các vấn đề phức tạp và sáng tạo. Sự kết hợp này mở ra hướng đi mới cho AI, kỳ vọng mang lại những đột phá trong cả việc hiểu và giải quyết vấn đề theo cách giống con người hơn.

Tài liệu tham khảo

[1] Tree of Thoughts: Deliberate Problem Solving with Large Language Models

[2] Repo github