acceptodds
Under review as a conference paper at ICLR 2027

Selective Execution with Answer-Determined Termination for Structured Reasoning

Abstract

Reasoning systems spend more computation on problems that look harder, yet how much a problem needs is fixed by the answer it asks for. Once every explanation compatible with the observations implies the same answer, further reasoning cannot change it. Solvers routinely continue past this point, recovering causal structure, proofs, or complete candidate scores that the question never required; we call this over-solving. Here we formalize answer determination under incomplete information, in the sense of certain answers and partial identification, and show that an answer can be unique while arbitrarily many richer explanations remain open, so a solver can stop earlier and can answer instances whose explanation is unrecoverable. Because possible answers can contract in any monotone pattern, no task-independent rule says which computation to skip; we therefore terminate execution with a task-specific completion rule that fires once the answer is determined, and order the computations before that point with a learned answer-relevance energy. On ACRE, CLUTRR, AlphaGeometry, RAVEN-FAIR, and MNS, this selective execution omits 33.95% to 99.98% of task-specific computation while matching or improving baseline accuracy, with gains of up to 30.99 percentage points. Efficient reasoning depends not only on how fast computations run but on which computations the answer requires.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
neural-symbolic reasoning, adaptive computation, selective execution, answer determination

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_fKz5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces a selective reasoning framework to reduce over-solving, where models continue reasoning after the requested answer is already determined. The method formalizes answer determination under incomplete information and combines task-specific stopping rules with a learned answer-relevance energy to prioritize useful computations. Experiments across five benchmarks show that it eliminates 33.95%–99.98% of task-specific computation while maintaining or improving accuracy, with gains of up to 30.99 percentage points. The key contribution is shifting reasoning efficiency from faster computation to computing only what is necessary to determine the answer.

Critical strengths
  1. The paper presents a general and practical framework that combines a task-specific completion rule for sound stopping with a learned answer-relevance energy function that prioritizes the remaining computations.

  2. The notion of “over-solving” is clearly motivated through intuitive examples, such as the blicket machine, and connected to established concepts, including certain answers and partial identification.

  3. The framework yields substantial computational savings across diverse settings, suggesting that its applicability extends beyond stopping LLM chain-of-thought reasoning.

Critical weaknesses
  1. The framework relies heavily on task-specific completion rules. Deriving exact rules may require substantial domain expertise, and this process is not automated. The generality of the approach therefore depends on how readily such rules can be formulated for new tasks.

  2. Some completion rules, such as the one used for MNS, are operational rather than exact and may trade stopping safety for computational efficiency. The paper would benefit from a more thorough quantification of the frequency and consequences of premature termination.

  3. In RAVEN-FAIR and ACRE, much of the wall-clock speedup comes from reformulating the baseline computation through decomposition or set-inclusion checks, rather than from selective execution itself. Although the authors acknowledge this distinction, it complicates the interpretation of the system-level comparisons and the attribution of the reported gains.

  4. The evaluation is relatively small in some settings, such as ACRE with 384 pooled queries. Statistical significance tests or confidence intervals would help establish whether the reported accuracy improvements are reliable.

  5. The sensitivity of the results to the capacity and input features of the learned energy function remains unclear. Please report the model size, input features, and training overhead for each task, and include a small ablation study examining the contribution of different feature subsets.

Questions for authors
  1. For tasks using approximate or operational completion rules, such as MNS, how often does premature termination occur, and how significantly does it affect answer accuracy? Can the authors quantify the trade-off between computational savings and stopping reliability?

  2. In RAVEN-FAIR and ACRE, how much of the reported wall-clock speedup comes from selective execution itself, as opposed to computational reformulations such as decomposition and set-inclusion checks? Please provide controlled comparisons to isolate the contribution of each component if possible.

6 comments
AuthorsOpenReview ↗

Response to Reviewer fKz5 (Part 1/2)

Thank you for recognizing the motivation and practical value of the paper, and for your suggestions on stopping reliability and experimental design. We have added the following results.

Can the domain knowledge needed to design stopping rules by hand be reduced?

We concentrate the required domain knowledge in task rules, basic operations, and answer requirements. The program uses these to generate or maintain answer constraints and check whether the acquired evidence determines the answer. Tasks with native proof verification reuse their verifiers. The shared learner determines computation order. The tasks are handled as follows:

TaskSupplied task semanticsHow the stopping check is obtained
ACREOR activation mechanism and object composition of observations and queriesThe program generates the mapping from possible observations to answers and stops when one answer category remains
CLUTRRRelation vocabulary and composition rulesMaintain derivable relations and supporting derivations; check whether the query relation is determined
RAVEN-FAIRLocal scoring form and candidate selection ruleThe program generates upper bounds on remaining scores to verify the winning candidate
AlphaGeometryNative inference rules and target propositionReuse native proof verification and stop when the target has a valid proof
MNSRule families, expression grammar, known values, and query positionVerify rule coverage and return when all compatible cases give the same answer; continue solving if answers are ambiguous or coverage is insufficient

Table 1 in Section 4 of the revised paper summarizes the completion criteria; Appendix B gives their construction and conditions of validity.

How often does incorrect early stopping occur in MNS, and what is its effect on accuracy?

The current MNS certificates return 0 incorrect answers, and selective execution maintains the accuracy of complete execution. We corrected the original implementation and use checks for rule coverage and answer agreement. The program verifies that the input satisfies the coverage conditions of the declared rule space and checks the query answers given by compatible rules. It returns when all compatible cases agree, and invokes the native query solver when answers are ambiguous or coverage is insufficient. The outcomes across 56,000 inputs are as follows:

CaseInputsAction
Coverage holds and the answer is unique17,100Return the certified answer
Different feasible answers exist8,900Invoke the native query solver
Insufficient rule coverage30,000Invoke the native query solver

Certificates directly answer 17,100 inputs, or 30.54% of the complete cohort, and all of these answers agree with the ground truth. The remaining 38,900 inputs proceed to native query solving. Exhaustive rule enumeration and selective execution produce identical stopping classifications. Learning and Reformulated return identical answers on all 56,000 inputs, both achieving 79.11% accuracy, compared with 75.97% for the original Baseline. Candidate checks decrease from 507,548,943 to 36,748,107 rows, a 92.760% reduction. Appendix B.5 of the revised paper describes the current completion checks and continuation procedure.

AuthorsOpenReview ↗

Response to Reviewer fKz5 (Part 2/2)

How much of the ACRE and RAVEN-FAIR speedup comes from computational reformulation, and how much from selective execution?

ACRE reformulation eliminates complete causal model fitting; RAVEN-FAIR reformulation replaces full neural scoring with decomposed scoring that can be evaluated term by term. Across the 2,000 problems corresponding to 8,000 ACRE queries, model fitting decreases from 2,000 calls to 0, replaced by direct observation checks. RAVEN-FAIR neural multiply-accumulate operations decrease from approximately 7.296×10¹² to 1.688×10¹¹. Fixed and Learning then use completion rules to omit remaining work in these reformulated computations. The table below compares work on the five complete evaluation cohorts. Within each task, the three versions use the same counting unit and return identical answers on every input.

TaskCounting unitReformulatedFixedLearningLearning reduction relative to complete execution
ACREObservation checks48,00012,23312,01274.975%
CLUTRRRelation pairs and splits46,57014,28013,55070.904%
RAVEN-FAIRLocal score evaluations131,07261,78661,69052.934%
AlphaGeometryMatching calls26,93424,79523,10814.205%
MNSCandidate-check rows507,548,94338,918,68236,748,10792.760%

The corresponding measured runtimes are shown below, in seconds, including control overhead:

TaskBaselineReformulatedFixedLearning
ACRE2,909.7780.5698.8250.259
CLUTRR20,396.3973.4283.4392.509
RAVEN-FAIR7,521.61112.66511.6678.205
AlphaGeometry599.684421.371398.340270.313
MNS1,021,553.8398,236.6365,967.6355,962.081

Complete execution after reformulation takes 0.569 seconds on ACRE, compared with 0.259 seconds for Learning, a 2.195× net speedup. The corresponding RAVEN-FAIR times are 12.665 and 8.205 seconds, a 1.544× net speedup. Native operations are further reduced by 74.975% and 52.934%, with accuracy maintained at 100.00% and 99.71%, respectively. Complete and selective execution after reformulation use the same answer criterion; the RAVEN-FAIR completion rule applies to the decomposed scorer. Table 1 in Section 4 of the revised paper describes the reformulations; Tables 2 and 3 in Section 5 report runtime across the three stages and work across the two transitions.

ACRE has only 384 queries. Is the accuracy improvement reliable?

We have expanded the evaluation to 2,000 problems and 8,000 queries. Baseline accuracy is 68.59%, while Learning achieves 100.00%, an improvement of 31.41 percentage points. Resampling by problem gives a 95% confidence interval of [30.25, 32.59] percentage points. Table 2 in Section 5 of the revised paper has been updated with accuracy and runtime at this scale; Appendix C.3 gives the evaluation settings.

Please report model size, input features, and training cost, and provide feature ablations.

All five tasks share the same policy. The graph policy and shared cost term have 21,219 parameters in total. The graph representation has 9 node types, 26 edge types, and 112-dimensional node fields. Inputs describe answer requirements, acquired evidence, candidate computations, and their dependencies. Object information describes what a computation involves, while evidence state indicates which work remains necessary. Execution uses a lightweight program extracted and refined from the graph policy.

The recorded training times are 1,400.64 seconds for the graph network and 22.09 seconds for the shared head. In the final round, cost collection at root and dynamic states took 36.96 seconds in total, and complete execution and selection of candidate policies took 10.82 seconds.

We fix the final model and separately mask two types of information on precomputed scoring inputs for 2,048 RAVEN-FAIR problems:

SettingLocal score evaluationsIncreaseAnswer changes
Complete model61,707—0
Without computation-object information85,03437.80%0
Without answer and evidence-progress information69,82413.15%0

Masking computation-object information increases score evaluations by 37.80%; masking answer and evidence-progress information increases them by 13.15%. All three settings return identical answers on every input. Appendices C.1–C.2 of the revised paper describe the model configuration and training objective.

Thank you again for your review. We clarified the stopping criteria for all five tasks in Table 1 and updated Table 2 to report the expanded ACRE evaluation on 8,000 queries. Please let us know if you have any further questions.

Thanks for the author's detailed response, which have addressed some of my concerns and helped improve the clarity of the paper. Additionally, the proposed method relies on task-specific completion rules, its applicability to other tasks still requires further validation. I will maintain my rating.

Reviewer_wmMZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates the problem of oversolving in reasoning systems. The authors define over solving as when a solver goes beyond what is needed to satisfy the answer requirements for a particular task. The paper proposes a theoretical lens to understand when an answer is determined and how it can precede a richer resolution of the task with additional justifications. Based on this, they propose a selective execution framework that learns which computations are relevant to determining an answer so that it can be prioritized over developing the more expensive, richer resolutions. The authors evaluate their approach on 5 structured reasoning tasks and report that their method leads to a significant reduction in task-specific computation while matching or improving over baselines.

Critical strengths
  1. The paper introduces a useful formulation to distinguish between answer determination and over-solving, which involves utilizing extra computations to produce richer explanations that are not always necessary to consider a given task as solved.
  2. The authors evaluate their method on diverse reasoning solver types that covers causal induction, geometric, relational and visual reasoning.
Critical weaknesses
  1. A main contribution of this paper is the learned answer-relevance function that would help prioritize which computations are performed in determining the answer quickly. This depends on being able to approximate how much computation remains after selecting a particular step, but it seems the actual training relies on successful reasoning traces, teacher outputs, and task-specific relevance labels. When the outcome is unknown, it is not clear that the next best computation to select is indeed the one that appears useful in hindsight from training examples. It is now clear how the training signals transfer to the learning objective, or that the answer relevance scores are meaningfully predictive of the amount of computation needed to reach an answer.

  2. Throughout the paper, there is no novel technical insight that separates the distinction between recovering an answer and recovering its complete explanation, or atleast it is presented in a very convoluted manner. The contribution appears general, but across the evaluated benchmarks, completely different completion conditions, supervision signals, and scoring architectures are employed. I am not fully convinced that there is a reusable algorithm that can be applied in any structured reasoning setting as presented by the paper, and am not able to clearly distinguish the technical insights that allow this.

Questions for authors
  1. What is the algorithmic component beyond the high level loop that is actually practical and useful for application in a given structured reasoning setting?
  2. Is it possible to design a task where the stopping condition is not simply hand designed and demonstrate that the approach works?
  3. Can the authors further clarify how training label are constructed generally, and how these signals translate to the learning objectives defined in the theory sections?
4 comments
AuthorsOpenReview ↗

Response to Reviewer wmMZ

Thank you for recognizing the distinction between answers and complete explanations, and the value of evaluation across tasks. We have added results on the shared algorithm, training objective, and automatic generation of stopping conditions.

The methods differ substantially across the five tasks. What exactly is the shared algorithm?

The shared components are a unified computational representation and a policy that learns computation order on this representation. The tasks execute different reasoning operations, but selecting computations requires the same information: what must be answered, what is already known, what can still be computed, and what those computations depend on. We organize this information into the same graph representation and use the same policy parameters to select the next computation. Task adapters provide rules and legal operations, while completion rules check whether the answer is determined.

This design follows from the distinction between an answer and a complete explanation: solving requires evidence sufficient to determine the answer. Reformulation first organizes computation around this requirement, and learning then compares the total work needed to complete a solution from different choices. The graph retains dependencies so that preparatory steps that do not yet determine the answer, but help subsequent reasoning, can also receive priority.

We first train a shared graph network, then extract and refine its policy into a lightweight program for execution. All five tasks use the same final policy parameters. Section 4 and Algorithm 1 of the revised paper describe the common representation and execution procedure; Appendices B and C provide the task interfaces and model configuration.

How do the training labels correspond to the theoretical objective? Can the scores predict how much computation is still needed to answer the query?

We construct labels from the measured cost of completing the query after alternative first actions, and the learned scores rank the lower-cost action first in 74.87% of unequal-cost pairs on RAVEN-FAIR. To obtain a label, we start from the same state, try a legal action, and record the cost of that action, all subsequent computations, and any required fallback. The training objective assigns lower energy to actions with lower completion cost. During refinement, the current policy selects the subsequent actions, so a preparatory step receives credit for work it saves later.

We evaluated this ordering at 2,048 RAVEN-FAIR states by trying each legal candidate and continuing with the final policy. Across 40,105 candidate pairs with different completion costs, the 95% confidence interval for ranking accuracy was 74.02%–75.71%. Sections 4.2–4.3 and Appendix C.2 describe the objective and loss.

Can you demonstrate a task whose stopping condition is generated automatically by a program?

Yes. The ACRE completion check is generated from the OR activation mechanism and object composition. We provide the program with the activation mechanism and the objects present in each observation and query. It generates possible observation outcomes and their corresponding answer categories. Each observation rules out incompatible cases, and execution can stop when all remaining cases imply the same answer category. Across 8,000 ACRE queries, this program returns the same answer on every query as complete execution after reformulation:

QueriesAccuracyQueries with answers differing from complete execution after reformulationReduction in observation checks
8,000100.00%074.975%

This procedure is generated from the supplied semantics, without specifying by hand which observations suffice for each query. Appendix B.1 of the revised paper gives the construction and its semantic basis.

Thank you again for your review. Revised Section 4 explains how the shared policy learns from completion costs, and Algorithm 1 shows when the executor stops. Please let us know if you have any further questions.

AuthorsOpenReview ↗

Further Response to Reviewer wmMZ

To further evaluate the unified model’s generalization beyond its training tasks, we conducted a zero-shot experiment on StepGame [1]. StepGame was not included in the original five-task training; evaluation directly uses the shared policy parameters obtained from joint training on those five tasks.

We reuse the spatial-relation rules from the public ASP solver [2], map reasoning states and legal operations into the unified representation, and stop when the relative coordinates required by the query are determined. The task interface supplies rules and answer conditions, while the original shared policy selects computations.

We compare Baseline, complete execution (Reformulated), a fixed heuristic (Fixed), and the frozen policy (Learning), with results below.

Table 1. Reasoning work and work reduction. The work unit is coordinate propagation.

TaskQueriesBaselineReformulatedFixedLearningReduction relative to ReformulatedAdditional reduction relative to Fixed
StepGame78,777647,899647,899348,694337,63247.89%3.17%

Table 2. Runtime and speedup. Baseline reuses the public ASP solver with a common parser. Fixed and Learning use the same incremental ASP backend, execution optimizations, legal operations, and completion rules. Timing includes policy execution overhead. Values are the mean total runtime across four measurements of the complete evaluation cohort.

TaskBaseline time / sFixed time / sLearning time / sBaseline / LearningFixed / Learning
StepGame164.69555.09554.9572.9968×1.0025×

All four methods return identical answers on the parseable test queries above, each achieving 100% accuracy.

The original shared policy achieves runtime comparable to Fixed after zero-shot transfer while further reducing computation, providing direct evidence of the unified model’s generalization beyond the five jointly trained tasks. When incorporating the new task, the interface supplies the semantics required for solving it, while computation selection uses the original shared policy. This further demonstrates the practical role of the unified representation and shared learning described in our previous response.

We welcome your further comments on this additional experiment and our previous response. If any aspects of the shared algorithm, training objective, or construction of stopping conditions remain unclear, we would be glad to discuss them further. Thank you for your time.

References

[1] Zhengxiang Shi, Qiang Zhang, and Aldo Lipani. StepGame: A New Benchmark for Robust Multi-Hop Spatial Reasoning in Texts. AAAI, 2022.

[2] Advancing Spatial Reasoning in Large Language Models: An In-depth Evaluation and Enhancement Using the StepGame Benchmark. AAAI, 2024.

AuthorsOpenReview ↗

Follow-up on Rebuttal

Dear Reviewer wmMZ,

Thank you again for your review. We have provided clarifications and additional experiments in our responses above to address the concerns you raised. We would appreciate it if you could review these updates and share your thoughts on whether any concerns remain. We would be happy to discuss any further questions.

Thank you for your time and consideration.

Thank you to the authors for responding to my comments and running new experiments. While some of the explanations have helped improve the paper understanding, I am not fully convinced that the method is generalisable or shows gains over fixed heuristics that warrant consideration. I therefore intend to maintain my score.

Reviewer_mFipOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

At a high level, the paper targets at avoiding unnecessary computation in structured reasoning. The authors address this problem by combining task-specific answer-determination conditions with learned computation priorities. Specifically, their methods contain two components. Given the current reasoning status (such as what is known, what remains unsolved), the first component helps decide whether whether the answer has already be determined. If no, second component will help decide next computation via a learned energy model. The reasoning state is then updated, and this process repeats until the answer is determined.

Additionally, the authors formalize answer determination and over-solving in structured reasoning using the set of answers compatible with currently available information. They show that an answer can become unique even when many underlying explanations remain possible, and that the set of possible answers contracts monotonically as information accumulates.

The evaluation on five related reasoning tasks show the proposed method is no worse than the baselines. The results suggest that answer-directed computation can be beneficial in structured domains, although the framework currently requires task-specific completion rules and supervision.

Critical strengths
  1. The paper presents a clear conceptual formulation of unnecessary computation in structured reasoning.
  2. Evaluation on five tasks show opportunities to eliminate unnecessary computation.
  3. Its primary practical contribution is demonstrating that several existing reasoning systems can be reformulated to terminate earlier without compromising the returned answer.
Critical weaknesses
  1. Per my understanding, the paper is primarily about structured reasoning systems where the task's mathematical structure can supply a rule for determining when further computation is unnecessary, which might limits its generalization.
  2. The learned model is meaningfully better than random ordering but only improves work reduction by 2.26 percentage points over the fixed heuristic. Additionally, fixed heuristic is faster than the proposed method.
Questions for authors
  1. Could the authors provide a more systematic decomposition of the reported speedups into gains from each component (e.g., reformulating the original solver, or answer-determined early termination)
  2. Could the authors clarify under what conditions the learned energy model provides a substantial advantage over inexpensive heuristic? From the ablation study, it seems the improvement is marginal and add latency overhead.
6 comments
AuthorsOpenReview ↗

Response to Reviewer mFip

Thank you for recognizing the value of the formalization and its practical potential for reducing computation across tasks. We address the benefits of learning and runtime overhead through a shared learned policy and comparisons on complete evaluation cohorts.

The method depends on task structure. How can it be applied to other tasks?

Adapting a task requires its reasoning operations, task rules, and answer requirements. The shared program organizes this information into a unified representation, maintaining acquired evidence and computations that remain to be performed. The same learner selects the next computation, and the completion rule checks whether the answer is determined. For declarative finite rules, the program generates answer constraints from the semantics; tasks with existing proof verification or score bounds reuse those checks. All five tasks use the same policy parameters. Section 4.1 and Table 1 of the revised paper describe the reformulations for the five tasks; Appendix B gives the construction of their completion rules.

What advantage does Learning offer over an inexpensive Fixed policy? Does scoring overhead offset the computation saved?

Learning can find a cheaper solving order when different computation orders incur different subsequent work and those differences are predictable from the current facts and dependencies. To reduce scoring overhead, we convert the trained policy into a lightweight program that executes directly. The table below compares the fixed heuristic (Fixed) and learned policy (Learning) in the current solvers. Both use the same inputs, reasoning operations, and completion rules. Native work measures the savings from computation order, while runtime includes each policy's execution and deployment overhead.

TaskReduction in native reasoning operations relative to FixedMeasured speedup over Fixed
ACRE1.807%34.023159×
CLUTRR5.112%1.370457×
RAVEN-FAIR0.155%1.421946×
AlphaGeometry6.804%1.473624×
MNS5.577%1.000931×

Learning reduces native operations relative to Fixed on all five tasks. On ACRE, it performs 1.807% fewer observation checks, while the measured wall-clock speedup is approximately 34×. The timing gain also reflects two implementation changes in the deployed policy: it combines selection with completion checking and reuses computations within each request. On CLUTRR, RAVEN-FAIR, and AlphaGeometry, the measured speedups range from 1.37× to 1.47×. On MNS, Learning checks 5.577% fewer candidate rows, but total runtime is nearly unchanged. Section 4.3 and Appendix C.2 describe policy extraction and execution.

How much of the system speedup comes from solver reformulation, and how much from selective execution?

We use Baseline→Reformulated to evaluate answer-directed reformulation and Reformulated→Learning to evaluate the additional selective execution. Reformulated executes the complete reformulated computation and already includes the benefit of changing the solving method around answer requirements. Learning then orders these computations and stops when the completion rule holds. Fixed provides a fixed-heuristic comparison using the same completion rules. The table below compares the original solver, complete execution after reformulation, the fixed heuristic, and the learned policy. Times are in seconds and include input processing, policy execution, verification, and solving.

TaskBaselineReformulatedFixedLearning
ACRE2,909.7780.5698.8250.259
CLUTRR20,396.3973.4283.4392.509
RAVEN-FAIR7,521.61112.66511.6678.205
AlphaGeometry599.684421.371398.340270.313
MNS1,021,553.8398,236.6365,967.6355,962.081

For example, ACRE takes 2,909.778 seconds with the original solver, 0.569 seconds with complete execution after reformulation, and 0.259 seconds with Learning; the corresponding RAVEN-FAIR times are 7,521.611, 12.665, and 8.205 seconds. Across the five tasks, selective execution further reduces native operations by 14.205%–92.760% relative to complete execution after reformulation, with 1.37–2.19× net speedup. In Section 5 of the revised paper, Table 2 reports runtime and accuracy for the three stages, Table 3(a) shows the computations replaced by reformulation, and Table 3(b) reports native work saved after reformulation.

Thank you again for your review. Section 5 now reports the savings from solver reformulation and the additional savings from selective execution separately in Tables 2 and 3. Please let us know if you have any further questions.

I appreciate the authors' detailed rebuttal and the substantial revisions to the paper. In particular, the new comparisons separating solver reformulation from selective execution help clarify the sources of the reported speedups. The unified representation and shared learned policy also provide a clearer picture of how the proposed framework can be applied across different tasks.

However, I remain unconvinced about the incremental benefit of the learned policy over a simple fixed heuristic. The reported reductions in native reasoning operations are relatively small (0.155%–6.804%), while some runtime improvements are substantially larger. For example, ACRE achieves a 34× speedup with only 1.807% fewer operations, partly due to additional implementation optimizations. This makes it difficult to isolate the benefit of learning itself. A comparison using the same execution optimizations for both Fixed and Learning would be more convincing.

Overall, while the revisions meaningfully address my concern about the original speedup comparisons, the contribution of the learned policy remains insufficiently established. I therefore intend to maintain my original score.

AuthorsOpenReview ↗

Further Response to Reviewer mFip

Thank you for your quick feedback. We would like to further point out that Learning’s contribution cannot be assessed solely by its additional speedup over Fixed. We provide a computation-selection method that can be reused across reasoning tasks, allowing computation allocation to be learned jointly and reducing the need to design and tune separate ordering strategies for each task. Using the same final policy parameters across five heterogeneous tasks demonstrates this cross-task applicability. Fixed is a baseline for evaluating its efficiency; the incremental gain over Fixed is one aspect of the value of shared learning.

Following your suggestion, we applied the same execution optimizations to both methods. Results on the complete evaluation cohorts are below:

TaskAdditional native work reduction relative to FixedFixed / Learning runtime ratio
ACRE1.81%1.968×
CLUTRR5.11%1.001×
AlphaGeometry6.80%1.034×
RAVEN-FAIR0.25%1.003×
MNS5.58%1.001×

The same learned policy achieves measured runtime comparable to or better than the fixed policies used in the five heterogeneous tasks, while further reducing computation and returning identical answers on every evaluated input. This addresses the fair-comparison concern and demonstrates the practical value of shared learning across tasks.

We hope the additional controlled comparisons and clarifications address your concerns about the learned policy’s contribution. Thank you for your time and constructive feedback.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response to All Reviewers

We thank the reviewers and area chairs for their careful reading and constructive feedback. Your questions helped us clarify how the method applies across tasks, when a solver can stop, and how much computation each component saves. We especially appreciate the reviewers’ recognition of the paper’s central observation that a query can have a definite answer even when several explanations remain possible.

We have developed this idea into a unified learning framework for structured reasoning. We first shift the solver’s objective from recovering a complete model or computing every candidate’s full score to determining the answer to the current query. All five tasks use the same computational representation and the same learned policy parameters. This answer-directed reformulation allows a solver to establish that a combination of objects activates a machine while one object’s causal role remains unknown, or to identify the winning candidate while some scores remain incomplete. The shared policy selects the next computation, and execution stops as soon as the task’s completion rule confirms that the available evidence determines the answer.

We compare three versions of each solver. Baseline is the original solver, Reformulated executes all prescribed computations after answer-directed reformulation, and Learning adds the shared policy and certificate-based stopping to the reformulated solver. The first table reports accuracy and total solving time for all three versions. The second shows how much additional computation Learning saves relative to Reformulated on the same inputs.

Overall Table 1. Accuracy and total solving time on the five evaluation cohorts. The overall speedup is the Baseline time divided by the Learning time.

TaskQueriesBaseline accuracyReformulated accuracyLearning accuracyBaseline time / sReformulated time / sLearning time / sOverall speedup
ACRE8,00068.59%100.00%100.00%2,909.7780.5690.25911,218.70×
CLUTRR86464.70%81.25%81.25%20,396.3973.4282.5098,128.70×
RAVEN-FAIR2,04886.57%99.71%99.71%7,521.61112.6658.205916.70×
AlphaGeometry23185.71%85.71%85.71%599.684421.371270.3132.22×
MNS56,00075.97%79.11%79.11%1,021,553.8398,236.6365,962.081171.34×

Baseline versus Reformulated shows the system changes from answer-directed reformulation; Reformulated versus Learning shows the runtime effect of adding the shared policy and certificate-based stopping. Timing for all versions covers input-dependent processing, control, verification, and actual solving.

Table 2. Reduction in native reasoning work under the unified representation. We compare the computations actually executed by Reformulated and Learning on the same inputs, with the same solving representation and definitions of native operations:

TaskQueriesNative work unitReformulated workLearning workNative reasoning reduction
ACRE8,000Observation checks48,00012,01274.975%
CLUTRR864Relation pairs and splits46,57013,55070.904%
RAVEN-FAIR2,048Local score evaluations131,07261,69052.934%
AlphaGeometry231Matching calls26,93423,10814.205%
MNS56,000Candidate-check rows507,548,94336,748,10792.760%

Learning matches or improves on the original solver’s accuracy across the five cohorts, with overall speedups from 2.22× to 11,218.70×. Within the reformulated solvers, it returns the same answer as complete execution on every evaluated input while eliminating 14.205%–92.760% of native operations. The corresponding incremental speedups range from 1.366× to 2.195×. Section 4 and Algorithm 1 describe the shared method. Tables 2 and 3 of the revised paper report the two stages of the comparison, and Appendix B gives the conditions under which each task can stop.

We kindly refer you to the revised paper for the updated results and discussions. Once again, we greatly appreciate your thoughtful review and constructive feedback.

AuthorsOpenReview ↗

Further General Response to All Reviewers

We thank the reviewers for acknowledging the clearer explanation of the unified representation and shared policy, as well as the improved clarity of the experimental comparisons. To address the questions about generalization and task-specific interfaces raised during the discussion, we conducted a zero-shot experiment on StepGame [1], directly evaluating the original shared policy beyond its training tasks.

StepGame was not included in the original five-task training; evaluation directly uses the shared policy parameters obtained from joint training on those five tasks. We reuse the spatial-relation rules from the public ASP solver [2], map reasoning states and legal operations into the unified representation, and stop when the relative coordinates required by the query are determined. The task interface supplies the rules and answer conditions required for solving, while the original shared policy selects computations.

Following the comparisons in our previous general response, we report results for Baseline, complete execution (Reformulated), and Learning, and include Fixed as a reference for computation-selection efficiency.

Given the documented template errors in the dataset version used [2], we compare all four methods on the same 78,777 test queries supported by the common parser.

Additional Table 1. Reasoning work and work reduction. The work unit is coordinate propagation.

TaskQueriesBaselineReformulatedFixedLearningReduction relative to ReformulatedAdditional reduction relative to Fixed
StepGame78,777647,899647,899348,694337,63247.89%3.17%

Additional Table 2. Runtime and speedup. Baseline reuses the public ASP solver with a common parser. The three unified versions share the incremental ASP backend and execution optimizations; Fixed and Learning use the same legal operations and completion rules. Timing covers input processing, control, verification, and actual solving. Values are the mean total runtime across four measurements of the complete evaluation cohort.

TaskBaseline time / sReformulated time / sFixed time / sLearning time / sBaseline / LearningFixed / Learning
StepGame164.69592.78655.09554.9572.9968×1.0025×

All four methods return identical answers on the parseable test queries above, each achieving 100% accuracy.

This experiment provides direct evidence of generalization beyond the five jointly trained tasks: on an unseen task, the original shared policy eliminates 47.89% of the reasoning work required by complete execution and reduces work by a further 3.17% relative to Fixed while achieving comparable runtime. Shared learning therefore also contributes through the transfer of learned computation-selection capabilities to new tasks, beyond its additional speedup over Fixed.

Task-specific adapters and completion rules do not imply that the computation-selection algorithm itself is task-specific. Section 4.1 and Appendix B explain their respective roles: interfaces provide task rules, legal computations, and answer requirements, while the shared policy selects the next computation. The StepGame results further validate this division: once the new task’s semantics are supplied, the original policy continues to select computations, demonstrating that task-specific completion rules do not restrict its applicability to the training tasks.

Our previous responses explained how five heterogeneous tasks share a unified representation, learning objective, and policy parameters. This additional experiment demonstrates zero-shot transfer of that same policy to an unseen task. We hope these clarifications and measured results address the questions raised during the discussion about algorithmic generality and applicability to new tasks.

We thank the reviewers and area chairs for their time and welcome further discussion.

References

[1] Zhengxiang Shi, Qiang Zhang, and Aldo Lipani. StepGame: A New Benchmark for Robust Multi-Hop Spatial Reasoning in Texts. AAAI, 2022.

[2] Advancing Spatial Reasoning in Large Language Models: An In-depth Evaluation and Enhancement Using the StepGame Benchmark. AAAI, 2024.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.