NeurIPS 2023 Recap, Part 3 of 4: Search, Tools, Agent Memory, and Attention Alternatives

Tree of Thoughts: search over steps you can evaluate

Combining numbers to reach 24 requires exploring arithmetic choices. Yet a model generating tokens from left to right can commit to a dead end before it knows whether the calculation will work. This part of the NeurIPS 2023 recap opens with reported GPT-4 performance of just 4% given task instructions and a few chain-of-thought examples—examples that spell out intermediate reasoning. The evaluation set and scoring details are unspecified, but the proposed failure mechanism is concrete: local token decisions provide no explicit lookahead or backtracking.

A maze analogy makes the distinction clear. A robot trained to imitate the next move in successful trajectories may still fail in a new maze requiring exploration. Search provides a way to explore alternatives, but language makes its design difficult: a move could be a token, sentence, or paragraph, rather than one of a constrained set of legal chess moves.

Tree of Thoughts uses intermediate reasoning steps as search moves. Choosing their size creates a generation–evaluation tradeoff: - Tokens are easy to generate but hard to judge. An initial number or operator reveals little about eventual success. - Complete solutions are easy to check but hard to generate. Checking whether an answer equals 24 does not help construct it. - Intermediate steps balance the two. Combining two remaining numbers produces a state whose continuations can be explored.

For each proposed combination, the model tries continuations and estimates the state's promise. The presenter illustrates a heuristic assigning high value when three trials find 24, medium value when attempts reach nearby numbers such as 25 or 26, and low value to less promising outcomes. The estimate need only guide search usefully, not perfectly predict success. A tree-search algorithm maintains alternatives while GPT-4 generates and evaluates moves. The presenter reports substantial improvements across diverse tasks without training a new model, but gives no task-level figures here.

Prompt design depends on the work performed at each step: - Repeated step types can share prompts. Games that repeatedly require an equation or clue can reuse one generation prompt and one evaluation prompt, without a separate planning stage. - Different step types may need advance planning. More complex tasks may require distinct prompts for different kinds of generation and evaluation.

For creative writing, the evaluator compares candidate plans against the instructions and votes for a plan ID. Repeated voting applies self-consistency to plan selection: aggregate several judgments to reduce dependence on one noisy vote. Ten or a hundred votes are suggested settings that exchange additional spending for potentially more reliable evaluation; no measured gains are given. The conversation closes with the presenter crediting cognitive-science collaborators at Princeton for bringing classical-search ideas into natural language processing research.

Toolformer: learn from calls whose results improve prediction

Toolformer learns which external tool to call, when to call it, and what inputs to supply, without human annotation of the training corpus. Its five tools provide up-to-date question answering, Wikipedia search, calculation, the current date and weekday, and translation into English. The approach inserts tool calls into a language-modeling corpus, then fine-tunes GPT-J on the augmented text. Starting with a familiar corpus such as CCNet is intended to limit disruption to existing language-modeling capabilities.

For text identifying Pittsburgh as the Steel City, asking a question-answering tool for Pittsburgh's other name helps predict the continuation. Asking which state Pittsburgh is in may return a valid answer without helping that prediction. Validity alone does not make a useful training example. Calls appear inline, with brackets enclosing a tool name, parenthesized input, and an arrow followed by the output. The returned information then becomes context for subsequent text.

Training-data generation follows three stages: 1. Propose calls. Instructions and examples prompt the model to insert calls that could help complete the text. 2. Execute calls. Parse the arguments, dispatch them to the appropriate tool, and insert its output. 3. Filter calls. Remove malformed calls, calls with no result, and calls whose results fail to improve prediction of the remaining text.

Filtering compares prediction under three contexts: no call, a call without its result, and the fully executed call. The usefulness score subtracts the executed-call score from the better of the two baselines. The result must help beyond merely including the question. The presentation calls this prediction metric perplexity while describing it as negative log likelihood, leaving its exact definition and normalization uncertain; lower scores are treated as better predictions.

A calendar result saying that today is Thursday, March 9 helps complete a reference to Friday as March 10. Conversely, a calculator call proposing a ratio from “85 patients” and “23 percent” does not help complete its surrounding text. The presentation compares filtering thresholds of 0.5 and 1.0; the lower threshold retains more examples. Wikipedia search supplies the most retained examples, calculator and translation the fewest. The final mixture caps each tool at 25,000 examples.

Evaluation covers fact completion, question answering, arithmetic, multilingual questions with English context, and date-dependent questions—tasks chosen because an available tool should help. The presenter reports that Toolformer outperforms its base model and a 175-billion-parameter comparator in almost all displayed cases despite being approximately 30 times smaller than the latter. Individual benchmark scores are not given. Two conditions qualify the comparison: - The question-answering tool is disabled for that evaluation. Its training data overlaps substantially with the evaluation tasks. - Translation provides little additional benefit. The proposed explanation is that the base model already encountered substantial multilingual text; Toolformer nevertheless remains on par with or ahead of the base model.

A five-size experiment compares tool-enabled models with the same models prevented from emitting calls through constrained decoding. The two smallest sizes show no benefit; a gap appears at larger sizes, with a similar pattern on math and a less distinct pattern on question answering. Tool access still requires the capacity to use it. Finally, held-out WikiText and CCNet evaluations show approximately equal perplexity for the base model, a CCNet-fine-tuned control, and Toolformer, supporting preservation of language modeling under those tests.

Voyager: preserve successful programs as reusable skills

Voyager combines reasoning, executable actions, and persistent experience in a Minecraft agent. Guanzhi Wang presents it as playing for hours without human intervention, exploring terrain, gathering materials, and acquiring skills. Its interface makes this possible for a text model: Mineflayer's high-level JavaScript API exposes nearby blocks, animals, enemies, and other game state as text. GPT-4 receives those observations and writes programs to act in the world.

Three components sustain the agent's work: - A coding module generates and revises actions. It writes JavaScript using supplied Mineflayer documentation and examples. - A skill library stores successful programs. The agent can retrieve working code instead of recreating it. - An automatic curriculum chooses tasks. A separate GPT-4 instance proposes work suited to current capabilities, aiming to maximize newly obtained items.

Program revision uses environment feedback, JavaScript errors, and critiques from another GPT-4 instance. The critic ties completion to observed state. Insufficient amethyst blocks a spyglass task; two units of white wool indicate another sheep remains in a three-sheep task; rotten flesh is treated as evidence of a zombie kill. Critique and refinement continue until the task is deemed successful or reaches a time limit.

The library separates how a skill is found from how it executes. GPT-3.5 summarizes each successful program in English. A vector representation, or embedding, of that description becomes the database key; the program is its value. Wang reports better retrieval from descriptions than raw code, with GPT-3.5 reducing summarization cost. For a new task, a generated solution hint and the world state form the retrieval query. Voyager retrieves five relevant skills and can reuse them directly, combine them, or write fresh code.

In the hunger example, the agent has one hunger point out of twenty and observes a cat, villager, pig, and wheat seed. Farming would take too long, so it selects the pig, retrieves an iron-sword crafting skill, and begins learning a hunting skill. Wang calls the library an in-context replay buffer: retrieved programs bring successful past work into the current task. The curriculum similarly implements curiosity-driven exploration through prompting. Both support learning through experience without updating model parameters.

Evaluation measures unique items against prompting iterations, comparing GPT-4-based implementations of ReAct, Reflexion, and AutoGPT without parameter training. Voyager reportedly progresses faster through wooden, stone, iron, and diamond technology and obtains roughly three times as many novel items as a prior method. It also reportedly travels twice as far under the same prompting-iteration budget. The specific comparator behind each multiplier, trial counts, and uncertainty estimates are unspecified. An ablation provides a more direct architectural result: without the skill library, progress plateaus.

The implementation presented lacks visual perception. A separate house-and-nether-portal demonstration replaces the critic with human feedback, so its building results have a different autonomy condition from the exploration runs. Multimodal construction remains future work in this 2023 account. The presentation closes by announcing release of the environment, algorithm, prompts, and pretrained skill libraries.

CogEval: knowing individual edges does not establish planning

CogEval, introduced in the recap through Ida Momennejad's poster presentation, tests whether apparent planning ability survives changes in task and environment. Its cognitive-science-inspired protocol defines an underlying ability through multiple measurable tasks and separates that ability from factors that could confound the measurement. The evaluation spans six graph structures and fifteen tasks in five categories. Success on an easy instance is insufficient evidence of a general capacity.

The graphs describe either spatial relationships, such as rooms joined by doors, or social relationships, such as friends passing a message. The question is whether a model extracts a cognitive map—a representation of environmental relationships usable for flexible planning. The presenter connects this to Edward Tolman's 1948 review, “Cognitive Maps in Rats and Men,” describing evidence that rats could learn environmental structure without rewards. Here, flexibility means incorporating changes such as a moved reward or a changed connection.

One value-based task starts in a lobby. The route through rooms 1 → 3 → 5 leads to $10; 2 → 4 → 6 leads to $50. With only one opportunity to collect money, the correct initial choice is room 2. Follow-up prompts change a reward or door connection, testing whether the model can revise its plan rather than repeat the original route.

The reported results show two consequential sensitivities: - Structure matters beyond graph size. GPT-4 performs near perfectly on an easy graph, but modest changes in branching or path length sharply reduce performance. A smaller graph can be harder when a valid route must pass through a bottleneck with no alternative path. - Local changes disrupt planning. Traversal with fixed structure and rewards is easier than tasks introducing detours or shortcuts. Cohere, Alpaca, and Llama are described as falling to zero in the displayed local-change results.

The failure examples distinguish three ways a route can go wrong: - Invented connectivity: the route uses an edge that does not exist. - Missed shortest path: the model returns 1 → 13 → 10 → 7 despite a direct edge from 1 to 7. - Unnecessary revisiting: a purported shortest path contains a loop. GPT-4 can correctly list individual edge tuples and still fail when composing a path. The presenter's diagnosis is a failure to stitch one-step relationships into valid multistep plans, consistent with the lack of robustness across tasks and graphs.

An audience member suggests that the easier cases resemble transitive commonsense benchmarks encountered during training. The presenter rejects that explanation, arguing that tree-like structures also occur in training text. She contrasts the models' bottleneck difficulties with a human planning heuristic: first reach a central subway transfer hub, then plan onward. A bottleneck can simplify the human plan even when it makes exact routing harder for the evaluated models.

Search instructions offer limited help in the tested settings. The models already received a step-by-step reasoning prompt. Describing breadth-first and depth-first search improves some paths within clusters, but helps little on shortest paths between clusters: no improvement at temperature zero in the discussed comparison, and a little at higher temperatures. The discussion closes with separate work on a prefrontal-cortex-inspired architecture that assigns GPT-4 different module roles; no quantitative results for that architecture are presented here.

S4: compute one state-space system as recurrence or convolution

Chris Ré turns from agent architectures to the operators inside sequence models. Audio, DNA, and contexts containing many examples motivate efficient processing of long sequences. He presents three complementary directions: - Improve hardware utilization, as in FlashAttention. - Approximate attention to change its computational demands. - Develop new operators using recurrent-network and signal-processing ideas.

His deeper motivation concerns spatial inductive bias: how much built-in spatial structure does a machine need to recognize an image? Sequential CIFAR poses image classification over flattened pixels. Ré points to the 2021 Long Range Arena (LRA) leaderboard, where sequential image classification lagged conventional image classification and the displayed models effectively guessed on PathX, a task asking whether two marked dots in a large image are connected.

S4 replaces the signal-mixing operator with a state-space system adapted from signal processing. Ré describes it as a linear time-invariant system and reports that the approach first solved PathX, with roughly a 26-point improvement on LRA. The image results also led him to question how much explicit spatial structure was necessary.

The starting system takes a scalar input, maintains a higher-dimensional hidden state, and projects that state to a scalar output. Learned matrices A and B govern state evolution through an ordinary differential equation. Treating a signal as continuous and then sampling it enables both continuous analysis and discrete computation. Solving the state equation yields a convolution-style integral; discretizing that solution connects two execution forms.

The same weights support both forms: - Recurrence updates the hidden state using the previous state and current input. - Convolution applies a filter that can span the full input sequence, rather than a small local neighborhood. This connects recurrent and convolutional neural-network formulations. The proposed sequence-processing cost is O(N log N) for sequence length N, but turning that asymptotic advantage into practical speed requires further engineering.

Signal processing supplies bounded-input, bounded-output stability: bounded inputs should not make outputs grow without bound. Ré describes constraining the state matrix's eigenvalues to the left half of the complex plane so their exponentials fall inside the unit disk, then preserving that condition during training. Diagonal matrices make the constraint easy to maintain. More expressive matrix classes make matrix exponentials harder to compute, creating a tradeoff among expressiveness, stability, and efficiency.

Avoiding large intermediate states and excessive memory movement makes the speed practical. The implementation need not materialize the high-dimensional hidden state at every time step. Long convolutions also require careful handling of fast Fourier transform operations: naïve implementations have poor memory behavior, while grouping operations around input/output costs improves utilization. Ré reports utilization approaching FlashAttention's, without specifying the hardware, workload, or utilization metric here. He credits S5, Mega, and RWKV among the contributions to renewed interest in recurrent models.

Associative recall: successful lookup can hide a capacity cost

Strong long-sequence results did not initially carry over to language. Ré reports that S4 was five perplexity points worse than transformers in the comparison motivating this investigation. Perplexity measures how well a model predicts text; the dataset and detailed comparison conditions are unspecified here. To probe the gap, researchers use associative recall: a sequence supplies letter–number associations, and a final query letter asks for its associated number. Attention handles this lookup readily, while two later S4 variants improve but still leave a gap.

Hyena reportedly reaches 100% on the particular associative-recall task under discussion while retaining speed, although sequence lengths, training conditions, and speed measurements are not given. Ré also describes successive alternatives approaching a strong attention baseline in comparisons at 350 million parameters. The baselines were released, with credit to Eleuther for an evaluation harness. These gains motivate a sharper test: require many lookups rather than one.

Multi-query associative recall (MQAR) extends the task to many queried letters, allowing comparisons across vocabulary size, sequence length, and model dimension. All the compared models can solve the task, but Ré reports different capacity requirements: - Attention needs roughly logarithmic model dimension in the discussed scaling comparison. - Hyena, RWKV, and the convolutional models covered by the reduction need dimensions that grow with sequence length. Task success therefore conceals a consequential distinction: how much capacity is needed as the task grows.

The closing experiment asks whether this synthetic lookup problem reflects language-model behavior. Researchers partition the Pile using repeated bigrams as a rough proxy for associative recall. A second occurrence of “common buzzard,” for example, offers an implicit lookup opportunity. That slice reportedly accounts for about 7% of the corpus; the remaining text forms the comparison slice.

Ré reports that this rough repeated-bigram analysis explains 82% of the attention gap. Part 3 ends mid-explanation, before the gap's metric and full comparison conditions are specified. The closing question is thus where the aggregate difference comes from: a relatively small slice of text may expose the lookup behavior that separates otherwise competitive sequence models.