Resampled Thought Trees

Resampled Thought Trees is a CSCI 544 final project for measuring which intermediate states in Tree-of-Thought (ToT) search actually preserve downstream success.

Instead of judging a reasoning tree only by its final answer, this repository logs internal ToT states, resamples search from those states, and estimates whether each node is a dead end, misleading, mixed, critical, or redundant viable. We evaluate this idea on two controlled ToT-style settings:

• Game24: deterministic legal arithmetic move generation with an LLM ranker.
• Crossword-style fill search: dataset-derived candidate fills filtered by crossing constraints with an LLM ranker.

The final result package includes:

• 1,600 Game24 node summaries and 16,000 Game24 resampling trials.
• 792 Game24 branch-ablation rows.
• 387 branch-diverse crossword node summaries and 3,870 crossword resampling trials.
• 248 high-score-path crossword node summaries and 2,480 crossword resampling trials.
• 280 saved tree logs across the final Game24 and crossword runs.

Public repository:

https://github.com/faraazusc/tot-resampled-thought-trees

Repository Structure

data/raw/                         Raw and constructed datasets
data/processed/                   Canonical experiment CSV outputs
docs/                             Progress notes and project documentation
logs/analysis_100p_final/         Game24 final ablation artifact
logs/final_analysis/              Final aggregate tables, figures, and memo
logs/game24_trees_100p_final/     Final Game24 tree logs
logs/crossword_trees_medium_20_*  Final crossword tree logs
notebooks/                        Exploratory notebook work
src/                              Experiment, dataset, and analysis scripts

The most important result manifest is:

logs/final_analysis/final_artifact_manifest.md

Environment Setup

The core analysis scripts use only the Python standard library. Installing requirements.txt adds optional convenience packages used by notebooks or by the faster Ollama HTTP path.

Recommended Python version: Python 3.12.

git clone https://github.com/faraazusc/tot-resampled-thought-trees.git
cd tot-resampled-thought-trees

python3 -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip
python -m pip install -r requirements.txt

Optional Ollama Setup

The full Game24 and crossword experiments use a local Ollama server for LLM ranking. The final reported runs used locally served LLaMA-family models recorded in the output metadata:

• Game24 node resampling: llama3:latest
• Game24 ablation and final crossword runs: llama3.2

Install Ollama from https://ollama.com/download, then run:

ollama pull llama3.2
ollama run llama3.2 "Reply with exactly: hello"

The scripts call Ollama at:

http://localhost:11434/api/chat

If local LLM execution is unavailable, the saved CSVs and logs in this repository are sufficient to review the methodology and regenerate the final analysis tables.

Device Used For Final Runs

The final experiments were run locally on Apple Silicon macOS machines using Ollama.

Primary submission environment:

Operating system: macOS
Architecture: arm64 Apple Silicon
Python: 3.12
LLM serving: Ollama on localhost:11434
Models: llama3:latest and llama3.2, as recorded per experiment

The full Game24 ablation and crossword runs are computationally expensive on a laptop. The final CSV artifacts are included so TA review does not require exact numerical reproduction.

Quick Verification

Run this first to verify the repository and regenerate the final aggregate analysis from the committed artifacts:

python src/final_analysis.py

Expected outputs are written under:

logs/final_analysis/

Important generated files include:

logs/final_analysis/final_analysis_overview.json
logs/final_analysis/final_findings_memo.md
logs/final_analysis/tables/game24_ablation_by_category.csv
logs/final_analysis/tables/game24_success_by_depth.csv
logs/final_analysis/tables/crossword_branch_success_by_depth.csv
logs/final_analysis/tables/crossword_branch_category_by_rank.csv

You can also run a small offline crossword smoke test without Ollama:

python src/crossword_experiment.py \
  --ranker deterministic \
  --num-puzzles 1 \
  --temperatures 0.0 \
  --branch-factor 2 \
  --max-frontier-size 12 \
  --selection-depths 1 4 \
  --max-nodes-per-puzzle 4 \
  --resample-trials 2 \
  --summary-csv tmp_smoke/crossword_summary.csv \
  --trials-csv tmp_smoke/crossword_trials.csv \
  --tree-log-dir tmp_smoke/crossword_trees

This confirms that the crossword parser, candidate generator, tree search, node selection, and resampling pipeline run end to end.

Reproducing The Final Analyses From Saved Results

The final report uses the following canonical files:

data/processed/game24_node_resampling_summary_100p_final.csv
data/processed/game24_node_resampling_trials_100p_final.csv
logs/analysis_100p_final/game24_root_ablation_100p_temps_0_0_0_2_merged.csv
data/processed/crossword_medium_20_summary_branch_diverse.csv
data/processed/crossword_medium_20_trials_branch_diverse.csv
data/processed/crossword_medium_20_summary_full.csv
data/processed/crossword_medium_20_trials_full.csv

To regenerate the final summary tables, figures, qualitative examples, and overview JSON:

python src/final_analysis.py

The script reads the canonical CSVs above and writes:

logs/final_analysis/final_analysis_overview.json
logs/final_analysis/final_artifact_manifest.md
logs/final_analysis/final_findings_memo.md
logs/final_analysis/qualitative_examples.md
logs/final_analysis/tables/
logs/final_analysis/figures/

Small Reproduction Runs

The full experiments are included below for completeness, but they are intentionally large. To inspect the mechanics without waiting for a full reproduction, run smaller versions that write into tmp_smoke/.

Small Game24 resampling run:

python src/game24_batch_experiment.py \
  --num-puzzles 3 \
  --temperatures 0.0 \
  --selection-depths 1 2 \
  --max-depth 3 \
  --branch-factor 4 \
  --max-nodes-per-puzzle 4 \
  --resample-trials 2 \
  --model llama3.2 \
  --summary-csv tmp_smoke/game24_summary.csv \
  --trials-csv tmp_smoke/game24_trials.csv \
  --tree-log-dir tmp_smoke/game24_trees

Small Game24 ablation run:

python src/game24_comprehensive_ablation.py \
  --num-puzzles 2 \
  --temperatures 0.0 \
  --candidate-depths 1 \
  --max-candidates-per-puzzle 2 \
  --node-resample-trials 2 \
  --baseline-trials 2 \
  --ablation-trials 2 \
  --model llama3.2 \
  --output-csv tmp_smoke/game24_ablation.csv

Small crossword run without Ollama:

python src/crossword_experiment.py \
  --ranker deterministic \
  --num-puzzles 1 \
  --temperatures 0.0 \
  --branch-factor 2 \
  --max-frontier-size 12 \
  --selection-depths 1 4 \
  --max-nodes-per-puzzle 4 \
  --resample-trials 2 \
  --summary-csv tmp_smoke/crossword_summary.csv \
  --trials-csv tmp_smoke/crossword_trials.csv \
  --tree-log-dir tmp_smoke/crossword_trees

The Game24 smoke commands still require Ollama because the Game24 ranker is LLM-based. The crossword smoke command can run fully offline with the deterministic ranker.

Running The Expensive Experiments

The commands below reproduce the final experiment configurations. They require Ollama and may take many hours on a laptop. Numerical values may vary slightly because LLM ranking can be stochastic and local model versions can differ.

In our local Apple Silicon/Ollama setup, the final Game24 node-resampling run logged about 1,868 minutes of wall-clock time, roughly 31 hours, for the 100-puzzle two-temperature configuration. The final crossword high-score-path run took about 289 minutes, and the branch-diverse crossword run took about 366 minutes. The comprehensive Game24 ablation also required long chunked runs and crash recovery. For review, the committed CSV and JSON artifacts should be treated as the canonical evidence package; the small commands above are the practical reproduction path.

The caffeinate -dimsu prefix is macOS-only and only prevents the laptop from sleeping during long runs. On Linux, Windows, or a managed server, remove that prefix and run the python ... command directly.

Game24 Node Resampling

caffeinate -dimsu python src/game24_batch_experiment.py \
  --num-puzzles 100 \
  --puzzle-offset 0 \
  --temperatures 0.0 0.2 \
  --selection-depths 1 2 \
  --max-depth 3 \
  --branch-factor 4 \
  --max-nodes-per-puzzle 8 \
  --resample-trials 10 \
  --model llama3:latest \
  --request-timeout 90 \
  --summary-csv data/processed/game24_node_resampling_summary_100p_final.csv \
  --trials-csv data/processed/game24_node_resampling_trials_100p_final.csv \
  --tree-log-dir logs/game24_trees_100p_final

Game24 Comprehensive Branch Ablation

caffeinate -dimsu python src/game24_comprehensive_ablation.py \
  --num-puzzles 100 \
  --puzzle-offset 0 \
  --temperatures 0.0 0.2 \
  --candidate-depths 1 \
  --node-resample-trials 10 \
  --baseline-trials 10 \
  --ablation-trials 10 \
  --model llama3.2 \
  --request-timeout 300 \
  --output-csv logs/analysis_100p_final/game24_root_ablation_100p_temps_0_0_0_2_merged.csv

The ablation evidence is strongest for depth-1 Game24 branches because --candidate-depths 1 was used.

Build Crossword Datasets

The raw Tree-of-Thought mini-crossword material is in:

data/raw/tot_mini0505_0_100_5_raw.json

Convert it into the smaller ToT mini-crossword JSON:

python src/convert_tot_mini_crosswords.py \
  --input data/raw/tot_mini0505_0_100_5_raw.json \
  --output data/raw/crosswords_tot_mini.json

Build the expanded 20-puzzle medium crossword benchmark from the original ToT raw file:

python src/build_medium_crosswords_from_tot.py \
  --input data/raw/tot_mini0505_0_100_5_raw.json \
  --output data/raw/crosswords_medium_20.json \
  --num-puzzles 20

Crossword High-Score-Path Run

caffeinate -dimsu python src/crossword_experiment.py \
  --puzzle-path data/raw/crosswords_medium_20.json \
  --ranker ollama \
  --num-puzzles 20 \
  --temperatures 0.0 0.2 \
  --branch-factor 4 \
  --max-frontier-size 256 \
  --selection-depths 4 8 12 16 20 24 28 32 36 \
  --max-nodes-per-puzzle 12 \
  --resample-trials 10 \
  --model llama3.2 \
  --request-timeout 300 \
  --summary-csv data/processed/crossword_medium_20_summary_full.csv \
  --trials-csv data/processed/crossword_medium_20_trials_full.csv \
  --tree-log-dir logs/crossword_trees_medium_20_full

Crossword Branch-Diverse Run

caffeinate -dimsu python src/crossword_experiment.py \
  --puzzle-path data/raw/crosswords_medium_20.json \
  --ranker ollama \
  --num-puzzles 20 \
  --temperatures 0.0 0.2 \
  --branch-factor 4 \
  --max-frontier-size 256 \
  --selection-depths 1 4 8 12 16 20 24 28 32 36 \
  --max-nodes-per-puzzle 12 \
  --diversify-branch-rank \
  --include-terminal-dead-nodes \
  --resample-trials 10 \
  --model llama3.2 \
  --request-timeout 300 \
  --summary-csv data/processed/crossword_medium_20_summary_branch_diverse.csv \
  --trials-csv data/processed/crossword_medium_20_trials_branch_diverse.csv \
  --tree-log-dir logs/crossword_trees_medium_20_branch_diverse

The branch-diverse run intentionally samples across branch ranks and includes terminal dead nodes. It is designed to expose useful, useless, and misleading thoughts; its category counts should not be interpreted as the natural frequency of all visited nodes.

How Results Are Generated

The pipeline is:

1. Generate legal candidate thoughts outside the model.
2. Use an Ollama-served LLM to rank candidate children.
3. Expand a ToT-style search tree and save every node.
4. Select internal nodes for resampling.
5. Restart search from each selected node multiple times.
6. Estimate empirical downstream success:

node_success_rate = successful_resampling_trials / total_resampling_trials

7. Assign each node to an operational category:

dead_end           success_rate <= 0.05
misleading         branch_rank <= 2 and success_rate <= 0.25, after dead ends
redundant_viable   success_rate >= 0.75 and mean_successful_leaves > 1.5
critical           success_rate >= 0.75, after redundant viable
mixed              everything else

8. For Game24 ablation, block a selected depth-1 branch and compare baseline search to ablated search using:

solve_rate_drop       = baseline_solve_rate - ablated_solve_rate
successful_leaf_drop  = baseline_successful_leaves - ablated_successful_leaves

Positive drops mean the branch was useful. Negative drops mean removing the branch helped or preserved search.

Key Findings Encoded In The Results

• Game24 nodes are strongly polarized into dead-end, critical, and redundant-viable states.
• Game24 depth-1 states have much higher average downstream success than depth-2 states.
• Local branch rank alone is not a reliable global utility proxy.
• Game24 ablation validates the node taxonomy: dead-end removal often helps, while critical and redundant-viable removal hurts solve rate or successful-leaf mass.
• Crossword search has a different geometry: wrong early fills often die immediately, while selected deeper surviving states become more reliable as crossing constraints accumulate and remaining search shrinks.
• Crossword runs contain no redundant-viable nodes under our thresholds, suggesting a narrower solution geometry than Game24.
• Temperature acts as an instability probe: mixed and misleading nodes appear under mild stochasticity.

Notes For TA Review

• The final numerical results are already committed as CSV and JSON artifacts.
• python src/final_analysis.py is the fastest way to regenerate the report-facing tables and figures from those artifacts.
• Full reruns require Ollama and can take many hours, especially Game24 ablation and crossword branch-diverse search.
• Exact numerical reproduction is not required for code review because local model versions and stochastic ranking can differ.
• The implementation aligns with the report methodology: controlled candidate generation, LLM ranking, tree logging, node-level resampling, operational node categories, and Game24 branch ablation.