Lecture 8: Neural and Symbolic Decision Making

What this lecture covers

This lecture, given by a research scientist director at Meta AI, examines why large language models struggle at planning and reasoning tasks, and surveys approaches to make them better. It opens with evidence that even strong models like GPT-4 Turbo and o1-preview perform poorly on realistic planning problems such as multi-city travel itineraries, with pass rates dropping toward zero as problem complexity increases, regardless of how recent the model is.

The lecture organizes solutions into three categories: scaling up models and compute; building hybrid systems that combine neural networks with combinatorial or symbolic solvers; and investigating whether neural networks trained by gradient descent naturally discover symbolic structure on their own. After watching, you should understand why planning is hard for LLMs, several concrete ways to combine language models with solvers, and evidence that trained neural networks can converge on interpretable algebraic solutions.

Key ideas

• LLMs are weak planners: on the travel-planning benchmark discussed, GPT-4 Turbo achieved roughly 0.6% pass rate on full itineraries, and performance for state-of-the-art models still collapses to near zero as the number of variables (cities, people) grows.
• Hybrid systems (LLM + solver): combining a language model, which understands natural language but plans poorly, with a symbolic or combinatorial solver, which plans well but doesn't understand language, by having the model translate requests into a structured format a solver can optimize.
• Agent constitution (APAC): a set of behavioral principles - accurate, proactive, efficient, credible - used to fine-tune a multi-round dialogue travel agent with DPO.
• Search-augmented models (Searchformer): training a model to first predict a solver's search trace (e.g. A* search steps) and then the final plan, which is far more parameter- and data-efficient than predicting the plan directly.
• **Bootstrapping shorter traces (Beyond A*)**: iteratively sampling a search-augmented model, keeping the shortest traces that still reach optimal plans, and retraining on them, which shrinks trace length while preserving or improving optimality.
• Dualformer: a follow-up model trained on traces with randomly dropped detail levels, which learns to switch automatically between a fast "system 1" mode and a slow "system 2" search mode.
• End-to-end differentiable solvers: learning a surrogate cost function that maps a problem description to solver inputs, then backpropagating through the solver to optimize placement/design problems like GPU table placement and photonic device design.
• Emergent symbolic representations: evidence that a small network trained on modular addition converges to a Fourier-basis representation that can be derived algebraically via a semiring/ring-homomorphism structure, without gradient descent.

Walkthrough

LLMs fail at realistic planning (2:02)

Using a travel-planning benchmark, the lecture shows that even GPT-4 Turbo, and later o1-preview and o1, achieve very low pass rates on generating itineraries that satisfy stated constraints (budget, room type, etc.), and that performance drops toward zero as the number of cities or people in the problem increases. This trend holds even for the newest models, suggesting the problem isn't simply solved by using a more recent model.

Three paths forward (9:11)

The lecture frames three broad solution categories: scaling up data, compute, and model size; building hybrid systems that pair neural networks with combinatorial or symbolic solvers, which are fast, don't need GPUs, and give optimality guarantees but can't parse natural language; and investigating whether trained networks spontaneously discover symbolic structure.

Combining LLMs with solvers on the travel task (11:11)

A follow-up to the travel-planning work has the LLM convert a natural-language request into a JSON specification, which is then fed to a mixed-integer linear programming solver to produce an optimal itinerary, which is converted back to text. This runs in under three seconds end to end and scored well in human evaluation. The lecture then extends this to multi-round dialogue, where an agent proactively asks clarifying questions, fine-tuned with DPO against an "APAC" constitution (accurate, proactive, efficient, credible) across 50 simulated traveler personas.

Learning to imitate and improve on search (20:14)

Searchformer trains a transformer to predict a solver's full search trace (such as A* exploring a maze) before predicting the final plan, rather than predicting the plan directly. This search-augmented approach reaches much higher accuracy with far fewer parameters and training examples than predicting plans alone, shown on maze navigation and the Sokoban puzzle game. A follow-up bootstrapping procedure repeatedly samples the model, keeps the shortest traces that still yield optimal plans, and retrains on them, progressively shrinking trace length while maintaining or improving optimality.

Dualformer and adaptive fast/slow reasoning (32:22)

Dualformer trains on traces with randomly dropped levels of search detail, from full traces down to solution-only data. The resulting model automatically learns to switch between a fast, direct-answer mode and a slow, search-then-answer mode depending on the problem, without explicit labels for which mode to use, and can also be forced into either mode by controlling its first output token. The same trace-dropping idea is shown to shorten reasoning chains and slightly improve accuracy on math problems.

End-to-end differentiable solvers for real-world design (41:27)

For problems with nonlinear objectives and combinatorial constraints, such as placing GPU workload tables onto devices under memory limits, or designing nanometer-scale photonic structures that bend light by wavelength, the lecture describes learning a surrogate cost function from a problem description, feeding it to a combinatorial solver, and backpropagating through the whole pipeline to learn the best surrogate coefficients. Variants that cache a learned mapping versus optimize at test time trade off solution quality against deployment speed, and outperform heuristic and reinforcement-learning baselines on both.

Do neural networks converge to symbolic solutions? (54:34)

The lecture closes by examining a simple modular addition task, where trained networks are known to develop Fourier-basis representations. Using a two-layer network and Fourier analysis, the lecture shows that gradient-descent solutions can be reconstructed algebraically from partial solutions combined through a semiring structure (a form of ring homomorphism), without running gradient descent at all. Comparing constructed solutions to actual trained networks shows a close match, suggesting neural networks may be converging on identifiable symbolic structure that could, in principle, be built directly rather than discovered through training.

Before you watch

• Basic familiarity with how neural networks are trained (gradient descent, loss functions) is assumed.
• Some exposure to search algorithms like A* and to reinforcement-learning-style fine-tuning (e.g. DPO) will help with the middle sections.

Check your understanding

1. What evidence does the lecture give that planning performance doesn't reliably improve just because a newer model is used?
2. How does the hybrid LLM-plus-solver approach to travel planning divide labor between the language model and the solver?
3. Why is a search-augmented model like Searchformer more data- and parameter-efficient than a model trained to predict plans directly?
4. What does Dualformer learn to do differently from a model trained only on full search traces or only on final solutions?
5. What does it mean for the constructed algebraic solutions to "match" the gradient-descent solutions in the modular addition experiment, and why is that finding notable?