Lateral Tree-of-Thoughts Surpasses ToT by Incorporating Logically-Consistent, Low-Utility Candidates

• URL: http://arxiv.org/abs/2510.01500v1
• Date: Wed, 01 Oct 2025 22:23:58 GMT
• Title: Lateral Tree-of-Thoughts Surpasses ToT by Incorporating Logically-Consistent, Low-Utility Candidates
• Abstract summary: Lateral Tree-of-Thoughts (LToT) is a drop-in controller that separates utility from logical consistency and treats low-utility but consistent candidates as assets rather than waste.<n>LToT explores laterals via Lateral Racing with Short-Circuit (LR--SC), a capped successive-halving race that spreads tiny probes across a very wide lateral set.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern deployments increasingly allocate large test-time compute (thousands of tokens or many node expansions) to boost reliability. Under such budgets, standard Tree-of-Thoughts-style search exhibits two pathologies: breadth saturation (additional samples mostly produce near-duplicates, so width stops growing) and depth myopia (noisy short-horizon utilities prune branches whose payoff appears after a few more steps). We propose Lateral Tree-of-Thoughts (LToT), a drop-in controller that separates utility from logical consistency and treats low-utility but consistent candidates as assets rather than waste. The frontier is split into mainlines (high-utility candidates used for exploitation) and laterals (consistent, initially low-utility candidates that receive short, cheap probes before judgment). LToT explores laterals via Lateral Racing with Short-Circuit (LR--SC): a capped successive-halving race that spreads tiny probes across a very wide lateral set, uses width-aware thresholds with repeat-to-confirm, and immediately promotes a branch once its envelope clears the mainline bar; mainlines are kept intentionally narrow so surplus compute is invested where width is cheap. We prove a pseudolinear lateral cost $\Theta(N_0 \log_{\eta} N_0)$ with logarithmically many rungs (initial lateral width $N_0$; culling factor $\eta>1$), in contrast to the exponential growth of uncapped mainlines. Empirical evaluations on benchmark tasks are in preparation and will be added in a future revision. In short, LToT turns large test-time budgets into principled diversity while preserving promotion discipline, mitigating saturation and myopia without inflating compute.

Related papers

• ECHO: Early-layer Collaborative Hierarchical Orchestration with Bonus Logits in Speculative Decoding [60.34475274870224]
  ECHO is a hierarchical dual-loop framework that exploits the functional asymmetry between LLM layers.<n>Within the inner loop, early-layer bonus logits drive rapid, multi-step draft-tree exploration at a minimal cost.<n>ECHO significantly boosts mean accepted tokens and achieves a 2.4$times$ to 2.9$times$ speedup.
  arXiv  Detail & Related papers  (2026-09-15T14:21:33Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Latent Recurrent Thoughts: Recurrent Refinement of Proposed Latents for Reasoning with Frozen LLMs [16.72007494160683]
  Chain-of-thought reasoning unfolds in discrete token space.<n> Reasoning instead in a model's continuous representation space.<n>We instantiate this as Latent Recurrent Thoughts.
  arXiv  Detail & Related papers  (2026-09-01T11:56:17Z)
• PRESTO: Prefix-Aligned Tree Drafting for Diffusion Speculative Decoding [98.71600061506206]
  We propose PRESTO, a principled framework that extends tree-based drafting to diffusion drafters.<n> PRESTO achieves up to an average of $1.5times$ end-to-end throughput speedup on the state-of-the-art dedicated diffusion drafter SD.
  arXiv  Detail & Related papers  (2026-06-20T14:32:14Z)
• Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret [1.0098114696565863]
  Queue length regret is defined as the expected difference between the learner's and oracle's queue lengths at horizon $T$.<n>In this paper, we improve this rate to $widetildemathcalO(T-1/2)$.
  arXiv  Detail & Related papers  (2026-06-08T15:51:25Z)
• Draft Less, Retrieve More: Hybrid Tree Construction for Speculative Decoding [27.332123289262086]
  Graft is a compensation framework that couples pruning and retrieval as mutually reinforcing operations.<n>On short-context benchmarks, it achieves up to 5.41$times$ speedup and improves average speedup by up to 21.8% on the large-scale Qwen3-235B.<n>We also provide a preliminary exploration of applying Graft to the DFlash-style block drafting paradigm, offering initial evidence and insights for extending grafting beyond autoregressive draft trees.
  arXiv  Detail & Related papers  (2026-05-19T16:55:48Z)
• Parallel-Probe: Towards Efficient Parallel Thinking via 2D Probing [76.48164395646019]
  Parallel-Probe is a training-free controller designed to optimize online parallel thinking.<n>It reduces sequential tokens by up to $textbf35.8$% and total token cost by over $textbf25.8$% while maintaining competitive accuracy.
  arXiv  Detail & Related papers  (2026-02-03T18:59:41Z)
• Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks [39.54576236079211]
  Speculative generation has emerged as a promising technique to accelerate inference in large language models.<n>In this work, we establish the first tight'' lower bounds on the runtime of any deterministic speculative generation algorithm.
  arXiv  Detail & Related papers  (2025-12-12T16:54:33Z)
• DiNo and RanBu: Lightweight Predictions from Shallow Random Forests [2.2080796858692575]
  DiNo and RanBu convert a small set of depth-limited trees into efficient, distance-weighted predictors.<n>RanBu matches or exceeds the accuracy of full-depth random forests in high-noise settings.<n>Both methods extend directly to quantile regression, maintaining accuracy with substantial speed gains.
  arXiv  Detail & Related papers  (2025-10-23T20:12:08Z)
• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  Reasoning training incentivizes LLMs to produce long chains of thought (long CoT), which allows them to explore solution strategies with self-checking.<n>This results in higher accuracy, but inflates context length, token/compute cost, and answer latency.<n>We ask: Can current models leverage their metacognition to provide other combinations on this Pareto frontier?<n>We identify an interesting inference family Parallel-Distill-Refine (PDR), which performs the following: (i) generate diverse drafts in parallel; (ii) distill them into a bounded, textual workspace; and (iii) refine conditioned on this workspace
  arXiv  Detail & Related papers  (2025-10-01T17:08:59Z)
• Pipeline Parallelism is All You Need for Optimized Early-Exit Based Self-Speculative Decoding [73.67253077506672]
  Large language models (LLMs) deliver impressive generation quality, but incur very high inference cost.<n>Early-exit based self-speculative decoding (EESD) has emerged to mitigate this cost.<n>We propose Pipeline-Parallel Self-Speculative Decoding (PPSD) that fully pipelines the draft and verification work.
  arXiv  Detail & Related papers  (2025-09-19T04:51:41Z)
• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  We propose and analyze TRAiL, a regret-optimal forced exploration algorithm for linear bandits. TraiL ensures a $Omega(sqrtT)$ growth in the inference quality, measured via the minimum eigenvalue of the design (regressor) matrix. We characterize an $Omega(sqrtT)$ minimax lower bound for any algorithm on the expected regret.
  arXiv  Detail & Related papers  (2024-11-19T01:08:13Z)
• Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
  We investigate the high-dimensional sparse linear bandits problem in a data-poor regime.<n>We show novel offline statistical guarantees of the lasso estimator for the linear model.<n>We propose a meta-algorithm based on corralling that does not need knowledge of optimal sparsity parameter $k$ at minimal cost to regret.
  arXiv  Detail & Related papers  (2024-10-26T01:42:03Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  We study high-dimensional multi-armed contextual bandits with batched feedback where the $T$ steps of online interactions are divided into $L$ batches. In specific, each batch collects data according to a policy that depends on previous batches and the rewards are revealed only at the end of the batch. Our algorithm achieves regret bounds comparable to those in fully sequential setting with only $mathcalO( log T)$ batches.
  arXiv  Detail & Related papers  (2023-11-22T06:06:54Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
  arXiv  Detail & Related papers  (2023-02-02T18:59:30Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  We study the optimal batch-regret tradeoff for batch linear contextual bandits. We prove its regret guarantee, which features a two-phase expression as the time horizon $T$ grows. We also prove a new matrix inequality concentration with dependence on their dynamic upper bounds.
  arXiv  Detail & Related papers  (2021-10-15T12:32:33Z)
• A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
  We introduce a general analysis framework and a family of algorithms for the linear bandit problem. Our new notion of optimism in expectation gives rise to a new algorithm, called sieved greedy (SG) that reduces the overexploration problem in OFUL. In addition to proving that SG is theoretically rate optimal, our empirical simulations show that SG outperforms existing benchmarks such as greedy, OFUL, and TS.
  arXiv  Detail & Related papers  (2020-02-12T18:54:41Z)

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.