acceptodds
Under review as a conference paper at ICLR 2027

Cost-Indexed Bracketing for Checkable Search

Abstract

We study hard-budget search with a sound terminal checker and a supplied finite hidden-state model. Stationary rejection-only retries reduce to completion counts; an exit-preserving phase construction extends this reduction through checkpoint creation. The resulting block success vectors are standard partially observable Markov decision process (POMDP) -vectors, with exact cost expressed by observable budget augmentation. We show how a cost-sliced envelope approximation composes through diagnostic and refresh decisions, and implement both rounded grids and standard -pruning. The latter is substantially more compact on the strongest tested bank: 255 vectors rather than 31,083 grid records. Computed lower/upper brackets, not a loose worst-case grid rate, guide refinement. A finite-row calibration procedure produces a true-environment bracket from sampled program proposals under explicit labeled-access assumptions. Experiments include measured 10,000-prior workloads, support-size resource failures, and 64 random graph catalogs. Post-refresh diagnosis helps modestly in unchecked catalogs but remains of little benefit when refresh already checks the checkpoint; greedy residual filling explains most fixed-bank allocation gains. The contribution is an exit-preserving search specialization of established POMDP approximation tools, with an explicit model-acquisition boundary, not a new value representation or a general claim about language-model reasoning.

Primary area:
foundation or frontier models, including LLMs
Keywords:
checkable search, hard-budget planning, POMDP approximation, checkpoint reuse, finite-sample calibration

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_beAUOpenReview ↗
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?
1 comment
AuthorsOpenReview ↗

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.

Reviewer_txnKOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper provides an algorithmic approach that enables search under a hard budget given access to a bank of saved prefixes, budget and diagnostic/quotas. The algorithm is evaluated on synthetic checkpoint catalogs, a sat setting, and a program repair problem.

(This is dense and unreadable, my review isn’t detailed and I recommend rejection solely on that basis)

Critical strengths

None

Critical weaknesses
  • There are no comparisons to prior work, including the ones cited in the related works.
  • The paper is targeted to the primary area of foundation or frontier models, including LLMs, but shows no results that supports this.
Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer txnK

Thank you for the review. We agree that the submitted paper was dense, and readability was our first priority.

Readability. We rewrote the abstract and Section 1 (pages 1–2) in plain language around one running example, defined the core terms before use, and opened each section by saying what it shows. The general response lists all changes and defines the terms used below.

W2: no LLM results. Appendix I adds two studies with real LLMs, summarized in Section 6. In the first, Qwen2.5-Coder-1.5B-Instruct writes the decoder. Because the model never wrote a correct signed decoder from the bare prompt in 768 samples, repeating that prompt reaches only 40.4–45.6% success. Our planner can also buy probes, which ask for one reference output, and start from partial programs. It reaches 67.4–80.5%, inside its certified brackets. Greedy policies with the same actions come within 0.54 points, so the planner mainly adds the bracket. The second study uses recorded samples (Brown et al., 2024) from five LLMs on CodeContests, two on MiniF2F and thirteen on MATH. There, planning as if retries were independent lowers held-out success by up to 6.1 points on CodeContests and 6.3 on MATH, compared with treating each problem's failures as persistent.

W1: no comparisons with prior work. We add four comparisons, each on the same tasks and budgets as our planner.

  • SARSOP, a standard POMDP solver, also keeps lower and upper bounds (Appendix J). On our instances with two hidden states, it is usually faster for a single prior and can certify tighter brackets. For 10,000 priors, however, our library takes 0.51 s in total and SARSOP 300–315 s. Counting only its solver time, SARSOP still takes 93–119 times our total. We did not test reusing SARSOP's bounds across priors.
  • OSCA (Zhang et al., 2025) allocates samples across LLMs by hill climbing, and our cost-weighted version of it comes within 0.22 points of our planner's held-out success, except at the smallest CodeContests budget, where it is 3.1 points lower (Appendix I.1). Our plan is also certified to be within 1.09 points of optimal on the training problems.
  • Appendix I.1 also compares three simple allocations on held-out problems. A plan that treats retries as independent loses 2.76–6.06 points to ours on CodeContests. The best single model is up to 0.39 points better than ours on CodeContests, and a uniform split across models, as in algorithm portfolios (Gomes & Selman, 2001), is up to 0.77 points better on MiniF2F.
  • Reflection-style retries, which show the same LLM "rejected" or a counterexample after each failure, reach 33.4–36.9%, below plain repetition (Appendix I.2).

Appendix K (Table 13) explains why three other families are omitted. Restart schedules decide when to abort runs of random length, while our attempts have fixed costs. Tree search uses feedback beyond accept or reject and gives no guarantee bracket. Per-prompt allocation sees each prompt before allocating, which our plans do not.

I thank the authors for their thoughtful discussion. After considering their responses to my review and those of the other reviewers, I maintain my original score.

AuthorsOpenReview ↗

Response to Reviewer txnK (follow-up)

Thank you for reading our responses and for the discussion. The revision addresses the three concerns in your review. We rewrote the abstract and Section 1 in plain language around one running example, and they now define the core terms before using them. Appendix I adds two studies with real LLMs. On the decoder task, our planner succeeds 67.4–80.5% of the time, while repeating the bare prompt succeeds 40.4–45.6% of the time. Appendix J and Appendix I.1 compare our planner with SARSOP and OSCA on the same tasks and budgets.

Reviewer_qPAQOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies hard-budget search with a sound terminal checker and a supplied finite hidden-state model. The authors show how a cost-sliced envelope approximation composes through diagnostic and refresh decisions and implement both rounded grids and standard ε-pruning. The experiments include measured workloads, support-size resource failures, and random graph catalogs.

Critical strengths

I really appreciate for the theory proof.

Critical weaknesses

W1: Very hard to understand this paper.

W2: In the table 3, the performance compared with Global in checked is extremely small, and the performance gain compared with Greedy and One-step is not big too. It is unclear if this method is really help.

W3: What is the position of this paper compared with related work??

Questions for authors

Q1: Could you clarify the novelty beyond adapting or combining existing method???

Q2: Could you provide the comparison with other existing method for checkable search?

3 comments
AuthorsOpenReview ↗

Response to Reviewer qPAQ

Thank you for the review and for your appreciation of the theory.

W1: hard to understand. We agree. The general response lists every change, including a rewritten abstract and Section 1, and defines the terms used below.

W2: the Table 3 gains are small. The average gains are small because Greedy also uses probes (diagnostics) and new checkpoints, which supply most of the gain. Phase, our planner, is exactly optimal for the rates fitted from samples, so it shows the most any policy could gain under that model. It is not optimal for the true rates, under which Table 3 scores every policy. Table 3's caption now states this and defines each column. Frozen never refreshes (never creates a new checkpoint), Global cannot probe the mode after its first refresh, and Greedy and One-step plan only one action ahead.

  • The near-zero gap to Global in checked catalogs is expected, because there a new checkpoint already reveals whether it is valid and a later probe rarely changes a decision. The two policies tie in 55–59 of 64 catalogs (Appendix H.11), whereas dropping new checkpoints, as Frozen does, costs 7.30–9.79 points.
  • The 0.6–1.6-point average gaps to Greedy and One-step mix exact ties with occasional large gains. Across the six conditions, Phase ties Greedy in 22–41 of the 64 catalogs and One-step in 24–42, and its gains exceed 2 points in 8–20 catalogs, reaching 13.71 points (Table 7). Phase is lower in at most 4 catalogs, by at most 3.04 points, because it is optimal for the fitted rates rather than the true ones.
  • With a real LLM, greedy policies also come within 0.54 points of our planner (Appendix I.2), so the planner's main addition is its bracket.

W3 and Q1: position, and novelty beyond combining methods. The ingredients, such as POMDP value functions and binomial confidence intervals, 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 do not drift between checkpoints. Then any adaptive policy with probes and checkpoints can be rewritten without loss as phases, each made of probes, fixed numbers of attempts and one new 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. Matching only each phase's chance of success would not allow this. This reduction makes the library reusable inside search, with an error that grows only with the budget (Theorems 4 and 5). Theorem 6 also gives a bound on true success that holds even for planners chosen after seeing the data. Discrete search theory is the special case in which each attempt can succeed in only one hidden state (new Proposition 10). We do not claim higher success than test-time compute methods for LLMs. Table 13 in Appendix K compares each line of related work with ours, and Q2 below gives direct comparisons.

Q2: comparison with existing methods for checkable search.

  • Appendix J compares SARSOP, a standard POMDP solver, on our instances with two hidden states. For one prior it is usually faster and can certify tighter brackets, but across 10,000 priors its solver time alone is 93–119 times our library's total. We did not test reusing SARSOP's bounds across priors.
  • OSCA (Zhang et al., 2025) allocates samples across LLMs, and Appendix I.1 compares our cost-weighted version of its hill climbing on recorded LLM samples. It comes within 0.22 points of our held-out success, except at the smallest CodeContests budget, where it is 3.1 points lower. On the training problems, Theorem 1 shows that no policy that sees only accept or reject beats the best count plan, that is, the best choice of how many samples to draw from each model. Our upper bound puts our plan within 1.09 points of that optimum.
  • Appendix I also compares repeated sampling, portfolio allocation and reflection-style retries. The retries, which show the same LLM "rejected" or a counterexample after each failure, reach only 33.4–36.9%, below plain repetition. Tree search uses feedback beyond accept or reject and gives no guarantee bracket, and per-prompt allocation sees each prompt, so neither is compared (Appendix K, Table 13).

Thank you so much for the reply. Considering the current response and other reviewers' feedback, I will maintain my original score.

AuthorsOpenReview ↗

Response to Reviewer qPAQ (follow-up)

Thank you for reading our reply and for your kind words about the theory.

The revision addresses each of your points. The abstract and Section 1 now follow one running example and define the core terms before they are used. The Table 3 caption defines every column and states that all policies are scored under the true rates. Appendix H.11 shows that the small average gains combine exact ties with gains of up to 13.71 points.

On the contribution and its position, Section 1 names Theorem 3 as the main new structural result. Appendix K (Table 13) places the paper among related work, and Appendices I and J compare our planner with OSCA and SARSOP.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: summary of the revision

We thank the reviewers. All three found the paper hard to read, and together they asked for evidence with real large language models (LLMs) and for comparisons with existing methods. We agree and revised the paper. The revised main text still fits in 10 pages, and the original numbering is unchanged.

What changed for readability.

  • The abstract and Section 1 are rewritten in plain language around one running example, an LLM writing a two-byte decoder whose byte order and signedness the specification leaves open.
  • Section 1 now defines the core terms before use, lists the three contributions with the section that proves each, and names Theorem 3 as the main new result.
  • Sections 2 to 6 each open by saying what they show, and every theorem is followed by a plain-language reading.
  • Symbols in Sections 2 and 3 are defined before use, and the grid index k is renamed q, since k also counts allowed probes.
  • The captions of Tables 1 to 4 and Figure 2 now define their symbols, columns and plans, and Figure 2 is redrawn to be legible.
  • Section 6 now points in one sentence to side results that only the appendix explains.
  • Appendix L (Table 14) is a glossary, and Appendix K (Table 13) places the paper among related work.

Terms used in the replies. A mode is the hidden variant of the task, such as the decoder's byte order, and a prior gives each mode's starting probability. A probe pays to observe something about the mode, a checkpoint is a saved partial solution, and a phase is the part of a policy between two new checkpoints. A bracket [L, U] pairs the success L of a policy we can run with an upper bound U on the success of every policy. The library is a table, computed once and reused for any prior. For each exact cost, it stores selected batches of attempts with their success probability in every mode.

New evidence. Appendix I adds two studies with real LLMs, and Appendix J compares our planner with SARSOP, a standard solver for partially observable Markov decision processes (POMDPs). We claim no new value representation or POMDP solver.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.