4 papers
On the Ability of Transformers to Verify Plans
Yash Sarrof, Yupei Du, Katharina Stein +3
Transformers have shown inconsistent success in AI planning tasks, and theoretical understanding of when generalization should be expected has been limited. We take important steps…
Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
Oliver Kraus, Yash Sarrof, Yuekun Yao +2
Chain-of-Thought (CoT) has been shown to empirically improve Transformers' performance, and theoretically increase their expressivity to Turing completeness. However, whether Trans…
A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems
Alex Duchnowski, Ellie Pavlick, Alexander Koller
To investigate the effect of problem presentation on LLMs' ability to solve optimization problems, we introduce the dataset of Everyday Hard Optimization Problems (EHOP), a collect…
Collaborative Problem-Solving in an Optimization Game
Isidora Jeknic, Alex Duchnowski, Alexander Koller
Dialogue agents that support human users in solving complex tasks have received much attention recently. Many such tasks are NP-hard optimization problems that require careful coll…