{"id":"fd633e9d-00f0-4e1b-8047-73a3ff6714c8","arxiv_id":"2605.10974","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Vertex-Softmax computes the tightest sound bounds on softmax from pre-softmax score intervals alone via vertex optimization with log-linear complexity and is proven optimal for interval-only information.","lead":"The paper introduces Vertex-Softmax, a method to compute tight bounds on softmax for transformer verification by proving the optimum occurs at vertices of the score interval box and can be found among linearly many candidates after sorting. This yields more precise certified robustness results on image classification attention models at lower computational cost than prior relaxations.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly isolates the scope limitation that is already stated in the paper's optimality result. Because the reduction to O(n) candidates is the only non-obvious step and the tightness claim is definitional once exactness is shown, there is no load-bearing gap that would move the CONDITIONAL verdict.","tokens_in":1735,"tokens_out":336,"duration_ms":102964,"concrete_test":"For n=6, generate 100 random coefficient vectors c and random boxes [l,u]; enumerate all 2^6=64 vertices, compute the true max of c·softmax(s), and confirm it is always equal to the max over the 7 threshold configurations; repeat for the minimization direction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the optimum of a linear functional of softmax(s) subject to independent interval constraints on each coordinate of s is always attained at a vertex, and moreover that after sorting the coefficients the optimum is among the O(n) threshold configurations (prefixes set to upper bound, suffix to lower bound). This yields an exact, log-linear algorithm and, by construction, the tightest bound obtainable from the intervals alone. The argument is internally consistent: the vertex claim follows from the threshold structure (each threshold point is a vertex), the structure theorem is the non-trivial step that reduces the search space, and the optimality characterization explicitly carves out the interval-only setting, correctly identifying what extra information would be needed for further tightening. No hidden assumption about score independence or downstream linearity is smuggled in.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript presents Vertex-Softmax, an exact optimization method for bounding the softmax function in transformer attention layers under interval constraints on the pre-softmax scores. The central contributions are proofs that the optimum is attained at a vertex of the box constraint and that a threshold structure allows checking only O(n) candidates after sorting the coefficients, resulting in a log-linear time algorithm. It also establishes that this bound is the tightest possible using only score intervals and integrates the method into a CROWN-style verifier with soundness guarantees, reporting improved certified accuracies on standard image classification datasets.","tokens_in":1870,"tokens_out":340,"duration_ms":149845,"significance":"This result is significant for the field of certified verification of neural networks, particularly transformers, as it eliminates avoidable slack in softmax relaxations without requiring additional assumptions like score correlations. The formal optimality result helps delineate the boundaries of interval-based verification. If the proofs are correct, the efficiency and tightness could lead to broader adoption in safety-critical applications of attention-based models. The empirical results suggest practical benefits over existing methods like alpha-CROWN.","major_comments":[],"minor_comments":[{"comment":"Abstract: The phrase 'relax softmax ndependently of the downstream objective' contains a likely typo ('ndependently' instead of 'independently').","section":null},{"comment":"Abstract: The parenthetical in 'CROWN Convex Relaxation based Optimization for Worst-case Neurons)-style verifier' appears malformed; it should probably read 'CROWN (Convex Relaxation based Optimization for Worst-case Neurons)-style verifier'.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive summary, recognition of the significance of the optimality and efficiency results for interval-based softmax bounding in transformer verification, and the recommendation of minor revision. No specific major comments were raised in the report.","responses":[],"tokens_in":1231,"tokens_out":64,"duration_ms":99786,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main contribution is a clean optimization result for the score-box problem: the maximum of a linear functional over softmax(s) with s in an interval box is always attained at a vertex, and after sorting the coefficients it lies among only O(n) threshold points (prefix upper, suffix lower). This yields the Vertex-Softmax primitive with log-linear complexity and, by the optimality theorem, the tightest sound bound possible from intervals alone. They correctly flag that correlations or score-value coupling would be needed for anything tighter. That is the new piece; prior relaxations in the verification literature treated softmax independently of the objective and left slack that this removes by construction. The integration into a CROWN-style verifier carries a formal soundness guarantee, and the experiments report higher certified rates plus tighter lower bounds on MNIST, Fashion-MNIST, and CIFAR-10 attention models while running faster than alpha-CROWN or branch-and-bound. The proofs appear internally consistent from the abstract and stress-test note, with no visible circularity or hidden assumptions about independence. The main soft spot is that everything remains interval-only, so real-world score dependence is still ignored; that is not a flaw but a stated boundary. Experiments stay on modest models, which is normal for this stage but leaves scaling questions open. This is for people working on certified robustness for transformers. It deserves a serious referee because it supplies a new, formally grounded primitive with measurable gains rather than another heuristic relaxation.","headline":"Vertex-Softmax gives an exact, log-linear bound on softmax under score intervals by proving vertex attainment and a threshold structure that reduces candidates to linear in sequence length.","tokens_in":2339,"tokens_out":367,"would_cite":true,"duration_ms":38472,"reading_group":"yes","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":"We prove that the exact optimum of this score-box problem is attained at a vertex of the constraint box, and establish a threshold structure theorem showing that, after sorting the objective coefficients, the optimum lies among only linearly many candidates"},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean","rs_theorem":"absolute_floor_iff_bare_distinguishability","paper_passage":"Vertex-Softmax is the tightest sound bound obtainable from score intervals alone"}],"headline":"Orthogonal: exact linear-fractional softmax-box optimization (vertex + threshold structure) unrelated to RS cost-forcing or distinction-derived structures","alignment":"orthogonal","rationale":"The paper's core results (Thm 3.1 vertex exactness of min c^T softmax(s) over score box B; Thm 3.2 reduction to K+1 sorted threshold vertices; Cor 3.3 optimality from intervals alone) operate on linear-fractional programs R(y)=(c·y)/(1·y) over positive boxes and standard CROWN bound propagation. RS derives J(x)=½(x+x^{-1})-1, φ, 8-tick periodicity, D=3 via Alexander duality, and parameter-free constants from a single distinction (reality_from_one_distinction, AbsoluteFloorClosure, Cost.FunctionalEquation, AlphaCoordinateFixation). No shared machinery, no cosh/J-cost identities, no ratio-symmetry forcing, no ladder/periodicity. Domain (ML verification) is outside RS scope.","tokens_in":55262,"confidence":"high","tokens_out":399,"duration_ms":22483,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"The exact optimum of bounding softmax over score intervals occurs at a vertex of the box, enabling a log-linear tight bound for transformer verification.","keywords":["transformer verification","softmax bounds","certified robustness","interval constraints","vertex optimization","attention mechanisms","CROWN"],"falsifier":"Finding a set of score intervals and objective coefficients where the maximizing point for the softmax is not a vertex of the box or is missed by the linear candidate list after sorting.","tokens_in":2638,"feed_emoji":"🔍","tokens_out":626,"duration_ms":206830,"temperature":0.7,"pith_summary":"This paper proves that when bounding the softmax function for transformer verification using only interval constraints on the pre-softmax scores, the exact worst-case value is always achieved at one of the corners of the interval box. A structure theorem shows that sorting the coefficients reduces the number of candidates to check to a linear number in the sequence length, enabling an efficient algorithm called Vertex-Softmax. This bound is the tightest possible using only the intervals, and when used in a verifier it raises the number of certifiably robust inputs on standard image datasets while running faster than alternatives. A reader would care because looser bounds currently limit how much safety can be guaranteed for attention models in practice.","feed_headline":"Vertex optimum solves tight softmax bounding for transformers","feed_subtitle":"Proves the maximum is at a box vertex and needs only linear candidates after sorting, leading to better certified rates on image tasks.","key_machinery":"Vertex-Softmax, the algorithm that finds the exact softmax bound by checking a linear number of sorted vertex candidates in the score interval box.","core_discovery":"We prove that the exact optimum of this score-box problem is attained at a vertex of the constraint box, and establish a threshold structure theorem showing that, after sorting the objective coefficients, the optimum lies among only linearly many candidates, yielding the Vertex-Softmax primitive with log-linear complexity in the sequence length. We further prove a formal optimality result showing that Vertex-Softmax is the tightest sound bound obtainable from score intervals alone.","pith_inferences":["The result implies that further tightening would require exploiting correlations between scores or coupling with output values.","The log-linear scaling supports application to longer sequence lengths in transformers.","Similar vertex-based exact optimization may apply to bounding other activation functions in neural network verifiers."],"forward_implications":["Integrates into CROWN-style verifiers while preserving formal soundness.","Improves certified robustness rates on MNIST, Fashion-MNIST, and CIFAR-10 models.","Tightens lower bounds on worst-case outputs substantially.","Matches or exceeds performance of alpha-CROWN and branch-and-bound at lower cost."],"fun_headline_variants":["Vertex optimum pins exact softmax maximum at box vertex","Threshold theorem limits softmax optimum to linear candidates","Vertex-Softmax yields tightest interval bound for attention","Log-linear vertex method tightens transformer verification"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The exact optimality and tightness results rely on having no additional information beyond independent interval constraints on each score.","fun_headline_variants_meta":{"raw":{"variants":["Vertex optimum pins exact softmax maximum at box vertex","Threshold theorem limits softmax optimum to linear candidates","Vertex-Softmax yields tightest interval bound for attention","Log-linear vertex method tightens transformer verification"]},"model":"grok-4.3","cost_usd":0.003484,"raw_usage":{"total_tokens":1746,"prompt_tokens":651,"num_sources_used":0,"completion_tokens":57,"cost_in_usd_ticks":34840500,"prompt_tokens_details":{"text_tokens":651,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1038,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":651,"tokens_out":57,"duration_ms":10056,"temperature":1.0,"reasoning_tokens":1038,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-13T06:07:15.895511+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Finding a set of score intervals and objective coefficients where the maximizing point for the softmax is not a vertex of the box or is missed by the linear candidate list after sorting.","supporting_citations":[],"review_version":1}