Skip to main content

fetchium_core/intelligence/
totr.rs

1//! Tree-of-Thoughts Research (ToTR) — PRD §8.12, §32.
2//!
3//! Decomposes a complex query into 2-5 parallel reasoning paths, runs
4//! independent sub-research per path, prunes low-quality branches, and
5//! synthesizes surviving paths.  Optionally runs a self-debate protocol
6//! (Advocate → Critic → Judge).
7//!
8//! **Graceful degradation**: if no LLM is available, uses keyword-based
9//! decomposition rather than AI decomposition.
10
11use std::fmt::Write as FmtWrite;
12
13use crate::error::FetchiumError;
14
15// ─── Configuration ────────────────────────────────────────────────────────────
16
17/// Configuration for the ToTR engine.
18#[derive(Debug, Clone)]
19pub struct TotrConfig {
20    /// Maximum number of reasoning branches (2-5 recommended).
21    pub max_branches: usize,
22    /// Prune branches scoring below `max_score × prune_threshold`.
23    pub prune_threshold: f64,
24    /// Enable the Advocate-Critic-Judge self-debate protocol.
25    pub self_debate: bool,
26}
27
28impl Default for TotrConfig {
29    fn default() -> Self {
30        Self {
31            max_branches: 3,
32            prune_threshold: 0.3,
33            self_debate: false,
34        }
35    }
36}
37
38// ─── Branch types ────────────────────────────────────────────────────────────
39
40/// Status of a reasoning branch.
41#[derive(Debug, Clone, PartialEq, serde::Serialize)]
42#[serde(rename_all = "snake_case")]
43pub enum BranchStatus {
44    Active,
45    Complete,
46    Pruned { reason: String },
47}
48
49/// A single reasoning branch in the tree.
50#[derive(Debug, Clone, serde::Serialize)]
51pub struct ThoughtBranch {
52    pub id: String,
53    /// Named perspective, e.g. "Economic Feasibility".
54    pub perspective: String,
55    /// Sub-queries assigned to this branch.
56    pub sub_queries: Vec<String>,
57    /// Summarised findings (text snippets from research).
58    pub findings: Vec<String>,
59    /// Aggregate evidence quality score 0.0-1.0.
60    pub score: f64,
61    pub status: BranchStatus,
62}
63
64// ─── Result types ─────────────────────────────────────────────────────────────
65
66/// Self-debate output (Advocate → Critic → Judge).
67#[derive(Debug, Clone, serde::Serialize)]
68pub struct DebateResult {
69    pub advocate_argument: String,
70    pub critic_argument: String,
71    pub judge_verdict: String,
72    pub confidence: f64,
73}
74
75/// Complete output of a ToTR run.
76#[derive(Debug, Clone, serde::Serialize)]
77pub struct TotrResult {
78    pub query: String,
79    pub branches: Vec<ThoughtBranch>,
80    /// Cross-path synthesis text.
81    pub synthesis: String,
82    pub debate: Option<DebateResult>,
83    pub total_branches: usize,
84    pub pruned_branches: usize,
85}
86
87impl TotrResult {
88    /// Markdown-formatted report of the ToTR result.
89    pub fn to_markdown(&self) -> String {
90        let mut out = String::new();
91        let _ = writeln!(out, "# Tree-of-Thoughts Research: {}\n", self.query);
92        let _ = writeln!(
93            out,
94            "_Branches: {} total, {} pruned_\n",
95            self.total_branches, self.pruned_branches
96        );
97
98        // Surviving branches
99        for branch in &self.branches {
100            if branch.status != BranchStatus::Complete {
101                continue;
102            }
103            let _ = writeln!(
104                out,
105                "## {} (score: {:.2})\n",
106                branch.perspective, branch.score
107            );
108            for finding in &branch.findings {
109                let _ = writeln!(out, "- {finding}");
110            }
111            out.push('\n');
112        }
113
114        // Pruned branches summary
115        let pruned: Vec<&ThoughtBranch> = self
116            .branches
117            .iter()
118            .filter(|b| matches!(b.status, BranchStatus::Pruned { .. }))
119            .collect();
120        if !pruned.is_empty() {
121            let _ = writeln!(out, "## Pruned Branches\n");
122            for b in pruned {
123                let reason = if let BranchStatus::Pruned { reason } = &b.status {
124                    reason.as_str()
125                } else {
126                    ""
127                };
128                let _ = writeln!(out, "- **{}**: {reason}", b.perspective);
129            }
130            out.push('\n');
131        }
132
133        let _ = writeln!(out, "## Synthesis\n\n{}\n", self.synthesis);
134
135        if let Some(debate) = &self.debate {
136            let _ = writeln!(out, "## Self-Debate\n");
137            let _ = writeln!(out, "**Advocate:**\n{}\n", debate.advocate_argument);
138            let _ = writeln!(out, "**Critic:**\n{}\n", debate.critic_argument);
139            let _ = writeln!(
140                out,
141                "**Judge** (confidence: {:.0}%):\n{}\n",
142                debate.confidence * 100.0,
143                debate.judge_verdict
144            );
145        }
146
147        out
148    }
149}
150
151// ─── Decomposition ────────────────────────────────────────────────────────────
152
153/// Decompose a query into perspectives using keyword heuristics (no LLM required).
154///
155/// Detects comparison/contrast/pros-cons patterns and generates up to
156/// `max_branches` perspectives automatically.
157pub fn decompose_query_heuristic(query: &str, max_branches: usize) -> Vec<(String, Vec<String>)> {
158    let lower = query.to_lowercase();
159    let mut perspectives: Vec<(String, Vec<String>)> = Vec::new();
160
161    // Comparison queries ("A vs B", "difference between X and Y")
162    if lower.contains(" vs ") || lower.contains(" versus ") || lower.contains("compare") {
163        perspectives.push((
164            "Technical Comparison".into(),
165            vec![
166                format!("{query} technical differences"),
167                format!("{query} performance benchmarks"),
168            ],
169        ));
170        perspectives.push((
171            "Use Case Analysis".into(),
172            vec![
173                format!("{query} best use cases"),
174                format!("{query} when to choose each"),
175            ],
176        ));
177        perspectives.push((
178            "Community & Ecosystem".into(),
179            vec![
180                format!("{query} ecosystem libraries"),
181                format!("{query} community size adoption"),
182            ],
183        ));
184    } else if lower.contains("how") || lower.contains("why") || lower.contains("explain") {
185        perspectives.push((
186            "Conceptual Foundation".into(),
187            vec![
188                format!("{query} fundamentals explained"),
189                format!("{query} overview introduction"),
190            ],
191        ));
192        perspectives.push((
193            "Practical Application".into(),
194            vec![
195                format!("{query} practical examples"),
196                format!("{query} real world usage"),
197            ],
198        ));
199        perspectives.push((
200            "Advanced Considerations".into(),
201            vec![
202                format!("{query} edge cases limitations"),
203                format!("{query} best practices"),
204            ],
205        ));
206    } else {
207        // Generic decomposition — extract key noun phrases as sub-topics.
208        let words: Vec<&str> = query.split_whitespace().collect();
209        let chunk_size = (words.len() / max_branches.max(1)).max(1);
210
211        for (i, chunk) in words.chunks(chunk_size).take(max_branches).enumerate() {
212            let sub_topic = chunk.join(" ");
213            perspectives.push((
214                format!("Perspective {}: {sub_topic}", i + 1),
215                vec![
216                    format!("{query} {sub_topic} overview"),
217                    format!("{query} {sub_topic} details"),
218                ],
219            ));
220        }
221    }
222
223    perspectives.truncate(max_branches);
224    perspectives
225}
226
227/// Attempt LLM-based decomposition, falling back to heuristic on any error.
228///
229/// `ai_complete_fn` is an async callback:
230/// ```text
231/// |prompt: String| async { Ok::<String, FetchiumError>(response_text) }
232/// ```
233pub async fn decompose_query<F, Fut>(
234    query: &str,
235    max_branches: usize,
236    ai_complete_fn: F,
237) -> Vec<(String, Vec<String>)>
238where
239    F: Fn(String) -> Fut,
240    Fut: std::future::Future<Output = Result<String, FetchiumError>>,
241{
242    let prompt = format!(
243        "Decompose this research question into {max_branches} distinct perspectives. \
244         For each perspective provide a short name (2-4 words) and 2 specific search queries. \
245         Output ONLY valid JSON: \
246         [{{\"perspective\": \"...\", \"queries\": [\"...\", \"...\"]}}]\n\nQuestion: {query}"
247    );
248
249    match ai_complete_fn(prompt).await {
250        Ok(response) => {
251            // Try to parse JSON response.
252            if let Ok(parsed) = serde_json::from_str::<Vec<serde_json::Value>>(&response) {
253                let mut result = Vec::new();
254                for item in parsed.into_iter().take(max_branches) {
255                    let perspective = item["perspective"]
256                        .as_str()
257                        .unwrap_or("Unknown")
258                        .to_string();
259                    let queries: Vec<String> = item["queries"]
260                        .as_array()
261                        .unwrap_or(&vec![])
262                        .iter()
263                        .filter_map(|q| q.as_str().map(String::from))
264                        .collect();
265                    if !perspective.is_empty() && !queries.is_empty() {
266                        result.push((perspective, queries));
267                    }
268                }
269                if !result.is_empty() {
270                    return result;
271                }
272            }
273            // JSON parse failed — fall through to heuristic.
274            tracing::warn!("ToTR: LLM decomposition JSON parse failed, using heuristic");
275            decompose_query_heuristic(query, max_branches)
276        }
277        Err(e) => {
278            tracing::warn!("ToTR: LLM unavailable ({e}), using heuristic decomposition");
279            decompose_query_heuristic(query, max_branches)
280        }
281    }
282}
283
284// ─── Branch scoring and pruning ───────────────────────────────────────────────
285
286/// Score each branch's findings and prune below `max_score × threshold`.
287pub fn score_and_prune(branches: &mut [ThoughtBranch], threshold: f64) {
288    let max_score = branches
289        .iter()
290        .map(|b| b.score)
291        .fold(f64::NEG_INFINITY, f64::max);
292
293    if max_score <= 0.0 {
294        // All branches scored 0 (no findings yet) — mark them Complete so
295        // synthesize can produce best-effort output from query decomposition.
296        for branch in branches.iter_mut() {
297            if branch.status == BranchStatus::Active {
298                branch.status = BranchStatus::Complete;
299            }
300        }
301        return;
302    }
303
304    let cutoff = max_score * threshold;
305    for branch in branches.iter_mut() {
306        if branch.score < cutoff {
307            branch.status = BranchStatus::Pruned {
308                reason: format!(
309                    "Score {:.2} below cutoff {:.2} (= {:.2} × {:.2})",
310                    branch.score, cutoff, max_score, threshold
311                ),
312            };
313        } else if branch.status == BranchStatus::Active {
314            branch.status = BranchStatus::Complete;
315        }
316    }
317}
318
319// ─── Synthesis ────────────────────────────────────────────────────────────────
320
321/// Synthesise surviving branches into a unified conclusion text.
322pub fn synthesize(branches: &[ThoughtBranch], query: &str) -> String {
323    let survivors: Vec<&ThoughtBranch> = branches
324        .iter()
325        .filter(|b| b.status == BranchStatus::Complete)
326        .collect();
327
328    if survivors.is_empty() {
329        return format!(
330            "No high-quality branches survived pruning for query: \"{query}\". \
331             Consider lowering the prune threshold or providing more sources."
332        );
333    }
334
335    let mut out = format!(
336        "Based on {count} research perspective{s} for \"{query}\":\n\n",
337        count = survivors.len(),
338        s = if survivors.len() == 1 { "" } else { "s" },
339    );
340
341    for branch in &survivors {
342        let _ = write!(
343            out,
344            "**{perspective}** (evidence quality: {score:.0}%): ",
345            perspective = branch.perspective,
346            score = branch.score * 100.0,
347        );
348        if branch.findings.is_empty() {
349            out.push_str("No findings.\n\n");
350        } else {
351            let summary = branch.findings.first().map(String::as_str).unwrap_or("");
352            let _ = writeln!(out, "{summary}\n");
353        }
354    }
355
356    out
357}
358
359// ─── Self-debate ─────────────────────────────────────────────────────────────
360
361/// Run a minimal synchronous self-debate based on available findings.
362/// For a full Advocate-Critic-Judge flow, use `run_totr_with_llm` (async).
363pub fn self_debate_heuristic(branches: &[ThoughtBranch], query: &str) -> DebateResult {
364    let pros: Vec<&str> = branches
365        .iter()
366        .filter(|b| b.status == BranchStatus::Complete && b.score >= 0.5)
367        .flat_map(|b| b.findings.iter().map(String::as_str))
368        .take(3)
369        .collect();
370
371    let cons: Vec<&str> = branches
372        .iter()
373        .filter(|b| b.status == BranchStatus::Complete && b.score < 0.5)
374        .flat_map(|b| b.findings.iter().map(String::as_str))
375        .take(3)
376        .collect();
377
378    let advocate_argument = if pros.is_empty() {
379        format!("Insufficient evidence to advocate for a strong conclusion about {query}.")
380    } else {
381        format!("Evidence in favour: {}", pros.join("; "))
382    };
383
384    let critic_argument = if cons.is_empty() {
385        format!("No significant counterevidence found against the main claim about {query}.")
386    } else {
387        format!("Counterevidence or limitations: {}", cons.join("; "))
388    };
389
390    let confidence = branches
391        .iter()
392        .filter(|b| b.status == BranchStatus::Complete)
393        .map(|b| b.score)
394        .sum::<f64>()
395        / branches
396            .iter()
397            .filter(|b| b.status == BranchStatus::Complete)
398            .count()
399            .max(1) as f64;
400
401    let judge_verdict = format!(
402        "Weighing both sides for \"{query}\": the balance of evidence suggests a nuanced answer \
403         with confidence {:.0}%. Both perspectives are worth considering.",
404        confidence * 100.0
405    );
406
407    DebateResult {
408        advocate_argument,
409        critic_argument,
410        judge_verdict,
411        confidence,
412    }
413}
414
415// ─── Main synchronous entry point ─────────────────────────────────────────────
416
417/// Run ToTR synchronously using heuristic decomposition and caller-supplied findings.
418///
419/// `findings_for_query` maps a sub-query string to a list of text snippets.
420/// Use this for testing or when async is not available.
421pub fn run_totr_sync(
422    query: &str,
423    config: &TotrConfig,
424    findings_for_query: impl Fn(&str) -> Vec<String>,
425) -> TotrResult {
426    let decomposition = decompose_query_heuristic(query, config.max_branches);
427
428    let mut branches: Vec<ThoughtBranch> = decomposition
429        .into_iter()
430        .enumerate()
431        .map(|(i, (perspective, sub_queries))| {
432            let mut all_findings = Vec::new();
433            let mut total_score = 0.0_f64;
434
435            for q in &sub_queries {
436                let f = findings_for_query(q);
437                total_score += if f.is_empty() { 0.0 } else { 0.7 };
438                all_findings.extend(f);
439            }
440
441            let score = if sub_queries.is_empty() {
442                0.0
443            } else {
444                total_score / sub_queries.len() as f64
445            };
446
447            ThoughtBranch {
448                id: format!("branch-{i}"),
449                perspective,
450                sub_queries,
451                findings: all_findings,
452                score,
453                status: BranchStatus::Active,
454            }
455        })
456        .collect();
457
458    let total_branches = branches.len();
459    score_and_prune(&mut branches, config.prune_threshold);
460    let pruned_branches = branches
461        .iter()
462        .filter(|b| matches!(b.status, BranchStatus::Pruned { .. }))
463        .count();
464
465    let synthesis = synthesize(&branches, query);
466
467    let debate = if config.self_debate {
468        Some(self_debate_heuristic(&branches, query))
469    } else {
470        None
471    };
472
473    TotrResult {
474        query: query.to_string(),
475        branches,
476        synthesis,
477        debate,
478        total_branches,
479        pruned_branches,
480    }
481}
482
483#[cfg(test)]
484mod tests {
485    use super::*;
486
487    #[test]
488    fn heuristic_decompose_comparison_query() {
489        let branches = decompose_query_heuristic("Rust vs Go for systems programming", 3);
490        assert!(!branches.is_empty());
491        assert!(branches.len() <= 3);
492        // Should detect the vs pattern
493        let names: Vec<&str> = branches.iter().map(|(n, _)| n.as_str()).collect();
494        assert!(
495            names
496                .iter()
497                .any(|n| n.contains("Comparison") || n.contains("Perspective")),
498            "perspectives={names:?}"
499        );
500    }
501
502    #[test]
503    fn run_totr_sync_produces_result() {
504        let config = TotrConfig::default();
505        let result = run_totr_sync("Rust vs Go", &config, |q| {
506            vec![format!("Finding about {q}")]
507        });
508        assert!(!result.query.is_empty());
509        assert!(!result.synthesis.is_empty());
510        assert!(result.total_branches > 0);
511    }
512
513    #[test]
514    fn pruning_removes_low_score_branches() {
515        let config = TotrConfig {
516            max_branches: 3,
517            prune_threshold: 0.5,
518            self_debate: false,
519        };
520        // Only branches with findings get non-zero scores.
521        // Queries for branch-0 return findings; branches 1,2 return none.
522        let result = run_totr_sync("complex query with technical implications", &config, |q| {
523            if q.contains("Conceptual")
524                || q.contains("Perspective 1")
525                || q.contains("fundamentals")
526                || q.contains("overview")
527            {
528                vec!["A relevant finding".to_string()]
529            } else {
530                vec![]
531            }
532        });
533        // At least one branch should survive
534        assert!(result.pruned_branches < result.total_branches);
535    }
536
537    #[test]
538    fn self_debate_returns_three_parts() {
539        let config = TotrConfig {
540            self_debate: true,
541            ..Default::default()
542        };
543        let result = run_totr_sync("nuclear fusion viability", &config, |q| {
544            vec![format!("evidence: {q}")]
545        });
546        let debate = result.debate.as_ref().expect("debate should be Some");
547        assert!(!debate.advocate_argument.is_empty());
548        assert!(!debate.critic_argument.is_empty());
549        assert!(!debate.judge_verdict.is_empty());
550    }
551
552    #[test]
553    fn to_markdown_contains_query() {
554        let config = TotrConfig::default();
555        let result = run_totr_sync("Rust memory model", &config, |q| {
556            vec![format!("finding about {q}")]
557        });
558        let md = result.to_markdown();
559        assert!(md.contains("Rust memory model"), "md={md}");
560    }
561}