CAPS: Cascaded Adaptive Pairwise Selection for Efficient Parallel Reasoning

• URL: http://arxiv.org/abs/2605.15513v1
• Date: Fri, 15 May 2026 01:16:12 GMT
• Title: CAPS: Cascaded Adaptive Pairwise Selection for Efficient Parallel Reasoning
• Abstract summary: CAPS is an inference-only framework that allocates verifier compute non-uniformly along two axes.<n> CAPS outperforms the leading pairwise verifier on 14 of 20 suites while using 25.4% of its verifier-token budget on code.
• Score: 24.596125996494717
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Parallel reasoning, where a generator samples many candidate solutions and an aggregator selects the best, is one of the most effective forms of test-time scaling in large language models, and pairwise self-verification has become its strongest aggregation primitive. Yet pairwise verification carries a heavy cost: each judgment reads two complete solutions in full, and existing methods perform tens of such judgments per problem regardless of whether the comparison is informative. We introduce CAPS (Cascaded Adaptive Pairwise Selection), an inference-only framework that allocates verifier compute non-uniformly along two orthogonal axes: an evidence axis that adapts how much of each candidate the judge sees, and a distribution axis that adapts how comparisons are spread across the pool. CAPS instantiates these into a four-stage cascade with an optional rescue subroutine, and admits a closed-form verifier-token cost in which the per-candidate marginal cost is roughly halved relative to uniform full-evidence schedules. On four self-verifying models (Qwen3-14B, GPT-OSS-20B, Qwen3-4B-Instruct/Thinking) and five reasoning benchmarks spanning code (LiveCodeBench-v5/v6, CodeContests) and math (AIME 2025, HMMT 2025), CAPS outperforms the leading pairwise verifier on 14 of 20 suites while using 25.4% of its verifier-token budget on code, and outperforms pointwise self-verification on all 20. The trade-off suites admit an interpretable diagnostic in terms of the verifier's accuracy at partial versus full evidence, providing a concrete pre-deployment check for cascade suitability.

Related papers

• Beyond QA Matching: Perturbation-Response Fingerprinting via Probability Distributions for Large Language Models [12.84004924761875]
  We introduce BReF, a training-free fingerprint that compares how probability distributions over four answer-option labels A/B/C/D move under controlled perturbations.<n>On a unified benchmark with 34 checkpoints, 22 documented direct-parent relations, and 411 suspect-candidate pairs, BReF retrieves the documented parent in 22/22 cases.<n>Same-family discrimination is harder, and paired tests show a significant exact-retrieval gain over a magnitude-only Top-25 control.
  arXiv  Detail & Related papers  (2026-09-06T01:35:07Z)
• Claim-Level Reliability Assessment for Efficient Test-Time Reasoning [9.168249719115845]
  We propose claim-level falsification as a principle for test-time scaling and instantiate it through Claim-Level Reliability Assessment (CLR)<n>CLR reallocates test-time compute from additional solution sampling to targeted verification.
  arXiv  Detail & Related papers  (2026-08-12T12:33:05Z)
• Conformal Cascade: Distribution-Free Accuracy Guarantees for Multi-Tier LLM Inference [6.094431019524038]
  Large language model (LLM) cascades reduce inference cost by routing easy queries to a small model and deferring hard queries to a larger one.<n>We introduce textbfConformal Cascade (CC), a multi-tier inference framework that uses conformal prediction set size as the deferral rule.
  arXiv  Detail & Related papers  (2026-07-27T19:19:58Z)
• Auditing Question-Order Effects in Large Language Models with the QQ Equality: Mechanism Characterization and a Saturation Caveat [4.07636450847048]
  Human survey respondents exhibit question-order effects that satisfy the QQ (quantum question) equality.<n>We develop the QQ equality into an audit criterion for sequential judgments of autoregressive large language models.
  arXiv  Detail & Related papers  (2026-07-19T12:22:06Z)
• FineVerify: Scaling Test-Time Compute with Fine-Grained Self-Verification for Agentic Search [88.16262636915975]
  FineVerify is a fine-grained self-verification framework for agentic search.<n>It decomposes each question into checkable sub-questions, verifies sampled candidates, and selects the candidate with the highest aggregated score.<n>FineVerify consistently outperforms standard scaling baselines.
  arXiv  Detail & Related papers  (2026-05-30T10:21:20Z)
• Pause and Reflect: Conformal Aggregation for Chain-of-Thought Reasoning [8.024041325202612]
  Chain-of-thought (CoT) reasoning with self-consistency improves performance by aggregating multiple sampled reasoning paths.<n>We introduce a conformal procedure for CoT reasoning that directly addresses aggregation uncertainty.<n>Our approach replaces majority voting with weighted score aggregation over reasoning paths and calibrates an abstention rule using conformal risk control.
  arXiv  Detail & Related papers  (2026-05-13T20:33:59Z)
• Calibrated Speculative Decoding: Frequency-Guided Candidate Selection for Efficient Inference [27.59556627479635]
  Calibrated Speculative Decoding recovers valid tokens discarded by standard verification.<n>Online Correction Memory aggregates historical rejections to propose recurring divergence patterns as rescue candidates.<n>Semantic Consistency Gating verifies candidate admissibility using probability ratios instead of exact token matching.
  arXiv  Detail & Related papers  (2026-04-15T09:01:54Z)
• $V_1$: Unifying Generation and Self-Verification for Parallel Reasoners [69.66089681814013]
  $V_$ is a framework that unifies generation and verification through efficient pairwise ranking.<n>$V_$-Infer improves Pass@1 by up to $10%$ over pointwise verification.<n>$V_$-PairRL achieves $7$--$9%$ test-time scaling gains over standard RL and pointwise joint training.
  arXiv  Detail & Related papers  (2026-03-04T17:22:16Z)
• PRIME: A Process-Outcome Alignment Benchmark for Verifiable Reasoning in Mathematics and Engineering [71.15346406323827]
  We introduce PRIME, a benchmark for evaluating verifiers on Process-Outcome Alignment verification.<n>We find that current verifiers frequently fail to detect derivation flaws.<n>We propose a process-aware RLVR training paradigm utilizing verifiers selected via PRIME.
  arXiv  Detail & Related papers  (2026-02-12T04:45:01Z)
• Scaling Agentic Verifier for Competitive Coding [66.11758166379092]
  Large language models (LLMs) have demonstrated strong coding capabilities but still struggle to solve competitive programming problems correctly in a single attempt.<n>Execution-based re-ranking offers a promising test-time scaling strategy, yet existing methods are constrained by either difficult test case generation or inefficient random input sampling.<n>We propose Agentic Verifier, an execution-based agent that actively reasons about program behaviors and searches for highly discriminative test inputs.
  arXiv  Detail & Related papers  (2026-02-04T06:30:40Z)
• Adaptive Test-Time Compute Allocation via Learned Heuristics over Categorical Structure [1.8055130471307603]
  Test-time computation has become a primary driver of progress in large language model (LLM) reasoning.<n>We study reasoning under a emphverification-cost-limited setting and ask how verification effort should be allocated across intermediate states.<n>We propose a state-level selective verification framework that combines (i) deterministic feasibility gating over a structured move interface, (ii) pre-verification ranking using a hybrid of learned state-distance and residual scoring, and (iii) adaptive allocation of verifier calls based on local uncertainty.
  arXiv  Detail & Related papers  (2026-02-03T19:57:53Z)
• ZIP-RC: Optimizing Test-Time Compute via Zero-Overhead Joint Reward-Cost Prediction [57.799425838564]
  We present ZIP-RC, an adaptive inference method that equips models with zero-overhead inference-time predictions of reward and cost.<n> ZIP-RC improves accuracy by up to 12% over majority voting at equal or lower average cost.
  arXiv  Detail & Related papers  (2025-12-01T09:44:31Z)
• Eigen-1: Adaptive Multi-Agent Refinement with Monitor-Based RAG for Scientific Reasoning [53.45095336430027]
  We develop a unified framework that combines implicit retrieval and structured collaboration.<n>On Humanity's Last Exam (HLE) Bio/Chem Gold, our framework achieves 48.3% accuracy.<n>Results on SuperGPQA and TRQA confirm robustness across domains.
  arXiv  Detail & Related papers  (2025-09-25T14:05:55Z)
• S$^4$C: Speculative Sampling with Syntactic and Semantic Coherence for Efficient Inference of Large Language Models [38.784951111677856]
  Large language models (LLMs) exhibit remarkable reasoning capabilities across diverse downstream tasks.<n>Their autoregressive nature leads to substantial latency inference, posing challenges for real-time applications.<n>We propose a Speculative Sampling with Syntactic and Semantic Coherence framework, which extends speculative sampling by leveraging multi-head drafting.
  arXiv  Detail & Related papers  (2025-06-17T03:38:19Z)
• Self-Evaluation Guided Beam Search for Reasoning [61.523627290397556]
  We introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of Large Language Model (LLM) We propose a decoding algorithm integrating the self-evaluation guidance via beam search. Our approach surpasses the corresponding Codex-backboned baselines in few-shot accuracy by $6.34%$, $9.56%$, and $5.46%$ on the GSM8K, AQuA, and StrategyQA.
  arXiv  Detail & Related papers  (2023-05-01T02:37:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.