Reproduce “Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity” 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
Debanjan Dutta, Anish Chakrabarty, Swagatam Das
This research provides concrete Chain of Thought (CoT) realizations for fundamental graph algorithms, including Depth-First Search and Dijkstra's algorithm, and for computing branching complexity measures like the Strahler number and tree width. The study details Transformer decoder architectures with unique hard-attention, demonstrating these capabilities in minimal fixed steps without relying on positional encodings or layer normalization.
Key insights
- CoT allows hard-attention Transformers to provide concrete, implementable architectures for problems in higher complexity classes, exemplified by the NC1-complete Strahler number computation.
- Transformer attention can offer computational advantages, such as selecting the minimum-distance unvisited vertex in Dijkstra's algorithm with constant-time attention, replacing explicit search operations.
- CoT realizability for derived quantities does not always trivially transfer across bijective representations, often requiring different architectural mechanisms or layer counts when switching between tree and Dyck path inputs.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.