درخت افکار و LATS: جستجوی آگاهانه در مدل‌های زبانی

در سیستم‌های مبتنی بر زنجیره‌ی افکار (Chain-of-Thought)، استدلال مدل در مسیری کاملاً خطی پیش می‌رود. اگر مدل در نخستین گام محاسباتی فرضی اشتباه را برگزیند، دیگر راهی برای بازگشت به عقب ندارد و تا انتها روی همان پایه‌ی غلط حرکت می‌کند. در مسائلی مثل برنامه‌نویسی پیشرفته یا معماهای منطقی، این محدودیت خطی بودن به افت شدید دقت منجر می‌شود.

روش «درخت افکار» (Tree of Thoughts) و الگوریتم پیشرفته‌تر LATS با تبدیل فرآیند تفکر به یک درخت جستجو، امکان تولید چندین گزینه‌ی جایگزین، ارزیابی گام‌های میانی و هرس کردن مسیرهای بن‌بست را فراهم می‌کنند. در این درس با ساختار این جستجوها، ترکیب MCTS با مدل‌های زبانی و معیارهای مهندسی برای مدیریت هزینه‌ی بالای توکن آشنا می‌شوید.

یک مسیر خطی در زنجیره‌ی افکار (Chain-of-Thought یا CoT) جایی برای بازگشت به عقب ندارد. روش «درخت افکار» یا ToT (یائو و همکاران، 2023) فرآیند استدلال را به یک درخت با خودارزیابی روی هر گره تبدیل می‌کند. روش LATS (ژو و همکاران، 2024) نیز ToT را با ReAct و Reflexion ذیل الگوریتم جستجوی درختی مونت‌کارلو (Monte Carlo Tree Search یا MCTS) یکپارچه می‌سازد. در مسئله‌ی «بازی 24»، دقت از 4% در CoT به 74% در ToT می‌رسد؛ LATS نیز در بنچمارک HumanEval به معیار pass@1 برابر با 92.7% دست می‌یابد.

اهداف یادگیری

• قالب‌بندی استدلال به‌شکل جستجو: گره‌ها همان «افکار»، یال‌ها «بسط‌ها»، و ارزش (Value) میزان «امیدبخش بودن» مسیر است.
• پیاده‌سازی یک جستجوی سطح‌اول (BFS) به سبک ToT تنها با کتابخانه‌ی استاندارد پایتون، همراه با امتیازدهیِ خودارزیاب.
• توسعه‌ی آن به یک حلقه‌ی کوچک و آموزشی LATS MCTS شامل مراحل انتخاب (Select)، بسط (Expand)، شبیه‌سازی (Simulate) و پس‌انتشار (Backpropagate).
• تصمیم‌گیری درباره‌ی اینکه چه زمانی جستجو ارزش چندبرابر شدن مصرف توکن را دارد (بازی 24، تولید کد) و چه زمانی یک مسیر خطی کفایت می‌کند (پرسش‌وپاسخ ساده).

صورت مسئله

زنجیره‌ی افکار یک پیمایش خطی است. اگر گام اول اشتباه باشد، تمام گام‌های بعدی روی یک فرض‌پایه (Premise) نادرست پیش می‌روند. در مسئله‌ی بازی 24 (رسیدن به عدد 24 با استفاده از چهار رقم و اعمال جمع، تفریق، ضرب و تقسیم)، مدل GPT-4 با روش CoT به دقت ناچیز 4% می‌رسد. مدل در همان ابتدای کار عبارت فرعی نادرستی را انتخاب می‌کند و دیگر توان جبران آن را ندارد.

آنچه فرآیند استدلال نیاز دارد، توانایی پیشنهاد چندین گزینه‌ی کاندید، ارزیابی آن‌ها، انتخاب گزینه‌های امیدبخش و بازگشت به عقب هنگام رسیدن به بن‌بست است. این همان «جستجو» است. روش‌های Tree of Thoughts و LATS دو فرمول‌بندی استاندارد و بنیادین در این زمینه هستند.

مفاهیم پایه

درخت افکار (Yao et al., NeurIPS 2023)

هر گره یک گام میانی منسجم («یک فکر») است. هر گره می‌تواند به K فکر فرزند بسط یابد. مدل زبانی با یک پرامپت امتیازدهی، هر گره را خودارزیابی می‌کند. الگوریتم‌های جستجو — اعم از BFS، جستجوی عمق‌اول (DFS) یا جستجوی پرتویی (Beam search) — این درخت را می‌کاوند.

                     (root: "find 24 from 4 6 4 1")
                    /               |            \
           ("6 - 4 = 2")    ("4 + 1 = 5")    ("4 * 6 = 24")  <- Score: HIGH
              /   \              |                  |
          ...    ...          ...                finish

بخش کلیدی و اتکاپذیر این سیستم، همان خودارزیابی است. مقاله‌ی مرجع سه حالت مختلف را نشان می‌دهد: دسته‌بندی سه‌گانه‌ی sure / likely / impossible (قطعی / محتمل / غیرممکن)، امتیاز عددی بین 1..10، و رأی‌گیری میان گزینه‌های کاندید. هر سه حالت در بازی 24 عملکرد CoT را به‌شکل چشمگیری پشت سر می‌گذارند (رسیدن از 4% به 74% با GPT-4).

روش LATS (Zhou et al., ICML 2024)

روش LATS مفاهیم ToT، ReAct و Reflexion را ذیل MCTS یکپارچه می‌کند. در اینجا مدل زبانی سه نقش دارد:

• خط‌مشی (Policy): پیشنهاد اقدامات کاندید بعدی (به سبک ReAct).
• تابع ارزش (Value Function): امتیازدهی به یک مسیر ناتمام (مشابه خودارزیابی در ToT).
• تأمل‌گر درونی (Self-reflector): نوشتن تأملی به زبان طبیعی در صورت شکست (مشابه Reflexion) و استفاده از آن برای شروع دوباره‌ی مسیرهای پیش‌روی بعدی (Rollout).

بازخورد محیط (مشاهدات) با تابع ارزش ترکیب می‌شود تا جستجو به‌جای تکیه‌ی صرف بر قضاوت‌های مدل، بر پایه‌ی نتایج واقعی ابزارها پیش برود. نتایج ثبت‌شده در زمان انتشار مقاله عبارت بودند از: معیار pass@1 معادل 92.7% روی HumanEval با GPT-4 (بهترین نتیجه‌ی موجود)، و میانگین 75.9 روی WebShop با GPT-3.5 (نزدیک به سطح فاین‌تیونینگ مبتنی بر گرادیان).

ساختار حداقلی MCTS

هر تکرار از چهار مرحله تشکیل می‌شود:

1. انتخاب (Select): پیمایش از ریشه به سمت یک برگ با استفاده از فرمول UCT (حد بالای اطمینان برای درخت‌ها).
2. بسط (Expand): تولید K فرزند از طریق خط‌مشی.
3. شبیه‌سازی (Simulate): پیش‌روی (Rollout) از یک فرزند با استفاده از خط‌مشی و امتیازدهی به برگ حاصل با تابع ارزش (یا پاداش محیط).
4. پس‌انتشار (Backpropagate): به‌روزرسانی تعداد بازدیدها و تخمین‌های ارزش در طول مسیر بازگشت به سمت ریشه.

فرمول UCT به‌صورت Q(s, a) + c * sqrt(ln N(s) / N(s, a)) تعریف می‌شود. عبارت اول نشان‌دهنده‌ی بهره‌برداری (Exploitation) و عبارت دوم نشان‌دهنده‌ی کاوش (Exploration) است. مقدار c را متناسب با هر مسئله تنظیم کنید.

واقعیت هزینه‌ها

جستجو مصرف توکن را منفجر می‌کند. ToT در بازی 24 بین 100 تا 1000 برابر CoT توکن می‌سوزاند. LATS نیز وضعیتی مشابه دارد. این هزینه رایگان نیست؛ بنابراین جستجو را فقط برای مواردی کنار بگذارید که:

• ناکارآمدیِ آشکار یک مسیر خطی در آن‌ها ثابت شده باشد (بازی 24، کدهای پیچیده).
• درستی پاسخ بسیار مهم‌تر از زمان اجرای برنامه باشد.
• تابع ارزش ارزان و قابل‌اعتمادی در دسترس باشد (تست‌های واحد برای کد، هدف صریح عددی برای ریاضیات).

اگر مسئله‌ی شما تنها یک پاسخ درست دارد اما ارزیابِ آن نویز زیادی تولید می‌کند، جستجو اغلب اوضاع را بدتر می‌کند؛ چون در نهایت یک پاسخ غلط را پیدا می‌کند که تصادفاً «امتیاز بالایی» گرفته است.

جایگاه در سال 2026

اکثر ایجنت‌های عملیاتی محیط پروداکشن LATS را اجرا نمی‌کنند؛ بلکه از ReAct به همراه اعتبارسنجی مبتنی بر ابزار استفاده می‌کنند (الگوی CRITIC، درس 05). جستجو عمدتاً در موقعیت‌های خاص و تخصصی به چشم می‌خورد:

• ایجنت‌های کدنویسی که تست‌ها را به‌عنوان تابع ارزش اجرا می‌کنند (مشابه HumanEval).
• ایجنت‌های پژوهش عمیق که چندین مسیر جستار (Query) را بررسی می‌کنند.
• جریان‌های کاریِ متکی به برنامه‌ریزی سنگین در زیرگراف‌های LangGraph.

سیستم AlphaEvolve (درس 11) نقطه‌ی اوج این مسیر در سال 2025 است: جستجوی تکاملی روی کد، برازشِ قابل‌بررسی توسط ماشین، و دستاوردهای پیشگامانه در مرزهای دانش (نخستین بهبود ضرب ماتریسی 4x4 پس از 56 سال).

پیاده‌سازی

فایل code/main.py این موارد را پیاده‌سازی می‌کند:

• یک جستجوی BFS کوچک به سبک ToT روی مسئله‌ای نمادین برای «انتخاب عملگرهای محاسباتی».
• یک حلقه‌ی کوچک و آموزشی LATS MCTS روی همان مسئله (شامل مراحل Select / Expand / Simulate / Backpropagate) همراه با گزینش به روش UCT.
• یک تابع ارزش که امتیاز نمادین را با امتیاز خودارزیاب ترکیب می‌کند.

اجرای آن:

python3 code/main.py

ردگیری محاسبات (Trace) نشان می‌دهد که ToT چگونه در هر گره سه کاندید را با BFS بسط می‌دهد، درحالی‌که LATS از طریق MCTS روی بهترین مسیر پیش‌روی همگرا می‌شود. تعداد توکن‌های مصرفی برای هر دو روش چاپ می‌شود.

کاربرد عملی

فریم‌ورک LangGraph کاوش به سبک ToT را در قالب الگوهای زیرگراف ارائه می‌دهد؛ پست وبلاگ تیم LangChain درباره‌ی LATS (مه 2024) مرجع آموزشی اصلی آن است. فریم‌ورک LlamaIndex نیز ایجنتی با نام TreeOfThoughts دارد. در اکثر ایجنت‌های عملیاتی سال 2026، این الگو پشت یک شرط کنترلی قرار می‌گیرد: if task_complexity > threshold: use_search() — برای بررسی بیشتر، به الگوی evaluator-optimizer در درس 05 مراجعه کنید.

تحویل نهایی

فایل outputs/skill-search-policy.md بر اساس ویژگی‌های مسئله، بودجه و دقتِ ارزیاب، میان روش‌های ReAct خطی، ToT، LATS و جستجوی تکاملی دست به انتخاب می‌زند.

تمرین‌ها

1. مدل آموزشی LATS را با مقادیر c=0.1 و c=2.0 در فرمول UCT اجرا کنید. ردگیری محاسبات چه تغییری می‌کند؟
2. تابع ارزش را با یک امتیازدهنده‌ی پرنویزتر جایگزین کنید (کمی نوسان تصادفی (Jitter) به آن بیفزایید). آیا MCTS باز هم بهترین برگ را پیدا می‌کند؟ حداقل نسبت سیگنال به نویزی که این روش تحمل می‌کند چقدر است؟
3. روش ToT را با جستجوی پرتویی پیاده‌سازی کنید (بهترین k مورد را در هر سطح نگه دارید) و آن را با BFS بسنجید. با یک سهمیه‌ی توکن (Token Budget) محدود، کدام روش بهتر عمل می‌کند؟
4. بخش 5.1 مقاله‌ی LATS را بخوانید. تعداد مسیرهای طی‌شده در HumanEval را بازتولید کنید: رسیدن به pass@1 گزارش‌شده به چند بار پیش‌روی نیاز دارد؟
5. بخش مربوط به «شرایطی که LATS کمک کمتری می‌کند» را در مقاله‌ی LATS بخوانید. یک قاعده‌ی تصمیم‌گیری در قالب یک پاراگراف بنویسید که ویژگی‌های مسئله را به استراتژی جستجوی مناسب نگاشت کند.

اصطلاحات کلیدی

مطالعه‌ی بیشتر

• Yao et al., Tree of Thoughts (arXiv:2305.10601) — مقاله‌ی مرجع
• Zhou et al., LATS (arXiv:2310.04406) — ترکیب MCTS با بازخورد Reflexion
• LangGraph overview — الگوهای زیرگراف برای جستجو
• AlphaEvolve (arXiv:2506.13131) — جستجوی تکاملی همراه با ارزیاب‌های برنامه‌نویسی‌شده