PaperlayerView exact revision on arXiv

Source-linked AI summary

InteractBench: Benchmarking LLMs on Competitive Programming under Unrevealed Information

Jiaze Li, Aocheng Shen, Bing Liu, Boyu Zhang, Xiaoxuan Fan, Qiankun Zhang, Xianjun Deng

arXiv:2608.29632v1cs.SEcs.AIcs.CL

TL;DR

Existing LLM coding benchmarks mainly provide complete inputs, leaving reasoning under unrevealed information and interaction constraints insufficiently measured. InteractBench introduces 322 offline-evaluable interactive tasks with local interactors and interaction-aware diagnostics, revealing difficulty increases and frequent interaction failures even among frontier reasoning models. Its scope is limited by the scarcity of interactive tasks and its zero-shot solver evaluations.

  • Problem

    Existing benchmarks primarily evaluate full-information coding tasks, providing limited coverage of programs that must acquire information through interactive queries under protocols and budgets.

  • Method

    InteractBench curates interactive tasks with local interactors and evaluates generated solvers using offline protocol checks, query-budget enforcement, and a fine-grained failure taxonomy.

  • Results

    Across 16 model configurations, performance consistently degrades with difficulty; algorithmic logic errors dominate, while protocol violations and query-budget overruns remain frequent even for frontier reasoning models.

  • Takeaways & Limitations

    Interactive problem solving exposes a gap from standard full-information coding benchmarks and requires diagnosing both algorithmic and interaction-specific failures.

  • Takeaways & Limitations

    The benchmark is constrained by the scarcity of interactive tasks and evaluates zero-shot model-generated solvers, leaving prompting and training strategies for future study.

Abstract

from arXiv · show

Competitive programming is increasingly being used to evaluate the algorithmic reasoning capabilities of large language models (LLMs). However, existing benchmarks primarily focus on full-information tasks where all problem inputs are provided upfront. This overlooks a critical dimension of algorithmic reasoning: the ability of generated programs to operate when key information is not revealed upfront. Interactive problems, a distinctive component of competitive programming, embody this challenge. These problems require programs to engage in multi-round interaction with an interactor (a judge program) under strict protocol constraints and limited query budgets, with new information revealed only in response to queries. To address this gap, we introduce InteractBench, a benchmark comprising 322 high-quality interactive problems curated from Codeforces, AtCoder, IOI, and ICPC. Each problem is packaged with executable local interactors, enabling fully offline evaluation. Unlike existing benchmarks, InteractBench assesses whether model-generated code can acquire information and track state dynamically. Our evaluation reveals a significant interaction gap: even the most advanced reasoning models achieve limited success on interactive problems. Beyond success rates, we propose a fine-grained failure taxonomy to diagnose the root causes of these deficiencies. Although algorithmic logic errors remain dominant, protocol violations and query-budget overruns are frequent. Code is available at https://github.com/kmsgk0/InteractBench.

1. Introduction

Existing coding benchmarks largely evaluate full-information, batch-style tasks, while interactive problems test online information acquisition under protocols and query budgets. InteractBench addresses this gap with offline evaluation and interaction-aware diagnostics.

  • Frontier coding benchmarks such as HumanEval and MBPP are approaching saturation, limiting differentiation among top models.
  • Most competitive-programming benchmarks provide full inputs upfront, leaving interactive problem solving underrepresented or excluded.
  • Interactive problems reveal hidden information through queries, requiring online strategies under strict protocols and problem-specific query budgets.
  • InteractBench curates interactive problems from Codeforces, AtCoder, IOI, and ICPC, with annotated categories, difficulty tiers, and versioned snapshots.
  • Each task includes an executable local interactor for fully offline, repeatable evaluation without external judge submission.
  • The harness supplements pass@k with protocol checks, query-budget enforcement, and failure labels distinguishing algorithmic errors from interaction-specific failures.

2. Related Work

Related benchmarks span general code synthesis and competitive programming, but many competitive-programming evaluations remain batch-oriented or dependent on external online judges. These choices limit interactive coverage and self-contained experimentation.

  • General code benchmarks began with short function-synthesis tasks and expanded toward harder problems, software engineering, stronger tests, and diverse instructions.
  • Competitive-programming benchmarks evaluate algorithmic reasoning under strict time and memory constraints.
  • Many competitive-programming benchmarks focus on batch-style problems where the full input is provided upfront.
  • Some benchmarks rely on external online-judge submissions, limiting fully self-contained evaluation.

3. InteractBench Construction

InteractBench formalizes interactive executions, selects multi-round budgeted tasks, and builds local evaluators through execution-driven validation. The resulting harness supports reproducible, interaction-aware assessment across task types and languages.

  • 3.1. Problem Definition: InteractBench models executions using solvers, interactors, hidden test cases, protocols, query budgets, and round-by-round transcripts.
  • 3.1. Problem Definition: Acceptance requires protocol conformity, staying within the query budget, and producing a correct final output for the hidden test case.
  • 3.2. Task Selection: Included tasks require multi-round interaction, well-defined protocols, and explicit or enforceable query budgets.
  • 3.2. Task Selection: Tasks receive expert-verified difficulty tiers and category labels across Graph, Search, Greedy, Bit, Data Structures, Math, and Game.
  • 3.3. Construction Pipeline: Evaluator artifacts are constructed through a propose–validate–adjudicate loop using candidate generators, interactors, verification submissions, and trace-grounded feedback.
  • 3.3. Construction Pipeline: Offline validation runs isolated solver and interactor processes while enforcing protocol, budget, time, and memory constraints and recording transcripts.
  • 3.3. Construction Pipeline: The packaged two-process interface supports portable cross-language execution without dependence on external judging infrastructure.
  • 3.3. Construction Pipeline: A supplementary online audit compares sampled official Accepted/Rejected outcomes with the offline harness where submission is permitted.

4. Experiments

The experiments evaluate interactive problem solving across difficulty tiers, categories, and failure modes using pass@k and an interaction-aware taxonomy. Results show that difficulty, category-specific state tracking, and interaction failures expose substantial limits even in frontier models.

  • Experimental setup: The evaluation uses local InteractBench tasks, 10 sampled solutions per problem, and pass@1/pass@5 metrics alongside an interaction-aware failure taxonomy.The analyses cover difficulty tiers, categories, and primary failure types in isolated execution settings.
  • Difficulty: Hard interactive tasks remain unsolved: Gemini-3-Pro-Preview reaches 0.597 on hard pass@5, while only two configurations exceed 0.400.Easy tasks approach saturation for frontier models, whereas hard tasks remain strongly discriminative.
  • Difficulty: Reasoning improves performance but does not remove the hard-task barrier; DeepSeek-V3.2-Thinking reaches overall pass@5 of 0.513 versus 0.262 for DeepSeek-V3.2.Qwen3-14B still achieves 0.000 hard pass@5 despite explicit reasoning.
  • Category breakdown: Graph is the dominant category bottleneck, with the best model below 0.500 in pass@1, while Gemini-3-Pro-Preview reaches 0.613 on Bit versus 0.475 on Graph.The category results also indicate complementary model strengths and recurring difficulty maintaining state across rounds.
  • Failure modes: Failure analysis finds WA dominant, while PE and IDLE mark early protocol breakdowns and QLE marks entering the protocol but exhausting the query budget.TLE, MLE, and RE occur but are generally secondary; QLE is reported at 0.119 for Gemini-3-Pro-Preview and 0.101 for GPT-5.2.
  • Additional analyses: Revealing hidden test data improves pass@1 and reduces protocol errors and query-budget overruns, but wrong answers remain the main residual failure type.Few-shot prompting and independent resampling perform similarly overall, while iterative refinement mainly repairs execution-level failures and depends on capability.

5. Conclusion

InteractBench evaluates interactive competitive-programming tasks with offline, reproducible infrastructure and interaction-aware diagnostics. Across 16 model configurations, performance declines with difficulty, while algorithmic errors dominate and protocol violations and query-budget overruns remain frequent.

  • InteractBench covers 322 interactive tasks from Codeforces, AtCoder, IOI, and ICPC, each packaged with an executable local interactor for fully offline, reproducible evaluation.The benchmark targets tasks where information is unrevealed during execution and acquired through multi-round queries.
  • The harness extends pass@k with protocol-compliance checks, query-budget enforcement, and interaction-specific failure modes.Reported failure modes include protocol violations, query-budget overruns, and deadlocks or timeouts.
  • Across 16 model configurations, performance consistently degrades as problem difficulty increases, revealing a gap between full-information coding benchmarks and interactive problem solving.
  • Failures are dominated by algorithmic logic errors, while protocol violations and query-budget overruns remain frequent even for frontier reasoning models.
  • Future work will expand benchmark coverage and develop prompting and training strategies for interactive querying, state maintenance, and protocol adherence.

6. Limitations

The main practical limitation is benchmark scale: interactive tasks are less common than batch-style problems, and reliable offline evaluation requires local interactors.

  • Scale remains the main practical limitation because interactive tasks are less common than batch-style problems and offline evaluation requires reliable local interactors.Future versions will collect more eligible tasks and construct new ones with verified interactors.
  • The experiments use zero-shot model-generated solvers, leaving prompting and training strategies for interactive querying, state maintenance, and protocol adherence to follow-up studies.

Impact Statement

InteractBench evaluates program synthesis when information is unrevealed and must be acquired through interaction. It is intended to support reliable, reproducible evaluation of code generation, state tracking, and protocol adherence.

  • InteractBench evaluates program synthesis under unrevealed information, requiring generated solvers to follow strict protocols and acquire information through multi-round queries.
  • The benchmark is intended to support research on reliable code generation, state tracking, and protocol adherence through fine-grained, reproducible evaluation of LLM-based coding systems.
  • The appendix organizes supplementary materials into specification, evaluation setup, supplementary experiments, and diagnostics and artifacts.

A.1. Task Card

Each InteractBench task includes a structured task card that specifies the interface required by the offline harness and makes the benchmark interface explicit and auditable.

  • Each task is accompanied by a structured task card specifying the interface required by the offline harness.
  • The task-card schema is included to make the benchmark interface explicit and auditable.
  • Table 5 presents the task-card fields in InteractBench.

B.1. Dataset Statistics

InteractBench’s appendix documents its task sources, annotation scheme, category definitions, and standardized code-generation setup. The benchmark uses expert-verified difficulty and category labels alongside prompts that enforce interactive I/O behavior.

  • Task sources and annotations: InteractBench tasks are curated from Codeforces, AtCoder, IOI, and ICPC sources.The dataset includes online judges and competition series.
  • Task sources and annotations: Category labels are multi-label, so a single task may contribute to multiple category counts.Category-level statistics are stratified by difficulty.
  • Category definitions: Graph tasks model hidden objects or targets using graph structures and relational or metric-like query signals.Solvers choose probes based on the partial structure inferred so far.
  • Category definitions: Bit tasks use low-bandwidth replies, while Data Structures tasks require online maintenance of structured state across replies.Typical state includes orders, permutations, partitions, or reconstruction invariants.
  • Evaluation setup: The evaluation uses a standardized zero-shot wrapper that compiles and executes generated programs against interactive judges.The wrapper enforces protocol compliance, flushing, and no extraneous output.
  • Evaluation setup: Generated programs must be single-file solutions that flush after every query and terminate on invalid judge responses.The prompt also prohibits debug output on stdout and specifies language-specific flushing mechanisms.

C.1. Batch vs. Interactive Evaluation

Batch evaluation reveals hidden test data upfront, while interactive evaluation requires acquiring it through queries. Revealing the data improves pass@1 and reduces interaction-specific failures, whereas refinement repairs some execution errors but leaves wrong answers dominant.

  • Batch versus interactive evaluation: On 150 matched problems, revealing hidden test data improves pass@1 for every tested configuration.The batch variant preserves final validation while removing information acquisition through queries.
  • Batch versus interactive evaluation: 0.180 vs. 0.093 and 0.011 vs. 0.056 show a rank reversal between Qwen3-14B variants in batch versus interactive evaluation.Qwen3-14B-NonThinking is higher in batch evaluation, while the thinking variant is higher interactively.
  • Batch versus interactive evaluation: Batch evaluation substantially reduces protocol errors and query-budget overruns, but wrong answers remain the dominant failure type.The comparison indicates that unrevealed information adds difficulty beyond the batch algorithmic core.
  • Mitigation strategies: Few-shot prompting is competitive with independent resampling and is slightly higher for most configurations.The clearest gains appear for weaker configurations such as Qwen3-14B and Qwen3-14B-NonThinking.
  • Mitigation strategies: Iterative refinement improves over a single attempt for stronger models but remains below independent resampling and few-shot prompting.refine@k denotes the cumulative solve rate within k refinement rounds.
  • Mitigation strategies: For GPT-5.2, compilation errors decrease from 0.040 at round 1 to 0.010 at round 5, while protocol errors decrease from 0.139 to 0.038.Wrong answers remain the dominant residual failure type after refinement.

C.3. Temporal Contamination Diagnostic via Time Splits

The time-split diagnostic probes whether temporal contamination explains performance on tasks with known release years. Across six representative model configurations, post-set pass@1 changes gradually rather than showing a cliff-like discontinuity.

  • Diagnostic design: The diagnostic reports mean pass@1 on problems released in years ≥Y as the cut year Y varies.It compares pre-set problems released before Y with post-set problems released from Y onward.
  • Results: Across six representative model configurations, the post-set pass@1 curves change gradually as the cut year advances.The models span major providers and open weights.
  • Results: No cliff-like discontinuity appears across the time-split sweep for the evaluated models.The evaluated configurations are Claude-Opus-4.5, GPT-5.2, Gemini-3-Pro-Preview, DeepSeek-V3.2-Thinking, Qwen3-32B, and Qwen3-30B-A3B-Thinking.

C.4. Multi-language and I/O Template Evaluation

The appendix tests InteractBench across four languages and with or without an interactive I/O template, then illustrates representative protocol failures. Template benefits are mixed, and wrong answers remain the main unsuccessful outcome after language-specific execution issues are separated.

  • C.4. Multi-language and I/O Template Evaluation: The evaluation compares five model configurations across C++, Python, Java, and Go using the same local interactors.Python and Java receive relaxed time limits for runtime overhead.
  • C.4. Multi-language and I/O Template Evaluation: Adding the I/O template improves DeepSeek-V3.2 on Python from 0.060 to 0.131 but lowers DeepSeek-V3.2-Thinking from 0.309 to 0.289.The template effect is therefore mixed rather than uniformly beneficial.
  • C.4. Multi-language and I/O Template Evaluation: The Python template mainly reduces idle or deadlocked runs rather than resolving algorithmic reasoning errors.Java and Go introduce more compile failures, especially for weaker models.
  • C.4. Multi-language and I/O Template Evaluation: Wrong answers remain the main source of unsuccessful runs after language-specific failures are separated.C++ shows the smallest template-versus-no-template difference, supporting its default use without templates.
  • D.1. Qualitative Evidence for Key Findings: Representative qualitative cases examine resampling as a way to recover from protocol or implementation brittleness.The examples are illustrative rather than exhaustive.
  • D.1. Qualitative Evidence for Key Findings: A fallback assigning valid query indices can turn a format-error failure into a protocol-valid attempt when indices would otherwise remain uninitialized.The failing example reports invalid query indices with zero queries and a query limit of two.
  • D.1. Qualitative Evidence for Key Findings: GPT-OSS-120B frequently produces IDLE failures by treating interactive tasks as ordinary offline input-output problems.Some stalls occur without issuing any query, contrasting with frontier models that more often reach wrong-answer failures.
  • D.1. Qualitative Evidence for Key Findings: A late IDLE can occur when a solver reads two integers after the judge emits only the -1 termination sentinel.The second read may block after otherwise protocol-shaped queries.

D.2. Error Case Studies

The case studies show that interactive failures arise from protocol mistakes, synchronization errors, query-budget exhaustion, resource failures, and insufficient reasoning even when interaction is otherwise valid.

  • InteractBench presents representative examples for each error type, pairing protocol descriptions, model code, harness evidence, and diagnoses.
  • PE: Protocol violations occur when submissions issue queries during the final-answer phase, producing format errors because the output no longer matches the interactor’s expected grammar.
  • IDLE: Missing flushes can deadlock execution because the interactor never receives the answer, while the solver blocks waiting for the next test case.
  • QLE: Query-budget overruns arise when exhaustive enumeration scales as k · 2^n, yielding QLE despite per-query protocol correctness.
  • RE: Skipping judge feedback desynchronizes the input stream, causing premature solver exit and interactor failure classified as RE.
  • Other failures include uncontrolled preprocessing that consumes the time limit, recursion without an empty-set base case that causes memory exhaustion, and selection logic that cannot certify the true top-K.

D.3. End-to-End Task Showcase: cf2036G

The cf2036G showcase demonstrates how InteractBench packages a non-adaptive task with generated hidden cases, a local interactor, protocol enforcement, query accounting, and recorded outcomes.

  • The showcase uses a non-adaptive cf2036G task with exactly three distinct hidden values and XOR range queries limited to 150 per test case.
  • Local interactor: The local interactor reads hidden cases, sends test inputs, validates XOR queries and answer values, enforces per-test and hard query caps, and logs metrics.
  • Local interactor: For XOR queries, the interactor returns the XOR of hidden values lying within the requested interval, while answer triples are sorted before comparison.
  • Hidden offline test case: The bundled hidden case contains n=999999999999999937 and hidden values 1, 288230376151711744, and 288230376151711745.
  • Evaluation outcome: A representative GPT-5.2 solver passes the showcased task, whereas sparse point-query heuristics can miss far-separated targets within the budget.

D.6. Expert Intervention Case Study

The case study shows how an overly strong uniqueness assumption caused an interactor to reject statement-consistent ! -1 answers, and how expert review replaced it with an ambiguity check validated against exhaustive enumeration.

  • 31 tasks required expert intervention after reaching the iteration cap during evaluator validation.
  • For n = 4, ⟨1, 1, 1, 2⟩ and ⟨1, 1, 1, 4⟩ generate identical replies despite differing hidden arrays, so ! -1 must be Accepted.The ambiguity persists even when all four possible triples are queried.
  • Non-zero replies alone do not establish uniqueness: ⟨1, 2, 3, 4⟩ and ⟨1, 2, 4, 3⟩ also induce identical replies for all four triples.
  • Standard solvers output ! -1 whenever multiple hidden arrays remain consistent with the interaction transcript.
  • The cf1847E interactor originally treated any non-degenerate triangle as sufficient evidence that the hidden array was uniquely identifiable.That assumption is invalid because distinct hidden arrays can produce identical replies for every allowed query.
  • The post-fix interactor checks whether an alternative hidden array preserves all oracle replies, accepting ! -1 for ambiguous arrays and rejecting it for uniquely identifiable arrays.The revision uses the small value domain and tests single-position replacements or two-position swaps as ambiguity witnesses.
Loading 2608.29632v1…