Reproduce “Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari
A formal theoretical model for test-time computation in Large Language Models is introduced, viewing inference as an algorithm interacting with a rewinding Markov chain. The derived "Caterpillar of Thoughts" (CaT) algorithm improves success rates on reasoning tasks, achieving 81% for Game of 24 (compared to 74% for ToT) and reducing token costs by over 20% while solving more 5x5 Crosswords.
Key insights
- The optimal test-time algorithm for LLMs with rewinding capability generates a "caterpillar" tree structure, implying that only a limited form of backtracking along a central path is theoretically necessary.
- Rewinding can offer exponential efficiency gains in terms of expected steps to reach a target state compared to non-backtracking methods.
- Even with noisy approximations of optimal hitting times (e.g., via Laplacian noise), robust algorithms can achieve target states efficiently, but adversarial noise can render approximation strategies exponentially complex.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.