Self-Steering Language Models
Authors: Gabriel Grand
Joshua B. Tenenbaum
Vikash Mansinghka
Alexander K. Lew
Jacob Andreas
Venue: COLM 2025 (2025)
Keywords: Probabilistic inference
sequential Monte Carlo
code generation
test-time search
constrained generation
reasoning
language models
TL;DR: We introduce a new approach to structuring test-time computation that uses LMs to plan and execute task-specific search procedures in a probabilistic programming language.

Abstract: While test-time reasoning enables language models (LMs) to tackle complex tasks, searching or planning in natural language can be slow, costly, and error-prone. But even when LMs struggle to emulate the precise reasoning steps needed to solve a problem, they often excel at describing its *abstract structure*—both how to verify solutions and *how to search* for them. This paper introduces DisCIPL, a method for “self-steering” LMs where a *Planner model* generates a task-specific *inference program* that is executed by a population of *Follower models*. Our approach equips LMs with the ability to write recursive search procedures that guide LM inference, enabling new forms of verifiable and efficient reasoning. When instantiated with a small Follower (e.g., Llama-3.2-1B or Qwen3-1.7B), DisCIPL matches (and sometimes outperforms) much larger models, including GPT-4o and o1, on challenging constrained generation tasks. Our work opens up a design space of highly-parallelized Monte Carlo inference strategies that outperform standard best-of-N sampling, require no finetuning, and can be implemented automatically by existing LMs.

Published as a conference paper at COLM 2025
Self-Steering Language Models
Gabriel Grand J Alexander K. Lew12 Jacob Andreas!
Joshua B. Tenenbaum
Vikash K. Mansinghka'
Massachusetts Institute of Technology Yale University
{gg, jbt, vkm, jda)@mit. edu alexander. 1ew.derr.wwealee.e...
github.co com/ waw.gggabrraneellaaaaaaa
Abstract
While test-time reasoning enables language models (LMs) to tackle com- plex tasks, searching or planning in natural language can be slow, costly, and error-prone. But even when LMs struggle to emulate the precise rea- soning steps needed solve a problem, they often excel describing its abstract structure- how to verify solutions and how to search for them. This paper introduces DISCIPL, a method for "self-steering" LMs where a Planerr model generates task-specific inference program that is executed by a population of Follower models. Our approach equips LMs with the abil- ity to write recursive search procedures that guide LM inference, enabling new forms of verifiable and efficient reasoning. When instantiated with Qwen3-1.7B), DISCIPL matches
small Follower (e.g., Llama-3.2-11 (and sometimes outperforms) much larger models, including GPT-4o and ol, on challenging constrained generation tasks. Our work opens up a design space of highly-parallelized Monte Carlo inference strategies that outperform standard best-of-N sampling, require no finetuning, and can be implemented automatically by existing LMs.
Introduction
Even as language models (LMs) are becoming increasingly proficient at reasoning tasks, progress has been "jagged" (Karpathy, 2024; Roose, 2025): today's frontier models surpass experts at science and math reasoning (e.g., Hendrycks et al., 2021; Rein et al., 2023; Wang et al., 2024b) yet still routinely struggle with counting, arithmetic, tic-tac-toe, metered po- etry, and other intuitively simple tasks (Ball et al., 2024; McCoy et al., 2023; Xu & Ma, 2024). For example, even very capable LMs have difficulty writing a coherent sentence under the constraints in Fig. 1, which are manageable for most proficient English speakers.
There is growing consensus that many problems require more deliberate, effortful style of thinking (Kahneman, 2011). However, an open question is how to structure inference so as to best leverage available computational resources. One popular approach performs in-context reasoning via serialized chain-of-thought (DeepSeek-A) et al., 2025; OpenAT, 2024b). While highly flexible, reasoning via autoregressive generation is costly, slow, and can still produce unreliable outputs. On the other hand, structured inference methods like tree search (Silver al., 2016; Yao et al., 2023) and sequential Monte Carlo (Lew et al., 2023; Loula et al., 2025; Zhao et al., 2024) attain better parallelism and efficiency by coordinating test-time computation via external algorithms. However, these methods require significant hand-engineering and rely on pre-defined scorers or verifiers, limiting their applicability.
In this work, we propose a new meta- reaaonnggg framework called DISCIPL in which lan- guage models themselues drive the decisions for how to structure inference- time computa- tion. our approach, a Planner LM generates an ad-hoc problem specification (encoding its understanding of the task requirements) and inference procedure (encoding its plan for how to solve the task). Importantly, the specification and plan are implemented as inference programs that invoke Follower LMs, either generatively decomposing reasoning into planning and execution, our architecture preserves flexibility while enabling orchestration of highly efficient, parallel search patterns.
likelihood evaluators. By

---

Published as a conference paper at COLM 2025
Generating reasoning
Existing inference- time methods for LMs
Please generate senterce:
Serial: Chaln-of-Thought
Parallel: guess-and-Chede
1) With exactly 18 words; 2) 4th, 8th, be Gleeeoow 'in', 'and' respectively.
Performance scales with generation length;
Performance scales with sample budget; reguitss vertfer and non- zero pasa rats.
requires extensive seriai computation.
Thinking... Crafting precision.... Variliing--
Taking stap back... Trying new asproech... Distiling Beotlond... Putting Ingother... Chacsinng distali....
Lay
The recent weather in Glasgow...
The beautiful city Glasgow famous for its stunning architecture and rich cultural heritage. (14
Glangoow prize int..
*.* & incressing inference cost...
The year begins Glasgoow with thrilling developments every corner, creative endeavors flourish acroes the vibrant community. (18 words)
incressing inforence cost...
Requiires nun-trivial search; standart LMs strogale to satisty all constraints.
The Scottish city Glasgow...
DisCIPL (Distributional Constraints by Inference Programming with Language Models)
class
Inffrrecettddll (Podel]:
def
init (self): {
The
benuttul
G
Sootland
3: "Glosgow", 7: "1n", 18: "and"
}
self-1, self salf-rar_xords 0, 18
asyne def stop(self):
your
bogino
Guaggow
ranvidd
number
thrce
next
constrotned, append
context a score its probabiiity wll.ii felfffixed:
Resample
awst selt observe (self, tsxed[selt (1)))
Scatlanc's largect
city
Garggo
tock
shird
prime
Else, soxple freety until sard houndary clse:
awit self, sarple(sull Fnnxt ward())
Increeent wond counter chech total sulf.i
Inference scales orthogonally generation length and can be efficiently parallelized with small LM.
selfi1 selff-aa_vvands:
self.end()
Planner writes probabilistic program that encodes a stepwise LM generation procedure satisfying constraints.
Inference engine coordinates Follower LM instances, dynamically allocating compute via Sequential Monte Carlo.
Figure 1: Self-steering language models with probabilistic programs. LMs struggle with problems that combine generation and reasoning under constraints (top left, task from Yao et al., 2024). Popular approaches (top right) scale inference by search sampling; however, even costly reasoning models do not always yield correct or fluent results (CoT example from ol,, single-shot, first attempt). In our method (DisCiPI., bottom), a Planner LM writes an inference program that defines step-by-step com- putations to steer a population of Follower LMs. Our approach combines the benefits serial and parallel methods: the Planner ensures correctness by construction, while the Followers collectively search for sequences with high probability. (See Fig. 7 for detailed visualization.)
To test this approach, we evaluate DISCIPL on two domains: (1) COLLIE (Yao et al., 2024), a challenging constrained generation benchmark on which even very large LMs perform unreliably; and (2) PUZZLES, a custom dataset of difficult tasks involving poetry compo- sition, wrintn budgeting, and itinerary planning. We instantiate DISCIPL using capable Planner LM to generate code (GPT-40 prompted with few-shot examples), and a small Follower LM to execute it (lightweight versions of Llama-3 Qwen3). On para- graph tasks, this approach boosts accuracy well beyond the original capabilities of the Follower. Meanwhile, enables the Follower to surpass the Planner and approach the performance of powerful reasoning models like 01. Finally, we study how DISCIPL scales with the size and capabil- ities of the underlying Follower model, allowing our approach to benefit organically from advances in LM architecture and training methods.
more tightly constrained sentence and puzzle tasks, DISCIPL
Amidst a growing body of task-specific search and sampling methods for LMs ($2), we introduce a generalized approach. By using LMs to implement their own inference pro- cedures on-the-fly, DISCIPL yields efficient solutions to problems that would otherwise require non-trivial human engineering. We believe that this new combination of code gen- eration and probabilistic inference represents an exciting step in test-time scaling.
2 Related Work
Scaling Inference- Time Computation. Reasoning via autoregressive generation is effec- tive for many tasks, and the success of ofaan--o-thought" (Nye et al., 2021; Wei et al., 2022) has spawned many variants that trade off generality and efficiency: whereas constructing
2

---

Published as a conference paper at COLM 2025
explicit "tree-of-thought" (Liu et al., 2023; Yao et al., 2023) requires problem-specific engineering, linearizing reasoning into one long "stream-of-searde"
(Gandhi et al., 2024; Lehnert et al., 2024) scales exponentially with tree depth. As an alternative, simple sam- pling procedures like best-of-N sampling (Brown et al., 2024; Cobbe et al., 2021) and self- consistency/ / majority voting (Wang et al., 2023a) have also emerged of scaling LM performance. These "embarrassingly parallel" methods (Herlihy & Shavit, 2012) are simple to implement, but can be computationally wasteful (Damani et al., 2024; Snell et al., 2024). By combining serial and parallel methods, our approach achieves a high degree of resource efficiency while maintaining flexibility.
popular means
Parallel and Asynchronous Generation. A variety of recent proposals leverage parallel and / or asynchronous generation with LMs (Jin et al., 2025; Ning et al., 2024; Pan et al., 2025; Rodionov et al., 2025). These methods typically define lightweight markup syntax to expose specific operations, like spawning and joining threads. In contrast, our approach offers far greater expressivity by building on Turing-complete programming language.
Self-Improvement. Recently, a variety of novel methods have been proposed for using LMs to optimize prompts (Fernando et al., 2024; Honovich et al., 2023; Khattab et al., 2023; Shinn et al., 2023; Yang et al., 2024; Zhou et al., 2023c), agentic systems (Hu et al., 2024), and optimization procedures themselves (Zelikman et al., 2023). DISCIPL shares a similar recursive flavor, but generates ad-hoc inference algorithus that provide token-level control over LM behavior at decoding time with probabilistic guarantees.
Constrained Generation. Recent years have seen a proliferation of benchmarks designed to test the ability of LMs to adhere to complex and compositional constraints (Chia et al., 2024; Jiang et al., 2023; Lin et al., 2020; Sun et al., 2023; Wang et al., 2022; Yao et al., 2024; Zhou et al., 2023a). Prior approaches have focused on developing decoding algorithms for specific classes of constraints (Hokamp & Liu, 2017; Koo et al., 2024; Lu et al., 2021; 2022; Poesia et al., 2022; Post & Vilar, 2018; Ugare et al., 2024; Willard & Louf, 2023) or guiding generation with neural models (Amini et al., 2023; Kumar et al., 2022; Li et al., 2022; Qin et al., 2022). Various learning-bass baaedd approaches have also been proposed, including self- correction through feedback (Welleck et al., 2023) and bootstrapping from self-generated instructions (Wang et al., 2023b; Zhou et al., 2023b).
Sequential Monte Carlo with LMs. Particle-based methods, such as sequential Monte Carlo (SMC; Doucet et al., 2001), offer a powerful framework for building adaptive inference-time search procedures. SMC has recently been applied to LMs to solve vari- ous tasks, including constrained generation (Lew et al., 2023; Loula et al., 2025; Zhao et al., 2024) and math reasoning (Feng et al., 2024; Puri et al., 2025). However, applying SMC to new problems requires either engineering or learning various parameters of the algorithm (e.g., reward models or twist functions); our work, an LM automates this process.
Probabilistic Programming and LMs. Probabilistic programming languages (PPLs) allow users to implement probabilistic models as programs, and automate aspects of probabilis- tic inference (Goodman et al., 2014). Some PPLs support LMs as parts of models (Dohan et al., 2022; Lew et al., 2020; 2023), and LMs have also been used to generate probabilistic programs over symbolic domains (Li et al., 2024; Wong et al., 2023). More recently, PPLs have evolved to feature programmable inference (Mansinghka et al., 2014; 2018), so that pro- grams can concisely specify both models and custom inference algorithms. We use LMs to generate code in LLAMPPL (Lew et al., 2023), a PPL built on modern LM stack that enables users to define inference procedures via short, intuitive Python programs.
3 DISCIPL
3.1 General Framework
A language model M is a distribution on token sequences from vocabulary x E V* whose probability factorizes autoregressively
(x) - PM(x; xxr). We designate roles for two LMs, a Planner Mp and a Follower Mp. We assume that both support efficient conditional generation, and that My also supports efficient conditional probability evaluation.
3

---

Published as a conference paper at COLM 2025
Algorithm DISCIPL Outer Loop
function DisCIPL((ask daskk Planner Mp, Follower Mj, N, retries R, Rnenine I)
2: result t Enull,
Imitialize with empty string
3: while result E and < do
4: πt ~ PMp[- prompt result)) b Generate inference program (with prior errors as feedback) b Execute the program with Follower
5:
result ~ [TT, N)
6:
if result & then
7:
r<- 7 return resul!
Retry on runtime errors
The key idea in DIsCIPL is that Mp can generate an inference program in some language L that describes how Mp should be used to solve a task. The program may make mul- tiple asynchronous queries Mp, in both generative (i.e., sampling) and evaluative (i.e., probability computation) modes. The language provides an inference engine I that takes program π E L, a Follower model Mf, and an inference budget N E N, and yields samples from distribution on results, which can either be answers E V* errors E E.
With these ingredients, the basic DISCIPL algorithm (Alg. 1) proceeds as follows. Given natural language task description 4takkr we first prompt the Planner Mp to generate program in π E L suitable for solving the task. We then attempt to run π using the infer- ence engine I. If inference succeeds, we return its output. Otherwise, correct n, passing the error and associated traceback, up to a max number of retries R.
re-prompt Mp to
Our Instantiation: Language Model Probabilistic Programs
Language of inference programs. In our instantiation of DIsCIPL, programs π are written in LLAMPPL (Lew et al., 2023), Python framework for probabilistic programming with language models. LLAMPPL programs work by repeatedly exlending candidate genera- tions by one more tokens, and then scoring the proposed extensions. The programmer (in our case, the Planner model) can customize the process by which new extensions are proposed and scored; behind the scenes, LLAMPPL's inference engine automatically co- ordinates the overall search, maintaining multiple candidate generations in parallel, and dynamically reallocating computational resources high-scoring partial completions.
As a concrete example, consider the program in Fig. 1, whose step method stochastically adds one word to the running generation, either sampling from Mr (using sample) forc- ing it to agree with word constraint (using observe). The observe method has the side- effect of updating the candidate's score, multiplying by the probability the Follower as- signs to the observed word. The illustration to the right of the program shows how these scores are used by the inference engine: when the word "Glasgow" is forced after the prefix "The year begins," " the candidate generation's 's score drops sharply (due to the low proba- bility of "Glasgow"), and the generation culled.
More generally, programs multiply an update w into that completion's running score. These score updates can encode hard constraints (0 indicates violation), soft constraints, based on symbolic heuristics, LM-as-judge schemes, or token probabilities under the Follower. They can also incorporate importance weights that correct for biases in the proposal process (see $3.3).
use arbitrary logic to extend partial completion and to
Mathematical interpretation of inference programs. An inference program π provides blueprint for sequential inference algorithmss that search for high-quality completions. For- mally, we say that the goal of these algorithms is to generate samples from a farget distribu- tion induced by the program that assigns high probability to high-scoring sequences. Let V' + P (V* x IR) denote step function that maps starting string to distribution (s)) over updated strings s' 1 and multiplicative score updates w E RR. Then for fixed maximum generation length T' E N, the target distribution is defined as
Pturger(s) (s) x Ess (o. (00()
1[5 = s]
W
(1)
4

---

Published as a conference paper at COLM 2025
(A) Token masking
(B) Self-hinting
(C) Self-checking
Generates exectly 10 chors
Generates gift
budget
Chects if text volid
text K 18
asyne def step(self);
def chock(self, text: str) -> hool:
while len(textt) <- K:
# Updote FoLLower LH proupt
1ines toxt.strip(..sppp
Sample
await self-hint(
len(1ines)
outo-update weight
fYYou have 5(self.bugget) left!"
return False
asyne with TokenLeng thHakk chars-k- (enns--)
Check syEtoble structure
gift awii self.extend(
for 1, in zipnnin 7, 5]): textstat. hatpaatsyylllalloeeeeeeeee
):
start="-", stop="\n"
text +n \
return False return True
awatt self.next, next__okeen(]
self, half.hudget weff.exttaat_rrceeeeet self.condition(seff
Figure 2: Inference programming patterns for self-steering, discussed in $3.3.
Intuitively, this equation defines the target probability of string s to be proportional to the probability of generating s via repeated application of step, upweighted or downweighted according to the accumulated score.
Scalable test-time search via probabilistic inference. Our inference engine implements several general-purpose Monte Carlo methods for approximately sampling from the target distribution Plarget- All methods support parallel scaling based on an inference budget N. Our experiments (54) evaluate three instantiations of DIsCIPL.
Importance Sampling (IS). Importance sampling generates N full completions $1,...,5 SN in parallel, by initializing N empty generations and repeatedly calling step until all have completed. For each candidate Si, the score updates w from each step are multiplied to obtain overall score w((). Lastly, final output is sampled s* from the distribution Pis(s(0) = z)(i / zoli). When Ptarget is well-defined, Pıs converges to Plarget as N -> co.
Sequential Monte Carlo (SMC). Like IS, SMC (Doucet et al., 2001, and see Alg. 2) initial- izes N empty generations, called particles, with associated weights initialized to 1. SMC alternates between (1) calling step on all particles in parallel and multiplying the returned score updates into the particle weights; and (2) resampling to cull low-scoring particles and replace them with copies of high-scoring particles. (All weights are reset to uniform af- resampling.) Maintaining multiple copies of promising particles allows each be ex- tended independently by the next call to step. This has the effect of adaptively reallocating the computation budget (N) focus on promising candidates. As in IS, the final particle s* is sampled with probability proportional to the weights. Under mild technical conditions, the SMC sampling distribution also converges to Parget as
c0.
Rejection Sampling (RS). When program's step method generates an entire completion and then computes binary score update, running I (with budget N) reduces to rejection sampling (generating N samples and checking whether any satisfy the constraint). We implement this pattern as DISCIPL-RS in 54.
3.3 Common Patterns
Programs in DIsCIPL adhere to several common inference patterns, for which we have implemented library support and which are also illustrated in the prompt to the Planner.
Step-by-step problem decomposition. The Planner must decide how to decom pose a task into sequence of -nd-soe steps; this determines how often different candidates are compared and resampled. A common pattern to make each step extend by task- relevant unit (e.g., a line of a poem, a word of sentence with word-level constraints, etc.).
Prior and proposal prompts. Imposing constraints can lead LMs to produce incoherent generations. For example, when prompted to generate a sentence using the words "dog." "throw," " and "frisbee," " small LMs yield semantically dubious completions like, "Two dogs are throwing frisbees at each other" (Lin et al., 2020). To promote coherency, programs can compensate for biases in the proposal distribution, which is aware of task-specific con- straints, with scores from prior, which ensures fluency. The Planner defines the prior and proposal distributions via separate prompts. Typically, the prior prompt defines more general instructions, e.g,, "Write sentence that is grammatically correct and makes sense."
5

---

Published as a conference paper at COLM 2025
Constrained generation with weight correction (Fig. 2A). In many situations, might want the Follower to generate specific token sequences (e.g,, "Glasgow"), or more gener- grammars. The Planner
ally, to adhere to formal constraints like regular expressions can apply token masks that both enforce these constraints at generation time, and automat- ically incorporate importance weights that correct for the distortion in the LM's distribution resulting from the mask (Loula et al., 2025; Park et al., 2024).
Self-hinting (Fig. 2B). Since the Planner controls the Follower's proposal prompt, one powerful pattern is to dynamically update it to reflect stateful information relevant to the next generation step. We expose a special hint ( method that injects "Note [hint)" into the Follower's 's context, where the hint can include text as well as Python vari- ables and objects. This technique functions as a generalized calculator (Cobbe et al., 2021) that can perform arbitrary symbolic computations and pass their results to the Follower.
self:
Self-checking (Fig. 2C). While programs often ensure correctness by construction, some problems cannot be verified until generation is complete. In other cases, it may still be preferable to use guess-and-check over constrained generation, or to catch bugs in the in- ference logic. For this reason, the Planner defines distinguished check() method, which (like everything it generates) can make use external libraries.
Experiments
4.1 Domains
Constrained generation. We evaluate DISCIPL COLLIE-v1 (Yao et al., 2024), con- strained generation benchmark designed as challenge dataset for LMs. Tasks in COLLIE (Table 2) are composed from formal grammar of constraints specified at multiple levels of text granularity; here, we focus on the sentence and paragraph levels. The combinatorial nature of the grammar is what makes COLLIE tasks challenging Yao et al. (2024) find that overall performance ranges from 16.3% (Alpaca-7B) to 50.9% (GPT-4).
Puzzles. To evaluate generalization beyond tasks that be defined with grammar, we construct mini-dataset of challenging naturalistic generation tasks. PUZZLES (Table 5) consists of four task types that require models to compose structured poetry, write a grant proposal abstract subject to various constraints, generate an ingredients list that meets monetary budget, and plan a multi-day travel itinerary.
4.2 Evaluation Metrics
Validity. We are interested in building systems that effectively leverage test-time compute to improve their answers to hard-to-answer queries. Accordingly, we focus on expected Pass@1, which (unlike Pass@k) models a setting that does not assume access to an oracle verifier. We implement generalized version of the standard unbiased Pass@k estimator (Brown et al., 2024; Chen al., 2021) that uses the weights computed during inference (if available) and uniform weights for baselines (App. D).
Coherency. As highlighted in the example Fig. 1, the introduction of constraints can impact the fluency of generated text. To assess coherency, we adopt the LLMaas-juudee evaluation from Yao et al. (2024) using GPT--o-mini with a zero-shot prompt (App. E). While coherency could also be assessed with human ratings, this approach offers a scalable, affordable, and reasonably reliable measure of the overall text quality.
4.3 Experiment Setup
Our experiments evaluate whether DISCIPL can generate effective and efficient inference programs for solving unseen tasks in stratified tros-vvaidatiin setup. We begin by man- ually writing an example inference model for a single instance of each task type in COLLIE and PUZZLES. We few-shot prompt the Planner LM with the examples from the corre- sponding domain (App. K.2), holding out the model corresponding to the target task type. (For PUZZLES, we also include the examples from COLLIE.)

---

Published as a conference paper at COLM 2025
Planner and Follower LMs. The goal of the Planner is to generate an InferenceModel subclass that implements various methods, including step() and check(). We use a system prompt in the style of README. md (App. K.1, which also serves as condensed tutorial on LLAMPPL for the interested reader) to instruct to the Planner how to write inference models. We instantiate the Planner with capable LM (gpt-40-2024-00 -6; OpenAI, 2024a) that can attend to detailed instructions; however, the Planner does not itself perform any reasoning outside generating Python code. Except where otherwise indicated in $5.3, we instantiate the Follower with Llama-3 3. -II--rrutc (Grattafiori et al., 2024).
Baselines. We benchmark DISCIPL against several baselines:
Follower-only: We prompt Mr to directly solve the task, sampling N independent
completions with temperature=1.0 We also run a variant with stochastic beam search where N controls the beam size.
Planner-only: We prompt Mp to solve the task both directly and with chain-of- thought (CoT; App. F.1). For comparison, we also benchmark smaller model 100-44--inii20224-20
in the same family.
Reasoning model: As a representative frontier CoT reasoning model, we evaluate ol (01-2024-12-17, OpenAT, 2024b). We note that ol is both theoretically and empirically more expensive than DISCIPL (see App. J for a detailed analysis of compute costs). Ac- cordingly, ol is primarily intended skyline on task performance, and is not directly comparable in terms of resource efficiency.
Expert programs. We evaluate a variant where we grant the Planner access to the ref- erence implementation corresponding to the target task. This oracle condition (denoted DISCIPL*) evaluates the extent which the Planner is able to recover the expert programs.
Results and Analysis
We report the main results of our experiments in Table 1 with figures breaking down sen- tence (Fig. 3), paragraph (Fig. 8), and PUZzLES (Fig. 9) performance by task.
5.1 Validity
Follower-only baseline is unreliable. Perhaps unsurprisingly given its size, Llama-1B only weakly able to follow the task instructions, scoring poorly on COLLIE sentence tasks @Pass@1=0.077 and PUZZl.E (Pass@1=0.08) and moderately on COLLIE paragraph (Pass@1=0.38) tasks. Notably, off-the-shelf decoding methods (e.g, beam search), which optimize for sequence log probability, do not improve performance on the constrained generation objective.
Planner-only baseline performance is task-dependent. While GPT-4o and GPT-4o-mini are nearly perfect at including specific words (e.g., sent_04), they struggle to position key- words at locations other than the start of sentence (e.g., sent_e2, para_05) and cannot reliably count characters (e.g., sent_01, sent_03), CoT prompting yields small improve- ments COLLIE sentences and PUZZLES; however, the reasoning is still incorrect in many cases (e.g,, App. F.2). These results are in line with Yao et al. (2024), who found that GPT-4 performed poorly on these tasks.
Reasoning model shows strong (though not perfect) performance. With the benefit of ample test-time compute, ol achieves near-ceiling Pass@1 on COLLIE tasks. Never- theless, Pass@1 for ol dips below 1.0 on several tasks (sent_01, para_03, para_05, and ingredients.list)
DISCIPL significantly boosts performance across domains. On all tasks, DISCIPL-SMC and DIsCIPL-IS far exceed the Follower-only baselines, enabling various skills like char- acter counting and word positioning that are entirely absent from Llama-3.2-1B. On para- graph tasks, DISCIPL closes most of the gap between the Follower and Planner perfor- mance, bringing Llama up to GPT-40/ G level (Fig. 8). Meanwhile, on sentence
Following OpenAl's guidelines, we query ol with max max_ aax_tokens=25000 Due to cost, we only query ol once per task instance.
7

---

DISCIPL knows when is wrong. Across all tasks, autogenerated check methods closely match ground truth verifiers (Fig. 5). However, rejection sampling (RS) produces Published as a conference paper at COLM 2025
Pass @1 for N=32
Pass@1 for varying
1.0
1.0
Pass@1
0.6
Pass@1
0.6
0.4
0.4
0.2
0.2
0.0
0.0
DiCIP
Follower Panner 01
12
4
16
32
03
1.0
Passig
0.8
0.64
0.4-
0.2
0.0
12.4
16
36
12:
SMC
DisCIPL-IS
DisCIPL-RS
Lama-33221B
GPT-4o-mini
DISCIPL*SMC
DIsCIPLYIS
DisCIPL'-RS
Lama-33224
GPT-4o
Figure 3: Validity on COLLIE Sentence-Level Tasks. (Top left) Average pass rate (Pass@1) with fixed inference budget (N=32) corresponding to the number of samples or particles. (Top right) Pass@1 un- der varying sample budget. While pass rates vary by task (botfom row), overall DISCIPL surpasses both the Follower and Planner baselines and approaches the performance strong reasoning model (o1). Moreover, the performance of autogenerated inference programs nearly matches that of expert programs (DISCIPL.").
COLLIE Sentence
COLLIE Paragraph
PUZZLES Coherency
Method
Sampling Method
Passãl
Coherency
Pass@1
Coherency
DisCIPL
SMC
Llama-3.2-18
0.76
0.69
6.72
0.42
6.40
Importance (IS)
Llama-3.2-1B
0.84
5.07
0.66
5.89
0.38
5.65
Rejection (RS)
Llama-3.2-10
0,20
8.22
0.62
8.48
0.25
8.85
Follower-only
Standard Beam Search
Llamm-3.2-118
0.07
8.12
0.38
8.28
0.08
8.60
Llama-3.2-18
0.08
8.93
0.38
8.96
0.03
8.68
Planner-only
Standard
GPT-to-mini
0.37
9:00
0.72
9,10
0.27
9:20
GPT-4o
0.25
GPT-4o (CoT)
0.46
8.73
0.76
8.79
0.30
9.28
Reasoning
Standard
ul
0.96
7.69
0.95
8.53
0.82
9.00
Table 1: Summary of results from all experiments. Pass@1 measures expected validity. Coherency (10-point scale) measures overall fluency for all generations (including invalid ones).
tasks, DISCIPL surpasses both Follower and Planner baselines, and approaches ol-level performance (Fig. 3). Finally, on PUZZLES, DISCIPL on average outperforms both Planner and Follower baselines, though performance varies between tasks and there is bigger gap between autogenerated and expert programs.
substantially fewer valid generations than combining step() and check (SMC and IS).
5.2
Coherency
What inference algorithms can we leverage to push the Pareto frontier of coherency valid- ity? Our results suggest that SMC (Fig. 4) is well-suited to this goal-in our experiments, SMC consistently achieves higher coherency scores than IS for comparable Pass@1. One way of understanding this result is through Fig. 1, which illustrates how SMC resampling filters out particles that satisfy constraints but introduce disfluencies. This also helps to explain why, on some tasks, the Pass@1 curves for DISCIPL-SMC appear relatively flat: in
8

---

Published as a conference paper at COLM 2025
DISIPL-SMC
DiSCPLIS
DUCPLAS
GP1-4
220 per LO cen OO san,
Cohernnc Sennyyccosss Score
5.0
4.5
4.0-
DMC DISCIPLIS
2.5
16
N Particles
Camerancy
Coneeenicy
Conorenicy
Cuhorenny
Figure 4: Coherency. (Left) SMC resampling leads to more coherent generations and scales with com- pute budget. (Right) Distributions of coherency scores on COLLIE sentence tasks (densities are nor- malized per-subplot). While non-reasoning LMs produce coherent but invalid text (red), DISCIPL, enables Llama to satisfy constraints (green) with improving coherency as the particle count scales.
RAI
Predicted
Predided
Predicted
Predicted
Predictdd
Predicted
Predicted
Prudkted
Preditted
(a) COLLIE Sentences
(b) COLLIE Paragraphs
(c) PUZZLES
Figure 5:
Classification accuracy of autogenerated check() methods. Across domains, DISCIPL aligns closely with the ground truth verifiers. (Ø denotes null results due to runtime errors; App. G.)
these cases, the inference programs ensure validity by construction, the benefits of scaling show up instead in the coherency scores.
While using separate proposal and prior ($3.3) generally improves coherency, in some cases, it may backfire: for instance, on sent_04 we see that Pass@1 decreases with N (Fig. 3). For this task, the Planner LM showed strong inductive bias towards word-level step, even when provided expert programs. However, this strategy will filter out particles containing target words, which have low probability under the prior. A smarter Planner could easily avoid this issue by choosing a step granularity that better aligns with the constraints (e.g., sampling multiple words until target is generated).
Scaling the Follower Model
While our main experiments instantiate DisCIPL with a specific Follower LM (Llama-3.2- 1B), in other settings, we may wish to utilize more capable Follower models. Here, we explore the effects of two different aspects of model choice- size and architecture-using COLLIE controlled setting characterize performance tradeoffs.
Model Size (Fig. 6, top) First, we hold the architecture constant and scale up the size of the Follower from 1B + 3B + 8B within the Llama-3 family.² As expected, the baselines improve with model size; nevertheless, for sentence tasks, these still significantly under- perform DISCIPL-SMC/IS. Moreover, we find that baseline Llama-3 coherency scales in- versely with Pass@1; intuitively, the larger Llama models appear to try harder to adhere to the constraints, which results in less natural text. In contrast, under DISCIPL-SMC/ Pass@1 and coherency improve simultaneously with Follower size (see App. B for full numbers). These results illustrate that even for fixed Planner LM, our inference programs nevertheless benefit from being executed by more capable Followers.
Model Family (Fig. 6, bottom) We instantiate DISCIPL with Qwen3 (Yang et al., 2025), newer LM that outperforms Llama-3 on various benchmarks and also provides lightweight models of comparable size. On sentence tasks, find that Qwen3-i.7B moderately out- performs Llama-3.2-1B at baseline, and that these benefits translate to DISCIPL (+0.07 Pass@1). (On paragraph tasks, do not find significant difference between models.) As these results highlight, DISCIPL reflects the capabilities of the underlying Follower LM, and stands to benefit as advances in distillation yield increasingly capable small LMs.
2ince the largest text-only model in the Llama-3.2 family is 3B parameters, we use Llama-3,1 1 for the 8B model. This reversion may explain apparent inconsistencies in scaling trends, such as the drop from 3B 8B for DISCIPL-RS seen in Fig. 6(a).

---

Published as a conference paper at COLM 2025
0.8
0.8
Pass@1
0.6
Pass@1
0.6
Method:
DISCIPL-SMI
0.4
0.4
DISCIPL-R
DISCIPL-BR L-RS
0.2-
Sampling
Bearn Search
18
3B
88
3B
88
Follower Model Parameters (Llama-3 x-Instruct)
Follower Model Parameters
(a) COLLIE Sentences: Scaling Llama
(b) COLLIE Paragraphs: Scaling Llama
0.8
2.6
Po0981
0.6
Pccag1
9.6
Follower Model: Llama-3.2-1B
Qwen3-1.7B
0.-
0.2
DSCIPSSO sanc uisciruis Duciraas
Sansling beam Search
DSCIP--SME DiscPLu DisciPLSs Sampling Beam Search
COLLIE Sentences: Llama
Qwen
(d) COLLIE Paragraphs: Llama Qwen
Figure 6: Characterizing effects of Follower model size and architecture. (Top row) Scaling size for fixed model family (Llama-3 1B, 3B, and 8B). (Bottom row) Comparing two LMs with similar size (Llama-3 vs. Qwen3).
6 Limitations, Future Work, and Conclusions
The results presented here represent an initial validation of the broad framework outlined in $3. In this section, we acknowledge several limitations of the current instantiation of DISCIPL and highlight several promising directions for follow-up work.
Generalization. In addition to other constrained generation settings (e-g., Lin et al., 2020; Zhou et al., 2023a), self-steering can also be extended to mathematical reasoning (Lightman et al., 2024; Wang et al., 2024a) as well domains with soft constraints (e.g., steering based on reward models).
Inference Algorithms. While many text generation tasks are amenable sequential in- ference, some problems may be more efficiently solved with backtracking (e.g., MCTS; Coulom, 2007; Kocsis & Szepesvári, 2006) or iterative editing (Welleck et al., 2023), both of which are implementable as extensions to DISCIPL.
Self-Improvement. Since generating inference programs requires non-trivial reasoning, we instantiate the Planner with larger and more capable LM than the Follower. How- ever, in principle, we could use the same LM to play these two roles. This recursive "self- steering" setup could learn by bootstrapping (e.g., Zelikman et al., 2022) or library learning (Ellis et al., 2021; Grand et al., 2024).
In conclusion, in this work, solving with language models that orchestrates inference-tima compute by writing and executing inference programs. We believe our approach offers unifying probabilistic per- spective on inference-time computation with LMs, as well as a practical tools for automat- ing inference engineering. Our results demonstrate the potential of self-steering to enable accurate and efficient parallel inference with populations of small LMs, with performance rivaling much larger and more costly frontier models. In future work, we aim generalize self-steering language models to new problem domains and inference patterns.
introduced DISCIPL, general framework for problem-
10

---

Published as a conference paper at COLM 2025
Acknozoledgments
We would like to thank Timothy O'Donnell, João Loula, Ced Zhang, Cédric Colas, Noah Goodman, Aniruddha Nrusimha, Linlu Qiu, Tan Zhi-Xuan, and Lionel Wong for helpful discussions and feedback. Special thanks to Ben LeBrun and the GenLM team for engi- neering support.
The authors gratefully acknowledge support from the MIT Quest for Intelligence, the MIT- IBM Watson AI Lab, the Intel Corporation, AFOSR, DARPA, ONR, and the National Sci- ence Foundation (NSF) under grants CCF-2217064 and IIS-2238240. G.G. is supported by a NSF Graduate Research Fellowship under Grant No. 2141064. J.B.T. supported by AFOSR, the MIT Quest for Intelligence, the MIT-IBM Watson AI Lab, ONR Science of AÍ, and Siegel Family Endowment. V.K.M. and A.K.L. are supported by an anonymous phil- anthropic gift well gifts from Siegel Family Foundation that support the MIT Quest for Intelligence. J.A. is supported by Sloan Research Fellowship. Any opinions, findings, and conclusions or recommendations expressed this material are those of the author(s) and do not necessarily reflect the views of sponsors.
Author Contributions
Gabriel Grand (primary author): Research conception, narrative development, software design and implementation, experiments, analysis of results, figure-making, writing.
Joshua B. Tenenbaum: Senior mentorship, narrative development.
Vikash K. Mansinghka: Senior mentorship, narrative development.
Alexander K. Lew: Senior mentorship, research conception, narrative development, math- ematical formalisms, analysis of results, figure-making writing.
Jacob Andreas: Senior mentorship, research conception, narrative development, analysis of results, writing.
11

---

Published as a conference paper at COLM 2025
References
Afra Amini, Li Du, and Ryan Cotterell. Structured voronoi sampling. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances Neural Information Processing Systems 36: Annual Conference on Neu- ral Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, Decem- ber 10 16, 2023, 2023. URL http: /ttp:///apppeeap/ae/eeeeeeeeese/ nips. 64ae05e3f www.eaaeeeeee5888 2allaaaf7772boffff4222---r-rrrr-
/ttpr//essssaaae/223//////////// html.
Thomas Ball, Shuo Chen, and Cormac Herley, Can We Count on LLMs? The Fixed-Effect Fallacy and Claims of GPT-4 Capabilities, 2024. URL https://arxivv argg 07638.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, and Azalia Mirhoseini. Large Language Monkeys: Scaling Inference Compute with Repeated Sampling, 2024. URL https: http://aaavvvvoooaaeeeoaaa .rg. httg//b///211/// 21787.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Élizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, An- drew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob Mc- Grew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. Evaluat- ing Large Language Models Trained on Code, 2021, URL https: / http///aiiivvie///iv/eee//e/eel/ wwwpxxiv.og/bb////// 03374.
Yew Ken Chia, Pengfei Hong, Lidong Bing, and Soujanya Poria. InstructEval: To- wards holistic evaluation of instruction-tunee
large language models. In Antonio Va- lerio Miceli-Barone, Fazl Barez, Shay Cohen, Elena Voita, Ulrich Germann, and Michal Lukasik (eds.), Proceedings of the First edition of the Workshop on the Scaling Behavior of Large Language Models (SCALE-LLM 2024), pp. 35-64, St. Julian's, Malta, 2024. Association for Computational Linguistics. URL ht hatp::://aaaaaaiiie aclaathologgyy....o org/ 2024. scalellm-1.. 1.4.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training Verifiers to Solve Math Word Problems, 2021. URL
https://aaxiv..or/abb/21121 14168.
Rémi Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. In H. Jaap van den Herik, Paolo Ciancarini, and H. H. L. M. (Jeroen) Donkers (eds.), Computers and Games, pp. 72-83, Berlin, Heidelberg, 2007. Springer. ISBN 978-3-540- 75538-8. doi: 10.1007/978-3
Mehul Damani, Idan Shenfeld, Andi Peng, Andreea Bobu, and Jacob Andreas. Learning How Hard to Think: Input-Adaptive Allocation of LM Computation, 2024. URL https: //arxiv. 22100 0470704777
DeepSeek-AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Jun- long J. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang, Lecong Zhang, Liang Zhao, Litong Wang, Liyue
12

---

Published as a conference paper at COLM 2025
Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang, Peng Zhang, Qiancheng Wang, Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, R. J. Chen, R. L. Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang, Shuiping Yu, Shunfeng Zhou, Shuting Pan, S. S. Li, Shuang Zhou, Shao- qing Wu, Shengfeng Ye, Tao Yun, Tian Pei, lianyu Sun, T. Wang, Wangding Zeng, Wan- jia Zhao, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang, W. L. Xiao, Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X. Q Li, Xi- angyue Jin, Xiaojin Shen, Xiaosha Chen, Xiaowen Sun, Xiaoxiang Wang, Xinnan Song, Xinyi Zhou, Xianzu Wang, Xinxia Shan, K. Li, Y.Q. Wang, Y. X. Wei, Yang Zhang, Yanhong Xu, Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Wang, Yi Yu, Yichao Zhang, Yifan Shi, Yiliang Xiong, Ying He, Yishi Piao, Yisong Wang, Yixuan Tan, Yiyang Ma, Yiyuan Liu, Yongqiang Guo, Yuan Ou, Yuduan Wang, Yue Gong, Yuheng Zou, Yujia He, Yunfan Xiong, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Y. X. Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng, Yuchen Zhu, Yunxian Ma, Ying Tang, Yukun Zha, Yuting Yan, Z. Z. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu WU, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song, Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang. DeepSeek-RI: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning, 2025, URL https: / //axxiv orgo 250/ 12948.
David Dohan, Winnie Xu, Aitor Lewkowyez, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A. Saurous, Jascha Sohl-dickstein, Kevin Murphy, and Charles Sutton. Language Model Cascades, 2022. URL https://arxiv. org/abs/2207.1125 10342.
Arnaud Doucet, Nando de Freitas, and Neil Gordon. Sequential Monte Carlo Methods in Practice Springer Science & Business Media, 2001. ISBN 978-0-387-95146--1
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke He- witt, Luc Cary, Armando Solar-Lezama, and Joshua Tenenbaum. DreamCoder: boot-
strapping inductive program synthesis with wake-sleep library learning. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pp. 835- 850, Virtual Canada, 2021. ACM. ISBN 978-1-4503-8391-2 doi: 10.1145 33533333333440038 URL https: //d. acm. wrg.aco....a...oooo.ooooooooo./o org wtwp////////oo/////////////////t 11411...114444444811 3454080.
Shengyu Feng, Xiang Kong, Shuang Ma, Aonan Zhang, Dong Yin, Chong Wang, Ruom- ing Pang, and Yiming Yang. Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlo, 2024. URL https: https://arxxv..rg/abbbb
abgg 01920.
Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel. Promptbreeder: Self-referential self-improvement via prompt evolution. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Aus- tria, July 21-27, 2024. OpenReview.net, 2024. URL https://openrevieww wtt.eewwwwieeeeommiiiiii.. 9ZxnPZGmPU.
Kanishk Gandhi, Denise H J Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah Goodman. Stream of search (sos): Learning to search in language. In First Conference on Language Modeling, 2024. URL https: //tp://///ppeeeiieww wtw.ee...eeffruumiiitt 2cop2jmQVL.
Noah Goodman, Vikash Mansinghka, Daniel M. Roy, Keith Bonawitz, and Joshua B. Tenen- baum. Church: a language for generative models, 2014. URL http://arxxv.org/aae 1206. 1206.3255. arXiv: 1266:322 [cs].
Gabriel Grand, Lionel Wong, Matthew Bowers, Theo X. Olausson, Muxin Liu, Joshua B. Tenenbaum, and Jacob Andreas. LILO: learning interpretable libraries by compress- ing and documenting code. In The Twelfth International Conference on Learning Repre- sentations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL
https://openreeviw.. http://www.eeeooooiiieoooooo/oee
13

---

Published as a conference paper at COLM 2025
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Ka- dian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aure- lien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cris- tian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius, Daniel Song, Danielle Pintz, Danny Livshits, Danny Wyatt, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Parcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Francisco Guzmán, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Govind Thattai, Graeme Nail, Gregoire Mialon, Guan Pang, Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, lliyan Zarov, Imanol Arrieta lbarra, Isabel Kloumann, Ishan Misra, Ivan Eytimov, Jack Zhang, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang, Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Alwala, Karthik Prasad, Kartikeya Upasani, Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, Khalid El-Arini, Krithika Iyer, Kshitiz Malik, Kuenley Chiu, Kunal Bhalla, Kushal Lakhotia, Lauren -eantala-Yerr, Laurens van der Maaten, Lawrence Chen, Liang Tan, Liz Jenkins, Louis Martin, Lovish Madaan, Lubo Malo, Lukas Blecher, Lukas Landzaat, Luke de Oliveira, Madeline Muzzi, Ma- hesh Pasupuleti, Mannat Singh, Manohar Paluri, Marcin Kardas, Maria Tsimpoukelli, Mathew Oldham, Mathieu Rita, Maya Pavlova, Melanie Kambadur, Mike Lewis, Min Si, Mitesh Kumar Singh, Mona Hassan, Naman Goyal, Narjes Torabi, Nikolay Bashlykov, Nikolay Bogoychev, Niladri Chatterji, Ning Zhang, Olivier Duchenne, Ónur Çelebi, Patrick Alrassy, Pengchuan Zhang, Pengwei Li, Petar Vasic, Peter Weng, Prajjwal Bhar- gava, Pratik Dubal, Praveen Krishnan, Punit Singh Koura, Puxin Xu, Qing He, Qingxiao Dong, Ragavan Srinivasan, Raj Ganapathy, Ramon Calderer, Ricardo Silveira Cabral, Robert Stojnic, Roberta Raileanu, Rohan Maheswari, Rohit Girdhar, Rohit Patel, Romain Sauvestre, Ronnie Polidoro, Roshan Sumbaly, Ross Taylor, Ruan Silva, Rui Hou, Rui Wang, Saghar Hosseini, Sahana Chennabasappa, Sanjay Singh, Sean Bell, Seohyun So- nia Kim, Sergey Edunov, Shaoliang Nie, Sharan Narang, Sharath Raparthy, Sheng Shen, Shengye Wan, Shruti Bhosale, Shun Zhang, Simon Vandenhende, Soumya Batra, Spencer Whitman, Sten Sootla, Stephane Collot, Suchin Gururangan, Sydney Borodinsky, Tamar Herman, Tara Fowler, Tarek Sheasha, Thomas Georgiou, Thomas Scialom, Tobias Speck- bacher, Todor Mihaylov, Tong Xiao, Ujjwal Karn, Vedanuj Goswami, Vibhor Gupta, Vi- gnesh Ramanathan, Viktor Kerkez, Vincent Gonguet, Virginie Do, Vish Vogeti, Vitor Al- biero, Vladan Petrovic, Weiwei Chu, Wenhan Xiong, Wenyin Fu, Whitney Meers, Xavier Martinet, Xiaodong Wang, Xiaofang Wang, Xiaoqing Ellen Tan, Xide Xía, Xinfeng Xie, Xuchao Jia, Xuewei Wang. Yaelle Goldschlag, Yashesh Gaur, Yasmine Babaei, Yi Wen, Yiwen Song, Yuchen Zhang, Yue Li, Yuning Mao, Zacharie Delpierre Coudert, Zheng Yan, Zhengxing Chen, Zoe Papakipos, Aaditya Singh, Aayushi Srivastava, Abha Jain, Adam Kelsey, Adam Shajnfeld, Adithya Gangidi, Adolfo Victoria, Ahuva Goldstand, Ajay Menon, Ajay Sharma, Alex Boesenberg, Alexei Baevski, Allie Feinstein, Amanda Kallet, Amit Sangani, Amos Teo, Anam Yunus, Andrei Lupu, Andres Alvarado, Andrew Caples, Andrew Gu, Andrew Ho, Andrew Poulton, Andrew Ryan, Ankit Ramchan- dani, Annie Dong, Annie Franco, Anuj Goyal, Aparajita Saraf, Arkabandhu Chowd- Ashley Gabriel, Ashwin Bharambe, Assaf Eisenman, Azadeh Yazdan, Beau James, Ben Maurer, Benjamin Leonhardi, Bernie Huang, Beth Loyd, Beto De Paola, Bhargavi Paranjape, Bing Liu, Bo Wu, Boyu Ni, Braden Hancock, Bram Wasti, Brandon Spence, Brani Stojkovic, Brian Gamido, Britt Montalvo, Carl Parker, Carly Burton, Catalina Mejia, Ce Liu, Changhan Wang, Changkyu Kim, Chao Zhou, Chester Hu, Ching- Chu, Chris Cai, Chris Tindal, Christoph Feichtenhofer, Cynthia Gao, Damon Civin, Dana Beaty, Daniel Kreymer, Daniel Li, David Adkins, David Xu, Davide Testuggine, Delia David, Devi Parikh, Diana Liskovich, Didem Foss, Dingkang Wang, Duc Le, Dustin Hol- land, Edward Dowling, Eissa Jamil, Elaine Montgomery, Eleonora Presani, Emily Hahn, Emily Wood, Tric Le, Erik Brinkman, Esteban Arcaute, Evan Dunbar, Evan Smoth-
14

---

Published as a conference paper at COLM 2025
ers, Fei Sun, Felix Kreuk, Feng Tian, Filippos Kokkinos, Firat Ozgenel, Francesco Cag- gioni, Frank Kanayet, Frank Seide, Gabriela Medina Florez, Gabriella Schwarz, Gada Badeer, Georgia Swee, Gil Halpem, Grant Herman, Grigory Sizov, Guangyi, Zhang, Guna Lakshminarayanan, Hakan Inan, Hamid Shojanazeri, Han Zou, Hannah Wang, Hanwen Zha, Haroun Habeeb, Harrison Rudolph, Helen Suk, Henry Aspegren, Hunter Goldman, Hongyuan Zhan, Ibrahim Damlaj, Igor Molybog, Igor Tufanov, llias Leon- tiadis, Irina-Elena Veliche, Itai Gat, Jake Weissman, James Geboski, James Kohli, Jan- ice Lam, Japhet Asher, Jean-Baptiste Gaya, Jeff Marcus, Jeff Tang, Jennifer Chan, Jenny Zhen, Jeremy Reizenstein, Jeremy Teboul, Jessica Zhong, Jian Jin, Jingyi Yang, Joe Cum- mings, Jon Carvill, Jon Shepard, Jonathan McPhie, Jonathan Torres, Josh Ginsburg, Jun- jie Wang, Kai Wu, Kam Hou U, Karan Saxena, Kartikay Khandelwal, Katayoun Zand, Kathy Matosich, Kaushik Veeraraghavan, Kelly Michelena, Keqian Li, Kiran Jagadeesh, Kun Huang, Kunal Chawla, Kyle Huang, Lailin Chen, Lakshya Garg, Lavender A, Le- andro Silva, Lee Bell, Lei Zhang, Liangpeng Guo, Licheng Yu, Liron Moshkovich, Luca Wehrstedt, Madian Khabsa, Manav Avalani, Manish Bhatt, Martynas Mankus, Matan Hasson, Matthew Lennie, Matthias Reso, Maxim Groshev, Maxim Naumov, Maya Lathi, Meghan Keneally, Miao Liu, Michael L. Seltzer, Michal Valko, Michelle Restrepo, Mi- hir Patel, Mik Vyatskov, Mikayel Samvelyan, Mike Clark, Mike Macey, Mike Wang, Miquel Jubert Hermoso, Mo Metanat, Mohammad Rastegari, Munish Bansal, Nand- hini Santhanam, Natascha Parks, Natasha White, Navyata Bawa, Nayan Singhal, Nick Egebo, Nicolas Usunier, Nikhil Mehta, Nikolay Pavlovich Laptev, Ning Dong, Norman Cheng, Oleg Chernoguz, Olivia Hart, Omkar Salpekar, Ozlem Kalínli, Parkin Kent, Parth Parekh, Paul Saab, Pavan Balaji, Pedro Rittner, Philip Bontrager, Pierre Roux, Piotr Dol- lar, Polina Zvyagina, Prashant Ratanchandani, Pritish Yuvraj, Qian Liang, Rachad Alao, Rachel Rodriguez, Rafi Ayub, Raghotham Murthy, Raghu Nayani, Rahul Mitra, Ran- gaprabhu Parthasarathy, Raymond Li, Rebekkah Hogan, Robin Battey, Rocky Wang, Russ Howes, Ruty Rinott, Sachin Mehta, Sachin Siby, Sai Jayesh Bondu, Samyak Datta, Sara Chugh, Sara Hunt, Sargun Dhillon, Sasha Sidorov, Satadru Pan, Saurabh Mahajan, Saurabh Verma, Seiji Yamamoto, Sharadh Ramaswamy, Shaun Lindsay, Shaun Lindsay, Sheng Feng, Shenghao Lin, Shengxin Cindy Zha, Shishir Patil, Shiva Shankar, Shugiang Zhang, Shuqiang Zhang, Sinong Wang, Sneha Agarwal, Soji Sajuyigbe, Soumith Chin- tala, Stephanie Max, Stephen Chen, Steve Kehoe, Steve Satterfield, Sudarshan Govin- daprasad, Sumit Gupta, Summer Deng, Sungmin Cho, Sunny Virk, Suraj Subramanian, Sy Choudhury, Sydney Goldman, Tal Remez, Tamar Glaser, Tamara Best, Thilo Koehler, Thomas Robínson, Tianhe Li, Tianjun Zhang, Tim Matthews, Timothy Chou, Tzook Shaked, Varun Vontimitta, Victoria Ajayi, Victoria Montanez, Vijai Mohan, Vinay Satish Kumar, Vishal Mangla, Vlad Ionescu, Vlad Poenaru, Vlad Tiberiu Mihailescu, Vladimir Ivanov, Wei Li, Wenchen Wang, Wenwen Jiang, Wes Bouaziz, Will Constable, Xiaocheng Tang, Xiaojian Wu, Xiaolan Wang, Xilun Wu, Xinbo Gao, Yaniv Kleinman, Yanjun Chen, Ye Hu, Ye Jia, Ye Qi, Yenda Li, Yilin Zhang, Ying Zhang, Yossi Adi, Youngjin Nam, Yu, Wang, Yu Zhao, Yuchen Hao, Yundi Qian, Yunlu Li, Yuzi He, Zach Rait, Zachary Vetoto, Zef Rosnbrick, Zhaoduo Wen, Zhenyu Yang, Zhiwei Zhao, and Zhiyu Ma. The Llama Herd of Models, 2024. URL https: //arxiv www.wxiiv.r////ooo org/ hergg/bb/2400) 2400./240..222 217833.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring Mathematical Problem Solving With the MATH Dataset, 2021. URL https: /tttp::///rxvv... wwtpxxivvorrg//bbee/ wtwp////////..../////// 03377744.
Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming, Revised Reprint. Elsevier, 2012. ISBN 978-0-12-397795-3, Google-Books-ID: vfvPtSZ7R7QC.
Chris Hokamp and Qun Liu. Lexically constrained decoding for sequence generation using grid beam search. In Regina Barzilay and Min-Yen Kan (eds.), Proceedings of the 55th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1535-1546, Vancouver, Canada, 2017. Association for Computational Linguistics. doi: 1118653/v//11//
URL
Or Honovich, Uri Shaham, Samuel R. Bowman, and Omer Levy. Instruction induction: From few examples to natural language task descriptions. In Anna Rogers, Jordan Boyd- Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association
15

---

Published as a conference paper at COLM 2025
for Computational Linguistics (Volume 1: Long Papers), PP. 1935-1952, Toronto, Canada, 2023. Association for Computational Linguistics. doi: 10.18653/ (0.18653/v1/2444 wwtp///2..a.llooo...00... URL https://acllanthoo.gg
htrrg/222...m acl-long. 108.
Shengran Hu, Cong Lu, and Jeff Clune. Automated Design of Agentic Systems, 2024. URL wwtp:///////.../... https://arrxv..rrr/////4/4..
08435.
Yuxin Jiang, Yufei Wang, Xingshan Zeng, Wanjun Zhong, Liangyou Li, Fei Mi, Lifeng Shang, Xin Jiang, Qun Liu, and Wei Wang. FellowBench: A Multi-level Fine-grained Constraints Following Benchmark for Large Language Models, 2023. URL https:
warxii..rrg/bb.... /2110 20410.
Tian Jin, Ellie Y. Cheng, Zack Ankner, Nikunj Saunshi, Blake M. Elias, Amir Yazdanbakhsh, Jonathan Ragan-Kelley, Suvinay Subramanian, and Michael Carbin. Learning to Keep Promise: Scaling Language Model Decoding Parallelism with Learned Asynchronous Decoding, 2025. URL https://arxis: wwww.oog//bba prrg/abs//502.. 11517.
Daniel Kahneman. Thinking, Fast and Slow. Macmillan, 2011. ISBN 978-0-374-27563-1. Google-Books-ID: SHyzzuCnuv8C.
Andrej Karpathy. Jagged Intelligence The word came up with to describe the (strange, unintuitive) fact that state of the art LLMs can both perform extremely impressive tasks (e.g. solve complex math problems) while simultancousll struggle with some very dumb problems., 2024. URL https: http:///ww.oockaaatt////////////
Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines, 2023. URL https://arxiv. org/ abs/2310.0373
Levente Kocsis and Csaba Szepesvári. Bandit Based Monte-Carlo Planning- In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou (eds.), Machine Learning: F.C.I. 2006, pp. 282-293, Berlin, Heidelberg, 2006. Springer. ISBN 978-3-540-44056-55 doi: 10.1007/ 11871842 29.
Terry Koo, Frederick Liu, and Luheng He. Automata-based constraints for language model decoding. In First Conference on Language Modeling, 2024. URL https: http:::////pppevviiiieee net/ forum?id=B0Bdbllyg 1myz...
Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. Gradient-based constrained sampling from language models. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 2251-2277, Abu Dhabi, United Arab Emirates, 2022. Association for Computational Linguistics. doi: 10.18653/v1 hwtp//2.eemnlppa/ee 144. URL https: https:://aclaattholoog org/ 2022, emnlp-main. 144.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient Memory Management for Large Language Model Serving with PagedAttenttin,, 2023. URL https://arxiv.. org/ abs/2309.06188 06180.
Lucas Lehnert, Sainbayar Sukhbaatar, Dilia Su, Qinqing Zheng, Paul McVay, Michael Rab- bat, and Yuandong Tian. Beyond A+: Better planning with transformers via search dynamics bootstrapping. In First Conference on Language Modeling, 2024. URL https: //tpenreview.rre wttp://www....ooooo////ottttoooe
Alexander K Lew, Michael Henry Tessler, Vikash K Mansinghka, and Joshua B Tenenbaum. Leveraging Unstructured Statistical Knowledge in Probabilistic Language of Thought. Proceedings of the Annual Meeting of the Cognitive Science Society, pp. 2020.
Alexander K. Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash K. Mansinghka. Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs, 2023,
URL https://arxiv orgi abs///////// 22366 03081.
16

---

Published as a conference paper at COLM 2025
Michael Y. Li, Emily B. Fox, and Noah D. Goodman. Automated statistical model discovery with language models. In Forty-first International Conference on Machine Learning, ICML 2024, Viemna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https: //ttpr///pperreview. net/forum?id-B5596MMaa.
Xiang Li, John Thickstun, Ishaan Gulrajani, Percy Liang, and Tatsunori B. Hashimoto. Diffusion-Im improves controllable text generation. In Sanmi Koyejo, S. Mo- hamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 De- cember 2022, 2022. URL http:::/ppprrsmmeee wttp:ccccppppaleeeeeeee filles/paper//222/// beebb5555855e6655ceeeee3358 Abstract- html.
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Tlya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https://openrevveww wttpi/ewwwee//ffrum id=v8LópN6E0i.
Bill Yuchen Lin, Wangchunshu Zhou, Ming Shen, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. CommonGen: A constrained text generation challenge for gener- ative commonsense reasoning. In Trevor Cohn, Yulan He, and Yang Liu (eds.), Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 1823-1840, Online, 2020. Association for Computational Linguistics. doi: 10.18653/ (1188653vl//// w1t//12...inneeeooo findinngs-emnll.leee URL https://acee https://aalanthoolgy org/2020. medingg--enlp... 165.
Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi, and Asli Celikyilmaz. Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding, 2023. URL https://arxiis /rrg// abs/2309. 5028.
João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K. Lew, Tim Vieira, and Timothy J. O'Donnell. Syntactic and semantic con- trol of large language models via sequential monte carlo. In The thirteenth interna- tional conference on learning representations, 2025. URL https://opennrviee..neeet id=xoXn62F2De.
Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. NouroLogic decoding: (un)supervised neural text generation with predicate logic constraints. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani- Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1288-4299 Online, 2021. Association for Computational Linguistics. doi: 10.18653/v 1l/20211221222 naacl-main.335 URL org/ naacl maicc. 339.
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. Neu- roLogic a a'esque decoding: Constrained text generation with lookahead heuristics. In Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz (eds.), Pro- ceedings of the 2022 Conference of the North American Chapter of the Association for Computa- tional Linguisties: Human Language Technologies, pp. 780-799, Seattle, United States, 2022. Association for Computational Linguistics. doi: https: https://aalanthollgg. org.2022.... naacl-man maiin.mm.... 57.
URL
Vikash Mansinghka, Daniel Selsam, and Yura Perov. Venture: a higher-order probabilistic programming platform with programmable inference, 2014. URL http://arxiv. org/ abs/1404.0092 arXiv:1404.0099 [cs].
Vikash K. Mansinghka, Ulrich Schaechtle, Shivam Handa, Alexey Radul, Yutian Chen, and Martin Rinard. Probabilistic programming with programmable inference. In Proceedings
17

---

Published as a conference paper at COLM 2025
of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 603,616, Philadelphia PA USA, 2018. ACM. ISBN 978-1-4503-5698-5. doi: 10.1145/ 3192366.3192409 URL https:///ot http//llllccccccccccc// acm. wrg//oi/1../.oooooooo 11 45/3192366. 0
R. Thomas McCoy, Shunyu Yao, Dan Friedman, Matthew Hardy, and Thomas L. Griffiths. Embers of Autoregression: Understanding Large Language Models Through the Prob- lem They are Trained to Solve, 2023. URL https:///rxiv.. org. httrrg/bb/23099/ 13638.
Xuefei Ning, Zinan Lin, Zixuan Zhou, Zifu Wang, Huazhong Yang, and Yu Wang. Skeleton- of-thought: Prompting llms for efficient parallel generation. In The Twelfth International Conference Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. Open- Review.net, 2024 URL
eww. htt/forrumiddmgg@BBaa
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show Your Work: Scratchpads for Intermediate Computation with Language Models, 2021. URL UBLLnttss//arrrv..or/////22222 0011112.011111 00114.
OpenAl. Hello GPT-4o, 2024a. URL http::://ppeaaa.ccm//innoeee
OpenAl. 01 System Card, 2024b.
URL
https://cdn.openan com/
01 01-syse system-card c222--224111211111 205. pdf.
Jiayi Pan, Xiuyu Li, Long Lian, Charlie Snell, Yifei Zhou, Adam Yala, Trevor Darrell, Kurt Keutzer, and Alane Suhr. Learning Adaptive Parallel Reasoning with Language Models, 2025. URL https: http:///aawww.oo/bb/////////
wrg.abs//50// 15466.
Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova, and Loris D'Antoni. Grammar-aligned decoding. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, Decem- ber 10 - 15, 2024, 2024. URL /taperss mipee www..iicppppp..eeeeeee wwtpaper_files/ppeeeeeepeeeeeeee /tlle//paper//22///// 2bdc2267c3d7d0 523e22 2
htmll.
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In The Tenth International Conference on Learning Representations, ICLR 2022, Vir- fual Event, April 25-29, 2022. OpenReview.net, 2022. URL / eview. net/ forum?i dmm.miiddntttt7JJee...
Matt Post and David Vilar. Fast lexically constrained decoding with dynamic beam allo- cation for neural machine translation. In Marilyn Walker, Heng Ji, and Amanda Stent (eds.), Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pp. 1314-1324, New Orleans, Louisiana, 2018 Association for Computational Linguistics. doi: 10.18653/v1. (6653/v1/N10 /N18-11199
URL http://////ccaaahloooooo org/N18-1119.
Isha Puri, Shivchander Sudalairaj, Guangxuan Xu, Kai Xu, and Akash Srivastava. A Prob- abilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methods, 2025. URL https://arxiv.. hww..oor//bbbo org//bs/25022 01618.
Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. COLD decoding: Energy-based constrained text generation with langevin dynamics. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 De- cember 9, 2022, 2022. URL http: / /twpp//aappppp//e///eeeeeeeeeeea nips wttp:ccccpppplleceeeee filles/paper/222///1/ htt.aaafeaeoeeeeeffffeeaeaeeeeee
waw.:aaa--attttttttt--ooeeeeeeee html..
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R. Bowman. GPQA: Graduate-Level Google- 12022.
Proof Q&A Benchmark, 2023. URL
18

---

Published as a conference paper at COLM 2025
Gleb Rodionov, Roman Garipov, Alina Shutova, George Yakushev, Erik Schultheis, Vage Egiazarian, Anton Sinitsin, Denis Kuznedelev, and Dan Alistarh. Hogwild! Inference: Parallel LLM Generation via Concurrent Attention, 2025. URL https://arxiv.orr//bbs.
06261.
Kevin Roose. When A.I. Passes This Test, Look Out. The New York Times, 2025. ISSN 0362-4331. URL https://www. http://wwww.ttimmms.s/.. ccmm/20255/1//2/teccm//00
ai- bi-test-hunne sestt-humnitys--lsttee etmmm
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: language agents with verbal reinforcement learning- In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neu- ral Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, Decem- ber 10 16, 2023, 2023. URL http: / http//aapprrseee//eee nips wttp:e/s..ipps.ccpppppppeppppepe wttps/ppeeallleeeepeeeeeeeeeee (b446778bb78266554488888888 0000 www.sbbrrtttttteeeaeeeeeeeeeeeee Corpaa/aa0000.0000-------aao----
htt.fflllee/aper/222///aa/ htmml..
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanc- tot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587)4844-499 2016. ISSN 1476-4687. doi: 10.1038/ (r.1038/nature166 naturel69611. URL https://ww.nnture..com nature. htt.///rrermmmrrttii/////atrrrr 6961.. Publisher: Nature Publishing Group.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM Test-Time Compute Optimally can More Effective than Scaling Model Parameters, 2024. URL https:
llaxxiv.rrg/aae abs//408. 033114
Jiao Sun, Yufei Tian, Wangchunshu Zhou, Nan Xu, Qian Hu, Rahul Gupta, John Wieting, Nanyun Peng, and Xuezhe Ma. Evaluating large language models controlled gener- ation tasks. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 3155-3168, Singapore, 2023. Association for Computational Linguistics. doi: 10.18653 111116////12223.mmmppppp 190. URL https: aacanthhoo/l org/2023. http222...mmmpmmmaa... emnlp-main. 190.
Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Syn- Code: LLM Generation with Grammar Augmentation, 2024. URL https://arxiv, org/ 0bs/2203300633
Tim Vieira, Ben LeBrun, Mario Giulianelli, Juan Luis Gastaldi, Brian DuSell, John Terilla, Timothy J. O'Donnell, and Ryan Cotterell. From Language Models over Tokens to Lan- guage Models over Characters, 2024. URL http:s://arrdd.or////////4222 037119
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Pp. 9426-9439, Bangkok, Thailand, 2024a. Association for Computational Lin- guistics. doi: 10.18653/ http://12222.aalooog..5555 acl-long.510/.
URL
wwt.ocoolnntoggyyyyoo org/2024.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Rep- resentations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023a. URL https://openrevice net/pdf?id=1PL
Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Atharva Naik, Arjun Ashok, Arut Selvan Dhanasekaran, Anjana Arunkumar, David Stap, Eshaan Pathak, Giannis Karamanolakis, Haizhi Lai, Ishan Purohit, Ishani
19

---

Published as a conference paper at COLM 2025
Mondal, Jacob Anderson, Kirby Kuznia, Krima Doshi, Kuntal Kumar Pal, Maitreya Pa- tel, Mehrad Moradshahi, Mihir Parmar, Mirali Purohit, Neeraj Varshney, Phani Rohitha Kaza, Pulkit Verma, Ravsehaj Singh Puri, Rushang Karia, Savan Doshi, Shailaja Keyur Sampat, Siddhartha Mishra, Sujan Reddy A, Sumanta Patro, Tanay Dixit, and Xudong Generalization via declarative instructions on 1600+ NLP tasks. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 5085- 5109, Abu Dhabi, United Arab Emirates, 2022. Association for Computational Linguis- tics. doi: 10.18653/ / /001///22.eemamm emnle- 340. URL https://aclantholoogy org/ 2222/
Shen. Super-Naturallnsttuciioo
emnlp-main. 340.
Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi. Self-instruct: Aligning language models with self- generated instructions. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pp. 13484-13508, Toronto, Canada, 2023b. Associa- tion for Computational Linguistics. doi: 10.18653v11/002.ac--oyy // //aclanthology. org/ wwwgg/223..222 acl-long. 754.
URL https:
Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Jian, Tianle Li, Max Ku, Kai Wang, Alex Zhuang, Rongqi Fan, Xiang Yue, and Wenhu Chen. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurlPS 2024, Vancowver, BC, Canada, Decem- ber 10- 15, 2024, 2024b. URL http: / httpppaapppppp/aa//eeeeeeeeeeee www..inpc....mm... wttpppperfillleppppppppeeeeeeeep ad236edc564f3et
1b2feafbb922444440 Abstract-Datasete aad_aand_____eee Benchnarks_chaaaeee html.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thoouht prompting elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. URL http::/ nips. cc/pepe__illss/ files/ html.
paper/2022 httpe///hhhhh//555990ee 3524ecf4f 15000006655554444444104101111113
Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. In The Eleventh Inter- national Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL httpst:
net met/ppffiii (pdfiid=hH33Je@ZDaa)
Brandon T. Willard and Rémi Louf. Efficient Guided Generation for Large Language Mod- els, 2023. URL. https://arxiv.cr wttp://wwwwwxxr///////aa 097722
Lionel Wong, Gabriel Grand, Alexander K. Lew, Noah D. Goodman, Vikash K. Mans- inghka, Jacob Andreas, and Joshua B. Tenenbaum. From Word Models to World Models: Translating from Natural Language Lanuuaae to the Probabilistic Language of Thought, 2023. URL
2306. 110906.1667. 12622.
Nan Xu and Xuezhe Ma. LLM The Genius Paradox: A Linguistic and Math Expert's Strug- gle with Simple Word-based Counting Problems, 2024. URL https://arxiin org/abs/ 2410. 14166.
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong lang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xu- ancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yuqiong Liu,
20

---

Published as a conference paper at COLM 2025
Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. Qwen3 Technical Report, 2025. URL https://arxivv org/ htt//bb//25555 093888 09388.
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Con- ference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRe- view.net, 2024. URL htt.://ppp.pppooeeeeeeee/e////te ntt.:forrrmmm.xBBBeeoW.....
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Adoances in Neural Information Processing Systems 36: Ammual Conference on Neural Information Processing Systems 2023, NeuriPS 2023, New Orleans, LA, USA, De- cember 10- 16, 2023, 2023. URL http: / nips wwtpappr_fileeeeeeeeeeeeeeeepeee /ttee//ppper/222//aaaaa 271db9922b8d1
html.
Shunyu Yao, Howard Chen, Austin W. Hanjie, Runzhe Yang, and Karthik R. Narasimhan. COLLIE: systematic construction of constrained text generation tasks. In The Twelfth International Conferennee on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OeenRevie 2024. URL
geet/formmiddkkxsllyyitt
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. Star: Bootstrapping rea- soning with reasoning. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022. URL http: /ttp::://pppppp..e/// nips. cctpappr_filllaeeeeeeeeeeceeappe httpr//22222/haah556999999 72c2444b2722444bbb6444 aeeee//ff.deeeeeaaaaarrratt--t-a
html.
Eric Zelikman, Eliana Lorch, Lester Mackey, and Adam Tauman Kalai. Self-Taught Opti- mizer (STOP): Recursively Self-Improving Code Generation, 2023. URL https:///sxxii org/abs/2310, 02304.
Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Baker Grosse. Probabilis- tic inference in language models via twisted sequential monte carlo. In Forty-first In- ternational Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https:://pperreiier met/foorum?dd=FrAAWNBB...
Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. Instruction-Foolooiing Evaluation for Large Language Mod- cls, 2023a. URL https://arxiits .rg. abs//311 07911111..
Wangchunshu Zhou, Yuchen Eleanor Jiang, Ethan Wilcox, Ryan Cotterell, and Mrin- maya Sachan. Controlled text generation with natural language instructions. In An- dreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawviï, USA, volume 202 of Proceedings of Machine Learning Research, Pp. 22602-42613 PMLR, 2023b. URL https: http::///occceee...... mlr pwwss/res222 220p://23322222233 html.
Yongchao Zhou, Andrei loan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Har- ris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwandaa May 1-5, 2023. OpenReview.net, 2023c. URL https://openreview.nee wwtp:/iwwwwee/ddffieiie 92gvk82DE-.
21

---

Published as a conference paper at COLM 2025
Appendix
Table of Contents
A SMC Visualization
23
B COLLIE Dataset and Results
24
Puzzles Dataset and Results
26
D Weighted Pass@1
28
E Coherency Score
28
F Planner-Only Ohain-of-Thought
28
F.1 Thouuht Prompt
28
F2 Error Examples
29
G DISCIPL Error Analysis
30
H Inference Methods
33
Implementation Details
33
Compute Cost Analysis
K Prompts and Code Links
36
K.1 Planner System Prompt
36
K.2 Example Models...
36
22

---

Published as a conference paper at COLM 2025
A
SMC Visualization
Step
remily
shore Gapar
Preeolkkoo Strgre
These Oragen
Theal fingue Clegge
theanne Grnge
Trean clager
Thear Gager
Thaigbron Guger
Thean Chagar
The coder in Guaoe
Feartd Stapee
marrre chChua
Drigee
Thrusiee non chapss
Step
The Gupa Unierrty Sorthed
The in stventy moded hard
Thenodery or snvunggn Suated
Thesoder Drgge sevinit roded hemely
Theseden Dragen enverppaten dleon
Theuades anverit ling
Clagen Leevnop racled plilerrty
Glagen anvonies instled
Thedaderr it Gagi Lsivering mes duulpn
daalerr Gaja Univerii Sordied
The dtaderr it Gaaa uniarity caded lunely
studera in Guaas Ulivrity hund
zudera Ouaon ctventer andin
maaker Osgpn snventy mndlggge
Thagen anurrt
Step
The in Unierit
kamning
in Uniwrity mudlnn the
madeer Orapn Univrity moding
Thenoder Orggon Ulivrity moding intrelyy
Theaades Dragen Lieurnty weriiiingg
Thevades
waringg and
Thedaieer Gaagn Lsiveriig dardin
cluderr in Lsiveriig coudin
The dtaderr it Univeriiy mer couding
studerr in Guaon Uliveriyy ver souding Socted
zaders Guaos Ulivrrity was soddigg hamed
modker Uliveriy vere muding limrrry and
Ulevrray mading
Thagos teeurny woriing
Step
it Unieerty
the
in Uniwnrt
maders in Univnrty moding cnwweed cosman roderts
shirly
Theaader
on duiing
Thevaden
people
Thevades
inneeeeationn line rigeater hepply for iive unveeiaa lowe the manning legities conta mestt eaey kap audeeily faddng solees. civeledd with mary bus
The diuierr it Gajus
The dailera it Uliveriiy souding couddd dhe loriy ona Satrrdyy naiiiig
zaders in Uliverity moding coudld lone ropether evey afterson for hours. hat sugiter dlogs earin
lowe en other ouderaals
it Univerii codrin paiell vapelee will alk sumonding eeryeber pura
Figure 7: Inference in action. Visualization of SMC inference for a DISCIPL program for the COLLIE sent_02 task (Fig. 1*): "Please generate sentence: 1) with exactly 18 words; 2) with the 4th, 8th, 11th words to be 'Glasgow', 'in', 'and' respectively." Weights for N=16 particles are computed after each step and correspond intuitively to measure of fluency under the constraints. For instance, after Step 1, particles for which "Glasgow" is natural 4th word are propagated (e.g., "The students at Glasgow"), while others are filtered out (e.g, "The big brown Glasgow"). Each step corresponds to single constraint: the first three steps each generate until the next target word, and the final step generates until the 18th word. In this way, the inference program ensures validity by construction, while adaptive resampling via SMC selects for overall coherency.
"Note that for pedagogical resons, some details have been simplified in the program that appears in Fig. 1. In particular, in Fig. 1, each step generates one word; hovever, in the program that produced this visualization, each step generates multiple words until the next constraint has been satisfied. Both approaches are valid, but the muldi-woord approach is more efficient and leads to better coherency, as discussed in $5.2.
23

---

Published as a conference paper at COLM 2025
B COLLIE Dataset and Results
We evaluate on a subset of 9/13 of the tasks in COLLIE-V1 (Yao et al., 2024) corresponding to the sentence and paragraph levels. use the task instances drawn from the Wikipedia corpus of COLLIE-vI. Since the number of instances varies significantly across task types, when computing aggregate metrics, we normalize with respect to task-level (sentence and paragraph), such that each task instance is treated as having been sampled from a uniform prior over constraint types.
TASK
N
EXAMPLE PROMPT
sent 01
38
Please generate a sentence with exactly 82 characters. Include whitespace into your character count. Please generate a sentence: 1) with exactly words; 2) with the 4th, 8th, 11th words to be 'Series', 'and', '4' respectively.
sent_02
98
sent_03 03
29
Please generate sentence: 1) with at least 9 words; 2) with all words having at most 7 characters.
sent_04 04
94
Please generate sentence containing the word 'have', 'rising', 'the'.
para_01
Please generate paragraph with all sentences having the 1st word to be 'The'. Please generate a paragraph: 1) with exactly 3 sentences; 2) not containing the word 'be'; not containing the word 'this'; not containing the word 'is'.
para_02
94
para 03
93
Please generate a paragraph: 1) with exactly 4 sentences; 2) with all sentences having at least 12 words; 3) with all sentences having at most 20 words.
para_00
04
18
Please generate a paragraph: having at least words.
with at least 3 sentences; 2) with all sentences
para_05
89
Please generate a paragraph: 1) with exactly sentences; 2) with sentences having the last word to be 'convention', 'president', 'Wisconsin' respectively.
Table 2: Summary of tasks in COLLIE-v1 used for evaluation.
sen_.1 01
sent 02
_4 Coh.
Overall
Pass81
Cob.
PaseB]
Col.
PesSS1
Coh.
Paw@B
Pas@1
Coh.
Method
Sampling
Model
D&CIPL
SMC
Llama-322-1B
0.81
6.61
0.81
4.80
0.86
5,07
0.53
5.96
0.76
5.61
Alama--32-338
0.97
7.71
0.84
4.34
0.97
7.28
0.54
6.12
0.83
6.36
Llama-3.1-4B
0.89
6.79
0.87
5,34
0.97
5.14
0.68
7.03
0.85
6.07
Qwen3-1.78
0.76
5.20
DisCIP
Importancc
Llama-3.2-1B
0.97
3.55
4.55
5.07
Llama-3.2-38
1.00
7,82
0.83
4.04
0.86
5.55
5.49
081
5.72
Llama-3.1-405
0.97
7.71
0.86
4.73
01977
4.31
0.72
6.59
0.88
5884
Qwen3-1.78
0.95
5.21
0.92
1.86
0.86
6.85
0.81
5.13
0.88
4.76
DisCIP
Rejection
Llama-3.2-1B
0.03
9.05
0.00
6.14
0.00
9.41
0.78
8.28
0.20
8:22
Llama--32-3B
0.61
7.92
0.00
5.28
0.90
7.28
0.82
8.67
0.58
7.29
Llama-3.1-46
700
Qwen3-1.78
0.06
8.21
0.01
4.47
0.55
8.59
0.90
8.02
0.38
7:32
DiCCPLL expert
SMC
Llama-32-18
0.95
7.29
0.98
5.06
1.00
7.76
0.67
6.32
0.90
6.61
Importance
Llama-3.2-18
1.00
6.61
0.98
4.06
1.00
6.08
0.65
6.21
0.91
5.73
progrmm
Repection
1.2.m-3.2.18
0.00
9.55
0.00
6.53
0.00
9.90
0.73
8.21
0.18
8.55
oollower-only
Standard
Llama 3.2.1B
Llama-322.1
0.00
9.24
0.00
6.01
0.00
8.86
0.27
8.36
0.07
8.12
Llama-3.2-3B
0.02
0.00
7.76
0.56
7.44
Llama-3.1-46
0.02
6.79
Beam Search
Llama-3.2.11
0.00
9.61
0.00
7.90
0.00
9.76
0.31
8.47
0.08
8.93
Llama-3.2-8
0.00
8.76
0.00
6.39
0.05
9.24
0.60
8.68
0.17
8:27
Llama-3.1-4B
0.02
0.00
5.76
0.01
8.79
0.85
8.69
0.22
7.90
Standard
Qwen3-1.7B
0.01
0.00
7,70
7.33
Beam Search
Owen3-1.78
0.01
5.95
0.00
3.96
0.15
7.90
0.80
7.69
0.24
6.37
Planner-only
Standard
GPT-4o-mini
0.07
0.00
9.55
0.89
8.71
0.37
9/00
GPT-4e
0.07
9.21
0.03
7.78
0.21
9.21
0.96
8.97
0.32
8.79
GPT-4o (CST)
0.07
8.87
0.08
7.89
0.71
9.31
0.98
8.84
0.46
8.3
Reasening
Standard
al
0.81
8.03
0.98
6.08
1.00
7.34
1.00
8.90
0.96
7.69
Table 3: COLLIE Sentence-Level Results.
While COLLIE also defines several word-level constraints, we found that, even with tools for fine-grained token masking, these present a particular challenge for LMs due to the problem of token misalignment. While it is possible to recover next-character distributions from token-level LMs (e.g., Vieira et al., 2024), such approximations are expensive to compute. Instead, we focus on constraints at the sentence-level and higher that can be effectively expressed with token-level LMs.
24

---

Published as a conference paper at COLM 2025
Pass@1 for N=8
Pass@1 for varying N
1.0
1.0
0.8
0.8
Pass@1
0.6
Pass@1
0.6
0.4
0.4
0.2
0.2
0.0
0.0
DSCIP
Follower Panner 01
2
para
para para_05
Pass@g
0.6-
0.4-
0.2-
SMC
DisCIPL-IS
U.ma-3.2-1B
GPT-4e-mini
DIsCIPL*SMC
DIsCIPLKIS
DisCIPL'-RS
Uama-332-4 (Beam)
GPT-4o
Figure 8: Validity on COLLIE Paragraph-Level Tasks. Figure structure is identical to COLLIE sentence-level tasks (Fig. 3). Since generations are longer, the total sampling budget limited to = 8. Baseline performance is higher for all models these tasks appear to be more in-distribution for LMs. Nevertheless, we observe that DISCIPL helps to close the Pass@1 gap between the Follower- only (Llama-3,2-15) and Planner-only (GPT-4o) baselines.
01
.13
05
Overall PaesBl Coh.
Passil Coh.
Pass4l
Method
Sampling
Model
DisCIPL
Llama-3.2-18
3,92
Llama-3.2-1
1.00
8.00
0.87
9.07
0:68
6:27
0.83
8:17
0.34
3.44
0.74
6.99
Llama-3.1-46
1,00
7.89
0.74
9.48
0.91
8.45
0.89
9.00
0.22
4.06
0.75
7.59
Qwen3-1.7B
0.60
6.06
0.72
6.22
DisCIPL
Importance
Llama-3.2-1B
0.89
3.56
0.79
7668
0.62
5,06
0.78
7,89
0.20
3.26
0.66
5,89
Ilama-3.2.38
0.70
5.59
Llama-3.1-88
0.89
7.33
0.78
8.02
0.91
7.53
0.78
7.39
0.21
3,76
0.71
6.77
Qwen3-1.78
0.89
6.00
0.82
8.56
0.62
5.42
0.72
5.78
0.20
3.54
0.65
5.85
DiCIPL
Rejection
Llama-32-11
0.89
7.67
0.91
9.07
0.48
8.81
0.78
9.17
0.01
7.61
0.62
8.48
Llama-3.2.88 3-
1.00
8:11
0.96
9.52
1.00
8.14
0.72
9.00
0.65
4.97
0.87
7.95
Llama-3.1-4B
8.78
9.46
0.97
8.69
0.89
9.17
0.73
8.18
Qwen3-1.7B
DiSCIP*
Llama-3.2-1B
0.86
0.98
8.92
0.96
7,83
expert
Importance
Llama-3.2-18
0.89
0.98
9.17
0.97
7.78
0.78
7.33
0.49
3.42
0.82
7.16
progams
Repection
1lama-3.2-118
0.89
8.22
0.95
9.16
0.48
8.97
0.67
9.28
0.04
7.46
0.61
8.62
Follower-only
Standard
Llama-3.2.18
0.88
6.89
0.68
8.98
0:10
8.81
0.24
9.22
0.00
7.33
0.38
8.28
Llama-3.2-3B
0.93
8.67
0.74
9:30
0.85
7..9
0.45
8.17
0.22
5.53
0.64
7.85
Llama-3.1-4B
0.99
8.33
0.79
9.46
0.84
8.41
0.68
$.89
0.34
4.82
0.73
7.99
Llama-3.2-18
9.40
0.03
9.977
8.96
Llama-3.2-35
1.00
8.67
0.60
9.79
0.77
8.60
0.08
8,83
0.19
6.71
0.49
8.52
Llama-3.1-90
1.00
9.00
0.30
9,80
0.90
8,89
0.71
8.94
0.25
5,38
0.63
8.44
Standard
Qwen3-1.7B
0.71
8.67
0.17
8.56
Qwen3-1.7B
Planser-only
Standard
GPT-to-mini
9.86
9.81
0.66
GPT-4o
0.96
9.33
0.91
9.84
0.87
9.74
0.74
9.22
0.51
7.66
0.80
9.16
GPT-4o (COT)
0.92
9.33
0.86
9.33
0.71
9.22
0.85
8.61
0:47
7.48
0.76
8.79
Reasoning
Standard
al
1.00
8.89
1.00
8.95
0.94
9.17
1.00
9,00
0.83
6.63
0.95
8.53
Table 4: COLLIE Paragraph-Level Results.
25

---

Published as a conference paper at COLM 2025
C Puzzles Dataset and Results
The PUZZLES dataset consists of four task types with prompts given in Table 5. We re-run each method 10 times on each task type to produce the results in Table 6.
TASK
PROMPT
DiSCIPL-SMC
The sun sets slowly in the evening sky Golden hues of orange and pink slowly fade
The stars
out world outsade night rest
tonight
Square Poem
Write a poem with 8 lines, where each line has evactly werds.
The moon full and bright and white A besscen in the dark and enclless night
The world quiet and still and deep the stillness, all calm and bright
Write abstract for grant proposal elephant ecology and conservation. Your resporse should start with "Alastract:
Studying complex behaviot, social dynamics, territorial boundaries Indiaa elephant populations using camera trap images and GIS analysis reveals that strang elephant hends are consistenlly associated with increased aqualic habitals, These findings suggest that elephant social hicrarchies play a crucial role in allocating resources and protecting against intrusioas by buffalo herds. Investigating the spatial overlap between elephant and buffalo habitats, results show that elephants priorttize buffer zones around food sources to minimize the risk competing utilizztion..
Abstract:
<YOUR ABSTRACT>" The abstract must between 75-1 to use any the following terms. conservation, sustsinability, env onvirnmment, ecology, wildlife, atrica, ssin, society, communiity, biodiversity, endangeved, threatened, species, habitat, poaching, science, research.
food resources, particularly graselands and
Grant Proposal
You
allowed
with larger
Please write an ingredients list for chocolate chip brownies with at most 7 ingredients costing less than $18.00 total. The list should be dashed builet point format starting with 'Ingredsents." Each ingredient should be listed on a separate line with the price given USD.
Ingredients:
11 and 1/2 sticks of unsalted butter ($3.50)
cup granulated sugar ($1.50)
Ingredients List
-2 large eggs (5) ($1.50)
- 1/2 cup unsweetened cocoa powder ($1.50)
- beaspoon vanilla extract ($125)
1 cup semi
chocolate chips (54.0))
Day
[06:00-07:30 Start the day Marina Bay Sands SkyPork for panosamic views of the city.
(07:30-99:30] Take a walk alonng the Marina Bay Wisterrrnt Promenade for a leisurelty stroll and enjoy the scenic views of the city.
[09:00-12:00] Visit Esplarade- Theatres
Bay for movie
performance.
[12:0011:30) 13:30 Have lunch at nearby restaurant, such as Jumbo Seafood, and
local seafood.
(13:0-15:30) Visit Singapore Botanic Gardens for relaxing walk and
take the bestutiful gardins.
[15:30-18:00] Explore the icunic Gardens by the Bay, learn about
Singapone's is flona and fauns, and marvel at the stunning architecture.
I'm planning a 3-day trip to Singapore, Please write me a detailed day-by-day itinerary that includes least four activities per day. The itinerary should I. and end with 'Day 3 with blank line between each Each activity should be listed separate line starting with time range 20-hour format in square brackets (for example, "[11:00-1300 (3:00 Visit the Gardens by the Hay")) ") Make sure to leave at leust 9 hours free time each day for
Day
107:00-19:00) Start the day at the Singapore Zoo, home to over 2,800 snimals from around world.
with "Day
[09:00-11:00 Visit nearby Universal Studios Singapore
Trip Itinerary
immensive theme park expertence with rides and attractions.
/ [11:00-12:30] Head to the icunic Merlion Park for a short walk and visit the
Merlion statue.
eatery, such Maxwell Food Centre, 1::30011:30] Have Junch at
and try some hawker food.
[14:0016:30] Take a short taxi ride to the Gardens by the Bay for a visit to the Cloud Forest and Flower Done.
(16:30-1800) Relax unwind the Garders by the Bay with scenic walk.
Day
[07000-09:00]
historic Fort Canning Park, former military base turned public park.
10:00-11:00] Explore the nearby National Gaileryy Singapore, featuring diverse collection of Southeast Asian
[11:00-12:00 Have Junch at nearby eatery, such Tiong Bahru, and try
some Singaporean cuisine.
112:30-14:30f Visit the nearby Little India and explore the vibrant streets of Chinatown and Little India. [1:30-16:30]
short taxi ride to iconic Marina Bay Sands the zoofuup bar for stunning views of the city.
Table 5: Puzzles tasks and example generations. Samples were randomly selected from among the valid outputs produced by DISCIPL-SMC.
26

---

Published as a conference paper at COLM 2025
Pass@1 for N-16
Pass@1 for varying N
0.2
0,2
0.0
0.0
DISCIPL propora
Follower Honner 01
Ingredients, list
eqquare_pem
trip Rineraryy
0.8
0.
12
16
DIsCIPLSMC DIsCIPLN-SMC.
DisCIPL-IS
DisCIFL-RS
3.2-1
GPT-4o mini
o1
DisCIPL
DisCIPLA-RS
Llama-3.2-18 (Bnam)
GPT44
Figure Validity PUZZLES. Pass@1 for fixed (top left) and varying (top right) sample budgets for four challenge tasks (bottom rows) While DISCIPL still surpasses both Follower and Planner baselines, generation more often produces suboptimal programs, leading to bigger gap vs. DISCIPL*.
Grant Proposal Passi]1
Ingredients List Fassilt
Square Poem Passib1
Trip Itinerary
Overall
Coh.
Coh.
Coh.
Passl11
Coh.
Passil
Coh.
Sampling
DNsCPPI
Llama-3.2-18
0.20
0.50
8:80
4.50
Importance
Llama-322-1B
0.10
3.70
0.70
8:50
0.60
6.20
0.10
1.30
5,65
Rejection
Llama-3.2-16
0.30
9.00
0.00
8.90
0.00
9.10
0.70
8:40
0.25
8.85
DiCIPL+
SMC
Llama-32-18
0.60
8:20
1,00
9.10
0.70
7.90
0.50
6.50
0.20
8.00
Importance
Alamm-332-118
0.60
7,70
1.30
8.50
0.70
6.60
0.60
6.00
0.72
7440
Rejection
Llama-3.2-1B
0.70
0.00
9.30
7.50
845
Follower-only
Standard
Llama-3.2-18
0.00
9.00
0.01
9.20
0.00
9.20
0.25
7.00
0.08
8.60
Llama-322-1B
Planner-ooly
Standard
GPT-4o-mini
0.98
0.06
9.50
0.05
9.10
9.20
GPT-4e (CoT)
0.91
9.00
0.17
9.50
0.01
9.40
0.12
9.20
0.30
9.28
Reasoning
Standard
ol
1.00
9.00
0.40
8.80
0.90
8.90
1.00
9.30
9,00
Table 6: PUZZLES Results.
27

---

Published as a conference paper at COLM 2025
D Weighted Pass@1
We formalize the the weighted Pass@1 metric used to evaluate model performance. This metric offers a natural way to incorporate sample-specific scores (e-g,, particle weights w;) into the evaluation. The approach is scale-invariant, the absolute scale of the weights does not affect the metric.
Consider a set of N samples, indexed by i 1,..., N. For each sample, we define:
A log-probability to & IR. In cases where wi is undefined (i.e., when generation pro- duces null output), set its corresponding weight to zero.
A binary pass indicator
{--(0, if sample passes,
0, if sample fails.
We define the unnormalized weight of sample as
3) = exp(w;))
where for methods that do not compute sample weights, we assume uniform weighting by setting W; for all i.
Weighted Pass@1 is defined the probability that single sample-drawn without placement from the N samples with probability proportional to i0-is a passing sample. Formally, this is given by
Σ
1:1,=1
Weighted Pass@1
This expression represents the fraction of the total weight that corresponds to passing sam- ples, and it reduces to the standard (unweighted) Pass@1 when all weights are equal.
E Coherency Score
To assess coherency, we adopt the LLM-as-judge evaluation from Yao et al. (2024) (App. E). Whereas the original evaluation used GPT-4, to reduce inference time and cost, we use GPT-4o-mini (60t-40-minn-2224-07--
We make minimal modifications to the original prompt to encourage GPT-4o-miní to adhere to the desired format.
Please concisely analyze the following text for coherency. Your analysis should be Amust* verbatim with 'The coherency score
longer than sentences <SCORE>', where <SCORE> is a number between and 10.
F Planner-Only Chain-of-Thought
E1
Chain-of-Thought Prompt
For the Planner-only (CoT) condition, we prompt GPT-4o with the following standard in- structions to think step-by-step. These are provided as a system prompt.
You are helping a user generate text that satisfies constraints. Think step-by-step in order to follow the user's instructions. Your final response should be enclosed in <answer></answer> tags.
28

---

Published as a conference paper at COLM 2025
F22
Error Examples
F.2.1
Character Counting
Task Prompt Please generate sentence with exactly 82 characters. Include whitespace into your character count.
GPT-4o To create a sentence with exactly 82 characters, I'll count each letter, space, and punc- tuation mark:
"The sun sets slowly over the ocean, painting the sky with hues of orange and pink delight."
Now, let's count the characters:
"The sun slowly over the ocean, painting the sky with hues of orange" (70 characters) and pink delight." (12 characters)
Total: 70 + 12 = 82 characters.
<answer=The sun sets slowly over the ocean, painting the sky with hues of orange and pink delight.</answer
Evaluator Invalid
Length is 90 characters (expected 82)
F222 Word Positioning
Task Prompt Please generate sentence:
1) with exactly 15 words;
2) with 4th, 8th, 11th words be 'collection', 'Noise', 'Testament' respectively.
GPT-4o To create sentence that meets all the requirements, let's start by laying out the posi- tions of the specific words:
1. (word 1)
2. (word 2)
(word 3)
4. collection
5. (word 5)
(word 6)
(word
Noise
9. (word 9)
10. (word 10)
11. Testament
(word 12)
13. (word 13)
14. (word 14)
15. (word 15)
Now, fill in the blanks with appropriate words to construct coherent sentence:
"The museum's vast collection included fascinating exhibit titled Noise, featuring the Testa- ment of artifacts." "
Evaluator Invalid
word is "exhibit" (expected "Noise") word 11 "featuring" (expected "Testament")
29

---

Published as a conference paper at COLM 2025
G DISCIPL Error Analysis
By learning from tracebacks, DISCIPL able to correct roughly half of all initial runtime rates of 2-6%
errors (Fig. 10, left). Nevertheless, even after 3 attempts, we observe COLLIE (App. B) and 18% on PUZZLES (App. C). Our analysis (Fig. 10, right) finds that most errors arise from invalid token masks and timeouts. Token mask errors occur when call to observe() () rules out all possible next tokens (e.g,, when attempting to generate punctuation when a mask that rules out punctuation is already active). Meanwhile, timeout errors are more commonly associated with infinite loops or the omission of termination conditions in the step() logic.
There are also cases where bugs in the generated inference programs yield incorrect out- puts without triggering any errors. App. G, we give examples of an off-by-one error (Code Block 1) and an accidental infinite loop (Code Block 2) and highlight how structural issues with the outputs can be traced back to these bugs. In future work, we aim to imple- ment richer form of feedback where outputs from inference are provided to the Planner LM to correct for these kinds of errors.
COLLIE Sentence Tasks
1.0
0.8-
Proportion
0.6
Valid
Uraaaato compale prisenilyy Daatneeeed
0.4
Invalid
FarCCaa Parc uoed wovert unnaad sarape provvot
eccede
0.2
Tiicr aped "uneddarten
0.0
Retry
COLLIE Paragraph Tasks
1.0
WOU
conpue
0.8-
Proportion
0.6
Valid
dee deputti Tar aut techhemma
Invalid
0.4
ontiral
coud arledd
0.2
Maai andiue
0.0
Retry
PUZZLES
1.0
0.8
Pogortoon
0.6
Vaid
Invalid
0.4
Ta0 (des Fur to
0.2
0
0.0
Retry
Figure 10: Inference-time errors in DISCIPL-SMC. (Left) Proportion of valid valid/invalid text generated each retry, with errors in gray. Roughly half of all initial errors (#1) are corrected with feedback (#2), with diminishing returns on remaining errors for subsequent retries. (Right) Breakdown Top-20 most frequent error messages aggregated across all retries.
30

---

Published as a conference paper at COLM 2025
Listing Example of buggy program generated by the Planner LM for COLLIE sent_@ task instance. The generated program correctly applies MaxCharsMask () to produce string that is exactly 102 characters. However, lines 33-34 subsequently force the Follower LM to generate punctuation, resulting in generations that exceed the target length by a single character.
class InferenceHodel (Hase*odel):
**Generates with exactly characters, including whitespace ...
3
_n.int___ self,
context,
7
tokens: int 32, ):
super() in context=context, max_tokenssmax, tokens,
10
N Task-specific variables selfi length 192
15
async def step(self): 17
*..
Step granularity: token
Generation strategys At each sample taken that fits within the renaining length. Once the target length is reached, force punctuation and end the sentence.
22
End condition: Target length is reached taken limit is reached.
Sample token that fits within the remaining length, asyne with (fx max_charssseeff lenghh_ len(sel))): token await self. next_ token()
29
# If we we've reached the target length, force punctuation and end the sentence len(self) self. lenget_ async with PunctuattooMtesk(sel1)) await self_next next, httffeeeetttrr(((_ token() await self. end).end() return
* Enforce taken linit self. context. token_count self tokens::::: self (onditionFaalse) await self, end() return
31

---

Published as a conference paper at COLM 2025
Listing Example of buggy program generated by the Planner LM for COLLIE para_ 05 task instance. The step() function contains while loop that samples words until the target sentence-ending word is generated. However, due to bug in the conditional at line 34, target words containing capital letters (e.g., Oxford, College) will never be matched. As result, the Follower LM will generate the first two sentences of the paragraph correctly and then loop indefinitely on the third sentence until it exceeds max_ mo__os.ens.
class InferenceModel (BaseModel):
2
GGenerates par agraphpph with exactly sentences, where each sentence ends with specific word.
def [
self, context, nax_ takats: 256,
7
(nserO(__nnii__... context-context,
11
nax_ Lox__tokessman max_ tokens,
Task-specific variables
self. sentence_ends ['offices", "deor", "Oxford", "College", "Initially"] self sentence__ountte
18
async def step(self):
Step granularity: sentence
Generation strategy: At each sample sentence until the specific last word is reached. After generating the specific last word for sentence, enforce punctuation.
25
End condition: All sentences are generated or token limit is reached. v.e
Generate sentence until the specific last word is generated lartet_last_werds self sentence, ends[self sentencee_oome ccunt]]
while True:
await self noxt__ord()
32
Check if the generated word is the target if word.stript strip(r......... lower() == last_ word: # Force punctuation after the target last word async with Punctuttionkssk(se11)) await self, next_token()
break
Enforce token linit if self context. token_count self tokens: self, condi (Fanselsse await self end() return
44
self contance_count +5
N End generation after all sentences produced self. sentenceecouut len(self sentence_ends):: await self. and() return
32

---

Published as a conference paper at COLM 2025
H Inference Methods
We provide formal definition of the SMC algorithm DISCIPL. Our implementation is adapted from the LLAMPPL with minor adjustments intended to provide robustness to bugs in autogenerated inference programs. In particular, we set maximum number of SMC steps T 1000 that programs that fail terminate do not run infinitely. We also invoke this method with wall-clock timeout (not shown) to interrupt infinite loops that might occur internally within a single step().
Algorithm Sequential Monte Carlo Inference Algorithm
1: function SMC((1, Mp, Ness, T)
2: for i = 1,..., N do 0 ((MF))
3:
Instantiate particles
4: for 1 = 1, 1,..,, do
await ()) for in x21)) x(N)
Advance particle state
6:
I,...,N do
7:
w D0l:
w
Normalize weights
8:
if
I (adtyy
Ness then
D. Compute effective sample size
9:
a1)) Categorical
2 will
1000
b Resample
10:
for 1,.,,.., N do (x11), z0l0) +- (x
N I will
11:
Vx e (x(11), xx2) , (N)) {xx VEOS) then
Check if all particles have terminated
return (x(1), x NN)
I Implementation Details
LLAMPPL inference is performed with the vLLM backend, which uses PagedAttention (Kwon et al., 2023) for improved efficiency. For baselines, max_tokens is set to 32 for COLLIE sentences, 128 for COLLIE paragraphs, and 512 for PUZZLES. For DIsCIPL, max_ tokens is defined by the Planner LM and programs executed with max of R 3 retries and variable timeout (120s for sentences, 240s for paragraphs, and 360s for puzzles). The max sampling budget N for each domain is determined based on the number of tasks and the generation length; we use N 32 for sentences, N = for paragraphs, and N 16 for puzzles.
max_tokens
33

---

Published as a conference paper at COLM 2025
J Compute Cost Analysis
To help quantify the algorithmic tradeoffs of DISCIPL, we present an in-depth study of inference costs for representative domain from our evaluations (COLLIE sentence tasks). Our analysis suggests that this is conservative choice; comparative efficiency advantages of DisCTPL. are likely even greater on longer-form generation tasks such as COLLIE para- graph generation and our PÜZZLES domain.
We perform an analysis of the dollar cost of the DIsCIPL-SMC method, the Follower-only, Planner-only, and ol baselines.
o1
Token Usage (Reasoning / /Program
2500
GPT-4o (CoT)
DisCIPL-SMC (Llama-3.2-1
2000
1500
1000
500
sent 01
sent_02
sent_03
sent_04
COLLIE Sentence-Leve Tasks
Figure 11: Comparison of the number of intermediate tokens generated by each method before pro- ducing an answer. DISCIPL programs are generally more compact than the reasoning traces gener- ated by large reasoning models (e.g, o1) and more accurate than standard LLMs (e.g., GPT-4o with chain-of-thought).
Key Takeaways
In absolute dollar cost, DISCIPL is cheaper than ol: As seen in Table 7, running DISCIPL is marginally cheaper than ol ($4.26 vs. $4.75 per 100 tasks).
DISCIPL's inference programs are 40.1% shorter and 80.2% cheaper to generate than ol reasoning traces. Programs generated by the Planner LM use 40.1% fewer tokens than reasoning traces generated by ol. addition, the generated tokens are on average 80.2% cheaper, they are generated by less expensive Mondel-GPT-AR Overall, per 100 tasks, the tokens generated inference programs cost $0.91, whereas the tokens of oll reasoning traces cost $4.59.
The cost of scaling inference-time compute with DISCIPL is negligible: With 32 par- ticles, the Follower LM's generations account for < 0.1% of the overall cost of DIsCiPL. Thus, for example, doubling the test-time compute budget (e.g., from 32 to 64 particles) would have negligible influence the total cost of DISCIPL. By contrast, doubling the reasoning budget for ol would nearly double its price, and similarly for Planner- only Chain-of-Thought.
In the current implementation, DISCIPL's cost is dominated by the long Planner system prompt: Because GPT-4o has not been trained LLaMPPLiifference programs, we use in-context learning with a detailed system prompt and few-shot examples. We find that 72% of the cost of DIsCIPL results from pre-filling the part of this prompt that is static across tasks.
Nevertheless, DISCIPL benefits significantly from prompt caching. On average, 95.6% of the Planner's 's prompt tokens were cached by OpenAl's servers, resulting in an automatic 50% discount. In a performance-optimiin further reduced by using local Planner LM with prefix caching, Alternatively, we could finetune the Planner LM on inference programs- in the same way that current reasoning models are finetuned re-prompting. Amortizing the Planner computation in this way would yield significant practical cost savings, up to 72% of the overall cost.
system, these costs could be
reasoning traces- avoid the need for expensive
34

---

Published as a conference paper at COLM 2025
Reasoning/ Program
Task Prompt
Planner Prompt (Non-Cached)
Planner Prompt (Cached)
Total
Follower-only (Llama-3.2-1B)
50.0001
50.0003
$0.0004
Planner-only (GPTT44))
$0.0365
Planner-only CoT (GPT-4o)
S0.0376
80:2751
90.0485
90.3612
90.1061
$4.5897
$0.0509
$4.7457
DISCIPL-SMC'
$0.0032
$0.9138
$0.0003
$0.2863
$3.0804
$4.2606
Table 7: Dollar cost per 100 tasks for each method.
Column Descriptions:
The cost of generating the tokens of the solution to the task. For example, in ol, answer generation tokens are those generated after reasoning has completed; for GPT-4o CoT, they the tokens tagged by the model constituting the final answer; and in DISCIPL, they are all tokens generated as candidate answers by the Follower LM.
Answer:
The cost of generating tokens instrumental to solving the task. For CoT and ol, these reasoning tokens. For DISCIPL, these are the tokens of the inference program generated by the Planner LM.
Reasoning/ / Program:
Task Prompt: The cost of pre-filling the task prompt, which describes the particular task being solved. For DISCIPL, this is the cost of explaining the task to the Follower, not to the Planner.
Planner Prompt: The cost of pre-filling the Planner's 's system prompt in DISCIPL. Some of the prompt task-specific and not cached, whereas some of the prompt is domain- general and cached across tasks, leading to 50% discount under OpenAl's prompt caching policy.
Token Counts and API Pricing Details
Input Cached Input
Output
Llama-3.2-1B'
$0.06
$0.06
GPT-4o"
$5.00
$2.50
$20.00
o1
$15.00
$7.50
$60.00
Inference Cost for 1M Tokens (as of 2025-05-31)
'Follower LM compute actually performed with local GPU inference; costs shown use To- gether API pricing as a conservative upper bound. https: //www together. ai/pricing
"OpenAI model pricing: see https://platfont www.efffrroooonni...oo.mm openai com//ocss/pricing openai.
https://
Average Token Counts and Standard Deviations per Task
Reasoning/ Program
Task
Planner Prompt
Planner Prompt (Cached)
Answer
Prompt
(Non-Cached)
Llama-3.2-18
14. (5.3)
48.3 (2.0)
GPT-4o
17.2
(12.3)
GPT-4o (CoT)
18.8 (25.7)
137.6 (83.6)
96.9 (12.3)
17.7
764.8 (1018.3)
(12.3)
DISCIPL-SMC'
23.2 (11.4) per particle
456.9 (69.4)
48.3 (2.0)
12894.3 (444.1)
12321.6 (1801.)
DDICCIPLSMCC instantiated with Llama-3.2-18 Follower, GPT-4o Planner, N 32 particles.
35

---

Published as a conference paper at COLM 2025
K
Prompts and Code Links
K.1 Planner System Prompt
We use single system prompt written in the style of a README. md to demonstrate to the Planner LM how to write inference models. Since this prompt is written condensed ex- planation of language model probabilistic programming, it also doubles as a useful tutorial for the interested reader.
? gi thub. ott.gpprwa.aaiiiirreiiee.o.ii.ia system_promplt
K.2 Example Models
We define expert-written programs for the COLLIE task, which are appended to the Plan- ner system prompt. Our experiments are leave-one-out design, such that the example(s) corresponding to the target task are always omitted from the prompt.
COLLIE Example Models
? github.com models.pp py
PUZZLES Example Models
gi github.comm www..b.ccmm/aaaeeeeeeeee
36


Reviews:
[{"review_id": "PvRpc1tpWY", "reviewer": "Reviewer_DTJV", "summary": "This paper introduces DisCIPL, a novel meta-reasoning framework designed to enhance inference in language models (LMs) through \"self-steering.\" The core innovation involves decomposing the inference process into a Planner model, which generates a task-specific probabilistic inference program, and Follower models, which execute these inference procedures. By utilizing recursive search procedures and leveraging highly parallelizable Monte Carlo methods, DISCIPL aims to combine the flexibility of chain-of-thought reasoning with the efficiency and verifiability of structured inference techniques. A significant contribution is the demonstrated capacity of smaller LMs, when integrated into the DisCIPL framework, to achieve performance comparable to larger, state-of-the-art models on complex constrained generation tasks.\n\nEmpirically, DisCIPL shows improvements in performance over baseline models across two benchmarks: COLLIE, a constrained text generation dataset, and PUZZLES, a diverse set of naturalistic tasks. Notably, when instantiated with the relatively small Llama-3.2-1B as the Follower, DisCIPL's performance matches and sometimes surpasses that of larger models like GPT-4o and o1, particularly in tightly constrained generation tasks. The empirical analysis further highlights that Sequential Monte Carlo (SMC) inference provides better coherence and constraint satisfaction than other methods, validating the efficiency and effectiveness of the proposed inference programming approach.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. DisCIPL advances LLAMPPL by automating the generation of inference programs (with options of sampling methods and common patterns). Allowing a Planner LLM (e.g., GPT-4o) to synthesize LLAMPPL programs autonomously is an interesting methodological innovation.\n2. Separating planning (high-capability LLM) from execution (smaller, computationally lighter LLM) allows smaller, more resource-efficient models to achieve performance comparable to larger models.\n3. The introduction and utilization of PUZZLES show some efforts in generalizing the problem and proposed method to a relatively more realistic setting", "reasons_to_reject": "1. The automated generation of inference programs heavily relies on a system prompt (missing in the current version, possibly due to negligence in formatting). Such a prompting method is not rigorously tested in the current version, and we have less clue on how and why it works, leaving unclear the underlying mechanisms responsible for the reported successes.\n2. While the PUZZLES testing set attempts to introduce more realistic scenarios, the overall problem scope remains narrowly confined to constrained-generation tasks. The method, as presented, does not adequately explore broader, potentially more impactful applications. I can imagine we may extend this into an agentic framework for a more powerful application scope. \n3. The surprisingly strong performance of baseline models (like o1) on challenging reasoning tasks suggests that general long-form reasoning might be able to generalize well to the problems this paper tried to solve. On the other hand, the proposed method essentially tries to inject more explicit priors to guide small LLMs, which seems not generalizable (and also powerful) as o1.  \n4. The absence of diverse baselines limits the robustness of empirical claims (we may need more serious baselines). Moreover, the evaluation currently relies solely on a single planner-follower pair. Additional experiments involving stronger planners and followers could clarify the method’s scalability and show its comparative advantage over existing state-of-the-art reasoning models (outperforming o1 seems be another necessary milestone )", "questions_to_authors": "- A.10 system prompt is missing \n- In addition to providing such a system prompt, can the authors run an ablation study (e.g., prompt variants, few‑shot vs. zero‑shot) to clarify how sensitive DisCIPL is to prompt design?\n- We might want to explore stronger or weaker planners (e.g., GPT‑4‑Turbo vs. GPT‑3.5) and a broader range of follower sizes (e.g., 7 B, 13 B) to establish clearer scaling trends and performance ceiling\n- A detailed breakdown of compute cost for DisCIPL vs. baseline large models (and basic sampling methods like beam search) would help practitioners judge real‑world trade‑offs.\n- Can we adapt DisCIPL to broader agentic settings (e.g., multi‑step tool use, web navigation)? Outlining concrete next steps or preliminary experiments would strengthen the case for wider impact.", "extra_scores": {}}, {"review_id": "jTJnnOQs34", "reviewer": "Reviewer_3m39", "summary": "This paper proposes DisCIPL, an agent framework including a planner and a follower. The planner writes a program about calling LMs to do generation (asynchronously), and the follower follows the program to generate. They show that a weak follower can achieve good performace.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The framework incorporates agent workflow, asynchronous probabilistic programming, sequential Monte Carlo, which seems to be interesting.", "reasons_to_reject": "1. The approach doesn't seem very practical. DisCIPL relies on a strong model to act as the planner and generate code, which is the most critical step. If such a strong model is already available, it's unclear why weaker models are used in subsequent stages.\n\n2. The paper lacks an appropriate baseline. If we only consider using the strong model as illustrated above, the setup closely resembles PoT-style methods. In that case, comparisons should be made against other agent-based workflows, rather than simply evaluating the strong model alone.\n\n3. The benchmark used appears to have already been solved by earlier reasoning models (e.g., o1). This raises the possibility that current techniques may easily solve the tasks presented in the paper.\n\n4. The approach may not generalize well to other types of planning problems.", "questions_to_authors": "SMC seems to be not necessary here. Can we use async probabilistic programming with standard parallel repeating generation?", "extra_scores": {}}, {"review_id": "kIVHIN2myR", "reviewer": "Reviewer_WVvh", "summary": "This paper proposes to use generative models in a hierarchical framework of planned generations. A larger LLM produces a code making use of predefined tools, including smaller LLM calls, to generate an answer to a given query. This structure allows the framework to perform well at some tasks where direct LLM usage, even with CoT, would struggle (counting, constrained generation). It can also reduce inference cost and/or latency by using smaller models and parallel calls.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The proposed framework seems relevant for real-world applications, helping to reduce inference cost and latency while preserving or even improving the result quality.\nTargeted experiments show some good features of the proposed approach.", "reasons_to_reject": "Many building blocs are involved in this work and some of them are not thoroughly studied.\n\nIt seems that constraint satisfactions such as the one given in figure 1 are artificial tasks that are interesting as benchmarks to show features of LLMs capabilities but are not good performance indicators to be optimized. The proposed approach seems specifically good at solving this particular type of task but it is not convincing to show that the DisCIPL framework is more generally relevant. Puzzles tasks look somewhat more realistic but the dataset is very small. Showing more convincing use-cases seems important.", "questions_to_authors": "Here are some suggestion about some building blocs to study more thoroughly:\nThe paper compares the DisCIPL approach to a reasoning model as O1, it seems that both could be combined and a reasoning model might produce better plans. Additionally, only a weak follower model (llama3.2-1b) has been tested. Many other models could be considered at no extra cost: Qwen3 0.6b, or 1.7b are both stronger and could be considered, they offer versions with thinking abilities that could also be interesting to consider; gemini-flash models are largely available for free and could be applied through API calls; gemma3 1b would also be a good option with much stronger abilities than llama3.2-1b (I am aware that some of these might not have been available during the writing of the paper but other models, stronger than llama3.2-1b, were available. I listed the current strong options at a similar cost).\n\nThe inference cost comparison is not clear. Table 1 shows better results for the o1 model, but they come at an extra cost, how can we compare the cost of DisCIPL that involves potentially several calls to the planner models (until no error) and many cheaper calls to the follower models? Maybe using only API models could work, for example using GPT4.1 for planning and GPT4.1-nano as follower and comparing with o3 on accuracy and total cost. Which one has the shortest latency to the final answer?", "extra_scores": {}}, {"review_id": "PWU1hapezi", "reviewer": "Reviewer_DG1U", "summary": "This paper proposes DisCIPL, a meta-reasoning framework that leverages a Planner LM to generate a probabilistic inference program that guides one or more Follower LMs to complete complex tasks. To empirically demonstrate the effectiveness of DisCIPL, the authors apply the proposed method to two constrained generation tasks (COLLIE and PUZZLES), with GPT-4o as the Planner and Llama-3.2-1B as the Follower. The method shows reasonable improvement over baselines (Planner-only and Follower-only) with respect to the weighted Pass@1 metric used to measure (constraint satisfaction) validity.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The proposed method (DisCIPL) is interesting and novel. I think it is a good instantiation to show how we might effectively combine the recurrent computation and parallel computation of LMs at test time. \n2. The experimental design choices are reasonable to show the effectiveness of DisCIPL.The empirical results on COLLIE and PUZZLES make the method promising: the method enables a small LM (Llama-3.2-1B) to outperform GPT-4o and get close to reasoning LMs like o1.", "reasons_to_reject": "1. I am concerned about the latency (in seconds) and scalability of this method, since it is sampling token-by-token (with sequential monte carlo). How much slower, if any, is the method compared to o1? How would the method scale to larger LMs, e.g. >= 7B?\n2. It might be interesting to test the method on some tasks where coherence does not matter much, such as Game of 24, to make the empirical results more convincing and comprehensive (i.e. potential generalization to math reasoning).", "questions_to_authors": "1. While I understand the complicated probabilistic program is generated by the Planner via prompting, some statements and comments on the reproducibility and open-source plan of DisCIPL would be appreciated.", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is a paper on LLM inference architecture design. The architecture consists of a more powerful planner model which generates task-specific inference programs and a host of smaller executor models which implement these programs. Through this parallel design and by including techniques such as recursive search, this system can improve the cost accuracy Pareto frontier on tasks such as COLLIE, a constrained generation benchmark and PUZZLES, a dataset of tasks such as poetry, grant-writing, budgeting, and itinerary planning. It would be interesting to see what it takes to make this work on domains exact verifiers like competitive coding. The authors did a good job addressing the reviewers concerns and I'd like to recommend the paper for acceptance.
Decision: Accept