{"id":"4e31787c-92f3-4dbc-afc2-fc7833bcb1e4","arxiv_id":"2603.11161","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Infinite-width transformers exhibit an inductive bias against high-complexity polynomial-time algorithms, with derived upper bounds on capturable tasks like sorting and string matching.","lead":"The paper defines algorithmic capture as a transformer's ability to extrapolate combinatorial tasks to arbitrary sizes with controllable error using logarithmic samples. This criterion helps distinguish true logic internalization from statistical interpolation in large models.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Infinite-width lazy/rich regime bounds may not govern finite-model extrapolation used in empirical capture tests","rationale":"Reader correctly flags the capture definition as pivotal, but the more immediate gap is the unbridged infinite-to-finite transfer; both point to the same risk that the separation between internalization and interpolation is not yet rigorously established for the models studied.","tokens_in":1645,"tokens_out":294,"duration_ms":25397,"concrete_test":"Fix a task (e.g., length-n string matching) and recompute the infinite-width complexity bound; then train finite-width (width=512) models to the same capture criterion and measure effective inference complexity via circuit depth or FLOPs on n=10^4 inputs; if the finite-width complexity exceeds the infinite bound by more than a constant factor while still satisfying controllable error, the transfer fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Upper bounds on inference-time complexity are derived only for infinite-width transformers (lazy and rich regimes). Empirical capture results (extrapolation on sort, string matching, induction heads) are obtained with finite-width models. No explicit argument or limit theorem is given showing that the complexity restriction survives the finite-width regime or that the logarithmic-sample-adaptation property is preserved; if the bias is an infinite-width artifact, the claimed inductive bias against higher-complexity polynomial-time procedures does not follow for the models actually tested.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.3","summary":"The paper formally defines algorithmic capture of combinatorial tasks as extrapolation to arbitrary sizes with controllable error and logarithmic sample adaptation. It reports empirical evidence of capture on simpler tasks (induction heads, sort, string matching) across scaling ranges up to 2.5 orders of magnitude, and non-capture on others. For infinite-width transformers in lazy and rich regimes, it derives upper bounds on inference-time computational complexity, concluding that transformers possess an inductive bias disfavoring higher-complexity polynomial-time heuristic procedures despite universal expressivity.","tokens_in":1761,"tokens_out":464,"duration_ms":21166,"significance":"If the central claims hold, the work supplies a sharp scaling criterion to separate logic internalization from statistical interpolation and supplies explicit complexity upper bounds that could explain observed transformer biases toward simpler algorithmic procedures. The combination of a formal capture definition with regime-specific bounds is a substantive contribution to understanding inductive bias in sequence models.","major_comments":[{"comment":"The upper bounds on inference-time complexity are derived exclusively for infinite-width transformers in the lazy and rich regimes, yet the empirical capture results (extrapolation on sort, string matching, induction heads) are obtained with finite-width models. No explicit limit theorem or continuity argument is provided showing that the complexity restriction or the logarithmic-sample-adaptation property survives the finite-to-infinite transition.","section":"theoretical analysis of infinite-width regimes"},{"comment":"The central claim that transformers disfavor higher-complexity procedures within the efficient polynomial-time heuristic scheme class rests on the infinite-width bounds; without a bridging result to finite models, the inductive-bias conclusion does not directly apply to the networks tested in the empirical sections.","section":"discussion of inductive bias"}],"minor_comments":[{"comment":"Empirical scaling plots lack error bars, data-exclusion criteria, and any statement of the number of random seeds or training runs.","section":"empirical results"},{"comment":"The manuscript does not indicate whether code or trained models will be released, which would be required to verify the reported capture thresholds.","section":"experimental setup"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the constructive comments. We address the two major points below, acknowledging the gap between the infinite-width analysis and finite-width experiments.","responses":[{"response":"We agree that the upper bounds are derived strictly for the infinite-width limit in both regimes, while all empirical capture results use finite-width models, and no explicit limit theorem or continuity argument is supplied. This is a genuine limitation of the current manuscript. In the revision we will insert a new subsection in the discussion that explicitly states the bounds apply only in the infinite-width case and that the finite-width experiments are presented as consistent empirical illustrations rather than as a proof that the bounds carry over exactly.","revision_made":"yes","referee_comment":"The upper bounds on inference-time complexity are derived exclusively for infinite-width transformers in the lazy and rich regimes, yet the empirical capture results (extrapolation on sort, string matching, induction heads) are obtained with finite-width models. No explicit limit theorem or continuity argument is provided showing that the complexity restriction or the logarithmic-sample-adaptation property survives the finite-to-infinite transition."},{"response":"The referee correctly notes that the inductive-bias claim, as currently worded, depends on the infinite-width bounds. We do not possess a bridging result, so the precise complexity upper bounds cannot be asserted for the finite-width networks used in the experiments. In revision we will qualify the relevant statements in the abstract, introduction, and conclusion to make clear that the disfavoring of higher-complexity procedures is established for infinite-width transformers, while the finite-width results provide supporting evidence of capture on simpler tasks.","revision_made":"yes","referee_comment":"The central claim that transformers disfavor higher-complexity procedures within the efficient polynomial-time heuristic scheme class rests on the infinite-width bounds; without a bridging result to finite models, the inductive-bias conclusion does not directly apply to the networks tested in the empirical sections."}],"tokens_in":1273,"tokens_out":424,"duration_ms":32856,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's main move is to define algorithmic capture as extrapolation to arbitrary task sizes with controllable error after only logarithmic samples. This gives a sharper way to separate internalized algorithms from plain interpolation than just looking at test accuracy on fixed sizes. They show capture on induction heads, sort, and string matching over scaling ranges up to 2.5 orders of magnitude, and non-capture on harder cases, which lines up with the claim that transformers favor lower-complexity polynomial procedures.","headline":"The new definition of algorithmic capture is a clean framing, but the infinite-width complexity bounds don't clearly transfer to the finite models in the experiments.","tokens_in":2211,"tokens_out":168,"would_cite":false,"duration_ms":30932,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"By analyzing infinite-width transformers in both the lazy and rich regimes, we derive upper bounds on the inference-time computational complexity... O(P N_MC T^3)"},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/RealityFromDistinction.lean","rs_theorem":"reality_from_one_distinction","paper_passage":"transformers possess an inductive bias that disfavors higher-complexity algorithmic procedures within the efficient polynomial-time heuristic scheme class"}],"headline":"Infinite transformer NTK complexity bounds unrelated to RS forcing from distinction","alignment":"orthogonal","rationale":"Paper centers on algorithmic capture definition, NNGP/NTK kernel propagation for infinite-width transformers, and O(T^{3+ε}) inference bounds from Monte Carlo covariance evaluation (Sec. 4.4, App. D-E). No use of J-cost functional equations, φ-ladder, 8-tick periodicity, or parameter-free constant derivations. Domain (cs.LG inductive bias) has no overlap with RS foundation chain.","tokens_in":59485,"confidence":"high","tokens_out":295,"duration_ms":13476,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Transformers possess an inductive bias that disfavors higher-complexity algorithmic tasks despite universal expressivity.","keywords":["algorithmic capture","inductive bias","infinite transformers","computational complexity","combinatorial tasks","scaling","lazy regime","rich regime"],"falsifier":"Demonstrating that an infinite transformer captures a higher-complexity polynomial-time task, such as a specific quadratic heuristic, by extrapolating to arbitrary sizes with controllable error and logarithmic samples would falsify the claimed upper bounds.","tokens_in":2544,"feed_emoji":"🤖","tokens_out":540,"duration_ms":45217,"temperature":0.7,"pith_summary":"The paper defines algorithmic capture as the ability of a transformer to extrapolate combinatorial tasks to arbitrary sizes with controllable error and only logarithmic sample adaptation. This definition supplies a scaling criterion that separates genuine logic internalization from statistical interpolation. Analysis of infinite-width transformers in lazy and rich regimes produces upper bounds on the inference-time computational complexity of tasks that can be captured. The resulting inductive bias is consistent with observed capture on low-complexity tasks such as induction heads, sorting, and string matching. A sympathetic reader would care because the bias explains why scaling succeeds on some algorithmic problems but encounters hard limits on others.","feed_headline":"Transformers bias against complex algorithms despite universal power","feed_subtitle":"Infinite-width analysis yields upper bounds on capturable task complexity, matching success on sort but limiting harder procedures.","key_machinery":"Algorithmic capture, defined as extrapolation to arbitrary task sizes with controllable error and logarithmic sample adaptation, serves as the scaling criterion that distinguishes logic internalization from statistical interpolation.","core_discovery":"Infinite transformers exhibit an inductive bias that disfavors higher-complexity algorithmic procedures within the efficient polynomial-time heuristic scheme class. Despite their universal expressivity, analysis in both lazy and rich regimes derives upper bounds on the inference-time computational complexity of the combinatorial tasks these networks can capture, and this is consistent with successful capture on simpler tasks such as induction heads, sort, and string matching.","pith_inferences":["The bias may limit performance on complex reasoning benchmarks even when models are scaled further.","Architectures that alter the lazy or rich regime dynamics could potentially raise the complexity ceiling.","Similar capture definitions could be applied to other architectures to compare their inductive biases on algorithmic tasks."],"forward_implications":["Transformers capture simpler combinatorial tasks such as induction heads, sorting, and string matching.","Higher-complexity procedures within the efficient polynomial-time class are disfavored by the inductive bias.","Upper bounds exist on the inference-time computational complexity of capturable tasks.","Empirical scaling across up to 2.5 orders of magnitude shows both capture and non-capture regimes."],"fun_headline_variants":["Transformer inductive bias limits complex task capture","Analysis bounds capturable complexity in infinite transformers","Transformers disfavor high complexity algorithms despite universality","Upper bounds derived on transformer algorithmic capture"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The formal definition of algorithmic capture sharply separates logic internalization from statistical interpolation.","fun_headline_variants_meta":{"raw":{"variants":["Transformer inductive bias limits complex task capture","Analysis bounds capturable complexity in infinite transformers","Transformers disfavor high complexity algorithms despite universality","Upper bounds derived on transformer algorithmic capture"]},"model":"grok-4.3","cost_usd":0.004438,"raw_usage":{"total_tokens":2090,"prompt_tokens":576,"num_sources_used":0,"completion_tokens":52,"cost_in_usd_ticks":44378000,"prompt_tokens_details":{"text_tokens":576,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1462,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":576,"tokens_out":52,"duration_ms":20820,"temperature":1.0,"reasoning_tokens":1462,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-15T13:06:08.545146+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Demonstrating that an infinite transformer captures a higher-complexity polynomial-time task, such as a specific quadratic heuristic, by extrapolating to arbitrary sizes with controllable error and logarithmic samples would falsify the claimed upper bounds.","supporting_citations":[],"review_version":1}