arXiv CSopen access

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

Alexander Du

Jianjun Ou

Duke University Durham, NC, USA

Duke University Durham, NC, USA

Danyang Zhuo

Matthew Lentz

Duke University Durham, NC, USA

Duke University Durham, NC, USA

Abstract

Existing Repair

Existing Checking

Large language models are increasingly used for code generation, but many generated programs fail to compile, a prerequisite for further correctness checks such as unit tests. Existing solutions for repairing static errors are costly in both latency and token consumption. Post-hoc repair delays error detection until generation completes and commonly regenerates large regions of previously valid code. Constrained semantic decoding checks after each token, incurring pertoken overhead while limiting repair to the current token even when the root cause lies earlier. We present Hydra, a system for efficient recovery from static errors during code generation. Hydra allows checking to proceed asynchronously with generation, avoiding checker overhead when the generated code is semantically correct. In addition, it provides checkpoint-and-rollback support for targeted repair, avoiding regeneration and rechecking of valid prefixes. We retrofit the Clang C/C++ compiler to support Hydra with modest modifications. Paired with a token-efficient repair strategy, Hydra reduces latency by up to 71% and token consumption by up to 70% relative to posthoc repair on C/C++ code generation tasks that encounter static errors.

Hydra (Ours)

arXiv:2605.15238v1 [cs.SE] 14 May 2026

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

1

2

1

…

2

i

…

…

i

j

Post-hoc detects errors too late

…

n

j

2 Incremental adds additional overhead for fine-grained checks

…

1

3 Both exhibit lockstep generation and checking, increasing overall latency

…

i

…

j

or

j′

1

…

4 Localized repair may not address the actual root cause

1

2

…

i

…

1

2

… 2

i

…

…

i

…

5 Broader repair adds redundant generation and checking

j j′ i′

A

Decouples generation and checking to take advantage of overlap

B

Supports incremental checking with checkpoint-and-rollback

C

Efficiently implements decisions from policies for targeted repair

…

j′

…

n

Elapsed Time Checking

Generation (Correct)

Error (Root Cause)

Generation (Incorrect)

Error (Detected)

Time and Location

Figure 1. Inefficiencies of correct code generation approaches and overview of our approach (Hydra).

1

Introduction

Large language models (LLMs) are increasingly used for code generation, powering assistants that synthesize, complete, and revise code from natural language instructions [2, 30]. In practice, AI-generated code frequently contains errors [26], especially when using smaller models [35] for cost or privacy reasons, or when targeting underrepresented languages and APIs [6, 13]. As a result, code generation is often an iterative process in which the model must repair its output in response to feedback. Repairing errors in generated code can incur substantial costs in both latency and token consumption [3, 7, 29], with token consumption translating to dollar cost for developers using hosted inference. Although correctness spans a broad spectrum, we focus on static correctness (i.e., syntactic and semantic errors caught by the compiler), a prerequisite for

downstream functional correctness: code must compile before it can be tested. While syntactic errors are relatively rare with current models, semantic errors remain common (Tab. 1) and present a significant challenge. Producing correct code requires two capabilities: checking (detecting errors) and repair (fixing them). Existing approaches are inefficient along both axes (Fig. 1). On the checking side, post-hoc methods wait until a complete program has been generated before invoking a checker [3, 5, 7], delaying error detection even when the first error appears early in the program. Incremental methods instead check at token granularity during generation [11, 14, 17, 22, 36], but this introduces per-token overhead that is often wasted, since 1

Du et al.

Table 1. Error breakdown for one-shot, unconstrained C++ code generation. Hard is a subset of All.

the vast majority of tokens are semantically valid. Both approaches also perform checking synchronously, in lockstep with generation, making the checker a latency bottleneck. On the repair side, existing methods face a complementary tradeoff. Localized approaches, such as constrained decoding, restrict repair to resampling the current token [11, 14, 17, 22, 36]. However, the root cause of an error often lies earlier in the program (Sec. 2.4), so local fixes may not address the actual problem. Broader repair approaches, such as post-hoc regeneration, can address distant root causes but waste effort by regenerating and re-checking large regions of previously checked code. We propose to treat code generation as a search over incrementally validated prefixes, using asynchronous checking and checkpoint-and-rollback to enable efficient, targeted repair. The compiler runs asynchronously alongside code generation, validating program fragments at its natural granularity (e.g., complete statements or declarations). Generation proceeds without blocking on the checker, eliminating checker overhead when generated code is semantically correct. As the checker validates successive fragments, it creates checkpoints: snapshots of both the accepted prefix and the checker’s internal state. When an error is detected, generation rolls back to an earlier checkpoint and explores an alternative continuation, reusing prior checker analysis rather than re-checking the same prefix from scratch. Repair targets the root cause by selecting among checkpoints, guided by a user-specified policy. Realizing this approach raises three challenges. First, production compilers are designed for complete programs, not incremental prefix validation. They maintain implicit state in the call stack, provide no rollback mechanism, and report errors only at the end. Second, because the checker runs asynchronously, errors may be reported after generation has advanced well past the error site. We therefore must maintain a consistent search tree despite delayed feedback and, when necessary, retroactively invalidate previously accepted progress. Third, the space of possible rollback points is large: rolling back too little may fail to address the root cause, while rolling back too far wastes previously validated work. We address these challenges in Hydra, a runtime for efficient, correct code generation. Hydra defines a new abstraction for incremental checking that can be retrofitted onto production compilers with minimal modifications. We demonstrate this by adapting Clang [23] with 500 modified lines plus a 1400-line shim (compared to Clang’s 1.2M-line front-end). At runtime, Hydra orchestrates rollouts that bind generation requests to checker instances. As rollouts make progress or encounter errors, Hydra supports an expressive policy interface for deciding how repair should allocate search effort. We use this interface to develop a policy that aims to reduce token consumption. Hydra also supports policies explored in prior work (e.g., using model uncertainty

Syntactic

Semantic

Functional

Model

All

Hard

All

Hard

All

Hard

Qwen2.5 32B gpt-oss 120B

0.1% 0.4%

0.2% 0.6%

16.5% 6.4%

23.4% 11.1%

72.5% 37.2%

72.8% 52.1%

to guide checkpoint selection) and enables future policy designs. We evaluate Hydra on C/C++ code generation with Qwen2.5-Coder-32B [15] and gpt-oss-120B [32]. Compared to post-hoc repair, on coding tasks that encounter static errors, Hydra reduces latency and token consumption by 71%/70% for Qwen2.5-Coder-32B and by 25%/27% for gptoss-120B, while achieving near 100% static correctness. In summary, we make the following contributions: 1. We identify inefficiencies in existing checking and repair methods for LLM-based code generation by characterizing the prevalence and nature of static errors, including that the root cause of an error often lies earlier in the code. 2. We present the design of Hydra, which supports incremental static analysis with checkpoint-and-rollback and flexible policies. We retrofit the Clang C/C++ compiler to the design and develop a repair policy based on Bayesian root-cause estimation that reduces token consumption. 3. We evaluate Hydra for both C/C++ (via Clang [23]) and TypeScript (via [26]) across two model sizes. We show that Hydra reduces latency and token consumption relative to post-hoc repair and constrained semantic decoding while maintaining equivalent functional correctness.

2

Background and Motivation

2.1

Prevalence of Static Errors

Before a generated program can be evaluated for functional correctness, it must first pass static checks: the analyses a compiler performs before producing an executable. These checks fall into two categories. Syntactic checks verify that the program conforms to the grammar of the language, such as balanced delimiters, well-formed expressions, and valid keyword usage. Semantic checks verify context-dependent properties, such as whether variables are declared before use, function calls receive the correct arguments, and operations are applied to compatible operand types. A program may be syntactically valid yet still fail static checks due to semantic errors. We evaluate representative models on unconstrained C++ code generation for LiveCodeBench and LiveCodeBenchPro [16, 39], two competitive programming benchmarks.1 For each generated program, we classify failures as syntactic, semantic, or functional (i.e., unit test failure). 1 Experiment details are given in Sec. 7.

2

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

1.00

The results in Tab. 1 suggest two main conclusions. First, static errors are a meaningful bottleneck to end-to-end correctness because they must be repaired before downstream validation can begin. This effect is more pronounced for smaller models: 16.6% of outputs from the 32B model contain static errors, compared with 6.8% for the 120B model. On the subset labeled hard by the benchmark authors, these error rates rise to 23.6% and 11.7%. Second, when static errors occur, they are overwhelmingly semantic errors (≥ 94% of static failures). Therefore, purely syntactic solutions [11] are insufficient. 2.2

CDF

0.75 0.50

32B (n=130) 120B (n=54)

0.25 0.00 0.0

0.2 0.5 0.8 1.0 0.0 0.2 0.5 0.8 1.0 Normalized Error Position Normalized Repair Distance

Figure 2. Nature of static errors in generated C++ code. well as additional cost that grows with prefix length. For reference, in our evaluation setup, gpt-oss 120B requires about 7 ms per token, showing that incremental checking can become the bottleneck. Finally, language-server-based validation does not cleanly support downstream correctness checks that require an executable, since a compiler must still be invoked separately.

Existing Approaches to Repair

We classify approaches to repairing static errors into two broad categories: post-hoc and incremental. Post-hoc methods first generate a complete candidate and then invoke a checker; if the checker reports one or more errors, the model is prompted again with error feedback, and this process repeats until a candidate is accepted or a budget is exhausted (e.g., a timeout) [7]. An advantage of post-hoc methods is that they work with existing, unmodified checkers. In contrast, incremental methods validate during generation, at token or statement granularity. However, existing checkers typically analyze only complete inputs, so incremental approaches require either custom analyzers or heuristic approximations, such as learned surrogates for program analysis [36], which can introduce false positives and false negatives. Repair methods can also be categorized by the form of their output: regeneration or editing. In regeneration-based repair, the model produces a new candidate, sometimes reusing part of the previous output. In edit-based repair, the model instead produces an edit to the current candidate, typically in a difflike format. Editing can reduce output token consumption by avoiding full regeneration, but it introduces an additional interface burden: the model must both identify a suitable repair candidate and express it in the required edit format. 2.3

32B (n=157) 120B (n=65)

2.4

Nature of Static Errors

To better characterize the efficiency limitations of existing approaches, we next analyze where static errors arise in generated programs. We distinguish the position where the compiler first reports an error from the position of the (potentially earlier) root cause. For example, given a declaration int x; followed by an assignment x = “hello”;, the reported error occurs at the assignment, while the root cause could instead lie at the earlier declaration if the correct type were char*. For each generated C++ program with a syntactic or semantic error, we record the earliest compiler-reported error offset (in characters) and normalize it by the total program length, yielding a normalized error position. Thus, values near 0 correspond to errors detected near the beginning of the program. Fig. 2 (left) shows that, for both models, detected errors are distributed throughout the program. This highlights an inefficiency of post-hoc repair: even when the first static error lies well before the end of the generated program, it is not discovered until generation completes. To approximate the position of the root cause, we prompt the stronger 120B model three times to produce a minimal repair for each failing candidate. For every repair that compiles successfully, we compute the first position at which it differs from the original program. We use the maximum of these positions, corresponding to the minimal successful repair, as a proxy for the root-cause location. Based on manual examination of sampled repairs, we found this proxy to be plausible. Fig. 2 (right) plots the normalized repair distance from the reported error to the root cause, normalized by the error position. A value near 0 indicates that the root cause coincides with the reported error, whereas a value near 1 indicates that the root cause lies near the beginning of the generated prefix. We find that rollback distances are broadly distributed:

Checker Overhead

Both post-hoc and incremental repair can incur substantial checker overhead. In both cases, generation and checking proceed in lockstep: after producing a candidate or prefix, the system invokes a checker and waits for the result before proceeding. This is especially problematic for incremental methods, which require frequent checker interactions. A practical challenge is that existing tools are not designed for low-latency prefix checking. Prior work therefore commonly approximates incremental validation either by repeatedly invoking a compiler on growing prefixes [17] or by submitting updates to a language server [1, 4, 37]. As we evaluate in Sec. 7.3, repeated compiler invocation is expensive, incurring about 419 ms per update because it processes the entire prefix from scratch. Language servers reduce this cost through preamble caching, but still incur a nontrivial fixed overhead of roughly 11 ms per update, as 3

Du et al. Rollout A

Hydra Rollout Manager

{

Active Rollouts (Gen, Chk)

}

Search Tree State ∅ P P P P E C

P

P

C

Policy Engine

Reqs

Inference Server

Tokens

(e.g., vLLM)

Delta

Shim

Events

State Actions

Checker (e.g., Clang)

Policy

Rollout B from A (L21)

1#include <iostream> 22 - 3 Lines Hidden 23 5int fruit(const string& s, int n) { 24 1 6 istringstream iss(s); 25 7 string tok; 26 8 iss >> tok; 27 9 size_t pos = tok.find("apples"); 28 10 if (pos != string::npos) { 29 1 11 30 iss.ignore(pos + 6); 12 int apples; 13 iss >> apples; 14 } 2 15 iss >> tok; 16 pos = token.find("oranges"); Pol 17 if (pos != string::npos) { PE 3 Lines Hidden 21 } 22 int mangoes = n-apples-oranges;

Use of undeclared identifier 'apples'

Rollout C from A (L6)

else { int oranges; iss >> oranges; pos = token.find("oranges"); if (pos != string::npos) { iss.ignore(pos + 8); Pol } PE } int mangoes = n-apples-oranges;

7 8 9

string temp; int apples, oranges; iss >> apples >> temp >> temp >> oranges; 10 return n-apples-oranges; 11}<EOS>

A

∅ …

Use of undeclared identifier 'apples'

1 5

… 11

Rollout A

Rollout B

Rollout C

…

Gen

Gen (L22+)

Gen (L7+)

2 14

Chk 1

Chk (A.2) 1

Chk (A.1)

…

Time

2

C

6

21 22

B …

29 1 30

Figure 3. Left: Overview of Hydra’s architecture. Right: Hydra’s workflow on an example benchmark problem, from the perspective of policy decisions and execution. Walkthrough. To illustrate the workflow, consider a simple, illustrative benchmark problem from HumanEvalPack [25] that asks for a function taking a string of the form “%d apples and %d oranges”, along with a number 𝑛 denoting the total fruit count, and returning the remaining fruit after subtracting the apples and oranges mentioned in the string. Hydra spawns a rollout (A), consisting of a new generation request and checker session. As the model generates tokens, Hydra streams them to the checker through the shim, allowing generation and analysis to overlap. As the checker advances, the shim reports progress events at various boundaries (e.g., statements) and periodically checkpoints checker state. In this example, we treat each line as an event and observe two checkpoints (1 and 2). Eventually, the checker detects an error at Line 22: the code refers to the identifier apples, but that identifier is declared inside an if block at Line 12 and is therefore out of scope. Upon receiving this error, Hydra invokes the user-specified policy, which operates over the full search tree constructed so far together with the current set of active rollouts (one, in this example). In this example, the policy first attempts a local repair by spawning a new rollout that resumes near the error site, after Line 21 from Rollout A. On the checker side, Hydra resumes from the nearest prior checkpoint, checkpoint 2 of Rollout A (ChkA.2), which lies after Line 14, and resubmits Lines 15–21 to reconstruct the desired checker state before analyzing newly generated tokens (Lines 22–30 of Rollout B). This local attempt also fails, suggesting that the true source of the error lies earlier in the code. The policy therefore spawns a new rollout that resumes after Line 6 of Rollout A; this continuation is ultimately accepted when the checker reaches end-of-stream (EOS). The bottom right of Fig. 3 shows the resulting execution trace across rollouts along with the final search-tree state.

roughly 20–40% of cases can be resolved locally, but 30–40% require backtracking at least halfway from the reported error. This suggests that restarting generation from scratch is often unnecessary, but that effective repair still requires searching over a broad range of restart points rather than making only local edits at the point of detection.

3

Overview

The observations in the previous section motivate three design requirements for Hydra. First, repair must be targeted rather than purely local, since the root cause of an error often lies far from the point of detection. Second, efficient repair requires incremental checking in a form that is compatible with existing checkers while reducing the cost of re-checking valid prefixes. Third, repair induces a rich search space over possible rollback points and continuations, which calls for an expressive policy interface. Fig. 3 presents an overview of the Hydra architecture (left) together with an example execution trace on a benchmark problem (right). Hydra consists of two main components: the rollout manager and the policy engine. The rollout manager interacts with the inference server to submit generation requests and receive token-by-token output via asynchronous streaming. It also interacts with checker sessions through a shim that provides a uniform interface for submitting incremental updates (deltas), receiving progress, error, and checkpoint events, and resuming from checkpoints. A rollout binds a generation request to a checker session. Multiple rollouts may be active concurrently, enabling parallel exploration of the repair search space. As events arrive, the rollout manager incrementally constructs a search tree state that records events across rollouts. When the rollout manager receives an error event, it invokes the policy engine with the current system state, including the active rollouts and the search tree. The policy then decides the next actions, such as spawning new rollouts, terminating active ones, or pruning search-tree and checkpoint state. 4

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

Table 2. Hydra API. 𝐻 = Hydra, 𝐶𝐴 = Checker (Active Session), 𝐶𝐶 = Checker (Checkpoint Session), and P = Policy. Dir.

Element

Description

𝐻 → 𝐶𝐴 𝐶𝐴 → 𝐻

submit(delta) init(id,pid) progress(off,cat [,meta]) error(off,cat,diag [,meta]) resume(chan) chkpt(off,id,pid)

Submit an incremental code fragment to an active checker. Report an active checker, together with its ID and parent ID. Report acceptance up to an offset tied to a semantic boundary (optional metadata). Report error at an offset, with category and diagnostic information (optional metadata). Create an active session from a checkpoint with a given communication channel. Report a checker checkpoint at an offset, together with its ID and parent ID.

on_node(node,state) spawn(start,prompt,params) kill(id) prune(target)

Notify the policy of an event-tree node and the current search state. Start a rollout from a progress node with the given prompt and sampling parameters. Terminate an active rollout by ID. Prune an event-tree node or attached checkpoint.

𝐻 → 𝐶𝐶 𝐶𝐶 → 𝐻 𝐻 →𝑃 𝑃 →𝐻

4

Design

4.1

Checker Interface and Management

might be “undeclared variable”, while the diagnostic identifies the offending symbol via “use of undeclared identifier x”. Both event types may additionally carry checker-specific metadata, without a fixed schema, such as suggested repairs or other semantic annotations. As an active session advances, it may also create checkpoints. These checkpoints support efficient, targeted repair by reducing the need to reanalyze known-valid prefixes from scratch. As the session reaches new progress boundaries, it may materialize a checkpoint session according to the checkpointing policy. For example, in our C/C++ implementation, this policy places a checkpoint after processing #include directives, since reparsing the preamble is expensive, and then creates additional checkpoints at a fixed interval thereafter. A checkpoint session opens a new channel to Hydra and reports itself via a chkpt message, identifying its session ID, its parent active session, and the offset it has analyzed up to. Checkpoint sessions are otherwise dormant. To continue from a checkpoint, Hydra sends a resume message to the checkpoint session, which creates a new active session bound to the supplied communication channel. That active session then reports itself with an init message, identifying its session ID and parent checkpoint.

Hydra must interoperate with a wide range of checkers, varying both by language (e.g., C/C++ and TypeScript) and by analysis (e.g., syntactic and semantic). Most such tools do not natively support prefix-level validation or branching from previously analyzed prefixes. Hydra therefore introduces the checker abstraction summarized in the top portion of Tab. 2. This abstraction provides the functionality needed for incremental analysis and rollback while requiring only a lightweight shim over an existing checker instead of a bespoke analyzer. We describe our Clang shim in Sec. 5. Hydra manages two kinds of sessions: active sessions and checkpoint sessions. An active session consumes incremental input and emits analysis events. A checkpoint session preserves checker state for a previously analyzed prefix so that later repairs can resume without reprocessing that prefix from scratch. Checkpoints are created from active sessions, and active sessions are resumed from checkpoints. Each session communicates with Hydra over an independent channel, such as a UNIX domain socket. For a fresh generation request, Hydra creates an initial active session by launching a new instance of the checker program. Hydra streams generator output to the active session via submit. The active session responds asynchronously with two event types: progress and error. Both event types include a byte offset, which serves as the synchronization boundary between generation and checking. This offsetbased design is important because Hydra allows generation and checking to proceed asynchronously, avoiding the overhead of lockstep execution. A progress event reports that the checker has advanced through the prefix up to a semantic boundary of category cat. In our C/C++ implementation, such boundaries include completed constructs such as for_stmt and struct_or_ union_def. An error event reports that the checker has rejected the prefix, together with a coarse error category cat and a diagnostic string diag. For example, the category

4.2

Managing Rollouts and Search State

Hydra organizes checker events into a search tree. Each node corresponds to a checker event at a specific offset and stores both the event metadata and the generated prefix up to that point. The tree is rooted at an initial node representing the empty prefix. Each rollout traces a path from its spawn node to its current leaf. A node may have multiple children, corresponding to rollouts that share a prefix and later diverge. When Hydra receives a progress event for a rollout, it appends a new node to that rollout’s path. Error events require additional care. Some errors are only detected after later context becomes available, even though their source lies earlier in the prefix. For example, certain struct or class member declaration errors may surface only once the enclosing type definition is complete. As a result, an error event 5

Du et al.

may retroactively invalidate one or more progress nodes previously emitted by the same rollout. In such cases, Hydra truncates the invalid suffix, removes it from the tree, and inserts the error node at the reported offset. When Hydra receives a chkpt message, it attaches a checkpoint handle to the corresponding progress node at the same offset. Progress nodes remain distinct even if multiple rollouts reach identical prefixes, because they represent different event histories. Checkpoint sessions, however, are deduplicated by the hash of the accepted prefix up to their offset. Hydra manages checkpoint lifetimes through reference counting and destroys a checkpoint session once all progress nodes that refer to it have been pruned. 4.3

inference engine to reuse computation for the shared prefix. This design also constrains repair-prompt construction: feedback should be placed late in the prompt so that the request preserves the longest possible shared prefix. In our implementation, feedback is introduced as a comment at the end of the reused code prefix, immediately before the model generates the repaired continuation. Checker-side rollback. On the checker side, Hydra locates the nearest ancestor of the start node with an attached checker checkpoint. If the start node itself is not checkpointed, Hydra resumes from that ancestor checkpoint and resubmits the generated tokens between the ancestor node and the start node to reconstruct the desired checker state. Thus, every progress node is a potential logical restart point, even when checker checkpoints are sparse. Keeping more checker checkpoints lowers reconstruction cost but uses more memory. Hydra exposes this tradeoff to the policy layer. Overall, Hydra supports a rich policy space. In this work, we instantiate this interface with a policy aimed at reducing token consumption (Sec. 6) and with adaptations of repair strategies from prior work [17] (Appendix E). Together, these case studies exercise the main capabilities of the interface.

Policy Support

Policy interface. The policy interface appears in the bottom portion of Tab. 2. Each policy implements a single callback, on_node, which Hydra invokes whenever a new checker event creates a tree node. The policy receives the new node (node) together with a read-only view of the current search state (state). This state includes the event tree (.tree), the set of active rollouts (.active), and the rollout that produced the event (.cur). This interface allows the policy to reason both locally and globally. For example, it may inspect ancestor relationships in the tree, detect repeated failures beneath a common valid prefix, or compare progress across multiple active rollouts.

5 Retrofitting a Real-World Compiler as an Incremental Checker Hydra requires checkers to operate incrementally, expose semantically meaningful progress, and support rollback to prior states. Production compilers, however, are typically designed for fully materialized programs, maintain substantial implicit analysis state, and provide no direct rollback mechanism. Prior work has often adapted existing compilers using brittle heuristics, such as synthesizing suffixes to complete incomplete prefixes (e.g., closing braces or inserting return statements), but such techniques can introduce both false positives and false negatives in correctness checking [17]. At the other extreme, some prior work builds custom incremental analyzers from scratch [22, 26, 34], but these often support only restricted language subsets and therefore constrain generation unnecessarily. To demonstrate that Hydra’s checker abstraction can be realized with a production compiler, we retrofit Clang [23] to support Hydra’s interface. C and C++ are both important systems languages and particularly challenging targets for LLM code generation. Adapting Clang to the Hydra checker interface required roughly 500 lines of compiler modifications, while our Hydra shim adds another 1,400 lines of code. The main changes are: (1) a streaming input abstraction, (2) process-level checkpoints, and (3) progress and checkpoint callbacks at safe parser boundaries. These modifications are largely confined to a thin adaptation layer, together with a few changes that enforce safe, blocking access to the input

Policy actions. In response, the policy may issue zero or more actions. The primary action is spawn, which starts a new rollout from a chosen progress node using a specified prompt and decoding parameters. A policy may issue multiple spawn actions in response to a single on_node, thereby requesting multiple concurrent rollouts; Hydra attempts to execute these in parallel subject to underlying resource constraints. This allows policies to express behaviors such as local rollback, deeper rollback after repeated failures, parallel exploration of several candidate repair sites, prompt variation in response to particular error patterns, or requests for generator-side metadata such as log probabilities. Policies may also issue kill to terminate an active rollout while retaining its search state for future repair, and prune to discard a subtree and release associated resources, including checkpoints. These actions allow policies to enforce resource budgets such as limits on memory, checkpoint count, or active parallelism. Generator-side rollback. To realize a spawn, Hydra must reconstruct both the generator context and the checker state associated with the chosen start node. On the generator side, Hydra does not explicitly checkpoint model state, such as KV-cache contents. Instead, it constructs the repair request from the original prompt and the generated prefix stored at the chosen start node, relying on prefix caching in the 6

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

Checkpoints (§5.2) Hydra

Clang Shim

CA100

chkpt error resume init

1 2 3

fork CC101

~~~~~~

from Hydra. Later, 𝐶𝐴100 may produce an error event. If the policy chooses to repair from an earlier point for which 𝐶𝐶101 is the nearest preceding checkpoint, Hydra sends a resume message to 𝐶𝐶101 containing a file descriptor for the new channel. In response, 𝐶𝐶101 invokes fork() again: the parent remains a reusable checkpoint, while the child becomes a new active session, 𝐶𝐴102 , that continues execution from the saved state. Overall, this design avoids invasive changes to Clang’s control flow and suggests a general strategy for adapting other recursive checkers whose state is difficult to serialize directly. Since fork() leverages copy-on-write, this mechanism is efficient in both latency and memory.

Synchronization (§5.3) ExpectAndConsumeSemi(diag::err…); R = handleExprStmt(Res, SubStmtCtx);

P3 L3 P2 L2 P1 L1

Before …

x

After

fork CA102

~~~~~~

S

=

y

/

z

;

r

e

t

…

PS, LS

R = handleExprStmt(Res, SubStmtCtx); if (Tok.is(semi) && !R.isInvalid()) maybeEmitBoundary("expr_stmt"); ExpectAndConsumeSemi(diag::err…);

Figure 4. Details on adapting Clang for Hydra. Left: forkbased checkpointing. Right: reordering parser actions to maintain synchronization at checkpoints.

5.3

stream. Clang’s existing parsing, semantic analysis, and diagnostic machinery are otherwise almost entirely unchanged. 5.1

Streaming Input

Clang is not designed to parse or analyze incomplete programs. Given an arbitrary prefix, it will often report a syntax error simply because a declaration, statement, or scope has not yet been completed. We therefore modify how Clang receives input while hiding the streaming nature of that input from the rest of the compiler. Concretely, we introduce a new StreamingBuffer that inherits from LLVM’s MemoryBuffer, the abstraction Clang ordinarily uses for mmap-backed files. Our Hydra shim appends generated code to this buffer as it arrives. Clang’s lexer assumes the underlying buffer is fully resident and frequently accesses it through direct pointer arithmetic; under streaming input, this assumption no longer holds. To address this, we replace direct buffer accesses with indirect read methods that wait for additional input when necessary. We also disable a small number of lexer optimizations (e.g., ASCII and UTF-8 fast paths) that assume the entire input is already resident. 5.2

Synchronization

Clang’s parser alternates between consuming tokens from the lexer and invoking semantic-analysis callbacks once a syntactic unit has been recognized. For Hydra, we want to report progress and potentially checkpoint after semantic analysis of a unit has completed, but before the parser has irreversibly consumed future input. Checkpointing too early would preserve incomplete semantic state, while checkpointing too late would break synchronization between Hydra’s view of the accepted prefix and the compiler’s internal state. In several places, Clang’s parser consumes a lookahead token before performing semantic actions on the current construct, leaving no safe checkpoint location. This ordering is not required for correctness; it is simply an implementation choice. We therefore reorder token consumption to occur after the relevant semantic analysis. Fig. 4 (right) shows one such example, with the original logic at the top and our modified version below. Original potential checkpoint locations (1, 2, 3) do not preserve synchronized parser and lexer state. After reordering, the new location (S) does.

6

Policy Case Study

Hydra supports expressive policies that manage repair using the API in Sec. 4. In this section, we develop two policies aimed at reducing token consumption while maintaining correctness.

Checkpointing

Clang uses a recursive descent parser, so much of its runtime state is implicit in the process stack rather than stored in an explicit, serializable object. Instead of attempting to extract and serialize this internal state, we use fork() to checkpoint the compiler at the process level. We illustrate this process in Fig. 4 (left). Suppose we have an active checker session with PID 100 (i.e., 𝐶𝐴100 ). While 𝐶𝐴100 emits progress events (not shown), the checkpointing strategy may decide to materialize a checkpoint, causing the shim to invoke fork(). The parent process, 𝐶𝐴100 , continues as an active session, while the child process, 𝐶𝐶101 , becomes a checkpoint session. 𝐶𝐶101 first sends a chkpt message to inform Hydra of its existence and then becomes dormant, preserving the compiler state while waiting for instructions

Preliminaries. We model the set of rollback candidates (i.e., ancestor progress nodes on the current path) available to the policy as 𝐶 = {𝑐 1 ≤ · · · ≤ 𝑐𝑚 }, ordered by position with 𝑐 1 at the start. For each newly detected error 𝑒, we posit a latent root cause 𝑟 and model the success probability of repairing from a node 𝑐 as 𝑃 (RepairSuccess | 𝑐, 𝑟 ) = 𝑞(𝑐, 𝑟 ) when 𝑐 < 𝑟 and 0 otherwise. Here, 𝑞(𝑐, 𝑟 ) captures the possibility that repair may still fail even when the candidate node lies sufficiently far before the root cause. Cost Model. We model the token cost 𝐶𝑇 (𝑐, 𝑒) of repairing an error 𝑒 from node 𝑐. As a simplifying assumption, we take the token cost of a repair attempt to be 𝐶𝑇 (𝑐, 𝑒) = 𝑒 − 𝑐 tokens. In practice, the realized cost may vary, since a rollout 7

Du et al.

Table 3. Generation efficiency in latency and output token consumption. Each entry reports values for C / C++. 32B UC1 Latency (s)

UC2

R1

120B R2

HY1

HY2

UC1

UC2

R1

R2

HY1

HY2

Mean 7.78/6.94 6.77/6.26 12.1/13.1 7.98/8.33 8.27/8.48 7.22/6.80 38.0/37.4 34.5/35.6 51.5/34.8 42.2/37.0 38.6/33.3 35.0/33.1 50% 6.85/6.08 6.17/5.68 7.28/6.83 6.22/6.19 6.98/6.30 6.28/5.89 32.9/29.8 30.8/29.7 38.7/28.1 33.3/31.6 31.7/27.4 30.0/27.2 75% 9.64/8.49 8.39/7.57 11.2/11.3 8.83/8.59 10.1/9.03 8.68/8.08 54.1/55.6 48.8/54.4 72.0/49.5 63.2/54.2 56.1/47.4 50.0/47.7

Mean 0.38/0.34 0.65/0.60 0.59/0.63 0.77/0.77 0.40/0.41 0.69/0.65 5.68/5.61 5.70/5.79 7.84/5.21 7.97/5.96 5.74/5.03 5.86/5.48 # Tok. (×103 ) 50% 0.34/0.30 0.59/0.55 0.36/0.33 0.60/0.57 0.35/0.31 0.60/0.56 5.15/4.71 5.34/5.15 6.10/4.36 6.03/5.16 4.96/4.34 5.36/4.85 75% 0.47/0.42 0.81/0.73 0.55/0.54 0.86/0.80 0.49/0.45 0.84/0.76 8.15/8.45 8.09/8.82 11.0/7.56 11.5/8.46 8.30/7.23 8.25/7.85

may terminate before or after offset 𝑒, either through success or failure. We also account for token consumption caused by lag between generator and checker.

1016 tasks total. We split these into 30/70 train/test partitions stratified by difficulty, using the training split for policy tuning and the test split for all reported results. We focus on C and C++, using Clang 22.0.0 with -Werror, -Wall, and -Wextra, and a 300 s per-task timeout. All methods use the same prompt and checker configuration. To directly compare against constrained semantic decoding, we also evaluate a restricted TypeScript setting (Sec. 7.2).

Root Cause Belief. For a given error, we maintain a belief distribution over 𝑟 , initialized from empirical priors similar to those shown on the right-hand side of Fig. 2. When a repair attempt from candidate 𝑐 𝑓 fails, this evidence shifts probability mass toward root causes that lie farther from the error, i.e., earlier in the program.

Methods. We compare unconstrained generation (UC), post-hoc repair (R), and Hydra (HY), each with one- and two-threaded variants. UC1 is standard one-shot generation, while UC2 runs two threads in parallel and returns the first completed candidate. R1 is single-threaded posthoc repair, while R2 runs two repair threads in parallel and returns the first thread to produce compilable code. We evaluate both regeneration- and edit-based repair, but report only the stronger result for each model: regeneration for Qwen2.5-Coder-32B and edit for gpt-oss-120B. HY1 is our single-threaded (i.e., single-rollout) policy, which aims to reduce token consumption, and HY2 is our two-rollout policy with preemption.

TokPol: Single-Rollout Policy. Upon receiving an error event, TokPol spawns exactly one new rollout to replace the failed rollout. For each candidate node 𝑐, the policy estimates the expected token cost of rolling back to 𝑐 by combining the immediate attempt cost with the expected future cost if repair from 𝑐 also fails. It then spawns a new rollout from the candidate node with the lowest expected cost. Additional details are given in Appendix B. TokPolK: Multi-Rollout Policy. TokPolK shares the same high-level model as TokPol but manages 𝐾 concurrent rollouts. Rollback candidate node selection in TokPolK is more involved because it must account for all active rollouts and therefore reason jointly about aggregate success probability and cost. Initially, TokPolK spawns 𝐾 rollouts with elevated temperature to encourage diversity. Upon receiving an error event, TokPolK spawns a new rollout similar to TokPol; however, it may also preemptively kill other rollouts if the current rollout has made substantial forward progress and replace them with rollouts that target this newer error. Additional details are given in Appendix C.

7

Metrics. We report per-instance latency, output token consumption, static correctness, and functional correctness. Unless otherwise stated, all results are measured on the full test partition and averaged over three random seeds. Statistical significance. For each model, language, and metric, we compute per-task means over the three seeds and compare non-UC methods using paired permutation tests with Holm correction at 𝛼 = 0.05. In the main tables, bold denotes the statistical frontier, i.e., methods for which no other method is significantly better.

Evaluation

Setup. All experiments run on a single node with one NVIDIA H200 GPU using vLLM [20] as the inference server. We evaluate two models: Qwen2.5-Coder-32B [15] and gptoss-120B [32]. For gpt-oss-120B, reasoning is enabled before code generation and between repair attempts. We evaluate on a benchmark formed by merging LiveCodeBench [16] and LiveCodeBench-Pro [39]. We retain language-agnostic tasks (i.e., those with stdin/stdout tests) released after a common cutoff date of 2024-07-01, yielding

7.1

C and C++ Results

Tab. 3 summarizes end-to-end efficiency, Fig. 5 visualizes error-conditioned efficiency, and Tab. 4 reports correctness outcomes. Efficiency. Hydra substantially reduces latency and token consumption relative to post-hoc repair across both languages and both model sizes, with the largest gains on 32B given the higher prevalence of static errors. 8

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

C

1.00

C++

32B

0.75 0.50

CDF

0.25 0.000 1.00

UC1 UC2 60

20

40

40

80 120 Latency (s)

0

R1 R2 1000 2000 3000

0

20

40

HY1 HY2 60 0

1000 2000 3000

120B

0.75 0.50 0.25 0.000

0

8000 16000 24000 0 Tokens

50 100 Latency (s)

150 0

8000 16000 24000 Tokens

Figure 5. Generation efficiency in latency and output token consumption, conditioned on an initial static error (for twothreaded methods, in either thread). For readability, each plot is truncated at the 95th percentile of non-timeout values. Table 4. Correctness outcomes for C and C++ programs across model sizes. Each entry reports C/C++ percentages of generation requests.

For 32B, both repair baselines are expensive. For example, on C, HY1 reduces mean latency by 31.7% and mean token consumption by 32.2% relative to R1. For 120B, all methods incur much higher absolute latency and token consumption, largely because the model spends substantially more time and tokens on the initial attempt. Even so, on C, HY1 reduces mean latency by 25.0% and mean token consumption by 26.8% relative to R1. The smaller differences at 120B reflect the fact that static errors are less frequent, so recovery strategy matters less often. In particular, we observe this for C++, which the model handles better than C. To analyze the benefits of Hydra when repair is needed (i.e., the initial attempt encounters a static error), we filter the overall results. For single-threaded methods, we apply filtering at the level of individual task-seed pairs. For twothreaded methods, we retain a task-seed pair if at least one of the two initial threads encounters a static error. We plot full CDFs for the filtered cases in Fig. 5, including attempts that time out. For readability, we truncate the xaxis separately for each model-language panel using the maximum, across methods, of the 95th percentile computed after excluding timeouts. Relative to R1, HY1 substantially reduces both mean latency and mean token consumption on C: by 71.0% and 70.4%, respectively, for the 32B model, and by 33.3% and 35.4%, respectively, for the 120B model. On C++, Hydra continues to improve efficiency for the 120B model, reducing token consumption by 24.5% and latency by 23.8%. For both the overall and filtered results, UC1 and UC2 serve as reference points rather than repair baselines. UC1 approximates a low-token setting, while UC2 approximates a low-latency setting; however, they are not formal lower bounds. UC2 may consume fewer tokens than UC1 if its first

32B

120B

Static

Func.

Static

Func.

UC1 UC2

88.8 / 83.4 90.9 / 85.7

9.2 / 10.8 9.0 / 10.8

60.3 / 93.0 57.4 / 92.2

39.9 / 55.7 38.6 / 53.0

R1 R2 HY1 HY2

99.1 / 98.8 99.8 / 99.8 99.9 / 99.8 99.9 / 100.0

10.0 / 11.8 10.0 / 11.7 10.0 / 11.9 10.0 / 11.6

96.8 / 99.6 99.6 / 99.9 99.5 / 99.9 99.7 / 99.9

53.2 / 55.3 54.1 / 55.7 52.5 / 54.5 51.4 / 54.9

completion is short, and HY may truncate generation early and generate a shorter repaired continuation. Moreover, our evaluation uses independently sampled stochastic generations, so any method may outperform UC due to sample-tosample variation. This caveat is most visible for the 120B model in Tab. 3 and Fig. 5. Such variation is expected because GPU kernels are not strictly deterministic, and because the prompt can differ across runs when the Harmony chat template includes the current date [31]. As shown next, UC1 and UC2 achieve their efficiency by omitting repair, at the cost of substantially lower static correctness. Correctness. Tab. 4 shows that Hydra matches or improves static correctness across both models and languages. These static correctness numbers include timeouts, so they reflect not only whether a method can produce a statically valid program, but also whether it can do so within the allotted 9

Du et al.

Table 5. Generation efficiency and correctness for TypeScript. Efficiency entries report latency (s) / output token consumption (×103 ).

budget. Excluding timeouts, Hydra achieves 100% static correctness, indicating that our incremental compiler is sound with respect to Clang on all completed runs. A potential concern is that Hydra might steer generation towards easy-to-compile but functionally poor programs. Tab. 4 shows this is not the case: Hydra reaches statically correct programs more efficiently while preserving functional correctness across both models and languages.

reduces mean latency from 93.8 s to 91.7 s, improves static correctness from 86.4% to 88.1%, and improves functional correctness from 33.4% to 40.1%. The 32B model achieves better static correctness than the 120B model because it incurs fewer timeouts. These results suggest that Hydra preserves CSD’s staticcorrectness benefits while avoiding some of the functional degradation caused by token-local resampling. When the model’s preferred continuation encounters an error, CSD may divert it to an alternative that satisfies static checks but is functionally incorrect. In contrast, Hydra can roll back beyond the immediate token, allowing the model to revise a larger semantic region and explore its natural distribution more freely. One issue we observed is that both models often generated unsupported TypeScript features despite being explicitly warned in the prompt, likely because they are trained primarily on full TypeScript. This restriction favors CSD: unsupported constructs can be filtered immediately by token-level resampling, whereas Hydra must rely on the model to repair itself using checker feedback.

7.2

7.3

Method

Mean

50%

75%

Static Func.

UC CSD HY1

8.82/0.42 7.99/0.38 10.9/0.52 54.2 37.4/0.71 18.6/0.39 35.4/0.59 94.6 34.2/0.74 13.7/0.41 33.3/0.62 96.8

4.2 4.2 4.3

UC 120B CSD HY1

40.1/5.88 36.2/5.60 57.0/8.24 72.2 93.8/7.14 74.2/6.89 142/10.0 86.4 91.7/8.63 63.4/6.65 133/11.9 88.1

34.3 33.4 40.1

32B

Constrained Decoding Comparison (TypeScript)

To our knowledge, no existing constrained semantic decoding (CSD) system supports C or C++. We therefore switch to TypeScript to compare against Mündler et al. [26], adapting their incremental TypeScript checker to work with Hydra.

Ablation Studies

Checker Overhead. We compare against two practical approximations to incremental checking used in prior work: repeated compiler invocation [17] and language-server updates [1, 4, 37]. For the former, we use Clang [23]; for the latter, clangd [24]. To measure checking cost under streaming input, we reveal each program in 50-byte increments. At each step, we invoke Clang on the entire current prefix, while clangd and our checker receive only the newly revealed increment. We evaluate on 300 compilable C++ programs from the training split that are at least 1000 bytes long. All three approaches incur a substantial initial update cost, driven largely by preamble processing (e.g., #include directives). At the first measured point (50 bytes), mean latency is 410.38 ms for Clang, 342.40 ms for clangd, and 350.65 ms for our checker. After startup, averaged over prefix lengths from 100 to 1000, Clang requires 418.62 ms per update, clangd requires 11.47 ms, and our checker requires only 0.72 ms. Moreover, our per-update cost remains essentially flat as prefix length grows. In contrast, repeated Clang invocations rerun analysis on the full prefix at each step. While clangd exposes an incremental interface, it caches only the preamble and still reanalyzes most of the prefix after each update.

Integration with Hydra. The TypeScript checker supports only a narrow subset of the language, rejecting many common constructs (e.g., classes, enums). We extend the parser to support several missing constructs, including typed arrays, typed anonymous functions, constructor unions, and numeric separators. We also modify the task interface to use a function solve(input: string): string rather than stdin/stdout, and prompt the model with an explicit list of unsupported features (Appendix F). We implement a shim around the checker to support diagnostic feedback, forkbased checkpoints, and checker events; these features are enabled only for Hydra. We also re-implement the CSD sampler as a vLLM logits processor, reducing time per token by 2–3×. Both CSD and Hydra use our extended checker. Token Consumption for CSD. CSD does not consume tokens in the same way as the other methods. At each step, it requests the full logits from the model and then directly samples candidate tokens from that distribution until checker acceptance. Therefore, we report the number of logits requests as CSD’s token consumption, analogous to generating one token for the other methods.

Checkpointing. Fig. 6 (left) compares checkpointing with a no-checkpointing baseline on 100 tasks with initial errors. For the 32B model on C++, checkpointing does not provide a clear advantage. In this regime, the generator is relatively slow (179 bytes/s) compared with the checker (3150 bytes/s), and rollouts are long enough that the checker can catch up even without checkpoint reuse. However, checkpointing becomes more beneficial with slower checkers and

Results. Tab. 5 reports the results. Across both models, Hydra matches or slightly reduces CSD’s mean latency while improving static correctness. With the 32B model, Hydra reduces mean latency from 37.4 s to 34.2 s and improves static correctness from 94.6% to 96.8%. With the 120B model, Hydra 10

1.2 1.1 1.0

1.19 1.09

3B C++

1.01

32B C++

32B TS

104

Clang (C++)

at random after each error; Backwards steps backwards through prior progress nodes toward the root; and Entropy, inspired by ROCODE [17], computes top-128 token entropy from the model’s logits and chooses the progress node preceding the maximum-entropy token.2 Fig. 7 reports results on 100 C++ tasks from Qwen2.5 32B that exhibit an initial error. Our policy achieves substantially lower latency and token consumption than all three alternatives. These gains suggest that effective rollback requires more than simply choosing an earlier accepted prefix. Entropy attempts to identify promising rollback locations, but relies on a model-side uncertainty signal that is only weakly coupled to the checker-reported failure. In contrast, our policy’s prior over root-cause distance chooses useful restart points while preserving as much validated work as possible.

1.6

103 3B 102

1.8 Speedup

Speedup

1.3

Generator speed (bytes/s)

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

1.4

32B

1.2

101 1 102 103 10 104 Checker speed (bytes/s)

1.0

Figure 6. Checkpointing ablation for C++ and TS. For C++, we evaluate speedup across models (32B and 3B) and via simulations over ranges of generator and checker speeds.

1.00 CDF

0.75 0.50

8

0.25 0.00

0

Random Backwards 25 50 75 Latency (s)

0

Entropy HY1 1500 3000 4500 Tokens

Discussion

Policies. In this paper, we instantiate Hydra with TokPol, a policy that explicitly targets token consumption in addition to correctness. Although the policy model makes several simplifying assumptions (e.g., the token cost associated with a given checkpoint), our empirical results show that it already provides a strong improvement over existing baselines. In principle, these policy decisions could incorporate richer checker-side signals (e.g., conditioning rollback decisions on the error category or diagnostic metadata), model-side signals (e.g., log probabilities), or even learned approaches to guide repair. We believe that Hydra provides both an efficient runtime and an expressive policy interface to enable future work along these directions.

Figure 7. Policy ablation on C++ for Qwen2.5 32B. faster models. On the TypeScript parser, checkpointing yields a 1.19× latency speedup relative to no checkpointing. Using Qwen2.5-Coder-3B as a representative faster model (454 bytes/s), we also observe a 1.09× speedup on C++. To better understand this tradeoff, we use traces collected from the 32B/C++ setting together with the latency model described in Appendix A to estimate the effect of varying generator and checker speeds, shown in Fig. 6 (right). The experiment should be viewed as a coarse extrapolation rather than a detailed simulation. In particular, we model generator latency and checker latency via linear functions; additionally, we use a single overall rate for checker speed, even though the actual speed can vary substantially across program regions (e.g., preamble processing). Even so, it roughly matches the measured results, predicting a 1.01× speedup for 32B and a 1.06× speedup for 3B. It underestimates the 3B gain because we use 32B traces, which exhibit fewer, longer rollbacks than 3B. These results suggest that checkpointing becomes increasingly valuable as generation speed grows relative to checker speed. When the generator is faster, reconstruction latency contributes a larger share of end-to-end latency, making checkpoint reuse more beneficial. As generators become faster through better hardware or decoding techniques (e.g., speculative decoding [21]), and as checkers become heavier due to richer static analysis (e.g., memory safety), we expect checkpointing to become correspondingly more important.

Spectrum of Correctness. This paper focuses on syntactic and semantic correctness. These properties remain challenging for current models and are prerequisites for downstream validation, including unit tests, integration tests, and formal verification. Our evaluation shows that Hydra significantly improves the efficiency of reaching static correctness while maintaining functional correctness comparable to existing baselines. By reaching statically correct code faster and more cheaply, Hydra provides a better starting point for subsequent repair or validation stages that address functional errors. In future work, we plan to extend Hydra to incorporate richer downstream signals, such as unit-test failures or verifier counterexamples.

9

Related Work

Post-Hoc Repair. Post-hoc repair (PHR) handles incorrect code by generating a candidate, validating it, and revising it in response to feedback. Prior work has studied PHR from compiler diagnostics [10, 12], from unit test failures [7, 18], and as part of agentic coding pipelines [5, 38]. Although PHR can improve correctness, it is token-inefficient: regeneration

Policies. We compare our TokPol policy against three alternatives: Random selects the next restart point uniformly

2 Algorithmic details are given in Appendix E.

11

Du et al.

10

recomputes large valid regions, while patching requires the model to localize the repair and express it precisely in an edit format, which can itself be difficult [27]. Hydra is compatible with many PHR techniques, such as prompts that provide the model with compiler feedback.

Conclusion

We presented Hydra, a runtime for efficient, correct code generation that runs the checker asynchronously alongside generation and supports checkpoint-and-rollback for targeted repair. Hydra introduces a lightweight incremental checker abstraction that can be retrofitted onto production compilers with modest modifications. We demonstrate this by adapting Clang with 500 lines of compiler changes plus a 1400-line shim. By decoupling checking from generation, Hydra eliminates checker overhead when generated code is correct, while its policy interface enables flexible repair strategies when errors arise. Our evaluation on C/C++ code generation with two model sizes shows that, on tasks whose initial attempt encounters a static error, Hydra reduces latency by up to 71% and token consumption by up to 70% compared to post-hoc repair. Our code will be publicly available.

Incremental Repair. Incremental methods attempt to detect and address errors during generation, reducing wasted decoding relative to PHR. These methods differ mainly in the granularity at which feedback is applied. Constrained decoding (CD) rejects tokens that violate a target formal language at each step [14, 19, 33]. In practice, such checks can often be accelerated with precomputed vocabulary masks [11]. However, richer static properties that depend on evolving program state are generally not expressible in this form. Constrained semantic decoding (CSD) extends CD with a token-level prefix analyzer [22, 26, 28, 34], allowing token acceptance to depend on semantic properties such as type correctness [26]. However, building such analyzers is difficult, and existing systems typically target restricted language subsets. Recent work on deriving prefix analyzers from higher-level specifications [28] reduces some manual effort, but still relies on specialized formalisms and remains less practical than production compilers like Clang. Other work applies static feedback at intermediate granularity. Language servers have been used to guide generation at selected points through autocomplete suggestions [1, 4, 37]. However, these interfaces expose only partial information about program validity and do not provide the full feedback available from a compiler. ROCODE also formulates code generation as search over larger program units [17], but it relies on syntactic heuristics to identify statement boundaries and repair points. In contrast, Hydra uses progress reported by the analyzer itself, grounding recovery in the analyzer’s actual notion of accepted program state. Overall, compared with prior work, Hydra emphasizes efficient analysis and error recovery, rather than correctness alone, while capturing the full semantics of C and C++ with practical implementation effort.

Acknowledgments This work is supported in part by National Science Foundation grants CNS-2238665, CNS-2402696, and OAC-2503010, as well as by gifts from Amazon, Meta, and Google. We used generative AI tools to aid in developing our prototype implementation and polishing some sections of the text.

References [1] Lakshya Agrawal, Aditya Kanade, Navin Goyal, Shuvendu K Lahiri, and Sriram Rajamani. 2023. Monitor-guided decoding of code LMs with static analysis of repository context. In Conference on Neural Information Processing Systems (NeurIPS). https://openreview.net/for um?id=qPUbKxKvXq [2] Anthropic. 2026. Claude Code. https://claude.com/product/claudecode Accessed: 2026-04-09. [3] Zhangqian Bi, Yao Wan, Zheng Wang, Hongyu Zhang, Batu Guan, Fangxin Lu, Zili Zhang, Yulei Sui, Hai Jin, and Xuanhua Shi. 2024. Iterative refinement of project-level code context for precise code generation with compiler feedback. In Findings of the Association for Computational Linguistics: ACL 2024. doi:10.18653/v1/2024.findingsacl.138 [4] Andrew Blinn, Xiang Li, June Hyung Kim, and Cyrus Omar. 2024. Statically contextualizing large language models with typed holes. In Object-oriented Programming, Systems, Languages, and Applications (OOPSLA). doi:10.1145/3689728 [5] Islem Bouzenia, Premkumar Devanbu, and Michael Pradel. 2025. RepairAgent: an autonomous, LLM-based agent for program repair. In International Conference on Software Engineering (ICSE). doi:10.1109/ ICSE55347.2025.00157 [6] Federico Cassano, John Gouwar, Daniel Nguyen, Sydney Nguyen, Luna Phipps-Costin, Donald Pinckney, Ming-Ho Yee, Yangtian Zi, Carolyn Jane Anderson, Molly Q Feldman, et al. 2022. MultiPL-E: a scalable and extensible approach to benchmarking neural code generation. arXiv preprint arXiv:2208.08227 (2022). https://arxiv.org/abs/22 08.08227 [7] Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2024. Teaching large language models to self-debug. In International Conference on Learning Representations (ICLR). https://openreview.net/for um?id=KuPixIqPiq [8] CRIU. 2026. CRIU. https://criu.org/Main_Page Accessed: 2026-04-09.

Process-/VM-level checkpointing and rollback. A natural question is whether standard process- or VM-level checkpointing [8, 9] could replace our fork-based approach. The key difficulty is that Hydra must checkpoint the checker independently of the inference engine. Engines like vLLM maintain large GPU-resident state (e.g., KV caches) that cannot be cheaply snapshotted or stored alongside checker state. Hydra therefore requires checkpoints at well-defined synchronization boundaries (where all tokens before the checkpoint have been consumed by the checker and no tokens after it have been processed) rather than arbitrary memory snapshots.

12

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

[23] LLVM Project. 2026. Clang: a C language family frontend for LLVM. https://clang.llvm.org Accessed: 2026-04-09. [24] LLVM Project. 2026. What is clangd? https://clangd.llvm.org Accessed: 2026-04-09. [25] Niklas Muennighoff, Qian Liu, Armel Zebaze, Qinkai Zheng, Binyuan Hui, Terry Yue Zhuo, Swayam Singh, Xiangru Tang, Leandro Von Werra, and Shayne Longpre. 2023. OctoPack: instruction tuning code large language models. In Conference on Neural Information Processing Systems (NeurIPS). https://openreview.net/forum?id=CjrPqvvUXL [26] Niels Mündler, Jingxuan He, Hao Wang, Koushik Sen, Dawn Song, and Martin Vechev. 2025. Type-constrained code generation with language models. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). doi:10.1145/3729274 [27] Niels Mündler, Mark Niklas Müller, Jingxuan He, and Martin Vechev. 2024. SWT-Bench: testing and validating real-world bug-fixes with code agents. In Conference on Neural Information Processing Systems (NeurIPS). https://openreview.net/forum?id=9Y8zUO11EQ [28] Shaan Nagy, Timothy Zhou, Nadia Polikarpova, and Loris D’Antoni. 2026. ChopChop: a programmable framework for semantically constraining the output of language models. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). doi:10.1145/3776708 [29] Theo X. Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar-Lezama. 2024. Is self-repair a silver bullet for code generation?. In International Conference on Learning Representations (ICLR). https://openreview.net/forum?id=y0GJXRungR [30] OpenAI. 2026. Codex. https://openai.com/codex/ Accessed: 2026-0409. [31] OpenAI. 2026. OpenAI Harmony response format. https://develo pers.openai.com/cookbook/articles/openai-harmony Accessed: 2026-05-01. [32] OpenAI, Sandhini Agarwal, Lama Ahmad, Jason Ai, Sam Altman, Andy Applebaum, Edwin Arbus, Rahul K. Arora, Yu Bai, Bowen Baker, Haiming Bao, Boaz Barak, Ally Bennett, Tyler Bertao, Nivedita Brett, Eugene Brevdo, Greg Brockman, Sebastien Bubeck, Che Chang, Kai Chen, Mark Chen, Enoch Cheung, Aidan Clark, Dan Cook, Marat Dukhan, Casey Dvorak, Kevin Fives, Vlad Fomenko, Timur Garipov, Kristian Georgiev, Mia Glaese, Tarun Gogineni, Adam Goucher, Lukas Gross, Katia Gil Guzman, John Hallman, Jackie Hehir, Johannes Heidecke, Alec Helyar, Haitang Hu, Romain Huet, Jacob Huh, Saachi Jain, Zach Johnson, Chris Koch, Irina Kofman, Dominik Kundel, Jason Kwon, Volodymyr Kyrylov, Elaine Ya Le, Guillaume Leclerc, James Park Lennon, Scott Lessans, Mario Lezcano-Casado, Yuanzhi Li, Zhuohan Li, Ji Lin, Jordan Liss, Lily Liu, Jiancheng Liu, Kevin Lu, Chris Lu, Zoran Martinovic, Lindsay McCallum, Josh McGrath, Scott McKinney, Aidan McLaughlin, Song Mei, Steve Mostovoy, Tong Mu, Gideon Myles, Alexander Neitz, Alex Nichol, Jakub Pachocki, Alex Paino, Dana Palmie, Ashley Pantuliano, Giambattista Parascandolo, Jongsoo Park, Leher Pathak, Carolina Paz, Ludovic Peran, Dmitry Pimenov, Michelle Pokrass, Elizabeth Proehl, Huida Qiu, Gaby Raila, Filippo Raso, Hongyu Ren, Kimmy Richardson, David Robinson, Bob Rotsted, Hadi Salman, Suvansh Sanjeev, Max Schwarzer, D. Sculley, Harshit Sikchi, Kendal Simon, Karan Singhal, Yang Song, Dane Stuckey, Zhiqing Sun, Philippe Tillet, Sam Toizer, Foivos Tsimpourlas, Nikhil Vyas, Eric Wallace, Xin Wang, Miles Wang, Olivia Watkins, Kevin Weil, Amy Wendling, Kevin Whinnery, Cedric Whitney, Hannah Wong, Lin Yang, Yu Yang, Michihiro Yasunaga, Kristen Ying, Wojciech Zaremba, Wenting Zhan, Cyril Zhang, Brian Zhang, Eddie Zhang, and Shengjia Zhao. 2025. gpt-oss-120b & gpt-oss-20b model card. arXiv preprint arXiv:2508.10925 (2025). https://arxiv.org/abs/2508.10925 [33] Kanghee Park, Timothy Zhou, and Loris D’Antoni. 2025. Flexible and efficient grammar-constrained decoding. In International Conference on Machine Learning (ICML). https://openreview.net/forum?id=L6CY AzpO1k

[9] Brendan Cully, Geoffrey Lefebvre, Dutch Meyer, Mike Feeley, Norm Hutchinson, and Andrew Warfield. 2008. Remus: high availability via asynchronous virtual machine replication. In Symposium on Networked Systems Design and Implementation (NSDI). doi:10.5555/1387589.1387 601 [10] Pantazis Deligiannis, Akash Lal, Nikita Mehrotra, Rishi Poddar, and Aseem Rastogi. 2025. RustAssistant: using LLMs to fix compilation errors in Rust code. In International Conference on Software Engineering (ICSE). doi:10.1109/ICSE55347.2025.00022 [11] Yixin Dong, Charlie F Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao, and Tianqi Chen. 2024. XGrammar: flexible and efficient structured generation engine for large language models. In Conference on Machine Learning and Systems (MLSys). https://openreview.net/for um?id=rjQfX0YgDl [12] Zhiyu Fan, Xiang Gao, Martin Mirchev, Abhik Roychoudhury, and Shin Hwei Tan. 2023. Automated repair of programs from large language models. In International Conference on Software Engineering (ICSE). doi:10.1109/ICSE48619.2023.00128 [13] Xiaodong Gu, Meng Chen, Yalan Lin, Yuhan Hu, Hongyu Zhang, Chengcheng Wan, Zhao Wei, Yong Xu, and Juhong Wang. 2025. On the effectiveness of large language models in domain-specific code generation. ACM Transactions on Software Engineering and Methodology 34, 3 (2025). doi:10.1145/3697012 [14] guidance-ai. 2026. Low-level guidance (llguidance). https://github.c om/guidance-ai/llguidance Accessed: 2026-04-09. [15] Binyuan Hui, Jian Yang, Zeyu Cui, Jiaxi Yang, Dayiheng Liu, Lei Zhang, Tianyu Liu, Jiajun Zhang, Bowen Yu, Keming Lu, Kai Dang, Yang Fan, Yichang Zhang, An Yang, Rui Men, Fei Huang, Bo Zheng, Yibo Miao, Shanghaoran Quan, Yunlong Feng, Xingzhang Ren, Xuancheng Ren, Jingren Zhou, and Junyang Lin. 2024. Qwen2.5-Coder technical report. arXiv preprint arXiv:2409.12186 (2024). https://arxiv.org/abs/2409.121 86 [16] Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and Ion Stoica. 2024. LiveCodeBench: holistic and contamination free evaluation of large language models for code. In International Conference on Learning Representations (ICLR). https://openreview.net/forum?id= chfJJYC3iL [17] Xue Jiang, Yihong Dong, Yongding Tao, Huanyu Liu, Zhi Jin, and Ge Li. 2025. ROCODE: integrating backtracking mechanism and program analysis in large language models for code generation. In International Conference on Software Engineering (ICSE). doi:10.1109/ICSE55347.20 25.00133 [18] Jiaolong Kong, Xiaofei Xie, Mingfei Cheng, Shangqing Liu, Xiaoning Du, and Qi Guo. 2025. ContrastRepair: enhancing conversationbased automated program repair via contrastive test case pairs. ACM Transactions on Software Engineering and Methodology 34, 8 (2025). doi:10.1145/3719345 [19] Terry Koo, Frederick Liu, and Luheng He. 2024. Automata-based constraints for language model decoding. In Conference on Language Modeling. https://openreview.net/forum?id=BDBdblmyzY [20] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with PagedAttention. In ACM Symposium on Operating Systems Principles (SOSP). doi:10.1145/3600006.3613165 [21] Yaniv Leviathan, Matan Kalman, and Yossi Matias. 2023. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning (ICML). https://openreview.net/forum?id= C9NEblP8vS [22] Lingxiao Li, Salar Rahili, and Yiwei Zhao. 2025. Correctnessguaranteed code generation via constrained decoding. In Conference on Language Modeling. https://openreview.net/forum?id=CYiXNIQegF

13

Du et al.

Here, 𝑎(𝑐) denotes the nearest checker checkpoint at or before 𝑐. The generator begins producing a suffix from 𝑐, while the checker may first need to replay from 𝑎(𝑐) to reach the same state. If the checker catches up before the generator reaches the next failure, it does not add latency; otherwise, the rollout becomes checker-bound. We model generator latency as 𝑛 𝐿𝐺 (𝑛) = + 𝐷𝐺 , 𝑆𝐺

[34] Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022. Synchromesh: reliable code generation from pre-trained language models. In International Conference on Learning Representations (ICLR). https://openreview.n et/forum?id=KmtVD97J43e [35] Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. 2023. Code LLama: open foundation models for code. arXiv preprint arXiv:2308.12950 (2023). https://arxiv.org/abs/2308.129 50 [36] Qinglin Wang, Zhihong Sun, Ruyun Wang, Tao Huang, Zhi Jin, Ge Li, and Chen Lyu. 2025. SemGuard: real-time semantic evaluator for correcting LLM-generated code. In IEEE/ACM International Conference on Automated Software Engineering (ASE). doi:10.1109/ASE63991.2025. 00160 [37] Yuxiang Wei, Chunqiu Steven Xia, and Lingming Zhang. 2023. Copiloting the copilots: fusing large language models with completion engines for automated program repair. In ACM International Conference on the Foundations of Software Engineering (FSE). doi:10.1145/36 11643.3616271 [38] John Yang, Carlos E. Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. 2024. SWE-agent: agentcomputer interfaces enable automated software engineering. In Conference on Neural Information Processing Systems (NeurIPS). https: //openreview.net/forum?id=mXpq6ut8J3 [39] Zihan Zheng, Zerui Cheng, Zeyu Shen, Shang Zhou, Kaiyuan Liu, Hansen He, Dongruixuan Li, Stanley Wei, Hangyi Hao, Jianzhu Yao, Peiyao Sheng, Zixuan Wang, Wenhao Chai, Aleksandra Korolova, Peter Henderson, Sanjeev Arora, Pramod Viswanath, Jingbo Shang, and Saining Xie. 2025. LiveCodeBench Pro: how do olympiad medalists judge LLMs in competitive programming?. In Conference on Neural Information Processing Systems (NeurIPS). https://openreview.net/for um?id=U5RIVFtat1

A

Policy Model

A.1

Preliminaries

where 𝑆𝐺 is the average generator speed in bytes per second and 𝐷𝐺 is a fixed startup delay. Checker latency is modeled as 𝑛 𝑛 𝐿𝐶 (𝑛) = + 𝐿𝑆 · + 𝐷𝐶 , 𝑆𝐶 𝑓𝐶 where 𝑆𝐶 is the average checker speed, 𝑓𝐶 is the checker checkpoint interval, 𝐿𝑆 is the stall time incurred when materializing a checker checkpoint, and 𝐷𝐶 is fixed startup overhead, including process and communication costs. A.3

We next model the token cost of a repair attempt from progress node 𝑐. As a simplifying approximation, we assume that the generator emits exactly 𝑒 − 𝑐 bytes before either succeeding or encountering a failure. In practice, the realized cost may be lower if the attempt fails early, or higher if it continues beyond 𝑒 before encountering an error. When the checker lags behind the generator, additional output may be generated while the checker catches up. We estimate the lag as Δ𝐿(𝑐, 𝑒) = 𝐿(𝑐, 𝑒) − 𝐿𝐺 (𝑒 − 𝑐),

Let C = {𝑐 1 ≤ · · · ≤ 𝑐𝑚 } denote the candidate rollback points available for a detected error at offset 𝑒. In our policy, the candidates are ancestor progress nodes on the current search-tree path, ordered by their offsets. The first candidate 𝑐 1 is the initial progress node at the beginning of generation. We posit a latent root-cause position 𝑟 ≤ 𝑒. A rollback to 𝑐 can repair the error only if it starts before the root cause: ( 𝑞(𝑐, 𝑟 ), 𝑐 < 𝑟, 𝑃 (Success | 𝑐, 𝑟 ) = 0, 𝑐 ≥ 𝑟.

and convert this additional time into generated bytes using the generator speed. The resulting token-cost estimate is 𝐶𝑇 (𝑐, 𝑒) = (𝑒 − 𝑐) + 𝑆𝐺 · Δ𝐿(𝑐, 𝑒). Thus, rollouts that require the checker to replay a long prefix are penalized, since they may allow the generator to consume extra tokens before the checker can report an error. A.4

Root Cause Belief

The policy maintains a belief 𝜋 over the normalized distance from the error to the root cause. For an error at offset 𝑒, define 𝑒 −𝑟 𝑑= ∈ [0, 1]. 𝑒 Smaller values of 𝑑 correspond to root causes close to the reported error, while larger values correspond to root causes farther back in the program. Let 𝑒 −𝑐 𝑥 (𝑐, 𝑒) = 𝑒 denote the normalized rollback distance. A rollback to 𝑐 reaches the root cause when 𝑑 < 𝑥 (𝑐, 𝑒). Under belief 𝜋, the

Thus, a rollback that starts at or after the root cause is assumed to preserve the error and therefore cannot succeed. A rollback that starts before the root cause is eligible to succeed, but may still fail with probability 1 − 𝑞(𝑐, 𝑟 ). For tractability, the policies use a constant success probability 𝑞 whenever 𝑐 < 𝑟 , so 𝑞(𝑐, 𝑟 ) = 𝑞. A.2

Token Cost Model

Latency Model

We model the latency of a repair attempt from progress node 𝑐 as the maximum of generator latency and checker latency: 𝐿(𝑐, 𝑒) = max(𝐿𝐺 (𝑒 − 𝑐), 𝐿𝐶 (𝑒 − 𝑎(𝑐))). 14

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

expected success probability of rolling back to 𝑐 is therefore

TokPol scores each candidate by combining the cost of attempting repair from that candidate with the expected cost of fallback attempts if the repair fails. We write

𝑃 (Success | 𝑐, 𝜋) = 𝑞 · Π(𝑥 (𝑐, 𝑒)), where

𝐶 ★ (𝑐)

Π(𝑥) = 𝑃𝜋 (𝑑 < 𝑥) is the cumulative mass assigned to root causes reached by rollback distance 𝑥. We also write

for the estimated continuation cost after a failed attempt from 𝑐. After such a failure, the continuation considers only candidates earlier than 𝑐:

𝑃 (Fail | 𝑐, 𝜋) = 1 − 𝑃 (Success | 𝑐, 𝜋).

C<𝑐 = {𝑐 ′ ∈ C : 𝑐 ′ < 𝑐}.

When a repair attempt from 𝑐 𝑓 fails, the failure provides evidence about the root cause. If 𝑑 < 𝑥 (𝑐 𝑓 , 𝑒), then the rollback reached the root cause and the attempt was eligible to succeed, but failed with probability 1 − 𝑞. If 𝑑 ≥ 𝑥 (𝑐 𝑓 , 𝑒), then the rollback did not reach the root cause, so failure was inevitable. Bayes’ rule gives the posterior ( (1 − 𝑞)𝜋 (𝑑), 𝑑 < 𝑥 (𝑐 𝑓 , 𝑒), CondFail(𝜋, 𝑐 𝑓 ) (𝑑) ∝ 𝜋 (𝑑), 𝑑 ≥ 𝑥 (𝑐 𝑓 , 𝑒).

Thus,   𝐶 ★ (𝑐) = ′min 𝐶𝑇 (𝑐 ′, 𝑒) + 𝑃 (Fail | 𝑐 ′, 𝑐, 𝜋) 𝐶 ★ (𝑐 ′ ) . 𝑐 ∈ C<𝑐

The selected rollback point is then   𝑐 ★ = arg min 𝐶𝑇 (𝑐, 𝑒) + 𝑃 (Fail | 𝑐, 𝜋) 𝐶 ★ (𝑐) . 𝑐∈C

The restriction to C<𝑐 applies only to the continuation estimate. After modeling a failure from 𝑐, later candidates do not reach any root causes that 𝑐 did not already reach.

This update shifts probability mass toward larger rollback distances: after a failed attempt, the policy becomes more willing to roll back earlier. A.5

B.2 Solution We solve this recursion by backward induction over the candidate nodes. For the earliest candidate, there are no earlier fallback points, so its continuation cost is zero. For each later candidate 𝑐𝑘 , we compute   𝐶 ★ (𝑐𝑘 ) = min 𝐶𝑇 (𝑐 𝑗 , 𝑒) + 𝑃 (Fail | 𝑐 𝑗 , 𝑐𝑘 , 𝜋) 𝐶 ★ (𝑐 𝑗 ) .

Progress

The policies must decide whether a newly reported error is another failure while repairing the same underlying target, or whether it represents meaningful progress to a new repair target. This distinction is important because failures on the same error target should update the posterior for that target, whereas a new target should begin with a fresh prior. We define progress operationally using offsets. Suppose a repair group is currently targeting an error at offset 𝑒 with category 𝜏, and a rollout in that group later reports an error at offset 𝑒 ′ with error category 𝜏 ′ . We say that the new error is a top-level error if

𝑗 <𝑘

This value estimates the minimum expected token cost of the fallback sequence available after an attempt from 𝑐𝑘 fails. Once all continuation values have been computed, TokPol scores each candidate as Score(𝑐) = 𝐶𝑇 (𝑐, 𝑒) + 𝑃 (Fail | 𝑐, 𝜋)𝐶 ★ (𝑐), and selects the candidate with minimum score. B.3

𝑒′ − 𝑒 > 𝜃

Algorithm 1 gives the TokPol policy. TokPol ignores progress nodes and acts only on error nodes. When an error is reported, the policy first determines whether it is a new toplevel error using the progress rule. For a new top-level error, the policy resets the belief to the prior 𝜋0 . Otherwise, the error is treated as another failed attempt on the same target, and the belief is updated by conditioning on the failed start node. The policy then selects a rollback point and spawns the next rollout.

and, when error-category matching is enabled, 𝜏′ ≠ 𝜏. Here, 𝜃 is a byte-offset threshold. The offset threshold filters out small local changes. The error-category condition is a further guard: if a rollout reports the same kind of error, it is often still failing for the same underlying reason.

B B.1

Algorithm

Single-Rollout Policy

C

Policy Objective

TokPolK extends TokPol to multiple concurrent rollouts. Instead of selecting a single next rollback point, it maintains a rollout group 𝐺 = {𝑔1, . . . , 𝑔 |𝐺 | },

TokPol maintains a single active rollout. When that rollout reports an error, the policy chooses an ancestor progress node from which to start the next repair attempt. The objective is to minimize the expected token cost required to make progress past the current repair target.

Multi-Rollout Policy

where each rollout 𝑔𝑖 ∈ 𝐺 starts from a candidate node 𝑔𝑖 .𝑐. Multiple rollouts may start from the same node. 15

Du et al.

Algorithm 1 TokPol policy.

preemption by later top-level errors. Rather than solving this full dynamic program, TokPolK uses a local approximation: it scores the currently proposed group by its expected cost per probability of success. Let 𝑃 (𝐺, 𝑒) be the probability that at least one rollout in 𝐺 repairs the target error, and let 𝐶 (𝐺, 𝑒) be the expected token cost incurred while executing the group. The group score is 𝐶 (𝐺, 𝑒) . 𝑆 (𝐺, 𝑒) = 𝑃 (𝐺, 𝑒) This score is the repeated-trials estimate of token cost per successful repair. TokPolK greedily constructs rollout groups that minimize this score.

def on_node(self, node, state): if node.kind != "error": return [] rollout = state.rollouts[node.rollout_id] if IsTopLevelError( node, self.target, self.theta, self.use_cat ): self.target = node self.pi = self.pi_0 else: self.pi = CondFail(self.pi, rollout.start)

Group success probability. For each rollout 𝑔𝑖 , define its normalized rollback distance 𝑒 − 𝑔𝑖 .𝑐 . 𝑥𝑖 = 𝑥 (𝑔𝑖 .𝑐, 𝑒) = 𝑒 Order the rollouts so that

C = ancestor_progress_nodes(node, state) c = self.tokmin_select(C, node.offset, self.pi) return [spawn(start=c)]

𝑥 1 ≤ 𝑥 2 ≤ · · · ≤ 𝑥 |𝐺 | ,

Algorithm 2 TokPol selection.

and let 𝑥 0 = 0. If the root cause lies in the interval (𝑥 𝑗 −1, 𝑥 𝑗 ], then exactly the rollouts 𝑔 𝑗 , . . . , 𝑔 |𝐺 | roll back far enough to reach it. The probability that at least one of these eligible rollouts succeeds is

def tokmin_select(self, C, e, pi): C = sorted(C, key=lambda c: c.offset)

1 − (1 − 𝑞) |𝐺 | − 𝑗+1 . Therefore,

cost = {c: C_T(c, e) for c in C} cont = {}

𝑃 (𝐺, 𝑒) = for c in C: earlier = [ c0 for c0 in C if c0.offset < c.offset ]

|𝐺 | ∑︁ 

Π(𝑥 𝑗 ) − Π(𝑥 𝑗 −1 )



 1 − (1 − 𝑞) |𝐺 | − 𝑗+1 .

𝑗=1

Here, Π(𝑥 𝑗 ) − Π(𝑥 𝑗 −1 ) is the posterior mass of root causes in the interval (𝑥 𝑗 −1, 𝑥 𝑗 ]. Group cost. To compute 𝐶 (𝐺, 𝑒), we order the same rollouts by increasing completion time. Let 𝑔˜1, . . . , 𝑔˜|𝐺 | denote this time-ordered sequence, and define

if not earlier: cont[c] = 0 else: posterior = CondFail(pi, c) cont[c] = min( cost[c0] + PFail(c0, posterior) * cont[c0] for c0 in earlier )

𝑡𝑖 = 𝐿(𝑔˜𝑖 .𝑐, 𝑒),

𝑡 0 = 0,

Δ𝑡𝑖 = 𝑡𝑖 − 𝑡𝑖 −1 .

During interval 𝑖, rollouts 𝑔˜𝑖 , . . . , 𝑔˜|𝐺 | are still active. We approximate their aggregate burn rate as 𝑅𝑖 =

|𝐺 | ∑︁ 𝐶𝑇 (𝑔˜ℓ .𝑐, 𝑒) ℓ=𝑖

𝐿(𝑔˜ℓ .𝑐, 𝑒)

.

The group incurs this burn rate only if no earlier completed rollout has succeeded. Let 𝑃survive (𝑖) denote the probability that the group is still running at the start of interval 𝑖. Using the rollback-distance ordering above,

return argmin( cost[c] + PFail(c, pi) * cont[c] for c in C )

𝑃survive (𝑖) =

|𝐺 | ∑︁ 

 Π(𝑥 𝑗 ) − Π(𝑥 𝑗 −1 ) (1 − 𝑞) 𝑁𝑖,𝑗 ,

𝑗=1

In contrast to the single-rollout case, modeling the exact continuation value of a rollout group is difficult. A group’s future cost depends on the order in which rollouts finish, posterior updates after failures, replacement decisions, and

where 𝑁𝑖,𝑗 is the number of rollouts that have completed before interval 𝑖 and whose rollback distance is at least 𝑥 𝑗 . These are exactly the completed rollouts that would have been eligible to repair a root cause in (𝑥 𝑗 −1, 𝑥 𝑗 ]. 16

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

Algorithm 3 TokPolK policy.

The expected group cost is then 𝐶 (𝐺, 𝑒) =

|𝐺 | ∑︁

def on_node(self, node, state): if node.kind == "progress": self.progress[node.rollout_id] = node.offset return []

Δ𝑡𝑖 · 𝑃 survive (𝑖) · 𝑅𝑖 .

𝑖=1

Each interval contributes its active burn rate, weighted by the probability that the group has not already terminated successfully. C.1

if node.kind != "error": return []

Solution

Given an existing group 𝐺 0 , TokPolK greedily adds new rollout starts one at a time. At each step, it selects the candidate whose addition minimizes the group score:

group = self.group_of(node.rollout_id) if group is None or IsTopLevelError( node, group.target, self.theta, self.use_cat ): return self.start_new_group(node, state)

𝑐𝑡 = arg min 𝑆 (𝐺𝑡 −1 ∪ {𝑐}, 𝑒), 𝑐∈C

where 𝐺𝑡 = 𝐺𝑡 −1 ∪ {𝑐𝑡 }. After 𝑛 steps, the newly selected rollout starts are the multiset difference 𝐺𝑛 \ 𝐺 0 . This same procedure is used both to initialize a new repair group and to replace a failed rollout within an existing group. C.2

return self.replace_in_group(node, state, group)

Algorithm 4 TokPolK creation of new repair group. def start_new_group(self, node, state): e = node.offset

Algorithm

Algorithm 3 shows the TokPolK policy. For progress nodes, TokPolK records the largest accepted offset reached by each rollout. These offsets are later used to decide which rollouts should be preempted when a new top-level error is discovered. For error nodes, TokPolK distinguishes two cases. If the error belongs to the rollout’s current repair group, the policy treats it as another failed attempt on the same target. It updates the group’s belief, removes the failed rollout, and greedily selects one replacement. If the error is a new toplevel error, the policy creates a new repair group. It preempts active rollouts whose latest progress is less than 𝛼𝑒, where 𝑒 is the new error offset and 𝛼 ∈ [0, 1] is the preemption coefficient. The freed slots are then filled using greedy group selection under the prior 𝜋 0 .

D

victims = { r for r in state.active_rollouts() if self.progress[r.id] < self.alpha * e } group = self.new_group(target=node, pi=self.pi_0) C = ancestor_progress_nodes(node, state) starts = self.latmin_select( C=C, G0=[], n=len(victims) + 1, e=e, pi=self.pi_0 ) return [kill(r.id) for r in victims] + \ [spawn(start=s) for s in starts]

Checkpoint Interval Selection

The checker checkpoint interval 𝑓𝐶 trades off replay cost against checkpointing overhead. Sparse checkpoints reduce the frequency of checkpoint materialization, but may place the nearest materialized checkpoint 𝑎(𝑐) far before the rollback point 𝑐. After rollback, the checker must replay from 𝑎(𝑐) before it can validate newly generated tokens. If replay is too slow, the checker falls behind the generator and the generator may emit extra tokens before the checker reports failure. Dense checkpoints reduce this replay distance, but increase checkpointing overhead. We choose the largest 𝑓𝐶 for which the checker catches up on at least a fraction 𝑄 of failed repair rollouts. For a repair attempt from 𝑐 that reports an error at 𝑒, catch-up requires

That is, the checker must replay from its nearest checkpoint to the error no later than the generator produces the suffix from 𝑐 to 𝑒. In our experiments, we set 𝑄 = 0.99. This conservative threshold reflects that the policy optimizes token consumption: when the checker fails to catch up, the generator may continue producing tokens for a suffix that is already statically invalid. We estimate the catch-up rate for each candidate checkpoint interval by Monte Carlo simulation. For each candidate value of 𝑓𝐶 , we evaluate the policy using the latency model induced by that same value. We perform a binary search over 𝑓𝐶 ∈ [𝑓min, 𝑓max ] and select the largest value whose Wilson confidence-interval lower bound is at least 𝑄.

𝐿𝐶 (𝑒 − 𝑎(𝑐)) ≤ 𝐿𝐺 (𝑒 − 𝑐). 17

Du et al.

Algorithm 5 TokPolK replacement on within-group failure.

Algorithm 7 Random Repair.

def replace_in_group(self, node, group, state): rollout = state.rollouts[node.rollout_id]

def on_node(self, node, state): if node.kind != "error": return []

group.pi = CondFail(group.pi, rollout.start) C = ancestor_progress_nodes(node, state) c = self.uniform_sample(C)

C = ancestor_progress_nodes(node, state) G0 = group.active_rollouts(state)

return [spawn(start=c)] starts = self.latmin_select( C=C, G0=G0, n=1, e=group.target.offset, pi=group.pi )

Algorithm 8 Statement-Level Repair. def on_node(self, node, state): if node.kind != "error": return []

return [spawn(start=s) for s in starts]

episode = self.episode_of(node.rollout_id)

Algorithm 6 TokPolK selection.

if episode is None or IsTopLevelError( node, episode.target, self.theta, self.use_cat ): C = ancestor_progress_nodes(node, state) episode = self.new_episode( target=node, candidates=C, attempts=self.a ) else: self.episode.advance_after_failure()

def latmin_select(self, C, G0, n, e, pi): G = list(G0) selected = [] for _ in range(n): c = argmin( S(G + [c], e, pi) for c in C ) G.append(c) selected.append(c)

c = self.episode.current_candidate() return [spawn(start=c)]

return selected

no repair episodes, beliefs, or candidate walk. This baseline provides a lower bound for informed rollback selection.

This procedure gives an optimistic upper bound on the safe checkpoint interval. A deep rollback may encounter a new error shortly after restarting, yielding a small generated suffix 𝑒 − 𝑐 but a large checker replay distance 𝑐 − 𝑎(𝑐). Such cases make catch-up harder than predicted by a simulation that assumes the rollout continues to the sampled error offset.

E.2

Statement-Level Repair

All baseline policies use the same checker implementation, checkpoint interval, prompts, and sampling configuration as TokPol and TokPolK. They differ only in how they select rollback nodes after an error event.

Statement-Level Repair uses a simple positional rollback order. For a new top-level error, it orders candidates from the most recent progress node before the error back toward the root. The policy attempts each candidate up to 𝑎 times before advancing to the next candidate. Once the candidate list is exhausted, subsequent errors in the same episode fall back to root retries until a new top-level error starts a fresh candidate list. This baseline isolates the value of positional rollback ordering without using the cost model or root-cause belief. In our experiments, we set 𝑎 = 1.

E.1

E.3

E

Baseline Policies

Random Repair

Random Repair is a memoryless baseline. On every error event, it samples uniformly from the ancestor progress nodes of the error and spawns a rollout from the selected node. Each error is handled independently: the policy maintains

Entropy-Based Repair

Entropy-Based Repair follows the same retry and exhaustion logic as Statement-Level Repair, but replaces the positional candidate order with an entropy-based order inspired by ROCODE [17]. The intuition is that high-entropy tokens 18

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

Algorithm 9 Entropy-Based Repair.

mark points where the model was uncertain, and these points may be more likely to contain the root cause of a downstream static error. During generation, the policy requests log-probabilities for the top 𝑘 tokens at each step. We use 𝑘 = 128. Given returned log-probabilities ℓ1, . . . , ℓ𝑘 , the per-token entropy is approximated as 𝐻ˆ𝑡 = −

𝑘 ∑︁

def on_node(self, node, state): if node.kind != "error": return [] episode = self.episode_of(node.rollout_id) if episode is None or IsTopLevelError( node, episode.target, self.theta, self.use_cat ): C = self.ancestor_progress_nodes(node, state)

𝑝 𝑗 log 𝑝 𝑗 − 𝑝 tail log 𝑝 tail,

𝑗=1

where 𝑝 𝑗 = exp(ℓ 𝑗 ),

𝑝 tail = max 0, 1 −

𝑘 ∑︁

! 𝑝𝑗 .

latest = C[-1] ranked = sorted( C[:-1], key=lambda c: (-c.max_entropy, -c.offset) ) candidates = [latest] + ranked

𝑗=1

The residual probability mass outside the top-𝑘 is treated as a single aggregate event. This avoids requesting the full vocabulary distribution, which would add substantial inference overhead. The checker reports progress nodes that partition the generated code into intervals. For each progress node, we record the maximum entropy over generated tokens in the corresponding interval. This value is stored in the node’s max_entropy metadata field. For each new top-level error, the first candidate is the most recent progress node before the error. The remaining candidates are sorted by decreasing max_entropy, with ties broken by larger byte offset. The retry and exhaustion behavior is otherwise identical to Statement-Level Repair. In our experiments, we set 𝑎 = 2, matching the local-attempt budget used by ROCODE before entropy-guided rollback.

episode = self.new_episode( target=node, candidates=candidates, attempts=self.a ) else: self.episode.advance_after_failure() c = self.episode.current_candidate() return [spawn(start=c, compute_entropy=True)]

19

Du et al.

F

Prompts

F.1

Initial (C++)

Overview: - Write a complete single-file C++ program that solves the problem. Requirements: - Return exactly one fenced `cpp` code block containing the full program. - Do not include any explanation or extra markdown before or after the code block. - Use only the C++ standard library. - Read from standard input and write to standard output. Problem title: {title} Problem statement: {description}

F.2

Regeneration-Based Repair (C++)

Overview: - The following C++ program was intended to solve the problem, but it failed to compile. - Produce a corrected program that compiles and solves the problem. Requirements: - Return exactly one fenced `cpp` code block containing the full corrected program. - Do not include any explanation or extra markdown before or after the code block. - Use only the C++ standard library. Problem title: {title} Problem statement: {description} Original program: ```cpp {code} ``` Compiler errors: {compiler_errors}

F.3

Edit-Based Repair (C++)

Overview: - The following C++ program was intended to solve the problem, but it failed to compile. - Produce SEARCH/REPLACE edits that make the program compile and solve the problem. Requirements: - Return exactly one fenced `cpp` block containing only SEARCH/REPLACE edits. - Do not include any explanation or extra markdown before or after the block. - Use only the C++ standard library. - Each SEARCH block must match exactly one contiguous region of complete lines in the current program. - Do not use partial-line matches. - Preserve indentation and spacing exactly. - Use an empty replacement block to delete lines. - Apply blocks in order. - If a SEARCH block would be ambiguous, include more surrounding lines until it is unique. Examples: Example 1: replace one unique block ```cpp <<<<<<< SEARCH 20

Hydra: Efficient, Correct Code Generation via Checkpoint-and-Rollback Support

int ans = 0; for (int x : a) ans += x; ======= long long ans = 0; for (int x : a) ans += x; >>>>>>> REPLACE ``` Example 2: delete one line ```cpp <<<<<<< SEARCH cerr << ans << endl; ======= >>>>>>> REPLACE ``` Problem title: {title} Problem statement: {description} Original program: ```cpp {code} ``` Compiler errors: {compiler_errors}

21