- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies how to spend a fixed budget searching for a solution when every answer can be checked perfectly but some unknown hidden factor (like which byte order a spec uses) makes repeated attempts fail together. The authors frame it as a careful application of known POMDP and statistics methods, not a new algorithm, and there are no experiments with real language models.
Critical strengths
- The proofs appear to be careful.
- Comparison to stronger baselines rather than weak ones. Report failures and null results. Careful statements without overclaiming.
- Thorough reproducibility section.
Critical weaknesses
- Writing lacks clarity and is very difficult to understand.
- The motivation is LLM search but there are no LLM experiments. Costs are abstract work units and the example is a toy with 16 candidate programs. The requirement to already know the hidden states is also hard to satisfy in practice.
- Experiments show simple approaches are nearly as good, which makes it unclear why this method is needed.
- Theory-heavy, which is fine, but lack novelty to satisfy a top-tier conference publication standard. Mostly a careful synthesis of existing statistics tools and fit them to search with a perfect checker.
Questions for authors
- Is there a realistic setting, ideally with an actual LLM, where the stationarity assumptions hold and the hidden-state model can be obtained?
- How does your approach relate to optimal search theory and robust MDPs?
Response to Reviewer beAU
Thank you for a careful review.
W1: clarity. We agree, and the general response lists the changes.
Q1 and W2a: a realistic setting with an actual LLM. Yes, the decoder task of Appendix I.2 is such a setting. Qwen2.5-Coder-1.5B-Instruct writes the programs, which the checker runs on all 65,536 inputs. Stationarity holds because each prompt is sampled at a fixed temperature, and the four modes (byte order and signedness) can be listed from the specification. From the bare prompt the model never wrote a correct signed decoder in 768 samples, so repeating that prompt reaches only 40.4–45.6% on held-out samples at budgets of 384–768 tokens. Our planner can also buy probes, which ask for one reference output, and start from partial programs (checkpoints). It reaches 67.4–80.5%, inside its certified brackets, from [64.4, 70.5] at the smallest budget to [74.3, 82.0] at the largest. With 95% confidence, the planned policy's true success is at least the left end and no policy exceeds the right end, for this model, these prompts and this temperature. If the prompt changed after every failure, each call would start a new phase and Theorem 3 would save little.
W2b: abstract costs. The LLM studies now use concrete costs, namely token allotments in the decoder and compute proportional to model size for the recorded samples of Appendix I.1. Only the controlled studies still use work units.
W2c: a toy with 16 programs. The candidates are now whatever the LLM writes: 1,228 distinct programs among 5,376 samples. We still declare the partial programs, probes and prior. The task is small on purpose, so that every mode can be listed, as the true-environment guarantee (Theorem 6) requires.
W2d: the hidden-state model must be known. We agree that this is the main assumption. When the modes can be listed from the specification, as in the decoder, the bracket certifies the true environment. When past samples are labeled by problem, as in Appendix I.1 (Brown et al., 2024), each problem can be its own hidden state, but the bracket then covers only the fitted model. A model that is too coarse costs accuracy: at the largest CodeContests budget, merging the training problems into two groups with averaged rates gives 19.87% held-out success, against 22.24% with one hidden state per problem.
W3: simple approaches are nearly as good. We largely agree. In the decoder the gain comes from the probes and partial programs, and on recorded samples from modeling persistent failure, which is worth up to 6.1 points on CodeContests. The optimizer matters little, since greedy policies come within 0.54 points of the planner in the decoder. On recorded samples, greedy filling and the hill climbing of OSCA (Zhang et al., 2025), which allocates samples across LLMs, come within about 0.2 points of our plan, except at the smallest CodeContests budget, where they are about 3 points lower. Even so, the best single model or a uniform split across models is sometimes slightly better on held-out problems. What the planner adds is its upper bound, which shows when a simple policy is near-optimal, although the decoder's 6–8-point bracket cannot separate policies 0.5 points apart.
W4: novelty. We agree that the ingredients are established, and Section 1 now names Theorem 3 as the main new structural result. Suppose the checker returns only accept or reject and success odds stay fixed between checkpoints. Theorem 3 shows that any adaptive policy with probes and checkpoints can then be rewritten without loss as phases, each of which buys probes, makes fixed numbers of attempts and creates one checkpoint. Each rewritten phase leaves the next one with exactly the same joint distribution of mode, observations, checkpoints and remaining resources as the original policy, so phases can be chained. Options (Sutton et al., 1999) compose arbitrary sub-policies, while Theorem 3 reduces each phase to fixed counts. This lets one precomputed library be reused inside search, with an error that grows with the budget but not with the number of probe outcomes or checkpoints (Theorems 4 and 5).
Q2: optimal search and robust MDPs (Appendix K). Classical search for a stationary target (Stone, 1975; Kadane, 2015) is the special case in which each attempt can succeed in only one hidden state (new Proposition 10). Our count reduction (Theorem 1) then becomes the known fact that detection probability depends only on how effort is allocated. We add probes, checkpoints and calibration but do not treat moving or false targets. For robust MDPs (Givan et al., 2000; Iyengar, 2005; Nilim & El Ghaoui, 2005), the new Proposition 11 shows that the worst case over the confidence intervals is the lower endpoint of every success rate, because success increases with each rate. The robust problem therefore needs only one ordinary planning call. This is the monotone case of Givan et al.'s pessimistic ordering.