درخت افکار و افکار: جستجو عمدا
Type: Build
Languages: Python (stdlib)
Prerequisites: Phase 14 · 01 (Agent Loop), Phase 14 · 03 (Reflexion)
Time: ~75 minutes
اهداف یادگیری
- استدلال چارچوبی به عنوان جستجو: گره ها "فکر" هستند، حواشی "موسعت" هستند، ارزش "چقدر امیدوار کننده است".
- پیاده سازی یک جستجوی درخت BFS سبک stdlib ToT با امتیاز ارزیابی شخصی.
- به یک حلقه LATS MCTS با انتخاب / گسترش / شبیه سازی / بازگشت باز کنید.
- تصمیم بگیرید که چه زمانی جستجو ارزش ضربات توکن (بازی 24، تولید کد) و چه زمانی یک مسیر واحد کافی است (ساده سوال و پاسخ).
مشکل
زنجیره تفکر یک راه خطی است. اگر اولین قدم اشتباه باشد، هر گام بعدی بر اساس یک پیش فرض بد کار می کند. در بازی 24 (با استفاده از چهار عدد با + − × ÷ برای 24) ، GPT-4 CoT به دقت 4٪ می رسد. مدل زیرعبوری اشتباه را زودتر انتخاب می کند و نمی تواند بازیابی کند.
آنچه به استدلال نیاز دارد توانایی پیشنهاد چند نامزد است، ارزیابی آنها، انتخاب امیدوار کننده ها و عقب نشینی زمانی که مهار افتاده ظاهر می شود. این جستجو است. درخت افکار و LATS دو فرموله قنونی هستند.
مفهوم
درخت افکار (Yao et al., NeurIPS 2023)
هر گره یک مرحله متقابل متماسک ("فکر") است. هر گره می تواند به افکار کودک K گسترش یابد. LLM هر گره را با یک پیام امتیاز خود ارزیابی می کند. جستجو درخت BFS، DFS یا شعاع را کشف می کند.
(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هر سه از CoT را در بازی 24 (4٪ -> 74٪ با GPT-4) به طور قابل توجهی شکست دادند.
LATS (Zhou و همکارانش، ICML 2024)
LATS ToT، ReAct و Reflexion را تحت MCTS متحد می کند. LLM سه نقش را دارد:
- Policy: پیشنهاد اقدام بعدی کاندید (به سبک ReAct).
- Value function: یک مسیر جزئی (توتو-اسلوب خود-بخش) را به دست آورید.
- Self-reflectorدر صورت شکست، یک بازتاب به زبان طبیعی (به سبک بازتاب) بنویسید و از آن برای بازبینی راه اندازی های آینده استفاده کنید.
بازخورد محیط زیست ( مشاهدات) به تابع ارزش ترکیب می شود تا جستجو توسط نتایج واقعی ابزار، نه فقط نظرات مدل مطلع شود. نتایج در زمان کاغذی: HumanEval pass@1 92.7% با GPT-4 (SOTA) ، WebShop متوسط 75.9 با GPT-3.5 (مقرر شدن تنظیمات دقیق مبتنی بر گرادیانت).
MCTS، حداقل
چهار مرحله در هر تکرار:
- Select از ریشه به برگ با استفاده از UCT (تکیه بالا به درختان) قدم بزنید.
- Expand از طریق این سیاست بچه های K را به دنیا بیاورید.
- Simulate از یک کودک با استفاده از سیاست، با عملکرد ارزش (یا پاداش محیط) برسیم کنید.
- Backpropagate تعداد بازدیدها و تخمین های ارزش را به روز کنید.
فرمول UCT: Q(s, a) + c * sqrt(ln N(s) / N(s, a)). اصطلاح اول استحصال ، دومين است اکتشافcبه هر وظیفه
واقعیت هزینه
جستجو توکن ها را منفجر می کند. ToT در بازی 24 از توکن های CoT 1001000x استفاده می کند. LATS مشابه است. این رایگان نیست؛ جستجوی ذخیره برای:
- وظایف که یک مسیر واحد به طور آشکار ناکافی است (بازی 24، کد پیچیده).
- وظایف که ساعت دیواری کمتر از دقت مهم است.
- وظایف با یک تابع ارزشی و قابل اعتماد (تست های واحد برای کد، هدف صریح برای ریاضیات)
اگر وظیفه شما تنها یک پاسخ درست و یک ارزیابی کننده سر و صدا داشته باشد، جستجو اغلب مشکلات را بدتر می کند پاسخ اشتباه "بخش" را پیدا می کند.
موقعیت در سال 2026
اکثر عوامل تولید LATS را اجرا نمی کنند. آنها ReAct را با تأیید مبتنی بر ابزار اجرا می کنند (CRITIC، درس 05). جستجو در طاقچه های تخصصی ظاهر می شود:
- عوامل کوڈنگ که آزمایشات را به عنوان تابع ارزش انجام می دهند (به سبک HumanEval).
- ماموران تحقیق عمیق که مسیرهای جستجو چندگانه را کشف می کنند.
- جریان های کاری سنگین برنامه ریزی در زیرگراف های LangGraph
آلفا ایولو (درسی 11) افراط 2025 است: جستجوی تکاملی در مورد کد، تناسب اندام قابل چک ماشین، پیشرفت های مرزی (اولین بهبود 4x4 در 56 سال)
آن را بسازید
code/main.pyابزار:
- يه BFS کوچک تو تو تو يه کار "تخيار حسابي"
- یک حلقه LATS MCTS بازی در همان کار (انتخاب / گسترش / شبیه سازی / بازگشت) با انتخاب UCT.
- یک تابع ارزش که یک نماد نمادین و یک نماد خود برابر را تشکیل می دهد.
اجرا کن
python3 code/main.pyردیابی نشان می دهد که ToT سه کاندید در هر گره با BFS گسترش می یابد، در مقایسه با LATS که در بهترین راه اندازی از طریق MCTS به هم می پیوندد.
ازش استفاده کن
LangGraph به عنوان الگوهای زیرگراف به عنوان اکتشافات سبک ToT ارسال می کند؛ وبلاگ تیم LangChain در LATS (مائی 2024) آموزش مرجع است. LlamaIndex یک TreeOfThoughtsبراي بيشتر ماموران توليدي 2026 اين الگوي پشت يهif task_complexity > threshold: use_search()دروازه در درس 05 الگوی ارزیابی کننده- بهینه سازی را ببینید.
-باده
outputs/skill-search-policy.mdانتخاب بین ReAct خطی، ToT، LATS و جستجوی تکاملی با توجه به شکل کار، بودجه و وفاداری ارزیابی کننده.
تمرینات
- بازیش رو با UCT c=0.1 در مقابل c=2.0 اجرا کن
- آیا MCTS هنوز بهترین برگ را پیدا می کند؟ حداقل سیگنال به صدا که تحمل می کند چیست؟
- اجرای ToT جستجو شعاع (در هر سطح بالا نگه دارید) و مقایسه با BFS. کدام یک با بودجه تکه تنگ بهتر است؟
- بخش 5.1 LATS را بخوانید. شمارش مسیر HumanEval را تکرار کنید: برای رسیدن به پاس@1 گزارش شده چند بار لازم است؟
- بحث مقاله LATS را در مورد "وقتی LATS کم کمک می کند" بخوانید. یک قانون تصمیم گیری یک پاراگراف را برای نقشه برداری از شکل کار برای استراتژی جستجو بنویسید.
اصطلاحات کلیدی
| Term | What people say | What it actually means |
|---|---|---|
| Tree of Thoughts | "Branching CoT" | Yao et al. — tree of thought nodes with self-evaluation |
| LATS | "MCTS for LLMs" | Zhou et al. — unifies ToT + ReAct + Reflexion under MCTS |
| UCT | "Upper confidence bound" | Select formula balancing exploitation (Q) and exploration (ln N / n) |
| Value function | "How good is this state" | Prompted LLM score or environment reward; feeds backprop |
| Policy | "Action proposer" | ReAct-style generator; emits candidate next thoughts/actions |
| Rollout | "Simulated trajectory" | Walk from a node to a leaf using policy, score with value |
| Backpropagate | "Update ancestors" | Push the leaf's reward up the path, updating visit counts and Q |
| Search cost | "Token explosion" | 100-1000x CoT on Game of 24; budget before you adopt |
خواندن بیشتر
- Yao et al., Tree of Thoughts (arXiv:2305.10601) کاغذی کاینونیکی
- Zhou et al., LATS (arXiv:2310.04406) MCTS با بازتاب بازتاب
- LangGraph overview الگوهای زیرگراف برای جستجو
- AlphaEvolve (arXiv:2506.13131) جستجوی تکاملی با ارزیابی کنندگان برنامه
This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.
Browse the complete course catalog or open this lesson on GitHub.