EnCompass: Enhancing Agent Programming with Search Over Program Execution Paths
Authors: Zhening Li
Armando Solar-Lezama
Yisong Yue
Stephan Zheng
Venue: NeurIPS 2025 poster ()
Keywords: AI agents
large language models
agent frameworks
angelic nondeterminism
inference-time strategies
test-time scaling
Primary area: infrastructure
TL;DR: programming framework that does runtime compilation of an LLM-based agent workflow into a search space, enabling independent experimentation of different overlaying inference-time search strategies

Abstract: We introduce a new approach to *agent programming*, the development of LLM-based agents. Current approaches to agent programming often entangle two aspects of agent design: the core workflow logic and the inference-time strategy (e.g., tree search). We introduce *probabilistic angelic nondeterminism* (PAN), a programming model that disentangles these two concerns, allowing the programmer to describe the agent workflow and independently experiment with different inference-time strategies by simply changing a few inputs. We provide an implementation of PAN in Python as the EnCompass framework, which uses a Python decorator to compile agent workflow programs into a search space. We present three case studies that demonstrate how the framework lets the programmer quickly improve the reliability of an agent and easily switch between different inference-time strategies, all with little additional coding.

ENCOMPASS: Enhancing Agent Programming with Search Over Program Execution Paths
Zhening Li' Asari AI, MIT CSAIL zhening. 1i@asari..a ai
Armando Solar-Lezama Asari AI, MIT CSAIL asolarOcsail. mit edu
Yisong Yue Asari AI, Caltech CMS yisongGasari.
Stephan Zheng
Asari Al stephan@asari. ai
Abstract
We introduce approach agent programming, the development of LLM- based agents. Current approaches to agent programming often entangle two aspects of agent design: the core workflow logic and the inference-tine time strategy (e.g., tree search). We introduce probabilistic angelic nondeterminism (PAN), programming model that disentangles these two concerns, allowing the programmer to describe the agent workflow and independently experiment with different inference-tine strategies by simply changing few inputs. We provide an implementation of PAN in Python as the ENCOMPASS framework, which uses a Python decorator to compile agent workflow programs into a search space. We present three case studies that demonstrate how the framework lets the programmer quickly improve the reliability an agent and easily switch between different inference-time strategies, all with little additional coding.
Introduction
Recent work has shown the power of scaling inference-time compute for LLMs II 2 where popular strategies include best-of-N sampling [3] 3 refinement 6 77, and tree search agents - systems that define how LLMs and other components interact to solve task these same strategies have become common ways of improving performance and reliability. Furthermore, several works have demonstrated the utility of applying sophisticated search and backtracking strategies in Al agents to improve performance various tasks g 10,
LLseb
14]
While various frameworks have been developed to simplify the low-level interaction between the program and the LLM 515 [6 [7 18), a framework for agent inference-time strategies has been absent. Our goal is to develop an inference-time strategy framework: framework that makes it easy experiment with different inference-time strategies independently of the design and implementation of the underlying agent workflow. Such framework is intended not to replace, but to be used in conjunction with LLM prompting and tool use frameworks, such as LangChain [15] or DSPy [16].
We target "program-in-comee
style agents, where one defines the workflow in code and uses In these agents, inference-time
the L.LM to accomplish specific subtasks [14 19 20
21 22
strategies have traditionally been limited to sampling and refinement loops 6, 19] whereas more sophisticated strategies such beam search and tree search have been rarely explored (14)
"Work performed as consultant for Asari AI "This "program-in-contro"" in-control" style contrasts with the "LLMM-in-comrool" style where the LLM decides the full sequence of operations (tool calls) in the workflow 10
13
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

compile
Irarchpplant)
ego 3in. secap ptppprtttr
#encompace .complee
soila rot egn, eotredi): Inarscheinnt))
search(
branchpetnne)
X
recors sole
(poow(pr search(...)
(a) ENCOMnASs Python code
(b) Underlying agent workflow
(c) Complied search space
(d) Overlaying search
Figure I: An ENCOMPASS program specifies an agent workflow, which is compiled into search space object, and inference- time scaling is accomplished through search over the nondeterministic execution paths of the agent workflow.
We identify the key bottleneck to be the entanglement of the inference-time scaling strategy with the core workflow logic when programming the agent. Programmers typically bake the inference- time strategy into the agent workflow [14] 19 20 [2]. which is inflexible, reduces readability, and limits the kinds of inference-time strategies that can be easily implemented. Therefore, we aim to design framework that cleanly separates the representation of the core workflow logic from the inference- time scaling strategy. The programmer could then make minimal modifications their agent to flexibly experiment with different inference-tine strategies. Also, different agents would no longer require custom implementations of the same inference- time strategy, but can instead reuse common implementation.
Our key insight that inference-time strategies can be viewed instances of search over different execution paths of a nondeterministic program. We developed the ENCOMPASS Python programming framework ("enhancing agents with compiled agent search"), depicted Figure I Figure I and Figure ITb show an agent program and its corresponding workflow, respectively. The user specifies the "locations of unreliability" in their agent source code using branchpoint () statements. A location of unreliability is an operation such as an LLM call where repeated invocations produce outputs of varying quality. Since these different outputs give rise to multiple possible futures of the program's 's execution, the program has a tree of possible execution paths. ENCOMPASS compiles the program into search space object (Figure [e> so that search can conducted over this tree of execution paths to find the path with the highest score (Figure [d).. We call this programming model probabilistic angelic nondeterminism (PAN). As a form of angelic nondeterminism 23), PAN lets the programmer write their program pretending the unreliable operations always produce good outputs, and the runtime searches the space possible exccution paths for one where the operations indced produced good outputs.
Our work makes the following conerete contributions:
We introduce the PAN programming model (Section 2.1 which uses angelic nondetermin- ism to separate inference- algorithms (search policy) from the underlying logic of the agent (specification of the search space).
We present ENCOMPASS, a Python library that implements PAN (Section 2.2 providing 1. primitives like br branchpoint () that the programmer can use inside their ENCOMPASS function, 2. a Python function decorator that compiles an ENCOMPASS function into a search space object at run-time, and 3. common search algorithms, as well as an interface for implementing custom search algorithms.
We illustrate how ENCOMPASS provides unifying framework for common inference-tine time strategies and agentic patterns, which are special cases of search over nondeterministic execution paths of ENCOMPASS programs (Section 3). ENCOMPASS also provides a natural generalization of these inference-time strategies.
We present case studies showing how ENCOMPASS enables easy experimentation of various inference-ting -irencee-tmeeaaee search strategies over an underlying agent workflow, allowing one to quickly identify the pest-performing strategy (Section 4). ENCOMPASS opens up new possibilities for inference-time scaling of program-in-control style agents, where inference-time strategies that were previously considered too cumbersome to implement are now made possible by EN COMPASS.

---

2 ENCOMPASS, a Python framework for PAN
In this section, we introduce the PAN programming model (Section 2.1 and describe its Python im- plementation in the ENCOMPASS framework (Section 2.2). For simplicity, we will ignore the feature
of memory sharing across different program execution paths (see Section 3.2). The documentation
for ENCOMPASS is in Appendix B and the ENCOMPASS compiler is described in Appendix C
2.1 Probabilistic angelic nondeterminism (PAN)
The core idea of PAN is to search over the tree of possible execution paths of probabilistic program where some operations (e.g.. L.LM calls) have randomness - to find the path that optimizes a user-speciffed objective. Given probabilistic program with branchpoints at certain locations in the program, we model its computation as a Markov chain over the space of possible program states. The Markov chain consists of the following components:
Branchpoints and the end of the program constitute a set of marked locations in the program. In Figure [ branchpoints are denoted by blue dots
A program state is pair consisting of marked location of the program and memory state, which mapping from variables values.
The code that executes from one marked location the next defines a probabilistic transition function that maps from a program state to the next program state. Program states at the end of the program are final, i.e., they have no next states, In Figure transitions are denoted by colored boxes
The initial state is the program state resulting from executing the program from the start until hitting the first branchpoint.
Normally, executing the probabilistic program results in one sampled trajectory of program states (Figure (p). In PAN, however, we search over the space of possible trajectories (Figure [d). Our search tree initially has just one node: the initial program state. At every step, the search policy chooses node in the current search tree, makes copy of the program state stored that node, samples a next program state according to the probabilistic transition function, and adds it to the search tree child of that node. The goal is to reach final program state that optimizes user-specified objective.
Note that search here is formulated differently from the usual graph search formulation because we don't have access to all the children of any given node - we can only stochastically sample children of parent node. However, existing graph search algorithms can be converted to algorithms in PAN by specifying each node's s branching factor, i.e., the number of children to sample. For example, depth-first search (DFS) with branching factor 3 involves sampling next states from the current state and recursing on each child.
This way of adapting graph search algorithms is currently the dominant approach in -ased agents that have tree search with an unenumerable action space of LLM outputs [8] 13 24
25).
However, we believe it is worth exploring search strategies beyond fixing the branching factor in an existing graph search algorithm, and Case Study 3 (Appendix (A.2) explores this direction by showing that a simple strategy repeatedly choosing the highest-scoring program state and sampling one next state can work quite well.
2.2 ENCOMPASS
The ENCOMPASS framework provides an instantiation of the PAN programming model in Python. implemented as the @encompass compile function decorator, which makes several new primitive keywords available in the body of the decorated function; the full list is given in Appendix B. The decorator compiles the function body into a search space object, which provides an interface for implementing search algorithms (Appendices B.2 and B.3 The compiler is described in Appendix C
Core primitives PASS-decorated function are branchpoint () and record_ecccoooc score ().
The most important primitives that are available in the body of ENCOM-
branchpoint (** branchposntttpppy
3

---

This statement marks a PAN branchpoint (Section 2.1 program state added as new node the search and the program's 's execution may branch into multiple execution paths.
location in the program where the
Branchpoint parameters provide information to the external search algorithm about the branch- point. For example, branchpoint (name="foo") gives the branchpoint a name that can be used refer the branchpoint in the search algorithm.
record_score (ww.rrrrrrrrree (score)
This records the numerical "score" used to guide the search process many search algorithms (e.g.. the heuristic in best-first search and value function in MCTS). Furthermore, the final score (the last score recorded before returning) usually specifies the final evaluation score be maximized by the search algorithm.
Inference-time search can now apply search over its nondeterministic execution paths by calling
Having defined an ENCoMPAsS--ecorate function func, the programmer
func(.... .) search (algo, **coo, **search_comff4
where algo is string such "dfs" "beam" specifying the search algorithm. This returns the function's is return value on the best execution path that search algorithm a algo could find. Appendix B.4 lists all algorithms that ENCOMPASS provides out-of-the-box.
Custom search algorithms The user can also define and register their custom search algorithm so that it can be invoked through the same search interface. The Checkpoint class wraps the program state and provides an interface for implementing custom search algorithms. Its step() method samples next program state: it resumes execution of the program from the current state until hitting the next branchpoint or a return statement, returning the new program state (cf. the probabilistic transition function from Section 2.1 The Checkpoint object's score attribute contains the score of the program state recorded through record_scored () See Appendix B.3 for more details.
3 Agent inference-time strategies in ENCOMPASS
While ENCOMPASS appears most suitable for implementing tree search in agents, other common inference-tine strategies can also be cleanly implemented search in ENCOMPASS. Furthermore, natural generalizations of these strategies that are otherwise difficult to implement are also easily represented in ENCOMPASS.
3.1 Best-of-N sampling and beam search
Given agent agent_ forward agentt_fowward(... of the agent, best-of-N (BoN) samples N times and chooses the output with the highest evaluation score. In ENCOMPASS, this is done by adding branchpoint the beginning of the function and recording the evaluation score at the end:
and an evaluator evaluate ( that evaluates the output
Boncompass. compile
def poont_forvard(....
branchpoint()
Driginal body agent
wew.erreeeaauuueeeeeeeee return result
agent_fforsrdd s.aaddd(....sssac......... search(...)
This defines a search tree with depth 1, where almost any search algorithm would sample several children from the root node and return the best child, thus reproducing best-of-N sampling.
call the above global best-of-N (GBoN) to contrast with local best-of-N N (LBoN), where an agent with multiple verifiable steps has best-of-N sampling applied each of them. In ENCOMPASS, this implemented by adding branchpoint () before each step and applying beam search with beam width 1:

---

denconpass compile def coant__forardd.... branchpoint: # Step 1
record_scoos wtt.ssscssaaatttttttooo......... (...))
branchpoint
Step 2 record_scare http_e/ccrccoootttoottt.......
branchpoint:))
# Step k 12 aucord_scoreeevallee
11
accoraavallutto.ttppk..c..
13
return reeuur
14
15
the "X" best-of-K
16 reault
agent_ aearch ("bean", bean_width-1,, Sorfalt__bracchnnee
Note that the two types of best-of-N sampling described this section globall and local sampling- are the two limiting cases of beam search. Global best-of-N sampling is beam search with beam width N and branching factor whereas local best-of-N sampling is beam search with beam width I and branching factor N. General beam search can thus be viewed interpolating between global and local resampling. This has the benefit effectively constraining the search space with local verification while also not losing global variety. Increasing the branching factor makes sure each step completed correctly to help prevent compounding errors, while increasing the beam width can help increase variety and thus improve reliability to mitigate potential errors made in earlier steps. In Case Study (Section 4. we empirically demonstrate that beam search indeed scales better than global best-of-N local best-of-N alone in complex agent workflows.
The ENCOMPASS implementation beam search over an agent workflow also benefits from flexibility in modifying the step granularity. Increasing the granularity (dividing steps up into smaller substeps) or decreasing the granularity (merging multiple steps into one) is as simple as adding or removing branchpoints in ENCOMPASS, whereas plain Python implementation would require structural changes to the code.
3.2 Refinement and backtracking with memory
Refinement can be viewed as sampling but with additional feedback from past sampling attempts. In ENCOMPASS, this is accomplished by adding a branchpoint generate multiple samples and memory of past attempts shared across the different sampled execution paths:
Concompass compile
def agent_forvardd....))
... stuff that
# Step with refinenent
feedbacke: McCopy
branchpoint:)
result do_etep(.... feedbacks) score, feedback www.corre.aa..fcccccceeeeee..ee.
faedbackss (faadbaak))
10
secordsscore(ccord
11
stuff that after
12
result
agent_ (earch("beaat" width-1 default, Breautt.braachiing-_rrrrre
Here, the NoCopy type annotation tells the ENCOMPASS compiler that the different execution paths should share the same reference to the feedbacks variable, so that appending feedback seen across all branches f
By adding another branchpoint () right before "feedbacks: NoCopy = ['", we create multiple parallel refinement loops, thus interpolating between fresh sampling and refinement and maintaining variety that may otherwise be lost from an agent that focuses heavily on the past feedback. This not unlike how beam search interpolates between global best-of-N and local best-of-N (Section [.1] In Case Study 3 (Appendix (..)) we demonstrate how different approach interpolating between refinement and sampling by adding branchpoints to refinement loop written in plain Python can result in better scaling than refinement alone.
3 Exceett that root node branching factor
"This effect is lost if feedbacks. append (feedback) is replaced with feedbacks feedbacks feedback], since that creates list instead of modifying the original one.
5

---

Note that refinement is the simplest case of backtracking with memory: backtracking to previous step while remembering what happened in previous attempts. ENCOMPASS, the general patter for backtracking with memory is to create shared mutable data structure right before branchpoint, which serves as a memory shared across all execution paths that follow.
3.3 Seff-consistency and group evaluation
Given an agent program agent_forward (input), self-consistency samples N times and chooses the output that appeared the most times (the majority vote) (26]. This be implemented as best-of- N sampling with an evaluation function that evaluates group of results at once. The ENCOMPASS record_ score(e supports this:
(ooeeity counts dofaultdict(nnt) for result
Genconpase compile
10 def for
branchpoint:))
counta [result] +- return (resul]) for result results
reault
record_score score(najorityyyvoe. result, label-Noze)
result
agent_forvard(... seaaaadd........r........ search(....)
In general, allowing the evaluation function to evaluate group of results at once is helpful when is difficult evaluate result its own. Another example of this is CodeT [2], which evaluates group of L.M-generated code samples against multiple -.g-enerrteed unit test cases by considering
both the number of unit test pass rate and agreement among code samples which test cases they pass.
Inference-time strategies like self-consistency and CodeT are examples of the more general search with evaluation of a group of execution paths in tandem. When one writes
record_score (group_eveall evaluator, evaluation target, label=group_1 label)
the scores of all program states where record_scored () called with label group_ label computed as group. evaluator( evaluation, targets), where evaluation, targets is the list of the evaluation, target variables across all the program states.
4 Case studies
We implemented and extended 3 program-in-contron style agents from the literature in ENCOMPASS. These case studies aim to answer the following research questions:
Does ENCOMPASS make it easier implement inference-time strategies and search in program-in-control style agents, and if so, how?
Does ENCOMPASS simplify experimenting with different inference-time strategies and search in program- program-in-control style agents, and if so, how?
Our case studies suggest that ENCOMPASS enables the exploration of inference-tine time strategies that are otherwise left unexplored due to their complexity implementation potentially unlocking better scaling laws.
Case Study our main case study and is presented in the main text here. Case Studies 2 and 3 are smaller and more didactic in purpose, and are presented in Appendix
we implement a lava-to-Python code repository translation agent with high-level architecture based on that of Syzygy (28). We then add branchpoints before LLM calls and, by toggling few parameters, local/global best-of-N N sampling and beam search at the file level and individual method level. We demonstrate these experiments on Java repositories from the MIT OCW Software Construction class. We find that beam search outperforms simpler sampling strategies, thus demonstrating how one can use ENCOMPASS to discover better inference-time scaling laws. Furthermore, we show how the equivalent plain Python implementation of the ENCOMPASS agent involves defining the search graph as a state machine, where the agent workflow is significantly obscured and modularity is compromised, whereas ENCOMPASS solves these issues.
In Case Study 1 (Section
experiment with variety of search strategies including

---

Table 1: Code modifications to implement search in our case studies, without ENCOMPASS vs. with ENCOMPASS. Metrics include the number lines/words added, changed and removed, the number of new function definitions, and the number lines of the original code where the indentation level was changed. For context, we also give the number of lines of code used to implement the core logic of the original base agent. All code is found in Appendix D with the modifications annotated.
This excludes changes to the indentation level of existing code. Thhe "core logic" defined as the functions that require modification when implementing search, hence excluding unmodified code like helper/utilityy functions and prompt templates.
Added lines (words)
Changed lines (words)
Removed lines (words)
New
Indent changed
Case Study
f'ns
1. Code Repo Translation LoC 597
ENCOMPASS +ENCOMPASS
+423 (+2735)
24 (-62/+186)
(-28)
+20
189
+75 (+514)
8 (-0/+40)
(-0)
+1
0
2. Hypothesis Search
-ENCOMPASS
+21 (+120)
3 (-1/+13)
--0)
+2
10
LoC = 11
+ENCOMPASS
+8 (+27)
(-0/49)
--0)
+0
0
3. Reflexion
EENOMPAASS
+27 (+181)
6 (-13/+31)
(-0)
+2
8
LoC 20
+ENCOMPASS
+9 (+32)
3 (-4/+13)
(-0)
+0
0
In Case Study 2 (Appendix A.1 we implement a simplified Hypothesis Search agent 19 We start with simple agent with two LLM calls. By adding branchpoint before each LLM call and applying multithreaded BFS out of the box, we reproduce a parallelized version of Hypothesis Search. We demonstrate how use ENCOMPASS to experiment with different search strategies (BFS vs. global best-of-N), and find that they perform equally well on subset of the ARC benchmark [29], the benchmark that Hypothesis Search used. We show how, despite the simplicity of the original agent, the equivalent program in plain Python already noticeably obscures the underlying agent workflow.
In Case Study 3 (Appendix A.2), we start with Reflexion 77. simple agent with refinement loop. We add a branchpoint at the beginning of the agent and at the beginning of the body of the refinement loop, and apply both global best-of-N and variant of best-first search. Following the original Reflexion paper, we evaluate on Herd We find that increasing N in best-of-N or the number of search steps in best-first search scales better than increasing the number of refinement iterations in vanilla Reflexion. We also show how the equivalent program in plain Python obscures the control flow and data flow of the underlying agent.
Table T and Appendix D compare the code modifications required to implement search with EN- COMPASS vs. without ENCOMPASS. On average, ENCOMPASS saves 3-6x of coding in terms of the number of lines/words that are added or changed.
Note that since ENCOMPASS targets program iieemm-i--coonnn co-conlrol style agents, our case studies do not include benchmarks of LLM-in-control style agents such as SWEBench (30) or WebArena (1
4.1 Case Study 1: Code Repository Translation Agent
In this case study, we demonstrate how to use ENCOMPASS to add branchpoints and implement search in lava-to-Pythor code repository translation agent based on the Syzygy agent architecture (28). By comparing with the equivalent plain Python implementation, we identify several concrete benefits of the separation of concerns offered by ENCOMPASS. We also demonstrate experimenting with different search strategies on one repository to find the best-performing strategy ('fine-grained beam search), and we apply this strategy to other repositories to obtain strong performance compared to simpler strategies (global/local best-of-N).
Base agent We built an agent that translates a Java repository into Python (Listing 18 The agent translates the repository byle-b dependency order. For each file, the agent calls the LLM to write the skeleton of the Python file, and for each Java method the agent calls the LLM to translate it into Python. Every translation followed by validation of the translation by 1) asking the LLM to write script that generates random test case inputs; 2) asking the LLM to write Java code to run the Java method on those inputs; 3) asking the L.MM to write Python code to run the translated Python method those inputs; and 4) comparing the Python and Java outputs to see if they match.
7

---

The ENCOMPASS agent In ENCOMPASS, we modify the base agent by adding a branchpoint before each of the LLM calls present the program (Listing[9)- To prevent different branches of the search from overwriting the same folder, we use Git to manage the repository, and write wrapper branchpoint. _eatttggtttttttt commit () around the built-in branchpoint (Listing 19. 1.5-15). We consider search at two different levels of the translation workflow: the file level ("coarse"), and the method level ("fine"). By adjusting the search parameters, we experimented with different search strategies at each level as well as different parameters to the search strategies. We applied 6 combinations of search strategies: "global best-of-N"", "local best-of-N (coarse)", "local best-of-N (fine)", "beam (coarse)", "local best-of-N (coarse) beam (fine)", and "beam (coarse) beam (fine)".
This was simple as changing a couple of parameters: the file-level search strategy specified at line 278 of Listing [9 and the method- search strategy is specified at line 264. Section 3.] explains the search algorithm and parameters passed to the searchh mul tiple ( method to implement global BoN, local BoN, and beam search.
Comparison with equivalent plain Python We demonstrated how ENCOMPASS lets an agent programmer easily switch between different search algorithms. To replicate this flexibilityy in plain Python, we need explicitly define the search graph that the ENCOMPASS function defines. The search graph takes the form of state machine where the states correspond to the branchpoints and the transitions follow the control flow the program. We maintain a dictionary frame with all the local variables of the program as we go through the transitions of the state machine. The result is Listing 20) which is long and difficult to read, so we illustrate this with a simplified version of our code repository translation agent that iterates through functions in source file, translating each of them by--by-
Bencompass. compile
2 def tranalate, functionn (source);
for source_fe branchpoint())
targat_fn tranclate(seurca_ft)
compile_success compile_ (target__)))
branchpoint()
10
sait_test__scom uun_uii__eestttrree
11
record_score (init_test__ccre)
The equivalent state machine in plain Python is given here with minor simplifications.
: TRAKSLATE auto
UNIT, UNIT_TEST TEST auto
def stop(stata: State, frame: dict(str, Any]):
frane frane.copy()
state
frane ["target__ translate (franee (wwaaearaaanauuuaaeeeaa ["aource_ [n"")
10
(framee return State. UNIT_TEST. frane, cospile_success
compile_ compile_eucoed succege compile_ (frame ("target__[""))
12
13
UNIT_
14
unit_ test, score run_unit__eee umiit_test(fte (frane "ttrgatt_f""] frane ["source_fn"" next souurca"]) return State. TRANSLATE, frane, unit, telt.teett_.core
15
16
Notice that the high-level control flow of "repeatedly translate and unit-test the translation" is no longer obvious from the code; difficult know whether any given variable access frame [...] might throw KeyError; and linters and static type checkers can't 't't be applied because variables are accessed through the frame dictionary. Furthermore, simple changes to the ENCOMPASS function such moving or removing a branchpoint would require significant structural changes to the state machine code that further create an opportunity for bugs. All these issues are exacerbated as we increase the complexity of the agent program, the state machine approach to defining agent search graphs not scalable. This can be seen Listing 20 (Appendix D.I. which applies the state machine approach to the original code repository translation agent.
Evaluation setup make affordable to run comprehensive experiments comparing the scaling behaviors of various inference-time strategies, first validated small repository consisting of

---

80
6.6
(%)
6.5
70
Self-elidation
2.
60
0.3
Cost (9)
Repository
GDth
LDoN (C-)
LOoN (5)
beam
L5OM
beam
COcN
LOON
beamn beamn
Figure 2: Results of using ENCOMPASS to apply different inference- time scaling methods to the code repository translation agent. All error bars show standard errors of the mean over 5 runs. (a) A comprehensive hyperparameter search for ps0: (b) For ps1 to ps4, we applying global best-of-N ("GBoN"), file-level local best-of-N ("LBoN (c.)"), and beam search at the file and method level ("beam (c.) + beam (f.)") while controlling for cost.
622 lines of Java code. The repository contains solutions to the first homework (ps0) from the Spring 2016 version of the MIT Software Construction class available on MIT OpenCourse Ware [32 33).
Because of the scarcity of test cases in the original repository, we use self- relf-validation (%) as the evaluation metric, which is calculated as the percentage match of the Python and Java outputs on the automatically generated test inputs, averaged across all translated non-test methods. If any step of the validation process failed (e.g., test input generation), then the match percentage is considered to be 0.
After identifying the inference-time strategy that scales best on psO, we evaluated it on the other repositories from the class (ps1 ps4). Each of them contains between 1 100 and 1900 lines of code, and all 4 repositories combined contain 5756 lines of code.
For all experiments, we set the LLM temperature to 0.0 for the base agent (no inference-time strategies), and 0.5 for the ENCOMPASS agent (with inference-time strategies).
Evaluation results Figure 2a shows a log-linear plot of the scaling of various inference-time strate- gies on psO. Consistent with prior work on inference-time scaling [4] (5, find that performance scales linearly with the logarithm of the cost (all x² p-values > 0.3). The best scaling is achieved with beam search applied both the file level and the individual method level ("beam (coarse), beam (fine)"), outperforming the second best strategy "beam (coarse)" with a p-value of 0.2 and all other strategies with statistical significance (p= < 0.03).
Notably, the best- pest-performing strategy ("beam (coarse), beam (fine)") also happens to be the most difficult one to implement in plain Python. It requires the programmer break up the entire workflow into all the individual LLM-calling steps where each step explicitly stores and retrieves variables from frame dictionary. This finding further demonstrates the merits of having framework like ENCOMPASS where experimenting with different search strategies can be done via simply changing few parameters. Combinations of agent and inference-time strategy that have better scaling but that programmers would otherwise choose not to implement due to their complexity of implementation, now made possible by ENCOMPASS.
We then evaluated the best-performing strategy "beam (coarse), beam (fine)" on ps1 through ps4 and compared it with two simpler baselines ("global best-of-N" "local best-of-N")) while controlling for cost. For beam search, we used a file-level beam width of 2 and a method-level beam width of was
3. whereas used N 16 for both global and local best-of-N. The average cost of $20-$20.5 for ps1, $27-$30 for ps2, $36-$39 for ps3, and $13.5-$14 for p84. The results are shown in Figure 26 Overall, "beam (coarse), beam (fine)" continues to outperform the other two simpler strategies.
To conclude, we have demonstrated the advantages of the separation of concerns offered by ENCOM- PASS. Implementing an inference-time strategy in ENCOMPASS mainly involves adding branchpoints before L.M calls, whereas without ENCOMPASS, significant source code modification that obscures the underlying workflow is often necessary. Furthermore, experimenting with different inference-time strategies in ENCOMPASS is often simple changing a few search parameters.

---

Related work
2 provides a comprehensive review of algo- rithms used during LLM inference to improve its reliability and performance. Examples include best-of-N sampling 4 5I, refinement 6 77 cofsisonsst [26]. and tree search [8] g 13].
Inference-time strategies for LLMs and agents
which are also commonly used in LLM- based agents [TO 12 14]. Section demonstrates how ENCOMPASS unifies and generalizes these inference-time scaling strategies for agents.
AT agent frameworks Several LLM-based agent frameworks have been developed to abstract away boilerplate code and other low-level concerns, and provide abstractions for common agentic patterns and components. AutoGen [88] simplifies multi-agent conversation workflows with tool use, LangChain [5] simplifies linear workflows with RAG and tool use, LangGraph [4] simplifies the creation of agent workflows state machines, and DSPy [16] automates prompt engineering. Complementary to these efforts, our framework, ENCOMPASS. simplifies applying inference- time scaling strategies to agents. Since ENCOMPASS involves adding statements such branchpoint () to an existing agent written in Python, it can be flexibly incorporated into agents built with an existing Python agent framework.
Angelic nondeterminism Previous implementations of angelic nondeterminism include John McCarthy's amb operator in Common Lisp B3 and the list monad in Haskell [36]. The main conceptual difference is that ENCOMPASS implements a probabilistic form of angelic nondeterninism, which samples from a probability distribution such as LLM instead of choosing from given set of choices.
Probabilistic programming Our work is also inspired by probabilistic programming, program- ming paradigm that separates the two main concerns of probabilistic inference: specifying the probabilistic model and implementing the inference algorithm. (See, e.g., (37] for review.) This allows the programmer to efficiently specify a probabilistic model in code while independently experiment with different probabilistic inference algorithms. Similarly, ENCOMPASS aims to separate the two main concerns of agent programming; specifying the core agent workflow and implementing the inference-time search strategy.
Limitations
ENCOMPASS targets program-in- in-control style agents, where implementations without ENCOMPASS typically force the programmer to entangle the underlying agent and the overlaying search strategy. ENCOMPASS is not meant for LLM-in-control style agents, where the aspects already decoupled. Nevertheless, there has been increased interest in "LLMMproggamm cintoogrra--i-coooroo conconto hybrid style agents which involve an LLM writing mooraam-i--contor style agent [38 39 40). It would be interesting to explore using ENCOMPASS to make it easier for the LLM to implement inference-time strategies LLM-calling programs that it writes.
Although ENCOMPASS simplifies the source code modifications needed to apply inference-ting strategies to existing agent, modifications still needed. There remains the engineering challenge of choosing the correct places to add branchpoints, adding sufficient and good-quality intermediate reward/verification signal, and designing good search algorithm. ENCOMPASS could be improved to eliminate the need for source code modifications entirely, where it solves the the majority of these remaining challenges by potentially using flexible L.LM-based search strategy.
7 Conclusion
This work introduced the ENCOMPASS programming framework, which decouples the two fundamen- tal aspects of agent programming: defining the core agent workflow and designing the eiference-time scaling strategy. By enabling the integration of sophisticated search strategies into complex agent workflows, ENCOMPASS opens up new possibilities for inference-time scaling of Al agents. Looking ahead, we anticipate that the ability to seamlessly combine agent workflows with powerful search techniques - enabled by ENCOMPASS - will unlock new scaling laws and drive the development of reliable LLM-augmented systems for solving complex real-wor world tasks.
10

---

References
[1] Charlic Victor Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time com- pute optimally can be more effective than scaling parameters for reasoning. In The Thirteenth International Conference on Learning Representations, 2025.
[2] Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf, Alex Xie, Graham Neubig, Ilia Kulikov, and Zaid Harchaoui. From decoding meta mnta-ggeneattion Inference- algorithms for large language models. Transactions on Machine Learning Research, November 2024.
[3] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. /4/68, 2021.
[4] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024.
[5] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with AlphaCode. Science, 378(6624);1092-1097 2022.
[6] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-Refine Iterative refinement with self-feedback. Advances Neural Information Processing Systems, 36, 2024.
[7] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
[8] 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. Advances in Neural Information Processing Systems, 36, 2024.
[9] Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, James Xu Zhao, Min- Yen Kan, Junxian He, and Michael Xie. Self-evaluation guided beam search for reasoning. Advances in Neural Information Processing Systems, 36, 2024.
[10] Andy Zhou, Kai Yan, Michal Shlapentokh-Rothene Language Agent Tree Search unifies reasoning, acting, and planning in language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 02138-62160 PMLR, 21-27 Jul 2024.
Haohan Wang, and Yu-Xiong Wang.
[11] Jing Yu Koh, Stephen McAleer, Daniel Fried, and Ruslan Salakhutdinov. Tree search for language model agents. arXiv preprint wxXv::407.011776 2024.
[12] Antonis Antoniades, Albert Örwall, Kexun Zhang. Yuxi Xie, Anirudh Goyal, and William Yang Wang. SWE-Search: Enhancing software agents with monte carlo tree search and iterative refinement. In The Thirteenth International Conference Learning Representations, 2025.
[13] Kaiyu Yang, Aidan Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan Prenger, and Animashree Anandkumar. LeanDojo: Theorem proving with retreeval-augmented language models. Advances in Neural Information Processing Systems, 36, 2024.
[14] Yutaro Yamada, Robert Tjarko Lange, Cong Lu, Shengran Hu, Chris Lu, Jakob Foerster, Jeff Clune, and David Ha. The Al Scientist-v2: Workshop-level automated scientific discovery via agentic tree search. arXiv preprint arXiv:2504.08066, 2025.
[15] Harrison Chase, Bagatur Askaryan, and Erick Friis. LangChain 0.3.16, 2025.

---

[16] Omar Khattab, Arnav Singhvi, Paridhi Maheshwari. Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan A, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. DSPy: Compiling declarative language model calls into late-of-the-an pipelines. In The Twelfth International Conference on Learning Representations, 2024.
[17] Luca Beurer-Kellner Marc Fischer, and Martin Vechev. Prompting is programming: A query language for large language models. Proceedings of the ACM on Programming Languages, ((PLD)):1946-166) 2023.
[18] Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, Ahmed Hassan Awadallah, Ryen W White, Doug Burger, and Chi Wang. AutoGen: Enabling next-gen LLM applications via multi multi-agent conversations. In First Conference on Language Modeling, 2024.
[19] Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah Goodman. Hypothesis search: Inductive reasoning with language models. In The Twelfth International Conference on Learning Representations, 2023.
[20] Ali Reza Ibrahimzada, Kaiyao Ke, Mrigank Pawagi, Muhammad Salman Abid, Rangeet Pan, Saurabh Sinha, and Reyhanch Jabbarvand. AlphaTrans: A neuro-symbolic compositional approach for repository-level code translation and validation. Proceedings of the ACM on Software Engineering, 2(FSE):2454 2476, 2025.
[21] Pei Zhou, Jay Pujara, Xiang Ren, Xinyun Chen, Heng-Tze Cheng, Quoc V Le, Ed Chi, Denny Zhou, Swaroop Mishra, and Huaixiu Steven Zheng. Self-Discover: Large language models self-compose reasoning structures. Advances in Neural Information Processing Systems, 37:126032- 126058, 2024.
[22] Chris Lu, Cong Lu, Robert Tjarko Lange, Jakob Foerster, Jeff Clune, and David Ha. The AI Scientist: Towards fully automated open-ended scientific discovery. arXiv preprint arXiv:2408.06292, 2024.
[23] Robert W Floyd. Nondeterministic algorithms. Journal of the ACM (JACM), 14(4):636-644, 1967.
[24] Di Zhang, Xiaoshui Huang, Dongzhan Zhou, Yuqiang Li, and Wanli Ouyang. Accessing GPT-4 level mathematical Olympiad solutions via Monte Carlo Tree Self-Refine with Llama-3 8B. arXiv preprint arXiv:24066073394 2024.
[25] Ziyu Wan, Xidong Feng, Muning Wen, Stephen Mareus Mcaleer, Ying Wen, Weinan Zhang, and Jun Wang. AlphaZero-like tree-search can guide large language model decoding and training. In International Conference on Machine Learning, pages 19890-49922 PMLR, 2024.
[26] Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. 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 Representations, 2023.
[27] Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian- Lian-Guang Lou, and Weizhu Chen. CodeT: Code generation with generated tests. In The Eleventh International Conference on Learning Representations, 2023.
[28] Manish Shetty, Naman Jain, Adwait Godbole, Sanjit A Seshia, and Koushik Sen. Syzygy: Dual code-test C to (safe) Rust translation using LLMs and dynamic analysis. arXiv preprint vrXiv:2412.14234 2024.
[29] François Chollet. On the measure of intelligence. arXiv preprint 1rXi::1911.015547,2000
[30] Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik R Narasimhan. SWE-bench: Can language models resolve real-world github issues? In The Twelfth International Conference on Learning Representations, 2024.
12

---

[31] Shuyan Zhou, Frank Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou. Yonatan Bisk, Daniel Fried, et al. WebArena: A realistic web environment for build- ing autonomous agents. In The Twelfth International Conference on Learning Representations, 2024.
[32] Denis Savenkov. github cwwm:/iizayBubbleeeiiiT-...0.. 2017.
[33] Robert Miller and Max Goldman. 6,005 - Software Construction on MIT OpenCourse Ware: Problem Set 0: Turtle Graphics, 2016.
[34] Nuno Campos, Barda Vadym, and William Hinthorn. LangGraph 0.2.68, 2025.
[35] John McCarthy. A basis for mathematical theory of computation. In Computer Programming and Formal Systems. North-Holland, 1963.
[36] Philip Wadler. Monads for functional programming. In Advanced Functional Programming: First International Spring School on Advanced Functional Programming Techniques Båstad, Sweden, May 24-30, 1995 Tutorial Text 1, pages 24-52. Springer, 1995.
[37] Noah D Goodman. The principles and practice of probabilistic programming. ACM SIGPLAN Notices, 48(1):399944444 402, 2013.
[38] Chengshu Li, Jacky Liang, Andy Zeng, Xinyun Chen, Karol Hausman, Dorsa Sadigh, Sergey Levine, Li Fei-Fei, Fei Xia, and Brian lchter. Chain of code: Reasoning with language model- augmented code emulator. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages PMLR, 21-27 Jul 2024.
[39] Shengran Hu, Cong Lu, and Jeff Clune. Automated design of agentic systems. In The Thirteenth International Conference on Learning Representations, 2025.
[40] Xunjian Yin, Xinyi Wang, Liangming Pan, Li Lin, Xiaojun Wan, and William Yang Wang. Gödel agent: A self-referential agent framework for recursively self-improvement. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 11890-279133 Vienna, Austria, July 2025. Association for Computational Linguistics.
[41] Cormac Flanagan, Amr Sabry, Bruce F Duba, and Matthias Felleisen. The essence of compiling with continuations. ACM Sigplan Notices, 28(6):237-247, 1993.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract summarizes the problem and the proposed solution; the introduc- tion defines the scope, identifies the problem, and summarizes the proposed solution and contributions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Limitations section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [NA]
Justification:
The paper proposes programming framework and makes no theoretical
claims.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Compiler details are in Appendix C Case studies describe experimental setup. Agent programs of case studies are in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
Company code
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puulic//uui /tti:///guideeeoooouuuuumbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See case study sections.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
See case study sections, including tables and figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Case study sections describe LLM costs and CPU used.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
No aspect of the research violated the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Foundational research with standard expectations in regards to societal impact
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No release of data/models with a high risk for misuse
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Existing agents and benchmarks cited and license terms followed
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used to help produce this research other than coding and writing tool.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
20

---

A Additional case studies
This appendix presents Case Studies 2 and 3. In these case studies, we study agents much simpler than the code translation agent in our main case study (Case Study 1) so that we can more explicitly compare code written ENCOMPASS vs. plain Python. Our objective to illustrate and under- stand how the modularity that ENCOMPASS provides lets programmers more easily implement and experiment with different inference-time scaling strategies for their agent.
Experiments for all case studies were conducted on a Macbook Pro with an M3 chip and 18 GB of RAM. All LLM calls were made through the OpenAl API.
A.1 Case Study 2: Hypothesis Search Agent
In this case study, we use a simple two-step agent for ARC-AGI 22 to illustrate how ENCOMPASS enables the programmer quickly implement inference-time search.
Base agent A task in ARC-AGI shows the agent around 3 validation examples of input-output grid pairs, and the objective is find the rule that transforms input grids into output grids and apply the rule to a test input grid. A simple agent for solving ARC-AGI tasks is as follows (Listing D:: 1. ask the LLM for a natural language hypothesis of the transformation rule; 2. ask the LLM implement the hypothesis in code.
def tt___ste___pee (task_info)) info):
Step 1: Get natural language hypothesis
hypothesis = agpothesia_agent [[task_inftt] hypothesis,
Step Implement the hypothesis in code
code solver_ ([task, info, hypothesis], solver salver_instructionn
return get_teat_outee outptootuuuuutut (code) Listing 1: Simple 2-step agent for ARC
The ENCOMPASS agent To convert this agent into a ENCOMPASS program, we identify the points of unreliability: the two LLM calls. Before each LLM call, allow the external search algorithm to search over different samples from the LLM. Finally, we add final verification step that evaluates the generated code the validation grid pairs, so that the search algorithm knows which execution paths did better. Here is the resulting ENCOMPASS agent (Listing :
add branchpoint
Gencompass. compile
def two_step_ageeteee asent (task_info). info):
# 1st branchpoint results in multiple samples of the natural language hypothesis branchpoint()
Step Get natural language hypothesis
hypothesis = hypothesis_agent (oteent([tsk___. [[[ask_innattt
2nd branchpoint results multiple code samples for each hypothesis branchpoint()
10
11
Step 2: Implement the hypothesis in code
code = solver agent ([task info, hypothesis], solver instructisttttiion)
15
Evaluate
16
percent_ percent_correct, feedback = run_val cun_validation(coda record_score (u_ceetet))
if percent_correet correct 1.0:
19
early_stop_search
20
return cos_test_outputtcoode
21

---

two_step_agent (task_inno)) search("paralees) __fs", default_branchinge
Listing 2: Two-step agent with BFS in ENCOMPASS reproduces Hypothesis Search
Here, we've chosen 8 samples of subsequent execution from each branchpoint and apply parallelized breadth-fing first search (parallel BFS) over all program execution paths, In particular, BFS samples natural language hypotheses following the first branchpoint, and for each hypothesis samples 8 code implementations from the second branchpoint. It then chooses the result from the 64 implementations with the highest evaluation score (recorded by version of Hypothesis Search [9] without the hypothesis summarization step and execution feedback loop.
This replicates
We also consider an agent with only the first of the two branchpoints. This gives rise to global best-of-N sampling, i.e., running the base agent N times in parallel and keeping the best run.
Comparison with equivalent plain Python implementing the ENCOMPASS agent, because the changes made to the original agent are minimal, the underlying logic of the agent is clearly portrayed by the code, with the external search logic (sampling) indicated by a few branchpoint statements.
We now compare this with the equivalent agent in plain Python. For the one-branchpoint hypothesis search agent (best-of-N), it is still relatively straightforward implement in plain Python by running N copies of the agent in N parallel threads until we find solution that passes validation.
However, further add the second branchpoint which is just additional line of code in EnCompass - the equivalent implementation in plain Python of parallel BFS requires significant structural changes. In defining the tasks to be executed in multithreaded fashion, the underlying agent workflow has been broken up and the program flow obscured, even though the agent only contains steps (Listing
concurrent. import Executor, compleedd
def wwt__ttp_aagnttee (tack info, branching); results
full_ soll_selvaddi Falsa
TereaoPoolEeccutor(() executor:
10
def run, one sae_forvard_peet
if full_solved:
12
return
Step natural language hypotheaia
14
15
hypotheats hypotheais i[taa hypothesta_ ion
16
17
def implement codecde)):
18
nonlocal full_solved
19
folvesoived: return
21
22
23
Step 2: Implement the hypothesie in code
24
code solver_agent agaakkatnttttttttiii hypothesis), solvar_ solvar_instructionn
26
Evaluate
28
percent_coreeee correct (uu.vallidatoon(ccde))
29
perceat_ correct 1:
30
full_solved True
31
apuults.appedd((e (get_ cotpttestttttptcccodo percent__coreett)
33
futurea [executor aubmit (implement, (n_cceee for in range (branchin]]
future as_ aa_cooppooee(((tuure)..
35
nuture.resulti
36
37
[oxecutor, submit (run_tte________eeee sne__oorwrrd_pseee for in range (branchin)] for future in as_ as_ccapleteddfuuaree. future. result()
futures
38
40
return (resulte, key=lenbda [01])(0]
42
44 gpo_step_agente (task__tiff branching-
Listing 3: Parallelized BFS in plain Python, obscuring the underlying two-step agent workflow
22

---

Table 2: Percentage accuracy of simple two-step agent on a subset of ARC with progressively more ENCOMPASS branchpoints: no branchpoints, branchpoint at the top. and 2 branchpoints before the 2 LLM calls. Accuracy improves quickly as more branchpoints are added. We also compare with the best agent discovered through meta-agent search (ADAS (39]
Base model
GPT-3.5
GPT-4o
Acc. (%)
Total cost
Acc. (%)
Total cost
Two-step agent
4.3 0.9
$0.41
24.0 + 1.5
$2.85
+ global best-of-NV, N 8 (ours)
11.7 + 0.8
$3.29
36.3 1.1
$22.76
global best-of-NV, = 36 (ours)
16.0 1.0
$14.81
38.7 + 1.1
$95.98
BFS, branching = 8 (ours)
15.0 0.9
$15.81
38.3 + 1.2
$88.69
ADAS best agent (reported)
13.7 +: 2.0
30.0 + 2.6
ADAS best agent (reproduced)
10.7 +: 0.8
$2.11
32.7 1.1
$27.85
'The reported results different checkpoint of GPT-4o and the estimated differently, using bontstrapping confidence interval.
The purpose of this evaluation section is to complete our demonstration of using ENCOMPASS to implement and compare different inference-time scaling strategies.
Evaluation
We use a subset of the ARC-AGI benchmark corresponding to the 60 tasks sampled from the "Public Training Set (Fasy)" that ADAS 39 used. We report the mean evaluation score well as its standard emorr over 5 seeds.
We evaluate the following agents on this ARC-AGI subset:
The two-step agent (base agent)
Global best-of-N applied to the two-step agent (one branchpoint), where N 88
The Hypothesis Search agent [19]. i... parallelized BFS applied the two-step agent (two
branchpoints), with branching factor 8.
The LLM temperature was set to 0.8 for experiments.
The evaluation results are shown Table [ The results show how scaling inference-time compute by adding branchpoint () statements and adjusting search parameters quickly increases the evaluation accuracy to results better than the best agent discovered by costly meta-agent search (ADAS) [39] Comparing the two scaling strategies, find that best-of-N and BFS comparable.
A.2 Case Study 3: Reflexion Agent
In this case study, we show how applying ENCOMPASS to an existing agentic pattern provides a new dimension for the cost-efficient scaling of inference-time compute.
Base agent As our baseline, we use Reflexion 7 as a coding agent (Listing 24 which uses an LLM iteratively reflect past attempts and their feedback improve the response. Feedback includes both L.LM-generated self-reflection and results from running I.L.M-geerated unit tests.
The ENCOMPASS agent In ENCOMPASS, modify Reflexion by adding two branchpoints (Listing 25 one before the initial code generation, and one at the top of the body of the for loop (i.e., before each iteration of self-reflection plus generation). Pass rate on the LLM-ggnerated unit tests feedback is used as the verification score in Socord_scord () in the ENCOMPASS agent. We apply two search strategies: one global best-of-N, and the other one is "reexpand best-first search", our variant of best- search (BeFS) where the strategy is to simply always choose the node with the highest verification score to step.
Comparison with equivalent plain Python Implementing best-of-N sampling in plain Python is straightforward - simply wrap the agent a for loop. However, to implement reexpand best-first search in the Reflexion agent, plain Python implementation requires structural changes to the code when ENCOMPASS only requires adding two branchpoints. In particular, the initial sampling step and the self-reflcction step are put into separate functions, corresponding the 2 actions that the agent
23

---

is allowed to take (Listing 26 chooses the best node expand: the chosen node is the root node, then new code sample is drawn from the L.M,, whereas if the node is not the root, then a self-reflection step is applied to it.
Appendix D.3). The agent maintains a search tree and iteratively
Furthermore, separating the actions into separate functions loses the natural logical ordering between them (the initial sampling step should occur before the self-reflection step). For more complex agent workflows like the code repository translation agent Section 4.1 the original underlying agent workflow becomes heavily obscured.
Evaluation The purpose of this evaluation section is complete our demonstration of using ENCOMPASS to implement and compare different inference-time scaling strategies.
LeetCode is website with programming exercises to help prepare for software engineer interviews, and the LeetCodeHard benchmark is a collection of 40 hard LeetCode problems [7]. A problem typically has few dozen test cases (occasionally few hundred over thousand test cases). While the LLM agent does not see these test cases, can use LLM- --M-eenrrtted test cases. We calculate the evaluation score the average pass rate over all 40 problems, where the pass rate for any given problem is the fraction of test cases passed.
For both the base agent and the ENCOMPASS BeFS agent, we consider 3 different cost settings (low, medium, high) where the number of code generations n = 5, 8, 13. In the base agent, we vary the number of feedback loops to be 4, 7, 12, whereas for the BeFS agent, the number of feedback loops fixed at but the total number of code generations is controlled by the external search algorithm algorithm. In the best-of-NV agent, we have 2 cost settings (low, high) by adjusting N 1, The temperature the LLM is set to 0.0 in the base agent and 0.5 (n = 5) or 1.0 (n = 13) in the ENCOMPASS agent.
As shown Table 3 controlling inference-time scaling through the external search algorithm in ENCOMPASS scales in more cost-efficient manner than scaling the number of feedback loops in Reflexion: the same performance achieved lower cost. Comparing the two scaling strategies, find that BeFS and best-of-N are comparable.
Table 3: Increasing the number of search steps in the ENCOMPASS Reflexion agent scales better than scaling the number of refinement loops in the vanilla Reflexion agent: the same performance is achieved at lower cost. All errors are standard errors of the mean over 5 runs.
Cost setting
Low
Medium
High
Acc. (%)
Cost/task (S)
Acc. (%)
Cost/task ($)
Acc. (%)
Cost/task ($)
Reflexion +fest-of-NV +BeFS
35.5 + 1.0
0.279 = 0.005
35.9 + 1.3
0.449 = 0.005
38.2 + 1.2
0.736 = 0.010
35,5 + 1.0
0,279 0.005
37.6 +
0.508 0.013
36.1 +: 2.1
0.168 + 0.004
36.1 +
0.289 + 0.007
38.1 + 1.3
0.512 + 0.006
24

---

B Documentation of ENCOMPASS
ENCOMPASS is instantiation of the PAN programming framework in Python. implemented as the @encompass. compile function decorator, which makes several new keywords primitives available in the body of the decorated function. Appendix (neendix(deserriiee deseribes how the decorator compiles the function body into an object that provides an interface for search.
This appendix organized follows:
lists all ENCOMPASS keyword primitives that are made available inside function with the Gencompass. compile decorator.
Appendix B.
describes the interface of the compiled search space object created by the @encompass compile decorator.
Appendix B.
Appendix B.3 describes the interface of the Checkpoint object that represents the program state at branchpoint return statement.
Appendix B.4 describes the search algorithms that ENCOMPASS provides out-of-the th--off-tee-oxx. as well as the abstract Search class that the user can subclass to define their own custom search algorithms.
B.1 ENCOMPASS primitives
The following the complete list of the 12 ENCOMPASS keyword primitives in alphabetical order. They are available in any function or async function with the Cencompass. compile decorator.
branchpoint (** btranhhposnt_paramm
This statement marks branchpoint. When combined with proper verification signal from record score statements (see below), this creates the illusion that the stochastic operations that follow now biased more desirable outputs, and unreliable operations (e.g.. L.M calls) have become more reliable.
This illusion (angelic nondeterminism) is accomplished through search over the different non- deterministic branches of the program's 's execution. More specifically, when the program's execution reaches branchpoint, the program will branch into multiple copies of itself and an external search algorithm implemented using the Checkpoint interface searches over the multiple branches of the program.
branchpoint_pare paramsssppapsssse
include the following keyword arguments (all are optional):
name: Any: A name to label the branchpoint
_ax_protection: int None: The maximum number of times stepping the next branchpoint allowed to raise an exception that gets protected (see documentation for ())
hessage_to_agent Any: A message to send to the agent (see below for messaging).
Other available keyword arguments depend on the specific search algorithm being used. For example, algorithms derived from graph search algorithms by fixing the branching factor allow the programmer to provide branchpoint-specif branching factor branching and maximum amount of parallelization max_workers when sampling the next state.
Example usage: The simplest use case is to add one branchpoint () statement the top of the function body (Listing which amounts to best-of-N sampling (Section 3.1):
@encompass. compile
def branchpoint_exxmple((.... example(...).
branchpoint()
something
5
record_acore(....
# Sample 10 times and output the result with the highest score cetappoin__xxmppee... search ("sampling",
s"aarchh"sapppl rom_roolouts)10)
Listing 4: branchpoint example: Best-of-N sampling
25

---

branchpoint O) also supports messaging with the controller (user of the Checkpoint interface) with syntax similar that of Python yield. This lets the programmer implement highly customized search algorithms optimized for their particular agent workflow decisions on node selection and backtracking can now depend on the details the execution state of the agent that are sent to the search process via this messaging interface.
Example usage: Listing [5] illustrates how messaging can be used let the controller decide whether to backtrack based on the execution state of the underlying agent.
Dencompass. compile
2 def branchpoint..mssaginnne _essaginn((tssk)
branchpoint()
solution
5
feedback
6
Python equivalent: response yield (...)
7
response = branchpoint (message, ( ttac solution, feedback) )
print (response)
10 # Python equivalent: generator aranchpoint__eesaging next (generator)
11 checkpoint0 branchpoint htttippiittmsssainngn.......e staar()
12 # Python equivalent: task, solution, feedback - next (generator)
checkpointi checkpointo.
task, solution, feedback checkpoint1 message_ssooeee fron_agentt
15 # Decide whether to backtrack
16 ahould_ backtrack = if should_ banlldbbccktcck:
solution, feedback)
Backtrack and retry last step Python equivalent
19 checkpoint1 checkpointO. s)
20 # Python equivalent: generator. send (f {should_ backtrackk"))
checkpoint2 checkpoint1.
message_ cassage_tto_aaeee "bentt=f"ackkraccked
Listing 5: Example of branchpoint with agent-controller messaging
branchpoint_chooss (choices: Iterable, ** *+branchpoint_pprrmms).
This is a variant of branchpoint where the resulting branches have the branchpoint_ choose (choices) expression evaluate the elements in the iterable choices. In other words, this implements regular angelic nondeterminism.
Example usage: The following function (Listing 6 guesses path from node goal in a graph. Conducting search over the nondeterministic execution branches becomes equivalent to actual search over the graph.
Dencompass compile
def graph_ (graph,, start_node, goal):
3 ...
Guess a path from "start_node" to "goal" in a "graph" represented as an adjacency list.
cur cur_node start_node path [cur_node]
7
8
cost_so_far
while cur cur_node != goal:
next_node aranchpoint_choosee choose (grapho [odee] identity=cur_noda path path [cur_node]
12
cost_so_fas get_edge_costt
total_estimated.co cost (cur (cur_node, next_node
13
cost_so_faa far coaettte_ossotttooooooeoooo goal
record sarr___core--ttaal het-oottal_sttmmttdd..etett
cur _od_ next_node return path
16
Conduct best-first search shortest path with A* search
26

---

sesp__searchhmyygaaaa.l my_start_node, my-goal) search "ebarch"bbet_ffreee top_k_popped =1, default_branching-el
Listing 6: Graph search example with branchpoint_choose
early.stop_search0
This early-stops the external search process because, e.g., correct answer has been found.
Example usage: (also see Case Studies 2 and 3)
Bencompass. . compile
2 def stely_stop_seardle wtt_ssarc__eemmpe..... example(...))
# Do something before branchpoint()
Ask LLM generate
answer 11m. (emeeeattttte..)
# Check answer
success check_answer (answer)
if success:
10
early_stop_sent sttop_search()
II
return answer
12
Listing 7: early_atop_seate example
kill_brance branch (err=None)
This kills the current branch of program execution. For example, if the LLM generated something irreparably bad, instead of recording large negative score (i.e., record_score (- (-1000),, one can simply kill the current branch.
Example usage:
@encompass. compile
def kill brwncha vrranch_exampe((...
something before branchpoint()
Ask LLM to do something
response = 11m. generate(...)
sanity_check_paae if not meitty_check.passed:
samity_check, Baaeecck_lmm_resppoieee (response)
#ill_branch(
10
# Do something after
Listing Example usage of kill_braach
ver: NeedsCopy
var: NeedsCopy expr
This tells the ENCOMPASS compiler that the variable named var needs to be copied upon branching. In other words, this type annotation declares a variable that is independent across all future execution paths of the program, assuming no "var: NoCopy" declaration ever occurs in the future.
By default, all local variables need copying, so NeedsCopy is typically only used undo an earlier NoCopy declaration.
Global variables are never copied. In fact, using "var: NeedsCopy" in Python function will actually declare a local variable named var that needs copying.
Note that variable assignment without a NeedsCopy or NoCopy declaration will not change whether it is NeedsCopy or NoCopy.
Example usage: this example, the programmer wishes to reuse the name of a NoCopy variable for something that needs copying (Listing
27

---

dencompass. compppppassccomplee
def needa_copy_ _opy_example (task)
3
Step Iterative refinement using NoCopy
4
feedbacks: NoCopy
[]
branchpoint()
score, feedback set__scoe__ate and secore_ad__eeeebaax.. feedbacke append (feedback) record_ serrrd_acoeeacco (score)
8
Step 2: Summarize every feedback in "feedbacks"
12
feedbacks: NeedsCopy Different summary attempts mutate differently so we want copies "feebbacke" on different search branches branchpoint() # Sample multiple summary attempts for i, feedback in enumerate (feeebackk) feedbacks [i] summarize sumariize_eeddaccie (fedback
13
16
17
result fgrnt_ search( ("dfs", default_
Listing 9: NeedsCopy example
var:
NoCopy
var: NoCopy
eapr
This tells the ENCOMPASS compiler that the variable named var need not be copied upon branching. In other words, this type annotation declares variable that is shared across all future execution paths of the program, assuming no "var: NeedsCopy" declaration ever occurs the future.
By default, all local variables need copying, NoCopy is needed declare variable to be shared across future execution paths.
Global variables are never copied, so there is no need to use "var: NoCopy" to specify a global variable that doesn't 't need copying. In fact, this declaration would actually declare a local variable named var that doesn't it need copying.
Note that variable assignment without a NeedsCopy NoCopy declaration will not change whether it is NeedsCopy or NoCopy.
Example usage: The simplest use case is to modify the best-of-N (one branchpoint at the top) by initializing shared memory of feedback from past attempts. This gives rise iterative refinement (Section 3.2).
Gencompass compile
2 no_copy_exanie copy_exammleetasst)
feedbacks: NoCopy []
branchpoint()
result = perform_ berform_taskttase (task, feedbacks)
score, feedback get_score_ wttp__coreeadd_eeeeeeeeeee fedbbac feedbacks . afpenddfeedaacca record_score (scor)))
7
8
# Sample 10 times and output the result with the highest score result fgontt search "sampling", mmm_rolouus==0)
Listing 10: Iterative refinement
optional Centiionnl_reuun(aaae (retarn, value)
This signals to the external search process that, although the program exccution hasn't finished, output return, value has already been produced and should be treated possible return value of the program.
Example usage: (also see Listing 25 in Case Study 2)
@encompass. compile
28

---

def Letoonal_returppeeaaale.........
11m. generate. _ateeeansssw.....
5 refined_answed 11m. wll..rffine_nnseee (answer, ...)
return aesswe
Listing optional _eeturn return answer
protect (expr, exception, maz_ retries-eeo))
If evaluating expression eupr may raise exception exception, then wrapping it in protect (...) creates the illusion that it no longer raises the exception. The illusion created by resampling from the most recent branchpoint until evaluating the expression longer raises the exception. maz_retries es, if not None, sets an upper limit on the number of retries.
Example usage: One example use case is parsing output from an LLM. The following example extracts the Python code block from an LLM and parses it. Both steps could eroo out because of the unreliability of the LLM, so we can wrap them in protect
@encompass lomppp
def parse hwtpliin__ttttteeeeee____e example(...))
something before branchpoint()
# Ask LLM to generate Python code response = 11m. generate(...)
Extract Python code
python_code protect (response. "prtt"""""""""""""""""""""""
"python'n", 1) [i]
.ppit("">*", 1) [o], IndexError)
10
# Parse Python code
python_ ast protect (ast.parse (pp.att.pareppyttoocooooooo SyntaxError) aomething after
13
Listing 12: protect example: Safely parsing output from an LLM
cecord_costs (**
This lets the user track various kinds of cost, e.g., LLM usage. The costs are aggregated and accessed through the dictionary conc.aggreagte_costs where func is the compiled function.
Example usage:
2 Bencompass compile
record_costs_exe (ooett__exaleee...)))
response, cost 11m. fecord_costed ain.generaatee...
11m pum_mum_me num_calls=1)
return response
Listing 13: record_coste example
record_score serrrddscoreeesee (score)
This is the main means for providing reward/verification signal to the external search algorithm by recording score. The exact semantics of this score will depend on the search algorithm used (e.g., heuristic for best-first search, value function for MCTS).
Example usage: The simplest example best-of-N sampling, which samples the agent workflow multiple times and selects the result with the highest score recorded by record_score.
Dencompass. compile
2 branchpoint, wttpantt_eeaeeeeee____
3
branchpoint() ()
# Do something Record_scoree...
29

---

# Sample times and output the result with the highest ceappoont__xxmppleeet .ee.......eaarheeeee search("dfs", default_
Listing 14: record_score example: Best-of-N sampling
record_sce ceroodd_cooeegrouppp evaluator, eval_target, target, label=eval, label)
This overloading of record_ _ccree enables evaluation that compares across multiple program execution branches. The simplest evaluating a result must be done relative to all results (Section 3.3
for this is self-consistency majority voting, where
searchover (func(...))
This is the syntax for calling an ENCOMPASS function func inside another ENCOMPASS function. This is similar to the await func(...) syntax for calling an asyne function inside another asyne function, where instead of await we use searchover.
Example usage: (also see Listing 19 in Case Study 1)
@encompass. compile def folpee__function(..))
Rencompass. compile
def Searchover_examplel.
Do something before
helper_result (harchoorrteelperffuutttt
Do something after
10
Listing 15: searchover example
searchover_avan http:o/errraaaaaaaaa..aeaaae (async_func(...))
This is the asynchronous counterpart to searchover (). In other words, it used to call an asyn- chronous ENCOMPASS function async.fune from within another asynchronous ENCOMPASS
function.
Example usage:
Gencompass. compile
asyne haync_helper_ffi functiion...nn..
Cencompass compile
asyne def searchover await_ (rriit_examlee(...)
7
# Do something before
8 helper_ pelperrresult searchover_avail (wwpeaaaaaaaceeeeeeereeettttttta
# Do something after
Listing 16: searchover_avait example
B.2 Compiled search space interface
The interface of the compiled search space allows the user to either step through the program or search over nondeterministic execution paths.
In what follows, func represents a function compiled with the @encompass compile decorator, and func(.... represents the search space object created from calling the compiled function some arguments.
func(...) s)art() Checkpoint
30

---

This begins execution of the function with the given arguments until the first branchpoint, i.e., branchpoint or branchpoint_choon choose (), which could be inside nested searchover function call. The program state at that point is wrapped into Checkpoint object, which can be used to step through the function, creating checkpoints branchpoints. A partial interface of Checkpoint is given in Appendix B.3
async.func(. .). asyac_ O -> AsyncCheckpoint
(asyne method) Asyne equivalent of funcl. start() for asyne ENCOMPASS functions.
func(...) (eeacchsearrc.... algo: str, **search_params) -> Any
This conducts search over the compiled search space using the given search algorithm and returns the final result, which is usually the return value (from either return return_ return_value or antionnl_rettin Search algorithms available in ENCOMPASS are detailed in Appendix B.4
from the branch with the highest latest recorded score.
async_func(... asspa_ssearch(searrchh algo: str, a#search_params -> Any
(async method) Async equivalent of func(.... . search for async ENCOMPASS functions. func(... .).
algo: str, **search.parrmm) -> list [tuple]
This is the search (),, except returns all results and not just the best Results returned as a list of pairs (rv, score) where rv is the return value of a branch and score is its score.
somee_func(.... aasyp__.errchmlllpppeeeeeeeerd algo, **search [tuple]
list
(Async method) Async equivalent of func(. .ww..cc...achhmmme.... stw.:...seaammmmiiplli.l mlltipee) for asyne ENCOMPASS functions.
func. costs: dict [str, float lint]
This is a dictionary containing the aggregate costs from all record_ statements. Key "<cost_ "est__nmme" is mapped to the sum of all costs recorded with that name via record_cost (<cost_name>=...
func. www.chboint_sseepepeeeeeeeo sttpriatttttee_o__ttttee Sict[Any. int]
This is a dictionary that maps the name of branchpoint to the number of times step() () has been called checkpoint of that branchpoint, over all calls to func since the last time zero_brt zero_branch www._branncnottccomoee countss () was called (see below). The dictionary will only contain step counts for named branchpoints, i.e., branchpoints with name parameter (i.e., branchpoint name=... or branchpoint. choose (choices, name=...).
wwwc..err.branccppppoooo branchpoint_counts () -> None func. zero_ zero
This zeros out the recorded total step counts of each named branchpoint.
B.3 Checkpoint object interface
A Checkpoint holds the program state at branchpoint or return statement of an ENCOMPASS program's execution.
class Checkpoint
step (tep(maxxprotectioneee score_db dbore_db__ aib_flushgggaaeeee Truue
Checkpoint
31

---

This continues execution of the program starting from the stored program state until the next time branchpoint is hit, returning new Checkpoint object.
Any expressions protected by a protect ( (epp, exception) will trigger resampling whenever the exception occurs, up maximum of max_protection resamplings if is not None.
If score_di chaorre_d__fls________eee____eee queueeuuueeeee is False, then pending evaluations recorded through the group- evaluation version of record_scor will not be processed.
Multiple step() calls on same Checkpoint are mostly independent: while variable assignments are independent, references to variables declared as NoCopy are shared, so that mutations a NoCopy object created before the current checkpoint are seen by all execution branches descended from this checkpoint.
If the branchpoint is branchpoint, choose choices: Iterable) instead of regualar branchpoint () statement, then multiple step () calls iterate through choices, and the resultant branches the traachhooitt_hhaae choose (choices) call evaluate the elements in cces.
step_ carp__smmlerreee (max__maaaaaa samples==onee, max_ protecciionnonee score_db__ ferre_db_flush. flffflushhuuuut queue eTrue) -> Generator (CherrttrrCheckpoinnt, None, None]
This calls () repeatedly and yields the resultant Checkpoint objects. This is done at most max_ _ax_sample es is not None; otherwise samples forever, or until the list of choices have been exhausted in branchpoint, srppoitttchhoee.... choose.
max_prote nax_protection specifies the total number of resamplings allowed for protected expres- sion evaluations.
See brrckkoint.stepp above for chtorr_db_flushh..
parallel_stee samplerrreerrrreeeeeeeeereeeeeee (max_samples-Nors Baunk_size-Wol max_protection =None, max_ workers=None, score _b____b_ff____ fobsffuushe__mmm quuss_uuue=TTre) -> Generator( Checkpoint, None, None]
Multithreaded version of Checkpoint step_sampler O), where max_workers specifies
the maximum number of threads to use and thunk_size, if given, does parallel samplings in batches of that size.
status: Status
The status the checkpoint object. One of Status RUNNING, Status DONE_STEPPING Status. RETURNED, and Status KILLED. The Status. DONE_STEPPING status only possible at branchpoint, choose with a finite set of choices.
has_ Das_return_value. bool
Whether there's 's return value from return return_vart value (if the checkpoint is at return statement) aationnalreturre (return_ (if the checkpoint is at branchpoint).
return_valuu value: Any
The return value of the function if it exists (i.c., if the checkpoint is at a return statement, is a branchpoint following an optional_reen return statement without an intervening branchpoint).
early_stoppe__seaate search: bool
Whether an program's execution.
statement has been called on any branch of the
score:
float int
The most recent score recorded through record_scorre ()
32

---

branchpoint_pprrms:: dict
This is dictionary containing the parameters of the branchpoint as specified through branchpoint (wwDranchooini.prreae or branchpoint_ choose (chosces (chosces ** Srranchpoint.paramss)
For asyne ENCOMPASS functions, there's corresponding AsyncCheckpoint with the same interface, except that certain methods are now async, and step_ saepssr and paralle__stop_amplle () have been merged into one ssync_step_samlles ().
class AsyncCheckpoint
async_step (max (max.proteciion-toon, serre_dbflusshquuueee -> Checkpoint
(async method) Async equivalent of Checkpoint.step()
aaync_step_sampleer saa.eeeeeeeasemmeeeeeeeeeeeeee chunk_size--onne eax_protection= None, max_word max_korkers=None score_db_ wtt.:udfffuussuuuuuuuuueeeee -> AsyncGenerator Checkpoint, None, None]
(async method) Asyne equivalent of Checkpoint. step_sampler() and Checkpoint. parallel_step_samplee.
status: Status
See Checkpoint. status.
has_retuunn_alle vvaluurr_value: bool
See
return_value Any
See C
early_stopped_ search: bool
See
score: floatline
See Checkpoint.score.
branchpoint__param:: dict
See Checkpoint Checcppoin..brrachponnn..ppe bra.chpoinnttpprama
B.4 Search interface and search algorithms
Search algorithms are implemented over the Checkpoint interface. Parameters to a search al- gorithm can be specified both in the arguments to search () when invoking a compiled search space object as well as branchpoint parameters specified as arguments to branchpoint () and branchpoint_chooss () within the ENCOMPASS function.
ENCOMPASS provides several common search algorithms out-of-the-box. The asyne implementations take advantage of the I/O-bound nature of LLM applications, whereas the non-async implementations use multithreaded parallelism, which the user can disable if they wish (e.g., to prevent race conditions when there are NoCopy variables). Here is the complete list of search algorithms in the current version of ENCOMPASS:
Depth- firstffirttao search (DFS)
33

---

Breadth-fise first search (BFS)
Best-fine ferst search (BeFS)
Beam search
Monte-Carlo tree search (MCTS), with given value function
Reexpand best-first search, variant of BeFS where expanded node be expanded again. This was used in Case Study 3 (Appendix (A.2).
Explorative reexpand best-first search, variant of reexpand BeFS where UCB-like exploration bonus is added to the score.
The user can also implement and register their custom search algorithm by subelassing the abstract Search class. Here, provide template for defining and registering custom search algorithm:
Oregister_aeaee _eaorcb_aloo aigo seyac-Falee) or "ie_ ar_a if subclassing "AsyacSearch" Mysearch(Search): searchh"
"ySearchh (AayaSSercc))
paran_nenes ['parani", "paran2"] names of branchpoint paraneters that will use
def
_initt__sseif, *, contigl, contiga, default.paranl, default.parani): colffco configl
celf.comfi2 config2
solf.dofault.pprras default_parani
10
self peaaall default_paran2
11
daf nearch.generator(
13
self,
init__rogran__et state: Checkpoint
15
>> Gonerator [tupr Ituple[Any, ScoroNithCallback) Xone, None]:
or "asyne def async_search. aymc_search.generatoo generator (self, intt.progran_state AnyncCheckpoint) if subclassing 'AsyacSearch"
18
Yielda (return_value. Any, www.uuithcacllbaceee BcoraWitaGallbact) a8 they are found.
20
22
ScoreRithhallback is wrapper around program state's score group evaluation vork properly.
24
25
REPLAGE CODE BELOW WITH YOUR CUSTOM SEARCH ALGORITHN
init_progran next.progran, state in saat_pprorrm_ttteee. for next, pratt_progaa__eee
27
parani next_progran_ stagrrnntttt.eet..... gette.get_bbr wet..bbancppoint.poee ("paran""""" self. self.default, default_parani
29
if next.program_atate. sta.ssttaaaaaaeee baseeeaas__rtteeeeeeee retureeetllleeeeeeeeeeee value:
30
yleld next_progran, state, return, return_alle, next.progran_ attoggaanttate...ae. acore, cabcaaa
32
34

---

C
The ENCOMPASS compiler
The ENCOMPASS compiler syntactically transforms ENCOMPASS function into an equivalent regular Python program by conversion to contmuation-ppasing style (CPS) and applying tail-call optimization.
For simplicity, we only describe how we compile ENCOMPASS functions that are not async. The compiler transformations for asyne ENCOMPASS functions nearly identical.
C.1 CPS for branchpoints
In this subsection, we describe how to convert piece of code containing branchpoints (but not any of the other EnCompass keyword primitives) into CPS. In its simplest form, transforming piece of code into CPS results function
cps eps_function (frame: Frame, rest: Frame -> None) -> None
which the piece of code the variable mapping frame to get variable mapping. followed by calling the callback rest on that new variable mapping. Here, the callback rest, called the continuation, represents the rest of the program.
For piece of code that doesn't contain any branchpoints, it suffices to transform variable accesses and assignments to explicitly use frame. For example,
y
compiled into
frame ['x']
frame ['y'] = frame ['x']
rest (frame)
Note that we omit the def cps function (frame,, rest): we're compiling to the body of the CPS function. We will call this the CPS body to distinguish from the CPS function. We defer the job of wrapping the CPS body into function whoever asked for the compilation. This simplifies the issue of naming CPS functions and referring to them with correct name.
in the compiled code, so technically
Since the compiled CPS function explicitly runs the continuation rest (frame), adding branch- point immediately after the piece of code amounts to modifying the continuation to incorporate the search process. So we replace rest (frame) with weachhoint_calllaaeee (frame, rest), which defines the rest of the program when we hit branchpoint, where rest here now represents the rest of the program when we resume from the branchpoint. Taking the example above and adding branchpoint at the end,
=
y branchpoint ()
gets compiled into the following CPS body:
frame ['x']
frame ['y'] - frame [ [x'']
rest)
Here, branchpoint_ catccpppint_calllackkkkc (frame, rest) first stores the current program state (frame, rest) as a node in the search tree, then uses the search algorithm to decide node (framel, rest1 ) in the search tree to expand, and call resti (framel. clone ()) run the rest of the program resuming from the branchpoint that saved the state (framel, rest1). Cloning frame1 is needed because otherwise multiple calls rest1 (frame1) would modify the same frame1 object.
So far we've 'ee only defined how to transform programs with no branchpoints and programs with one branchpoint at the end. The transformation of general program with branchpoints in arbitrary
35

---

locations can be defined recursively with these two base cases. For example, a program with branchpoint in the middle,
x 1
branchpoint ()
y =
Listing 17: Program with a branchpoint in the middle
a concatenation of two programs:
A
x
branchpoint ()
and
B
where we can apply the recursive transformation rule for concatenation,
rest(frame))
CPS(B)
CPS(A)
to obtain the CPS body
def rest (frame):
frame I'y'] = frame ['x'] + 1
Sinish_callbes (frame)
frame ['x'] branchpoint, laaakabaaaaaa, rest)
Note that we have replaced rest (frame) with callbac in the compilation of B to avoid name collision with the def rest(fram)) As a result, the compiled CPS function of the complete top-level program (AST root node) also has to reflect this name function change in its signature: top_level_cpp ooneettioos (frame, finish_ callback) instead of hop__evel_.os__functe (frame, rest). So, Listing 17 is our entire program, then its CPS function is
def cillvvelcpss_fuuttioooooooooooo
finish_callbact)
def rest (frame):
frame ['y'] frame('x')
finish_ callback (frame)
frame ['']] = branchpoint, callback(fram, rest))
As more complicated example, consider the following code:
i
A
branchpoint( ()
A
j
while 10:
j -- 1
branchpoint ()
B
X
+- 1
Y
print(j)
We've chunked up the statements at the top level into 3 pieces: A, B and C. Each chunk consists of zero or more branchpoint-free statements followed by statement containing branchpoint, except for the last chunk C which is branchpoint-free. We apply the concatenation rule to A and (B; C), which recursively applies the concatenation rule to and C. This then recursively compiles the last statement of B the while loop. Compiling the while loop using the while loop rule recursively compiles the body of the while loop using the concatenation rule on the chunks X and Y.
The concatenation rule as applied to chunks X and Y gives
36

---

def rest :
CPS body of
frame ['i']
continue_calllackttteeee callback(frame)
continue
# CPS body of
frame ['] -
wat.:aaaaaaaaccfaaaaaaaaa branchpoitt.clllacc((feeee
rest)
where avoid name collision we replaced rest (frame) with continuu_callbback (framee))
Applying the while loop rule gives
def body_cps, wtty_cps_ffnccee function (frame, continue, continue_callback,, callback, CPS body of (X; Y) (from above)
callkckk)
def rest (frame) CPS body of frame ['i'] '] +- continue Nontinue_callback callback (frame)
# CPS body of X frame ['j -
htt.ripooint..alllaccccffrrerr rest)
10
while_cps_ cen.ieeicp_functionnnn (frame, rest):
11
if frame(' 10:
fody-coss_uucttin (frame, lambda frame: while_cps_ hwtp:/ppe_uenooinnneiee (frame, rest))
else:
(frame)
15 caile_css_functinn (frame, rest)
Finally, applying the concatenation rule twice in (B;C)) gives the CPS body of the entire program:
# CPS body of (A; B; C) def reramframe):
CPS body (B; C)
def rest (frame):
# CPS body of C print (ttrame['''] finish_ waw.bacc (frame)
CPS body of frame [rjme['j'] 0
# CPS body of the while loop (from above)
CPS body of 12 frame ['i']
13 cetpcppoint_cllllacceeeeeeeeeeee
rest)
And, as usual, to get the CPS function of this program, we simply wrap the above CPS body into def top_level_cpp__fuee ffrction (frame, Finish_callbacia function.
Note that the general solution to dealing with name collision is to add the correct version of rest frame) to the end of each "body" in the AST during preprocessing, so that we don't 't have to deal with during conversion to CPS:
At the end of the top-level program, add finish, callhackllaaclcaaaaaceaa (frame) during prepro- cessing. During conversion CPS, the signature of the CPS function of a top-level program will be hop_level_cps_uunciiie (frami,,, (frame, mmishhcallbacck instead of wtwp_leel_pss_fuuctiieeeeeeeeeee
rest).
At the end of the body of for/while loop, add continue_ continue_calllack((FF (frame)) during preprocessing. During conversion to CPS, the signature of the CPS function of the body of for/while loop will be Creek_calllbee instead of body_ _ps function (frame, rest). Note that this also specifies the names of the callbacks that continue and break statements in the body get converted to during conversion to CPS - two birds with one stone.
continue, callback,
At the end of the body of an if or an else, add if _f__ess_calll caw.back (frame ). During conversion to CPS, the signature of the CPS function of the body
37

---

of an if will be ff..booy.gs_.tucciionnnaaaa if if_else_callback, instead of wwwy_ops__fuuctiiiieee fopction (frame, rest), and similarly for else.
At the end of the body of function, add return_ Cattuuunaalllacuueee (frame. caller_ _rammr_frame) During conversion to CPS, the signature of the CPS function of the body of a func- tion will be function_bose ceedy_cps_ffuctiiooooooo function (frame, return_callback) instead of (frame, rest).
Junction_bodyy
We ready formally write down the full set of transformations for EnCompass programs with the simplest version of EnCompass that only has branchpoints. For simplicity, we only describe the transformations done for synchronous code (no async/await) where only loops, if/else statements and function definitions have branchpoints (with, try-except, and match statements are all branchpoint- free).
Preprocessing
The preprocessing stage consists of the following steps:
Convert names var to frame "war'" ']
2. Add finish_ (faabccccaalbakkfrraem the end of the program.
3. Add Dartimue_callbacc(fffe to the end of the body of every for/while loop.
4. Add wal.leeealllacctfffee statement.
to the end of the body of every branch of every if-else
5. Add return_ carburncalllbak (frame. (frame.caleer frame) to the end of the body of every function that doesn't already end in return statement.
6. Make the following replacements:
continue continue (framee)
break break btteaaaaallbaaeeeeeeaaaaaaaaaaae callaaaaclccccccccaaeaaa
return rv + cetum caller_frame rv)
Conversion to CPS Here are the general transformation rules for compiling a top-level program or the body of function, after the preprocessing steps described above have been completed.
1. Base case branchpoint-free: If A has no branchpoints, make no changes. In other words, CPS(A) A.
2. Base case branchpoint: A branchpoint
branchpoint()
becomes
branchpoint_callbene caw.aacctcaaaaaccccccacaaacaa rest)
3. Concatenation: For (A; B) where = (A': a) with A' branchpoint- free and a a single branchpoints branchpoint for/while/fflelse statement
statement containing one containing a branchpoint, but not e.g. function definition containing a branchpoint),
1 A' # zero or more branchpoint-free free statements single statement containing one more branchpoints statements
the compiled CPS body is
def rest ( CPS(B)
2
A'
CPS(a)
4. While loops:
For a while loop containing one or more branchpoints,
while
A # contains more branchpoints
the compiled CPS body is
38

---

def cody_cpss_functoon contimue_callback, break_callbace
CPS(A)
a def
rest);
4
e:
body_ cudyccps_function
frame,
lambda frame: whille.cps_fuccioontftee rest),
8
rest
9
else:
rest (frame)
while_ wtt_ccccssscocneeeeeccccoooooocc (frame, rest)
5. For loops: For a for loop containing one or more branchpoints,
1 for in e:
A # contains one or more branchpoints
the compiled CPS body is
body_
contimue_callback, break, callback)
2
CPS(A)
def for ftt_cpssffucctionrfrreeoe (frame, rest);
try:
next
6
except StopIteration:
frame. wwteetrele..pp... p)
rest (frame)
def
(frame)
frame, wwt.eitaeee.ppooo..
rest (frame)
_ody_cps_ffut cps_ffnnciio(
frame, lambda frame: for htt.ccp_ffucttioffrrree rest), breakk_callbn
frame. iiteralless...... append (c) for_cps_functiie (frame, rest)
6. If-else statements: For an if-else statement containing one or more branchpoints,
1 if e:
A
else:
the compiled CPS body is
def if bbddyy.cp..functiin(rraa. if =f_ellee_callbck): CPS(A)
3 def else
if if_else_callll callbcck)
4
CPS(B)
5 if e: L__bood_ccp_fuucciionaaaaa rest)
else:
else_body fwwctpsoooooonnaaaaeeaaee reat)
C.2 Tail-call optimization
There are two issues with the compiled CPS representation. One issue is performance the extra function calls cause overhead, and long for/while loops become deep recursive calls that can exceed Python's recursion depth limit. The second issue that defining the search algorithm by defining branchpoint, callback (frame, rest) is unnatural and difficult. Typically, a search algorithm implemented assuming access step method that returns a child of node, new new__taa state step (state).
39

---

We solve both issues via tail-call optimization. More specifically, every branchpoint_callbace frame, rest) replaced with return frame, rest, and rest (frame) no longer resumes from branchpoint to execute the rest of the program, but only executes until the next branchpoint is hit, at which point the frame, rest at that branchpoint returned. In other words, new frame, new_rest rest (frame.ccll) ()) is exactly the new_state step stea(state) that we need, where we identify state with (frame, rest).
With this modification, reproducing the execution of the program when all branchpoints are ignored now involves a while loop that keeps stepping until the program finishes:
frame +
reat = lambda frame: hpp__eeee__cs_ffuctiii (frame, lambda frame: (frame, None))
while rest is not None:
frame, rest (frame)
And simple DFS looks like this:
frame (
rest lambda frame:
(frmm,, lambda frame: (frame, None)
stack [(frame, rest)]
results [
while stack:
frame, rest stack. ())
for in range (aagerbbhhhig_facttooo
new_frame, new_rest rest (frame clone())
if new_rest is None:
10
resulta.append (frame)
(frame)
11
else:
12
stack. append ( (new frame, new new_reat))
We can wrap the state (frame, rest) into a Checkpoint object that provides a step method wrapping new_fre -rame, new new_rest
rest (frame. clone ()), and any search algorithm can now be implemented using the Checkpoint interface.
We also need modify the CPS transformation rules return the next state instead of running the entire continuation to completion. The details of the modifications are as follows:
1. Base case branchpoint-free: No change.
2. Base case branchpoint: A branchpoint
branchpoint()
is now compiled to
frame,
3. Concatenation: No change.
4. While loops: Prepend return to these 3 lines:
2 def chill__cs__funciionfraene rest);
if
4 return body_sps_fuuctionn...
5. else:
return rest (frame)
<-
return while_cps_fet wwtpccpsffunnioonrrrara.. rest) <-
5. For loops: Prepend return to these 3 lines:
def for_cps_function (frame, rest):
5
return rest (frame)
return cestyccss_fnctionn
<.
40

---

return for_cps_funccioon(fran.. rest)
<-
6.
lf-else statements: Prepend return to these 2 lines:
2 e:
3 return if ot__oodyccpp.fuuccionnaaaee rest) #
else:
rest)
C.3 Other keywords
Most other ENCOMPASS primitives provide auxiliary information, which we store dictionary info. We modify our transformation rules that info always occurs alongside frame, so the Checkpoint object is now a wrapper around the 3-tuple (frame, info, rest). The Checkpoint class implements the intended semantics of these additional ENCOMPASS keywords using the information stored inside info - details which we will omit.
Note that info is copied upon wttespoinn.sttep.... similar to how frame gets cloned. In other words, stepping is now implemented as new new_frame, new_info, new_rest rest (frame (), info. copy ()).
For keywords that are used standalone statements, preprocessing is done to convert these keywords into statements that modify info. The only exception is kill_ branchh)), which transformed into f finish__ sallssaccllllccc () call. Here, list the preprocessing transformations for all keywords that are used as standalone statements:
early_stop_searchC info ["eaarly_ttop_seacch True
kill_branch(e) + finish__cllball (frame, e, info, killed-True)
NeedsCopy
var = v; if var in info ["nocopy")] info [ ["nocopy"] remove (var)
An annotated assignment is broken into two statements - the annotation and the assignment before this transformation on the annotation occurs.
NoCopy + info ["nocopy"] (v)
An annotated assignment broken into two statements the annotation and the assignment before this transformation the annotation occurs.
optional_return (e) + info ["optional_rv"] =
record_costs (ocoodd_ostsseeeuoddd33 + [nfo["costs]] = dict (keywords)
record_score, (args) +
info ["score"] info ["score_db") db") suwmiuu (args)
Here info ["score_db'] is ScoreDB object whose submit submit_score () method returns
thunk that represents the eventual value of the score. This extra complexity is needed to implement group evaluation (Section 3.3)
Without group evaluation,
record_ _cccrrsceeeeeee (c) + info ["score"] would suffice.
Now, the remaining keyword primitives - branchpoint (), caacchoint_chhosse () searchover () and protect are all used expressions that can be part of larger expression or a statement A statement that contains one or more of these keyword primitives needs to be partially converted A-normal form [41), where the return value from a keyword primitive first assigned to a temporary variable, and its occurrence in the statement is replaced with that temporary variable. This is done recursively for keywords nested within keywords. For example, the statement
*While Appendix C.1 treated branchpoint () as statement, in fact it can be used to communicate with the controller (user of the Checkpoint interface), where messages from the controller appear the return value of branchpoint ().
41

---

answer = get_answer"
branchpoint, choose [searchover (agent1 (task)), protect (agent222tt ValueError))
when converted to A-normal form will become
frame. tmp. v [0] searchover (agent (task))
frame. tmp vara [1] Protect(agent22 (task), ValueError)
frame. tmp_vars [2] branchpoint_ chhoee [[frame. tmp- vare [0], frame. tmp_ vars (1]])
get_ wnwwer(framm tap_taaaaeeeeeee vara [2])
After conversion to A-normal form, each statement that assigns the output of a keyword primitive to temporary variable is further transformed as follows:
frame. tmp_vars [N]
branchpoint (kwargs) - [no change]
frame. tmp_vars [N] breuchpoint__cooseeee kwargs) +
iterable
iterator, iterator_copy tee(iterable)
try:
next (iterator_copy)
except StopIteration:
info["doma (doon__teppping) True
frame. tmp_vars ["iterator_list""" [iterator]
frame. tmp_vars [None] branchpoint (kwargs) discard message from
controller not yet supported by caachpoint_choose
try:
frame. tmp_ [ars next (frame. vars wwp.waas""iteeattttiot ""iieerator_iist""" [o])
except StopIteration e:
raise FinishedSteppinngrroo from e
frame. tmr_ (nitrrattrrttriii list"] [0], iterator_copy = tee
frame frame.tap_vat tmp_ vars ("iteratorr_tiii []st"][o]] try:
next (iterator_copy)
except StopIteration:
info["last_brae info["lest_braacdppiitt htwpr//rraappotttoooeeeeeepppppp
True
frame. tmp_vars [N]
searchover [no change]
frame. tap_vars
vars [N] protect (eapr, err) +
try:
frame. tateeetavvvrrreee [N] expr
3 except err:
4
finish, callback callback(frame, err, info, killed=True, protected-True)
Finally, note that we have to modify the CPS transformation rule for branchpoints from Appendix C.2 well adding a CPS transformation rule for searchover. The new rules are:
frame. tmp_ [N]
branchpoint (kwargs)
def branchpoint_ree best (frame, info, message_to_agent)
2 frame. tap_vars[[N [N] gessage_to_agent
(frame, info) return frame, info, branchpoint_rees reat, dict (kwargs)
So now, sampling next program state now implemented as frame, info, branchpoint_rest restt, branchpoint_parreee paramms branchpoint_ rest (frame. clone info.copy() (), to_gett............
frame. var_ [N] searchover (c)
42

---

def return_rest (frame, info):
frame tap_vara rest (frame, info)
func_call
if not isinstance call, SearchSpacowWthhrrgs):
raise SearchoverTypeerror (1 (f"searchover expects
Searchspaceeiithhrrss object, instead got (type(fuuc_ccall))
7
8
Frame
focal==fuec_cll...arr.....
caller caller_frames fraeeeffarm--eeme
enclosing enclosing_frame-Prain fraaggffmaaeeereeeee.a from_ clouurereur
getclosurevare (func_ aeaall.ssarrhheeee.... www.sceeeaaee..aeee... appcce_.raaped_ft
)
info, return_rest,
43

---

D Code comparisons for case studies: base agent vs. ENCOMPASS agent vs. equivalent plain Python implementation
In this appendix, for each case study, we show the code for the underlying base agent, the agent augmented with search in ENCOMPASS, and the equivalent agent implemented in plain Python. We annotate the changes made relative to the base agent:
+n: This line was added and has n words (a word defined in Vim).
x (-m+n): This line was changed; and words were removed and words were added.
# -m: This line removed and it contained words.
# <-k: This line (or group of omitted lines) was indent to the left by k indentation levels.
# >>k: This line (or group of omitted lines) was indent to the right by l indentation levels.
We do count lines added that don't contain any code (i.e., that blank only contain comment).
We see that, while changes made to the base agent support search in ENCOMPASS minimal, sig- nificant changes are needed to support search in the plain Python implemenation, thus demonstrating the representational advantage of ENCOMPASS.
We will omit code that remains unchanged between the base agent, the ENCOMPASS agent, and the EN ENCOMPASS agent's plain Python implementation. Code segments that have been omitted are indicated by ellipses"... "...".
44

---

D.1
Case Study 1: Code Repository Translation Agent
Base agent:
rum_code_And_.oom wwwpare (oethre target_code,, Logging; define como variables
translation.mit)::
method. "maii":
Test. test_.1npns inpute Nome
1f *Systee. in in source_ code:
Wribe imput
ecript
10
Proupt LLK
11
12
teet forzat specification fron
fatal, erroz:
14
return 0.0
15
16
frox responce
fatal_
18
return
19
20
Generate
fatal_ error:
return 0.0
23
24
Directly and coupaze rested coxposent Function
26
ratch
27
zetura float (ostch)
28
Otherviau, have
function teat component
30
31
Define cone variables
32
input generation script generate test inputs
34
35
Prompt LLM
36
... teat ingut, spacification rаagonss
38
fatal, ozzoz:
39
zetura 0.0
40
... teat lngut goneration acript respense
42
fatal, crzor:
43
zeturn 0.0
44
... Generate text inputa
46
fatal_errcn arcor:
47
zetura 0.0
Larget
inputa
50
51
Prompt LEM
... ousput apocification respouse
54
fatal_arron arror:
55
return 0.0
... Earget nain
zwagonns
58
fatal_ orcoz:
59
return 0.0
...
target
62.
fatal_ _rrro:: zwturn 0.0
63
...
target. vain function
66
fatal_erroe:
67
0.0
... target nain
target
70
Iun target code with nain function on test inputa
71
cource
73
74
Prompt LIM
75
...
response
77
futai_error:
78
return 0.0
70
...
arror:
82
return 0.0
83
...
target nain target
tarpet code function
inputa
86
87
astches
45

---

fractin
91
92
def translate,di clamm(tranaeeioonomm))
... Sane sssup (#.5..
pazse files)
95
aethods, to to_tsansttte
96
wun_rathodd__ee trannaalca Jen toteeclaaattt.tttmmlaaaaaa)
tramlatee
paon_tests_
99
for sathod in sathods, to, in_trasllst::
100
target_code, translato_ auccesa seauslate_nethoolssttaae tadget_code, souroe_code, translation.uit) translate,
(ranzlate_aucceel count
103
104
code
translation, unit..s.tten teattet:::
107
paso_tastx, tasts_ttt__oooooo count to run, tnn_teet__nnuullee (tat.ttntilattarr_...om (target,_ode, translaation_uiit)
108
elan:
tnes_tests_cous qut_cooe_and__compee
rathod,
111
target_cods,
112
souron_codee code,
115
116
Separataly test nain function (Python 'if ._.ane.. '_.mkin__"" " black) if it's present not tranclation, we..m............. ....
min_methode_ to tranelate
119
translata_auncee auccomss count
120
run_code,, andde
Ladget_codm,
123
cource_code,
124
transl Caanelatioonuntt...
127
logging and saving prograss
128
pass,teets_comm, translere.esccoss.com nus_rethodr_,to weweettootttttttsniiiiee to_translate,
131
132
def ant code, target_codo_root terperatare):
source_ oubdir "erc/aain/antird"
nuz wwc.essuul. translstions
135
nay mww_mccosssfll.poo parsses
dirs, files ce.vall(ouurooccdeeeee pubdir)) files:
Read antlr4 gramar file
139
modification
Write to target directory
143
antlrd
Cbeck 1f the generated files can be pareed
147
www.sacccccfll.ccoo.m crancistoonnn
parces
151
dcf codo, code,trumcinn tww.clationnnoooommmom agent (source, code_ target_code. cotgetttdddrottttt.ooo zoot, arge): up logging
ropo for saving progress
0.1, Copy resource filee (cro/aatenreeooucee and src/test/resouree) reporreeeeceerro wecoorre__fileiiieeeeee (sourcoe__o cacuurroeooooootttt_eeeoeeeeesse cagoo__coderoos)
155
up acuppaattr44source.oo code_roott, sogot__ood__rot, tega.tonperature)
applicable (erc/soin/antird)
158
159
topological order
translation, wite get, get_trasslation order and (ppure coot, targes_codo_reet
163
for translation, unit in trasslation, units: Generate goncrate, stabeeee___ee__eeeeeee paccese generate stauasseeesseeeeeeeeeeeeeeeeeeee
class
167
Translate each class
pas__eetts_coume translate__uccces_coo sun_sethods,
branch
(trasslation,
170
Log results
171
Pinel logging saving
174
return Gime__comii
175
code, ap....))
Listing 18: Code repository translation agent
46

---

With ENCOMPASS:
Import: unid +2 encerpass
Gencerpane compile +4 def branchpoint..pl
log_atr=""immccpoomm franchpoint: reached", pwc_branch_name haw.enaneeeer""r""" brranch', +bbracckoinn..parae
repo Rego
#
with open ceanrget_coddrrott / sonn" "x*) Ax +16 srrstollog_sst '\a')
repo gtt repo.git commi:( ppp..gt.commi(( a", log_str) # +10
11
12
cur comnit etx str(repo (repoorooaddd..... commit) * -10 branchpoint (**bracchhotns..prrr repo.git git. checkout commit)
13
+4
15
repo.gtt (pppcch ct", bto...brac cane) (uuid midi())) +16
16
17
ocscepaac compile
19
def run_code_and. cowpoaanndcccareeeeoooe (nethod,, target_codb, courca,code, translation_umit, bane_score): (-0+2)
20
Logging; define come variables
zethod. type
23
24
Test, inpute None
25
'Systes. coarchoeerbbranclooss sit_comii((
27
tranclation, unit sarget_code_root, +4
28
1'Gesorate seat inpuca for and sest ftranslation, unit target, module, past):: (coppoestt pame)", +16
29
2"bp gen.inpute_ wwwpttpttetttrttttteeeee test.rain (tranclation, unit. target, morgett.oddio.ppp. parhh) (ana))((oopppeeee (coxponent, _ame))
31
32
STEP 1: Vrite test impuz generation ecrips and generate test inputs
Proupt
35
36
Get test input Corzat specification Iren LIN reaposse reture
37
39
40
Get test input goneration script froz. LLM response return
43
44
Cecerate teat Inputa
fatal,
rwturn
47
STEP 2: Directly run codes and coupare then 1f tested coxposont is naia function 48
51
zetura float (oatch)
52
Othervise, have
Function cosporent
55
Dafina scow variablea
56
(branchpoint..iis translation, unit. corgettcoodeeaeeeeeooooo coot,
59
I'Guaarace test isputa for cauuiiatiionusii tndule. module, pathlle_patt)aaaaaa (ssthod)", a +18 P'ggggen, Inputa- feraneerraaaattt laniuun targee wwwdill..ptiii.... (owthod)", a +12
60
63
STFP 1: Vrite teat. input generation script and generate tast inpota
64
... Prompt
67
Get Leat isgut, forsatt spacification from LLM zeaposas
68
fatal_arror
pad branchpointa awarchover (branchpoins.gee connniiiitttttiiiiiiieeaaaaaniii (trumelation, unit. targett,code_roon nearchover (branchpotnt.git cormi (tramelaation unii www.gtttttttgtt.oomo. target..ode_rroot) * return 0.0
71
72
test input generatioon acript. from response
75
fatal_ arror:
76
branchpointe (branchpoint..gi itp.pttt..itt..mmiiii
wtt.gttt_ccdeerroattt awarchover frrancppoin..g. giit.ii.ttttttotoe.. cancc (trenslation atooummiiiin targett_code_root
78
79
return 0.0
80
Genorate inpute
fatal_. .eroor:
83
pad branchpointts
84
cearchover (branch boranchoont..gtt. wtt.ggttt.oottttt. (tranclationn
root))
(braschpotnt..gtt wtt.oottt.tttt..oo....o.
on.unit target_.coderooot
return
87
88
record__core (bare_score 0.01)
47

---

translation, unit,, target, codd,, poott I'Busning langet code for Strmslatiinn, wnii. targei,nodull,... modale patpa/l.aaaha) path)- # +18 ""pprrn,, target- target- (cranslation unit. target_oodula "aaaale..paah-__e (asthod)", # +12
92
93
96
STEP 2: Run the target codo with the test inputa
97
98
Proupt
100
Get. nutput fornat apecification from LIM response
101
1f fatal_ orroz:
pad branchgointa
aearchover (branchpoint, gitt,..riiit.... (trumslation,un) carraaiooo..iittttge.oooooooe caraat.
104
zeturn 0.0
105
Larget function LDM rwaponze
azroz: pad branchpointa
108
109
awarchovez (branchpoint.gie wew.ealoontt.g..co...... (tramslation,,us carget_ # +8
112
Paras target main Function code
113
fatal_arror:
pad branchgointa
searchover (branchpoint, giit. (tramslation, target,.coe__ooot)
116
return 0.0
117
...
target
fatal fatal_arron aeroor:
120
pad branchpointa
121
searchover (branchpotnt.
124
Add target nain function to target code
125
Run code with main function text. inputa
record_ccore (core 0.02)
128
129
searchower brancchoonnt.gtt.... commmt
*Rumninn sourcw ende (translaat intionnnit taargtttr sorrpet__odddleee moduul..prth)- [nwchodd", tbp ran, nource (tranclation, unit. carrger_ootll.ppttee patta-((mettt (method?", # +12
132
133
STEP 3:
Generate source codo main function and run
136
Proupt
Get source nain function code from LLM reaponse
140
12 fatal, crroz:
141
Parse and extract cource main function AS7 node
144
12 fatal_error: orror:
...
Add target nain function to target code
148
Bun target code with main function test inputs
149
151
match. fraction sun(satches) leu(aatches)
152
fraction
156
Beacoxpasa complle
def tranclate, class (tramslatios.uualll unit))
Sone setup (e.g.,
parse
aethoda_to, to__ttooitttttteeeeeeeeeee
160
nux www.eettodddeee to, translate Jon Lon/aothodo.to.rreee cranccaatte))
tramllate
aasa_testa_cout for zethod in zethods_5e to_dd___o__teeeeeee twa.slasa::::
164
searchovez (branchpoint comnit(
translation, untt. target_cede codyet_ceed__eeeeee
r'Begin (tranclatios unit. source clase. plase_path) tranclation
167
a trasslationn usit. source claooppatt)((auttecel d +12
168
3) +1
target_code, tramslate_ puccess trannlate_eecholleatbbb target_code, source_code, translation,
171
1f cauulase_sucessa
172
tranalate, sucomas_count (ecord_scorettaannla
paso_teats_comm)) +6
175
save Larget code
176
pass, Leata rus_teate Leat, socc.oodalee (Sarget_code, trasslacion,umi) pass_Ieste____mm teste_count +u pass_testa
179
180
elan:
pass, searchover code, compare (-0+2)
48

---

target_code,
184
Dourow sourow_code,
185
trinslatios_una
(-0+1)
188
www.ddd_ocoocrraoaatooooee Seccoeecccssss.... pass_teats_ +6
189
Eeparately
(Python
block)
not tramelation, iat.aaaioooommtia.e..... tast: ....
mun compmeetttttt Lo, cramalata t-
193
translate, saucslate succesa, pass_tasta,
196
codgei_code, soures_codm,
197
tranzlation_uis
acoze translate, www.latt__cccsssooooo success_comme pass_ wewtteetttttcooee count (-O+1)
200
))
201
record score (translate (translata_uucowaa www.sascccccccmmtt count. +6
... logging saving progress
204
205
www.tettttscct translate_ wtwp://cee_cccccsccooooee (nn(tthods_.ee tranclate), nev_branch
208
Bencmpaans compile
209
del aetup_antle4 (anuree((nn,,,c _oott_rott sarpet_codd_root, terperatorw):
cource_cabdir 'erc/astn/amtirr"
nuy, mur_caccessful_.tne trannilnioon
212
nux amm_saccossfll__2 parsssx
213
for dire, files www.ral(eurro.ccttee rote rubdr))
Read ancled gramar
216
217
searchover (rrehovertranncoointt.ggg
14
target_code code_
"'Iranslate antirs grarzar (eource (al..path.ssaaa))
220
anta wwwgggrrr-rrrrreeee Hil. path.atan) # +10
221
modification
224
225
Krite directory
227
Ruz sntlrd to gonerate target Python classes
228
229
files
231
record_ (uceessca tranelacions nun, mum_eesces pparsse)
232
233
235
236
Rencoraane compile
237
def www.ssataiiinnnnnommmo (source_cod)
sarget_code_root argo):
...
up logging git repo for saving progrese
240
0.1. Copy rescurce files (aro/satn/resoureee and azc/testtressourcs)) copy wew.yreeeccceee.ee wtw.ecssouceecoot
241
target_codo_rooz)
243
0.2, Set up antirt if applicable (cxe/soin/antti) /attin)
214
ccore cearchover www.tepponnrrdoooorrrreeecee coapcceocodooooooooo target_codo_roor, texperataa)) (-046)
topological order
247
cranclation.uni9 units get, www.sttaattionnoommmmmmm order,,oordrreeeee wttp://ooorrrrooddddeeeeeeeeeeee
target,
248
249
for transiation, translstion, wnits:
cearchover chrrasccoottt....... comiici
251
carget_code__tee poot,
252
I'Bagin (translation, unit, source, purree_clade clase_path) translation." # Trip-tramlaata-t12: wtraalattatttssatttaaa (trasslltionn unit clanp.att""
255
256
Generate stuba for the class gonerate_stue
generate (tusssstttttsssstiioooooo.o
259
total score to sunerate_stlle auccesa # +3 zecord_scoss score (total_ E
260
Traulate
263
searchover (breschpoiut.ggt wwt.tioritttttooeooooooeeeeeeeee cor.et(truncaattinn unit. www.:attcodeerrroooooteeeoooo code_root, branching-1)) +12
264
translate,co class rasulaa trunslate claze (trmmlaaioon unit). wwarch, ("pann" bean", bist_wi Sufault__brncching (-C+14)
westtt_cotttttttttttt count, translate, success, count, sethods translate, nev, bez_branch), cranslate class_realla
(pass_teste,
braschpoins_choood
wammeiiiggllmtmmmiatt....l. clausa # (see above)
266
prevent, apent
very a.g.
total acore +o pass_teats,____pppoaoappaaaeeete tat___tat__ccmtt (ous_rethods_co translace record_acoze pcorr)) 8
269
270
49

---

Tegging saving
234
275
return finel_comiit
278 ood_trrnslation.per wow.tooonoggt................... beban""" beas_vidthe3, defenet, defesit. branching-
x (-0+18)
Listing 19: Beam search in ENCOMPASS, 5 branchpoints excluding padding
50

---

Without ENCOMPASS: Explicitly defining state machine to support general search not only sig- nificantly obscures the underlying agent logic, but is also prone bugs such KeyError when accessing the dictionary cur state that stores all the variables. A lot of newly added code is for bookkeeping to maintain a persistent state, which is implemented as dictionary that stores the variables of the base agent.
import import nurpy a5 mp
att_.constttaarret root, log_etrr" reachec"):
repo Stargearett_coo pode_ root) 8
wish open(target_.ooee coceeroooooroottt / "courdt. log", "at) as +16
f.og.teloog. 'An')
repo. sat.)dd("),)
10
repo,gti git commin("" wwt.:ggt.comittt..o. log_ctr) +10
I1
cur_connit ssr(repo.hnn head. commit)) +10 commit
12
15
def chockout, n0w bransa coderreet_oooo___ee root, cur cor_conntt, new, bran nev_branch
16
Ropo (target, code.
repo.git. cbeckout (curico
18
repo.gtt www.ggit..iiccce p0itch( c", brancce_a_ac__eeeeeeeeee sane) midd()))) +16
19
20
run, codo, compare, wwwparo.ppceuuueeeeee
prelude(cur, etate, com_com cuz_ccore): det used variables from "our, state"
22
25
mothod cuz, astato aratt ("uethod*) +6
24
target_code
code cur_state stutsstta(""auut (aautttaauroeccc
26
translation, unit cur pur_state[""es "raatttttransatiiuuuuuus
27
28
Logging; define variables
30
zethod type "msin":
31
32
inpute
34
Store now variables to "non_stan atate
35
nev_state copy) a +6
36
("oethod") awthod nev_state("rua wtcpll_ooooooooooeeeoeee [og_ptthh_t
pea__cod__oo_p_e
38
state (teest inpute") test, iapots
39
nev_atate ('dapendancy_ (ileaaay_______aa ["fatal_ersor"] fetal_error
Sopundency_flleeeee files_atr
40
42
if "Byates.in" in" in souro__code:
43
git counit
44
git_.ormit((
tramslation, unit. Largettccoe_rooe
46
3"Gueeraee test imputa for and rest (translation unit. target sauggt__oodaal pacpe_ooodeepaabbeeee (mothod)*, (acthce
+16
47
48
return Bev_ stace, rua code, and_ cosparo_goa gesteetsoo_.ettttoeeeeeeeeeee test, Lapptt__oisttttee xain, sur_scoze, comsit
50
51
zeturn codecode, and compare_ruu aouret codea, exiating pain( our_acore, cur comxit) $ +9
...
scee variables
54
55
Store nevly defiined variables ax 'sev_atate"
()
nea_otate ("suthod") xethod
58
nsu_atata? (trim_cod__log.eeoo patpp rin_codd__lg_eee 8
59
nes_state ("mus, teat, inputa") nux, teat, inputa +6
["tarpet_cood__ut wwwp./tthoot..eett.
carget_code_uitt toooe_utthott_aatt
nev_atate cardge__cod_____ th_ddmyy.raat
sarget_crnde_vith with..ithhhhhtttaase...m
62
nea_state| "dapandenay... hagambaao_ffila__aeee [it"" hepanduncy_filee
63
fatal. error"]] [rrral_
frrol #
git comsit
66
comnit git.commit +4
67
translation, unit..target_coee
inpute (cransistion,,e target, wecpeettooosleepeeee www.sle.pptaai... (nethod)",
70
return twu_atase, run
car_acore, comsit a
71
72
73
def run_con code wnd_aaddddd___eeeeeeeeee canpare__en__eed
cur_comrit, car_asorw):
74
Get used variables fron tout, state attatlllaaee ('mched"""
75
aethod tranclation, unit cur, cur_etatof aur_etato("ecanoattto unit"]
18
77
run, log.path depandancy. files files_atr atr aur_statan ['depeedmmcyy.. filery [irr
cur_etate I' ('runrrcoooo caae_cooo____geeee woo.o_lo._ppttttee Jog_path"]
78
79
fatal, error orror statel (fabeee"attllerareee orror
chackout, aww_branch(
82
cur, commit, +2
83
t'bp-gen_
rain- [eranel lation.unis targes..odule.ppe www..le..aaaaa.e.eee....
[methhod*, teeeeeeeiii...ttt--eeeeee''
51

---

Prepare nast step
87
oev_siate cuz_atata.copp B +6
88
Arite input generation script and genarate inputa
91
Proopt LLM <-2
92
isgut forsat specification from reaponae
fatal_arror:
95
return nev_atate, wamalata_clls.gottaiee eur_acore, None <-2 A (-3+7)
96
ingut, peneration script. LJN responze
fatal_
99
return neu atutetate, mauuulat__clss.pateeeee cur_acore, Hone <-2 A (-3+7)
100
Generate inputa
arror: error
103
return nav_atata, cranalata_clava www.ss/osttoodeeaaeea. mir_acors, None <-2 (-3+7)
104
nevly
nav_atata ("atdin_ formec]] atdin_fomaat
107
ueu_state (' gan, iom_iiputa_cnnle "n jon_ieputs_cnde
108
t'test_ inguta] testt_ipuute #
[arrar"]
111
return codecode, rwn_code_and_com www__nneaaree.....o wat.rrre_r___rrreeeeee htt.://wwrrr.ccoo...ttttttnnne
cur_ncore, cur_commit) +9.
112
def cm__cod__add corgaren___ www.errgettttttttteeeee
cur_commtt, CIT_AGOrR);
115
Get used variables ax from car_atate"
116
gethod otatte""eehhot
Far_atate
com_code_oo..a pog. cur_atate["rmm, attaattrrmm.cck___gg.ettt
119
dependency.ftlee str cur_statal""dee deepensmey..tiloo.eeee
120
stdin_forme formtt statal ('atdin, format"] a 16
toptsi cur ("tost_inpuree"
122
fstal_ error our statel "fatal_error"'] #
123
124
Directly
tected mothod nain function
aatch
127
128
Store variables "ee__ttate"
acv_state cuz (tt_tttte.cco7) copy() state tesspeestss, tests, count")
(match) 4:
131
decide
score set.ttttteeeeee Stranlttranniato ruccese,eeeeeeeee count"] nev, ("pare testseeetsseoooeeeeeeee count return _es_etate, cranelateecllss. www.an.ostlldee.. score, Hone <-2 (-3+7)
135
136
run, codo. and compare_gen, weo.geettttttooteeeeeeeee test, Anputa (cur, (cur_ paate, cur_cornit, cuz_acoro): det used vart variables from ptate"
138
139
method our, wewattttteetttte translation,
cur_statol (wtrratttattiionuuiii
run, ron_cod__ pog_ cuz, cuz_etate "errrru_od_d_iee log___oo____paaa1 mut test, inpute testt_ target_codo. aado__ithhuttpee jaia cur, state ( paatte"targo__code socdo_wtthoutnnatn $ +5
cur wet.tttattemmm mum, sest septtanpptt"]
143
dependency, ftteeseetr cur_etate ('dppedddaa tetol, cur_state ["fatal,
146
1:7
chockout, now, brancc # +2
cur_canit,
1' gon, inputs (translation, porpeee_ooollepppeee patataaaaaaaaa (method)"
151
Write
inputs
154
Proopt LEM
155
spacification zeaponae
erroz:
158
cornit coramittraalastoe unit. Saagge__code_eeeeeeeeeeeeeeeeeee +8
159
zeturn cur_state, con_codu, and Samppare_dlll_... cuz_score, commit # (-3+7)
... test input generation script respense
162
12 fatal, arcor:
163
comnit att.ccomittrrssaaatee catesssattoonnnutte unst, waw.ettttreeereeeeeeeeeeeeeeee code_root) # +8 cur_stale, rww_cocn_and_ccpppree.
eut_acore,
166
Gunorate test inputs
167
if fatal_ srror:
git_comii (trassaattiiiiinn wsit, targett_eeeeeeeee.....ooooo (ett___ode_rett)
retura cur_state, run, code, ccaparo_idlo____ score, comnit (-3-7)
170
171
# Store novly defined variables "sev_stace" car_atata.copy()
mes_atate (fatainn_ [orme"]] stdin_fomat
174
nes_state| (' wwwp_lapttaacdooo
gon jon_iapata_code +6
175
nes_atate ["twat__ [eguta_1iatt] caat, intiiinntaa_____ list
futal ecroe"]
52

---

Corputa scare git comnit
179
score nev aiate (artte(bbbuuosssese + 0.01 # +10
180
comsit gār, commiti & d.+4
tracslationn,ee ittpesmnmtttt..tt....oo.
("Bunnin tazget code (trumsltion,,u Larget, patke
183
184
return rez_atate, wtwp:ccll__ddddreeeeeee carget,t_t comnit A
187
del run con_e and congarae idle, ((ur state, cur_cormit, pur_acorw): A
188
translation, unit cur, ataatte"truulaatioonn
# #-+6
brunch commit)
cossit (trrmni (trrmmlation unit. code.,atto) 18 return cut stase, run, code, codparrrrree iile__ car_acore, comrit +8
191
192
run, code, and, cospare, run, target, (ode cur_atate, cur_cosnit, cur_acore); Get used variabl wx from "cur, aatata
195
196
aaiate nothod aaa.aattta"aalaae ("awchod") #
tranelation.
aur_state["sramnlatte
run_ cmn_cod__og..pe pat pur_attte[""rmm (errrr"n_ooooe code__ag..pata""
199
cadgei_coda, dew.
our "ar_aatte""""rr ("tarr""erreoaolloeeeee codi___od___eieeeeee wwt.eooittttdaeeeeooooo dansy
200
dependency. ftler_atr cur_statal ['depeddencyyy-
firnccyffiesssrr77 48
aadin_foman
('aatiii_fffomm formatt"
gen, cndeta cur cur_atate aataatataeaaan inputa_cnde""
203
tass_ tass_ingete ingetss.tt....
aar_atate[" intsss_
48
204
fatal, arror cur statatata[ ['fatal_ # +8
Maackout_nww_beree branhranch(
207
cur corri,, +2
208
tbp
(trane lation, unit. todues (method)', (nthood,,,,
211
Run the target code with the test imputs
212
... Proupt
214
215
Get, mupput fornat apecification from LIM responze
fatal_ orror:
att_commts
target_.ode_.ror
return cur ststa, run, code,
caceee_nd___cppprre wowparae_ddlllll iidle,, sur_acore, conmit (-3+7)
219
220
Get target function fatai_crror crror:
LLX
222
cornit git.commit (wranclattoonnnnnooooooo unit. Parget__ode__oott 48
223
return cur cur_state, run_code_and___ wtt.:/nddccpprr.ddeeee... cur_acore, commit # (-317
224
...
target
226
error::
227
connit git,comii (traneliilllttoon unit, target_ codee +8
228
conde_sn__comprre...mm compare, and,
connit (-3+7)
230
Ertract target zain function AS7 node
231
12 iatal_orrorr.
eit_commi (transsatin, retura cur, cur_etate, run, conpocopprre_... cuz, score, connit
234
235
Add target nain function to target code code
236
function inpute
238
Store nosly defined variables to "se9_stase" etuee cuz, cop() 46
239
sucdout_foraeee
format
nex_state ""target_code wwwo_wooodddoooooooooo mainn]] targes_code, wwte_oith__ettt
242
new state ('run, ttrguttargettttttmeee targettrreruutttteet [aaget_reeulte"] run, reruer.reetttt -6
243
nou_state ['fatal_ orroe"] fatal_error # +6
244
Carpute
giz
246
score no9 "aatte"baae_ece" commit git, comnit( +1
0.02 +10
2:7
trazalation, ceode__oot,
f'Bamning source code (translation, wnit. target, module_patki) (uccho (seechod)",
250
251
retuzn sea_ataie, cww.code_esddeeeeeed wwwpardddooeeeeeeeeeeeeee wttpaare__eaaorrreooooooooo score, comnit #
252
254
def run_code and casperaaaeeaa www.iiddeleedd_eeeeeeeeeeeeeeeee
2(cur state, cur, cor_conit,, cusrscore): A
255
tranclation, unit cur_atato[ atwtatttttaaaaaa "aaatttfrransaaiouuuuut)) # +6
checkout brenchh(uur_ccomii
258
Store nov variables to "809 "soo_ttate" aea_atate sur_atata.cog (opy) +6 ("asthod Idx")
259
262
# git comsit; decide next step
263 if nev_state "ssattt"sttood_id mn Ian (taeeeeesateef (oothoda to, translate")): d
None next_atap Lranslate, wwwssccaaaallaaeeeee
266
clae: +2
267
nev_atatel (owthodd" nev_atatel fnotthdea trenelata") [owu_atate ['wwthod_idd='] +13 comicc)
53

---

translation, waw.etttttototooeeoooeeeeee
B'Bgin (tramslation wtw.sttssosoo.oooooooooo translation [onv_atata(""wehod 13-""
271
)
272
next_atop translate_ wwwhoodeeddddooooooooeeeoppee save A
atap, sur_score,
215
276 del run_code_ and corgare, www_aauure_ccoom cecprro__cdddeeeeeeeeeeeee
code(cor__atttt coomiit aur_acorw): +9
Ges variablez from mathod cur por_attatemmmchod"
279
translation unit in
cur sur_atate["
+6
280
run code_ lom_cood_oog_aeeee pog_ cur_atate ("run_ "ra 46+6
281
sur__atatal"aorra coddr""
cur carget_code,witt code_vith_nainn cur_atata( (anaaaatt_nnnluuuiiiii atdin, forat cur, cur_atace sutdin_fosmat")
283
284
stdous, formet statal satdou, format"] a 16
list
(aaaaatt""at_apptttttae [istta error cur_atate[ "fatal, erroz")
287
288
chackout nww, brwnchh A +2
sig--ran_nurraw- (trans uni barget_ www.reee_odddd.oooooooo www.soo..aaaiiia..aaaao path? (nathhd)"'
291
)
292
stap awa_state cur_atate.cooy"
Prepare
295
nov_rtate nww_atate["rethod (ttwthod_ idx"1 =- 1 # +8
296
run
299
Prompt LEM
300
rezponse
fatal_error:
303
git comit; decide next step
304
rez_etate wws_ettate"rmethed ['mnthod__ddd"' (nwv_ataate (tteehaaitttt.tttraaaaaaaaaaa
conzit
next_.tep
+3
307
slawz +2
308
("rasthod"] neu_statel stste("xethods, transiate" [nez_ctaaee ("athoottttoo__idx"
git..cornit(
tranal aatinllatinuuuttttooo www.tttarget.ccca.....o
311
2'Begin (tranclation, unit. source_clace.patbe translation of "totttt"ootooo")) 416
312
soxt_
and, save
314
return neu_ctate, stop, score, comnit (-3+7)
315
function node
orror:
git comnit; decide next step
319
Scz(aav_etatee taaasev_erteertetheee ('aethods_ peeeshodd_tt__eeeeee trancllate"]): # 1f #09, se9_statee" (aatte""attod__da
320
loone
soxt_siep translate, i
322
cloc: +2
323
no9_rtate wet.atteentthocc [" - www.etttt[["xechoess ttr.iiods_ttttrsssssttts." [ner_stare ("ottrodddddd_ddd] 413
git_cormiv(
tranciation, unit. Sarget_codo_roce
326
*"llgin (trane lation, uonttontt.....o.. clapce..casss.tttiie translation of [nee_statel (net_state["tethod"" "Iothood 13.", +16
327
+1
328
tranclate mwtteedd and, nev,etate, next_.tep, cur_ecore,
(-347)
330
331
Add target nain function to target code target code
function inputa
334
matchee
335
Seiclffraction sun(sarches) / len(natches)
336
"pes_state"
338
nea_state cuz, www.sstaeeccpppt # +6
339
nov state pase, cesta_count") fatch_fractio +6
Corpute score; git commit;
step
342
scoze 209_statee sratee"translate" sesssss__cccsse_ee rount"] =ov__tate ptpapttttappas westoeeosuuutteee count") # +11
343
nev_state| ("sathod_ - Isn(awv statel ('owthoda, to tramslate a
Hone
next_step trrmclase_clacoppotttii
346
slau: +2
347
nev_stase =ttate""eetod") soo_stazef "ttazee"nothoda (tnohhodd_s to, trinslate") (aev_atate (avv_etat((xettto__ddee +13 gotmcc
translation, wnit. Larget, codeeet__cdddeeee root,
350
I'Bogin (translation unis, source clacc__cassspptt) tramslation of (oousstato(xechod") [""ettod"")>"" +15
351
translate pothod and
ptaee, next, atop, scoze,
(-147)
354
355
www._ells_pppueeeee (our_atate,
cur_acorw):
Get used vuriuble from "cur_state" translation unit cue, wwwaaatatt""aaaa "waate"frrnsaatiouuuu +6
358
359
(e.g., and parse files)
54

---

nus, nun_rethods_ta to, translace inwthoooods__t taaraaaaaa)
363
tramslate, success, count
364
cepp_tests__ooue count = for
rwthoda, translate:
367
Store sevty defined variables to "se9_stace"
368
ows_state cur_atata.cog ctptt. # 16
("aetheds
oethodo, trinslate
nnv_ntata| sear___ethot__o_teeee tranelaaal mun rin_rethods_ translate
371
nes_stals ('cranalata, auccesa, count"] Lrunalate, succeas_comme -6 Crmnllats.mncceaz
372
nes_state (' "pasa, count") pas__tests_coume couts_couut
("awthod__dds idx"]
nww_state swthhdd swthods, [ramslatee[]
315
376
conmit
git_committ
translation, usit. www..ttttttttt..ooo. soot,
179
BBggin (trana atinmnnnit............... sourec smires_clant.pat)) tranalation of (nev_statee ("nwthod " +15
380
re2_etase, translate_mehoo..ed_..wo cur_score,
385
384
def translate, waw.laateeed.aattt and_eaveeeen (eur_state, cur_comnt,, cur_ecore):
det
from cur_atate cur_atate("accho"))
187
cranslation_umis cur attatee"trenilatiinn. source, code cur_statal "sourrs__code
#6
388
18
target_ cur_state ("target,
trand mucoea couns statet (transeeettannaeeeee.o wttpa//llaattttteeoeoooooeoo count"]
391
paza teata, cur_atate sataate"'pan "pan_tteatx_contt)) +6
392
chackout branch(
our comsit, trrmmiiate-ttrraaltttim
395
1bb-- translate--eeee (tranclation, aareilattionnnittie clatse.catss.path/ (nethoo"- #
396
transiste, retbod(zethod,, nev_rtate our cur_state.copp capy()
399
400
tranelation,
cranslate_miccess:
tracalata__micone castt_,nccceesccmntt count
403
acore translate_ succese,ccomm count pars_sosts_comnt
404
... target
407
1f tranclacion. wetilasiooo_mnttii...e www...t..ttttttt........ # C-]
408
pass_tects_
www.noddllelaecee wts...ooleetaagge.coom translation, unit)
pans_tests_ tenn_ttettscconnt ron, wnw.ecode_nd__rppueeee
411
zethod,
412
code,
414
pronslation_ unit,
415
neviy defined variables "nec_state"
ses_etate[ "ecore" ceensisto.rucceess count pare, tosts_count #
419
420
comnit)
422
Stoze 209 variables to "tov_ttate
423
nov_ctate aov_ctate["sethod, Idx") +-
git commit; decide next stop
426
12 www.etatel"settod..
len state ('oothods, so.traanlatte")
427
comnit Hone #
next_step trrasiste_class.peoo clw.sssppsttidd...
else: ["o_sttatt""ethhh" wwv_stated ('nothoda__eee translate") [nveesstt[[tserttoo_dde] +13
430
431
connit commio) # +2
translation_uii target__ttgttteeeeeeooo
I'Bagin (tranolation unit. courcoeclass.ppaat
(aov_etate("xxctot))
435
trainlate, pave a
next_atep,
438
439
classattteelaaeeeeeeeeeeeeeeeeee def translate, class, wttp:ppoottt_teeeeeeee (ttpudd__o_rrrotttteoeeaoao coEncot cur_score): +9
des variablez translation, wiit a target, codo cur, our_state""targed "aaarget_code)) wwwmllatesunccss.coo pass nut sothods, to, tranclace cur ocate ("uux, zethods, to, tramclate"]
443
tramslate suncess,comm cur, atate "aaata"""raa ("Lranalate count") a -6
"ur__atat"""pe pasa,
446
447
nov_state state.ccom capte.copy(
-5
Separataly tout nain function (Python __Rane... "_aaiin_ block) present 12 not translation, is is_test and .... munuwthhods, to, translate
450
451
55

---

453
neuly variahlea "tau_atata"
455
nev_atate (" I'tunnjnchuiaa Lacdda_eoo trumllatt]] ninunecheds, to tramllae 2 16
456
nev_state ("trasslace_ success, _uccess_couat"] cronslate wuceessscccccccooooocooeoe count F +6
["rathod"] "main"
puccsss comnt count pass_ 3 nev_atatel ("bass_ acorm")
459
460
rwturn conn,cod_.aee and conpara. www.:pppwwldeeee...eeeeo
cur_commict) #
reburn tranelate, www.eeeeacneeoooott.ooooo wet..pootiddda (nec_atate, dir_corntt, cur_acore)
463
464
pir_acorn):
Get used varlables from "cur_atate"
467
translation unii cur our_atate(" "wa.d"ccaaaaiioouuaa
+6
468
trana auteeuunoossscom
cir_statel "ttate""trann ['trranlaate, perrannlateeentee count"] +6
pass,
pasa,
nus thoda, to translace cut acate puuu aotthoada_oooo.. trassassatt""
471
472
logg and aaving
return_yalus (pass_taatt__com return retorn_valow, None, cur_atorw, Yone (-Or11)
ancones count, niy, nur_ratthods,co wtt.eoood.c.t.tatalleeeeee reg_branch) (sen belox)
415
476
translate, castt__llaeeee class (trannaaaationnuuii bean_vidth, branching): (-0+4) Use bean search to translate class nethod-by-nethon
479
480
anit_etate ("transiarion_ tranclation_
step transl wtw.:aaae..ppeleeee...
483
commit. Konw +3
484
Shatt,atup(init.atttt. init_comit, init_atorm)]
487
resulte [] a
488
while lan (bowe) 0:
pec_prograz, states_.iett
for state, step, score, commit bext: +11
491
sww www.pragran_atase. statee [stap(atata, cormit, score) for in range (brgechhhh) +18
492
sov_progron, states.tte.... andd x(2), reverse-Irue)
www.prorran.ttteee stater__tttte__see www.aappeeppporreeeeeee. wtw.aewwwwoogontttteee.e
not_doma_nee nww...nv..eer www..pragrwr_ttee attate
495
for in range (len (nev_ prograr, (tstes_1ict(oi] randon permutation in up sp.randon, permuatiion (nee, prog_progaar... states_liet)); +18 new, new, prograz, state new, sev.progras,ctatess states, stat [1] +8
+11
496
indices break ties
499
new staata nec, nec_step, nev_acare, nec_comet zww.progran_etare
500
stop Noone:
reculte, append (nev_ctate, nec_score)
slee: +2
503
not, dond.ddo__ce progran, states, apw.ad prograr.tttateee 8 +6
304
not_done_nect pev.pogrrrr.rrrr... etates, cort(
loyelasbda progran_state prograx ptateesr_cateoooooo score, roverse-True +12
306
507
bean not, dote__oo__ee www.neeewrgor....om httprrsserattteeeeoorrooo
resulta
511
def setup.aztird, prueudee sturette state, cur, connit cur cux_sc)re): # (-6+6)
512
det variables from
spurce_code_root cur,state[" staattl"ourrceooooorrrooo
514
515
nov_ctate cur_ctato.copz( t 46
source_ "arc/aada/antire"
518
new, stutetate| (i trancisstons="
519
nou_state ("aus_ auccessful parsess"" = +3
520
""roos_dirs wttpdddrrrrrreeeesss_eeeeeee 2ist"_ l1st www.://ourc_coooocoooo source_eubdiee) (-B+8)
in
522
525
nes_ctate ("2001_ besoot,ddree dirrr.ille....ooiiioiiiiiiiieiie sdx") +
("1ee ida"]
326
root, dirs, iiles new, wtw_staeell satttol'ee ["root_dirs, dirs, dirs_fflce, filce, 1ist" stee_state["" ("root__dee #s1es__dx"]] +14 file filea staasttttt"" idx"]] +8
527
...
gramzar
330
531
# Store zovly defined variables "se9_stace"
(ilepat__il__pahh") nea_atate| grrattt"""rarrrrora comienit gearnar content
534
535 # git comsit
cassit git_cormit(
sarget_code_ root, ITramelate actleé gramar (snurc__file.pall (ir.ree/ile..athaaatee?"" +10
538
539
)
relurn staje antup.antlrrdbodd cur_acorw, comii
542
543
def setup_actled, (eur commit, acore)
56

---

amnree_cod__rant sur_atate]" wwwrce_sooaa_raeee
347
Larget_code ront cur cur_atate rod"__ +6
548
tesperature translation
4.+6
mus_auconasull mus_pucceafull parsea Auu_stte("nuun successt parsuez)"
por__atat=""mn__nucc aac.oassoossflll___. translations)
351
root, dizs, files ouz cur_state[" ("rote""rot__d ["root_ddrs________ files, [ist"]
(eoot_ +14
552
film files Caur_atata("Fii [" +8
sur_atate[" aauusot""arooe (aaeree_flle.paaill
grwwrar_comee comtent our cur_state[" gramear_comtns""
555
556
chackout n00, brunch P +2
Plgp-trmmlaas wtw.rr....rrrree... (scarcsssaaaaaaa filerrre__flll,aeeeeeereeeeeeeee (tw../flaeaaattaaeiiee..
559
)
560
... andification seaded <-2
563
Vrita to target directory & c-2
564
... Cbeck if the gomerated Cilea can be parsed <-2
generate target Python
567
568
min_ancoonaful trrnnaaaiions minesscoenafll parrss
571
nnvatate our car_atata.capy( # +8
572
loop nnv_ttate forssddrr__fileee....
575
neu_tatte? ("ffll_idd"" +-
576
""tile__de""" len(tiles);
+10
loop complated
loop
579
nev_state wti.satttttileeeee [iileeddd" = e 46
580
(nnw (ntuu_attael(" ("ante""rnt,tillle www.ddin...eellstttte +12
loop completed
code zepo tranclation agent
aww_otate"ttttll..o "attal raturn code_tranal srst_ttaanlation peramnlatioonngett...o cntioonnttptttteee pralude (nwu mur_comitt, cur_acore) 4 (-0r15)
www.eeeeol..prreee...o x (see below)
583
584
root, (nat__ (file, Idx"]]
proottterrottddee ['root_dire wwr..t..rrr.llleee..e.ee ftlee_ [nee_ (trooo.dtrrr.tileeee..
587
588
Read antlrd file <-2
Store noply defined variables to "tate
591
source_filn.path 46 content"] grarnar, content
592
git comnit
595
comsit commiti # +1
396
codet
I'rrmsslaee antlrd gramnar (sourco_file_pens (tt..filll.pa..aaa.....aaa
598
)
599
comxit
603
def code translation, age.bi...aearr.eeeleee wwtp:ppoooto__ccuureeeoo sttte, cur, commit, cur cur_score); # det variables "uu_ettate"
smurce_cod__oom
606
target_codb_roer cur_stated "taate""arget__odd_rr"""""
607
up logging
zepo saving progress
610
0.1. Copy resource filee (ere/aattaresoorcee and src/test/resoorres) wesoarco_fileeaaoeeeee
611
repyrresorcee files (iwrescwuro
targes_code_roos)
noply defined
"nev_rtare"
014
neu_state cur cur_state.copp/ copy #
615
nev_etate ["repo"] repo -6
("remllta")
sea_state casparatuur") ocate ("arg"") teaperature
618
619
return setup. wttp://wiee..rruuuaaassa.eemmee cur commit, cur_acore)
622
def code_tranzled translation prasiiacion..gett.ppeleee www.tt.peeluss_eec... (icud___(csssatte, cur cur_caxit, cur cur_scoze); F +9
625
det used variables from "cur, cur_etate"
target_code_rett sur_atate[" (aaattt"""uue_...
cur_atate cuarget_codd_roet
626
627
# det class nasea in Eopologicul order translation
get, www.crassaatinnerr...ee and depandenc (wwurce_cooe_eeeeeeeeeeeeeaeeeee targes_coda_roos)
630
Store sevly defined variables to 'sev_atate"
631 nou_state cur_atate.copy() +6
cracslation_unita asa_atate Cewmulationn [_dx""
634
635
# git comsit
teamslation
"astatt"""eee ('crmnslation unita [nev, (" unit_idd"]]
57

---

stanslation..nit...i wwwp:uintt.trgge.ooooeoooo wtt.eaattttteeeeeeeeeeeeeee root,
639
I"Bugin (tramslati aatinnattinnn unit. source, source, class.paaa tramsationn" +10
640
) +1
cur_acore,
643
644 def code,
poale_t tranalationn ention,tiionii aegetaageetttereeeeeee
pww.ppaerttaaaae attura (our cataee, cur, car_contt,, aur_acorw); A Get variablea
aranelation_um cur, cur_atate["tramal attranalaaioonnniiiiti wtt.ttteeeaamllllaiiooooo i11 tatal score cur_atatal (total"""ooallaaaaao (acorw #
647
648
chackout branch
our comsi,,
651
Mlp-ttaanlate- (trraatttttttaaattte coinnaatiooniom unit, source, courc,,laraa.pahhl +10
652
)
655
genaratasaalbe stteesstt____seeeeeeeeeeee auconss
<-1
656
gecerate_atibe
659
Store sealy defined variables to "sev_atece"
660
cur_state. copy()
generattaataati paconaa"]] generata,ataha,
ataaatate acorw"] total_acore
663
664
# git comiit
cow.stttrraaeaaattoo...mmm warget,code.roon
return state, Coderransalttiongeeete chwerrreeaatttttooeeeeeeeettteee 2), tatal_score, comnit +12
667
668
CadeTransl aet.eenggeerrrrraaaallllaa
i.iiit... (ailf, birth, branching):
671
selt bear, width bean,pidth #
672
self branching branching
called Palce
+6
675
676
def call... (self,
cur_ecore);
sarget_ mur_statal ""t.atttaaaarre........
679
tranclation, unit cur curastatel "areee""zee ("traaalssionnunte unit"] +6 sotal_score eur_etate (total. "totol_ccoree] gencrate_sten stube,
680
cur (t
683
if not salf.cal called:
+6
branch(cur, commit)
self. trane www.aaccaaac..c..eee...eeee
tromilate_cclene(raaaeeeiii. bedn_sidthrseef www.ddthreel--bbee.rded.d bedh,, Dofasit__bannching
self. branching) # ( (-0+20)
687
self,
690
(pacs_teste,comm count, translate, countss_count, 20 omn_zethodr_ta self outpur__dx)
to.ttranslate, nez_branch), selt. arrnnsatee_clase.eee
above)
*o1" to prevent agent from "chesting" (have very for oig: zero stube implement) sotal_score + tests_ count (aux xethods to, translate +)
693
694
696
697
Increment result_.dzz self Idx
700
Store new variabler to "nov_ctate"
701
nev_state coppo. state ("cores__ccore" total_ neq_stase ["reeulte"]
704
for translation, unit is sranslation_uitta nev nev_stase "aaaactirassssiiooo... _mit__iz"") **
705
git commit; decide
step
708 1f _es_stase| "raace"transaation.ue _nd___dxi__ lez www.:/aateeetnnccttttooooo :) +12
709
comsit Hone +3 soxt_siep
clse:
712
seu www.trriiaaiionn.o wnit nos_state wtw.saateerrasssatiio.oue (ows__tate("" Iataaa/aasaaattttsstttttaooaooo (dee)) +10
713
commit git, cornit( F
craaslation.uii.tuuee wtwp:aaiii.witttuupeeee....eeee
I'Bugin (ues, tww.stacciinnnoooomooo www.seeeeeeeeee..eeeooeeeee tramslation.", $
716
+1
717
mest_atep cade, tadk_trassslttion pestttpeeerat..atua noxt_atop,
comit
720
721
def code_trasse
lioe www.ttppptteeeeeeeeeoooooo state, cur, comsit, cur, cur_ec) # repoxitory
translacion,
Larget_code, code_ront "ur_atttt"""tree (ttoaaaaeeeicccc_rooooooo cood____o_o)
724
repo cut stace ["rupo"] +5
725
Pinel
58

---

reborn_yaloa final_cormit
balow)
729
return valorn None, out sar_s,c None (-0+8)
730
code, trandlation, agant (sourow, coot, target, soot, arga, bean, width, branching): (-O+4) Use bean search to translate a class bethed-by-aedeed
733
734
init_state
ceeersa_cdeerrott souren_ende_ "Larget_cndl__ree ronte" targei_cnda_root, +5
737
738
"argat: arga, $ +5
step code, translation prentupr
141
comit Kene +3
742
init_acore 0.0 +5
atap(inntt. comict, inlt_acore)]
745
ramilta [] a
746
whill (boe)) 0: A
nev.progran_staters
state, step, acore, commit benz: +11
749
branching befault..ranchhnng if noc is inimstane (atap, Colbhruaheeislggeeaaaaaaalaa slaw step. www.hhenchiingg
viep # +19
sww.progran_atatee [step(atate,
(branccin)
swv, www.progran_ataeee statss..ort(kyy-lanaall
x(2), zeverse-Trum)
752
nev www.progran_state strusttaer____e list. seiisstappedddnma wwwenddaww.roggwnettttetee
16
753
not_donw_nee, www.ppragnee.. jatatex
+3
range www...pograr.eteee....... sregror_
randon permutation on indicas break ties
756
for in up, randon, permutation rew.rndon..ermtaaiioo. (1mn(nn atattrn list);; # +18
757
nev.prograz_ pro.grrrgr.eetee
states, stetts
48
nee_stap, nec_acore,
www.progran_etact
nev_stap stap None:
760
resulte, append append stet, nev_score)) 48
761
slae: +2
done www.nnccppeeeee pwwgran, statenn (pw.
not, deme__net.rrorree states.eors cort
764
kanblanbda progran_atate: progray_ataate..o scare, reverse-Trse # +12
765
pott.doc..eev.poree
reburn ras (rwaul it, kagel lamoda x[2))
768
769
ageat(.... (..., sidch-a, branching-3)
(-0-8)
Listing Beam search implemented in plain Python
59

---

D.2 Case Study 2: Hypothesis Search Agent
Base agent:
def
(task_info))
# Step 1: Get natural language hypothesis
hypothesis hypothesis_agent ([task, [task_ infol, sypothesia_innstructiinn
# Step 2: Implement the hypothesis in code
code solver_agee ([task_info, info, hypothesis], solver innerr_nisttructin)) tattteetttttuuccaoie
10
11
12 two_step_agent (task_info) Listing 21: Simple 2-step agent for ARC (base)
60

---

With ENCOMPASS:
import encompass +2
Gencompass. Gencompass.compiee +4
def two_step_agent (task_info):
branchpoint () # +2
Step Get natural language hypothesis
hypothesis - aypothesis_agent ([task_ind)) info], bypothesis_instruutionn))
branchpoint() ()
+2
12
Step Implement the hypothesis code
13
14
code = solver_agent ([task_infa info, hypothesis], jolver_instruction)
16
Evaluate
17
percent_correct run_ (eoealldaationcode)) +6
18
record_score )percent_coorrett) +4
if percent_correes =- 1: # +5
Sarly_stopssearee
+2
21
22
return get_ pet__tett_oupuuttie (code)
23
25
two_step wo__see_ageet (task_info) seprac("paalllel_.bbr default_branne br x (-0+9)
Listing 22: Parallelized BFS in ENCOMPASS, branchpoints
61

---

Without ENCOMPASS: The code devoted to parallelization obscures the underlying agent logic.
from concurrent.futtin import ThreadPoolExecuton) completed # +8
def wro_step_agent (task_ing info, branching): x (-0+2)
results 0 +3
foll_solved False +3
with ThreadPoolExecutor(( as executor: +6
def () +3
if full_solved: # +3
12
return
13
Step 1: Get natural language hypothesis
14
# ->2
hypothesis hypothesis_agee (itask_info) hypothesis instrruttonni
->2
16
17
def implement_in inde # +3
nonlocal full_solved # +2
20
full_solved: +3
21
return # +1
22
Step 2: Implement the hypothesis in code
24
->3
25
code solver_agent ([task_infe info, hypothesis], solver, solver_instructinn
->3
Evaluate percent_correet run_vall (on_valllatioo(code) +6 if parcent_corrett == 1: # +5
28
29
30
full_solven True # +3
(-1+7) futures [executor.c submitt (implemmmtmlmmnnnnn....... inn for range (branching)
results (oppend(gee_ttst_ouuceeeee (code) percent,correct))
32
33
+16
for future in completed # +7
ruture.result() +4
36
37
futures [executor.
subecutor.submit submit (run_one one cereoonn_frrrrre mue_fooward__pas) for in range range (branching)]
# +16
for future in conuueeted(futuress) +7
ntture.resut( +4
40
41
return max (reaults, key=lambda x: x[1]) [0] # +16
44
two_step_agent (task_info, branching-a) x (-0+4)
Listing 23; Parallelized BFS implemented in plain Python
62

---

D.3 Case Study 3: Reflexion Agent
Base agent:
def reflexion, agent (task_ info, internal_tests, max_iters);
# first attempt
code = solver _aeever_aeeteeeee (task_info)
percent_correct, feedback run_validationncode, internal_tests)
if solved, exit early if percent_correct =- 1.0: return code
10
for cur jite in range(1, (1, max_iters). relf-reflect and apply to next attempt
11
(code, reflection = self_ree self_roflection_agent (code, feedback)
code solver_agent (task_info, code, feedback, reflection)
14
percent_correct, feedback run vadidaatioooodde,, internal_tests)
15
16
if solved, exit early if percent_correct == 1.0:
code
19
20
return code
eeflexion_agent(....
Listing 24: Reflexion agent (base)
63

---

With ENCOMPASS:
import encompass +2
Gencompass, Gempolpass.compile +4
def reflexion_agee aeeeiiinnnaen(eeeeeeeeeee (task_info, internal_tests, max_iters).
record_score (0. 2)
+6
branchpoint() +2
first attempt
code - aalveraagents (task_info)
percent_correct, feedback Yun__allidtiion(oode, internal_tests)
(opoodd_ccoeeperceet_ccccom correct) +4 rerionaa_returrccoooo
12
+4
13
# if solved, exit early
if percent_correct 1.0:
16
early_stop_search
(-2+2)
17
18
for cur cur_iter in range (1, max max_iters):
branchpoint() +2
self-reflect and apply next attempt reflection self_reflection_agent (code, feedback)
21
22
code = aaalver_aeentttak_innn code, feedback, reflection)
23
percent_correct, feedback ion.valiatiioncoode internal_testa
secord_scorepprrcttt_ooree correct) +4
25
optional +4
26
27
if solved, exit early
if percent_ == 1.0:
early_stop_searche
(-2+2)
30
31
return code
32
reflexionagentt search ("reexpand_beet__firsss
best_ bestrfirstttt max max_num, www.uressltsstttte1eeeeemm (-0+9)
Listing 25: Reexpand best-first search in ENCOMPASS, branchpoints
64

---

Without ENCOMPASS: Defining separate actions for search obscures the ordering of actions.
from queue import PriorityQueue +4
def get httpiiallattttpttttttee (taskm_ittn info, tetetsal_tests, max_ pax_iters): +9 first attempt
code solver solver_agent agent (task_info
percent_correct, feedback run_validationccod,, internal_testar
# if solved, exit early
if percent_corree =- 1.0: early_stop True (-2+3)
11
12
13
next_atep do_one fo__one_releeee reflexion # +3
return next_atep, early_stop stop, percent,correct, code, feedback, 1 +12
15
16
17
def do_one___
internal_tester max max_iters, code, feedback, cur our_idx):
# +15
Self-reflect and apply to next attempt
19
reflection self_reflection agent (code, feedback) <-1 code Salveraaeette (task _inf, code, feedback, reflection) <-1 percent_correct feedback run_ san.validaiiooccaa (eeatall <-1
20
21
if solved, exit early
24
if percent_correee correct 1.0: #
25
early_stop True # <-1 # x (-2+3)
26
next_idx cur_idx # (-8+4)
28
next_step None if next_idx max_iters else do_one_ree oneleeeeiiooonn return next_atep, early_stop, carcent code, feedback, next_idx +12
29
30
Apply best-first search choosing the highest-scoring state 33 to apply an action
34
def reflexion_agent (taak info, aaternal_tests. max sters max_nu_reoulls): # (-0+2)
tuut_program_staee () +3
36
init_step get_initial attempt
37
PriorityQueue() +4
38
soogram_states_to_exee put (init_step, init_ program_sttte)) # +8
percent_correct None # +3
finished = False
41
num_results
+3
42
results 0 +3
43
while not
expand.exptyy. and not finished: +10
step, program_state program_ states_to_eepeeeeeee_eeeeeeeeeee exp_add
exp(nd.pop() pop() +8
program_state eeppiean_t_eppaad..eeamm put (program_ startam
put it back
46
next_step, early_stop, percent_corree correct, code, feedback, next_idx step( task_info, internal_tester max max_iters ittrs, *program_state) # +23
47
eesults.appente ((code, percent_correct) # +8 if early_stop: +3
19
50
if pext_atep is not None: program_staten stwatsstttttttte to expand. put (next__tep, (code, feedback, next_idx)))
51
+13
num_results
33
if num_resut results >= max max_num_resuuts: +5
54
break # +1
55
return max (results, key=lambda x: x[1]) [0] # x (-1+15)
58
eeflexion_agent(C max max_num_resultee
(-0+4)
Listing 26: Reexpand best-first search implemented in plain Python
65


Reviews:
[{"review_id": "1b5zLyuN6q", "reviewer": "Reviewer_fzrw", "summary": "This paper presents the ENCOMPASS framework a method designed to decouple the agent workflow logic from inference-time strategies in large language model (LLM)-based agent systems. The authors introduce the concept of \"probabilistic angelic nondeterminism\" (PAN) and demonstrate how it can be used to enable flexible experimentation with different search-based inference-time strategies in AI agents. The framework provides a clean way to experiment with strategies such as best-of-N sampling, beam search, and Monte Carlo Tree Search (MCTS). Three case studies are presented, showcasing the advantages of ENCOMPASS in enhancing the reliability and performance of LLM-based agents.", "questions": "How does the proposed framework compares against existing agent frameworks on standard agent benchmarks?", "limitations": "The token consumption comparison of building similar agents using the proposed agent framework and existing ones are not analyzed.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The paper is clearly written and the programming framework is carefully designed and presented in detail.\n2. The proposed framework could potentially benefit future research on LLM Agents.\n3. The authors provide clear showcases of how the proposed framework can facilitate research on test-time strategies for LLM Agents.\n\nWeaknesses:\n1. The novelty and technical contribution of the paper is limited, it in general looks more suitable for a technical report for an open-source codebase, but may not suits the scope of academic conferences very well.\n2. There lacks quantitative experiments on agent benchmarks such as GAIA/HLE/BrowseComp/etc., therefore, it is unclear if the proposed framework can achieve similar or higher empirical performance compared to existing agent frameworks. It is also unclear whether and how much test-time strategies, which can be easily implemented using the framework, actually works.", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Weakness 1, novelty and technical contribution\n\nEnCompass is novel in a couple of ways.\n* EnCompass is, as far as we know, the first (and so far only) inference-time and search framework for agents.\n* Conceptually, we introduced a unifying framework of common inference-time strategies as special cases of search over nondeterministic execution paths, and this conceptual framework was implemented as an actual programming framework. Programming frameworks that unify and simplify various aspects of agent programming regularly appear at top ML conferences – examples include:\n  * DSPy at ICLR 2024 (spotlight): https://iclr.cc/virtual/2024/poster/17642\n  * AutoGen at COLM 2024: https://openreview.net/forum?id=BAakY1hNKS\n* We applied the idea of angelic nondeterminism — a programming construct typically limited to work on the early days of symbolic automated reasoning — to the actual programming of modern LLM agents. The specific version of angelic nondeterminism — *probabilistic* angelic nondeterminism — is also novel.\n\n## Response to Weakness 2 and Question 1, quantitative experiments and comparisons on agent benchmarks\n\nIt is widely reported that test-time inference strategies can improve LLM agents [3, 4, 5, 6, 7, 8, 9, 10, 11, 16, 17, 18]. Common examples include Best-of-N, refinement, MCTS, and more, all of which are known to work. Our EnCompass framework enables an elegant way to specify such strategies so that implementation is easy and streamlined. Our three case studies demonstrate this.\n\nTo address the comment on lack of additional benchmarks, we conducted an additional set of evaluations on BIG-Bench Hard, and integrated EnCompass with Chain-of-Code (CoC) [a], which is a SOTA method on that benchmark.  Our version of Chain-of-Code (CoC) uses an LLM to write agent code where undefined function calls are emulated by LLMs. EnCompass then compiles the LLM-written code so that we can easily search over different combinations of LLM emulation outputs. We ran parallel beam search with beam width 2 and branching factor 2. Search branches that errored out are killed, and for those that survive, we took the majority vote answer. We use 3-shot prompting as in the original paper, and Qwen3-14b to match the discontinued text-davinci-003 which the original authors used. The results are shown below -- CoC+EnCompass achieves the best performance.\n\n\n| | Direct (reported) | Direct (reproduced) | CoT (reported) | CoT (reproduced) | CoC (reported) | CoC (reproduced) | CoC+EnCompass (ours) |\n| --- | --- | --- | --- | --- | --- | --- | --- |\n| All | 55 | 54 | 72 | 79 | 84 | 84 | **87** |\n| No LLM emulation needed* | 44 | 46 | 72 | 81 | 94 | **96** | **96** | \n| Need LLM emulation | 66 | 63 | 72 | 76 | 72 | 72 | **77** |\n\n*These are the tasks where the LLM-generated code is a regular *deterministic* Python program where search over nondeterministic execution paths, by definition, would not help.\n\nWe accomplished this without the need to prompt the LLM to write code that implements parallelized search by itself. Instead, we simply took the original code it generated, modified it to add branchpoints, and used EnCompass to compile it and apply beam search. This further demonstrates the ease with which EnCompass can be applied to existing agents to improve performance via search.\n\nNote that our evaluations do not compare EnCompass with other frameworks because EnCompass is, to the best of our knowledge, the *only* inference-time strategy and search framework (see Related Work section). Another framework that is the only framework of its kind is DSPy (ICLR 2024 spotlight). Indeed, the evaluations in the DSPy paper do not compare with other frameworks, but instead focus on showcasing the result of prompt optimization. Similarly, our main evaluation of EnCompass focuses on showcasing how easy it is to use EnCompass to implement and experiment with different inference-time strategies and search algorithms on top of any underlying agent workflow.\n\nOur integration of EnCompass with CoC highlights that EnCompass is designed to be orthogonal to existing agents/agent frameworks so that it can be flexibly used in conjunction with them to achieve the benefits of both. For example, you can also use both EnCompass to implement inference-time strategies and DSPy for prompt optimization in your agent and get the benefits from both the easily-implemented inference-time strategies and the prompt optimization. If you had to choose between EnCompass and DSPy then you'd want to compare them, but you can just use both.\n\nFinally, we note that benchmarks that require an LLM-in-control agent architecture are currently not in the scope of EnCompass. For example, GAIA, HLE and BrowseComp are all designed to evaluate LLMs interacting with an environment via tools (e.g., web search), and are thus out of scope. Nevertheless, an interesting direction for future work is to extend EnCompass to agents that are more \"LLM-in-control\". For example, an LLM controller could write EnCompass agent code that can itself call LLMs or spawn LLM-written EnCompass subagents. Our experiments on Chain-of-Code above can be seen as preliminary experiments in that direction, and the results have been promising, but a full exploration requires a separate project.\n\n[a] Li, Chengshu, et al. \"Chain of code: Reasoning with a language model-augmented code emulator.\" arXiv preprint arXiv:2312.04474 (2023).\n\n## Limitation 1, token consumption comparison\n\nIn all of our case studies, we list the API costs involved in each experiment to compare the scaling laws of different inference-time strategies. Since cost is determined by the agent you build and not by the framework(s) used to build it†, we do not compare the cost of an EnCompass agent vs. the cost of an equivalent agent without EnCompass — they will have the exact same token consumption. Instead, we focus on showcasing how EnCompass is used to implement different inference-time strategies, and to compare their scaling laws we have reported cost in our case studies.\n\n\n†DSPy may be an exception since it can be used to optimize prompts to change the token consumption."}, {"review_id": "5mDyg4ABsI", "reviewer": "Reviewer_qd97", "summary": "This paper addresses interence-time scaling issues for agent\nprogramming contexts that rely specifically on \"program-in-control”\nstyle agents in which the workflow for the agents is specified in code\nand LLMs used to solve each subtask.  Borrowing from work in\nprobabilistic programming the framework, called EnCompass, relies on a\nprogamming model that separates the workflow logic from the\ninference-time (search) strategy.  EnCompass allows programmers to\neasily experiment with different inference-time approaches by defining\na set of core primitives via a python function decorator. The\nprimitives can then be invoked in the workflow code to invoke specific\ninference-time scaling strategies.", "questions": "1. Are there references to show the rise in developing\n\"program-in-control\" agent-based systems?  This would help to\nmotivate the need for EnCompass.\n\n2. Do we know that programmers aren't already using EnCompass-style\napproaches when developing agent-based LLM systems?\n\n3. What is the definition of \"angelic\" nondeterminism\nvs. nondeterminism?\n\n4. In term of the limitations, what type of inference-time scaling\nstrategies would NOT benefit from EnCompass?  Can EnCompass be used\nfor workflows that combine program-in-control and LLM-in-control\napproaches, or do these not really occur?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. The approach makes it easy for programmers of (program-in-control)\nagent-based systems to experiment with (and share code for) different\ninference-time search strategies rather than coding those strategies\ndirectly into the agent workflow code.  This is nice. It would\npotentially allow more complex tasks to be solved reliably using\nagent-based deep-learning approaches.\n\n2. Examples are provided to show how multiple standard inference-time\nsearch strategies would be implemented.  An evaluation using three\ncase studies summarizes the code differences with and without\nEnCompass; results show that EnCompass pretty significantly simplifies\nthe code.\n\n3. EnCompass can be used in conjunction with existing LLM prompting\nand tool use frameworks like LangChain.\n\n\nWeaknesses\n\n1. It isn't clear that the programming solution provided isn't already\nin use by folks building agent-based LLM systems.\n\n2. The limitations of EnCompass are not thoroughly discussed.", "was_revised": true, "final_justification": "No unresolved issues for me.  The rebuttal together with the other reviews (and their rebuttals) addressed my concerns.", "rebuttal": "We appreciate the reviewer for their time and effort reviewing our paper. We address your concerns and questions below.\n\n## Weakness 1 and Question 2, does the solution already exist?\n\nTo the best of our knowledge, no openly published agent framework compiles an agent workflow to a search space object to enable abstractly specifying inference-time search strategies.  It is certainly hard to say what existing programming solutions are being used in proprietary frameworks, but we feel that speculation falls outside the purview of the NeurIPS review process (consistent with the NeurIPS call-for-papers policy).\n\n## Weakness 2, need more discussion of limitations\n\nHere is a more thorough discussion of the limitations of EnCompass:\n* EnCompass is most useful for “program-in-control” and “LLM+program-in-control” agents where there’s a program (written by a human or LLM) that defines the agent workflow. It is not as useful for “LLM-in-control” agents where the agent is an LLM outputting actions to act in an environment. However, “LLM+program-in-control” could be considered more expressive/general than “LLM-in-control” agents and has seen increasing interest lately (see our response to Question 1 below).\n* At the implementation level, because EnCompass uses a decorator that reads the function’s source code and modifies its behavior (supporting additional primitives like `branchpoint()`), it may not be compatible with other decorators that read the function’s source code and assumes regular Python. This is not currently a practical issue since it is rare for decorators to read and rely on the function's source code. Neither is this a fundamental limitation, since it can be addressed with a more feature-rich transpiler that can reconcile decorators.\n\n\n## Question 1, popularity of \"program-in-control\" style agents\n\nThere has been continued interest in “program-in-control” style agents like Hypothesis Search [16], AlphaTrans [17], Self-Discover [18], Syzygy [a], and Parsel [b]. As hand-designed workflows, they often target more specific tasks (e.g., AlphaTrans and Syzygy are code translation agents), but these also include generalists (Hypothesis Search for inductive reasoning, Parsel for coding, and Self-Discover for general reasoning). Agents for specific large-scale tasks — such as AlphaTrans and Syzygy, both for translating entire code repositories — are often \"program-in-control\" since, at such a scale, having the skeleton of the agent workflow be programmatically defined is important for structuring the workflow and ensuring it follows a well-defined plan.\n\nA few recent works use a hybrid “LLM+program-in-control” approach, where LLMs write agent code (ADAS [33], GodelAgent [c], Chain-of-Code [d]), combining the benefits of programming and natural language. EnCompass continues to be helpful in this situation since it makes it easier for LLMs to write agents with sophisticated inference-time strategies. We demonstrate in recent experiments we ran applying EnCompass to Chain-of-Code – see our response to Weakness 2 of Reviewer fzrw.\n\n[a] Shetty, Manish, et al. \"Syzygy: Dual code-test C to (safe) Rust translation using llms and dynamic analysis.\" arXiv preprint arXiv:2412.14234 (2024).\n\n[b] Zelikman, Eric, et al. \"Parsel🐍: Algorithmic Reasoning with Language Models by Composing Decompositions.\" Advances in Neural Information Processing Systems 36 (2023): 31466-31523.\n\n[c] Yin, Xunjian, et al. \"Godel agent: A self-referential agent framework for recursive self-improvement.\" arXiv preprint arXiv:2410.04444 (2024).\n\n[d] Li, Chengshu, et al. \"Chain of code: Reasoning with a language model-augmented code emulator.\" arXiv preprint arXiv:2312.04474 (2023).\n\n## Question 3, angelic nondeterminism vs. nondeterminism\n\nNondeterminism is the general concept where the execution of a program has multiple available paths. A program state is not always followed by a unique next program state; instead, potentially multiple next program states are possible. \"Angelic\" nondeterminism refers to ways of executing a nondeterministic program where execution paths that lead to \"better\" outcomes are preferred and chosen. For example:\n\n* In nondeterministic programs that solve decision problems, the output \"yes\" is preferred to the output \"no\", so if there exists an execution path that leads to the output \"yes\", then that execution path will be taken. (These nondeterministic deciders are used to define complexity classes like NP.)\n* In implementations of the amb operator (found in some Lisp dialects and other languages), amb nondeterministically chooses from a set of values, where the actual choices made are those that satisfy constraints or assertions later in the program. The \"good\" execution path that gets chosen (if it exists) is the one where all constraints are satisfied.\n\nThe opposite of \"angelic\" nondeterminism is \"demonic\" nondeterminism, where the worst possible choices will be made (from the perspective of achieving the desired outcome). Probabilistic programs represent another form of nondeterminism, where execution paths are chosen according to specified probability distributions.\n\nImplementation of angelic nondeterminism necessarily involves searching across different execution paths to find those that satisfy the desired criteria.\n\n## Question 4, limitations?\n\nTo your first question, inference-time strategies that are designed to be entangled with the agent workflow benefit less from EnCompass. Suppose one designs a complex agent with inference-time strategies that are highly specific to the underlying agent workflow and dependent on runtime details specific to this agent. An example could be a code translation agent that does refinement for errors of a certain kind (e.g. compilation errors) but sampling for other errors (e.g. runtime errors), has a very specific backtracking strategy (e.g. if the last 3 translated methods failed, then backtrack to the previous file), etc. Then there isn't a general search strategy like \"beam search\" or \"best-first search\" that replicates such specific inference-time strategies, so EnCompass is not applicable in this situation.\n\nHowever, it has been on our to-do list to address this by allowing communication between the underlying agent workflow and the search process (see our response to Weakness 1 of Reviewer CQ3F). Then we can define a custom search process that receives messages from the agent on, e.g., which branchpoint it wants to backtrack to, and the search process backtracks to that branchpoint. Here, we continue to see the benefits of separating search from the underlying workflow that we have discussed in the paper (306-352) while also enabling highly customized search processes that are tailored to the workflow. By making checkpoints of the agent program, EnCompass allows the search process to cleanly backtrack to any checkpoint, even if the logic of doing so depends on details of the current state of the agent process.\n\nTo your second question, one way to combine program-in-control and LLM-in-control approaches is to have an LLM write the agent program, which could call LLMs and spawn sub-agents, etc. Here, EnCompass can be used as to the programs that the LLM writes. (Also see our responses to Weakness 2 of Reviewer CQ3F and the last question of Reviewer 49qq.)"}, {"review_id": "p4tZ9mTR1y", "reviewer": "Reviewer_49qq", "summary": "EnCompass is a python-based framework for performing inference-time search on code-based agents systems. The goal of EnCompass is enable users to easily implement different search algorithms without having to change many of the underlying details. EnCompass frames different inference time strategies as a search over different execution paths of a non-deterministic program, which is exactly what is done in LLM tree-based agents. Many examples are presented in the paper on how Encompass results in more straightforward and robust code for users especially when trying inference time algorithms.", "questions": "- What kind of hardware is required for EnCompass? Can someone with a consumer laptop run it using a package like Ollama? \n\n- Is there a way to visualize or trace what is happening as the search is happening so the user knows what is going on? \n\n- While this is beyond the scope of the paper, having such a framework for \"LLM-in-control\" could also be useful. Could EnCompass be extended to include that?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- Making LLM and agent systems more robust and easier otherwise use is a high impact area since many users often use unoptimized custom built implementations that vary from user to user. Easier experimentation and implementation would benefit many people in the area. (Significance)\n- Both the underlying observations about the connections between inference time algorithms and probabilistic program is novel as well as the design of the system. (Originality) \n- The many examples comparing the original implementation and the EnCompass implementation are very useful in understanding the system. (Clarity, Quality)\n- Initial results show that less code is required when using the system. (Quality)\n\nWeaknesses\n- EnCompass seems to have a high learning curve, making it hard for users to adapt initially, especially in relatively simplistic cases. (Quality)\n- It is unclear how much compute is required in general for EnCompass to run and what happens if that compute is not available. For example, if an LLM is being used locally and there is only one GPU, how is that parallelized. (Clarity)", "was_revised": true, "final_justification": "The authors addressed all of my concerns during the rebuttal including computational resources. It can be hard to estimate the learning curve of EnCompass right now but with tutorials and visualizations it seems that users could learn it easily. I think EnCompass addresses a very important issue and provides a framework for reproducible experiments which does not exist at the moment so I recommend accept.", "rebuttal": "We thank the reviewer for their time and effort. We address your comments and questions below.\n\n## Weakness 1, learning curve\n\nWhile the concept of probabilistic angelic nondeterminism (PAN) is unfamiliar to many people, it is the only concept that needs to be understood to learn EnCompass. Otherwise, the basic use of EnCompass is completely encapsulated by three commands: `branchpoint()`, `record_score()`, and `my_agent(...).search(...)`. EnCompass is fairly lightweight to use, and one can create tutorials and reference examples for common search strategies.\n\n## Weakness 2, compute and parallelization\n\nHow much compute is required and what happens when that is not available will be determined by the code that the user writes, as well as the specific search algorithm being used (which could be user-defined, or one that EnCompass provides out-of-the-box). As an example, consider the following code:\n```\n@encompass.compile\ndef run_agent()\n    branchpoint(branching=3)\n    call_llm(\"prompt 1\")  # Replace this with whatever framework/API you're using to call LLMs, e.g., LangChain, DSPy, Ollama, OpenAI API, etc.\n    branchpoint(branching=5)\n    call_llm(\"prompt 2\")  # Replace this with whatever framework/API you're using to call LLMs, e.g., LangChain, DSPy, Ollama, OpenAI API, etc.\n\nrun_agent().search(\"parallel_dfs\")\n```\nThis depth-first search will result in 3 LLM calls with \"prompt 1\" and 3 * 5 = 15 LLM calls with \"prompt 2\", with maximum parallelism (unless multithreading is disabled via the `max_workers=1` keyword argument). How much compute this requires or how multiple LLM requests get queued or dynamically batched will be determined by the framework the user uses for calling LLMs.\n\n## Question 1, hardware requirements\n\nEnCompass by itself has no dependencies. This is because the compiler uses the Python standard library `ast` for AST transformations and the search algorithms also only use Python standard libraries.\nHowever, the agent code you write may have certain requirements, e.g., if you run LLMs locally with Ollama, then you probably need a GPU, and your agent code will depend on the Ollama library:\n```\nimport ollama\n\n@encompass.compile\ndef run_agent()\n    branchpoint(branching=3)\n    response1 = ollama.generate(model=\"gemma:2b\", prompt=\"prompt 1\")\n    branchpoint(branching=5)\n    response2 = ollama.generate(model=\"gemma:2b\", prompt=\"prompt 1\")\n\nrun_agent().search(\"parallel_dfs\")\n```\nThe fact that EnCompass has no dependencies means that you can flexibly use it with any LLM framework, which is one of the strengths of EnCompass.\n\n## Question 2, visualization and tracing\n\nYes – there are a few ways to do this depending on what is being visualized/traced.\nFor tracing LLM calls/usage, there are existing libraries that do that. For example, when we ran our experiments, we used AgentOps. EnCompass also provides a primitive for recording usage of any resource via `record_costs`.\nFor recording the number of times each branchpoint is visited, EnCompass does this for named branchpoints (Appendix B.2): `func.branchpoint_step_counts` keeps track of this. (To name a branchpoint, do `branchpoint(name=<name>)`.)\nThe user can implement any custom tracing/logging/visualization about the search process by writing a wrapper around `branchpoint()`:\n```python\n@encompass.compile\ndef branchpoint_with_tracing(logger_state):\n    logger_state = log_and_visualize(logger_state)  # User-defined function to trace/log/visualize\n    branchpoint()\n    return logger_state\n```\nThen replacing every `branchpoint()` in your agent with `logger_state = searchover(branchpoint_with_tracking(logger_state))` will enable tracing/visualization.\nFor example, to visualize the entire search tree every time a new node gets created:\n```python\nclass Node:\n    def __init__(self, root=None):\n        self.children = []\n        self.root = root if root is not None else self\n    def create_child(self):\n        child = Node(root=self.root)\n        self.children.append(child)\n        return child\n    def visualize_tree(self):\n        self.root.visualize_sub_tree()\n\n@encompass.compile\ndef branchpoint_with_visualization(parent_node):\n    parent_node.visualize_tree()\n    branchpoint()\n    child_node = parent_node.create_child() if node is not None else Node()\n    child_node.visualize_tree()\n    return child_node\n\n@encompass.compile\ndef run_agent():\n    cur_node = Node()\n    cur_node = searchover(branchpoint_with_visualization(cur_node))  # used to be branchpoint()\n    # Step 1\n    ...\n    cur_node = searchover(branchpoint_with_visualization(cur_node))  # used to be branchpoint()\n    # Step 2\n    ...\n    cur_node = searchover(branchpoint_with_visualization(cur_node))  # used to be branchpoint()\n    # Step 3\n    ...\n```\nIf certain tracing capabilities (such as the one above) become a common requirement by users, we will implement them within EnCompass itself so that the user doesn't need to implement it themselves.\n\n## Question 3, extension to \"LLM-in-control\" agents\n\nIn “LLM-in-control” agents where an LLM chooses actions to take in an environment, since the interface the environment provides already makes it easy to implement search, there isn’t a need for disentangling the core agent workflow from the overlaying search strategy, which is the key offering of EnCompass. Nevertheless, it is still helpful to have a framework that provides out-of-the-box search algorithms that you can easily add to your agent, as well as a standardized interface for search algorithms so that they can be reused across different “LLM-in-control” agents.\nIndeed, EnCompass accomplishes both of these goals for “LLM-in-control” agents. Suppose your “LLM-in-control” agent has an environment `agent_env: AgentEnv` in which the LLM takes actions `action: Action`, so that a rollout looks like\n```python\nfor step in range(max_steps):\n    action = llm_decide_action(agent_env)\n    agent_env.act(action)\n```\nThen by putting this into EnCompass,\n```python\n@encompass.compile\ndef run_agent():\n    for step in range(max_steps):\n        branchpoint()\n        action = llm_decide_action(agent_env)\n        agent_env.act(action)\n        record_score(evaluate_state(agent_env))\n```\nwe now have access to a standardized interface for implementing search (Appendix B3) and can also use out-of-the-box search algorithms by writing, e.g., `run_agent().search(“beam”, beam_width=3, default_branching=3)`.\n\nMore recently, there’s been works that could be described as “LLM+program-in-control” agents (not discussed in the paper), where the LLM writes agent code which could itself call LLMs or spawn LLM subagents, etc. These agents have the flexibility of “LLM-in-control” agents combined with the benefits of programming (more functional and hence better state management, expressive control-flow structures, etc.). For these agents, the fact that there are agents/subagents defined programmatically means that the issue of entangling the underlying workflow with the overlaying search strategy will resurface, which is addressed by EnCompass. We conducted preliminary experiments in this direction – see our response to Weakness 2 of Reviewer fzrw."}, {"review_id": "O2ePcHA2rA", "reviewer": "Reviewer_CQ3F", "summary": "The paper identifies gap for a framework for agent inference-time search strategies. The key bottleneck identified is not having a clean abstraction/separation between core agent-workflow logic, and search logic. So the paper proposes to separate the expression of the core workflow of the agent and inference-time strategies. The key insight highlighted by the paper is that inference-time strategies can be viewed as search over different execution paths of the non deterministic program. With this insight, the paper presents Encompass, a framework allowing the user to express locations of non-determinism in code using a special annotation and then compiling the annotated program into a search space object. Overall, the paper contributes the probabilistic angelic nondeterminism (PAN) programming model along with Encompass, a python library implementation, and demonstrate case studies using encompass.", "questions": "Can the authors address the 2 main points I raised in the strengths and weaknesses section above?\n\nI am also curious to learn about the following (mostly minor) points:\n1. Could you explain if Encompass works in a multithreaded environment? Specifically, can the refine example in section 3.2 be used with multithreading?\n2. How does the system handle exceptions thrown within Encompass programs? It is not clear from the paper what `protect` does.\n3. What is the behaviour when `searchover` is not used to call sub-modules?\n4. Can Encompass search with the notion of a budget (which could be in terms of time, money, system resources, etc.)? I believe it would be especially useful if there is support for a search timeout, that can stop the search after a user-provided threshold time.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I highly appreciate the problem motivated by the paper (being able to define an agentic workflow, and separately invoking various well known as well as custom search strategies over it). The abstraction provided by the Encompass library are convenient, and will no doubt enable further research in agentic inference time search by making it convenient for researchers to experiment with different combinations of agentic-workflow architecture and applying different search algorithms over it. The paper highlights multiple case studies augmenting different base agents with different search techniques, hence establishing the flexibility of the Encompass library. Hence, I believe that Encompass is going to be a very useful contribution as a software.\n\nHowever, I have the following concerns which I request the authors to discuss:\n1. While the motivation to decouple agent-workflow and branch-selection-in-nondeterministic-execution is clear, there are situations where the branch selection decision is taken non-deterministically, but stochastically depending on the branch-local state. In such scenarios, it is desired that the agent-workflow be able to  encode a latent parameter which the search strategy can take into account. For example, using LLMs to select specialize subagent for query routing. In this scenario, while this program point is certainly a non-deterministic branchpoint, there are strong priors to select nodes. For such scenarios (which I believe are common usecases), it would strengthen the framework to discuss or support latent state communication between workflow and search modules.\n2. Increasingly, agents are being developed with control flow authority delegated to LLMs, as opposed to the \"program-in-control\" agents studied in this paper. Such systems go a step further, and enable multiple agents to collaborate, making the system highly non-deterministic, as well as making it impossible to annotate `branchpoint()` ahead of time (which is one of the core abstractions of Encompass). It would be interesting to discuss how the Encompass abstractions might be adapted or extended to handle LLM-driven agent workflows, where branchpoints cannot be statically anticipated.", "was_revised": true, "final_justification": "Author's rebuttal sufficiently addressed the concerns as noted in the comment.", "rebuttal": "We thank the reviewer for their detailed questions and comments -- we provide responses to them below.\n\n## Weakness 1, communication between underlying workflow and overlaying search process\n\nThe current version of EnCompass allows the following way to communicate between the search process and agent workflow: since the search strategy can see all variables in the state of the agent via `checkpoint._frame`, a variable can be devoted to be latent information that the search process uses to make decisions, and another variable can be devoted to messages sent to the agent from the search process\n```python\n@encompass.compile\ndef run_agent():\n    ...\n    latent_info = ...\n    branchpoint()\n    print(received_message)\n    ...\n\ncheckpoint = run_agent().start()\nlatent_info = checkpoint._frame['latent_info']\n# Make decisions based on latent_info\ncheckpoint._frame['received_message'] = \"some message\"  # Send message to agent\n```\nWe plan to implement a cleaner two-way communication feature between the agent workflow and the search process. We will mimic the syntax for communication in Python generators. Recall that Python generators use the syntax `received_value = yield sent_value` for communication, e.g.,\n```python\ndef example_generator():\n    name = yield \"Hi! What’s your name?\"\n    age = yield f\"Hi {name}! How old are you?\"\n    yield f\"{name} is {age} years old\"\n\ngen = example_generator()\nprint(next(gen))  # Prints \"Hi! What’s your name?\"\nprint(gen.send(\"Jack\"))  # Prints \"Hi Jack! How old are you?\"\nprint(gen.send(34))   # Prints \"Jack is 34 years old.\"\n```\nWe plan to implement similar syntax in EnCompass, so our example above will look like\n```python\n@encompass.compile\ndef run_agent():\n    ...\n    latent_info = ...\n    received_message = branchpoint(message=latent_info)\n    ...\n\ncheckpoint = run_agent().start()\nlatent_info = checkpoint.message\n# Make decisions based on latent_info\ncheckpoint.step(\"Some message\")  # Send message the next time step() is called\n```\n\n## Weakness 2, agents where LLMs have more control-flow authority\n\nOne way to implement LLM-driven agent workflows is to have LLM write the agent code that calls LLMs. Systems like this have control-flow in the authority of LLMs since LLMs are writing the code. (If the LLM cannot statically anticipate, e.g., the second half of the agent workflow, it can even write code that implements just the first few steps, and at the end spawn an LLM sub-agent that does the rest.) Since everything is still in code – just written by LLMs – EnCompass can be directly applied to the code to enable search. In this use case, EnCompass is used to simplify agent programming not for humans, but for LLMs.\n\nIn such a system, a solution to not being able to statically anticipate branchpoints is to replace the remainder of the workflow with a sub-agent call, and that sub-agent will now have more information about the current progress of the workflow that it can write code knowing where to place branchpoints.\n\nBut that replaces the entire second half of the workflow with a subagent call. In the case where one wants to write the entire agent workflow in code but dynamically determine where to place branchpoints, one simple solution that can be currently implemented with EnCompass is to put branchpoints inside `if` blocks:\n```python\n@encompass.compile\ndef run_agent():\n    # Step 1\n    ...\n    if should_branch_after_step1(step1_result):\n        branchpoint()\n    # Step 2\n    ...\n    if should_branch_after_step2(step1_result, step2_result):\n        branchpoint()\n    ...\n```\n\nFor a related discussion, see our response to the last question by Reviewer 49qq.\n\n## Question 1, multithreading\n\nYes! All out-of-the-box search algorithms are by default implemented with multithreading so that creating the children of a node are done in parallel. (To disable parallelism, use the keyword argument `default_max_workers=1` when calling `search()`.)\n\nHowever, multithreading can cause race conditions when different search branches mutate shared state. For the refine example in Section 3.2, enabling multithreading will likely cause all search branches to see an empty `feedbacks`, so they do fresh resamples instead of refinement. Because the logic of refinement is sequential and is incompatible with parallelism – later refinements depend on the results of previous refinements – one must disable multithreading here by passing `default_max_workers=1` in calling `search()` (which we omitted for simplicity in the code example).\n\nBesides globally turning on/off multithreading, EnCompass also lets you specify for each branchpoint whether samples of children of a node at that branchpoint can be done in parallel via a keyword argument to `branchpoint()` – by writing `branchpoint(max_workers=1)`, multithreading is turned off.\n\n## Question 2, exception handling and `protect()`\n\nAn unhandled exception that didn’t occur inside `protect` will cause the entire program to error out with that exception. While Python natively has `try: ... except: ...`, EnCompass supports two additional patterns for error handling:\n1. Putting the code inside `protect(...)`, as shown in Listing 6 of the paper. This will automatically create a retry loop that retries from the most recent branchpoint when the protected code throws the specified exception, until the exception is no longer thrown. For example, consider the following code.\n```python\n@encompass.compile\ndef run_agent():\n    sum_so_far = 0\n    for i in range(10):\n        branchpoint()\n        sum_so_far += protect(1 / random.choice([0, 1, 2]), ZeroDivisionError)\n    return sum_so_far\nrun_agent().search(\"sampling\", num_rollouts=1)\n```\nAlthough this conducts only 1 rollout, we automatically retry from the most recent branchpoint whenever there’s a ZeroDivisonError. Thus, each iteration of the loop gets retried until the randomly chosen integer is not 0, so in the end `sum_so_far` is the sum of 10 independent random variables that are each 1 or ½ with equal probability.\n2. Catching the exception and killing the current search branch with `kill_branch()`. For example,\n```python\n@encompass.compile\ndef run_agent():\n    sum_so_far = 0\n    for i in range(10):\n        branchpoint(branching=5)\n        try:\n            sum_so_far += 1 / random.choice([0, 1, 2])\n        except ZeroDivisionError:\n            kill_branch()\n        record_score(sum_so_far)\n    return sum_so_far\nrun_agent().search(\"best_first\")\n```\nHere, we conduct best-first search with branching factor 5. So we sample 5 times iteration 0 of the loop, and the sample with the highest `sum_so_far` continues on and gets 5 samples of iteration 1 of the loop, and the one that has the highest `sum_so_far` continues on and gets 5 samples of iteration 2 of the loop, so on and so forth. When we sample iteration i of the loop and it errors out, that search branch is killed, i.e., the sample is discarded. So on average we only have 3.33 samples of each iteration of the loop. It is possible that all search branches get killed before any of them reach the return statement, in which case the entire agent will error out with `AllBranchesKilledError`.\n\n## Question 3, calling sub-modules without `searchover`\n\nFor an EnCompass function `sub_agent`, `sub_agent(...)` is a `SearchSpaceWithArgs` object that provides methods such as `search(search_algo, **search_config)` (Section 2.2, Appendix B.2). Thus, without using `searchover` to run the sub-agent (`searchover(sub_agent(...))`), `sub_agent(...)` will be that `SearchSpaceWithArgs` object. This can be used to implement nested search. For example, in the code translation case study, we have both beam search at the class level, and when translating each class, we conduct nested beam search at the method level. Indeed, in the loop that iterates through all the classes, we do `sub_agent(...).search(“beam”, ...)` instead of `searchover(sub_agent(...))` (Listing 19 line 189).\n\n## Question 4, search with budget\n\nWhile current out-of-the-box search algorithms provided by EnCompass do not automatically support searching with a budget, the user can track usage of various resources and what the search tree looks like in EnCompass – see our response to Question 2 by Reviewer 49qq.\n\nTo implement global budget constraints, there are two ways that come to mind:\n* We can make use of the `Search.search_generator(self, init_program_state)` interface (`Search` is the base class for all search algorithms). This is a generator that yields a result every time a new result becomes available. So we can implement a `search_with_budget()` method that iterates through the generator until some budget has been exceeded, where budget tracking is supported via `record_costs` (Listing 7). Then it returns the best result among all the results that have been yielded so far.\n* We can follow a similar implementation to that of `early_stop_search()`. For `early_stop_search()`, there's a `Checkpoint.early_stopped_search` attribute that the search algorithm sees and stops the search process if it is `True`. Similarly, we can modify the `Checkpoint.step()` method so that if the budget has been exceeded, the returned checkpoint will have an attribute `exceeded_budget` set to True, that the search algorithm can see so that it can stop."}]

Author rebuttal:

Meta-review: This paper presents EnCompass, a framework that improves robustness and usability of LLM-based agent systems. The paper is clearly written, reduces implementation effort, and enables flexible experimentation with different agentic-workflow architectures and search strategies, which will likely facilitate further research in agentic inference-time search. While one reviewer raised concerns regarding the comparison with other methods, the authors have already addressed the main points sufficiently in the rebuttal. Therefore, I recommend acceptance.
Decision: Accept (poster)