Learning & Reasoning / ACL 2026 Findings

When the Code and the Pseudocode Disagree

DuET predicts a test’s expected output by running generated code and separately asking a language model to trace pseudocode. The two routes recover from different failures.

DuET: Dual Execution for Test Output Prediction with Generated Code and Pseudocode

Hojae Han, Jaejin Kim, Seung-won Hwang, Yu Jin Kim, Moontae Lee

Overview

A test needs an answer before it can tell whether a program is right. For a running average, the average after the first number should be that number. A generated program might divide by the full list length from the start. The computer will run it faithfully and return the wrong answer. A model tracing a plain-language algorithm might avoid that bug, yet lose track when the same job takes many steps. DuET combines the outputs of those two routes to predict what a test should expect.

Key Findings

A cumulative average that goes wrong

Consider a request to compute running averages for the list [2, 4, 6, 8]. The correct answer is [2.0, 3.0, 4.0, 5.0]. In Figure 2a of the paper, the generated pseudocode captures this logic faithfully, but the translated program divides the running total by the full list length at every step and returns [0.5, 1.5, 3.0, 5.0].

Figure 2 from the ACL Findings paper. One example has a good plan that becomes bad code. In the other, a model makes a tracing error even though the plan and executable code are correct.
Figure 2 from the ACL Findings paper. One example has a good plan that becomes bad code. In the other, a model makes a tracing error even though the plan and executable code are correct.

Test output prediction asks a model to produce the expected output for a given problem and input without a trusted solution on hand (Section 2.1).

Earlier work such as TestChain grounds the prediction in generated code and runs it directly (Figure 1a). The authors argue this makes prediction correctness entangled with implementation quality. A minor translation slip, such as a misindexed operation or a missing edge case, ruins an otherwise correct plan (Section 3.1). The paper formalizes the baseline as

f(d,i)=e(g(d),i)f(d,i)=e(g(d),i)

in Equation 1, where dd is the problem description, ii is the test input, gg generates code, and ee executes it. The authors then split gg into pseudocode generation pp followed by translation tt into code, so g=t∘pg = t \circ p.

Letting a language model trace the pseudocode

The first contribution skips translation. Equation 2 defines

f^(d,i)=e^(d,p(d),i)\hat f(d,i)=\hat e(d,p(d),i)

where e^\hat e is a language model that reasons through the pseudocode step by step on the given input (Section 3.2.1). Because pseudocode states the algorithm at a higher level, syntax slips and indexing bugs have less room to enter.

This route has its own weakness. The authors call it execution hallucination. In Figure 2b, a binary-list problem requires up to 100 update steps. The model's trace drifts around step 47 and produces a wrong final list even though the pseudocode and the code are both correct. Appendix M gives a concrete case where the model invents a second zero in the string "2245047" and returns 0 deletions.

Two routes, one vote

DuET puts both approaches to work on the same test input. It generates pseudocode independently for each route. One model traces its pseudocode, while the other route translates its plan into executable code and runs it. Each route votes for the output it expects. The paper adds a path-weighted variant in Equation 3.

Figure 3 from the ACL Findings paper. Independent pseudocode generations feed two execution routes, and the outputs are combined by voting.
Figure 3 from the ACL Findings paper. Independent pseudocode generations feed two execution routes, and the outputs are combined by voting.

With OO and O^\hat O as the multisets of outputs from direct and LLM-based execution, the final prediction is

o=arg⁡max⁡o∈O∪O^[w(o,O)⋅V(o,O)+w(o,O^)⋅V(o,O^)]o=\arg\max_{o\in O\cup\hat O}\left[w(o,O)\cdot V(o,O)+w(o,\hat O)\cdot V(o,\hat O)\right]

where V(o,O)=∣{i:oi∈O,oi=o}∣V(o,O)=|\{i: o_i\in O, o_i=o\}| counts how many samples in a route produced oo. The weight w(o,O)w(o,O) equals whighw_{high} if every output in that route equals oo, and wbasew_{base} otherwise, with whigh>wbasew_{high}>w_{base}. Appendix E sets whigh=2w_{high}=2 and wbase=1w_{base}=1. The LLM path also falls back to an ungrounded prediction when its samples disagree.

In the main experiments, the system draws 10 outputs from each route. Appendix D counts 4n LLM calls and n code executions for n candidates, which batches down to two forward passes under full parallelization.

A gain that survives a fairer comparison

On the 442-problem LiveCodeBench test output prediction benchmark, DuET with GPT-4-Turbo-2024-04-09 reaches 81.1 Pass@1. The authors report this as 6.9 points above GPT-4-Turbo with voting and 5.6 points above TestChain with voting (Section 5.1).

Method (LiveCodeBench, May 1, 2023–Apr 1, 2024)Pass@1
GPT-4-Turbo-2024-04-09 (leaderboard)67.5
GPT-4-Turbo-2024-04-09 + functional majority voting74.2
TestChain + functional majority voting75.5
DuET81.1

Selected rows from Table 1 of the paper.

The gain is 13.6 points against the leaderboard figure and 5.6 against TestChain with voting. Both comparisons matter because voting already helps the underlying model. On a contamination-limited 76-problem subset (Table 2), DuET beats TestChain for every backbone, for example 53.3 versus 46.3 for Llama-3.1-8B-Instruct and 78.3 versus 71.5 for Llama-3.1-70B-Instruct.

Why the routes complement each other

The paper's diagnostics split problems by whether the generated code passes all test inputs. Figure 5 reports the result. When the code is correct, direct execution scores 100, pseudocode tracing scores 86.7, and DuET scores 97.3. When the code is wrong, direct execution falls to 39.4 and pseudocode tracing holds at 53.9, while DuET reaches 51.1. This split uses correctness information unavailable in practice, so it describes the mechanism and does not offer a deployable selector.

Figure 6 bins problems by execution trace length, counting one step per executed line of code. Pseudocode tracing often beats direct execution up to roughly 100 steps, then declines as long reasoning chains accumulate errors. The figure shows the combined method performing well across the plotted lengths. Appendix G adds a view by input difficulty. Direct execution wins on Easy and Medium inputs, pseudocode tracing wins on Hard ones (41.2 versus 23.7 in Table 8), and DuET ranks first on All, Easy and Medium.

Table 5 sweeps the design space with GPT-4-Turbo on the May 2023–Apr 2024 split.

VariantGroundingExecutionPass@1
No groundingnonenone74.2
TestChaincodedirect75.5
LLM-based code executioncodeLLM72.2
LLM-based pseudocode executionpseudocodeLLM74.1
Direct and LLM-based code executioncodeboth77.4
LLM-based code and pseudocode executionbothLLM73.6
DuET (path-weighted voting)bothboth80.8

Selected rows from Table 5 of the paper.

Pairing direct execution with pseudocode tracing (80.8) beats pairing it with code tracing (77.4). Appendix B finds that mid- and high-level pseudocode beats low-level pseudocode, and the choice between step-by-step and 3-step tracing shows no consistent winner.

Picking among generated programs

The second test asks whether better predicted outputs help choose among 20 candidate programs. Following CodeT, five test inputs per problem are paired with predicted outputs to filter candidates (Section 5.2).

Filtering method, Llama-3.1-8B-InstructPass@1Pass@10
No filtering33.973.3
CodeT54.274.3
TestChain48.667.6
DuET57.475.1
DuET without direct code execution55.975.1

Table 3 of the paper reports this comparison on LiveCodeBench-Easy.

TestChain falls 5.6 points below CodeT. Section 6.1 calls this the zero-advantage problem. Outputs derived from the candidate programs themselves carry little signal when most candidates are right, and mislead when most are wrong, as the sum(a, b) example in Figure 4 illustrates. The pseudocode path does not depend on the code being ranked, and DuET gains 3.2 points over CodeT.

More votes help only when their errors differ

The pattern holds elsewhere with some caveats. On BigCodeBench-Hard with QwQ-32B (Table 6), DuET reaches 25.3 Pass@1 against 24.0 for no filtering, and it is the only method above that baseline. On DevEval, evaluated on 367 problems after excluding cases where all candidates were uniformly right or wrong, DuET ranks first or second in every domain (Figure 7). On HumanEval and HumanEval+ with Llama-3.1-70B-Instruct (Table 10), gains are small, 85.1 and 75.4 against CodeT's 84.7 and 75.0, and the authors attribute this to saturation.

Path weighting adds at most a small improvement in the reported experiment. Table 12 shows gains of at most 0.7 points, such as 77.6 rising to 78.3 for Llama-3.1-70B-Instruct, with no losses. The authors also note that their TestChain is a single-pass reproduction without a public implementation, that test inputs were generated simply, and that LiveCodeBench has not been updated for newer models. One implication is that the two routes must fail differently often enough for their combined vote to help. The authors point to adaptive weighting as a way to learn when to trust each route.

Questions & Answers

The opening answers are simulated author responses based on the paper.

Q: Why ask for an output if the computer can just run the program?

A: Running an implementation gives the output that implementation produces. A test needs the output the problem specifies. Our method uses generated implementations because a trusted one may be unavailable. It also traces a separate description of the algorithm so one implementation bug has less influence.

Q: Why does unanimous agreement get more weight?

A: Unanimity gives us a cheap indication that sampling within a route is stable. We use it to give that route’s votes more influence. Samples can still agree because they share a misunderstanding of the problem, so the weight does not establish calibrated confidence.

Q: What does the lower TestChain result in the second table mean?

A: In this experiment, direct execution alone made the chosen candidate less likely to solve the problem than the CodeT comparison. An output derived from candidate code can reinforce mistakes already common in that code. The result concerns this filtering setup and model.

Q: Could a service use Figure 5 to pick a route before running it?

A: Figure 5 groups examples by whether the generated program passes all the test inputs. That is valuable for understanding how the paths complement each other, but a service without a trusted reference cannot see that grouping in advance. A fair routing test has to use observable signals, such as disagreement or an execution error, and compare at matched model-token and execution budgets.

Future Ideas

Route disagreement to a test reviewer

For a codebase with a trusted reference implementation, generate candidate expected outputs for new regression tests and measure them against the reference in shadow mode. When the two paths disagree, show a reviewer the earliest divergence the tool can reliably align between the program trace and the prose explanation. Treat the prediction as review evidence, and use the reference or an engineer to set the final expected output.

Compare dual routing with single-route uncertainty sampling and random review at the same model-call and human-review budgets. Measure incorrect tests caught, useful regression cases retained, and review time. Include a random audit of unanimous results so shared mistakes remain visible. Advance only if the system finds more useful regressions without raising the rate of accepted incorrect expectations.

Before presenting a first-divergence explanation, audit a sample of program traces and prose steps for alignment. If the two do not align or the pseudocode route falls back to a trace-free prediction, show that status and route the case for ordinary review.

Sources

Original abstract

This work addresses test output prediction, a key challenge in test case generation. To improve the reliability of predicted outputs by LLMs, prior approaches generate code first to ground predictions. One grounding strategy is direct execution of generated code, but even minor errors can cause failures. To address this, we introduce LLM-based pseudocode execution, which grounds prediction on more error-resilient pseudocode and simulates execution via LLM reasoning. We further propose DUET, a dual-execution framework that combines both approaches by functional majority voting. Our analysis shows the two approaches are complementary in overcoming the limitations of direct execution suffering from code errors, and pseudocode reasoning from hallucination. On LiveCodeBench, DUET achieves the state-of-the-art performance, improving Pass@1 by 13.6 pp. For filtering candidates in code generation, DUET shows the best Pass@1 on LiveCodeBenchEasy, BigCodeBench-Hard, DevEval and HumanEval(+).