PaperlayerView exact revision on arXiv

Source-linked AI summary

Loose LIPS Sink Ships: Asking Questions in Battleship with Language-Informed Program Sampling

Gabriel Grand, Valerio Pepe, Jacob Andreas, Joshua B. Tenenbaum

arXiv:2402.19471v2cs.CLcs.AI

TL;DR

The paper studies how people ask informative questions in grounded settings while searching large hypothesis spaces with limited cognitive resources. It introduces LIPS, which uses LLMs to generate questions and translate them into programs for information-gain evaluation. With modest sampling, LLM priors approach or exceed mean human informativity, though top human questions remain stronger and grounding is imperfect.

  • Problem

    How people efficiently generate informative questions from vast hypothesis spaces under cognitive resource constraints remains an open question.

    Source: Introduction · p. 1

  • Method

    LIPS samples natural-language questions from an LLM prior, translates them into programs, and selects candidates by simulated Expected Information Gain.

    Source: Introduction · p. 1

  • Results

    At k = 5, both LLMs approached human mean performance; at k = 10, both significantly outperformed the human mean, though top human questions outperformed top model-generated questions.

    Source: Informativity · p. 6, Sample efficiency · p. 6

  • Takeaways & Limitations

    LLM priors can capture human-like question distributions in a Bayesian model, while generated questions still show grounding shortcomings.

    Source: Question type · p. 6, Groundedness · p. 6

    The PCFG is treated as an unconditional prior because a board-conditional model would require many thousands of labeled board-question pairs.

    Source: Grammar proposal distribution · p. 3

Abstract

from arXiv · show

Questions combine our mastery of language with our remarkable facility for reasoning about uncertainty. How do people navigate vast hypothesis spaces to pose informative questions given limited cognitive resources? We study these tradeoffs in a classic grounded question-asking task based on the board game Battleship. Our language-informed program sampling (LIPS) model uses large language models (LLMs) to generate natural language questions, translate them into symbolic programs, and evaluate their expected information gain. We find that with a surprisingly modest resource budget, this simple Monte Carlo optimization strategy yields informative questions that mirror human performance across varied Battleship board scenarios. In contrast, LLM-only baselines struggle to ground questions in the board state; notably, GPT-4V provides no improvement over non-visual baselines. Our results illustrate how Bayesian models of question-asking can leverage the statistics of language to capture human priors, while highlighting some shortcomings of pure LLMs as grounded reasoners.

Introduction

The paper asks how people efficiently generate informative questions in grounded settings while navigating large hypothesis spaces with limited cognitive resources. LIPS uses language-model proposals and symbolic evaluation to model this process, yielding questions that track human performance while retaining grounding challenges.

Introduction

  • The paper models efficient, informative question generation in a grounded environment under cognitive resource constraints.The motivating challenge is selecting useful questions from a vast space of grammatically valid possibilities.Source: Introduction · p. 1
  • Unlike prior approaches that used the board only for utility computation, this approach also uses board information to cue question generation.The paper frames this as bottom-up use of the situation alongside top-down evaluation.Source: Introduction · p. 1
  • LIPS samples natural-language questions, translates them into programs, and selects candidates by simulated Expected Information Gain.The model uses language models as both a question prior and a language-to-program translator.Source: Introduction · p. 1
  • With small sample budgets, LLM priors yield informative questions calibrated to human data, but LLM-based models still produce redundant or uninformative questions.The paper reports that GPT-4V provides no improvement over non-visual baselines.Source: Introduction · p. 2

The Battleship Game

The study uses the original single-turn Battleship question-asking task, in which participants ask about hidden ships on partially revealed boards.

The Battleship Game

  • Participants see a partially revealed board and ask a goal-directed question to help locate hidden ships.The task evaluates question asking in a grid-based environment.Source: The Battleship Game · p. 2
  • The task contains 18 unique 6x6 board contexts, each with three ships varying in length, orientation, and placement.The ships are red, blue, and purple, with lengths of 2–4 tiles and horizontal or vertical orientations.Source: The Battleship Game · p. 2
  • This study uses the original single-turn task rather than later multi-turn variants.The later variants extended the paradigm to study multi-turn interactions.Source: The Battleship Game · p. 2

Models

The models score questions by how much they reduce uncertainty over compatible boards, then search proposal distributions for high-value candidates. The proposals come from either a Battleship grammar or language models that generate natural-language questions and translate them into programs.

Models

  • The ideal observer starts with a uniform prior over compatible boards and updates beliefs after an answer using its likelihood under each board.The marginal likelihood is computed by enumeration or approximated by sampling over the board hypothesis space.Source: Models · p. 2
  • Expected Information Gain measures the expected reduction in board-state entropy, using log2 so its values are in bits.A yes/no question ruling out half the boards has EIG of 1.Source: Models · p. 2
  • Rather than fit question features to human data, the model samples k candidates and selects the one with maximum EIG, treating human-like questions as an outcome of a generic prior under resource limits.The parameter k controls the amount of internal computation.Source: Models · p. 3

Grammar proposal distribution

  • The PCFG proposal uses Battleship concepts and operations to form executable questions; its short-program bias is useful, but it remains unconditional without many thousands of labeled board-question pairs.The grammar follows prior work and omits lambda abstractions and trivial depth-1 expressions during sampling.Source: Grammar proposal distribution · p. 3

Language model proposal distribution

Experiment

The experiment tests question generation and selection on Battleship boards using human data, LLMs, and a hand-engineered grammar. LIPS with small sample budgets produces questions near human performance, while translation fidelity and grounding remain constraints.

Participants, materials, and methods

  • The human dataset contains 605 question-board pairs from 40 participants across 18 Battleship boards.Each board had 26–39 questions; participants were asked for questions with single-word answers.Source: Human data · p. 4
  • Both LLMs received the same prompts; few-shot prompts included human questions from other boards, and translation prompts used sampled language-program pairs.Questions were sampled 100 per board; GPT-4 prompt and board formats varied across zero-shot/few-shot and textual, grid, visual, or no-board conditions.Source: Prompting · p. 4, Sampling · p. 4

Results and Discussion

  • At k = 10, both LLMs significantly outperformed the human mean, yet all models remained below the best human-generated questions.The reported p-values were p < 0.001 for CodeLlama and p = 0.01 for GPT-4 (textual, few-shot).Source: Figure 3 · p. 5, Informativity · p. 6
  • At k = 5, both LLMs were closely calibrated to the human EIG distribution, but the top human questions outperformed model questions.The comparison concerns the full distribution; the top human questions were approximately the 85th–90th percentile.Source: Figure 3 · p. 5, Sample efficiency · p. 6
  • CodeLlama translated 75% of sampled questions and GPT-4 translated 88%, while GPT-4 zero-shot translation fidelity was 40%.In this evaluation, a question had to be expressible in the Battleship DSL to count as informative.Source: Translation fidelity · p. 6
  • Among valid programs, 40% from CodeLlama and 33% from GPT-4 had EIG = 0; GPT-4’s visual condition did not outperform the no-board condition.Zero-EIG questions were redundant with information already revealed on the board.Source: Figure 3 · p. 5, Groundedness · p. 6
  • Few-shot LLMs approximated the human question-type distribution, with CodeLlama closer; zero-shot GPT-4 defaulted to boolean questions.Humans preferred boolean and numeric answers, while the hand-engineered grammar produced an approximately uniform type distribution.Source: Question type · p. 6, Figure 4 · p. 6

Conclusion

The conclusion presents LIPS as sampling questions from a noisy LLM prior and translating them into programs in a language of thought. It identifies richer representations and more sample-efficient inference as future directions.

Conclusion

  • The paper uses an existing domain-specific language as an initial language of thought, while suggesting Bayesian program induction as a way to learn a new one.Source: Conclusion · p. 6
  • The authors suggest a domain-general programming language such as Python as an alternative to a domain-specific language.Source: Conclusion · p. 6
  • More sample-efficient inference methods and applying them to longer interactions, such as multi-turn Battleship, are identified as future directions.Source: Conclusion · p. 6

Appendix

The appendix presents example human and model questions, symbolic programs, and reported values across Battleship board contexts.

Appendix

  • Examples span location, ship-size, and occupied-row questions, illustrating how sampled queries vary across board contexts and models.The table includes human questions about ship locations and occupied rows, as well as model questions about ship sizes and tile locations.Source: Table 2 · p. 9, Appendix · pp. 12–13
  • Grammar outputs programs directly, so the table omits its natural-language question column.The table’s examples pair model outputs with best and random samples; for models, random samples come from LIPS outputs with k = 10.Source: Table 2 · p. 9
  • In one example, both the human and CodeLlama ask for the purple ship’s top-left location, while GPT-4 repeats a ship-size question.The human and CodeLlama ask, “At what location is the top left part of the purple ship?”; GPT-4 repeats “How many tiles is the blue ship?”Source: Appendix · p. 12
  • The human asks for the location of the bottom-right part of the purple ship.Source: Appendix · p. 13
  • “How many tiles is the purple ship?” is paired with the value 1.56.Source: Appendix · p. 13
  • GPT-4 asks twice how many tiles the purple ship is, with the value 1.56 each time.Source: Appendix · p. 13

Full results

Table 3 reports statistics for all models and values of k, with means and standard errors computed across board contexts.

Full results

  • Table 3 reports statistics for all models and values of k, with µ and σM computed across board contexts.Source: Table 3 · p. 14
  • The table counts parseable-program translations as Valid and questions with EIG > 0 as Informative.Source: Table 3 · p. 14
  • Its complexity measures include program-tree depth and size, plus the number of words in each natural-language question.Source: Table 3 · p. 14

Prompts

The model uses two few-shot prompt formats, for question generation and translation, with some message formats varying by board modality.

Prompts

  • Prompts are procedurally constructed as few-shot examples for task-relevant question generation and translation.Source: Prompts · p. 15
  • Message formats can vary with the board representation modality: textual, grid, or visual.Source: Prompts · p. 15
  • System, User, and Assistant labels mark instructions, user inputs, and generated responses; they are metadata for GPT-4 or prepended text for CodeLlama.Source: Prompts · p. 15

Question generation prompt

The prompt frames the model as a Battleship player asked to pose one information-seeking question with a one-word answer. It supplies a target board in a selected representation, optionally with human-question examples.

Question generation prompt

  • The target board can be represented as an image, textual description, or grid using H, W, R, B, and P for hidden, water, and ship tiles.In the visual representation, hidden tiles are light gray, water dark gray, and ships red, blue, or purple.Source: Question generation prompt · p. 15
  • Few-shot prompts add questions from human data on three non-target boards, while zero-shot prompts omit those examples.The few-shot examples comprise 10 questions per board; the no-board condition omits the target board and transition message.Source: Question generation prompt · p. 15
  • The model is instructed to ask one question that helps reveal hidden-ship locations and can be answered with a single word.The prompt casts the model as a game-playing agent and requests no additional explanation.Source: Question generation prompt · p. 15
  • The prompt’s sample questions ask about a ship’s location, orientation, and presence in a column.The examples include asking where a ship’s top-left part is, whether it is horizontal, and whether a ship occupies column F.Source: Question generation prompt · p. 16

Translation prompt

The translation prompt casts the LLM as a Battleship-question translator, using language–code examples before presenting a target question. Its examples illustrate the intended mapping from questions to query programs.

Translation prompt

  • The prompt includes 12 language–code example pairs sampled from human data, excluding examples from the target board.The examples are randomly sampled without replacement.Source: Translation prompt · p. 17
  • The prompt ends with a target question in language for the LLM to translate into code.One example maps “Do the red ship and the purple ship touch?” to “(touch Red Purple).”Source: Translation prompt · p. 17
  • The translator prompt instructs the LLM to convert each user question into a query program.The Battleship task instructions match those used in the question-generation prompt.Source: Translation prompt · p. 17
  • Example questions ask about ship orientation and counts, including whether more ships are horizontal than vertical.Other examples ask how many ships are horizontal and whether the blue ship is horizontal.Source: Translation prompt · p. 17

Related papers

Loading 2402.19471v2…